| 1 | package analytics |
| 2 | |
| 3 | // TopKSize bounds a top-keys summary (pages, referers, events) per app |
| 4 | // per day per box (spec §3.3). Misra–Gries: exact below the cap, a lower |
| 5 | // bound within the summary's error above it, mergeable, with the evicted |
| 6 | // mass kept in OtherKey so totals are conserved. |
| 7 | const TopKSize = 500 |
| 8 | |
| 9 | // OtherKey is the fold-over row for keys beyond the cap. |
| 10 | const OtherKey = "_other" |
| 11 | |
| 12 | // MaxKeyLen caps a key's bytes. |
| 13 | const MaxKeyLen = 256 |
| 14 | |
| 15 | // TopK is a Misra–Gries summary with TopKSize counters. |
| 16 | type TopK struct { |
| 17 | counts map[string]int64 |
| 18 | other int64 |
| 19 | } |
| 20 | |
| 21 | // NewTopK returns an empty summary. |
| 22 | func NewTopK() *TopK { return &TopK{counts: make(map[string]int64)} } |
| 23 | |
| 24 | // Add counts n occurrences of key. When the summary is full and key is |
| 25 | // new, every counter is decremented by the smallest amount that frees a |
| 26 | // slot, and the decremented mass moves to other. |
| 27 | func (t *TopK) Add(key string, n int64) { |
| 28 | if len(key) > MaxKeyLen { |
| 29 | key = key[:MaxKeyLen] |
| 30 | } |
| 31 | if n <= 0 { |
| 32 | return |
| 33 | } |
| 34 | if _, ok := t.counts[key]; ok || len(t.counts) < TopKSize { |
| 35 | t.counts[key] += n |
| 36 | return |
| 37 | } |
| 38 | // Full and new: take the smallest counter as the decrement. |
| 39 | min := int64(-1) |
| 40 | for _, v := range t.counts { |
| 41 | if min < 0 || v < min { |
| 42 | min = v |
| 43 | } |
| 44 | } |
| 45 | if n <= min { |
| 46 | t.other += n |
| 47 | return |
| 48 | } |
| 49 | for k, v := range t.counts { |
| 50 | if v <= min { |
| 51 | delete(t.counts, k) |
| 52 | t.other += v |
| 53 | } else { |
| 54 | t.counts[k] = v - min |
| 55 | t.other += min |
| 56 | } |
| 57 | } |
| 58 | t.counts[key] = n - min |
| 59 | t.other += min |
| 60 | } |
| 61 | |
| 62 | // Merge folds o into t: counters add, other adds, then t re-folds to the |
| 63 | // cap so a merge of two full summaries stays bounded. |
| 64 | func (t *TopK) Merge(o *TopK) { |
| 65 | merged := NewTopK() |
| 66 | merged.other = t.other + o.other |
| 67 | sum := make(map[string]int64, len(t.counts)+len(o.counts)) |
| 68 | for k, v := range t.counts { |
| 69 | sum[k] += v |
| 70 | } |
| 71 | for k, v := range o.counts { |
| 72 | sum[k] += v |
| 73 | } |
| 74 | for k, v := range sum { // Add re-applies the cap |
| 75 | merged.Add(k, v) |
| 76 | } |
| 77 | t.counts, t.other = merged.counts, merged.other |
| 78 | } |
| 79 | |
| 80 | // Fold returns the counters plus OtherKey when any mass fell over. |
| 81 | func (t *TopK) Fold() map[string]int64 { |
| 82 | out := make(map[string]int64, len(t.counts)+1) |
| 83 | for k, v := range t.counts { |
| 84 | out[k] = v |
| 85 | } |
| 86 | if t.other > 0 { |
| 87 | out[OtherKey] = t.other |
| 88 | } |
| 89 | return out |
| 90 | } |
| 91 | |
| 92 | // TopKFrom rebuilds a summary from a folded map (the day file's shape). |
| 93 | func TopKFrom(m map[string]int64) *TopK { |
| 94 | t := NewTopK() |
| 95 | for k, v := range m { |
| 96 | if k == OtherKey { |
| 97 | t.other += v |
| 98 | continue |
| 99 | } |
| 100 | t.Add(k, v) |
| 101 | } |
| 102 | return t |
| 103 | } |
| 104 | |
| 105 | // Approximate reports whether counters are lower bounds (mass fell over). |
| 106 | func (t *TopK) Approximate() bool { return t.other > 0 } |
| 107 | |
amadan