Percentiles Live Data Capture

Question

Szukam algorytmu, który określa percentyle dla przechwytywania danych na żywo.

Weźmy na przykład pod uwagę rozwój aplikacji serwerowej.

Serwer może mieć czas reakcji w następujący sposób: 17 ms 33 ms 52 ms 60 ms 55 ms itp

Warto zgłoszenia czas 90. percentyl reakcji, czas reakcji 80-ty percentyl itp.

Algorytm naiwny polega na wstawianiu każdego czasu odpowiedzi do listy. Gdy statystyki są wymagane, posortuj listę i uzyskaj wartości we właściwych pozycjach.

Wykorzystanie pamięci skaluje się liniowo z liczbą żądań.

Czy istnieje algorytm, który podaje "przybliżone" statystyki percentyla z ograniczonym wykorzystaniem pamięci? Na przykład, powiedzmy, że chcę rozwiązać ten problem w taki sposób, że przetwarzam miliony żądań, ale chcę tylko użyć jednego kilobajtu pamięci do śledzenia percentyla (odrzucenie śledzenia dla starych żądań nie jest opcją, ponieważ centyle mają być dla wszystkich wniosków).

Wymagają również, aby nie było a priori wiedzy o dystrybucji. Na przykład nie chcę określać żadnych zakresów segmentów przed czasem.

Answer 1

Wierzę, że istnieje wiele dobrych algorytmów przybliżonych dla tego problemu. Dobrym podejściem do pierwszego cięcia jest po prostu użycie tablicy o stałym rozmiarze (np. 1K danych). Napraw pewne prawdopodobieństwo p. Dla każdego żądania, z prawdopodobieństwem p, zapisz jego czas odpowiedzi w tablicy (zastępując najstarszy tam czas). Ponieważ tablica to podpróbkowanie strumienia na żywo, a subsampling zachowuje dystrybucję, wykonanie statystyk w tej tablicy da przybliżenie statystyk pełnego strumienia na żywo.

Podejście to ma wiele zalet: nie wymaga informacji a priori, a kodowanie jest łatwe. Możesz go szybko zbudować i określić eksperymentalnie, na konkretnym serwerze, w którym momencie wzrost bufora ma tylko znikomy wpływ na odpowiedź. To jest punkt, w którym przybliżenie jest wystarczająco precyzyjne.

Jeśli okaże się, że potrzebujesz zbyt dużej ilości pamięci, aby uzyskać dokładne statystyki, będziesz musiał dalej kopać. Dobre słowa kluczowe to: "przetwarzanie strumieniowe", "statystyki strumieniowe" i oczywiście "centyle". Możesz także wypróbować podejście "gniew i przekleństwa".

Answer 2

Jeśli chcesz utrzymywać zużycie pamięci na stałym poziomie, ponieważ otrzymujesz coraz więcej danych, będziesz musiał (a) w jakiś sposób uzyskać resample. Oznacza to, że musisz zastosować jakiś schemat rebinning. Możesz poczekać, aż zdobędziesz pewną ilość surowych danych wejściowych przed rozpoczęciem ponownego łączenia, ale nie możesz tego całkowicie uniknąć.

Twoje pytanie naprawdę pyta "jaki jest najlepszy sposób dynamicznego dzielenia moich danych"? Istnieje wiele podejść, ale jeśli chcesz zminimalizować swoje założenia dotyczące zakresu lub rozkładu wartości, jakie możesz otrzymać, to prostym podejściem jest uśrednienie nad wiaderkami o stałym rozmiarze k, z logarytmicznie rozłożonymi szerokościami. Na przykład powiedzmy, że chcesz jednocześnie przechowywać 1000 wartości w pamięci. Wybierz rozmiar dla k, powiedz 100. Wybierz minimalną rozdzielczość, powiedz 1ms. Następnie

• Pierwsze wiadro zajmuje się wartości między 0-1ms (width = 1ms)
• Second wieloczynnościowy: 1-3ms (W = 2ms)
• Trzeciego wiadra: 3-7ms (w = 4ms)
• Fourth wieloczynnościowy: 7-15ms (w = 8ms)
• ...
• dziesiątego wieloczynnościowy: 511-1023ms (w = 512ms)

Ten typPodejściejest podobne do systemów chunkingowych użytych w hash table algorithms, używanych przez niektóre systemy plików i algorytmy alokacji pamięci. Działa dobrze, gdy dane mają duży zakres dynamiki.

W miarę pojawiania się nowych wartości można wybrać sposób ponownego próbkowania, w zależności od wymagań. Na przykład możesz śledzić numer moving average, użyć first-in-first-out lub innej, bardziej wyrafinowanej metody.Zobacz algorytm Kademlia dla jednego podejścia (używane przez Bittorrent).

Ostatecznie ponowne łączenie może spowodować utratę pewnych informacji. Twoje wybory dotyczące binningu będą określać, jakie informacje są tracone. Innym sposobem na powiedzenie tego jest to, że pamięć pamięci o stałym rozmiarze oznacza kompromis między dynamic range i sampling fidelity; jak sprawić, żeby ten kompromis należał do ciebie, ale jak każdy problem z próbkowaniem, nie ma ominięcia tego podstawowego faktu.

Jeśli naprawdę interesują Cię zalety i wady, żadna odpowiedź na tym forum nie może być wystarczająca. Powinieneś zajrzeć do sampling theory. Dostępnych jest ogromna ilość badań na ten temat.

Podsumowując, podejrzewam, że czasy serwera będą miały stosunkowo mały zakres dynamiki, więc bardziej swobodne skalowanie w celu umożliwienia częstszego pobierania wspólnych wartości może zapewnić dokładniejsze wyniki.

Edytuj: Aby odpowiedzieć na Twój komentarz, oto przykład prostego algorytmu binningowego.

• Przechowujesz 1000 wartości w 10 pojemnikach. Każdy pojemnik zawiera zatem 100 wartości. Załóżmy, że każdy bin jest zaimplementowany jako tablica dynamiczna ("lista", w terminach Perla lub Pythona).

• Kiedy nowa wartość jest w:

  • Określ, które bin powinien być przechowywany w oparciu o granicach bin już wybranych.
  • Jeśli pojemnik nie jest pełny, dodaj jego wartość do listy pojemników.
  • Jeśli pojemnik jest pełny, usuń wartość u góry listy pojemników i dodaj nową wartość na dole listy pojemników. Oznacza to, że stare wartości są z czasem odrzucane.

• Aby znaleźć 90. percentyl, sortuj bin 10. 90. percentyl jest pierwszą wartością na posortowanej liście (element 900/1000).

Jeśli nie podoba ci się wyrzucanie starych wartości, możesz zamiast tego zastosować alternatywny schemat. Na przykład, gdy bin się zapełni (osiąga 100 wartości, w moim przykładzie), możesz wziąć średnią z najstarszych 50 elementów (tj. Pierwszych 50 na liście), odrzucić te elementy, a następnie dołączyć nowy średni element do kosz, pozostawiając ci pojemnik z 51 elementami, który ma teraz miejsce na 49 nowych wartości. Jest to prosty przykład ponownego łączenia.

Inny przykład ponownego łączenia to downsampling; na przykład wyrzucenie co piątej wartości na posortowanej liście.

Mam nadzieję, że ten konkretny przykład pomoże. Kluczem do zabrania jest to, że istnieje wiele sposobów na osiągnięcie stałego algorytmu starzenia się pamięci; tylko Ty możesz zdecydować, co jest zadowalające, biorąc pod uwagę Twoje wymagania.

Answer 3

Użyj dynamicznej tablicy T [] dużych liczb całkowitych lub czegoś, w którym T [n] zlicza ile razy czas odpowiedzi wynosi n milisekund. Jeśli naprawdę robisz statystyki dla aplikacji serwera, to prawdopodobnie czas odpowiedzi wynoszący 250 ms jest twoim absolutnym limitem. Więc twoje 1 KB ma 32-bitową liczbę całkowitą dla każdego ms między 0 a 250, a masz trochę wolnego miejsca na pojemnik przelewowy. Jeśli chcesz mieć coś z większą liczbą pojemników, idź z 8-bitowymi liczbami na 1000 binów i momentem przepełnienia licznika (tj.256-e żądanie w tym czasie odpowiedzi) przesunąłeś bity we wszystkich pojemnikach o 1 (efektywnie zmniejszając o połowę wartość we wszystkich pojemnikach). Oznacza to, że pomijasz wszystkie pojemniki, które przechwytują mniej niż 1/127-e opóźnień, które najczęściej odwiedzane są pojemniki.

Jeśli naprawdę, naprawdę potrzebujesz zestawu konkretnych pojemników, proponuję użyć pierwszego dnia z prośbą o wymyślenie rozsądnie ustalonego zestawu pojemników. Wszystko, co dynamiczne, byłoby dość niebezpieczne w aplikacji na żywo, wrażliwej na wydajność. Jeśli wybierzesz tę ścieżkę, lepiej będzie wiedzieć, co robisz, lub pewnego dnia zostaniesz wezwany z łóżka, aby wyjaśnić, dlaczego twój statyczny statystyk nagle zje 90% CPU i 75% pamięci na serwerze produkcyjnym.

Co do dodatkowych statystyk: Dla średnich i wariancji istnieją pewne nice recursive algorithms, które zajmują bardzo mało pamięci. Te dwie statystyki mogą być przydatne same w sobie dla wielu dystrybucji, ponieważ central limit theorem stwierdza, że ​​rozkłady, które wynikają z wystarczająco dużej liczby zmiennych niezależnych, zbliżają się do rozkładu normalnego (który jest w pełni określony przez średnią i wariancję), można użyć jednego z nich. the normality tests na ostatnim N (gdzie N wystarczająco duży, ale ograniczony przez twoje wymagania pamięciowe), aby monitorować, czy nadal istnieje założenie normalności.

Answer 4

Właśnie opublikowałem blog post on this topic. Podstawową ideą jest zmniejszenie wymogu dokładnych obliczeń na rzecz "95% procent odpowiedzi zajmuje 500ms-600ms lub mniej" (dla wszystkich dokładnych percentylów od 500ms do 600ms)

Możesz użyć dowolnej liczby wiader dowolny dowolny rozmiar (np. 0ms-50ms, 50ms-100ms, ... po prostu wszystko, co pasuje do twojego zastosowania). Zwykle nie powinno być problemu, ale wszystkie żądania przekraczające pewien czas odpowiedzi (na przykład 5 sekund dla aplikacji WWW) w ostatnim wiadrze (tj.> 5000 ms).

Dla każdego nowo uchwyconego czasu odpowiedzi, wystarczy zwiększyć licznik wiadra, w którym się znajduje. Aby oszacować n-ty percentyl, wystarczy tylko zsumować liczniki, aż suma przekroczy n procent całości.

Podejście to wymaga tylko 8 bajtów na zasobnik, umożliwiając śledzenie 128 pojemników z 1K pamięci. Jest to więcej niż wystarczające do analizowania czasów reakcji aplikacji WWW z wykorzystaniem ziarnistości 50 ms).

Jako przykład, tutaj jest Google Chart Utworzyłem od 1 godziny przechwyconych danych (przy użyciu 60 liczniki z 200ms na wiadrze):

response times http://j.mp/3bTf36

ładny, prawda?:) Read more on my blog.

Answer 5

Wypróbuj prosty algorytm zdefiniowany w artykule "Procedura sekwencyjna równoczesnego szacowania kilku wartości procentowych" (Raatikainen). Jest szybki, wymaga 2 * m + 3 markerów (dla m percentylów) i dąży do szybkiego przybliżenia.

Answer 6

(Minęło sporo czasu, odkąd to pytano, ale chciałbym zwrócić uwagę na kilka prac związanych z badaniami naukowymi)

Odnotowano znaczną ilość badań na przybliżonych percentyla strumieni danych w w ciągu ostatnich kilku lat. Kilka ciekawych prelekcji z pełnymi definicji algorytmu:

• A fast algorithm for approximate quantiles in high speed data streams

• Space-and time-efficient deterministic algorithms for biased quantiles over data streams

• Effective computation of biased quantiles over data streams

Wszystkie te dokumenty zaproponować algorytmy z sub-liniowej złożoności przestrzeni dla obliczanie przybliżonych percentyle nad strumieniem danych.