TL;DR: Před čtyřmi lety jsem odešel z Google s nápadem na nový nástroj pro monitorování serverů. Cílem bylo spojit obvykle izolované funkce do jedné služby a analýza protokolů, sběr metrik, a přístrojové desky. Jednou ze zásad je, že služba musí být opravdová rychle, poskytující vývojářům snadný, interaktivní a příjemný zážitek. To vyžaduje zpracování mnohagigabajtových datových sad ve zlomcích sekundy při zachování rozpočtu. Stávající nástroje pro správu protokolů jsou často pomalé a neohrabané, takže jsme stáli před dobrou výzvou: chytře navrhnout nástroj, který uživatelům poskytne nové zkušenosti.
Tento článek popisuje, jak jsme ve Scalyr tento problém vyřešili aplikací metod staré školy, přístupu hrubé síly, odstraněním zbytečných vrstev a vyhýbáním se složitým datovým strukturám. Tyto lekce můžete aplikovat na své vlastní inženýrské problémy.
Síla staré školy
Analýza protokolů obvykle začíná hledáním: najděte všechny zprávy, které odpovídají určitému vzoru. Ve Scalyru jsou to desítky nebo stovky gigabajtů protokolů z mnoha serverů. Moderní přístupy zpravidla zahrnují konstrukci nějaké složité datové struktury optimalizované pro vyhledávání. Určitě jsem to viděl na Googlu, kde jsou v tomhle druhu docela dobří. Ale rozhodli jsme se pro mnohem hrubší přístup: lineární skenování protokolů. A fungovalo to – poskytujeme prohledávatelné rozhraní, které je řádově rychlejší než naši konkurenti (viz animace na konci).
Klíčovým poznatkem bylo, že moderní procesory jsou skutečně velmi rychlé při jednoduchých a přímočarých operacích. To lze snadno přehlédnout ve složitých, vícevrstvých systémech, které se spoléhají na rychlost I/O a síťové operace, a takové systémy jsou dnes velmi běžné. Proto jsme vyvinuli design, který minimalizuje vrstvy a přebytečné nečistoty. S více procesory a servery paralelně dosahuje rychlost vyhledávání 1 TB za sekundu.
Klíčové poznatky z tohoto článku:
- Hledání hrubou silou je životaschopný přístup k řešení skutečných problémů velkého rozsahu.
- Hrubá síla je konstrukční technika, nikoli řešení bez práce. Jako každá technika je pro některé problémy vhodnější než jiné a může být implementována špatně nebo dobře.
- Hrubá síla je zvláště dobrá pro dosažení stabilní produktivita.
- Efektivní použití hrubé síly vyžaduje optimalizaci kódu a použití dostatečných zdrojů ve správný čas. Je vhodný, pokud jsou vaše servery silně neuživatelsky vytíženy a uživatelská operace zůstává prioritou.
- Výkon závisí na návrhu celého systému, nejen na algoritmu vnitřní smyčky.
(Tento článek popisuje vyhledávání dat v paměti. Ve většině případů, když uživatel provádí prohledávání protokolů, servery Scalyr je již uložily do mezipaměti. Další článek pojednává o vyhledávání neuložených protokolů. Platí stejné zásady: efektivní kód, hrubá síla s velkými výpočetními zdroji).
Metoda hrubé síly
Tradičně se velký soubor dat prohledává pomocí indexu klíčových slov. Při použití v protokolech serveru to znamená hledání každého jedinečného slova v protokolu. Pro každé slovo je třeba vytvořit seznam všech inkluzí. Díky tomu lze snadno najít všechny zprávy s tímto slovem, například „chyba“, „firefox“ nebo „transaction_16851951“ – stačí se podívat do indexu.
Tento přístup jsem použil ve společnosti Google a fungovalo to dobře. Ale ve Scalyru prohledáváme logy bajt po bajtu.
Proč? Z abstraktního algoritmického hlediska jsou indexy klíčových slov mnohem efektivnější než vyhledávání hrubou silou. Neprodáváme však algoritmy, ale výkon. A výkon není jen o algoritmech, ale také o systémovém inženýrství. Musíme vzít v úvahu vše: objem dat, typ vyhledávání, dostupný hardware a softwarový kontext. Rozhodli jsme se, že pro náš konkrétní problém je něco jako „grep“ vhodnější než index.
Indexy jsou skvělé, ale mají svá omezení. Jedno slovo je snadné najít. Ale vyhledávání zpráv s více slovy, jako je „googlebot“ a „404“, je mnohem obtížnější. Hledání fráze jako „nezachycená výjimka“ vyžaduje těžkopádnější index, který zaznamenává nejen všechny zprávy s tímto slovem, ale také konkrétní umístění slova.
Skutečný problém nastává, když nehledáte slova. Řekněme, že chcete vidět, kolik provozu pochází od robotů. První myšlenkou je vyhledat v protokolech slovo „bot“. Takto najdete některé roboty: Googlebot, Bingbot a mnoho dalších. Ale zde „bot“ není slovo, ale jeho část. Pokud v indexu hledáme „bot“, nenajdeme žádné příspěvky se slovem „Googlebot“. Pokud zkontrolujete každé slovo v rejstříku a poté v rejstříku vyhledáte nalezená klíčová slova, vyhledávání se značně zpomalí. Výsledkem je, že některé programy protokolů neumožňují hledání částí slov nebo (v nejlepším případě) umožňují speciální syntaxi s nižším výkonem. Tomu se chceme vyhnout.
Dalším problémem je interpunkce. Chcete najít všechny požadavky od 50.168.29.7? A co ladění protokolů obsahujících [error]? Dolní indexy obvykle přeskakují interpunkci.
Konečně, inženýři milují výkonné nástroje a někdy lze problém vyřešit pouze regulárním výrazem. K tomu se index klíčových slov příliš nehodí.
Kromě toho indexy komplex. Každá zpráva musí být přidána do několika seznamů klíčových slov. Tyto seznamy by měly být neustále uchovávány ve formátu, který lze snadno vyhledávat. Dotazy s frázemi, fragmenty slov nebo regulárními výrazy je třeba přeložit do operací s více seznamy a výsledky naskenovat a zkombinovat, aby se vytvořila sada výsledků. V kontextu rozsáhlé služby pro více nájemců tato složitost vytváří problémy s výkonem, které nejsou viditelné při analýze algoritmů.
Indexy klíčových slov také zabírají hodně místa a úložiště je hlavní náklad v systému správy protokolů.
Na druhou stranu každé vyhledávání může spotřebovat hodně výpočetního výkonu. Naši uživatelé oceňují vysokorychlostní vyhledávání unikátních dotazů, ale takové dotazy jsou zadávány poměrně zřídka. Pro typické vyhledávací dotazy, například pro dashboard, používáme speciální techniky (popíšeme je v příštím článku). Jiné požadavky jsou natolik vzácné, že jen zřídka musíte zpracovávat více než jeden najednou. To však neznamená, že naše servery nejsou zaneprázdněny: jsou zaneprázdněny prací s přijímáním, analýzou a komprimací nových zpráv, vyhodnocováním výstrah, komprimací starých dat a tak dále. Máme tedy poměrně významnou zásobu procesorů, které lze použít k provádění dotazů.
Hrubá síla funguje, pokud máte hrubý problém (a hodně síly)
Hrubá síla funguje nejlépe na jednoduché problémy s malými vnitřními smyčkami. Často můžete optimalizovat vnitřní smyčku tak, aby běžela velmi vysokou rychlostí. Pokud je kód složitý, je mnohem obtížnější jej optimalizovat.
Náš vyhledávací kód měl původně poměrně velkou vnitřní smyčku. Ukládáme zprávy na stránkách ve 4K; každá stránka obsahuje nějaké zprávy (v UTF-8) a metadata pro každou zprávu. Metadata jsou struktura, která kóduje délku hodnoty, interní ID zprávy a další pole. Vyhledávací cyklus vypadal takto:
Toto je zjednodušená verze skutečného kódu. Ale i zde je vidět vícenásobné umístění objektů, kopie dat a volání funkcí. JVM je docela dobrý v optimalizaci volání funkcí a přidělování pomíjivých objektů, takže tento kód fungoval lépe, než jsme si zasloužili. Během testování jej zákazníci poměrně úspěšně využívali. Ale nakonec jsme to posunuli na další úroveň.
(Můžete se ptát, proč ukládáme zprávy v tomto formátu se 4K stránkami, textem a metadaty, spíše než přímo pracovat s protokoly. Existuje mnoho důvodů, které se scvrkávaly na skutečnost, že interně je Scalyr engine spíše jako distribuovaná databáze než jako souborový systém. Textové vyhledávání je často kombinováno s filtry ve stylu DBMS na okrajích po analýze protokolu. Můžeme současně prohledávat mnoho tisíc protokolů najednou a jednoduché textové soubory nejsou vhodné pro naši transakční, replikovanou, distribuovanou správu dat).
Zpočátku se zdálo, že takový kód není příliš vhodný pro optimalizaci hrubou silou. "Skutečná práce" v String.indexOf() nedominoval ani profilu CPU. To znamená, že samotná optimalizace této metody by nepřinesla významný efekt.
Stává se, že na začátku každé stránky ukládáme metadata a na druhém konci je pak text všech zpráv v UTF-8. Využili jsme toho a přepsali jsme smyčku, abychom prohledali celou stránku najednou:
Tato verze funguje přímo na pohledu raw byte[] a prohledává všechny zprávy najednou na celé stránce 4K.
To je mnohem jednodušší optimalizovat pro metodu hrubé síly. Interní vyhledávací smyčka je volána současně pro celou stránku 4K, nikoli samostatně u každého příspěvku. Neexistuje žádné kopírování dat, žádné přidělování objektů. A složitější operace s metadaty jsou volány pouze tehdy, když je výsledek pozitivní, a ne u každé zprávy. Tímto způsobem jsme odstranili spoustu režií a zbytek zátěže se soustředí do malé vnitřní vyhledávací smyčky, která se dobře hodí pro další optimalizaci.
Náš skutečný vyhledávací algoritmus je založen na . Je podobný algoritmu Boyer-Moore, který v každém kroku vynechává přibližně délku vyhledávacího řetězce. Hlavním rozdílem je, že kontroluje dva bajty najednou, aby se minimalizovaly falešné shody.
Naše implementace vyžaduje vytvoření 64K vyhledávací tabulky pro každé vyhledávání, ale to není nic ve srovnání s gigabajty dat, kterými prohledáváme. Vnitřní smyčka zpracovává několik gigabajtů za sekundu na jednom jádru. V praxi se stabilní výkon pohybuje kolem 1,25 GB za vteřinu na každém jádru a je co zlepšovat. Je možné eliminovat část režie mimo vnitřní smyčku a plánujeme experimentovat s vnitřní smyčkou v C namísto Java.
Používáme sílu
Diskutovali jsme o tom, že vyhledávání v protokolech lze implementovat „zhruba“, ale jak velkou „moc“ máme? Docela dost.
1 jádro: Při správném použití je jedno jádro moderního procesoru samo o sobě poměrně výkonné.
8 jader: Momentálně běžíme na serverech Amazon hi1.4xlarge a i2.4xlarge SSD, každý s 8 jádry (16 vlákny). Jak bylo uvedeno výše, tato jádra jsou obvykle zaneprázdněna operacemi na pozadí. Když uživatel provede vyhledávání, operace na pozadí jsou pozastaveny, čímž se uvolní všech 8 jader pro vyhledávání. Vyhledávání je obvykle dokončeno ve zlomku sekundy, po které se obnoví práce na pozadí (program omezení rychlosti zajišťuje, že příval vyhledávacích dotazů nenaruší důležitou práci na pozadí).
16 jader: kvůli spolehlivosti organizujeme servery do skupin master/slave. Každý master má pod svým velením jeden SSD a jeden EBS server. Pokud dojde k selhání hlavního serveru, SSD server okamžitě zaujme jeho místo. Téměř po celou dobu fungují master a slave dobře, takže každý datový blok je prohledávatelný na dvou různých serverech (server EBS slave má slabý procesor, takže to nebereme v úvahu). Úlohu mezi ně rozdělíme, takže máme k dispozici celkem 16 jader.
Mnoho jader: V blízké budoucnosti budeme distribuovat data mezi servery tak, aby se všechny podílely na zpracování každého netriviálního požadavku. Každé jádro bude fungovat. [Poznámka: implementovali jsme plán a zvýšili rychlost vyhledávání na 1 TB/s, viz poznámka na konci článku].
Jednoduchost zajišťuje spolehlivost
Další výhodou metody hrubé síly je její poměrně konzistentní výkon. Vyhledávání obvykle není příliš citlivé na detaily problému a datové sady (myslím, že proto se nazývá „hrubé“).
Index klíčových slov někdy přináší neuvěřitelně rychlé výsledky a jindy ne. Řekněme, že máte 50 GB protokolů, ve kterých se výraz 'customer_5987235982' vyskytuje přesně třikrát. Vyhledávání tohoto výrazu počítá tři umístění přímo z indexu a bude dokončeno okamžitě. Složité vyhledávání pomocí zástupných znaků však může prohledat tisíce klíčových slov a trvat dlouho.
Na druhou stranu, vyhledávání hrubou silou funguje u jakéhokoli dotazu víceméně stejnou rychlostí. Hledání dlouhých slov je lepší, ale i hledání jediného znaku je celkem rychlé.
Jednoduchost metody hrubé síly znamená, že její výkon se blíží svému teoretickému maximu. Existuje méně možností pro neočekávané přetížení disku, spory o zámek, sledování ukazatelů a tisíce dalších důvodů selhání. Právě jsem se podíval na požadavky uživatelů Scalyr minulý týden na našem nejvytíženějším serveru. Žádostí bylo 14 000. Přesně osm z nich trvalo déle než jednu sekundu; 99 % dokončeno během 111 milisekund (pokud jste nepoužili nástroje pro analýzu protokolů, věřte mi: je to rychlé).
Stabilní a spolehlivý výkon je důležitý pro snadné používání služby. Pokud se periodicky zpožďuje, uživatelé jej budou vnímat jako nespolehlivé a zdráhají se jej používat.
Hledání protokolu v akci
Zde je krátká animace, která ukazuje vyhledávání Scalyr v akci. Máme demo účet, kam importujeme každou událost do každého veřejného úložiště Github. V této ukázce zkoumám data za týden: přibližně 600 MB nezpracovaných protokolů.
Video bylo nahráno živě, bez speciální přípravy, na mé ploše (asi 5000 kilometrů od serveru). Výkon, který uvidíte, je z velké části způsoben , stejně jako rychlý a spolehlivý backend. Kdykoli dojde k pauze bez indikátoru 'načítání', pozastavuji se já, abyste si mohli přečíst, co se chystám stisknout.
Konečně,
Při zpracovávání velkého množství dat je důležité zvolit dobrý algoritmus, ale „dobrý“ neznamená „fantastický“. Přemýšlejte o tom, jak bude váš kód fungovat v praxi. Teoretická analýza algoritmů vynechává některé faktory, které mohou mít v reálném světě velký význam. Jednodušší algoritmy se snadněji optimalizují a jsou stabilnější v okrajových situacích.
Přemýšlejte také o kontextu, ve kterém bude kód spuštěn. V našem případě potřebujeme dostatečně výkonné servery pro správu úloh na pozadí. Uživatelé zahajují vyhledávání relativně zřídka, takže si můžeme půjčit celou skupinu serverů na krátkou dobu potřebnou k dokončení každého vyhledávání.
Pomocí metody hrubé síly jsme implementovali rychlé, spolehlivé a flexibilní vyhledávání v sadě protokolů. Doufáme, že tyto nápady budou užitečné pro vaše projekty.
Upravit: Název a text se změnily z „Vyhledávání rychlostí 20 GB za sekundu“ na „Vyhledávání rychlostí 1 TB za sekundu“, aby odrážely nárůst výkonu za posledních několik let. Toto zvýšení rychlosti je způsobeno především změnami v typu a počtu serverů EC2, které dnes dodáváme, aby sloužily naší zvýšené zákaznické základně. Brzy se chystají změny, které poskytnou další dramatický nárůst provozní efektivity, a my se nemůžeme dočkat, až se o ně podělíme.
Zdroj: www.habr.com