| 1 |
|
| /* po_limit.h - three limits, enforced in three places, failing three ways. |
| 2 |
|
| * |
| 3 |
|
| * TREATING THESE AS ONE LIMIT IS THE MISTAKE. Each has a wrong answer that is |
| 4 |
|
| * worse than the limit itself, and the wrong answers are different, so one |
| 5 |
|
| * mechanism cannot serve all three. |
| 6 |
|
| * |
| 7 |
|
| * All three matter on a single-tenant box. They are what stops one |
| 8 |
|
| * misconfigured service taking down the machine whose job is to tell you why |
| 9 |
|
| * things fell over. |
| 10 |
|
| * |
| 11 |
|
| * INGEST RATE -> a partial success naming the rejected count. |
| 12 |
|
| * |
| 13 |
|
| * Not a 429. A 429 makes the exporter re-send the whole batch, forever, at |
| 14 |
|
| * the moment the server is already under pressure - the limit becomes an |
| 15 |
|
| * amplifier. OTLP has `partial_success` precisely for this: accept what |
| 16 |
|
| * fits, say how much did not, and the exporter drops the rest rather than |
| 17 |
|
| * queueing it. |
| 18 |
|
| * |
| 19 |
|
| * CARDINALITY -> the NEW series is dropped. |
| 20 |
|
| * |
| 21 |
|
| * Never an eviction. Evicting an existing series to admit a new one turns a |
| 22 |
|
| * cardinality problem into data loss on the exact series somebody has open |
| 23 |
|
| * in a dashboard, which is the one they are watching because it matters. |
| 24 |
|
| * |
| 25 |
|
| * STORAGE BYTES -> retention is SHORTENED. |
| 26 |
|
| * |
| 27 |
|
| * Not a refusal to write. A store over its byte budget should lose old |
| 28 |
|
| * data; it must not lose the incident happening now, which is when it is |
| 29 |
|
| * most needed and least replaceable. |
| 30 |
|
| * |
| 31 |
|
| * THE ARENA IS MAPPED BEFORE THE FORK. |
| 32 |
|
| * |
| 33 |
|
| * A counter mapped afterwards is private to each worker, and the symptom is a |
| 34 |
|
| * limit that is silently N times what was configured - which looks like the |
| 35 |
|
| * limit not working rather than like a fork bug. po_shared.h does the |
| 36 |
|
| * mapping; this file adds the rate window to it. |
| 37 |
|
| */ |
| 38 |
|
| #ifndef PO_LIMIT_H |
| 39 |
|
| #define PO_LIMIT_H |
| 40 |
|
| |
| 41 |
|
| #include "punk_observe/po_compat.h" |
| 42 |
|
| #include "punk_observe/po_time.h" |
| 43 |
|
| #include "punk_observe/po_shared.h" |
| 44 |
|
| |
| 45 |
|
| /* ---- ingest rate ---------------------------------------------------------- |
| 46 |
|
| * |
| 47 |
|
| * A one-second window, held in the shared arena so the limit is per POOL. Two |
| 48 |
|
| * counters, because a thousand tiny records and one enormous one are |
| 49 |
|
| * different problems and a byte limit alone lets the first through. */ |
| 50 |
|
| typedef struct { |
| 51 |
|
| po_u64 window_ns; |
| 52 |
|
| po_u64 max_records; /* 0 = unlimited */ |
| 53 |
|
| po_u64 max_bytes; /* 0 = unlimited */ |
| 54 |
|
| } po_rate_cfg; |
| 55 |
|
| |
| 56 |
|
| /* A view onto the window, wherever it lives. In production these point into |
| 57 |
|
| * the shared page (po_shared_rate); a test that only cares about the |
| 58 |
|
| * arithmetic can point them at locals. The indirection is what lets the same |
| 59 |
|
| * code be both fork-shared and unit-testable. */ |
| 60 |
|
| typedef struct { |
| 61 |
|
| po_u64 *window_start; |
| 62 |
|
| po_u64 *records; |
| 63 |
|
| po_u64 *bytes; |
| 64 |
|
| po_u64 *rejected; |
| 65 |
|
| } po_rate_win; |
| 66 |
|
| |
| 67 |
|
| /* The window inside the fork-shared arena. */ |
| 68 |
19 |
| static void po_shared_rate(po_shared *s, po_rate_win *w) { |
| 69 |
19 |
| w->window_start = &s->m->rate_window_start; |
| 70 |
19 |
| w->records = &s->m->rate_records; |
| 71 |
19 |
| w->bytes = &s->m->rate_bytes; |
| 72 |
19 |
| w->rejected = &s->m->rate_rejected; |
| 73 |
19 |
| } |
| 74 |
|
| |
| 75 |
28 |
| static void po_rate_cfg_init(po_rate_cfg *c, po_u64 rec, po_u64 bytes) { |
| 76 |
28 |
| c->window_ns = PO_NS_PER_SEC; |
| 77 |
28 |
| c->max_records = rec; |
| 78 |
28 |
| c->max_bytes = bytes; |
| 79 |
28 |
| } |
| 80 |
|
| |
| 81 |
|
| /* A private window, for a caller with no pool. Still goes through the same |
| 82 |
|
| * admit function, so the single-worker path is not a second implementation. */ |
| 83 |
|
| typedef struct { po_u64 start, records, bytes, rejected; } po_rate_local; |
| 84 |
|
| |
| 85 |
9 |
| static void po_rate_local_bind(po_rate_local *l, po_rate_win *w) { |
| 86 |
9 |
| memset(l, 0, sizeof(*l)); |
| 87 |
9 |
| w->window_start = &l->start; |
| 88 |
9 |
| w->records = &l->records; |
| 89 |
9 |
| w->bytes = &l->bytes; |
| 90 |
9 |
| w->rejected = &l->rejected; |
| 91 |
9 |
| } |
| 92 |
|
| |
| 93 |
|
| /* Admit as much of a batch as fits, and REPORT the remainder. |
| 94 |
|
| * |
| 95 |
|
| * Returns how many records were accepted. The caller turns the difference |
| 96 |
|
| * into `rejected_data_points` on the OTLP partial success - which is why this |
| 97 |
|
| * is a count and not a boolean. A yes/no answer would force the caller to |
| 98 |
|
| * refuse the whole batch, and refusing whole batches is what makes a limiter |
| 99 |
|
| * an amplifier. */ |
| 100 |
32 |
| static po_u64 po_rate_admit(po_rate_cfg *c, po_rate_win *w, |
| 101 |
|
| po_u64 records, po_u64 bytes) { |
| 102 |
32 |
| po_u64 now = po_now_ns(); |
| 103 |
32 |
| po_u64 room_r = records, room_b = records, per; |
| 104 |
|
| |
| 105 |
32 |
▶ | if (!c->max_records && !c->max_bytes) return records; /* unconfigured */ |
Branch: 2 branches
| Branch | True | False | Total |
| if (!c->max_records && !c->max_bytes) return records; /* unconfigured */ |
18 |
14 |
32 |
| if (!c->max_records && !c->max_bytes) return records; /* unconfigured */ |
17 |
1 |
18 |
|
| 106 |
15 |
▶ | if (!records) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!records) return 0; |
0 |
15 |
15 |
|
| 107 |
|
| |
| 108 |
|
| /* A fixed window, reset when it has elapsed. Chosen over a sliding one |
| 109 |
|
| * because a sliding window needs per-key history and this counter lives |
| 110 |
|
| * in a flat shared page; the cost is that a burst can straddle a boundary, |
| 111 |
|
| * which for a backpressure limit is acceptable and for a billing meter |
| 112 |
|
| * would not be. */ |
| 113 |
15 |
▶ | if (!*w->window_start || now - *w->window_start >= c->window_ns) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (!*w->window_start || now - *w->window_start >= c->window_ns) { |
6 |
9 |
15 |
| if (!*w->window_start || now - *w->window_start >= c->window_ns) { |
1 |
5 |
6 |
|
| 114 |
10 |
| *w->window_start = now; |
| 115 |
10 |
| *w->records = 0; |
| 116 |
10 |
| *w->bytes = 0; |
| 117 |
|
| } |
| 118 |
|
| |
| 119 |
15 |
▶ | if (c->max_records) |
Branch: 1 branch
| Branch | True | False | Total |
| if (c->max_records) |
14 |
1 |
15 |
|
| 120 |
14 |
| room_r = *w->records >= c->max_records |
| 121 |
14 |
▶ | ? 0 : c->max_records - *w->records; |
Branch: 1 branch
| Branch | True | False | Total |
| ? 0 : c->max_records - *w->records; |
13 |
1 |
14 |
|
| 122 |
|
| |
| 123 |
15 |
▶ | if (c->max_bytes) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (c->max_bytes) { |
2 |
13 |
15 |
|
| 124 |
2 |
▶ | po_u64 room = *w->bytes >= c->max_bytes ? 0 : c->max_bytes - *w->bytes; |
Branch: 1 branch
| Branch | True | False | Total |
| po_u64 room = *w->bytes >= c->max_bytes ? 0 : c->max_bytes - *w->bytes; |
2 |
0 |
2 |
|
| 125 |
|
| /* Bytes are converted to a record allowance at the batch's own |
| 126 |
|
| * average size. Estimating rather than measuring per record is the |
| 127 |
|
| * honest limitation: the alternative is a per-record size the caller |
| 128 |
|
| * does not have at this point. */ |
| 129 |
2 |
| per = bytes / records; |
| 130 |
2 |
▶ | if (!per) per = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!per) per = 1; |
0 |
2 |
2 |
|
| 131 |
2 |
| room_b = room / per; |
| 132 |
|
| } |
| 133 |
|
| |
| 134 |
|
| { |
| 135 |
15 |
| po_u64 admit = room_r < room_b ? room_r : room_b; |
| 136 |
15 |
▶ | if (admit > records) admit = records; |
Branch: 1 branch
| Branch | True | False | Total |
| if (admit > records) admit = records; |
0 |
15 |
15 |
|
| 137 |
15 |
| *w->records += admit; |
| 138 |
15 |
▶ | *w->bytes += records ? (bytes / records) * admit : 0; |
Branch: 1 branch
| Branch | True | False | Total |
| *w->bytes += records ? (bytes / records) * admit : 0; |
15 |
0 |
15 |
|
| 139 |
15 |
| *w->rejected += records - admit; |
| 140 |
15 |
| return admit; |
| 141 |
|
| } |
| 142 |
|
| } |
| 143 |
|
| |
| 144 |
|
| /* ---- cardinality ---------------------------------------------------------- |
| 145 |
|
| * |
| 146 |
|
| * po_shared.h owns the counter; this is the decision written where the other |
| 147 |
|
| * two limits are, so all three read together. |
| 148 |
|
| * |
| 149 |
|
| * An existing series is NEVER evicted. `po_shared_admit_series` only ever |
| 150 |
|
| * increments, so admission is monotonic and a refusal cannot displace |
| 151 |
|
| * anything - the property is structural rather than a rule somebody has to |
| 152 |
|
| * remember. */ |
| 153 |
0 |
| static int po_limit_series(po_shared *s) { |
| 154 |
0 |
| return po_shared_admit_series(s); |
| 155 |
|
| } |
| 156 |
|
| |
| 157 |
|
| /* ---- the indexed-attribute allowlist -------------------------------------- |
| 158 |
|
| * |
| 159 |
|
| * THE LIMIT THAT MATTERS MORE THAN ANY OF THE THREE NUMBERS. |
| 160 |
|
| * |
| 161 |
|
| * Logs and spans carry unbounded attributes. Only the configured set becomes |
| 162 |
|
| * an index dimension; the rest stay in the record and are reachable by a |
| 163 |
|
| * residual filter, so nothing is lost - it is just slower to find. Without |
| 164 |
|
| * this, one service putting a request id in a resource attribute takes the |
| 165 |
|
| * store down, and the store is right to refuse. |
| 166 |
|
| * |
| 167 |
|
| * THE OVERFLOW COUNTER NAMES THE ATTRIBUTE. The person who hits this first is |
| 168 |
|
| * a self-hoster with no support contract and no dashboard telling them which |
| 169 |
|
| * attribute did it, so "cardinality limit exceeded" is not an answer. The |
| 170 |
|
| * name is. */ |
| 171 |
|
| #define PO_ATTR_OVERFLOW_MAX 16 |
| 172 |
|
| |
| 173 |
|
| typedef struct { |
| 174 |
|
| char name[PO_ATTR_OVERFLOW_MAX][64]; |
| 175 |
|
| size_t name_len[PO_ATTR_OVERFLOW_MAX]; |
| 176 |
|
| po_u64 count[PO_ATTR_OVERFLOW_MAX]; |
| 177 |
|
| uint32_t n; |
| 178 |
|
| po_u64 dropped_other; /* past the naming cap, still counted */ |
| 179 |
|
| } po_attr_overflow; |
| 180 |
|
| |
| 181 |
5 |
| static void po_attr_overflow_init(po_attr_overflow *o) { |
| 182 |
5 |
| memset(o, 0, sizeof(*o)); |
| 183 |
5 |
| } |
| 184 |
|
| |
| 185 |
51 |
| static void po_attr_overflow_note(po_attr_overflow *o, const char *k, |
| 186 |
|
| size_t klen) { |
| 187 |
|
| uint32_t i; |
| 188 |
51 |
▶ | if (klen > 63) klen = 63; |
Branch: 1 branch
| Branch | True | False | Total |
| if (klen > 63) klen = 63; |
0 |
51 |
51 |
|
| 189 |
558 |
▶ | for (i = 0; i < o->n; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < o->n; i++) |
512 |
46 |
558 |
|
| 190 |
512 |
▶ | if (o->name_len[i] == klen && memcmp(o->name[i], k, klen) == 0) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (o->name_len[i] == klen && memcmp(o->name[i], k, klen) == 0) { |
230 |
282 |
512 |
| if (o->name_len[i] == klen && memcmp(o->name[i], k, klen) == 0) { |
5 |
225 |
230 |
|
| 191 |
5 |
| o->count[i]++; |
| 192 |
5 |
| return; |
| 193 |
|
| } |
| 194 |
46 |
▶ | if (o->n >= PO_ATTR_OVERFLOW_MAX) { o->dropped_other++; return; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (o->n >= PO_ATTR_OVERFLOW_MAX) { o->dropped_other++; return; } |
24 |
22 |
46 |
|
| 195 |
22 |
| memcpy(o->name[o->n], k, klen); |
| 196 |
22 |
| o->name[o->n][klen] = '\0'; |
| 197 |
22 |
| o->name_len[o->n] = klen; |
| 198 |
22 |
| o->count[o->n] = 1; |
| 199 |
22 |
| o->n++; |
| 200 |
|
| } |
| 201 |
|
| |
| 202 |
|
| /* The worst offender, which is what a status page shows. */ |
| 203 |
5 |
| static int po_attr_overflow_worst(const po_attr_overflow *o) { |
| 204 |
|
| uint32_t i; |
| 205 |
5 |
| int best = -1; |
| 206 |
5 |
| po_u64 most = 0; |
| 207 |
27 |
▶ | for (i = 0; i < o->n; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < o->n; i++) |
22 |
5 |
27 |
|
| 208 |
22 |
▶ | if (best < 0 || o->count[i] > most) { best = (int)i; most = o->count[i]; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (best < 0 || o->count[i] > most) { best = (int)i; most = o->count[i]; } |
17 |
5 |
22 |
| if (best < 0 || o->count[i] > most) { best = (int)i; most = o->count[i]; } |
0 |
17 |
17 |
|
| 209 |
5 |
| return best; |
| 210 |
|
| } |
| 211 |
|
| |
| 212 |
|
| /* ---- storage bytes -------------------------------------------------------- |
| 213 |
|
| * |
| 214 |
|
| * The retention job's answer to a byte budget: how far back can be kept. |
| 215 |
|
| * |
| 216 |
|
| * Blocks are given oldest-first with their sizes. The horizon returned is the |
| 217 |
|
| * age at which keeping any more would exceed the budget. Nothing is refused |
| 218 |
|
| * and no write fails; the store simply remembers less. |
| 219 |
|
| * |
| 220 |
|
| * Returns the number of blocks to KEEP (the newest ones). Zero means the |
| 221 |
|
| * budget cannot hold even the newest block, which is a configuration error |
| 222 |
|
| * rather than a reason to drop it - the caller keeps one and says so. */ |
| 223 |
|
| typedef struct { |
| 224 |
|
| po_u64 age_ns; /* how old the block is */ |
| 225 |
|
| po_u64 bytes; |
| 226 |
|
| } po_blk_size; |
| 227 |
|
| |
| 228 |
6 |
| static uint32_t po_limit_storage(const po_blk_size *b, uint32_t n, |
| 229 |
|
| po_u64 budget, po_u64 *kept_bytes, |
| 230 |
|
| po_u64 *horizon_ns) { |
| 231 |
6 |
| po_u64 total = 0; |
| 232 |
6 |
| uint32_t keep = 0; |
| 233 |
|
| int i; |
| 234 |
|
| |
| 235 |
6 |
▶ | if (kept_bytes) *kept_bytes = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (kept_bytes) *kept_bytes = 0; |
6 |
0 |
6 |
|
| 236 |
6 |
▶ | if (horizon_ns) *horizon_ns = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (horizon_ns) *horizon_ns = 0; |
6 |
0 |
6 |
|
| 237 |
6 |
▶ | if (!n) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!n) return 0; |
1 |
5 |
6 |
|
| 238 |
5 |
▶ | if (!budget) { /* unconfigured: keep everything */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (!budget) { /* unconfigured: keep everything */ |
1 |
4 |
5 |
|
| 239 |
11 |
▶ | for (i = 0; i < (int)n; i++) total += b[i].bytes; |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < (int)n; i++) total += b[i].bytes; |
10 |
1 |
11 |
|
| 240 |
1 |
▶ | if (kept_bytes) *kept_bytes = total; |
Branch: 1 branch
| Branch | True | False | Total |
| if (kept_bytes) *kept_bytes = total; |
1 |
0 |
1 |
|
| 241 |
1 |
▶ | if (horizon_ns) *horizon_ns = PO_U64_MAX; |
Branch: 1 branch
| Branch | True | False | Total |
| if (horizon_ns) *horizon_ns = PO_U64_MAX; |
1 |
0 |
1 |
|
| 242 |
1 |
| return n; |
| 243 |
|
| } |
| 244 |
|
| |
| 245 |
|
| /* Newest first, because the newest data is the data being looked at. */ |
| 246 |
22 |
▶ | for (i = (int)n - 1; i >= 0; i--) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = (int)n - 1; i >= 0; i--) { |
21 |
1 |
22 |
|
| 247 |
21 |
▶ | if (total + b[i].bytes > budget) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (total + b[i].bytes > budget) break; |
3 |
18 |
21 |
|
| 248 |
18 |
| total += b[i].bytes; |
| 249 |
18 |
| keep++; |
| 250 |
18 |
▶ | if (horizon_ns) *horizon_ns = b[i].age_ns; |
Branch: 1 branch
| Branch | True | False | Total |
| if (horizon_ns) *horizon_ns = b[i].age_ns; |
18 |
0 |
18 |
|
| 251 |
|
| } |
| 252 |
4 |
▶ | if (kept_bytes) *kept_bytes = total; |
Branch: 1 branch
| Branch | True | False | Total |
| if (kept_bytes) *kept_bytes = total; |
4 |
0 |
4 |
|
| 253 |
|
| |
| 254 |
|
| /* THE NEWEST BLOCK IS ALWAYS KEPT. A budget smaller than one block is a |
| 255 |
|
| * misconfiguration, and answering it by deleting the incident in progress |
| 256 |
|
| * would be the limiter doing more damage than the thing it limits. */ |
| 257 |
4 |
▶ | if (!keep) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!keep) { |
1 |
3 |
4 |
|
| 258 |
1 |
| keep = 1; |
| 259 |
1 |
▶ | if (kept_bytes) *kept_bytes = b[n - 1].bytes; |
Branch: 1 branch
| Branch | True | False | Total |
| if (kept_bytes) *kept_bytes = b[n - 1].bytes; |
1 |
0 |
1 |
|
| 260 |
1 |
▶ | if (horizon_ns) *horizon_ns = b[n - 1].age_ns; |
Branch: 1 branch
| Branch | True | False | Total |
| if (horizon_ns) *horizon_ns = b[n - 1].age_ns; |
1 |
0 |
1 |
|
| 261 |
|
| } |
| 262 |
4 |
| return keep; |
| 263 |
|
| } |
| 264 |
|
| |
| 265 |
|
| #endif /* PO_LIMIT_H */ |