Granted Patent B2

US 11,615,063 · App. 17/155,224 · Granted Mar 28, 2023

Inventors: Alexei Kabishcer (Ramat Gan, IL); Uri Shabi (Tel Mond, IL)

Assignee: EMC IP Holding Company LLC

G06F16/215G06F16/2255H03M7/3088

Abstract

Claims (75)

1. For a data storage system having a plurality of physical storage devices on which data units are stored, a method comprising:

applying a first hash function to a first data unit to produce a first hash value of a first data unit;

determining that the first hash value of the first data unit has a same hash value as any of one or more other data units;

responsive to said determining that the first hash value of the first data unit has the same hash value as a second data unit of the one or more other data units, performing dictionary-based compression of the first data unit using the second data unit as a dictionary;

determining, during said dictionary-based compression of the first data unit using the second data unit as a dictionary, that the first data unit and the second data unit are not identical; and

responsive to said determining, during said dictionary-based compression of the first data unit using the second data unit as a dictionary, that the first data unit and the second data unit are not identical, storing, on one or more of the plurality of physical storage devices, a compressed data unit which is a compressed form of the first data unit produced by said dictionary-based compression using the second data unit as a dictionary.

2. The method of claim 1 , wherein the first hash function is applied to only a portion of the first data unit to produce the first hash value.

3. The method of claim 2 , further comprising:

applying a second hash function to a plurality of chunks of the first data unit to produce, for each of the plurality of chunks, a third hash value;

determining a plurality of maximum values or minimum values from among the third hash values; and

forming the portion of the first data unit from at least a subset of the chunks that produced the maximum values or minimum values.

4. The method of claim 3 , further comprising:

for each chunk of the subset of chunks, appending other contiguous pieces of data from before and/or after the chunk within the data unit to the chunk to produce an extended chunk, wherein the portion of the data is formed from the extended chunks.

5. The method of claim 3 , further comprising:

recording a relative position within the first data unit of each chunk that produced one of the plurality of maximum or minimum values; and

for the at least subset of chunks, obtaining the chunk from the recorded relative position of the chunk.

6. The method of claim 5 , further comprising:

ordering the at least subset of chunks according to the relative positions of the chunks within the first data unit,

wherein forming the portion includes concatenating the chunks according to the ordering.

7. The method of claim 1 , wherein the method further comprises:

applying the first hash function to a candidate data unit to produce a third hash value of the candidate data unit;

determining that the third hash value does not match an existing hash value of any of the one or more other data units; and

responsive to determining that the third hash value does not match the existing hash value of any of the one or more other data units, compressing the candidate data unit using self-compression, and storing the third hash value in a hash index.

8. A data storage system comprising:

a plurality of physical storage devices on which data units are stored; and

one or more memories comprising code stored thereon that, when executed, performs a method including:

applying a first hash function to a first data unit to produce a first hash value of a first data unit;

determining that the first hash value of the first data unit has a same hash value as any of one or more other data units;

responsive to said determining that the first hash value of the first data unit has the same hash value as a second data unit of the one or more other data units, performing dictionary-based compression of the first data unit using the second data unit as a dictionary;

determining, during said dictionary-based compression of the first data unit using the second data unit as a dictionary, that the first data unit and the second data unit are not identical; and

responsive to said determining, during said dictionary-based compression of the first data unit using the second data unit as a dictionary, that the first data unit and the second data unit are not identical, storing, on one or more of the plurality of physical storage devices, a compressed data unit which is a compressed form of the first data unit produced by said dictionary-based compression using the second data unit as a dictionary.

9. The data storage system of claim 8 , wherein the first hash function is applied to only a portion of the first data unit to produce the first hash value.

10. The data storage system of claim 9 , wherein the method further includes:

applying a second hash function to a plurality of chunks of the first data unit to produce, for each of the plurality of chunks, a third hash value;

determining a plurality of maximum values or minimum values from among the third hash values; and

forming the portion of the first data unit from at least a subset of the chunks that produced the maximum values or minimum values.

11. The data storage system of claim 10 , wherein the method further includes:

for each chunk of the subset of chunks, appending other contiguous pieces of data from before and/or after the chunk within the data unit to the chunk to produce an extended chunk,

wherein the portion of the data is formed from the extended chunks.

12. The data storage system of claim 10 , wherein the method further includes:

recording a relative position within the first data unit of each chunk that produced one of the plurality of maximum or minimum values; and

for the at least subset of chunks, obtaining the chunk from the recorded relative position of the chunk.

13. The data storage system of claim 12 , wherein the method further includes:

ordering the at least subset of chunks according to the relative positions of the chunks within the first data unit,

wherein forming the portion includes concatenating the chunks according to the ordering.

14. The data storage system of claim 8 , wherein the method further comprises:

applying the first hash function to a candidate data unit to produce a third hash value of the candidate data unit;

determining that the third hash value does not match an existing hash value of any of the one or more other data units; and

responsive to determining that the third hash value does not match the existing hash value of any of the one or more other data units, compressing the candidate data unit using self-compression, and storing the third hash value in a hash index.

15. For a data storage system having a plurality of physical storage devices on which data units are stored, non-transitory computer-readable media having code stored thereon that, when executed, performs a method comprising:

applying a first hash function to a first data unit to produce a first hash value of a first data unit;

determining that the first hash value of the first data unit has a same hash value as any of one or more other data units;

responsive to said determining that the first hash value of the first data unit has the same hash value as a second data unit of the one or more other data units, performing dictionary-based compression of the first data unit using the second data unit as a dictionary,

determining, during said dictionary-based compression of the first data unit using the second data unit as a dictionary, that the first data unit and the second data unit are not identical; and

responsive to said determining, during said dictionary-based compression of the first data unit using the second data unit as a dictionary, that the first data unit and the second data unit are not identical, storing, on one or more of the plurality of physical storage devices, a compressed data unit which is a compressed form of the first data unit produced by said dictionary-based compression using the second data unit as a dictionary.

16. The non-transitory computer-readable media of claim 15 , wherein the first hash function is applied to only a portion of the first data unit to produce the first hash value.

17. The non-transitory computer-readable media of claim 16 , wherein the method further comprises:

applying a second hash function to a plurality of chunks of the first data unit to produce, for each of the plurality of chunks, a third hash value;

determining a plurality of maximum values or minimum values from among the third hash values; and

forming the portion of the first data unit from at least a subset of the chunks that produced the maximum values or minimum values.

18. The non-transitory computer-readable media of claim 17 , wherein the method further comprises:

for each chunk of the subset of chunks, appending other contiguous pieces of data from before and/or after the chunk within the data unit to the chunk to produce an extended chunk, wherein the portion of the data is formed from the extended chunks.

19. The non-transitory computer-readable media of claim 18 , wherein the method further comprises:

recording a relative position within the first data unit of each chunk that produced one of the plurality of maximum or minimum values; and

for the at least subset of chunks, obtains the chunk from the recorded relative position of the chunk.

20. The non-transitory computer-readable media of claim 15 , wherein the method further comprises:

applying the first hash function to a candidate data unit to produce a third hash value of the candidate data unit;

determining that the third hash value does not match an existing hash value of any of the one or more other data units; and

responsive to determining that the third hash value does not match the existing hash value of any of the one or more other data units, compressing the candidate data unit using self-compression, and storing the first third hash value in a hash index.

21. The method of claim 1 , further comprising:

applying the first hash function to a candidate data unit to produce a third hash value of the candidate data unit;

determining that the third hash value of the candidate data unit matches one hash value of a corresponding data unit of the one or more other data units;

responsive to said determining that the third hash value of the candidate data unit matches said one hash value of the corresponding data unit, performing said dictionary-based compression of the candidate data unit using the corresponding data unit as a dictionary;

determining, during said dictionary-based compression of the candidate data unit using the corresponding data unit as a dictionary, that the candidate data unit and the corresponding data unit are identical; and

responsive to said determining, during said dictionary-based compression of the candidate data unit using the corresponding data unit as a dictionary, that the candidate data unit and the corresponding data unit are identical, storing, on one or more of the plurality of physical storage devices, a reference to the corresponding candidate data unit as the candidate data unit.

Assignments (9)

Continuity (1)