TL;DR: Cztery lata temu opuściłem Google z pomysłem na nowe narzędzie do monitorowania serwerów. Pomysł polegał na połączeniu izolowanych zwykle funkcji w jedną usługę i analiza logów, zbieranie metryk, i dashboardy. Jedna z zasad jest taka, że usługa musi być rzetelna szybko, zapewniając devopsowi łatwe, interaktywne i przyjemne doświadczenie. Wymaga to przetwarzania wielogigabajtowych zestawów danych w ułamkach sekundy przy zachowaniu budżetu. Istniejące narzędzia do zarządzania logami są często powolne i nieporęczne, dlatego stanęliśmy przed dobrym wyzwaniem: mądrze zaprojektować narzędzie, które zapewni użytkownikom nowe doświadczenia.
W tym artykule opisano, jak w Scalyr rozwiązaliśmy ten problem, stosując metody starej szkoły, podejście brute-force, eliminując niepotrzebne warstwy i unikając skomplikowanych struktur danych. Możesz zastosować te lekcje do własnych problemów inżynierskich.
Moc starej szkoły
Analiza dziennika zwykle rozpoczyna się od wyszukiwania: znajdź wszystkie wiadomości pasujące do określonego wzorca. W Scalyrze są to dziesiątki lub setki gigabajtów logów z wielu serwerów. Nowoczesne podejścia z reguły obejmują budowę złożonej struktury danych zoptymalizowanej pod kątem wyszukiwania. Z pewnością widziałem to w Google, gdzie są całkiem dobrzy w tego typu rzeczach. Zdecydowaliśmy się jednak na znacznie bardziej prymitywne podejście: liniowe skanowanie kłód. I zadziałało — zapewniamy interfejs z możliwością wyszukiwania, który jest o rząd wielkości szybszy niż nasi konkurenci (patrz animacja na końcu).
Kluczowym spostrzeżeniem było to, że nowoczesne procesory rzeczywiście są bardzo szybkie w wykonywaniu prostych i prostych operacji. Łatwo to przeoczyć w złożonych, wielowarstwowych systemach, które opierają się na szybkości we/wy i operacjach sieciowych, a takie systemy są dziś bardzo powszechne. Dlatego opracowaliśmy projekt, który minimalizuje warstwy i nadmiar zanieczyszczeń. W przypadku wielu procesorów i serwerów pracujących równolegle prędkość wyszukiwania osiąga 1 TB na sekundę.
Najważniejsze wnioski z tego artykułu:
- Wyszukiwanie metodą brute-force to realne podejście do rozwiązywania rzeczywistych problemów na dużą skalę.
- Brutalna siła to technika projektowania, a nie rozwiązanie niewymagające pracy. Jak każda technika, jest ona lepiej dostosowana do niektórych problemów niż inne i może zostać wdrożona źle lub dobrze.
- Brutalna siła jest szczególnie dobra do osiągnięcia stabilny wydajność.
- Efektywne użycie brutalnej siły wymaga optymalizacji kodu i zastosowania wystarczających zasobów we właściwym czasie. Jest to odpowiednie rozwiązanie, jeśli Twoje serwery nie są obciążone dużym obciążeniem, a operacje użytkownika pozostają priorytetem.
- Wydajność zależy od projektu całego systemu, a nie tylko od algorytmu pętli wewnętrznej.
(W tym artykule opisano wyszukiwanie danych w pamięci. W większości przypadków, gdy użytkownik przeszukuje dzienniki, serwery Scalyr już je umieściły w pamięci podręcznej. W następnym artykule omówione zostanie wyszukiwanie logów niezapisanych w pamięci podręcznej. Obowiązują te same zasady: wydajny kod, brutalna siła z dużymi zasobami obliczeniowymi).
Metoda brutalnej siły
Tradycyjnie duży zbiór danych przeszukiwany jest za pomocą indeksu słów kluczowych. W przypadku dzienników serwera oznacza to wyszukiwanie każdego unikalnego słowa w dzienniku. Dla każdego słowa musisz sporządzić listę wszystkich wtrąceń. Ułatwia to znalezienie wszystkich wiadomości zawierających to słowo, na przykład „błąd”, „firefox” lub „transakcja_16851951” - wystarczy zajrzeć do indeksu.
Zastosowałem to podejście w Google i zadziałało dobrze. Ale w Scalyrze przeszukujemy logi bajt po bajcie.
Dlaczego? Z abstrakcyjnego algorytmicznego punktu widzenia indeksy słów kluczowych są znacznie wydajniejsze niż wyszukiwania metodą brute-force. Jednak nie sprzedajemy algorytmów, sprzedajemy wydajność. Wydajność to nie tylko kwestia algorytmów, ale także inżynierii systemów. Musimy wziąć pod uwagę wszystko: ilość danych, rodzaj wyszukiwania, dostępny kontekst sprzętu i oprogramowania. Zdecydowaliśmy, że w przypadku naszego konkretnego problemu lepiej będzie pasować coś takiego jak „grep” niż indeks.
Indeksy są świetne, ale mają ograniczenia. Jedno słowo jest łatwe do znalezienia. Jednak wyszukiwanie wiadomości zawierających wiele słów, takich jak „googlebot” i „404”, jest znacznie trudniejsze. Wyszukiwanie frazy takiej jak „nieprzechwycony wyjątek” wymaga bardziej kłopotliwego indeksu, który rejestruje nie tylko wszystkie wiadomości zawierające to słowo, ale także konkretną lokalizację tego słowa.
Prawdziwa trudność pojawia się, gdy nie szukasz słów. Załóżmy, że chcesz zobaczyć, ile ruchu pochodzi z botów. Pierwszą myślą jest przeszukanie logów pod kątem słowa „bot”. W ten sposób znajdziesz boty: Googlebot, Bingbot i wiele innych. Ale tutaj „bot” nie jest słowem, ale jego częścią. Jeśli będziemy szukać w indeksie hasła „bot”, nie znajdziemy żadnych postów zawierających słowo „Googlebot”. Jeśli sprawdzisz każde słowo w indeksie, a następnie przeskanujesz indeks w poszukiwaniu znalezionych słów kluczowych, wyszukiwanie znacznie spowolni. W rezultacie niektóre programy dziennika nie pozwalają na wyszukiwanie częściowe lub (w najlepszym wypadku) umożliwiają specjalną składnię przy niższej wydajności. Chcemy tego uniknąć.
Kolejnym problemem jest interpunkcja. Czy chcesz znaleźć wszystkie żądania od 50.168.29.7? A co z debugowaniem dzienników zawierających [error]? Indeksy dolne zwykle pomijają znaki interpunkcyjne.
Wreszcie inżynierowie uwielbiają potężne narzędzia i czasami problem można rozwiązać jedynie za pomocą wyrażenia regularnego. Indeks słów kluczowych nie jest do tego zbyt odpowiedni.
Poza tym indeksy złożony. Każda wiadomość wymaga dodania do kilku list słów kluczowych. Listy te należy zawsze przechowywać w formacie umożliwiającym łatwe przeszukiwanie. Zapytania zawierające frazy, fragmenty słów lub wyrażenia regularne należy przetłumaczyć na operacje na wielu listach, a wyniki zeskanować i połączyć w celu uzyskania zestawu wyników. W kontekście usługi na dużą skalę z wieloma dzierżawcami ta złożoność powoduje problemy z wydajnością, które nie są widoczne podczas analizy algorytmów.
Indeksy słów kluczowych również zajmują dużo miejsca, a przechowywanie stanowi główny koszt w systemie zarządzania dziennikami.
Z drugiej strony każde wyszukiwanie może zużywać dużo mocy obliczeniowej. Nasi użytkownicy cenią sobie szybkie wyszukiwanie unikalnych zapytań, jednak takie zapytania zdarzają się stosunkowo rzadko. W przypadku typowych zapytań, np. o dashboard, stosujemy specjalne techniki (opiszemy je w kolejnym artykule). Inne żądania są na tyle rzadkie, że rzadko trzeba przetwarzać więcej niż jedno na raz. Nie oznacza to jednak, że nasze serwery nie są zajęte: są zajęte odbieraniem, analizowaniem i kompresowaniem nowych wiadomości, oceną alertów, kompresowaniem starych danych i tak dalej. Tym samym mamy dość pokaźną podaż procesorów, które można wykorzystać do realizacji zapytań.
Brutalna siła działa, jeśli masz brutalny problem (i dużo siły)
Brutalna siła działa najlepiej w przypadku prostych problemów z małymi pętlami wewnętrznymi. Często można zoptymalizować pętlę wewnętrzną, aby działała z bardzo dużymi prędkościami. Jeśli kod jest skomplikowany, znacznie trudniej jest go zoptymalizować.
Nasz kod wyszukiwania pierwotnie miał dość dużą pętlę wewnętrzną. Przechowujemy wiadomości na stronach w rozdzielczości 4K; każda strona zawiera wiadomości (w formacie UTF-8) i metadane dla każdej wiadomości. Metadane to struktura, która koduje długość wartości, wewnętrzny identyfikator wiadomości i inne pola. Cykl poszukiwań wyglądał następująco:
To jest uproszczona wersja rzeczywistego kodu. Ale nawet tutaj widocznych jest wiele rozmieszczeń obiektów, kopii danych i wywołań funkcji. JVM jest całkiem dobra w optymalizacji wywołań funkcji i przydzielaniu obiektów efemerycznych, więc ten kod działał lepiej, niż na to zasługiwaliśmy. Podczas testów klienci używali go z powodzeniem. Ale w końcu przenieśliśmy to na wyższy poziom.
(Możesz zapytać, dlaczego przechowujemy wiadomości w tym formacie ze stronami 4K, tekstem i metadanymi, zamiast bezpośrednio pracować z logami. Powodów jest wiele, które sprowadzają się do tego, że wewnętrznie silnik Scalyr bardziej przypomina rozproszoną bazę danych niż system plików.Wyszukiwanie tekstowe często łączy się z filtrami w stylu DBMS na marginesach po analizie logów.Możemy jednocześnie przeszukiwać wiele tysięcy logów na raz, a proste pliki tekstowe nie nadają się do naszego transakcyjnego, replikowanego, rozproszonego zarządzania danymi).
Początkowo wydawało się, że taki kod nie za bardzo nadaje się do optymalizacji metodą brute-force. „Prawdziwa praca” w String.indexOf() nie zdominował nawet profilu procesora. Oznacza to, że sama optymalizacja tej metody nie przyniesie znaczącego efektu.
Tak się składa, że na początku każdej strony przechowujemy metadane, a na drugim końcu upakowany jest tekst wszystkich wiadomości w UTF-8. Korzystając z tego, przepisaliśmy pętlę, aby przeszukać całą stronę na raz:
Ta wersja działa bezpośrednio na widoku raw byte[] i przeszukuje wszystkie wiadomości jednocześnie na całej stronie 4K.
Dużo łatwiej jest to zoptymalizować pod kątem metody brute-force. Wewnętrzna pętla wyszukiwania jest wywoływana jednocześnie dla całej strony 4K, a nie osobno dla każdego posta. Nie ma kopiowania danych, nie ma alokacji obiektów. Bardziej złożone operacje na metadanych są wywoływane tylko wtedy, gdy wynik jest pozytywny, a nie przy każdej wiadomości. W ten sposób wyeliminowaliśmy mnóstwo narzutu, a reszta obciążenia została skoncentrowana w małej wewnętrznej pętli wyszukiwania, która dobrze nadaje się do dalszej optymalizacji.
Nasz rzeczywisty algorytm wyszukiwania opiera się na . Działa podobnie do algorytmu Boyera-Moore’a i pomija w każdym kroku mniej więcej długość szukanego ciągu. Główna różnica polega na tym, że sprawdza dwa bajty na raz, aby zminimalizować liczbę fałszywych dopasowań.
Nasza implementacja wymaga utworzenia tabeli przeglądowej o wielkości 64 KB dla każdego wyszukiwania, ale to nic w porównaniu z gigabajtami danych, które przeszukujemy. Wewnętrzna pętla przetwarza kilka gigabajtów na sekundę na jednym rdzeniu. W praktyce stabilna wydajność wynosi około 1,25 GB na sekundę na każdym rdzeniu i jest co poprawiać. Możliwe jest wyeliminowanie części narzutu poza pętlą wewnętrzną i planujemy eksperymentować z pętlą wewnętrzną w C zamiast w Javie.
Używamy siły
Omówiliśmy, że przeszukiwanie dzienników można wdrożyć „w przybliżeniu”, ale jaką „moc” mamy? Sporo.
1 rdzeń: Przy prawidłowym użyciu pojedynczy rdzeń nowoczesnego procesora sam w sobie jest dość wydajny.
8 rdzeni: Obecnie pracujemy na serwerach Amazon hi1.4xlarge i i2.4xlarge SSD, każdy z 8 rdzeniami (16 wątków). Jak wspomniano powyżej, rdzenie te są zwykle zajęte operacjami w tle. Gdy użytkownik przeprowadza wyszukiwanie, operacje w tle są zawieszane, uwalniając wszystkie 8 rdzeni do wyszukiwania. Wyszukiwanie kończy się zwykle w ułamku sekundy, po czym praca w tle zostaje wznowiona (program ograniczający przepustowość dba o to, aby zalew zapytań nie zakłócał ważnej pracy w tle).
16 rdzeni: dla niezawodności organizujemy serwery w grupy master/slave. Każdy master ma pod swoją komendą jeden serwer SSD i jeden serwer EBS. Jeśli główny serwer ulegnie awarii, serwer SSD natychmiast zajmie jego miejsce. Prawie cały czas master i slave działają dobrze, więc każdy blok danych można przeszukiwać na dwóch różnych serwerach (serwer slave EBS ma słaby procesor, więc nie bierzemy tego pod uwagę). Dzielimy zadanie pomiędzy nimi tak, że w sumie mamy do dyspozycji 16 rdzeni.
Wiele rdzeni: W najbliższej przyszłości będziemy dystrybuować dane pomiędzy serwerami w taki sposób, aby wszystkie brały udział w przetwarzaniu każdego nietrywialnego żądania. Każdy rdzeń będzie działał. [Notatka: wdrożyliśmy plan i zwiększyliśmy prędkość wyszukiwania do 1 TB/s, patrz uwaga na końcu artykułu].
Prostota zapewnia niezawodność
Kolejną zaletą metody brutalnej siły jest jej dość spójne działanie. Zazwyczaj wyszukiwanie nie jest zbyt czułe na szczegóły problemu i zbioru danych (chyba dlatego nazywa się to „zgrubnym”).
Indeks słów kluczowych czasami daje niewiarygodnie szybkie wyniki, a innym razem nie. Załóżmy, że masz 50 GB logów, w których termin „customer_5987235982” pojawia się dokładnie trzy razy. Wyszukiwanie tego terminu zlicza trzy lokalizacje bezpośrednio z indeksu i kończy się natychmiast. Jednak złożone wyszukiwania z użyciem symboli wieloznacznych mogą skanować tysiące słów kluczowych i zająć dużo czasu.
Z drugiej strony wyszukiwania metodą brute-force działają z mniej więcej taką samą szybkością dla każdego zapytania. Wyszukiwanie długich słów jest lepsze, ale nawet wyszukiwanie pojedynczego znaku jest dość szybkie.
Prostota metody brutalnej siły powoduje, że jej wydajność jest bliska teoretycznego maksimum. Istnieje mniej opcji nieoczekiwanych przeciążeń dysku, rywalizacji o blokady, ścigania wskaźników i tysięcy innych przyczyn niepowodzeń. Właśnie przejrzałem żądania złożone przez użytkowników Scalyr w zeszłym tygodniu na naszym najbardziej obciążonym serwerze. Było 14 000 wniosków. Dokładnie osiem z nich trwało dłużej niż jedną sekundę; Ukończono w 99% w ciągu 111 milisekund (jeśli nie korzystałeś z narzędzi do analizy logów, zaufaj mi: to jest szybkie).
Stabilne i niezawodne działanie jest ważne dla łatwości korzystania z usługi. Jeśli występują okresowe opóźnienia, użytkownicy będą postrzegać je jako zawodne i niechętnie z nich korzystają.
Wyszukiwanie dziennika w akcji
Oto krótka animacja przedstawiająca wyszukiwarkę Scalyr w akcji. Mamy konto demo, na którym importujemy każde wydarzenie do każdego publicznego repozytorium Github. W tym demo sprawdzam dane z tygodnia: około 600 MB surowych logów.
Film nagrywany był na żywo, bez specjalnego przygotowania, na moim komputerze stacjonarnym (ok. 5000 km od serwera). Wydajność, którą zobaczysz, jest w dużej mierze zasługą , a także szybki i niezawodny backend. Ilekroć następuje pauza bez wskaźnika „ładowania”, robię to ja, aby można było przeczytać, co zamierzam nacisnąć.
Na zakończenie
Przy przetwarzaniu dużej ilości danych ważny jest wybór dobrego algorytmu, jednak „dobry” nie znaczy „wymyślny”. Zastanów się, jak Twój kod będzie działał w praktyce. Teoretyczna analiza algorytmów pomija pewne czynniki, które w świecie rzeczywistym mogą mieć ogromne znaczenie. Prostsze algorytmy są łatwiejsze do optymalizacji i bardziej stabilne w sytuacjach brzegowych.
Pomyśl także o kontekście, w którym kod zostanie wykonany. W naszym przypadku potrzebujemy wystarczająco wydajnych serwerów, aby zarządzać zadaniami w tle. Użytkownicy inicjują wyszukiwania stosunkowo rzadko, dzięki czemu możemy wypożyczyć całą grupę serwerów na krótki okres potrzebny do zakończenia każdego wyszukiwania.
Stosując metodę brutalnej siły, wdrożyliśmy szybkie, niezawodne i elastyczne wyszukiwanie w zestawie dzienników. Mamy nadzieję, że te pomysły przydadzą się w Twoich projektach.
равка: Tytuł i tekst zmieniono z „Wyszukiwanie z szybkością 20 GB na sekundę” na „Wyszukiwanie z szybkością 1 TB na sekundę”, aby odzwierciedlić wzrost wydajności w ciągu ostatnich kilku lat. Ten wzrost prędkości wynika przede wszystkim ze zmian w typie i liczbie serwerów EC2, które dzisiaj instalujemy, aby obsługiwać naszą zwiększoną bazę klientów. Wkrótce pojawią się zmiany, które zapewnią kolejny radykalny wzrost wydajności operacyjnej i nie możemy się doczekać, aby się nimi podzielić.
Źródło: www.habr.com