Updating data stored in a dispersed storage network

• US 8,782,492 B2
• Filed: 08/17/2012
• Issued: 07/15/2014
• Est. Priority Date: 10/04/2011
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Resch, Jason K., Leggette, Wesley
• Primary Examiner(s): TRIMMINGS, JOHN P
• Application Number:
  US13/588,350
• Publication Number:
  US 20130086447A1
• Time in Patent Office: 697 Days
• Field of Search: 714/6.2, 714/764, 711/114
• US Class Current: 714/764
• CPC Class Codes: G06F 11/00 Error detection; Error correction; Monitoring error detection, correction or monitoring in information storage based on relative movement between record carrier and transducer G11B20/18; monitoring, i.e. supervising the progress of recording or reproducing G11B27/36; in static stores G11C29/00
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 15/17331 Distributed shared memory [DSM], e.g. remote direct memory access [RDMA]
• CPC Class Codes: G06F 21/33 using certificates
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• 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 2209/04 Masking or blinding
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0863 involving passwords or one-time passwords network architectures or network communication protocols for using one-time keys in a packet data network H04L63/067
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3263 involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823

Abstract

A method begins by a dispersed storage (DS) processing module receiving a modified data object, wherein the modified data object is a modified version of a data object and the data object is divided into a plurality of data segments and stored in the DSN. The method continues with the DS processing module mapping portions of the modified data object to the plurality of data segments that includes creating a middle data segment of a second plurality of data segments based on a corresponding middle data segment of the plurality of data segments when a portion of the portions corresponds to middle data of the modified data object. The method continues with the DS processing module encoding the middle data segment using a dispersed storage error coding function to produce an encoded data segment and overwriting the corresponding middle data segment with the encoded data segment in the DSN.

Claims

1. A method comprises:

receiving a modified data object for storage in a dispersed storage network (DSN), wherein the modified data object is a modified version of a data object and wherein the data object is divided into a plurality of data segments that is encoded using a dispersed storage error coding function and stored in the DSN;

mapping portions of the modified data object to the plurality of data segments that includes;

when a portion of the portions of the modified data object maps to a data segment of the plurality of data segments, adding the data segment to a second plurality of data segments for the modified data object;

when another portion of the portions of the modified data object does not map to one of the plurality of data segments, determining whether the another portion corresponds to beginning data, middle data, or ending data of the modified data object; and

when the another portion corresponds to the middle data of the modified data object, creating a middle data segment of the second plurality of data segments based on a corresponding middle data segment of the plurality of data segments;

encoding the middle data segment of the second plurality of data segments using the dispersed storage error coding function to produce an encoded data segment; and

overwriting the corresponding middle data segment with the encoded data segment in the DSN.

2. The method of claim 1 further comprises:

partitioning the modified data object into the portions based on known size of data segments of the plurality of data segments of the data object.

3. The method of claim 1, wherein the mapping comprises:

comparing a deterministic function value of one of the portions of the modified data object with a deterministic function value of a corresponding data segment of the plurality of data segments;

when the deterministic function value of the one of the portions substantially matches the deterministic function value of the corresponding data segment, indicating that the one of the portions maps to the corresponding data segment; and

when the deterministic function value of the one of the portions does not substantially match the deterministic function value of the corresponding data segment, indicating that the one of the portions does not map to the corresponding data segment.

4. The method of claim 3 further comprises:

accessing a segment allocation table to obtain the deterministic function value of the corresponding data segment.

5. The method of claim 1 further comprises:

updating a segment allocation table of the data object with the second plurality of data segments.

6. The method of claim 1 further comprises:

when the another portion corresponds to the beginning data of the modified data object, creating at least one new beginning data segment for the second plurality of data segments.

7. The method of claim 1 further comprises:

when the another portion corresponds to the ending data of the modified data object, creating at least one new ending data segment for the second plurality of data segments.

8. The method of claim 1 further comprises:

creating the second plurality of data segments to have a same number of data segments as the plurality of data segments when the modified data object includes modification to the middle data.

9. The method of claim 1 further comprises:

the encoding the middle data segment including;

dividing the middle data segment into a matrix of data blocks;

creating an encoded data block matrix based on the matrix of data blocks and an

encoding matrix of the dispersed storage error coding function; and

creating a set of encoded data slices from the encoded data block matrix;

the overwriting the corresponding middle data segment with the encoded data segment including;

identifying an encoded data slices of the set of encoded data slices that is different than a corresponding encoded data slice of a second set of encoded data slices of the corresponding middle data segment; and

overwriting, in a dispersed storage unit of the DSN, the corresponding encoded data slice with the encoded data slice.

10. A dispersed storage (DS) module comprises:

a first module, when operable within a computing device, causes the computing device to;

receive a modified data object for storage in a dispersed storage network (DSN), wherein the modified data object is a modified version of a data object and wherein the data object is divided into a plurality of data segments that is encoded using a dispersed storage error coding function and stored in the DSN;

a second module, when operable within the computing device, causes the computing device to map portions of the modified data object to the plurality of data segments that includes;

when a portion of the portions of the modified data object maps to a data segment of the plurality of data segments, add the data segment to a second plurality of data segments for the modified data object;

when another portion of the portions of the modified data object does not map to one of the plurality of data segments, determine whether the another portion corresponds to beginning data, middle data, or ending data of the modified data object; and

when the another portion corresponds to the middle data of the modified data object, create a middle data segment of the second plurality of data segments based on a corresponding middle data segment of the plurality of data segments;

a third module, when operable within the computing device, causes the computing device to;

encode the middle data segment of the second plurality of data segments using the dispersed storage error coding function to produce an encoded data segment; and

a fourth module, when operable within the computing device, causes the computing device to;

overwrite the corresponding middle data segment with the encoded data segment in the DSN.

11. The DS module of claim 10, wherein the second module further functions to:

partition the modified data object into the portions based on known size of data segments of the plurality of data segments of the data object.

12. The DS module of claim 10, wherein the second module functions to map by:

comparing a deterministic function value of one of the portions of the modified data object with a deterministic function value of a corresponding data segment of the plurality of data segments;

when the deterministic function value of the one of the portions substantially matches the deterministic function value of the corresponding data segment, indicating that the one of the portions maps to the corresponding data segment; and

when the deterministic function value of the one of the portions does not substantially match the deterministic function value of the corresponding data segment, indicating that the one of the portions does not map to the corresponding data segment.

13. The DS module of claim 12, wherein the second module further functions to:

access a segment allocation table to obtain the deterministic function value of the corresponding data segment.

14. The DS module of claim 12, wherein the second module further functions to:

update a segment allocation table of the data object with the second plurality of data segments.

15. The DS module of claim 12, wherein the second module further functions to:

when the another portion corresponds to the beginning data of the modified data object, create at least one new beginning data segment for the second plurality of data segments.

16. The DS module of claim 12, wherein the second module further functions to:

when the another portion corresponds to the ending data of the modified data object, create at least one new ending data segment for the second plurality of data segments.

17. The DS module of claim 12, wherein the second module further functions to:

create the second plurality of data segments to have a same number of data segments as the plurality of data segments when the modified data object includes modification to the middle data.

18. The DS module of claim 12 further comprises:

the third module functions to encode the middle data segment by;

dividing the middle data segment into a matrix of data blocks;

creating an encoded data block matrix based on the matrix of data blocks and an encoding matrix of the dispersed storage error coding function; and

creating a set of encoded data slices from the encoded data block matrix;

the fourth module functions to the overwrite the corresponding middle data segment with the encoded data segment by;

identifying an encoded data slice of the set of encoded data slices that is different than a corresponding encoded data slice of a second set of encoded data slices of the corresponding middle data segment; and

overwriting, in a dispersed storage unit of the DSN, the corresponding encoded data slice with the encoded data slice.