Method and system for distributed garbage collection of deduplicated datasets

Patent metadata

Field	Value
Publication number	US-11301374-B2
Application number	US-201916257062-A
Country	US
Kind code	B2
Filing date	Jan 24, 2019
Priority date	Mar 31, 2016
Publication date	Apr 12, 2022
Grant date	Apr 12, 2022

Abstract

Embodiments relating to garbage collection for a deduplicated and compressed storage device are described. One embodiment provides for a computer implemented method including creating a multiple sets of Bloom filters distributed across a set of multiple computing device nodes. One set of Bloom filters stores differing ranges of fingerprints for data stored on deduplicated storage containers, while a second set of Bloom filters includes a set of fingerprints correlated with files in a file system directory structure. A set of live fingerprints is determined for live fingerprints and storage segments associated with those fingerprints are copied to new storage containers.

First claim

What is claimed is:

1. A computer implemented method for distributed garbage collection of deduplicated datasets, the method comprising:
determining a set of live fingerprints for each of one or more deduplicated storage containers, wherein for each of the deduplicated storage containers, the set of live fingerprints includes a fingerprint stored on the storage container that is associated with a file in a file system directory structure, wherein the determining of the set of live fingerprints includes
determining, by performing a query into each Bloom filter in a set of Bloom filters, whether that Bloom filter is associated with a container identifier (CID) for each fingerprint in a fingerprint index associated with the deduplicated storage containers, and
inserting each fingerprint and CID pair into the set of live fingerprints, in response to determining that Bloom filter is associated with the CID; and

performing garbage collection operations by copying a storage segment having a fingerprint in the set of live fingerprints from the one or more deduplicated storage containers to one or more new storage containers.

2. The method as in claim 1 , further comprising:
enumerating a set of data deduplication fingerprints for data stored on the deduplicated storage containers; and
storing a first candidate fingerprint in a first Bloom filter in the set of Bloom filters, wherein the first candidate fingerprint has an identifier in a range associated with the first Bloom filter.

3. The method as in claim 2 , wherein each node stores a separate Bloom filter in the set of Bloom filters, each Bloom filter associated with a disjoint range of fingerprint identifiers.

4. The method as in claim 3 , further comprising enumerating the first candidate fingerprint on a first node in a set of computing device nodes and storing the first candidate fingerprint on the Bloom filter stored on the first node, wherein the first candidate fingerprint has an identifier in a range associated with Bloom filter stored on the first node.

5. The method as in claim 3 , further comprising enumerating the first candidate fingerprint on a first node in the set of computing device nodes and transmitting the first candidate fingerprint to a second node, the first candidate fingerprint having an identifier in a range associated with the Bloom filter stored on the second node.

6. The method as in claim 3 , further comprising:
enumerating the first candidate fingerprint on a first node in the set of multiple computing device nodes;
storing the first candidate fingerprint on the Bloom filter stored on the first node, wherein the first candidate fingerprint has an identifier in a range associated with Bloom filter stored on the first node;
enumerating a second candidate fingerprint on the first node;
transmitting the second candidate fingerprint to a second node, the second candidate fingerprint having an identifier in a range associated with the Bloom filter stored on the second node; and
storing the second candidate fingerprint in the Bloom filter stored on the second node.

7. The method as in claim 1 , further comprising creating the set of Bloom filters, including:
correlating a fingerprint in a Bloom filter of the set of Bloom filters with a fingerprint referenced by a file of the file system directory structure, the fingerprint referencing a storage segment within the deduplicated storage containers; and
storing the fingerprint in a Bloom filter of the set of Bloom filters.

8. The method as in claim 1 , further comprising deleting one or more deduplicated storage containers including live content that has been copied forward to new containers.

9. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations, the operations comprising:
determining a set of live fingerprints for each of one or more deduplicated storage containers, wherein for each of the deduplicated storage containers, the set of live fingerprints includes a fingerprint stored on the storage container that is associated with a file in a file system directory structure, wherein the determining of the set of live fingerprints includes
determining, by performing a query into each Bloom filter in a set of Bloom filters, whether that Bloom filter is associated with a container identifier (CID) for each fingerprint in a fingerprint index associated with the deduplicated storage containers, and
inserting each fingerprint and CID pair into the set of live fingerprints, in response to determining that Bloom filter is associated with the CID; and

performing garbage collection operations by copying a storage segment having a fingerprint in the set of live fingerprints from the one or more deduplicated storage containers to one or more new storage containers.

10. The machine-readable medium as in claim 9 , wherein the operations further comprise:
enumerating a set of data deduplication fingerprints for data stored on the deduplicated storage containers; and
storing a first candidate fingerprint in a first Bloom filter in the set of Bloom filters, wherein the first candidate fingerprint has an identifier in a range associated with the first Bloom filter.

11. The machine-readable medium as in claim 10 , wherein each node stores a separate Bloom filter in the set of Bloom filters, each Bloom filter associated with a disjoint range of fingerprint identifiers.

12. The machine-readable medium as in claim 11 , wherein the operations further comprise enumerating the first candidate fingerprint on a first node in a set of computing device nodes and storing the first candidate fingerprint on the Bloom filter stored on the first node, wherein the first candidate fingerprint has an identifier in a range associated with Bloom filter stored on the first node.

13. The machine-readable medium as in claim 11 , wherein the operations further comprise enumerating the first candidate fingerprint on a first node in the set of computing device nodes and transmitting the first candidate fingerprint to a second node, the first candidate fingerprint having an identifier in a range associated with the Bloom filter stored on the second node.

14. The machine-readable medium as in claim 11 , wherein the operations further comprise:
enumerating the first candidate fingerprint on a first node in the set of multiple computing device nodes;
storing the first candidate fingerprint on the Bloom filter stored on the first node, wherein the first candidate fingerprint has an identifier in a range associated with Bloom filter stored on the first node;
enumerating a second candidate fingerprint on the first node;
transmitting the second candidate fingerprint to a second node, the second candidate fingerprint having an identifier in a range associated with the Bloom filter stored on the second node; and
storing the second candidate fingerprint in the Bloom filter stored on the second node.

15. The machine-readable medium as in claim 9 , wherein the operations further comprise creating the set of Bloom filters, including:
correlating a fingerprint in a Bloom filter of the set of Bloom filters with a fingerprint referenced by a file of the file system directory structure, the fingerprint referencing a storage segment within the deduplicated storage containers; and
storing the fingerprint in a Bloom filter of the set of Bloom filters.

16. The machine-readable medium as in claim 9 , wherein the operations further comprise deleting one or more deduplicated storage containers including live content tha

Assignees

• Emc Ip Holding Co Llc

Inventors

• Wallace Grant

Classifications

• G06F2212/7205

  Cleaning, compaction, garbage collection, erase control · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title

• G06F2212/1032

  Reliability improvement, data loss prevention, degraded operation etc · CPC title

• G06F2212/401

  Compressed data · CPC title

• G06F3/06

  Digital input from, or digital output to, record carriers {, e.g. RAID, emulated record carriers or networked record carriers} · CPC title