| 1 | // Package analytics is the pure half of the Analytics tab (spec |
| 2 | // 2026-09-07-errors-and-analytics-design.md §3.3): the visitor and top-key |
| 3 | // sketches, the in-memory meter the edge feeds, the day-file wire shape |
| 4 | // and its idempotent CAS merge, the daily salt, the bot list and the |
| 5 | // cross-box range read. internal/edge observes, internal/host flushes, |
| 6 | // internal/console reads — the applog/apperr split. |
| 7 | package analytics |
| 8 | |
| 9 | import ( |
| 10 | "encoding/base64" |
| 11 | "errors" |
| 12 | "math" |
| 13 | "math/bits" |
| 14 | ) |
| 15 | |
| 16 | // HLLPrecision is the register-index width: 2^11 registers, 2 KB, ~2.3% |
| 17 | // standard error (spec §3.3). One sketch per app per day per box. |
| 18 | const HLLPrecision = 11 |
| 19 | const hllRegisters = 1 << HLLPrecision |
| 20 | |
| 21 | // HLL is a HyperLogLog cardinality sketch over 64-bit hashes. |
| 22 | type HLL struct{ reg [hllRegisters]uint8 } |
| 23 | |
| 24 | // mix64 is MurmurHash3's fmix64 finalizer. Add uses it to avalanche the |
| 25 | // incoming hash before slicing out the register index and run bits: the |
| 26 | // register index is the hash's top HLLPrecision bits, and callers' hash |
| 27 | // functions (FNV-1a included — see h64 in hll_test.go) do not reliably |
| 28 | // mix entropy into their high bits, especially for short, sequential |
| 29 | // inputs sharing a common prefix ("v0".."v99999"), which otherwise |
| 30 | // starves most registers and skews Count. |
| 31 | func mix64(x uint64) uint64 { |
| 32 | x ^= x >> 33 |
| 33 | x *= 0xff51afd7ed558ccd |
| 34 | x ^= x >> 33 |
| 35 | x *= 0xc4ceb9fe1a85ec53 |
| 36 | x ^= x >> 33 |
| 37 | return x |
| 38 | } |
| 39 | |
| 40 | // Add records one hashed element. |
| 41 | func (h *HLL) Add(hash uint64) { |
| 42 | hash = mix64(hash) |
| 43 | idx := hash >> (64 - HLLPrecision) |
| 44 | rest := hash<<HLLPrecision | 1<<(HLLPrecision-1) // guard bit bounds the run |
| 45 | rank := uint8(bits.LeadingZeros64(rest)) + 1 |
| 46 | if rank > h.reg[idx] { |
| 47 | h.reg[idx] = rank |
| 48 | } |
| 49 | } |
| 50 | |
| 51 | // Merge folds o into h by register max — the union of the two sets. |
| 52 | func (h *HLL) Merge(o *HLL) { |
| 53 | for i := range h.reg { |
| 54 | if o.reg[i] > h.reg[i] { |
| 55 | h.reg[i] = o.reg[i] |
| 56 | } |
| 57 | } |
| 58 | } |
| 59 | |
| 60 | // Empty reports whether nothing was added. |
| 61 | func (h *HLL) Empty() bool { |
| 62 | for _, r := range h.reg { |
| 63 | if r != 0 { |
| 64 | return false |
| 65 | } |
| 66 | } |
| 67 | return true |
| 68 | } |
| 69 | |
| 70 | // Count estimates the cardinality (Flajolet et al. 2007 with the small- |
| 71 | // range linear-counting correction). |
| 72 | func (h *HLL) Count() float64 { |
| 73 | m := float64(hllRegisters) |
| 74 | alpha := 0.7213 / (1 + 1.079/m) |
| 75 | var sum float64 |
| 76 | zeros := 0 |
| 77 | for _, r := range h.reg { |
| 78 | sum += math.Pow(2, -float64(r)) |
| 79 | if r == 0 { |
| 80 | zeros++ |
| 81 | } |
| 82 | } |
| 83 | est := alpha * m * m / sum |
| 84 | if est <= 2.5*m && zeros > 0 { |
| 85 | est = m * math.Log(m/float64(zeros)) |
| 86 | } |
| 87 | return est |
| 88 | } |
| 89 | |
| 90 | const hllVersion = 1 |
| 91 | |
| 92 | // Encode renders the sketch as base64 of a version byte plus the registers. |
| 93 | func (h *HLL) Encode() string { |
| 94 | b := make([]byte, 1+hllRegisters) |
| 95 | b[0] = hllVersion |
| 96 | copy(b[1:], h.reg[:]) |
| 97 | return base64.StdEncoding.EncodeToString(b) |
| 98 | } |
| 99 | |
| 100 | // DecodeHLL parses Encode's output; "" is an empty sketch, an unknown |
| 101 | // version is an error (a future shape this build cannot read). |
| 102 | func DecodeHLL(s string) (*HLL, error) { |
| 103 | h := &HLL{} |
| 104 | if s == "" { |
| 105 | return h, nil |
| 106 | } |
| 107 | b, err := base64.StdEncoding.DecodeString(s) |
| 108 | if err != nil { |
| 109 | return nil, err |
| 110 | } |
| 111 | if len(b) != 1+hllRegisters || b[0] != hllVersion { |
| 112 | return nil, errors.New("analytics: unknown visitors sketch version or size") |
| 113 | } |
| 114 | copy(h.reg[:], b[1:]) |
| 115 | return h, nil |
| 116 | } |
| 117 | |
amadan