Önbelleksiz Tasarım Karşıt Kalıbı

Önceki dersin son sayısı rahatsız edici bir soru bıraktı: isabet oranı 0,8286 iken depo, önbellek hiç yokmuş gibi 513,89 istek/s taşıyordu. Buraya kadar her ders bir önbelleğin var olduğunu varsaydı ve yalnız onun nasıl düzenleneceğini tartıştı. Bu ders varsayımı kaldırır ve soruyu ters yönden sorar: önbellek gerçekten gerekli mi.

Sorunun iki yanlış yanıtı vardır ve ikisi de aynı kusurdan doğar. Birincisi önbelleksiz tasarım karşıt kalıbı: erişim örüntüsü tekrarla dolu olduğu hâlde her okumanın depoya gitmesi. İkincisi bunun aynası: tekrar barındırmayan bir yola önbellek konması. İkisi de erişim örüntüsünün ölçülmemesinin sonucudur, bu yüzden bu ders örüntüyü ölçer.

Dört Örüntü

Model süreç içidir: aynı önbellek dört ayrı akışla koşturulur, sayaçlar açıktır. Akışların hepsi K01’in üç akışından türetilmiştir — takip sorgusu, durum olayı yazması ve gün sonu ücretlendirme taraması — ve hızları K01’in hesabından gelir: tepe okuma 416,67 istek/s, toplu tarama 833,33 kayıt/s. Pencere yine 480 saniyedir.

// onbellek/oruntu.mjs — ayni onbellek dort erisim oruntusuyle kosturulur. Onbellek ve
// depo birer modul; sayaclar aciktir. Oruntuler K01'in uc akisindan turetilmistir.
export const K01 = {
  tepeOkuma: (2_000_000 * 6 / 86_400) * 3,      // 416,67 istek/s
  tepeYazma: (400_000 * 7 / 86_400) * 3,        // 97,22 istek/s
  topluTarama: (30 * 400_000) / (4 * 3600),     // 833,33 kayit/s
};
export const PENCERE = 480;                      // saniye

function rastgeleUretec(tohum) {
  return () => ((tohum = (tohum * 1103515245 + 12345) % 2147483648) / 2147483648);
}

// Takip sorgusu: bir gonderinin sorgulari `obek` uzunlugunda gelir.
export function takipAkisi(istek, calismaKumesi = 1000, obek = 10) {
  const rast = rastgeleUretec(20260730);
  let sonraki = 1;
  const etkin = Array.from({ length: calismaKumesi }, () => ({ no: sonraki++, kalan: obek }));
  const cikti = [];
  for (let i = 0; i < istek; i++) {
    const j = Math.floor(rast() * etkin.length);
    cikti.push(["oku", `takip:${etkin[j].no}`]);
    if ((etkin[j].kalan -= 1) === 0) etkin[j] = { no: sonraki++, kalan: obek };
  }
  return cikti;
}

// Ucretlendirme taramasi: her satici-gun kaydi bir kez okunur, sirayla.
export function taramaAkisi(kayit) {
  return Array.from({ length: kayit }, (_, i) => ["oku", `donem:${i + 1}`]);
}

// Sicak yazma: kucuk bir anahtar uzayina okumadan cok yazma duser.
export function sicakYazmaAkisi(islem, anahtar = 40, yazmaPayi = 0.7) {
  const rast = rastgeleUretec(4242);
  return Array.from({ length: islem }, () => {
    const a = `bolge:${Math.floor(rast() * anahtar) + 1}`;
    return [rast() < yazmaPayi ? "yaz" : "oku", a];
  });
}

// Iki akisi sirayla ic ice gecirir: her `araN` takip istegi arasina `sokN` tarama istegi.
export function karistir(a, b, araN, sokN) {
  const cikti = [];
  let i = 0, j = 0;
  while (i < a.length || j < b.length) {
    for (let k = 0; k < araN && i < a.length; k++) cikti.push(a[i++]);
    for (let k = 0; k < sokN && j < b.length; k++) cikti.push(b[j++]);
  }
  return cikti;
}

// atla: bu ad alanindaki anahtarlar onbellege hic ugramaz.
export function kosum(islemler, { kapasite, atla = null }) {
  const m = new Map();
  const s = { istek: 0, okuma: 0, isabet: 0, depoOkuma: 0, depoYazma: 0, dokunus: 0, takipIstek: 0, takipIsabet: 0 };
  for (const [tur, anahtar] of islemler) {
    s.istek += 1;
    const takip = anahtar.startsWith("takip:");
    if (takip) s.takipIstek += 1;
    if (atla !== null && anahtar.startsWith(atla)) {
      if (tur === "oku") s.depoOkuma += 1; else s.depoYazma += 1;
      s.dokunus += 1;
      continue;
    }
    if (tur === "yaz") { s.depoYazma += 1; s.dokunus += 2; m.delete(anahtar); continue; }
    s.okuma += 1; s.dokunus += 1;
    if (m.has(anahtar)) {
      s.isabet += 1; if (takip) s.takipIsabet += 1;
      const d = m.get(anahtar); m.delete(anahtar); m.set(anahtar, d);
      continue;
    }
    s.depoOkuma += 1; s.dokunus += 2;
    m.set(anahtar, 1);
    if (m.size > kapasite) m.delete(m.keys().next().value);
  }
  return s;
}

// onbellek/karar.mjs — dort oruntude onbellegin kazandirdigi ve kaybettirdigi
import { K01, PENCERE, takipAkisi, taramaAkisi, sicakYazmaAkisi, karistir, kosum } from "./oruntu.mjs";

const KAPASITE = 2000;
const OKUMA = Math.round(K01.tepeOkuma * PENCERE);
const TARAMA = Math.round(K01.topluTarama * PENCERE);

const takip = takipAkisi(OKUMA);
const tarama = taramaAkisi(TARAMA);
const sicak = sicakYazmaAkisi(OKUMA);

console.log(`pencere ${PENCERE} s: takip sorgusu ${OKUMA}, donem taramasi ${TARAMA} kayit, kapasite ${KAPASITE}`);
console.log(`(K01: tepe okuma ${K01.tepeOkuma.toFixed(2)}/s, toplu tarama ${K01.topluTarama.toFixed(2)} kayit/s)\n`);

const ORUNTU = [
  ["takip sorgusu", takip],
  ["donem taramasi", tarama],
  ["sicak yazma", sicak],
  ["takip + tarama", karistir(takip, tarama, 1, 2)],
];

console.log("oruntu           istek  okuma  tekil anahtar  tekrar  isabet  depo erisimi  onbelleksiz  fark  ek dokunus/istek");
console.log("--------------- ------ ------ -------------- ------- ------- ------------- ----------- ----- -----------------");
for (const [ad, akis] of ORUNTU) {
  const r = kosum(akis, { kapasite: KAPASITE });
  const tekil = new Set(akis.map(([, a]) => a)).size;
  const depo = r.depoOkuma + r.depoYazma;
  console.log(`${ad.padEnd(15)} ${String(r.istek).padStart(6)} ${String(r.okuma).padStart(6)} ${String(tekil).padStart(14)} ` +
    `${(r.istek / tekil).toFixed(2).padStart(7)} ${(r.isabet / r.okuma).toFixed(4).padStart(7)} ` +
    `${String(depo).padStart(13)} ${String(r.istek).padStart(11)} ${(depo - r.istek).toString().padStart(5)} ` +
    `${((r.dokunus - r.istek) / r.istek).toFixed(2).padStart(17)}`);
}

console.log("\ntoplu tarama ayni onbellekten gecerse takip sorgusuna ne olur:");
const birlikte = karistir(takip, tarama, 1, 2);
const gecen = kosum(birlikte, { kapasite: KAPASITE });
const atlayan = kosum(birlikte, { kapasite: KAPASITE, atla: "donem:" });
const yalniz = kosum(takip, { kapasite: KAPASITE });
const satir = (ad, r) => {
  const depo = r.depoOkuma + r.depoYazma;
  const takipS = K01.tepeOkuma * (1 - r.takipIsabet / r.takipIstek);
  console.log(`${ad.padEnd(28)} ${(r.takipIsabet / r.takipIstek).toFixed(4).padStart(14)} ` +
    `${String(depo).padStart(13)} ${(depo / PENCERE).toFixed(2).padStart(15)} ${(takipS + K01.tepeYazma).toFixed(2).padStart(16)}`);
};
console.log("durum                          takip isabeti  depo erisimi  depo erisimi/s  depoya ulasan/s");
console.log("---------------------------- --------------- ------------- --------------- ----------------");
satir("tarama yok", yalniz);
satir("tarama onbellekten geciyor", gecen);
satir("tarama onbellegi atliyor", atlayan);
console.log(`\ntaramanin onbellekten gecmesinin bedeli = ${(gecen.depoOkuma + gecen.depoYazma) - (atlayan.depoOkuma + atlayan.depoYazma)} ek depo erisimi`);
console.log(`takip isabetindeki kayip = ${((atlayan.takipIsabet / atlayan.takipIstek) - (gecen.takipIsabet / gecen.takipIstek)).toFixed(4)}`);

pencere 480 s: takip sorgusu 200000, donem taramasi 400000 kayit, kapasite 2000
(K01: tepe okuma 416.67/s, toplu tarama 833.33 kayit/s)

oruntu           istek  okuma  tekil anahtar  tekrar  isabet  depo erisimi  onbelleksiz  fark  ek dokunus/istek
--------------- ------ ------ -------------- ------- ------- ------------- ----------- ----- -----------------
takip sorgusu   200000 200000          20477    9.77  0.8976         20483      200000 -179517              0.20
donem taramasi  400000 400000         400000    1.00  0.0000        400000      400000     0              2.00
sicak yazma     200000  60078             40 5000.00  0.3001        181968      200000 -18032              1.12
takip + tarama  600000 600000         420477    1.43  0.1571        505735      600000 -94265              1.69

toplu tarama ayni onbellekten gecerse takip sorgusuna ne olur:
durum                          takip isabeti  depo erisimi  depo erisimi/s  depoya ulasan/s
---------------------------- --------------- ------------- --------------- ----------------
tarama yok                           0.8976         20483           42.67           139.90
tarama onbellekten geciyor           0.4713        505735         1053.61           317.50
tarama onbellegi atliyor             0.8976        420483          876.01           139.90

taramanin onbellekten gecmesinin bedeli = 85252 ek depo erisimi
takip isabetindeki kayip = 0.4263

Bütün sayılar hesap sınıfındadır: belirlenimli akışlar üzerinde sayılmışlardır.

Karşıt Kalıbın Bedeli

İlk satır karşıt kalıbı tanımlıyor. Takip sorgusunda tekrar oranı 9,77: her takip numarası pencerede ortalama on kez sorulur. Önbelleksiz tasarımda depo 200.000 erişim görür, önbellekli tasarımda 20.483 — fark 179.517 erişim, yani onda dokuzu gereksizdi. K01’in hesabında bu, depoya ulasan istek/s satırının 513,89 ile 139,90 arasındaki farkıdır: 3,67 kat. Önbelleksiz tasarım, deponun bu katsayıyla boyutlandırılmasını gerektirir ve ondan kaçınmanın bedeli istek başına 0,20 ek dokunuştur.

İkinci satır aynanın öteki yüzü. Dönem taraması 400.000 satıcı-gün kaydını okur ve hepsi farklıdır; tekrar oranı tam olarak 1,00, isabet 0,0000. Önbellekli ve önbelleksiz depo erişimi eşit — fark sıfır. Kazanılan hiçbir şey yokken istek başına 2,00 ek dokunuş ödenir: bir yoklama ve bir yerleştirme. Bu örüntüde önbelleksiz tasarım karşıt kalıp değil, doğru tasarımdır.

Üçüncü satır tekrarın tek başına yetmediğini gösteriyor. Sıcak yazma örüntüsünde kırk anahtar 200.000 işlem görüyor; tekrar oranı 5000, bu tablodaki en yüksek değer. Buna karşılık isabet yalnız 0,3001. Neden, işlemlerin 140.000’inin yazma olmasıdır: her yazma girdiyi düşürür ve sonraki okuma ıska alır. Yüksek tekrar oranı bir önbelleği haklı çıkarmaz; haklı çıkaran şey, tekrarın iki yazma arasına sığmasıdır.

Bir Örüntü Başka Bir Örüntüyü Bozar

Dördüncü satır ile ikinci tablo aynı olguyu iki açıdan gösteriyor. Takip sorgusu ile dönem taraması aynı önbellekten geçtiğinde birleşik isabet 0,1571’e, takip sorgusunun kendi isabeti 0,8976’dan 0,4713’e iniyor. Taramanın 400.000 farklı anahtarı, kapasitesi 2000 olan önbelleğe sürekli girip çıkıyor ve girerken takip girdilerini dışarı itiyor.

Sayı burada işareti değiştiriyor. Tarama önbelleği atladığında toplam depo erişimi 420.483, önbellekten geçtiğinde 505.735: aradaki 85.252 erişim, önbelleğin eklediği yüktür. depoya ulasan istek/s 139,90’dan 317,50’ye çıkıyor. Bir önbellek, yanlış örüntüye açıldığında koruduğu şeyi bozar.

Çözüm önbelleği kaldırmak değil, tarama akışını ondan geçirmemektir. Son satır bunu ölçüyor: donem: ad alanı atlandığında takip isabeti hiç düşmeden 0,8976’da kalıyor ve depoya ulasan istek/s 139,90’a geri dönüyor. Tarama yine 400.000 kayıt okuyor — o okumalar zaten kaçınılmazdı — ama artık kimsenin çalışma kümesini tahliye etmiyor. K01’in gün sonu işini ayrı bir dört saatlik pencereye koymasının gerekçesi bu tabloda görünür hâle geliyor.

Karar Kuralı

Dört ölçüm birlikte okunduğunda önbellek kararı dört koşula iner ve dördü de sayılabilir.

Tekrar oranı birden büyük olmalı. Pencerede istek sayısının tekil anahtar sayısına oranı 1,00 ise kazanılacak hiçbir şey yoktur; dönem taraması bu koşulda kalır.

Tekrar iki yazma arasına sığmalı. Sıcak yazma örüntüsünde tekrar 5000 ama okuma başına düşen yazma oranı yüksek olduğu için isabet 0,3001’de kalıyor. Ölçülecek nicelik tekrar değil, bir girdinin ömrü boyunca aldığı okuma sayısıdır.

Çalışma kümesi kapasiteye sığmalı. Bu konunun ilk dersi kapasitesi 2000 olan bir önbelleğin 1000 gönderilik çalışma kümesini karşıladığını ölçmüştü; kapasite altına inildiğinde katmanlar artıklarını birbirine sızdırır.

Aynı önbelleği paylaşan başka bir örüntü çalışma kümesini tahliye etmemeli. Bu koşul ötekilerin hepsi sağlansa bile tek başına bozulabilir ve bozulduğunda önbellek net zarara geçer: 85.252 ek depo erişimi.

Dördü sağlanmıyorsa önbelleksiz tasarım karşıt kalıp değildir; ölçülmeden verilmiş bir önbellek kararı ise her durumda öyledir.

Özet

• Takip sorgusunda tekrar oranı 9,77 ve önbelleksiz tasarım depoya 200.000 erişim bindiriyor; önbellekli tasarımda 20.483. K01’in depoya ulasan istek/s satırında bu 513,89 ile 139,90 arasındaki 3,67 katlık farktır.
• Dönem taramasında tekrar oranı 1,00, isabet 0,0000 ve depo erişimi iki tasarımda da 400.000; kazanç sıfırken istek başına 2,00 ek dokunuş ödenir.
• Sıcak yazma örüntüsünde tekrar oranı 5000 olduğu hâlde isabet 0,3001: yüksek tekrar bir önbelleği haklı çıkarmaz, tekrarın iki yazma arasına sığması çıkarır.
• Tarama aynı önbellekten geçtiğinde takip isabeti 0,8976’dan 0,4713’e iniyor ve toplam depo erişimi 420.483’ten 505.735’e çıkıyor; önbellek 85.252 erişim ekliyor.
• Karar dört koşula iner: tekrar oranı birden büyük, tekrar iki yazma arasına sığıyor, çalışma kümesi kapasiteye sığıyor ve başka bir örüntü onu tahliye etmiyor.

Sonraki Adım

Bu derste önbelleğin gerekli olduğu örüntüler ayrıldı, ama bir soru hep açık kaldı. Önbellekten dönen değer, deponun o andaki değeriyle aynı olmak zorunda değil; ikisinin ayrıldığı süre bu konunun ikinci dersinde bir kez ölçüldü — geçersizleştirme kapatıldığında 105.794 bayat okuma — ve dördüncü dersinde bir parametreye bağlandı: beş saniyelik üst sınır süresi keyfi seçilmişti ve seçimin gerekçesi yazılmamıştı. Sıradaki ders o gerekçeyi kurar. Bayatlığın ne kadarının kabul edilebilir olduğu bir mühendislik tercihi değil, verinin kendisinden çıkan bir sayıdır: bir gönderinin durumu ne sıklıkla değişiyorsa, o değişimden daha kısa bir pencere bayat yanıt üretmez. Sonraki ders pencereyi bu ilişkiden hesaplar, saniyede kaç bayat yanıt kabul edildiğini sayar ve aynı bayatlık bütçesiyle isabetin nereye kadar çıkabileceğini ölçer.