| 1 |
|
| /* po_rollup.h - downsampled tiers, and the aggregate that is refused. |
| 2 |
|
| * |
| 3 |
|
| * A month of a 15-second series is 172,800 points. Charting it on a |
| 4 |
|
| * 1,200-pixel screen decodes 144 points per pixel to draw one, which is a |
| 5 |
|
| * long wait for a picture that could not show the difference. |
| 6 |
|
| * |
| 7 |
|
| * So the compactor writes two tiers, at five minutes and one hour, each point |
| 8 |
|
| * carrying: |
| 9 |
|
| * |
| 10 |
|
| * { count, sum, min, max, last } |
| 11 |
|
| * |
| 12 |
|
| * THAT SET IS CLOSED UNDER MERGING, which is the property that matters: an |
| 13 |
|
| * hourly point is built from twelve five-minute points without going back to |
| 14 |
|
| * the raw data, and the arithmetic is the same at every tier. |
| 15 |
|
| * |
| 16 |
|
| * IT ANSWERS EVERY AGGREGATE THE LANGUAGE HAS - EXCEPT ONE. |
| 17 |
|
| * |
| 18 |
|
| * avg = sum / count |
| 19 |
|
| * min = min |
| 20 |
|
| * max = max |
| 21 |
|
| * sum = sum |
| 22 |
|
| * rate = a difference over count or sum, per temporality |
| 23 |
|
| * p50, p90, p95, p99 -> REFUSED |
| 24 |
|
| * |
| 25 |
|
| * PERCENTILES DO NOT MERGE FROM SUMMARY STATISTICS. There is no function of |
| 26 |
|
| * {count, sum, min, max} that yields a p95, and every approximation that |
| 27 |
|
| * looks close is wrong in the tail - which is the only part of a latency |
| 28 |
|
| * chart anybody reads. A store that quietly returns a plausible number here |
| 29 |
|
| * has broken the single thing the chart is for, so it returns an error |
| 30 |
|
| * instead, and phase 12 renders that error rather than an empty panel. |
| 31 |
|
| * |
| 32 |
|
| * Where the series is a HISTOGRAM the percentile merges exactly from the |
| 33 |
|
| * bucket counts, and the rollup keeps them. That is the supported path for a |
| 34 |
|
| * long-range percentile, and it is why histogram instruments are worth using. |
| 35 |
|
| */ |
| 36 |
|
| #ifndef PO_ROLLUP_H |
| 37 |
|
| #define PO_ROLLUP_H |
| 38 |
|
| |
| 39 |
|
| #include "punk_observe/po_compat.h" |
| 40 |
|
| #include "punk_observe/po_metric.h" |
| 41 |
|
| |
| 42 |
|
| #define PO_TIER_RAW 0 |
| 43 |
|
| #define PO_TIER_5M 1 |
| 44 |
|
| #define PO_TIER_1H 2 |
| 45 |
|
| |
| 46 |
|
| #define PO_TIER_5M_NS ((po_u64)300 * 1000000000ULL) |
| 47 |
|
| #define PO_TIER_1H_NS ((po_u64)3600 * 1000000000ULL) |
| 48 |
|
| |
| 49 |
4397 |
| static po_u64 po_tier_span(int tier) { |
| 50 |
|
| return tier == PO_TIER_5M ? PO_TIER_5M_NS |
| 51 |
4397 |
▶ | : tier == PO_TIER_1H ? PO_TIER_1H_NS : 0; |
Branch: 2 branches
| Branch | True | False | Total |
| : tier == PO_TIER_1H ? PO_TIER_1H_NS : 0; |
104 |
4293 |
4397 |
| : tier == PO_TIER_1H ? PO_TIER_1H_NS : 0; |
104 |
0 |
104 |
|
| 52 |
|
| } |
| 53 |
|
| |
| 54 |
|
| typedef struct { |
| 55 |
|
| po_u64 t; /* the bucket's start, tier-aligned */ |
| 56 |
|
| po_u64 count; |
| 57 |
|
| double sum; |
| 58 |
|
| double min, max; |
| 59 |
|
| double last; |
| 60 |
|
| int resets; /* counter resets INSIDE this bucket */ |
| 61 |
|
| } po_rpoint; |
| 62 |
|
| |
| 63 |
|
| typedef struct { |
| 64 |
|
| po_rpoint *p; |
| 65 |
|
| uint32_t n, cap; |
| 66 |
|
| int tier; |
| 67 |
|
| } po_rollup; |
| 68 |
|
| |
| 69 |
44 |
| static int po_rollup_init(po_rollup *r, int tier) { |
| 70 |
44 |
| memset(r, 0, sizeof(*r)); |
| 71 |
44 |
| r->tier = tier; |
| 72 |
44 |
| r->cap = 32; |
| 73 |
44 |
| r->p = (po_rpoint *)calloc(r->cap, sizeof(po_rpoint)); |
| 74 |
44 |
| return r->p != NULL; |
| 75 |
|
| } |
| 76 |
|
| |
| 77 |
44 |
| static void po_rollup_free(po_rollup *r) { |
| 78 |
44 |
| free(r->p); r->p = NULL; r->n = r->cap = 0; |
| 79 |
44 |
| } |
| 80 |
|
| |
| 81 |
4397 |
| static po_rpoint *po_rollup_bucket(po_rollup *r, po_u64 t) { |
| 82 |
4397 |
| po_u64 span = po_tier_span(r->tier); |
| 83 |
4397 |
▶ | po_u64 start = span ? t - (t % span) : t; |
Branch: 1 branch
| Branch | True | False | Total |
| po_u64 start = span ? t - (t % span) : t; |
4397 |
0 |
4397 |
|
| 84 |
4397 |
▶ | if (r->n && r->p[r->n - 1].t == start) return &r->p[r->n - 1]; |
Branch: 2 branches
| Branch | True | False | Total |
| if (r->n && r->p[r->n - 1].t == start) return &r->p[r->n - 1]; |
4355 |
42 |
4397 |
| if (r->n && r->p[r->n - 1].t == start) return &r->p[r->n - 1]; |
4272 |
83 |
4355 |
|
| 85 |
125 |
▶ | if (r->n == r->cap) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (r->n == r->cap) { |
0 |
125 |
125 |
|
| 86 |
0 |
| uint32_t want = r->cap * 2; |
| 87 |
0 |
| po_rpoint *np = (po_rpoint *)realloc(r->p, want * sizeof(po_rpoint)); |
| 88 |
0 |
▶ | if (!np) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!np) return NULL; |
0 |
0 |
0 |
|
| 89 |
0 |
| memset(np + r->cap, 0, (want - r->cap) * sizeof(po_rpoint)); |
| 90 |
0 |
| r->p = np; r->cap = want; |
| 91 |
|
| } |
| 92 |
125 |
| r->p[r->n].t = start; |
| 93 |
125 |
| return &r->p[r->n++]; |
| 94 |
|
| } |
| 95 |
|
| |
| 96 |
|
| /* Fold one raw point in. |
| 97 |
|
| * |
| 98 |
|
| * `reset` is the flag the CHUNK carries, detected at encode time in phase 5. |
| 99 |
|
| * It is recorded here because the raw points are about to be dropped, and a |
| 100 |
|
| * rate computed over a rolled-up range containing an undetected reset is |
| 101 |
|
| * simply wrong with nothing left in the data to reveal it. */ |
| 102 |
4293 |
| static int po_rollup_add(po_rollup *r, po_u64 t, double v, int reset) { |
| 103 |
4293 |
| po_rpoint *b = po_rollup_bucket(r, t); |
| 104 |
4293 |
▶ | if (!b) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!b) return 0; |
0 |
4293 |
4293 |
|
| 105 |
4293 |
▶ | if (b->count == 0) { b->min = v; b->max = v; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (b->count == 0) { b->min = v; b->max = v; } |
104 |
4189 |
4293 |
|
| 106 |
|
| else { |
| 107 |
4189 |
▶ | if (v < b->min) b->min = v; |
Branch: 1 branch
| Branch | True | False | Total |
| if (v < b->min) b->min = v; |
55 |
4134 |
4189 |
|
| 108 |
4189 |
▶ | if (v > b->max) b->max = v; |
Branch: 1 branch
| Branch | True | False | Total |
| if (v > b->max) b->max = v; |
3293 |
896 |
4189 |
|
| 109 |
|
| } |
| 110 |
4293 |
| b->sum += v; |
| 111 |
4293 |
| b->last = v; |
| 112 |
4293 |
| b->count++; |
| 113 |
4293 |
▶ | if (reset) b->resets++; |
Branch: 1 branch
| Branch | True | False | Total |
| if (reset) b->resets++; |
3 |
4290 |
4293 |
|
| 114 |
4293 |
| return 1; |
| 115 |
|
| } |
| 116 |
|
| |
| 117 |
|
| /* Build the next tier up from this one, WITHOUT touching the raw data. This |
| 118 |
|
| * is the closure property in one function. */ |
| 119 |
22 |
| static int po_rollup_promote(const po_rollup *from, po_rollup *to, int tier) { |
| 120 |
|
| uint32_t i; |
| 121 |
22 |
▶ | if (!po_rollup_init(to, tier)) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_rollup_init(to, tier)) return 0; |
0 |
22 |
22 |
|
| 122 |
126 |
▶ | for (i = 0; i < from->n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < from->n; i++) { |
104 |
22 |
126 |
|
| 123 |
104 |
| const po_rpoint *s = &from->p[i]; |
| 124 |
104 |
| po_rpoint *b = po_rollup_bucket(to, s->t); |
| 125 |
104 |
▶ | if (!b) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!b) return 0; |
0 |
104 |
104 |
|
| 126 |
104 |
▶ | if (b->count == 0) { b->min = s->min; b->max = s->max; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (b->count == 0) { b->min = s->min; b->max = s->max; } |
21 |
83 |
104 |
|
| 127 |
|
| else { |
| 128 |
83 |
▶ | if (s->min < b->min) b->min = s->min; |
Branch: 1 branch
| Branch | True | False | Total |
| if (s->min < b->min) b->min = s->min; |
0 |
83 |
83 |
|
| 129 |
83 |
▶ | if (s->max > b->max) b->max = s->max; |
Branch: 1 branch
| Branch | True | False | Total |
| if (s->max > b->max) b->max = s->max; |
18 |
65 |
83 |
|
| 130 |
|
| } |
| 131 |
104 |
| b->sum += s->sum; |
| 132 |
104 |
| b->count += s->count; |
| 133 |
104 |
| b->last = s->last; /* the latest wins; buckets arrive in order */ |
| 134 |
104 |
| b->resets += s->resets; |
| 135 |
|
| } |
| 136 |
22 |
| return 1; |
| 137 |
|
| } |
| 138 |
|
| |
| 139 |
|
| /* Answering an aggregate from a tier. |
| 140 |
|
| * |
| 141 |
|
| * Returns 1 with *out set, or 0 for an aggregate a rollup cannot honour - and |
| 142 |
|
| * the caller reports that refusal rather than substituting something. */ |
| 143 |
44 |
| static int po_rollup_agg(const po_rollup *r, int agg, double *out) { |
| 144 |
|
| uint32_t i; |
| 145 |
44 |
| double acc = 0; |
| 146 |
44 |
| po_u64 n = 0; |
| 147 |
|
| |
| 148 |
44 |
| switch (agg) { |
| 149 |
14 |
| case PO_AGG_COUNT: |
| 150 |
52 |
▶ | for (i = 0; i < r->n; i++) n += r->p[i].count; |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < r->n; i++) n += r->p[i].count; |
38 |
14 |
52 |
|
| 151 |
14 |
| *out = (double)n; |
| 152 |
14 |
| return 1; |
| 153 |
10 |
| case PO_AGG_SUM: |
| 154 |
40 |
▶ | for (i = 0; i < r->n; i++) acc += r->p[i].sum; |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < r->n; i++) acc += r->p[i].sum; |
30 |
10 |
40 |
|
| 155 |
10 |
| *out = acc; |
| 156 |
10 |
| return 1; |
| 157 |
4 |
| case PO_AGG_AVG: |
| 158 |
19 |
▶ | for (i = 0; i < r->n; i++) { acc += r->p[i].sum; n += r->p[i].count; } |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < r->n; i++) { acc += r->p[i].sum; n += r->p[i].count; } |
15 |
4 |
19 |
|
| 159 |
4 |
▶ | *out = n ? acc / (double)n : 0; |
Branch: 1 branch
| Branch | True | False | Total |
| *out = n ? acc / (double)n : 0; |
4 |
0 |
4 |
|
| 160 |
4 |
| return 1; |
| 161 |
4 |
| case PO_AGG_MIN: |
| 162 |
19 |
▶ | for (i = 0; i < r->n; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < r->n; i++) |
15 |
4 |
19 |
|
| 163 |
15 |
▶ | if (i == 0 || r->p[i].min < acc) acc = r->p[i].min; |
Branch: 2 branches
| Branch | True | False | Total |
| if (i == 0 || r->p[i].min < acc) acc = r->p[i].min; |
11 |
4 |
15 |
| if (i == 0 || r->p[i].min < acc) acc = r->p[i].min; |
0 |
11 |
11 |
|
| 164 |
4 |
| *out = acc; |
| 165 |
4 |
| return r->n > 0; |
| 166 |
4 |
| case PO_AGG_MAX: |
| 167 |
19 |
▶ | for (i = 0; i < r->n; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < r->n; i++) |
15 |
4 |
19 |
|
| 168 |
15 |
▶ | if (i == 0 || r->p[i].max > acc) acc = r->p[i].max; |
Branch: 2 branches
| Branch | True | False | Total |
| if (i == 0 || r->p[i].max > acc) acc = r->p[i].max; |
11 |
4 |
15 |
| if (i == 0 || r->p[i].max > acc) acc = r->p[i].max; |
1 |
10 |
11 |
|
| 169 |
4 |
| *out = acc; |
| 170 |
4 |
| return r->n > 0; |
| 171 |
8 |
| case PO_AGG_P50: case PO_AGG_P90: |
| 172 |
|
| case PO_AGG_P95: case PO_AGG_P99: |
| 173 |
|
| /* See the header. Not approximated. */ |
| 174 |
8 |
| return 0; |
| 175 |
0 |
| default: |
| 176 |
0 |
| return 0; |
| 177 |
|
| } |
| 178 |
|
| } |
| 179 |
|
| |
| 180 |
4 |
| static const char *po_rollup_refusal(int agg) { |
| 181 |
4 |
▶ | switch (agg) { |
Branch: 1 branch
| Branch | True | False | Total |
| switch (agg) { |
4 |
0 |
4 |
|
| 182 |
4 |
| case PO_AGG_P50: case PO_AGG_P90: |
| 183 |
|
| case PO_AGG_P95: case PO_AGG_P99: |
| 184 |
4 |
| return "a percentile cannot be computed from downsampled data; " |
| 185 |
|
| "shorten the range to reach raw points, or record the " |
| 186 |
|
| "series as a histogram"; |
| 187 |
0 |
| default: |
| 188 |
0 |
| return "that aggregate is not available from downsampled data"; |
| 189 |
|
| } |
| 190 |
|
| } |
| 191 |
|
| |
| 192 |
|
| /* Does the range contain a counter reset? A rate over a rolled-up range must |
| 193 |
|
| * know, and after retention this is the only place that remembers. */ |
| 194 |
44 |
| static int po_rollup_resets(const po_rollup *r) { |
| 195 |
|
| uint32_t i; |
| 196 |
44 |
| int n = 0; |
| 197 |
169 |
▶ | for (i = 0; i < r->n; i++) n += r->p[i].resets; |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < r->n; i++) n += r->p[i].resets; |
125 |
44 |
169 |
|
| 198 |
44 |
| return n; |
| 199 |
|
| } |
| 200 |
|
| |
| 201 |
|
| #endif /* PO_ROLLUP_H */ |