Distributed and Deduplicating Data Storage System and Methods of Use

Abstract

Systems and methods for distributed and deduplicating a data store are provided herein. An exemplary method for distributed and deduplicating stored data, may include receiving an input data stream, segmenting the input data stream into chunks, creating a signature for each of the chunks, distributing each chunk to one of a plurality of containers, each container having a container identifier, and creating an index that includes a mapping of a chunk signature and a container identifier.

What is claimed is: 
     
         1 . A method, comprising:
 generating an input signature for at least a portion of an input data stream from a client, the input signature including a representation of data included in the input data stream;   comparing the input signature to stored signatures of data included in a deduplicated backup data store;   selecting a stored signature based upon the step of comparing the input signature to the stored signatures of data included in a deduplicated backup data store;   comparing data associated with the selected stored signature to the at least a portion of the input data stream to determine unique data included in the at least a portion of the input data stream; and   distributing the unique data to the deduplicated backup data store.   
     
     
         2 . The method according to  claim 1 , wherein generating an input signature comprises applying a facial recognition algorithm to the at least a portion of an input data stream. 
     
     
         3 . The method according to  claim 1 , wherein comparing data associated with the selected stored signature to the at least a portion of the input data stream comprises:
 performing an exact comparison between data of the selected stored signature to data of the at least a portion of the input data stream;   ignoring data of the at least a portion of the input data stream that is an exact match to data of the selected stored signature; and   storing in the deduplicated backup data store, data of the at least a portion of the input data stream that is not an exact match to data of the selected stored signature.   
     
     
         4 . A method comprising:
 receiving an input data stream;   segmenting the input data stream into chunks;   creating a signature for each of the chunks;   distributing each chunk to one of a plurality of containers, each container comprising a container identifier; and   creating a locality index that includes a mapping of a chunk signature and a container identifier, wherein the chunk signatures and container identifiers for each of the chunks are related to one another because they were created from the input stream.   
     
     
         5 . The method according to  claim 4 , further comprising creating a container index that includes an offset and a length for each chunk included in a container. 
     
     
         6 . The method according to  claim 4 , wherein the signatures of the chunks each comprise a cryptographic hash value. 
     
     
         7 . The method according to  claim 5 , further comprising:
 receiving a request for a file associate with one of the chunks;   pre-fetching remaining ones of the chunks or associated files; and   providing the requested file to the client.   
     
     
         8 . The method according to  claim 7 , further comprising providing one or more of the remaining ones of the chunks or associated files from the pre-fetch when requested by the client. 
     
     
         9 . A system, comprising:
 a processor;   logic encoded in one or more tangible media for execution by the processor and when executed operable to perform operations comprising:
 generating an input signature for at least a portion of an input data stream from a client, the input signature including a representation of data included in the input data stream; 
 comparing the input signature to stored signatures of data included in a deduplicated backup data store; 
 selecting a stored signature based upon the step of comparing the input signature to the stored signatures of data included in a deduplicated backup data store; 
 comparing data associated with the selected stored signature to the at least a portion of the input data stream to determine unique data included in the at least a portion of the input data stream; and 
 distributing the unique data to the deduplicated backup data store. 
   
     
     
         10 . The system according to  claim 9 , wherein the deduplicated backup data store resides within a cloud. 
     
     
         11 . The system according to  claim 9 , wherein generating an input signature includes the processor further executing the logic to perform operations of applying a facial recognition algorithm to the at least a portion of an input data stream. 
     
     
         12 . The system according to  claim 9 , wherein comparing data of the selected stored signature to the at least a portion of the input data stream comprises includes the processor further executing the logic to perform operations of:
 performing an exact comparison between data of the selected stored signature to data of the at least a portion of the input data stream;   ignoring data of the at least a portion of the input data stream that does not exactly match data of the selected stored signature; and   storing in the deduplicated backup data store, data of the at least a portion of the input data stream that does not exactly match data of the selected stored signature.   
     
     
         13 . The system according to  claim 9 , wherein the processor further executes the logic to perform operations of:
 receiving the input data stream;   segmenting the input data stream into chunks;   creating an extent from sequential chunks; and   hashing each chunk to create a signature, each signature comprising a hash value for data included in the chunk.   
     
     
         14 . The system according to  claim 13 , wherein the processor further executes the logic to perform operations of:
 distributing unique chunks to the backup data store in proximity to one another; and   creating an index that includes a location of each of the unique distributed chunks.   
     
     
         15 . The system according to  claim 14 , wherein the processor further executes the logic to perform operations of:
 creating a distributed hash table link for the unique distributed chunks; and   combining distributed hash table links into a localized distributed hash table.   
     
     
         16 . The system according to  claim 9 , wherein the processor further executes the logic to perform operations of selecting a stored signature based upon information indicative of an object to which the input data stream belongs. 
     
     
         17 . A method, comprising:
 receiving an input data stream;   separating the input data stream into chunks;   performing one or more of an exact and an approximate matching of the chunks of the input data stream to chunks stored in a deduplicated backup data store to determine unique chunks;   determining one or more locations in the deduplicated backup data store for the unique chunks;   updating an index to include the unique chunks with their locations; and   distributing the unique chunks to the deduplicated backup data store according to the index.   
     
     
         18 . A method, comprising:
 receiving a first input data stream at a first point in time, the first point in time being associated with a first file modification operation for a first set of files occurring on a client;   segmenting the first input data stream into chunks;   creating a signature for each of the chunks;   distributing each chunk to one of a first plurality of containers, each container comprising a container identifier, the first plurality of containers being proximate to one another on a backup data store;   creating a locality index that includes a mapping of a chunk signature and a container identifier, wherein the chunk signatures and container identifiers for each of the chunks are related to one another because they were created from the first input data stream;   receiving a second input data stream at a second point in time, the second point in time being associated with a second file modification operation for a second set of files occurring on a client;   segmenting the second input data stream into chunks;   creating a signature for each of the chunks;   distributing each chunk to one of a second plurality of containers, each container comprising a container identifier, the second plurality of containers being proximate to one another on a backup data store; and   creating a locality index that includes a mapping of a chunk signature and a container identifier, wherein the chunk signatures and container identifiers for each of the chunks are related to one another because they were created from the second input data stream.