Typeahead Sistem Tasarımı: Arama Otomatik Tamamlama Ölçekte Nasıl Çalışır

Bir arama kutusuna “how to” yazın; öneriler siz bir sonraki kelimeyi bitirmeden görünür. Bu özellik neredeyse her tuş vuruşunda, her kullanıcı için bir isteği yanıtlar ve anında gibi hissettirmelidir: Onlarca yıl öncesine uzanan yanıt süreleri araştırmaları, “sistem anında tepki veriyor” hissinin sınırını yaklaşık 0,1 saniye olarak koyar. Otomatik tamamlamadaki hiçbir parça tek başına zor değildir. Zorluk, basit şeyleri çok yüksek bir istek hızında, dar bir gecikme bütçesi içinde yapmak ve bunu yaparken önerileri taze ve asla göstermek istemeyeceğiniz şeylerden arınmış tutmaktır.

Bu yazı bir typeahead servisi tasarlıyor: gereksinimler ve kapasite, top-k önek indeksi, sunum ve sharding, çevrimdışı derleme hattı, trend sorgular, önbellekleme, kişiselleştirme ve filtreleme; iki yarının da diyagramıyla.

Gereksinimler

İşlevsel:

• Bir önek için, çoğunlukla popülerliğe göre sıralanmış en iyi 5 ila 10 tamamlama döndürülür.
• Yeni trendler günler içinde değil, dakikalar içinde yansıtılır.
• Politikalarınızı ihlal eden öneriler asla gösterilmez.

İşlevsel olmayan:

• Uçtan uca yaklaşık 100 ms; ağ süresinden sonra bu, arka uca onlarca milisaniyelik bir bütçe bırakır.
• Yüksek erişilebilirlik: Öneriler başarısız olursa arama yine çalışır, bu yüzden sistem zarif biçimde geri çekilir.
• Ucuz: Bu, her tuş vuruşunda çalışır.

Kapasite

Her biri günde 10 arama yapan 50 milyon günlük kullanıcı ve istemci her karakter için bir istek göndermeyi bıraktıktan sonra arama başına yaklaşık 6 öneri isteği varsayalım:

Tasarımı iki gözlem şekillendirir. Kısa önekler son derece tekrarlıdır: “w” yazan herkes aynı soruyu sorar. Ve bir önekin yanıtı yavaş değişir, bu yüzden önceden hesaplanabilir.

İşin yarısını istemci yapar

• Debounce. Bir istek göndermeden önce son tuş vuruşundan sonra 100 ila 200 ms bekleyin, böylece hızlı yazanlar karakter başına bir istek tetiklemez.
• Bayat istekleri iptal edin. Yeni bir önek gittiğinde öncekini iptal edin ve daha eski bir önek için geç gelen yanıtları yok sayın.
• Yerelde önbelleğe alın. “how t” hepsi “how to” ile başlayan on sonuç döndürdüyse, istemci bunları istek atmadan “how to” için filtreleyebilir.
• Sessizce geri çekilin. Öneri çağrısı başarısız olur ya da yavaşlarsa hiçbir şey göstermeyin; arama yine de çalışmalıdır.

Top-k önek indeksi

Klasik yapı bir trie'dir; her düğüm bir önektir ve çocukları onu bir karakter uzatır. İstek anında trie'de yürüyüp en popüler sorgular için tüm alt ağacı aramak, popüler önekler için fazla yavaştır. Bunun yerine yanıtı önceden hesaplayın: Her önek düğümünde, önceden sıralanmış en iyi k tamamlamayı saklayın. Bir arama tek bir okumaya dönüşür.

Birçok uygulama işaretçi tabanlı trie'yi tamamen atlar ve önekten top-k listesine düz bir eşleme saklar; çok uzun önekler nadir olduğu ve daha yavaş bir yola düşebileceği için bu eşleme bir azami önek uzunluğuyla sınırlanır. Toplanmış sayımlardan bir tane oluşturmak kısadır:

import heapq
from collections import defaultdict

def build_prefix_index(query_counts, k=10, max_prefix=12):
    index = defaultdict(list)  # prefix -> min-heap of (count, query)
    for query, count in query_counts.items():
        for n in range(1, min(len(query), max_prefix) + 1):
            heap = index[query[:n]]
            if len(heap) < k:
                heapq.heappush(heap, (count, query))
            elif count > heap[0][0]:
                heapq.heapreplace(heap, (count, query))
    return {p: [q for _, q in sorted(h, reverse=True)] for p, h in index.items()}

Çıktı salt okunurdur ve her sunucu düğümünde belleğe yüklenir. Zaten Elasticsearch çalıştırıyorsanız, completion suggester aynı fikri bir özellik olarak sunar: Belgeleri, hızlı aramaları mümkün kılan ama oluşturması maliyetli olan ve bellekte saklanan veri yapılarını anlatır; bu da tam olarak bu tasarımın yaptığı ödünleşimdir.

Sunum ve sharding

Öneri servisi öneki normalleştirir (küçük harf, kırpma, Unicode normalleştirme), top-k listesini indeksten okur, trend ve kişisel sonuçları birleştirir, filtreler ve döndürür. Okuduğu her şey bellektedir.

İndeks tek bir makineye sığmaz hâle geldiğinde onu shard'layın. İlk harfe göre shard'lamak doğal görünür ama son derece dengesizdir: “s” ile başlayan sorgular “x” ile başlayanlardan çok daha fazladır. Bunun yerine öneki hash'leyin ya da ölçülen trafiğin aralıklarına göre bölün ve her shard'ı çoğaltın ki bir düğüm arızası yalnızca kapasiteyi azaltsın. İndeks çevrimdışı yeniden oluşturulduğu için replikaların yazmalar üzerinde anlaşması gerekmez; her biri aynı snapshot'ı yükler.

Çevrimdışı derleme hattı

1. Toplayın. Arama ön yüzleri tamamlanan her sorguyu Kafka gibi bir akışa loglar.
2. Birleştirin. Bir toplu iş, sorguları bir pencere boyunca sayar, örneğin son 30 gün, yakın günlere daha fazla ağırlık vererek; gizliliği korumak ve gürültüyü temizlemek için eşiğin altındaki nadir sorguları atar.
3. Filtreleyin. Bir şey öneri hâline gelmeden önce engel listelerini ve politika sınıflandırıcılarını uygulayın.
4. Oluşturun. Önek indeksini yukarıdaki gibi hesaplayın ve sürümlü bir snapshot olarak nesne depolamaya yazın.
5. Dağıtın. Sunucu düğümleri yeni snapshot'ı eskisinin yanına yükler, atomik olarak geçiş yapar ve hızlı geri alma için önceki sürümü saklar.

Saatlik ya da günlük yeniden derlemeler, ana indeksi çoğu sorgu için yeterince taze tutar.

Trend sorgular

Son dakika bir haber, bir sonraki toplu derlemeden çok önce, dakikalar içinde yeni ve popüler bir sorgu üretir. Küçük bir gerçek zamanlı katman ekleyin: Bir akış işlemcisi sorguları kayan pencerelerde sayar, taban çizgisinden çok daha hızlı yükselenleri tespit eder ve onları önek anahtarıyla Redis gibi hızlı bir depoya yazar. Öneri servisi bunları toplu sonuçlarla birleştirir. Bu katmanı küçük tutun ve agresif şekilde filtreleyin; koordineli bir saldırının öneri yerleştirmeye çalışacağı yer burasıdır.

Her katmanda önbellekleme

Kısa önekler en sıcak ve en önbelleklenebilir olanlardır, çünkü herkes için aynıdır. Kişiselleştirilmiş sonuçlar CDN'de önbelleğe alınamaz; kişiselleştirmeyi hafif tutmanın bir nedeni de budur.

Kişiselleştirme, yazım hataları ve filtreleme

• Kişisel geçmiş. Kullanıcının kendi son sorgularını genel önerilerle harmanlamak çok işe yarar; son sorgular cihazda ya da kullanıcı başına küçük bir depoda duruyorsa ucuzdur.
• Yazım hataları. Önekten bir düzenleme uzaklığındaki bulanık eşleşme “pyhton” yazanı kurtarır. Daha pahalıdır; bu yüzden birçok sistem önce tam önekleri dener ve yalnızca sonuçlar az olduğunda bulanık eşleşmeye geçer.
• Filtreleme iki kez uygulanır: çevrimdışı, bir sorgu indekse girmeden önce; çevrimiçi ise yeniden derleme olmadan dakikalar içinde güncellenebilen hızlı bir engel listesine karşı.

Typeahead diyagramı

Nasıl okunur:

• Çevrimiçi çerçeve tuş vuruşu başına yoldur: tarayıcı, CDN önbelleği, API ağ geçidi ve öneri servisi.
• Öneri servisi bellekteki iki önek shard'ını ve Redis trend deposunu okur, sonuçları birleştirir ve filtreler.
• Çevrimdışı çerçeve derleme yoludur: Kafka'dan gelen sorgu logları, toplama işi ve nesne depolamadaki sürümlü indeks snapshot'ları.
• Nesne depolamadan shard'lara giden kesikli kenar snapshot yüklemesidir; iki yarı arasındaki tek bağlantı odur.
• Markdown bloğu gecikme bütçesini ve kapasite rakamlarını gösterir.

Okuma ağırlıklı sistemleri net çizmek

• Çevrimiçi ve çevrimdışını ayırın. İki yarının farklı gecikme bütçeleri, arıza biçimleri ve sahipleri vardır; diyagram bunu bir bakışta göstermelidir.
• Her önbellek katmanını süresiyle birlikte gösterin. Okuma ağırlıklı bir sistemde mimarinin büyük kısmı önbelleklerdir.
• İki yarı arasındaki tek bağlantıyı çizin: burada sürümlü bir snapshot. Güncellemelerin kullanıcılara nasıl ulaştığını ve geri almanın nasıl çalıştığını açıklar.
• Çevrimiçi yolun üzerine gecikme bütçesini yazın.

Genel yaklaşım için sistem tasarımı diyagramı örneğine bakın. Önbellekleme stratejileri diyagramı önbellek katmanlarını daha derinlemesine ele alıyor; log toplama ise veri hattı mimari diyagramındaki desenleri izliyor.

Archboard'da oluşturun

1. Google ya da GitHub ile giriş yapın ve bir diyagram oluşturun.
2. İki Temel Çerçeve düğümü ekleyin: Online, per keystroke ve Offline, hourly build.
3. Çevrimiçi çerçeveye tarayıcı için Ağ paketinden bir Cihaz düğümü, Bulut paketinden bir CDN ve bir API ağ geçidi, öneri servisi için bir Hesaplama düğümü, önek shard'ları için Veri paketinden iki Redis düğümü ve trend sorgular için bir Redis düğümü daha ekleyin.
4. Çevrimdışı çerçeveye sorgu logları için Veri paketinden bir Kafka düğümü, toplama işi için Bulut paketinden bir Hesaplama düğümü ve indeks snapshot'ları için Veri paketinden bir Nesne deposu ekleyin.
5. İstek yolunu soldan sağa, derleme yolunu onun altına çizin ve snapshot'lardan shard'lara kesikli bir kenar ekleyin.
6. Temel paketinden gecikme bütçesini ve kapasiteyi içeren bir Markdown bloğu ekleyin.

Örnek 13 diyagram düğümü kullanıyor ve Free planın sınırları içinde kalıyor.

SSS

Otomatik tamamlama için hangi veri yapısı kullanılır? Her önekte en iyi k tamamlamanın önceden hesaplandığı bir trie ya da önekten sonuçlara düz bir eşleme. Ön hesaplama her aramayı bellekte tek bir okumaya dönüştürür.

Otomatik tamamlama ne kadar hızlı olmalı? Tuş vuruşundan önerilere yaklaşık 100 ms anında gibi hissettirir. Ağ süresinden sonra bu, arka uca onlarca milisaniye bırakır; indeksin bellekte durmasının nedeni budur.

Öneriler nasıl güncel kalır? Bir toplu iş hattı indeksi saatte ya da günde bir sorgu loglarından yeniden oluşturur; gerçek zamanlı bir katman da hızla yükselen sorguları dakikalar içinde ekler.

Otomatik tamamlama istekleri her tuş vuruşunda gönderilmeli mi? Hayır. İstemcide 100 ila 200 ms debounce uygulayın, eskimiş istekleri iptal edin ve daha uzun önekler için önbellekteki sonuçları yeniden kullanın. Bu, istek hacmini önemli ölçüde azaltır.

Saldırgan öneriler nasıl dışarıda tutulur? Sorgular indekse girmeden önce çevrimdışı filtreleyin, asgari popülerlik eşikleri uygulayın ve sonuçları çevrimiçi olarak hızla güncelleyebildiğiniz bir engel listesine karşı kontrol edin.

Ücretsiz başlayın — tek kullanıcı, kredi kartı gerekmez.