Distributed client side deduplication index cache
Systems and methods for deduplicating data are provided. An index used in deduplicating data is distributed to clients. The clients can use the distributed index to provide hints as to whether the data is deduplicated at the server. The server may be associated with a main index used to confirm whether the data is deduplicated based on the hints.
1. A method for deduplicating data, the method comprising:
determining whether one or more chunks are represented in a local index of a client, wherein the local index is a distributed portion of a fast index maintained by a server, wherein the local index associates partial identifiers with version numbers;
determining partial identifier for each of the one or more chunks, wherein the local index allows a version number to be determined from the partial identifier;
uploading a hint for each of the one or more chunks that is represented in the local index to a server that maintains a fast index and a main index, wherein the hint includes the version number from the local index and wherein the server determines whether the one or more chunks associated with each of the hints are already stored by the server based on the version number, wherein the version number is unique for each of the one or more chunks represented in the local index and allows the server to determine whether the one or more chunks associated with the hints are stored by the server from the main index without accessing the fast index for the one or more chunks associated with the hints; and
updating the local index for each of the one or more chunks that is not a duplicate of a chunk already stored at the server.
2. The method of claim 1 , further comprising dividing a file into the one or more chunks.
3. The method of claim 1 , wherein determining whether the one or more chunks are represented in a local index of a client includes hashing each of the one or more chunks to generate the identifier, wherein the identifier includes a hash or a partial hash.
4. The method of claim 3 , further comprising accessing the local index based on the hashes the partial hashes.
5. The method of claim 4 , further comprising returning at least the version number of the chunks that are represented in the local index.
6. The method of claim 5 , wherein the hint for each chunk represented in the local index includes the chunk and a version number of a chunk that may be a duplicate of the chunk.
7. The method of claim 1 , further comprising receiving version numbers for each of the one or more chunks that is unique and not previously stored by the server and updating the local index with the version numbers.
8. The method of claim 1 , wherein the local index comprises a portion of the fast index maintained at the server.
9. The method of claim 1 , further comprising storing the local index in a fast memory.
10. A method for deduplicating data using a distributed index, the method comprising:
receiving hints that are associated with a-specific chunks identified by a client at a server, each of the hints including a version number;
receiving identifiers for chunks that are not associated with the hints;
checking a fast index maintained by the server for the chunks identified by the client that are not associated with the hints to identify version numbers of the chunks, wherein the fast index associates partial identifiers to version numbers such that the fast index is checked for the chunks based on the partial identifiers of the chunks that are not associated with the hints;
checking a main index based on the version number identified from the fast index and received from the client to confirm deduplication of the chunks that are not associated with the hints, wherein the chunks that are not associated with the hints are uploaded when not present in the fast index or not present in the main index; and
confirming deduplication for the specific chunk using the main index without accessing the fast index for the chunks associated with the hints using the version numbers received from the client for the specific chunks.
11. The method of claim 10 , further comprising receiving the chunks to be added to the server and assigning a version number to all of the chunks that are not confirmed as deduplicated in the main index.
12. The method of claim 11 , further comprising adding all of the chunks that are not confirmed as deduplicated to the main index and to the fast index.
13. The method of claim 12 , further comprising assigning a version number to each of the chunks that are not confirmed as deduplicated and entering the version number and hash into the main index and entering a partial hash and the version number into the fast index.
14. The method of claim 11 , further comprising providing the version numbers of all of the chunks that are not confirmed to a client that submitted the chunks, wherein the client maintains a local index that includes a portion of the fast index.
15. The method of claim 14 , further comprising seeding the local index of the client.
16. The method of claim 11 , wherein chunks not found in the main index are new chunks that are added to storage, wherein chunks that are represented in the main index are deduplicated and are not added to the storage.
17. The method of claim 10 , further comprising, when multiple matches are present in the fast index, determining a correct match from the main index based on a whole hash and/or the version number.
18. The method of claim 10 , further comprising distributing the fast index to a plurality of clients including the client.
19. The method of claim 18 , wherein the plurality of clients are each associated with a local index and wherein the hints provided from one client are determined from the local indexes of more than one of the plurality of clients.
20. The method of claim 10 , further comprising generating a hash for each of the chunks by the server or by the client.