TL;DR: Négy évvel ezelőtt elhagytam a Google-t egy új szerverfigyelő eszköz ötletével. Az ötlet az volt, hogy az általában elszigetelt funkciókat egyetlen szolgáltatásban egyesítsék és naplóelemzés, mérőszámok gyűjtése, és a műszerfalak. Az egyik alapelv, hogy a szolgáltatásnak valódinak kell lennie gyors, amely könnyű, interaktív, élvezetes élményt nyújt a devopoknak. Ehhez a több gigabájtos adathalmazok feldolgozása a másodperc töredéke alatt szükséges, miközben a költségvetésen belül marad. A meglévő naplókezelési eszközök gyakran lassúak és nehézkesek, ezért egy jó kihívással kellett szembenéznünk: okosan megtervezni egy olyan eszközt, amely új élményt nyújt a felhasználóknak.
Ez a cikk leírja, hogyan oldottuk meg ezt a problémát a Scalyrnél régi iskolai módszerek, a brute force megközelítés alkalmazásával, a szükségtelen rétegek kiiktatásával és az összetett adatstruktúrák elkerülésével. Ezeket a leckéket alkalmazhatja saját mérnöki problémáira.
Old School Power
A naplóelemzés általában kereséssel kezdődik: keresse meg az összes üzenetet, amely megfelel valamilyen mintának. A Scalyrben ezek több tíz vagy száz gigabájtnyi naplófájl sok szerverről. A modern megközelítések rendszerint valamilyen összetett, keresésre optimalizált adatstruktúra felépítését foglalják magukban. Minden bizonnyal láttam ezt a Google-on, ahol elég jók az ilyesmiben. De mi egy sokkal nyersebb megközelítés mellett döntöttünk: a naplók lineáris pásztázása mellett. És működött – olyan kereshető felületet biztosítunk, amely nagyságrendekkel gyorsabb versenytársainknál (lásd az animációt a végén).
A legfontosabb felismerés az volt, hogy a modern processzorok valóban nagyon gyorsak az egyszerű, egyértelmű műveletekben. Ezt könnyű kihagyni a bonyolult, többrétegű rendszerekben, amelyek I/O sebességre és hálózati műveletekre támaszkodnak, és az ilyen rendszerek manapság nagyon elterjedtek. Ezért olyan kialakítást fejlesztettünk ki, amely minimálisra csökkenti a rétegeket és a felesleges törmeléket. Ha több processzor és szerver párhuzamosan működik, a keresési sebesség eléri a másodpercenkénti 1 TB-ot.
A cikk legfontosabb gondolatai:
- A brute-force keresés életképes megközelítés valós, nagy léptékű problémák megoldására.
- A nyers erő tervezési technika, nem munka nélküli megoldás. Mint minden technika, ez is jobban megfelel bizonyos problémákra, mint mások, és rosszul vagy jól alkalmazható.
- A nyers erő különösen jó az eléréshez stabil termelékenység.
- A nyers erő hatékony használatához a kód optimalizálása és elegendő erőforrás megfelelő időben történő alkalmazása szükséges. Alkalmas, ha a szerverei nagy, nem felhasználói terhelésnek vannak kitéve, és a felhasználói műveletek továbbra is prioritást élveznek.
- A teljesítmény a teljes rendszer kialakításától függ, nem csak a belső hurok algoritmusától.
(Ez a cikk a memóriában lévő adatok keresését írja le. A legtöbb esetben, amikor a felhasználó naplókeresést végez, a Scalyr szerverek már gyorsítótárazták. A következő cikk a gyorsítótárazott naplók keresését tárgyalja. Ugyanazok az elvek érvényesek: hatékony kód, nyers erő nagy számítási erőforrásokkal).
Brute force módszer
Hagyományosan egy nagy adathalmazban keresnek kulcsszóindex segítségével. A szervernaplókra alkalmazva ez azt jelenti, hogy minden egyedi szót meg kell keresni a naplóban. Minden szóhoz listát kell készítenie az összes zárványról. Így könnyen megtalálhatja az összes ilyen szót tartalmazó üzenetet, például „hiba”, „firefox” vagy „tranzakció_16851951” – csak nézze meg az indexben.
Ezt a megközelítést alkalmaztam a Google-nál, és jól működött. De a Scalyrben bájtonként keresünk a naplókban.
Miért? Absztrakt algoritmikus szempontból a kulcsszóindexek sokkal hatékonyabbak, mint a brute force keresések. Mi azonban nem algoritmusokat, hanem teljesítményt adunk el. A teljesítmény pedig nem csak az algoritmusokról szól, hanem a rendszertervezésről is. Mindent figyelembe kell vennünk: az adatok mennyiségét, a keresés típusát, az elérhető hardver- és szoftverkörnyezetet. Úgy döntöttünk, hogy a mi konkrét problémánkra valami olyan, mint a „grep”, jobban megfelel, mint egy index.
Az indexek nagyszerűek, de vannak korlátaik. Egy szót könnyű megtalálni. A több szót tartalmazó üzenetek keresése, például „googlebot” és „404”, azonban sokkal nehezebb. Az olyan kifejezések kereséséhez, mint például az „elfogatlan kivétel”, bonyolultabb indexre van szükség, amely nemcsak az adott szót tartalmazó összes üzenetet rögzíti, hanem a szó konkrét helyét is.
Az igazi nehézség akkor jön, amikor nem keresel szavakat. Tegyük fel, hogy látni szeretné, mekkora forgalom érkezik a robotoktól. Az első gondolat az, hogy a naplókban keressük a „bot” szót. Így találhat néhány botot: Googlebot, Bingbot és sok más. De itt a „bot” nem egy szó, hanem annak egy része. Ha a „bot” kifejezésre keresünk az indexben, nem találunk olyan bejegyzéseket, amelyekben szerepel a „Googlebot” szó. Ha minden szót ellenőriz az indexben, majd az indexben keresi a talált kulcsszavakat, a keresés nagymértékben lelassul. Ennek eredményeként egyes naplóprogramok nem tesznek lehetővé részszavas keresést, vagy (a legjobb esetben) speciális szintaxist tesznek lehetővé alacsonyabb teljesítménnyel. Ezt szeretnénk elkerülni.
Egy másik probléma az írásjelek. Meg akarja találni az összes kérést a következőtől: 50.168.29.7? Mi a helyzet a tartalmazó hibakeresési naplókkal [error]? Az alsó indexek általában kihagyják az írásjeleket.
Végül a mérnökök szeretik a hatékony eszközöket, és néha egy probléma csak reguláris kifejezéssel oldható meg. A kulcsszóindex nem nagyon alkalmas erre.
Ezen kívül az indexek összetett. Minden üzenetet több kulcsszólistához kell hozzáadni. Ezeket a listákat mindig könnyen kereshető formátumban kell tartani. A kifejezéseket, szótöredékeket vagy reguláris kifejezéseket tartalmazó lekérdezéseket többlistás műveletekké kell lefordítani, az eredményeket pedig be kell vizsgálni és kombinálni kell eredményhalmaz létrehozásához. Egy nagyszabású, több bérlős szolgáltatás kontextusában ez a komplexitás teljesítménybeli problémákat okoz, amelyek nem láthatók az algoritmusok elemzésekor.
A kulcsszóindexek is sok helyet foglalnak el, és a tárolás jelentős költséget jelent egy naplókezelő rendszerben.
Másrészt minden keresés sok számítási energiát fogyaszthat. Felhasználóink nagyra értékelik az egyedi lekérdezések gyors keresését, de az ilyen lekérdezések viszonylag ritkán történnek. A tipikus keresési lekérdezésekhez, például egy irányítópulthoz, speciális technikákat használunk (a következő cikkben ismertetjük őket). Más kérések elég ritkák, ezért ritkán kell egyszerre több kérést feldolgoznia. Ez azonban nem jelenti azt, hogy szervereink nem lennének elfoglaltak: az új üzenetek fogadásával, elemzésével és tömörítésével, a riasztások kiértékelésével, a régi adatok tömörítésével stb. Így meglehetősen jelentős processzorkészlettel rendelkezünk, amelyekkel lekérdezéseket tudunk végrehajtani.
A nyers erő akkor működik, ha brutális problémája van (és sok erővel)
A nyers erő a kis belső hurkokkal rendelkező egyszerű problémáknál működik a legjobban. A belső hurkot gyakran úgy optimalizálhatja, hogy nagyon nagy sebességgel működjön. Ha a kód összetett, akkor sokkal nehezebb optimalizálni.
A keresési kódunk eredetileg meglehetősen nagy belső hurokkal rendelkezett. Az üzeneteket 4K felbontásban tároljuk az oldalakon; minden oldal tartalmaz néhány üzenetet (UTF-8-ban) és az egyes üzenetekhez tartozó metaadatokat. A metaadatok olyan struktúra, amely kódolja az érték hosszát, a belső üzenetazonosítót és egyéb mezőket. A keresési ciklus így nézett ki:
Ez a tényleges kód egyszerűsített változata. De még itt is látható több objektum elhelyezés, adatmásolat és függvényhívás. A JVM elég jól optimalizálja a függvényhívásokat és kiosztja az efemer objektumokat, így ez a kód jobban működött, mint amit megérdemeltünk volna. A tesztelés során az ügyfelek meglehetősen sikeresen használták. De végül átvittük a következő szintre.
(Megkérdezheti, hogy miért ebben a formátumban tároljuk az üzeneteket 4K-s oldalakkal, szövegekkel és metaadatokkal, ahelyett, hogy közvetlenül a naplókkal dolgoznánk. Számos oka van, amelyek arra vezethetők vissza, hogy a Scalyr motor belsőleg inkább egy elosztott adatbázishoz, mint egy fájlrendszer A szöveges keresést gyakran kombinálják a naplóelemzés után a margókban lévő DBMS-szerű szűrőkkel. Egyszerre sok ezer naplóban kereshetünk egyszerre, és az egyszerű szöveges fájlok nem alkalmasak tranzakciós, replikált, elosztott adatkezelésünkre).
Kezdetben úgy tűnt, hogy egy ilyen kód nem nagyon alkalmas a nyers erő optimalizálására. "Valódi munka" benne String.indexOf() nem is uralta a CPU profilt. Vagyis önmagában ennek a módszernek az optimalizálása nem hozna jelentős hatást.
Előfordul, hogy minden oldal elején metaadatokat tárolunk, és az összes UTF-8-as üzenet szövegét a másik végén csomagoljuk. Ezt kihasználva átírtuk a ciklust, hogy egyszerre keressünk a teljes oldalon:
Ez a verzió közvetlenül a nézetben működik raw byte[] és az összes üzenetet egyszerre keresi a teljes 4K oldalon.
Ez sokkal könnyebben optimalizálható a brute force módszerhez. A belső keresési hurkot egyszerre hívja meg a teljes 4K-s oldalra, nem pedig minden bejegyzésre külön. Nincs adatmásolás, nincs objektumok kiosztása. És az összetettebb metaadat-műveletek csak akkor hívódnak meg, ha az eredmény pozitív, és nem minden üzenetnél. Így rengeteg többletköltséget küszöböltünk ki, a terhelés többi része pedig egy kis belső keresőkörben összpontosul, ami kiválóan alkalmas a további optimalizálásra.
A tényleges keresési algoritmusunk a . Hasonló a Boyer-Moore algoritmushoz, minden lépésnél kihagyja a keresési karakterlánc hosszát. A fő különbség az, hogy egyszerre két bájtot ellenőriz, hogy minimalizálja a hamis egyezéseket.
Megvalósításunkhoz minden kereséshez létre kell hozni egy 64 1,25 méretű keresési táblát, de ez semmi ahhoz képest, hogy hány gigabájtnyi adatot keresünk. A belső hurok másodpercenként több gigabájtot dolgoz fel egyetlen magon. A gyakorlatban a stabil teljesítmény körülbelül XNUMX GB/s minden magon, és van még mit javítani. Lehetőség van a belső cikluson kívüli többletterhelés egy részének kiküszöbölésére, és azt tervezzük, hogy Java helyett C-ben belső ciklussal kísérletezünk.
Erőt alkalmazunk
Megbeszéltük, hogy a naplókeresés "nagyjából" megvalósítható, de mennyi "erőnk" van? Elég sok.
1 mag: Ha helyesen használják, egy modern processzor egyetlen magja önmagában is elég erős.
8 mag: Jelenleg Amazon hi1.4xlarge és i2.4xlarge SSD szervereken futunk, mindegyik 8 maggal (16 szál). Mint fentebb említettük, ezek a magok általában háttérműveletekkel vannak elfoglalva. Amikor a felhasználó keresést végez, a háttérben végzett műveletek felfüggesztésre kerülnek, így mind a 8 mag felszabadul a kereséshez. A keresés általában a másodperc töredéke alatt befejeződik, ezután folytatódik a háttérmunka (a fojtóprogram gondoskodik arról, hogy a keresési lekérdezések özöne ne zavarja a fontos háttérmunkát).
16 mag: a megbízhatóság érdekében a szervereket master/slave csoportokba rendezzük. Minden mesternek egy SSD és egy EBS szervere van a parancsnoksága alatt. Ha a fő szerver összeomlik, az SSD-szerver azonnal átveszi a helyét. Szinte mindig jól működik a master és a slave, így minden adatblokk két különböző szerveren kereshető (az EBS slave szervernek gyenge a processzora, ezért nem vesszük figyelembe). A feladatot felosztjuk közöttük, így összesen 16 mag áll rendelkezésünkre.
Sok mag: A közeljövőben úgy fogjuk elosztani az adatokat a szerverek között, hogy mindegyik részt vegyen minden nem triviális kérés feldolgozásában. Minden mag működni fog. [Jegyzet: megvalósítottuk a tervet, és 1 TB/s-ra növeltük a keresési sebességet, lásd a cikk végén található megjegyzést].
Az egyszerűség garantálja a megbízhatóságot
A brute force módszer másik előnye a meglehetősen egyenletes teljesítmény. Jellemzően a keresés nem túl érzékeny a probléma részleteire és az adathalmazra (azt hiszem, ezért hívják "durvának").
A kulcsszóindex néha hihetetlenül gyors eredményeket produkál, máskor pedig nem. Tegyük fel, hogy 50 GB naplója van, amelyben a „customer_5987235982” kifejezés pontosan háromszor jelenik meg. A kifejezésre történő keresés három helyet számol közvetlenül az indexből, és azonnal befejeződik. Az összetett helyettesítő karakteres keresések azonban több ezer kulcsszót is átvizsgálhatnak, és hosszú ideig tartanak.
Másrészt a brute force keresések többé-kevésbé azonos sebességgel működnek bármely lekérdezés esetén. A hosszú szavak keresése jobb, de még egyetlen karakter keresése is elég gyors.
A nyers erő módszerének egyszerűsége azt jelenti, hogy teljesítménye megközelíti az elméleti maximumot. Kevesebb lehetőség áll rendelkezésre a váratlan lemeztúlterhelés, a zárolási versengés, a mutató üldözése és a meghibásodások ezernyi egyéb oka esetén. Most néztem meg a Scalyr-felhasználók által a múlt héten a legforgalmasabb szerverünkön tett kéréseket. 14 000 kérés érkezett. Közülük pontosan nyolcnak kellett egy másodpercnél tovább; 99%-a 111 ezredmásodperc alatt készült el (ha még nem használt naplóelemző eszközöket, higgyen nekem: ez gyors).
A stabil, megbízható teljesítmény fontos a szolgáltatás egyszerű használatához. Ha időnként késik, a felhasználók megbízhatatlannak fogják tekinteni, és nem szívesen használják.
Naplókeresés működés közben
Íme egy rövid animáció, amely bemutatja a Scalyr keresést működés közben. Van egy demófiókunk, amelybe minden nyilvános Github-tárhelybe importálunk minden eseményt. Ebben a bemutatóban egy hétnyi adatot vizsgálok meg: körülbelül 600 MB nyers naplót.
A videót élőben rögzítettem, különösebb előkészület nélkül, az asztalomon (kb. 5000 kilométerre a szervertől). A látható teljesítmény nagyrészt ennek köszönhető , valamint egy gyors és megbízható háttér. Amikor szünet van „betöltés” jelző nélkül, akkor én állok szünetet, hogy elolvashassa, mit fogok lenyomni.
Összefoglalva
Nagy mennyiségű adat feldolgozásakor fontos a jó algoritmus kiválasztása, de a „jó” nem azt jelenti, hogy „divatos”. Gondolja át, hogyan fog működni a kód a gyakorlatban. Az algoritmusok elméleti elemzése kihagy néhány olyan tényezőt, amelyek a való világban nagy jelentőséggel bírhatnak. Az egyszerűbb algoritmusok könnyebben optimalizálhatók és stabilabbak élhelyzetekben.
Gondoljon arra is, hogy a kód milyen környezetben kerül végrehajtásra. Esetünkben kellő teljesítményű szerverekre van szükségünk a háttérfeladatok kezeléséhez. A felhasználók viszonylag ritkán indítanak keresést, így egy teljes szervercsoportot kölcsönözhetünk az egyes keresések befejezéséhez szükséges rövid időre.
Brute force módszert alkalmazva gyors, megbízható, rugalmas keresést hajtottunk végre egy sor naplóban. Reméljük, hogy ezek az ötletek hasznosak lesznek a projektjeihez.
Szerkesztés: A cím és a szöveg a „Keresés 20 GB/másodperccel” helyett „Keresés 1 TB/s sebességgel” módosult, tükrözve az elmúlt néhány évben tapasztalt teljesítménynövekedést. Ez a sebességnövekedés elsősorban a megnövekedett ügyfélbázisunk kiszolgálására felállított EC2 szerverek típusában és számában bekövetkezett változásoknak köszönhető. Hamarosan olyan változások jönnek, amelyek újabb drámai lökést adnak a működési hatékonyságban, és alig várjuk, hogy megosszuk őket.
Forrás: will.com