Arama otomatik tamamlama (typeahead)

Problem

"Bir e-ticaret sitesinin arama kutusu için otomatik tamamlama tasarla. Kullanıcı yazdıkça, yazdığı ön eke uyan en popüler 10 arama önerisi gösterilmeli. Öneriler kullanıcı yazarken anlık hissettirmeli, popülerlik zamanla güncellenmeli, trend olan aramalar hızlı yansımalı ve uygunsuz öneriler asla gösterilmemeli."

Bu soru bir veri yapısı sorusu gibi başlar (trie ve top-K) ama asıl ölçtüğü şey gecikme bütçesi ve okuma yolunu yazma yolundan ayırmaktır. Her tuş vuruşu bir istek olabilir; öneriler 100 ms içinde gelmezse kullanıcı yazmaya devam eder ve öneri anlamsızlaşır. Mülakatçının dinlemek istediği konular: hangi verinin önceden hesaplanacağı, servis anında ne kadar iş yapılacağı, verinin nasıl güncelleneceği, istemci tarafı optimizasyonlar, Türkçe metin normalizasyonu ve filtreleme.

Netleştirme soruları ve varsayımlar

Kapasite tahmini

İstek:
  50M DAU x 5 arama x ~4 öneri isteği (debounce sonrası) = 1 milyar istek/gün
  1.000.000.000 / 86.400 ≈ 11.600 /s ortalama, tepe (x3) ≈ 35.000 /s

Veri:
  son 30 günün farklı sorguları ~100M; gürültü ve tek seferlik sorgular atılınca ilk 10M sorgu
  ortalama sorgu ~20 karakter
  farklı ön ek sayısı (paylaşımlı, uzunluk 20 ile sınırlı) ~30M varsayımı
    (kaba; uzun ön eklerin çoğu tek sorguya ait olduğundan gerçek sayı 2-3 katı çıkabilir, ölçülmeli)
  ön ek başına: anahtar ~10 B + 10 öneri id x 4 B + yapı yükü ≈ 100 B
  30M x 100 B ≈ 3 GB  + öneri metinleri 10M x ~30 B ≈ 300 MB

Servis:
  veri 3-4 GB (ön ek sayısı 3 katı çıksa ~10 GB) ile tek bir node'un belleğine sığar -> sharding yerine tam kopya
  node başına güvenli 10.000 istek/s varsayımıyla 35.000 / 10.000 ≈ 4 node; yedek ve bölge payıyla 8

Teşhis:

• Okuma çok yoğun, yazma yok denecek kadar az: Öneri verisi servis anında değişmez; periyodik olarak yeniden üretilir. Bu, okuma yolunu tamamen önceden hesaplanmış ve değişmez bir yapıdan servis etmeye izin verir.
• Veri belleğe sığıyor: Her servis node'u verinin tamamını taşıyabilir; sharding, dağıtık sorgu ve birleştirme gerekmez. Ölçek yatayda kopya eklemektir.
• Gecikme bütçesi dar: Mobil ağda gidiş-dönüş tek başına onlarca milisaniye. Sunucuya kalan bütçe 20-30 ms; servis anında sıralama, birleştirme ya da veritabanı çağrısı yapacak yer yok.

API

GET /api/v1/suggestions?q=kırmızı%20el&limit=10&locale=tr-TR
-> 200
Cache-Control: public, max-age=300
{ "query": "kırmızı el",
  "suggestions": [ { "text": "kırmızı elbise", "type": "QUERY" },
                   { "text": "kırmızı elbise abiye", "type": "QUERY" },
                   { "text": "kırmızı eldiven", "type": "QUERY" } ],
  "snapshot": "2026-10-23T03:00Z" }

• İstek GET'tir ve cache'lenebilir: aynı ön ek için cevap herkes için aynıdır (kişiselleştirme yokken). Bu, CDN ve tarayıcı cache'ini devreye sokar.
• snapshot, cevabın hangi veri sürümünden geldiğini söyler; hata ayıklama ve A/B karşılaştırması için.
• Arama sorgusu ayrıca loglanır (POST /api/v1/search-events ya da arama servisinin kendi logu); bu log öneri hattının ham verisidir.

Veri modeli

Servis yapısı (bellekte, değişmez snapshot):

prefix_index : normalize edilmiş ön ek -> [öneri_id x 10]   (sıralı, önceden hesaplanmış top-10)
suggestions  : öneri_id -> { görüntülenecek metin, skor, tip }
blocklist    : servis anında uygulanan engelli öneri id'leri (snapshot'tan bağımsız güncellenir)

Toplama tarafı (analitik depo):

search_logs           : (zaman, normalize sorgu, kullanıcı hash'i, sonuç sayısı, tıklama/sepete ekleme)
query_stats_daily     : (gün, normalize sorgu, arama sayısı, tekil kullanıcı, dönüşüm)
query_scores          : (normalize sorgu, skor)   -- zaman ağırlıklı, filtrelerden geçmiş

Yüksek seviye tasarım

flowchart LR
    U[İstemci, debounce ve yerel cache] --> CDN[CDN kısa ön ekler]
    CDN --> LB[Load balancer]
    LB --> SV[Öneri servis node'ları, bellekte snapshot]
    SV --> TR[Trend katmanı]
    U -->|arama logları| K[(Kafka)]
    K --> AGG[Toplama job'ları, saatlik ve günlük]
    K --> RT[Trend akış işleyicisi]
    RT --> TR
    AGG --> FLT[Filtreler, engel listesi, eşikler]
    FLT --> BLD[Snapshot üretici]
    BLD --> OBJ[(Nesne deposu, versiyonlu snapshot)]
    OBJ -->|atomik yükleme| SV
    MOD[Moderasyon paneli] --> BL[(Engel listesi)]
    BL --> SV

Okuma ve yazma yolu tamamen ayrıdır:

• Okuma yolu: İstek, bellekteki önceden hesaplanmış yapıdan tek bir anahtar okumasıyla cevaplanır; trend katmanı varsa küçük bir birleştirme yapılır, engel listesi uygulanır.
• Yazma yolu (çevrimdışı): Arama logları Kafka'dan toplanır, sayılır, filtrelenir, skorlanır, her ön ek için top-10 hesaplanır ve versiyonlu bir snapshot olarak yayınlanır. Servis node'ları yeni snapshot'ı arka planda yükler ve hazır olunca atomik olarak geçer.

Derinlemesine

Veri yapısı: trie, düz ön ek tablosu, FST

Naif trie: Her karakter bir düğüm; ön ekin düğümüne gidip altındaki bütün sorguları dolaşmak ve en popüler 10'u bulmak. Sorun: "e" gibi kısa bir ön ekin altında milyonlarca sorgu vardır; her istekte alt ağacı dolaşmak bütçeyi aşar.

Top-K'yı düğümlerde önceden hesaplamak: Her düğümde o ön ekin en popüler 10 sorgusu saklanır. Sorgu süresi ön ek uzunluğuyla orantılı (düğüme inmek) artı sabit (hazır listeyi okumak) olur. Bedeli bellek (her düğümde 10 referans) ve güncellemenin pahalı olması; ama güncelleme çevrimdışı yapıldığı için sorun değildir.

Düz ön ek tablosu: Trie'yi tamamen düzleştirip ön ek → top-10 hash map'i olarak tutmak. Sorgu tek bir hash okumasıdır; uygulaması en basitidir. Ön ek uzunluğunu sınırlamak (ör. 20 karakter) tablo boyutunu kontrol altında tutar; daha uzun ön eklerde 20. karakterin listesi filtrelenir.

FST (finite state transducer): Ön ekleri ve son ekleri paylaşan, çok kompakt bir otomat. Lucene'in kullandığı yapıdır; Elasticsearch'ün completion suggester'ı da hızlı arama için oluşturması pahalı ama bellekte tutulan veri yapıları kullanır. Bellek verimliliği en yüksek seçenektir; kendi servisinde sıfırdan yazmak ise en zahmetlisidir.

Seçim: veri birkaç GB olduğu için düz ön ek tablosu (ya da top-K'lı trie) yeterlidir ve en kolay işletilir. Bellek sıkışırsa FST'ye geçilir.

Skorlama: sadece arama sayısı değil

• Zaman ağırlığı: Bugünkü arama, 25 gün önceki aramadan değerlidir. Günlük sayılar üstel azalmayla toplanır: skor = sum(sayı_gün x 0,9^(gün_farkı)). Böylece "kışlık mont" Ekim'de yükselir, Mart'ta düşer.
• Tekil kullanıcı: Bir botun ya da tek bir kullanıcının aynı sorguyu binlerce kez araması skoru şişirmemeli; sayım tekil kullanıcı (ya da kullanıcı başına sınırlı katkı) üzerinden yapılır.
• Kalite sinyalleri: Sonuç vermeyen sorgular (sıfır sonuç) önerilmez; tıklama ve sepete ekleme oranı yüksek sorgular yukarı çıkar. E-ticarette amaç sadece "popüler" değil "işe yarayan" sorguyu önermektir.
• Eşikler: Bir sorgunun öneri olabilmesi için en az N farklı kullanıcı tarafından aranmış olması gerekir. Bu hem gürültüyü hem de kişisel verinin (birinin kendi adını, telefonunu araması) öneri olarak sızmasını engeller.

Güncelleme hattı ve trendler

• Temel snapshot (günlük): Batch job son 30 günün loglarını toplar, skorlar, filtreler, top-10'ları hesaplar ve snapshot üretir. Snapshot nesne deposuna versiyonlu yazılır; servis node'ları yeni versiyonu indirip belleğe yükler, doğrulama (boyut, örnek sorgularda sonuç) geçerse atomik olarak geçer, geçmezse eskisinde kalır. Geri almak bir önceki versiyona dönmektir.
• Trend katmanı (dakikalar): Bir ünlünün paylaştığı ürün ya da ani bir olay, günlük güncellemeyi bekleyemez. Bir akış işleyicisi son 1 saatteki sorgu sayılarını kayan pencerede sayar ve normal seviyesine göre ani yükselen sorguları çıkarır. Bu küçük bir kümedir (birkaç bin sorgu); servis node'larına birkaç dakikada bir itilir ve servis anında temel top-10 ile birleştirilir. Trendler de filtrelerden geçer; yanlış bir trend sorgusunun saniyeler içinde milyonlarca kullanıcıya önerilmesi ciddi bir risktir.
• Engel listesi (anında): Hukuki ya da etik bir sorunla karşılaşılan bir öneri bir sonraki snapshot'ı bekleyemez. Engel listesi ayrı tutulur, servis anında uygulanır ve dakikalar içinde yayılır; engellenen öneri yerine listedeki 11. aday gösterilir (bu yüzden her ön ek için 10 değil birkaç fazla aday saklamak işe yarar).

İstemci tarafı: en ucuz istek hiç atılmayan istektir

• Debounce: Her tuş vuruşunda değil, yazma 100-150 ms durduğunda istek atılır. Hızlı yazan kullanıcı için istek sayısı yarıdan fazla düşer.
• Uçuştaki isteği iptal etmek: Kullanıcı "kırm" yazarken "kır" isteğinin cevabı geç gelirse gösterilmemeli; istemci eski isteği iptal eder ya da cevabı yok sayar (cevapta query alanı bunun içindir).
• İstemci cache'i: "kırmı" için gelen sonuçlar, kullanıcı geri silip tekrar yazarsa yerelden gösterilir. Ayrıca bazı istemciler bir ön ekin sonuç listesini, daha uzun ön ekler için yerelde filtreler.
• CDN: Kısa ön ekler (1-3 karakter) toplam trafiğin büyük kısmını oluşturur ve herkes için aynıdır; Cache-Control: public, max-age=300 ile edge'de cache'lenir. Kişiselleştirme eklenirse kişisel kısım ayrı bir istekte ya da istemcide birleştirilir, aksi halde CDN cache'i işe yaramaz.

Gecikme bütçesi

Kullanıcı hedefi                    100 ms
  istemci debounce sonrası istek       0 ms (debounce bütçeye dahil değil)
  mobil ağ gidiş-dönüşü              40-60 ms
  TLS ve gateway                      5-10 ms
  servis (hash okuma + birleştirme)   1-5 ms
  kalan pay                          ~20 ms

Bu bütçede servis anında veritabanı çağrısı, uzak bir sıralama servisi ya da çok shard'lı bir sorgu yoktur. Sunucu tarafında p99 gecikmenin de düşük olması için GC duraklamaları önemlidir: büyük, değişmez bir yapı JVM'de eski nesil (old generation) heap'te durur; düşük duraklamalı bir GC (ZGC ya da G1 ayarı) ve snapshot değişiminde iki kopyanın aynı anda bellekte olmasına yetecek heap gerekir (Kitap Bölüm 3).

Türkçe metin normalizasyonu

Türkçe, otomatik tamamlamanın en sinsi hatalarına zemin hazırlar:

• Büyük-küçük harf: "I".toLowerCase(Locale.ROOT) "i" döner ama Türkçede I'nın küçüğü ı'dır; "İ".toLowerCase(Locale.ROOT) ise i + birleşik nokta işaretinden oluşan iki karakterlik bir dizgedir. Locale'siz toLowerCase hem yanlış eşleşme hem de görünmez karakter üretir. Küçültme Locale.forLanguageTag("tr") ile yapılır.
• ASCII yazım: Kullanıcılar sık sık seker, cilek, isik yazar. Hem indekslenen sorgular hem gelen ön ek aynı katlamadan geçer: aksan işaretleri atılır, ı → i. Görüntülenen öneri ise orijinal Türkçe yazımla gösterilir (şeker).
• Boşluk ve noktalama: Fazla boşluklar teke indirilir; baştaki ve sondaki boşluklar atılır.

public final class QueryNormalizer {

    private static final Locale TR = Locale.forLanguageTag("tr");
    private static final Pattern MARKS = Pattern.compile("\\p{M}+");
    private static final Pattern SPACES = Pattern.compile("\\s+");

    private QueryNormalizer() {
    }

    public static String normalize(String query) {
        String lower = query.strip().toLowerCase(TR);                       // IŞIK -> ışık, İ -> i
        String noMarks = MARKS.matcher(Normalizer.normalize(lower, Normalizer.Form.NFD))
                              .replaceAll("");                              // ş -> s, ğ -> g, ç -> c
        return SPACES.matcher(noMarks.replace('ı', 'i')).replaceAll(" ");   // ı'nın ayrışımı yok
    }
}

Bu sınıf JDK 21 ile çalıştırıldı: IŞIK → isik, İstanbul → istanbul, Şeker Çilek → seker cilek, ÖĞÜT → ogut. Aynı normalizasyonun indeksleme ve sorgu tarafında birebir aynı kodla yapılması şarttır; iki tarafın ayrı yazılması, eşleşmeyen önerilerin en yaygın nedenidir.

Elasticsearch ile çözmek

Ekip zaten Elasticsearch kullanıyorsa iki hazır seçenek vardır:

• Completion suggester: Hız için optimize edilmiştir; arkasındaki veri yapıları bellekte tutulur ve oluşturulması pahalıdır. Her öneriye bir weight verilebilir, fuzzy sorguyla yazım hatası toleransı sağlanır ve öneriler near real-time görünür (refresh sonrası). Popüler sorgu önerisi için uygundur.
• search_as_you_type alanı: Alanı shingle (2 ve 3 kelimelik) alt alanlarına ve bir edge n-gram alt alanına böler; dokümantasyonun önerdiği sorgu, bu alanları hedefleyen bool_prefix tipinde bir multi_match'tir. Kelime sırası farklı yazılsa da eşleşir. Ürün adı önerisi ("elbise kırmızı" yazana "Kırmızı Saten Elbise") için uygundur.

Trade-off: Elasticsearch işletimi hazır ve esnek (filtre, fuzzy, çok alanlı eşleşme), ama her istek bir ağ çağrısı ve bir arama motoru sorgusudur; 35.000 istek/s ve 20 ms bütçede kapasite ve gecikme dikkatle ölçülmelidir. Popüler sorgu önerisi için kendi bellek içi servisi, ürün adı önerisi için Elasticsearch kullanmak yaygın ve makul bir ayrımdır. Türkçe için analyzer'da turkish lowercase ve ASCII folding filtreleri yapılandırılmalıdır (Kitap Bölüm 11).

Kişiselleştirme (ikinci aşama)

Temel top-10'u değiştirmeden kişiselleştirme eklemenin ucuz yolu: servis her ön ek için 30-50 aday döner, istemci ya da ince bir kişiselleştirme katmanı kullanıcının son aramaları ve kategori tercihleriyle yeniden sıralar. Böylece ön ek cevabı herkes için aynı kalır ve CDN'de cache'lenebilir; kişisel kısım küçük ve kullanıcıya özel bir veridir (son 20 arama). Bütçeyi aşan bir model çağrısı kritik yola konmaz.

Darboğazlar, hatalar ve trade-off'lar

Trade-off'lar:

• Önceden hesaplama: Servis anı çok ucuz; bedeli tazelik (günlük snapshot) ve bunu telafi eden trend katmanının karmaşıklığı.
• Tam kopya ve sharding: Veri sığdığı için her node tam kopya taşır; ölçek yatay kopya eklemektir. Veri büyürse ön eke göre sharding gerekir.
• Kendi servisi ve Elasticsearch: Gecikme ve maliyet kontrolü ile esneklik ve hazır özellikler arasında.
• Ortak cevap ve kişiselleştirme: CDN cache'lenebilirliği için kişiselleştirmeyi ayrı katmana ittik.

Üç seviyede cevap

Soru: "Otomatik tamamlamayı hangi veri yapısıyla yaparsın?"

Soru: "Önerilerin 100 ms içinde gelmesini nasıl sağlarsın?"

Soru: "Öneriler nasıl güncellenir? Bir anda trend olan bir aramayı nasıl yakalarsın?"

Mülakatçı için

Takip soruları:

• Çok dilli bir sitede ön ek tablosu nasıl bölünür?
• "iphone 1" yazana "iphone 15" mi "iphone 16" mı önce gelmeli? Skoru kim, nasıl belirler?
• Yeni snapshot'ın eskisinden iyi olduğunu nasıl ölçersin?
• Yazım hatası toleransını servis anında bütçeyi aşmadan nasıl eklersin?

Seviye beklentisi: Mid seviyede top-K'lı trie, çevrimdışı güncelleme, debounce ve cache beklenir. Senior'dan gecikme bütçesinin sayısal anlatımı, okuma/yazma ayrımının tasarımı yönlendirmesi, trend katmanı, güvenlik ve skorlama kalitesi beklenir.

Hızlı tekrar

Kaynaklar

• Alex Xu, System Design Interview: An Insider's Guide (Cilt 1): "Design a Search Autocomplete System" bölümü.
• Elasticsearch: Suggesters (completion suggester): Completion suggester'ın bellekteki veri yapıları, weight, fuzzy sorgular ve near real-time davranışı.
• Elasticsearch: search_as_you_type field type: Shingle ve edge n-gram alt alanları, bool_prefix sorgusu.