Handling data slice revisions in a dispersed storage network

• US 10,394,468 B2
• Filed: 02/23/2017
• Issued: 08/27/2019
• Est. Priority Date: 02/23/2017
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Motwani, Manish, Viraraghavan, Praveen, Volvovski, Ilya
• Primary Examiner(s): Gebril, Mohamed M
• Application Number:
  US15/440,454
• Publication Number:
  US 20180239546A1
• Time in Patent Office: 915 Days
• Field of Search: 711165
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• 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]

Abstract

A method for execution by a storage unit of a dispersed storage network (DSN) includes receiving a data slice for storage. A first bin that includes the data slice is generated and stored in a first location of a memory device of the storage unit, and a bin pointer that includes a reference to the first location is generated. A revision of the data slice is later received, and a second bin that includes the revised data slice is generated and stored in a second location of the memory device. A modified bin pointer is generated by editing the bin pointer to include a reference to the second location. A back pointer that references the first location is generated in response to commencing writing of the revised data slice. The back pointer is deleted in response to determining that the revised data slice has reached a finalized write stage.

Claims

1. A method for execution by a storage unit of a dispersed storage network (DSN) that includes a processor, the method comprises:

receiving, via a network, a data slice for storage;

writing the data slice by generating a first bin that includes the data slice and storing the first bin in a first location of a memory device of the storage unit;

generating an original bin pointer associated with the data slice that includes a reference to the first location;

receiving, via the network, a revision of the data slice;

writing the revision of the data slice by generating a second bin that includes the revision of the data slice and storing the second bin in a second location of the memory device, wherein the second bin is a revised version of the first bin;

generating a modified bin pointer by editing the original bin pointer to include a reference to the second location;

generating a back pointer associated with the revision of the data slice that references the first location in response to commencing writing of the revision of the data slice; and

deleting the back pointer in response to determining that the revision of the data slice has reached a finalized write stage;

wherein the original bin pointer is stored in a random access memory (RAM) of the storage unit, and wherein the back pointer is generated by retrieving the original bin pointer from RAM; and

wherein the back pointer is generated in conjunction with generating the modified bin pointer, wherein the modified bin pointer includes the back pointer, and wherein the back pointer is deleted from the modified bin pointer in response to determining that the revision of the data slice has reached the finalized write stage.

2. The method of claim 1, further comprising:

storing the first bin in the first location of the memory device based on an original append point;

generating an updated append point in response to storing the first bin;

determining a current append point in response to receiving the revision of the data slice; and

storing the second bin in the second location of the memory device based on the current append point.

3. The method of claim 2, wherein generating the updated append point is based on the original append point and a length of the first bin.

4. The method of claim 1, further comprising:

determining a set of outdated bins at a time after the finalized write stage of the revision of the data slice, wherein the set of outdated bins includes the first bin; and

deleting the set of outdated bins.

5. The method of claim 4, wherein the first bin is included in the set of outdated bins based on the deletion of the back pointer that references the first location.

6. The method of claim 1, wherein creating the back pointer includes writing the back pointer to the second bin, and wherein the back pointer is deleted from the second bin in response to determining that the revision of the data slice has reached the finalized write stage.

7. The method of claim 1, further comprising:

receiving a request for the data slice from a requesting entity via the network;

retrieving the data slice from the memory device based on the original bin pointer; and

transmitting the data slice to the requesting entity;

wherein the revision of the data slice is generated by the requesting entity based on making revisions to the data slice received from the storage unit.

8. The method of claim 1, wherein a plurality of bin pointers correspond to a plurality of data slices stored in the memory device, wherein the plurality of bin pointers are stored in a random access memory (RAM) of the storage unit, wherein each of the plurality of bin pointers includes a back pointer field, wherein generating the modified bin pointer includes assigning the reference to the first location to the back pointer field, and wherein deleting the back pointer from the modified bin pointer includes assigning a null value to the back pointer field.

9. The method of claim 8, wherein generating the original bin pointer includes assigning the back pointer field of the original bin pointer to the null value in response to determining that the data slice is not a revision.

10. The method of claim 9, further comprising:

updating an outdated bin list to include the reference to the first bin in response to determining that the revision of the data slice has reached the finalized write stage by retrieving the reference to the first bin from the back pointer field of the modified bin pointer prior to assigning the null value to the back pointer field, and

deleting a plurality of bins indicated in the outdated bin list in response to determining a cleanup requirement.

11. The method of claim 1, wherein a length of the first bin is based on a size of the data slice, wherein a length of the second bin is based on a size of the revision of the data slice, and wherein a difference in length between the first bin and the second bin is based on a change of size between the data slice and the revision of the data slice.

12. The method of claim 1, wherein the original bin pointer includes offset information that corresponds to a length of the first bin, and wherein generating the modified bin pointer includes updating the offset information to correspond to a length of the second bin.

13. The method of claim 1, wherein writing the revision of the data slice is commenced at a first time, wherein the finalized write stage of the revision of the data slice is reached at a second time, and wherein a time period between the first time and the second time corresponds to a write-commit stage of the revision of the data slice.

14. The method of claim 1, further comprising:

generating a second modified bin pointer by deleting the reference to the second location and including the reference to the first location by utilizing the back pointer in response to determining that the writing the revision of the data slice failed.

15. The method of claim 1, wherein the data slice is mapped to the original bin pointer based on an identifier of the data slice.

16. A processing system of a storage unit of a dispersed storage network (DSN) comprises:

at least one processor;

a memory that stores operational instructions, that when executed by the at least one processor cause the processing system to;

receive, via a network, a data slice for storage;

write the data slice by generating a first bin that includes the data slice and storing the first bin in a first location of a memory device of the storage unit;

generate an original bin pointer associated with the data slice that includes a reference to the first location;

receive, via the network, a revision of the data slice;

write the revision of the data slice by generating a second bin that includes the revision of the data slice and storing the second bin in a second location of the memory device, wherein the second bin is a revised version of the first bin;

generate a modified bin pointer by editing the original bin pointer to include a reference to the second location;

generate a back pointer associated with the revision of the data slice that references the first location in response to commencing writing of the revision of the data slice; and

delete the back pointer in response to determining that the revision of the data slice has reached a finalized write stage;

wherein the original bin pointer is stored in a random access memory (RAM) of the storage unit, and wherein the back pointer is generated by retrieving the original bin pointer from RAM; and

wherein the back pointer is generated in conjunction with generating the modified bin pointer, wherein the modified bin pointer includes the back pointer, and wherein the back pointer is deleted from the modified bin pointer in response to determining that the revision of the data slice has reached the finalized write stage.

17. The processing system of claim 16, wherein the operational instructions, when executed by the at least one processor, further cause the processing system to:

store the first bin in the first location of the memory device based on an original append point;

generate an updated append point in response to storing the first bin;

determine a current append point in response to receiving the revision of the data slice; and

store the second bin in the second location of the memory device based on the current append point.

18. A non-transitory computer readable storage medium comprises:

at least one memory section that stores operational instructions that, when executed by a processing system of a dispersed storage network (DSN) that includes a processor and a memory, causes the processing system to;

receive, via a network, a data slice for storage;

write the data slice by generating a first bin that includes the data slice and storing the first bin in a first location of a memory device;

generate an original bin pointer associated with the data slice that includes a reference to the first location;

receive, via the network, a revision of the data slice;

write the revision of the data slice by generating a second bin that includes the revision of the data slice and storing the second bin in a second location of the memory device, wherein the second bin is a revised version of the first bin;

generate a modified bin pointer by editing the original bin pointer to include a reference to the second location;

generate a back pointer associated with the revision of the data slice that references the first location in response to commencing writing of the revision of the data slice; and

delete the back pointer in response to determining that the revision of the data slice has reached a finalized write stage;

wherein the original bin pointer is stored in a random access memory (RAM), and wherein the back pointer is generated by retrieving the original bin pointer from RAM; and

wherein the back pointer is generated in conjunction with generating the modified bin pointer, wherein the modified bin pointer includes the back pointer, and wherein the back pointer is deleted from the modified bin pointer in response to determining that the revision of the data slice has reached the finalized write stage.