Conditional writes at distributed storage services

Patent metadata

Field	Value
Publication number	US-9569459-B1
Application number	US-201414230378-A
Country	US
Kind code	B1
Filing date	Mar 31, 2014
Priority date	Mar 31, 2014
Publication date	Feb 14, 2017
Grant date	Feb 14, 2017

Abstract

A node of a distributed storage service receives a read request from a client, directed to a particular physical page storing at least a portion of a file store object. The node transmits, to the client, a particular operation sequence number (OSN), obtained from a replicated state machine, indicative of an order in which the read request was processed at the node relative to other requests directed to the file store object. The node receives a write request from the client directed to the page. The write request includes the particular OSN. The node determines whether the page has been modified after the particular OSN was obtained. If the page has not been modified since the OSN was obtained, a modification indicated in the write request is performed; otherwise, the write request is rejected.

First claim

What is claimed is:

1. A system, comprising:
one or more computing devices configured to:
determine, at a client of a storage subsystem of a distributed multi-tenant storage service, that a particular file store operation is to be implemented at least in part as a read-modify-write sequence directed to a particular physical page of a file store object, wherein the storage subsystem is configured to use a replicated state machine to coordinate changes to the file store object;
receive, at a selected node of the storage subsystem, a read request directed to the particular physical page by the client, wherein the selected node is selected by the storage service based at least in part on the particular physical page;
obtain, at the selected node, a read logical timestamp from the replicated state machine, wherein the read logical timestamp is indicative of an order in which the read request was processed at the selected node relative to other service requests directed to the file store object;
transmit, by the selected node to the client, the read logical timestamp;
receive, at the selected node, a write request directed to the particular physical page, wherein the write request indicates (a) a modification to be applied to the particular physical page and (b) the read logical timestamp of the read request;
determine, by the selected node, using the replicated state machine and the read logical timestamp indicated in the write request, whether the particular physical page has been modified since the read logical timestamp was obtained by the selected node from the replicated state machine; and
in response to a determination that the particular physical page has not been modified since the read logical timestamp was obtained, apply the modification to the particular physical page.

2. The system as recited in claim 1 , wherein the one or more computing devices are further configured to:
in response to a determination that the particular physical page has been modified since the read logical timestamp was obtained, reject the write request.

3. The system as recited in claim 1 , wherein the storage service exposes an industry-standard file system interface to customers, wherein the storage service includes an access subsystem and a metadata subsystem, and wherein the client of the storage subsystem comprises one of (a) a node of the access subsystem, or (b) a node of the metadata subsystem.

4. The system as recited in claim 1 , wherein the particular physical page stores a portion of a particular replica of a plurality of replicas corresponding to a logical file store object, wherein the selected node of the storage subsystem is responsible for serializing updates to the plurality of replicas.

5. The system as recited in claim 1 , wherein the one or more computing devices are further configured to:
maintain, at the selected node, a circular buffer comprising a plurality of log entries, wherein a particular log entry of the plurality of log entries indicates (a) an identifier of a physical page of the file store object at which a modification was applied and (b) a logical timestamp associated with the modification; and
examine contents of the buffer to determine whether the particular physical page has been modified since the read logical timestamp was obtained.

6. A method, comprising:
performing, by one or more computing devices comprising one or more respective hardware processors:
receiving, at a selected node of a storage subsystem of a distributed storage service, a read request of a read-modify-write sequence directed to a particular physical page of a storage object by a client of the storage subsystem, wherein the selected node is selected by the storage service based at least in part on the particular physical page;
transmitting, by the selected node to the client, a read logical timestamp indicative of an order in which the read request was processed at the selected node relative to other service requests directed to the file store object, wherein the read logical timestamp is obtained from a replicated state machine; and
applying, by the selected node, a modification indicated in a write request of the read-modify-write sequence in response to determining that the particular physical page has not been modified since the read logical timestamp was obtained, wherein the write request indicates the read logical timestamp of the read request.

7. The method as recited in claim 6 , further comprising performing, by the one or more computing devices:
determining, by the selected node in response to a different write request of a different read-modify-write sequence, that a different physical page has been modified since a corresponding read logical timestamp was obtained for the different physical page and transmitted to the client; and
rejecting, by the selected node, the different write request.

8. The method as recited in claim 6 , wherein the distributed storage service exposes an industry-standard file system interface to customers, wherein the distributed storage service includes an access subsystem and a metadata subsystem, and wherein the client of the storage subsystem comprises one of (a) a node of the access subsystem, or (b) a node of the metadata subsystem.

9. The method as recited in claim 6 , wherein the particular physical page stores a portion of a particular replica of a plurality of replicas corresponding to a logical file store object, wherein the selected node of the storage subsystem is responsible for coordinating updates to the plurality of replicas.

10. The method as recited in claim 9 , wherein the selected node of the storage subsystem is responsible for coordinating updates to the plurality of replicas using a consensus-based protocol and the replicated state machine.

11. The method as recited in claim 6 , wherein the file store object is a metadata structure comprising configuration information associated with one or more file store data objects.

12. The method as recited in claim 6 , wherein the file store object is a data file.

13. The method as recited in claim 6 , further comprising performing, by the one or more computing devices:
maintaining, at the selected node, a buffer comprising a plurality of log entries, wherein a particular log entry of the plurality of log entries indicates (a) an identifier of a physical page of the file store object at which a modification was applied and (b) a logical timestamp associated with the modification, wherein said determining that the particular physical page has not been modified since the read logical timestamp was obtained comprises examining contents of the buffer; and
storing, in the buffer, subsequent to said determining that the particular physical page has not been modified since the read logical timestamp was obtained, an entry including an identifier of the particular physical page and a logical timestamp associated with said applying the modification indicated in the write request.

14. The method as recited in claim 13 , further comprising performing, by the one or more computing devices:
determining, at the selected node in response to a different write request from the client, wherein the different write request is submitted as part of a different read-modify-write sequence for which a different read logical timestamp was provided to the client, an earliest logical timestamp indicated in the buffer;
comparing, at the selected node, the earliest logical timestamp with the different read logical timestamp; and
rejecting the different write request in response to a determination that the different read logical timestamp is lower than the e

Assignees

• Amazon Tech Inc

Inventors

• Strauss Jacob A
• Vincent Pradeep
• Frasca Michael Robert
• Frigo Matteo
• Oikarinen Matti Juhani

Classifications

• G06F17/30194 Primary

  Physics · mapped topic

• G06F16/184 Primary

  implemented as replicated file system · CPC title

• G06F16/182 Primary

  Distributed file systems · CPC title