System and method for implementing shared probabilistic counters storing update probability values

摘要

The systems and methods described herein may implement probabilistic counters and/or update mechanisms for those counters such that they are dependent on the value of a configurable accuracy parameter. The accuracy parameter value may be adjusted to provide fine-grained control over the tradeoff between the accuracy of the counters and the performance of applications that access them. The counters may be implemented as data structures that include a mantissa portion and an exponent portion that collectively represent an update probability value. When updating the counters, the value of the configurable accuracy parameter may affect whether, when, how often, or by what amount the mantissa portion and/or the exponent portion are updated. Updating a probabilistic counter may include multiplying its value by a constant that is dependent on the value of a configurable accuracy parameter. The counters may be accessible within transactions. The counters may have deterministic update policies.

主权项

1. A method, comprising:
performing by one or more computing nodes, each of which comprises at least one processor core and a memory:
beginning execution of a multithreaded application that comprises one or more operations to increment a shared counter, wherein the shared counter is implemented as a data structure that is accessible by a plurality of threads of the multithreaded application that are executing on the one or more computing nodes, wherein the data structure stores a representation of an update probability value, wherein the update probability value indicates a probability that the representation of the update probability value will be updated in response to initiation of an increment operation targeting the shared counter, and wherein a projected value of the shared counter is computable based at least in part on the representation of the update probability value;initiating, by a given thread of the application, an increment operation targeting the shared counter;in response to said initiating, determining whether to perform the increment operation, wherein said determining is dependent, at least in part, on the representation of the update probability stored in the data structure; andin response to determining that the increment operation is to be performed, updating the representation of the update probability value stored in the data structure, wherein the updated representation represents a probability that the updated representation of the update probability value stored in the data structure will be further updated in response to initiation of a subsequent increment operation;wherein one or more of said determining whether to perform the increment operation or said updating the representation of the update probability value are dependent on a pre-determined value of a configurable accuracy parameter.