
HNSW Graf Mimarisi ile Yüksek Boyutlu Vektör Uzayında Hızlı Arama
Vektör veritabanlarında HNSW hiyerarşik küçük dünya graf mimarisi, yaklaşık en yakın komşu (ANN) araması, efConstruction parametresi ve analizi.
Büyük Dil Modelleri (LLM), anlamsal arama ve öneri sistemleri metinleri, görselleri ve kullanıcı profillerini yüzlerce veya binlerce boyuttan oluşan yoğun gömme vektörlerine (dense embedding vectors) dönüştürür. 1536 boyutlu bir vektör uzayında kullanıcı sorgusuna en yakın vektörü bulmak için kaba kuvvet (exact k-NN) yaklaşımı milyonlarca vektör arasında mesafe hesaplamayı gerektirir ve saniyeler sürer. Vektör veritabanlarının (pgvector, Pinecone, Milvus, Qdrant) kalbinde yer alan Hiyerarşik Gezilebilir Küçük Dünya (Hierarchical Navigable Small World - HNSW) graf mimarisi, yaklaşık en yakın komşu (ANN) aramasını logaritmik karmaşıklığa indirerek milisaniyelik yanıtlar üretir.
Kapsam Notu: Bu teknik analiz Malkov ve Yashunin'in 2016 HNSW algoritması, pgvector uygulaması ve vektör graf indeksleme parametreleri dikkate alınarak hazırlanmıştır.
Küçük Dünya (Small World) Grafları ve Skip-List Analojisi
HNSW mimarisini kavramak için tek boyutlu bağlı listeleri hızlandıran Skip-List veri yapısını hatırlamak gerekir. Skip-List'te üst katmanlar seyrek elemanlar içerir ve arama sırasında büyük adımlarla hedefe yaklaşmayı sağlar.
Yura Malkov ve Dmitry Yashunin bu fikri çok boyutlu metrik uzaylara uyarlayarak çok katmanlı bir graf hiyerarşisi inşa etmiştir:
Katman 2 (Seyrek Graf): [Düğüm A] ---------------------------> [Düğüm B]
| |
Katman 1 (Orta Graf) : [Düğüm A] ------------> [Düğüm C] ---> [Düğüm B]
| | |
Katman 0 (Taban Graf) : [Düğüm A] <-> [Düğüm D] <-> [Düğüm C] <-> [Düğüm B]
(Tüm veri noktaları burada yoğun bağlıdır)
- Katman 2 (Üst Katmanlar): Çok az sayıda düğüm ve uzun mesafeli bağlantılar içerir. Uzayda otoyol görevi görür.
- Katman 0 (Zemin Katman): Kümedeki tüm vektörleri barındırır ve yalnızca yakın komşuluk bağlantılarına sahiptir. Yerel sokak haritası gibidir.
Arama Algoritması: Açgözlü Arama (Greedy Routing)
Bir sorgu vektörü ($q$) geldiğinde arama işlemi en üst katmandaki giriş noktasından (entry point) başlar:
- Açgözlü Gezinme: Algoritma mevcut düğümün komşularını inceler. Sorgu vektörüne mevcut düğümden daha yakın bir komşu bulduğu sürece o yöne doğru sıçrar.
- Yerel Minimuma Ulaşma: Mevcut katmanda sorguya daha yakın bir komşu kalmadığında bir alt katmana inilir.
- Taban Katmanda İnce Arama: En alt katmanda (Katman 0) belirlenen aday havuzu (
efSearch) genişliğinde taranarak en yakın K adet komşu tespit edilir.
Bu çok katmanlı sıçrama mekanizması arama karmaşıklığını $O(N)$ seviyesinden $O(\log N)$ seviyesine düşürür.
HNSW İnşa Parametreleri: M, efConstruction ve efSearch
HNSW grafının bellek tüketimini ve arama doğruluğunu (recall) belirleyen üç kritik parametre vardır:
1. M (Maksimum Komşu Sayısı)
Her bir düğümün bağlanabileceği maksimum kenar sayısıdır (Katman 0 için genellikle $2M$ kullanılır).
- Tipik Değerler: 16, 32 veya 64.
Marttıkça graf bağlantıları güçlenir, yüksek boyutlu uzaylarda doğruluk artar. Ancak bellek tüketimi ve indeks inşa süresi katlanır.
2. efConstruction (İnşa Sırasındaki Aday Havuzu Boyutu)
Yeni bir vektör grafa eklenirken en uygun komşuları bulmak için taranan dinamik listenin boyutudur.
- Tipik Değerler: 64, 128, 200.
- Yüksek değerler daha kusursuz bir graf örgüsü kurar ve arama başarısını artırır. İndeksleme süresini uzatır.
3. efSearch (Sorgu Sırasındaki Dinamik Liste Boyutu)
Sorgu anında bellekte tutulan en yakın adayların sayısıdır.
- Tipik Değerler: 40, 100.
efSearcharttıkça sorgunun doğru komşuları bulma oranı (%99 recall) yükselir ancak sorgu gecikmesi (latency) birkaç milisaniye artar.
-- pgvector üzerinde HNSW indeksi oluşturma
CREATE INDEX idx_belgeler_vektor ON belgeler
USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 128)
Bellek Duvarı (RAM Tüketimi)
HNSW graf mimarisinin en büyük bedeli bellek açlığıdır. Standart B-Tree veya ters dizinlerin aksine HNSW grafının yüksek verimle çalışması için tüm graf düğümlerinin ve kenar işaretçilerinin RAM üzerinde yaşaması gerekir.
1 milyon adet 1536 boyutlu float32 vektör yaklaşık 6 GB ham veri tutarken, HNSW graf bağlantıları ile birlikte indeks boyutu 10 ila 15 GB RAM gerektirebilir. Bellek yetersiz kaldığında ve graf sayfaları disk takasına (swap) düştüğünde arama süresi mikrosaniyelerden saniyelere fırlar.
Yazıyı Değerlendir
0 tepkiFikirlerinizi tek tıkla paylaşarak geri bildirim bırakın.
Ali Purtaş
@alipurtas • Hey, This is Ali!
Kendi halinde yazılım geliştiren bir öğrenci. Sistemler kuruyor, deniyor, bozuyor ve öğrendiği gerçek çözümleri burada belgeliyor.
Konu Kümesi & Önerilen Yazılar
Redis Pub/Sub ile L1/L2 Çok Katmanlı Önbellek Geçersizleştirme Ağı
Süreç içi yerel RAM (L1) ile merkezi Redis (L2) katmanlarını senkron tutan Pub/Sub tabanlı geçersizleştirme ve istemci önbellekleme mimarisi.
Önbellek İzdihamı ve XFetch Probabilistik Erken Yenileme Algoritması
Önbellek izdihamı (cache stampede) krizlerini önleyen XFetch olasılıksal erken yenileme algoritması ve tekil uçuş (singleflight) desen analizi.
Write-Behind Önbellekleme ve Veritabanı Toplu Yazma Yükü Mimarisi
Write-behind önbellekleme ile yazma gecikmesini düşürme, toplu veritabanı yazımları, veri kaybı riskleri ve çöküş kurtarma mimari rehberi.
Tartışma & Yorumlar
0Tartışmaya katılmak ve soru sormak için oturum açmalısınız.
Giriş Yap