--- title: 'Arama Önerisi' source: 'https://academia.sh/tr/kurslar/vaka-calismalari/arama-onerisi' course: 'Vaka Çalışmaları' language: tr updated: '2026-08-17T18:10:56+00:00' license: 'CC BY-SA 4.0' --- # Arama Önerisi Yanıtın yazma anında hazırlanamadığı bir okuma vakası: önek ağacının bellek ve arama maliyetinin düz listeyle karşılaştırılması, ağacın derinliğinin bellek bütçesinden bir sayı olarak seçilmesi, güncelleme gecikmesinin ilk on öneride ürettiği değişimin ölçülmesi ve donan bir yapının bayatlıkla bozulması. Ö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ı ```js // 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**. ```js // 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.