Generating and optimizing summary index levels in a deduplication storage system

• US 10,452,297 B1
• Filed: 10/31/2016
• Issued: 10/22/2019
• Est. Priority Date: 05/02/2016
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Karr, Ronald, Miller, Ethan L., Sandvig, Cary A., Wang, Feng, Zhang, Wei
• Primary Examiner(s): Chan, Tracy C.
• Application Number:
  US15/339,684
• Time in Patent Office: 1,086 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• 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/0673 Single storage device
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: H03M 7/3091 Data deduplication

Abstract

The method and system generates a first deduplication map (DDM) level including first data and a second DDM level including second data. The method or apparatus also generates a first index summary (IS) level corresponding to the first DDM level and a second IS level corresponding to the second DDM level. The method or apparatus merges the first data of the first DDM level and the second data of the second DDM level to generate a third DDM level comprising third data. The method or apparatus in response to generating the third DDM level, generates a third IS level to accelerate lookup within the third DDM level.

Claims

1. A deduplication system comprising:

a persistent storage resource;

a volatile memory; and

a processing device, operatively coupled to the persistent storage resource and the volatile memory, to;

generate a first deduplication map (DDM) level comprising first data and a second DDM level comprising second data;

generate a first index summary (IS) level corresponding to the first DDM level and a second IS level corresponding to the second DDM level, wherein the first IS level accelerates lookup within the first DDM level and the second IS level accelerates lookup within the second DDM level;

merge the first data of the first DDM level and the second data of the second DDM level to generate a third DDM level comprising third data; and

in response to generating the third DDM level;

generate a third IS level corresponding to the third DDM level; and

replace the first IS level and the second IS level with the third IS level, the third IS level to accelerate lookup within the third DDM level, wherein the third IS level comprises a value used to derive a plurality of bits in the third DDM level.

2. The deduplication system of claim 1, wherein to merge the first data of the first DDM level and the second data of the second DDM level to generate the third DDM level, the processing device further to:

perform a sort merge on the first data of the first DDM level and the second data of the second DDM level.

3. The deduplication system of claim 1, wherein the third IS level provides an indication of location of the plurality of bits in the third DDM level.

4. The deduplication system of claim 1, wherein the first data of the first DDM level and the second data of the second DDM level are evenly distributed.

5. The deduplication system of claim 1, wherein the third DDM level comprises a complete hash value of data stored in the deduplication system, wherein the third IS level comprises a partial hash value of the data stored in the deduplication system, and wherein the value of the third IS level used to derive the plurality of bits in the third DDM is the partial hash value of the data stored in the deduplication system.

6. The deduplication system of claim 1, the processing device further to:

perform deduplication of received data using the third IS level.

7. The deduplication system of claim 6, wherein to perform the deduplication the processing device to:

generate a hash value for the received data;

compare the hash value for the received data to a partial hash value of the third IS level to determine a first match; and

responsive to determining the first match exists;

determine an indication of location in the third DDM level containing a complete hash value using the third IS level, and

compare the hash value for the received data to the complete hash value based on the indication of location in the third DDM level to determine a second match; and

responsive to determining the second match exists;

determine the received data is duplicate data.

8. A non-transitory computer-readable medium to store instructions that, when executed by a processing device, cause the processing device to:

generate a first deduplication map (DDM) level comprising first data and a second DDM level comprising second data;

generate a first index summary (IS) level corresponding to the first DDM level and a second IS level corresponding to the second DDM level, wherein the first IS level accelerates lookup within the first DDM level and the second IS level accelerates lookup within the second DDM level;

merge the first data of the first DDM level and the second data of the second DDM level to generate a third DDM level comprising third data; and

in response to generating the third DDM level;

generate a third IS level corresponding to the third DDM level; and

replace the first IS level and the second IS level with the third IS level, the third IS level to accelerate lookup within the third DDM level, wherein the third IS level comprises a value used to derive a plurality of bits in the third DDM level.

9. The non-transitory computer-readable medium of claim 8, wherein to merge the first data of the first DDM level and the second data of the second DDM level to generate the third DDM level, the processing device further to:

perform a sort merge on the first data of the first DDM level and the second data of the second DDM level.

10. The non-transitory computer-readable medium of claim 8, wherein the third IS level provides an indication of location of the plurality of bits in the third DDM level.

11. The non-transitory computer-readable medium of claim 8, wherein the third DDM level comprises a complete hash value of data stored in a storage system, wherein the third IS level comprises a partial hash value of the data stored in the storage system, and wherein the value of the third IS level used to derive the plurality of bits in the third DDM is the partial hash value of the data stored in the storage system.

12. The non-transitory computer-readable medium of claim 8, the processing device further to:

perform deduplication of received data using the third IS level.

13. The non-transitory computer-readable medium of claim 12, wherein to perform the deduplication the processing device to:

generate a hash value for the received data;

compare the hash value for the received data to a partial hash value of the third IS level to determine a first match; and

responsive to determining the first match exists;

determine an indication of location in the third DDM level containing a complete hash value using the third IS level, and

compare the hash value for the received data to the complete hash value based on the indication of location in the third DDM level to determine a second match; and

responsive to determining the second match exists;

determine the received data is duplicate data.

14. A method comprising:

generating a first deduplication map (DDM) level comprising first data and a second DDM level comprising second data;

generating a first index summary (IS) level corresponding to the first DDM level and a second IS level corresponding to the second DDM level, wherein the first IS level accelerates lookup within the first DDM level and the second IS level accelerates lookup within the second DDM level;

merging the first data of the first DDM level and the second data of the second DDM level to generate a third DDM level comprising third data; and

in response to generating the third DDM level

generating a third IS level corresponding to the third DDM level; and

replacing the first IS level and the second IS level with the third IS level, the third IS level to accelerate lookup within the third DDM level, wherein the third IS level comprises a value used to derive a plurality of bits in the third DDM level.

15. The method of claim 14, wherein merging the first data of the first DDM level and the second data of the second DDM level to generate the third DDM level comprises:

performing a sort merge on the first data of the first DDM level and the second data of the second DDM level.

16. The method of claim 14, wherein the third IS level provides an indication of location of the plurality of bits in the third DDM level.

17. The method of claim 14, wherein the first data of the first DDM level and the second data of the second DDM level are evenly distributed.

18. The method of claim 14, wherein the third DDM level comprises a complete hash value of data stored in a storage system, wherein the third IS level comprises a partial hash value of the data stored in the storage system, and wherein the value of the third IS level used to derive the plurality of bits in the third DDM is the partial hash value of the data stored in the storage system.

19. The method of claim 14, further comprising:

performing deduplication of received data using the third IS level.

20. The method of claim 19, wherein performing the deduplication comprises:

generating a hash value for the received data;

comparing the hash value for the received data to a partial hash value of the third IS level to determine a first match; and

responsive to determining the first match exists;

determining an indication of location in the third DDM level containing a complete hash value using the third IS level, and

comparing the hash value for the received data to the complete hash value based on the indication of location in the third DDM level to determine a second match; and

responsive to determining the second match exists;

determining the received data is duplicate data.