Garbage collection scope detection for distributed storage

Patent metadata

Field	Value
Publication number	US-10061697-B2
Application number	US-201615193142-A
Country	US
Kind code	B2
Filing date	Jun 27, 2016
Priority date	Dec 16, 2015
Publication date	Aug 28, 2018
Grant date	Aug 28, 2018

Abstract

Systems and methods for determining garbage collection (GC) scope in a distribute storage system using chunk-based storage. The systems and methods are compatible with multi-version concurrency control (MVCC) semantics.

First claim

What is claimed is:

1. A method for use with a distributed storage system comprising a plurality of storage devices, the method comprising:
initializing a garbage collection (GC) front value as the maximum sequence number associated with a storage chunk within a set of consecutively sealed storage chunks, the storage chunks corresponding to storage capacity allocated within the storage devices and having associated sequence numbers;
using the GC front value to determine GC scope, the GC scope including zero or more of the storage chunks;
retrieving metadata information about the GC scope storage chunks;
identifying unreferenced storage chunks from the GC scope storage chunks using the metadata information; and
reclaiming storage capacity corresponding to the unreferenced storage chunks.

2. The method of claim 1 further comprising:
sealing additional storage chunks; and
advancing the GC front value if the additional sealed storage chunk have sequence numbers consecutive to a previous GC front value.

3. The method of claim 2 wherein the storage chunks are used to store search tree elements, wherein advancing the GC front value comprises advancing the GC front value unless a search tree is being updated.

4. The method of claim 3 further comprising:
setting a first GC front block when a first search tree update commences; and
setting a second GC front block when a second search tree update commences,
wherein advancing the GC front value comprises advancing the GC front value after the first search tree update completes to the value of the second GC front block.

5. The method of claim 2 wherein sealing additional storage chunks comprises sealing additional storage chunks in response to a timeout expiring.

6. The method of claim 1 wherein retrieving metadata information about the GC candidate storage chunks comprises looking up metadata information in a metadata table using storage chunk sequence numbers.

7. A distributed storage system comprising:
a plurality of storage devices;
two or more storage nodes configured to:
initialize a garbage collection (GC) front value as the maximum sequence number associated with a storage chunk within a set of consecutively sealed storage chunks, the storage chunks corresponding to storage capacity allocated within the storage devices and having associated sequence numbers;
use the GC front value to determine GC scope, the GC scope including zero or more of the storage chunks;
retrieve metadata information about the GC scope storage chunks;
identify unreferenced storage chunks from the GC scope storage chunks using the metadata information; and
reclaim storage capacity corresponding to the unreferenced storage chunks.

8. The distributed storage system of claim 7 wherein the two or more storage nodes are further configured to:
seal additional storage chunks; and
advance the GC front value if the additional sealed storage chunk have sequence numbers consecutive to a previous GC front value.

9. The distributed storage system of claim 8 wherein the storage chunks are used to store search tree elements, wherein the two or more storage nodes are configured to advance the GC front value unless a search tree is being updated.

10. The distributed storage system of claim 9 wherein the two or more storage nodes are configured to:
set a first GC front block when a first search tree update commences;
set a second GC front block when a second search tree update commences; and
advance the GC front value after the first search tree update completes to the value of the second GC front block.

11. The distributed storage system of claim 8 wherein the two or more storage nodes are configured to seal additional storage chunks in response to a timeout expiring.

12. The distributed storage system of claim 7 wherein the two or more storage nodes are configured lookup metadata information in a metadata table using storage chunk sequence numbers.

Assignees

• Emc Corp
• Emc Ip Holding Co Llc

Inventors

• Danilov Mikhail
• Srivastav Shashwat
• Malygin Mikhail
• Wang Chen
• Tchoub Ivan

Classifications

• G06F3/0683

  Plurality of storage devices · CPC title

• G06F17/30327

  Physics · mapped topic

• G06F12/0261 Primary

  using reference counting · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title