TL;DR: Prieš ketverius metus palikau „Google“ su idėja apie naują serverio stebėjimo įrankį. Idėja buvo sujungti paprastai izoliuotas funkcijas į vieną paslaugą ir žurnalų analizė, metrikos rinkimas, ir prietaisų skydeliai. Vienas iš principų – paslauga turi būti tikrai greitas, suteikdamas „devops“ lengvą, interaktyvią ir malonią patirtį. Tam reikia apdoroti kelių gigabaitų duomenų rinkinius per sekundės dalis, neviršijant biudžeto. Esami žurnalų valdymo įrankiai dažnai yra lėti ir nepatogūs, todėl susidūrėme su dideliu iššūkiu: sumaniai sukurti įrankį, kuris suteiktų vartotojams naujos patirties.
Šiame straipsnyje aprašoma, kaip mes, Scalyr, išsprendėme šią problemą taikydami senosios mokyklos metodus, brutalios jėgos metodą, pašalindami nereikalingus sluoksnius ir išvengdami sudėtingų duomenų struktūrų. Šias pamokas galite pritaikyti savo inžinerinėms problemoms spręsti.
Senosios mokyklos galia
Žurnalo analizė paprastai prasideda paieška: suraskite visus pranešimus, atitinkančius tam tikrą šabloną. „Scalyr“ tai yra dešimtys ar šimtai gigabaitų žurnalų iš daugelio serverių. Šiuolaikiniai metodai, kaip taisyklė, apima tam tikros sudėtingos duomenų struktūros, optimizuotos paieškai, sukūrimą. Aš tikrai tai mačiau „Google“, kur jie gana gerai išmano tokius dalykus. Tačiau mes pasirinkome daug grubesnį metodą: linijinį rąstų nuskaitymą. Ir tai pavyko – pateikiame paieškos sąsają, kuri yra daug greičiau nei mūsų konkurentai (žr. animaciją pabaigoje).
Pagrindinė įžvalga buvo ta, kad šiuolaikiniai procesoriai iš tiesų labai greitai atlieka paprastas ir nesudėtingas operacijas. To lengva nepastebėti sudėtingose, daugiasluoksnėse sistemose, kurios priklauso nuo įvesties / išvesties greičio ir tinklo operacijų, ir tokios sistemos šiandien yra labai paplitusios. Taigi sukūrėme dizainą, kuris sumažina sluoksnius ir šiukšlių perteklių. Kai lygiagrečiai veikia keli procesoriai ir serveriai, paieškos greitis siekia 1 TB per sekundę.
Pagrindinės šio straipsnio pastabos:
- Brute-force paieška yra perspektyvus būdas sprendžiant realaus pasaulio didelio masto problemas.
- Brutalia jėga yra projektavimo technika, o ne sprendimas be darbo. Kaip ir bet kuri technika, ji geriau tinka kai kurioms problemoms nei kitoms ir gali būti įgyvendinta prastai arba gerai.
- Brutalia jėga ypač naudinga pasiekti stabilus produktyvumas.
- Norint efektyviai panaudoti brutalią jėgą, reikia optimizuoti kodą ir tinkamu laiku panaudoti pakankamai išteklių. Tai tinka, jei jūsų serveriai yra labai apkrauti ne naudotojais, o vartotojo operacijos išlieka prioritetinės.
- Našumas priklauso nuo visos sistemos konstrukcijos, o ne tik nuo vidinio ciklo algoritmo.
(Šiame straipsnyje aprašoma duomenų paieška atmintyje. Daugeliu atvejų, kai vartotojas atlieka paiešką žurnale, „Scalyr“ serveriai juos jau išsaugojo talpykloje. Kitame straipsnyje bus aptarta talpykloje išsaugotų žurnalų paieška. Galioja tie patys principai: efektyvus kodas, brutali jėga su dideliais skaičiavimo ištekliais).
Brutalios jėgos metodas
Tradiciškai didelio duomenų rinkinio ieškoma naudojant raktinių žodžių indeksą. Taikant serverio žurnalus, tai reiškia, kad reikia ieškoti kiekvieno unikalaus žodžio žurnale. Kiekvienam žodžiui turite sudaryti visų įtraukimų sąrašą. Tai leidžia lengvai rasti visus pranešimus su šiuo žodžiu, pvz., „error“, „firefox“ arba „transaction_16851951“ – tiesiog pažiūrėkite į rodyklę.
Naudojau šį metodą „Google“ ir jis veikė gerai. Tačiau „Scalyr“ žurnaluose ieškome baitas po baito.
Kodėl? Abstrakčiu algoritminiu požiūriu raktinių žodžių indeksai yra daug efektyvesni nei žiaurios jėgos paieškos. Tačiau mes parduodame ne algoritmus, o našumą. Našumas priklauso ne tik nuo algoritmų, bet ir su sistemų inžinerija. Turime atsižvelgti į viską: duomenų kiekį, paieškos tipą, turimą aparatinę ir programinę įrangą. Nusprendėme, kad mūsų konkrečiai problemai kažkas panašaus į „grep“ labiau tinka nei indeksas.
Indeksai yra puikūs, tačiau jie turi apribojimų. Vieną žodį lengva rasti. Tačiau ieškoti pranešimų su keliais žodžiais, pvz., „googlebot“ ir „404“, yra daug sunkiau. Ieškant tokios frazės kaip „nepagauta išimtis“, reikalinga sudėtingesnė rodyklė, kurioje būtų įrašyti ne tik visi pranešimai su šiuo žodžiu, bet ir konkreti žodžio vieta.
Tikrieji sunkumai atsiranda tada, kai neieškai žodžių. Tarkime, kad norite pamatyti, kiek srauto sulaukia robotai. Pirma mintis – žurnaluose ieškoti žodžio „bot“. Taip rasite kai kuriuos robotus: Googlebot, Bingbot ir daugelį kitų. Bet čia „botas“ yra ne žodis, o jo dalis. Jei indekse ieškosime „bot“, nerasime įrašų su žodžiu „Googlebot“. Jei patikrinsite kiekvieną žodį rodyklėje ir tada nuskaitysite rodyklėje rastus raktinius žodžius, paieška labai sulėtės. Dėl to kai kurios žurnalo programos neleidžia ieškoti dalies žodžių arba (geriausiu atveju) leidžia specialią sintaksę su mažesniu našumu. Norime to išvengti.
Kita problema yra skyrybos ženklai. Ar norite rasti visas užklausas nuo 50.168.29.7? Ką daryti su derinimo žurnalais, kuriuose yra [error]? Pradiniai indeksai paprastai praleidžia skyrybos ženklus.
Galiausiai, inžinieriai mėgsta galingus įrankius, o kartais problemą galima išspręsti tik naudojant reguliariąją išraišką. Raktinių žodžių indeksas tam nelabai tinka.
Be to, indeksai kompleksas. Kiekvienas pranešimas turi būti įtrauktas į kelis raktinių žodžių sąrašus. Šie sąrašai visada turėtų būti laikomi lengvai pasiekiamu formatu. Užklausos su frazėmis, žodžių fragmentais ar reguliariosiomis išraiškomis turi būti išverstos į kelių sąrašų operacijas, o rezultatai nuskaityti ir sujungti, kad būtų sukurtas rezultatų rinkinys. Didelės apimties, kelių nuomininkų paslaugos kontekste dėl šio sudėtingumo kyla našumo problemų, kurios nėra matomos analizuojant algoritmus.
Raktinių žodžių indeksai taip pat užima daug vietos, o saugojimas yra didelė žurnalo valdymo sistemos kaina.
Kita vertus, kiekviena paieška gali sunaudoti daug skaičiavimo galios. Mūsų vartotojai vertina sparčią unikalių užklausų paiešką, tačiau tokios užklausos atliekamos palyginti retai. Įprastoms paieškos užklausoms, pavyzdžiui, informacijos suvestinė, naudojame specialius metodus (juos apibūdinsime kitame straipsnyje). Kitos užklausos pateikiamos pakankamai retai, todėl retai tenka apdoroti daugiau nei vieną iš karto. Bet tai nereiškia, kad mūsų serveriai nėra užimti: jie yra užsiėmę naujų pranešimų priėmimu, analizavimu ir suspaudimu, įspėjimų vertinimu, senų duomenų glaudinimu ir pan. Taigi, turime gana didelę procesorių, kurie gali būti naudojami užklausoms vykdyti, pasiūlą.
Brutali jėga veikia, jei turite žiaurių problemų (ir daug jėgos)
Brutali jėga geriausiai veikia sprendžiant paprastas problemas, susijusias su mažomis vidinėmis kilpomis. Dažnai galite optimizuoti vidinę kilpą, kad ji veiktų labai dideliu greičiu. Jei kodas sudėtingas, jį optimizuoti yra daug sunkiau.
Mūsų paieškos kodas iš pradžių turėjo gana didelę vidinę kilpą. Saugome pranešimus puslapiuose 4K; kiekviename puslapyje yra keletas pranešimų (UTF-8) ir kiekvieno pranešimo metaduomenys. Metaduomenys yra struktūra, užkoduojanti reikšmės ilgį, vidinį pranešimo ID ir kitus laukus. Paieškos ciklas atrodė taip:
Tai supaprastinta tikrojo kodo versija. Tačiau net ir čia matomos kelios objektų vietos, duomenų kopijos ir funkcijų iškvietimai. JVM gana gerai optimizuoja funkcijų iškvietimus ir paskirsto trumpalaikius objektus, todėl šis kodas veikė geriau nei nusipelnėme. Bandymų metu klientai jį gana sėkmingai naudojo. Bet galiausiai perkėlėme į kitą lygį.
(Galite paklausti, kodėl saugome pranešimus šiuo formatu su 4K puslapiais, tekstu ir metaduomenimis, o ne tiesiogiai dirbame su žurnalais. Yra daug priežasčių, kurios susiveda į tai, kad Scalyr variklis yra labiau panašus į paskirstytą duomenų bazę, o ne į failų sistema. Teksto paieška dažnai derinama su DBMS stiliaus filtrais paraštėse po žurnalo analizavimo. Vienu metu galime ieškoti daugelyje tūkstančių žurnalų vienu metu, o paprasti tekstiniai failai netinka mūsų operacijų, replikuotų, paskirstytų duomenų tvarkymui).
Iš pradžių atrodė, kad toks kodas nelabai tinkamas žiaurios jėgos optimizavimui. „Tikras darbas“. String.indexOf() net nedominavo CPU profilyje. Tai yra, vien šio metodo optimizavimas didelio efekto neduos.
Taip atsitinka, kad metaduomenis saugome kiekvieno puslapio pradžioje, o visų pranešimų tekstas UTF-8 yra supakuotas kitame gale. Pasinaudodami tuo, perrašėme kilpą, kad iš karto būtų ieškoma visame puslapyje:
Ši versija veikia tiesiogiai rodinyje raw byte[] ir ieško visų pranešimų iš karto visame 4K puslapyje.
Tai daug lengviau optimizuoti brutalios jėgos metodui. Vidinė paieškos kilpa iškviečiama vienu metu visame 4K puslapyje, o ne atskirai kiekviename įraše. Nėra duomenų kopijavimo, objektų paskirstymo. Sudėtingesnės metaduomenų operacijos iškviečiamos tik tada, kai rezultatas yra teigiamas, o ne kiekviename pranešime. Tokiu būdu pašalinome daugybę papildomų išlaidų, o likusi apkrova sutelkta į mažą vidinę paieškos kilpą, kuri puikiai tinka tolesniam optimizavimui.
Mūsų tikrasis paieškos algoritmas yra pagrįstas . Jis panašus į Boyer-Moore algoritmą, kiekviename žingsnyje praleidžiant maždaug paieškos eilutės ilgį. Pagrindinis skirtumas yra tas, kad jis vienu metu tikrina du baitus, kad sumažintų klaidingas atitiktis.
Mūsų įgyvendinimui reikia sukurti 64 1,25 peržvalgos lentelę kiekvienai paieškai, bet tai nieko, palyginti su gigabaitais duomenų, kurių ieškome. Vidinė kilpa apdoroja kelis gigabaitus per sekundę viename branduolyje. Praktiškai stabilus kiekvieno branduolio našumas yra apie XNUMX GB per sekundę, todėl yra kur tobulėti. Galima pašalinti dalį papildomų išlaidų už vidinės kilpos ribų, todėl planuojame eksperimentuoti su vidiniu C ciklu vietoj Java.
Mes naudojame jėgą
Aptarėme, kad žurnalų paiešką galima įgyvendinti „apytiksliai“, bet kiek mes turime „galios“? Daugoka.
1 šerdis: Kai naudojamas teisingai, vienas šiuolaikinio procesoriaus branduolys yra gana galingas.
8 branduoliai: Šiuo metu dirbame Amazon hi1.4xlarge ir i2.4xlarge SSD serveriuose, kurių kiekvienas turi 8 branduolius (16 gijų). Kaip minėta pirmiau, šie branduoliai paprastai yra užimti foninėmis operacijomis. Kai vartotojas atlieka paiešką, foninės operacijos sustabdomos, todėl paieškai atlaisvinami visi 8 branduoliai. Paprastai paieška baigiama per sekundės dalį, po kurios atnaujinamas foninis darbas (drosavimo programa užtikrina, kad daugybė paieškos užklausų netrukdytų svarbiam foniniam darbui).
16 branduoliai: dėl patikimumo serverius suskirstome į pagrindines/pagalbines grupes. Kiekvienas meistras turi vieną SSD ir vieną EBS serverį. Jei pagrindinis serveris sugenda, SSD serveris iš karto užima vietą. Beveik visą laiką pagrindinis ir pavaldinys veikia gerai, todėl kiekvieną duomenų bloką galima ieškoti dviejuose skirtinguose serveriuose (EBS vergas serveris turi silpną procesorių, todėl mes į tai neatsižvelgiame). Mes paskirstome užduotis tarp jų, kad iš viso būtų 16 branduolių.
Daug branduolių: artimiausiu metu duomenis paskirstysime tarp serverių taip, kad jie visi dalyvautų apdorojant kiekvieną nereikšmingą užklausą. Kiekvienas branduolys veiks. [Pastaba: įgyvendinome planą ir padidinome paieškos greitį iki 1 TB/s, žr. pastabą straipsnio pabaigoje].
Paprastumas užtikrina patikimumą
Kitas brutalios jėgos metodo pranašumas yra gana nuoseklus veikimas. Paprastai paieška nėra labai jautri problemos detalėms ir duomenų rinkiniui (manau, kad todėl ji vadinama „rupia“).
Raktinių žodžių indeksas kartais duoda neįtikėtinai greitus rezultatus, o kartais ne. Tarkime, kad turite 50 GB žurnalų, kuriuose terminas „customer_5987235982“ pasirodo lygiai tris kartus. Šio termino paieška skaičiuoja tris vietas tiesiai iš indekso ir bus baigta akimirksniu. Tačiau sudėtingos pakaitos simbolių paieškos gali nuskaityti tūkstančius raktinių žodžių ir užtrukti ilgai.
Kita vertus, žiaurios jėgos paieškos atliekamos daugiau ar mažiau tokiu pačiu greičiu bet kuriai užklausai. Geriau ieškoti ilgų žodžių, tačiau net vieno simbolio paieška yra gana greita.
Brutalios jėgos metodo paprastumas reiškia, kad jo veikimas yra artimas teoriniam maksimumui. Yra mažiau netikėtų disko perkrovų, užrakinimo, žymeklio persekiojimo ir daugybės kitų gedimo priežasčių parinkčių. Ką tik peržiūrėjau Scalyr vartotojų užklausas praėjusią savaitę mūsų judriausiame serveryje. Buvo 14 000 prašymų. Lygiai aštuoni iš jų užtruko daugiau nei vieną sekundę; 99 % atlikta per 111 milisekundžių (jei nenaudojote žurnalo analizės įrankių, patikėkite manimi: tai greita).
Stabilus, patikimas veikimas yra svarbus norint patogiai naudotis paslauga. Jei jis periodiškai vėluoja, vartotojai jį suvoks kaip nepatikimą ir nenorės juo naudotis.
Žurnalo paieška veikia
Štai trumpa animacija, rodanti, kaip veikia Scalyr paieška. Turime demonstracinę paskyrą, į kurią importuojame kiekvieną įvykį kiekvienoje viešoje „Github“ saugykloje. Šioje demonstracijoje aš išnagrinėju savaitės duomenis: maždaug 600 MB neapdorotų žurnalų.
Vaizdo įrašas buvo įrašytas gyvai, be specialaus pasiruošimo, mano darbalaukyje (apie 5000 kilometrų nuo serverio). Spektaklis, kurį pamatysite, daugiausia priklauso nuo to , taip pat greita ir patikima backend. Kai yra pauzė be „įkrovimo“ indikatoriaus, pristabdau aš, kad galėtumėte perskaityti, ką aš paspaudžiu.
užbaigiant
Apdorojant didelius duomenų kiekius, svarbu pasirinkti gerą algoritmą, tačiau „geras“ nereiškia „išgalvotas“. Pagalvokite, kaip jūsų kodas veiks praktiškai. Teorinė algoritmų analizė nepaiso kai kurių veiksnių, kurie gali būti labai svarbūs realiame pasaulyje. Paprastesnius algoritmus lengviau optimizuoti ir jie yra stabilesni kraštutinėse situacijose.
Taip pat pagalvokite apie kontekstą, kuriame kodas bus vykdomas. Mūsų atveju mums reikia pakankamai galingų serverių, kad galėtume valdyti fonines užduotis. Vartotojai paieškas inicijuoja palyginti retai, todėl galime pasiskolinti visą serverių grupę trumpam laikotarpiui, kurio reikia kiekvienai paieškai atlikti.
Naudodami brutalios jėgos metodą įgyvendinome greitą, patikimą ir lanksčią paiešką rąstų rinkinyje. Tikimės, kad šios idėjos bus naudingos jūsų projektams.
Redaguoti: Pavadinimas ir tekstas pakeisti iš „Ieškoti 20 GB per sekundę“ į „Ieškoti 1 TB per sekundę“, kad atspindėtų našumo padidėjimą per pastaruosius kelerius metus. Šį spartos padidėjimą visų pirma lėmė EC2 serverių tipo ir skaičiaus pasikeitimai, kuriuos šiandien statome, kad aptarnautume išaugusią klientų bazę. Netrukus bus pokyčių, kurie dar kartą dramatiškai padidins veiklos efektyvumą, ir mes nekantraujame jais pasidalinti.
Šaltinis: www.habr.com