IP Library Granted Patent US 9,547,548
Granted Patent B2
US 9,547,548 · App. 15/012,555 · Granted Jan 17, 2017

Detecting storage errors in a dispersed storage network

Inventors: Asimuddin Kazi (Naperville, IL); Jason K. Resch (Chicago, IL)
Assignee: International Business Machines Corporation
G06F11/10G06F3/065G06F3/067G06F3/0619G06F11/08G06F11/1068G06F11/1076G06F11/1092H03M13/05H03M13/611G06F11/008G06F2211/109
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 9,547,548
App. No.
15/012,555
Granted
Jan 17, 2017
Kind
B2
Abstract

A method includes dividing a data object into data partitions. The method further includes, for each data partition: dividing the data partition into data segments; dispersed storage error encoding the data segments to produce sets of encoded data slices; storing the sets of encoded data slices in a first set of storage units; and generating a segment allocation table regarding storage information of the sets of encoded data slices. The method further includes generating a directory of segment allocation tables. The method further includes receiving an access request regarding at least a portion of the data object. The method further includes accessing the directory to identify one or more segment allocation tables containing storage information for the at least a portion of the data object. The method further includes accessing encoded data slices of the at least the portion of the data object based on the storage information.

Claims (102)

1. A method for execution by one or more computing devices, the method comprises:

dividing a data object into a plurality of data partitions;

for each data partition of the plurality of data partitions:

dividing the data partition into a plurality of data segments;

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

storing the plurality of sets of encoded data slices in a first set of storage units of a distributed storage network (DSN);

generating a segment allocation table regarding storage information of the plurality of sets of encoded data slices;

generating a directory of a plurality of segment allocation tables from the segment allocation tables for each of the data partitions;

receiving an access request regarding at least a portion of the data object;

accessing the directory to identify one or more segment allocation tables of the plurality of segment allocation tables containing storage information for the at least a portion of the data object; and

accessing encoded data slices of the at least the portion of the data object based on the storage information of the identified segment allocation tables.

2. The method of claim 1 , wherein the directory comprises:

a plurality of entries regarding the plurality of segment allocation tables, wherein an entry of the plurality of entries includes a data portion identifier field and a vault source name field, wherein the data portion identifier stores an identifier of one of the plurality of data partitions and the vault source name field stores a vault source name that is used to generate a DSN storage address for the corresponding segment allocation table.

3. The method of claim 1 , wherein the segment allocation table comprises:

a start segment value source name field that stores a source name corresponds to a first set of encoded data slices of the plurality of sets of encoded data slices;

a segment size field stores a size value for the data segments, for the set of encoded data slices, or for an encoded data slice of the set of encoded data slices; and

a total length field stores a value corresponding to the number of data segments in the plurality of data segments, to the data size for the plurality of data segments, a number of sets of encoded data slices in the plurality of sets of encoded data slices, or a data size of the plurality of sets of encoded data slices.

4. The method of claim 1 further comprises:

dividing a first data partition of the plurality of data partitions into a first plurality of data segments;

dispersed storage error encoding, in accordance with first dispersed storage error encoding parameters, the first plurality of data segments to produce a first plurality of sets of encoded data slices;

storing the first plurality of sets of encoded data slices in the first set of storage units;

dividing a second data partition of the plurality of data partitions into a second plurality of data segments;

dispersed storage error encoding, in accordance with second dispersed storage error encoding parameters, the second plurality of data segments to produce a second plurality of sets of encoded data slices; and

storing the second plurality of sets of encoded data slices in a second set of storage units of the DSN.

5. The method of claim 1 further comprises:

dispersed storage error encoding the segment allocation table to produce a set of encoded SAT encoded slices; and

storing the set of encoded SAT encoded slices in storage units of the DSN.

6. The method of claim 1 further comprises:

when the access request is a read request, wherein the accessing encoded data slices of the portion of the data object based on the storage information of the identified segment allocation tables further includes:

identifying DSN addresses for a particular plurality of sets of encoded data slices corresponding to a data portion of the at least the portion of the data object;

retrieving a decode threshold number of encoded data slices for each set of the plurality of sets of encoded data slices; and

recovering the data portion of the at least the portion of the data object from the decode threshold number of encoded data slices for each set of the plurality of sets of encoded data slices.

7. A computing device comprises:

an interface;

memory; and

a processing module operably coupled to the interface and to the memory, wherein the processing module is operable to:

divide a data object into a plurality of data partitions;

for each data partition of the plurality of data partitions:

divide the data partition into a plurality of data segments;

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

output, via the interface, the plurality of sets of encoded data slices to a first set of storage units of a distributed storage network (DSN) for storage therein;

generate a segment allocation table regarding storage information of the plurality of sets of encoded data slices;

generate a directory of a plurality of segment allocation tables from the segment allocation tables for each of the data partitions;

receive an access request regarding at least a portion of the data object;

access the directory to identify one or more segment allocation tables of the plurality of segment allocation tables containing storage information for the at least a portion of the data object; and

access encoded data slices of the at least the portion of the data object based on the storage information of the identified segment allocation tables.

8. The computing device of claim 7 , wherein the directory comprises:

a plurality of entries regarding the plurality of segment allocation tables, wherein an entry of the plurality of entries includes a data portion identifier field and a vault source name field, wherein the data portion identifier stores an identifier of one of the plurality of data partitions and the vault source name field stores a vault source name that is used to generate a DSN storage address for the corresponding segment allocation table.

9. The computing device of claim 7 , wherein the segment allocation table comprises:

a start segment value source name field that stores a source name corresponds to a first set of encoded data slices of the plurality of sets of encoded data slices;

a segment size field stores a size value for the data segments, for the set of encoded data slices, or for an encoded data slice of the set of encoded data slices; and

a total length field stores a value corresponding to the number of data segments in the plurality of data segments, to the data size for the plurality of data segments, a number of sets of encoded data slices in the plurality of sets of encoded data slices, or a data size of the plurality of sets of encoded data slices.

10. The computing device of claim 7 , wherein the processing module is further operable to:

divide a first data partition of the plurality of data partitions into a first plurality of data segments;

dispersed storage error encode, in accordance with first dispersed storage error encoding parameters, the first plurality of data segments to produce a first plurality of sets of encoded data slices;

output, via the interface, the first plurality of sets of encoded data slices to the first set of storage units for storage therein;

divide a second data partition of the plurality of data partitions into a second plurality of data segments;

dispersed storage error encode, in accordance with second dispersed storage error encoding parameters, the second plurality of data segments to produce a second plurality of sets of encoded data slices; and

output, via the interface, the second plurality of sets of encoded data slices to a second set of storage units of the DSN for storage therein.

11. The computing device of claim 7 , wherein the processing module is further operable to:

dispersed storage error encode the segment allocation table to produce a set of encoded SAT encoded slices; and

output, via the interface, the set of encoded SAT encoded slices to storage units of the DSN for storage therein.

12. The computing device of claim 7 , wherein the processing module is further operable to:

when the access request is a read request, wherein the accessing encoded data slices of the portion of the data object based on the storage information of the identified segment allocation tables further includes:

identify DSN addresses for a particular plurality of sets of encoded data slices corresponding to a data portion of the at least the portion of the data object;

retrieve, via the interface, a decode threshold number of encoded data slices for each set of the plurality of sets of encoded data slices; and

recover the data portion of the at least the portion of the data object from the decode threshold number of encoded data slices for each set of the plurality of sets of encoded data slices.

13. A non-transitory storage device comprises:

a first storage section that stores operational instructions that, when executed by a computing device, causes the computing device to:

divide a data object into a plurality of data partitions;

for each data partition of the plurality of data partitions:

divide the data partition into a plurality of data segments;

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

output the plurality of sets of encoded data slices to a first set of storage units of a distributed storage network (DSN) for storage therein;

generate a segment allocation table regarding storage information of the plurality of sets of encoded data slices;

generate a directory of a plurality of segment allocation tables from the segment allocation tables for each of the data partitions;

a second storage section that stores operational instructions that, when executed by the computing device or a second computing device, causes the computing device or the second computing device to:

receive an access request regarding at least a portion of the data object;

access the directory to identify one or more segment allocation tables of the plurality of segment allocation tables containing storage information for the at least a portion of the data object; and

access encoded data slices of the at least the portion of the data object based on the storage information of the identified segment allocation tables.

14. The non-transitory storage device of claim 13 , wherein the directory comprises:

a plurality of entries regarding the plurality of segment allocation tables, wherein an entry of the plurality of entries includes a data portion identifier field and a vault source name field, wherein the data portion identifier stores an identifier of one of the plurality of data partitions and the vault source name field stores a vault source name that is used to generate a DSN storage address for the corresponding segment allocation table.

15. The non-transitory storage device of claim 13 , wherein the segment allocation table comprises:

a start segment value source name field that stores a source name corresponds to a first set of encoded data slices of the plurality of sets of encoded data slices;

a segment size field stores a size value for the data segments, for the set of encoded data slices, or for an encoded data slice of the set of encoded data slices; and

a total length field stores a value corresponding to the number of data segments in the plurality of data segments, to the data size for the plurality of data segments, a number of sets of encoded data slices in the plurality of sets of encoded data slices, or a data size of the plurality of sets of encoded data slices.

16. The non-transitory storage device of claim 13 , wherein the first storage section further stores operational instructions that, when executed by the computing device, causes the computing device to:

divide a first data partition of the plurality of data partitions into a first plurality of data segments;

dispersed storage error encode, in accordance with first dispersed storage error encoding parameters, the first plurality of data segments to produce a first plurality of sets of encoded data slices;

output the first plurality of sets of encoded data slices to the first set of storage units for storage therein;

divide a second data partition of the plurality of data partitions into a second plurality of data segments;

dispersed storage error encode, in accordance with second dispersed storage error encoding parameters, the second plurality of data segments to produce a second plurality of sets of encoded data slices; and

output, via the interface, the second plurality of sets of encoded data slices to a second set of storage units of the DSN for storage therein.

17. The non-transitory storage device of claim 13 further comprises:

a third storage section that stores operational instructions that, when executed by the computing device, causes the computing device to:

dispersed storage error encode the segment allocation table to produce a set of encoded SAT encoded slices; and

output the set of encoded SAT encoded slices to storage units of the DSN for storage therein.

18. The non-transitory storage device of claim 13 , wherein the second storage section further stores operational instructions that, when executed by the computing device or a second computing device, causes the computing device or the second computing device to:

when the access request is a read request, wherein the accessing encoded data slices of the portion of the data object based on the storage information of the identified segment allocation tables further includes:

identify DSN addresses for a particular plurality of sets of encoded data slices corresponding to a data portion of the at least the portion of the data object;

retrieve, a decode threshold number of encoded data slices for each set of the plurality of sets of encoded data slices; and

recover the data portion of the at least the portion of the data object from the decode threshold number of encoded data slices for each set of the plurality of sets of encoded data slices.

Assignments (4)
CORRECTIVE ASSIGNMENT TO CORRECT THE 9992063 AND 10334045 LISTED IN ERROR PREVIOUSLY RECORDED ON REEL 049556 FRAME 0012. ASSIGNOR(S) HEREBY CONFIRMS THE ASSIGNOR HEREBY CONFIRMS THE ASSIGNMENT. Recorded Jan 14, 2020
From: INTERNATIONAL BUSINESS MACHINES CORPORATION
To: PURE STORAGE, INC.
Reel/Frame 052205/0705 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 21, 2019
From: INTERNATIONAL BUSINESS MACHINES CORPORATION
To: PURE STORAGE, INC.
Reel/Frame 049556/0012 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 6, 2016
From: CLEVERSAFE, INC.
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 038629/0015 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Feb 25, 2016
From: KAZI, ASIMUDDIN; RESCH, JASON K.
To: CLEVERSAFE, INC.
Reel/Frame 037832/0198 →
Continuity (3)
Continuation 13890438 · May 9, 2013
Provisional Application 61663796 · Jun 25, 2012
Related Publication 20160147593A1 · May 26, 2016