| 1 |
|
| /* po_merge.h - the k-way merge that repays phase 4's per-worker writing. |
| 2 |
|
| * |
| 3 |
|
| * Phase 4 accepted N segments per block from N workers, because the |
| 4 |
|
| * alternative was a dedicated writer serialising every ingest. The bill comes |
| 5 |
|
| * due here, once, off the hot path: N sorted runs become one. |
| 6 |
|
| * |
| 7 |
|
| * A loser tree would beat a linear scan of the heads above roughly sixteen |
| 8 |
|
| * runs. N is the WORKER COUNT - four, eight, sixteen - so the linear scan |
| 9 |
|
| * wins on cache behaviour and is a tenth of the code. If somebody ever runs |
| 10 |
|
| * this with sixty-four workers, that is the moment to change it, with the |
| 11 |
|
| * measurement that justified it. |
| 12 |
|
| * |
| 13 |
|
| * THE MERGE IS DETERMINISTIC. The same inputs produce a byte-identical |
| 14 |
|
| * output, which makes a regression a diff rather than an investigation - and |
| 15 |
|
| * it means a re-compaction after a crash produces the same segment rather |
| 16 |
|
| * than a different-but-equivalent one. |
| 17 |
|
| */ |
| 18 |
|
| #ifndef PO_MERGE_H |
| 19 |
|
| #define PO_MERGE_H |
| 20 |
|
| |
| 21 |
|
| #include "punk_observe/po_compat.h" |
| 22 |
|
| #include "punk_observe/po_rec.h" |
| 23 |
|
| |
| 24 |
|
| #define PO_MERGE_MAX_RUNS 64 |
| 25 |
|
| |
| 26 |
|
| typedef struct { |
| 27 |
|
| const po_rec *rec; |
| 28 |
|
| size_t n, i; |
| 29 |
|
| } po_run; |
| 30 |
|
| |
| 31 |
|
| typedef struct { |
| 32 |
|
| po_run run[PO_MERGE_MAX_RUNS]; |
| 33 |
|
| int nrun; |
| 34 |
|
| po_u64 emitted; |
| 35 |
|
| po_u64 duplicates; |
| 36 |
|
| } po_merge; |
| 37 |
|
| |
| 38 |
16 |
| static void po_merge_init(po_merge *m) { memset(m, 0, sizeof(*m)); } |
| 39 |
|
| |
| 40 |
68 |
| static int po_merge_add_run(po_merge *m, const po_rec *r, size_t n) { |
| 41 |
68 |
▶ | if (m->nrun >= PO_MERGE_MAX_RUNS) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (m->nrun >= PO_MERGE_MAX_RUNS) return 0; |
0 |
68 |
68 |
|
| 42 |
68 |
| m->run[m->nrun].rec = r; |
| 43 |
68 |
| m->run[m->nrun].n = n; |
| 44 |
68 |
| m->run[m->nrun].i = 0; |
| 45 |
68 |
| m->nrun++; |
| 46 |
68 |
| return 1; |
| 47 |
|
| } |
| 48 |
|
| |
| 49 |
|
| /* The ordering. Time first, then a TOTAL tiebreak - without one the merge is |
| 50 |
|
| * unstable and two runs of the same inputs differ. */ |
| 51 |
18494 |
| static int po_rec_before(const po_rec *a, const po_rec *b) { |
| 52 |
18494 |
▶ | if (a->t_unix_nano != b->t_unix_nano) |
Branch: 1 branch
| Branch | True | False | Total |
| if (a->t_unix_nano != b->t_unix_nano) |
18359 |
135 |
18494 |
|
| 53 |
18359 |
| return a->t_unix_nano < b->t_unix_nano; |
| 54 |
135 |
▶ | if (a->series != b->series) return a->series < b->series; |
Branch: 1 branch
| Branch | True | False | Total |
| if (a->series != b->series) return a->series < b->series; |
118 |
17 |
135 |
|
| 55 |
17 |
▶ | if (a->kind != b->kind) return a->kind < b->kind; |
Branch: 1 branch
| Branch | True | False | Total |
| if (a->kind != b->kind) return a->kind < b->kind; |
1 |
16 |
17 |
|
| 56 |
16 |
▶ | if (a->span_id != b->span_id) return a->span_id < b->span_id; |
Branch: 1 branch
| Branch | True | False | Total |
| if (a->span_id != b->span_id) return a->span_id < b->span_id; |
0 |
16 |
16 |
|
| 57 |
16 |
| return 0; |
| 58 |
|
| } |
| 59 |
|
| |
| 60 |
20259 |
| static int po_rec_same(const po_rec *a, const po_rec *b) { |
| 61 |
20259 |
| return a->t_unix_nano == b->t_unix_nano |
| 62 |
135 |
▶ | && a->series == b->series |
Branch: 1 branch
| Branch | True | False | Total |
| && a->series == b->series |
17 |
118 |
135 |
|
| 63 |
17 |
▶ | && a->kind == b->kind |
Branch: 1 branch
| Branch | True | False | Total |
| && a->kind == b->kind |
16 |
1 |
17 |
|
| 64 |
16 |
▶ | && a->span_id == b->span_id |
Branch: 1 branch
| Branch | True | False | Total |
| && a->span_id == b->span_id |
16 |
0 |
16 |
|
| 65 |
16 |
▶ | && a->trace_id_hi == b->trace_id_hi |
Branch: 1 branch
| Branch | True | False | Total |
| && a->trace_id_hi == b->trace_id_hi |
16 |
0 |
16 |
|
| 66 |
20394 |
▶ | && a->trace_id_lo == b->trace_id_lo; |
Branch: 2 branches
| Branch | True | False | Total |
| && a->trace_id_lo == b->trace_id_lo; |
135 |
20124 |
20259 |
| && a->trace_id_lo == b->trace_id_lo; |
16 |
0 |
16 |
|
| 67 |
|
| } |
| 68 |
|
| |
| 69 |
|
| /* Pull the next record. Returns NULL when every run is drained. |
| 70 |
|
| * |
| 71 |
|
| * DUPLICATES ARE COLLAPSED HERE. Phase 4's crash window - a WAL consumed into |
| 72 |
|
| * a segment, then re-consumed after a crash between rename and unlink - |
| 73 |
|
| * leaves the same records twice. Making the write path idempotent would cost |
| 74 |
|
| * a fsync and a lookup per batch on the hot path; collapsing on the read side |
| 75 |
|
| * costs one comparison in a merge that is already comparing. */ |
| 76 |
1829 |
| static const po_rec *po_merge_next(po_merge *m) { |
| 77 |
1829 |
| int i, best = -1; |
| 78 |
|
| const po_rec *out; |
| 79 |
|
| |
| 80 |
|
| for (;;) { |
| 81 |
1829 |
| best = -1; |
| 82 |
22500 |
▶ | for (i = 0; i < m->nrun; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < m->nrun; i++) { |
20671 |
1829 |
22500 |
|
| 83 |
20671 |
▶ | if (m->run[i].i >= m->run[i].n) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (m->run[i].i >= m->run[i].n) continue; |
364 |
20307 |
20671 |
|
| 84 |
38801 |
| if (best < 0 || |
| 85 |
18494 |
| po_rec_before(&m->run[i].rec[m->run[i].i], |
| 86 |
18494 |
| &m->run[best].rec[m->run[best].i])) |
| 87 |
4204 |
| best = i; |
| 88 |
|
| } |
| 89 |
1829 |
▶ | if (best < 0) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (best < 0) return NULL; |
16 |
1813 |
1829 |
|
| 90 |
|
| |
| 91 |
1813 |
| out = &m->run[best].rec[m->run[best].i]; |
| 92 |
1813 |
| m->run[best].i++; |
| 93 |
|
| |
| 94 |
|
| /* Drain any identical record from the other runs. */ |
| 95 |
|
| { |
| 96 |
1813 |
| int dropped = 0; |
| 97 |
22416 |
▶ | for (i = 0; i < m->nrun; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < m->nrun; i++) { |
20603 |
1813 |
22416 |
|
| 98 |
40878 |
| while (m->run[i].i < m->run[i].n && |
| 99 |
20259 |
| po_rec_same(&m->run[i].rec[m->run[i].i], out)) { |
| 100 |
16 |
| m->run[i].i++; |
| 101 |
16 |
| dropped++; |
| 102 |
|
| } |
| 103 |
|
| } |
| 104 |
1813 |
| m->duplicates += (po_u64)dropped; |
| 105 |
|
| } |
| 106 |
1813 |
| m->emitted++; |
| 107 |
1813 |
| return out; |
| 108 |
|
| } |
| 109 |
|
| } |
| 110 |
|
| |
| 111 |
|
| #endif /* PO_MERGE_H */ |