Methods to efficiently implement coarse granularity cache eviction based on segment deletion hints

Patent metadata

Field	Value
Publication number	US-9720835-B1
Application number	US-201514609839-A
Country	US
Kind code	B1
Filing date	Jan 30, 2015
Priority date	Jan 30, 2015
Publication date	Aug 1, 2017
Grant date	Aug 1, 2017

Abstract

A data processing system and methods for performing cache eviction are disclosed. An exemplary method includes maintaining a metadata set for each cache unit of a cache device, wherein the cache device comprises a plurality of cache units, each cache unit having a plurality of segments, wherein each metadata set includes deletion hints (DH) metadata indicating whether the plurality of segments of a corresponding cache unit are valid. The exemplary method further includes in response to determining that a cache eviction is to be performed, selecting a predetermined number of cache units from the plurality of cache units, and determining a score for each of the selected cache units based on the DH metadata of the respective metadata set. The DH metadata may include, for example, a validation count for each segment group or cache unit. A deprecated segment can be changed back to being valid, and the score for each of the selected cache units may further be determined based on a determined probability.

First claim

What is claimed is:

1. A computer-implemented method, the method comprising:
maintaining a metadata set for each cache unit of a cache device, wherein the cache device comprises a plurality of cache units, each cache unit having a plurality of segments, wherein each metadata set includes deletion hints (DH) metadata indicating whether each of the plurality of segments of a corresponding cache unit is valid or deprecated, wherein each of the plurality of segments can chance from being valid to being deprecated, wherein each deprecated segment can change back to being valid;
in response to determining that a cache eviction is to be performed:
selecting a predetermined number of cache units from the plurality of cache units, and
determining a score for each of the selected cache units based on the DH metadata of the respective metadata set; and

evicting one or more of the selected predetermined number of cache units based on their respective scores.

2. The method of claim 1 , wherein maintaining the metadata set for each cache unit of the cache device comprises:
receiving DHs of a set of one or more segments from a cache client;
identifying one or more cache units that contain one or more segments of the set of one or more segments; and
updating the DH metadata of the identified one or more cache units.

3. The method of claim 1 , wherein maintaining the metadata set for each cache unit of the cache device comprises maintaining the NI metadata of each metadata set at a segment granularity.

4. The method of claim 1 , wherein maintaining the metadata set for each cache unit of the cache device comprises maintaining the NI metadata of each metadata set at a segment group granularity.

5. The method of claim 1 , wherein maintaining the metadata set for each cache unit of the cache device comprises maintaining the NI metadata of each metadata set at a cache unit granularity.

6. The method of claim 1 , wherein maintaining the metadata set for each cache unit of the cache device comprises maintaining a bit map, wherein each bit of the bit map indicates a DH of a segment.

7. The method of claim 1 , wherein maintaining the metadata set for each cache unit of the cache device comprises maintaining a validation count for each segment group, wherein each validation count indicates a total number of valid segments in a respective segment group.

8. The method of claim 1 , wherein maintaining the metadata set for each cache unit of the cache device comprises maintaining a validation count for each cache unit, wherein each validation count indicates a total number of valid segments in a respective cache unit.

9. The method of claim 1 , wherein the method further comprises:
determining a probability of a deprecated segment changing back to being valid; and
determining the score for each cache unit of the selected predetermined number of cache units further based on the determined probability.

10. The method of claim 9 , wherein the probability of a deprecated segment changing back to being valid is calculated at a sub-cache granularity, wherein the sub-cache granularity is one of per file, folder, or volume, and wherein the calculated probability for a particular granularity is used in determining the score for the corresponding cache unit.

11. The method of claim 1 , further comprising:
copying one or more valid segments of the evicted one or more cache units to one or more other cache units.

12. A non-transitory computer-readable storage medium having computer code stored therein, which when executed by a processor, causes the processor to perform operations comprising:
maintaining a metadata set for each cache unit of a cache device, wherein the cache device comprises a plurality of cache units, each cache unit having a plurality of segments, wherein each metadata set includes deletion hints (DH) metadata indicating whether each of the plurality of segments of a corresponding cache unit is valid or deprecated, wherein each of the plurality of segments can change from being valid to being deprecated, wherein each deprecated segment can change back to being valid;
in response to determining that a cache eviction is to be performed:
selecting a predetermined number of cache units from the plurality of cache units, and
determining a score for each of the selected cache units based on the DH metadata of the respective metadata set; and

evicting one or more of the selected predetermined number of cache units based on their respective scores.

13. The non-transitory computer-readable storage medium of claim 12 , wherein maintaining the metadata set for each cache unit of the cache device comprises:
receiving DHs of a set of one or more segments from a cache client;
identifying one or more cache units that contain one or more segments of the set of one or more segments; and
updating the DH metadata of the identified one or more cache units.

14. The non-transitory computer-readable storage medium of claim 12 , wherein maintaining the metadata set for each cache unit of the cache device comprises maintaining the DH metadata of each metadata set at a segment granularity.

15. The non-transitory computer-readable storage medium of claim 12 , wherein maintaining the metadata set for each cache unit of the cache device comprises maintaining the DH metadata of each metadata set at a segment group granularity.

16. The non-transitory computer-readable storage medium of claim 12 , wherein maintaining the metadata set for each cache unit of the cache device comprises maintaining the DH metadata of each metadata set at a cache unit granularity.

17. The non-transitory computer-readable storage medium of claim 12 , wherein maintaining the metadata set for each cache unit of the cache device comprises maintaining a bit map, wherein each bit of the bit map indicates a DH of a segment.

18. The non-transitory computer-readable storage medium of claim 12 , wherein maintaining the metadata set for each cache unit of the cache device comprises maintaining a validation count for each segment group, wherein each validation count indicates a total number of valid segments in a respective segment group.

19. The non-transitory computer-readable storage medium of claim 12 , wherein maintaining the metadata set for each cache unit of the cache device comprises maintaining a validation count for each cache unit, wherein each validation count indicates a total number of valid segments in a respective cache unit.

20. The non-transitory computer-readable storage medium of claim 12 , wherein the operations further comprise:
determining a probability of a deprecated segment changing back to being valid; and
determining the score for each cache unit of the selected predetermined number of cache units further based on the determined probability.

21. The non-transitory computer-readable storage medium of claim 20 , wherein the probability of a deprecated segment changing back to being valid is calculated at a sub-cache granularity, wherein the sub-cache granularity is one of per file, folder, or volume, and wherein the calculated probability for a particular granularity is used in determining the score for the corresponding cache unit.

22. The non-transitory computer-readable storage medium of claim 12 , further comprising:
copying one or more valid segments of the evicted one or more cache units to one or more other cache units.

23. A data processing system, comprising:
a cache device comprisi

Assignees

• Emc Ip Holding Co Llc

Inventors

• Shilane Philip
• Wallace Grant
• Douglis Frederick
• Li Cheng

Classifications

• G06F12/126 Primary

  with special data handling, e.g. priority of data or instructions, handling errors or pinning · CPC title

• G06F2212/62

  Details of cache specific to multiprocessor cache arrangements · CPC title

• G06F2212/69

  Physics · mapped topic

• G06F12/121

  using replacement algorithms · CPC title

• G06F12/0833 Primary

  in combination with broadcast means (e.g. for invalidation or updating) · CPC title