Identifying modified chunks in a data set for storage

• US 8,452,732 B2
• Filed: 05/17/2012
• Issued: 05/28/2013
• Est. Priority Date: 05/09/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yakushev, Mark L., Smith, Mark A.
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US13/474,624
• Publication Number:
  US 20120290546A1
• Time in Patent Office: 376 Days
• Field of Search: 707/693, 707/697, 707/692, 707/687, 707/698, 707/654, 707/700, 710/62, 710/68, 710/65, 710/74
• US Class Current: 707/654
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• 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/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Provided are a computer program product, system, and method for identifying modified chunks in a data set for storage. Modifications are received to at least one of the chunks in the data set. A determination is made of at least one range of least one of the chunks including data affected by the modifications determination is made as to whether at least one chunk outside of the at least one range has changed. For each determined at least one chunk outside of the at least one range that has changed, a determination is made of at least one new chunk and a new digest of the at least one new chunk and information is added on the at least one new chunk and information to locate the new chunk in the data set.

Claims

1. A method for processing modifications to a data set in storage, comprising:

maintaining information on a data set of variable length chunks, including a digest of each chunk and information to locate the chunk in the data set;

receiving modifications to at least one of the chunks in the data set;

determining at least one range of least one of the chunks including data affected by the modifications, wherein each range identifies one chunk or sequential chunks having data affected by the modifications;

processing the at least one chunk in each range to determine at least one new chunk in each range, and for each determined new chunk, a digest of the new chunk;

determining whether at least one chunk outside of the at least one range has changed;

for each determined at least one chunk outside of the at least one range that has changed, determining at least one new chunk and a new digest of the at least one new chunk; and

adding to the set information the new digest information on the at least one new chunk and information to locate the new chunk in the data set.

2. The method of claim 1, wherein determining whether the at least one chunk outside of the range has changed comprises determining whether the at least one chunk outside of the range starts at a different boundary in the data set.

3. The method of claim 1, wherein each range is identified by an offset in the data set at which the range starts and a length of the range, wherein for each chunk in the data set, there is a digest, chunk size, and an ordering of the chunk in the data set, and wherein determining the chunks within each range comprises:

determining a first chunk in the range including the offset of the range; and

determining a last chunk in the range in the data set including an end of the range determined by the range offset and the length, wherein processing the at least one chunk in the range comprises processing from the first chunk in the range to an end of the last chunk in the range to determine the at least one new chunk in the range.

4. The method of claim 1, wherein each range is identified by an offset in the data set at which the range starts and a length of the range and wherein for each chunk in the data set, there is a digest, chunk size, and an ordering of the chunk in the data set, wherein processing the chunks outside of each range comprises:

for a first chunk following the range, determining whether the chunk is at a same boundary in the data set as before receiving the modifications;

processing the first chunk to determine a new first chunk, including a digest of the new first chunk, in response to determining that the first chunk is not at the same boundary in the data set as before receiving the modifications; and

in response to determining that the first chunk is at the same boundary as before the modification, continuing the processing of any subsequent chunks following the first chunk until a next range or end of data set is reached.

5. The method of claim 4, wherein the operations further comprise:

in response to processing the first chunk to determine the new first chunk, processing any subsequent chunks following the first chunk in the data set until an end of the data set is reached, a beginning of a next range is reached or a subsequent chunk is processed that is at a same boundary in the data set as before receiving the modifications.

6. The method of claim 1, further comprising:

for each determined new chunk, transmitting a message to a server backup manager to determine whether the backup server has a copy of the new chunk;

receiving a response from the server backup manager indicating the determined new chunks which are already maintained at the backup server;

transmitting to the server backup manager each determined new chunk indicated as not already maintained at the backup server; and

transmitting to the server backup manager the digest of each determined new chunk and information to locate the chunk in the data set to include in a copy of the data set information at the server backup manager.

7. The method of claim 1, wherein a number of the determined new chunks for one range has changed from a number of the chunks in the range before the modifications.

8. The method of claim 1, wherein at least one of the determined new chunks for one range are located at different boundaries in the data set than the chunks in the range before the modifications.

9. The method of claim 1, wherein determining the at least one range comprises:

determining any ranges of modifications covering overlapping regions of the data set; and

merging ranges having overlapping regions of the data set into a single range so that the ranges used to determine the chunks to process cover non-overlapping regions of the data set.