Golang news

📌 HyperLogLog на Go простыми словами Redis может примерно считать уникальные значения, почти не храня сами значения. Идея такая: - берём строку - считаем от неё хеш - первые биты выбирают ячейку - остальные биты проверяем на количество нулей подряд - чем длиннее серия нулей, тем более редкое событие мы увидели - редкие события намекают, что элементов прошло много Минимальный пример на Go:

package main

import (
 "fmt"
 "hash/fnv"
 "math/bits"
)

const registersCount = 16

type HyperLogLog struct {
 registers [registersCount]uint8
}

func hash64(s string) uint64 {
 h := fnv.New64a()
 _, _ = h.Write([]byte(s))
 return h.Sum64()
}

func (hll *HyperLogLog) Add(value string) {
 hash := hash64(value)

 // первые 4 бита выбирают регистр: 2^4 = 16
 index := hash >> 60

 // остальные биты используем для поиска серии нулей
 rest := hash << 4

 // сколько нулей подряд в начале
 zeros := uint8(bits.LeadingZeros64(rest) + 1)

 if zeros > hll.registers[index] {
  hll.registers[index] = zeros
 }
}

func main() {
 hll := HyperLogLog{}

 values := []string{
  "user_1",
  "user_2",
  "user_3",
  "user_1",
  "user_2",
  "user_4",
  "user_5",
 }

 for _, v := range values {
  hll.Add(v)
 }

 fmt.Println(hll.registers)
}

Это не полноценный Redis HyperLogLog, а понятная учебная версия. Что тут важно: • дубликаты дают тот же хеш • один и тот же хеш попадает в тот же регистр • регистр хранит только максимум найденных нулей • сами user_1, user_2, user_3 не сохраняются • память остаётся почти постоянной В Redis всё серьёзнее: там 16 384 регистра, аккуратная математика для оценки cardinality и поправки на маленькие и большие значения.