Memory use and eviction in a deduplication storage system

Patent metadata

Field	Value
Publication number	US-9940060-B1
Application number	US-201615331181-A
Country	US
Kind code	B1
Filing date	Oct 21, 2016
Priority date	May 2, 2016
Publication date	Apr 10, 2018
Grant date	Apr 10, 2018

Abstract

The method includes storing data including an index summary (IS) and a deduplication map (DDM) in volatile memory of a deduplication system. The method also includes detecting that the stored data exceeds a data allocation size limit for the volatile memory. The method includes evicting the data from the volatile memory using a memory eviction policy to meet the data allocation size limit. The method further includes performing a first eviction by evicting the DDM levels from an oldest DDM level to a newest DDM level until a first one of the data allocation size limit or a DDM threshold is met. The method also includes performing a second eviction by evicting the IS levels from an oldest IS level to a newest IS level until a first one of the data allocation size limit or IS threshold is met in response to the data allocation size limit not being met by the first eviction.

First claim

What is claimed is:

1. A method comprising:
storing data comprising an index summary (IS) and a deduplication map (DDM) in volatile memory of a deduplication system, wherein the index summary comprises IS levels and accelerates lookup into the deduplication map, wherein the deduplication map comprises DDM levels and identifies locations of data blocks in a persistent storage resource of the deduplication system;
detecting that the stored data exceeds a data allocation size limit for the volatile memory; and
evicting the data from the volatile memory using a memory eviction policy to meet the data allocation size limit, wherein evicting using the memory eviction policy comprises:
performing a first eviction by evicting the DDM levels from an oldest DDM level to a newest DDM level until a first one of the data allocation size limit or a DDM threshold is met; and
responsive to the data allocation size limit not being met by the first eviction, performing a second eviction by evicting the IS levels from an oldest IS level to a newest IS level until a first one of the data allocation size limit or IS threshold is met.

2. The method of claim 1 , wherein evicting using the memory eviction policy further comprises:
responsive to the data allocation size limit not being met by the second eviction, performing a third eviction by evicting the DDM levels from the oldest DDM level to the newest DDM level; and
responsive to the data allocation size limit not being met by the third eviction, performing a fourth eviction by evicting the IS levels from oldest IS level to the newest IS level.

3. The method of claim 1 , wherein the DDM levels from the oldest DDM level to the newest DDM level are determined by a time order of writes of the data blocks to the persistent storage resource, wherein the writes of the data blocks are responsive to inline deduplication or background deduplication.

4. The method of claim 3 , wherein the IS levels from the oldest IS level to the newest IS level are determined by the time order of writes of the data blocks to the persistent storage resource, and wherein the IS levels correspond to the DDM levels of the deduplication map.

5. The method of claim 4 , wherein the IS levels from the oldest IS level to the newest IS level and the DDM levels from the oldest DDM level to the newest DDM level are further determined by a time order of deduplication of the data blocks in the background deduplication.

6. The method of claim 1 , wherein the IS levels of index summary comprise partial hash values of the data blocks stored in the persistent storage resource, wherein the DDM levels of the deduplication map correspond to the IS levels of the index summary and comprise complete hash values of the data blocks, wherein the index summary accelerates lookup into the deduplication map by linking partial hash values of the index summary to specific areas of the deduplication map used to accelerate a search of the deduplication map for complete hash values and identifiers of the locations of the data blocks in the persistent storage resource of the deduplication system.

7. The method of claim 1 , further comprising:
performing inline deduplication of an incoming data block using the data remaining in the volatile memory in view of the eviction using the memory eviction policy.

8. The method of claim 7 , wherein performing the inline deduplication of the incoming data block using the data remaining in the volatile memory in view of eviction using the memory eviction policy, further comprises:
generating a hash value for the incoming data block;
comparing the hash value for the incoming data block to the index summary in volatile memory to determine a match; and
responsive to determining the match does not exist, discontinuing the inline deduplication of the incoming data block.

9. The method of claim 8 , wherein performing the inline deduplication of the incoming data block using the data remaining in the volatile memory in view of eviction using the memory eviction policy, further comprises:
responsive to determining the match exists, comparing the hash value for the incoming data block to the deduplication map in volatile memory rather than the deduplication map in the persistent storage resource.

10. The method of claim 1 , wherein the volatile memory is random access memory.

11. A deduplication system comprising:
a persistent storage resource;
a volatile memory; and
a processing device, operatively coupled to the persistent storage resource and volatile memory, to:
store data comprising an index summary (IS) and a deduplication map (DDM) in the volatile memory of the deduplication system, wherein the index summary comprises IS levels and accelerates lookup into the deduplication map, wherein the deduplication map comprises DDM levels and identifies locations of data blocks in the persistent storage resource of the deduplication system;
detect that the stored data exceeds a data allocation size limit for the volatile memory; and
evict the data from the volatile memory using a memory eviction policy to meet the data allocation size limit, wherein evicting using the memory eviction policy comprises:
perform a first eviction by evicting the DDM levels from an oldest DDM level to a newest DDM level until a first one of the data allocation size limit or a DDM threshold is met; and
responsive to the data allocation size limit not being met by the first eviction, perform a second eviction by evicting the IS levels from an oldest IS level to a newest IS level until a first one of the data allocation size limit or IS threshold is met.

12. The deduplication system of claim 11 , wherein to evict using the memory eviction policy, the processing device further to:
responsive to the data allocation size limit not being met by the second eviction, perform a third eviction by evicting the DDM levels from the oldest DDM level to the newest DDM level; and
responsive to the data allocation size limit not being met by the third eviction, perform a fourth eviction by evicting the IS levels from oldest IS level to the newest IS level.

13. The deduplication system of claim 11 , the processing device further to:
perform inline deduplication of an incoming data block using the data remaining in the volatile memory in view of the eviction using the memory eviction policy.

14. The deduplication system of claim 13 , wherein to perform the inline deduplication of the incoming data block using the data remaining in the volatile memory in view of eviction using the memory eviction policy, the processing device further to:
generate a hash value for the incoming data block;
compare the hash value for the incoming data block to the index summary in volatile memory to determine a match; and
responsive to determining the match does not exist, discontinue the inline deduplication of the incoming data block.

15. The deduplication system of claim 14 , wherein to perform the inline deduplication of the incoming data block using the data remaining in the volatile memory in view of eviction using the memory eviction policy, the processing device further to:
responsive to determining the match exists, compare the hash value for the incoming data block to the deduplication map in volatile memory rather than the deduplication map in the persistent storage resource.

16. A non-transitory computer-readable storage medium comprising instruction that, in response to execution by a processing device, cause the processing device to:
store data comprising an index summary (IS) and a deduplication map (DDM) in volat

Assignees

• Pure Storage Inc

Inventors

• Colgrove John
• Karr Ronald
• Miller Ethan L
• Perneti Vinay K
• Sandvig Cary A
• Wang Feng
• Zhang Wei

Classifications

• G06F3/0685

  Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays · CPC title

• G06F3/0611

  in relation to response time · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title

• G06F3/0641 Primary

  De-duplication techniques · CPC title