System and method for high performance deduplication indexing

• US 8,370,315 B1
• Filed: 05/28/2010
• Issued: 02/05/2013
• Est. Priority Date: 05/28/2010
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Efstathopoulos, Petros, Guo, Fanglu
• Primary Examiner(s): NGUYEN, MERILYN P
• Application Number:
  US12/790,461
• Time in Patent Office: 984 Days
• Field of Search: 707/696, 707/697, 707/699, 707/715, 707/769
• US Class Current: 707/696
• CPC Class Codes: G06F 16/174 Redundancy elimination performed by the file system management of the data involved in backup or backup restore using de-duplication of the data G06F11/14
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06F 16/2228 Indexing structures

Abstract

A system and method for efficiently reducing latency of accessing an index for a data segment stored on a server. A server both removes duplicate data and prevents duplicate data from being stored in a shared data storage. The file server is coupled to an index storage subsystem holding fingerprint and pointer value pairs corresponding to a data segment stored in the shared data storage. The pairs are stored in a predetermined order. The file server utilizes an ordered binary search tree to identify a particular block of multiple blocks within the index storage subsystem corresponding to a received memory access request. The index storage subsystem determines whether an entry corresponding to the memory access request is located within the identified block. Based on at least this determination, the file server processes the memory access request accordingly. In one embodiment, the index storage subsystem is a solid-state disk (SSD).

Claims

1. A computer system comprising:

a server comprising a processor and a memory;

an index comprising a plurality of blocks, wherein each block comprises a plurality of entries, each entry including a fingerprint and an identifier which identifies where a corresponding data segment is stored within a data storage subsystem;

wherein in response to receiving a storage access request corresponding to a given fingerprint, the server is configured to;

access a data structure comprising a plurality of entries, wherein each entry of the plurality of entries identifies a block of the plurality of blocks, and a fingerprint corresponding to a first entry of the block;

responsive to said access of the data structure, identify a particular block of the plurality of blocks corresponding to the storage access request; and

responsive to identifying the particular block, send a query corresponding

to the particular block to the index;

wherein in response to the query, the index is configured to convey a response to the server that indicates whether the given fingerprint is included within the particular block;

wherein the plurality of blocks of the index are sorted based on a value of an entry in a given block, and wherein responsive to said access of the data structure the particular block identified is one of;

a block in the index whose first entry includes a fingerprint value that is a smallest value of all first entry fingerprint values that are greater than the given fingerprint; and

a block with a first entry including a fingerprint value that is a largest value of all first entry fingerprint values that are less than the given fingerprint.

2. The system as recited in claim 1, wherein the data structure comprises a binary search tree, and wherein the index is stored on a solid-state disk (SSD).

3. The system as recited in claim 1, wherein said data structure is searched based on a fingerprint value.

4. The system as recited in claim 2, wherein the server is further configured to store a subset of the index in a cache, and wherein prior to accessing the index stored on the SSD, the server is configured to access said subset to determine whether the particular block is included therein.

5. The system as recited in claim 3, wherein the server is further configured to prefetch information from the index to be stored in the cache, in response to sending the query to the index, wherein the prefetched information has a spatial or temporal locality associated with the query.

6. The system as recited in claim 1, wherein the server is further configured to store the storage access request in a write buffer in response to determining the memory access request is a write request and the query results in a miss.

7. The system as recited in claim 6, wherein the server is further configured to add new entries to the index in a manner that preserves a sort order of the index.

8. A computer implemented method comprising:

maintaining an index comprising a plurality of blocks, wherein each block comprises a plurality of entries, each entry including a fingerprint and an identifier which identifies where a corresponding data segment is stored within a data storage subsystem;

receiving a memory access request at a server;

accessing a data structure comprising a plurality of entries, wherein each entry of the plurality of entries identifies a block of the plurality of blocks, and a fingerprint corresponding to a first entry of the block;

responsive to said access of the data structure, identifying a particular block of the plurality of blocks corresponding to the storage access request;

responsive to identifying the particular block the server sending a query corresponding to the particular block to the index;

the index conveying a response to the server that indicates whether the given fingerprint is included within the particular block, responsive to the query;

wherein the plurality of blocks of the index are sorted based on a value of an entry in a given block, and wherein responsive to said accessing of the data structure the particular block identified is one of;

a block in the index whose first entry includes a fingerprint value that is a smallest value of all first entry fingerprint values that are greater than the given fingerprint; and

a block with a first entry including a fingerprint value that is a largest value of all first entry fingerprint values that are less than the given fingerprint.

9. The method as recited in claim 8, wherein the data structure comprises a binary search tree within a first device, and wherein the index is stored on a solid-state disk (SSD) separate from the first device.

10. The method as recited in claim 9, wherein the server is further configured to store a subset of the index in a cache, and wherein prior to accessing the index stored on the SSD, the method comprises the server accessing said subset to determine whether the particular block is included therein.

11. The method as recited in claim 10, wherein the method further comprises the server prefetching information from the index to be stored in the cache, in response to sending the query to the index, wherein the prefetched information has a spatial or temporal locality associated with the query.

12. The method as recited in claim 8, further comprising searching the data structure based on a fingerprint value.

13. The method as recited in claim 8, wherein the server is further configured to store the memory access request in a write buffer in response to determining the memory access request is a write request and the query results in a miss.

14. The method as recited in claim 13, further comprising the server adding new entries to the index in a manner that preserves a sort order of the index.

15. A non-transitory computer-readable medium storing program instructions that are executable to:

maintain an index comprising a plurality of blocks, wherein each block comprises a plurality of entries, each entry including a fingerprint and an identifier which identifies where a corresponding data segment is stored within a data storage subsystem;

receive a storage access request at a server;

access a data structure comprising a plurality of entries, wherein each entry of the plurality of entries identifies a block of the plurality of blocks, and a fingerprint corresponding to a first entry of the block;

responsive to said access of the data structure, identify a particular block of the plurality of blocks corresponding to the storage access request;

responsive to identifying the particular block, cause the server to send a query corresponding to the particular block to the index; and

cause the index to convey a response to the server that indicates whether the given fingerprint is included within the particular block, responsive to the query;

wherein the instructions are further executable to sort the plurality of blocks of the index based on a value of an entry in a given block, and wherein responsive to said access of the data structure the particular block identified is one of;

a block in the index whose first entry includes a fingerprint value that is a smallest value of all first entry fingerprint values that are greater than the given fingerprint; and

a block with a first entry including a fingerprint value that is a largest value of all first entry fingerprint values that are less than the given fingerprint.

16. The non-transitory computer-readable medium as recited in claim 15, wherein the data structure comprises a binary search tree within a first device, and wherein the index is stored on a second device separate from the first device.

17. The non-transitory computer-readable medium as recited in claim 16, wherein the second device is an SSD device.