| 1 |
|
| /* po_bloom.h - a trigram bloom filter, one per log block. |
| 2 |
|
| * |
| 3 |
|
| * The problem: a log search must not decompress every block the label filter |
| 4 |
|
| * leaves. The classic answers are both wrong here. |
| 5 |
|
| * |
| 6 |
|
| * - Index every term (the Elasticsearch shape). The index approaches the |
| 7 |
|
| * size of the data and a high-cardinality field inflates it without |
| 8 |
|
| * bound. |
| 9 |
|
| * - Index nothing and scan (the plain Loki shape). Correct, and it |
| 10 |
|
| * decompresses everything the labels leave. |
| 11 |
|
| * |
| 12 |
|
| * This filter is the third option: it stores NO TEXT and answers exactly one |
| 13 |
|
| * question, "can this block possibly contain that substring". A block whose |
| 14 |
|
| * answer is no is skipped unopened. A block whose answer is yes is |
| 15 |
|
| * decompressed and matched EXACTLY, so a false positive costs one |
| 16 |
|
| * decompression and never a wrong answer. |
| 17 |
|
| * |
| 18 |
|
| * THE ASYMMETRY IS THE WHOLE DESIGN. |
| 19 |
|
| * |
| 20 |
|
| * A false positive = a wasted decompression. |
| 21 |
|
| * A false negative = A LOST LOG LINE. |
| 22 |
|
| * |
| 23 |
|
| * There is no acceptable rate of the second, so the bit count is derived from |
| 24 |
|
| * the measured distinct-trigram count rather than picked, and t/0041-bloom.t |
| 25 |
|
| * asserts zero false negatives over a generated corpus. That test is the |
| 26 |
|
| * reason this file exists in this shape. |
| 27 |
|
| * |
| 28 |
|
| * (Search::Trigram was the obvious candidate and is not usable: sg_abi.h:66-69 |
| 29 |
|
| * copies each document's text INTO the index and the table has no serialise |
| 30 |
|
| * at all, so it is an in-memory document store rather than something a sealed |
| 31 |
|
| * segment can carry.) |
| 32 |
|
| */ |
| 33 |
|
| #ifndef PO_BLOOM_H |
| 34 |
|
| #define PO_BLOOM_H |
| 35 |
|
| |
| 36 |
|
| #include "punk_observe/po_compat.h" |
| 37 |
|
| #include "punk_observe/po_hash.h" |
| 38 |
|
| |
| 39 |
|
| /* Two independent hashes, derived from one 128-bit murmur by taking its two |
| 40 |
|
| * halves. Kirsch-Mitzenmacher: h_i = h1 + i*h2 gives k hashes from two with no |
| 41 |
|
| * measurable loss, so this costs one hash per trigram rather than k. */ |
| 42 |
|
| #define PO_BLOOM_K 4 |
| 43 |
|
| |
| 44 |
|
| typedef struct { |
| 45 |
|
| unsigned char *bits; |
| 46 |
|
| uint32_t nbits; /* always a power of two, so masking works */ |
| 47 |
|
| uint32_t mask; |
| 48 |
|
| uint32_t added; /* trigrams inserted, for the sizing report */ |
| 49 |
|
| } po_bloom; |
| 50 |
|
| |
| 51 |
|
| /* Size from the expected distinct-trigram count and a target false-positive |
| 52 |
|
| * rate. The optimal m/n for rate p is -ln(p)/(ln2)^2; for p = 1% that is |
| 53 |
|
| * about 9.6 bits per element, which this rounds up to the next power of two |
| 54 |
|
| * so the index can mask instead of dividing. */ |
| 55 |
242 |
| static uint32_t po_bloom_bits_for(uint32_t n) { |
| 56 |
242 |
| po_u64 want = (po_u64)n * 10 + 64; /* ~10 bits each, plus a floor */ |
| 57 |
242 |
| uint32_t p = 64; |
| 58 |
2027 |
▶ | while ((po_u64)p < want && p < (1u << 30)) p <<= 1; |
Branch: 2 branches
| Branch | True | False | Total |
| while ((po_u64)p < want && p < (1u << 30)) p <<= 1; |
1785 |
242 |
2027 |
| while ((po_u64)p < want && p < (1u << 30)) p <<= 1; |
1785 |
0 |
1785 |
|
| 59 |
242 |
| return p; |
| 60 |
|
| } |
| 61 |
|
| |
| 62 |
242 |
| static int po_bloom_init(po_bloom *b, uint32_t expect) { |
| 63 |
242 |
| memset(b, 0, sizeof(*b)); |
| 64 |
242 |
| b->nbits = po_bloom_bits_for(expect); |
| 65 |
242 |
| b->mask = b->nbits - 1; |
| 66 |
242 |
| b->bits = (unsigned char *)calloc((b->nbits + 7) / 8, 1); |
| 67 |
242 |
| return b->bits != NULL; |
| 68 |
|
| } |
| 69 |
|
| |
| 70 |
242 |
| static void po_bloom_free(po_bloom *b) { free(b->bits); b->bits = NULL; } |
| 71 |
|
| |
| 72 |
1293917 |
| static void po_bloom_set(po_bloom *b, const char *p, size_t len) { |
| 73 |
1293917 |
| po_h128 h = po_murmur3_128(p, len, 0); |
| 74 |
|
| int i; |
| 75 |
6469585 |
▶ | for (i = 0; i < PO_BLOOM_K; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < PO_BLOOM_K; i++) { |
5175668 |
1293917 |
6469585 |
|
| 76 |
5175668 |
| uint32_t bit = (uint32_t)((h.lo + (po_u64)i * h.hi) & b->mask); |
| 77 |
5175668 |
| b->bits[bit >> 3] |= (unsigned char)(1 << (bit & 7)); |
| 78 |
|
| } |
| 79 |
1293917 |
| b->added++; |
| 80 |
1293917 |
| } |
| 81 |
|
| |
| 82 |
183050 |
| static int po_bloom_test_raw(const unsigned char *bits, uint32_t mask, |
| 83 |
|
| const char *p, size_t len) { |
| 84 |
183050 |
| po_h128 h = po_murmur3_128(p, len, 0); |
| 85 |
|
| int i; |
| 86 |
903572 |
▶ | for (i = 0; i < PO_BLOOM_K; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < PO_BLOOM_K; i++) { |
723628 |
179944 |
903572 |
|
| 87 |
723628 |
| uint32_t bit = (uint32_t)((h.lo + (po_u64)i * h.hi) & mask); |
| 88 |
723628 |
▶ | if (!(bits[bit >> 3] & (1 << (bit & 7)))) return 0; /* definitely not */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (!(bits[bit >> 3] & (1 << (bit & 7)))) return 0; /* definitely not */ |
3106 |
720522 |
723628 |
|
| 89 |
|
| } |
| 90 |
179944 |
| return 1; /* possibly */ |
| 91 |
|
| } |
| 92 |
|
| |
| 93 |
0 |
| static int po_bloom_test(const po_bloom *b, const char *p, size_t len) { |
| 94 |
0 |
| return po_bloom_test_raw(b->bits, b->mask, p, len); |
| 95 |
|
| } |
| 96 |
|
| |
| 97 |
|
| /* ---- trigrams ------------------------------------------------------------- |
| 98 |
|
| * |
| 99 |
|
| * BYTE trigrams, not character ones. A trigram may split a UTF-8 codepoint, |
| 100 |
|
| * which is harmless BECAUSE the filter only ever prunes and the surviving |
| 101 |
|
| * block is matched exactly - and because the query is split by the identical |
| 102 |
|
| * rule, so the same split happens on both sides. Documented here so nobody |
| 103 |
|
| * later "fixes" it into a codepoint-aware version that no longer matches what |
| 104 |
|
| * was indexed. |
| 105 |
|
| * |
| 106 |
|
| * Case folding is applied at BOTH index and query time. Folding only at query |
| 107 |
|
| * time would skip blocks containing the term in another case, which is a |
| 108 |
|
| * false negative wearing a disguise. |
| 109 |
|
| */ |
| 110 |
8486848 |
| static unsigned char po_fold(unsigned char c) { |
| 111 |
8486848 |
▶ | return (c >= 'A' && c <= 'Z') ? (unsigned char)(c - 'A' + 'a') : c; |
Branch: 2 branches
| Branch | True | False | Total |
| return (c >= 'A' && c <= 'Z') ? (unsigned char)(c - 'A' + 'a') : c; |
4910266 |
3576582 |
8486848 |
| return (c >= 'A' && c <= 'Z') ? (unsigned char)(c - 'A' + 'a') : c; |
445142 |
4465124 |
4910266 |
|
| 112 |
|
| } |
| 113 |
|
| |
| 114 |
|
| typedef void (*po_trigram_cb)(void *ud, const char *tri); |
| 115 |
|
| |
| 116 |
180050 |
| static void po_trigrams(const char *p, size_t len, po_trigram_cb cb, void *ud) { |
| 117 |
|
| size_t i; |
| 118 |
|
| char t[3]; |
| 119 |
180050 |
▶ | if (len < 3) return; /* see po_bloom_query_usable */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (len < 3) return; /* see po_bloom_query_usable */ |
0 |
180050 |
180050 |
|
| 120 |
2972294 |
▶ | for (i = 0; i + 3 <= len; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i + 3 <= len; i++) { |
2792244 |
180050 |
2972294 |
|
| 121 |
2792244 |
| t[0] = (char)po_fold((unsigned char)p[i]); |
| 122 |
2792244 |
| t[1] = (char)po_fold((unsigned char)p[i + 1]); |
| 123 |
2792244 |
| t[2] = (char)po_fold((unsigned char)p[i + 2]); |
| 124 |
2792244 |
| cb(ud, t); |
| 125 |
|
| } |
| 126 |
|
| } |
| 127 |
|
| |
| 128 |
1293917 |
| static void po_bloom_add_cb(void *ud, const char *tri) { |
| 129 |
1293917 |
| po_bloom_set((po_bloom *)ud, tri, 3); |
| 130 |
1293917 |
| } |
| 131 |
|
| |
| 132 |
242 |
| static void po_bloom_add_text(po_bloom *b, const char *p, size_t len) { |
| 133 |
242 |
| po_trigrams(p, len, po_bloom_add_cb, b); |
| 134 |
242 |
| } |
| 135 |
|
| |
| 136 |
|
| /* Count distinct trigrams, so a block can be sized from what it actually |
| 137 |
|
| * holds rather than from a guess. Uses a small open set; blocks are ~1MB so |
| 138 |
|
| * the distinct count is bounded well under 2^24. */ |
| 139 |
|
| typedef struct { unsigned char seen[1 << 21]; uint32_t n; } po_tri_count; |
| 140 |
|
| |
| 141 |
1293917 |
| static void po_tri_count_cb(void *ud, const char *tri) { |
| 142 |
1293917 |
| po_tri_count *c = (po_tri_count *)ud; |
| 143 |
1293917 |
| uint32_t h = po_hash32(tri, 3) & ((1u << 24) - 1); |
| 144 |
1293917 |
| uint32_t byte = h >> 3; |
| 145 |
1293917 |
| unsigned char m = (unsigned char)(1 << (h & 7)); |
| 146 |
1293917 |
▶ | if (!(c->seen[byte] & m)) { c->seen[byte] |= m; c->n++; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!(c->seen[byte] & m)) { c->seen[byte] |= m; c->n++; } |
195162 |
1098755 |
1293917 |
|
| 147 |
1293917 |
| } |
| 148 |
|
| |
| 149 |
|
| /* CAN THIS QUERY USE THE FILTER AT ALL? |
| 150 |
|
| * |
| 151 |
|
| * A query shorter than three bytes has NO trigrams, so testing it would test |
| 152 |
|
| * nothing and "no trigram matched" would wrongly prune every block. A search |
| 153 |
|
| * for "ok" must fall through to scanning the candidates, not silently return |
| 154 |
|
| * empty. This is the bug that would make short searches quietly wrong, so it |
| 155 |
|
| * is a named predicate rather than an implicit length check somewhere. */ |
| 156 |
180801 |
| static int po_bloom_query_usable(size_t qlen) { return qlen >= 3; } |
| 157 |
|
| |
| 158 |
|
| /* Test every trigram of the query. ANY absent trigram means the block cannot |
| 159 |
|
| * contain the query. */ |
| 160 |
|
| typedef struct { const unsigned char *bits; uint32_t mask; int possible; } |
| 161 |
|
| po_bloom_probe; |
| 162 |
|
| |
| 163 |
204410 |
| static void po_bloom_probe_cb(void *ud, const char *tri) { |
| 164 |
204410 |
| po_bloom_probe *p = (po_bloom_probe *)ud; |
| 165 |
204410 |
▶ | if (!p->possible) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!p->possible) return; |
21360 |
183050 |
204410 |
|
| 166 |
183050 |
▶ | if (!po_bloom_test_raw(p->bits, p->mask, tri, 3)) p->possible = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_bloom_test_raw(p->bits, p->mask, tri, 3)) p->possible = 0; |
3106 |
179944 |
183050 |
|
| 167 |
|
| } |
| 168 |
|
| |
| 169 |
179571 |
| static int po_bloom_may_contain(const unsigned char *bits, uint32_t mask, |
| 170 |
|
| const char *q, size_t qlen) { |
| 171 |
|
| po_bloom_probe p; |
| 172 |
179571 |
▶ | if (!po_bloom_query_usable(qlen)) return 1; /* cannot prune: assume yes */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_bloom_query_usable(qlen)) return 1; /* cannot prune: assume yes */ |
5 |
179566 |
179571 |
|
| 173 |
179566 |
| p.bits = bits; p.mask = mask; p.possible = 1; |
| 174 |
179566 |
| po_trigrams(q, qlen, po_bloom_probe_cb, &p); |
| 175 |
179566 |
| return p.possible; |
| 176 |
|
| } |
| 177 |
|
| |
| 178 |
|
| /* The exact match that runs AFTER the filter says "possible". Case-folded to |
| 179 |
|
| * agree with the filter, and a plain byte search: the filter prunes, this |
| 180 |
|
| * decides. */ |
| 181 |
1783 |
| static const char *po_memfind(const char *hay, size_t hn, |
| 182 |
|
| const char *needle, size_t nn) { |
| 183 |
|
| size_t i, j; |
| 184 |
1783 |
▶ | if (nn == 0 || nn > hn) return NULL; |
Branch: 2 branches
| Branch | True | False | Total |
| if (nn == 0 || nn > hn) return NULL; |
1783 |
0 |
1783 |
| if (nn == 0 || nn > hn) return NULL; |
240 |
1543 |
1783 |
|
| 185 |
52376 |
▶ | for (i = 0; i + nn <= hn; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i + nn <= hn; i++) { |
51251 |
1125 |
52376 |
|
| 186 |
55476 |
▶ | for (j = 0; j < nn; j++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (j = 0; j < nn; j++) |
55058 |
418 |
55476 |
|
| 187 |
110116 |
▶ | if (po_fold((unsigned char)hay[i + j]) != |
Branch: 1 branch
| Branch | True | False | Total |
| if (po_fold((unsigned char)hay[i + j]) != |
50833 |
4225 |
55058 |
|
| 188 |
105891 |
| po_fold((unsigned char)needle[j])) break; |
| 189 |
51251 |
▶ | if (j == nn) return hay + i; |
Branch: 1 branch
| Branch | True | False | Total |
| if (j == nn) return hay + i; |
418 |
50833 |
51251 |
|
| 190 |
|
| } |
| 191 |
1125 |
| return NULL; |
| 192 |
|
| } |
| 193 |
|
| |
| 194 |
|
| #endif /* PO_BLOOM_H */ |