HyperLogLog liczy miliardy różnych elementów w pamięci liczonej w kilobajtach
Aby dokładnie policzyć, ilu różnych użytkowników pojawiło się w ogromnym strumieniu, najprościej byłoby zapamiętać wszystkie unikalne identyfikatory. HyperLogLog robi coś zupełnie innego: hashuje elementy i obserwuje statystycznie rzadkie wzorce w bitach wyników, przede wszystkim długość początkowego ciągu zer. Bardzo długi taki ciąg jest mało prawdopodobny, więc jego pojawienie się sugeruje dużą liczbę prób. Wiele małych rejestrów pozwala połączyć takie obserwacje w estymację cardinality. Autorzy algorytmu pokazali, że można estymować liczności znacznie przekraczające miliard z typowym błędem około 2% przy pamięci rzędu 1,5 kB w opisanej konfiguracji.
Dokładne liczenie wymaga pamiętania tożsamości
Pytanie „ile zdarzeń przyszło?” jest łatwe: wystarczy licznik. Pytanie „ile różnych identyfikatorów przyszło?” jest trudniejsze, bo duplikaty nie mogą zwiększać wyniku. Dokładne rozwiązanie zwykle przechowuje zbiór widzianych identyfikatorów albo inną strukturę zdolną rozstrzygać ich unikalność. Przy setkach milionów wartości pamięć takiego rozwiązania staje się istotnym kosztem.
HyperLogLog rezygnuje z dokładności. Nie pamięta, kim byli użytkownicy. Próbuje oszacować samą liczność zbioru na podstawie własności hashy. To radykalna zmiana pytania: zamiast zachować reprezentację elementów, zachowujemy niewielki statystyczny ślad świadczący o tym, jak wiele niezależnych elementów prawdopodobnie widzieliśmy.
Rzadkie zera działają jak ślad dużej liczby prób
Dobrze zachowujący się hash można traktować w tym kontekście jak ciąg niemal losowych bitów. Szansa, że zaczyna się od jednego zera, wynosi około 1/2; od dwóch — 1/4; od dziesięciu — 1/1024. Jeśli wśród hashy zobaczymy bardzo długi prefiks zer, jest to przesłanka, że wykonano dużo prób. Jedna ekstremalna obserwacja byłaby jednak bardzo niestabilna.
Dlatego HyperLogLog dzieli obserwacje na wiele rejestrów. Część bitów hasha wybiera rejestr, a pozostałe służą do pomiaru rzadkiego wzorca. Następnie algorytm odpowiednio agreguje wartości rejestrów i koryguje estymację. Dzięki wielu równoległym małym obserwacjom pojedynczy szczęśliwy lub pechowy hash ma mniejszy wpływ na całość.
1,5 kilobajta i liczności powyżej miliarda
Praca Philippe'a Flajoleta, Érica Fusy'ego, Oliviera Gandoueta i Frédérica Meuniera z 2007 roku opisuje HyperLogLog jako probabilistyczny algorytm do estymowania liczby różnych elementów w bardzo dużych zbiorach. Autorzy podają zależność typowego błędu standardowego od liczby rejestrów oraz konkretny przykład: liczności znacznie powyżej 10^9 można estymować z typową dokładnością około 2% przy pamięci około 1,5 kB.
To liczba, którą warto rozumieć jako parametr konkretnej konfiguracji opisanej w publikacji, a nie magiczną stałą gwarantującą 2% w każdym systemie i przy każdym sposobie implementacji. Sedno pozostaje imponujące: pamięć potrzebna do estymacji nie musi rosnąć proporcjonalnie do liczby unikalnych elementów.
Kiedy przybliżenie jest lepsze od dokładności
Jeżeli wynik ma decydować o rozliczeniu finansowym jednej konkretnej osoby, kilkuprocentowy błąd może być niedopuszczalny. Jeśli jednak system ma na bieżąco oszacować liczbę unikalnych urządzeń, zapytań lub adresów widzianych w gigantycznym strumieniu, dokładny zbiór może być nieproporcjonalnie drogi. Wtedy kontrolowany błąd staje się rozsądną ceną za stałą, bardzo małą pamięć.
HyperLogLog jest dobrym przykładem „sketchu” strumieniowego. Zamiast kompresować dane tak, by dało się je odtworzyć, kompresuje odpowiedź na jedno wybrane pytanie. Po zapisaniu samego szkicu nie odzyskamy listy użytkowników. Możemy jednak niezwykle tanio przybliżyć ich liczbę — i właśnie ta asymetria jest źródłem oszczędności.
Szkice można scalać bez odzyskiwania oryginalnych elementów
HyperLogLog ma jeszcze jedną własność ważną w systemach rozproszonych. Jeśli dwa węzły policzyły szkice dla rozłącznych albo nakładających się fragmentów strumienia przy tych samych parametrach, ich rejestry można połączyć, biorąc dla każdego indeksu maksimum. Wynika to bezpośrednio z tego, że rejestr przechowuje najbardziej ekstremalną zaobserwowaną wartość dla danej grupy hashy. Nie trzeba przesyłać wszystkich identyfikatorów ani odtwarzać danych źródłowych. Takie algebraiczne składanie jest jednym z powodów, dla których małe probabilistyczne szkice są tak wygodne przy liczeniu unikalnych zdarzeń w wielu maszynach.
Dokładność rośnie jak pierwiastek z liczby rejestrów
Analiza Flajoleta i współautorów podaje typowy błąd standardowy HyperLogLog około 1,04/√m, gdzie m oznacza liczbę rejestrów. To oznacza charakterystyczny kompromis: aby mniej więcej dwukrotnie zmniejszyć błąd standardowy, trzeba użyć około czterokrotnie większej liczby rejestrów. Nie ma tu darmowego liniowego przelicznika „dwa razy więcej pamięci = dwa razy większa precyzja”. Jednocześnie m może pozostawać bardzo małe w porównaniu z liczbą rozróżnianych elementów. Właśnie dlatego przykład z publikacji — liczności daleko powyżej 10^9, około 2% typowego błędu i 1,5 kB pamięci — jest tak sugestywny. Pamięć nie rośnie wraz z każdym nowym identyfikatorem; służy do poprawiania statystycznego obrazu rozkładu obserwacji.