Method and apparatus for on-disk deduplication metadata for a deduplication file system

• US 10,255,287 B2
• Filed: 07/31/2015
• Issued: 04/09/2019
• Est. Priority Date: 07/31/2015
• Status: Active Grant

• Current Assignee: hiveIO, Inc.
• Original Assignee: hiveIO, Inc.
• Inventors: Sarab, Farshid Eslami, Auradkar, Vikram
• Primary Examiner(s): Hershley, Mark E
• Application Number:
  US14/815,482
• Publication Number:
  US 20170031945A1
• Time in Patent Office: 1,348 Days
• Field of Search: 707692
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641

Abstract

A method and apparatus is disclosed herein for maintaining deduplication metadata on disk separate from an in-memory deduplication file system for a deduplication computing system. The method may include reading deduplication metadata from a first memory of a deduplication computing system. Furthermore, the method may include maintaining deduplicated data for a file system in a second memory, and maintaining the deduplication metadata that describes the deduplicated data of the file system in the first memory of the deduplication computing system, wherein the first memory is a different type of memory and separated from the second memory in the deduplication computing system. Furthermore, the method may include accessing the deduplication metadata in the second memory in response to receipt of a request by the deduplication computing system to perform a first operation with deduplicated data of the file system in the second memory.

Claims

1. A method comprising:

reading deduplication metadata from a first memory of a deduplication computing system, wherein the deduplication metadata comprises a deduplication metadata hash table, wherein the deduplication metadata hash table comprises a plurality of slots with deduplication metadata entries distributed among the plurality of slots based on unique identifiers from the deduplication metadata entries, and wherein the at least a portion of the unique identifiers are mask values each comprising a lower portion of bits of a unique identifier, and wherein the mask value is an index to the slots of the deduplication metadata table;

maintaining deduplicated data for a file system of the deduplication computing system in a second memory;

maintaining the deduplication metadata that describes the deduplicated data of the file system in the first memory of the deduplication computing system, wherein the first memory is a different type of memory and separated from the second memory in the deduplication computing system;

in response to receipt of a request by the deduplication computing system to perform a first operation with deduplicated data of the file system in the second memory, accessing the deduplication metadata in the first memory;

dynamically resizing the deduplication metadata hash table to a new size based on one or more runtime conditions associated with an amount of utilization of the deduplication metadata hash table at runtime;

allocating or deallocating slots for the deduplication metadata hash table based on the new size; and

redistributing deduplication metadata entries to slots of the deduplication metadata hash table based on mask values associated with unique identifiers from the deduplication metadata entries.

2. The method of claim 1, wherein the deduplication metadata hash table comprises one or more deduplication metadata entries describing blocks in the file system, the description including at least a logic block number, a unique identifier, a reference count, and a pointer to said each data block in the file system, and wherein the deduplication metadata comprises a checksum array comprising at least a portion of a unique identifier associated with each data block of the file system.

3. The method of claim 2, wherein each slot of the plurality of slots comprises a header and a plurality of entries, the header located at the beginning of each slot and describing a status of the slot, and the plurality of entries storing zero or more deduplication metadata entries following the header, wherein the zero or more deduplication metadata entries are sorted within a slot based on unique identifier.

4. The method of claim 3, wherein the deduplication metadata further comprises a granular lock array, wherein a first set of one or more locks referenced in the granular lock array block a second operation of the deduplication computing system when the second operation is associated with deduplication metadata located in a same slot as the deduplication metadata associated with the first operation, and wherein a second set of one or more locks referenced in the granular lock array do not block a third operation of the deduplication computing system when the third operation is associated with deduplication metadata located in a different slot from the slot where the deduplication metadata associated with the first operation is located.

5. The method of claim 3, wherein the amount of utilization of the deduplication metadata hash table is based, at least in part, on

one or more runtime conditions comprising a number of deduplication metadata entries within one or more slots of the deduplication metadata hash table, a total number of deduplication metadata entries within the deduplication metadata hash table, and a total number of data blocks within the file system.

6. The method of claim 2, wherein the checksum array comprises an array or sequential entries, each entry corresponding to a logical block of the file system, wherein an entry in the array comprises at least a portion of a unique identifier for data, if any, within a logic block of the file system.

7. The method of claim 6, wherein the at least a portion of the unique identifier is a mask value comprising a lower portion of bits of the unique identifier, and wherein the mask value is an index to the slots of the deduplication metadata table.

8. The method of claim 1, wherein the second memory is a volatile memory of the deduplication computing system, and wherein the first memory is a non-volatile memory coupled with the deduplication computing system.

9. The method of claim 8, wherein the volatile memory comprises at least one of a random access memory and a flash memory.

10. The method of claim 8, wherein the non-volatile memory comprises at least one of a hard disk drive, an array of aggregated hard disks, a storage area network, and a network attached storage.

11. The method of claim 1, wherein the deduplication computing system processes data operations in a data path between a virtual machine and the second memory, in real time or substantially real-time.

12. An article of manufacture having one or more non-transitory computer readable storage media storing executable instructions thereon which when executed cause a system to perform a method comprising:

reading deduplication metadata from a first memory of a deduplication computing system, wherein the deduplication metadata comprises a deduplication metadata hash table, wherein the deduplication metadata hash table comprises a plurality of slots with deduplication metadata entries distributed among the plurality of slots based on unique identifiers from the deduplication metadata entries, and wherein the at least a portion of the unique identifiers are mask values each comprising a lower portion of bits of a unique identifier, and wherein the mask value is an index to the slots of the deduplication metadata table;

maintaining deduplicated data for a file system of the deduplication computing system in a second memory;

maintaining the deduplication metadata that describes the deduplicated data of the file system in the first memory of the deduplication computing system, wherein the first memory is a different type of memory and separated from the second memory in the deduplication computing system;

in response to receipt of a request by the deduplication computing system to perform a first operation with deduplicated data of the file system in the second memory, accessing the deduplication metadata in the first memory;

dynamically resizing the deduplication metadata hash table to a new size based on one or more runtime conditions associated with an amount of utilization of the deduplication metadata hash table at runtime;

allocating or deallocating slots for the deduplication metadata hash table based on the new size; and

redistributing deduplication metadata entries to slots of the deduplication metadata hash table based on mask values associated with unique identifiers from the deduplication metadata entries.

13. The article of manufacture of claim 12, wherein the deduplication metadata hash table comprises one or more deduplication metadata entries describing blocks in the file system, the description including at least a logic block number, a unique identifier, a reference count, and a pointer to said each data block in the file system, and wherein the deduplication metadata comprises a checksum array comprising at least a portion of a unique identifier associated with each data block of the file system.

14. The article of manufacture of claim 13, wherein each slot of the plurality of slots comprises a header and a plurality of entries, the header located at the beginning of each slot and describing a status of the slot, and the plurality of entries storing zero or more deduplication metadata entries following the header, wherein the zero or more deduplication metadata entries are sorted within a slot based on unique identifier.

15. The article of manufacture of claim 14, wherein the deduplication metadata further comprises a granular lock array, wherein a first set of one or more locks referenced in the granular lock array block a second operation of the deduplication computing system when the second operation is associated with deduplication metadata located in a same slot as the deduplication metadata associated with the first operation, and wherein a second set of one or more locks referenced in the granular lock array do not block a third operation of the deduplication computing system when the third operation is associated with deduplication metadata located in a different slot from the slot where the deduplication metadata associated with the first operation is located.

16. The article of manufacture of claim 14, wherein the amount of utilization of the deduplication metadata hash table is based, at least in part, on

one or more runtime conditions comprising a number of deduplication metadata entries within one or more slots of the deduplication metadata hash table, a total number of deduplication metadata entries within the deduplication metadata hash table, and a total number of data blocks within the file system.

17. The article of manufacture of claim 13, wherein the checksum array comprises an array or sequential entries, each entry corresponding to a logical block of the file system, wherein an entry in the array comprises at least a portion of a unique identifier for data, if any, within a logic block of the file system.

18. The article of manufacture of claim 17, wherein the at least a portion of the unique identifier is a mask value comprising a lower portion of bits of the unique identifier, and wherein the mask value is an index to the slots of the deduplication metadata table.

19. The article of manufacture of claim 12, wherein the second memory is a volatile memory of the deduplication computing system, and wherein the first memory is a non-volatile memory coupled with the deduplication computing system.

20. The article of manufacture of claim 19, wherein the volatile memory comprises at least one of a random access memory and a flash memory.

21. The article of manufacture of claim 19, wherein the non-volatile memory comprises at least one of a hard disk drive, an array of aggregated hard disks, a storage area network, and a network attached storage.

22. The article of manufacture of claim 12, wherein the deduplication computing system processes data operations in a data path between a virtual machine and the second memory, in real time or substantially real-time.

23. A deduplication computing system comprising:

a first memory to store deduplication metadata;

a second memory to store deduplicated data; and

a processor coupled with the first memory and the second memory to

read the deduplication metadata from the first memory, wherein the deduplication metadata comprises a deduplication metadata hash table, wherein the deduplication metadata hash table comprises a plurality of slots with deduplication metadata entries distributed among the plurality of slots based on unique identifiers from the deduplication metadata entries, and wherein the at least a portion of the unique identifiers are mask values each comprising a lower portion of bits of a unique identifier, and wherein the mask value is an index to the slots of the deduplication metadata table,

maintain the deduplicated data for a file system of the deduplication computing system in the second memory,

maintain the deduplication metadata that describes the deduplicated data of the file system in the first memory of the deduplication computing system, wherein the first memory is a different type of memory and separated from the second memory in the deduplication computing system,

in response to receipt of a request by the deduplication computing system to perform a first operation with deduplicated data of the file system in the second memory, access the deduplication metadata in the first memory;

dynamically resize the deduplication metadata hash table to a new size based on one or more runtime conditions associated with an amount of utilization of the deduplication metadata hash table at runtime;

allocating or deallocating slots for the deduplication metadata hash table based on the new size; and

redistributing deduplication metadata entries to slots of the deduplication metadata hash table based on mask values associated with unique identifiers from the deduplication metadata entries.

24. The deduplication computing system claim 23, wherein the deduplication metadata hash table comprises one or more deduplication metadata entries describing blocks in the file system, the description including at least a logic block number, a unique identifier, a reference count, and a pointer to said each data block in the file system, and wherein the deduplication metadata comprises a checksum array comprising at least a portion of a unique identifier associated with each data block of the file system.

25. The deduplication computing system of claim 23, wherein the second memory is a volatile memory of the deduplication computing system, and wherein the first memory is a non-volatile memory coupled with the deduplication computing system.

26. The deduplication computing system of claim 23, wherein the deduplication computing system processes data operations in a data path between a virtual machine and the second memory, in real time or substantially real-time.