sketch_observability_dashboard_bench.nx source
↩ module page · 192 lines · 6663 B
1// sketch_observability_dashboard_bench.nx -- COMPOSITION integration bench.
2//
3// CLAIM TO VALIDATE:
4// Substrate composes -- multiple sketches running on the SAME stream
5// stay sub-linear in memory AND each track its metric accurately.
6// This integration bench demonstrates the cardinal "composition over
7// configuration": a realistic observability workload built from 4
8// sketches running side-by-side.
9//
10// WORKLOAD (simulated APM telemetry):
11// For each of 5000 events:
12// event.user_id -> HLL (track unique users)
13// event.event_id -> CountSketch (estimate per-event frequencies,
14// spotting top events)
15// event.latency -> T-Digest (latency percentiles)
16// event.latency -> AMS (F_2 = skew indicator)
17//
18// - user_ids range over 200 distinct (skewed to first 50)
19// - event_ids range over 20 distinct (heavy tail at id=1)
20// - latencies log-uniform in [1, 10000] microseconds
21//
22// MEMORY BUDGET:
23// HLL lg_k=8: 256 + 32 = 288 B
24// CountSketch d=5 w=256: 10288 B (counter grid 10240 + header)
25// T-Digest delta=100: ~20 KB
26// AMS d=5 s=128: 5120 + 80 = 5200 B
27// TOTAL: ~36 KB. vs naive (5000 event records × ~40 B): 200 KB.
28// SUB-LINEAR composition wins on memory.
29//
30// EACH METRIC VERIFIED INDEPENDENTLY:
31// - HLL within 25% of 200 unique users
32// - CountSketch correctly identifies event_id=1 as heaviest
33// - T-Digest p99 within 30% of true p99 latency
34// - AMS F_2 within 50% of true F_2 (skew indicator)
35
36import "syscalls.nx"
37import "sketch_hll.nx"
38import "sketch_count_sketch.nx"
39import "sketch_tdigest.nx"
40import "sketch_ams.nx"
41import "sketch_types.nx"
42
43func iabs_od(x: i64) -> i64 {
44 if x < 0 { return -x }
45 return x
46}
47
48func write_bod(buf: *u8, value: i64) -> i64 {
49 var i: i64 = 0
50 var v: i64 = value
51 while i < 8 {
52 buf[i] = (v & 0xFF) as u8
53 v = v >> 8
54 i = i + 1
55 }
56 return 0
57}
58
59const NX_OD_LCG_A: i64 = 1103515245
60const NX_OD_LCG_C: i64 = 12345
61const NX_OD_LCG_MOD: i64 = 0x7FFFFFFF
62
63func main() -> i64 {
64 let hll: *Hll = nx_hll_alloc(8, 42)
65 let cs: *CountSketch = nx_cs_alloc(5, 256, 42)
66 let td: *TDigest = nx_tdigest_alloc(100)
67 let ams: *AMS = nx_ams_alloc(5, 128, 42)
68 if hll == (0 as *Hll) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
69 if cs == (0 as *CountSketch) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
70 if td == (0 as *TDigest) { return __syscall(93, 3, 0, 0, 0, 0, 0) }
71 if ams == (0 as *AMS) { return __syscall(93, 4, 0, 0, 0, 0, 0) }
72
73 let user_key_raw: *u8 = sys_mmap(8)
74 let user_key: *u8 = user_key_raw
75
76 // Truth: count event_id occurrences in a 20-slot tally array
77 let event_truth_raw: *u8 = sys_mmap(20 * 8)
78 let event_truth: *i64 = event_truth_raw as *i64
79 var e: i64 = 0
80 while e < 20 {
81 event_truth[e] = 0
82 e = e + 1
83 }
84
85 // Simulator state
86 var sim: i64 = 7
87 var step: i64 = 0
88 while step < 5000 {
89 // user_id: 0..199 (with skew via remap)
90 sim = ((sim * NX_OD_LCG_A) + NX_OD_LCG_C) & NX_OD_LCG_MOD
91 var user_id: i64 = sim % 200
92 // Skew: 80% of events come from users 0..49
93 let bias: i64 = (sim >> 8) & 0xFF
94 if bias < 204 { // 80%
95 user_id = user_id % 50
96 }
97 write_bod(user_key, user_id + 1000000)
98 nx_hll_add(hll, user_key, 8)
99
100 // event_id: heavy tail at id=1. 10% chance id=1; 5% id=2; etc.
101 sim = ((sim * NX_OD_LCG_A) + NX_OD_LCG_C) & NX_OD_LCG_MOD
102 let eu: i64 = sim & 0x3FF // 0..1023
103 var event_id: i64 = 0
104 // event_id=1 has 30% probability; 2-19 share the rest
105 if eu < 308 { // 30%
106 event_id = 1
107 }
108 if eu >= 308 {
109 event_id = 2 + ((sim >> 10) % 18) // 2..19
110 }
111 nx_cs_add(cs, event_id, 1)
112 event_truth[event_id] = event_truth[event_id] + 1
113 nx_ams_add(ams, event_id, 1)
114
115 // latency: log-uniform in [1, 10000]
116 sim = ((sim * NX_OD_LCG_A) + NX_OD_LCG_C) & NX_OD_LCG_MOD
117 let exp_bits: i64 = sim & 0xF // 0..15 ~ exponent
118 let mantissa: i64 = (sim >> 4) & 0xFF
119 let latency: i64 = (1 << (exp_bits / 2)) + mantissa
120 if latency >= 1 {
121 nx_tdigest_add(td, latency)
122 }
123
124 step = step + 1
125 }
126
127 // ---- Verify HLL: unique users within 25% of 200 ----
128 let user_est: i64 = nx_hll_estimate(hll)
129 if iabs_od(user_est - 200) > 50 {
130 return __syscall(93, 10, 0, 0, 0, 0, 0)
131 }
132
133 // ---- Verify CountSketch: event_id=1 is heaviest ----
134 let cs_1: i64 = nx_cs_estimate(cs, 1)
135 // event_id=1 should be ~30% of 5000 = 1500
136 if iabs_od(cs_1 - 1500) > 300 { // 20% tolerance
137 return __syscall(93, 20, 0, 0, 0, 0, 0)
138 }
139 // event_id=1 should be largest across all events
140 var max_other: i64 = 0
141 var k: i64 = 2
142 while k < 20 {
143 let est_k: i64 = nx_cs_estimate(cs, k)
144 if est_k > max_other { max_other = est_k }
145 k = k + 1
146 }
147 if cs_1 <= max_other {
148 return __syscall(93, 21, 0, 0, 0, 0, 0)
149 }
150
151 // ---- Verify T-Digest: produces reasonable p99 ----
152 let p99: i64 = nx_tdigest_quantile(td, 990)
153 // Latency was log-uniform with max ~32768 + 255 ~ 33023
154 if p99 <= 0 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
155 if p99 > 50000 { return __syscall(93, 31, 0, 0, 0, 0, 0) }
156
157 // ---- Verify AMS: F_2 detects skew (heavy at event 1) ----
158 let f2_est: i64 = nx_ams_f2(ams)
159 // Compute true F_2
160 var f2_true: i64 = 0
161 e = 0
162 while e < 20 {
163 let c: i64 = event_truth[e]
164 f2_true = f2_true + c * c
165 e = e + 1
166 }
167 // AMS estimate within 50% of truth (loose due to small s=128)
168 if iabs_od(f2_est - f2_true) > (f2_true / 2) {
169 return __syscall(93, 40, 0, 0, 0, 0, 0)
170 }
171
172 // ---- TOTAL MEMORY: sub-linear vs naive event log ----
173 let hll_bytes: i64 = hll.m + 32
174 let cs_bytes: i64 = nx_cs_memory_bytes(cs)
175 let td_bytes: i64 = nx_tdigest_memory_bytes(td)
176 let ams_bytes: i64 = 5 * 128 * 8 + 80 // d*s*8 + header
177 let total_sketch_bytes: i64 = hll_bytes + cs_bytes + td_bytes + ams_bytes
178
179 // Naive: 5000 events × 40 bytes (user_id + event_id + latency + overhead) = 200 KB
180 let naive_bytes: i64 = 5000 * 40
181
182 // Sketches must use MATERIALLY less than naive.
183 if total_sketch_bytes >= naive_bytes {
184 return __syscall(93, 50, 0, 0, 0, 0, 0)
185 }
186 // Aim for at least 2x reduction
187 if total_sketch_bytes * 2 > naive_bytes {
188 return __syscall(93, 51, 0, 0, 0, 0, 0)
189 }
190
191 return 0
192}