Önbelleksizlik

Bir önceki ders deponun yapısını sorguladı ve bir yazmanın kendi sınıfına hizmet etmeyen payını saydı. Bu dersin sorusu okuma tarafındadır ve önce yanıtlanmış görünür. Veri Katmanı Ölçekleme kursunun önbellek konusu, önbelleğin gerekmediği yeri ölçmüştü: tekrar oranı 1,00 olan dönem taraması için önbellek istek başına 2,00 ek dokunuş getiriyor ve hiçbir şey kazandırmıyordu. Bu ders o ölçümün aynadaki yüzüdür — önbelleğin gerektiği hâlde konmadığı yer. Ama ölçülen nicelik aynı değildir. Orada yinelenen bir okuma sayıldı; burada yinelenen bir hesap sayılır.

Belirti şudur: uygulama katmanının işlemci doluluğu gün sonu penceresinde doyuma yaklaşıyor, oysa depoya inen istek hızı değişmedi. K01’in hesabında depoya ulasan istek/s 138,89 ve önbellek isabeti V9 varsayımıyla 0,90; iki sayı da yerinde duruyor. Yavaşlayan şey depo değil, uygulamanın kendisi.

Aynı Belirti, İki Neden

Birinci neden: istek başına iş gerçekten arttı. Yanıta yeni alanlar girmiştir; seri hâle getirme uzamıştır. Bu, dördüncü dersin ölçtüğü aşırı veri çekmenin işlemci tarafındaki karşılığıdır.

İkinci neden: aynı hesap aynı girdiyle yineleniyor. İstek başına iş hiç değişmemiştir; değişen, aynı işin kaç kez tekrarlandığıdır. Buna önbelleksizlik (no caching) denir ve ders boyunca ölçülen biçimi belleme (memoization) ile giderilir: hesabın sonucu, girdilerinden türetilen bir hesap anahtarına karşı saklanır.

İkisini ayıran ölçüm, çağrıları okuma anahtarına göre değil hesap anahtarına göre tekilleştirmektir. Hesap tekrarı bire yakınsa neden birincidir ve belleme bir şey kazandırmaz; tekrar birden büyükse neden ikincidir. Bu iki tekrar oranı aynı akışta ayrışabilir, ve bu dersin asıl bulgusu odur.

Hesap ve Üç Akış

Ücretlendirme hesabı gerçek bir işlevdir: ağırlık dilimi taranır, sıralı tarife kural listesi yürünür ve sözleşme çarpanı bulunur. Ölçülen nicelik süre değil, koşum sırasında yürütülen adım sayısıdır; süre bu makineye bağlı olurdu, adım sayısı değildir.

KK8 — hesabın biçimi. Sekiz bölge, beş ağırlık dilimi, üç sözleşme sınıfı ve on yedi sıralı tarife kuralı. Gerekçe: M18’in gönderi kitaplığındaki bolge, tarife ve sozlesme alanları bu biçimi verir; kural listesi iç bölge, kaynak bölge ve yakalayıcı olmak üzere üç katmandır. Duyarlılığı üçüncü akışla verilir: ağırlık dilimlenmeden anahtara girerse tekrar çöker. Bu varsayım K01’in tablosuna eklenmez.

// hesap/tarife.mjs — ucretlendirme hesabi ve uc akis. Sayaclar gercek kosum sirasinda artar;
// olculen nicelik sure degil, yurutulen adim sayisidir.
export const BOLGE = 8;
export const DILIM = [1, 5, 20, 50, Infinity];          // agirlik dilimi ust sinirlari
export const SOZLESME = ["standart", "sozlesmeli", "toplu"];

export const KURAL = [];
for (let k = 1; k <= BOLGE; k += 1) KURAL.push({ k: `B${k}`, h: `B${k}`, carpan: 1.0 });
for (let k = 1; k <= BOLGE; k += 1) KURAL.push({ k: `B${k}`, h: "*", carpan: 1.0 + k / 10 });
KURAL.push({ k: "*", h: "*", carpan: 2.5 });            // yakalayici kural

export const sayac = { hesap: 0, anahtar: 0, arama: 0 };
const sifirla = () => { sayac.hesap = 0; sayac.anahtar = 0; sayac.arama = 0; };

// Hesabin kendisi: dilim taranir, kural listesi sirayla yurunur, sozlesme carpani bulunur.
export function ucret(g) {
  let d = 0;
  while (DILIM[d] < g.agirlik) { sayac.hesap += 1; d += 1; }
  let carpan = 0;
  for (const kural of KURAL) {
    sayac.hesap += 1;
    if ((kural.k === "*" || kural.k === g.kaynak) && (kural.h === "*" || kural.h === g.hedef)) {
      carpan = kural.carpan; break;
    }
  }
  let s = 0;
  while (SOZLESME[s] !== g.sozlesme) { sayac.hesap += 1; s += 1; }
  sayac.hesap += 1;
  return carpan * (d + 1) * (1 + s / 4);
}

// Hesap anahtari yalniz belleme icin kurulur; dort alan okunur, dilim ayrica taranir.
export function anahtar(g) {
  let d = 0;
  while (DILIM[d] < g.agirlik) { sayac.anahtar += 1; d += 1; }
  sayac.anahtar += 3;
  return g.surekli ? `${g.kaynak}>${g.hedef}|${g.agirlik}|${g.sozlesme}`
                   : `${g.kaynak}>${g.hedef}|${d}|${g.sozlesme}`;
}

// 32 bit tam sayi aritmetigiyle tohumlu uretec; Math.imul kesinlik kaybini onler.
export function rastgeleUretec(tohum) {
  let s = tohum >>> 0;
  return () => ((s = (Math.imul(s, 1664525) + 1013904223) >>> 0) / 4294967296);
}

// Donem taramasi: her satici-gun kaydi bir kez okunur (okuma tekrari 1,00), ama hesabin
// girdileri kucuk bir kumeden gelir. `surekli` acikken agirlik dilimlenmeden anahtara girer.
export function donemAkisi(kayit, { surekli = false, tohum = 20260730 } = {}) {
  const rast = rastgeleUretec(tohum);
  return Array.from({ length: kayit }, (_, i) => ({
    okuma: `donem:${i + 1}`, surekli,
    kaynak: `B${Math.floor(rast() * BOLGE) + 1}`,
    hedef: `B${Math.floor(rast() * BOLGE) + 1}`,
    agirlik: surekli ? Math.round(rast() * 60000) / 1000 : [0.5, 3, 12, 35, 80][Math.floor(rast() * 5)],
    sozlesme: SOZLESME[Math.floor(rast() * SOZLESME.length)],
  }));
}

// Takip sorgusu: ayni gonderi obek obek sorulur; hesap girdileri gonderinin kendisinden gelir.
export function takipAkisi(istek, calismaKumesi = 1000, obek = 10, tohum = 4242) {
  const rast = rastgeleUretec(tohum);
  const gonderi = (no) => {
    const r = rastgeleUretec(no * 7919 + 13);
    return { okuma: `takip:${no}`, surekli: false, kaynak: `B${Math.floor(r() * BOLGE) + 1}`,
      hedef: `B${Math.floor(r() * BOLGE) + 1}`, agirlik: [0.5, 3, 12, 35, 80][Math.floor(r() * 5)],
      sozlesme: SOZLESME[Math.floor(r() * SOZLESME.length)] };
  };
  let sonraki = 1;
  const etkin = Array.from({ length: calismaKumesi }, () => ({ no: sonraki++, kalan: obek }));
  return Array.from({ length: istek }, () => {
    const j = Math.floor(rast() * etkin.length);
    const g = gonderi(etkin[j].no);
    if ((etkin[j].kalan -= 1) === 0) etkin[j] = { no: sonraki++, kalan: obek };
    return g;
  });
}

export function onbelleksiz(akis) {
  sifirla();
  for (const g of akis) ucret(g);
  return { ...sayac, girdi: 0 };
}

export function bellemeli(akis) {
  sifirla();
  const m = new Map();
  for (const g of akis) {
    const a = anahtar(g);
    sayac.arama += 1;
    if (m.has(a)) continue;
    m.set(a, ucret(g));
  }
  return { ...sayac, girdi: m.size };
}

// hesap/olcum.mjs — okuma tekrari ile hesap tekrarinin ayrilmasi ve bellemenin karsiligi
import { ucret, anahtar, donemAkisi, takipAkisi, onbelleksiz, bellemeli } from "./tarife.mjs";

const KAYIT = 120_000;            // K01: donem satici-gun
const ISTEK = 200_000;            // K01: 480 s x 416,67 istek/s tepe okuma

// Sutun genisligi tek yerden gelir; baslik ile satir hep hizali kalir.
const EN = [22, 8, 13, 15, 13, 15];
const yaz = (h) => console.log(h.map((x, i) => (i ? String(x).padStart(EN[i]) : String(x).padEnd(EN[i]))).join(" "));
const cizgi = () => console.log(EN.map((n) => "-".repeat(n)).join(" "));

const AKIS = [
  ["donem taramasi", donemAkisi(KAYIT)],
  ["takip sorgusu", takipAkisi(ISTEK)],
  ["donem, surekli agirlik", donemAkisi(KAYIT, { surekli: true })],
];

yaz(["akis", "cagri", "tekil okuma", "okuma tekrari", "tekil hesap", "hesap tekrari"]);
cizgi();
const olcum = [];
for (const [ad, akis] of AKIS) {
  const o = onbelleksiz(akis);
  const b = bellemeli(akis);
  const tekilOkuma = new Set(akis.map((g) => g.okuma)).size;
  olcum.push([ad, akis.length, o, b]);
  yaz([ad, akis.length, tekilOkuma, (akis.length / tekilOkuma).toFixed(2), b.girdi,
    (akis.length / b.girdi).toFixed(2)]);
}

console.log();
yaz(["akis", "adim yok", "adim belleme", "oran", "adim/cagri", "belleme girdisi"]);
cizgi();
for (const [ad, n, o, b] of olcum) {
  const bt = b.hesap + b.anahtar + b.arama;
  yaz([ad, o.hesap, bt, (o.hesap / bt).toFixed(2), (o.hesap / n).toFixed(2), b.girdi]);
}

// Basabas noktasi olculen ortalamalardan cikar: C adim hesap, K adim anahtar, L adim arama.
console.log();
yaz(["akis", "C", "K", "L", "basabas tekrar", "olculen tekrar"]);
cizgi();
for (const [ad, n, o, b] of olcum) {
  const [C, K, L] = [o.hesap / n, b.anahtar / n, b.arama / n];
  yaz([ad, C.toFixed(2), K.toFixed(2), L.toFixed(2),
    (C / (C - K - L)).toFixed(2), (n / b.girdi).toFixed(2)]);
}

// KK9: tarife revizyonu donemin ortasinda yururluge giriyor. Anahtar surumu icermezse
// bellemeden donen deger revizyondan sonraki kayitlar icin yanlistir; yanlislar sayilir.
const REVIZYON = 1.05;
const surumlu = donemAkisi(KAYIT).map((g, i) => ({ ...g, surum: i < KAYIT / 2 ? 1 : 2 }));
const dogruDeger = (g) => ucret(g) * (g.surum === 2 ? REVIZYON : 1);
console.log();
for (const eksik of [true, false]) {
  const m = new Map();
  let yanlis = 0;
  for (const g of surumlu) {
    const a = eksik ? anahtar(g) : `${anahtar(g)}|s${g.surum}`;
    if (!m.has(a)) m.set(a, dogruDeger(g));
    if (Math.abs(m.get(a) - dogruDeger(g)) > 1e-9) yanlis += 1;
  }
  console.log(`anahtar surumu ${eksik ? "icermiyor" : "iceriyor "}: belleme girdisi ${String(m.size).padStart(6)},` +
    ` yanlis sonuc ${String(yanlis).padStart(6)}, yanlis orani ${(yanlis / KAYIT).toFixed(4)}`);
}

akis                      cagri   tekil okuma   okuma tekrari   tekil hesap   hesap tekrari
---------------------- -------- ------------- --------------- ------------- ---------------
donem taramasi           120000        120000            1.00           960          125.00
takip sorgusu            200000         20444            9.78           960          208.33
donem, surekli agirlik   120000        120000            1.00        119365            1.01

akis                   adim yok  adim belleme            oran    adim/cagri belleme girdisi
---------------------- -------- ------------- --------------- ------------- ---------------
donem taramasi          1860493        734534            2.53         15.50             960
takip sorgusu           3102366       1214858            2.55         15.51             960
donem, surekli agirlik  1948593       2745984            0.71         16.24          119365

akis                          C             K               L basabas tekrar  olculen tekrar
---------------------- -------- ------------- --------------- ------------- ---------------
donem taramasi            15.50          5.00            1.00          1.63          125.00
takip sorgusu             15.51          5.00            1.00          1.63          208.33
donem, surekli agirlik    16.24          5.73            1.00          1.71            1.01

anahtar surumu icermiyor: belleme girdisi    960, yanlis sonuc  60000, yanlis orani 0.5000
anahtar surumu iceriyor : belleme girdisi   1920, yanlis sonuc      0, yanlis orani 0.0000

Adım sayıları ve tekil anahtar sayıları ölçüm sınıfındadır: koşum sırasında sayılmışlardır. Çağrı sayıları K01’den gelen hesap, hesabın biçimi varsayım sınıfındadır.

Okuma Tekrarı Hesap Tekrarını Söylemiyor

İlk tablonun ilk satırı bu dersin gerekçesidir. Dönem taramasında okuma tekrarı 1,00: her satıcı-gün kaydı bir kez okunur ve bir daha okunmaz. Veri Katmanı Ölçekleme kursu bu satır için doğru kararı vermişti — bu akışa okuma önbelleği konmaz. Aynı akışın hesap tekrarı ise 125,00: 120.000 kayıt yalnız 960 farklı hesap anahtarına düşüyor, çünkü ücret gönderinin kendisine değil bölge çiftine, ağırlık dilimine ve sözleşme sınıfına bağlıdır. Bir akış hem okuma önbelleğini hak etmeyebilir hem de her kaydında yinelenen bir hesap taşıyabilir; iki ölçü aynı akışta ayrışır.

Takip sorgusunda ikisi de büyük: okuma tekrarı 9,78, hesap tekrarı 208,33. Bu akışta okuma önbelleği hesabın bir bölümünü zaten önler; önbelleksizlik burada ikinci bir kat olarak durur.

Üçüncü satır sınırı gösteriyor. Ağırlık dilimlenmeden anahtara girdiğinde 120.000 kayıt 119.365 farklı anahtar üretiyor ve hesap tekrarı 1,01’e iniyor. Hesabın kendisi değişmedi; değişen, anahtarın ayırt ettiği şeyin inceliği.

Bellemenin Tavanı

İkinci tablo kazancı adım cinsinden veriyor. Dönem taramasında önbelleksiz koşum 1.860.493 adım yürütüyor, bellemeli koşum 734.534: oran 2,53. Kazanç 125 katlık tekrarla orantılı değil ve nedeni üçüncü tabloda: hesap çağrı başına ortalama 15,50 adım, ama hesap anahtarını kurmak her çağrıda 5,00 adım ve aramanın kendisi 1,00 adım. Belleme tekrarları tümüyle ortadan kaldırsa bile çağrı başına 6 adım ödenmeye devam eder. Kazancın tavanı bu yüzden 15,50 / 6,00, yani 2,58’dir; ölçülen 2,53 o tavanın hemen altındadır.

Bu, bellemenin ölçüsünü tersine çevirir. Kazancı belirleyen şey tekrar oranı değil, hesabın anahtarına oranıdır. Tekrar oranı yalnız tavana ne kadar yaklaşıldığını söyler.

Üçüncü tablo başabaş noktasını veriyor. Ölçülen üç maliyetten çıkan eşik $C / (C - K - L)$ biçimindedir ve dönem taraması için 1,63: hesap tekrarı bu değerin üstündeyse belleme öder. Ölçülen tekrar 125,00 olduğuna göre fazlasıyla öder. Sürekli ağırlık akışında eşik 1,71 ve ölçülen tekrar 1,01; belleme orada zarardadır — oran 0,71, yani bellemeli koşum önbelleksizden 1,41 kat daha çok adım yürütüyor.

Karşılığında Büyüyen

Belleme iki şeyi büyütür ve ikisi de sayılabilir.

Bellek. Dönem taramasında 960 girdi tutulur; sürekli ağırlık akışında 119.365. İkinci sayı, kazancın olmadığı yerde bedelin nasıl patladığını gösterir: kayıt başına neredeyse bir girdi. Veri Katmanı Ölçekleme kursunun ölçtüğü 2,00 ek dokunuşun buradaki karşılığı budur.

Yanlışlık yüzeyi. Son iki satır bunu ölçüyor. Tarife dönemin ortasında revize ediliyor (KK9; gerekçe: ücretlendirme aylık dönem üzerinden mutabık kalınır, revizyon dönem içinde yürürlüğe girebilir). Hesap anahtarı sürümü içermediğinde belleme 960 girdi tutuyor ve sonuçların 0,5000‘i yanlış çıkıyor — revizyondan sonraki bütün kayıtlar, revizyondan önce hesaplanmış değeri alıyor. Sürüm anahtara eklendiğinde girdi 1920’ye çıkıyor ve yanlış oranı 0,0000 oluyor. Bedel iki katına çıkan bellektir; kazanılan şey doğruluktur.

Önbelleksiz bir hesap yanlış olamaz. Belleme, doğruluğu anahtarın eksiksizliğine bağlar ve bu bağ ölçülmezse sessizce kopar.

Önbelleksizliğin Doğru Olduğu Koşul

Önbelleksizlik iki koşulda karşıt kalıp değil, doğru tasarımdır ve ikisi de sayıyla verilir.

Hesap tekrarı başabaş eşiğinin altındaysa. Sürekli ağırlık akışında tekrar 1,01, eşik 1,71; belleme adımı 1,41 kat artırır ve 119.365 girdi tutar. Bu akışta hesabı her seferinde yapmak doğrudur.

Hesap anahtardan ucuzsa. Eşik $C / (C - K - L)$ ifadesinde $C \le K + L$ olduğunda tanımsızdır: anahtarı kurmak hesabı yapmaktan pahalıysa hiçbir tekrar oranı bellemeyi kurtarmaz. Bu ölçümde $C$ 15,50 ve $K + L$ 6,00 olduğu için koşul sağlanıyor, ama ucuz bir hesapta sağlanmaz.

Özet

• Belirti uygulama katmanının doyuma yaklaşmasıdır; iki nedeni vardır — istek başına iş büyümüştür ya da aynı hesap yinelenmektedir. Ayıran ölçüm, çağrıların hesap anahtarına göre tekilleştirilmesidir.
• Dönem taramasında okuma tekrarı 1,00 iken hesap tekrarı 125,00: bir akış okuma önbelleğini hak etmezken her kaydında yinelenen bir hesap taşıyabilir. Veri Katmanı Ölçekleme kursunun ölçtüğü örüntünün aynadaki yüzü budur.
• Bellemenin kazancı 2,53 kat ve tavanı 15,50 / 6,00 = 2,58; tavanı belirleyen şey tekrar oranı değil, hesabın anahtar kurma maliyetine oranıdır.
• Başabaş tekrar ölçülen maliyetlerden çıkar ve 1,63’tür; sürekli ağırlık akışında tekrar 1,01, eşik 1,71 ve belleme 0,71 kata düşer — orada önbelleksizlik doğru tasarımdır.
• Bellemenin karşılığı bellek ve yanlışlık yüzeyidir: 960 girdiye karşı 119.365 girdi, ve hesap anahtarı tarife sürümünü içermediğinde sonuçların 0,5000’i yanlış çıkıyor.

Sonraki Adım

Buraya kadarki yedi kalıbın hepsi tek bir sahibin işini ölçtü: sistemin yaptığı fazla iş, kendi akışları arasında paylaştırıldı. Bir varsayım hiç sorulmadı — paylaşılan kaynağı kullanan herkesin aynı taraf olduğu. Gönderi takip ve ücretlendirme servisi tek bir müşteriye hizmet etmiyor; satıcılar aynı uçtan, aynı depodan ve aynı işçi havuzundan geçiyor. Sonraki ders belirtiyi buradan alır: toplam istek hızı hiç değişmediği hâlde bir satıcı grubunun gördüğü gecikme büyüyor. Bunun da iki nedeni vardır ve ikisini ayıran ölçü istek sayısı değildir — bir isteğin kaç birim iş doğurduğu akıştan akışa altmış kat değişir, ve payı istekle sayan bir ölçüm gürültüyü hiç göremez.