Conditional writes at distributed storage services

• US 9,569,459 B1
• Filed: 03/31/2014
• Issued: 02/14/2017
• Est. Priority Date: 03/31/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Frasca, Michael Robert, Strauss, Jacob A., Vincent, Pradeep, Frigo, Matteo, Oikarinen, Matti Juhani
• Primary Examiner(s): Robinson, Greta
• Application Number:
  US14/230,378
• Time in Patent Office: 1,051 Days
• Field of Search: 707/609, 707/615, 707/619, 707/634, 707/639, 707/704, 707/812, 707/822, 707/610, 707/638, 707/703, 711/111, 711/154, 711/155, 711/162, 711/163
• US Class Current: 1/1
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/184 implemented as replicated file system

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.

Claims

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 earliest logical timestamp.

15. The method as recited in claim 14, further comprising performing, by the one or more computing devices:

determining a metric of rejections resulting at least in part from comparisons of read logical timestamps with earliest logical timestamps of the buffer; and

changing a size of the buffer based at least in part on the metric.

16. The method as recited in claim 6, wherein the particular physical page belongs to a particular extent, further comprising:

storing, at the selected node, a buffer indicative of write logical timestamps at one of (a) a physical-page-level granularity or (b) an extent-level granularity; and

examining contents of the buffer to determine that the particular physical page has not been modified since the read logical timestamp was obtained.

17. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors:

receive, at a selected node of a storage subsystem of a distributed storage service, a read request of a read-modify-write sequence from a client, directed to a particular physical page storing at least a portion of a file store object, wherein the selected node is selected by the storage service based at least in part on the particular physical page;

transmit, by the selected node to the client, a first operation sequence number (OSN) indicative of an order in which the read request was processed at the selected node relative to one or more other requests directed to the file store object, wherein the first OSN is received from a replicated state machine associated with the file store object;

receive, at the selected node, a write request from the client directed to the particular physical page, wherein the write request includes the first OSN of the read request;

apply, by the selected node, a modification indicated in the write request in response to determining that the particular physical page has not been modified since the first OSN was obtained.

18. The non-transitory computer-accessible storage medium as recited in claim 17, 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 comprises one of (a) a node of the access subsystem, or (b) a node of the metadata subsystem.

19. The non-transitory computer-accessible storage medium as recited in claim 17, 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.

20. The non-transitory computer-accessible storage medium as recited in claim 19, 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.

21. The non-transitory computer-accessible storage medium as recited in claim 17, wherein the instructions, when executed on the one or more processors:

maintain, 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 first OSN was obtained comprises examining contents of the buffer.