Source-linked AI summary
Invertible Bloom Lookup Tables
Michael T. Goodrich, Michael Mitzenmacher
TL;DR
The paper addresses the need for a probabilistic lookup table that stores key-value pairs while also allowing its contents to be listed. It introduces the invertible Bloom lookup table, which provides thresholded high-probability listing, efficient updates, and checksum-based error tolerance. The resulting structure remains space-efficient during temporary overload and supports applications such as database reconciliation and network tracking.
Problem
Existing probabilistic structures for key-value pairs did not provide the desired ability to list all stored pairs.
Method
The paper develops a Bloom-filter variation for key-value pairs with lookup, listing, threshold-aware operation, and additional checksums for selected errors.
Results
The IBLT lists all key-value pairs with high probability when their number is at most threshold t, while space remains at most linear in t even when the stored count exceeds t.
Takeaways & Limitations
The structure supports database reconciliation and network tracking by combining contents listing, efficient updates, and robustness to specified errors.
Takeaways & Limitations
Lookup and listing have their stated high-probability guarantees only when the current number of keys is at most t, and recovery can fail when no suitable cell is found.
Abstract
from arXiv · showhide
We present a version of the Bloom filter data structure that supports not only the insertion, deletion, and lookup of key-value pairs, but also allows a complete listing of its contents with high probability, as long the number of key-value pairs is below a designed threshold. Our structure allows the number of key-value pairs to greatly exceed this threshold during normal operation. Exceeding the threshold simply temporarily prevents content listing and reduces the probability of a successful lookup. If later entries are deleted to return the structure below the threshold, everything again functions appropriately. We also show that simple variations of our structure are robust to certain standard errors, such as the deletion of a key without a corresponding insertion or the insertion of two distinct values for a key. The properties of our structure make it suitable for several applications, including database and networking applications that we highlight.
1 Introduction
The paper introduces the invertible Bloom lookup table (IBLT), a Bloom-filter variation for key-value pairs that supports probabilistic lookup and high-probability content listing. Its thresholded, space-efficient design also supports error-tolerant operation and applications including database reconciliation and network tracking.
- 1 Introduction: The IBLT extends Bloom filters from set membership to probabilistic storage and retrieval of fixed-length integer key-value pairs.Unlike prior key-value structures cited here, it is specifically designed to list all stored pairs.
- 1.2 Our Results: Insertions, deletions, and lookups take O(k) time, where k is the number of random hash functions, while lookup succeeds with a probability that can approach 1.The structure also supports complete listing with high probability when the number of pairs is at most threshold t, in O(t) time.
- 1.2 Our Results: Space remains at most linear in threshold t even when the number of stored pairs grows well beyond t, including to polynomial in t.This avoids the space growth and more expensive lookups associated with explicitly maintaining a list of all pairs.
- 1.2 Our Results: Additional checksums allow the IBLT to tolerate unpaired deletions, repeated same-value insertions, and simultaneous multiple values for a key.The paper connects this error tolerance with applications that require contents listing.
- Applications and Usage Cases: For database reconciliation, an IBLT lets one party identify differing records using a message of size O(t), where t bounds the number of differences.Indices serve as keys and record checksums as values; the method identifies insertions, deletions, and differing checksums.
- Applications and Usage Cases: For network tracking, the IBLT records TCP flows, supports fast updates and listing below threshold t, and regains its intended functionality after temporary overload subsides.The structure can also be copied to an offline agent for processing and can tolerate several flow-tracking errors.
2 A Simple Version of the Invertible Bloom Lookup Table
The simple IBLT stores key-value pairs in hashed cells and supports updates, lookups, and complete listing with high probability below a designed threshold.
- Listing set entries: LISTENTRIES succeeds with high probability when n is below the designed threshold, returning the complete contents if all cells are emptied during peeling.Otherwise, it returns only a partial list with a “list-incomplete” condition.
- Data operations: INSERT and DELETE always succeed under distinct-key and correctly matched-operation assumptions, while GET may return a constant-probability “not found” failure.A returned value or null is correct under these assumptions; failure occurs when no mapped cell contains only one entry.
- Data structure architecture: The structure uses O(m) words even when the number of stored key-value pairs temporarily exceeds m.The table is initialized with m cells, each containing a constant number of fields.
- Data structure architecture: IBLT cells store counts, key sums, and value sums for key-value pairs mapped by k distinct hash locations.Insertions add one to the count and add the key and value to the corresponding sums; deletions subtract them.
- Assumptions: The analysis assumes fully random hash functions for simplicity, although the authors state that full randomness does not appear strictly required.Limited-independence guarantees for worst-case data remain an open theoretical issue in the cited discussion.
- Listing set entries: For k constant and m > (c_k + ϵ)n, listing failure is O(n^−k+2) for small cores, while larger-core failures are exponentially small.The threshold constants c_k arise from the 2-core thresholds of random hypergraphs.
3 Adding Fault Tolerance to an Invertible Bloom Lookup Table
The IBLT adds checksum-based fault tolerance for extraneous deletions, duplicate values, and other inconsistencies, while preserving high-probability listing under stated conditions.
- Extraneous Deletions: HashkeySum checks detect whether count-1 cells correspond to valid keys despite extraneous deletions.A false check occurs with probability at most 1/R when hashed key values align spuriously.
- Assumptions: The fault-tolerance analysis assumes false checksum checks do not occur, requiring sufficiently random hashes and sufficiently large checksum fields.
- Multiple Values: Value checksums detect inconsistent values, but a key inserted with multiple values poisons its associated cells and can block listing recovery.If a key is inserted and deleted with different values, even a count-1 cell can pass key checks while its valueSum is incorrect.
- Multiple Values: With a constant invalid-key fraction γ, the approximate unrecoverability probability for a valid key is (1 − e^(−kγn/m))^k.For k = 5, m/n = 8, and γ = 1/10, the probability is approximately 8.16 · 10^−7.
- Extraneous Deletions: LISTENTRIES can recover all valid keys with high probability when n^(1−β) keys are invalid, k = ⌈1/β⌉ + 4, and m > (ck + ϵ)n.
- Lost Memory Subblocks: A lost memory subblock can still permit high-probability listing, with only reduced GET success probability when the remaining hashes suffice.
4 Space-Saving for an Invertible Bloom Lookup Table
IBLT space can be reduced through compression, quotienting, XORs in restricted settings, or by sacrificing lookup accuracy while preserving successful listing.
- Compression: Compressed arrays and variable-length fields can remove wasted space from zero entries and oversized fixed-length fields.
- Quotienting: Quotienting stores a bucket and quotient value, reducing space for fields such as keySum and hashkeySum.
- Quotienting: XORs can replace sums when duplicate copies of the same key-value pair are absent, saving space.
- Accuracy–Space Trade-off: Reducing lookup accuracy can lower space requirements because high space usage primarily supports accurate GET operations, not LISTENTRIES.
5 Simulations and Experiments
Simulations validate the predicted listing thresholds and show robust recovery with duplicate identical values, extraneous deletions, and some multiple-valued keys.
- Threshold Validation: Asymptotic decoding thresholds closely match simulations even with 10,000 and 100,000 keys.All trials succeeded at 14,600 cells for 10,000 keys and at least 144,000 cells for 100,000 keys.
- Duplicates and Extraneous Deletions: 20,000 trials with duplicate identical values and extraneous deletions achieved complete listing every time and 97.83% average GET success.The same result held for both 10,000 keys with 80,000 cells and 100,000 keys with 800,000 cells.
- Multiple Values: With 500 multiple-valued keys, 9,500 valid pairs were fully recovered in 19,996 of 20,000 trials; with 1,000, they were fully recovered in 19,872 trials.GET success remained 97.83% on valid keys in both cases.
- Multiple Values: Complete recovery becomes less likely as the number of multiple-valued keys increases, even when the invalid-key percentage is unchanged.
- Multiple Values: Across Table 2 experiments, no trial left more than three valid keys unrecovered despite invalid multiple-valued keys.The experiments used 10,000 or 100,000 total keys with 1,000, 2,000, or 10,000 multiple-valued keys.
6 Conclusion and Future Work
The paper extends Bloom filters to key-value pairs with content listing and derives its analysis from recent results on 2-cores in hypergraphs.
- Conclusion: The IBLT extends Bloom filters to key-value pairs and supports listing its contents.The authors identify allowing multiple values as a direction for future work.