[2009 WSDM] Büyük Ölçekli Bilgi Erişim Sistemleri Kurmanın Zorlukları

Bilgi erişim sistemlerinin başlıca boyutları ve trade-off'ları

• Sistem tasarlanırken aşağıdaki unsurlar arasındaki mühendislik trade-off'ları dengeli biçimde değerlendirilmelidir.
  • İndekslenen belge sayısı
  • Saniye başına işlenen sorgu sayısı (QPS)
  • İndeks tazeliği/güncelleme hızı
  • Sorgu gecikmesi (latency)
  • Her belge için saklanan bilgi miktarı
  • Skor hesaplama/arama algoritmasının karmaşıklığı/maliyeti
• Mühendislik zorluğu, bu parametrelerin çarpımıyla orantılı olma eğilimindedir.
• Tüm bu unsurlar toplam performansı ve maliyet başına performansı ($ başına performans) etkiler.

Sistem ölçeğindeki değişim (1999 vs 2009)

• Son 10 yılda sistem ölçeği ve performans gereksinimleri dramatik biçimde değişti.
  • # belge: ~70 milyon → milyarlarca (~100 kat artış)
  • günlük işlenen sorgu sayısı: (~1000 kat artış)
  • belge başına indeks bilgisi: (~3 kat artış)
  • güncelleme gecikmesi: aylar → dakikalar (~10000 kat azalma)
  • ortalama sorgu gecikmesi: <1 saniye → <0.2 saniye (~5 kat azalma)
  • sistem kaynakları: daha fazla makine * daha hızlı makine (~1000 kat artış)
• Bu parametreler sürekli, bazen de birkaç basamak birden değiştiği için sistem tasarımı da durmadan evrilmek zorundadır.
  • Belirli bir anda (X) uygun olan bir tasarım, 10 kat ya da 100 kat ölçekte son derece yanlış bir tasarım olabilir. (Bu nedenle yaklaşık 10 kat büyümeyi göz önünde bulundurarak tasarlamak gerekir; ancak 100 kat olmadan önce yeniden yazım planlanmalıdır.)
  • Son 10 yılda 7 büyük yeniden yapılanma oldu.

İlk sistem mimarisi (1997-1999)

• Araştırma projesi aşaması (1997):
  • Frontend web sunucusu sorguları alır ve indeks sunucuları ile belge sunucularına dağıtık işleme istekleri gönderir
  • İndeks sunucuları: belge ID'si (docid) temelinde sharding
  • Belge sunucuları: belge ID'si (docid) temelinde sharding
• Temel ilkeler:
  • Belgelere tamsayı ID'ler (docids) atanır (önemli/yüksek kaliteli belgelere daha küçük ID'ler verilir)
  • İndeks sunucuları: (sorgu) → sıralanmış (skor, docid, ...) listesi döndürür. docid tabanlı sharding, kapasite için replication. Maliyet O(#sorgu * indeksteki #belge).
  • Belge sunucuları: (docid, sorgu) → (başlık, snippet) üretir. docid → disk üzerindeki tam belge eşlemesi. docid tabanlı sharding. Maliyet O(#sorgu).
• Serving sistemi (1999):
  • Araştırma projesi yapısına cache sunucuları ve reklam sistemi entegrasyonu eklendi
  • İndeks/belge sunucusu shard kopyaları (replicas) işletildi
  • Caching: Hem indeks sonuçları hem de belge snippet'leri cache'lendi. Cache hit oranı %30-60. Performans artışı ve sorgu gecikmesinin azalmasına büyük katkı sağladı. (Ancak indeks güncellemesi/cache flush sırasında büyük gecikme spike'ları oluşabileceğine dikkat edilmeli.)

İndeks partitioning stratejileri

• Belgeye göre (By doc): Her shard, belgelerin bir kısmının indeksini tutar (Google'ın seçimi)
  • Avantajlar: Shard başına bağımsız sorgu işleme, ek belge bazlı bilginin tutulmasının kolay olması, daha az ağ trafiği (istek/yanıt)
  • Dezavantajlar: Tüm shard'ların sorguyu işlemesi gerekir, K kelimelik bir sorgu için N shard üzerinde O(K*N) disk seek gerekir
• Kelimeye göre (By word): Her shard, tüm belgeler için kelimelerin bir kısmının indeksini tutar
  • Avantajlar: K kelimelik sorguyu en fazla K shard işler, O(K) disk seek
  • Dezavantajlar: Çok daha yüksek ağ bant genişliği gerekir (eşleşen belgelerin kelime bazlı bilgileri tek yerde toplanmalıdır), belge bazlı bilgiyi korumak zordur

İlk crawling ve indexing (1998-1999)

• Crawling:
  • Basit bir batch crawling sistemi: başlangıç URL listesi → sayfaları crawl et → linkleri çıkarıp kuyruğa ekle → yeterli sayfa toplanınca dur
  • Dikkat edilmesi gerekenler: Belirli siteleri aşırı yüklememek, henüz crawl edilmemiş sayfaların önceliğini belirlemek (ör. PageRank), crawl edilmemiş URL kuyruğunu verimli yönetmek, makine arızalarını ele almak
• Indexing:
  • Basit bir batch indexing sistemi: basit Unix araçları tabanlı
  • Sorunlar: Checkpoint olmaması nedeniyle makine arızalarında süreç çok sancılıydı; kaynak veride checksum olmaması donanım bit hatalarına yol açtı (erken dönem makinelerde ECC/parity olmaması bunu kötüleştirdi, "çoğunlukla sıralı" problemi), "düşmanca bellek ve programlama" deneyimi
  • Çözüm: Küçük kayıt checksum'ları saklayan ve bozuk kayıtları atlayıp yeniden senkronize olabilen dosya soyutlamaları geliştirildi

İndeks güncelleme yöntemi (1998-1999)

• Periyot: Yaklaşık ayda bir
• Süreç:
  1. Trafiğin düşük olduğu saat beklenir
  2. Bazı kopyalar çevrimdışı alınır
  3. Yeni indeks çevrimdışı kopyalara kopyalanır
  4. Güncellenmiş indeksi işaret eden yeni frontend başlatılır ve trafiğin bir kısmını işler
• İndeks sunucusu disk kullanım stratejisi:
  • Diskin dış kısmı (outer part) daha yüksek bant genişliği sağlar
  1. (Eski indeks hizmet verirken) yeni indeks diskin iç kısmına (inner half) kopyalanır
  2. Yeni indeksi kullanacak şekilde yeniden başlatılır
  3. Eski indeks silinir
  4. Yeni indeks daha hızlı dış bölüme (faster half) yeniden kopyalanır
  5. İç bölüme kopyalanmış ilk yeni indeks silinir
  6. Boşalan iç alan, performansı artıran veri yapıları için kullanılır (ör. Pair cache - sık birlikte görülen sorgu terimi çiftlerinin posting list intersection sonuçlarının önceden hesaplanması)

Büyümeye uyum ve ölçekleme (1999-2001)

• '99, '00 ve '01 yıllarında indeks boyutu ve trafik hızla arttı (~50 milyon → 1 milyardan fazla sayfa, aylık %20 trafik büyümesi + Yahoo iş ortaklığıyla trafiğin bir gecede 2 katına çıkması vb.)
• İndeks sunucusu performansı çok kritik hale geldi: Sürekli makine ekleme + her ay yazılım tabanlı %10-30 performans iyileştirmesi gerekiyordu
• Ölçekleme yöntemi: Daha fazla shard ve replica eklemek
• Çıkarımlar:
  • Shard yanıt süresi, disk seek sayısı ve okunması gereken veri miktarından etkilenir
  • Performans iyileştirme alanları: daha iyi disk scheduling, geliştirilmiş indeks encoding

İndeks encoding tekniklerinin gelişimi

• İlk encoding ('97): Çok basit byte-aligned biçim (WORD → [docid+nhits:32b, hit:16b, hit:16b...]). Hit, konum + özniteliklerdir (font boyutu, başlık vb.). Büyük posting list'ler için skip table eklendi. Decoding ucuzdu ancak sıkıştırma oranı düşüktü, bu yüzden çok fazla disk bant genişliği gerektiriyordu.
• Çeşitli encoding teknikleri:
  • Bit düzeyi: Unary, Gamma, Rice_k (Golomb kodunun özel durumu), Huffman-Int
  • Byte-aligned: varint (byte başına 7 bit + devam biti)
• Blok tabanlı indeks biçimi: Hem alan hem de CPU kullanımı azaldı (~%30 boyut küçülmesi), decoding hızı arttı. Değişken uzunluklu bloklar kullanıldı. Header (delta, uzunluk vb.) + belge ID delta'ları (Rice_k) + hit sayıları (Gamma) + hit öznitelikleri (run-length Huffman) + hit konumları (Huffman-Int).
• Yeni indeks biçimi (2004 sonrası): Tek bir düz konum alanı kullanıldı. Yardımcı veri yapılarıyla belge sınırları takip edildi. Posting list'ler delta-encoded konum listeleridir. Kompaktlık ve çok hızlı decoding birlikte kritik önem taşır.

Bellek içi indeks sistemi (2001 başı)

• Arka plan: Sharding ölçeklemesi + replica artışı sayesinde tüm indeks kopyasını bellekte tutmaya yetecek toplam bellek mümkün hale geldi
• Mimari: Frontend → load balancer (bal) → shard'lar (her shard için birden çok bellek içi indeks sunucusu kopyası)
• Avantajlar: Throughput büyük ölçüde arttı, latency ciddi biçimde düştü (özellikle daha önce GB düzeyinde disk I/O gerektiren karmaşık sorgular hızlandı - ör. "circle of life")
• Sorunlar:
  • Varyans (Variance): Onlarca makine yerine binlerce makine kullanımı → öngörülemezlik arttı (ör. rastgele cron işleri sorun çıkarabiliyordu)
  • Erişilebilirlik (Availability): Her belge indeks verisinin tek veya az sayıda kopyası vardı → "ölüm sorguları" (tüm backend'lerin aynı anda düşmesi), makine arızalarında indeks verisinin erişilebilirliği sorunu (özellikle önemli belgeler için replication gerekli)

Daha sonraki sistem tasarımları ve teknolojiler (2004 sonrası)

• Donanım: Daha büyük ölçekli veri merkezleri, şirket içi tasarlanmış rack'ler, PC sınıfı anakartlar, düşük maliyetli depolama/ağ donanımı, Linux + şirket içi geliştirilen yazılımlar
• Serving tasarımı (2004 sürümü): Hiyerarşik yapı
  • Root sunucuları → Parent sunucuları → Leaf sunucuları (GFS'den File Loader aracılığıyla Repository Shard yüklenir)
  • Cache sunucusu entegrasyonu

Group Varint encoding

• Fikir: Varint decoding'deki verimsizliği (çok sayıda branch/shift/mask işlemi) çözmek. 4 tamsayı değeri grup halinde 5~17 byte'a encode etmek.
• Yöntem:
  • Her değerin byte uzunluğunu (1~4 byte) gösteren 2 bitlik 4 tag bir araya getirilerek 1 byte'lık bir prefix byte oluşturulur.
  • Prefix byte'tan sonra gerçek veri byte'ları saklanır.
• Decoding: Prefix byte okunur, indeks olarak kullanılıp önceden hesaplanmış 256 girdilik tabloda lookup yapılır → offset ve mask bilgisi alınır, ardından 4 değer tek seferde decode edilir.
• Performans: Önceki yöntemlerden çok daha hızlıdır (Group Varint: ~400M/sn, 7-bit Varint: ~180M/sn, 30-bit Varint w/ 2-bit len: ~240M/sn)

Universal Search (2007)

• Yalnızca web arama sonuçlarını değil, farklı türde bilgileri de (görseller, yerel bilgiler, haberler, videolar, bloglar, kitaplar vb.) birleştirip gösteren sistem.
• Super root düğümü, birden fazla uzman arama sistemine (vertical search engine) sorgu gönderir ve sonuçları birleştirir.

Düşük gecikmeli crawling ve indexing'in zorlukları

• Güncellemeleri dakikalar içinde yansıtmak çok zor bir iştir.
• Crawling heuristics: Hangi sayfalar crawl edilecek?
• Crawling sistemi: Sayfalar hızlı crawl edilmelidir.
• Indexing sistemi: PageRank, anchor text gibi global verilere bağımlıdır → online approximation gerekir.
• Serving sistemi: Sorgu işlenirken güncellemeleri kabul etmeye hazır olmalıdır (batch update sisteminden çok farklı veri yapıları gerekir).

Deneylerin önemi ve altyapı

• Deney yapma kolaylığı: Çok önemlidir (hızlı deney döngüsü → daha fazla deney → daha fazla iyileştirme).
• Deney türleri:
  • Kolay deneyler: mevcut veri ağırlıklarını ayarlamak vb.
  • Zor deneyler: üretim indeksinde olmayan yeni veri gerektirir. (Yeni verinin üretilmesi/entegrasyonu ve deneylerde kullanımının kolay olması gerekir.)
• Temel altyapı:
  • GFS: Büyük ölçekli dağıtık dosya sistemi
  • MapReduce: Büyük ölçekli veri işleme işlerinin kolay yazılıp çalıştırılması. (Üretim indeks verisi üretimini hızlandırır, geçici deneylerin hızlı yapılmasını sağlar.)
  • BigTable: Yarı yapılandırılmış (semi-structured) depolama sistemi. (Belge bazlı bilgiye çevrimiçi/verimli erişim, birden fazla sürecin belge bilgisini asenkron güncelleyebilmesi - saatler düzeyinden dakikalar düzeyine inen güncellemeler için önemlidir)

Deney döngüsü ve yayına alma

1. Fikir üretimi ve offline deneyler:
   • MapReduce, BigTable vb. ile veri üretilir.
   • Offline deneyler yürütülür ve etki doğrulanır (insan değerlendirmeli sorgu setleri, rastgele sorgu setleri vb.).
   • Bu aşamada prototipin gecikmesi/throughput'u önemli değildir.
   • Deney sonuçlarına göre yinelemeli iyileştirme yapılır.
2. Canlı deneyler:
   • Offline deney sonuçları iyi ise gerçek kullanıcı trafiğinin küçük bir bölümünde (tiny sliver) canlı deney yapılır (çoğunlukla rastgele örneklem, bazen belirli sorgu sınıfları üzerinde).
   • Bu aşamada throughput'tan çok latency önemlidir! Deney framework'ü üretim ortamı gecikmesine yakın çalışmalıdır.
3. Performans ayarı ve yayına alma:
   • Canlı deney sonuçları iyiyse, tam yük altında çalışabilecek şekilde performans tuning/yeniden uygulama yapılır (ör. çalışma anında hesaplama yerine veriyi önceden hesaplamak, "yeterince iyiyse" daha ucuz approx kullanmak).
   • Yayına alma (Rollout) süreci kritiktir: kalite ve maliyet arasındaki trade-off sürekli değerlendirilmelidir; hızlı yayına alma ile düşük gecikme/site kararlılığı arasında denge kurulmalıdır (arama kalite ekibi ile performans/kararlılık ekibi arasında iyi iş birliği gerekir).

Gelecek yönelimler ve zorluklar

• Çapraz dilli bilgi erişimi (Cross-Language IR): Dünyadaki tüm belgeleri tüm dillere çevirmek → indeks boyutu hızla büyür, hesaplama maliyeti yüksektir. (Çeviri kalitesi sürekli iyileşmeli; daha büyük ve karmaşık dil modellerini işlemek için büyük ölçekli sistemler gerekir.)
• Bilgi erişim sistemlerinde erişim kontrol listeleri (ACLs): Özel/yarı özel/geniş paylaşımlı/herkese açık belgelerin karışık olduğu ortamlar. (Boyutları çok değişen ACL'leri verimli işleyebilen sistemler gerekir - 10 kişiyle paylaşılan belge ile tüm dünyayla paylaşılan belge için en iyi çözüm aynı değildir; paylaşım kalıpları zamanla değişebilir.)
• Verimli IR sistemlerinin otomatik inşası: Şu anda farklı amaçlar için birden çok sistem kullanılıyor (çok hızlı güncelleme, ultra büyük belge hacmi vb.). (Parametreler verildiğinde gereksinime uygun verimli arama sistemi otomatik kurabilen tek bir sistem geliştirilebilir mi?)
• Yarı yapılandırılmış veriden bilgi çıkarımı: Açık semantik etiketlere sahip veri çok azdır. Tablo, form vb. yarı yapılandırılmış veri ise bol miktardadır. (Yapılandırılmamış/yarı yapılandırılmış kaynaklardan yapılandırılmış bilgi çıkarmayı geliştirecek algoritma ve teknikler gerekir - çok gürültü vardır ama tekrar kullanılabilir; farklı kaynaklardaki bilgileri ilişkilendirme/birleştirme/toplulaştırma yeteneği önemlidir.)

Sonuç

• Büyük ölçekli bilgi erişim sistemlerini tasarlamak ve kurmak zorlu ama eğlenceli bir iştir.
• Yeni arama teknolojileri çoğu zaman yeni sistem tasarımları gerektirir.