TL;DR: Cztery lata temu opuściłem Google z pomysłem na nowe narzędzie do monitorowania serwerów. Idea polegała na połączeniu w jedną usługę zwykle odizolowanych funkcji i analizy logów, zbierania metryk, i panelu monitorowania. Jedną z zasad jest to, że serwis musi być naprawdę szybki, zapewniając deweloperom łatwą, interaktywną, przyjemną pracę. Wymaga to przetwarzania zestawów danych o kilku gigabajtach w ułamkach sekundy, nie wychodząc poza budżet. Istniejące narzędzia do pracy z logami są często wolne i nieporęczne, dlatego stanęliśmy przed dobrym wyzwaniem: umiejętnie zaprojektować narzędzie, aby dać użytkownikom nowe doznania z pracy.
W tym artykule opisujemy, jak w Scalyr rozwiązaliśmy ten problem, stosując metody staroszkolne, podejście siłowe, eliminując zbędne warstwy i unikając skomplikowanych struktur danych. Te lekcje możecie zastosować do własnych zadań inżynieryjnych.
Siła staroszkolna
Analiza logów zazwyczaj zaczyna się od poszukiwań: znalezienie wszystkich komunikatów pasujących do pewnego wzoru. W Scalyr to dziesiątki lub setki gigabajtów logów z wielu serwerów. Nowoczesne podejścia zazwyczaj polegają na budowaniu jakiejś skomplikowanej struktury danych, zoptymalizowanej do wyszukiwania. Oczywiście widziałem to w Google, gdzie są całkiem dobrzy w takich kwestiach. Ale postawiliśmy na dużo prostsze podejście: liniowe skanowanie logów. I zadziałało to — zapewniamy interfejs z wyszukiwaniem na poziomie dziesięć razy szybszym niż u konkurencji (zobacz animację na końcu).
Kluczowym wnioskiem było to, że nowoczesne procesory są naprawdę bardzo szybkie w prostych, bezpośrednich operacjach. Łatwo to przeoczyć w złożonych, wielowarstwowych systemach, które opierają się na szybkości operacji I/O i sieciowych, a takie systemy są dzisiaj bardzo powszechne. W związku z tym zaprojektowaliśmy architekturę, która minimalizuje liczbę warstw i zbędnego śmiecia. Z kilkoma procesorami i serwerami równolegle, prędkość wyszukiwania osiąga 1 TB na sekundę.
Kluczowe wnioski z tego artykułu:
- Proste wyszukiwanie to jak najbardziej wykonalne podejście do rzeczywistych, skalowalnych problemów.
- Brute force to technika projektowania, a nie uwolnienie od pracy. Jak każda technika, najlepiej nadaje się do niektórych problemów, a jej realizacja może być zła lub dobra.
- Brute force jest szczególnie dobra do osiągania stabilnej wydajności.
- Efektywne wykorzystanie brute force wymaga optymalizacji kodu oraz terminowego zastosowania odpowiedniej ilości zasobów. Jest to odpowiednie, gdy twoje serwery są pod dużym obciążeniem, niezwiązanym z użytkownikami, a operacje użytkowników pozostają w priorytecie.
- Wydajność zależy od projektu całego systemu, a nie tylko od algorytmu wewnętrznej pętli.
(W tym artykule opisano wyszukiwanie danych w pamięci. W większości przypadków, gdy użytkownik wykonuje wyszukiwanie w logach, serwery Scalyr już je zbuforowały. W następnym artykule omówimy wyszukiwanie w logach, które nie są buforowane. Stosuje się te same zasady: efektywny kod, metoda brute force z dużymi zasobami obliczeniowymi).
Metoda brute force
Tradycyjnie wyszukiwanie w dużym zbiorze danych odbywa się za pomocą indeksu słów kluczowych. W odniesieniu do logów serwerowych oznacza to wyszukiwanie każdego unikalnego słowa w dzienniku. Dla każdego słowa należy sporządzić listę wszystkich wystąpień. Umożliwia to łatwe znalezienie wszystkich wiadomości zawierających to słowo, na przykład 'error', 'firefox' lub 'transaction_16851951' — po prostu przeszukując indeks.
Stosowałem takie podejście w Google i sprawdziło się dobrze. Ale w Scalyr przeszukujemy logi bajt po bajcie.
Dlaczego? Z abstrakcyjnego punktu widzenia algorytmicznego indeksy słów kluczowych są dużo wydajniejsze niż brute force. Jednak nie sprzedajemy algorytmów, sprzedajemy wydajność. A wydajność to nie tylko algorytmy, ale również inżynieria systemowa. Musimy uwzględnić wszystko: objętość danych, typ wyszukiwania, dostępny sprzęt i kontekst programowy. Zdecydowaliśmy, że dla naszego konkretnego problemu taka opcja jak 'grep' nadaje się lepiej niż indeks.
Indeksy są świetne, ale mają swoje ograniczenia. Łatwo znaleźć jedno słowo. Natomiast wyszukiwanie wiadomości z wieloma słowami, takimi jak 'googlebot' i '404' — jest znacznie trudniejsze. Wyszukiwanie frazy takiej jak 'uncaught exception' wymaga bardziej złożonego indeksu, który rejestruje nie tylko wszystkie wiadomości z tym słowem, ale i konkretne miejsce tego słowa.
Prawdziwy problem pojawia się, gdy nie szuka się słów. Załóżmy, że chcesz sprawdzić, ile ruchu pochodzi od botów. Pierwsza myśl to przeszukać logi pod kątem słowa 'bot'. W ten sposób znajdziesz niektóre boty: Googlebot, Bingbot i wiele innych. Ale tutaj 'bot' to nie słowo, a jego część. Jeśli będziemy szukać 'bot' w indeksie, nie znajdziemy wiadomości zawierających słowo 'Googlebot'. Jeśli sprawdzać każde słowo w indeksie, a potem skanować indeks według znalezionych słów kluczowych, wyszukiwanie znacznie się spowolni. W rezultacie niektóre programy do pracy z logami nie pozwalają na wyszukiwanie po częściach słowa lub (w najlepszym przypadku) umożliwiają użycie specjalnej składni o niższej wydajności. Chcemy tego uniknąć.
Kolejny problem to interpunkcja. Czy chcesz znaleźć wszystkie zapytania od 50.168.29.7? Что насчёт отладки логов, содержащих [error]? Индексы обычно пропускают пунктуацию.
W końcu inżynierowie lubią potężne narzędzia, a czasami problem można rozwiązać tylko za pomocą wyrażeń regularnych. Indeks słów kluczowych nie nadaje się do tego zbytnio.
Dodatkowo, indeksy są skomplikowane. każdą wiadomość należy dodać do kilku list słów kluczowych. Listy te powinny być nieustannie utrzymywane w formacie wygodnym do wyszukiwania. Zapytania z frazami, fragmentami słów lub wyrażeniami regularnymi należy przekształcać w operacje z wieloma listami, a wyniki skanować i łączyć w celu uzyskania zbioru wynikowego. W kontekście rozbudowanej, wieloosobowej usługi, ta złożoność stwarza problemy wydajnościowe, które są niewidoczne podczas analizy algorytmów.
Indeksy słów kluczowych również zajmują dużo miejsca, a przechowywanie danych jest głównym kosztem w systemie zarządzania logami.
Z drugiej strony, na każde wyszukiwanie można poświęcić dużo mocy obliczeniowej. Nasi użytkownicy cenią sobie szybkie wyszukiwanie unikalnych zapytań, ale takie zapytania wykonują stosunkowo rzadko. W przypadku typowych zapytań, na przykład w panelu monitorowania, stosujemy specjalne techniki (opiszemy je w następnym artykule). Inne zapytania są na tyle rzadkie, że zwykle przetwarzamy nie więcej niż jedno na raz. Ale to nie znaczy, że nasze serwery nie są zajęte: są obciążone pracą przy odbiorze, analizie i kompresji nowych wiadomości, ocenie powiadomień, kompresji starych danych i tak dalej. W ten sposób mamy całkiem spory zapas procesorów, które można zaangażować do realizacji zapytań.
Brute force działa, jeśli masz prosty problem (i dużo mocy).
Brute force najlepiej sprawdza się w prostych zadaniach z małymi pętlami wewnętrznymi. Często można zoptymalizować wewnętrzną pętlę, aby działała na bardzo wysokich prędkościach. Jeśli kod jest skomplikowany, znacznie trudniej go zoptymalizować.
Początkowo w naszym kodzie wyszukiwania był dość duży wewnętrzny cykl. Przechowujemy wiadomości na stronach po 4K; każda strona zawiera pewne wiadomości (w UTF-8) i metadane dla każdej wiadomości. Metadane to struktura, w której zakodowane są długość wartości, wewnętrzny ID wiadomości i inne pola. Cykl wyszukiwania wyglądał tak:
To uproszczona wersja w porównaniu do rzeczywistego kodu. Ale nawet tutaj widać kilka zakotwiczeń obiektu, kopii danych i wywołań funkcji. JVM całkiem dobrze optymalizuje wywołania funkcji i zarządza efemerycznymi obiektami, więc ten kod działał lepiej, niż na to zasługiwaliśmy. Podczas testów klienci dość skutecznie z niego korzystali. Ale w końcu przeszliśmy na nowy poziom.
(Możesz zapytać, dlaczego przechowujemy wiadomości w takim formacie z stronami po 4K, tekstem i metadanymi, zamiast pracować bezpośrednio z logami. Jest wiele powodów, 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 Bazy Danych po przetworzeniu logów. Możemy jednocześnie przeszukiwać wiele tysięcy logów, a proste pliki tekstowe nie nadają się do naszego transakcyjnego, replikowanego, rozproszonego zarządzania danymi).
Początkowo wydawało się, że taki kod nie jest zbyt odpowiedni do optymalizacji metodą brute force. „Prawdziwa praca” w String.indexOf() nawet nie dominowała w profilu CPU. Oznacza to, że optymalizacja tylko tej metody nie przyniosłaby znaczących efektów.
Tak się złożyło, że przechowujemy metadane na początku każdej strony, a tekst wszystkich wiadomości w UTF-8 jest pakowany na drugim końcu. Wykorzystując to, przepisaliśmy pętlę do przeszukiwania całej strony:
Taka wersja działa bezpośrednio na widoku raw byte[] i przeprowadza przeszukiwanie wszystkich wiadomości na całej stronie 4K.
To znacznie łatwiej optymalizować dla metody brute force. Wewnętrzna pętla wyszukiwania jest wywoływana jednocześnie dla całej strony 4K, a nie oddzielnie dla każdej wiadomości. Nie ma kopiowania danych ani alokacji obiektów. A bardziej skomplikowane operacje z metadanymi są wywoływane tylko przy pozytywnym wyniku, a nie dla każdej wiadomości. Dzięki temu wyeliminowaliśmy dużo narzutu, a pozostałe obciążenie koncentruje się w małej wewnętrznej pętli wyszukiwania, która dobrze nadaje się do dalszej optymalizacji.
Nasz rzeczywisty algorytm wyszukiwania oparty jest na . Jest podobny do algorytmu Boyera-Moore'a z pominięciem około długości wyszukiwanej frazy na każdym kroku. Główna różnica polega na tym, że sprawdza dwa bajty na raz, aby zminimalizować fałszywe trafienia.
Nasza implementacja wymaga utworzenia tabeli wyszukiwania 64K dla każdego wyszukiwania, ale to drobiazg w porównaniu do gigabajtów danych, w których szukamy. 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, a istnieje potencjał do poprawy. Można wyeliminować niektóre narzuty poza wewnętrzną pętlą i planujemy eksperymentować z wewnętrzną pętlą w C zamiast w Javie.
Zastosuj moc
Rozmawialiśmy, że przeszukiwanie logów można zrealizować „na sztywno”, ale ile „mocy” mamy? Nie mało.
1 rdzeń: przy odpowiednim użyciu jeden rdzeń współczesnego procesora jest dość mocny sam w sobie.
8 rdzeni: obecnie pracujemy na serwerach Amazon hi1.4xlarge i i2.4xlarge SSD, z których każdy ma 8 rdzeni (16 wątków). Jak wspomniano wcześniej, zazwyczaj te rdzenie są zajęte operacjami w tle. Gdy użytkownik wykonuje wyszukiwanie, operacje w tle są wstrzymywane, uwalniając wszystkie 8 rdzeni do wyszukiwania. Wyszukiwanie zazwyczaj kończy się w ułamku sekundy, po czym prace w tle są wznawiane (program regulatora zapewnia, że natłok zapytań nie zakłóci ważnej pracy w tle).
16 rdzeni: dla niezawodności organizujemy serwery w grupy master/slave. Każdy master ma pod sobą jeden serwer SSD i jeden EBS. Jeśli główny serwer zawiedzie, to serwer na SSD natychmiast zajmuje jego miejsce. Przez większość czasu master i slave działają normalnie, więc każdy blok danych jest dostępny do wyszukiwania na dwóch różnych serwerach (podległy serwer EBS ma słaby procesor, więc go nie bierzemy pod uwagę). Dzielimy zadanie między nimi, więc łącznie mamy dostępne 16 rdzeni.
Wiele rdzeni: w najbliższej przyszłości rozdzielimy dane między serwery w taki sposób, aby wszystkie uczestniczyły w przetwarzaniu każdego nietrywialnego zapytania. Będzie pracował każdy rdzeń. [Uwaga: zrealizowaliś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 brute force jest dość stabilna wydajność. Zazwyczaj wyszukiwanie nie jest zbyt wrażliwe na szczegóły zadania i zbioru danych (myślę, że dlatego nazywa się to „brute force”).
Indeks słów kluczowych czasami zwraca niesamowicie szybki wynik, a czasami nie. Załóżmy, że masz 50 GB logów, w których termin „customer_5987235982” występuje dokładnie trzy razy. Wyszukiwanie według tego terminu bezpośrednio z indeksu wskazuje trzy lokalizacje i kończy się natychmiast. Ale złożone wyszukiwanie z użyciem symboli zastępczych może skanować tysiące słów kluczowych i zająć dużo czasu.
Z drugiej strony, wyszukiwanie metodą brute force dla każdego zapytania wykonuje się z mniej więcej taką samą prędkością. Wyszukiwanie długich słów jest lepsze, ale nawet wyszukiwanie jednego znaku odbywa się wystarczająco szybko.
Prostota metody brute force sprawia, że jej wydajność jest bliska teoretycznemu maksimum. Jest tutaj mniej możliwości na nieprzewidziane przeciążenie dysków, konflikty przy blokadach, pogoń za wskaźnikiem i tysiące innych przyczyn awarii. Właśnie spojrzałem na zapytania złożone przez użytkowników Scalyr w zeszłym tygodniu na naszym najbardziej obciążonym serwerze. Było 14 000 zapytań. Zaledwie osiem z nich zajęło więcej niż jedną sekundę; 99% wykonano w ciągu 111 milisekund (jeśli nie używałeś narzędzi do analizy logów, uwierz mi: jest szybko).
Stabilna, niezawodna wydajność jest kluczowa dla użyteczności usługi. Jeśli czasami spowalnia, użytkownicy postrzegają ją jako niewiarygodną i niechętnie z niej korzystają.
Wyszukiwanie w logach w działaniu
Oto mała animacja, która pokazuje wyszukiwanie Scalyr w działaniu. Mamy konto demonstracyjne, na które importujemy każde zdarzenie z każdego publicznego repozytorium Github. W tej demonstracji przyglądam się danym z tygodnia: około 600 MB surowych logów.
Wideo zostało nagrane na żywo, bez specjalnego przygotowania, na moim komputerze stacjonarnym (około 5000 kilometrów od serwera). Wydajność, którą zobaczysz, w dużej mierze zawdzięczasz , a także szybkiemu i niezawodnemu backendowi. Za każdym razem, gdy następuje pauza bez wskaźnika „loading”, robię pauzę, abyś miał czas do przeczytania, co zamierzam kliknąć.
Na zakończenie
Przy przetwarzaniu dużych zbiorów danych ważne jest, aby wybrać dobry algorytm, ale „dobry” nie oznacza „dziwaczny”. Zastanów się, jak twój kod będzie działać w praktyce. Niektóre czynniki kluczowe w rzeczywistym świecie nie wychodzą na jaw podczas teoretycznej analizy algorytmów. Prostsze algorytmy są łatwiejsze do optymalizacji i są stabilniejsze w sytuacjach granicznych.
Zastanów się również nad kontekstem, w którym wykonywany będzie kod. W naszym przypadku potrzebne są dość mocne serwery do zarządzania zadaniami działającymi w tle. Użytkownicy stosunkowo rzadko inicjują wyszukiwanie, więc możemy pożyczyć całą grupę serwerów na krótki czas niezbędny do przeprowadzenia każdego wyszukiwania.
Metodą brute force zrealizowaliśmy szybkie, niezawodne, elastyczne wyszukiwanie w zbiorze logów. Mamy nadzieję, że te pomysły będą przydatne w twoich projektach.
Poprawka: nagłówek i tekst zmieniły się z „Wyszukiwanie z prędkością 20 GB na sekundę” na „Wyszukiwanie z prędkością 1 TB na sekundę”, aby odzwierciedlić wzrost wydajności w ciągu ostatnich kilku lat. To zwiększenie prędkości jest przede wszystkim związane ze zmianą rodzaju i liczby serwerów EC2, które dzisiaj uruchamiamy, by obsłużyć rosnącą bazę klientów. W najbliższym czasie oczekujemy zmian, które zapewnią kolejne znaczące zwiększenie efektywności, i z niecierpliwością czekamy, aby móc o tym opowiedzieć.
Źródło: habr.com
