Geçersizleştirme

Önceki dersin son ölçümü bayat bir girdi bıraktı: yazma kuralına uyulduğu hâlde önbellekte eski değer kaldı ve elli okuma boyunca öyle kaldı. O girdiyi düşürecek bir mekanizma olmadıkça sorun kendiliğinden çözülmez.

Önbellekteki bir girdinin düşürülmesine geçersizleştirme (invalidation) denir ve üç ayrı tetikleyicisi vardır. Girdi belirli bir süre sonra kendiliğinden düşebilir, bir olay onu düşürebilir ya da anahtarın kendisi değişerek girdiyi erişilemez kılabilir. Bu ders üçünü aynı iş yükünde koşturur ve her birinin ürettiği bayat okuma sayısını ölçer.

Ölçüm Düzeneği

Şema önceki dersinkidir; üzerine İş Mantığı Yerleşimi konusunda kurulan giden_kutusu tablosu eklenir. Yazma işlemi hem raf sayısını günceller hem de aynı işlemde olay kaydını bu tabloya düşürür.

# kur.sh — onceki dersin semasi, uzerine M16/K04'teki giden kutusu tablosu
rm -f kutuphane.db
sqlite3 kutuphane.db <<'SQL'
CREATE TABLE kitap (kitap_id INTEGER PRIMARY KEY, baslik TEXT NOT NULL,
                    sube_id INTEGER NOT NULL, rafta INTEGER NOT NULL);
CREATE TABLE giden_kutusu (ileti_id INTEGER PRIMARY KEY, govde TEXT NOT NULL,
                           durum TEXT NOT NULL DEFAULT 'bekliyor');
INSERT INTO kitap SELECT n, 'Kitap ' || n, n % 3 + 1, 3
  FROM (WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 60) SELECT n FROM s);
SQL
sqlite3 kutuphane.db "SELECT 'kitap=' || count(*) || ' toplam_rafta=' || sum(rafta) FROM kitap;"

kitap=60 toplam_rafta=180

İş yükü yine 1200 işlemdir. Saat olarak gerçek zaman değil iş yükü adımı kullanılır: her işlem saati bir artırır. Böylece yaşam süresi karşılaştırması makineden bağımsız aynı sayıları üretir; süre birimi milisaniye değil adımdır.

Üç Yol

Üç strateji aynı üç soruya farklı yanıt verir: anahtar nedir, girdi ne kadar yaşar, yazma olduğunda ne yapılır.

// gecersizlestirme.mjs — sure, olay ve surum tabanli gecersizlestirme ayni is yukunde
import { DatabaseSync } from "node:sqlite";
import { copyFileSync, rmSync } from "node:fs";

function isYuku(adet) {                            // %85 okuma, %15 yazma, 12 populer kitap
  let tohum = 20250729;
  const rast = () => ((tohum = (tohum * 1103515245 + 12345) % 2147483648) / 2147483648);
  return Array.from({ length: adet }, () => {
    const yaz = rast() < 0.15;
    return [yaz ? "yaz" : "oku", Math.floor(rast() * 12) + 1, yaz ? (rast() < 0.5 ? -1 : 1) : 0];
  });
}

function kaynakAc(dosya) {
  rmSync(dosya, { force: true });
  copyFileSync("kutuphane.db", dosya);
  const db = new DatabaseSync(dosya);
  const s = { okuma: 0 };
  return {
    s, db,
    oku: (id) => { s.okuma += 1; return db.prepare("SELECT rafta FROM kitap WHERE kitap_id = ?").get(id).rafta; },
    dogru: (id) => db.prepare("SELECT rafta FROM kitap WHERE kitap_id = ?").get(id).rafta,
    yaz(id, delta) {                               // yazma ve olay ayni islemde (giden kutusu)
      db.exec("BEGIN");
      const yeni = Math.max(0, this.dogru(id) + delta);
      db.prepare("UPDATE kitap SET rafta = ? WHERE kitap_id = ?").run(yeni, id);
      db.prepare("INSERT INTO giden_kutusu (govde) VALUES (?)").run(JSON.stringify({ kitapId: id }));
      db.exec("COMMIT");
    },
    kapat: () => db.close(),
  };
}

function kosu(etiket, kurulum) {
  const kaynak = kaynakAc("gecersiz.db");
  const kutu = new Map();                          // anahtar -> { deger, sonGecerlilik }
  const o = { isabet: 0, iska: 0, bayat: 0 };
  let adim = 0;                                    // saat: gercek zaman degil, is yuku adimi
  const strateji = kurulum(kaynak, kutu, () => adim);
  for (const [tur, id, delta] of isYuku(1200)) {
    adim += 1;
    if (tur === "oku") {
      const anahtar = strateji.anahtar(id);
      const girdi = kutu.get(anahtar);
      let deger;
      if (girdi && girdi.sonGecerlilik > adim) { o.isabet += 1; deger = girdi.deger; }
      else { o.iska += 1; deger = kaynak.oku(id); kutu.set(anahtar, { deger, sonGecerlilik: strateji.omur(adim) }); }
      if (deger !== kaynak.dogru(id)) o.bayat += 1;
    } else {
      kaynak.yaz(id, delta);
      strateji.yazildi(id);
    }
    strateji.dongu?.();
  }
  kaynak.kapat();
  rmSync("gecersiz.db", { force: true });
  return `${etiket.padEnd(22)}${[kaynak.s.okuma, o.isabet, o.iska, o.bayat].map((n) => String(n).padStart(10)).join("")}`;
}

// 1) Sure tabanli: yazma onbellege dokunmaz, girdi omru dolunca duser.
const sureTabanli = (omur) => () => ({
  anahtar: (id) => `kitap:${id}`,
  omur: (adim) => adim + omur,
  yazildi: () => {},
});

// 2) Olay tabanli: yazma giden kutusuna dusen olayi uretir, tuketici anahtari siler.
const olayTabanli = (gecikme) => (kaynak, kutu) => {
  let sayim = 0;
  return {
    anahtar: (id) => `kitap:${id}`,
    omur: () => Infinity,
    yazildi: () => {},
    dongu() {                                      // tuketici her `gecikme` adimda bir calisir
      if ((sayim += 1) % gecikme !== 0) return;
      const iletiler = kaynak.db.prepare(
        "SELECT ileti_id, govde FROM giden_kutusu WHERE durum = 'bekliyor'").all();
      for (const i of iletiler) {
        kutu.delete(`kitap:${JSON.parse(i.govde).kitapId}`);
        kaynak.db.prepare("UPDATE giden_kutusu SET durum = 'islendi' WHERE ileti_id = ?").run(i.ileti_id);
      }
    },
  };
};

// 3) Surum tabanli: anahtarin icinde surum var; yazma surumu artirir, eski anahtar erisilemez olur.
const surumTabanli = () => {
  const surum = new Map();
  return {
    anahtar: (id) => `kitap:s${surum.get(id) ?? 1}:${id}`,
    omur: () => Infinity,
    yazildi: (id) => surum.set(id, (surum.get(id) ?? 1) + 1),
  };
};

console.log(["gecersizlestirme", "kay.okuma", "isabet", "iska", "bayat"]
  .map((b, i) => (i === 0 ? b.padEnd(22) : b.padStart(10))).join(""));
console.log(kosu("sure (omur=10)", sureTabanli(10)));
console.log(kosu("sure (omur=50)", sureTabanli(50)));
console.log(kosu("sure (omur=200)", sureTabanli(200)));
console.log(kosu("olay (gecikme=5)", olayTabanli(5)));
console.log(kosu("olay (gecikme=25)", olayTabanli(25)));
console.log(kosu("surum", surumTabanli));

gecersizlestirme       kay.okuma    isabet      iska     bayat
sure (omur=10)               626       399       626        18
sure (omur=50)               232       793       232       147
sure (omur=200)               72       953        72       445
olay (gecikme=5)             155       870       155        14
olay (gecikme=25)            153       872       153        97
surum                        156       869       156         0

Sayıların Söyledikleri

Süre tabanlı satırlar tek bir eğri çiziyor. Yaşam süresi ondan iki yüze çıktığında kaynak okuması 626’dan 72’ye düşüyor, bayat okuma 18’den 445’e çıkıyor. Bu iki sayı aynı düğmenin iki ucudur: yaşam süresi, kaynağa binen yük ile kabul edilen bayatlık arasındaki dönüşüm oranıdır. Sıfıra yaklaştıkça önbellek anlamsızlaşır, büyüdükçe önbellek kendi gerçekliğini kurar.

Olay tabanlı satırlar bu eğriden çıkıyor. Beş adımlık tüketici gecikmesiyle kaynak okuması 155, bayat okuma 14. Aynı bayatlık düzeyi için süre tabanlı yol dört kat fazla kaynak okuması istiyordu. Fark, geçersizleştirmenin nedene bağlanmasından gelir: girdi zaman geçtiği için değil, veri değiştiği için düşer. Değişmeyen anahtar sonsuza kadar önbellekte kalır.

Olay tabanlı yolun zayıflığı ikinci satırda görünüyor. Tüketici gecikmesi beşten yirmi beşe çıktığında bayat okuma 14’ten 97’ye yükseldi. Bayatlık penceresi artık olayın üretilmesiyle işlenmesi arasındaki süredir. Bu, bir teslim sorunudur: olay üretildi ve kaydedildi, ama henüz kimse okumadı.

Sürüm tabanlı satırda bayat okuma sıfırdır. Yazma anahtarı değiştirdiği için eski girdi aranmaz bile; yeni anahtar hiçbir zaman önbellekte bulunmaz ve ilk okuma kaynağa gider. Kaynak okuması 156 ile olay tabanlı yolla hemen hemen aynıdır, bayatlık ise tümüyle kalkmıştır.

Sürüm Anahtara Girdiğinde

Sürüm tabanlı geçersizleştirmenin iki sonucu vardır: silme işlemi hiç yapılmaz ve eski girdiler önbellekte kalmayı sürdürür. Aşağıdaki blok her ikisini de gösterir. Ayrıca sürümün tek bir kayıt yerine bir ad alanının tamamına konabileceğini gösterir; bu biçimine nesil (generation) denir.

// surum-anahtari.mjs — surum anahtara girince eski girdiler erisilemez olur, ama silinmez
const kutu = new Map();
const surum = new Map();                          // kitap basina surum
let subeSurumu = 1;                               // sube duzeyinde ortak surum (nesil)

const kitapAnahtari = (id) => `kitap:s${surum.get(id) ?? 1}:${id}`;
const listeAnahtari = (subeId, sayfa) => `sube:${subeId}:n${subeSurumu}:liste:${sayfa}`;

kutu.set(kitapAnahtari(7), { rafta: 3 });
kutu.set(listeAnahtari(2, 1), ["Kitap 5", "Kitap 8"]);
kutu.set(listeAnahtari(2, 2), ["Kitap 11"]);
console.log("baslangic anahtarlari:", [...kutu.keys()].join("  "));

surum.set(7, 2);                                  // kitap 7 guncellendi
subeSurumu += 1;                                  // sube listeleri toptan gecersiz
console.log("kitap 7 icin aranan anahtar:", kitapAnahtari(7),
  "-> onbellekte:", kutu.has(kitapAnahtari(7)));
console.log("sube 2 sayfa 1 icin aranan  :", listeAnahtari(2, 1),
  "-> onbellekte:", kutu.has(listeAnahtari(2, 1)));

kutu.set(kitapAnahtari(7), { rafta: 2 });
const canli = new Set([kitapAnahtari(7), listeAnahtari(2, 1), listeAnahtari(2, 2)]);
const olu = [...kutu.keys()].filter((a) => !canli.has(a));
console.log(`girdi=${kutu.size}  erisilemez girdi=${olu.length}  ->`, olu.join("  "));

baslangic anahtarlari: kitap:s1:7  sube:2:n1:liste:1  sube:2:n1:liste:2
kitap 7 icin aranan anahtar: kitap:s2:7 -> onbellekte: false
sube 2 sayfa 1 icin aranan  : sube:2:n2:liste:1 -> onbellekte: false
girdi=4  erisilemez girdi=3  -> kitap:s1:7  sube:2:n1:liste:1  sube:2:n1:liste:2

Nesil sayacının değeri şudur: bir şubenin liste sayfaları kaç tane olursa olsun, tek bir sayının artırılmasıyla hepsi geçersizleşir. Anahtarların tek tek bulunup silinmesi gerekmez — paylaşılan bir önbellekte anahtar deseniyle arama pahalı, çoğu zaman da tehlikelidir.

Bedeli son satırdadır. Dört girdinin üçü artık hiçbir okumanın aramayacağı ölü girdidir. Bu girdiler yer kaplar ve ancak yaşam süresiyle ya da tahliye politikasıyla temizlenir. Sürüm tabanlı geçersizleştirme bu yüzden her zaman bir üst sınır süresiyle birlikte kurulur.

İkinci koşul, sürüm sayacının paylaşılan olmasıdır. Yukarıdaki örnekte sayaç süreç belleğindedir; iki uygulama örneği çalıştığında biri sürümü artırdığında diğeri bunu görmez ve eski anahtarı okumayı sürdürür. Sayacın kendisi paylaşılan depoda tutulmalı, dolayısıyla her okumada bir ek erişim ödenmelidir.

Hangi Yol Nerede

Üç yol birbirini dışlamaz; katman katman kurulur.

Süre tabanlı yol her zaman vardır, çünkü diğerlerinin başarısız olduğu durumda tek güvencedir. Bir olay kaybolduğunda ya da bir uygulama örneği sürüm artışını kaçırdığında, bayatlığı sınırlayan tek şey yaşam süresidir. İstemci ve kenar önbelleklerinde ise tek seçenektir: o kopyalara ulaşıp silmenin yolu yoktur.

Olay tabanlı yol veri değiştiğinde tepki verir ve bayatlığı yaşam süresinden bağımsız kılar. Doğruluğu, olayın gerçekten teslim edilmesine bağlıdır. Ölçümdeki tüketici gecikmesi bunun en iyimser hâliydi: olay kaydedilmişti ve yalnız geç okunuyordu. Kaybolan bir olay sonsuza kadar bayat bir girdi bırakır.

Sürüm tabanlı yol geçersizleştirmeyi okuma yoluna taşır: yanlış girdiyi silmek yerine doğru girdiyi başka bir adla arar. Yarış koşullarına en dayanıklı yoldur, çünkü silme işleminin sırasına bağlı değildir. Bedeli, ölü girdilerin biriktirdiği yerdir.

Özet

• Yaşam süresi, kaynak yükü ile kabul edilen bayatlık arasındaki dönüşüm oranıdır: ömür 10’dan 200’e çıktığında kaynak okuması 626’dan 72’ye düştü, bayat okuma 18’den 445’e çıktı.
• Olay tabanlı geçersizleştirme bu eğriden çıkar: beş adımlık tüketici gecikmesiyle 155 kaynak okuması ve 14 bayat okuma, yani aynı bayatlık için dörtte bir kaynak yükü.
• Olay tabanlı yolun bayatlık penceresi, olayın üretilmesi ile işlenmesi arasındaki süredir; gecikme beşten yirmi beşe çıktığında bayat okuma 14’ten 97’ye yükseldi.
• Sürüm anahtara girdiğinde bayat okuma sıfıra iner ve silme işlemi hiç yapılmaz; nesil sayacıyla bir ad alanının tamamı tek artışla geçersizleşir.
• Sürüm tabanlı yolun bedeli erişilemez girdilerdir; bu yüzden her zaman bir üst sınır süresiyle kurulur ve sayacın paylaşılan olması gerekir.

Sonraki Adım

Bu derste anahtar üç kez değişti: önce kitap:7, sonra sürümü taşıyan bir biçim, sonra bir şubenin nesil sayacını taşıyan bir liste anahtarı. Her seferinde anahtarın içine bir bilgi daha kondu ve her seferinde bu iş elle yapıldı. Anahtar yapısı elle kurulduğunda iki hata kaçınılmazdır: iki farklı sorgunun aynı anahtara düşmesi ve bir kiracının verisinin başka bir kiracıya sunulması. Sonraki ders anahtarı bir tasarım nesnesi olarak ele alır; ad alanı, kiracı ayrımı ve ölçütlerin kurallı sıralanması üzerine kurulu bir üreteç yazar ve iki hatayı da koşturarak gösterir.