Data deduping in content centric networking manifests

• US 10,067,948 B2
• Filed: 03/18/2016
• Issued: 09/04/2018
• Est. Priority Date: 03/18/2016
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Solis, Ignacio
• Primary Examiner(s): DANG, THANH HA T
• Application Number:
  US15/074,870
• Publication Number:
  US 20170270134A1
• Time in Patent Office: 900 Days
• Field of Search: 707692
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

A storage system facilitates deduping repeating data segments when generating a Manifest hierarchy for a file. During operation, the system can select a partitioning function that identifies a pattern that is expected to occur a predetermined number of times within the file. The system can process a plurality of segments of the file, using the partitioning function, to identify a set of chunk boundaries. The system generates a chunk for each file portion between two consecutive chunk boundaries, and generates a Manifest that includes a Content Object Hash (COH) value for each partitioned chunk. The system can store the Manifest and the unique partitioned chunks in a storage repository, such that two partitioned chunks with a common COH value are stored once in the storage repository.

Claims

1. A computer-implemented method, comprising:

selecting, by a computer system, a partitioning function that identifies a pattern that is expected to occur a predetermined number of times within a data block, wherein the data block corresponds to a file in a filesystem;

processing a plurality of segments of the data block, using the partitioning function, to identify a set of chunk boundaries, wherein the partitioning function takes as input a segment s_i consisting of m consecutive bytes, wherein segment s_istarts at the i^th byte of the data block;

generating a chunk for each portion of the data block between two consecutive chunk boundaries;

generating one or more Manifests, wherein each Manifest includes a Content Object Hash (COH) value for each partitioned chunk;

storing, by the computer system, each Manifest and the corresponding partitioned chunk in a storage repository, wherein two partitioned chunks with a common COH value are stored once in the storage repository; and

determining that the file in the filesystem has been modified, and in response, the computer-implemented method further comprising;

determining a portion of the file that has been modified;

determining a nameless Content Object affected by the modification to the file based on the COH value;

generating one or more new nameless Content Objects that include the modification to the file and are to replace the affected Content Object;

storing the one or more nameless Content Objects in the storage repository; and

updating, in one or more Manifests of a Manifest hierarchy, COH values corresponding to the modified portion of the file to replace the affected Content Object with the new nameless Content Objects, at the modified portion of the file, to achieve data deduping across multiple files.

2. The computer-implemented method of claim 1, wherein identifying the chunk boundaries involves:

processing a respective segment s_i to obtain an n-bit identifier which has an expected repetition period in the data block approximately equal to a target chunk size; and

determining whether the n-bit pattern matches a predetermined boundary indicator.

3. The computer-implemented method of claim 2, wherein processing the segment s_i involves applying a mask M to segment s_i to mask all but the n least significant bits of segment s_i.

4. The computer-implemented method of claim 2, wherein processing the segment s_i involves computing a hash value h(s_i), and obtaining the last n bits of the computed hash value.

5. The computer-implemented method of claim 1, wherein storing a respective chunk in the storage repository involves:

upon determining that the respective chunk is smaller than or equal to a predetermined size;

generating a nameless Content Object that includes the respective chunk; and

storing the nameless Content Object in the data repository, if the nameless Content Object does not exist in the data repository.

6. The computer-implemented method of claim 1, wherein storing a respective chunk in the storage repository involves:

upon determining that the respective chunk is larger than a predetermined size;

selecting a second partitioning function that identifies a second pattern that is expected to occur a second predetermined number of times within the chunk;

using the second partitioning function to partition the chunk into a collection of sub-chunks;

generating a second Manifest that includes a Content Object Hash (COH) value for each partitioned sub-chunk; and

storing the second Manifest and the unique sub-chunks that do not exist in the storage repository.

7. The computer-implemented of claim 1, wherein the Manifest hierarchy includes a root Manifest;

and

wherein the computer-implemented method comprises repeating the step of updating the COH values corresponding to the modified portion of the file in the one or more Manifests until the root Manifest is updated.

8. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:

selecting a partitioning function that identifies a pattern that is expected to occur a predetermined number of times within a data block, wherein the data block corresponds to a file in a filesystem;

processing a plurality of segments of the data block, using the partitioning function, to identify a set of chunk boundaries, wherein the partitioning function takes as input a segment s_i consisting of m consecutive bytes, wherein segment s_i starts at the i^th byte of the data block;

generating a chunk for each portion of the data block between two consecutive chunk boundaries;

generating one or more Manifests, wherein each Manifest includes a Content Object Hash (COH) value for each partitioned chunk;

storing each Manifest and the corresponding partitioned chunk in a storage repository, wherein two partitioned chunks with a common COH value are stored once in the storage repository; and

determining that the file in the filesystem has been modified, and in response, the method further comprising;

determining a portion of the file that has been modified;

determining a nameless Content Object affected by the modification to the file based on the COH value;

generating one or more new nameless Content Objects that include the modification to the file and are to replace the affected Content Object;

storing the one or more nameless Content Objects in the storage repository; and

updating, in one or more Manifests of a Manifest hierarchy, COH values corresponding to the modified portion of the file to replace the affected Content Object with the new nameless Content Objects, at the modified portion of the file, to achieve data deduping across multiple files.

9. The non-transitory computer-readable storage medium of claim 8, wherein identifying the chunk boundaries involves:

processing a respective segment s_i to obtain an n-bit identifier which has an expected repetition period in the data block approximately equal to a target chunk size; and

determining whether the n-bit pattern matches a predetermined boundary indicator.

10. The non-transitory computer-readable storage medium of claim 9, wherein processing the segment s_i involves applying a mask M to segment s_i to mask all but the n least significant bits of segment s_i.

11. The non-transitory computer-readable storage medium of claim 9, wherein processing the segment s_i involves computing a hash value h(s_i) and obtaining the last n bits of the computed hash value.

12. The non-transitory computer-readable storage medium of claim 8, wherein storing a respective chunk in the storage repository involves:

upon determining that the respective chunk is smaller than or equal to a predetermined size;

generating a nameless Content Object that includes the respective chunk; and

storing the nameless Content Object in the data repository, if the nameless Content Object does not exist in the data repository.

13. The non-transitory computer-readable storage medium of claim 8, wherein storing a respective chunk in the storage repository involves:

upon determining that the respective chunk is larger than a predetermined size;

selecting a second partitioning function that identifies a second pattern that is expected to occur a second predetermined number of times within the chunk;

using the second partitioning function to partition the chunk into a collection of sub-chunks;

generating a second Manifest that includes a Content Object Hash (COH) value for each partitioned sub-chunk; and

storing the second Manifest and the unique sub-chunks that do not exist in the storage repository.

14. The non-transitory computer-readable storage medium of claim 8, wherein the Manifest hierarchy includes a root Manifest;

and

wherein the method comprises repeating the step of updating the COH values corresponding to the modified portion of the file in the one or more Manifests until the root Manifest is updated.

15. A computer system, comprising:

a processor;

a memory storing instructions that when executed by the processor cause the computer system to;

select a partitioning function that identifies a pattern that is expected to occur a predetermined number of times within a data block, wherein the data block corresponds to a file in a filesystem;

process a plurality of segments of the data block, using the partitioning function, to identify a set of chunk boundaries, wherein the partitioning function takes as input a segment s_i consisting of m consecutive bytes, wherein segment s_i starts at the i^th byte of the data block;

generate a chunk for each portion of the data block between two consecutive chunk boundaries;

generate one or more Manifests, wherein each Manifest includes a Content Object Hash (COH) value for each partitioned chunk;

store each Manifest and the corresponding partitioned chunk in a storage repository, wherein two partitioned chunks with a common COH value are stored once in the storage repository; and

determining that the file in the filesystem has been modified, and in response, the instructions further cause the computer system to;

determine a portion of the file that has been modified;

determine a nameless Content Object affected by the modification to the file based on the COH value;

generate one or more new nameless Content Objects that include the modification to the file and are to replace the affected Content Object;

store the one or more nameless Content Objects in the storage repository; and

update, in one or more Manifests of a Manifest hierarchy, COH values corresponding to the modified portion of the file to replace the affected Content Object with the new nameless Content Objects, at the modified portion of the file, to achieve data deduping across multiple files.

16. The computer system of claim 15, wherein identifying the chunk boundaries involves:

processing a respective segment s_i to obtain an n-bit identifier which has an expected repetition period in the data block approximately equal to a target chunk size; and

determining whether the n-bit pattern matches a predetermined boundary indicator.

17. The computer system of claim 16, wherein processing the segment s_i involves applying a mask M to segment s_i to mask all but the n least significant bits of segment s_i.

18. The computer system of claim 16, wherein processing the segment s_i involves computing a hash value h(s_i) and obtaining the last n bits of the computed hash value.

19. The computer system of claim 15, wherein storing a respective chunk in the storage repository involves:

upon determining that the respective chunk is smaller than or equal to a predetermined size;

generating a nameless Content Object that includes the respective chunk; and

storing the nameless Content Object in the data repository, if the nameless Content Object does not exist in the data repository.

20. The computer system of claim 15, wherein storing a respective chunk in the storage repository involves:

upon determining that the respective chunk is larger than a predetermined size;

selecting a second partitioning function that identifies a second pattern that is expected to occur a second predetermined number of times within the chunk;

using the second partitioning function to partition the chunk into a collection of sub-chunks;

generating a second Manifest that includes a Content Object Hash (COH) value for each partitioned sub-chunk; and

storing the second Manifest and the unique sub-chunks that do not exist in the storage repository.