TL;DR: Empat tahun lalu saya meninggalkan Google dengan idea untuk alat pemantauan pelayan baharu. Ideanya adalah untuk menggabungkan fungsi yang biasanya terpencil ke dalam satu perkhidmatan dan analisis log, pengumpulan metrik, dan papan pemuka. Salah satu prinsipnya ialah perkhidmatan itu mestilah benar-benar cepat, menyediakan devops dengan pengalaman yang mudah, interaktif dan menyeronokkan. Ini memerlukan pemprosesan set data berbilang gigabait dalam pecahan sesaat sambil kekal dalam bajet. Alat pengurusan log sedia ada selalunya perlahan dan kikuk, jadi kami berdepan dengan cabaran yang baik: mereka bentuk alat dengan bijak untuk memberi pengguna pengalaman baharu.
Artikel ini menerangkan cara kami di Scalyr menyelesaikan masalah ini dengan menggunakan kaedah sekolah lama, pendekatan kekerasan, menghapuskan lapisan yang tidak perlu dan mengelakkan struktur data yang kompleks. Anda boleh menggunakan pelajaran ini untuk masalah kejuruteraan anda sendiri.
Kuasa Sekolah Lama
Analisis log biasanya bermula dengan carian: cari semua mesej yang sepadan dengan corak tertentu. Dalam Scalyr, ini adalah berpuluh atau ratusan gigabait log daripada banyak pelayan. Pendekatan moden, sebagai peraturan, melibatkan pembinaan beberapa struktur data kompleks yang dioptimumkan untuk carian. Saya sudah tentu melihat ini di Google, di mana mereka cukup mahir dalam perkara seperti ini. Tetapi kami menyelesaikan pendekatan yang lebih kasar: pengimbasan linear log. Dan ia berjaya - kami menyediakan antara muka yang boleh dicari yang susunan magnitudnya lebih pantas daripada pesaing kami (lihat animasi di bahagian akhir).
Wawasan utama ialah pemproses moden sememangnya sangat pantas pada operasi yang mudah dan mudah. Ini mudah terlepas dalam sistem berbilang lapisan yang kompleks yang bergantung pada kelajuan I/O dan operasi rangkaian, dan sistem sedemikian sangat biasa hari ini. Jadi kami membangunkan reka bentuk yang meminimumkan lapisan dan serpihan berlebihan. Dengan berbilang pemproses dan pelayan secara selari, kelajuan carian mencapai 1 TB sesaat.
Pengambilan penting daripada artikel ini:
- Carian brute-force ialah pendekatan yang berdaya maju untuk menyelesaikan masalah berskala besar dunia sebenar.
- Brute force ialah teknik reka bentuk, bukan penyelesaian tanpa kerja. Seperti mana-mana teknik, ia lebih sesuai untuk beberapa masalah daripada yang lain, dan boleh dilaksanakan dengan buruk atau baik.
- Brute force amat baik untuk dicapai stabil produktiviti.
- Penggunaan kekerasan yang berkesan memerlukan kod pengoptimuman dan menggunakan sumber yang mencukupi pada masa yang sesuai. Ia sesuai jika pelayan anda berada di bawah beban bukan pengguna yang berat dan operasi pengguna kekal sebagai keutamaan.
- Prestasi bergantung pada reka bentuk keseluruhan sistem, bukan hanya algoritma gelung dalaman.
(Artikel ini menerangkan pencarian data dalam ingatan. Dalam kebanyakan kes, apabila pengguna melakukan carian log, pelayan Scalyr telah mencachenya. Artikel seterusnya akan membincangkan mencari log tidak dicache. Prinsip yang sama digunakan: kod cekap, kekerasan dengan sumber pengiraan yang besar).
Kaedah brute force
Secara tradisinya, set data yang besar dicari menggunakan indeks kata kunci. Apabila digunakan pada log pelayan, ini bermakna mencari setiap perkataan unik dalam log. Untuk setiap perkataan, anda perlu membuat senarai semua kemasukan. Ini memudahkan untuk mencari semua mesej dengan perkataan ini, contohnya 'ralat', 'firefox' atau "transaction_16851951" - lihat sahaja dalam indeks.
Saya menggunakan pendekatan ini di Google dan ia berfungsi dengan baik. Tetapi dalam Scalyr kami mencari bait log demi bait.
kenapa? Dari sudut pandangan algoritmik abstrak, indeks kata kunci jauh lebih cekap daripada carian kekerasan. Walau bagaimanapun, kami tidak menjual algoritma, kami menjual prestasi. Dan prestasi bukan sahaja mengenai algoritma, tetapi juga mengenai kejuruteraan sistem. Kita mesti mempertimbangkan segala-galanya: volum data, jenis carian, konteks perkakasan dan perisian yang tersedia. Kami memutuskan bahawa untuk masalah khusus kami, sesuatu seperti 'grep' adalah lebih sesuai daripada indeks.
Indeks adalah hebat, tetapi ia mempunyai had. Satu perkataan mudah dicari. Tetapi mencari mesej dengan berbilang perkataan, seperti 'googlebot' dan '404', adalah lebih sukar. Mencari frasa seperti 'pengecualian tidak ditangkap' memerlukan indeks yang lebih rumit yang merekodkan bukan sahaja semua mesej dengan perkataan itu, tetapi juga lokasi khusus perkataan itu.
Kesukaran sebenar datang apabila anda tidak mencari kata-kata. Katakan anda ingin melihat jumlah trafik yang datang daripada bot. Pemikiran pertama ialah mencari log untuk perkataan 'bot'. Beginilah cara anda akan menemui beberapa bot: Googlebot, Bingbot dan banyak lagi. Tetapi di sini 'bot' bukan perkataan, tetapi sebahagian daripadanya. Jika kami mencari 'bot' dalam indeks, kami tidak akan menemui sebarang siaran dengan perkataan 'Googlebot'. Jika anda menyemak setiap perkataan dalam indeks dan kemudian mengimbas indeks untuk kata kunci yang ditemui, carian akan menjadi sangat perlahan. Akibatnya, sesetengah program log tidak membenarkan carian separuh perkataan atau (paling baik) membenarkan sintaks khas dengan prestasi yang lebih rendah. Kami mahu mengelakkan ini.
Masalah lain ialah tanda baca. Adakah anda ingin mencari semua permintaan daripada 50.168.29.7? Bagaimana pula dengan log nyahpepijat yang mengandungi [error]? Subskrip biasanya melangkau tanda baca.
Akhirnya, jurutera menyukai alat yang berkuasa, dan kadangkala masalah hanya boleh diselesaikan dengan ungkapan biasa. Indeks kata kunci tidak begitu sesuai untuk ini.
Selain itu, indeks kompleks. Setiap mesej perlu ditambahkan pada beberapa senarai kata kunci. Senarai ini hendaklah disimpan dalam format yang mudah dicari pada setiap masa. Pertanyaan dengan frasa, serpihan perkataan atau ungkapan biasa perlu diterjemahkan ke dalam operasi berbilang senarai dan keputusan diimbas serta digabungkan untuk menghasilkan set hasil. Dalam konteks perkhidmatan berbilang penyewa berskala besar, kerumitan ini mewujudkan isu prestasi yang tidak dapat dilihat semasa menganalisis algoritma.
Indeks kata kunci juga mengambil banyak ruang, dan penyimpanan merupakan kos utama dalam sistem pengurusan log.
Sebaliknya, setiap carian boleh menggunakan banyak kuasa pengkomputeran. Pengguna kami menghargai carian berkelajuan tinggi untuk pertanyaan unik, tetapi pertanyaan sedemikian jarang dibuat. Untuk pertanyaan carian biasa, contohnya, untuk papan pemuka, kami menggunakan teknik khas (kami akan menerangkannya dalam artikel seterusnya). Permintaan lain cukup jarang sehingga anda jarang perlu memproses lebih daripada satu demi satu. Tetapi ini tidak bermakna pelayan kami tidak sibuk: mereka sibuk dengan kerja menerima, menganalisis dan memampatkan mesej baharu, menilai makluman, memampatkan data lama dan sebagainya. Oleh itu, kami mempunyai bekalan pemproses yang agak ketara yang boleh digunakan untuk melaksanakan pertanyaan.
Brute force berfungsi jika anda mempunyai masalah kasar (dan banyak kekerasan)
Brute force berfungsi paling baik pada masalah mudah dengan gelung dalaman yang kecil. Selalunya anda boleh mengoptimumkan gelung dalaman untuk berjalan pada kelajuan yang sangat tinggi. Jika kod itu rumit, adalah lebih sukar untuk mengoptimumkannya.
Kod carian kami pada asalnya mempunyai gelung dalaman yang agak besar. Kami menyimpan mesej pada halaman pada 4K; setiap halaman mengandungi beberapa mesej (dalam UTF-8) dan metadata untuk setiap mesej. Metadata ialah struktur yang mengekodkan panjang nilai, ID mesej dalaman dan medan lain. Kitaran carian kelihatan seperti ini:
Ini ialah versi ringkas kod sebenar. Tetapi di sini, berbilang peletakan objek, salinan data dan panggilan fungsi boleh dilihat. JVM cukup bagus dalam mengoptimumkan panggilan fungsi dan memperuntukkan objek yang tidak kekal, jadi kod ini berfungsi lebih baik daripada yang sepatutnya. Semasa ujian, pelanggan menggunakannya dengan agak berjaya. Tetapi akhirnya kami membawanya ke peringkat seterusnya.
(Anda mungkin bertanya mengapa kami menyimpan mesej dalam format ini dengan halaman 4K, teks dan metadata, dan bukannya bekerja dengan log secara langsung. Terdapat banyak sebab, yang berpunca daripada fakta bahawa secara dalaman enjin Scalyr lebih seperti pangkalan data yang diedarkan daripada sistem fail. Carian teks selalunya digabungkan dengan penapis gaya DBMS dalam jidar selepas penghuraian log. Kami boleh mencari beribu-ribu log serentak pada masa yang sama dan fail teks ringkas tidak sesuai untuk pengurusan data transaksi, replika dan teragih kami).
Pada mulanya, nampaknya kod sedemikian tidak begitu sesuai untuk pengoptimuman kekerasan. "Kerja sebenar" dalam String.indexOf() bahkan tidak menguasai profil CPU. Maksudnya, mengoptimumkan kaedah ini sahaja tidak akan membawa kesan yang ketara.
Kebetulan kami menyimpan metadata pada permulaan setiap halaman, dan teks semua mesej dalam UTF-8 dibungkus di hujung yang lain. Mengambil kesempatan daripada ini, kami menulis semula gelung untuk mencari seluruh halaman sekaligus:
Versi ini berfungsi secara langsung pada paparan raw byte[] dan mencari semua mesej sekali gus merentas seluruh halaman 4K.
Ini adalah lebih mudah untuk dioptimumkan untuk kaedah kekerasan. Gelung carian dalaman dipanggil serentak untuk keseluruhan halaman 4K, bukannya secara berasingan pada setiap siaran. Tiada penyalinan data, tiada peruntukan objek. Dan operasi metadata yang lebih kompleks dipanggil hanya apabila hasilnya positif, dan bukan pada setiap mesej. Dengan cara ini kami telah menghapuskan satu tan overhed, dan beban selebihnya tertumpu dalam gelung carian dalaman yang kecil, yang sangat sesuai untuk pengoptimuman selanjutnya.
Algoritma carian sebenar kami adalah berdasarkan . Ia serupa dengan algoritma Boyer-Moore, melangkau lebih kurang panjang rentetan carian pada setiap langkah. Perbezaan utama ialah ia menyemak dua bait pada satu masa untuk meminimumkan padanan palsu.
Pelaksanaan kami memerlukan membuat jadual carian 64K untuk setiap carian, tetapi itu tidak seberapa berbanding dengan gigabait data yang kami cari melalui. Gelung dalam memproses beberapa gigabait sesaat pada satu teras. Dalam amalan, prestasi stabil adalah sekitar 1,25 GB sesaat pada setiap teras, dan terdapat ruang untuk penambahbaikan. Adalah mungkin untuk menghapuskan beberapa overhed di luar gelung dalam, dan kami merancang untuk bereksperimen dengan gelung dalam dalam C dan bukannya Java.
Kami menggunakan kekerasan
Kami telah membincangkan bahawa carian log boleh dilaksanakan "secara kasar", tetapi berapa banyak "kuasa" yang kita ada? Agak banyak.
1 teras: Apabila digunakan dengan betul, satu teras pemproses moden agak berkuasa dengan sendirinya.
8 teras: Kami sedang berjalan pada pelayan SSD hi1.4xlarge dan i2.4xlarge Amazon, masing-masing dengan 8 teras (16 utas). Seperti yang dinyatakan di atas, teras ini biasanya sibuk dengan operasi latar belakang. Apabila pengguna melakukan carian, operasi latar belakang digantung, membebaskan kesemua 8 teras untuk carian. Carian biasanya selesai dalam sepersekian saat, selepas itu kerja latar belakang disambung semula (program pendikit memastikan bahawa barisan pertanyaan carian tidak mengganggu kerja latar belakang yang penting).
16 teras: untuk kebolehpercayaan, kami menyusun pelayan ke dalam kumpulan tuan/hamba. Setiap tuan mempunyai satu SSD dan satu pelayan EBS di bawah arahannya. Jika pelayan utama ranap, pelayan SSD segera mengambil tempatnya. Hampir sepanjang masa, tuan dan hamba berfungsi dengan baik, supaya setiap blok data boleh dicari pada dua pelayan yang berbeza (pelayan hamba EBS mempunyai pemproses yang lemah, jadi kami tidak menganggapnya). Kami membahagikan tugas di antara mereka, supaya kami mempunyai sejumlah 16 teras yang tersedia.
Banyak teras: Dalam masa terdekat, kami akan mengedarkan data merentas pelayan dengan cara yang mereka semua mengambil bahagian dalam memproses setiap permintaan yang bukan remeh. Setiap teras akan berfungsi. [Catatan: kami melaksanakan rancangan itu dan meningkatkan kelajuan carian kepada 1 TB/s, lihat nota di penghujung artikel].
Kesederhanaan memastikan kebolehpercayaan
Satu lagi kelebihan kaedah kekerasan adalah prestasi yang agak konsisten. Biasanya, carian tidak begitu sensitif kepada butiran masalah dan set data (saya rasa itulah sebabnya ia dipanggil "kasar").
Indeks kata kunci kadangkala menghasilkan hasil yang sangat pantas, dan kadangkala tidak. Katakan anda mempunyai 50 GB log di mana istilah 'customer_5987235982' muncul tepat tiga kali. Carian untuk istilah ini mengira tiga lokasi terus daripada indeks dan akan selesai serta-merta. Tetapi carian kad bebas yang kompleks boleh mengimbas beribu-ribu kata kunci dan mengambil masa yang lama.
Sebaliknya, carian kekerasan berprestasi pada kelajuan yang lebih kurang sama untuk sebarang pertanyaan. Mencari perkataan yang panjang adalah lebih baik, tetapi mencari satu aksara pun agak pantas.
Kesederhanaan kaedah brute force bermakna prestasinya hampir kepada maksimum teorinya. Terdapat lebih sedikit pilihan untuk lebihan cakera yang tidak dijangka, pertikaian kunci, mengejar penunjuk dan beribu-ribu sebab lain untuk kegagalan. Saya hanya melihat permintaan yang dibuat oleh pengguna Scalyr minggu lepas pada pelayan tersibuk kami. Terdapat 14 permintaan. Tepat lapan daripada mereka mengambil masa lebih daripada satu saat; 000% selesai dalam masa 99 milisaat (jika anda belum menggunakan alat analisis log, percayalah saya: ia cepat).
Prestasi yang stabil dan boleh dipercayai adalah penting untuk kemudahan penggunaan perkhidmatan. Jika ia ketinggalan secara berkala, pengguna akan menganggapnya sebagai tidak boleh dipercayai dan enggan menggunakannya.
Carian log dalam tindakan
Berikut ialah animasi pendek yang menunjukkan carian Scalyr dalam tindakan. Kami mempunyai akaun demo di mana kami mengimport setiap acara dalam setiap repositori Github awam. Dalam demo ini, saya meneliti data bernilai seminggu: kira-kira 600 MB log mentah.
Video itu dirakam secara langsung, tanpa penyediaan khas, pada desktop saya (kira-kira 5000 kilometer dari pelayan). Prestasi yang anda akan lihat sebahagian besarnya disebabkan oleh , serta bahagian belakang yang pantas dan boleh dipercayai. Setiap kali ada jeda tanpa penunjuk 'pemuatan', sayalah yang berhenti seketika supaya anda boleh membaca perkara yang saya akan tekan.
Kesimpulannya
Apabila memproses sejumlah besar data, adalah penting untuk memilih algoritma yang baik, tetapi "baik" tidak bermaksud "mewah". Fikirkan tentang cara kod anda akan berfungsi dalam amalan. Analisis teori algoritma meninggalkan beberapa faktor yang boleh menjadi sangat penting dalam dunia sebenar. Algoritma yang lebih mudah adalah lebih mudah untuk dioptimumkan dan lebih stabil dalam situasi tepi.
Fikirkan juga tentang konteks di mana kod itu akan dilaksanakan. Dalam kes kami, kami memerlukan pelayan yang cukup berkuasa untuk mengurus tugas latar belakang. Pengguna memulakan carian agak jarang, jadi kami boleh meminjam keseluruhan kumpulan pelayan untuk tempoh singkat yang diperlukan untuk melengkapkan setiap carian.
Menggunakan kaedah kekerasan, kami melaksanakan carian yang pantas, boleh dipercayai dan fleksibel merentas set log. Kami berharap idea ini berguna untuk projek anda.
Edit: Tajuk dan teks telah ditukar daripada "Cari pada 20 GB sesaat" kepada "Cari pada 1 TB sesaat" untuk mencerminkan peningkatan prestasi sejak beberapa tahun lalu. Peningkatan kelajuan ini terutamanya disebabkan oleh perubahan dalam jenis dan bilangan pelayan EC2 yang kami sediakan hari ini untuk melayani pangkalan pelanggan kami yang bertambah. Terdapat perubahan yang akan datang tidak lama lagi yang akan memberikan satu lagi rangsangan dramatik dalam kecekapan operasi, dan kami tidak sabar untuk berkongsinya.
Sumber: www.habr.com