Probabilistic Data Structures TODO
Concept
Probabilistic data structures trade an exact answer for a bounded error, in exchange for a large reduction in memory. A Bloom filter tests set membership using a bit array and k hash functions; it can produce false positives but never false negatives, and doesn't support deletion. A Cuckoo filter instead stores a short fingerprint of the element in one of two candidate buckets, which lets it support deletion. A Count-Min sketch estimates frequencies using a grid of counters indexed by several hash rows; collisions can cause it to overestimate, but never underestimate. HyperLogLog estimates the cardinality (count of distinct elements) by recording, across many buckets, the maximum number of leading zero bits seen in a hash value — using almost constant memory.
In places like logs, mempools, or caches where the element count runs into the hundreds of millions, holding an exact set or counter blows the memory budget before anything else fails.
Code & Formula
# Day 6: 확률적 자료구조 — Bloom Filter로 집합 포함 여부를 확률적으로 판정
# 비트 배열 + k개의 해시로 원소를 삽입하고, 거짓 양성(false positive)이 실제로 발생함을 확인한다.
import hashlib
class BloomFilter:
def __init__(self, size, k):
self.size = size
self.k = k
self.bits = [0] * size
def _hashes(self, item):
for i in range(self.k):
h = hashlib.sha256(f"{i}:{item}".encode()).digest()
yield int.from_bytes(h, "big") % self.size
def add(self, item):
for idx in self._hashes(item):
self.bits[idx] = 1
def might_contain(self, item):
return all(self.bits[idx] for idx in self._hashes(item))
bf = BloomFilter(size=64, k=3)
inserted = [f"tx-{i}" for i in range(20)]
for item in inserted:
bf.add(item)
checked, false_positives = 2000, 0
for i in range(checked):
probe = f"probe-{i}"
if probe not in inserted and bf.might_contain(probe):
false_positives += 1
print(f"삽입 원소 {len(inserted)}개, 비트 배열 크기 {bf.size}, 해시 개수 {bf.k}")
print(f"might_contain('tx-5') = {bf.might_contain('tx-5')} (실제 포함 원소 -> 항상 True)")
print(f"거짓 양성 {false_positives} / {checked}회 (비율 {false_positives / checked:.3%})")
docs/code/algorithms/algorithms-6.py
Exercise
Implement a Bloom filter and, by varying the bit count m and the number of hash functions k, compare the measured false-positive rate against the theoretical value.
Practical Connection
Bloom-style filters are used in P2P gossip to avoid re-propagating transaction or block hashes that have already been seen, and Verex could apply the same idea as a cheap first-pass filter for event logs or order IDs it has already processed.
Where it lands in Jayverse
- Verex: size the Bloom filter to a stated false-positive budget. Before wiring it into event-log processing, pick m and k for a concrete target — e.g. under 0.1% FP at 10M processed order IDs — and fall back to an exact check on every positive hit, since Bloom never gives false negatives but the exact check is still required.
- gitboard: use a Count-Min sketch or HyperLogLog for high-cardinality metrics. Track approximate event volume or distinct-error counts across services without storing every log line, for dashboard metrics that don't need exactness.
- Devnet: prefer a Cuckoo filter for the rolling seen-tx cache. Anvil devnet resets and forks periodically, so an already-seen-tx cache needs deletion support, which a Bloom filter doesn't offer but a Cuckoo filter does.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| trade X for Y | X를 Y와 맞바꾸다 · 정확도를 포기하고 다른 이득을 얻을 때. "trade an exact answer for a bounded error" |
| in exchange for | ~의 대가로 · 무엇을 포기하고 무엇을 얻는지 말할 때. "in exchange for a large reduction in memory" |
| blow the budget | 예산(한도)을 초과해버리다 · 메모리 한도를 넘어설 때. "blows the memory budget before anything else fails" |
| run into (a number) | (수치가) ~에 달하다, 이르다 · 원소 개수가 매우 커질 때. "the element count runs into the hundreds of millions" |
| first-pass filter | 1차 거름망(초벌 필터링) · 값싼 사전 필터링 용도로 쓰일 때. "a cheap first-pass filter for event logs" |
| re-propagate | 다시 전파하다 · 이미 본 데이터를 또 퍼뜨리는 낭비를 막을 때. "to avoid re-propagating transaction or block hashes" |
| Bloom filter | 블룸 필터 · 비트 배열과 k개의 해시함수로 멤버십을 검사, 오탐은 가능해도 오탈락은 없음. "A Bloom filter tests set membership using a bit array" |
| Cuckoo filter | 쿠쿠 필터 · 원소의 짧은 지문을 두 후보 버킷 중 하나에 저장해 삭제를 지원. "instead stores a short fingerprint of the element" |
| Count-Min sketch | 카운트-민 스케치 · 여러 해시 행으로 색인된 카운터 그리드로 빈도를 추정, 과대추정은 가능해도 과소추정은 없음. "collisions can cause it to overestimate, but never underestimate" |
| HyperLogLog | 하이퍼로그로그 · 해시값의 선행 0 비트 최댓값을 버킷마다 기록해 거의 상수 메모리로 카디널리티를 추정. "estimates the cardinality (count of distinct elements) by recording" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.