Arama Önerisi

Önceki vakada yanıt yazma anında hazırlanabiliyordu, çünkü kimin için hazırlanacağı yazıldığı anda belliydi. Burada o özellik yok: kullanıcı her tuş vuruşunda bir arama önerisi ister ve ne yazacağı önceden bilinmez. Yanıt yazma anında hazırlanamıyorsa okuma anında hazırlanmak zorundadır, ve bu kez okuma eşiği tuş vuruşları arasına sığacak kadar küçüktür. Bu ders hangi yapının o eşiği tutabildiğini ve güncelleme gecikmesinin sonuçlara ne yaptığını ölçer.

Kısıtlar

İşlevsel gereksinimler. I1: verilen önek için en çok 10 öneri döner. I2: öneriler sorgu sıklığına göre sıralanır. I3: yeni sorgular öneri havuzuna girer. I4: engellenen sorgu önerilmez.

Kapsam daraltması. Yazım düzeltme, kişiselleştirme, anlamsal eşleştirme ve çok dillilik dışarıdadır. Öneri yalnız ilk 10 karaktere kadar olan önek için verilir; daha uzun önekte istemci elindeki listeyi süzer. Bu daraltma tasarımın en pahalı kaleminde karşılığını bulacak.

Kod	Eşik	Eşiğin kaynağı
G1	öneri yanıtının ortancası 20 ms’yi geçmez	iki tuş vuruşu arasındaki aralık
G2	öneri yapısı 8 GB’yi geçmez	yapının bölünmeden tek düğümün belleğinde tutulması
G3	yeni sorgunun öneri listesine girme gecikmesi 600 saniyeyi geçmez	yükselen sorgunun aynı gün yakalanması

Varsayımlar

Kod	Varsayım	Değer	Gerekçe
VA1	günlük arama	20.000.000	tamamlanan arama sayısı
VA2	arama başına öneri isteği	12	yazılan her karakter bir istek üretir
VA3	tepe çarpanı	3	tepe saatteki hızın gün ortalamasına oranı
VA4	farklı sorgu sayısı	30.000.000	uzun kuyruk, çoğu sorgu birkaç kez sorulur
VA5	günde eklenen yeni sorgu	300.000	havuzun yüzde biri her gün yenilenir
VA6	sorgu sıklık dağılımı	Zipf, üs 1	sıra r’inci sorgunun sıklığı 1/r ile orantılı
VA7	öneri listesi uzunluğu	10	I1’in listesi

Kabaca Büyüklük Hesabı

// oneri/hesap.mjs — VA1–VA7'den cikan kabaca buyukluk hesabi ve esiklerin sayiya cevrilmesi
const VA = { gunlukArama: 20e6, aramaBasinaOneri: 12, tepe: 3, farkliSorgu: 30e6, gunlukYeniSorgu: 300_000, listeUzunlugu: 10 };
const GUN = 86_400, BELLEK = 8e9, PENCERE = 600;      // BELLEK: G2 esigi, PENCERE: G3 esigi
const b = (x, n = 2) => x.toFixed(n);

const oneriTepe = (VA.gunlukArama * VA.aramaBasinaOneri / GUN) * VA.tepe;
const aramaTepe = (VA.gunlukArama / GUN) * VA.tepe;
console.log(`tepe oneri istegi/s = ${b(oneriTepe)}   tepe arama/s = ${b(aramaTepe)}   oran = ${b(oneriTepe / aramaTepe)}`);
console.log(`G2'nin sorgu basina bayt butcesi = ${b(BELLEK / VA.farkliSorgu)} bayt (${BELLEK / 1e9} GB / ${(VA.farkliSorgu / 1e6)} milyon sorgu)`);
console.log(`G3 penceresinde biriken yeni sorgu = ${b(VA.gunlukYeniSorgu / GUN * PENCERE)} (gunde ${VA.gunlukYeniSorgu.toLocaleString("tr-TR")})`);
console.log(`yeniden kurma isi gunde ${b(GUN / PENCERE)} kez kosar; her kosum ${(VA.farkliSorgu / 1e6)} milyon sorguyu tarar`);

const iki = (VA.gunlukArama * VA.aramaBasinaOneri * 2 / GUN) * VA.tepe;
console.log(`VA2 duyarliligi: arama basina oneri 12 -> 24 ise tepe ${b(iki)} istek/s; bellek butcesi degismiyor, cunku yapi istek sayisina bagli degil`);

tepe oneri istegi/s = 8333.33   tepe arama/s = 694.44   oran = 12.00
G2'nin sorgu basina bayt butcesi = 266.67 bayt (8 GB / 30 milyon sorgu)
G3 penceresinde biriken yeni sorgu = 2083.33 (gunde 300.000)
yeniden kurma isi gunde 144.00 kez kosar; her kosum 30 milyon sorguyu tarar
VA2 duyarliligi: arama basina oneri 12 -> 24 ise tepe 16666.67 istek/s; bellek butcesi degismiyor, cunku yapi istek sayisina bagli degil

Üç sayı tasarımı belirliyor. Tepe öneri isteği saniyede 8333,33 — aramanın on iki katı, çünkü her karakter bir istek üretiyor. G2’nin 8 GB’lik eşiği sorgu başına 266,67 bayta dönüşüyor ve veri yapısı seçimini bir bütçe sorusuna çeviriyor. G3’ün penceresi yeniden kurma işini günde 144 koşuma bağlıyor, her koşumda 2083,33 yeni sorgu birikiyor.

Yapıların Ölçülmesi

Önek ağacı (prefix tree), Veri Yapıları kursunun Sözcük Ağaçları dersinde kurulan yapıdır. Mekaniği burada yeniden anlatılmaz; ölçülen şey bu vakadaki iki parametresidir — derinlik ve düğüm başına tutulan hazır liste.

// oneri/yapilar.mjs — onek agaci ile duz listenin bellek ve arama maliyeti, ve guncelleme
// gecikmesinin sonuc tazeligine etkisi. Sorgu kumesi kendi yazilmis uretecle uretilir. MODELDIR.
const TOHUM = 20260730, SORGU = 50_000, SOZCUK = 4000, ORNEK = 2000, K = 10, VA4 = 30e6;
const DUGUM_BAYT = 48, KAYIT_EK = 8;                 // muhasebe: dugum 48 bayt, kayit basina 8 bayt ek
let s = TOHUM % 2147483647;
const rast = () => (s = (s * 48271) % 2147483647) / 2147483647;
const sec = (a) => a[Math.floor(rast() * a.length)];

const HECE = ["ka", "le", "mi", "tu", "ro", "sa", "ne", "bi", "dol", "gar", "ver", "tan", "yi", "us", "ce"];
const sozluk = [];
for (let i = 0; i < SOZCUK; i += 1) {
  let k = "";
  for (let h = 0, n = 2 + Math.floor(rast() * 2); h < n; h += 1) k += sec(HECE);
  sozluk.push(k);
}
const sorgular = [], gorulen = new Set();
while (sorgular.length < SORGU) {
  const n = 1 + Math.floor(rast() * 3);
  let q = sec(sozluk);
  for (let i = 1; i < n; i += 1) q += " " + sec(sozluk);
  if (gorulen.has(q) === false) { gorulen.add(q); sorgular.push(q); }
}
const siklik = new Float64Array(SORGU);              // Zipf: sira r -> 1e6/r
for (let i = 0; i < SORGU; i += 1) siklik[i] = 1e6 / (i + 1);

const kok = new Map(), derinlikte = new Int32Array(64);
for (const q of sorgular) {                          // onek agaci: her dugum bir Map
  let d = kok, k = 0;
  for (const c of q) {
    k += 1;
    let alt = d.get(c);
    if (alt === undefined) { alt = new Map(); d.set(c, alt); derinlikte[Math.min(k, 63)] += 1; }
    d = alt;
  }
}
const b = (x, n = 2) => x.toFixed(n);
const karakter = sorgular.reduce((a, q) => a + q.length, 0);
console.log(`model: ${SORGU.toLocaleString("tr-TR")} farkli sorgu, ortalama uzunluk ${b(karakter / SORGU)} karakter`);
console.log(`\n${"yapi".padEnd(30)}${"dugum".padStart(11)}${"sorgu basina bayt".padStart(19)}${"VA4 sorguda GB".padStart(16)}`);
console.log(`${"duz liste".padEnd(30)}${"-".padStart(11)}${b((karakter + SORGU * KAYIT_EK) / SORGU).padStart(19)}` +
  `${b((karakter + SORGU * KAYIT_EK) / SORGU * VA4 / 1e9).padStart(16)}`);
let birikim = 1;
for (let d = 1; d <= 63; d += 1) {
  birikim += derinlikte[d];
  if ([6, 8, 10].includes(d) === false && d !== 63) continue;
  const bayt = birikim * (DUGUM_BAYT + K * 4);       // dugum + dugumdeki hazir liste
  console.log(`${`onek agaci, derinlik ${d === 63 ? "tam" : d}`.padEnd(30)}${birikim.toLocaleString("tr-TR").padStart(11)}` +
    `${b(bayt / SORGU).padStart(19)}${b(bayt / SORGU * VA4 / 1e9).padStart(16)}`);
}

// Istek sikligi Zipf'e gore agirlikli: siklik 1/r oldugundan sira = SORGU^u dagilimindan cekilir.
const agirlikliSec = () => Math.min(SORGU - 1, Math.floor(Math.pow(SORGU, rast())) - 1);
const sirali = sorgular.map((q, i) => [q, i]).sort((a, c) => (a[0] < c[0] ? -1 : a[0] > c[0] ? 1 : 0));
const ikiliLog = Math.ceil(Math.log2(SORGU));
const agacB = [], listeB = [], aralik = [];
for (let i = 0; i < ORNEK; i += 1) {
  const q = sorgular[agirlikliSec()], onek = q.slice(0, 1 + Math.floor(rast() * Math.min(10, q.length)));
  let alt = 0, ust = sirali.length;                   // ikili arama ile aralik basi
  while (alt < ust) { const o = (alt + ust) >> 1; if (sirali[o][0] < onek) alt = o + 1; else ust = o; }
  let n = 0;
  while (alt + n < sirali.length && sirali[alt + n][0].startsWith(onek)) n += 1;
  agacB.push(onek.length + 1);                        // inis + dugumdeki hazir listenin okunmasi
  listeB.push(ikiliLog + n);
  aralik.push([alt, n]);
}
const yuzde = (a, p) => [...a].sort((x, y) => x - y)[Math.floor(p * a.length)];
const ort = (a) => a.reduce((x, y) => x + y, 0) / a.length;
console.log(`\n${"arama".padEnd(32)}${"ortalama birim".padStart(16)}${"p99".padStart(8)}`);
for (const [ad, a] of [["onek agaci (hazir liste okunur)", agacB], ["duz sirali liste (ikili + tarama)", listeB]])
  console.log(`${ad.padEnd(32)}${b(ort(a)).padStart(16)}${String(yuzde(a, 0.99)).padStart(8)}`);

// Guncelleme gecikmesi: sorgularin bir payi zamanla yukseliyor; eski anlik goruntuyle uretilen
// oneri listesi ile o andaki dogru liste karsilastiriliyor.
const YUKSELEN = 0.02, YARILANMA = 3600;
const yukselen = new Uint8Array(SORGU);
for (let i = 0; i < SORGU; i += 1) yukselen[i] = rast() < YUKSELEN ? 1 : 0;
const enUst = (alt, n, f) => {
  const p = [];
  for (let i = 0; i < n; i += 1) { const j = sirali[alt + i][1]; p.push([f(j), j]); }
  p.sort((x, y) => y[0] - x[0]);
  return p.slice(0, K).map((x) => x[1]);
};
console.log(`\n${"gecikme".padStart(9)}${"yukselme kati".padStart(15)}${"ilk 10'da ortusme".padStart(19)}${"basi degisen onek".padStart(19)}`);
for (const gecikme of [600, 3600, 21_600, 86_400]) {
  const kat = 1 + gecikme / YARILANMA;
  let ortusme = 0, bas = 0;
  for (const [alt, n] of aralik) {
    const eski = enUst(alt, n, (j) => siklik[j]);
    const yeni = enUst(alt, n, (j) => siklik[j] * (yukselen[j] ? kat : 1));
    const kume = new Set(yeni);
    ortusme += eski.filter((x) => kume.has(x)).length / Math.max(1, Math.min(K, n));
    if (eski[0] !== yeni[0]) bas += 1;
  }
  console.log(`${`${gecikme} s`.padStart(9)}${b(kat).padStart(15)}${b(ortusme / aralik.length, 4).padStart(19)}` +
    `${b(bas / aralik.length, 4).padStart(19)}`);
}

const TEPE = 8333.33;                                 // hesap blogundan: tepe oneri istegi/s
console.log(`\ntepede birim/s: onek agaci ${b(ort(agacB) * TEPE)}, duz sirali liste ${b(ort(listeB) * TEPE)} ` +
  `(oran ${b(ort(listeB) / ort(agacB))})`);

model: 50.000 farkli sorgu, ortalama uzunluk 15.42 karakter

yapi                                dugum  sorgu basina bayt  VA4 sorguda GB
duz liste                               -              23.42            0.70
onek agaci, derinlik 6              4.588               8.07            0.24
onek agaci, derinlik 8             24.762              43.58            1.31
onek agaci, derinlik 10            86.967             153.06            4.59
onek agaci, derinlik tam          357.080             628.46           18.85

arama                             ortalama birim     p99
onek agaci (hazir liste okunur)             6.10      11
duz sirali liste (ikili + tarama)         1047.32    6593

  gecikme  yukselme kati  ilk 10'da ortusme  basi degisen onek
    600 s           1.17             0.9979             0.0000
   3600 s           2.00             0.9898             0.0015
  21600 s           7.00             0.9546             0.0795
  86400 s          25.00             0.8382             0.1640

tepede birim/s: onek agaci 50833.31, duz sirali liste 8727688.18 (oran 171.69)

Birinci tablo derinliği bir bütçe kararına çeviriyor. Tam derinlikte önek ağacı sorgu başına 628,46 bayt istiyor, VA4 ölçeğinde 18,85 GB — G2’nin 8 GB’lik eşiğinin iki katından fazla. Derinlik 10’a kesildiğinde sorgu başına 153,06 bayta, 4,59 GB‘ye iniyor ve eşiğin altına giriyor. Kapsam daraltmasının karşılığı burada: on karakterden uzun öneke öneri verilmemesi bir kolaylık değil, ağacın bütçeye sığmasını sağlayan kısıttır. Maliyet derinlikle doğrusal büyümüyor — 6’dan 8’e geçiş baytı beş katına, 8’den 10’a geçiş üç buçuk katına çıkarıyor.

İkinci tablo arama maliyetini veriyor. Birim, ziyaret edilen bir düğüm ya da karşılaştırılan bir kayıttır; süre değildir. Önek ağacında ortalama 6,10 birim ve p99’da 11 birim harcanıyor: maliyet sorgu sayısına değil önek uzunluğuna bağlı, bu yüzden en kötü durum da sınırlı. Düz sıralı listede ikili arama aralığın başını buluyor ama eşleşen kayıtların hepsi taranmak zorunda: ortalama 1047,32 birim, p99’da 6593. Tepe yükte fark 50.833,31’e karşı 8.727.688,18 birim/s, yani 171,69 kat.

Üçüncü tablo güncelleme gecikmesinin bedelini veriyor. G3’ün 600 saniyelik penceresinde ilk on önerinin örtüşmesi 0,9979 ve hiçbir öneğin baştaki önerisi değişmiyor. Pencere bir saate çıkınca örtüşme 0,9898, altı saate çıkınca 0,9546 ve öneklerin 0,0795’inde baş değişiyor; günde bir kez kurulan bir yapıda örtüşme 0,8382’ye iniyor ve öneklerin 0,1640’ında en üstteki öneri yanlış oluyor. Tazelik doğrusal bozulmuyor: ilk on dakika neredeyse bedava, ilk gün pahalı.

Tasarım

• Önek ağacı, derinlik 10 (Veri Yapıları, Sözcük Ağaçları). Parametre derinliktir; 4,59 GB ile G2’nin altında kalır.
• Somutlaştırılmış görünüm (Veri Katmanı Ölçekleme, Somutlaştırılmış Görünümler). Her düğümde o önekin ilk 10 önerisi hazır durur; parametre düğüm başına 10 kayıt × 4 bayttır ve arama maliyetini alt ağaç yürüyüşünden 6,10 birime indiren şey budur.
• Çoğaltma (Veri Dağıtımı, Çoğaltma). Her öneri düğümü yapının tam kopyasını bellekte tutar; parametre kopya başına 4,59 GB’dir.
• İtme tabanlı dağıtım (Trafik Katmanı, İtme ve Çekme Tabanlı Dağıtım). Yapı toplu olarak kurulup düğümlere itilir; parametre 600 saniyelik periyot, yani günde 144 koşumdur.
• Görev kuyruğu ve arka plan işi (Uygulama Katmanı, Görev Kuyrukları ve Arka Plan İşleri). Parametre, yeniden kurma koşumu başına taranan 30 milyon sorgudur.
• Kenar önbelleği (Trafik Katmanı, İçerik Dağıtım Ağları). Öneri yanıtı kişiye özel olmadığı için kenarda önbelleklenebilir; parametre, ömrün G3 ile aynı 600 saniye olmasıdır. Önceki vakada bu kalıp tam da bu nedenle kullanılamamıştı.

Bilerek kullanılmayan iki kalıp. Parçalama (Veri Dağıtımı, Parçalama) kullanılmıyor: yapı 4,59 GB ile tek düğüme sığdığı için parçalamak her isteği dağıt–topla’ya çevirir ve p99’u bozardı. Yanında okuma önbelleği (Veri Katmanı Ölçekleme, Yanında Okuma) kullanılmıyor: yapının tamamı zaten bellekte, arkasında ısınacak bir depo yok.

Elenen Alternatif: Düz Sıralı Liste

Alternatif tasarım ağaç kurmaz; sorguları sıralı bir dizide tutar, öneki ikili aramayla bulur ve eşleşen aralığı tarar. Kazandığı şey ölçüldü ve büyüktür: sorgu başına 23,42 bayt, VA4 ölçeğinde 0,70 GB, önek ağacının kullandığının altıda birinden az; üstelik derinlik sınırı gerekmediği için uzun önekler de karşılanır.

Eleme sayısı arama maliyetindedir: ortalama 1047,32 birime karşı 6,10 birim ve tepe yükte 8.727.688,18’e karşı 50.833,31 birim/s. Asıl sorun ortalama değil uçtur — p99’da 6593 birim, çünkü kısa önekler binlerce kayıtla eşleşiyor ve hepsi sıklığa göre sıralanmak zorunda. G1 tuş vuruşları arasına sığma eşiğidir ve p99’u bozan bir yapı bu eşiği taşıyamaz. Alternatif hangi kısıt değişirse kazanır: öneri yalnız uzun öneklerde verilseydi eşleşen aralık küçülür ve iki yapı yaklaşırdı; kararı belirleyen, en kısa öneğin kaç kayıtla eşleştiğidir.

Arıza Davranışı ve Feda Edilen

Yeniden kurma işi durursa yapı donar ve istekler yanıtlanmaya devam eder — arıza belirtisi hata değil, tazeliğin kaymasıdır. Üçüncü tablo bu kaymayı sayıyor: iş bir saat durursa ilk on önerinin örtüşmesi 0,9898, altı saat durursa 0,9546 ve öneklerin 0,0795’inde baştaki öneri yanlış, bir gün durursa 0,8382 ve 0,1640. Zarif bozulma (Dayanıklılık ve Güvenilirlik, Zarif Bozulma) burada kendiliğinden gelir, çünkü okuma yolu kurma yoluna bağlı değildir.

Bir öneri düğümü düşerse hiçbir istek kaybolmaz: her düğüm tam kopya tuttuğu için yük ötekilere dağılır, yalnız kapasite payı azalır. Çoğaltmanın parçalamaya yeğlenmesinin ikinci karşılığı budur.

Feda edilen derinlik ve tazeliktir. On karakterden uzun önek hazır liste bulamaz, istemcinin süzmesine kalır; yeni bir sorgu 600 saniyeye kadar önerilmez. İkisi de bilerek satın alındı: karşılığında yapı tek düğümün belleğine sığdı ve arama maliyeti önek uzunluğuna indi.

Özet

• Tepe öneri isteği saniyede 8333,33, aramanın on iki katı; G2’nin 8 GB’lik eşiği sorgu başına 266,67 baytlık bir bütçeye dönüşüyor.
• Tam derinlikte önek ağacı sorgu başına 628,46 bayt ve 18,85 GB istiyor — bütçenin dışında. Derinlik 10’a kesilince 153,06 bayt ve 4,59 GB oluyor; kapsam daraltması burada karşılığını buluyor.
• Düğümde hazır tutulan ilk 10 öneri, aramayı ortalama 6,10 birime ve p99’da 11 birime indiriyor.
• Düz sıralı liste belleğin altıda birinden azını kullanıyor (0,70 GB) ama ortalama 1047,32, p99’da 6593 birim harcıyor; tepe yükte fark 171,69 kat ve eleme uçtan geliyor.
• Güncelleme gecikmesi doğrusal bozulmuyor: 600 saniyede örtüşme 0,9979 ve baş değişimi 0,0000; bir günde örtüşme 0,8382 ve öneklerin 0,1640’ında en üstteki öneri yanlış.
• Feda edilen, on karakterden uzun öneğin hazır listesi ve 600 saniyelik tazelik penceresidir.

Sonraki Adım

Üç vakada da yanıt bir kayıt oldu: bir hedef bağlantı, bir gönderi listesi, bir öneri listesi. Taşınan bayt küçüktü ve pahalı kalem hesap ya da bellekti; ağ hiç kısıt olmadı. Bir sonraki vakada bu değişir: aynı sistem hem birkaç yüz baytlık kişiye özel yanıtlar hem de her istekte tekrar gönderilen büyük ve değişmeyen dosyalar taşır. İkisi aynı yoldan geçtiğinde biri ötekinin kuyruğunu bozar. Soru, iki trafiğin nereden ayrılacağı ve ayrımın kökene ulaşan istek sayısına ve taşınan bayta ne yaptığıdır.