Method to keep on-disk physical deduplication index layer up to date
Techniques for keeping on-disk, physical deduplication (“dedupe”) index levels up to date to increase the efficiency of data deduplication in storage systems. The techniques include providing a plurality of dedupe indexes across a memory level and a disk level of a storage system, in which the plurality of dedupe indexes include an in-memory dedupe index at the memory level, and an on-disk dedupe index at the disk level. The techniques include applying a plurality of eviction rules regarding evicting entries of the on-disk dedupe index, in which the plurality of eviction rules avoid random evictions of entries from the on-disk dedupe index. The techniques include, in response to applying the plurality of eviction rules, identifying a plurality of entries of the on-disk dedupe index as eviction candidates. The techniques include evicting the identified eviction candidates from the on-disk dedupe index.
1 . A method comprising:
providing a plurality of deduplication (“dedupe”) indexes across a memory level and a disk level of a storage system, the plurality of dedupe indexes including an in-memory dedupe index at the memory level, and an on-disk dedupe index at the disk level, the plurality of dedupe indexes for use by the storage system in performing data deduplication operations;
applying a plurality of eviction rules regarding evicting digest entries of the on-disk dedupe index, the plurality of eviction rules avoiding random evictions of digest entries from the on-disk dedupe index;
in response to applying the plurality of eviction rules, identifying a number of digest entries of the on-disk dedupe index as eviction candidates; and
evicting the identified eviction candidates from the on-disk dedupe index,
wherein each of the plurality of dedupe indexes includes a plurality of digest entries, each digest entry including a digest of a stored dataset and a pointer to information pertaining to a location of the stored dataset, and
wherein the applying a plurality of eviction rules includes:
applying a first eviction rule including avoiding removing or evicting digest entries for stored datasets pointed to by virtual pointers having a reference count with a first value greater than a predetermined maximum reference count;
applying a second eviction rule including preferring removing or evicting digest entries for stored datasets pointed to by virtual pointers having the predetermined maximum reference count;
applying a third eviction rule including preferring removing or evicting digest entries for stored datasets deemed non-deduplicable; and
applying a fourth eviction rule including avoiding removing or evicting “clean” digest entries previously destaged from the in-memory dedupe index.
2 . The method of claim 1 wherein the applying a first eviction rule includes, in response to a reference count of a virtual pointer being updated to the first value greater than the predetermined maximum reference count from a second value less than the first value, adding a corresponding “dirty” digest entry to the in-memory dedupe index, the corresponding dirty digest entry not being previously destaged to the on-disk dedupe index.
3 . The method of claim 1 wherein the applying a second eviction rule includes preferring removing or evicting, from the in-memory dedupe index, digest entries for stored datasets pointed to by virtual pointers having the predetermined maximum reference.
4 . The method of claim 3 further comprising:
logging updates to digest entries of the in-memory dedupe index in a dedupe log, and
wherein the applying a second eviction rule includes preferring removing or evicting, from the on-disk dedupe index, digest entries for stored datasets pointed to by virtual pointers having the predetermined maximum reference count, using the logged updates in the dedupe log.
5 . The method of claim 1 wherein each digest entry includes a binary indication of whether the stored dataset is deduplicable or non-deduplicable, and wherein the applying a third eviction rule includes determining that a stored dataset is deemed non-deduplicable based on the binary indication.
6 . The method of claim 5 wherein the applying a third eviction rule includes avoiding destaging the stored dataset deemed non-deduplicable to the on-disk dedupe index.
7 . The method of claim 5 wherein the determining that a stored dataset is deemed non-deduplicable includes determining that a corresponding digest entry is a clean digest entry previously destaged to the on-disk dedupe index, and avoiding updating the binary indication of the clean digest entry.
8 . The method of claim 1 further comprising:
determining a target number of the eviction candidates based on one or more of a maximum number of digest entries that the on-disk dedupe index can accommodate, a current number of digest entries in the on-disk dedupe index, a number of digest entries to be destaged from the in-memory dedupe index, and a number of digest entries for datasets pointed to by virtual pointers whose reference counts have been updated.
9 . The method of claim 8 further comprising:
determining that the number of digest entries of the on-disk dedupe index identified as eviction candidates does not meet the target number of the eviction candidates; and
repeating applying at least the second eviction rule and the third eviction rule.
10 . The method of claim 8 further comprising:
determining that the number of digest entries of the on-disk dedupe index identified as eviction candidates meets the target number of the eviction candidates; and
having evicted the identified eviction candidates from the on-disk dedupe index, destaging digest entries from the in-memory dedupe index to the on-disk dedupe index.
11 . A system comprising:
a memory; and
processing circuitry configured to execute program instructions out of the memory to:
provide a plurality of deduplication (“dedupe”) indexes across a memory level and a disk level of the system, the plurality of dedupe indexes including an in-memory dedupe index at the memory level, and an on-disk dedupe index at the disk level, the plurality of dedupe indexes for use in performing data deduplication operations;
apply a plurality of eviction rules regarding evicting digest entries of the on-disk dedupe index, the plurality of eviction rules avoiding random evictions of digest entries from the on-disk dedupe index;
in response to applying the plurality of eviction rules, identify a number of digest entries of the on-disk dedupe index as eviction candidates; and
evict the identified eviction candidates from the on-disk dedupe index,
wherein each of the plurality of dedupe indexes includes a plurality of digest entries, each digest entry including a digest of a stored dataset and a pointer to information pertaining to a location of the stored dataset, and
wherein the processing circuitry is configured to execute the program instructions out of the memory to:
apply a first eviction rule including avoiding removing or evicting digest entries for stored datasets pointed to by virtual pointers having a reference count with a first value greater than a predetermined maximum reference count;
apply a second eviction rule including preferring removing or evicting digest entries for stored datasets pointed to by virtual pointers having the predetermined maximum reference count;
apply a third eviction rule including preferring removing or evicting digest entries for stored datasets deemed non-deduplicable; and
apply a fourth eviction rule including avoiding removing or evicting “clean” digest entries previously destaged from the in-memory dedupe index.
12 . The system of claim 11 wherein the processing circuitry is configured to execute the program instructions out of the memory, in response to a reference count of a virtual pointer being updated to the first value greater than the predetermined maximum reference count from a second value less than the first value, to add a corresponding “dirty” digest entry to the in-memory dedupe index, the corresponding dirty digest entry not being previously destaged to the on-disk dedupe index.
13 . The system of claim 11 wherein the processing circuitry is configured to execute the program instructions out of the memory to prefer removing or evicting, from the in-memory dedupe index, digest entries for stored datasets pointed to by virtual pointers having the predetermined maximum reference count.
14 . The system of claim 13 wherein the processing circuitry is configured to execute the program instructions out of the memory to:
log updates to digest entries of the in-memory dedupe index in a dedupe log, and
prefer removing or evicting, from the on-disk dedupe index, digest entries for stored datasets pointed to by virtual pointers having the predetermined maximum reference count, using the logged updates in the dedupe log.
15 . The system of claim 11 wherein each digest entry includes a binary indication of whether the stored dataset is deduplicable or non-deduplicable, and wherein the processing circuitry is configured to execute the program instructions out of the memory to determine that a stored dataset is deemed non-deduplicable based on the binary indication.
16 . The system of claim 15 wherein the processing circuitry is configured to execute the program instructions out of the memory to avoid destaging the stored dataset deemed non-deduplicable to the on-disk dedupe index.
17 . The system of claim 15 wherein the processing circuitry is configured to execute the program instructions out of the memory to:
determine that a corresponding digest entry is a clean digest entry previously destaged to the on-disk dedupe index; and
avoid updating the binary indication of the clean digest entry.
18 . A computer program product including a set of non-transitory, computer-readable media having instructions that, when executed by processing circuitry, cause the processing circuitry to perform a method comprising:
providing a plurality of deduplication (“dedupe”) indexes across a memory level and a disk level of a storage system, the plurality of dedupe indexes including an in-memory dedupe index at the memory level, and an on-disk dedupe index at the disk level, the plurality of dedupe indexes for use by the storage system in performing data deduplication operations;
applying a plurality of eviction rules regarding evicting digest entries of the on-disk dedupe index, the plurality of eviction rules avoiding random evictions of digest entries from the on-disk dedupe index;
in response to applying the plurality of eviction rules, identifying a number of digest entries of the on-disk dedupe index as eviction candidates; and
evicting the identified eviction candidates from the on-disk dedupe index,
wherein each of the plurality of dedupe indexes includes a plurality of digest entries, each digest entry including a digest of a stored dataset and a pointer to information pertaining to a location of the stored dataset, and
wherein the applying a plurality of eviction rules includes:
applying a first eviction rule including avoiding removing or evicting digest entries for stored datasets pointed to by virtual pointers having a reference count with a first value greater than a predetermined maximum reference count;
applying a second eviction rule including preferring removing or evicting digest entries for stored datasets pointed to by virtual pointers having the predetermined maximum reference count;
applying a third eviction rule including preferring removing or evicting digest entries for stored datasets deemed non-deduplicable; and
applying a fourth eviction rule including avoiding removing or evicting “clean” digest entries previously destaged from the in-memory dedupe index.