Techniques for automatically freeing space in a log-structured storage system

Patent metadata

Field	Value
Publication number	US-2016253104-A1
Application number	US-201414767387-A
Country	US
Kind code	A1
Filing date	Jun 27, 2014
Priority date	Jun 27, 2014
Publication date	Sep 1, 2016
Grant date	—

Abstract

A method includes (a) writing blocks of data to a storage device, pluralities of the blocks of data being organized into macroblocks, macroblocks having a first fixed size, pluralities of the macroblocks being organized into segments, segments having a second fixed size, (b) marking some of the written blocks as deleted, (c) computing a ratio of storage marked as deleted (SMD) from a segment and storage written (SW) to the segment (ratio SMD:SW), and (d) in response to the computed ratio exceeding a threshold value, performing a compaction operation on the segment. Performing the compaction operation on the segment includes (1) copying blocks which have not been marked as deleted from within macroblocks that contain at least one block marked as deleted to a new macroblock of the first fixed size and (2) in response to copying, marking the macroblocks from which the blocks were copied as free for reuse.

First claim

What is claimed is:

1 . A method of reclaiming storage, the method comprising:
writing blocks of data to a storage device, pluralities of the blocks of data being organized into macroblocks, macroblocks having a first fixed size, pluralities of the macroblocks being organized into segments, segments having a second fixed size; marking some of the written blocks as deleted; computing a ratio of storage marked as deleted (SMD) from a segment and storage written (SW) to the segment (ratio SMD:SW); and in response to the computed ratio exceeding a threshold value, performing a compaction operation on the segment, performing the compaction operation on the segment including:
copying blocks which have not been marked as deleted from within macroblocks that contain at least one block marked as deleted to a new macroblock of the first fixed size; and
in response to copying, marking the macroblocks from which the blocks were copied as free for reuse.

2 . The method of claim 1 wherein computing the ratio includes dividing a number of blocks deleted from the segment by a number of blocks written to the segment.

3 . The method of claim 1 wherein:
writing blocks of data to the storage device includes, for each block written within a segment, incrementing a write counter associated with that segment; and
marking some of the written blocks as deleted includes, for each block deleted within a segment, incrementing a delete counter associated with that segment.

4 . The method of claim 3 wherein computing the ratio of storage marked as deleted from the segment and storage written to the segment includes performing a division operation by dividing the delete counter associated with that segment by the write counter associated with that segment.

5 . The method of claim 4 wherein computing the ratio includes repeatedly performing the division operation for that segment upon iterating through all other segments of the data storage device.

6 . The method of claim 4 wherein computing the ratio includes repeatedly performing the division operation for that segment every time a predefined number of combined write and delete operations are performed on that segment.

7 . The method of claim 1 wherein:
writing blocks of data to the storage device includes, for each block written within a segment, updating a block use metadata bitmap associated with the macroblock into which that block is organized to indicate that that block stores active data;
marking some of the written blocks as deleted includes, for each block deleted within a segment, updating the block use metadata bitmap associated with the macroblock into which that block is organized to indicate that that block does not store active data; and
performing the compaction operation on the segment further includes identifying the macroblocks that contain at least one block marked as deleted by counting, for each macroblock, whether the block use metadata bitmap for that macroblock indicates the presence of any blocks without active data.

8 . The method of claim 7 wherein:
at least one macroblock organized into the segment contains a predefined number of uncompressed blocks, the block use metadata bitmap associated with the at least one macroblock including exactly the predefined number of bit entries, each bit entry indicating whether or not a respective block stores active data; and
for the at least one macroblock , counting whether the block use metadata bitmap for that macroblock indicates the presence of any blocks without active data includes determining whether or not the block use metadata bitmap associated with the at least one macroblock contains any bit entries indicating that a block does not store active data.

9 . The method of claim 7 wherein:
at least one macroblock organized into the segment contains a variable number of compressed blocks, the block use metadata bitmap associated with the at least one macroblock including a number of bit entries equal to a maximum number of compressed blocks allowed per macroblock, each bit entry up to the variable number indicating whether or not a respective block stores active data;
the at least one macroblock includes a metadata header, the metadata header storing a compressed size for each compressed block within the at least one macroblock; and
for the at least one macroblock , counting whether the block use metadata bitmap for that macroblock indicates the presence of any blocks without active data includes:
calculating the variable number of compressed blocks within the at least one macroblock with reference to the metadata header of the at least one macroblock; and
determining whether or not the block use metadata bitmap associated with the at least one macroblock contains any bit entries up to the calculated variable number indicating that a block does not store active data.

10 . The method of claim 9 wherein copying blocks which have not been marked as deleted from within macroblocks that lack at least one block marked as deleted to the new macroblock of the first fixed size include:
copying a compressed block from within the at least one macroblock to the new macroblock; and
selecting additional compressed blocks from the at least one macroblock and other macroblocks in order to efficiently fill the new macroblock with minimal wasted space.

11 . The method of claim 1 wherein the first fixed size is 64 kilobytes and the second fixed size is 2 megabytes.

12 . The method of claim 1 wherein the first fixed size is 1 megabyte and the second fixed size is 128 megabytes.

13 . The method of claim 1 wherein:
writing blocks of data to the storage device includes, for each block written:
assigning a unique address to that block, the unique address identifying the macroblock into which that block is organized and a position of that block within the macroblock;
sending the unique address of that block to an application which is responsible for writing that block; and
storing, within metadata for that block, a backpointer to the application which is responsible for writing that block; and

the method further includes, prior to marking the macroblocks from which the blocks were copied as free for reuse:
assigning a new unique address to that block within the new macroblock, the new unique address identifying the new macroblock and a position of that block within the new macroblock;
extracting the backpointer to the application which is responsible for writing that block from within the metadata for that block;
sending the new unique address of that block to the application which is responsible for writing that block, with reference to the backpointer; and
storing, within new metadata for that block within the new macroblock, the backpointer to the application which is responsible for writing that block.

14 . The method of claim 1 wherein the method further includes prioritizing a segment for compaction by ordering segments by calculated from highest to lowest, the segment with the highest ratio being selected for earliest compaction.

15 . A computer program product comprising a non-transitory computer-readable storage medium storing a set of instructions, which, when performed by a computing device, cause the computing device to perform the following operations:
writing blocks of data to a storage device, pluralities of the blocks of data being organized into macroblocks, macroblocks having a first fixed size, pluralities of the macroblocks being organized into segments, segments having a second fixed size; marking some of the written blocks as deleted; computing

Assignees

• Emc Corp

Inventors

• Romanovskiy Alexey Valentinovich

Classifications

• G06F12/123

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title

• G06F2212/608

  Details relating to cache mapping · CPC title

• G06F3/0652

  Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket · CPC title

• G06F3/064

  Management of blocks · CPC title

• G06F3/0673

  Single storage device · CPC title