include/punk_observe/po_rollup.h

filter: Statementstmt 89.7% 79 / 88 Branchbran 80.0% 48 / 60 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 85.8% 127 / 148 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/punk_observe/po_view.h ↑ Summary include/punk_observe/po_sgraph.h »
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
BranchTrueFalseTotal
: 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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!b) return 0; 0 4293 4293
105 4293 ▶ if (b->count == 0) { b->min = v; b->max = v; }
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (v < b->min) b->min = v; 55 4134 4189
108 4189 ▶ if (v > b->max) b->max = v;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!po_rollup_init(to, tier)) return 0; 0 22 22
122 126 ▶ for (i = 0; i < from->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!b) return 0; 0 104 104
126 104 ▶ if (b->count == 0) { b->min = s->min; b->max = s->max; }
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
*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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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 */
« include/punk_observe/po_view.h ↑ Summary include/punk_observe/po_sgraph.h »