| 1 |
|
| /* po_logidx.h - the block directory, and the label allowlist. |
| 2 |
|
| * |
| 3 |
|
| * Two jobs, and the second one is the one that keeps the store alive. |
| 4 |
|
| * |
| 5 |
|
| * THE DIRECTORY. One entry per block, carrying the stream, the time span, the |
| 6 |
|
| * offsets and the bloom. A time filter skips a block by reading 48 bytes, |
| 7 |
|
| * WITHOUT INFLATING IT - which is the entire point of having a directory at |
| 8 |
|
| * all, and the reason t_min/t_max live here and not inside the compressed |
| 9 |
|
| * bytes. |
| 10 |
|
| * |
| 11 |
|
| * THE ALLOWLIST. A stream is a label set, and a label set with a request id in |
| 12 |
|
| * it is one stream per request. That is the cardinality explosion wearing a |
| 13 |
|
| * different costume, and it arrives the same way it always does: somebody |
| 14 |
|
| * adds `user_id` or a full URL as a resource attribute. |
| 15 |
|
| * |
| 16 |
|
| * So ONLY configured attributes become stream labels. Everything else stays |
| 17 |
|
| * in the record, searchable by residual filter but not indexed. Without this, |
| 18 |
|
| * one customer takes the store down and the store is RIGHT to refuse. |
| 19 |
|
| */ |
| 20 |
|
| #ifndef PO_LOGIDX_H |
| 21 |
|
| #define PO_LOGIDX_H |
| 22 |
|
| |
| 23 |
|
| #include "punk_observe/po_compat.h" |
| 24 |
|
| #include "punk_observe/po_log.h" |
| 25 |
|
| |
| 26 |
|
| #define PO_LABEL_MAX 32 |
| 27 |
|
| #define PO_LABEL_KEYMAX 128 |
| 28 |
|
| |
| 29 |
|
| /* The default allowlist. Deliberately short: these are the dimensions people |
| 30 |
|
| * actually filter logs by, and every addition multiplies the stream count. |
| 31 |
|
| * An operator can extend it; the point is that the default is safe rather |
| 32 |
|
| * than convenient. */ |
| 33 |
|
| static const char *const PO_DEFAULT_LABELS[] = { |
| 34 |
|
| "service.name", |
| 35 |
|
| "severity", |
| 36 |
|
| "host.name", |
| 37 |
|
| "deployment.environment", |
| 38 |
|
| NULL |
| 39 |
|
| }; |
| 40 |
|
| |
| 41 |
|
| typedef struct { |
| 42 |
|
| char key[PO_LABEL_MAX][PO_LABEL_KEYMAX]; |
| 43 |
|
| uint32_t klen[PO_LABEL_MAX]; |
| 44 |
|
| int n; |
| 45 |
|
| } po_labelset; |
| 46 |
|
| |
| 47 |
10 |
| static void po_labelset_default(po_labelset *s) { |
| 48 |
|
| int i; |
| 49 |
10 |
| memset(s, 0, sizeof(*s)); |
| 50 |
50 |
▶ | for (i = 0; PO_DEFAULT_LABELS[i] && i < PO_LABEL_MAX; i++) { |
Branch: 2 branches
| Branch | True | False | Total |
| for (i = 0; PO_DEFAULT_LABELS[i] && i < PO_LABEL_MAX; i++) { |
40 |
10 |
50 |
| for (i = 0; PO_DEFAULT_LABELS[i] && i < PO_LABEL_MAX; i++) { |
40 |
0 |
40 |
|
| 51 |
40 |
| size_t l = strlen(PO_DEFAULT_LABELS[i]); |
| 52 |
40 |
| memcpy(s->key[i], PO_DEFAULT_LABELS[i], l); |
| 53 |
40 |
| s->klen[i] = (uint32_t)l; |
| 54 |
40 |
| s->n++; |
| 55 |
|
| } |
| 56 |
10 |
| } |
| 57 |
|
| |
| 58 |
5 |
| static int po_labelset_add(po_labelset *s, const char *k, size_t len) { |
| 59 |
5 |
▶ | if (s->n >= PO_LABEL_MAX || len >= PO_LABEL_KEYMAX) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (s->n >= PO_LABEL_MAX || len >= PO_LABEL_KEYMAX) return 0; |
5 |
0 |
5 |
| if (s->n >= PO_LABEL_MAX || len >= PO_LABEL_KEYMAX) return 0; |
0 |
5 |
5 |
|
| 60 |
5 |
| memcpy(s->key[s->n], k, len); |
| 61 |
5 |
| s->klen[s->n] = (uint32_t)len; |
| 62 |
5 |
| s->n++; |
| 63 |
5 |
| return 1; |
| 64 |
|
| } |
| 65 |
|
| |
| 66 |
|
| /* Is this attribute a stream label, or does it stay in the record? |
| 67 |
|
| * |
| 68 |
|
| * The answer decides whether an attribute multiplies the stream count. A |
| 69 |
|
| * `user_id` answering yes here is how a log store dies. */ |
| 70 |
65 |
| static int po_is_label(const po_labelset *s, const char *k, size_t len) { |
| 71 |
|
| int i; |
| 72 |
150 |
▶ | for (i = 0; i < s->n; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < s->n; i++) |
93 |
57 |
150 |
|
| 73 |
93 |
▶ | if (s->klen[i] == (uint32_t)len && memcmp(s->key[i], k, len) == 0) |
Branch: 2 branches
| Branch | True | False | Total |
| if (s->klen[i] == (uint32_t)len && memcmp(s->key[i], k, len) == 0) |
10 |
83 |
93 |
| if (s->klen[i] == (uint32_t)len && memcmp(s->key[i], k, len) == 0) |
8 |
2 |
10 |
|
| 74 |
8 |
| return 1; |
| 75 |
57 |
| return 0; |
| 76 |
|
| } |
| 77 |
|
| |
| 78 |
|
| /* ---- the directory -------------------------------------------------------- */ |
| 79 |
|
| |
| 80 |
|
| typedef struct { |
| 81 |
|
| po_block_hdr h; |
| 82 |
|
| po_u64 off; /* of the compressed bytes within the region */ |
| 83 |
|
| po_u64 bloom_off; /* of the bloom bits */ |
| 84 |
|
| } po_dir_ent; |
| 85 |
|
| |
| 86 |
|
| typedef struct { |
| 87 |
|
| po_dir_ent *e; |
| 88 |
|
| uint32_t n, cap; |
| 89 |
|
| } po_blockdir; |
| 90 |
|
| |
| 91 |
0 |
| static int po_blockdir_init(po_blockdir *d) { |
| 92 |
0 |
| memset(d, 0, sizeof(*d)); |
| 93 |
0 |
| d->cap = 16; |
| 94 |
0 |
| d->e = (po_dir_ent *)calloc(d->cap, sizeof(po_dir_ent)); |
| 95 |
0 |
| return d->e != NULL; |
| 96 |
|
| } |
| 97 |
|
| |
| 98 |
0 |
| static void po_blockdir_free(po_blockdir *d) { |
| 99 |
0 |
| free(d->e); d->e = NULL; d->n = d->cap = 0; |
| 100 |
0 |
| } |
| 101 |
|
| |
| 102 |
0 |
| static int po_blockdir_add(po_blockdir *d, const po_dir_ent *ent) { |
| 103 |
0 |
▶ | if (d->n == d->cap) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (d->n == d->cap) { |
0 |
0 |
0 |
|
| 104 |
0 |
| uint32_t want = d->cap * 2; |
| 105 |
0 |
| po_dir_ent *ne = (po_dir_ent *)realloc(d->e, want * sizeof(po_dir_ent)); |
| 106 |
0 |
▶ | if (!ne) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!ne) return 0; |
0 |
0 |
0 |
|
| 107 |
0 |
| d->e = ne; d->cap = want; |
| 108 |
|
| } |
| 109 |
0 |
| d->e[d->n++] = *ent; |
| 110 |
0 |
| return 1; |
| 111 |
|
| } |
| 112 |
|
| |
| 113 |
|
| /* THE PRUNE. Given a time range, a stream filter and a search term, which |
| 114 |
|
| * blocks must actually be opened? |
| 115 |
|
| * |
| 116 |
|
| * Three tests in increasing cost order, and the order is the design: |
| 117 |
|
| * 1. the stream - an integer compare |
| 118 |
|
| * 2. the time span - two integer compares, no inflation |
| 119 |
|
| * 3. the bloom - a few hashes over the query's trigrams |
| 120 |
|
| * |
| 121 |
|
| * Only a block surviving all three is decompressed, and then it is matched |
| 122 |
|
| * exactly. `opened` reports how many survived, so a test can assert that the |
| 123 |
|
| * pruning actually pruned rather than trusting that it did. */ |
| 124 |
|
| typedef struct { |
| 125 |
|
| uint32_t considered; |
| 126 |
|
| uint32_t skipped_stream; |
| 127 |
|
| uint32_t skipped_time; |
| 128 |
|
| uint32_t skipped_bloom; |
| 129 |
|
| uint32_t candidates; |
| 130 |
|
| } po_prune_stats; |
| 131 |
|
| |
| 132 |
1252 |
| static int po_block_candidate(const po_dir_ent *e, |
| 133 |
|
| int have_stream, po_u64 stream, |
| 134 |
|
| po_u64 from, po_u64 to, |
| 135 |
|
| const unsigned char *bloom_bits, |
| 136 |
|
| const char *q, size_t qlen, |
| 137 |
|
| po_prune_stats *st) { |
| 138 |
1252 |
▶ | if (st) st->considered++; |
Branch: 1 branch
| Branch | True | False | Total |
| if (st) st->considered++; |
1252 |
0 |
1252 |
|
| 139 |
|
| |
| 140 |
1252 |
▶ | if (have_stream && e->h.stream != stream) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (have_stream && e->h.stream != stream) { |
2 |
1250 |
1252 |
| if (have_stream && e->h.stream != stream) { |
1 |
1 |
2 |
|
| 141 |
1 |
▶ | if (st) st->skipped_stream++; |
Branch: 1 branch
| Branch | True | False | Total |
| if (st) st->skipped_stream++; |
1 |
0 |
1 |
|
| 142 |
1 |
| return 0; |
| 143 |
|
| } |
| 144 |
1251 |
▶ | if (e->h.t_min > to || e->h.t_max < from) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (e->h.t_min > to || e->h.t_max < from) { |
1248 |
3 |
1251 |
| if (e->h.t_min > to || e->h.t_max < from) { |
12 |
1236 |
1248 |
|
| 145 |
15 |
▶ | if (st) st->skipped_time++; |
Branch: 1 branch
| Branch | True | False | Total |
| if (st) st->skipped_time++; |
15 |
0 |
15 |
|
| 146 |
15 |
| return 0; |
| 147 |
|
| } |
| 148 |
1236 |
▶ | if (qlen && bloom_bits && po_bloom_query_usable(qlen)) { |
Branch: 3 branches
| Branch | True | False | Total |
| if (qlen && bloom_bits && po_bloom_query_usable(qlen)) { |
1226 |
10 |
1236 |
| if (qlen && bloom_bits && po_bloom_query_usable(qlen)) { |
1226 |
0 |
1226 |
| if (qlen && bloom_bits && po_bloom_query_usable(qlen)) { |
1218 |
8 |
1226 |
|
| 149 |
1218 |
▶ | if (!po_bloom_may_contain(bloom_bits, e->h.bloom_bits - 1, q, qlen)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_bloom_may_contain(bloom_bits, e->h.bloom_bits - 1, q, qlen)) { |
613 |
605 |
1218 |
|
| 150 |
613 |
▶ | if (st) st->skipped_bloom++; |
Branch: 1 branch
| Branch | True | False | Total |
| if (st) st->skipped_bloom++; |
613 |
0 |
613 |
|
| 151 |
613 |
| return 0; |
| 152 |
|
| } |
| 153 |
|
| } |
| 154 |
623 |
▶ | if (st) st->candidates++; |
Branch: 1 branch
| Branch | True | False | Total |
| if (st) st->candidates++; |
623 |
0 |
623 |
|
| 155 |
623 |
| return 1; |
| 156 |
|
| } |
| 157 |
|
| |
| 158 |
|
| #endif /* PO_LOGIDX_H */ |