Önden Tazeleme

Önceki derste yazma, önbellekteki girdiyi ayakta tuttu. Yazma gelmeyen bir anahtarın girdisi ise yalnız bir nedenle düşer: süresi dolar. Yaşam süresi bu tasarımda isteğe bağlı bir ayar değil, bir güvenlik ağıdır — bu konunun ikinci dersi, kaybolan bir geçersizleştirme iletisinin hiçbir sayaçta görünmeden bayat bir girdi bıraktığını ölçmüştü. Girdiye bir üst sınır süresi konmasının nedeni budur.

O sınırın bir bedeli var ve bu dersin ilk sayısı odur. Süresi dolduğu anda o anahtarı soran istek ıska alır, depoya gider ve bekler. Beklemeyi ortadan kaldırmanın bir yolu vardır: girdi hâlâ geçerliyken, ömrünün sonuna yaklaştığında arka planda yenilenir. Buna önden tazeleme (refresh-ahead) denir. Bu ders eşiği bir parametre olarak oynatır ve iki sayıyı karşı karşıya koyar: kurtarılan bekleme ile boşa giden tazeleme.

Saat ve Ömür

Model süreç içidir ve zamanı bir sayaçla temsil eder: her okuma saati bir tik ilerletir. Tikin saniyeye çevrilmesi K01’in tepe okuma hızıyla yapılır — 416,67 istek/s olduğuna göre bir saniye 416,67 tiktir. Gerçek süre ölçülmez; ölçülen her şey sayımdır ve koşumdan koşuma değişmez.

Yaşam süresi bu derste 5 saniye alınmıştır. B1 (bu dersin varsayımı): takip kaydının önbellek girdisine verilen üst sınır süresi 5 saniyedir. Gerekçe: süre, kaybolan bir geçersizleştirmenin en fazla ne kadar sürebileceğini sınırlar ve bu sürenin ne olması gerektiği bu konunun son dersinin konusudur; burada sabit tutulur ki tek değişken eşik olsun. Duyarlılık son ölçümde yazılıdır. Varsayım K01’in tablosuna eklenmez.

// onbellek/tazele.mjs — onden tazelemenin surec ici modeli. Saat bir sayactir: her okuma
// bir tik ilerletir ve K01'in tepe okuma hizina gore saniyeye cevrilir. Yasam suresi, esik
// orani ve secim kurali parametredir; sure olculmez, islem sayilir.
export const K01 = {
  tepeOkuma: (2_000_000 * 6 / 86_400) * 3,
  tepeYazma: (400_000 * 7 / 86_400) * 3,
};

export function akis({ okuma, oran, calismaKumesi, obek }) {
  let tohum = 20260730;
  const rast = () => ((tohum = (tohum * 1103515245 + 12345) % 2147483648) / 2147483648);
  let sonraki = 1;
  const etkin = Array.from({ length: calismaKumesi }, () => ({ no: sonraki++, kalan: obek }));
  const cikti = [];
  let borc = 0;
  for (let i = 0; i < okuma; i++) {
    const j = Math.floor(rast() * etkin.length);
    const g = etkin[j];
    cikti.push(["oku", `takip:${g.no}`]);
    if ((g.kalan -= 1) === 0) etkin[j] = { no: sonraki++, kalan: obek };
    for (borc += oran; borc >= 1; borc -= 1)
      cikti.push(["yaz", `takip:${etkin[Math.floor(rast() * etkin.length)].no}`]);
  }
  return cikti;
}

// esik: girdinin kalan omru yasam suresinin bu orani altina duserse okuma sirasinda
// arkadan tazelenir. esik = 0 onden tazeleme yok demektir.
// enAzGorulme: yalniz bu kadar kez okunmus anahtarlar tazelenir (secici tazeleme).
export function kosum(islemler, { kapasite, omur, esik, enAzGorulme = 0 }) {
  const kutu = new Map();                 // anahtar -> { biter, tazelendi }
  const s = { isabet: 0, bekleyen: 0, tazeleme: 0, bosaTazeleme: 0, depoOkuma: 0, depoYazma: 0 };
  const gorulme = new Map();
  let saat = 0;
  const dus = (anahtar) => {
    const g = kutu.get(anahtar);
    if (g && g.tazelendi) s.bosaTazeleme += 1;
    kutu.delete(anahtar);
  };
  const koy = (anahtar, tazelendi) => {
    kutu.delete(anahtar);
    kutu.set(anahtar, { biter: saat + omur, tazelendi });
    if (kutu.size > kapasite) dus(kutu.keys().next().value);
  };
  for (const [tur, anahtar] of islemler) {
    if (tur === "yaz") { s.depoYazma += 1; if (kutu.has(anahtar)) koy(anahtar, false); continue; }
    saat += 1;
    gorulme.set(anahtar, (gorulme.get(anahtar) ?? 0) + 1);
    const g = kutu.get(anahtar);
    if (g === undefined || g.biter <= saat) {
      if (g !== undefined) dus(anahtar);            // suresi dolmus girdi: tazelendiyse bosa gitti
      s.bekleyen += 1; s.depoOkuma += 1;
      koy(anahtar, false);
      continue;
    }
    s.isabet += 1;
    if (g.tazelendi) g.tazelendi = false;           // tazelenen deger okundu: bosa gitmedi
    if (esik > 0 && g.biter - saat <= omur * esik && gorulme.get(anahtar) >= enAzGorulme) {
      s.tazeleme += 1; s.depoOkuma += 1;
      koy(anahtar, true);
    } else {
      kutu.delete(anahtar); kutu.set(anahtar, g);   // en son kullanilan sona alinir
    }
  }
  for (const anahtar of [...kutu.keys()]) dus(anahtar);
  return s;
}

Boşa tazeleme, yenilenen bir girdinin bir daha okunmadan düşmesidir. Model bunu bir bayrakla sayar: tazelenen girdi okunursa bayrak silinir, girdi okunmadan süresi dolar ya da tahliye edilirse boşa tazeleme sayacı artar. Yazma yolu önceki dersin kararını sürdürür — içinden yazma — bu yüzden yazma girdiyi düşürmez, ömrünü yeniden başlatır.

Eşiğin Oynatılması

// onbellek/esik.mjs — esik orani oynatilinca kurtarilan bekleme ile bosa giden tazeleme
import { akis, kosum, K01 } from "./tazele.mjs";

const OKUMA = 200_000, KAPASITE = 2000;
const ORAN = K01.tepeYazma / K01.tepeOkuma;
const OMUR_SN = 5, OMUR = Math.round(OMUR_SN * K01.tepeOkuma);   // tik cinsinden yasam suresi
const islemler = akis({ okuma: OKUMA, oran: ORAN, calismaKumesi: 1000, obek: 10 });

console.log(`okuma ${OKUMA}, kapasite ${KAPASITE}, yasam suresi ${OMUR_SN} s = ${OMUR} okuma tiki`);
console.log(`bir tik = 1/${K01.tepeOkuma.toFixed(2)} s (K01 tepe okuma hizi)\n`);
console.log("esik  isabet  bekleyen  tazeleme  bosa tazeleme  bosa orani  depo okuma  onbellek arkasi/s  depoya ulasan/s");
console.log("----- ------ --------- --------- -------------- ----------- ----------- ------------------ ---------------");
for (const esik of [0, 0.1, 0.25, 0.5, 1]) {
  const r = kosum(islemler, { kapasite: KAPASITE, omur: OMUR, esik });
  const arka = K01.tepeOkuma * (r.depoOkuma / OKUMA);
  console.log(`${esik.toFixed(2).padStart(5)} ${(r.isabet / OKUMA).toFixed(4).padStart(6)} ` +
    `${String(r.bekleyen).padStart(9)} ${String(r.tazeleme).padStart(9)} ${String(r.bosaTazeleme).padStart(14)} ` +
    `${(r.tazeleme === 0 ? 0 : r.bosaTazeleme / r.tazeleme).toFixed(4).padStart(11)} ` +
    `${String(r.depoOkuma).padStart(11)} ${arka.toFixed(2).padStart(18)} ${(arka + K01.tepeYazma).toFixed(2).padStart(15)}`);
}

console.log("\nbosa tazeleme cok okunan anahtari elemekle azalmiyor (esik 0,25):");
console.log("en az gorulme  tazeleme  bosa tazeleme  bosa orani");
for (const enAz of [0, 3, 5, 8]) {
  const r = kosum(islemler, { kapasite: KAPASITE, omur: OMUR, esik: 0.25, enAzGorulme: enAz });
  console.log(`${String(enAz).padStart(13)} ${String(r.tazeleme).padStart(9)} ${String(r.bosaTazeleme).padStart(14)} ` +
    `${(r.bosaTazeleme / r.tazeleme).toFixed(4).padStart(11)}`);
}

console.log("\nasil kaldirac yasam suresidir (esik 0 ile 0,25 yan yana):");
console.log("omur (s)  esik 0 isabet  esik 0 depo  esik 0,25 isabet  esik 0,25 depo  esik 0,25 bekleyen  depoya ulasan/s");
for (const sn of [2, 5, 15, 60]) {
  const o = Math.round(sn * K01.tepeOkuma);
  const a = kosum(islemler, { kapasite: KAPASITE, omur: o, esik: 0 });
  const b = kosum(islemler, { kapasite: KAPASITE, omur: o, esik: 0.25 });
  const arka = K01.tepeOkuma * (b.depoOkuma / OKUMA);
  console.log(`${String(sn).padStart(8)} ${(a.isabet / OKUMA).toFixed(4).padStart(14)} ${String(a.depoOkuma).padStart(12)} ` +
    `${(b.isabet / OKUMA).toFixed(4).padStart(17)} ${String(b.depoOkuma).padStart(15)} ${String(b.bekleyen).padStart(19)} ` +
    `${(arka + K01.tepeYazma).toFixed(2).padStart(16)}`);
}

okuma 200000, kapasite 2000, yasam suresi 5 s = 2083 okuma tiki
bir tik = 1/416.67 s (K01 tepe okuma hizi)

esik  isabet  bekleyen  tazeleme  bosa tazeleme  bosa orani  depo okuma  onbellek arkasi/s  depoya ulasan/s
----- ------ --------- --------- -------------- ----------- ----------- ------------------ ---------------
 0.00 0.7109     57815         0              0      0.0000       57815             120.45          217.67
 0.10 0.7363     52731      9780           1862      0.1904       62511             130.23          227.45
 0.25 0.7660     46806     23922           4120      0.1722       70728             147.35          244.57
 0.50 0.7994     40128     50540           8728      0.1727       90668             188.89          286.11
 1.00 0.8286     34270    165730          27825      0.1679      200000             416.67          513.89

bosa tazeleme cok okunan anahtari elemekle azalmiyor (esik 0,25):
en az gorulme  tazeleme  bosa tazeleme  bosa orani
            0     23922           4120      0.1722
            3     22693           4035      0.1778
            5     17116           3662      0.2140
            8      8524           3075      0.3607

asil kaldirac yasam suresidir (esik 0 ile 0,25 yan yana):
omur (s)  esik 0 isabet  esik 0 depo  esik 0,25 isabet  esik 0,25 depo  esik 0,25 bekleyen  depoya ulasan/s
       2         0.4884       102320            0.5263          116205               94735           339.32
       5         0.7109        57815            0.7660           70728               46806           244.57
      15         0.8686        26288            0.8884           31562               22315           162.98
      60         0.8976        20482            0.8977           20510               20461           139.95

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

Sayıların Okunması

İlk satır güvenlik ağının faturasını veriyor. Önceki ders içinden yazmayla 0,9170 isabet ölçmüştü; oraya beş saniyelik bir üst sınır süresi konunca isabet 0,7109‘a düşüyor ve depoya ulasan istek/s 151,04’ten 217,67’ye çıkıyor. Kaybolan geçersizleştirmelere karşı konan sınır, isabetin beşte birine mal oluyor.

Eşik büyüdükçe iki sütun ters yönlere gidiyor. Bekleyen istek 57.815’ten 34.270’e iniyor; buna karşılık tazeleme sayısı sıfırdan 165.730’a çıkıyor ve bunun 27.825’i boşa gidiyor. Boşa oranı eşikten neredeyse bağımsız: beş satırın dördünde 0,17 ile 0,19 arasında. Bunun nedeni yapısaldır — bir tazelemenin boşa gitmesi, o anahtarın bir daha okunmamasıdır ve bu, öbeğin son sorgusunda kaçınılmaz olarak olur. Okunan hiçbir sayaç bir sorgunun sonuncu olduğunu önceden söyleyemez.

İkinci tablo bunu doğruluyor. “Az okunan anahtarları tazeleme” kuralı sezgisel olarak boşa tazelemeyi azaltmalıydı; ölçüm tersini söylüyor. Eşik sekize çekildiğinde tazeleme sayısı 23.922’den 8524’e iniyor ama boşa oranı 0,1722’den 0,3607’ye çıkıyor. Elenen tazelemeler zaten işe yarayanlardı: çok okunmuş bir anahtar öbeğinin sonuna daha yakındır. İsraf, erişimin başında değil sonundadır ve görülme sayısıyla ayrılamaz.

Son satır bu dersin en sert sayısını taşıyor. Eşik 1 alındığında — yani her okuma bir tazeleme tetiklediğinde — isabet oranı 0,8286 gibi saygıdeğer bir yerde duruyor, ama depo okuması 200.000, yani istek sayısının tamamı. depoya ulasan istek/s 513,89: bu, bu konunun ilk dersinde önbelleksiz tasarım için hesaplanan sayının aynısıdır. Önbellek çalışıyor, isabet sayacı doluyor, gösterge iyi görünüyor ve depo tam yükü taşıyor. Yüksek isabet oranı, depo yükü hakkında tek başına hiçbir şey söylemez.

Asıl Kaldıraç

Üçüncü tablo eşiği ömürle yan yana koyuyor ve sıralamayı tersine çeviriyor. Ömür 2 saniyeden 60 saniyeye çıktığında eşiksiz isabet 0,4884’ten 0,8976’ya, depoya ulasan istek/s ise 339,32’den 139,95’e iniyor. Aynı aralıkta eşiğin katkısı sürekli küçülüyor: 2 saniyede isabeti 0,0379 artırıyor, 60 saniyede yalnız 0,0001. Ömür 60 saniyeyken önden tazeleme 28 fazladan depo okuması yapıp bekleyen isteği 20.482’den 20.461’e indiriyor — ölçülebilir ama anlamsız bir kazanç.

Kural buradan çıkıyor: önden tazeleme, yaşam süresinin erişim öbeğine göre kısa kaldığı durumda beklemeyi azaltır. Ömür öbekten uzunsa girdi zaten süresi dolmadan yeniden okunur ve tazelenecek bir şey yoktur. Ömür kısaysa tazeleme işe yarar, ama kurtardığı her bekleme için depoya fazladan okuma bindirir ve o okumaların yaklaşık altıda biri boşa gider.

Bu, önden tazelemeyi bir gecikme aracı yapar, bir yük azaltma aracı değil. K01’in depoya ulasan istek/s satırı bu derste her seferinde yukarı gitti. Bir tasarım kararının hesabı iyileştirmesi zorunlu değildir; ölçülmesi ve ödünleşiminin yazılması zorunludur.

Özet

• Kaybolan geçersizleştirmelere karşı konan beş saniyelik üst sınır süresi isabeti 0,9170’ten 0,7109’a indirdi ve depoya ulasan istek/s satırını 151,04’ten 217,67’ye çıkardı.
• Eşik 0’dan 1’e çıktığında bekleyen istek 57.815’ten 34.270’e indi, tazeleme 165.730’a çıktı ve bunun 27.825’i boşa gitti; boşa oranı eşikten bağımsız biçimde 0,17 civarında kaldı.
• Az okunan anahtarları elemek boşa tazelemeyi azaltmıyor, oranı 0,1722’den 0,3607’ye çıkarıyor: israf erişimin sonundadır ve görülme sayısıyla ayrılamaz.
• Eşik 1 alındığında isabet 0,8286 iken depo okuması 200.000 ve depoya ulasan istek/s 513,89 oluyor — önbelleksiz tasarımın sayısı. Yüksek isabet oranı depo yükü hakkında bir şey söylemez.
• Asıl kaldıraç yaşam süresidir: 2 saniyeden 60 saniyeye çıkınca isabet 0,4884’ten 0,8976’ya, depoya ulasan istek/s 339,32’den 139,95’e iniyor ve önden tazelemenin katkısı 0,0001’e düşer.

Sonraki Adım

Bu 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. Demek ki çalışan bir önbellek, hiç önbellek olmamasıyla aynı yükü üretebiliyor. O zaman ters yönden sorulması gereken bir soru var ve bu konuda henüz hiç sorulmadı: önbellek gerçekten gerekli mi. Buraya kadar her ders bir önbelleğin var olduğunu varsaydı ve yalnız onun nasıl düzenleneceğini tartıştı. Sıradaki ders varsayımı kaldırır: hangi erişim örüntülerinde önbellek eklemek depoya ulasan istek/s satırını hiç değiştirmez, hangi örüntülerde onu yükseltir ve önbelleksiz bir tasarımın gerçekten karşıt kalıp olduğu sınır nerede başlar.