GARBAGE COLLECTION AND HOTSPOTS RELIEF FOR A DATA DEDUPLICATION CHUNK STORE

• US 20120159098A1
• Filed: 12/17/2010
• Published: 06/21/2012
• Est. Priority Date: 12/17/2010
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cheung, Chun Ho (Ian), Oltean, Paul Adrian, Benton, James Robert
• Application Number:
  US12/971,694
• Publication Number:
  US 20120159098A1
• Time in Patent Office: Days
• US Class Current: 711/162
• CPC Class Codes: G06F 12/0261 using reference counting

Abstract

Techniques for garbage collecting unused data chunks in storage are provided. According to one implementation, data chunks stored in a chunk container that are unused are identified based an analysis of one or more stream map chunks indicated as deleted. The identified data chunks are indicated as deleted. The storage space in the chunk container filled by the data chunks indicated as deleted may then be reclaimed. Techniques for selectively backing up data chunks are also provided. According to one implementation, a data chunk is received for storing in a chunk container. A backup copy of the received data chunk is stored in a backup container if the received data chunk is in a predetermined top percentage of most referenced data chunks in the chunk container and has a number of references greater than a predetermined reference threshold.

Claims

1. A method for garbage collecting a chunk store, the chunk store including data stored as a plurality of data chunks, the plurality of data chunks including stream map chunks, each stream map chunk corresponding to a stream map for a corresponding data stream and referencing data chunks stored in one or more chunk containers of the chunk store that are included in the corresponding data stream, the method comprising:

identifying data chunks stored in the one or more chunk containers that are unused based on being referenced only by stream map chunks indicated as deleted;

indicating the identified data chunks as deleted; and

reclaiming storage space in the one or more chunk containers containing the data chunks indicated as deleted.

2. The method of claim 1, wherein each stream map chunk references data chunks stored in the one or more chunk containers by corresponding data chunk identifiers, said identifying comprises:

scanning a plurality of stream map chunks to determine any stream map chunks not indicated as deleted;

including data chunk identifiers referenced by each stream map chunk indicated as not deleted in a data structure;

scanning the plurality of stream map chunks to determine any stream map chunks indicated as deleted; and

determining any data chunk identifiers referenced by the stream map chunks determined to be indicated as deleted that are not included in the data structure.

3. The method of claim 2, wherein said indicating comprises:

indicating as deleted the data chunks corresponding to the data chunk identifiers determined to be referenced by the stream map chunks indicated as deleted and that are not included in the data structure.

4. The method of claim 1, wherein each stream map chunk references data chunks stored in the one or more chunk containers by corresponding data chunk identifiers, said identifying comprises:

scanning at least one delete log to determine any stream map chunks not indicated as deleted;

including data chunk identifiers referenced by each stream map chunk indicated as not deleted in a data structure;

generating a deletion bitmap that indicates a plurality of stream map chunks of one or more stream containers, indicates the stream map chunks indicated as not deleted, and indicates other stream map chunks as deleted;

deleting the scanned at least one delete log;

scanning the deletion bitmap to determine any stream map chunks indicated as deleted; and

determining any data chunk identifiers referenced by the stream map chunks determined to be indicated as deleted that are not included in the data structure.

5. The method of claim 1, wherein said reclaiming comprises:

copying each data chunk not indicated as deleted in the chunk container to a new container; and

populating a redirection table of the new container to map a first chunk identifier in the chunk container to a second chunk identifier in the new container for each copied data chunk.

6. The method of claim 5, wherein the chunk store includes a hash index that stores a plurality of hash index entries, wherein each hash index entry of the hash index maps a data chunk identifier to a hash of a corresponding data chunk, wherein said reclaiming further comprises:

modifying at least one entry of the hash index by replacing the data chunk identifier in the hash entry with the new data chunk identifier obtained from the redirection table and chunk headers of the data chunks.

7. The method of claim 5, further comprising:

for each stream map chunk of the chunk store,

locating one or more referenced data chunks in one or more redirection tables of one or more chunk containers of the chunk store by corresponding data chunk identifiers stored in the stream map chunk for the referenced data chunks, and

appending the data chunk identifier in the stream map chunk for each of the one or more referenced data chunks located in the one or more redirection tables of the one or more chunk containers with the corresponding new data chunk identifier in the one or more redirection tables of the one or more chunk containers.

8. The method of claim 7, wherein said appending comprises:

appending data chunk identifiers in place in the stream map chunk in the chunk container.

9. The method of claim 7, wherein said appending comprises:

generating a second chunk container that includes the stream map chunk; and

appending data chunk identifiers in the stream map chunk in the second chunk container, the second chunk container being a stream map container.

10. A method for efficient data backup in a chunk store that stores a plurality of data streams in the form of data chunks, each data stream stored as a stream map that references data chunks of the data stream in a chunk container of the chunk store, the method comprising:

receiving a data chunk for storing in a chunk container;

determining whether the received data chunk is in a predetermined top percentage of most referenced data chunks in the chunk container, has a number of references greater than a predetermined heuristic that includes a predetermined reference threshold, and is not replicated for backup; and

storing a backup copy of the received data chunk in a backup container if the received data chunk is determined to be in the predetermined top percentage and/or to have a number of references greater than the predetermined reference threshold, and to not be replicated for backup.

11. The method of claim 10, wherein said determining comprises:

determining whether the received data chunk is a duplicate of a data chunk stored in the chunk container;

if the received data chunk is determined to be a duplicate, determining whether the received data chunk has an entry in a reference count table;

if the received data chunk is determined to be a duplicate and to have an entry in the reference count table, modifying a reference count value in the entry for the received data chunk in the reference count table; and

if the received data chunk is determined to be a duplicate and to not have an entry in the reference count table, adding an entry for the received data chunk to the reference count table that includes a data chunk identifier for the received data chunk, a reference count value for the received data chunk that is a sum of an initial reference count value and an expected count value, an indication that the reference count value for the received data chunk is not an exact value, and an indication that the received data chunk is not replicated in a backup container.

12. The method of claim 11, wherein said determining whether the received data chunk is in a predetermined top percentage of most referenced data chunks in the chunk container and/or has a number of references greater than a predetermined reference threshold further comprises:

adding an entry for the received data chunk to the reference count table if the received data chunk is determined to not be a duplicate, the entry for the received data chunk including a data chunk identifier for the received data chunk, an initial reference count value for the received data chunk, an indication that the reference count value for the received data chunk is an exact value, and an indication that the received data chunk is not replicated in the backup container.

13. The method of claim 11, wherein said determining whether the received data chunk is in a predetermined top percentage of most referenced data chunks in the chunk container and/or has a number of references greater than a predetermined reference threshold further comprises:

determining whether the received data chunk is replicated in the backup container; and

if the received data chunk is determined to not be replicated in the backup container,

determining whether the received data chunk has a reference count value that is greater than a minimum reference count value for already replicated data chunks, and/or

determining whether the reference count value of the received data chunk is greater than a predetermined threshold.

14. The method of claim 13, wherein said storing comprises:

if the received data chunk is determined to not be replicated in the backup container, is determined to have a reference count value that is greater than the minimum reference count value for already replicated data chunks, and/or to have a reference count value greater than the predetermined threshold,

storing a backup copy of the received data chunk in the backup container, and

modifying the entry in the reference count table for the received data chunk to include an indication that the received data chunk is replicated in the backup container.

15. The method of claim 14, further comprising:

determining that the reference count table has reached a predetermined size;

reconsolidating the reference count table to maintain entries for data chunks having reference count values in a top predetermined percentage and/or greater than the predetermined threshold; and

storing a backup copy of data chunks in the backup container for data chunks not present in the backup container and having entries in the reconsolidated reference count table.

16. The method of claim 15, wherein said reconsolidating comprises:

generating a second reference count table that includes a subset of the entries for data chunks of the first reference count table, the subset of entries including entries for data chunks in the first reference count table that indicate that the reference count value is not an exact value;

setting reference count values for all entries in the second reference count table to zero;

incrementing the reference count value for each data chunk in the second reference count table that is referenced by a non-deleted stream map;

replacing the reference count value in the first reference count table with a corresponding reference count value in the second reference count table for each entry in the first reference count table;

indicating in each entry in the first reference count table that the corresponding reference count value is an exact value;

determining entries in the first reference count table not having reference count values in the top predetermined percentage and/or greater than the predetermined threshold; and

discarding the entries in the first reference count table determined not to have reference count values in the top predetermined percentage and/or greater than the predetermined threshold.

17. A garbage collection module for garbage collecting a chunk store, the chunk store including data stored as a plurality of data chunks, the plurality of data chunks including stream map chunks, each stream map chunk corresponding to a stream map for a corresponding data stream and referencing data chunks stored in one or more chunk containers of the chunk store that are included in the corresponding data stream, the garbage collection module comprising:

a stream map chunk scanner configured to identify data chunks stored in the one or more chunk containers that are unused based on being referenced only by stream map chunks indicated as deleted;

a deleted data chunk indicator configured to indicate the identified data chunks as deleted; and

a storage space reclaimer configured to reclaim storage space in the one or more chunk containers containing the data chunks indicated as deleted.

18. The garbage collection module of claim 17, wherein each stream map chunk references data chunks stored in the one or more chunk containers by corresponding data chunk identifiers, wherein the stream map chunk scanner includes:

a Bloom filter generator configured to generate a Bloom filter;

wherein the stream map chunk scanner scans a plurality of stream map chunks to determine any stream map chunks not indicated as deleted, includes data chunk identifiers referenced by each stream map chunk indicated as not deleted in the Bloom filter, scans the plurality of stream map chunks to determine any stream map chunks indicated as deleted, and determines any data chunk identifiers referenced by the stream map chunks determined to be indicated as deleted that are not included in the Bloom filter.

19. The garbage collection module of claim 17, wherein the storage space reclaimer comprises:

a data chunk copier that copies each data chunk not indicated as deleted in the chunk container to a new container; and

a redirection table populator that populates a redirection table of the new container to map a first chunk identifier in the chunk container to a second chunk identifier in the new container for each copied data chunk.

20. The garbage collection module of claim 19, wherein the chunk store includes a hash index that stores a plurality of hash index entries, wherein each hash index entry of the hash index maps a data chunk identifier to a hash of a corresponding data chunk, wherein the storage space reclaimer modifies at least one entry of the hash index by replacing the data chunk identifier in the hash entry with the new data chunk identifier obtained from the redirection table and chunk headers of the data chunks.