nx_sketch_cuckoo.nx source
↩ module page · 283 lines · 9662 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
32// nx_safety_envelope:
33// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
34// sil_target: SIL1
35// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
36// verdict: NOT_YET_EVALUATED
37
38import "nx_syscalls.nx"
39import "nx_sketch_types.nx"
40
41const NX_CUCKOO_BUCKET_SIZE: i64 = 4
42const NX_CUCKOO_FP_BITS: i64 = 8
43const NX_CUCKOO_MAX_KICKS: i64 = 500
44const NX_CUCKOO_EMPTY: i64 = 0 // fingerprint 0 = slot empty
45
46// LCG constants for random eviction selection.
47const NX_CUCKOO_LCG_A: i64 = 1103515245
48const NX_CUCKOO_LCG_C: i64 = 12345
49const NX_CUCKOO_LCG_MOD: i64 = 0x7FFFFFFF
50
51struct CuckooFilter {
52 buckets: *u8, // n_buckets * 4 bytes
53 n_buckets: i64, // power of 2
54 mask: i64, // n_buckets - 1
55 total: i64, // items currently stored
56 rng_state: i64,
57}
58
59// === fingerprint derivation =====================================
60//
61// Fingerprint is the low 8 bits of the item hash, but adjusted so
62// it's never 0 (0 is the empty sentinel). Caller passes a 64-bit
63// hash; we mix and mask.
64
65func nx_cuckoo_fingerprint(hash: i64) -> i64 {
66 let fp: i64 = hash & 0xFF
67 if fp == 0 { return 1 } // remap 0 -> 1 (never empty sentinel)
68 return fp
69}
70
71// === bucket index derivation ====================================
72//
73// Two candidate buckets per item:
74// b1 = (hash >> 8) & mask
75// b2 = b1 XOR (hash_of_fingerprint & mask)
76// Symmetric: given any one of {b1, b2}, can derive the other
77// without storing the original hash.
78
79func nx_cuckoo_bucket1(c: *CuckooFilter, hash: i64) -> i64 {
80 return (hash >> 8) & c.mask
81}
82
83// Hash the fingerprint via a small mixing function to spread it.
84func nx_cuckoo_fp_hash(fp: i64) -> i64 {
85 let h: i64 = (fp * 0x9E3779B97F4A7C15) & 0xFFFFFFFFFFFFFFFF
86 return h
87}
88
89func nx_cuckoo_bucket2(c: *CuckooFilter, b1: i64, fp: i64) -> i64 {
90 let fph: i64 = nx_cuckoo_fp_hash(fp)
91 return (b1 ^ fph) & c.mask
92}
93
94// === construction ===============================================
95//
96// n_buckets must be a power of 2 and >= 4.
97
98func nx_cuckoo_alloc(n_buckets: i64, seed: i64) -> *CuckooFilter {
99 if n_buckets < 4 { return 0 as *CuckooFilter }
100 if (n_buckets & (n_buckets - 1)) != 0 {
101 // not power of 2
102 return 0 as *CuckooFilter
103 }
104 let raw: *u8 = sys_mmap(48)
105 let c: *CuckooFilter = raw as *CuckooFilter
106 c.n_buckets = n_buckets
107 c.mask = n_buckets - 1
108 let bytes: i64 = n_buckets * NX_CUCKOO_BUCKET_SIZE
109 c.buckets = sys_mmap(bytes)
110 var i: i64 = 0
111 while i < bytes {
112 c.buckets[i] = 0
113 i = i + 1
114 }
115 c.total = 0
116 c.rng_state = seed | 1
117 return c
118}
119
120func nx_cuckoo_rng_next(c: *CuckooFilter) -> i64 {
121 let next: i64 = ((c.rng_state * NX_CUCKOO_LCG_A) + NX_CUCKOO_LCG_C) & NX_CUCKOO_LCG_MOD
122 c.rng_state = next
123 return next
124}
125
126// === bucket helpers =============================================
127
128func nx_cuckoo_bucket_addr(c: *CuckooFilter, b: i64) -> *u8 {
129 return (c.buckets as i64 + b * NX_CUCKOO_BUCKET_SIZE) as *u8
130}
131
132func nx_cuckoo_try_insert_bucket(c: *CuckooFilter, b: i64, fp: i64) -> i64 {
133 // Returns 1 if there was an empty slot and we filled it; 0 else.
134 let buf: *u8 = nx_cuckoo_bucket_addr(c, b)
135 var i: i64 = 0
136 while i < NX_CUCKOO_BUCKET_SIZE {
137 if buf[i] == NX_CUCKOO_EMPTY {
138 buf[i] = fp
139 return 1
140 }
141 i = i + 1
142 }
143 return 0
144}
145
146func nx_cuckoo_bucket_contains(c: *CuckooFilter, b: i64, fp: i64) -> i64 {
147 let buf: *u8 = nx_cuckoo_bucket_addr(c, b)
148 var i: i64 = 0
149 while i < NX_CUCKOO_BUCKET_SIZE {
150 if buf[i] == fp { return 1 }
151 i = i + 1
152 }
153 return 0
154}
155
156func nx_cuckoo_bucket_remove(c: *CuckooFilter, b: i64, fp: i64) -> i64 {
157 let buf: *u8 = nx_cuckoo_bucket_addr(c, b)
158 var i: i64 = 0
159 while i < NX_CUCKOO_BUCKET_SIZE {
160 if buf[i] == fp {
161 buf[i] = NX_CUCKOO_EMPTY
162 return 1
163 }
164 i = i + 1
165 }
166 return 0
167}
168
169// === insert (with random eviction) ==============================
170//
171// Try bucket1 then bucket2; if both full, evict a random
172// fingerprint from one of them and relocate it to its alternate.
173// Bounded by NX_CUCKOO_MAX_KICKS retries; on failure, the filter
174// is considered full.
175
176func nx_cuckoo_insert(c: *CuckooFilter, hash: i64) -> i64 {
177 let fp: i64 = nx_cuckoo_fingerprint(hash)
178 let b1: i64 = nx_cuckoo_bucket1(c, hash)
179 if nx_cuckoo_try_insert_bucket(c, b1, fp) == 1 {
180 c.total = c.total + 1
181 return 1
182 }
183 let b2: i64 = nx_cuckoo_bucket2(c, b1, fp)
184 if nx_cuckoo_try_insert_bucket(c, b2, fp) == 1 {
185 c.total = c.total + 1
186 return 1
187 }
188 // Both buckets full -- kick.
189 var cur_b: i64 = b1
190 if (nx_cuckoo_rng_next(c) & 1) == 1 { cur_b = b2 }
191 var cur_fp: i64 = fp
192 var kick: i64 = 0
193 while kick < NX_CUCKOO_MAX_KICKS {
194 let buf: *u8 = nx_cuckoo_bucket_addr(c, cur_b)
195 // Pick random slot in this bucket, swap.
196 let slot: i64 = nx_cuckoo_rng_next(c) & (NX_CUCKOO_BUCKET_SIZE - 1)
197 let evicted: i64 = buf[slot]
198 buf[slot] = cur_fp
199 cur_fp = evicted
200 // Move evicted to its alternate bucket.
201 cur_b = nx_cuckoo_bucket2(c, cur_b, cur_fp)
202 if nx_cuckoo_try_insert_bucket(c, cur_b, cur_fp) == 1 {
203 c.total = c.total + 1
204 return 1
205 }
206 kick = kick + 1
207 }
208 // Failed -- filter is too full. Last evicted fingerprint is
209 // lost (the original item, however, is still represented by
210 // whatever slot we wrote during the kick chain).
211 return 0
212}
213
214// === contains ====================================================
215
216func nx_cuckoo_contains(c: *CuckooFilter, hash: i64) -> i64 {
217 let fp: i64 = nx_cuckoo_fingerprint(hash)
218 let b1: i64 = nx_cuckoo_bucket1(c, hash)
219 if nx_cuckoo_bucket_contains(c, b1, fp) == 1 { return 1 }
220 let b2: i64 = nx_cuckoo_bucket2(c, b1, fp)
221 return nx_cuckoo_bucket_contains(c, b2, fp)
222}
223
224// === delete ======================================================
225//
226// Cuckoo filter supports DELETE -- the headline capability Bloom
227// lacks. Find the fingerprint in either bucket, clear it.
228// Returns 1 if removed, 0 if not present. Caveat: if the same
229// item was inserted twice, only one copy is removed.
230
231func nx_cuckoo_delete(c: *CuckooFilter, hash: i64) -> i64 {
232 let fp: i64 = nx_cuckoo_fingerprint(hash)
233 let b1: i64 = nx_cuckoo_bucket1(c, hash)
234 if nx_cuckoo_bucket_remove(c, b1, fp) == 1 {
235 c.total = c.total - 1
236 return 1
237 }
238 let b2: i64 = nx_cuckoo_bucket2(c, b1, fp)
239 if nx_cuckoo_bucket_remove(c, b2, fp) == 1 {
240 c.total = c.total - 1
241 return 1
242 }
243 return 0
244}
245
246// === error bound + query =========================================
247//
248// False-positive rate: ~ 2 * bucket_size / 2^fp_bits = 2*4/256 = 3.1%
249// at any load. Tighter than naive Bloom at the same memory for
250// most workloads.
251// confidence = 1 - FPR.
252
253func nx_cuckoo_fpr_ppb() -> i64 {
254 return 31000000 // 3.1%
255}
256
257func nx_cuckoo_query(c: *CuckooFilter, hash: i64) -> *ApproxI64 {
258 let present: i64 = nx_cuckoo_contains(c, hash)
259 // Envelope for membership: absent is exact (0), present has
260 // bounded-uncertain (might be a false positive).
261 // We declare conf as 1 - FPR so callers see the true reliability.
262 return nx_approx_new(present, NX_ENV_ABS, 0,
263 1000000000 - nx_cuckoo_fpr_ppb(),
264 NX_MATURITY_REFERENCE_IMPL,
265 NX_ADV_HONEST)
266}
267
268// === memory + load introspection =================================
269
270func nx_cuckoo_memory_bytes(c: *CuckooFilter) -> i64 {
271 return 48 + c.n_buckets * NX_CUCKOO_BUCKET_SIZE
272}
273
274func nx_cuckoo_total(c: *CuckooFilter) -> i64 {
275 return c.total
276}
277
278// Load factor in parts-per-thousand. Cuckoo filters degrade
279// gracefully up to ~95% load; beyond that, inserts start failing.
280func nx_cuckoo_load_ppt(c: *CuckooFilter) -> i64 {
281 let cap: i64 = c.n_buckets * NX_CUCKOO_BUCKET_SIZE
282 return (c.total * 1000) / cap
283}