Abaikan ElasticSearch, GitHub membina enjin carian dari awal! Bagaimana untuk mencari gudang kod 200 juta?

Pada Disember 2021, GitHub mengeluarkan pratonton teknologi dan menjalankan pengoptimuman menyeluruh untuk menyelesaikan masalah "tiada apa-apa yang boleh ditemui" dalam carian kod GitHub.

Pada November tahun lalu, di Persidangan Pembangun GitHub Universe, pegawai itu mengeluarkan versi beta awam, yang terutamanya menyelesaikan masalah mencari pembangun, masalah membaca dan menavigasi.

Pada persidangan itu, seseorang bertanyakan soalan penting, Apakah prinsip di sebalik penambahbaikan "Carian Kod"?

Baru-baru ini, GitHub menerbitkan blog yang menerangkan secara terperinci prinsip teknikal dan seni bina sistem di sebalik model baharu.

Bina enjin carian GitHub dari awal

Ringkasnya, bahagian belakang enjin carian baharu ialah roda yang tulis semula penyelidik Rust. Dioptimumkan khusus untuk carian kod, nama kod Blackbird .

Pada pandangan pertama, membina enjin carian dari awal mungkin kelihatan seperti keputusan yang membingungkan: Mengapa bermula sekali lagi? Bukankah sudah banyak penyelesaian sumber terbuka di luar sana? Mengapa perlu membazirkan lagi tenaga untuk membina perkara baharu?

Malah, GitHub telah cuba menggunakan penyelesaian sedia ada untuk menyelesaikan masalah carian, tetapi malangnya, produk untuk carian teks universal sukar disesuaikan dengan Carian untuk "kod" . Oleh kerana kelajuan pengindeksan terlalu perlahan, pengalaman pengguna adalah lemah, dan bilangan pelayan yang diperlukan adalah besar dan kos operasi terlalu tinggi.

Walaupun terdapat beberapa projek sumber terbuka yang lebih baharu yang disesuaikan secara khusus untuk carian kod, ia masih tidak sesuai untuk pangkalan kod sebesar GitHub.

Berdasarkan pemerhatian di atas, pembangun GitHub telah menetapkan tiga matlamat dan kesimpulan utama:

1 Pengguna sedang mencari Anda boleh dapatkan pengalaman baharu dalam proses Anda boleh mendapatkan jawapan dengan bertanya beberapa soalan kod dan mencari, menyemak imbas, menavigasi (menavigasi) dan membaca kod secara berulang.

2. Terdapat banyak perbezaan antara carian kod dan carian teks umum.

Pembangun menulis kod untuk difahami oleh mesin, jadi proses carian kod harus mengambil kesempatan daripada struktur dan perkaitan kod dan pengguna boleh mencari tanda baca (mis., operator seperti noktah, kurungan terbuka, dsb. dalam kod);

3. Skala GitHub memang memberikan cabaran yang unik.

Versi lama enjin carian menggunakan Elasticsearch, dan mengambil masa beberapa bulan untuk mengindeks semua kod pada GitHub (kira-kira 800 pada masa itu) Sepuluh ribu perpustakaan kod), tetapi kini bilangan repositori kod telah melebihi 200 juta, dan kod ini tidak statik: pembangun sentiasa menyerahkan, dan kod itu sentiasa berubah, yang sangat mencabar untuk membina enjin carian.

Pada masa ini dalam versi beta, pengguna boleh mencari kira-kira 45 juta pangkalan kod, yang mengandungi 115TB kod dan 15.5 bilion dokumen.

Ringkasnya, barang siap tidak dapat memenuhi keperluan, jadi binalah dari awal.

Cuba Grep?

Apabila mencari, alat yang biasa digunakan ialah "grep". Dengan memasukkan ungkapan, anda boleh memadankan dalam teks, jadi mengapa tidak menggunakan grep sahaja untuk mengatasi masalah carian?

Untuk menjawab soalan ini, anda boleh mengira dahulu tempoh masa yang diperlukan untuk memadankan 115TB kod dengan ripgrep.

Pada mesin dengan CPU Intel 8 teras, ripgrep boleh berjalan dalam 2.769 saat (~0.6 GB/ saat /core) menjalankan pertanyaan ungkapan biasa terhadap fail 13 GB yang dicache dalam memori.

Selepas pengiraan mudah, kita dapati bahawa kaedah ini tidak sesuai untuk data besar semasa: dengan mengandaikan bahawa program carian kod berjalan pada kelompok dengan 32 pelayan, setiap mesin mempunyai 64 Teras, walaupun semua 115TB kod dimasukkan ke dalam ingatan dan semuanya berjalan lancar, ia akan mengambil masa kira-kira 96 ​​saat untuk 2,048 teras CPU menjalankan pertanyaan "satu", dan hanya ada satu pengguna perlu beratur, yang bermaksud bahawa hanya QPS adalah 0.01 hanya boleh digunakan dengan grep

, jadi kekerasan tidak akan berfungsi dan anda hanya boleh membina indeks dahulu.

Indeks carian (indeks carian)

Hanya apabila maklumat yang berkaitan diprakira dalam bentuk indeks boleh enjin carian bertindak balas dengan cepat apabila membuat pertanyaan Secara ringkasnya, Indeks ialah pemetaan nilai kunci Dalam kes indeks terbalik, kunci ialah kata kunci dan nilainya ialah senarai tertib ID dokumen di mana perkataan itu muncul.

Dalam tugas pencarian kod, penyelidik menggunakan jenis indeks songsang khas iaitu indeks ngram.

An ngram ialah jujukan aksara dengan panjang n Contohnya, n = 3 (trigam) bermakna panjang maksimum kekunci hanya boleh 3. Untuk kekunci yang lebih panjang, ia adalah. perlu Potong mengikut panjang 3. Contohnya, had dibahagikan kepada lim, imi, mit dan

nya Apabila melakukan carian, hasil pertanyaan berbilang kunci digabungkan dan rentetan diperoleh selepas digabungkan. Senarai dokumen yang muncul

Soalan seterusnya ialah bagaimana untuk menyiapkan pembinaan indeks dalam masa yang agak munasabah.

Para penyelidik mendapati bahawa: Git menggunakan pencincangan beralamat kandungan, dan sebenarnya terdapat banyak kandungan pendua pada GitHub, jadi penyelidik mencadangkan dua kaedah berikut untuk membina indeks.

1 shard by Git blob object ID menyediakan cara yang baik untuk mengagihkan dokumen secara sama rata antara serpihan dan mengelakkan pertindihan sambil boleh menggunakannya seperti yang diperlukan Kembangkan nombor. daripada serpihan pada bila-bila masa.

2 Modelkan indeks sebagai pepohon dan gunakan pengekodan pembezaan (pengekodan delta) untuk mengurangkan bilangan rangkak dan mengoptimumkan metadata dalam indeks, di mana metadata Data termasuk senarai tempat dokumen muncul (laluan, cawangan dan repositori) serta maklumat tentang objek ini (nama repositori, pemilik, keterlihatan, dll.). Untuk beberapa repositori popular, jumlah metadata boleh menjadi agak besar.

GitHub juga telah mereka bentuk sistem untuk memastikan hasil pertanyaan konsisten dengan kod yang diserahkan.

Jika pengguna mencari pangkalan kod semasa ahli pasukan menolak kod, maka dokumen yang baru diserahkan tidak boleh dimasukkan dalam hasil carian sehingga sistem telah memproses sepenuhnya dokumen yang baru diserahkan , dan Blackbird akan menjadikan pertanyaan komit seks yang konsisten sebagai bahagian teras reka bentuknya.

Blackbird

Berikut ialah gambar rajah seni bina enjin carian Blackbird.

Pertama, Kafka akan menyediakan acara untuk menentukan kandungan indeks, dan kemudian akan terdapat sejumlah besar program crawler Berinteraksi dengan Git, yang juga mempunyai perkhidmatan untuk mengekstrak simbol daripada kod sekali lagi menggunakan Kafka untuk mengindeks setiap serpihan dan mendapatkan dokumen sasaran.

Walaupun sistem hanya bertindak balas kepada peristiwa seperti "git push" untuk mengambil perubahan dan peristiwa serupa, terdapat beberapa kerja tambahan yang diperlukan untuk menelan semua pangkalan kod buat kali pertama.

Ciri utama sistem ini ialah pengoptimuman perintah penyerapan awal untuk memanfaatkan sepenuhnya pengekodan tambahan.

GitHub menggunakan struktur data kebarangkalian baharu untuk mewakili persamaan asas kod, dan dikira daripada traversal berurutan mendatar bagi pepohon rentang minimum graf persamaan asas kod Susunan pengambilan.

Berdasarkan susunan penyerapan yang dioptimumkan, proses pembinaan pokok delta adalah untuk membezakan setiap asas kod daripada asas kod induknya, yang juga bermakna sistem hanya perlu merangkak arus asas kod Unik kepada gumpalan, merangkak melibatkan mendapatkan semula kandungan gumpalan daripada Git, menghuraikannya untuk mengekstrak simbol dan mencipta dokumen yang akan berfungsi sebagai input kepada indeks.

Fail-fail ini kemudiannya diterbitkan ke topik Kafka yang lain, iaitu tempat data dibahagikan antara serpihan. Setiap serpihan menggunakan partition Kafka dalam topik.

Menggunakan Kafka boleh memisahkan indeks daripada rangkak dan pengisihan mesej dalam Kafka juga boleh menjadikan hasil pertanyaan konsisten.

Serpihan pengindeks kemudiannya mencari dokumen ini dan membina indeks: menandakan kandungan, simbol dan laluan untuk membina indeks ngram dan indeks berguna lain (bahasa, pemilik, pangkalan kod, dsb.) dan membuang hasilnya ke cakera .

Akhir sekali, padatkan serpihan dan runtuhkan indeks yang lebih kecil menjadi indeks yang lebih besar, supaya pertanyaan lebih cekap dan pergerakan lebih mudah.

Kitaran hayat pertanyaan

Dengan indeks, penjejakan pertanyaan melalui sistem menjadi mudah Setiap pertanyaan ialah ungkapan biasa, yang boleh ditulis sebagai " /arguments? / org:rails lang:Ruby", yang mencari kod yang ditulis dalam bahasa Ruby oleh organisasi Rails.

Terdapat juga perkhidmatan antara GitHub.com dan shards, yang bertanggungjawab untuk menyelaraskan penerimaan pertanyaan pengguna dan menyebarkan permintaan kepada setiap hos dalam kelompok carian, dan akhirnya menggunakan Redis untuk mengurus ruang cakera (kuota) dan cache beberapa data kawalan akses.

Halaman hadapan menerima pertanyaan pengguna dan menyerahkannya kepada Blackbird, yang kemudian menghuraikan pertanyaan itu ke dalam pokok sintaks abstrak, menulis semula ke dalam ID bahasa kanonik dan Tandakan ayat dengan kebenaran dan skop.

Langkah seterusnya ialah menghantar n permintaan serentak: satu kepada setiap serpihan dalam kelompok carian dan sistem akan Strategi sharding tertentu adalah untuk menghantar permintaan pertanyaan kepada setiap shard dalam kelompok.

Kemudian, lakukan beberapa transformasi pada pertanyaan pada setiap serpihan individu untuk mencari maklumat dalam indeks.

Akhir sekali agregat hasil yang dikembalikan oleh semua serpihan, susun semula mengikut skor, tapis (semak kebenaran sekali lagi) dan kembali ke 100 teratas, kemudian bahagian hadapan GitHub.com melakukan penyerlahan sintaks, penyerlahan istilah, penomboran, dan akhirnya kami boleh membentangkan hasil ke halaman.

Dalam penggunaan sebenar, masa tindak balas p99 bagi satu serpihan adalah kira-kira 100ms Walau bagaimanapun, disebabkan oleh sebab seperti mengagregatkan respons, kebenaran menyemak dan penyerlahan sintaks, jumlah masa tindak balas ialah. lebih lama.

Pertanyaan menduduki satu teras CPU pada pelayan indeks selama 100 milisaat, jadi had atas hos 64 teras ialah kira-kira 640 pertanyaan sesaat. Berbanding dengan kaedah grep (0.01 QPS), kaedah ini boleh dikatakan agak pantas.

Ringkasan

Selepas seni bina sistem yang lengkap diperkenalkan, anda boleh menyemak semula skala masalah.

Saluran paip pengambilan GitHub boleh menerbitkan kira-kira 120,000 dokumen sesaat, jadi ia mengambil masa kira-kira 36 jam untuk memproses kesemua 15.5 bilion dokumen, bagaimanapun, pengindeksan delta boleh mengurangkan Lebih daripada 50% bilangan dokumen yang perlu dirangkak membenarkan keseluruhan proses mengindeks semula keseluruhan korpus dalam masa kira-kira 18 jam.

Membuat beberapa penemuan dalam skala indeks Jumlah kandungan awal ialah 115TB Selepas memadamkan kandungan pendua dan menggunakan pengindeksan tambahan, jumlah kandungan dikurangkan kepada kira-kira 28TB.

Dan indeks itu sendiri hanya 25TB, yang merangkumi bukan sahaja semua indeks (termasuk ngrams), tetapi juga salinan mampat semua kandungan unik, yang juga bermakna jumlah saiz indeks termasuk kandungan adalah lebih kurang Hanya satu perempat daripada saiz data asal!

Atas ialah kandungan terperinci Abaikan ElasticSearch, GitHub membina enjin carian dari awal! Bagaimana untuk mencari gudang kod 200 juta?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!