ELASTICALLY MANAGING CACHE FOR SUB-BLOCK DEDUPLICATION

• US 20200133546A1
• Filed: 10/31/2018
• Published: 04/30/2020
• Est. Priority Date: 10/31/2018
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Faibish, Sorin, Armangau, Philippe, Gonczi, Istvan, Bassov, Ivan, Vankamamidi, Vamsi K.
• Granted Patent: US 10,838,643 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• CPC Class Codes: G06F 12/124 being minimized, e.g. non MRU
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/465 Structured object, e.g. database record
• 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/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0671 In-line storage system
• CPC Class Codes: G06F 3/068 Hybrid storage device

Abstract

A technique for managing cache in a storage system that supports data deduplication renders each of a set of data blocks as multiple sub-blocks and loads a cache-resident digest database on a per-block basis, selectively creating new digest entries in the database for all sub-blocks in a block, but only for blocks that contain no duplicate sub-blocks. Sub-blocks of blocks containing duplicates are excluded. By limiting digest entries to sub-blocks of blocks that contain no duplicates, the storage system limits the size of the digest database, and thus of the cache, while also biasing the contents of the digest database toward entries that are likely to produce deduplication matches in the future.

Claims

1. A method of managing cache in a data storage system that supports data deduplication, the method comprising:

performing, for each of a set of data blocks in the cache, an evaluation operation configured to (i) produce a first result in response to the data block containing no sub-blocks that match any digest entries in a digest database, and (ii) produce a second result in response to the data block containing at least one sub-block that matches a digest entry in the digest database, the digest database stored in the cache; and

selectively processing each of the set of data blocks along one of a first path and a second path, including

for each of a first set of data blocks for which the evaluation operation produces the first result, processing the respective data block along the first path, including creating multiple new digest entries in the digest database, one new digest entry for each of the sub-blocks of the respective data block; and

for each of a second set of data blocks for which the evaluation operation produces the second result, processing the respective data block along the second path, including creating no new digest entries in the digest database for any of the sub-blocks of the respective data block.

2. The method of claim 1, wherein the digest database contains multiple digest entries, each of the digest entries provided for a respective sub-block and including a reference to a parent block in the cache that contains the respective sub-block.

3. The method of claim 2, further comprising implementing an eviction policy for the cache.

4. The method of claim 3, wherein the eviction policy includes an LRU (Least Recently Used) policy.

5. The method of claim 3, further comprising providing a parent-child data structure (PCDS) that associates parent blocks in the cache with respective references to digest entries of child sub-blocks of the respective parent blocks.

6. The method of claim 5, wherein the PCDS stores a respective record for each of multiple parent blocks, each record located using a respective key that uniquely identifies the record, each key formed by performing a mathematical operation on contents of the parent block.

7. The method of claim 6, wherein the PCDS is stored in the cache, and wherein the method further comprises:

identifying a parent block to be evicted from the cache in accordance with the eviction policy;

performing the mathematical operation on the identified parent block to produce a parent key;

performing a look-up in the PCDS for a parent record uniquely identified by the parent key; and

evicting, from the digest database, each digest entry referenced in the parent record.

8. The method of claim 7, further comprising:

evicting the parent record from the PCDS; and

evicting the identified parent block from the cache.

9. The method of claim 6, further comprising:

forming a new block in the cache;

performing the mathematical operation on the new block to produce a new key;

performing a look-up in the PCDS for a record uniquely identified by the new key; and

in response to finding the record uniquely identified by the new key, performing a full-block-based deduplication operation on the new block.

10. The method of claim 3, further comprising:

forming a set of prior data blocks in the cache; and

for each of the set of prior data blocks, creating a new digest entry in the digest database for each novel sub-block contained in the prior data block, regardless of whether the prior data block also contains any duplicate sub-blocks,

wherein a sub-block is “

novel”

when it does not match any digest entry already stored in the digest database and is “

duplicate”

when it matches a digest entry already stored in the digest database.

11. The method of claim 10, wherein the cache operates in multiple modes, the modes including (i) a first mode in which the cache performs the evaluation operation and selectively creates digest entries for all sub-blocks or for no sub-blocks of respective data blocks, depending on results of the evaluation operation, and (ii) a second mode in which the cache creates new entries for novel sub-blocks, regardless of whether the novel sub-blocks have siblings that are duplicate sub-blocks.

12. The method of claim 11,

wherein the cache operates in the first mode in response to a fullness of the cache exceeding a predetermined water mark, and

wherein the cache operates in the second mode in response to the fullness of the cache being less than the predetermined water mark.

13. The method of claim 3, further comprising, upon identifying multiple novel sub-blocks and a set of duplicate sub-blocks in a data block:

deduplicating each of the set of duplicate sub-blocks by matching each duplicate sub-block to a sub-block already stored in the data storage system;

placing the novel sub-blocks together in a single dataset;

compressing the dataset to produce a compressed dataset; and

storing the compressed data set in a storage extent.

21. The method of claim 1, wherein at least one of the second set of data blocks includes a sub-block that does not match any digest entry in the digest database.

22. The method of claim 21, wherein processing each respective block of the second set of data blocks along the second path further includes performing deduplication on each matching sub-block of the respective data block, each matching sub-block matching an entry in the digest database.

14. A data storage system, comprising control circuitry that includes a set of processing units coupled to memory, the control circuitry constructed and arranged to:

perform, for each of a set of data blocks in the cache, an evaluation operation configured to (i) produce a first result in response to the data block containing no sub-blocks that match any digest entries in a digest database, and (ii) produce a second result in response to the data block containing at least one sub-block that matches a digest entry in the digest database, the digest database stored in the cache; and

selectively process each of the set of data blocks along one of a first path and a second path, including

for each of a first set of data blocks for which the evaluation operation produces the first result, process the respective data block along the first path to create multiple new digest entries in the digest database, one new digest entry for each of the sub-blocks of the respective data block; and

for each of a second set of data blocks for which the evaluation operation produces the second result, process the respective data block along the second path to create no new digest entries in the digest database for any of the sub-blocks of the respective data block.

15. A computer program product including a set of non-transitory, computer-readable media having instructions which, when executed by control circuitry of a data storage system that supports data deduplication, cause the control circuitry to perform a method of managing cache, the method comprising:

performing, for each of a set of data blocks in the cache, an evaluation operation configured to (i) produce a first result in response to the data block containing no sub-blocks that match any digest entries in a digest database, and (ii) produce a second result in response to the data block containing at least one sub-block that matches a digest entry in the digest database, the digest database stored in the cache; and

selectively processing each of the set of data blocks along one of a first path and a second path, including

for each of a first set of data blocks for which the evaluation operation produces the first result, processing the respective data block along the first path, including creating multiple new digest entries in the digest database, one new digest entry for each of the sub-blocks of the respective data block; and

for each of a second set of data blocks for which the evaluation operation produces the second result, processing the respective data block along the second path, including creating no new digest entries in the digest database for any of the sub-blocks of the respective data block.

16. The computer program product of claim 15, wherein the method further comprises providing a parent-child data structure (PCDS) that associates parent blocks in the cache with respective references to digest entries of child sub-blocks of the respective parent blocks.

17. The computer program product of claim 16, wherein the PCDS stores a respective record for each of multiple parent blocks, each record located using a respective key that uniquely identifies the record, each key formed by performing a mathematical operation on contents of the parent block.

18. The computer program product of claim 15, wherein the cache operates in multiple modes, the modes including (i) a first mode in which the cache performs the evaluation operation and selectively creates digest entries for all sub-blocks or for no sub-blocks of respective data blocks, depending on results of the evaluation operation, and (ii) a second mode in which the cache creates new entries for novel sub-blocks, regardless of whether the novel sub-blocks have siblings that are duplicate sub-blocks.

19. The computer program product of claim 18,

wherein the cache operates in the first mode in response to a fullness of the cache exceeding a predetermined water mark, and

wherein the cache operates in the second mode in response to the fullness of the cache being less than the predetermined water mark.

20. The computer program product of claim 15, further comprising, upon identifying multiple novel sub-blocks and a set of duplicate sub-blocks in a data block:

deduplicating each of the set of duplicate sub-blocks by matching each duplicate sub-block to a sub-block already stored in the data storage system;

placing the novel sub-blocks together in a single dataset;

compressing the dataset to produce a compressed dataset; and

storing the compressed data set in a storage extent,

wherein a sub-block is “

novel”

when it does not match any digest entry already stored in the digest database and is “

duplicate”

when it matches a digest entry already stored in the digest database.