TL;DR: Apat na taon na ang nakalipas umalis ako sa Google na may ideya para sa isang bagong tool sa pagsubaybay sa server. Ang ideya ay upang pagsamahin ang karaniwang nakahiwalay na mga function sa isang serbisyo at pagsusuri ng log, pagkolekta ng mga sukatan, at mga dashboard. Isa sa mga prinsipyo ay ang serbisyo ay dapat na tunay mabilis, na nagbibigay sa mga devop ng madali, interactive, kasiya-siyang karanasan. Nangangailangan ito ng pagproseso ng mga multi-gigabyte data set sa mga fraction ng isang segundo habang nananatili sa loob ng badyet. Ang mga kasalukuyang tool sa pamamahala ng log ay kadalasang mabagal at clunky, kaya napaharap kami sa isang magandang hamon: matalinong pagdidisenyo ng tool upang bigyan ang mga user ng bagong karanasan.
Inilalarawan ng artikulong ito kung paano namin nalutas sa Scalyr ang problemang ito sa pamamagitan ng paglalapat ng mga lumang pamamaraan ng paaralan, isang brute force na diskarte, pag-aalis ng mga hindi kinakailangang layer at pag-iwas sa mga kumplikadong istruktura ng data. Maaari mong ilapat ang mga araling ito sa iyong sariling mga problema sa engineering.
Old School Power
Karaniwang nagsisimula ang pagsusuri sa log sa isang paghahanap: hanapin ang lahat ng mensaheng tumutugma sa isang partikular na pattern. Sa Scalyr, ito ay sampu o daan-daang gigabytes ng mga log mula sa maraming mga server. Ang mga modernong diskarte, bilang panuntunan, ay kinabibilangan ng pagbuo ng ilang kumplikadong istruktura ng data na na-optimize para sa paghahanap. Tiyak na nakita ko ito sa Google, kung saan medyo magaling sila sa ganitong uri ng bagay. Ngunit kami ay nanirahan sa isang mas cruder na diskarte: linear scan ng mga log. At gumana ito - nagbibigay kami ng nahahanap na interface na mas mabilis kaysa sa aming mga kakumpitensya (tingnan ang animation sa dulo).
Ang pangunahing insight ay ang mga modernong processor ay talagang napakabilis sa simple at diretsong operasyon. Ito ay madaling makaligtaan sa mga kumplikadong, multi-layer system na umaasa sa bilis ng I/O at mga pagpapatakbo ng network, at ang mga ganitong sistema ay karaniwan na ngayon. Kaya bumuo kami ng isang disenyo na nagpapaliit ng mga layer at labis na mga labi. Sa maraming processor at server na magkatulad, ang bilis ng paghahanap ay umaabot sa 1 TB bawat segundo.
Mga pangunahing takeaways mula sa artikulong ito:
- Ang brute-force na paghahanap ay isang praktikal na diskarte para sa paglutas ng real-world, malakihang mga problema.
- Ang brute force ay isang diskarte sa disenyo, hindi isang solusyon na walang trabaho. Tulad ng anumang pamamaraan, ito ay mas angkop sa ilang mga problema kaysa sa iba, at maaaring ipatupad nang hindi maganda o maayos.
- Ang brute force ay lalong mabuti para sa pagkamit matatag pagganap.
- Ang mabisang paggamit ng brute force ay nangangailangan ng pag-optimize ng code at paglalapat ng sapat na mapagkukunan sa tamang oras. Ito ay angkop kung ang iyong mga server ay nasa ilalim ng mabigat na pag-load na hindi gumagamit at ang mga pagpapatakbo ng gumagamit ay nananatiling priyoridad.
- Ang pagganap ay nakasalalay sa disenyo ng buong system, hindi lamang sa inner loop algorithm.
(Ang artikulong ito ay naglalarawan ng paghahanap ng data sa memorya. Sa karamihan ng mga kaso, kapag ang isang gumagamit ay nagsasagawa ng isang paghahanap ng log, ang mga Scalyr server ay na-cache na ito. Tatalakayin ng susunod na artikulo ang paghahanap para sa mga hindi naka-cach na log. Ang parehong mga prinsipyo ay nalalapat: mahusay na code, brute force na may malaking mapagkukunan ng computational).
Paraan ng brute force
Ayon sa kaugalian, ang isang malaking set ng data ay hinahanap gamit ang isang index ng keyword. Kapag inilapat sa mga log ng server, nangangahulugan ito ng paghahanap para sa bawat natatanging salita sa log. Para sa bawat salita, kailangan mong gumawa ng isang listahan ng lahat ng mga inklusyon. Pinapadali nitong mahanap ang lahat ng mensahe gamit ang salitang ito, halimbawa 'error', 'firefox' o "transaction_16851951" - tingnan lang sa index.
Ginamit ko ang diskarteng ito sa Google at gumana ito nang maayos. Ngunit sa Scalyr hinahanap namin ang logs byte byte.
Bakit? Mula sa abstract algorithmic point of view, ang mga keyword index ay mas mahusay kaysa sa mga brute force na paghahanap. Gayunpaman, hindi kami nagbebenta ng mga algorithm, nagbebenta kami ng pagganap. At ang pagganap ay hindi lamang tungkol sa mga algorithm, kundi pati na rin sa engineering ng mga sistema. Dapat nating isaalang-alang ang lahat: dami ng data, uri ng paghahanap, magagamit na konteksto ng hardware at software. Napagpasyahan namin na para sa aming partikular na problema, ang isang bagay tulad ng 'grep' ay mas angkop kaysa sa isang index.
Ang mga index ay mahusay, ngunit mayroon silang mga limitasyon. Ang isang salita ay madaling mahanap. Ngunit ang paghahanap ng mga mensahe na may maraming salita, gaya ng 'googlebot' at '404', ay mas mahirap. Ang paghahanap ng pariralang tulad ng 'uncaught exception' ay nangangailangan ng mas masalimuot na index na nagtatala hindi lamang sa lahat ng mensahe na may salitang iyon, kundi pati na rin sa partikular na lokasyon ng salita.
Ang tunay na kahirapan ay dumarating kapag hindi ka naghahanap ng mga salita. Sabihin nating gusto mong makita kung gaano karaming trapiko ang nanggagaling sa mga bot. Ang unang pag-iisip ay ang paghahanap sa mga log para sa salitang 'bot'. Ito ay kung paano mo mahahanap ang ilang mga bot: Googlebot, Bingbot at marami pang iba. Ngunit narito ang 'bot' ay hindi isang salita, ngunit isang bahagi nito. Kung hahanapin namin ang 'bot' sa index, hindi kami makakahanap ng anumang mga post na may salitang 'Googlebot'. Kung susuriin mo ang bawat salita sa index at pagkatapos ay i-scan ang index para sa mga keyword na natagpuan, ang paghahanap ay bumagal nang husto. Bilang resulta, hindi pinapayagan ng ilang log program ang mga part-word na paghahanap o (sa pinakamaganda) pinapayagan ang espesyal na syntax na may mas mababang pagganap. Gusto naming iwasan ito.
Ang isa pang problema ay ang bantas. Gusto mo bang hanapin ang lahat ng kahilingan mula sa 50.168.29.7? Paano ang tungkol sa pag-debug ng mga log na naglalaman ng [error]? Karaniwang nilalaktawan ng mga subscript ang bantas.
Sa wakas, ang mga inhinyero ay mahilig sa makapangyarihang mga tool, at kung minsan ang isang problema ay malulutas lamang sa isang regular na expression. Ang index ng keyword ay hindi masyadong angkop para dito.
Bilang karagdagan, ang mga indeks kumplikado. Ang bawat mensahe ay kailangang idagdag sa ilang listahan ng keyword. Ang mga listahang ito ay dapat na panatilihin sa isang madaling mahahanap na format sa lahat ng oras. Ang mga query na may mga parirala, mga fragment ng salita, o mga regular na expression ay kailangang isalin sa mga multi-list na operasyon, at ang mga resulta ay na-scan at pinagsama upang makagawa ng isang set ng resulta. Sa konteksto ng malakihan, maraming nangungupahan na serbisyo, ang pagiging kumplikadong ito ay lumilikha ng mga isyu sa pagganap na hindi nakikita kapag sinusuri ang mga algorithm.
Ang mga index ng keyword ay tumatagal din ng maraming espasyo, at ang storage ay isang malaking gastos sa isang log management system.
Sa kabilang banda, ang bawat paghahanap ay maaaring kumonsumo ng maraming kapangyarihan sa pag-compute. Pinahahalagahan ng aming mga user ang mga high-speed na paghahanap para sa mga natatanging query, ngunit ang mga naturang query ay medyo bihira. Para sa karaniwang mga query sa paghahanap, halimbawa, para sa isang dashboard, gumagamit kami ng mga espesyal na diskarte (iilalarawan namin ang mga ito sa susunod na artikulo). Ang iba pang mga kahilingan ay medyo madalang na bihira kang magproseso ng higit sa isa sa isang pagkakataon. Ngunit hindi ito nangangahulugan na ang aming mga server ay hindi abala: abala sila sa gawain ng pagtanggap, pagsusuri at pag-compress ng mga bagong mensahe, pagsusuri ng mga alerto, pag-compress ng lumang data, at iba pa. Kaya, mayroon kaming medyo makabuluhang supply ng mga processor na maaaring magamit upang magsagawa ng mga query.
Gumagana ang brute force kung mayroon kang malupit na problema (at maraming puwersa)
Pinakamahusay na gumagana ang brute force sa mga simpleng problema na may maliliit na panloob na loop. Kadalasan maaari mong i-optimize ang panloob na loop upang tumakbo sa napakataas na bilis. Kung kumplikado ang code, mas mahirap i-optimize ito.
Ang aming search code ay orihinal na may medyo malaking panloob na loop. Nag-iimbak kami ng mga mensahe sa mga pahina sa 4K; bawat pahina ay naglalaman ng ilang mensahe (sa UTF-8) at metadata para sa bawat mensahe. Ang metadata ay isang istraktura na nag-e-encode sa haba ng value, internal message ID, at iba pang mga field. Ang ikot ng paghahanap ay ganito ang hitsura:
Ito ay isang pinasimpleng bersyon ng aktwal na code. Ngunit kahit dito, makikita ang maraming placement ng object, kopya ng data, at function na tawag. Ang JVM ay medyo mahusay sa pag-optimize ng mga function na tawag at paglalaan ng mga ephemeral na bagay, kaya ang code na ito ay gumana nang mas mahusay kaysa sa nararapat sa amin. Sa panahon ng pagsubok, ginamit ito ng mga customer nang matagumpay. Ngunit sa huli ay dinala namin ito sa susunod na antas.
(Maaari kang magtanong kung bakit kami nag-iimbak ng mga mensahe sa format na ito na may 4K na mga pahina, text at metadata, sa halip na direktang magtrabaho kasama ang mga log. Maraming dahilan, na nagmumula sa katotohanan na sa loob ng Scalyr engine ay mas katulad ng isang distributed database kaysa sa isang file system. Ang paghahanap ng teksto ay madalas na pinagsama sa mga filter na istilo ng DBMS sa mga margin pagkatapos ng pag-parse ng log. Maaari tayong sabay na maghanap ng maraming libu-libong log nang sabay-sabay, at ang mga simpleng text file ay hindi angkop para sa aming transactional, kinokopya, distributed na pamamahala ng data).
Sa una, tila ang naturang code ay hindi masyadong angkop para sa brute force optimization. "Tunay na trabaho" sa String.indexOf() hindi man lang nangibabaw ang profile ng CPU. Iyon ay, ang pag-optimize sa paraang ito lamang ay hindi magdadala ng makabuluhang epekto.
Nagkataon na nag-iimbak kami ng metadata sa simula ng bawat pahina, at ang teksto ng lahat ng mga mensahe sa UTF-8 ay naka-pack sa kabilang dulo. Sinasamantala ito, muling isinulat namin ang loop upang hanapin ang buong pahina nang sabay-sabay:
Ang bersyon na ito ay gumagana nang direkta sa view raw byte[] at hinahanap ang lahat ng mensahe nang sabay-sabay sa buong 4K page.
Ito ay mas madaling i-optimize para sa paraan ng brute force. Ang panloob na loop ng paghahanap ay tinatawag nang sabay-sabay para sa buong 4K na pahina, sa halip na hiwalay sa bawat post. Walang pagkopya ng data, walang paglalaan ng mga bagay. At ang mas kumplikadong mga operasyon ng metadata ay tinatawag lamang kapag positibo ang resulta, at hindi sa bawat mensahe. Sa ganitong paraan naalis namin ang isang toneladang overhead, at ang natitirang bahagi ng load ay puro sa isang maliit na panloob na loop ng paghahanap, na angkop na angkop para sa karagdagang pag-optimize.
Ang aming aktwal na algorithm sa paghahanap ay batay sa . Ito ay katulad ng algorithm ng Boyer-Moore, na nilalaktawan ang humigit-kumulang na haba ng string ng paghahanap sa bawat hakbang. Ang pangunahing pagkakaiba ay sinusuri nito ang dalawang byte sa isang pagkakataon upang mabawasan ang mga maling tugma.
Ang aming pagpapatupad ay nangangailangan ng paglikha ng 64K lookup table para sa bawat paghahanap, ngunit iyon ay walang halaga kumpara sa gigabytes ng data na aming hinahanap. Ang panloob na loop ay nagpoproseso ng ilang gigabytes bawat segundo sa isang core. Sa pagsasagawa, ang matatag na pagganap ay nasa paligid ng 1,25 GB bawat segundo sa bawat core, at may puwang para sa pagpapabuti. Posibleng alisin ang ilan sa mga overhead sa labas ng inner loop, at plano naming mag-eksperimento sa isang panloob na loop sa C sa halip na Java.
Gumagamit kami ng dahas
Napag-usapan namin na ang paghahanap ng log ay maaaring ipatupad nang "halos", ngunit gaano karaming "kapangyarihan" ang mayroon tayo? Medyo marami.
1 core: Kapag ginamit nang tama, ang isang solong core ng isang modernong processor ay medyo malakas sa sarili nitong karapatan.
8 core: Kasalukuyan kaming tumatakbo sa Amazon hi1.4xlarge at i2.4xlarge SSD server, bawat isa ay may 8 core (16 na thread). Tulad ng nabanggit sa itaas, ang mga core na ito ay karaniwang abala sa mga pagpapatakbo sa background. Kapag nagsagawa ng paghahanap ang user, sinuspinde ang mga operasyon sa background, na nagpapalaya sa lahat ng 8 core para sa paghahanap. Karaniwang natatapos ang paghahanap sa loob ng ilang segundo, pagkatapos nito ay magpapatuloy ang background work (tinitiyak ng throttling program na ang barrage ng mga query sa paghahanap ay hindi nakakasagabal sa mahalagang background work).
16 core: para sa pagiging maaasahan, inaayos namin ang mga server sa mga master/slave group. Ang bawat master ay may isang SSD at isang EBS server sa ilalim ng kanyang utos. Kung nag-crash ang pangunahing server, agad na pumapalit ang SSD server. Halos sa lahat ng oras, ang master at alipin ay gumagana nang maayos, upang ang bawat bloke ng data ay mahahanap sa dalawang magkaibang mga server (ang EBS slave server ay may mahinang processor, kaya hindi namin ito isinasaalang-alang). Hinahati namin ang gawain sa pagitan nila, upang magkaroon kami ng kabuuang 16 na mga core na magagamit.
Maraming core: Sa malapit na hinaharap, ipapamahagi namin ang data sa mga server sa paraang lahat sila ay lumahok sa pagproseso ng bawat kahilingang hindi mahalaga. Ang bawat core ay gagana. [Tandaan: ipinatupad namin ang plano at pinataas ang bilis ng paghahanap sa 1 TB/s, tingnan ang tala sa dulo ng artikulo].
Ang pagiging simple ay nagsisiguro ng pagiging maaasahan
Ang isa pang bentahe ng brute force na paraan ay ang medyo pare-parehong pagganap nito. Karaniwan, ang paghahanap ay hindi masyadong sensitibo sa mga detalye ng problema at set ng data (I guess that's why it's called "coarse").
Ang index ng keyword kung minsan ay gumagawa ng hindi kapani-paniwalang mabilis na mga resulta, at kung minsan ay hindi. Sabihin nating mayroon kang 50 GB ng mga log kung saan eksaktong tatlong beses lumilitaw ang terminong 'customer_5987235982'. Ang paghahanap para sa terminong ito ay nagbibilang ng tatlong lokasyon nang direkta mula sa index at agad na makukumpleto. Ngunit ang mga kumplikadong paghahanap sa wildcard ay maaaring mag-scan ng libu-libong mga keyword at magtagal.
Sa kabilang banda, ang mga brute force na paghahanap ay gumaganap sa halos parehong bilis para sa anumang query. Ang paghahanap ng mahahabang salita ay mas mahusay, ngunit kahit na ang paghahanap para sa isang karakter ay medyo mabilis.
Ang pagiging simple ng paraan ng brute force ay nangangahulugan na ang pagganap nito ay malapit sa teoretikal na maximum nito. Mayroong mas kaunting mga opsyon para sa hindi inaasahang mga overload ng disk, pagtatalo sa lock, paghabol ng pointer, at libu-libong iba pang mga dahilan para sa pagkabigo. Tiningnan ko lang ang mga kahilingan na ginawa ng mga gumagamit ng Scalyr noong nakaraang linggo sa aming pinaka-abalang server. Mayroong 14 kahilingan. Eksaktong walo sa kanila ang tumagal ng higit sa isang segundo; 000% ang nakumpleto sa loob ng 99 millisecond (kung hindi ka pa gumamit ng mga tool sa pagsusuri ng log, magtiwala sa akin: ito ay mabilis).
Ang matatag, maaasahang pagganap ay mahalaga para sa kadalian ng paggamit ng serbisyo. Kung nahuhuli ito nang pana-panahon, iisipin ng mga user na hindi ito mapagkakatiwalaan at nag-aatubiling gamitin ito.
Mag-log search sa aksyon
Narito ang isang maikling animation na nagpapakita ng pagkilos ng paghahanap sa Scalyr. Mayroon kaming demo account kung saan ini-import namin ang bawat kaganapan sa bawat pampublikong Github repository. Sa demo na ito, sinusuri ko ang isang linggong halaga ng data: humigit-kumulang 600 MB ng mga raw log.
Ang video ay naitala nang live, nang walang espesyal na paghahanda, sa aking desktop (mga 5000 kilometro mula sa server). Ang pagganap na makikita mo ay higit sa lahat ay dahil sa , pati na rin ang isang mabilis at maaasahang backend. Sa tuwing may pause na walang 'loading' indicator, ako ang nag-pause para mabasa mo kung ano ang pipindutin ko.
Sa pagtatapos
Kapag nagpoproseso ng malaking halaga ng data, mahalagang pumili ng isang mahusay na algorithm, ngunit ang "mabuti" ay hindi nangangahulugang "magarbong." Isipin kung paano gagana ang iyong code sa pagsasanay. Ang teoretikal na pagsusuri ng mga algorithm ay nag-iiwan ng ilang mga kadahilanan na maaaring maging napakahalaga sa totoong mundo. Ang mga mas simpleng algorithm ay mas madaling i-optimize at mas matatag sa mga gilid na sitwasyon.
Isipin din ang konteksto kung saan ipapatupad ang code. Sa aming kaso, kailangan namin ng sapat na makapangyarihang mga server upang pamahalaan ang mga gawain sa background. Ang mga user ay nagpapasimula ng mga paghahanap na medyo madalang, kaya maaari kaming humiram ng isang buong pangkat ng mga server para sa maikling panahon na kinakailangan upang makumpleto ang bawat paghahanap.
Gamit ang isang brute force na paraan, nagpatupad kami ng mabilis, maaasahan, flexible na paghahanap sa isang hanay ng mga log. Umaasa kami na ang mga ideyang ito ay kapaki-pakinabang para sa iyong mga proyekto.
I-edit: Ang pamagat at teksto ay nagbago mula sa "Maghanap sa 20 GB bawat segundo" patungong "Maghanap sa 1 TB bawat segundo" upang ipakita ang mga pagtaas ng pagganap sa nakalipas na ilang taon. Ang pagtaas ng bilis na ito ay pangunahing dahil sa mga pagbabago sa uri at bilang ng mga EC2 server na inilalagay namin ngayon upang pagsilbihan ang aming dumaraming customer base. May mga paparating na pagbabago na magbibigay ng isa pang dramatikong pagpapalakas sa kahusayan sa pagpapatakbo, at hindi na kami makapaghintay na ibahagi ang mga ito.
Pinagmulan: www.habr.com