TL;DR: Pred štyrmi rokmi som odišiel z Google s nápadom na nový nástroj na monitorovanie serverov. Myšlienkou bolo spojiť zvyčajne izolované funkcie do jednej služby a analýza protokolov, zber metrík, a prístrojové dosky. Jednou zo zásad je, že služba musí byť pravdivá rýchlo, ktorý poskytuje vývojárom jednoduchý, interaktívny a príjemný zážitok. Vyžaduje si to spracovanie multigigabajtových dátových súborov v zlomkoch sekundy, pričom je potrebné dodržať rozpočet. Existujúce nástroje na správu protokolov sú často pomalé a neohrabané, takže sme čelili dobrej výzve: inteligentne navrhnúť nástroj, ktorý používateľom poskytne novú skúsenosť.
Tento článok popisuje, ako sme v Scalyr vyriešili tento problém aplikáciou metód starej školy, prístupu hrubej sily, odstránením nepotrebných vrstiev a vyhýbaním sa zložitým dátovým štruktúram. Tieto lekcie môžete použiť na svoje vlastné inžinierske problémy.
Sila starej školy
Analýza protokolov zvyčajne začína vyhľadávaním: nájdite všetky správy, ktoré zodpovedajú určitému vzoru. V Scalyr sú to desiatky alebo stovky gigabajtov protokolov z mnohých serverov. Moderné prístupy spravidla zahŕňajú vytvorenie nejakej komplexnej dátovej štruktúry optimalizovanej na vyhľadávanie. Určite som to videl na Googli, kde sú v takýchto veciach celkom dobrí. Rozhodli sme sa však pre oveľa hrubší prístup: lineárne skenovanie protokolov. A fungovalo to – poskytujeme prehľadávateľné rozhranie, ktoré je rádovo rýchlejšie ako naši konkurenti (pozri animáciu na konci).
Kľúčovým poznatkom bolo, že moderné procesory sú skutočne veľmi rýchle pri jednoduchých a priamočiarych operáciách. Toto je ľahké prehliadnuť v zložitých, viacvrstvových systémoch, ktoré sa spoliehajú na rýchlosť I/O a sieťové operácie, a takéto systémy sú dnes veľmi bežné. Preto sme vyvinuli dizajn, ktorý minimalizuje vrstvy a nadmerné nečistoty. S viacerými procesormi a servermi paralelne dosahuje rýchlosť vyhľadávania 1 TB za sekundu.
Hlavné poznatky z tohto článku:
- Hľadanie hrubou silou je životaschopný prístup na riešenie rozsiahlych problémov v reálnom svete.
- Hrubá sila je dizajnová technika, nie riešenie bez práce. Ako každá technika, je vhodnejšia na niektoré problémy ako iné a môže byť implementovaná zle alebo dobre.
- Hrubá sila je obzvlášť dobrá na dosiahnutie stabilný výkon.
- Efektívne využitie hrubej sily si vyžaduje optimalizáciu kódu a použitie dostatočných zdrojov v správnom čase. Je vhodný, ak sú vaše servery veľmi zaťažené neužívateľským zaťažením a používateľské operácie zostávajú prioritou.
- Výkon závisí od návrhu celého systému, nielen od algoritmu vnútornej slučky.
(Tento článok popisuje vyhľadávanie údajov v pamäti. Vo väčšine prípadov, keď používateľ vykoná vyhľadávanie v protokoloch, servery Scalyr ich už uložili do vyrovnávacej pamäte. Nasledujúci článok bude diskutovať o vyhľadávaní protokolov bez vyrovnávacej pamäte. Platia rovnaké princípy: efektívny kód, hrubá sila s veľkými výpočtovými zdrojmi).
Metóda hrubej sily
Tradične sa veľký súbor údajov vyhľadáva pomocou indexu kľúčových slov. Pri použití v protokoloch servera to znamená vyhľadávanie každého jedinečného slova v protokole. Pre každé slovo musíte urobiť zoznam všetkých inklúzií. Vďaka tomu je ľahké nájsť všetky správy s týmto slovom, napríklad „chyba“, „firefox“ alebo „transaction_16851951“ – stačí sa pozrieť do indexu.
Tento prístup som použil v spoločnosti Google a fungovalo to dobre. Ale v Scalyr hľadáme protokoly bajt po byte.
prečo? Z hľadiska abstraktného algoritmu sú indexy kľúčových slov oveľa efektívnejšie ako vyhľadávanie hrubou silou. Nepredávame však algoritmy, ale výkon. A výkon nie je len o algoritmoch, ale aj o systémovom inžinierstve. Musíme zvážiť všetko: objem dát, typ vyhľadávania, dostupný hardvér a softvérový kontext. Rozhodli sme sa, že pre náš konkrétny problém je niečo ako „grep“ vhodnejšie ako index.
Indexy sú skvelé, ale majú obmedzenia. Jedno slovo sa nájde ľahko. Ale vyhľadávanie správ s viacerými slovami, ako napríklad „googlebot“ a „404“, je oveľa zložitejšie. Hľadanie frázy ako „nezachytená výnimka“ si vyžaduje ťažkopádnejší index, ktorý zaznamenáva nielen všetky správy s daným slovom, ale aj konkrétne umiestnenie slova.
Skutočný problém nastáva, keď nehľadáte slová. Povedzme, že chcete vidieť, aká veľká návštevnosť pochádza od robotov. Prvou myšlienkou je vyhľadať v protokoloch slovo „bot“. Takto nájdete niektorých robotov: Googlebot, Bingbot a mnoho ďalších. Ale tu „bot“ nie je slovo, ale jeho časť. Ak v indexe hľadáme výraz „bot“, nenájdeme žiadne príspevky so slovom „Googlebot“. Ak skontrolujete každé slovo v indexe a potom prehľadáte index pre nájdené kľúčové slová, vyhľadávanie sa výrazne spomalí. Výsledkom je, že niektoré protokolové programy neumožňujú vyhľadávanie častí slov alebo (v najlepšom prípade) umožňujú špeciálnu syntax s nižším výkonom. Tomuto sa chceme vyhnúť.
Ďalším problémom je interpunkcia. Chcete nájsť všetky žiadosti z 50.168.29.7? Čo sa týka ladenia protokolov obsahujúcich [error]? Dolné indexy zvyčajne vynechávajú interpunkciu.
Napokon, inžinieri milujú výkonné nástroje a niekedy sa problém dá vyriešiť iba regulárnym výrazom. Index kľúčových slov nie je na to veľmi vhodný.
Okrem toho aj indexy komplexné. Každú správu je potrebné pridať do niekoľkých zoznamov kľúčových slov. Tieto zoznamy by sa mali vždy uchovávať vo formáte, v ktorom sa dá ľahko vyhľadávať. Dotazy s frázami, fragmentmi slov alebo regulárnymi výrazmi je potrebné preložiť do operácií s viacerými zoznamami a výsledky naskenovať a skombinovať, aby sa vytvorila sada výsledkov. V kontexte rozsiahlej služby pre viacerých nájomníkov táto zložitosť vytvára problémy s výkonom, ktoré nie sú viditeľné pri analýze algoritmov.
Indexy kľúčových slov tiež zaberajú veľa miesta a úložný priestor je hlavným nákladom v systéme správy protokolov.
Na druhej strane každé vyhľadávanie môže spotrebovať veľa výpočtového výkonu. Naši používatelia oceňujú vysokorýchlostné vyhľadávanie jedinečných dopytov, ale takéto dopyty sa zadávajú pomerne zriedka. Pre typické vyhľadávacie dopyty, napríklad pre dashboard, používame špeciálne techniky (popíšeme ich v ďalšom článku). Iné požiadavky sú natoľko zriedkavé, že ich musíte len zriedka spracovať viac ako jednu naraz. To však neznamená, že naše servery nie sú zaneprázdnené: sú zaneprázdnené prácou s prijímaním, analýzou a komprimáciou nových správ, vyhodnocovaním upozornení, komprimáciou starých údajov atď. Máme teda pomerne značnú zásobu procesorov, ktoré možno použiť na vykonávanie dotazov.
Hrubá sila funguje, ak máte brutálny problém (a veľa sily)
Hrubá sila funguje najlepšie na jednoduché problémy s malými vnútornými slučkami. Často môžete optimalizovať vnútornú slučku tak, aby bežala pri veľmi vysokých rýchlostiach. Ak je kód zložitý, je oveľa ťažšie ho optimalizovať.
Náš vyhľadávací kód mal pôvodne pomerne veľkú vnútornú slučku. Správy ukladáme na stránkach v rozlíšení 4K; každá stránka obsahuje nejaké správy (v UTF-8) a metadáta pre každú správu. Metadáta sú štruktúra, ktorá kóduje dĺžku hodnoty, interné ID správy a ďalšie polia. Vyhľadávací cyklus vyzeral takto:
Toto je zjednodušená verzia skutočného kódu. Ale aj tu sú viditeľné viaceré umiestnenia objektov, kópie údajov a volania funkcií. JVM je celkom dobrý v optimalizácii volaní funkcií a prideľovaní dočasných objektov, takže tento kód fungoval lepšie, ako sme si zaslúžili. Počas testovania ho zákazníci celkom úspešne využívali. Nakoniec sme to však posunuli na ďalšiu úroveň.
(Môžete sa opýtať, prečo ukladáme správy v tomto formáte so 4K stránkami, textom a metadátami, namiesto toho, aby sme pracovali priamo s protokolmi. Existuje mnoho dôvodov, ktoré sa scvrkávajú na skutočnosť, že interne je Scalyr engine skôr ako distribuovaná databáza ako súborový systém. Textové vyhľadávanie sa často kombinuje s filtrami v štýle DBMS na okrajoch po analýze protokolu. Môžeme súčasne prehľadávať mnoho tisíc protokolov naraz a jednoduché textové súbory nie sú vhodné pre našu transakčnú, replikovanú, distribuovanú správu údajov).
Spočiatku sa zdalo, že takýto kód nie je príliš vhodný na optimalizáciu hrubou silou. "Skutočná práca" v String.indexOf() nedominoval ani profil CPU. To znamená, že samotná optimalizácia tejto metódy by nepriniesla výrazný efekt.
Stáva sa, že metadáta ukladáme na začiatok každej stránky a text všetkých správ v UTF-8 je zabalený na druhom konci. Využijúc to, prepísali sme slučku, aby sme prehľadali celú stránku naraz:
Táto verzia funguje priamo na pohľade raw byte[] a prehľadá všetky správy naraz na celej 4K stránke.
Toto je oveľa jednoduchšie optimalizovať pre metódu hrubej sily. Interná vyhľadávacia slučka sa volá súčasne pre celú stránku s rozlíšením 4K, nie samostatne v každom príspevku. Neexistuje žiadne kopírovanie údajov, žiadne prideľovanie objektov. A zložitejšie operácie s metadátami sa volajú len vtedy, keď je výsledok pozitívny, a nie pri každej správe. Týmto spôsobom sme odstránili veľa režijných nákladov a zvyšok záťaže sa sústredí do malej vnútornej vyhľadávacej slučky, ktorá sa dobre hodí na ďalšiu optimalizáciu.
Náš skutočný vyhľadávací algoritmus je založený na . Je podobný Boyer-Moorovmu algoritmu, pričom v každom kroku preskakuje približne dĺžku vyhľadávacieho reťazca. Hlavným rozdielom je, že kontroluje dva bajty naraz, aby sa minimalizovali falošné zhody.
Naša implementácia vyžaduje vytvorenie 64K vyhľadávacej tabuľky pre každé vyhľadávanie, ale to nie je nič v porovnaní s gigabajtmi údajov, ktoré prehľadávame. Vnútorná slučka spracováva niekoľko gigabajtov za sekundu na jednom jadre. V praxi sa stabilný výkon pohybuje okolo 1,25 GB za sekundu na každom jadre a je čo zlepšovať. Je možné eliminovať časť réžie mimo vnútornej slučky a plánujeme experimentovať s vnútornou slučkou v C namiesto Java.
Používame silu
Diskutovali sme o tom, že vyhľadávanie v protokoloch sa dá implementovať „približne“, ale koľko „moci“ máme? Pomerne veľa.
1 jadro: Pri správnom použití je jedno jadro moderného procesora samo o sebe dosť výkonné.
8 jadier: Momentálne používame servery Amazon hi1.4xlarge a i2.4xlarge SSD, každý s 8 jadrami (16 vlákien). Ako je uvedené vyššie, tieto jadrá sú zvyčajne zaneprázdnené operáciami na pozadí. Keď používateľ vykoná vyhľadávanie, operácie na pozadí sa pozastavia, čím sa uvoľní všetkých 8 jadier na vyhľadávanie. Vyhľadávanie sa zvyčajne dokončí v zlomku sekundy, po ktorej sa obnoví práca na pozadí (program obmedzovania zaisťuje, že záplava vyhľadávacích dopytov nezasahuje do dôležitej práce na pozadí).
16 jadier: pre spoľahlivosť organizujeme servery do skupín master/slave. Každý master má pod velením jeden SSD a jeden EBS server. Ak hlavný server zlyhá, server SSD okamžite zaujme jeho miesto. Takmer po celú dobu fungujú master a slave dobre, takže každý dátový blok je možné vyhľadávať na dvoch rôznych serveroch (podriadený server EBS má slabý procesor, takže to neuvažujeme). Rozdelíme medzi nich úlohu, aby sme mali k dispozícii celkovo 16 jadier.
Veľa jadier: V blízkej budúcnosti budeme distribuovať údaje medzi servery tak, aby sa všetky podieľali na spracovaní každej netriviálnej požiadavky. Každé jadro bude fungovať. [Poznámka: implementovali sme plán a zvýšili rýchlosť vyhľadávania na 1 TB/s, pozri poznámku na konci článku].
Jednoduchosť zaručuje spoľahlivosť
Ďalšou výhodou metódy hrubej sily je jej pomerne konzistentný výkon. Vyhľadávanie zvyčajne nie je veľmi citlivé na podrobnosti o probléme a súbore údajov (myslím, že preto sa to nazýva „hrubé“).
Index kľúčových slov niekedy prináša neuveriteľne rýchle výsledky a inokedy nie. Povedzme, že máte 50 GB denníkov, v ktorých sa výraz 'customer_5987235982' vyskytuje presne trikrát. Vyhľadávanie tohto výrazu počíta tri miesta priamo z indexu a okamžite sa dokončí. Komplexné vyhľadávanie pomocou zástupných znakov však môže skenovať tisíce kľúčových slov a trvať dlho.
Na druhej strane, vyhľadávanie hrubou silou funguje pri akomkoľvek dopyte viac-menej rovnakou rýchlosťou. Vyhľadávanie dlhých slov je lepšie, ale aj vyhľadávanie jedného znaku je celkom rýchle.
Jednoduchosť metódy hrubej sily znamená, že jej výkon sa blíži k teoretickému maximu. Existuje menej možností pre neočakávané preťaženie disku, spor o zámok, prenasledovanie ukazovateľa a tisíce ďalších dôvodov zlyhania. Práve som sa pozrel na požiadavky používateľov Scalyr minulý týždeň na našom najrušnejšom serveri. Žiadostí bolo 14 000. Presne osem z nich trvalo viac ako jednu sekundu; 99 % dokončených za 111 milisekúnd (ak ste nepoužili nástroje na analýzu protokolov, verte mi: je to rýchle).
Stabilný a spoľahlivý výkon je dôležitý pre jednoduché používanie služby. Ak bude pravidelne meškať, používatelia ho budú vnímať ako nespoľahlivý a nebudú ho chcieť používať.
Hľadanie denníka v akcii
Tu je krátka animácia, ktorá ukazuje vyhľadávanie Scalyr v akcii. Máme demo účet, kde importujeme každú udalosť do každého verejného úložiska Github. V tejto ukážke skúmam údaje za týždeň: približne 600 MB nespracovaných protokolov.
Video bolo nahrané naživo, bez špeciálnej prípravy, na mojej ploche (asi 5000 kilometrov od servera). Výkon, ktorý uvidíte, je z veľkej časti spôsobený , ako aj rýchly a spoľahlivý backend. Vždy, keď je pauza bez indikátora „načítavania“, robím pauzu ja, aby ste si mohli prečítať, čo sa chystám stlačiť.
na záver
Pri spracovaní veľkého množstva údajov je dôležité vybrať si dobrý algoritmus, ale „dobrý“ neznamená „vymyslený“. Zamyslite sa nad tým, ako bude váš kód fungovať v praxi. Teoretická analýza algoritmov vynecháva niektoré faktory, ktoré môžu byť v reálnom svete veľmi dôležité. Jednoduchšie algoritmy sa ľahšie optimalizujú a sú stabilnejšie v okrajových situáciách.
Myslite aj na kontext, v ktorom bude kód vykonaný. V našom prípade potrebujeme dostatočne výkonné servery na správu úloh na pozadí. Používatelia spúšťajú vyhľadávanie relatívne zriedkavo, takže si môžeme požičať celú skupinu serverov na krátku dobu potrebnú na dokončenie každého vyhľadávania.
Pomocou metódy hrubej sily sme implementovali rýchle, spoľahlivé a flexibilné vyhľadávanie v súbore denníkov. Dúfame, že tieto nápady budú užitočné pre vaše projekty.
Upraviť: Názov a text sa zmenili z „Vyhľadávanie rýchlosťou 20 GB za sekundu“ na „Vyhľadávanie rýchlosťou 1 TB za sekundu“, aby odrážali nárast výkonu za posledných niekoľko rokov. Toto zvýšenie rýchlosti je primárne spôsobené zmenami v type a počte serverov EC2, ktoré dnes uvádzame, aby slúžili našej zvýšenej zákazníckej základni. Čoskoro prídu zmeny, ktoré prinesú ďalšie dramatické zvýšenie prevádzkovej efektivity, a už sa nevieme dočkať, kedy sa o ne podelíme.
Zdroj: hab.com