Metadata structures for low latency and high throughput inline data compression

Patent metadata

Field	Value
Publication number	US-9612774-B2
Application number	US-201414770566-A
Country	US
Kind code	B2
Filing date	Dec 23, 2014
Priority date	Jun 27, 2014
Publication date	Apr 4, 2017
Grant date	Apr 4, 2017

Abstract

Improved techniques of managing storage in a data storage system involve compressing a subset of block and macroblock metadata. Advantageously, a data storage system operating according to the improved techniques is able to store more metadata in volatile memory even for huge data objects.

First claim

What is claimed is:

1. A method of managing storage in a data storage system, the method comprising:
writing data blocks to a storage device of the data storage system, pluralities of the data blocks being organized into macroblocks having a fixed size;
generating macroblock metadata describing the data blocks organized in the macroblocks;
compressing a subset of the macroblock metadata;
in response to an access request, decompressing a portion of the subset of the macroblock metadata that was compressed; and
providing access to data blocks organized in the macroblocks using the decompressed portion of the subset of the macroblock metadata.

2. A method as in claim 1 , further comprising:
generating block metadata describing the data blocks written to the storage device;
compressing a subset of the block metadata;
in response to an access request, decompressing a portion of the subset of the block metadata that was compressed; and
providing access to data blocks using the decompressed portion of the subset of the block metadata and the decompressed portion of the subset of the macroblock metadata.

3. A method as in claim 2 , further comprising:
prior to writing the data blocks to the storage device, receiving a data block to be written to the storage device, performing an inline compression operation on the data block; and
storing the data block in a macroblock in a macroblock buffer;
wherein generating the macroblock metadata includes producing a bitmap of a set of bitmaps in response to storing the data block in the macroblock, a bitmap of the set of bitmaps indicating (i) whether a macroblock contains compressed data and (ii) which data blocks organized in the macroblock are being used.

4. A method as in claim 3 , wherein compressing the subset of the macroblock metadata includes:
writing the subset of the macroblock metadata to the macroblock buffer; and
performing the inline compression operation on the macroblock metadata; and
wherein compressing the subset of the block metadata includes performing the inline compression operation on the block metadata.

5. A method as in claim 3 , wherein a portion of the block and macroblock metadata is arranged in a sparse array of slots, each of the slots of the sparse array having a pointer, the value of the pointer being one of (i) a pointer to a bitmap-array-in-use or (ii) a null pointer, the bitmap-array-in-use containing bitmaps of the set of bitmaps, the null pointer indicating an available slot; and
wherein writing the subset of the macroblock metadata to the location in the storage device includes:
identifying a slot pointing to a least-recently-used bitmap array;
writing the bitmaps contained in the least-recently-used bitmap array to the location in the storage device; and
setting the pointer of the identified slot to the null pointer.

6. A method as in claim 5 , wherein each of the slots of the sparse array includes a timestamp indicating the most recent time at which one of bitmaps of the bitmap array to which that slot points was written to;
wherein each of the slots of the sparse array having a pointer to a bitmap array in use further includes a dirty data indicator indicating whether the bitmap array contains data that is not stored in the storage device; and
wherein identifying the slot pointing to the least-recently-used bitmap array includes finding the slot of the array of slots with the oldest timestamp having a dirty data indicator indicating that the bitmap array contains data not stored in the storage device.

7. A method as in claim 6 , wherein the method further comprises:
writing, in a macroblock stored in a location in the storage device, the bitmaps contained in the slot pointing to the least-recently-used bitmap array and having the dirty data indicator indicating that the bitmap array contains data that is not stored in the storage device;
wherein the method further comprises generating a logical block number indicating the location in the storage device at which the macroblock to which the bitmaps were written is stored; and
wherein decompressing the portion of the compressed subset of the macroblock metadata includes accessing the compressed bitmap array at the location indicated by the logical block number returned to the slot.

8. A method as in claim 7 , wherein generating the macroblock metadata further includes, in response to storing the data block in the macroblock and writing the macroblock to the storage device, producing an inline compression (IC) key indicating (i) a location in the storage device where the macroblock that contains the data block was written and (ii) a location of the data block within the macroblock that contains the data block.

9. A method as in claim 8 , further comprising:
receiving a request to overwrite data stored in the data block;
retrieving the IC key produced in response to storing the data block in the macroblock and writing the macroblock to the storage device;
locating the data block from the retrieved IC key;
copying the data block to a location in another macroblock, the other macroblock stored at another location in the storage device;
producing a new IC key indicating the location of the other macroblock in the storage device and the location of the copied data block within the other macroblock; and
overwriting the data in the copied data block.

10. A method as in claim 8 , wherein the data stored in the data block is referenced by a first file system data structure;
wherein the method further comprises performing a sharing operation to share the data stored in the data block with a second file system data structure, wherein performing the sharing operation includes:
generating a backpointer that identifies another data block that stores the data, the other data block being reference by the second file system data structure; and
storing the backpointer in a backpointer array; and

wherein compressing the subset of the block metadata includes:
compressing a subset of the backpointer array;
writing the compressed subset of the backpointer array to a macroblock stored in the storage device; and
in response to the writing, returning a logical block number to a slot of the sparse array of slots.

11. A method as in claim 10 , wherein decompressing the portion of the subset of the block metadata that was compressed includes:
reading the logical block number to find the macroblock in which the compressed subset of the backpointer was written, and decompressing the compressed subset of the backpointer; and
wherein providing access to the data blocks organized in the macroblocks using the decompressed portion of the subset of the block metadata includes reading a backpointer of the backpointer array to find the data stored in the other data block.

12. A computer program product comprising a non-transitory computer-readable storage medium storing a set of instructions which, when performed by a computer device, cause the computing device to perform the following operations:
writing data blocks to the storage medium, pluralities of the data blocks being organized into macroblocks having a fixed size;
in response to writing the data blocks, generating macroblock metadata describing the data blocks organized in the macroblocks;
compressing a subset of the macroblock metadata;
in response to an access request, decompressing a portion of the subset of the macroblock metadata that was compressed; and
providing access to data blocks organized in the macroblocks using the decompressed portion of the subset of the macroblock metadata.

13. A computer program product as in claim 12 , wherein the

Assignees

• Emc Corp
• Emc Ip Holding Co Llc

Inventors

• Romanovskiy Alexey Valentinovich

Classifications

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F12/0871

  Allocation or management of cache space · CPC title

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F2212/7207

  management of metadata or control data · CPC title