sketch_counting_bloom.nx source
↩ module page · 247 lines · 9024 B
1// sketch_counting_bloom.nx -- Counting Bloom filter (Fan-Cao-Almeida-Broder 1998).
2//
3// Bloom filter where each "bit" is a c-bit COUNTER instead of a single
4// bit. Insert increments k counters; delete decrements them. Query
5// returns "present" iff all k counters > 0.
6//
7// Compared to other set-membership primitives we ship:
8// - sketch_bloom (v2): bits only; no delete; smallest memory
9// - sketch_cuckoo: stores fingerprints in buckets; supports delete;
10// constant-time lookups; preferred when FPR < 3%
11// - sketch_counting_bloom (this): COUNTERS not bits; supports delete;
12// simpler than Cuckoo when FPR matters less;
13// supports MULTI-SET membership (counter > N tests)
14//
15// FPR is the same as classic Bloom: (1 - e^(-kn/m))^k. Memory is
16// k * c times Bloom's (c is counter width in bits).
17//
18// COUNTER SATURATION: caps at 2^c - 1. Once saturated, subsequent
19// decrements DO NOT restore the original count (information loss).
20// We use c=4 (saturation at 15), trading slight FPR overcount risk
21// for memory.
22//
23// LOSSLESS-LANGUAGE DISCIPLINE:
24// nx_cbloom_query returns ApproxI64 with NX_ENV_ABS, param_a tracking
25// saturation events (so caller knows whether the filter has reached
26// information-loss territory).
27
28import "syscalls.nx"
29import "murmur3.nx"
30import "sketch_types.nx"
31
32const NX_CB_COUNTER_MAX: i64 = 15 // 4-bit counters; saturates at 15
33const NX_CB_COUNTERS_PER_BYTE: i64 = 2 // 4-bit packed two per byte
34
35struct CountingBloom {
36 counters: *u8, // packed 4-bit counters
37 cap_counters: i64, // total counter slots (power of 2)
38 mask: i64, // cap_counters - 1
39 k: i64, // hash functions
40 n_inserted: i64,
41 saturations: i64, // count of saturation events (information loss)
42}
43
44// === counter access (4 bits per slot, 2 per byte) ================
45
46func nx_cb_counter_get(cb: *CountingBloom, idx: i64) -> i64 {
47 let byte_idx: i64 = idx >> 1
48 let high: i64 = idx & 1
49 let b: i64 = cb.counters[byte_idx]
50 if high == 0 { return b & 0x0F }
51 return (b >> 4) & 0x0F
52}
53
54func nx_cb_counter_set(cb: *CountingBloom, idx: i64, value: i64) -> i64 {
55 let byte_idx: i64 = idx >> 1
56 let high: i64 = idx & 1
57 let b: i64 = cb.counters[byte_idx]
58 var v: i64 = value & 0x0F
59 if high == 0 {
60 cb.counters[byte_idx] = (b & 0xF0) | v
61 }
62 if high == 1 {
63 cb.counters[byte_idx] = (b & 0x0F) | (v << 4)
64 }
65 return 0
66}
67
68// === alloc =======================================================
69
70func nx_cb_is_pow2(n: i64) -> i64 {
71 if n < 16 { return 0 }
72 if (n & (n - 1)) != 0 { return 0 }
73 return 1
74}
75
76func nx_cb_alloc(cap_counters: i64, k: i64) -> *CountingBloom {
77 if nx_cb_is_pow2(cap_counters) != 1 { return 0 as *CountingBloom }
78 if k < 1 { return 0 as *CountingBloom }
79 if k > 16 { return 0 as *CountingBloom }
80 let raw: *u8 = sys_mmap(56)
81 let cb: *CountingBloom = raw as *CountingBloom
82 let bytes: i64 = cap_counters / NX_CB_COUNTERS_PER_BYTE
83 cb.counters = sys_mmap(bytes)
84 var i: i64 = 0
85 while i < bytes {
86 cb.counters[i] = 0
87 i = i + 1
88 }
89 cb.cap_counters = cap_counters
90 cb.mask = cap_counters - 1
91 cb.k = k
92 cb.n_inserted = 0
93 cb.saturations = 0
94 return cb
95}
96
97// === insert / contains / delete ==================================
98//
99// Insert: increment k counters; if any reaches NX_CB_COUNTER_MAX,
100// the saturation counter ticks (counters stick at max thereafter).
101//
102// Delete: decrement k counters by 1, with floor at 0. CAUTION: if
103// any counter is at NX_CB_COUNTER_MAX (saturated), it stays there
104// (information loss). Caller should track via nx_cb_saturations.
105
106func nx_cb_insert(cb: *CountingBloom, key: *u8, len: i64) -> i64 {
107 let h1: i64 = murmur3_32(0, key, len) & 0xFFFFFFFF
108 let h2: i64 = murmur3_32(1, key, len) & 0xFFFFFFFF
109 var i: i64 = 0
110 while i < cb.k {
111 let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
112 let idx: i64 = combined & cb.mask
113 let cur: i64 = nx_cb_counter_get(cb, idx)
114 if cur >= NX_CB_COUNTER_MAX {
115 cb.saturations = cb.saturations + 1
116 }
117 if cur < NX_CB_COUNTER_MAX {
118 nx_cb_counter_set(cb, idx, cur + 1)
119 }
120 i = i + 1
121 }
122 cb.n_inserted = cb.n_inserted + 1
123 return 0
124}
125
126func nx_cb_contains(cb: *CountingBloom, key: *u8, len: i64) -> i64 {
127 let h1: i64 = murmur3_32(0, key, len) & 0xFFFFFFFF
128 let h2: i64 = murmur3_32(1, key, len) & 0xFFFFFFFF
129 var i: i64 = 0
130 while i < cb.k {
131 let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
132 let idx: i64 = combined & cb.mask
133 if nx_cb_counter_get(cb, idx) == 0 { return 0 }
134 i = i + 1
135 }
136 return 1
137}
138
139func nx_cb_delete(cb: *CountingBloom, key: *u8, len: i64) -> i64 {
140 // Caller responsibility: only call delete on items that were
141 // inserted. Decrement all k counters by 1 (with floor 0, and
142 // saturated counters STAY at saturation).
143 let h1: i64 = murmur3_32(0, key, len) & 0xFFFFFFFF
144 let h2: i64 = murmur3_32(1, key, len) & 0xFFFFFFFF
145 var i: i64 = 0
146 while i < cb.k {
147 let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
148 let idx: i64 = combined & cb.mask
149 let cur: i64 = nx_cb_counter_get(cb, idx)
150 if cur == 0 {
151 // Item was never inserted (or already deleted).
152 return -1
153 }
154 if cur < NX_CB_COUNTER_MAX {
155 nx_cb_counter_set(cb, idx, cur - 1)
156 }
157 // If saturated, leave at saturation -- info already lost.
158 i = i + 1
159 }
160 cb.n_inserted = cb.n_inserted - 1
161 return 0
162}
163
164// === minimum-counter ESTIMATE of element multiplicity =============
165//
166// MULTI-SET CAPABILITY (beyond classic Bloom):
167// For multi-sets (same item inserted N times), the minimum of the
168// k counters lower-bounds the true multiplicity. This works
169// because each insertion increments k counters by 1, so even the
170// MINIMUM counter for an item must have at least mult(item).
171//
172// Returns 0 if item not present.
173
174func nx_cb_estimate_multiplicity(cb: *CountingBloom, key: *u8, len: i64) -> i64 {
175 let h1: i64 = murmur3_32(0, key, len) & 0xFFFFFFFF
176 let h2: i64 = murmur3_32(1, key, len) & 0xFFFFFFFF
177 let combined0: i64 = h1 & cb.mask
178 var min_count: i64 = nx_cb_counter_get(cb, combined0)
179 var i: i64 = 1
180 while i < cb.k {
181 let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
182 let idx: i64 = combined & cb.mask
183 let c: i64 = nx_cb_counter_get(cb, idx)
184 if c < min_count { min_count = c }
185 i = i + 1
186 }
187 return min_count
188}
189
190// === FPR (same formula as Bloom) ==================================
191
192func nx_cb_fpr_ppb(cb: *CountingBloom) -> i64 {
193 if cb.n_inserted == 0 { return 0 }
194 let m_over_n: i64 = cb.cap_counters / cb.n_inserted
195 if m_over_n <= 0 { return 1000000000 }
196 if m_over_n == 1 { return 618500000 }
197 if m_over_n == 2 { return 382500000 }
198 if m_over_n == 4 { return 146300000 }
199 if m_over_n == 8 { return 21420000 }
200 if m_over_n == 16 { return 458000 }
201 if m_over_n == 32 { return 216 }
202 return 0
203}
204
205func nx_cb_query(cb: *CountingBloom, key: *u8, len: i64) -> *ApproxI64 {
206 let present: i64 = nx_cb_contains(cb, key, len)
207 let fpr: i64 = nx_cb_fpr_ppb(cb)
208 return nx_approx_new(present, NX_ENV_ABS, cb.saturations,
209 1000000000 - fpr,
210 NX_MATURITY_REFERENCE_IMPL,
211 NX_ADV_HONEST)
212}
213
214// === merge ========================================================
215//
216// Counter-wise addition (with saturation). Both filters must have
217// matching cap + k.
218
219func nx_cb_merge(a: *CountingBloom, b: *CountingBloom) -> *CountingBloom {
220 if a.cap_counters != b.cap_counters { return 0 as *CountingBloom }
221 if a.k != b.k { return 0 as *CountingBloom }
222 let out: *CountingBloom = nx_cb_alloc(a.cap_counters, a.k)
223 var i: i64 = 0
224 while i < a.cap_counters {
225 let va: i64 = nx_cb_counter_get(a, i)
226 let vb: i64 = nx_cb_counter_get(b, i)
227 var sum: i64 = va + vb
228 if sum > NX_CB_COUNTER_MAX {
229 sum = NX_CB_COUNTER_MAX
230 out.saturations = out.saturations + 1
231 }
232 nx_cb_counter_set(out, i, sum)
233 i = i + 1
234 }
235 out.n_inserted = a.n_inserted + b.n_inserted
236 return out
237}
238
239// === introspection ================================================
240
241func nx_cb_saturations(cb: *CountingBloom) -> i64 {
242 return cb.saturations
243}
244
245func nx_cb_memory_bytes(cb: *CountingBloom) -> i64 {
246 return 56 + cb.cap_counters / NX_CB_COUNTERS_PER_BYTE
247}