Idempotent distributed counters using a Forgetful Bloom Filter

Subramanyam, Rajath

Permalink

https://hdl.handle.net/2142/88936 Copy

Description

Title

Idempotent distributed counters using a Forgetful Bloom Filter

Author(s)

Subramanyam, Rajath

Issue Date

2015-08-18

Director of Research (if dissertation) or Advisor (if thesis)

Gupta, Indranil

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Distributed Key-Value/NoSQL Storage Systems
• Bloom Filter
• Exactly-once Semantics

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 thesis, 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.

Graduation Semester

2015-12

Type of Resource

text

Permalink

http://hdl.handle.net/2142/88936

Copyright and License Information

Copyright 2015 Rajath Subramanyam

Owning Collections