ProHoster > Blogs > Administrācija > Meklēt ar ātrumu 1 TB/s

Meklēt ar ātrumu 1 TB/s

TL;DR: Pirms četriem gadiem es atstāju Google ar ideju par jaunu servera uzraudzÄ«bas rÄ«ku. Ideja bija apvienot parasti izolētas funkcijas vienā pakalpojumā kolekcija un žurnālu analÄ«ze, metrikas apkopoÅ”ana, brÄ«dinājumus un informācijas paneļiem. Viens no principiem ir tāds, ka pakalpojumam ir jābÅ«t patiesam ātri, nodroÅ”inot devops vienkārÅ”u, interaktÄ«vu un patÄ«kamu pieredzi. Å im nolÅ«kam ir jāapstrādā vairāku gigabaitu datu kopas sekundes daļās, nepārsniedzot budžetu. EsoÅ”ie žurnālu pārvaldÄ«bas rÄ«ki bieži ir lēni un neveikli, tāpēc mēs saskārāmies ar labu izaicinājumu: gudri izstrādāt rÄ«ku, lai sniegtu lietotājiem jaunu pieredzi.

Å ajā rakstā ir aprakstÄ«ts, kā mēs Scalyr atrisinājām Å”o problēmu, izmantojot vecās skolas metodes, brutālā spēka pieeju, novērÅ”ot nevajadzÄ«gus slāņus un izvairoties no sarežģītām datu struktÅ«rām. Å Ä«s nodarbÄ«bas varat izmantot savām inženiertehniskajām problēmām.

Vecās skolas spēks

Žurnāla analÄ«ze parasti sākas ar meklÄ“Å”anu: atrodiet visus ziņojumus, kas atbilst noteiktam modelim. Programmā Scalyr tie ir desmitiem vai simtiem gigabaitu žurnālu no daudziem serveriem. MÅ«sdienu pieejas, kā likums, ietver sarežģītas datu struktÅ«ras izveidi, kas optimizēta meklÄ“Å”anai. Es noteikti to esmu redzējis Google tÄ«klā, kur viņi ir diezgan labi Å”ajās lietās. Bet mēs izvēlējāmies daudz rupjāku pieeju: baļķu lineāro skenÄ“Å”anu. Un tas darbojās ā€” mēs nodroÅ”inām meklējamu saskarni, kas ir vairākas reizes ātrāka nekā mÅ«su konkurenti (skatiet animāciju beigās).

Galvenais ieskats bija tāds, ka mÅ«sdienu procesori patieŔām ir ļoti ātri, veicot vienkārÅ”as un vienkārÅ”as darbÄ«bas. To var viegli nepamanÄ«t sarežģītās, daudzslāņu sistēmās, kas balstās uz I/O ātrumu un tÄ«kla darbÄ«bām, un Ŕādas sistēmas mÅ«sdienās ir ļoti izplatÄ«tas. Tāpēc mēs izstrādājām dizainu, kas samazina slāņus un liekos gružus. Ja paralēli ir vairāki procesori un serveri, meklÄ“Å”anas ātrums sasniedz 1 TB sekundē.

Galvenās atziņas no Ŕī raksta:

  • Brutāla meklÄ“Å”ana ir dzÄ«votspējÄ«ga pieeja reālu, liela mēroga problēmu risināŔanai.
  • Brutālais spēks ir dizaina tehnika, nevis risinājums bez darba. Tāpat kā jebkura tehnika, tā ir labāk piemērota dažām problēmām nekā citām, un to var Ä«stenot slikti vai labi.
  • Brutāls spēks ir Ä«paÅ”i labs, lai sasniegtu stabils produktivitāte.
  • Lai efektÄ«vi izmantotu brutālu spēku, ir nepiecieÅ”ams optimizēt kodu un piemērot pietiekamus resursus Ä«stajā laikā. Tas ir piemērots, ja jÅ«su serveri ir pakļauti lielai lietotāju slodzei un lietotāju darbÄ«bas joprojām ir prioritāte.
  • Veiktspēja ir atkarÄ«ga no visas sistēmas konstrukcijas, nevis tikai no iekŔējās cilpas algoritma.

(Å ajā rakstā ir aprakstÄ«ta datu meklÄ“Å”ana atmiņā. Vairumā gadÄ«jumu, kad lietotājs veic meklÄ“Å”anu žurnālā, Scalyr serveri to jau ir saglabājuÅ”i keÅ”atmiņā. Nākamajā rakstā tiks apspriesta nekeÅ”atmiņā saglabāto žurnālu meklÄ“Å”ana. Tiek piemēroti tie paÅ”i principi: efektÄ«vs kods, brutāls spēks ar lieliem skaitļoÅ”anas resursiem).

Brutālā spēka metode

Tradicionāli liela datu kopa tiek meklēta, izmantojot atslēgvārdu indeksu. Lietojot servera žurnālos, tas nozÄ«mē, ka žurnālā ir jāmeklē katrs unikālais vārds. Katram vārdam ir jāizveido visu ieslēgumu saraksts. Tādējādi ir viegli atrast visus ziņojumus ar Å”o vārdu, piemēram, 'error', 'firefox' vai "transaction_16851951" ā€” vienkārÅ”i skatieties rādÄ«tājā.

Es izmantoju Å”o pieeju Google, un tā darbojās labi. Bet Scalyr mēs meklējam žurnālus pa baitam.

Kāpēc? No abstraktā algoritmiskā viedokļa atslēgvārdu indeksi ir daudz efektÄ«vāki nekā meklÄ“Å”ana ar brutālu spēku. Tomēr mēs nepārdodam algoritmus, bet gan veiktspēju. Un veiktspēja ir saistÄ«ta ne tikai ar algoritmiem, bet arÄ« par sistēmu inženieriju. Mums jāņem vērā viss: datu apjoms, meklÄ“Å”anas veids, pieejamā aparatÅ«ra un programmatÅ«ras konteksts. Mēs nolēmām, ka mÅ«su konkrētajai problēmai kaut kas lÄ«dzÄ«gs ā€œgrepā€ ir labāk piemērots nekā indekss.

Indeksi ir lieliski, taču tiem ir ierobežojumi. Vienu vārdu ir viegli atrast. Taču meklēt ziņojumus ar vairākiem vārdiem, piemēram, ā€œgooglebotā€ un ā€œ404ā€, ir daudz grÅ«tāk. Lai meklētu tādu frāzi kā ā€œnepieÄ·erts izņēmumsā€, ir nepiecieÅ”ams apgrÅ«tinoŔāks rādÄ«tājs, kas reÄ£istrē ne tikai visus ziņojumus ar Å”o vārdu, bet arÄ« konkrētā vārda atraÅ”anās vietu.

ÄŖstās grÅ«tÄ«bas rodas, kad nemeklē vārdus. Pieņemsim, ka vēlaties redzēt, cik daudz trafika nāk no robotprogrammatÅ«rām. Pirmā doma ir žurnālos meklēt vārdu 'bot'. Šādi jÅ«s atradÄ«siet dažus robotus: Googlebot, Bingbot un daudzus citus. Bet Å”eit "bots" nav vārds, bet gan tā daļa. Ja indeksā meklēsim ā€œbotā€, mēs neatradÄ«sim nevienu ziņu ar vārdu ā€œGooglebotā€. Ja pārbaudÄ«sit katru vārdu rādÄ«tājā un pēc tam pārmeklēsiet indeksā atrastos atslēgvārdus, meklÄ“Å”ana ievērojami palēnināsies. Rezultātā dažas žurnālprogrammas neļauj meklēt vārdu daļu vai (labākajā gadÄ«jumā) atļauj Ä«paÅ”u sintaksi ar zemāku veiktspēju. Mēs vēlamies no tā izvairÄ«ties.

Vēl viena problēma ir pieturzÄ«mes. Vai vēlaties atrast visus pieprasÄ«jumus no 50.168.29.7? Kas par atkļūdoÅ”anas žurnāliem, kas satur [error]? ApakÅ”raksti parasti izlaiž pieturzÄ«mes.

Visbeidzot, inženieri mÄ«l spēcÄ«gus rÄ«kus, un dažreiz problēmu var atrisināt tikai ar regulāru izteiksmi. Atslēgvārdu rādÄ«tājs tam nav Ä«paÅ”i piemērots.

Turklāt indeksi komplekss. Katrs ziņojums ir jāpievieno vairākiem atslēgvārdu sarakstiem. Å ie saraksti vienmēr ir jāsaglabā viegli meklējamā formātā. Vaicājumi ar frāzēm, vārdu fragmentiem vai regulārām izteiksmēm ir jāpārvērÅ” vairāku sarakstu operācijās, un rezultāti jāskenē un jāapvieno, lai izveidotu rezultātu kopu. Liela mēroga, vairāku nomnieku pakalpojuma kontekstā Ŕī sarežģītÄ«ba rada veiktspējas problēmas, kas nav redzamas, analizējot algoritmus.

Atslēgvārdu indeksi arÄ« aizņem daudz vietas, un uzglabāŔana ir lielas izmaksas žurnālu pārvaldÄ«bas sistēmā.

No otras puses, katra meklÄ“Å”ana var patērēt daudz skaitļoÅ”anas jaudas. MÅ«su lietotāji novērtē ātrdarbÄ«gu unikālu vaicājumu meklÄ“Å”anu, taču Ŕādi vaicājumi tiek veikti salÄ«dzinoÅ”i reti. Tipiskiem meklÄ“Å”anas vaicājumiem, piemēram, informācijas panelim, mēs izmantojam Ä«paÅ”us paņēmienus (mēs tos aprakstÄ«sim nākamajā rakstā). Citi pieprasÄ«jumi ir pietiekami reti, tāpēc jums reti ir jāapstrādā vairāki pieprasÄ«jumi vienlaikus. Taču tas nenozÄ«mē, ka mÅ«su serveri nav aizņemti: tie ir aizņemti ar jaunu ziņojumu saņemÅ”anu, analÄ«zi un saspieÅ”anu, brÄ«dinājumu izvērtÄ“Å”anu, veco datu saspieÅ”anu utt. Tādējādi mums ir diezgan ievērojams procesoru piedāvājums, ko var izmantot vaicājumu izpildei.

Brutālais spēks darbojas, ja jums ir rupja problēma (un daudz spēka)

Brutālais spēks vislabāk darbojas vienkārŔām problēmām ar mazām iekŔējām cilpām. Bieži vien jÅ«s varat optimizēt iekŔējo cilpu, lai tā darbotos ļoti lielā ātrumā. Ja kods ir sarežģīts, to optimizēt ir daudz grÅ«tāk.

MÅ«su meklÄ“Å”anas kodam sākotnēji bija diezgan liela iekŔējā cilpa. Mēs saglabājam ziņojumus lapās 4K; katrā lapā ir daži ziņojumi (UTF-8) un katra ziņojuma metadati. Metadati ir struktÅ«ra, kas kodē vērtÄ«bas garumu, iekŔējā ziņojuma ID un citus laukus. MeklÄ“Å”anas cikls izskatÄ«jās Ŕādi:

Meklēt ar ātrumu 1 TB/s

Å Ä« ir faktiskā koda vienkārÅ”ota versija. Bet pat Å”eit ir redzami vairāki objektu izvietojumi, datu kopijas un funkciju izsaukumi. JVM diezgan labi spēj optimizēt funkciju izsaukumus un pieŔķirt Ä«slaicÄ«gus objektus, tāpēc Å”is kods darbojās labāk, nekā bijām pelnÄ«juÅ”i. TestÄ“Å”anas laikā klienti to diezgan veiksmÄ«gi izmantoja. Bet galu galā mēs to pacēlām uz nākamo lÄ«meni.

(Varat jautāt, kāpēc mēs glabājam ziņojumus Å”ajā formātā ar 4K lapām, tekstu un metadatiem, nevis strādājam tieÅ”i ar žurnāliem. Ir daudz iemeslu, kas izriet no tā, ka iekŔēji Scalyr dzinējs vairāk atgādina izkliedētu datu bāzi, nevis failu sistēma. Teksta meklÄ“Å”ana bieži tiek apvienota ar DBVS stila filtriem malās pēc žurnālu parsÄ“Å”anas. Mēs varam vienlaikus meklēt daudzos tÅ«kstoÅ”os žurnālu vienlaikus, un vienkārÅ”i teksta faili nav piemēroti mÅ«su darÄ«jumu, replicēto, izplatÄ«to datu pārvaldÄ«bai).

Sākotnēji Ŕķita, ka Ŕāds kods nav Ä«paÅ”i piemērots brutālā spēka optimizācijai. "ÄŖsts darbs". String.indexOf() pat nedominēja CPU profilā. Tas ir, Ŕīs metodes optimizÄ“Å”ana vien nedotu bÅ«tisku efektu.

Gadās, ka mēs glabājam metadatus katras lapas sākumā, un visu UTF-8 ziņojumu teksts tiek iesaiņots otrā galā. Izmantojot Å”o iespēju, mēs pārrakstÄ«jām cilpu, lai meklētu visā lapā uzreiz:

Meklēt ar ātrumu 1 TB/s

Å Ä« versija darbojas tieÅ”i skatā raw byte[] un meklē visus ziņojumus vienlaikus visā 4K lapā.

To ir daudz vieglāk optimizēt brutālā spēka metodei. IekŔējā meklÄ“Å”anas cilpa tiek izsaukta vienlaikus visai 4K lapai, nevis atseviŔķi katrā ziņā. Nav datu kopÄ“Å”anas, objektu pieŔķirÅ”anas. Un sarežģītākas metadatu darbÄ«bas tiek izsauktas tikai tad, ja rezultāts ir pozitÄ«vs, nevis katram ziņojumam. Tādā veidā mēs esam likvidējuÅ”i tonnu pieskaitāmo izdevumu, un pārējā slodze ir koncentrēta nelielā iekŔējā meklÄ“Å”anas cilpā, kas ir labi piemērota turpmākai optimizācijai.

MÅ«su faktiskais meklÄ“Å”anas algoritms ir balstÄ«ts uz lieliska LeonÄ«da Volņicka ideja. Tas ir lÄ«dzÄ«gs Boyer-Moore algoritmam, katrā solÄ« izlaižot aptuveni meklÄ“Å”anas virknes garumu. Galvenā atŔķirÄ«ba ir tā, ka tā vienlaikus pārbauda divus baitus, lai samazinātu viltus atbilstÄ«bu.

MÅ«su ievieÅ”anai ir nepiecieÅ”ams izveidot 64 1,25 uzmeklÄ“Å”anas tabulu katram meklējumam, taču tas nav nekas, salÄ«dzinot ar datu gigabaitiem, kurus mēs meklējam. IekŔējā cilpa apstrādā vairākus gigabaitus sekundē vienā kodolā. Praksē stabila veiktspēja ir aptuveni XNUMX GB sekundē katrā kodolā, un ir iespējas uzlabot. Ir iespējams novērst daļu no pieskaitāmajām izmaksām ārpus iekŔējās cilpas, un mēs plānojam eksperimentēt ar iekŔējo cilpu C valodā, nevis Java.

Mēs izmantojam spēku

Mēs esam apsprieduÅ”i, ka žurnālu meklÄ“Å”anu var Ä«stenot "aptuveni", bet cik daudz mums ir "jauda"? Diezgan daudz.

1 kodols: Pareizi lietojot, viens mūsdienu procesora kodols pats par sevi ir diezgan spēcīgs.

8 serdeņi: PaÅ”laik mēs strādājam Amazon hi1.4xlarge un i2.4xlarge SSD serveros, katrs ar 8 kodoliem (16 pavedieni). Kā minēts iepriekÅ”, Å”ie kodoli parasti ir aizņemti ar fona darbÄ«bām. Kad lietotājs veic meklÄ“Å”anu, fona darbÄ«bas tiek apturētas, tādējādi meklÄ“Å”anai tiek atbrÄ«voti visi 8 kodoli. MeklÄ“Å”ana parasti tiek pabeigta sekundes daļā, pēc kuras tiek atsākts fona darbs (drosÄ“Å”anas programma nodroÅ”ina, ka meklÄ“Å”anas vaicājumu straume netraucē svarÄ«gu fona darbu).

16 serdeņi: uzticamÄ«bas labad mēs sakārtojam serverus galvenajās/slavenajās grupās. Katram meistaram ir viens SSD un viens EBS serveris. Ja galvenais serveris avarē, SSD serveris nekavējoties ieņem tā vietu. GandrÄ«z visu laiku galvenais un slavenais darbojas labi, tāpēc katrs datu bloks ir meklējams divos dažādos serveros (EBS vergu serverim ir vājÅ” procesors, tāpēc mēs to neuzskatām). Mēs sadalām uzdevumus starp tiem, lai kopā bÅ«tu pieejami 16 kodoli.

Daudzi serdeņi: tuvākajā nākotnē mēs sadalÄ«sim datus starp serveriem tā, lai tie visi piedalÄ«tos katra nenozÄ«mÄ«ga pieprasÄ«juma apstrādē. Katrs kodols darbosies. [PiezÄ«me: Ä«stenojām plānu un palielinājām meklÄ“Å”anas ātrumu lÄ«dz 1 TB/s, skatiet piezÄ«mi raksta beigās].

VienkārŔība nodroŔina uzticamību

Vēl viena brutālā spēka metodes priekÅ”rocÄ«ba ir tās diezgan konsekventa veiktspēja. Parasti meklÄ“Å”ana nav Ä«paÅ”i jutÄ«ga pret problēmas un datu kopas detaļām (domāju, ka tāpēc to sauc par "rupju").

Atslēgvārdu rādÄ«tājs dažreiz sniedz neticami ātrus rezultātus, bet citreiz ne. Pieņemsim, ka jums ir 50 GB žurnālu, kuros vārds ā€œcustomer_5987235982ā€ tiek parādÄ«ts tieÅ”i trÄ«s reizes. Meklējot Å”o vārdu, tiek uzskaitÄ«tas trÄ«s atraÅ”anās vietas tieÅ”i no rādÄ«tāja, un tā tiks pabeigta uzreiz. Taču sarežģīta aizstājējzÄ«mju meklÄ“Å”ana var skenēt tÅ«kstoÅ”iem atslēgvārdu un aizņemt ilgu laiku.

No otras puses, brutālā spēka meklÄ“Å”ana jebkuram vaicājumam veic vairāk vai mazāk tādu paÅ”u ātrumu. Labāk ir meklēt garus vārdus, taču pat vienas rakstzÄ«mes meklÄ“Å”ana ir diezgan ātra.

Brutālā spēka metodes vienkārŔība nozÄ«mē, ka tās veiktspēja ir tuvu tās teorētiskajam maksimumam. Ir mazāk iespēju neparedzētai diska pārslodzei, bloÄ·Ä“Å”anai, rādÄ«tāja dzÄ«Å”anai un tÅ«kstoÅ”iem citu kļūmes iemeslu. Es tikko paskatÄ«jos uz Scalyr lietotāju pieprasÄ«jumiem pagājuÅ”ajā nedēļā mÅ«su noslogotākajā serverÄ«. Bija 14 000 pieprasÄ«jumu. TieÅ”i astoņiem no tiem vajadzēja vairāk nekā vienu sekundi; 99% pabeigti 111 milisekundēs (ja neesat izmantojis žurnālu analÄ«zes rÄ«kus, ticiet man: tas ir ātri).

Stabila, uzticama veiktspēja ir svarÄ«ga pakalpojuma ērtai lietoÅ”anai. Ja tas periodiski atpaliek, lietotāji to uztvers kā neuzticamu un nelabprāt to izmantos.

Žurnāla meklÄ“Å”ana darbÄ«bā

Å eit ir Ä«sa animācija, kas parāda Scalyr meklÄ“Å”anu darbÄ«bā. Mums ir demonstrācijas konts, kurā mēs importējam katru notikumu katrā publiskajā Github repozitorijā. Å ajā demonstrācijā es pārbaudu nedēļas datus: aptuveni 600 MB neapstrādātu žurnālu.

Video tika ierakstÄ«ts tieÅ”raidē, bez Ä«paÅ”as sagatavoÅ”anās, uz mana darbvirsmas (apmēram 5000 kilometrus no servera). Veiktspēja, ko redzēsit, lielā mērā ir saistÄ«ta ar tÄ«mekļa klienta optimizācija, kā arÄ« ātra un uzticama aizmugursistēma. Ikreiz, kad ir pauze bez ā€œielādesā€ indikatora, es apstājos, lai jÅ«s varētu izlasÄ«t, ko es gatavojos nospiest.

Meklēt ar ātrumu 1 TB/s

Noslēgumā

Apstrādājot lielu datu apjomu, ir svarÄ«gi izvēlēties labu algoritmu, taču ā€œlabsā€ nenozÄ«mē ā€œiedomātsā€. Padomājiet par to, kā jÅ«su kods darbosies praksē. Algoritmu teorētiskā analÄ«ze izslēdz dažus faktorus, kuriem var bÅ«t liela nozÄ«me reālajā pasaulē. VienkārŔāki algoritmi ir vieglāk optimizējami un stabilāki malu situācijās.

Padomājiet arÄ« par kontekstu, kurā kods tiks izpildÄ«ts. MÅ«su gadÄ«jumā mums ir nepiecieÅ”ami pietiekami jaudÄ«gi serveri, lai pārvaldÄ«tu fona uzdevumus. Lietotāji sāk meklÄ“Å”anu salÄ«dzinoÅ”i reti, tāpēc mēs varam aizņemties veselu serveru grupu uz Ä«su laiku, kas nepiecieÅ”ams katras meklÄ“Å”anas pabeigÅ”anai.

Izmantojot brutālā spēka metodi, mēs ieviesām ātru, uzticamu un elastÄ«gu meklÄ“Å”anu baļķu komplektā. Mēs ceram, ka Ŕīs idejas noderēs jÅ«su projektiem.

Rediģēt: Virsraksts un teksts ir mainÄ«ts no ā€œMeklēt ar ātrumu 20 GB sekundēā€ uz ā€œMeklēt ar ātrumu 1 TB sekundēā€, lai atspoguļotu veiktspējas pieaugumu dažu pēdējo gadu laikā. Å is ātruma pieaugums galvenokārt ir saistÄ«ts ar izmaiņām EC2 serveru tipā un skaitā, ko Å”odien ievietojam, lai apkalpotu mÅ«su palielināto klientu bāzi. DrÄ«zumā gaidāmas izmaiņas, kas nodroÅ”inās vēl vienu dramatisku darbÄ«bas efektivitātes pieaugumu, un mēs nevaram vien sagaidÄ«t, kad varēsim ar tām dalÄ«ties.

Avots: www.habr.com

Pievieno komentāru