⚡️ Как Redis считает миллиарды уникальных значений, почти не тратя память
Есть алгоритм HyperLogLog. Он позволяет примерно понять, сколько уникальных элементов прошло через систему, используя около 12 KB памяти.
Идея простая: Redis не хранит сами элементы.
Он делает так:
- берёт элемент
- считает от него хеш
- часть хеша использует как номер ячейки
- в другой части смотрит, сколько нулей подряд встретилось
- если новое число больше старого - обновляет ячейку
Почему это работает?
Потому что длинная серия нулей в хеше встречается редко.
Например:
- 1 ноль подряд - довольно часто
- 5 нулей подряд - уже реже
- 10 нулей подряд - примерно шанс 1 к 1024
- 20 нулей подряд - совсем редкое событие
Если Redis увидел очень редкий паттерн, значит через него, скорее всего, прошло много разных элементов.
В Redis используется 16 384 маленьких счётчика. Каждый хранит максимальную «редкость», которую видел для своей группы элементов.
Потом Redis объединяет эти значения математикой и получает оценку уникальных элементов.
Не точное число, а очень близкую оценку.
Главный прикол HyperLogLog:
он может обработать хоть миллионы, хоть миллиарды значений, но память почти не растёт.
Именно поэтому Redis умеет считать уникальных пользователей, IP, запросы или события без огромных таблиц и списков.
