TL; DR: Opat taun ka tukang kuring ninggalkeun Google sareng ideu pikeun alat ngawaskeun server énggal. Gagasanna nyaéta ngagabungkeun fungsi anu biasana terasing kana hiji layanan jeung analisis log, ngumpulkeun métrik, jeung dasbor. Salah sahiji prinsipna nyaéta yén jasa kedah leres-leres gancang, nyadiakeun devops kalawan gampang, interaktif, pangalaman nikmat. Ieu peryogi ngolah set data multi-gigabyte dina fraksi sadetik bari tetep dina anggaran. Alat manajemén log anu aya sering lambat sareng kikuk, janten kami disanghareupan tangtangan anu saé: pinter ngarancang alat pikeun masihan pangguna pangalaman énggal.
Artikel ieu ngajelaskeun kumaha urang di Scalyr direngsekeun masalah ieu ku nerapkeun métode sakola heubeul, pendekatan brute force, ngaleungitkeun lapisan teu perlu jeung Ngahindarkeun struktur data kompléks. Anjeun tiasa nerapkeun palajaran ieu kana masalah rékayasa anjeun sorangan.
Kakuatan Sakola Heubeul
Analisis log biasana dimimitian ku milarian: panggihan sadaya pesen anu cocog sareng pola anu tangtu. Dina Scalyr, ieu mangrupikeun puluhan atanapi ratusan gigabyte log tina seueur server. pendekatan modern, sakumaha aturan, ngalibetkeun pangwangunan sababaraha struktur data kompléks dioptimalkeun pikeun pilarian. Kuring pasti ningali ieu dina Google, dimana aranjeunna lumayan saé dina hal ieu. Tapi kami netep dina pendekatan anu langkung kasar: scanning log linier. Sareng éta damel - kami nyayogikeun antarbeungeut anu tiasa dipilarian anu langkung ageung langkung gancang tibatan pesaing kami (tingali animasi dina tungtungna).
Wawasan konci éta prosesor modéren memang gancang pisan dina operasi anu sederhana sareng lugas. Ieu gampang sono dina kompléks, sistem multi-lapisan nu ngandelkeun I / O speed na jaringan operasi, sarta sistem sapertos pisan umum kiwari. Janten urang ngembangkeun desain anu ngaminimalkeun lapisan sareng kaleuwihan lebu. Kalayan sababaraha prosesor sareng server paralel, laju milarian ngahontal 1 TB per detik.
Takeaways konci tina artikel ieu:
- Pilarian brute-force mangrupikeun pendekatan anu lumayan pikeun ngarengsekeun masalah-masalah skala ageung di dunya nyata.
- Brute force mangrupikeun téknik desain, sanés solusi anu henteu dianggo. Sapertos téknik naon waé, éta langkung cocog pikeun sababaraha masalah tibatan anu sanés, sareng tiasa dilaksanakeun kirang atanapi saé.
- Brute force hususna hadé pikeun ngahontal stabil produktivitas.
- Pamakéan brute force anu éféktif merlukeun optimalisasi kode jeung nerapkeun sumber daya anu cukup dina waktu anu pas. Cocog upami server anjeun aya dina beban non-pamaké anu beurat sareng operasi pangguna tetep janten prioritas.
- Performance gumantung kana desain sakabéh sistem, teu ngan algoritma loop jero.
(Artikel ieu ngajelaskeun milarian data dina mémori. Dina kalolobaan kasus, nalika pangguna milarian log, server Scalyr parantos nyéépkeun éta. kalawan sumberdaya komputasi badag).
Métode Brute Force
Sacara tradisional, hiji set data badag anu searched maké indéks keyword. Nalika dilarapkeun kana log server, ieu hartosna milarian unggal kecap unik dina log. Pikeun unggal kecap, anjeun kedah ngadamel daptar sadaya inklusi. Ieu ngagampangkeun milarian sadaya pesen nganggo kecap ieu, contona 'kasalahan', 'firefox' atanapi "transaction_16851951" - tingali dina indéks.
I dipaké pendekatan ieu di Google sarta digawé ogé. Tapi dina Scalyr urang milarian log byte byte.
Naha? Tina sudut pandang algoritmik anu abstrak, indéks kecap konci langkung épisién tibatan milarian gaya kasar. Nanging, kami henteu ngajual algoritma, kami ngajual kinerja. Sareng pagelaran henteu ngan ukur ngeunaan algoritma, tapi ogé ngeunaan rékayasa sistem. Urang kudu mertimbangkeun sagalana: volume data, tipe pilarian, hardware sadia tur konteks software. Kami mutuskeun yén pikeun masalah khusus urang, sapertos 'grep' langkung cocog tibatan indéks.
Indexes anu hébat, tapi maranéhna boga watesan. Hiji kecap gampang pikeun manggihan. Tapi milarian pesen nganggo sababaraha kecap, sapertos 'googlebot' sareng '404', langkung sesah. Milarian frasa sapertos 'pangecualian anu teu katangkep' peryogi indéks anu langkung rumit anu ngarékam henteu ngan ukur sadaya pesen anu nganggo kecap éta, tapi ogé lokasi khusus kecap éta.
Kasusah nyata datang nalika anjeun teu pilari kecap. Anggap anjeun hoyong ningali sabaraha lalu lintas anu asalna tina bot. Pikiran kahiji nyaéta milarian log pikeun kecap 'bot'. Ieu kumaha anjeun bakal mendakan sababaraha bot: Googlebot, Bingbot sareng seueur anu sanésna. Tapi di dieu 'bot' sanés kecap, tapi bagian tina éta. Upami urang milarian 'bot' dina indéks, urang moal mendakan tulisan anu nganggo kecap 'Googlebot'. Lamun pariksa unggal kecap dina indéks lajeng nyeken indéks pikeun kecap konci kapanggih, pilarian bakal ngalambatkeun turun greatly. Hasilna, sababaraha program log teu ngidinan pilarian bagian-kecap atawa (paling pangalusna) ngidinan sintaksis husus kalawan kinerja handap. Urang rék nyingkahan ieu.
Masalah séjén nyaéta tanda baca. Naha anjeun hoyong milarian sadaya pamundut ti 50.168.29.7? Kumaha upami debugging log ngandung [error]? Langganan biasana ngalewatan tanda baca.
Tungtungna, insinyur cinta alat kuat, sarta kadangkala masalah ngan bisa direngsekeun ku éksprési biasa. Indéks keyword henteu cocog pisan pikeun ieu.
Sajaba ti éta, indéks kompléks. Unggal pesen kudu ditambahkeun kana sababaraha daptar keyword. Daptar ieu kudu disimpen dina format gampang searchable sepanjang waktos. Patarosan sareng frasa, fragmen kecap, atanapi ekspresi biasa kedah ditarjamahkeun kana operasi multi-daftar, sareng hasil scan sareng digabungkeun pikeun ngahasilkeun set hasil. Dina konteks layanan multi-tenant skala ageung, pajeulitna ieu nyiptakeun masalah kinerja anu henteu katingali nalika nganalisa algoritma.
Indéks kecap konci ogé nyéépkeun seueur rohangan, sareng neundeun mangrupikeun biaya utama dina sistem manajemén log.
Di sisi séjén, unggal pilarian bisa meakeun loba daya komputasi. Pamaké kami ngahargaan panéangan-speed tinggi pikeun queries unik, tapi queries sapertos dijieun relatif jarang. Pikeun queries pilarian has, contona, pikeun dasbor, kami ngagunakeun téhnik husus (urang bakal ngajelaskeun aranjeunna dina artikel salajengna). Paménta sanésna jarang pisan sahingga anjeun jarang kedah ngolah langkung ti hiji sakaligus. Tapi ieu lain hartosna yén server kami henteu sibuk: aranjeunna sibuk ku karya narima, analisa jeung compressing pesen anyar, evaluating ngabejaan, compressing data heubeul, jeung saterusna. Ku kituna, urang boga suplai cukup signifikan tina prosesor nu bisa dipaké pikeun ngaéksekusi queries.
Gaya kasar tiasa dianggo upami anjeun gaduh masalah kasar (sareng seueur kakuatan)
Gaya brute jalan pangalusna dina masalah basajan kalawan loop internal leutik. Sering anjeun tiasa ngaoptimalkeun loop internal pikeun ngajalankeun dina kecepatan anu luhur pisan. Upami kodena rumit, langkung hese pikeun ngaoptimalkeunana.
Kode pilarian kami asalna miboga loop jero cukup badag. Urang nyimpen pesen dina kaca dina 4K; unggal kaca ngandung sababaraha seratan (dina UTF-8) jeung metadata pikeun tiap pesen. Metadata mangrupikeun struktur anu nangkodkeun panjang nilai, ID pesen internal, sareng widang anu sanés. Daur panéangan katingali sapertos kieu:
Ieu versi saderhana tina kode sabenerna. Tapi sanajan di dieu, sababaraha panempatan obyék, salinan data, sareng telepon fungsi katingali. JVM lumayan saé pikeun ngaoptimalkeun sauran fungsi sareng alokasi objék ephemeral, janten kode ieu langkung saé tibatan anu pantes. Salila tés, para nasabah nganggo éta lumayan suksés. Tapi ahirna urang nyandak eta ka tingkat salajengna.
(Anjeun bisa jadi nanya naha urang nyimpen pesen dina format ieu kalawan kaca 4K, téks na metadata, tinimbang gawé bareng log langsung. Aya loba alesan, nu kulub handap kanyataan yén internal mesin Scalyr leuwih kawas database disebarkeun ti a Sistim file. Pilarian téks mindeng digabungkeun jeung DBMS-gaya saringan dina margins sanggeus log parsing. Urang sakaligus bisa neangan loba rébuan log sakaligus, sarta file téks basajan teu cocog pikeun transactional kami, replicated, manajemén data disebarkeun).
Mimitina, sigana yén kode sapertos kitu henteu cocog pisan pikeun optimasi gaya kasar. "Karya nyata" dina String.indexOf() malah teu ngadominasi profil CPU. Hartina, optimizing metoda ieu nyalira moal mawa éfék signifikan.
Éta kajadian yén urang nyimpen metadata di awal unggal halaman, sareng téks sadaya pesen dina UTF-8 dibungkus dina tungtung anu sanés. Ngamangpaatkeun ieu, urang rewrote loop pikeun neangan sakabéh kaca sakaligus:
Vérsi ieu jalan langsung dina pintonan raw byte[] sareng milarian sadaya pesen sakaligus dina sadaya halaman 4K.
Ieu leuwih gampang pikeun ngaoptimalkeun metoda brute force. The loop pilarian internal disebut sakaligus pikeun sakabéh kaca 4K, tinimbang misah dina unggal pos. Henteu aya salinan data, henteu aya alokasi objék. Sareng operasi metadata anu langkung kompleks disebut ngan ukur nalika hasilna positip, sareng henteu dina unggal pesen. Ku cara ieu kami geus ngaleungitkeun hiji ton overhead, sarta sesa beban ieu ngumpul dina loop pilarian internal leutik, nu ogé cocog pikeun optimasi salajengna.
Algoritma pilarian sabenerna kami dumasar kana . Ieu sarupa jeung algoritma Boyer-Moore, skipping kira panjang string pilarian dina unggal hambalan. Beda utama nyaéta yén éta pariksa dua bait sakaligus pikeun ngaminimalkeun patandingan palsu.
Palaksanaan kami merlukeun nyieun tabel lookup 64K pikeun tiap pilarian, tapi éta nanaon dibandingkeun jeung gigabytes data urang ditéang ngaliwatan. Gelung batin ngolah sababaraha gigabyte per detik dina hiji inti. Dina prakték, kinerja stabil sabudeureun 1,25 GB per detik dina unggal inti, tur aya rohangan pikeun perbaikan. Kasebut nyaéta dimungkinkeun pikeun ngaleungitkeun sababaraha overhead luar tina loop jero, sarta kami rencanana ékspérimén kalawan loop jero dina C tinimbang Java.
Urang ngagunakeun kakuatan
Kami parantos ngabahas yén milarian log tiasa dilaksanakeun "kasarna", tapi sabaraha "kakuatan" anu urang gaduh? Cukup loba.
1 inti: Lamun dipaké leres, inti tunggal processor modern cukup kuat dina katuhu sorangan.
8 cores: Urang ayeuna ngajalankeun on Amazon hi1.4xlarge na i2.4xlarge server SSD, unggal kalawan 8 cores (16 threads). Sakumaha didadarkeun di luhur, cores ieu biasana sibuk jeung operasi tukang. Nalika pangguna ngalaksanakeun panéangan, operasi latar digantungkeun, ngabébaskeun sadayana 8 inti pikeun milarian. Pamilarian biasana réngsé dina sadetik, saatos éta padamelan latar diteruskeun (program throttling mastikeun yén barrage queries milarian henteu ngaganggu padamelan latar anu penting).
16 cores: pikeun reliabilitas, urang ngatur server kana master / grup budak. Unggal master gaduh hiji SSD sareng hiji server EBS dina paréntahna. Lamun server utama ngadat, server SSD langsung nyokot tempatna. Ampir sadaya waktu, master na budak gawéna rupa, ku kituna unggal blok data anu searchable dina dua server béda (server budak EBS boga processor lemah, sangkan teu nganggap eta). Urang ngabagi tugas antara aranjeunna, ku kituna urang boga total 16 cores sadia.
Loba cores: Dina mangsa nu bakal datang, urang bakal ngadistribusikaeun data sakuliah server dina cara sapertos nu aranjeunna sadayana ilubiung dina ngolah unggal pamundut non-trivial. Unggal inti bakal jalan. [Catetan: kami ngalaksanakeun rencana sareng ningkatkeun kagancangan milarian ka 1 TB / s, tingali catetan dina tungtung tulisan].
Kesederhanaan mastikeun reliabilitas
Kauntungan sejen tina metoda brute force nyaéta kinerja anu cukup konsisten. Ilaharna, pilarian teu pisan sénsitip kana detil masalah na data set (Kuring nebak éta naha mangka disebut "kasar").
Indéks keyword kadang ngahasilkeun hasil incredibly gancang, sarta kali séjén teu. Anggap anjeun gaduh 50 GB log dimana istilah 'customer_5987235982' muncul persis tilu kali. Pilarian pikeun istilah ieu cacah tilu lokasi langsung ti indéks jeung bakal ngalengkepan instan. Tapi pamilarian wildcard kompléks tiasa nyeken rébuan kecap konci sareng nyandak waktos anu lami.
Di sisi anu sanés, pamilarian brute force ngalaksanakeun langkung seueur atanapi kirang kecepatan anu sami pikeun pamundut naon waé. Milarian kecap anu panjang langkung saé, tapi milarian karakter tunggal anu cukup gancang.
Kesederhanaan metode brute force hartina kinerja na deukeut ka maksimum teoritis na. Aya pilihan pangsaeutikna pikeun overloads disk kaduga, contention konci, pointer ngudag, sarta rébuan alesan séjén pikeun gagal. Kuring ngan nempo requests dijieun ku pamaké Scalyr minggu panungtungan on server pangsibukna urang. Aya 14 pamundut. Persis dalapan di antarana nyandak leuwih ti hiji detik; 000% réngsé dina 99 milidetik (upami anjeun teu acan nganggo alat analisis log, percanten ka kuring: éta gancang).
Stabil, kinerja dipercaya penting pikeun betah pamakéan jasa. Lamun lags périodik, pamaké bakal ngarasa salaku teu bisa dipercaya jeung horéam ngagunakeun eta.
Log pilarian dina aksi
Ieu animasi pondok anu nunjukkeun panéangan Scalyr dina aksi. Kami gaduh akun demo dimana urang ngimpor unggal acara di unggal gudang Github umum. Dina demo ieu, kuring nalungtik patut saminggu data: kira 600 MB log atah.
Video dirékam langsung, tanpa persiapan khusus, dina desktop kuring (sakitar 5000 kilométer ti server). Kinerja anu anjeun tingali seueurna kusabab , kitu ogé backend gancang jeung dipercaya. Iraha waé aya jeda tanpa indikator 'loading', éta kuring ngareureuhkeun supados anjeun tiasa maca naon anu kuring badé pencét.
dina kacindekan
Nalika ngolah data anu ageung, penting pikeun milih algoritma anu saé, tapi "saé" sanés hartosna "mewah". Pikirkeun kumaha kode anjeun bakal dianggo dina prakna. Analisis téoritis algoritma ninggalkeun sababaraha faktor anu tiasa penting pisan dina dunya nyata. Algoritma saderhana langkung gampang dioptimalkeun sareng langkung stabil dina kaayaan ujung.
Pikirkeun ogé kontéks dimana kodeu bakal dieksekusi. Dina kasus urang, urang peryogi server anu cukup kuat pikeun ngatur tugas latar. Pamaké ngamimitian maluruh rélatif jarang, ku kituna urang bisa nginjeum sakabéh grup server pikeun periode pondok diperlukeun pikeun ngalengkepan unggal pilarian.
Ngagunakeun métode brute force, urang nerapkeun gancang, dipercaya, pilarian fléksibel sakuliah susunan log. Kami ngarepkeun ideu ieu mangpaat pikeun proyék anjeun.
Édit: Judul sareng téks parantos robih tina "Pilarian dina 20 GB per detik" janten "Pilarian dina 1 TB per detik" pikeun ngagambarkeun paningkatan kinerja dina sababaraha taun ka pengker. Kanaékan kagancangan ieu utamina kusabab parobihan dina jinis sareng jumlah server EC2 anu kami pasang ayeuna pikeun ngalayanan pangkalan palanggan kami. Aya parobihan anu bakal datang anu bakal masihan dorongan dramatis dina efisiensi operasional, sareng urang henteu tiasa ngantosan pikeun ngabagikeunana.
sumber: www.habr.com