| 1 |
|
| /* po_gorilla.h - delta-of-delta timestamps, XOR values. |
| 2 |
|
| * |
| 3 |
|
| * A naive point is 16 bytes: 8 of timestamp, 8 of double. A series scraped |
| 4 |
|
| * every 15 seconds for a day is 5,760 points, 92KB, times however many series |
| 5 |
|
| * a fleet has. The published Gorilla result is about 1.37 bytes per point, |
| 6 |
|
| * and the two halves are independent and both simple. |
| 7 |
|
| * |
| 8 |
|
| * TIMESTAMPS: DELTA OF DELTA. Points arrive on an interval, so the delta is |
| 9 |
|
| * nearly constant and the delta of the delta is nearly always zero. |
| 10 |
|
| * |
| 11 |
|
| * ONE DEPARTURE FROM THE PAPER, AND IT IS FORCED. Gorilla stores the second |
| 12 |
|
| * timestamp as a 14-bit delta, because its timestamps are SECONDS. OTLP |
| 13 |
|
| * timestamps are NANOSECONDS: a 15-second scrape interval is 1.5e10 ns, which |
| 14 |
|
| * does not fit 14 bits, or 32. So the first delta is written as a full 64 |
| 15 |
|
| * bits. It costs eight bytes ONCE per chunk - amortised over 120 points that |
| 16 |
|
| * is under a bit each - and taking the published constant unexamined would |
| 17 |
|
| * have produced a decoder that silently truncates every interval. |
| 18 |
|
| * |
| 19 |
|
| * VALUES: XOR AGAINST THE PREVIOUS. A gauge that barely moves and a counter |
| 20 |
|
| * that increments both XOR to a value with long runs of leading and trailing |
| 21 |
|
| * zeros. |
| 22 |
|
| */ |
| 23 |
|
| #ifndef PO_GORILLA_H |
| 24 |
|
| #define PO_GORILLA_H |
| 25 |
|
| |
| 26 |
|
| #include "punk_observe/po_compat.h" |
| 27 |
|
| #include "punk_observe/po_bits.h" |
| 28 |
|
| |
| 29 |
|
| typedef struct { |
| 30 |
|
| po_bw bw; |
| 31 |
|
| po_u64 t_prev; |
| 32 |
|
| po_i64 d_prev; /* the previous delta, signed: points can arrive |
| 33 |
|
| * out of order and a delta can be negative */ |
| 34 |
|
| po_u64 v_prev; /* the previous value's BIT PATTERN */ |
| 35 |
|
| int lead_prev; |
| 36 |
|
| int len_prev; |
| 37 |
|
| uint32_t n; |
| 38 |
|
| } po_gor_w; |
| 39 |
|
| |
| 40 |
49 |
| static int po_gor_w_init(po_gor_w *g) { |
| 41 |
49 |
| memset(g, 0, sizeof(*g)); |
| 42 |
49 |
| g->lead_prev = -1; |
| 43 |
49 |
| return po_bw_init(&g->bw, 256); |
| 44 |
|
| } |
| 45 |
|
| |
| 46 |
49 |
| static void po_gor_w_free(po_gor_w *g) { po_bw_free(&g->bw); } |
| 47 |
|
| |
| 48 |
|
| /* Append one point. `bits` is the value's BIT PATTERN, not its numeric value. |
| 49 |
|
| * |
| 50 |
|
| * Passing the bit pattern rather than a double is deliberate: it makes NaN |
| 51 |
|
| * payloads, the infinities and negative zero survive exactly, and it means |
| 52 |
|
| * an integer point (OTLP's as_int) uses the identical path without a lossy |
| 53 |
|
| * trip through a double. */ |
| 54 |
105037 |
| static void po_gor_put(po_gor_w *g, po_u64 t, po_u64 bits) { |
| 55 |
105037 |
▶ | if (g->n == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (g->n == 0) { |
49 |
104988 |
105037 |
|
| 56 |
49 |
| po_bw_put(&g->bw, t, 64); /* the anchor timestamp */ |
| 57 |
49 |
| po_bw_put(&g->bw, bits, 64); /* and the anchor value */ |
| 58 |
49 |
| g->t_prev = t; |
| 59 |
49 |
| g->v_prev = bits; |
| 60 |
49 |
| g->d_prev = 0; |
| 61 |
49 |
| g->n = 1; |
| 62 |
49 |
| return; |
| 63 |
|
| } |
| 64 |
|
| |
| 65 |
104988 |
▶ | if (g->n == 1) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (g->n == 1) { |
48 |
104940 |
104988 |
|
| 66 |
|
| /* The first delta, in full. See the header note: nanoseconds do not |
| 67 |
|
| * fit the paper's 14 bits. */ |
| 68 |
48 |
| po_i64 d = (po_i64)(t - g->t_prev); |
| 69 |
48 |
| po_bw_put(&g->bw, (po_u64)d, 64); |
| 70 |
48 |
| g->d_prev = d; |
| 71 |
48 |
| g->t_prev = t; |
| 72 |
|
| } |
| 73 |
|
| else { |
| 74 |
104940 |
| po_i64 d = (po_i64)(t - g->t_prev); |
| 75 |
104940 |
| po_i64 dod = d - g->d_prev; |
| 76 |
|
| |
| 77 |
|
| /* THE RANGES ARE TWO'S-COMPLEMENT RANGES, NOT THE PAPER'S. |
| 78 |
|
| * |
| 79 |
|
| * Gorilla is usually written as [-63, 64] in 7 bits, [-255, 256] in |
| 80 |
|
| * 9, and so on. Those are 128 and 512 distinct values, so they fit - |
| 81 |
|
| * but only with an offset. Stored DIRECTLY as two's complement, 7 |
| 82 |
|
| * bits holds -64..63, and a dod of 64 written that way reads back as |
| 83 |
|
| * -64. The point lands in the wrong place and nothing reports it. |
| 84 |
|
| * |
| 85 |
|
| * Taking the published constants unexamined put exactly that bug in |
| 86 |
|
| * here, and the bucket-boundary test caught it. */ |
| 87 |
104940 |
▶ | if (dod == 0) po_bw_put1(&g->bw, 0); |
Branch: 1 branch
| Branch | True | False | Total |
| if (dod == 0) po_bw_put1(&g->bw, 0); |
104920 |
20 |
104940 |
|
| 88 |
20 |
▶ | else if (dod >= -64 && dod <= 63) { |
Branch: 2 branches
| Branch | True | False | Total |
| else if (dod >= -64 && dod <= 63) { |
12 |
8 |
20 |
| else if (dod >= -64 && dod <= 63) { |
2 |
10 |
12 |
|
| 89 |
2 |
| po_bw_put(&g->bw, 0x2, 2); /* 10 */ |
| 90 |
2 |
| po_bw_put(&g->bw, (po_u64)dod & 0x7F, 7); |
| 91 |
|
| } |
| 92 |
18 |
▶ | else if (dod >= -256 && dod <= 255) { |
Branch: 2 branches
| Branch | True | False | Total |
| else if (dod >= -256 && dod <= 255) { |
12 |
6 |
18 |
| else if (dod >= -256 && dod <= 255) { |
4 |
8 |
12 |
|
| 93 |
4 |
| po_bw_put(&g->bw, 0x6, 3); /* 110 */ |
| 94 |
4 |
| po_bw_put(&g->bw, (po_u64)dod & 0x1FF, 9); |
| 95 |
|
| } |
| 96 |
14 |
▶ | else if (dod >= -2048 && dod <= 2047) { |
Branch: 2 branches
| Branch | True | False | Total |
| else if (dod >= -2048 && dod <= 2047) { |
10 |
4 |
14 |
| else if (dod >= -2048 && dod <= 2047) { |
4 |
6 |
10 |
|
| 97 |
4 |
| po_bw_put(&g->bw, 0xE, 4); /* 1110 */ |
| 98 |
4 |
| po_bw_put(&g->bw, (po_u64)dod & 0xFFF, 12); |
| 99 |
|
| } |
| 100 |
10 |
▶ | else if (dod >= -((po_i64)1 << 31) && dod < ((po_i64)1 << 31)) { |
Branch: 2 branches
| Branch | True | False | Total |
| else if (dod >= -((po_i64)1 << 31) && dod < ((po_i64)1 << 31)) { |
9 |
1 |
10 |
| else if (dod >= -((po_i64)1 << 31) && dod < ((po_i64)1 << 31)) { |
7 |
2 |
9 |
|
| 101 |
7 |
| po_bw_put(&g->bw, 0x1E, 5); /* 11110 */ |
| 102 |
7 |
| po_bw_put(&g->bw, (po_u64)dod & 0xFFFFFFFFu, 32); |
| 103 |
|
| } |
| 104 |
|
| else { |
| 105 |
|
| /* The 64-bit escape. Gorilla has no such case because its |
| 106 |
|
| * timestamps are seconds; nanoseconds reach it whenever a series |
| 107 |
|
| * genuinely jumps, and without it those points would be lost. */ |
| 108 |
3 |
| po_bw_put(&g->bw, 0x1F, 5); /* 11111 */ |
| 109 |
3 |
| po_bw_put(&g->bw, (po_u64)dod, 64); |
| 110 |
|
| } |
| 111 |
104940 |
| g->d_prev = d; |
| 112 |
104940 |
| g->t_prev = t; |
| 113 |
|
| } |
| 114 |
|
| |
| 115 |
|
| { /* the value */ |
| 116 |
104988 |
| po_u64 x = g->v_prev ^ bits; |
| 117 |
104988 |
▶ | if (x == 0) po_bw_put1(&g->bw, 0); |
Branch: 1 branch
| Branch | True | False | Total |
| if (x == 0) po_bw_put1(&g->bw, 0); |
353 |
104635 |
104988 |
|
| 118 |
|
| else { |
| 119 |
104635 |
| int lead = 0, trail = 0, i; |
| 120 |
532613 |
▶ | for (i = 63; i >= 0 && !((x >> i) & 1); i--) lead++; |
Branch: 2 branches
| Branch | True | False | Total |
| for (i = 63; i >= 0 && !((x >> i) & 1); i--) lead++; |
532613 |
0 |
532613 |
| for (i = 63; i >= 0 && !((x >> i) & 1); i--) lead++; |
427978 |
104635 |
532613 |
|
| 121 |
544918 |
▶ | for (i = 0; i < 64 && !((x >> i) & 1); i++) trail++; |
Branch: 2 branches
| Branch | True | False | Total |
| for (i = 0; i < 64 && !((x >> i) & 1); i++) trail++; |
544918 |
0 |
544918 |
| for (i = 0; i < 64 && !((x >> i) & 1); i++) trail++; |
440283 |
104635 |
544918 |
|
| 122 |
104635 |
▶ | if (lead > 31) lead = 31; /* the field is 5 bits */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (lead > 31) lead = 31; /* the field is 5 bits */ |
585 |
104050 |
104635 |
|
| 123 |
|
| |
| 124 |
104635 |
| po_bw_put1(&g->bw, 1); |
| 125 |
|
| /* REUSE REQUIRES THE MEANINGFUL BITS TO FIT THE PREVIOUS WINDOW |
| 126 |
|
| * IN POSITION, NOT MERELY IN WIDTH. |
| 127 |
|
| * |
| 128 |
|
| * The previous window covers bits [lead_prev, lead_prev+len_prev), |
| 129 |
|
| * so reuse is only valid when this xor's meaningful range sits |
| 130 |
|
| * inside it: lead >= lead_prev AND trail >= trail_prev. |
| 131 |
|
| * |
| 132 |
|
| * The first version checked `(64 - lead - trail) <= len_prev` - |
| 133 |
|
| * the WIDTH fits - which is not the same thing. An xor whose bits |
| 134 |
|
| * start inside the window but extend past its bottom had the |
| 135 |
|
| * overhang silently shifted away, and the decoder reconstructed a |
| 136 |
|
| * different number. No crash, no error: a wrong value on a chart. |
| 137 |
|
| * |
| 138 |
|
| * It survived 100,000 random doubles because random values never |
| 139 |
|
| * take this branch - consecutive random mantissas share nothing, |
| 140 |
|
| * so every point stores a new window. A smoothly increasing |
| 141 |
|
| * series takes it on almost every point, which is what most real |
| 142 |
|
| * metrics are. */ |
| 143 |
104635 |
▶ | if (g->lead_prev >= 0 && g->len_prev > 0 |
Branch: 2 branches
| Branch | True | False | Total |
| if (g->lead_prev >= 0 && g->len_prev > 0 |
104591 |
44 |
104635 |
| if (g->lead_prev >= 0 && g->len_prev > 0 |
104591 |
0 |
104591 |
|
| 144 |
104591 |
▶ | && lead >= g->lead_prev |
Branch: 1 branch
| Branch | True | False | Total |
| && lead >= g->lead_prev |
104289 |
302 |
104591 |
|
| 145 |
104289 |
▶ | && trail >= 64 - g->lead_prev - g->len_prev) { |
Branch: 1 branch
| Branch | True | False | Total |
| && trail >= 64 - g->lead_prev - g->len_prev) { |
104165 |
124 |
104289 |
|
| 146 |
104165 |
| po_bw_put1(&g->bw, 0); |
| 147 |
104165 |
| po_bw_put(&g->bw, x >> (64 - g->lead_prev - g->len_prev), |
| 148 |
|
| g->len_prev); |
| 149 |
|
| } |
| 150 |
|
| else { |
| 151 |
470 |
| int len = 64 - lead - trail; |
| 152 |
470 |
▶ | if (len < 1) len = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (len < 1) len = 1; |
0 |
470 |
470 |
|
| 153 |
470 |
▶ | if (len > 64) len = 64; |
Branch: 1 branch
| Branch | True | False | Total |
| if (len > 64) len = 64; |
0 |
470 |
470 |
|
| 154 |
470 |
| po_bw_put1(&g->bw, 1); |
| 155 |
470 |
| po_bw_put(&g->bw, (po_u64)lead, 5); |
| 156 |
|
| /* 64 is written as 0 in six bits: a length of 0 is |
| 157 |
|
| * meaningless (that is the xor==0 case), so the encoding is |
| 158 |
|
| * unambiguous and 64-bit differences stay representable. */ |
| 159 |
470 |
| po_bw_put(&g->bw, (po_u64)(len & 0x3F), 6); |
| 160 |
470 |
| po_bw_put(&g->bw, x >> trail, len); |
| 161 |
470 |
| g->lead_prev = lead; |
| 162 |
470 |
| g->len_prev = len; |
| 163 |
|
| } |
| 164 |
|
| } |
| 165 |
104988 |
| g->v_prev = bits; |
| 166 |
|
| } |
| 167 |
104988 |
| g->n++; |
| 168 |
|
| } |
| 169 |
|
| |
| 170 |
|
| /* ---- reading ------------------------------------------------------------- */ |
| 171 |
|
| |
| 172 |
|
| typedef struct { |
| 173 |
|
| po_br br; |
| 174 |
|
| po_u64 t_prev; |
| 175 |
|
| po_i64 d_prev; |
| 176 |
|
| po_u64 v_prev; |
| 177 |
|
| int lead_prev; |
| 178 |
|
| int len_prev; |
| 179 |
|
| uint32_t i, n; |
| 180 |
|
| } po_gor_r; |
| 181 |
|
| |
| 182 |
47 |
| static void po_gor_r_init(po_gor_r *g, const void *buf, size_t nbits, |
| 183 |
|
| uint32_t count) { |
| 184 |
47 |
| memset(g, 0, sizeof(*g)); |
| 185 |
47 |
| po_br_init(&g->br, buf, nbits); |
| 186 |
47 |
| g->lead_prev = -1; |
| 187 |
47 |
| g->n = count; |
| 188 |
47 |
| } |
| 189 |
|
| |
| 190 |
|
| /* Returns 1 and fills *t and *bits, or 0 at the end / on a malformed stream. */ |
| 191 |
105054 |
| static int po_gor_next(po_gor_r *g, po_u64 *t, po_u64 *bits) { |
| 192 |
105054 |
▶ | if (g->br.err || g->i >= g->n) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (g->br.err || g->i >= g->n) return 0; |
105054 |
0 |
105054 |
| if (g->br.err || g->i >= g->n) return 0; |
47 |
105007 |
105054 |
|
| 193 |
|
| |
| 194 |
105007 |
▶ | if (g->i == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (g->i == 0) { |
47 |
104960 |
105007 |
|
| 195 |
47 |
| g->t_prev = po_br_get(&g->br, 64); |
| 196 |
47 |
| g->v_prev = po_br_get(&g->br, 64); |
| 197 |
47 |
| g->d_prev = 0; |
| 198 |
|
| } |
| 199 |
104960 |
▶ | else if (g->i == 1) { |
Branch: 1 branch
| Branch | True | False | Total |
| else if (g->i == 1) { |
46 |
104914 |
104960 |
|
| 200 |
46 |
| po_i64 d = (po_i64)po_br_get(&g->br, 64); |
| 201 |
46 |
| g->d_prev = d; |
| 202 |
46 |
| g->t_prev = (po_u64)((po_i64)g->t_prev + d); |
| 203 |
46 |
| goto value; |
| 204 |
|
| } |
| 205 |
|
| else { |
| 206 |
104914 |
| po_i64 dod = 0; |
| 207 |
104914 |
▶ | if (po_br_get1(&g->br) == 0) dod = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (po_br_get1(&g->br) == 0) dod = 0; |
104894 |
20 |
104914 |
|
| 208 |
20 |
▶ | else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 7), 7); |
Branch: 1 branch
| Branch | True | False | Total |
| else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 7), 7); |
2 |
18 |
20 |
|
| 209 |
18 |
▶ | else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 9), 9); |
Branch: 1 branch
| Branch | True | False | Total |
| else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 9), 9); |
4 |
14 |
18 |
|
| 210 |
14 |
▶ | else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 12), 12); |
Branch: 1 branch
| Branch | True | False | Total |
| else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 12), 12); |
4 |
10 |
14 |
|
| 211 |
10 |
▶ | else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 32), 32); |
Branch: 1 branch
| Branch | True | False | Total |
| else if (po_br_get1(&g->br) == 0) dod = po_sext(po_br_get(&g->br, 32), 32); |
7 |
3 |
10 |
|
| 212 |
3 |
| else dod = (po_i64)po_br_get(&g->br, 64); |
| 213 |
|
| |
| 214 |
104914 |
| g->d_prev = g->d_prev + dod; |
| 215 |
104914 |
| g->t_prev = (po_u64)((po_i64)g->t_prev + g->d_prev); |
| 216 |
104914 |
| goto value; |
| 217 |
|
| } |
| 218 |
|
| |
| 219 |
47 |
▶ | if (g->br.err) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (g->br.err) return 0; |
0 |
47 |
47 |
|
| 220 |
47 |
| *t = g->t_prev; *bits = g->v_prev; |
| 221 |
47 |
| g->i++; |
| 222 |
47 |
| return 1; |
| 223 |
|
| |
| 224 |
104960 |
| value: |
| 225 |
|
| { |
| 226 |
104960 |
▶ | if (po_br_get1(&g->br) == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (po_br_get1(&g->br) == 0) { |
104616 |
344 |
104960 |
|
| 227 |
|
| /* unchanged */ |
| 228 |
|
| } |
| 229 |
104616 |
▶ | else if (po_br_get1(&g->br) == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| else if (po_br_get1(&g->br) == 0) { |
104152 |
464 |
104616 |
|
| 230 |
|
| po_u64 m; |
| 231 |
104152 |
▶ | if (g->len_prev <= 0) { g->br.err = 1; return 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (g->len_prev <= 0) { g->br.err = 1; return 0; } |
0 |
104152 |
104152 |
|
| 232 |
104152 |
| m = po_br_get(&g->br, g->len_prev); |
| 233 |
104152 |
| g->v_prev ^= m << (64 - g->lead_prev - g->len_prev); |
| 234 |
|
| } |
| 235 |
|
| else { |
| 236 |
464 |
| int lead = (int)po_br_get(&g->br, 5); |
| 237 |
464 |
| int len = (int)po_br_get(&g->br, 6); |
| 238 |
|
| po_u64 m; |
| 239 |
464 |
▶ | if (len == 0) len = 64; /* the 64 encoding, see above */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (len == 0) len = 64; /* the 64 encoding, see above */ |
2 |
462 |
464 |
|
| 240 |
464 |
▶ | if (lead + len > 64) { g->br.err = 1; return 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (lead + len > 64) { g->br.err = 1; return 0; } |
0 |
464 |
464 |
|
| 241 |
464 |
| m = po_br_get(&g->br, len); |
| 242 |
464 |
| g->v_prev ^= m << (64 - lead - len); |
| 243 |
464 |
| g->lead_prev = lead; |
| 244 |
464 |
| g->len_prev = len; |
| 245 |
|
| } |
| 246 |
|
| } |
| 247 |
104960 |
▶ | if (g->br.err) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (g->br.err) return 0; |
0 |
104960 |
104960 |
|
| 248 |
104960 |
| *t = g->t_prev; *bits = g->v_prev; |
| 249 |
104960 |
| g->i++; |
| 250 |
104960 |
| return 1; |
| 251 |
|
| } |
| 252 |
|
| |
| 253 |
|
| /* Bit patterns in and out, so a caller that has a double converts explicitly |
| 254 |
|
| * and a caller that has an integer does not convert at all. */ |
| 255 |
105495 |
| static po_u64 po_d2b(double d) { po_u64 b; memcpy(&b, &d, 8); return b; } |
| 256 |
67 |
| static double po_b2d(po_u64 b) { double d; memcpy(&d, &b, 8); return d; } |
| 257 |
|
| |
| 258 |
|
| #endif /* PO_GORILLA_H */ |