2026-09-19T15:54:53Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/88936 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Gupta, Indranil Subramanyam, Rajath 2016-03-02T19:32:55Z 2016-03-02T19:32:55Z 2015-08-18 2015-12 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. Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-03-02 without embargo terms The student, Rajath Subramanyam, accepted the attached license on 2015-08-18 at 07:27. The student, Rajath Subramanyam, submitted this Thesis for approval on 2015-08-18 at 07:48. This Thesis was approved for publication on 2015-08-18 at 14:19. DSpace SAF Submission Ingestion Package generated from Vireo submission #8663 on 2016-03-02 at 12:48:49 Made available in DSpace on 2016-03-02T19:32:55Z (GMT). No. of bitstreams: 2 SUBRAMANYAM-THESIS-2015.pdf: 691743 bytes, checksum: 7c7193d791a9b02eb3bee930dc7193f3 (MD5) LICENSE.txt: 4215 bytes, checksum: e47b4a88866528ba565c8ac2dd195b4b (MD5) Previous issue date: 2015-08-18 application/pdf http://hdl.handle.net/2142/88936 en Copyright 2015 Rajath Subramanyam Distributed Key-Value/NoSQL Storage Systems Bloom Filter Exactly-once Semantics Idempotent distributed counters using a Forgetful Bloom Filter text text Computer Science Computer Science University of Illinois at Urbana-Champaign Thesis M.S.