Data aware deduplication object storage (DADOS)

• US 10,761,758 B2
• Filed: 12/21/2016
• Issued: 09/01/2020
• Est. Priority Date: 12/21/2015
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Doerner, Don, Zeis, Michael, Wideman, Roderick, Wade, Greg, Lord, Steve, Goker, Turguy
• Primary Examiner(s): Mofiz, Apu M
• Assistant Examiner(s): Holland, Sheryl L
• Application Number:
  US15/386,484
• Publication Number:
  US 20170177266A1
• Time in Patent Office: 1,350 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/163 Server or database system
• CPC Class Codes: G06F 2212/261 Storage comprising a plurality of storage devices
• CPC Class Codes: G06F 2212/262 configured as RAID
• CPC Class Codes: G06F 2212/263 Network storage, e.g. SAN or NAS
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Embodiments include a data aware deduplicating object store. The data aware deduplicating data store includes a consistent hashing logic that manages a consistent hashing architecture for the object store. The consistent hashing architecture includes a metadata ring and a bulk ring. The consistent hashing architecture may be a multiple ring architecture comprising a metadata ring and two or more bulk rings. A bulk ring may include a key/value (k/v) data store, where a k/v data store stores a shard of an index and a reference count that facilitates the individual approach to garbage collection or data reclamation. The data aware deduplicating data store also includes a deduplication logic that provides data deduplication for data to be stored in the object store. The deduplication logic performs variable length deduplication and provides a shared nothing approach.

Claims

1. A data aware deduplicating object store, comprising:

a collection of storage devices, wherein each device includes a processor and non-transitory storage medium storing instructions that cause the processor to perform corresponding functions;

a consistent hashing logic configured to;

receive a first item having a first item identifier;

break data of the item into at least two chunks;

perform a first hash function on each chunk to generate a recipe comprising respective chunk identifiers of the at least two chunks;

perform a second hash function on the item identifier to determine a metadata location on a metadata ring of a dual ring architecture;

store the recipe in the metadata location;

provide respective chunk identifiers and chunks for storing in a bulk ring of the dual ring architecture; and

a deduplication logic configured to;

receive the chunk identifiers and chunks from the consistent hashing logic;

access a plurality of Bloom filter shards, wherein each Bloom filter shard stores information about chunks of data stored in an associated key/value data store of the bulk ring, to perform deduplication on each chunk based on the chunk identifier for the chunk to determine whether the chunk is a duplicate chunk already present in the bulk ring;

increment a respective reference count for each respective chunk identifier based on the recipe including the respective chunk, wherein the reference count facilitates garbage collection or data reclamation; and

when the chunk of data is a duplicate chunk, refrain from providing the duplicate chunk to the bulk ring for storing.

2. The data aware deduplicating object store of claim 1, where the deduplication logic performs variable length deduplication.

3. The data aware deduplicating object store of claim 1, wherein the metadata ring and the bulk ring comprise different memory devices.

4. The data aware deduplicating object store of claim 1, where different memory devices in the bulk ring have different properties.

5. The data aware deduplicating object store of claim 1, where each key/value data store comprises a key corresponding to the hash of a chunk of data and a value corresponding to data in the chunk of data.

6. The data aware deduplicating object store of claim 1, where a first key/value data store in the bulk ring utilizes a first data protection scheme and a second key/value data store in the bulk ring utilizes a second data protection scheme that is different from the first data protection scheme, wherein a data protection scheme comprises an erasure coding approach, a RAID approach, or a replication approach.

7. The data aware deduplicating object store of claim 1, where a first key/value data store in the bulk ring utilizes a first power management scheme and a second key/value data store in the bulk ring utilizes a second power management scheme that is different from the first power management scheme.

8. The data aware deduplicating object store of claim 1, where a first key/value data store in the bulk ring utilizes a first garbage collection or data reclamation scheme and a second key/value data store in the bulk ring utilizes a second garbage collection or data reclamation scheme that is different from the first garbage collection or data reclamation scheme.

9. The data aware deduplicating object store of claim 8, where a key/value data store stores a shard of an index and a reference count that facilitates the first and second garbage collection or data reclamation schemes.

10. The data aware deduplicating object store of claim 9, where a key/value data store performs its own garbage collection or data reclamation.

11. The data aware deduplicating object store of claim 1, where the consistent hashing logic is configured to perform replication during ingest and erasure coding after deduplication has been performed.

12. The data aware deduplicating object store of claim 1, where the consistent hashing logic and the deduplication logic provide indirect pattern recognition of content stored in the key/value data store using hash based signatures of less than an entire item.

13. A non-transitory computer-readable storage device storing computer-executable instructions that when executed by a computer control the computer to perform a method, the method comprising:

accessing a first set of electronic data to be stored in a data aware deduplicating object store comprising a collection of storage devices, where the data aware deduplicating data store comprises a consistent hashing architecture, where the consistent hashing architecture is a dual-ring architecture comprising a metadata ring and a bulk ring, where the metadata ring comprises a first set of key/value (k/v) nodes and the bulk ring comprises a second set of k/v nodes;

chunking the first set of electronic data into a set of data chunks using a variable length deduplication approach;

generating a set of hashed chunk and chunk identifier pairs by hashing each member of the set of data chunks to generate a chunk identifier for the chunk, wherein the chunk identifiers comprise a recipe for the first set of electronic data;

hashing an identifier for the first set of electronic data to generate a metadata location on the metadata ring;

storing the recipe in the metadata location;

providing the set of hashed chunks for storing in the bulk ring;

access a plurality of Bloom filter shards, wherein each Bloom filter shard stores information about chunks of data stored in an associated key/value data store of the bulk ring, to determine whether the hashed chunk has already been stored in the bulk ring;

incrementing a respective reference count for each respective chunk identifier based on the recipe including the respective chunk, wherein the reference count facilitates garbage collection or data reclamation; and

refraining from storing a hashed chunk of the set in the bulk ring upon determining that the hashed chunk has already been stored in the bulk ring.

14. The non-transitory computer-readable storage device of claim 13, where storing the chunk identifiers includes storing the chunk identifiers on a k/v node that does not store a hashed chunk.

15. The non-transitory computer-readable storage device of claim 13, where a first k/v node stores a first index shard in a first flash memory, and a first hashed chunk in a first type of storage device, where the first type of storage device is a solid state drive (SSD), a hard disk drive (HDD), or a shingled magnetic recording (SMR) drive.

16. The non-transitory computer-readable storage device of claim 15, where a second, different k/v node stores a second index shard in a second flash memory, and a second hashed chunk in a second, different type of storage device, where the second, different type of storage device is a solid state drive (SSD), a hard disk drive (HDD), or a shingled magnetic recording (SMR) drive.

17. The non-transitory computer-readable storage device of claim 13, where a first k/v node employs a first power management scheme, and where a second k/v node employs a second, different power management scheme.

18. The non-transitory computer-readable storage device of claim 13, where a first k/v node employs a first garbage collection or data reclamation scheme, and where a second, different k/v node employs a second, different garbage collection or data reclamation scheme.

19. The non-transitory computer-readable storage device of claim 18, where a k/v node stores a shard of an index and a reference count, where the shard of the index or the reference count facilitates garbage collection or data reclamation.

20. The non-transitory computer-readable storage device of claim 19, where the k/v node performs its own garbage collection or data reclamation.

21. The non-transitory computer-readable storage device of claim 13, further comprising storing content based searching work, or virus checking work on the k/v node.

22. The non-transitory computer-readable storage device of claim 21, where virus checking includes performing indirect pattern recognition of content stored in a k/v node using hash based signatures of less than an entire item.

23. A system for data aware deduplication object storage, the system comprising:

an object store;

means for managing a consistent hashing architecture associated with the object store, where the consistent hashing architecture is a multiple ring architecture comprising at least one metadata ring and at least one bulk ring, where the at least one metadata ring includes one or more key/value (k/v) data stores, and where the at least one bulk ring includes one or more k/v data stores;

means for receiving a first item having a first item identifier;

means for breaking the item into at least two chunks;

means for hashing each chunk to generate respective chunk identifiers, wherein the chunk identifiers comprise a recipe for the first item;

means for hashing the item identifier to determine a metadata location on the metadata ring;

means for storing the recipe in the metadata location;

means for providing the chunk identifiers and the chunks for storing in the bulk ring at a bulk ring location;

means for deduplicating data to be stored in the object store based on the chunk identifiers using a variable length deduplication approach;

means for storing deduplicated data in the bulk ring;

wherein the means for deduplicating is configured to refrain from providing duplicate data to the means for storing deduplicated data in the bulk ring; and

means for power management of a k/v data store or garbage collection for the k/v data store at an individual level.