System and method for managing a deduplication table

• US 9,805,048 B2
• Filed: 10/18/2012
• Issued: 10/31/2017
• Est. Priority Date: 10/18/2012
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Week, Lisa, Maybee, Mark
• Primary Examiner(s): Yi, David X
• Assistant Examiner(s): GRULLON, FRANCISCO A
• Application Number:
  US13/655,035
• Publication Number:
  US 20140115258A1
• Time in Patent Office: 1,839 Days
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 12/127 using additional replacement algorithms
• CPC Class Codes: G06F 16/1752 based on file chunks

Abstract

Implementations described and claimed herein provide systems and methods for allocating and managing resources for a deduplication table. In one implementation, an upper limit to an amount of memory allocated to a deduplication table is established. The deduplication table has one or more checksum entries, and each checksum entry is associates a checksum with unique data. A new checksum entry corresponding to new unique data is prevented from being added to the deduplication table where adding the new checksum entry will cause the deduplication table to exceed a size limit. The new unique data has a checksum that is different from the checksums in the one or more checksum entries in the deduplication table.

Claims

1. A method comprising:

preventing an amount of memory of a level one cache allocated to a deduplication table from being less than a current size of the deduplication table stored in the level one cache;

establishing an upper limit to the amount of a level one cache allocated to a deduplication table using at least one processor, the deduplication table having one or more secure hash entries, each secure hash entry associating a secure hash value with unique data, the upper limit preventing the deduplication table from growing unbounded and maintaining an entirety of the deduplication table in only the level one cache; and

preventing, using the at least one processor, a new secure hash entry corresponding to new unique data from being added to the deduplication table where adding the new secure hash entry will cause the deduplication table to exceed the upper limit, the new unique data having a secure hash value that is different from the secure hash values in the one or more secure hash entries in the deduplication table.

2. The method of claim 1, wherein the level one cache allocated to the deduplication table is direct random access memory based cache.

3. The method of claim 1, wherein the upper limit is less than a maximum capacity of the level one cache.

4. The method of claim 1 further comprising:

writing the new unique data to a storage location.

5. The method of claim 1 further comprising:

removing at least one of the one or more secure hash entries in the deduplication table to create space for at least one new secure hash entry.

6. The method of claim 5, wherein the at least one secure hash entry is removed based on user input.

7. The method of claim 5, wherein the at least one secure hash entry is removed based on a reference count entry associated with the at least one secure hash entry, the reference count entry indicating a number of write requests for duplicate copies of data by incrementing a reference count each time a write request is received for data having a duplicate secure hash value that matches one of the secure hash entries in the deduplication table.

8. The method of claim 7, wherein the at least one secure hash entry is removed when the reference count entry is zero for a time period.

9. The method of claim 8, wherein the time period is set by a user.

10. The method of claim 1, wherein each secure hash entry is a checksum entry and the secure hash values are checksum values.

11. One or more non-transitory tangible computer-readable storage media storing computer-executable instructions for performing a computer process on a computing system, the computer process comprising:

storing an entirety of a deduplication table in a level one cache being only one level of cache memory, the deduplication table having one or more secure hash entries, each secure hash entry associating a secure hash value with unique data;

preventing the deduplication table from growing unbounded by establishing an upper limit to an amount of the level one cache allocated to a the deduplication table, the upper limit keeping the entirety of the deduplication table resident in the level one cache;

preventing the amount of the level one cache allocated to the deduplication table from being less than a current size of the deduplication table and larger than a maximum capacity of the level one cache; and

preventing a new secure hash entry corresponding to new unique data from being added to the deduplication table where adding the new secure hash entry will cause the deduplication table to exceed the upper limit, the new unique data having a secure hash value that is different from the secure hash values in the one or more secure hash entries in the deduplication table.

12. The one or more non-transitory tangible computer-readable storage media of claim 11, the computer process further comprising:

removing at least one of the one or more secure hash entries in the deduplication table to create space for at least one new secure hash entry.

13. The one or more non-transitory tangible computer-readable storage media of claim 12, wherein the at least one secure hash entry is removed based on user input.

14. A system comprising:

a level one cache having one level of direct random access memory based cache storing an entirety of a deduplication table having one or more secure hash entries, each secure hash entry associating a secure hash value with unique data; and

a deduplication module executable by at least one processor, the deduplication module allocating an amount of memory in the level one cache to the deduplication table, the deduplication module preventing the amount of memory in the level one cache from being less than a current size of the deduplication table, the deduplication module establishing an upper limit to an amount of the one level of direct random access memory based cache of the level one cache allocated to a the deduplication table to retain the entirety of the deduplication table in the one level of direct random access memory based cache of the level one cache by precluding the deduplication table from growing unbounded, the deduplication module preventing a new secure hash entry corresponding to new unique data from being added to the deduplication table where adding the new secure hash entry will cause the deduplication table to exceed the upper limit, the new unique data having a secure hash value that is different from the secure hash values in the one or more secure hash entries in the deduplication table.

15. The system of claim 14, wherein the upper limit is less than a maximum capacity of the one level of direct random access memory based cache of the level one cache.

16. The system of claim 14, wherein the deduplication module is further configured to remove at least one of the one or more secure hash entries in the deduplication table to create space for at least one new secure hash entry.

17. The system of claim 16, wherein the deduplication module removes the at least one secure hash entry from the deduplication table based on user input.

18. The system of claim 16, wherein the deduplication module removes the at least one secure hash entry from the deduplication table based on a reference count entry associated with the at least one secure hash entry, the reference count entry indicating a number of write requests for duplicate copies of data by incrementing a reference count each time a write request is received for data having a duplicate secure hash value that matches one of the secure hash entries in the deduplication table.