Kod araması neden zor?

 (blog.val.town)
1 puan yazan GN⁺ 2024-04-12 | 1 yorum | WhatsApp'ta paylaş
  • Val Town araması Postgres ILIKE tabanlı alt dize araması olduğu için neredeyse hiç sıralama yapmıyor; çok kelimeli sorgularda da zayıf kaldığından iyileştirme talepleri çok
  • Doğal dil aramasındaki stop word kaldırma, kök bulma ve lemmatizasyon gibi kurallar, koddaki değişken adlarını, fonksiyon adlarını ve token sınırlarını bozabilir
  • Postgres Full Text Search altyapıyı basit tutmayı sağlayabilir; ancak önceki projelerde ölçeklenebilirlik sorunları yaşanmıştı ve Val Town da tek düğümlü Postgres sınırlarını test ediyor
  • Yumuşak lansmanı yapılan v2 arama pg_trgrm tabanlı trigram araması kullanıyor; ancak regex aramasının aksine serbest biçimli sorgularda sıralamayı istenen seviyeye getirmek zor
  • Elasticsearch, Meilisearch, Zoekt ve ParadeDB gibi alternatifler var; fakat ayrı altyapı, operasyon yükü ve barındırma desteği olup olmaması seçimde kısıt olarak kalıyor

Val Town aramasının takıldığı nokta

  • Val Town araması şu anda Postgres’in ILIKE özelliğini kullanıyor
    • Arama terimi kodun içinde geçiyorsa sonuçlarda gösteren bir alt dize araması yöntemi
    • Sıralama neredeyse yok ve çok kelimeli sorgular düzgün desteklenmiyor
  • Daha iyi arama, Val Town’da en çok istenen özelliklerden biri
  • İyileştirme çalışmaları sürüyor, ancak gereksinimlere uyan bir çözüm henüz bulunamadı
  • Şimdiye kadar belirlenen koşullar şöyle
    • Yaygın arama çözümleri doğal dile göre tasarlanmış
    • Kod aramasına ihtiyaç duyan büyük şirketler kendi arama sistemlerine çok zaman ve para yatırıyor
    • Val Town’un halihazırda çok fazla verisi var; bu yüzden iyi ölçeklenen bir çözüm gerekiyor
    • Veritabanını ölçeklemek yerine ayrı bir arama servisi kullanılırsa altyapı ve karmaşıklık açısından ödünleşim önemli hale geliyor

Doğal dil arama kuralları neden koda uymuyor?

  • Tipik tam metin araması (FTS) ayarları, İngilizce gibi doğal dilleri hedefleyen algoritmaları varsayılan olarak sunar
    • Stop word kaldırma: “the”, “it” gibi çok yaygın kelimeleri indekslemeden önce kaldırır
    • Kök bulma: “running” kelimesini “run”a çevirerek “runs” aramasıyla da bulunmasını sağlar
    • Lemmatizasyon: “excellent” aramasının “great” içeren belgeleri de bulması için eşanlamlıları daha yaygın kelimelerle değiştirebilir
  • Aynı kurallar koda uygulandığında anlam kayar
    • TypeScript’te the bir stop word değil, aramak isteyebileceğiniz geçerli bir değişken adı olabilir
    • Koddaki kelime sınırları doğal dilden farklıdır
    • Fonksiyon adlarına kök bulma uygulamak anlamlı sonuçlar vaat etmez
  • Postgres to_tsvector('english', ...), doğal dil cümlelerini indekslerken özgün metni ciddi biçimde değiştirir
    • I am writing this example sentence, 'exampl':5 'sentenc':6 'write':3 gibi dönüştürülür
  • Kodda tokenizasyon sorunu daha belirgin hale gelir
    • function stringifyNumber(a: number): string { return a.toString() }, 'a.tostring':7 'function':1 'number':4 'return':6 'string':5 'stringifynumb':2 gibi indekslenir
    • function gibi kelimeler kalır; a.toString() ise . varsayılan kelime sınırı olmadığı için iki tokene ayrılmaz

Postgres Full Text Search’ün artıları ve eksileri

  • Postgres Full Text Search uzantısını sunar ve Val Town’un barındırma sağlayıcısı Render da bunu destekler
  • Val Town bugüne kadar Postgres’i yoğun biçimde kullandı; Postgres, dokümantasyonu ve barındırma desteği iyi olan bir teknoloji olarak değerlendiriliyor
  • Küçük bir ekip için altyapıyı olabildiğince basit tutmak önemlidir; Postgres ile çözülebiliyorsa Postgres kullanma motivasyonu yüksektir
  • Ancak daha önce FTS kullanılan projelerde performans ve ölçeklenebilirlik sorunları yaşandı
    • Observable sonunda Elasticsearch’e geçti
    • Val Town’un çok sayıda val’i var ve tek düğümlü Postgres kümesinin sınırlarını test ediyor
  • Kod aramasında FTS’nin başarıyla kullanıldığı örnekler bulmak zor olduğundan, ilk seçenek olarak kullanmak yerine yedek plan olarak tutuluyor

pg_trgrm tabanlı v2 arama deneyi

  • Val Town’un yumuşak lansmanını yaptığı v2 arama algoritması Postgres’in pg_trgrm uzantısına dayanıyor
    • pg_trgrm, Postgres’te trigram araması uygular
  • Kod aramasında trigramın zaten başarılı örnekleri var
    • Russ Cox’un 2012 tarihli yazısı, Google Code Search’ün trigram indeksi ve özel regex uygulaması kullandığı örneği ele alır
    • GitHub’ın yeni kod arama sistemi de trigram araması kullanır
    • Sourcegraph, Google’dan devralınan trigram tabanlı bir arama aracına sahiptir
  • Val Town’un Postgres pg_trgrm yaklaşımı, Stephen Gutekanst’ın Postgres tabanlı yerel depo indeksleme yazısından büyük ölçüde etkilendi
  • Uygulama, arama metninin bulunduğu kolona GIN indeksi ve gin_trgm_ops uygular
  • pg_trgrm regex araması için iyi bir çözüm olsa da, Val Town’daki çoğu arama gibi daha serbest sorgulara pek uymaz
    • Arama sıralaması için word_similarity kullanılıyor
    • Algoritmayı makul sıralamaya yaklaştıracak şekilde ayarlamak çok zor

Arama motoru seçenekleri ve operasyonel ödünleşimler

  • Değerlendirilen seçenekler arasında bağımsız arama servisleri ile Postgres uzantıları karışık halde bulunuyor
    • Meilisearch: bağımsız, Rust, 41 bin yıldız
    • Typesense: bağımsız, C++, 17 bin yıldız
    • Zoekt: bağımsız, Go, 406 yıldız
    • ParadeDB: Postgres uzantısı, Rust, 3,2 bin yıldız
    • Sonic: bağımsız, Rust, 19,4 bin yıldız
  • Kod odaklı araçlar mevcut, ancak çoğu kapalı kaynak
    • GitHub araması çok iyi, fakat bu özel bir ekip ve gerçek bir zaman bütçesiyle ortaya çıkmış bir ürün
  • Sourcegraph’ın sürdürdüğü Zoekt fork’u ilginç, ancak çok niş ve büyük bir yeni altyapı yatırımı gerektiriyor
  • Elasticsearch sonunda kaçınılmaz çözüm olabilir
    • Koda özel bir işlem sunmuyor, ancak neredeyse sınırsız özelleştirilebilir
    • Java bellek ayarlamayı öğrenmek, uygulamaya ilk kalıcı disk depolamasını eklemek ve veriler için ek bir doğruluk kaynağını yönetmek yük oluşturuyor
    • Elasticsearch Cloud kullanmak bakım yükünü azaltma olasılığı sunuyor
  • Meilisearch, Elasticsearch alternatifi olarak umut verici görünüyor
    • Rust tabanlı olması cazip
    • Kendi karşılaştırma yazısında ölçeklenebilirlikten çok gecikmeyi vurguluyor gibi; altyapı yükünün daha düşük olup olmayacağı ise net değil
  • ParadeDB Elasticsearch gibi çalışıp “sadece Postgres” olmasıyla çekici
    • Ancak Render’da bu uzantı henüz kullanılamıyor

Küçük bir ekibin arama altyapısı seçerken taşıdığı yük

  • Kod araması, İngilizce aramasından daha zordur
  • Küçük ekiplerin altyapıyı basit tutma, geliştirme ortamı kurulumunu kolaylaştırma ve veriyi aynı yerde tutma motivasyonu vardır
  • Val Town, sürekli bakım gerektiren bir seçeneğe aceleyle bağlanmak istemiyor
  • Orta ve büyük şirketlerde yalnızca arama “servisi” değil, arama “ekibi” olmasının bir nedeni var

İlgili okumalar

1 yorum

 
GN⁺ 2024-04-12
Hacker News görüşleri

  • Sourcegraph'ta çalışıyorum; büyük ölçekli işleme elbette gerekebilir ama bir ürüne ilk kez kod arama ekliyorsanız, en baştan indeksleme ile başlamayın, sınırlarına gelene kadar anlık aramayı öneririm
    Yalnızca ilk N sonucu bulmanız gereken durumlarda tüm veriyi sonuna kadar taramadan da sonuç tamponunu doldurabiliyorsunuz; bu yüzden düşündüğünüzden daha uzun süre idare ediyor. Böyle şeyler yapan biriyle, Val Town tarafındaki insanlarla da memnuniyetle konuşmak isterim

    • İndeks tabanlı aramaya ihtiyaç duyulduğunda, bulduğum en iyi yöntem Zoekt oldu
      Sourcegraph bir süre Zoekt'in bakımını üstlenmişti ve Livegrep ile Hound, indekslemeyi hedeflediğimiz ölçekte çeşitli açılardan zorlanıyordu. Eski ve hantal bir OpenGrok dağıtımından Zoekt'e geçtikten sonra hem indeksleme performansı hem de arama performansı/kullanılabilirliği açısından fark büyüktü. Sourcegraph, Zoekt'in sunduğu kod aramasının üstüne çok daha gelişmiş özellikler ekliyor
    • İndeks olmadan da epey ileri gidilebilmesi şaşırtıcıydı
      Örneğin GritQL(https://github.com/getgrit/gritql) için de hız adına eninde sonunda indeks gerekeceğini hep düşünmüştüm, ama şu ana kadar tamamen anlık aramayla oldukça iyi dayandı
    • Bu yaklaşımı birçok probleme uyguluyorum. Önce en az durum tutan basit yöntemi kullanıyor, ancak hız için belleğe daha fazla yaslanmak gerektiğini kanıtladıktan sonra değiştiriyorum
      Önbellek olmayınca sistemi doğru şekilde sürdürmek çok daha basit oluyor
    • Gerçekten büyük ölçekli ve temsili bir iş yükü ortaya çıktıktan sonra uygun indeksleme yöntemini seçmek çok daha kolaylaşıyor
    • Zaman serisi veritabanı yapan birisi, disk bloklarını sıkıştırılmış halde tutup akış halinde açarak arama yapıyordu
      L2 önbelleğe sığan şeyler gerçekten çok ama çok hızlı çalışıyor

  • Kod arama gerçekten zor ve iyi bir kod arama platformu hayatı çok daha kolaylaştırıyor
    Google'dan ayrılırsam en çok özleyeceğim şey muhtemelen kurum içi kod araması olur. blaze hedefi bulma, guice binding'leri ve diğer her şeyle iş akışına o kadar iyi entegre ki onsuz çalışmayı hayal etmek zor. GitHub aramasını her kullandığımda bunun değerini daha çok anlıyorum; mesele GitHub aramasının kötü olması değil, genel amaçlı bir kod arama platformu yapmanın doğası gereği çok daha zor olması

    • Ayrılırsanız, Google'ın kod arama çalışmasına dayanılarak geliştirilen Livegrep'i kullanabilirsiniz
      Şu anda kişisel olarak kullanmıyorum ama harika ve çoğu ihtiyacı karşılayacak gibi görünüyor. https://github.com/livegrep/livegrep
    • guice binding katmanı özelliği iyi ama arayüz daha iyi olabilir
      Arama kutusundan doğrudan sağlayıcıyı ya da kullanım yerlerini bulabilmek güzel olurdu

  • Temel kod arama becerileri yeni geliştiricilere açıkça pek öğretilmiyor, ama erken dönemde mutlaka edinilmesi gereken temel bir yetkinlik gibi görünüyor
    Önerilen akış, Ctrl+F gibi her yerde çalışan aramayı öğrenmek, ardından ripgrep'e(https://github.com/BurntSushi/ripgrep) geçmek. Bu, isteğe bağlı bir tercih olmaktan çok gerçekten harika ve keşfetmesi kolay bir araç; ayrıca terminali açık tutma gerekliliği de yeni başlayanlar için aslında faydalı. Mümkünse güçlü bir komut satırı düzenleyicisi de öğrenmek iyi olur; eskiden Emacs önerirdim ama artık neredeyse her yerde kurulu gelen temel vim'i öneriyorum. Çünkü aynı pencerede grep yapıp düzenleme yapabiliyorsunuz. Sonrasında grep -r, grep -ri, grep -ril gibi, ripgrep'in varsayılan olarak yaptığı davranışları eski grep ile de öğrenebilir, en sonunda da ripgrep'in sınırlarına çarptığınızda gerçek indeks tabanlı özel kod arama araçlarına geçebilirsiniz

    • VSCode arama özelliği için de ripgrep kullandığından iyi bir başlangıç noktasıdır
    • GitHub, henüz klonlamadığınız depolar dahil, ister açık ister organizasyon depoları olsun, depolar arasında kod aramak için de harika bir araçtır
    • Git deposu ararken, hız dışında ripgrep'in git grep karşısında ne gibi avantajları olduğunu merak ediyorum

  • hound'un(https://github.com/hound-search/hound) anılmamasına şaşırdım
    Bu alandaki açık kaynak çözümler içinde önde gelenlerden biri olduğunu düşünüyordum. Wikimedia örneğini(https://codesearch.wmcloud.org/search/) kullandım ve genel olarak memnunum

  • IDE ve geliştirici araçları yapanların, düzgün bir kod araması yapmak için neden en başından beri derleyici platformunu açmak gerektiğini düşündüğünün sebebi bu
    Çünkü gereken işlerin önemli bir kısmı, sonuçta derleyicinin kullandığı iç temsilleri yeniden kurmakla ilgili. İyi bir kod araması aynı zamanda refactoring desteğinin, otomatik tamamlamanın ve yaygın IDE özelliklerinin temelini oluşturuyor. Elbette bu söylendiği kadar kolay değil; bu yüzden derleyici yapan tarafta araçlar çoğu zaman geri planda kaldı. JetBrains de Kotlin’in ilk dönemlerinde bu hatayı yaptı ve Kotlin 2.0’da artımlı derleme gibi destekleri kolaylaştırmak için bunu kısmen düzeltiyor. Rust topluluğu da birkaç yıl önce IDE dostluğunu artırmaya yönelik büyük bir çaba sırasında aynı içgörüye ulaştı. IBM bunu zamanında Eclipse’te gerçekten doğru yapmıştı ve sonrasında kimse tam olarak yetişemedi. IntelliJ yaklaşık 2–3 basamak daha yavaştı; yani saniyelerle milisaniyeler arasında fark vardı. Eclipse’te, sözdizimi hataları olsa bile kısmen derlenebilen Java için çok hızlı bir artımlı derleyici vardı ve IDE’nin kod temsili bu derleyiciye bağlıydı. Bir yazım hatası ekleyip kodun bir kısmını bozduğunuzda, sorunlu dosyalar tüm kod tabanında anında kırmızı alt çizgiyle işaretleniyordu; yazım hatasını düzelttiğiniz anda da gecikmeden kayboluyordu. Bu, dosyalar ile sözdizimi ağacı arasında bir eşleme olmasını gerektiriyor ve Eclipse bunu artımlı derleyiciye bağlı olduğu için yapabiliyordu. IntelliJ bunu yapamıyor; bu yüzden yeniden derleme yapılana kadar normal/bozuk durumlar konusunda agresif biçimde yanıltabiliyor ve iç durum diskle uyuşmadığında çok sayıda sahte hata gösterebiliyor. Çalıştır dediğinizde birkaç saniyelik derleme gecikmesi oluyor ve ancak o zaman IDE’nin çalıştırılabilir gösterdiği durumun yanlış olduğunu öğreniyorsunuz. Eclipse’te derleyici ile iç durum paylaşıldığı için bunların hepsi anlık ve açıktı. Kusurları ve sinir bozucu hataları çoktu ama o özellik özleniyor

    • Elbette Microsoft’un Roslyn (.NET derleyicisi) bunun istisnası
      https://willspeak.me/2021/11/24/red-green-syntax-trees-an-ov...
      https://ericlippert.com/2012/06/08/red-green-trees/
      Roslyn SDK ile araçlar geliştirdim; gerçekten çok iyiydi
    • Eclipse’in Java için artımlı derleyicisi gerçekten olağanüstü, ama Maven ve Gradle gibi harici build sistemleriyle entegrasyon ve çoklu dil desteği IntelliJ’de daha iyi olduğu için sonunda insanlar oraya geçti
    • Eclipse’te hâlâ anlık ve muğlak olmayan bir deneyim var
      Pek çok insanın başka bir IDE’ye geçmemesinin başlıca nedeni bu

  • GitHub eskiden a.toString() ifadesini iki tokene bölerek “düzeltmiş” gibi görünüyordu ve bu oldukça can sıkıcıydı
    GitHub, IDE benzeri kullanım yeri bulma özelliğini geliştiriyor ama hâlâ kusursuz değil; bu yüzden kaçırılmış kullanımları bulmak için bazen "foo.bar()" gibi bir metin araması yapmak isteyebiliyorsunuz. Ama bu kök indirgeme benzeri davranış yüzünden sonuçlar, foo ve bar’ın ayrı ayrı geçtiği bütün yerleri de bularak şişiyor

  • Zoekt’in bu kadar geçiştirilmesini anlamıyorum
    Tam olarak bu amaç için yapıldı ve diğer seçeneklere göre daha büyük bir yeni altyapı yükü de getirmiyor. Sunucu tek bir binary, indeksleyici de tek bir binary; bundan daha basit olması zor. Elasticsearch’ten daha korkutucu görünmesi için bir sebep yok

  • Son dönemde gördüğüm kod arama yaklaşımları içinde en ilginç olanlardan biri septum: https://github.com/pyjarrett/septum
    Düzgün bir kod araması yapmanın en zor kısmının doğru miktarda çevresel bağlamı getirmek olduğunu düşünüyorum; septum ise bu sorunu dosya düzeyinde çözmeye çalışan bir araç. Ayrıca bahsedilmemesine şaşırdığım bir diğer şey de stack-graphs(https://github.com/github/stack-graphs); bu da kod tabanının tamamındaki sembol ilişkilerini artımlı olarak çözümlemeye çalışıyor. GitHub’un dosyalar arası hassas indekslemesini çalıştırıyor ve kavramsal olarak da sağlam, ancak açık kaynak sürümünü çalıştırmakta zorlandım

  • Oracle’da USER/ALL/DBA_SOURCE görünümleri var ve veritabanına yüklenmiş tüm PL/SQL (SQL/PSM) kodu burada görünüyor
    Bilerek obfuscate edilmediyse her şey düz metin olarak görülebiliyor. Sahip, nesne adı, LINE[NUMBER], TEXT[VARCHAR2(4000)] sütunları var ve kayıtlı kaynak kod üzerinde LIKE ya da regexp_like() kullanılabiliyor. EnterpriseDB bunu Postgres içinde uyguladı mı, yoksa bir eklenti olarak mı sunuluyor merak ediyorum. SQL/PSM’nin büyük kısmı zaten Oracle’dan geldiği için, gayet beklenebilecek bir özellik. https://en.wikipedia.org/wiki/SQL/PSM

  • “GitHub araması harika” denmiş ama gerçekten öyle mi?
    Çoğu durumda neredeyse işe yaramaz geliyor; klonlayıp ardından ripgrep kullanmak çok daha verimli. Sorun belki de aramanın kendisinden çok UX’in korkunç olmasıdır.