SYSTEM AND METHOD FOR CREATING DEDUPLICATED COPIES OF DATA STORING NON-LOSSY ENCODINGS OF DATA DIRECTLY IN A CONTENT ADDRESSABLE STORE

• US 20120124013A1
• Filed: 11/16/2010
• Published: 05/17/2012
• Est. Priority Date: 11/16/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Actifio, Inc. (Alphabet Inc.)
• Inventors: PROVENZANO, Christopher A.
• Granted Patent: US 8,299,944 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• 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

Abstract

Systems and methods are disclosed for storing deduplicated images in which a portion of the image is stored in encoded form directly in a hash table, the method comprising: organizing unique content of each data object as a plurality of content segments and storing the content segments in a data store; receiving content to be included in the deduplicated image of the data object; determining if the received content may be encoded using a predefined non-lossy encoding technique and in which the encoded value would fit within the field for containing a hash signature; if so, placing the encoding in the field and marking the hash structure to indicate that the field contains encoded content; otherwise, generating a hash signature for the received content and placing the hash signature in the field and placing the received content in a corresponding content segment if it is unique.

Claims

1. A method of storing deduplicated images in which a portion of the image is stored in encoded form directly in a hash table, the method comprising:

organizing unique content of each data object as a plurality of content segments and storing the content segments in a data store;

for each data object, creating an organized arrangement of hash structures, wherein each structure, for a subset of the hash structures, includes a field to contain a hash signature for a corresponding content segment and is associated with a reference to the corresponding content segment, wherein the logical organization of the arrangement represents the logical organization of the content segments as they are represented within the data object;

receiving content to be included in the deduplicated image of the data object;

determining if the received content may be encoded using a predefined non-lossy encoding technique and in which the encoded value would fit within the field for containing a hash signature;

if so, placing the encoding in the field and marking the hash structure to indicate that the field contains encoded content for the deduplicated image;

if not, generating a hash signature for the received content and placing the hash signature in the field and placing the received content in a corresponding content segment in said data store if it is unique.

2. The method of claim 1, wherein said non-lossy encoding is a run-length encoding.

3. The method of claim 1, wherein hash signatures for each data object are created using the SHA-1 cryptographic hash function.

4. The method of claim 1, further comprising subsequently reconstituting the content from the encoded content.