Wiarygodny test integracji kodu przy użyciu HyperLogLog?

Question

Używamy implementacji HyperLogLoga na Twitterze w Algebiorze. Biorąc pod uwagę liczbę N i czek w naszym systemie, który wykorzystuje HyperLogLog do oszacowania aktualnej wielkości stopniowo rosnącej kolekcji i testowania, czy jest on mniejszy lub równy N, jak możemy napisać test integracji lub systemu, który testuje to sprawdzanie i jest prawie gwarantowane przejście, jeśli nasz kod, który wywołuje HyperLogLog jest poprawny? Testowany system jest niedeterministyczny, ponieważ z jednej strony jest wielowątkowy.

W pierwszej chwili pomyślałem, że właściwym sposobem napisania testu integracji, który jest niezawodny w tym przypadku, jest "zrzucenie naszych standardów". Jaka jest więc wystarczająca liczba elementów (M) do umieszczenia w punkcie końcowym, aby mieć pewność, że HyperLogLog oszacuje łączną liczbę elementów jako większą niż N, z prawdopodobieństwem, powiedzmy,> = 0,999999?

Czy istnieje lepsze podejście?

Standardowe granice błędu można konfigurować, ale nie określają one bezpośrednio maksymalnych granic błędu, które możemy prawdopodobnie zobaczyć raz na jakiś czas - na czym mi zależy, aby uniknąć losowych nieudanych kompilacji CI na podstawie wywołującej zmarnowany czas i ciągnięcie za włosy!

Obawiam się również, że sposób, w jaki generujemy losowe dane w testach, może nie generować równomiernie rozłożonych danych losowych w odpowiednich aspektach, co może mieć istotny wpływ na obliczenia prawdopodobieństwa.

Answer 1

Złam to trochę. Istnieją dwa główne zachowania szukasz testu:

1. Realizacja Twitter HyperLogLog wykonuje prawidłowo, to znaczy, że daje dobre oszacowanie liczby elementów.

2. Twój kod zużywający struktury HyperLogLog (np. Liczniki) zwiększa je w razie potrzeby.

Należy zauważyć, że zachowanie nr 2 jest łatwe do przetestowania w czasie kompilacji przy użyciu testów jednostkowych, a nie w testach integracyjnych. Jest to lepsze rozwiązanie i pozwoli złapać większość problemów.

Case # 1 może być również podzielone na trzy przypadki:

A, gdy liczba elementów jest 0;

B, gdy liczba pozycji jest mała (5, 100 lub 1000);

C, gdy liczba pozycji jest duża (miliony/miliardy).

I znów przypadki A i B mogą i powinny być testowane w czasie budowy przy użyciu testów jednostkowych. Powinieneś zdecydować o dopuszczalnych granicach błędu w zależności od aplikacji i mieć twierdzenia UT, że oszacowanie mieści się w tych granicach - nie ma znaczenia, że ​​wybrałeś HyperLogLog jako podstawową metodę szacowania, testy powinny traktować estymator jako czarną skrzynkę . Jako pole do gry, powiedziałbym, że 10% błąd jest uzasadniony dla większości celów, ale to naprawdę zależy od konkretnego zastosowania. Te granice powinny reprezentować najgorszą możliwą dokładność, z jaką Twoja aplikacja może żyć. Na przykład licznik błędów krytycznych może nie być w stanie żyć z DOWOLNYMI błędami szacowania, więc użycie w tym celu narzędzia HyperLogLog powinno spowodować przerwanie testu jednostki. Licznik liczby różnych użytkowników może być w stanie żyć z aż 50% błędem szacowania - to zależy od Ciebie.

Pozostaje nam ostatni przypadek - testowanie, że implementacja HyperLogLog daje dobre oszacowanie dużej liczby elementów.Nie można tego testować w czasie kompilacji, a nawet test integracyjny jest do zrobienia. Jednak w zależności od tego, jak bardzo wierzysz w implementację HyperLogLog na Twitterze, możesz uznać, że NIE TESTUJE to w ogóle - Twitter powinien już to zrobić. Może to wydawać się oderwaniem od najlepszych praktyk, ale biorąc pod uwagę koszty ogólne, które mogą być związane z testami integracyjnymi, może się to opłacać w twoim przypadku.

Jeśli zdecydujesz się napisać test integracji, będziesz musiał modelować ruch, jakiego oczekujesz podczas produkcji i wygenerować go z wielu źródeł, ponieważ będziesz generować miliony/miliardy żądań. Możesz zapisać próbkę rzeczywistego ruchu produkcyjnego i użyć go do testowania (prawdopodobnie najdokładniejsza metoda) lub sprawdzić, jak wygląda Twój ruch i wygenerować podobny wygląd ruchu testowego. Ponownie, granice błędów powinny być wybrane zgodnie z wnioskiem, i powinieneś być w stanie zamienić metodę szacowania na lepszą bez przerywania testu.