Алгоритъмът използва вероятности и хеш-функции, за да оценява уникални посещения с минимална памет

Оценяването на броя уникални посетители на голям уебсайт може да се извърши с изненадващо малко памет – едва 12 KB за 100 милиона потребители. Това става възможно благодарение на алгоритъма HyperLogLog, който вместо да съхранява всеки идентификатор, използва статистически методи, за да оцени общия брой. За сравнение, традиционните подходи изискват стотици мегабайти за същия обем данни.

В основата на HyperLogLog стои наблюдението, че редките събития могат да подскажат мащаба на цялото множество. Ако хвърляме монета, вероятността да се паднат десет езита подред е една на 1024. Колкото по-дълга е поредицата от еднакви страни, толкова по-голям е вероятният брой опити. Алгоритъмът прилага същия принцип към цифрови данни, като прекарва всеки потребителски идентификатор през хеш-функция и следи най-дългата последователност от нули в началото на получения битов низ.

Тази стратегия позволява повторните посещения да не се броят многократно, защото хеш-функцията връща един и същ резултат за един и същ идентификатор. За да се намали влиянието на случайността, HyperLogLog разделя потока от данни на множество групи и комбинира техните резултати чрез математическа формула.

Икономия на памет и точност

Реализацията на HyperLogLog в Redis използва 16 384 регистъра, които заемат около 12 KB. Според документацията на Redis стандартната относителна грешка е приблизително 0,81%. За много аналитични задачи такава точност е напълно достатъчна. За сравнение, съхраняването на 100 милиона идентификатора по 8 байта всеки би заело 800 MB само за самите стойности, без допълнителната памет за индексиране и проверка за дубликати.

Алгоритъмът е особено полезен и при обединяване на статистики от множество сървъри. Всеки сървър може да изчисли приблизителния брой уникални посетители, а след това резултатите се комбинират, без да се налага събиране на огромна обща база от идентификатори. По същия начин може да се оцени седмична аудитория от дневни броячи, без да се броят повторно едни и същи хора.

Приложения и ограничения

HyperLogLog отдавна се използва в популярни услуги. Google прилага подобрена версия, наречена HyperLogLog++, в Google Analytics 4 за оценка на броя потребители и сесии. Поради това някои показатели за аудиторията в Google Analytics могат леко да се различават от точните стойности. Алгоритъмът е подходящ и за преброяване на уникални търсения, анализ на мрежови събития и оценка на различните IP адреси, свързващи се със сървър.

Алгоритъмът е представен през 2007 г. от математиците Филип Флажоле, Ерик Фюзи, Оливие Гандуе и Фредерик Менье. Те показват, че е възможно да се оцени броят на елементите дори в набори, надхвърлящи един милиард записи, с типична грешка от около 2% и използване на едва 1,5 KB памет.

HyperLogLog има и ограничения. Той не позволява да се разбере кой точно е посетил сайта, да се възстанови списъкът с потребители или да се получи гарантирано точна бройка. Освен това един човек може да бъде отчетен няколко пъти, ако сайтът издава различни идентификатори за различните му устройства или браузъри. Въпреки това, когато трябва бързо да се оцени аудитория от десетки милиони, малката грешка е приемлива цена за значителната икономия на изчислителни ресурси и памет.