Client side data deduplication

• US 7,814,149 B1
• Filed: 09/29/2008
• Issued: 10/12/2010
• Est. Priority Date: 09/29/2008
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (Gen Digital Inc.)
• Inventors: Stringham, Russell R.
• Primary Examiner(s): Tran; Philip B
• Application Number:
  US12/240,441
• Time in Patent Office: 743 Days
• Field of Search: 709/203, 709217-219, 709223-224, 707/999.003, 707/999.004, 707/758
• US Class Current: 709/203
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Methods and systems that use a client locality table when performing client-side data deduplication are disclosed. One method involves searching one or more client locality tables for the signature of a data unit (e.g., a portion of a volume or file). The client locality tables include signatures of data units stored in a deduplicated data store. If the signature is not found in the client locality tables, the signature is sent from a deduplication client to a deduplication server and added to one of the client locality tables. If instead the signature is found in the client locality tables, sending of the new signature to the deduplication server is inhibited.

Claims

1. A method comprising:

searching one or more client locality tables for a new signature of a new data unit, wherein the one or more client locality tables comprise signatures of data units stored in a deduplicated data store;

sending the new signature from a deduplication client to a deduplication server and adding the new signature to one of the one or more client locality tables, in response to not finding the new signature in the one or more client locality tables; and

inhibiting sending of the new signature from the deduplication client to the deduplication server, in response to finding the new signature in the one or more client locality tables.

2. The method of claim 1, wherein the one or more client locality tables comprise a first signature added to the one or more client locality tables by the deduplication client during a first deduplication session and a second signature added to the one or more client locality tables by the deduplication client during a second deduplication session.

3. The method of claim 1, further comprising:

receiving an identifier identifying the new data unit from the deduplication server, in response to sending the new signature to the deduplication server; and

storing the identifier in one of the one or more client locality tables, wherein the storing the identifier associates the identifier with the new signature.

4. The method of claim 3, further comprising sending a request to retrieve the new data unit to the deduplication server, wherein the request comprises the identifier but not the new signature.

5. The method of claim 3, further comprising sending a request to retrieve a data object comprising the new data unit to the deduplication server, wherein the request comprises a run list, and wherein the run list specifies a range of one or more identifiers that comprises the identifier.

6. The method of claim 3, wherein the identifier comprises at least one of:

a sequence number and a session identifier.

7. The method of claim 1, further comprising copying the one or more client locality tables from a first client computing device to a second client computing device, wherein the second client computing device implements the deduplication client.

8. The method of claim 1, further comprising accessing a client pointer table, in response to not finding the new signature in a cached one of the one or more client locality tables, wherein the pointer table indicates a subset of a set of signatures maintained by the deduplication client.

9. The method of claim 8, further comprising loading a new client locality table into a cache, in response to finding the new signature in the subset of the signatures indicated by the pointer table, wherein the new locality table comprises the new signature.

10. The method of claim 8, wherein the accessing the pointer table comprises using a portion of the new signature as an index into the pointer table.

11. A computer readable non-transitory storage medium storing executable program instructions, wherein, when executed, the executable program instructions are configured to implement a deduplication client, and wherein the deduplication client is configured to:

search one or more client locality tables for a new signature of a new data unit, wherein the one or more client locality tables comprise signatures of data units stored in a deduplicated data store;

send the new signature to a deduplication server and add the new signature to one of the one or more client locality tables, in response to not finding the new signature in the one or more client locality tables; and

inhibit sending of the new signature to the deduplication server, in response to finding the new signature in the one or more client locality tables.

12. The computer readable non-transitory storage medium of claim 11, wherein the one or more client locality tables comprise a first signature added to the one or more client locality tables by the deduplication client during a first deduplication session and a second signature added to the one or more client locality tables by the deduplication client during a second deduplication session.

13. The computer readable non-transitory storage medium of claim 11, wherein the deduplication client is further configured to:

receive an identifier identifying the new data unit from the deduplication server, in response to sending the new signature to the deduplication server; and

store the identifier in one of the one or more client locality tables, wherein storing the identifier in the one of the one or more client locality tables associates the identifier with the new signature.

14. The computer readable non-transitory storage medium of claim 13, wherein the deduplication client is further configured to send a request to retrieve the new data unit to the deduplication server, wherein the request comprises the identifier but not the new signature.

15. The computer readable non-transitory storage medium of claim 13, wherein the deduplication client is further configured to send a request to retrieve a data object comprising the new data unit to the deduplication server, wherein the request comprises a run list, and wherein the run list specifies a range of one or more identifiers that comprises the identifier.

16. The computer readable non-transitory storage medium of claim 11, wherein the one or more client locality tables were generated by a different deduplication client.

17. The computer readable non-transitory storage medium of claim 11, wherein the deduplication client is further configured to access a client pointer table, in response to not finding the new signature in a cached one of the one or more client locality tables, wherein the pointer table indicates a subset of a set of signatures maintained by the deduplication client.

18. The computer readable non-transitory storage medium of claim 17, wherein the deduplication client is further configured to load a new client locality table into a cache, in response to finding the new signature in the subset of the signatures indicated by the pointer table, wherein the new locality table comprises the new signature.

19. The computer readable non-transitory storage medium of claim 17, wherein accessing the pointer table comprises using a portion of the new signature as an index into the pointer table.

20. A system comprising:

storage means for storing one or more client locality tables, wherein the one or more client locality tables comprise signatures of data units stored in a deduplicated data store;

data deduplication client means, wherein the data deduplication client means;

search the one or more client locality tables for a new signature of a new data unit,

send the new signature to a deduplication server and add the new signature to one of the one or more client locality tables, in response to not finding the new signature in the one or more client locality tables, and

inhibit sending of the new signature to the deduplication server, in response to finding the new signature in the one or more client locality tables.

21. A system comprising:

a storage device storing user data comprising a plurality of data units; and

a data deduplication client coupled to access the storage device, wherein the data deduplication client is configured to;

search one or more client locality tables for a new signature of a first data unit of the plurality of data units;

send the new signature to a deduplication server and add the new signature to one of the one or more client locality tables, in response to not finding the new signature in the one or more client locality tables; and

inhibit sending of the new signature to the deduplication server, in response to finding the new signature in the one or more client locality tables.