Coalescing transactional same-block writes for virtual block maps

Patent metadata

Field	Value
Publication number	US-9430503-B1
Application number	US-201313929999-A
Country	US
Kind code	B1
Filing date	Jun 28, 2013
Priority date	Jun 28, 2013
Publication date	Aug 30, 2016
Grant date	Aug 30, 2016

Abstract

A technique for preserving metadata changes in a transaction log involves coalescing metadata changes based on the block of storage in which the metadata to be changed resides. Metadata change information that accompanies a file system command is stored in nodes of a searchable data structure, wherein each node accumulates metadata changes for a respective block of storage. Once all metadata changes are specified in the searchable data structure, or after some threshold number of metadata changes have been stored, the storage processor composes a transaction for each node summarizing the metadata changes and writes the transaction to the transaction log.

First claim

What is claimed is:

1. In a storage system including a storage device and a storage processor, a method of preserving metadata changes in a transaction log, the method comprising:
in response to a request to perform a file system operation on a file stored in the storage device, identifying, by the storage processor, a set of metadata change instructions that accompany the file system operation on the file;
arranging metadata change information specified in the set of metadata change instructions among multiple nodes of a searchable data structure, each of the multiple nodes accumulating metadata change information to be recorded in a respective block of storage in the storage device, such that each node of the searchable data structure accumulates metadata change information for a different block of the storage device; and
for each node of the set of nodes, writing the accumulated metadata change information to the transaction log,
wherein each respective block of storage in which metadata change information is to be recorded stores multiple elements of metadata, such that each node of the searchable data structure corresponds to a respective block of storage and to respective metadata elements,
wherein, when arranging the metadata change information, accumulating metadata change information to be recorded in a respective block of storage includes accumulating changes in greater than one of the metadata elements stored in that block of storage, and
wherein accumulating the metadata change information in each node of the searchable data structure includes accumulating elements of metadata in respective bits of a bitmap, the bitmap providing a respective bit for each of the elements of metadata.

2. A method as in claim 1 ,
wherein the storage device stores multiple virtual block map (VBM) blocks, each VBM block including multiple VBM entries, each VBM entry including a VBM pointer pointing to a block of the storage device;
wherein each of the set of metadata change instructions includes a block identifier identifying a VBM block in the storage device; and
wherein arranging the set of metadata change instructions in multiple nodes of the searchable data structure includes reading, from each of the set of metadata change instructions, the block identifier identifying the respective VBM block.

3. A method as in claim 2 ,
wherein the searchable data structure is a binary tree; and
wherein arranging the set of metadata change instructions in multiple nodes of the searchable data structure further includes:
for each of the metadata change instructions, traversing at least a portion of the binary tree to determine whether the block identifier of the VBM block specified in the metadata change instruction is already represented in a node of the binary tree,
for each metadata change instruction for which the block identifier is already represented in a node the binary tree, updating the respective node of the binary tree to reflect the metadata change instruction, and
for each metadata change instruction for which the block identifier is not already represented in a node of the binary tree, generating a new node in the binary tree and updating the new node of the binary tree to reflect the metadata change instruction.

4. A method as in claim 3 ,
wherein the binary tree is an Adelson-Velskii and Landis (AVL) tree; and
wherein the method further comprises:
after deleting a node of the AVL tree, when leaf nodes of the AVL tree have a difference in height of more than one level, rotating the nodes of the AVL tree so that the leaf nodes have at most one hierarchal level difference in height.

5. A method as in claim 2 , further comprising:
prior to writing the accumulated metadata change instructions to the transaction log, composing, for each node of the searchable data structure, a transaction representing the metadata change instructions accumulated in the respective node;
wherein writing the accumulated metadata change instructions to the transaction log includes writing each composed transaction to the transaction log.

6. A method as in claim 5 , further comprising:
counting a number of metadata change instructions accumulated in the searchable data structure, and
comparing the counted number of metadata change instructions with a threshold number of metadata change instructions, wherein the accumulated metadata change information is written to the transaction log when the number of metadata change instructions exceeds the threshold number of metadata change instructions; and
removing nodes from the searchable data structure after the accumulated metadata change information in the respective nodes is written to the transaction log.

7. A method as in claim 2 ,
wherein each of the multiple nodes of the searchable data structure includes multiple bitmaps for tracking metadata change information pertaining to a respective block of the storage medium;
wherein arranging the set of metadata change instructions in the multiple nodes of the searchable data structure includes updating the bitmaps for tracking the metadata change information in different nodes of the searchable data structure.

8. A method as in claim 7 ,
wherein the multiple bitmaps for each of the multiple nodes of the searchable data structure include i) an allocated bitmap, ii) a to be committed bitmap, iii) a to be modified bitmap, and iv) a to be freed bitmap.

9. A method as in claim 8 ,
wherein writing the accumulated metadata change information to the transaction log includes:
grouping the bitmaps written into a node of the searchable data structure into a log descriptor entry; and
transferring the log descriptor entry to the transaction log.

10. A method as in claim 1 , wherein each of the multiple nodes of the searchable data structure includes a to be committed bitmap for tracking metadata change information pertaining to a respective block of the storage medium.

11. A storage system for preserving metadata changes in a transaction log, the storage system comprising:
a storage device; and
a storage processor, the storage processor including:
memory; and
a set of processors coupled to the memory to form control circuitry, the control circuitry constructed and arranged to:
in response to a request to perform a file system operation on a file stored in the storage device, identify a set of metadata change instructions that accompany the file system operation on the file;
arrange the set of metadata change instructions in multiple nodes of a searchable data structure, each of the multiple nodes accumulating metadata changes specified in metadata change instructions to be recorded in a respective block of storage in the storage device, such that each node of the searchable data structure accumulates metadata change information for a different block of the storage device; and
for each node of the set of nodes, write the accumulated metadata change information to the transaction log,

wherein each respective block of storage in which metadata change information is to be recorded stores multiple elements of metadata, such that each node of the searchable data structure corresponds to a respective block of storage and to respective metadata elements,
wherein, when arranging the metadata change information, the control circuitry accumulating metadata change information to be recorded in a respective block of storage is constructed and arranged to accumulate changes in greater than one of the metadata elements stored in that block of storage, and
wherein accumulating the metadata change information in each node of the searchable data structure, the control circuitry is constructed and arranged to accum

Assignees

• Emc Corp

Inventors

• Delgado Diane M
• Yetto Lawrence
• Karaban Alexei
• Davenport William C
• Armangau Philippe

Classifications

• G06F17/30289 Primary

  Physics · mapped topic

• G06F16/14 Primary

  Details of searching files based on file metadata · CPC title

• G06F16/1865

  Transactional file systems · CPC title

• G06F16/21 Primary

  Design, administration or maintenance of databases · CPC title