Pipelined counter signatures

• US 10,013,184 B1
• Filed: 06/30/2016
• Issued: 07/03/2018
• Est. Priority Date: 06/30/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Morkel, John Michael, Cole, Timothy Daniel, de Kadt, Christopher Richard Jacques, Vermeulen, Allan Henry
• Primary Examiner(s): Thai, Tuan
• Application Number:
  US15/199,929
• Time in Patent Office: 733 Days
• Field of Search: 711100, 711154, 711200
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A system may comprise a storage device on which counters are stored. A counter may be associated with an identifier. A computing node of the system may receive a request to modify the counter. In response to the request, a read signature may be stored and may comprise a hash of the identifier and a tolerance of the counter to change. A write signature may be stored in response to the request, and may comprise a hash of the identifier and a magnitude of the requested modification. A conflict may be detected by comparing a sum of the magnitudes of requested changes to the tolerance of the read operation.

Claims

1. A system, comprising:

a storage device configured to store thereon a plurality of counters, wherein a counter of the plurality of counters is associated with an identifier;

a computing node in communication with the storage device in order to maintain the counter, wherein the computing node at least;

in response to a requested modification of the counter, stores, in a first data structure, a first data set representative of reading a value of the counter, the first data set comprising a hash of the identifier and a tolerance value indicative of a permissible magnitude of change to the value of the counter;

in response to the requested modification of the counter, stores, in a second data structure, a second data set representative of writing to the value of the counter, the second data set comprising the hash of the identifier and a magnitude of the requested modification to the value of the counter;

computes a sum of magnitudes of requested modifications associated with the counter, the sum comprising the magnitude of the requested modification to the value of the counter stored in the second data structure;

determines to process the requested modification, the determining based at least in part on comparing the sum to the tolerance value stored in the first data structure; and

stores an updated value for the counter based on the requested modification.

2. The system of claim 1, wherein the computing node at least:

computes the hash using a first hash function when the requested modification is an increment of the counter; and

computes the hash using a second hash function, different from the first hash function, when the requested modification is a decrement of the counter.

3. The system of claim 1, wherein the computing node at least:

determines to disallow processing of a second requested modification of the counter, based at least in part on comparing a second tolerance value associated with the second requested modification to the sum of magnitudes of the requested modifications.

4. The system of claim 1, wherein the computing node at least:

in response to determining that the requested modification is associated with incrementing the counter, computing the sum of magnitudes of the requested modifications by at least identifying magnitudes of increment operations associated with the counter; and

in response to determining that the requested modification is associated with incrementing the counter, computing the sum of magnitudes of the requested modifications by at least identifying magnitudes of increment operations associated with the counter.

5. The system of claim 1, wherein the computing node at least:

stores, in the first data structure, a first plurality of data sets representative of a plurality of readings of the counter, the first plurality of data sets comprising the first data set;

stores, in the second data structure, a second plurality of data sets representative of a plurality of writes to the counter, the second plurality of data sets comprising the second data set; and

computes the sum of magnitudes of the requested modifications by at least locating the second plurality of data sets in the second data structure using the hash of the identifier.

6. A method comprising:

receiving a request to change a counter, the request comprising information indicative of a requested magnitude of change to the counter, the counter associated with an identifier of the counter;

storing a first data comprising a representation of the identifier of the counter and data indicative of a tolerance to change of the counter;

storing a second data comprising the representation of the identifier and the requested magnitude of change to the counter;

computing a sum indicative of a total magnitude of unprocessed requested changes to the counter, the sum comprising the requested magnitude of change to the counter;

determining to change the counter based on the request, by at least comparing the sum to the tolerance to change to the counter; and

processing the request to change the counter by at least storing an updated value for the counter based on the requested magnitude of change to the counter.

7. The method of claim 6, wherein the first data and the second data are stored in a compressed bloom filter.

8. The method of claim 6, wherein the tolerance to change is based at least in part on a difference between a current value of the counter and a minimum value of the counter.

9. The method of claim 6, wherein the tolerance to change is based at least in part on a difference between a current value of the counter and a maximum value of the counter.

10. The method of claim 6, wherein the tolerance to change is based at least in part on a current value of the counter and the requested magnitude of change.

11. The method of claim 6, further comprising:

forming the representation of the identifier using a first hash function when the request to change the counter is associated with incrementing the counter; and

forming the representation of the identifier using a second hash function, different from the first hash function, when the request to change the counter is associated with decrementing the counter.

12. The method of claim 6, wherein the sum is computed based on operations of a same type as the requested change, and operations not of the same type are excluded from the sum.

13. The method of claim 6, further comprising:

determining that the request to change the counter is associated with decrementing the counter; and

computing the sum indicative of a total magnitude of requested changes by at least identifying magnitudes of decrementing operations linked to the counter by an associative data structure and ordered subsequent to the requested change.

14. The method of claim 6, wherein the first data corresponds to a read signature of the request and the second data corresponds to a write signature of the request.

15. A non-transitory computer-readable storage medium having stored thereon executable instructions that, upon execution by a computing device, cause the computing device at least to:

receive a request to change a counter, the request comprising information indicative of a requested magnitude of change to the counter, the counter associated with an identifier of the counter;

store, in response to the request, a first data representative of reading from the counter, the first data comprising a representation of the identifier of the counter and data indicative of a permitted magnitude of change to the counter;

store, in response to the request, a second data comprising the representation of the identifier and the requested magnitude of change to the counter;

compute a sum indicative of a total magnitude of requested changes to the counter, the sum comprising the requested magnitude of change to the counter;

determine to change the counter based on the request, by at least comparing the sum to the permitted magnitude of change to the counter; and

process the requested change to the counter by at least storing an updated value for the counter based on the requested magnitude of change to the counter.

16. The non-transitory computer-readable storage medium of claim 15, wherein the first data is representative of reading the counter in association with the request, and wherein the second data is representative of writing to the counter in association with the request.

17. The non-transitory computer-readable storage medium of claim 15, comprising further instructions that, upon execution by the computing device, cause the computing device to at least:

form the representation using a first hash function when the request to change the counter is associated with incrementing the counter; and

form the representation using a second hash function, different from the first hash function, when the request to change the counter is associated with decrementing the counter.

18. The non-transitory computer-readable storage medium of claim 15, comprising further instructions that, upon execution by the computing device, cause the computing device to at least:

determine that the request to change the counter is associated with incrementing the counter; and

calculate the sum indicative of a total magnitude of unprocessed requested changes based at least in part on magnitudes of incrementing operations linked to the counter by an associative data structure.

19. The non-transitory computer-readable storage medium of claim 15, comprising further instructions that, upon execution by the computing device, cause the computing device to at least:

determine the permitted magnitude of change based at least in part on a difference between a current value of the counter and a minimum value of the counter.

20. The non-transitory computer-readable storage medium of claim 15, comprising further instructions that, upon execution by the computing device, cause the computing device to at least:

determine the permitted magnitude of change based at least in part on a difference between a current value of the counter and a maximum value of the counter.