Read descriptors at heterogeneous storage systems

• US 10,303,795 B2
• Filed: 09/10/2014
• Issued: 05/28/2019
• Est. Priority Date: 09/10/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Vermeulen, Allan Henry, Muniswamy-Reddy, Kiran-Kumar, Cole, Timothy Daniel, Rath, Timothy Andrew
• Primary Examiner(s): Pyo, Monica M
• Application Number:
  US14/482,668
• Publication Number:
  US 20160070771A1
• Time in Patent Office: 1,721 Days
• Field of Search: 707609, 707615, 707619, 707634, 707639, 707704, 707812, 707822
• CPC Class Codes: G06F 11/1425 by reconfiguration of node membership
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 11/202 where processing functionality is redundant redundant communication control functionality G06F11/2005, redundant storage control functionality G06F11/2089
• CPC Class Codes: G06F 11/3006 where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems multiprogramming arrangements G06F9/46; allocation of resources G06F9/50
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 2201/83 the solution involving signatures
• 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

In response to a read request directed to a first data store of a storage group, a state transition indicator is identified, corresponding to a modification that has been applied at the data store before a response to the read is prepared. A read descriptor that includes the state transition indicator and read repeatability verification metadata is prepared. The metadata can be used to check whether the read request is a repeatable read. The read descriptor is transmitted to a client-side component of the storage group.

Claims

1. A system, comprising:

one or more computing devices configured to;

receive a first read request directed to a first data store of a plurality of data stores of a heterogeneous storage group, wherein the first read request comprises a first filtering criterion to be used to identify a first result set;

determine an indicator of a particular state transition, wherein the particular state transition comprises one or more modifications applied to the first data store prior to an identification of the first result set;

identify the first result set using the first filtering criterion;

generate a read descriptor comprising (a) the indicator of the particular state transition and (b) read repeatability verification metadata (RRVM) usable to determine whether the first read request represents a repeatable read that when resubmitted would return a result set consistent with the first result set;

transmit the first result set and a representation of the read descriptor to a client-side component of the heterogeneous storage group; and

determine, based at least in part on an analysis of the read descriptor, that a write request directed to a particular data store of the heterogeneous storage group subsequent to the first read request meets an acceptance criterion.

2. The system as recited in claim 1, wherein the RRVM comprises a representation of the first filtering criterion.

3. The system as recited in claim 1, wherein the RRVM comprises a representation of an expression to be evaluated to determine whether a repetition of the first read request would result in a different result set than the first result set.

4. The system as recited in claim 1, wherein the RRVM is based at least in part on an address of a data object included in the first result set.

5. The system as recited in claim 1, wherein the representation of the read descriptor comprises an obfuscated version of the read descriptor.

6. A method, comprising:

performing, by one or more computing devices;

receiving a first read request directed to a first data store;

determining an indicator of a particular state transition, wherein the particular state transition comprises one or more modifications applied to the first data store prior to an identification of a first result set of the first read request;

generating a read descriptor comprising (a) the indicator of the particular state transition and (b) read repeatability verification metadata (RRVM) usable to determine whether the first read request represents a repeatable read that when resubmitted would return a result set consistent with the first result set; and

transmitting, in response to the first read request, at least a representation of the read descriptor and the first result set to a particular destination.

7. The method as recited in claim 6, wherein the RRVM comprises a representation of a selection criterion indicated in the read request.

8. The method as recited in claim 6, wherein the RRVM comprises a representation of a function to be invoked to determine whether a repetition of the first read request would result in a different result set than the first result set.

9. The method as recited in claim 6, wherein the RRVM is based at least in part on an address of a data object included in the first result set.

10. The method as recited in claim 6, wherein the RRVM comprises an output of a selected hash function applied to the address of a data object included in the first result set.

11. The method as recited in claim 6, wherein the indication of the particular state transition comprises a logical timestamp.

12. The method as recited in claim 6, wherein the read descriptor comprises an indication of a last-modification-time of a data object of the first result set.

13. The method as recited in claim 6, wherein the read descriptor comprises an indication of a last-modification-time of a table of the first data store, wherein the table comprises one of more data objects of the first result set.

14. The method as recited in claim 6, wherein the representation of the read descriptor comprises an obfuscated version of the read descriptor.

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

determining a number of padding bytes to be incorporated in the representation of the read descriptor, wherein said determining comprises using a random number computation; and

incorporating the number of padding bytes within the representation of the read descriptor prior to said transmitting the representation.

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

determine, in response to a read request directed at a first data store of a storage group, an indicator of a particular state transition corresponding to a modification that has been applied at the first data store prior to a generation of a first result set of the read request;

generate a read descriptor comprising (a) an indication of the particular state transition and (b) read repeatability verification metadata (RRVM) usable to determine whether the first read request represents a repeatable read that when resubmitted would return a result set consistent with the first result set; and

initiate a transmission of the read descriptor and the first result set to a client-side component of the storage group.

17. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the RRVM comprises a representation of a selection criterion indicated in the read request.

18. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the RRVM comprises a representation of a function to be invoked to determine whether a repetition of the read request would result in a different result set than the first result set.

19. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the RRVM is based at least in part on an address of a data object included in the first result set.

20. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the indication of the particular state transition comprises a logical timestamp.