DATA MODIFICATION IN A DISPERSED STORAGE NETWORK

• US 20140351624A1
• Filed: 08/06/2014
• Published: 11/27/2014
• Est. Priority Date: 06/22/2010
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Resch, Jason K.
• Granted Patent: US 10,095,578 B2
• Time in Patent Office: Days
• US Class Current: 714/6.2
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; 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], H04L67/1097
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/141 for bus or memory accesses
• CPC Class Codes: G06F 11/167 Error detection by comparing the memory output
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: H04L 2209/043 of tables, e.g. lookup, substitution or mapping
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/80 Wireless
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/12 Applying verification of the received information cryptographic mechanisms or cryptographic arrangements for data integrity or data verification H04L9/32
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• 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 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC
• CPC Class Codes: H04L 9/3247 : involving digital signatures
• 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
• CPC Class Codes: H04L 9/3271 : using challenge-response
• CPC Class Codes: H04W 12/041 : Key generation or derivation
• CPC Class Codes: H04W 12/0431 : Key distribution or pre-distribution; Key agreement
• CPC Class Codes: H04W 12/10 : Integrity
• CPC Class Codes: H04W 12/35 : Protecting application or service provisioning, e.g. securing SIM application provisioning

Abstract

A method for modifying data stored in a dispersed storage network (DSN). In various embodiments, a data object is received for storage in DSN memory. A dispersed storage processing unit determines a number of data segments for the data object and divides the data object into a plurality of data blocks. The data blocks are allocated to the data segments in a column-row orientation (for example, columns may be populated with successive data blocks of the data object). The data segments are encoded to produce a plurality of sets of encoded data slices. Additional data received for the data object is divided into additional data blocks that are allocated to data segments to create one or more new columns, which are encoded to produce a plurality of encoded data slice addendums. The encoded data slice addendums are then appended to existing encoded data slices corresponding to the data object.

Claims

1. A method comprises:

receiving a data object for storage in dispersed storage network (DSN) memory, the data object including a plurality of successive data bytes;

determining a plurality of data segments for the data object;

allocating the data bytes of the data object to the plurality of data segments such that successive bytes of a data segment include successive kth data bytes of the data object; and

dispersed storage error encoding the plurality of data segments to produce a set of encoded data slices for each data segment, wherein a decode threshold number k of encoded data slices of a set of encoded data slices is required to recover a corresponding data segment of the data object, and wherein an individual encoded data slice of a set of encoded data slices yields substantially no information regarding the corresponding data segment.

2. The method of claim 1, wherein the encoded data slices are arranged in rows, the number of rows of a set of encoded data slices corresponding to the decode threshold number k of encoded data slices.

3. The method of claim 1 further comprises:

for each data segment of the plurality of data segments, generating n-k parity slices in accordance with an error coding dispersal storage function, wherein n corresponds to a number of pillars in a DSN.

4. The method of claim 1, wherein dispersed storage error encoding includes multiplying each data segment by an encoding matrix.

5. The method of claim 4, wherein the encoding matrix includes a unity matrix.

6. The method of claim 1 further comprises:

sending the set of encoded data slices for each data segment to the DSN memory for storage therein.

7. A method for execution by a dispersed storage (DS) processing unit, the method comprises:

receiving a data object for storage in dispersed storage network (DSN) memory;

determining a number of data segments for the data object;

dividing the data object into a plurality of data blocks;

allocating the plurality of data blocks to the data segments in a column-row orientation;

encoding the data segments to produce a plurality of sets of encoded data slices;

receiving additional data of the data object;

dividing the additional data into additional data blocks;

allocating the additional data blocks to the data segments to create a new column for the data segments; and

encoding the new column of the data segments to produce a plurality of encoded data slice addendums.

8. The method of claim 7, wherein allocating the plurality of data blocks to the data segments in a column-row orientation and allocating the additional data blocks to the data segments includes allocating a successive number k of unallocated data blocks of the data object in each column.

9. The method of claim 8, wherein the number k corresponds to a decode threshold number of encoded data slices of a set of encoded data slices required to recover a corresponding data segment of the data object.

10. The method of claim 7 further comprises:

for each data segment of the number of data segments, generating n-k parity slices in accordance with an error coding dispersal storage function, wherein n corresponds to a number of pillars in a DSN.

11. The method of claim 7 wherein the additional data of the data object is appended to the end of the data object, the method further comprises:

sending the plurality of sets of encoded data slices to the DSN memory for storage therein; and

sending the plurality of encoded data slice addendums to the DSN memory for storage therein in association with the plurality of sets of encoded data slices.

12. The method of claim 11 further comprises:

storing the plurality of sets of encoded data slices in the DSN memory; and

storing the plurality of encoded data slice addendums in the DSN memory, wherein the plurality of encoded data slice addendums is appended to the end of the plurality of sets of encoded data slices.

13. The method of claim 7 wherein the additional data of the data object is disposed between the beginning and the end of the data object, the method further comprises:

generating a segment reconstruction pointer that represents a location of the new column in relation to other columns of the data segments prior to encoding of the new column.

14. The method of claim 13 further comprises:

sending the plurality of sets of encoded data slices to the DSN memory for storage therein; and

sending the plurality of encoded data slice addendums to the DSN memory for storage therein in association with the plurality of sets of encoded data slices.

15. The method of claim 14 further comprises:

storing the plurality of sets of encoded data slices in the DSN memory; and

storing the plurality of encoded data slice addendums in the DSN memory, wherein the plurality of encoded data slice addendums is appended to the end of the plurality of sets of encoded data slices.

16. The method of claim 7 wherein dispersed storage error encoding includes multiplying each data segment by an encoding matrix.

17. A dispersed storage (DS) processing unit comprises:

at least one interface;

a memory; and

a processing module coupled to the at least one interface and the memory, the processing module configured to;

receive, via the at least one interface, a data object for storage in dispersed storage network (DSN) memory;

determine a number of data segments for the data object;

divide the data object into a plurality of data blocks;

allocate the plurality of data blocks to the data segments in a column-row orientation;

encode the data segments to produce a plurality of sets of encoded data slices;

receive, via the interface, additional data of the data object;

divide the additional data into additional data blocks;

allocate the additional data blocks to the segments to create a new column for the data segments; and

encode the new column of the data segments to produce a plurality of encoded data slice addendums.

18. The DS processing unit of claim 17, wherein data segments include a successive number k of data blocks of the data object in each column.

19. The DS processing unit of claim 18, wherein the number k corresponds to a decode threshold number of encoded data slices of a set of encoded data slices required to recover a corresponding data segment of the data object.

20. The DS processing unit of claim 17, the processing module further configured to:

send, via the at least one interface, the plurality of sets of encoded data slices to the DSN memory for storage therein; and

send, via the at least one interface, the plurality of encoded data slice addendums to the DSN memory for storage therein in association with the plurality of sets of encoded data slices.