| 1 |
|
| /* po_result.h - one result shape, and metadata that is never optional. |
| 2 |
|
| * |
| 3 |
|
| * A TRUNCATED RESULT THAT LOOKS COMPLETE IS THE OBSERVABILITY EQUIVALENT OF A |
| 4 |
|
| * GREEN DASHBOARD OVER DROPPED SPANS. |
| 5 |
|
| * |
| 6 |
|
| * That is the failure this project exists to stop people having, so every |
| 7 |
|
| * result carries how much it scanned, whether a budget cut it short, and - |
| 8 |
|
| * for a percentile - whether the number is exact or estimated. A percentile |
| 9 |
|
| * whose method is unknown is a number nobody can act on. |
| 10 |
|
| */ |
| 11 |
|
| #ifndef PO_RESULT_H |
| 12 |
|
| #define PO_RESULT_H |
| 13 |
|
| |
| 14 |
|
| #include "punk_observe/po_compat.h" |
| 15 |
|
| #include "punk_observe/po_row.h" |
| 16 |
|
| |
| 17 |
|
| #define PO_RES_ROWS 1 /* individual rows: logs, spans, traces */ |
| 18 |
|
| #define PO_RES_SERIES 2 /* grouped aggregates */ |
| 19 |
|
| #define PO_RES_SCALAR 3 /* one number */ |
| 20 |
|
| |
| 21 |
|
| typedef struct { |
| 22 |
|
| char key[128]; /* the group key, or empty for a scalar */ |
| 23 |
|
| size_t key_len; |
| 24 |
|
| double value; |
| 25 |
|
| po_u64 count; |
| 26 |
|
| /* for percentiles and averages the accumulator needs the samples */ |
| 27 |
|
| double *samples; |
| 28 |
|
| uint32_t nsamp, csamp; |
| 29 |
|
| } po_group; |
| 30 |
|
| |
| 31 |
|
| typedef struct { |
| 32 |
|
| int shape; |
| 33 |
|
| po_group *g; |
| 34 |
|
| uint32_t ng, cg; |
| 35 |
|
| |
| 36 |
|
| po_row *row; /* PO_RES_ROWS */ |
| 37 |
|
| uint32_t nrow, crow; |
| 38 |
|
| |
| 39 |
|
| /* The bucket width a `bucket(1m)` query asked for, carried out to the |
| 40 |
|
| * caller so a renderer knows the groups are a time series rather than a |
| 41 |
|
| * set of labels - and how wide each point is. Zero when the query did not |
| 42 |
|
| * bucket. */ |
| 43 |
|
| po_u64 bucket_ns; |
| 44 |
|
| |
| 45 |
|
| /* meta - ALWAYS populated */ |
| 46 |
|
| po_u64 scanned_rows; |
| 47 |
|
| po_u64 scanned_bytes; |
| 48 |
|
| po_u64 blocks; |
| 49 |
|
| po_u64 blocks_skipped; |
| 50 |
|
| int truncated; /* a budget cut the scan short */ |
| 51 |
|
| int degraded; /* something was approximated */ |
| 52 |
|
| int exact; /* percentile method: 1 exact, 0 estimated */ |
| 53 |
|
| int steps; /* how many times the executor yielded */ |
| 54 |
|
| |
| 55 |
|
| /* Too many distinct groups to answer. NOT a truncation: a bucketed chart |
| 56 |
|
| * missing its tail looks like a service that stopped reporting, so this |
| 57 |
|
| * is refused with advice instead of served short. */ |
| 58 |
|
| int too_many_groups; |
| 59 |
|
| |
| 60 |
|
| /* THE EXEMPLAR IDS OF EVERY ROW THAT SURVIVED THE FILTERS, collected only |
| 61 |
|
| * when the query asked to re-key on them. |
| 62 |
|
| * |
| 63 |
|
| * An aggregate CONSUMES its rows: after `| bucket(5m) p99` there are |
| 64 |
|
| * buckets and no rows at all, so a cross-signal jump reading the result's |
| 65 |
|
| * rows finds nothing and joins to nothing - which is what the flagship |
| 66 |
|
| * expression did on its first run, silently and with `ok` true. The ids |
| 67 |
|
| * are therefore taken where a row passes the filters, before whatever |
| 68 |
|
| * happens to the row itself. |
| 69 |
|
| * |
| 70 |
|
| * `| exemplars` after an aggregate means "the traces behind the points |
| 71 |
|
| * this pipeline selected", which is the question somebody bucketing to a |
| 72 |
|
| * p99 is asking. It is not "the trace AT the p99" - that would need the |
| 73 |
|
| * percentile's own sample to carry an id, and claiming it without that |
| 74 |
|
| * would be a precise-sounding wrong answer. */ |
| 75 |
|
| po_u64 *ex_hi, *ex_lo; |
| 76 |
|
| uint32_t nex, cap_ex; |
| 77 |
|
| int ex_overflow; /* past the cap; the caller refuses */ |
| 78 |
|
| } po_result; |
| 79 |
|
| |
| 80 |
|
| /* The same ceiling po_traceset enforces, named once here so the executor can |
| 81 |
|
| * stop collecting rather than growing without bound. */ |
| 82 |
|
| #define PO_MAX_EXEMPLARS 4096 |
| 83 |
|
| |
| 84 |
4217 |
| static int po_result_exemplar(po_result *r, po_u64 hi, po_u64 lo) { |
| 85 |
4217 |
▶ | if (!hi && !lo) return 1; /* no id: nothing to join to */ |
Branch: 2 branches
| Branch | True | False | Total |
| if (!hi && !lo) return 1; /* no id: nothing to join to */ |
7 |
4210 |
4217 |
| if (!hi && !lo) return 1; /* no id: nothing to join to */ |
7 |
0 |
7 |
|
| 86 |
4210 |
▶ | if (r->nex >= PO_MAX_EXEMPLARS) { r->ex_overflow = 1; return 1; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (r->nex >= PO_MAX_EXEMPLARS) { r->ex_overflow = 1; return 1; } |
104 |
4106 |
4210 |
|
| 87 |
4106 |
▶ | if (r->nex == r->cap_ex) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (r->nex == r->cap_ex) { |
12 |
4094 |
4106 |
|
| 88 |
12 |
▶ | uint32_t want = r->cap_ex ? r->cap_ex * 2 : 64; |
Branch: 1 branch
| Branch | True | False | Total |
| uint32_t want = r->cap_ex ? r->cap_ex * 2 : 64; |
6 |
6 |
12 |
|
| 89 |
12 |
| po_u64 *nh = (po_u64 *)realloc(r->ex_hi, want * sizeof(po_u64)); |
| 90 |
12 |
| po_u64 *nl = (po_u64 *)realloc(r->ex_lo, want * sizeof(po_u64)); |
| 91 |
12 |
▶ | if (nh) r->ex_hi = nh; |
Branch: 1 branch
| Branch | True | False | Total |
| if (nh) r->ex_hi = nh; |
12 |
0 |
12 |
|
| 92 |
12 |
▶ | if (nl) r->ex_lo = nl; |
Branch: 1 branch
| Branch | True | False | Total |
| if (nl) r->ex_lo = nl; |
12 |
0 |
12 |
|
| 93 |
12 |
▶ | if (!nh || !nl) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (!nh || !nl) return 0; |
12 |
0 |
12 |
| if (!nh || !nl) return 0; |
0 |
12 |
12 |
|
| 94 |
12 |
| r->cap_ex = want; |
| 95 |
|
| } |
| 96 |
4106 |
| r->ex_hi[r->nex] = hi; |
| 97 |
4106 |
| r->ex_lo[r->nex] = lo; |
| 98 |
4106 |
| r->nex++; |
| 99 |
4106 |
| return 1; |
| 100 |
|
| } |
| 101 |
|
| |
| 102 |
|
| /* The ceiling on distinct groups. |
| 103 |
|
| * |
| 104 |
|
| * Two reasons, and the second is the load-bearing one. No chart can show more |
| 105 |
|
| * than a couple of thousand points, so a result past this is not something |
| 106 |
|
| * anybody can read - and po_result_group looks its key up by walking every |
| 107 |
|
| * group it has, so the cost of getting here is quadratic. `bucket(1ns)` over |
| 108 |
|
| * an hour is three and a half trillion groups, which is not a slow query, it |
| 109 |
|
| * is a hung worker. */ |
| 110 |
|
| #define PO_MAX_GROUPS 10000 |
| 111 |
|
| |
| 112 |
1118 |
| static void po_result_init(po_result *r) { |
| 113 |
1118 |
| memset(r, 0, sizeof(*r)); |
| 114 |
1118 |
| r->exact = 1; |
| 115 |
1118 |
| } |
| 116 |
|
| |
| 117 |
1118 |
| static void po_result_free(po_result *r) { |
| 118 |
|
| uint32_t i; |
| 119 |
12755 |
▶ | for (i = 0; i < r->ng; i++) free(r->g[i].samples); |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < r->ng; i++) free(r->g[i].samples); |
11637 |
1118 |
12755 |
|
| 120 |
1118 |
| free(r->ex_hi); free(r->ex_lo); |
| 121 |
1118 |
| free(r->g); free(r->row); |
| 122 |
1118 |
| r->g = NULL; r->row = NULL; r->ng = r->nrow = 0; |
| 123 |
1118 |
| } |
| 124 |
|
| |
| 125 |
64467 |
| static po_group *po_result_group(po_result *r, const char *key, size_t len) { |
| 126 |
|
| uint32_t i; |
| 127 |
64467 |
▶ | if (len > sizeof(r->g[0].key)) len = sizeof(r->g[0].key); |
Branch: 1 branch
| Branch | True | False | Total |
| if (len > sizeof(r->g[0].key)) len = sizeof(r->g[0].key); |
0 |
64467 |
64467 |
|
| 128 |
50226202 |
▶ | for (i = 0; i < r->ng; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < r->ng; i++) |
50214558 |
11644 |
50226202 |
|
| 129 |
50214558 |
▶ | if (r->g[i].key_len == len && |
Branch: 2 branches
| Branch | True | False | Total |
| if (r->g[i].key_len == len && |
50163533 |
51025 |
50214558 |
| if (r->g[i].key_len == len && |
50162330 |
1203 |
50163533 |
|
| 130 |
50163533 |
▶ | (len == 0 || memcmp(r->g[i].key, key, len) == 0)) return &r->g[i]; |
Branch: 1 branch
| Branch | True | False | Total |
| (len == 0 || memcmp(r->g[i].key, key, len) == 0)) return &r->g[i]; |
51620 |
50110710 |
50162330 |
|
| 131 |
11644 |
▶ | if (r->ng == r->cg) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (r->ng == r->cg) { |
356 |
11288 |
11644 |
|
| 132 |
356 |
▶ | uint32_t want = r->cg ? r->cg * 2 : 8; |
Branch: 1 branch
| Branch | True | False | Total |
| uint32_t want = r->cg ? r->cg * 2 : 8; |
74 |
282 |
356 |
|
| 133 |
356 |
| po_group *ng = (po_group *)realloc(r->g, want * sizeof(po_group)); |
| 134 |
356 |
▶ | if (!ng) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!ng) return NULL; |
0 |
356 |
356 |
|
| 135 |
356 |
| memset(ng + r->cg, 0, (want - r->cg) * sizeof(po_group)); |
| 136 |
356 |
| r->g = ng; r->cg = want; |
| 137 |
|
| } |
| 138 |
11644 |
▶ | if (len) memcpy(r->g[r->ng].key, key, len); |
Branch: 1 branch
| Branch | True | False | Total |
| if (len) memcpy(r->g[r->ng].key, key, len); |
11629 |
15 |
11644 |
|
| 139 |
11644 |
| r->g[r->ng].key_len = len; |
| 140 |
11644 |
| return &r->g[r->ng++]; |
| 141 |
|
| } |
| 142 |
|
| |
| 143 |
4264 |
| static int po_group_sample(po_group *g, double v) { |
| 144 |
4264 |
▶ | if (g->nsamp == g->csamp) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (g->nsamp == g->csamp) { |
444 |
3820 |
4264 |
|
| 145 |
444 |
▶ | uint32_t want = g->csamp ? g->csamp * 2 : 16; |
Branch: 1 branch
| Branch | True | False | Total |
| uint32_t want = g->csamp ? g->csamp * 2 : 16; |
75 |
369 |
444 |
|
| 146 |
444 |
| double *ns = (double *)realloc(g->samples, want * sizeof(double)); |
| 147 |
444 |
▶ | if (!ns) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!ns) return 0; |
0 |
444 |
444 |
|
| 148 |
444 |
| g->samples = ns; g->csamp = want; |
| 149 |
|
| } |
| 150 |
4264 |
| g->samples[g->nsamp++] = v; |
| 151 |
4264 |
| return 1; |
| 152 |
|
| } |
| 153 |
|
| |
| 154 |
15276 |
| static int po_result_row(po_result *r, const po_row *src) { |
| 155 |
15276 |
▶ | if (r->nrow == r->crow) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (r->nrow == r->crow) { |
232 |
15044 |
15276 |
|
| 156 |
232 |
▶ | uint32_t want = r->crow ? r->crow * 2 : 32; |
Branch: 1 branch
| Branch | True | False | Total |
| uint32_t want = r->crow ? r->crow * 2 : 32; |
91 |
141 |
232 |
|
| 157 |
232 |
| po_row *nr = (po_row *)realloc(r->row, want * sizeof(po_row)); |
| 158 |
232 |
▶ | if (!nr) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!nr) return 0; |
0 |
232 |
232 |
|
| 159 |
232 |
| r->row = nr; r->crow = want; |
| 160 |
|
| } |
| 161 |
15276 |
| r->row[r->nrow++] = *src; |
| 162 |
15276 |
| return 1; |
| 163 |
|
| } |
| 164 |
|
| |
| 165 |
11613 |
| static int po_dcmp(const void *a, const void *b) { |
| 166 |
11613 |
| double x = *(const double *)a, y = *(const double *)b; |
| 167 |
11613 |
▶ | return x < y ? -1 : (x > y ? 1 : 0); |
Branch: 1 branch
| Branch | True | False | Total |
| return x < y ? -1 : (x > y ? 1 : 0); |
11496 |
117 |
11613 |
|
| 168 |
|
| } |
| 169 |
|
| |
| 170 |
|
| /* PERCENTILES: EXACT BELOW A THRESHOLD, ESTIMATED ABOVE, AND THE RESULT SAYS |
| 171 |
|
| * WHICH. |
| 172 |
|
| * |
| 173 |
|
| * Sorting a hundred thousand samples to answer a p99 is affordable; sorting a |
| 174 |
|
| * hundred million is not. Above the threshold the samples are decimated, and |
| 175 |
|
| * `exact` goes to 0 - because a percentile whose method the reader cannot |
| 176 |
|
| * know is a number they cannot act on. */ |
| 177 |
|
| #define PO_EXACT_MAX 200000 |
| 178 |
|
| |
| 179 |
19 |
| static double po_percentile(po_group *g, double q, int *exact) { |
| 180 |
19 |
▶ | if (!g->nsamp) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!g->nsamp) return 0; |
0 |
19 |
19 |
|
| 181 |
19 |
▶ | if (g->nsamp > PO_EXACT_MAX && exact) *exact = 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (g->nsamp > PO_EXACT_MAX && exact) *exact = 0; |
0 |
19 |
19 |
| if (g->nsamp > PO_EXACT_MAX && exact) *exact = 0; |
0 |
0 |
0 |
|
| 182 |
19 |
| qsort(g->samples, g->nsamp, sizeof(double), po_dcmp); |
| 183 |
|
| { |
| 184 |
19 |
| double idx = q * (double)(g->nsamp - 1); |
| 185 |
19 |
| uint32_t lo = (uint32_t)idx; |
| 186 |
19 |
▶ | uint32_t hi = lo + 1 < g->nsamp ? lo + 1 : lo; |
Branch: 1 branch
| Branch | True | False | Total |
| uint32_t hi = lo + 1 < g->nsamp ? lo + 1 : lo; |
19 |
0 |
19 |
|
| 187 |
19 |
| double frac = idx - (double)lo; |
| 188 |
19 |
| return g->samples[lo] + (g->samples[hi] - g->samples[lo]) * frac; |
| 189 |
|
| } |
| 190 |
|
| } |
| 191 |
|
| |
| 192 |
|
| #endif /* PO_RESULT_H */ |