Idempotent Distributed Counters Using a Forgetful Bloom Filter

Rajath Subramanyam, Indranil Gupta, Luke M. Leslie, Wenting Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Distributed key-value stores power the backend of high-performance web services and cloud computing applications. Key-value stores such as Cassandra rely heavily on counters to keep track of the occurrences of various kinds of events. However, today's implementations of counters do not provide exactly-once semantics. A typical scenario is that a client requests a counter increment, times out waiting for a response, and creates a duplicate request, thus resulting in a double increment on the server side. In this paper, we address this problem by presenting, analyzing, and evaluating a novel server-side data structure called the Forgetful Bloom Filter (FBF). Like a traditional Bloom filter, an FBF is a compact representation of a set of elements (e.g., client requests). However, an FBF is more powerful than a Bloom filter in two aspects: i) it can forget older elements (e.g., requests that are too old to apply), and ii) it is self-adapting under a varying workload. We also present an adaptive variant of FBF that adapts itself to meet a desired false positive rate-thus the error achieved in the counter can be bounded even as the workload changes. We present experimental results from a prototype implementation of FBFs and discuss the implications for a key-value store such as Cassandra. Our results show that the FBF is highly accurate in maintaining correct counter values.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages113-124
Number of pages12
ISBN (Electronic)0769556361, 9781467395663
DOIs
StatePublished - Oct 28 2015
EventInternational Conference on Cloud and Autonomic Computing, ICCAC 2015 - Boston, United States
Duration: Sep 21 2015Sep 25 2015

Publication series

NameProceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015

Other

OtherInternational Conference on Cloud and Autonomic Computing, ICCAC 2015
CountryUnited States
CityBoston
Period9/21/159/25/15

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Idempotent Distributed Counters Using a Forgetful Bloom Filter'. Together they form a unique fingerprint.

  • Cite this

    Subramanyam, R., Gupta, I., Leslie, L. M., & Wang, W. (2015). Idempotent Distributed Counters Using a Forgetful Bloom Filter. In Proceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015 (pp. 113-124). [7312146] (Proceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICCAC.2015.30