sketch_cuckoo.nx source
↩ module page · 277 lines · 9682 B
1// sketch_cuckoo.nx -- Cuckoo Filter (Fan et al. 2014).
2//
3// Approximate-set-membership primitive with DELETION support --
4// the headline capability Bloom filters lack. Each item gets one
5// of two candidate buckets (the second derived from the
6// fingerprint via XOR), so lookups check both buckets and inserts
7// fall back to relocation when both are full.
8//
9// Versus Bloom (runtime/bloom.nx already shipped):
10// Bloom: k bit-sets per insert, no delete, false-positive rate
11// ~ (1 - e^(-kn/m))^k
12// Cuckoo: fingerprint slots per bucket, supports delete, false-
13// positive rate ~ 2 * bucket_size / (2^fp_bits)
14// At the same memory + FP rate, Cuckoo is typically more
15// space-efficient than Bloom AND supports deletes.
16//
17// Parameters:
18// n_buckets: power of 2 (for XOR-friendly indexing). Total
19// capacity is roughly 95% * n_buckets * 4.
20// bucket_size: we use 4 (canonical; trade-off well-studied).
21// fingerprint: 8 bits (1 byte per slot). False-positive rate
22// ~ 2*4/256 = 3.1% at high load. 16-bit
23// fingerprints (0.024% FP) are queued for v2.
24//
25// LOSSLESS-LANGUAGE DISCIPLINE (doc 20):
26// Membership query returns ApproxI64 with envelope_kind =
27// NX_ENV_ABS, param_a = 0 (false positives but NEVER false
28// negatives for items truly inserted), conf_ppb = 1e9 -
29// expected_fpr_ppb. Substrate's typed envelope precisely
30// declares "absent" is exact and "present" is bounded-uncertain.
31
32import "syscalls.nx"
33import "sketch_types.nx"
34
35const NX_CUCKOO_BUCKET_SIZE: i64 = 4
36const NX_CUCKOO_FP_BITS: i64 = 8
37const NX_CUCKOO_MAX_KICKS: i64 = 500
38const NX_CUCKOO_EMPTY: i64 = 0 // fingerprint 0 = slot empty
39
40// LCG constants for random eviction selection.
41const NX_CUCKOO_LCG_A: i64 = 1103515245
42const NX_CUCKOO_LCG_C: i64 = 12345
43const NX_CUCKOO_LCG_MOD: i64 = 0x7FFFFFFF
44
45struct CuckooFilter {
46 buckets: *u8, // n_buckets * 4 bytes
47 n_buckets: i64, // power of 2
48 mask: i64, // n_buckets - 1
49 total: i64, // items currently stored
50 rng_state: i64,
51}
52
53// === fingerprint derivation =====================================
54//
55// Fingerprint is the low 8 bits of the item hash, but adjusted so
56// it's never 0 (0 is the empty sentinel). Caller passes a 64-bit
57// hash; we mix and mask.
58
59func nx_cuckoo_fingerprint(hash: i64) -> i64 {
60 let fp: i64 = hash & 0xFF
61 if fp == 0 { return 1 } // remap 0 -> 1 (never empty sentinel)
62 return fp
63}
64
65// === bucket index derivation ====================================
66//
67// Two candidate buckets per item:
68// b1 = (hash >> 8) & mask
69// b2 = b1 XOR (hash_of_fingerprint & mask)
70// Symmetric: given any one of {b1, b2}, can derive the other
71// without storing the original hash.
72
73func nx_cuckoo_bucket1(c: *CuckooFilter, hash: i64) -> i64 {
74 return (hash >> 8) & c.mask
75}
76
77// Hash the fingerprint via a small mixing function to spread it.
78func nx_cuckoo_fp_hash(fp: i64) -> i64 {
79 let h: i64 = (fp * 0x9E3779B97F4A7C15) & 0xFFFFFFFFFFFFFFFF
80 return h
81}
82
83func nx_cuckoo_bucket2(c: *CuckooFilter, b1: i64, fp: i64) -> i64 {
84 let fph: i64 = nx_cuckoo_fp_hash(fp)
85 return (b1 ^ fph) & c.mask
86}
87
88// === construction ===============================================
89//
90// n_buckets must be a power of 2 and >= 4.
91
92func nx_cuckoo_alloc(n_buckets: i64, seed: i64) -> *CuckooFilter {
93 if n_buckets < 4 { return 0 as *CuckooFilter }
94 if (n_buckets & (n_buckets - 1)) != 0 {
95 // not power of 2
96 return 0 as *CuckooFilter
97 }
98 let raw: *u8 = sys_mmap(48)
99 let c: *CuckooFilter = raw as *CuckooFilter
100 c.n_buckets = n_buckets
101 c.mask = n_buckets - 1
102 let bytes: i64 = n_buckets * NX_CUCKOO_BUCKET_SIZE
103 c.buckets = sys_mmap(bytes)
104 var i: i64 = 0
105 while i < bytes {
106 c.buckets[i] = 0
107 i = i + 1
108 }
109 c.total = 0
110 c.rng_state = seed | 1
111 return c
112}
113
114func nx_cuckoo_rng_next(c: *CuckooFilter) -> i64 {
115 let next: i64 = ((c.rng_state * NX_CUCKOO_LCG_A) + NX_CUCKOO_LCG_C) & NX_CUCKOO_LCG_MOD
116 c.rng_state = next
117 return next
118}
119
120// === bucket helpers =============================================
121
122func nx_cuckoo_bucket_addr(c: *CuckooFilter, b: i64) -> *u8 {
123 return (c.buckets as i64 + b * NX_CUCKOO_BUCKET_SIZE) as *u8
124}
125
126func nx_cuckoo_try_insert_bucket(c: *CuckooFilter, b: i64, fp: i64) -> i64 {
127 // Returns 1 if there was an empty slot and we filled it; 0 else.
128 let buf: *u8 = nx_cuckoo_bucket_addr(c, b)
129 var i: i64 = 0
130 while i < NX_CUCKOO_BUCKET_SIZE {
131 if buf[i] == NX_CUCKOO_EMPTY {
132 buf[i] = fp
133 return 1
134 }
135 i = i + 1
136 }
137 return 0
138}
139
140func nx_cuckoo_bucket_contains(c: *CuckooFilter, b: i64, fp: i64) -> i64 {
141 let buf: *u8 = nx_cuckoo_bucket_addr(c, b)
142 var i: i64 = 0
143 while i < NX_CUCKOO_BUCKET_SIZE {
144 if buf[i] == fp { return 1 }
145 i = i + 1
146 }
147 return 0
148}
149
150func nx_cuckoo_bucket_remove(c: *CuckooFilter, b: i64, fp: i64) -> i64 {
151 let buf: *u8 = nx_cuckoo_bucket_addr(c, b)
152 var i: i64 = 0
153 while i < NX_CUCKOO_BUCKET_SIZE {
154 if buf[i] == fp {
155 buf[i] = NX_CUCKOO_EMPTY
156 return 1
157 }
158 i = i + 1
159 }
160 return 0
161}
162
163// === insert (with random eviction) ==============================
164//
165// Try bucket1 then bucket2; if both full, evict a random
166// fingerprint from one of them and relocate it to its alternate.
167// Bounded by NX_CUCKOO_MAX_KICKS retries; on failure, the filter
168// is considered full.
169
170func nx_cuckoo_insert(c: *CuckooFilter, hash: i64) -> i64 {
171 let fp: i64 = nx_cuckoo_fingerprint(hash)
172 let b1: i64 = nx_cuckoo_bucket1(c, hash)
173 if nx_cuckoo_try_insert_bucket(c, b1, fp) == 1 {
174 c.total = c.total + 1
175 return 1
176 }
177 let b2: i64 = nx_cuckoo_bucket2(c, b1, fp)
178 if nx_cuckoo_try_insert_bucket(c, b2, fp) == 1 {
179 c.total = c.total + 1
180 return 1
181 }
182 // Both buckets full -- kick.
183 var cur_b: i64 = b1
184 if (nx_cuckoo_rng_next(c) & 1) == 1 { cur_b = b2 }
185 var cur_fp: i64 = fp
186 var kick: i64 = 0
187 while kick < NX_CUCKOO_MAX_KICKS {
188 let buf: *u8 = nx_cuckoo_bucket_addr(c, cur_b)
189 // Pick random slot in this bucket, swap.
190 let slot: i64 = nx_cuckoo_rng_next(c) & (NX_CUCKOO_BUCKET_SIZE - 1)
191 let evicted: i64 = buf[slot]
192 buf[slot] = cur_fp
193 cur_fp = evicted
194 // Move evicted to its alternate bucket.
195 cur_b = nx_cuckoo_bucket2(c, cur_b, cur_fp)
196 if nx_cuckoo_try_insert_bucket(c, cur_b, cur_fp) == 1 {
197 c.total = c.total + 1
198 return 1
199 }
200 kick = kick + 1
201 }
202 // Failed -- filter is too full. Last evicted fingerprint is
203 // lost (the original item, however, is still represented by
204 // whatever slot we wrote during the kick chain).
205 return 0
206}
207
208// === contains ====================================================
209
210func nx_cuckoo_contains(c: *CuckooFilter, hash: i64) -> i64 {
211 let fp: i64 = nx_cuckoo_fingerprint(hash)
212 let b1: i64 = nx_cuckoo_bucket1(c, hash)
213 if nx_cuckoo_bucket_contains(c, b1, fp) == 1 { return 1 }
214 let b2: i64 = nx_cuckoo_bucket2(c, b1, fp)
215 return nx_cuckoo_bucket_contains(c, b2, fp)
216}
217
218// === delete ======================================================
219//
220// Cuckoo filter supports DELETE -- the headline capability Bloom
221// lacks. Find the fingerprint in either bucket, clear it.
222// Returns 1 if removed, 0 if not present. Caveat: if the same
223// item was inserted twice, only one copy is removed.
224
225func nx_cuckoo_delete(c: *CuckooFilter, hash: i64) -> i64 {
226 let fp: i64 = nx_cuckoo_fingerprint(hash)
227 let b1: i64 = nx_cuckoo_bucket1(c, hash)
228 if nx_cuckoo_bucket_remove(c, b1, fp) == 1 {
229 c.total = c.total - 1
230 return 1
231 }
232 let b2: i64 = nx_cuckoo_bucket2(c, b1, fp)
233 if nx_cuckoo_bucket_remove(c, b2, fp) == 1 {
234 c.total = c.total - 1
235 return 1
236 }
237 return 0
238}
239
240// === error bound + query =========================================
241//
242// False-positive rate: ~ 2 * bucket_size / 2^fp_bits = 2*4/256 = 3.1%
243// at any load. Tighter than naive Bloom at the same memory for
244// most workloads.
245// confidence = 1 - FPR.
246
247func nx_cuckoo_fpr_ppb() -> i64 {
248 return 31000000 // 3.1%
249}
250
251func nx_cuckoo_query(c: *CuckooFilter, hash: i64) -> *ApproxI64 {
252 let present: i64 = nx_cuckoo_contains(c, hash)
253 // Envelope for membership: absent is exact (0), present has
254 // bounded-uncertain (might be a false positive).
255 // We declare conf as 1 - FPR so callers see the true reliability.
256 return nx_approx_new(present, NX_ENV_ABS, 0,
257 1000000000 - nx_cuckoo_fpr_ppb(),
258 NX_MATURITY_REFERENCE_IMPL,
259 NX_ADV_HONEST)
260}
261
262// === memory + load introspection =================================
263
264func nx_cuckoo_memory_bytes(c: *CuckooFilter) -> i64 {
265 return 48 + c.n_buckets * NX_CUCKOO_BUCKET_SIZE
266}
267
268func nx_cuckoo_total(c: *CuckooFilter) -> i64 {
269 return c.total
270}
271
272// Load factor in parts-per-thousand. Cuckoo filters degrade
273// gracefully up to ~95% load; beyond that, inserts start failing.
274func nx_cuckoo_load_ppt(c: *CuckooFilter) -> i64 {
275 let cap: i64 = c.n_buckets * NX_CUCKOO_BUCKET_SIZE
276 return (c.total * 1000) / cap
277}