TL;DR: Empat tahun lalu saya meninggalkan Google dengan ide untuk alat pemantauan server baru. Idenya adalah untuk menggabungkan fungsi-fungsi yang biasanya terisolasi menjadi satu layanan dan analisis log, pengumpulan metrik, dan dasbor. Salah satu prinsipnya adalah pelayanan harus benar-benar cepat, memberikan pengalaman yang mudah, interaktif, dan menyenangkan bagi para pengembang. Hal ini memerlukan pemrosesan kumpulan data multi-gigabyte dalam sepersekian detik namun tetap sesuai anggaran. Alat pengelolaan log yang ada sering kali lambat dan kikuk, jadi kami dihadapkan pada tantangan yang bagus: merancang alat dengan cerdas untuk memberikan pengalaman baru kepada pengguna.
Artikel ini menjelaskan bagaimana kami di Scalyr memecahkan masalah ini dengan menerapkan metode jadul, pendekatan brute force, menghilangkan lapisan yang tidak diperlukan, dan menghindari struktur data yang rumit. Anda dapat menerapkan pelajaran ini pada masalah teknik Anda sendiri.
Kekuatan Sekolah Tua
Analisis log biasanya dimulai dengan pencarian: menemukan semua pesan yang cocok dengan pola tertentu. Di Scalyr, ini adalah puluhan atau ratusan gigabyte log dari banyak server. Pendekatan modern, pada umumnya, melibatkan pembangunan beberapa struktur data kompleks yang dioptimalkan untuk pencarian. Saya pasti pernah melihat ini di Google, di mana mereka cukup pandai dalam hal semacam ini. Namun kami memilih pendekatan yang lebih kasar: pemindaian log secara linier. Dan itu berhasil - kami menyediakan antarmuka yang dapat ditelusuri jauh lebih cepat dibandingkan pesaing kami (lihat animasi di bagian akhir).
Wawasan utamanya adalah bahwa prosesor modern memang sangat cepat dalam pengoperasian yang sederhana dan mudah. Hal ini mudah diabaikan dalam sistem multi-lapisan yang kompleks yang mengandalkan kecepatan I/O dan operasi jaringan, dan sistem seperti itu sangat umum saat ini. Jadi kami mengembangkan desain yang meminimalkan lapisan dan serpihan berlebih. Dengan beberapa prosesor dan server secara paralel, kecepatan pencarian mencapai 1 TB per detik.
Poin penting dari artikel ini:
- Pencarian brute force adalah pendekatan yang layak untuk memecahkan masalah berskala besar di dunia nyata.
- Brute force adalah teknik desain, bukan solusi tanpa pekerjaan. Seperti teknik apa pun, teknik ini lebih cocok untuk beberapa masalah dibandingkan yang lain, dan dapat diterapkan dengan buruk atau baik.
- Kekerasan sangat baik untuk pencapaian stabil produktifitas.
- Penggunaan brute force yang efektif memerlukan pengoptimalan kode dan penerapan sumber daya yang memadai pada waktu yang tepat. Sangat cocok jika server Anda berada di bawah beban non-pengguna yang berat dan operasi pengguna tetap menjadi prioritas.
- Kinerja bergantung pada desain keseluruhan sistem, bukan hanya algoritma loop dalam.
(Artikel ini menjelaskan pencarian data di memori. Dalam kebanyakan kasus, ketika pengguna melakukan pencarian log, server Scalyr telah menyimpannya dalam cache. Artikel berikutnya akan membahas pencarian log yang tidak di-cache. Prinsip yang sama berlaku: kode efisien, brute force dengan sumber daya komputasi yang besar).
Metode kekerasan
Secara tradisional, kumpulan data besar dicari menggunakan indeks kata kunci. Ketika diterapkan pada log server, ini berarti mencari setiap kata unik di log. Untuk setiap kata, Anda perlu membuat daftar semua penyertaannya. Hal ini memudahkan untuk menemukan semua pesan dengan kata ini, misalnya 'kesalahan', 'firefox' atau "transaksi_16851951" - lihat saja di indeks.
Saya menggunakan pendekatan ini di Google dan berhasil dengan baik. Namun di Scalyr kami mencari log byte demi byte.
Mengapa? Dari sudut pandang algoritmik abstrak, indeks kata kunci jauh lebih efisien daripada pencarian brute force. Namun, kami tidak menjual algoritma, kami menjual kinerja. Dan kinerja bukan hanya tentang algoritma, tetapi juga tentang rekayasa sistem. Kita harus mempertimbangkan segalanya: volume data, jenis pencarian, konteks perangkat keras dan perangkat lunak yang tersedia. Kami memutuskan bahwa untuk masalah khusus kami, sesuatu seperti 'grep' lebih cocok daripada indeks.
Indeks memang bagus, tetapi memiliki keterbatasan. Satu kata mudah ditemukan. Namun menelusuri pesan dengan banyak kata, seperti 'googlebot' dan '404', jauh lebih sulit. Menelusuri frasa seperti 'pengecualian yang tidak tertangkap' memerlukan indeks yang lebih rumit yang mencatat tidak hanya semua pesan dengan kata tersebut, namun juga lokasi spesifik dari kata tersebut.
Kesulitan sebenarnya datang ketika Anda tidak mencari kata-kata. Katakanlah Anda ingin melihat berapa banyak lalu lintas yang berasal dari bot. Pikiran pertama adalah mencari kata 'bot' di log. Beginilah cara Anda menemukan beberapa bot: Googlebot, Bingbot, dan banyak lainnya. Namun di sini 'bot' bukanlah sebuah kata, melainkan bagian darinya. Jika kita mencari 'bot' di indeks, kita tidak akan menemukan postingan dengan kata 'Googlebot'. Jika Anda memeriksa setiap kata dalam indeks dan kemudian memindai indeks untuk mencari kata kunci yang ditemukan, pencarian akan sangat melambat. Akibatnya, beberapa program log tidak mengizinkan pencarian sebagian kata atau (paling banter) mengizinkan sintaksis khusus dengan kinerja lebih rendah. Kami ingin menghindari hal ini.
Masalah lainnya adalah tanda baca. Apakah Anda ingin menemukan semua permintaan dari 50.168.29.7? Bagaimana dengan debugging log yang berisi [error]? Subskrip biasanya melewatkan tanda baca.
Terakhir, para insinyur menyukai alat yang canggih, dan terkadang masalah hanya dapat diselesaikan dengan ekspresi reguler. Indeks kata kunci sangat tidak cocok untuk ini.
Selain itu, indeks kompleks. Setiap pesan perlu ditambahkan ke beberapa daftar kata kunci. Daftar ini harus disimpan dalam format yang mudah dicari setiap saat. Kueri dengan frasa, fragmen kata, atau ekspresi reguler perlu diterjemahkan ke dalam operasi multi-daftar, dan hasilnya dipindai serta digabungkan untuk menghasilkan kumpulan hasil. Dalam konteks layanan multi-penyewa berskala besar, kompleksitas ini menciptakan masalah kinerja yang tidak terlihat saat menganalisis algoritme.
Indeks kata kunci juga memakan banyak ruang, dan penyimpanan merupakan biaya utama dalam sistem manajemen log.
Di sisi lain, setiap pencarian dapat menghabiskan banyak daya komputasi. Pengguna kami menghargai pencarian berkecepatan tinggi untuk pertanyaan unik, namun pertanyaan seperti itu relatif jarang dibuat. Untuk kueri penelusuran biasa, misalnya untuk dasbor, kami menggunakan teknik khusus (kami akan menjelaskannya di artikel berikutnya). Permintaan lainnya cukup jarang sehingga Anda jarang harus memproses lebih dari satu permintaan dalam satu waktu. Namun ini tidak berarti bahwa server kami tidak sibuk: server kami sibuk dengan pekerjaan menerima, menganalisis dan mengompresi pesan baru, mengevaluasi peringatan, mengompresi data lama, dan sebagainya. Oleh karena itu, kami memiliki persediaan prosesor yang cukup signifikan yang dapat digunakan untuk mengeksekusi kueri.
Brute force berfungsi jika Anda memiliki masalah brute (dan banyak force)
Brute force bekerja paling baik pada masalah sederhana dengan loop internal kecil. Seringkali Anda dapat mengoptimalkan loop internal agar berjalan pada kecepatan yang sangat tinggi. Jika kodenya rumit, akan lebih sulit untuk mengoptimalkannya.
Kode pencarian kami awalnya memiliki loop dalam yang cukup besar. Kami menyimpan pesan di halaman dengan resolusi 4K; setiap halaman berisi beberapa pesan (dalam UTF-8) dan metadata untuk setiap pesan. Metadata adalah struktur yang mengkodekan panjang nilai, ID pesan internal, dan bidang lainnya. Siklus pencarian terlihat seperti ini:
Ini adalah versi sederhana dari kode sebenarnya. Namun bahkan di sini, beberapa penempatan objek, salinan data, dan pemanggilan fungsi terlihat. JVM cukup bagus dalam mengoptimalkan pemanggilan fungsi dan mengalokasikan objek sementara, jadi kode ini bekerja lebih baik dari yang seharusnya. Selama pengujian, pelanggan menggunakannya dengan cukup sukses. Namun pada akhirnya kami membawanya ke level berikutnya.
(Anda mungkin bertanya mengapa kami menyimpan pesan dalam format ini dengan halaman 4K, teks dan metadata, daripada bekerja dengan log secara langsung. Ada banyak alasan, yang intinya adalah fakta bahwa secara internal mesin Scalyr lebih seperti database terdistribusi daripada a sistem file. Pencarian teks sering dikombinasikan dengan filter gaya DBMS di margin setelah penguraian log. Kita dapat mencari ribuan log secara bersamaan, dan file teks sederhana tidak cocok untuk manajemen data transaksional, replikasi, dan terdistribusi).
Awalnya, sepertinya kode seperti itu tidak terlalu cocok untuk optimasi brute force. "Pekerjaan nyata" di String.indexOf() bahkan tidak mendominasi profil CPU. Artinya, optimalisasi cara ini saja tidak akan membawa pengaruh yang signifikan.
Kebetulan kami menyimpan metadata di awal setiap halaman, dan teks semua pesan dalam UTF-8 dikemas di ujung lainnya. Memanfaatkan hal ini, kami menulis ulang loop untuk mencari seluruh halaman sekaligus:
Versi ini berfungsi langsung pada tampilan raw byte[] dan mencari semua pesan sekaligus di seluruh halaman 4K.
Ini jauh lebih mudah untuk dioptimalkan dengan metode brute force. Putaran pencarian internal dipanggil secara bersamaan untuk seluruh halaman 4K, bukan secara terpisah pada setiap postingan. Tidak ada penyalinan data, tidak ada alokasi objek. Dan operasi metadata yang lebih kompleks dipanggil hanya jika hasilnya positif, dan tidak pada setiap pesan. Dengan cara ini kami telah menghilangkan banyak overhead, dan sisa beban terkonsentrasi dalam loop pencarian internal kecil, yang sangat cocok untuk pengoptimalan lebih lanjut.
Algoritme pencarian kami yang sebenarnya didasarkan pada . Hal ini mirip dengan algoritma Boyer-Moore, melewatkan kira-kira panjang string pencarian pada setiap langkah. Perbedaan utamanya adalah ia memeriksa dua byte sekaligus untuk meminimalkan kecocokan yang salah.
Implementasi kami memerlukan pembuatan tabel pencarian 64K untuk setiap pencarian, tapi itu tidak seberapa dibandingkan dengan gigabyte data yang kami cari. Loop bagian dalam memproses beberapa gigabyte per detik pada satu inti. Dalam praktiknya, kinerja stabil adalah sekitar 1,25 GB per detik pada setiap inti, dan masih ada ruang untuk perbaikan. Ada kemungkinan untuk menghilangkan beberapa overhead di luar loop dalam, dan kami berencana untuk bereksperimen dengan loop dalam di C, bukan di Java.
Kami menggunakan kekerasan
Kita telah membahas bahwa pencarian log dapat diterapkan "secara kasar", namun seberapa besar "kekuatan" yang kita miliki? Cukup banyak.
1 inti: Jika digunakan dengan benar, satu inti prosesor modern sudah cukup kuat.
8 core: Saat ini kami menjalankan server SSD Amazon hi1.4xlarge dan i2.4xlarge, masing-masing dengan 8 core (16 thread). Seperti disebutkan di atas, inti ini biasanya sibuk dengan operasi latar belakang. Saat pengguna melakukan pencarian, operasi latar belakang ditangguhkan, membebaskan 8 inti untuk pencarian. Pencarian biasanya selesai dalam sepersekian detik, setelah itu pekerjaan latar belakang dilanjutkan (program pembatasan memastikan bahwa rentetan permintaan pencarian tidak mengganggu pekerjaan latar belakang yang penting).
16 core: untuk keandalan, kami mengatur server ke dalam grup master/slave. Setiap master memiliki satu SSD dan satu server EBS di bawah komandonya. Jika server utama mengalami crash, maka server SSD akan segera menggantikan tempatnya. Hampir sepanjang waktu, master dan slave berfungsi dengan baik, sehingga setiap blok data dapat dicari di dua server berbeda (server slave EBS memiliki prosesor yang lemah, jadi kami tidak mempertimbangkannya). Kami membagi tugas di antara mereka, sehingga kami memiliki total 16 core yang tersedia.
Banyak inti: Dalam waktu dekat, kami akan mendistribusikan data ke seluruh server sedemikian rupa sehingga mereka semua berpartisipasi dalam memproses setiap permintaan non-sepele. Setiap inti akan bekerja. [Catatan: kami menerapkan rencana tersebut dan meningkatkan kecepatan pencarian menjadi 1 TB/dtk, lihat catatan di akhir artikel].
Kesederhanaan menjamin keandalan
Keunggulan lain dari metode brute force adalah kinerjanya yang cukup konsisten. Biasanya, penelusuran tidak terlalu sensitif terhadap detail masalah dan kumpulan data (saya rasa itulah mengapa disebut "kasar").
Indeks kata kunci terkadang memberikan hasil yang sangat cepat, dan terkadang tidak. Katakanlah Anda memiliki log sebesar 50 GB dengan istilah 'customer_5987235982' muncul tepat tiga kali. Pencarian untuk istilah ini menghitung tiga lokasi langsung dari indeks dan akan selesai seketika. Namun pencarian wildcard yang kompleks dapat memindai ribuan kata kunci dan memakan waktu lama.
Di sisi lain, penelusuran brute force bekerja dengan kecepatan yang kurang lebih sama untuk kueri apa pun. Mencari kata-kata yang panjang lebih baik, tetapi bahkan mencari satu karakter pun cukup cepat.
Kesederhanaan metode brute force berarti kinerjanya mendekati maksimum teoritis. Ada lebih sedikit opsi untuk kelebihan beban disk yang tidak terduga, pertikaian kunci, pengejaran penunjuk, dan ribuan alasan kegagalan lainnya. Saya baru saja melihat permintaan yang dibuat oleh pengguna Scalyr minggu lalu di server tersibuk kami. Ada 14 permintaan. Tepatnya delapan di antaranya membutuhkan waktu lebih dari satu detik; 000% selesai dalam 99 milidetik (jika Anda belum pernah menggunakan alat analisis log, percayalah: itu cepat).
Performa yang stabil dan andal penting untuk kemudahan penggunaan layanan. Jika lambat secara berkala, pengguna akan menganggapnya tidak dapat diandalkan dan enggan menggunakannya.
Log pencarian dalam tindakan
Berikut adalah animasi singkat yang menunjukkan aksi pencarian Scalyr. Kami memiliki akun demo tempat kami mengimpor setiap acara di setiap repositori Github publik. Dalam demo ini, saya memeriksa data selama seminggu: sekitar 600 MB log mentah.
Video tersebut direkam secara langsung, tanpa persiapan khusus, di desktop saya (sekitar 5000 kilometer dari server). Performa yang akan Anda lihat sebagian besar disebabkan oleh , serta backend yang cepat dan andal. Setiap kali ada jeda tanpa indikator 'loading', saya yang menjeda agar Anda bisa membaca apa yang akan saya tekan.
Sebagai kesimpulan
Saat memproses data dalam jumlah besar, penting untuk memilih algoritma yang baik, namun βbaikβ tidak berarti βmewah.β Pikirkan tentang bagaimana kode Anda akan bekerja dalam praktiknya. Analisis teoretis terhadap algoritme mengabaikan beberapa faktor yang mungkin sangat penting di dunia nyata. Algoritme yang lebih sederhana lebih mudah untuk dioptimalkan dan lebih stabil dalam situasi edge.
Pikirkan juga konteks di mana kode akan dieksekusi. Dalam kasus kami, kami memerlukan server yang cukup kuat untuk mengelola tugas latar belakang. Pengguna relatif jarang melakukan pencarian, sehingga kami dapat meminjam seluruh grup server untuk jangka waktu singkat yang diperlukan untuk menyelesaikan setiap pencarian.
Dengan menggunakan metode brute force, kami menerapkan pencarian yang cepat, andal, dan fleksibel di seluruh kumpulan log. Kami berharap ide-ide ini berguna untuk proyek Anda.
Sunting: Judul dan teks telah diubah dari "Penelusuran dengan kecepatan 20 GB per detik" menjadi "Penelusuran dengan kecepatan 1 TB per detik" untuk mencerminkan peningkatan kinerja selama beberapa tahun terakhir. Peningkatan kecepatan ini terutama disebabkan oleh perubahan jenis dan jumlah server EC2 yang kami siapkan saat ini untuk melayani peningkatan basis pelanggan kami. Akan segera ada perubahan yang akan memberikan peningkatan dramatis dalam efisiensi operasional, dan kami tidak sabar untuk mengumumkannya.
Sumber: www.habr.com