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

Fingerprint

Servers
Cloud computing
Web services
Data structures
Semantics
Filter
Workload

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems and Management

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

Idempotent Distributed Counters Using a Forgetful Bloom Filter. / Subramanyam, Rajath; Gupta, Indranil; Leslie, Luke M.; Wang, Wenting.

Proceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 113-124 7312146 (Proceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015).

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

Subramanyam, R, Gupta, I, Leslie, LM & Wang, W 2015, Idempotent Distributed Counters Using a Forgetful Bloom Filter. in Proceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015., 7312146, Proceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015, Institute of Electrical and Electronics Engineers Inc., pp. 113-124, International Conference on Cloud and Autonomic Computing, ICCAC 2015, Boston, United States, 9/21/15. https://doi.org/10.1109/ICCAC.2015.30
Subramanyam R, Gupta I, Leslie LM, Wang W. Idempotent Distributed Counters Using a Forgetful Bloom Filter. In Proceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015. Institute of Electrical and Electronics Engineers Inc. 2015. p. 113-124. 7312146. (Proceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015). https://doi.org/10.1109/ICCAC.2015.30
Subramanyam, Rajath ; Gupta, Indranil ; Leslie, Luke M. ; Wang, Wenting. / Idempotent Distributed Counters Using a Forgetful Bloom Filter. Proceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 113-124 (Proceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015).
@inproceedings{a4e5ef8bcd2840ceaa587edca92ee3fc,
title = "Idempotent Distributed Counters Using a Forgetful Bloom Filter",
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.",
author = "Rajath Subramanyam and Indranil Gupta and Leslie, {Luke M.} and Wenting Wang",
year = "2015",
month = "10",
day = "28",
doi = "10.1109/ICCAC.2015.30",
language = "English (US)",
series = "Proceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "113--124",
booktitle = "Proceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015",
address = "United States",

}

TY - GEN

T1 - Idempotent Distributed Counters Using a Forgetful Bloom Filter

AU - Subramanyam, Rajath

AU - Gupta, Indranil

AU - Leslie, Luke M.

AU - Wang, Wenting

PY - 2015/10/28

Y1 - 2015/10/28

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84962129722&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84962129722&partnerID=8YFLogxK

U2 - 10.1109/ICCAC.2015.30

DO - 10.1109/ICCAC.2015.30

M3 - Conference contribution

AN - SCOPUS:84962129722

T3 - Proceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015

SP - 113

EP - 124

BT - Proceedings - 2015 International Conference on Cloud and Autonomic Computing, ICCAC 2015

PB - Institute of Electrical and Electronics Engineers Inc.

ER -