Mengapa pencarian kode itu sulit

 (blog.val.town)
1 poin oleh GN⁺ 2024-04-12 | 1 komentar | Bagikan ke WhatsApp
  • Pencarian Val Town saat ini adalah pencarian substring berbasis Postgres ILIKE, sehingga hampir tidak ada pemeringkatan dan juga lemah untuk kueri multi-kata, sehingga banyak permintaan perbaikan
  • Aturan pencarian bahasa alami seperti penghapusan stopword, stemming, dan lemmatisasi dapat merusak nama variabel, nama fungsi, dan batas token dalam kode
  • Postgres Full Text Search dapat menjaga infrastruktur tetap sederhana, tetapi pada proyek sebelumnya ada masalah skalabilitas, dan Val Town juga sedang menguji batas Postgres node tunggal
  • Pencarian v2 yang diluncurkan secara soft menggunakan pencarian trigram berbasis pg_trgrm, tetapi tidak seperti pencarian regex, sulit menyesuaikan pemeringkatan kueri bentuk bebas ke tingkat yang diinginkan
  • Ada alternatif seperti Elasticsearch, Meilisearch, Zoekt, dan ParadeDB, tetapi infrastruktur terpisah, beban operasional, dan ketersediaan dukungan hosting tetap menjadi kendala dalam pemilihan

Titik macet pencarian Val Town

  • Pencarian Val Town saat ini menggunakan ILIKE dari Postgres
    • Ini adalah metode pencarian substring: jika istilah pencarian terdapat di dalam kode, hasilnya akan muncul
    • Hampir tidak ada pemeringkatan, dan kueri multi-kata tidak didukung dengan baik
  • Pencarian yang lebih baik adalah salah satu fitur yang paling banyak diminta di Val Town
  • Pekerjaan perbaikan sedang berlangsung, tetapi belum ditemukan solusi yang sesuai dengan kebutuhan
  • Sejauh ini, syarat-syarat yang telah teridentifikasi adalah sebagai berikut
    • Solusi pencarian arus utama dirancang untuk bahasa alami
    • Perusahaan besar yang membutuhkan pencarian kode menginvestasikan banyak waktu dan biaya ke sistem pencarian buatan sendiri
    • Val Town sudah memiliki banyak data, sehingga dibutuhkan solusi yang dapat diskalakan dengan baik
    • Jika menggunakan layanan pencarian terpisah alih-alih penskalaan database, kompromi dari sisi infrastruktur dan kompleksitas menjadi penting

Mengapa aturan pencarian bahasa alami tidak cocok untuk kode

  • Konfigurasi full-text search (FTS) pada umumnya menyediakan algoritme bawaan yang menargetkan bahasa alami seperti bahasa Inggris
    • Penghapusan stopword: kata yang terlalu umum seperti “the” atau “it” dihapus sebelum pengindeksan
    • Stemming: “running” diubah menjadi “run” agar tetap bisa ditemukan saat mencari “runs”
    • Lemmatisasi: pencarian “excellent” dapat juga menemukan dokumen yang berisi “great” dengan mengganti sinonim ke kata yang lebih umum
  • Jika aturan yang sama diterapkan ke kode, maknanya menjadi meleset
    • Dalam TypeScript, the bukan stopword, melainkan bisa jadi nama variabel yang valid yang memang ingin dicari
    • Batas kata dalam kode berbeda dari bahasa alami
    • Sulit mengharapkan hasil yang bermakna jika stemming diterapkan ke nama fungsi
  • Postgres to_tsvector('english', ...) sangat mengubah teks asli saat mengindeks kalimat bahasa alami
    • I am writing this example sentence diubah menjadi seperti 'exampl':5 'sentenc':6 'write':3
  • Dalam kode, masalah tokenisasi terlihat lebih jelas
    • function stringifyNumber(a: number): string { return a.toString() } diindeks menjadi seperti 'a.tostring':7 'function':1 'number':4 'return':6 'string':5 'stringifynumb':2
    • Kata seperti function tetap ada, tetapi a.toString() tidak terpecah menjadi dua token karena . bukan batas kata bawaan

Kelebihan dan kekurangan Postgres Full Text Search

  • Postgres menyediakan ekstensi Full Text Search, dan penyedia hosting Val Town, Render, juga mendukungnya
  • Selama ini Val Town telah banyak memanfaatkan Postgres, dan Postgres dinilai sebagai teknologi dengan dokumentasi dan dukungan hosting yang baik
  • Bagi tim kecil, menjaga infrastruktur sesederhana mungkin itu penting, sehingga ada dorongan kuat untuk memakai Postgres jika masalahnya bisa diselesaikan di sana
  • Namun, proyek-proyek sebelumnya yang menggunakan FTS mengalami masalah performa dan skalabilitas
    • Observable pada akhirnya berpindah ke Elasticsearch
    • Val Town memiliki banyak vals dan sedang menguji batas cluster Postgres node tunggal
  • Sulit menemukan contoh penggunaan FTS yang sukses untuk pencarian kode, sehingga ini lebih dibiarkan sebagai opsi cadangan daripada pilihan pertama

Eksperimen pencarian v2 berbasis pg_trgrm

  • Algoritme pencarian v2 yang diluncurkan secara soft oleh Val Town didasarkan pada pg_trgrm dari Postgres
    • pg_trgrm mengimplementasikan pencarian trigram di Postgres
  • Trigram sudah punya contoh keberhasilan dalam pencarian kode
    • Tulisan Russ Cox tahun 2012 membahas kasus Google Code Search yang memakai indeks trigram dan implementasi regex khusus
    • Sistem pencarian kode baru GitHub juga menggunakan pencarian trigram
    • Sourcegraph memiliki alat pencarian berbasis trigram yang diwarisi dari Google
  • Pendekatan Postgres pg_trgrm milik Val Town banyak dipengaruhi oleh tulisan Stephen Gutekanst tentang pengindeksan repositori lokal berbasis Postgres
  • Implementasinya menerapkan indeks GIN dan gin_trgm_ops pada kolom yang berisi teks pencarian
  • pg_trgrm adalah solusi yang baik untuk pencarian regex, tetapi kurang cocok untuk kueri yang lebih bebas seperti kebanyakan pencarian di Val Town
    • Untuk pemeringkatan pencarian, saat ini digunakan word_similarity
    • Sangat sulit menyetel algoritme agar mendekati pemeringkatan yang masuk akal

Opsi mesin pencari dan kompromi operasional

  • Yang ditinjau mencakup campuran layanan pencarian standalone dan ekstensi Postgres
    • Meilisearch: standalone, Rust, 41k bintang
    • Typesense: standalone, C++, 17k bintang
    • Zoekt: standalone, Go, 406 bintang
    • ParadeDB: ekstensi Postgres, Rust, 3.2k bintang
    • Sonic: standalone, Rust, 19.4k bintang
  • Ada alat khusus kode, tetapi kebanyakan bersifat tertutup
    • Pencarian GitHub sangat unggul, tetapi itu adalah hasil dari tim khusus dan alokasi waktu nyata
  • Fork Zoekt yang dipelihara Sourcegraph menarik, tetapi sangat niche dan membutuhkan investasi infrastruktur baru yang besar
  • Elasticsearch pada akhirnya bisa menjadi solusi yang tak terhindarkan
    • Tidak punya penanganan khusus untuk kode, tetapi hampir tanpa batas dalam hal kustomisasi
    • Mempelajari tuning memori Java, memperkenalkan persistent disk storage pertama ke aplikasi, dan mengelola sumber kebenaran data tambahan menjadi beban tersendiri
    • Menggunakan Elasticsearch Cloud bisa mengurangi beban pemeliharaan
  • Meilisearch tampak menjanjikan sebagai alternatif Elasticsearch
    • Menarik karena berbasis Rust
    • Dalam tulisan perbandingannya sendiri, tampaknya lebih menekankan latensi daripada skalabilitas, dan belum jelas apakah beban infrastrukturnya benar-benar lebih rendah
  • ParadeDB menarik karena bekerja seperti Elasticsearch tetapi tetap “hanya Postgres”
    • Namun, ekstensi itu belum bisa digunakan di Render

Beban saat tim kecil memilih infrastruktur pencarian

  • Pencarian kode lebih sulit daripada pencarian bahasa Inggris
  • Tim kecil punya dorongan untuk menjaga infrastruktur tetap sederhana, memudahkan setup lingkungan pengembangan, dan menyimpan data di tempat yang sama
  • Val Town tidak ingin terburu-buru terikat pada opsi yang membutuhkan pengelolaan berkelanjutan
  • Ada alasan mengapa di perusahaan menengah dan besar bukan hanya ada “layanan” pencarian, tetapi juga “tim” pencarian

Bacaan terkait

1 komentar

 
GN⁺ 2024-04-12
Pendapat Hacker News

  • Saya di Sourcegraph, dan pemrosesan skala besar tentu saja diperlukan, tetapi jika Anda baru pertama kali memasukkan pencarian kode ke dalam produk, saya menyarankan pencarian langsung sampai batasnya terasa, bukan memulai dari indeks sejak awal
    Jika Anda hanya perlu menemukan N hasil pertama, Anda tidak perlu menelusuri semuanya sampai akhir untuk mengisi buffer hasil, jadi pendekatan ini bertahan lebih lama daripada yang dikira. Saya juga dengan senang hati ingin berbicara dengan orang-orang yang membuat hal seperti ini, juga orang-orang di Val Town

    • Jika pencarian terindeks menjadi perlu, Zoekt adalah cara terbaik yang saya temukan
      Sourcegraph dulu mengambil alih pemeliharaan Zoekt, dan Livegrep serta Hound kewalahan dalam berbagai aspek pada skala yang ingin kami indeks. Setelah pindah dari deployment OpenGrok lama yang sudah reyot ke Zoekt, perbedaannya besar baik dalam performa pengindeksan maupun performa/kegunaan pencarian. Sourcegraph menambahkan fitur-fitur yang jauh lebih canggih di atas pencarian kode yang disediakan Zoekt
    • Saya terkejut bahwa kita bisa melangkah cukup jauh tanpa indeks
      Misalnya, saya selalu berpikir GritQL(https://github.com/getgrit/gritql) pada akhirnya akan membutuhkan indeks demi kecepatan, tetapi sejauh ini semuanya masih cukup bertahan hanya dengan pencarian langsung
    • Saya menerapkan pendekatan ini pada berbagai masalah. Saya cenderung memulai dari cara sederhana dengan state sesedikit mungkin, lalu baru mengubahnya setelah terbukti perlu condong ke memori demi kecepatan
      Tanpa cache, jauh lebih sederhana untuk menjaganya tetap benar
    • Setelah ada beban kerja nyata yang berskala dan representatif, barulah jauh lebih mudah memilih metode pengindeksan yang tepat
    • Seseorang yang pernah membuat database temporal menyimpan blok disk dalam keadaan terkompresi, lalu mendekompresinya secara streaming saat mencari
      Hal-hal yang masuk ke cache L2 benar-benar berjalan sangat cepat

  • Pencarian kode memang sangat sulit, dan platform pencarian kode yang bagus membuat hidup jauh lebih mudah
    Jika saya meninggalkan Google, pencarian kode internal mungkin akan menjadi hal yang paling saya rindukan. Karena terintegrasi begitu baik dengan semua alur kerja seperti mencari target blaze, binding guice, dan sebagainya, sulit membayangkan bekerja tanpanya. Setiap kali memakai pencarian GitHub, saya makin merasakan nilainya; bukan karena pencarian GitHub buruk, melainkan karena membuat platform pencarian kode serbaguna memang secara inheren jauh lebih sulit

    • Jika Anda keluar, Anda bisa memakai Livegrep, yang dibuat berdasarkan pekerjaan pencarian kode Google
      Saya pribadi tidak sedang memakainya sekarang, tetapi itu bagus dan sepertinya akan memenuhi sebagian besar kebutuhan. https://github.com/livegrep/livegrep
    • Fitur hierarki binding guice bagus, tetapi UI-nya masih bisa lebih baik
      Akan menyenangkan jika bisa langsung menemukan provider atau lokasi penggunaan dari kotak pencarian

  • Teknik pencarian kode dasar tidak secara eksplisit diajarkan dengan baik kepada developer baru, tetapi tampaknya merupakan kemampuan inti yang harus dikuasai sejak awal
    Alur yang saya rekomendasikan adalah mempelajari pencarian yang tersedia di mana-mana seperti Ctrl+F, lalu beralih ke ripgrep(https://github.com/BurntSushi/ripgrep). Ini bukan sekadar opsi, melainkan alat yang benar-benar bagus dan mudah ditemukan, dan keharusan membuka terminal justru baik untuk pemula. Jika memungkinkan, ada baiknya juga mempelajari satu editor command-line yang kuat; dulu saya akan merekomendasikan Emacs, tetapi sekarang saya merekomendasikan versi dasar vim yang terpasang hampir di mana-mana, karena Anda bisa melakukan grep dan mengedit di jendela yang sama. Berikutnya, pelajari juga perilaku yang secara default dilakukan ripgrep dengan grep lama, seperti grep -r, grep -ri, grep -ril, dan terakhir, ketika Anda terbentur batas ripgrep, barulah beralih ke alat pencarian kode khusus berbasis indeks yang sebenarnya

    • Fitur pencarian VSCode juga menggunakan ripgrep, jadi itu titik awal yang bagus
    • GitHub juga alat yang sangat baik untuk mencari kode lintas repositori, baik repositori publik maupun repositori organisasi, bahkan untuk repositori yang belum Anda clone
    • Saya penasaran, saat mencari di repositori Git, selain kecepatan, apa keunggulan ripgrep dibanding git grep

  • Saya terkejut hound(https://github.com/hound-search/hound) tidak disebut
    Saya mengira itu salah satu solusi open source terdepan di bidang ini. Saya sudah memakai instance Wikimedia(https://codesearch.wmcloud.org/search/) dan secara umum puas

  • Inilah alasan mengapa orang-orang yang membuat IDE dan alat pengembang sejak lama berpendapat bahwa untuk melakukan pencarian kode yang benar, mereka harus membuka platform compiler
    Karena sebagian besar pekerjaan yang diperlukan pada akhirnya adalah merekonstruksi representasi internal yang digunakan compiler. Pencarian kode yang baik juga menjadi fondasi untuk dukungan refactoring, autocomplete, dan fitur-fitur IDE umum. Tentu saja, ini tidak semudah kedengarannya; di pihak pembuat compiler, alat sering kali menjadi prioritas belakangan, dan JetBrains juga melakukan kesalahan ini pada masa awal Kotlin, lalu kini sedang memperbaiki sebagian di Kotlin 2.0 agar dukungan seperti incremental compilation lebih mudah. Komunitas Rust juga mendapatkan wawasan yang sama beberapa tahun lalu saat melakukan upaya besar untuk meningkatkan keramahan terhadap IDE. IBM dahulu berhasil melakukannya dengan benar di Eclipse, dan sejak itu belum banyak yang mampu menyusul. IntelliJ sekitar 2–3 digit lebih lambat, sehingga bedanya antara hitungan detik dan milidetik. Eclipse punya incremental compiler yang sangat cepat untuk Java, yang tetap dapat mengompilasi sebagian meski ada kesalahan sintaks, dan representasi kode di IDE terhubung ke compiler itu. Jika Anda memasukkan typo sehingga merusak sebagian kode, file-file yang bermasalah di seluruh codebase langsung ditandai garis bawah merah, dan begitu typo diperbaiki, tanda itu hilang tanpa jeda. Ini hanya mungkin jika ada pemetaan antara file dan syntax tree, dan Eclipse bisa melakukannya karena terhubung ke incremental compiler. IntelliJ tidak bisa melakukan ini, sehingga sampai rebuild dilakukan, ia kadang secara aktif berpura-pura soal status valid/tidak valid, dan jika state internalnya melenceng dari disk, ia menampilkan banyak error palsu. Saat dijalankan, ada jeda kompilasi beberapa detik, dan baru saat itu kadang Anda tahu bahwa status yang ditampilkan IDE sebagai bisa dijalankan ternyata keliru. Di Eclipse, karena compiler dan state internal berbagi informasi, semua ini instan dan jelas. Memang ada banyak kekurangan dan bug yang menjengkelkan, tetapi fitur itu membuat rindu

    • Tentu saja, Roslyn milik Microsoft (compiler .NET) adalah pengecualian
      https://willspeak.me/2021/11/24/red-green-syntax-trees-an-ov...
      https://ericlippert.com/2012/06/08/red-green-trees/
      Saya pernah membuat alat dengan Roslyn SDK, dan rasanya benar-benar bagus
    • Incremental compiler Java di Eclipse memang luar biasa, tetapi pada akhirnya saya pindah ke IntelliJ karena integrasinya dengan sistem build eksternal seperti Maven dan Gradle serta dukungan banyak bahasanya lebih baik
    • Di Eclipse, semuanya masih instan dan tidak ambigu
      Ini alasan utama banyak orang tidak pindah ke IDE lain

  • Sepertinya GitHub dulu pernah “memperbaiki” sesuatu dengan memecah a.toString() menjadi dua token, dan itu cukup menyebalkan
    GitHub memang sedang memperkuat pencarian lokasi penggunaan seperti IDE, tetapi belum sempurna, jadi kadang saya ingin melakukan pencarian teks seperti "foo.bar()" untuk menemukan penggunaan yang terlewat. Namun karena perilaku stemming seperti ini, hasilnya membengkak karena ikut menemukan semua tempat yang menyebut foo dan bar secara terpisah

  • Saya tidak mengerti mengapa Zoekt dipandang sepintas begitu saja
    Ia dibuat persis untuk tujuan ini, dan bukan beban infrastruktur baru yang lebih besar dibanding opsi lain. Servernya satu binary, indexer-nya juga satu binary; sulit membayangkan yang lebih sederhana dari ini. Saya tidak melihat alasan untuk lebih takut pada Zoekt dibanding Elasticsearch

  • Salah satu pendekatan pencarian kode paling menarik yang belakangan saya lihat adalah septum: https://github.com/pyjarrett/septum
    Menurut saya, bagian tersulit dalam membuat pencarian kode yang benar adalah mengambil konteks sekitar dalam jumlah yang tepat, dan septum adalah alat yang mencoba menyelesaikan masalah ini pada level file. Hal lain yang mengejutkan tidak disebut adalah stack-graphs(https://github.com/github/stack-graphs), yang berupaya menafsirkan relasi simbol di seluruh codebase secara bertahap. Ini menggerakkan indexing presisi lintas-file milik GitHub dan secara konseptual juga masuk akal, tetapi saya kesulitan menjalankan versi open source-nya

  • Oracle memiliki view USER/ALL/DBA_SOURCE, dan semua kode PL/SQL(SQL/PSM) yang dimuat ke database muncul di sana
    Jika tidak sengaja di-obfuscate, semuanya terlihat sebagai plaintext. Ada kolom owner, nama objek, LINE[NUMBER], TEXT[VARCHAR2(4000)], dan Anda bisa memakai LIKE atau regexp_like() pada source code yang tersimpan. Saya penasaran apakah EnterpriseDB mengimplementasikan ini di dalam Postgres, atau menyediakannya sebagai ekstensi. Karena sebagian besar SQL/PSM memang berasal dari Oracle, fitur seperti ini wajar diharapkan. https://en.wikipedia.org/wiki/SQL/PSM

  • Katanya “pencarian GitHub itu hebat”, tetapi benarkah begitu?
    Dalam kebanyakan kasus, rasanya hampir tidak berguna, dan jauh lebih efisien untuk clone lalu memakai ripgrep. Mungkin masalahnya bukan pencarian sebenarnya, melainkan UX-nya yang buruk