Concurrent record updating with mitigation of contention

Abstract

Methods, systems, and computer-readable media for concurrent record updating with mitigation of contention are disclosed. A record containing a numerical value is divided into a plurality of buckets. The buckets contain portions of the numerical value. A selected bucket of the plurality of buckets is randomly determined for a request to update the numerical value. A portion of the numerical value in the selected bucket is updated based at least in part on the request. Access to the selected bucket is granted using optimistic concurrency or pessimistic concurrency.

What is claimed is: 
     
       1. A system, comprising:
 one or more computing devices configured to implement a record updating service, wherein the record updating service is configured to:
 divide a record containing a numerical value into a plurality of buckets, wherein the buckets contain portions of the numerical value whose summation is the numerical value; 
 receive a request to increase or decrease the numerical value; 
 determine a selected bucket of the plurality of buckets corresponding to the request, wherein the selected bucket is determined on a random basis; and 
 increase or decrease a portion of the numerical value in the selected bucket based at least in part on the request, wherein access to the selected bucket is granted using optimistic concurrency. 
 
 
     
     
       2. The system as recited in  claim 1 , wherein the record updating service is further configured to:
 receive an additional request to increase or decrease the numerical value, wherein the additional request is received before processing of the request is completed; 
 determine an additional selected bucket of the plurality of buckets corresponding to the additional request, wherein the additional selected bucket is determined on a random basis; and 
 increase or decrease a portion of the numerical value in the additional selected bucket based at least in part on the additional request, wherein access to the additional selected bucket is granted using optimistic concurrency. 
 
     
     
       3. The system as recited in  claim 1 , wherein the record is divided into the plurality of buckets based at least in part on a detection of contention on the record. 
     
     
       4. A computer-implemented method, comprising:
 performing, by one or more computing devices that implement a record updating service:
 dividing a record containing a numerical value into a plurality of buckets, wherein the buckets contain portions of the numerical value; 
 determining a selected bucket of the plurality of buckets corresponding to a request to update the numerical value, wherein the selected bucket is determined on a random basis; and 
 updating a portion of the numerical value in the selected bucket based at least in part on the request. 
 
 
     
     
       5. The method as recited in  claim 4 , wherein access to the selected bucket is granted using an optimistic concurrency technique, and wherein the method further comprises:
 receiving an additional request to update the numerical value, wherein the additional request is received before processing of the request is completed; 
 determining an additional selected bucket of the plurality of buckets corresponding to the additional request, wherein the additional selected bucket is determined on a random basis; and 
 updating a portion of the numerical value in the additional selected bucket based at least in part on the additional request, wherein access to the additional selected bucket is granted using the optimistic concurrency technique. 
 
     
     
       6. The method as recited in  claim 4 , wherein the record is divided into the plurality of buckets based at least in part on a detection of contention on the record. 
     
     
       7. The method as recited in  claim 4 , further comprising:
 determining that a portion of the numerical value in a particular bucket of the plurality of buckets has dropped below a threshold value; and 
 increasing the portion of the numerical value in the particular bucket using a value provisioned from the record or transferred from one or more other buckets of the plurality of buckets. 
 
     
     
       8. The method as recited in  claim 4 , further comprising:
 determining that a portion of the numerical value in a particular bucket of the plurality of buckets has dropped below a threshold value; 
 if the portion of the numerical value in the particular bucket is greater than zero, moving the portion of the numerical value from the particular bucket to the record or to one or more other buckets of the plurality of buckets; and 
 eliminating the particular bucket. 
 
     
     
       9. The method as recited in  claim 4 , further comprising:
 adding a new bucket to the plurality of buckets, wherein a portion of the numerical value in the new bucket is provisioned from the record or transferred from one or more other buckets of the plurality of buckets. 
 
     
     
       10. The method as recited in  claim 4 , further comprising:
 determining an initial quantity of the plurality of buckets for the record based at least in part on a number of average concurrent requests for a plurality of other records. 
 
     
     
       11. The method as recited in  claim 4 , further comprising:
 modifying a quantity of the plurality of buckets for the record based at least in part on an observed rate of contention on the plurality of buckets. 
 
     
     
       12. The method as recited in  claim 4 , further comprising:
 receiving an additional request to update the numerical value, wherein the additional request is received before processing of the request is completed; 
 determining the selected bucket of the plurality of buckets corresponding to the additional request, wherein the selected bucket is determined on a random basis; 
 failing to process the additional request using the selected bucket due to contention on the selected bucket; 
 determining an additional selected bucket of the plurality of buckets corresponding to the additional request, wherein the additional selected bucket is determined on a random basis; and 
 updating a portion of the numerical value in the additional selected bucket based at least in part on the additional request, wherein access to the additional selected bucket is granted using optimistic concurrency. 
 
     
     
       13. The method as recited in  claim 4 , further comprising:
 assigning an identifier to a particular one of the buckets, wherein the identifier is based at least in part on a primary key for the record plus an additional value specific to the particular one of the buckets. 
 
     
     
       14. The method as recited in  claim 4 , wherein access to the selected bucket is granted using a lock according to a pessimistic concurrency technique, and wherein the method further comprises:
 receiving an additional request to update the numerical value, wherein the additional request is received before processing of the request is completed; 
 determining an additional selected bucket of the plurality of buckets corresponding to the additional request, wherein the additional selected bucket is determined on a random basis; and 
 updating a portion of the numerical value in the additional selected bucket based at least in part on the additional request, wherein access to the additional selected bucket is granted using a lock according to the pessimistic concurrency technique. 
 
     
     
       15. A computer-readable storage medium storing program instructions computer-executable to perform:
 dividing a record into a plurality of sub-records, wherein the sub-records contain portions of the record; 
 determining a selected sub-record of the plurality of sub-records corresponding to a request to update the record; and 
 updating the portion of the record in the selected sub-record based at least in part on the request, wherein access to the selected sub-record is granted using optimistic concurrency. 
 
     
     
       16. The computer-readable storage medium as recited in  claim 15 , wherein the program instructions are further computer-executable to perform:
 receiving an additional request to update the record, wherein the additional request is received before processing of the request is completed; 
 determining an additional selected sub-record of the plurality of sub-records corresponding to the additional request, wherein the additional selected sub-record is determined on a random basis; and 
 updating a portion of the record in the additional selected sub-record based at least in part on the additional request, wherein access to the additional selected sub-record is granted using optimistic concurrency. 
 
     
     
       17. The computer-readable storage medium as recited in  claim 15 , wherein the record is divided into the plurality of sub-records based at least in part on a detection of contention on the record. 
     
     
       18. The computer-readable storage medium as recited in  claim 15 , wherein the program instructions are further computer-executable to perform:
 determining that a portion of the record in a particular sub-record of the plurality of sub-records has dropped below a threshold size; and 
 increasing the portion of the record in the particular sub-record using one or more elements provisioned from the record or transferred from one or more other sub-records of the plurality of sub-records. 
 
     
     
       19. The computer-readable storage medium as recited in  claim 15 , wherein the program instructions are further computer-executable to perform:
 determining that a portion of the record in a particular sub-record of the plurality of sub-records has dropped below a threshold size; 
 if the portion of the record in the particular sub-record is greater than zero, moving the portion of the record from the particular sub-record to the record or to one or more other sub-records of the plurality of sub-records; and 
 eliminating the particular sub-record. 
 
     
     
       20. The computer-readable storage medium as recited in  claim 15 , wherein the program instructions are further computer-executable to perform:
 modifying a quantity of the plurality of sub-records for the record based at least in part on an observed rate of contention on the plurality of sub-records.