Consistent reads in a distributed transaction protocol

Patent metadata

Field	Value
Publication number	US-11226764-B2
Application number	US-202016744448-A
Country	US
Kind code	B2
Filing date	Jan 16, 2020
Priority date	Jan 16, 2020
Publication date	Jan 18, 2022
Grant date	Jan 18, 2022

Abstract

Methods and systems for consistent reads in a distributed transaction protocol are disclosed. A method includes: receiving, by a computing device, a request to write a revision of a data object in a dispersed storage network (DSN); sending, by the computing device, a proposal with the revision of the data object to a plurality of storage units; receiving, by the computing device, a response to the proposal from each of the plurality of storage units, the response including a proposed minimum timestamp corresponding to the data object; determining, by the computing device, a minimum timestamp for the data object based on the proposed minimum timestamps received from the plurality of storage units; and determining, by the computing device, a version of the data object written in the DSN based on the minimum timestamp.

First claim

What is claimed is:

1. A method comprising:
receiving, by a dispersed storage (DS) processing unit in a dispersed storage network, a request to write a revision of a data object in the dispersed storage network, wherein the data object is stored as slices at a plurality of DS storage units in the dispersed storage network and the revision of the data object is a newer version of the data object;
sending, by the DS processing unit, a proposal with the revision of the data object to the plurality of DS storage units;
receiving, by the DS processing unit, a response to the proposal from each of the plurality of DS storage units, the response including a proposed minimum timestamp corresponding to the data object;
determining, by the DS processing unit, a minimum timestamp for the data object based on the proposed minimum timestamps received from the plurality of DS storage units;
determining, by the DS processing unit, a version of the data object written in the dispersed storage network based on the minimum timestamp; and
completing the write of the revision of the data object in the dispersed storage network based on the determined version.

2. The method according to claim 1 , further comprising determining, by the DS processing unit, a current timestamp of the DS processing unit, and
wherein the proposal includes the current timestamp of the DS processing unit.

3. The method according to claim 2 , wherein the response to the proposal received from each of the plurality of DS storage units further comprises a current timestamp of the DS storage unit.

4. The method according to claim 3 , further comprising the DS processing unit using a Paxos protocol to determine the minimum timestamp based on the responses to the proposal received from the DS storage units.

5. The method according to claim 1 , wherein the determining the version of the data object written in the dispersed storage network comprises determining a WINNING-SUCCESSOR using a Paxos protocol based on the responses to the proposal received from the DS storage units.

6. The method according to claim 5 , wherein the completing the write of the revision of the data object is performed based on the WINNING-SUCCESSOR.

7. The method according to claim 1 , wherein:
the DS processing unit comprises a relative system clock, a logical counter, and a relative hybrid logical clock;
the relative hybrid logical clock is a hybrid logical clock that provides ordering of events based on the relative system clock and the logical counter;
the DS processing unit determines a current timestamp for the write request using the relative hybrid logical clock; and
the DS processing using sends the current timestamp with the proposal.

8. A computer program product comprising:
one or more computer readable storage media, and program instructions collectively stored on the one or more computer readable storage media, the program instructions comprising:
program instructions to receive, by the DS processing unit in a dispersed storage network, a read request for a data object, wherein the data object is stored as slices at a plurality of DS storage units in the dispersed storage network, the read request includes a request timestamp, and the request is received from a client computer system;
program instructions to determine, by the DS processing unit, a current timestamp;
program instructions to retrieve, by the DS processing unit, data from storage corresponding to the data object at the request timestamp;
program instructions to update, by the DS processing unit, a read timestamp cache based on the current timestamp;
program instructions to provide, by the DS processing unit, the retrieved data to a dispersed storage (DS) processing unit; and
program instructions to generate, by the DS processing unit, a response to the read request and return the response to the client computer system.

9. The computer program product according to claim 8 , wherein the updating the read timestamp cache comprises setting a value at an index corresponding to the data object to a maximum of a value presently stored at the index and the current timestamp.

10. The computer program product according to claim 8 , further comprising program instructions to determine a difference between the request timestamp and the read timestamp.

11. The computer program product according to claim 10 , further comprising program instructions to, in response to the difference between the request timestamp and the read timestamp exceeding a predetermined maximum acceptable skew, reject the read request.

12. The computer program product according to claim 8 , wherein request timestamp is a hybrid logical clock timestamp.

13. The computer program product according to claim 8 , wherein:
the DS processing unit comprises a relative system clock, a logical counter, and a relative hybrid logical clock;
the relative hybrid logical clock is a hybrid logical clock that provides ordering of events based on the relative system clock and the logical counter; and
the DS processing unit determines the current timestamp using the relative hybrid logical clock.

14. A system comprising:
a hardware processor, a computer readable memory, and one or more computer readable storage media associated with a computing device, wherein the computing device is a dispersed storage (DS) processing unit;
program instructions to receive, by the DS processing unit in a dispersed storage network, a request to write a revision of a data object in the dispersed storage network, wherein the data object is stored as slices at a plurality of DS storage units in the dispersed storage network and the revision of the data object is a newer version of the data object;
program instructions to send, by the DS processing unit, a proposal with the revision of the data object to the plurality of DS storage units;
program instructions to receive, by the DS processing unit, a response to the proposal from each of the plurality of DS storage units, the response including a proposed minimum timestamp corresponding to the data object;
program instructions to determine, by the DS processing unit, a minimum timestamp for the data object based on the proposed minimum timestamps received from the plurality of DS storage units;
program instructions to determine, by the DS processing unit, a version of the data object written in the dispersed storage network based on the minimum timestamp; and
program instructions to completing a write of the revision of the data object in the dispersed storage network based on the determined version,
wherein the program instructions are collectively stored on the one or more computer readable storage media for execution by the hardware processor via the computer readable memory.

15. The system according to claim 14 , further comprising program instructions to determine a current timestamp of the DS processing unit,
wherein the proposal includes the current timestamp of the DS processing unit.

16. The system according to claim 15 , wherein the response to the proposal received from each of the plurality of DS storage units further comprises a current timestamp of the DS storage unit.

17. The system according to claim 16 , further comprising program instructions to use a Paxos protocol to determine the minimum timestamp based on the responses to the proposal received from the DS storage units.

18. The system according to claim 14 , wherein the determining the version of the data object written in the dispersed storage network comprises determining a WINNIN

Assignees

• IBM

Inventors

• Dhuse Gregory R
• Khadiwala Ravi
• Li Mingyu

Classifications

• G06F3/0659

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title

• G06F3/0667

  at data level, e.g. file, record or object virtualisation · CPC title

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F3/067 Primary

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• H04L67/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 title