include/punk_observe/po_chunk.h

filter: Statementstmt 97.9% 141 / 144 Branchbran 70.5% 72 / 102 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 86.5% 213 / 246 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/decode.xs ↑ Summary include/punk_observe/po_traceidx.h »
1 /* po_chunk.h - the settled part of a window, kept so it is computed once.
2 *
3 * THE PAST DOES NOT CHANGE, AND IT WAS BEING RECOMPUTED ON EVERY REFRESH.
4 *
5 * A dashboard over twenty-four hours re-scans twenty-four hours every time it
6 * loads, of which all but the last few minutes is settled data that will
7 * answer the same way for ever. Measured on a demo store, one panel of
8 * `spans | where service = "cards" | bucket(30m) count` took 3.1 seconds, and
9 * a two-panel dashboard paid it twice per refresh.
10 *
11 * WHAT MAKES SPLITTING SOUND is that a bucket is computed from the records
12 * inside it and nothing else, and bucket indices are ABSOLUTE - `t /
13 * bucket_ns`, never an offset from the query's start (po_qexec.h builds the
14 * group key that way). So the buckets two adjacent windows produce are
15 * exactly the buckets one window over both would have produced, and
16 * concatenating them is not an approximation. t/0930 asserts it against a
17 * real store rather than trusting this paragraph.
18 *
19 * THE CALLER'S ROW BUDGET TRAVELS WITH EACH CHUNK, and getting that wrong is
20 * how splitting a window turns a complete answer into a partial one. A panel
21 * asks for no ceiling because a graph that stops mid-window draws some other
22 * window and labels it with this one; when the split dropped those options
23 * and ran every chunk at the store's default, each busy hour truncated at
24 * 500,000 and the panel reported the sum of two dozen capped scans. So
25 * everything the caller passed beyond the window itself is forwarded verbatim
26 * to every chunk, and only the window is this file's to decide.
27 *
28 * A CHUNK THAT TRUNCATED IS NOT STORED. It is still the answer for this call
29 * - it is exactly what an uncached query would have said - but caching it
30 * freezes a number that is known to be short for the entry's whole life.
31 */
32 #ifndef PO_CHUNK_H
33 #define PO_CHUNK_H
34  
35 #include "punk_observe/po_compat.h"
36 #include "punk_observe/po_query.h"
37  
38 /* About an hour of work is worth reusing; much more and the settled part
39 * shrinks, much less and the entries multiply for no gain. Rounded DOWN to a
40 * whole number of buckets - a chunk that split a bucket would store each half
41 * as a count of part of it, and the chart would dip at every chunk edge. */
42 #define PO_CHUNK_TARGET_NS 3600000000000ULL
43  
44 /* Telemetry arrives late: an exporter batches, a network stalls. A bucket
45 * that has only just closed can still gain records, so caching it freezes a
46 * number that was about to change. Two minutes is past the batch intervals
47 * the SDKs default to; too small shows a wrong value, too large only costs a
48 * little more work, so it errs long. */
49 #define PO_CHUNK_LAG_NS 120000000000ULL
50  
51 44 static po_u64 po_chunk_width(po_u64 bucket_ns) {
52 po_u64 n;
53 44 ▶ if (!bucket_ns) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!bucket_ns) return 0; 0 44 44
54 44 n = PO_CHUNK_TARGET_NS / bucket_ns;
55 44 ▶ if (!n) n = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) n = 1; 1 43 44
56 44 return bucket_ns * n;
57 }
58  
59 91 static po_u64 po_chunk_floor(po_u64 t, po_u64 w) {
60 91 ▶ return w ? (t / w) * w : t;
Branch: 1 branch
BranchTrueFalseTotal
return w ? (t / w) * w : t; 91 0 91
61 }
62  
63 /* THE BUCKET WIDTH, OR ZERO WHEN THE QUERY MUST BE RUN WHOLE.
64 *
65 * A stage that ranks rows against each other cannot be split: the top five of
66 * each half is not the top five of the whole, and a sort has no meaning
67 * inside a chunk. The cross-signal stages re-key the stream against a set
68 * collected across the entire pipeline, so a chunk of one is not a chunk of
69 * the answer. Each of these turns chunking off rather than producing a
70 * plausible wrong result - the same rule the planner applies to everything
71 * else it cannot honour. */
72 60 static po_u64 po_chunk_bucket_ns(const po_query *q) {
73 const po_stage *s;
74 60 po_u64 b = 0;
75 60 ▶ if (!q) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!q) return 0; 0 60 60
76 115 ▶ for (s = q->stages; s; s = s->next) {
Branch: 1 branch
BranchTrueFalseTotal
for (s = q->stages; s; s = s->next) { 69 46 115
77 69 switch (s->kind) {
78 14 case PO_ST_LIMIT: case PO_ST_TOPN: case PO_ST_SLOWEST:
79 case PO_ST_SORT:
80 case PO_ST_EXEMPLARS: case PO_ST_TRACES:
81 case PO_ST_LOGS: case PO_ST_SPANS:
82 14 return 0;
83 53 case PO_ST_BUCKET: case PO_ST_RATE:
84 53 ▶ if (s->dur) b = s->dur;
Branch: 1 branch
BranchTrueFalseTotal
if (s->dur) b = s->dur; 53 0 53
85 53 break;
86 2 default: break;
87 }
88 }
89 46 return b;
90 }
91  
92 /* ---- the merged answer ----------------------------------------------------
93 *
94 * Chunks come back as separate results and have to become one. Held as plain
95 * arrays rather than built into Perl structures per chunk, because the merge
96 * de-duplicates and the intermediate hashes would all be thrown away.
97 */
98 typedef struct { po_u64 at; double value; po_u64 count; } po_cpt;
99  
100 typedef struct {
101 char *key;
102 size_t klen;
103 po_cpt *pt;
104 size_t n, cap;
105 } po_cser;
106  
107 typedef struct {
108 po_cser *s;
109 size_t n, cap;
110 po_u64 bucket_ns;
111 po_u64 scanned;
112 po_u64 scanned_bytes;
113 int truncated;
114 int exact;
115 int degraded;
116 } po_cres;
117  
118 147 static void po_cres_init(po_cres *r) {
119 147 memset(r, 0, sizeof(*r));
120 147 r->exact = 1;
121 147 }
122  
123 147 static void po_cres_free(po_cres *r) {
124 size_t i;
125 418 ▶ for (i = 0; i < r->n; i++) { free(r->s[i].key); free(r->s[i].pt); }
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < r->n; i++) { free(r->s[i].key); free(r->s[i].pt); } 271 147 418
126 147 free(r->s);
127 147 memset(r, 0, sizeof(*r));
128 147 }
129  
130 459 static po_cser *po_cres_series(po_cres *r, const char *key, size_t klen) {
131 size_t i;
132 688 ▶ for (i = 0; i < r->n; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < r->n; i++) 417 271 688
133 417 ▶ if (r->s[i].klen == klen
Branch: 1 branch
BranchTrueFalseTotal
if (r->s[i].klen == klen 188 229 417
134 188 ▶ && (klen == 0 || memcmp(r->s[i].key, key, klen) == 0))
Branch: 2 branches
BranchTrueFalseTotal
&& (klen == 0 || memcmp(r->s[i].key, key, klen) == 0)) 188 0 188
&& (klen == 0 || memcmp(r->s[i].key, key, klen) == 0)) 188 0 188
135 188 return &r->s[i];
136 271 ▶ if (r->n == r->cap) {
Branch: 1 branch
BranchTrueFalseTotal
if (r->n == r->cap) { 136 135 271
137 136 ▶ size_t want = r->cap ? r->cap * 2 : 8;
Branch: 1 branch
BranchTrueFalseTotal
size_t want = r->cap ? r->cap * 2 : 8; 0 136 136
138 136 po_cser *ns = (po_cser *)realloc(r->s, want * sizeof(po_cser));
139 136 ▶ if (!ns) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!ns) return NULL; 0 136 136
140 136 memset(ns + r->cap, 0, (want - r->cap) * sizeof(po_cser));
141 136 r->s = ns; r->cap = want;
142 }
143 271 r->s[r->n].key = (char *)malloc(klen + 1);
144 271 ▶ if (!r->s[r->n].key) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!r->s[r->n].key) return NULL; 0 271 271
145 271 ▶ if (klen) memcpy(r->s[r->n].key, key, klen);
Branch: 1 branch
BranchTrueFalseTotal
if (klen) memcpy(r->s[r->n].key, key, klen); 270 1 271
146 271 r->s[r->n].key[klen] = '\0';
147 271 r->s[r->n].klen = klen;
148 271 return &r->s[r->n++];
149 }
150  
151 /* ONE POINT PER (SERIES, INSTANT), the later one winning. Chunks do not
152 * overlap, so this only bites at a shared edge - but a duplicated instant
153 * would draw a spike where two chunks meet, and a spike that is an artefact
154 * of the cache is worse than no cache. */
155 941 static int po_cser_put(po_cser *s, po_u64 at, double v, po_u64 count) {
156 size_t i;
157 3811 ▶ for (i = 0; i < s->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < s->n; i++) { 2870 941 3811
158 2870 ▶ if (s->pt[i].at == at) {
Branch: 1 branch
BranchTrueFalseTotal
if (s->pt[i].at == at) { 0 2870 2870
159 0 s->pt[i].value = v;
160 0 s->pt[i].count = count;
161 0 return 1;
162 }
163 }
164 941 ▶ if (s->n == s->cap) {
Branch: 1 branch
BranchTrueFalseTotal
if (s->n == s->cap) { 271 670 941
165 271 ▶ size_t want = s->cap ? s->cap * 2 : 32;
Branch: 1 branch
BranchTrueFalseTotal
size_t want = s->cap ? s->cap * 2 : 32; 0 271 271
166 271 po_cpt *np = (po_cpt *)realloc(s->pt, want * sizeof(po_cpt));
167 271 ▶ if (!np) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!np) return 0; 0 271 271
168 271 s->pt = np; s->cap = want;
169 }
170 941 s->pt[s->n].at = at;
171 941 s->pt[s->n].value = v;
172 941 s->pt[s->n].count = count;
173 941 s->n++;
174 941 return 1;
175 }
176  
177 800 static int po_cpt_cmp(const void *a, const void *b) {
178 800 po_u64 x = ((const po_cpt *)a)->at, y = ((const po_cpt *)b)->at;
179 800 ▶ return x < y ? -1 : (x > y ? 1 : 0);
Branch: 1 branch
BranchTrueFalseTotal
return x < y ? -1 : (x > y ? 1 : 0); 0 800 800
180 }
181  
182 21 static void po_cres_sort(po_cres *r) {
183 size_t i;
184 62 ▶ for (i = 0; i < r->n; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < r->n; i++) 41 21 62
185 41 ▶ if (r->s[i].n > 1)
Branch: 1 branch
BranchTrueFalseTotal
if (r->s[i].n > 1) 40 1 41
186 40 qsort(r->s[i].pt, r->s[i].n, sizeof(po_cpt), po_cpt_cmp);
187 21 }
188  
189 /* ---- the stored form ------------------------------------------------------
190 *
191 * A BESPOKE BLOB, NOT JSON, and the reason is precision rather than speed.
192 * An instant is unsigned 64-bit and goes past 2^53, so a JSON number cannot
193 * hold one: it would come back rounded to a bucket edge that is near the
194 * right one and is not it, and every chunk boundary would drift. Fixed-width
195 * little-endian fields have no such question, and the decoder can reject a
196 * blob it does not understand instead of half-reading it.
197 *
198 * "POC2" | bucket_ns u64 | scanned u64 | scanned_bytes u64 | flags u8
199 * | nseries u32
200 * per series: klen u32, key bytes, npoints u32
201 * per point: at u64, value f64, count u64
202 *
203 * THE MAGIC IS PART OF THE UPGRADE. `POC1` entries were written by a version
204 * whose chunks ran at the store's default row ceiling rather than the
205 * caller's, so a busy chunk truncated and froze a partial count for its whole
206 * TTL. Those bytes are not worth reading, and the key namespace moved with
207 * this magic so they are never reached at all.
208 */
209 #define PO_CHUNK_MAGIC "POC2"
210 #define PO_CHUNK_F_TRUNCATED 0x01
211 #define PO_CHUNK_F_INEXACT 0x02
212 #define PO_CHUNK_F_DEGRADED 0x04
213  
214 1578 static void po_c_put64(unsigned char *p, po_u64 v) {
215 int i;
216 14202 ▶ for (i = 0; i < 8; i++) p[i] = (unsigned char)((v >> (i * 8)) & 0xFF);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 8; i++) p[i] = (unsigned char)((v >> (i * 8)) & 0xFF); 12624 1578 14202
217 1578 }
218 1318 static po_u64 po_c_get64(const unsigned char *p) {
219 1318 po_u64 v = 0; int i;
220 11862 ▶ for (i = 0; i < 8; i++) v |= ((po_u64)p[i]) << (i * 8);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 8; i++) v |= ((po_u64)p[i]) << (i * 8); 10544 1318 11862
221 1318 return v;
222 }
223 526 static void po_c_put32(unsigned char *p, uint32_t v) {
224 int i;
225 2630 ▶ for (i = 0; i < 4; i++) p[i] = (unsigned char)((v >> (i * 8)) & 0xFF);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) p[i] = (unsigned char)((v >> (i * 8)) & 0xFF); 2104 526 2630
226 526 }
227 471 static uint32_t po_c_get32(const unsigned char *p) {
228 471 uint32_t v = 0; int i;
229 2355 ▶ for (i = 0; i < 4; i++) v |= ((uint32_t)p[i]) << (i * 8);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) v |= ((uint32_t)p[i]) << (i * 8); 1884 471 2355
230 471 return v;
231 }
232  
233 114 static size_t po_chunk_size(const po_cres *r) {
234 114 size_t n = 4 + 8 + 8 + 8 + 1 + 4, i;
235 320 ▶ for (i = 0; i < r->n; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < r->n; i++) 206 114 320
236 206 n += 4 + r->s[i].klen + 4 + r->s[i].n * 24;
237 114 return n;
238 }
239  
240 114 static size_t po_chunk_encode(const po_cres *r, unsigned char *out) {
241 114 size_t o = 0, i, j;
242 114 memcpy(out, PO_CHUNK_MAGIC, 4); o += 4;
243 114 po_c_put64(out + o, r->bucket_ns); o += 8;
244 114 po_c_put64(out + o, r->scanned); o += 8;
245 114 po_c_put64(out + o, r->scanned_bytes); o += 8;
246 228 out[o++] = (unsigned char)((r->truncated ? PO_CHUNK_F_TRUNCATED : 0)
247 114 ▶ | (r->exact ? 0 : PO_CHUNK_F_INEXACT)
Branch: 2 branches
BranchTrueFalseTotal
| (r->exact ? 0 : PO_CHUNK_F_INEXACT) 0 114 114
| (r->exact ? 0 : PO_CHUNK_F_INEXACT) 114 0 114
248 114 ▶ | (r->degraded ? PO_CHUNK_F_DEGRADED : 0));
Branch: 1 branch
BranchTrueFalseTotal
| (r->degraded ? PO_CHUNK_F_DEGRADED : 0)); 0 114 114
249 114 po_c_put32(out + o, (uint32_t)r->n); o += 4;
250 320 ▶ for (i = 0; i < r->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < r->n; i++) { 206 114 320
251 206 po_c_put32(out + o, (uint32_t)r->s[i].klen); o += 4;
252 206 ▶ if (r->s[i].klen) { memcpy(out + o, r->s[i].key, r->s[i].klen);
Branch: 1 branch
BranchTrueFalseTotal
if (r->s[i].klen) { memcpy(out + o, r->s[i].key, r->s[i].klen); 206 0 206
253 206 o += r->s[i].klen; }
254 206 po_c_put32(out + o, (uint32_t)r->s[i].n); o += 4;
255 618 ▶ for (j = 0; j < r->s[i].n; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < r->s[i].n; j++) { 412 206 618
256 412 double v = r->s[i].pt[j].value;
257 po_u64 bits;
258 412 po_c_put64(out + o, r->s[i].pt[j].at); o += 8;
259 412 memcpy(&bits, &v, 8);
260 412 po_c_put64(out + o, bits); o += 8;
261 412 po_c_put64(out + o, r->s[i].pt[j].count); o += 8;
262 }
263 }
264 114 return o;
265 }
266  
267 /* WOULD THIS BE READ AT ALL. The question a warmer asks, which is not the
268 * question a reader asks: it wants to know whether an entry is worth leaving
269 * alone, not what is in it, and building a result per chunk to find out would
270 * be most of the cost of not having needed to. A blob that passes here and
271 * fails the full decode later is deleted by the read path. */
272 21 static int po_chunk_valid(const unsigned char *b, size_t len) {
273 21 ▶ if (!b || len < 4 + 8 + 8 + 8 + 1 + 4) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!b || len < 4 + 8 + 8 + 8 + 1 + 4) return 0; 21 0 21
if (!b || len < 4 + 8 + 8 + 8 + 1 + 4) return 0; 0 21 21
274 21 return memcmp(b, PO_CHUNK_MAGIC, 4) == 0;
275 }
276  
277 /* Merges a stored blob INTO an accumulating result. Every length is checked
278 * against what is left rather than trusted: the bytes come back from a cache
279 * on disk, which is somewhere a truncated write or a stale format can leave
280 * something that is not what was written. A blob that does not add up is
281 * refused whole, and the caller recomputes the chunk. */
282 96 static int po_chunk_decode(po_cres *r, const unsigned char *b, size_t len) {
283 96 size_t o = 0, i, j;
284 uint32_t ns;
285 unsigned char flags;
286  
287 96 ▶ if (len < 4 + 8 + 8 + 8 + 1 + 4) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (len < 4 + 8 + 8 + 8 + 1 + 4) return 0; 0 96 96
288 96 ▶ if (memcmp(b, PO_CHUNK_MAGIC, 4) != 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (memcmp(b, PO_CHUNK_MAGIC, 4) != 0) return 0; 1 95 96
289 95 o = 4;
290 95 ▶ if (!r->bucket_ns) r->bucket_ns = po_c_get64(b + o);
Branch: 1 branch
BranchTrueFalseTotal
if (!r->bucket_ns) r->bucket_ns = po_c_get64(b + o); 0 95 95
291 95 o += 8;
292 95 r->scanned += po_c_get64(b + o); o += 8;
293 95 r->scanned_bytes += po_c_get64(b + o); o += 8;
294 95 flags = b[o++];
295 95 ▶ if (flags & PO_CHUNK_F_TRUNCATED) r->truncated = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (flags & PO_CHUNK_F_TRUNCATED) r->truncated = 1; 0 95 95
296 95 ▶ if (flags & PO_CHUNK_F_INEXACT) r->exact = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (flags & PO_CHUNK_F_INEXACT) r->exact = 0; 0 95 95
297 95 ▶ if (flags & PO_CHUNK_F_DEGRADED) r->degraded = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (flags & PO_CHUNK_F_DEGRADED) r->degraded = 1; 0 95 95
298 95 ns = po_c_get32(b + o); o += 4;
299  
300 283 ▶ for (i = 0; i < ns; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < ns; i++) { 188 95 283
301 uint32_t klen, np;
302 po_cser *s;
303 188 ▶ if (o + 4 > len) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (o + 4 > len) return 0; 0 188 188
304 188 klen = po_c_get32(b + o); o += 4;
305 188 ▶ if (klen > len || o + klen + 4 > len) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (klen > len || o + klen + 4 > len) return 0; 188 0 188
if (klen > len || o + klen + 4 > len) return 0; 0 188 188
306 188 s = po_cres_series(r, (const char *)(b + o), klen);
307 188 ▶ if (!s) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!s) return 0; 0 188 188
308 188 o += klen;
309 188 np = po_c_get32(b + o); o += 4;
310 188 ▶ if (np > (len - o) / 24) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (np > (len - o) / 24) return 0; 0 188 188
311 564 ▶ for (j = 0; j < np; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < np; j++) { 376 188 564
312 376 po_u64 at = po_c_get64(b + o);
313 376 po_u64 bits = po_c_get64(b + o + 8);
314 376 po_u64 cnt = po_c_get64(b + o + 16);
315 double v;
316 376 memcpy(&v, &bits, 8);
317 376 o += 24;
318 376 ▶ if (!po_cser_put(s, at, v, cnt)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!po_cser_put(s, at, v, cnt)) return 0; 0 376 376
319 }
320 }
321 95 return 1;
322 }
323  
324 #endif /* PO_CHUNK_H */
« xs/decode.xs ↑ Summary include/punk_observe/po_traceidx.h »