{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/88936"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/88936","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"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 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.","abstract_html":"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.","abstract_has_math":false,"creators":["Subramanyam, Rajath"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Gupta, Indranil"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-03-02T19:32:55Z","date_published":"2016-03-02T19:32:55Z","updated_at":"2026-07-22T22:26:32Z","subjects":["Distributed Key-Value/NoSQL Storage Systems","Bloom Filter","Exactly-once Semantics"],"languages":["en"],"rights":["Copyright 2015 Rajath Subramanyam"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/88936","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Gupta, Indranil"]},{"key":"dc:creator","label":"Author","values":["Subramanyam, Rajath"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016-03-02T19:32:55Z","2015-08-18","2015-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Distributed Key-Value/NoSQL Storage Systems","Bloom Filter","Exactly-once Semantics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2015 Rajath Subramanyam"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/88936"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Idempotent distributed counters using a Forgetful Bloom Filter"]}]}],"canonical_facts":{"dc:contributor":["Gupta, Indranil"],"dc:creator":["Subramanyam, Rajath"],"dc:date":["2016-03-02T19:32:55Z","2015-08-18","2015-12"],"dc:description":["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"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/88936"],"dc:language":["en"],"dc:rights":["Copyright 2015 Rajath Subramanyam"],"dc:subject":["Distributed Key-Value/NoSQL Storage Systems","Bloom Filter","Exactly-once Semantics"],"dc:title":["Idempotent distributed counters using a Forgetful Bloom Filter"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:32Z"}