TL;DR: Antaŭ kvar jaroj mi forlasis Guglon kun ideo por nova servila monitora ilo. La ideo estis kombini kutime izolitajn funkciojn en unu servon kaj protokolo analizo, metrika kolekto, kaj paneloj. Unu el la principoj estas, ke la servo devas esti vere rapida, provizante devopojn kun facila, interaga, ĝua sperto. Ĉi tio postulas prilaboradon de multgigabajtaj datumserioj en frakcioj de sekundo dum vi restas ene de buĝeto. Ekzistantaj protokopaj iloj estas ofte malrapidaj kaj mallertaj, do ni alfrontis bonan defion: saĝe desegni ilon por doni al uzantoj novan sperton.
Ĉi tiu artikolo priskribas kiel ni ĉe Scalyr solvis ĉi tiun problemon aplikante malnovajn lernejajn metodojn, krudfortan aliron, forigante nenecesajn tavolojn kaj evitante kompleksajn datumstrukturojn. Vi povas apliki ĉi tiujn lecionojn al viaj propraj inĝenieraj problemoj.
Old School Power
Registro-analizo kutime komenciĝas per serĉo: trovu ĉiujn mesaĝojn, kiuj kongruas kun certa ŝablono. En Scalyr, ĉi tiuj estas dekoj aŭ centoj da gigabajtoj da protokoloj de multaj serviloj. Modernaj aliroj, kiel regulo, implikas la konstruadon de iu kompleksa datumstrukturo optimumigita por serĉo. Mi certe vidis ĉi tion ĉe Guglo, kie ili sufiĉe lertas pri ĉi tia afero. Sed ni decidis pri multe pli kruda aliro: linia skanado de ŝtipoj. Kaj ĝi funkciis - ni provizas serĉeblan interfacon kiu estas ordoj de grandeco pli rapida ol niaj konkurantoj (vidu animacion ĉe la fino).
La ŝlosila kompreno estis, ke modernaj procesoroj estas ja tre rapidaj ĉe simplaj, simplaj operacioj. Ĉi tio estas facile maltrafi en kompleksaj, plurtavolaj sistemoj, kiuj dependas de I/O-rapideco kaj retaj operacioj, kaj tiaj sistemoj estas tre oftaj hodiaŭ. Do ni evoluigis dezajnon kiu minimumigas tavolojn kaj troajn derompaĵojn. Kun pluraj procesoroj kaj serviloj paralele, la serĉrapideco atingas 1 TB je sekundo.
Ŝlosilaĵoj de ĉi tiu artikolo:
- Brutforta serĉo estas realigebla aliro por solvi realajn, grandskalajn problemojn.
- Bruta forto estas dezajnotekniko, ne senlabora solvo. Kiel ĉiu tekniko, ĝi pli taŭgas por iuj problemoj ol aliaj, kaj povas esti efektivigita malbone aŭ bone.
- Bruta forto estas precipe bona por atingi stabila produktiveco.
- Efika uzo de krudforto postulas optimumigi kodon kaj apliki sufiĉajn rimedojn en la ĝusta tempo. Ĝi taŭgas se viaj serviloj estas sub peza ne-uzanta ŝarĝo kaj uzantoperacioj restas prioritato.
- Efikeco dependas de la dezajno de la tuta sistemo, ne nur de la interna buklo-algoritmo.
(Ĉi tiu artikolo priskribas serĉadon de datumoj en memoro. Plejofte, kiam uzanto faras protokolserĉon, la Scalyr-serviloj jam konservis ĝin en kaŝmemoro. La sekva artikolo diskutos pri serĉado de nekaŝigitaj protokoloj. La samaj principoj validas: efika kodo, krudforto. kun grandaj komputilaj rimedoj).
Brutforta metodo
Tradicie, granda datumaro estas serĉata uzante ŝlosilvorton. Se aplikite al servilaj protokoloj, tio signifas serĉi ĉiun unikan vorton en la protokolo. Por ĉiu vorto, vi devas fari liston de ĉiuj inkludoj. Ĉi tio faciligas trovi ĉiujn mesaĝojn kun ĉi tiu vorto, ekzemple 'eraro', 'firefox' aŭ "transaction_16851951" - nur rigardu en la indekso.
Mi uzis ĉi tiun aliron ĉe Google kaj ĝi bone funkciis. Sed en Scalyr ni serĉas la protokolojn bajto post bajto.
Kial? De abstrakta algoritma vidpunkto, ŝlosilvortaj indeksoj estas multe pli efikaj ol krudfortaj serĉoj. Tamen, ni ne vendas algoritmojn, ni vendas rendimenton. Kaj agado ne temas nur pri algoritmoj, sed ankaŭ pri sistema inĝenierado. Ni devas konsideri ĉion: volumo de datumoj, tipo de serĉo, disponebla aparataro kaj programaro kunteksto. Ni decidis, ke por nia aparta problemo, io kiel 'grep' pli taŭgas ol indekso.
Indeksoj estas bonegaj, sed ili havas limigojn. Unu vorto estas facile trovebla. Sed serĉi mesaĝojn kun pluraj vortoj, kiel 'googlebot' kaj '404', estas multe pli malfacila. Serĉi frazon kiel 'nekaptita escepto' postulas pli ĝenan indekson, kiu registras ne nur ĉiujn mesaĝojn kun tiu vorto, sed ankaŭ la specifan lokon de la vorto.
La vera malfacilaĵo venas kiam vi ne serĉas vortojn. Ni diru, ke vi volas vidi kiom da trafiko venas de robotoj. La unua penso estas serĉi la protokolojn por la vorto 'bot'. Jen kiel vi trovos kelkajn robotojn: Googlebot, Bingbot kaj multaj aliaj. Sed ĉi tie 'bot' ne estas vorto, sed parto de ĝi. Se ni serĉas 'bot' en la indekso, ni ne trovos afiŝojn kun la vorto 'Googlebot'. Se vi kontrolas ĉiun vorton en la indekso kaj poste skanas la indekson por la trovitaj ŝlosilvortoj, la serĉo multe malrapidiĝos. Rezulte, iuj protokolprogramoj ne permesas partvortajn serĉojn aŭ (en la plej bona kazo) permesas specialan sintakson kun pli malalta rendimento. Ni volas eviti ĉi tion.
Alia problemo estas interpunkcio. Ĉu vi volas trovi ĉiujn petojn de 50.168.29.7? Kio pri sencimigaj protokoloj enhavantaj [error]? Abonoj kutime preterlasas interpunkcion.
Fine, inĝenieroj amas potencajn ilojn, kaj foje problemo povas esti solvita nur per regula esprimo. La ŝlosilvorto-indekso ne tre taŭgas por tio.
Krome, la indicoj kompleksa. Ĉiu mesaĝo devas esti aldonita al pluraj ŝlosillistoj. Ĉi tiuj listoj devas esti konservitaj en facile serĉebla formato ĉiam. Demandoj kun frazoj, vortfragmentoj aŭ regulaj esprimoj devas esti tradukitaj al plurlistaj operacioj, kaj la rezultoj skanitaj kaj kombinitaj por produkti rezultan aron. En la kunteksto de grandskala, plur-luanta servo, ĉi tiu komplekseco kreas rendimentajn problemojn, kiuj ne estas videblaj kiam oni analizas la algoritmojn.
Ŝlosilvortoj ankaŭ okupas multe da spaco, kaj stokado estas grava kosto en ŝtipadministra sistemo.
Aliflanke, ĉiu serĉo povas konsumi multe da komputika potenco. Niaj uzantoj aprezas altrapidajn serĉojn por unikaj demandoj, sed tiaj demandoj estas faritaj relative malofte. Por tipaj serĉdemandoj, ekzemple, por panelo, ni uzas specialajn teknikojn (ni priskribos ilin en la sekva artikolo). Aliaj petoj estas sufiĉe maloftaj, ke vi malofte devas procesi pli ol unu samtempe. Sed ĉi tio ne signifas, ke niaj serviloj ne estas okupataj: ili estas okupataj per la laboro ricevi, analizi kaj kunpremi novajn mesaĝojn, taksi atentigojn, kunpremi malnovajn datumojn ktp. Tiel, ni havas sufiĉe signifan provizon de procesoroj, kiuj povas esti uzataj por efektivigi demandojn.
Bruta forto funkcias se vi havas krudan problemon (kaj multe da forto)
Bruta forto funkcias plej bone ĉe simplaj problemoj kun malgrandaj internaj bukloj. Ofte vi povas optimumigi la internan buklon por funkcii al tre altaj rapidecoj. Se la kodo estas kompleksa, estas multe pli malfacile optimumigi ĝin.
Nia serĉkodo origine havis sufiĉe grandan internan buklon. Ni stokas mesaĝojn sur paĝoj ĉe 4K; ĉiu paĝo enhavas kelkajn mesaĝojn (en UTF-8) kaj metadatenojn por ĉiu mesaĝo. Metadatenoj estas strukturo kiu ĉifras la longon de la valoro, internan mesaĝan ID, kaj aliajn kampojn. La serĉciklo aspektis jene:
Ĉi tio estas simpligita versio de la reala kodo. Sed eĉ ĉi tie, pluraj objektolokigoj, datumkopioj kaj funkciovokoj estas videblaj. La JVM sufiĉe lertas pri optimumigo de funkciovokoj kaj asignado de efemeraj objektoj, do ĉi tiu kodo funkciis pli bone ol ni meritis. Dum testado, klientoj uzis ĝin sufiĉe sukcese. Sed finfine ni prenis ĝin al la sekva nivelo.
(Vi povas demandi, kial ni konservas mesaĝojn en ĉi tiu formato kun 4K paĝoj, teksto kaj metadatumoj, anstataŭ labori kun protokoloj rekte. Estas multaj kialoj, kiuj resumiĝas al la fakto, ke interne la Scalyr-motoro estas pli kiel distribuita datumbazo ol dosiersistemo. Teksta serĉo estas ofte kombinita kun DBMS-stilaj filtriloj en la marĝenoj post protokolo-analizo. Ni povas samtempe serĉi multajn milojn da protokoloj samtempe, kaj simplaj tekstdosieroj ne taŭgas por nia transakcia, reproduktita, distribuita datumadministrado).
Komence, ŝajnis, ke tia kodo ne tre taŭgas por brutforta optimumigo. "Vera laboro" en String.indexOf() eĉ ne regis la CPU-profilon. Tio estas, optimumigi ĉi tiun metodon sole ne alportus gravan efikon.
Okazas, ke ni stokas metadatenojn komence de ĉiu paĝo, kaj la teksto de ĉiuj mesaĝoj en UTF-8 estas pakita ĉe la alia fino. Profitante ĉi tion, ni reverkis la buklon por serĉi la tutan paĝon samtempe:
Ĉi tiu versio funkcias rekte sur la vido raw byte[] kaj serĉas ĉiujn mesaĝojn samtempe tra la tuta 4K paĝo.
Ĉi tio estas multe pli facile optimumebla por la krudforta metodo. La interna serĉbuklo estas vokita samtempe por la tuta 4K paĝo, prefere ol aparte sur ĉiu afiŝo. Ne estas kopiado de datumoj, neniu asigno de objektoj. Kaj pli kompleksaj metadatumaj operacioj estas nomitaj nur kiam la rezulto estas pozitiva, kaj ne sur ĉiu mesaĝo. Tiel ni forigis multan superkoston, kaj la resto de la ŝarĝo koncentriĝas en malgranda interna serĉbuklo, kiu taŭgas por plia optimumigo.
Nia reala serĉalgoritmo baziĝas sur . Ĝi estas simila al la Boyer-Moore-algoritmo, pretersaltas proksimume la longon de la serĉŝnuro ĉe ĉiu paŝo. La ĉefa diferenco estas, ke ĝi kontrolas du bajtojn samtempe por minimumigi falsajn kongruojn.
Nia efektivigo postulas krei 64K serĉtabelon por ĉiu serĉo, sed tio estas nenio kompare kun la gigabajtoj da datumoj, kiujn ni serĉas. La interna buklo prilaboras plurajn gigabajtojn je sekundo sur ununura kerno. En praktiko, stabila rendimento estas ĉirkaŭ 1,25 GB sekundo sur ĉiu kerno, kaj estas loko por plibonigo. Eblas elimini iom da la superkosto ekster la interna buklo, kaj ni planas eksperimenti kun interna buklo en C anstataŭ Java.
Ni uzas forton
Ni diskutis, ke protokolserĉado povas esti efektivigita "malglate", sed kiom da "potenco" ni havas? Sufiĉe multe.
1 kerno: Se uzata ĝuste, ununura kerno de moderna procesoro estas sufiĉe potenca en si mem.
8 kernoj: Ni nuntempe funkcias per Amazon hi1.4xlarge kaj i2.4xlarge SSD-serviloj, ĉiu kun 8 kernoj (16 fadenoj). Kiel menciite supre, ĉi tiuj kernoj estas kutime okupataj per fonaj operacioj. Kiam la uzanto faras serĉon, fonoperacioj estas suspenditaj, liberigante ĉiujn 8 kernojn por serĉo. La serĉo kutime finiĝas en frakcio de sekundo, post kiu fona laboro rekomencas (la streĉa programo certigas, ke la tumulto de serĉdemandoj ne malhelpas gravan fonan laboron).
16 kernoj: por fidindeco, ni organizas servilojn en majstrajn/sklavojn grupojn. Ĉiu majstro havas unu SSD kaj unu EBS-servilon sub sia komando. Se la ĉefa servilo kraŝas, la SSD-servilo tuj prenas sian lokon. Preskaŭ ĉiam, majstro kaj sklavo funkcias bone, tiel ke ĉiu datumbloko estas serĉebla sur du malsamaj serviloj (la sklava servilo EBS havas malfortan procesoron, do ni ne konsideras ĝin). Ni dividas la taskon inter ili, tiel ke ni disponu entute 16 kernojn.
Multaj kernoj: En proksima estonteco, ni distribuos datumojn tra serviloj tiel, ke ili ĉiuj partoprenu en la prilaborado de ĉiu ne-triviala peto. Ĉiu kerno funkcios. [Noto: ni efektivigis la planon kaj pliigis la serĉrapidecon al 1 TB/s, vidu noton ĉe la fino de la artikolo].
Simpleco certigas fidindecon
Alia avantaĝo de la krudforta metodo estas ĝia sufiĉe konsekvenca agado. Tipe, serĉo ne estas tre sentema al la detaloj de la problemo kaj datumaro (mi supozas ke tial ĝi nomiĝas "kruda").
La ŝlosilvorto-indekso foje produktas nekredeble rapidajn rezultojn, kaj alifoje ĝi ne faras. Ni diru, ke vi havas 50 GB da protokoloj, en kiuj la termino 'customer_5987235982' aperas ekzakte trifoje. Serĉo por ĉi tiu termino kalkulas tri lokojn rekte de la indekso kaj finiĝos tuj. Sed kompleksaj ĵokeraj serĉoj povas skani milojn da ŝlosilvortoj kaj daŭri longan tempon.
Aliflanke, krudfortaj serĉoj rezultas pli-malpli samrapide por iu ajn demando. Serĉi longajn vortojn estas pli bone, sed eĉ serĉi unu signon estas sufiĉe rapida.
La simpleco de la krudforta metodo signifas ke ĝia efikeco estas proksima al sia teoria maksimumo. Estas malpli da ebloj por neatenditaj disko-troŝarĝoj, ŝlosila disputo, montrilo-ĉasado kaj miloj da aliaj kialoj de fiasko. Mi ĵus rigardis la petojn faritajn de Scalyr-uzantoj pasintsemajne sur nia plej okupata servilo. Estis 14 petoj. Ĝuste ok el ili daŭris pli ol unu sekundon; 000% kompletigitaj ene de 99 milisekundoj (se vi ne uzis protokolan analizilon, fidu min: ĝi estas rapida).
Stabila, fidinda agado gravas por facileco de uzado de la servo. Se ĝi malfruas periode, uzantoj perceptos ĝin kiel nefidinda kaj malvolontas uzi ĝin.
Ensalutu serĉon en ago
Jen mallonga animacio, kiu montras Scalyr-serĉon en ago. Ni havas demonstran konton, kie ni importas ĉiun eventon en ĉiu publika Github-deponejo. En ĉi tiu demo, mi ekzamenas semajnan valoron de datumoj: proksimume 600 MB da krudaj protokoloj.
La video estis registrita vive, sen speciala preparo, sur mia labortablo (ĉirkaŭ 5000 kilometroj de la servilo). La agado, kiun vi vidos, estas plejparte pro , same kiel rapida kaj fidinda backend. Kiam ajn estas paŭzo sen 'ŝarĝa' indikilo, estas mi paŭzo, por ke vi povu legi tion, kion mi premas.
En konkludo
Kiam oni prilaboras grandajn kvantojn da datumoj, estas grave elekti bonan algoritmon, sed "bona" ne signifas "fanta". Pensu pri kiel via kodo funkcios praktike. La teoria analizo de algoritmoj forlasas kelkajn faktorojn kiuj povas esti de granda graveco en la reala mondo. Pli simplaj algoritmoj estas pli facile optimumeblaj kaj pli stabilaj en randaj situacioj.
Pensu ankaŭ pri la kunteksto en kiu la kodo estos ekzekutita. En nia kazo, ni bezonas sufiĉe potencajn servilojn por administri fonajn taskojn. Uzantoj iniciatas serĉojn relative malofte, do ni povas prunti tutan grupon da serviloj por la mallonga periodo necesa por plenumi ĉiun serĉon.
Uzante krudfortan metodon, ni efektivigis rapidan, fidindan, flekseblan serĉon tra aro da protokoloj. Ni esperas, ke ĉi tiuj ideoj estas utilaj por viaj projektoj.
Redaktu: La titolo kaj teksto ŝanĝiĝis de "Serĉu je 20 GB je sekundo" al "Serĉu je 1 TB je sekundo" por reflekti la rendimentopliiĝojn dum la lastaj jaroj. Ĉi tiu pliiĝo de rapideco estas ĉefe pro ŝanĝoj en la tipo kaj nombro de EC2-serviloj, kiujn ni hodiaŭ metas por servi nian pliigitan klientbazon. Baldaŭ venos ŝanĝoj, kiuj donos alian draman akcelon en funkcia efikeco, kaj ni ne povas atendi dividi ilin.
fonto: www.habr.com