# US 2016/0253104 A1 · Techniques for automatically freeing space in a log-structured storage system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2016/0253104 A1
- Document ID: US20160253104A1
- Status: Published application
- Kind: A1
- Application number: 14/767,387
- Filed: 2014-06-27
- Published: 2016-09-01
- Earliest claimed: 2014-06-27
- Assignees: EMC Corporation
- Applicants: Emc Corporation
- Inventors: Alexey Valentinovich Romanovskiy
- Web page: https://patentgrep.com/patent/US20160253104A1

## CPC

- G06F 3/0661: {Format or protocol conversion arrangements}
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/064: {Management of blocks}
- G06F 3/065: {Replication mechanisms}
- G06F 3/0652: {Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 3/0673: {Single storage device}
- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G06F 12/0261: {using reference counting}
- G06F 12/0855: Overlapped cache accessing, e.g. pipeline (G06F12/0846 takes precedence)
- G06F 12/0868: Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
- G06F 12/0871: Allocation or management of cache space
- G06F 12/0873: Mapping of cache memory to specific storage devices or parts thereof
- G06F 12/123: with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
- G06F 2212/1024: Latency reduction
- G06F 2212/1044: Space efficiency improvement
- G06F 2212/281: Single cache
- G06F 2212/313: In storage device
- G06F 2212/401: Compressed data
- G06F 2212/461: Sector or disk block
- G06F 2212/608: Details relating to cache mapping
- G06F 2212/7205: Cleaning, compaction, garbage collection, erase control
- G06F 2212/7207: management of metadata or control data
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 3)

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.

### Claim 5 (depends on 4)

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.

### Claim 6 (depends on 4)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 7)

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.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 1)

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

### Claim 12 (depends on 1)

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

### Claim 13 (depends on 1)

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.

### Claim 14 (depends on 1)

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.

### Claim 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 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.

### Claim 16

An apparatus comprising:
persistently-backed system memory;
a data storage device; and
processing circuitry configured to perform the following operations:
writing blocks of data to the data 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, within the persistently-backed system memory, 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.