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 in a distributed system, the method comprising:
distributing a portion of a fast index from a server to a client that stores the portion of the fast index as a local index, wherein the fast index at the server and the local index at the client associate partial identifiers of chunks with version numbers of the chunks and wherein the portion of the fast index distributed to the client remains at the server, wherein the partial identifiers include a portion of full identifiers of the chunks;
receiving hints that are associated with chunks identified by a client, each of the hints including a version number, wherein the chunks are each associated with a full identifier and wherein each of the chunks is identified when a portion of the full identifier matches one of the partial identifiers in the local index; and
confirming whether the chunks identified by the client are deduplicated or should be added to data of the distributed system using the main index, wherein chunks that are confirmed in the main index using the version number are duplicates and chunks that are not confirmed in the main index are added to the data of the distributed system.
2. The method of claim 1 , further comprising confirming deduplication for the chunks using only the main index for the chunks associated with the hints using the version numbers received from the client for the chunks to access the main index.
3. The method of claim 1 , wherein each hint corresponds to a portion of a corresponding full identifier.
4. The method of claim 1 , further comprising updating the local index for each of the one or more chunks that is not confirmed, using the main index, as a duplicate of a chunk already stored at the server.
5. The method of claim 1 , further comprising confirming that the chunks are deduplicated when found in both the fast index at the server and the main index.
6. The method of claim 1 , wherein the portion of the fast index at the client and the fast index at the server associate partial hashes of the chunks with their corresponding version numbers, wherein the main index associated full hashes of the chunks with their corresponding version numbers, wherein each version number is unique.
7. The method of claim 1 , wherein the main index further associates the chunks with metadata including location metadata.
8. The method of claim 1 , further comprising updating the portion of the local index distributed to the client.
9. The method of claim 1 , further comprising accessing only the main index to confirm that a chunk is deduplicated when only a single match is found in the fast index.
10. The method of claim 1 , further comprising:
receiving identifiers for chunks that are not associated with the hints, wherein the chunks that are not associated with the hits include chunks whose partial identifiers are missing from the local index;
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; and
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.
11. The method of claim 1 , wherein the chunks not present in the main index are added to the storage.
12. The method of claim 1 , further comprising, when multiple matches are present in the portion of the fast index, determining a correct match from the main index based on a whole hash and/or the version numbers.
13. The method of claim 1 , further wherein the client used a plurality of local portions of the fast index distributed to multiple clients to generate the hints.
14. A non-transitory computer readable medium comprising computer executable instructions for execution by a processor for implementing a method for deduplicating data in a distributed system, the method comprising:
distributing a portion of a fast index from a server to a client that stores the portion of the fast index as a local index, wherein the fast index at the server and the local index at the client associate partial identifiers of chunks with version numbers of the chunks and wherein the portion of the fast index distributed to the client remains at the server, wherein the partial identifiers include a portion of full identifiers of the chunks;
receiving hints that are associated with chunks identified by a client, each of the hints including a version number, wherein the chunks are each associated with a full identifier and wherein each of the chunks is identified when a portion of the full identifier matches one of the partial identifiers in the local index; and
confirming whether the chunks identified by the client are deduplicated or should be added to data of the distributed system using the main index, wherein chunks that are confirmed in the main index using the version number are duplicates and chunks that are not confirmed in the main index are added to the data of the distributed system.
15. The non-transitory computer readable medium of claim 14 , the method the method further comprising confirming deduplication for the chunks using only the main index for the chunks associated with the hints using the version numbers received from the client for the chunks to access the main index.
16. The non-transitory computer readable medium of claim 14 , wherein each hint corresponds to a portion of a corresponding full identifier.
17. The non-transitory computer readable medium of claim 14 , the method further comprising at least one of:
adding the chunks to the storage when the chunks are not present in the main index;
when multiple matches are present in the portion of the fast index, determining a correct match from the main index based on a whole hash and/or the version numbers;
wherein the client used a plurality of local portions of the fast index distributed to multiple clients to generate the hints; or
updating the portion of the local index for each of the one or more chunks that is not a duplicate of a chunk already stored at the server.
18. The non-transitory computer readable medium of claim 14 , the method further comprising confirming that the chunks are deduplicated when found in both the fast index at the server and the main index or only accessing only the main index to confirm that a chunk is deduplicated when only a single match is found in the fast index.
19. The non-transitory computer readable medium of claim 14 , wherein the portion of the fast index at the client and the fast index at the server associate partial hashes of the chunks with their corresponding version numbers, wherein the main index associated full hashes of the chunks with their corresponding version numbers, wherein each version number is unique, wherein the main index further associates the chunks with metadata including location metadata, the method further comprising updating the portion of the local index distributed to the client.
20. The non-transitory computer readable medium of claim 14 , the method further comprising:
receiving identifiers for chunks that are not associated with the hints, wherein the chunks that are not associated with the hits include chunks whose partial identifiers are missing from the local index;
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; and
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.