TL;DR: Duela lau urte Google utzi nuen zerbitzariaren monitorizazio tresna berri baten ideia batekin. Ideia zen normalean isolatutako funtzioak zerbitzu bakarrean konbinatzea eta log azterketa, metrika bilketa, eta aginte-panelak. Printzipioetako bat zerbitzuak benetan izan behar duela da azkar, devopei esperientzia erraz, interaktibo eta atsegina eskainiz. Horrek gigabyte anitzeko datu multzoak segundo zatitan prozesatu behar ditu aurrekontuaren barruan mantenduz. Dauden erregistroak kudeatzeko tresnak sarritan motelak eta traketsak izaten dira, beraz, erronka on baten aurrean geunden: erabiltzaileei esperientzia berri bat emateko tresna bat modu adimentsuan diseinatzea.
Artikulu honek Scalyr-en arazo hau nola konpondu genuen deskribatzen du eskola zaharreko metodoak, indar gordinaren ikuspegia aplikatuz, beharrezkoak ez diren geruzak ezabatuz eta datu-egitura konplexuak saihestuz. Ikasgai hauek zure ingeniaritza arazoetan aplika ditzakezu.
Eskola Zaharreko boterea
Erregistroaren azterketa bilaketa batekin hasten da normalean: bilatu eredu jakin batekin bat datozen mezu guztiak. Scalyr-en, zerbitzari askotako hamar edo ehunka gigabyte erregistro dira. Ikuspegi modernoek, oro har, bilaketarako optimizatutako datu-egitura konplexu batzuk eraikitzen dituzte. Zalantzarik gabe, Googlen ikusi dut hau, non nahiko onak diren horrelako gauzetan. Baina askoz ikuspegi gordinago batean finkatu ginen: erregistroen eskaneatu lineala. Eta funtzionatu zuen: gure lehiakideek baino tamaina-aginduak bizkorrago den interfaze bilagarria eskaintzen dugu (ikusi animazioa amaieran).
Funtsezko ikuspegia zen prozesadore modernoak oso azkarrak direla eragiketa sinple eta zuzenetan. Erraza da hori galtzea I/O abiaduran eta sareko eragiketetan oinarritzen diren geruza anitzeko sistema konplexuetan, eta horrelako sistemak oso ohikoak dira gaur egun. Beraz, geruzak eta gehiegizko hondakinak gutxitzen dituen diseinu bat garatu genuen. Hainbat prozesadore eta zerbitzari paraleloan, bilaketa-abiadura segundoko TB 1era iristen da.
Artikulu honen ondorio nagusiak:
- Indar gordineko bilaketa ikuspegi bideragarria da mundu errealeko eta eskala handiko arazoak konpontzeko.
- Indar gordina diseinu teknika bat da, ez lanik gabeko irtenbide bat. Edozein teknika bezala, arazo batzuetarako beste batzuetara baino hobeto egokitzen da, eta gaizki edo ondo inplementa daiteke.
- Indar gordina lortzeko oso ona da egonkorra produktibitatea.
- Indar gordinaren erabilera eraginkorrak kodea optimizatzea eta baliabide nahikoak une egokian aplikatzea eskatzen du. Egokia da zure zerbitzariak erabiltzaileak ez diren karga handian badaude eta erabiltzaileen eragiketak lehentasuna izaten jarraitzen badu.
- Errendimendua sistema osoaren diseinuaren araberakoa da, ez bakarrik barruko begizta algoritmoaren araberakoa.
(Artikulu honek memorian datuak bilatzea deskribatzen du. Kasu gehienetan, erabiltzaile batek log bilaketa bat egiten duenean, Scalyr zerbitzariek dagoeneko gorde dute cachean. Hurrengo artikuluan cachean gabeko erregistroen bilaketari buruz hitz egingo da. Printzipio berdinak aplikatzen dira: kode eraginkorra, indar gordina. baliabide konputazional handiekin).
Indar gordinaren metodoa
Tradizionalki, datu-multzo handi bat gako-indize bat erabiliz bilatzen da. Zerbitzariaren erregistroetan aplikatzen denean, horrek esan nahi du erregistroko hitz bakarra bilatu behar dela. Hitz bakoitzeko, sartze guztien zerrenda egin behar duzu. Horrek hitz hau duten mezu guztiak aurkitzea errazten du, adibidez, 'error', 'firefox' edo "transaction_16851951" - aurkibidean begiratu besterik ez dago.
Ikuspegi hau Googlen erabili nuen eta ondo funtzionatu zuen. Baina Scalyr-en erregistroak bytez byte bilatzen ditugu.
Zergatik? Ikuspuntu algoritmiko abstraktutik, gako-indizeak indar gordinaren bilaketak baino askoz eraginkorragoak dira. Hala ere, ez ditugu algoritmoak saltzen, errendimendua saltzen dugu. Eta errendimendua ez da algoritmoei buruz bakarrik, baizik eta sistemen ingeniaritzari buruzkoa ere. Dena kontuan hartu behar dugu: datuen bolumena, bilaketa mota, eskuragarri dagoen hardware eta software testuingurua. Gure arazo berezirako, 'grep' bezalako zerbait indize bat baino hobeto egokitzen zela erabaki genuen.
Indizeak bikainak dira, baina mugak dituzte. Hitz bat erraza da aurkitzea. Baina hainbat hitz dituzten mezuak bilatzea, hala nola, 'googlebot' eta '404', askoz zailagoa da. "Atzeman gabeko salbuespena" bezalako esaldi bat bilatzeko indize astunagoa behar da, hitz hori duten mezu guztiak ez ezik, hitzaren kokapen zehatza ere erregistratzen dituena.
Benetako zailtasuna hitzen bila ez zaudenean dator. Demagun botetatik zenbat trafiko datorren ikusi nahi duzula. Lehenengo pentsamendua erregistroetan bilatzea da 'bot' hitza. Honela aurkituko dituzu bot batzuk: Googlebot, Bingbot eta beste asko. Baina hemen 'bot' ez da hitz bat, haren zati bat baizik. Indizean 'bot' bilatzen badugu, ez dugu 'Googlebot' hitza duen mezurik aurkituko. Indizeko hitz guztiak egiaztatzen badituzu eta ondoren aurkitutako gako-hitzen aurkibidea aztertzen baduzu, bilaketa asko motelduko da. Ondorioz, erregistro-programa batzuek ez dute hitz zatiko bilaketak onartzen edo (onenean) sintaxi berezia onartzen dute errendimendu baxuagoarekin. Hau saihestu nahi dugu.
Beste arazo bat puntuazioa da. Eskaera guztiak aurkitu nahi dituzu 50.168.29.7? Zer gertatzen da arazketako erregistroak dituztenak [error]? Harpidedunek puntuazioa saltatzen dute normalean.
Azkenik, ingeniariek tresna indartsuak maite dituzte, eta batzuetan arazo bat adierazpen erregular batekin soilik konpondu daiteke. Hitz gakoen indizea ez da oso egokia horretarako.
Horrez gain, indizeak konplexua. Mezu bakoitza gako-zerrenda batzuetara gehitu behar da. Zerrenda hauek erraz bila daitekeen formatuan gorde behar dira uneoro. Esaldiak, hitz zatiak edo esamolde erregularrak dituzten kontsultak zerrenda anitzeko eragiketetara itzuli behar dira, eta emaitzak eskaneatu eta konbinatu emaitza multzo bat sortzeko. Eskala handiko eta maizter anitzeko zerbitzu baten testuinguruan, konplexutasun horrek algoritmoak aztertzean ikusten ez diren errendimendu arazoak sortzen ditu.
Hitz gakoen indizeek ere leku asko hartzen dute, eta biltegiratzea kostu handia da erregistroak kudeatzeko sistema batean.
Bestalde, bilaketa bakoitzak konputazio-potentzia handia kontsumi dezake. Gure erabiltzaileek kontsulta bereziak egiteko abiadura handiko bilaketak eskertzen dituzte, baina horrelako kontsultak nahiko gutxitan egiten dira. Bilaketa ohiko kontsultak egiteko, adibidez, aginte-panel baterako, teknika bereziak erabiltzen ditugu (hurrengo artikuluan deskribatuko ditugu). Beste eskaera batzuk nahiko gutxi dira, gutxitan bat baino gehiago prozesatu behar dituzu aldi berean. Baina horrek ez du esan nahi gure zerbitzariak lanpetuta ez daudenik: lanpetuta daude mezu berriak jaso, aztertu eta konprimitzeko, alertak ebaluatzeko, datu zaharrak konprimitzeko, etab. Horrela, kontsultak egiteko erabil daitezkeen prozesadore eskaintza nahiko esanguratsua dugu.
Indar gordinak arazo gordinaren bat baduzu (eta indar asko) funtzionatzen du
Indar gordinak ondoen funtzionatzen du barneko begizta txikiekin arazo sinpleetan. Sarritan, barneko begizta optimiza dezakezu oso abiadura handietan exekutatzeko. Kodea konplexua bada, askoz zailagoa da optimizatzea.
Gure bilaketa-kodeak hasiera batean barruko begizta handi samarra zuen. Mezuak orrietan gordetzen ditugu 4K-n; orrialde bakoitzak mezu batzuk (UTF-8n) eta mezu bakoitzaren metadatuak ditu. Metadatuak balioaren luzera, barneko mezuaren IDa eta beste eremu batzuk kodetzen dituen egitura bat da. Bilaketa-zikloa honelakoa izan zen:
Hau benetako kodearen bertsio sinplifikatu bat da. Baina hemen ere, hainbat objektu kokatzea, datu-kopia eta funtzio-deiak ikusgai daude. JVM nahiko ona da funtzio-deiak optimizatzeko eta objektu iragankorrak esleitzeko, beraz, kode honek merezi baino hobeto funtzionatu zuen. Probetan zehar, bezeroek nahiko arrakastaz erabili zuten. Baina azkenean hurrengo mailara eraman genuen.
(Galdetu dezakezu zergatik gordetzen ditugun formatu honetan mezuak 4K orrialdeekin, testuekin eta metadatuekin, erregistroekin zuzenean lan egin beharrean. Arrazoi asko daude, eta horiek barnean Scalyr motorra datu-base banatu baten antza baino gehiago da. fitxategi-sistema. Testu-bilaketa sarritan DBMS estiloko iragazkiekin konbinatzen da erregistro-analisia egin ondoren. Aldi berean, milaka erregistro bilatu ditzakegu aldi berean, eta testu-fitxategi sinpleak ez dira egokiak gure datu transakzionalak, errepikatuak eta banatuak kudeatzeko).
Hasieran, zirudien kode hori ez zela oso egokia indar gordina optimizatzeko. "Benetako lana" atalean String.indexOf() CPU profila ere ez zuen menderatu. Hau da, metodo hau bakarrik optimizatzeak ez luke eragin handirik ekarriko.
Gertatzen da orri bakoitzaren hasieran metadatuak gordetzen ditugula eta UTF-8-ko mezu guztien testua beste muturrean bilduta egotea. Hori aprobetxatuz, begizta berridatzi dugu orrialde osoa aldi berean bilatzeko:
Bertsio honek zuzenean funtzionatzen du ikuspegian raw byte[] eta mezu guztiak aldi berean bilatzen ditu 4K orrialde osoan.
Hau askoz errazagoa da indar gordinaren metodorako optimizatzea. Barne bilaketa-begizta aldi berean deitzen da 4K orri osorako, mezu bakoitzean bereizita beharrean. Ez dago datuen kopiarik, ez objektuen esleipenik. Eta metadatu eragiketa konplexuagoak emaitza positiboa denean bakarrik deitzen dira, eta ez mezu guztietan. Horrela gainkostu asko kendu ditugu eta gainerako karga barne bilaketa-begizta txiki batean kontzentratzen da, optimizazio gehiagorako egokia dena.
Gure benetako bilaketa-algoritmoan oinarritzen da . Boyer-Moore algoritmoaren antzekoa da, eta urrats bakoitzean bilaketa-katearen luzera gutxi gorabehera saltatzen du. Desberdintasun nagusia da aldi berean bi byte egiaztatzen dituela, parekatze faltsuak minimizatzeko.
Gure ezarpenak bilaketa bakoitzeko 64K bilaketa-taula bat sortzea eskatzen du, baina hori ez da ezer bilatzen ari garen datu gigabyteekin alderatuta. Barne begiztak segundoko hainbat gigabyte prozesatzen ditu nukleo bakarrean. Praktikan, errendimendu egonkorra segundoko 1,25 GB ingurukoa da nukleo bakoitzean, eta hobetzeko aukera dago. Posible da barneko begiztatik kanpoko gainkostu batzuk kentzea, eta C barneko begizta batekin esperimentatzeko asmoa dugu Javaren ordez.
Indarra erabiltzen dugu
Erregistroen bilaketa "gutxi gorabehera" inplementa daitekeela eztabaidatu dugu, baina zenbat "potentzia" dugu? Nahiko asko.
1 muin: behar bezala erabiltzen denean, prozesadore moderno baten nukleo bakarra nahiko indartsua da berez.
8 nukleo: Une honetan Amazon hi1.4xlarge eta i2.4xlarge SSD zerbitzarietan exekutatzen ari gara, bakoitza 8 nukleoekin (16 hari). Goian esan bezala, nukleo hauek atzeko planoko eragiketekin lanpetuta egon ohi dira. Erabiltzaileak bilaketa bat egiten duenean, atzeko planoko eragiketak eten egiten dira, bilaketarako 8 nukleoak askatuz. Bilaketa segundo zati batean amaitzen da normalean, eta, ondoren, atzeko planoko lanari berriro ekiten zaio (aztertu programak ziurtatzen du bilaketa-kontsulten barra-barrak ez duela oztopatzen atzeko planoko lan garrantzitsua).
16 nukleo: fidagarritasuna lortzeko, zerbitzariak maisu/esklabo taldeetan antolatzen ditugu. Maisu bakoitzak SSD eta EBS zerbitzari bat ditu bere agindupean. Zerbitzari nagusiak huts egiten badu, SSD zerbitzariak berehala hartuko du bere lekua. Ia denbora guztian, maisuak eta esklaboak ondo funtzionatzen dute, beraz, datu-bloke bakoitza bi zerbitzari ezberdinetan bila daiteke (EBS esklabo zerbitzariak prozesadore ahula du, beraz, ez dugu kontuan hartzen). Bien artean banatzen dugu zeregina, guztira 16 nukleo ditugu eskuragarri.
Nukleo asko: Etorkizun hurbilean, datuak zerbitzarietan banatuko ditugu, denek eskaera ez-trivial guztiak prozesatzen parte har dezaten. Nukleo bakoitzak funtzionatuko du. [Ohar: plana ezarri dugu eta bilaketa-abiadura 1 TB/s-ra igo dugu, ikusi oharra artikuluaren amaieran].
Sinpletasunak fidagarritasuna bermatzen du
Indar gordinaren metodoaren beste abantaila bat errendimendu nahiko koherentea da. Normalean, bilaketa ez da oso sentikorra arazoaren eta datu-multzoaren xehetasunekin (uste dut horregatik deitzen zaiola "lodia").
Hitz gakoen indizeak batzuetan emaitza izugarri azkarrak sortzen ditu, eta beste batzuetan ez. Demagun 50 GB-ko erregistroak dituzula eta bertan 'customer_5987235982' terminoa hiru aldiz zehatz-mehatz agertzen da. Termino honen bilaketak hiru kokapen zenbatzen ditu indizetik zuzenean eta berehala osatuko da. Baina komodinen bilaketa konplexuek milaka gako-hitz eskaneatu ditzakete eta denbora luzea izan dezakete.
Bestalde, indar gordineko bilaketak abiadura berdinean funtzionatzen du edozein kontsultarako. Hitz luzeak bilatzea hobe da, baina karaktere bakarra bilatzea ere nahiko azkarra da.
Indar gordinaren metodoaren sinpletasunak esan nahi du bere errendimendua maximo teorikotik gertu dagoela. Aukera gutxiago daude ustekabeko disko gainkargak, blokeoen gatazka, erakusleen atzetik eta huts egiteko beste milaka arrazoi. Joan den astean Scalyr-eko erabiltzaileek gure zerbitzari okupatuenean egindako eskaerak aztertu ditut. 14 eskaera izan ziren. Haietako zortzik segundo bat baino gehiago behar izan zuten; % 000 99 milisegundoren barruan osatu da (erregistroen analisirako tresnak erabili ez badituzu, fidatu nigan: azkarra da).
Errendimendu egonkorra eta fidagarria garrantzitsua da zerbitzua erabiltzeko erraztasunerako. Aldian-aldian atzeratzen bada, erabiltzaileek fidagarria ez dela ulertuko dute eta ez dute erabiltzeko gogorik izango.
Erregistratu bilaketa ekintzan
Hona hemen Scalyr bilaketa ekintzan erakusten duen animazio labur bat. Demo kontu bat dugu, non gertaera guztiak inportatzen ditugun Github biltegi publiko guztietan. Demo honetan, aste bateko datuen balioa aztertzen dut: gutxi gorabehera 600 MB erregistro gordinak.
Bideoa zuzenean grabatu zen, prestaketa berezirik gabe, nire mahaigainean (zerbitzaritik 5000 bat kilometrora). Ikusiko duzun errendimenduari zor zaio neurri handi batean , baita backend azkar eta fidagarria ere. "Kargatzen" adierazlerik gabeko etenaldi bat dagoen bakoitzean, ni naiz pausatzen ari naizena sakatu behar dudana irakur dezazun.
Ondorioz
Datu-kopuru handiak prozesatzen dituzunean, garrantzitsua da algoritmo on bat aukeratzea, baina "ona" ez du "dotorea" esan nahi. Pentsatu nola funtzionatuko duen zure kodea praktikan. Algoritmoen analisi teorikoak mundu errealean garrantzi handia izan dezaketen faktore batzuk kanpoan uzten ditu. Algoritmo sinpleagoak optimizatzen errazagoak dira eta egonkorragoak dira ertz egoeretan.
Era berean, pentsatu kodea zein testuingurutan exekutatu behar den. Gure kasuan, behar adina zerbitzari indartsuak behar ditugu atzeko zereginak kudeatzeko. Erabiltzaileek nahiko gutxitan egiten dituzte bilaketak, beraz, zerbitzari talde oso bat maileguan hartu dezakegu bilaketa bakoitza burutzeko behar den epe laburrerako.
Indar gordineko metodo bat erabiliz, bilaketa azkarra, fidagarria eta malgua ezarri genuen erregistro multzo batean. Ideia hauek zure proiektuetarako erabilgarriak izatea espero dugu.
Editatu: Izenburua eta testua "Bilatu 20 GB segundoko"tik "Bilatu 1 TB segundoko" izatera pasatu dira, azken urteotan errendimenduaren gorakada islatzeko. Abiadura igoera hau, batez ere, gaur egun jartzen ari garen EC2 zerbitzarien mota eta kopuruan aldaketak direla eta, gure bezero-base handituari zerbitzatzeko. Laster badaude aldaketak eraginkortasun operatiboan beste bultzada nabarmen bat emango dutenak, eta ezin gara itxaron horiek partekatzeko.
Iturria: www.habr.com