Süre Sonu Yönetimi

Önceki dersin son ölçümü bir boşluk bıraktı. Süre sonu damgası taşıyan bir depoda, sekiz yüz bin baytlık bütçenin sonunda tutulan 8.988 girişin 7.969’u süresi dolmuş girişlerdi ve bellekte duruyorlardı. Süresi dolmuş bir girişe erişildiğinde doğru davranış üretiliyordu — giriş yok sayılıyor ve düşürülüyordu — ama kimse erişmediği sürece giriş yerini koruyordu. Tazelik penceresi okuma sonucunu düzeltti, tutulan baytı düzeltmedi.

Bu ders o boşluğu ele alır. İki yol vardır ve ikisi de aynı depoda birlikte çalışabilir. Tembel temizleme, girişi yalnız ona erişildiğinde kontrol eder ve süresi dolmuşsa siler; maliyeti sıfıra yakındır, çünkü zaten yapılacak olan aramanın üstüne bir karşılaştırma ekler. Etkin temizleme, arka planda anahtar alanından örnek alır, süresi dolmuş olanları siler ve örneklemede çok dolmuş giriş çıkarsa turu yineler; maliyeti, hiçbir istemcinin istemediği bir iştir.

Düzenek

KB9. Kütüphanenin bir saatlik trafiği: saniyede 20 yeni anahtar konur ve 60 erişim yapılır. Anahtarların yüzde 30’u 60 saniyelik ödünç kilidi, yüzde 50’si 300 saniyelik katalog girişi, yüzde 20’si 1.800 saniyelik oturum kaydıdır. Erişimlerin yüzde 70’i son iki bin anahtara, yüzde 30’u bütün anahtar alanına gider. Değer gövdesi 24 bayttır; giriş üstverisi 48, süre sonu damgası 16 bayttır.

KB10. Etkin temizleme her saniye bir tur başlatır. Turda belirli sayıda anahtar örneklenir; süresi dolmuş olanlar silinir. Örneklenenlerin dörtte birinden fazlası dolmuşsa tur yinelenir, en çok on altı kez.

// sure.mjs — süre sonu damgalı depo, tembel ve etkin temizleme
export const TEMEL = 48, DAMGA = 16;             // KB1: giriş üstverisi, KB6: süre sonu damgası

export function uretec(t0) {
  let a = t0 >>> 0;
  return () => { a = (a + 0x6d2b79f5) >>> 0; let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1); t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
}

export class Depo {
  constructor(tohum) {
    this.g = new Map(); this.sonu = new Map(); this.dizi = []; this.yer = new Map();
    this.bayt = 0; this.saat = 0; this.r = uretec(tohum);
    this.tembelSilinen = 0; this.etkinSilinen = 0; this.ornekleneni = 0; this.tur = 0;
    this.gecikmeToplam = 0; this.gecikmeEnKotu = 0; this.tepeOlu = 0;
  }
  maliyet(a) { return Buffer.byteLength(a) + 24 + TEMEL + DAMGA; }
  koy(a, omur) {
    if (!this.g.has(a)) {
      this.bayt += this.maliyet(a);
      this.yer.set(a, this.dizi.length); this.dizi.push(a);
    }
    this.g.set(a, 1); this.sonu.set(a, this.saat + omur);
  }
  sil(a) {
    this.bayt -= this.maliyet(a); this.g.delete(a); this.sonu.delete(a);
    const i = this.yer.get(a), son = this.dizi.pop();
    if (i < this.dizi.length) { this.dizi[i] = son; this.yer.set(son, i); }
    this.yer.delete(a);
  }
  eris(a) {                                      // tembel temizleme: dolmuş giriş erişimde düşer
    if (!this.g.has(a)) return 'yok';
    if (this.sonu.get(a) > this.saat) return 'isabet';
    const gecikme = this.saat - this.sonu.get(a);
    this.gecikmeToplam += gecikme;
    if (gecikme > this.gecikmeEnKotu) this.gecikmeEnKotu = gecikme;
    this.tembelSilinen++; this.sil(a);
    return 'dolmus';
  }
  etkin(ornek, esik = 0.25, enCokTur = 16) {      // etkin temizleme: örnekleyip silen turlar
    for (let t = 0; t < enCokTur; t++) {
      let silinen = 0, bakilan = 0;
      for (let i = 0; i < ornek && this.dizi.length > 0; i++) {
        const a = this.dizi[Math.floor(this.r() * this.dizi.length)];
        bakilan++;
        if (this.sonu.get(a) <= this.saat) { this.sil(a); silinen++; }
      }
      this.ornekleneni += bakilan; this.etkinSilinen += silinen; this.tur++;
      if (bakilan === 0 || silinen / bakilan < esik) return;
    }
  }
  olu() {
    let sayi = 0, bayt = 0;
    for (const a of this.g.keys()) if (this.sonu.get(a) <= this.saat) { sayi++; bayt += this.maliyet(a); }
    return { sayi, bayt };
  }
}

// Bir saatlik kütüphane trafiği: saniyede 20 yeni anahtar, 60 erişim.
export function kos(ornek, tohum = 20260731, sure = 3600) {
  const d = new Depo(tohum + 7), r = uretec(tohum);
  const tur = [['kilit', 60], ['katalog', 300], ['oturum', 1800]];
  const anahtarlar = [];
  for (let t = 1; t <= sure; t++) {
    d.saat = t;
    for (let i = 0; i < 20; i++) {
      const p = r(), [ad, omur] = p < 0.30 ? tur[0] : p < 0.80 ? tur[1] : tur[2];
      const a = ad + ':' + String(anahtarlar.length).padStart(6, '0');
      anahtarlar.push(a); d.koy(a, omur);
    }
    for (let i = 0; i < 60; i++) {                // %70 son 2000 anahtardan, %30 tüm alandan
      const n = anahtarlar.length;
      const j = r() < 0.70 ? n - 1 - Math.floor(r() * Math.min(2000, n))
        : Math.floor(r() * n);
      d.eris(anahtarlar[j]);
    }
    if (ornek > 0) d.etkin(ornek);
    if (t % 60 === 0) {                           // tepe ölçümü dakikada bir alınır
      const o = d.olu();
      if (o.bayt > d.tepeOlu) d.tepeOlu = o.bayt;
    }
  }
  return d;
}

Ölçüm

// olcum.mjs — tembel temizleme tek başına ve üç örnekleme boyuyla etkin temizleme
import { kos } from './sure.mjs';

console.log('bir saatlik trafik: 72000 anahtar konur, 216000 erişim yapılır, tohum 20260731');
console.log('yöntem            tutulan giriş  ölü giriş  ölü bayt  ölü pay  tepe ölü bayt');
const kosumlar = [['yalnız tembel', 0], ['etkin, 5 örnek', 5], ['etkin, 20 örnek', 20],
  ['etkin, 100 örnek', 100]];
const sonuc = kosumlar.map(([ad, n]) => [ad, n, kos(n)]);
for (const [ad, , d] of sonuc) {
  const o = d.olu();
  console.log(ad.padEnd(17), String(d.g.size).padStart(13), String(o.sayi).padStart(10),
    String(o.bayt).padStart(9), ('%' + ((o.bayt / d.bayt) * 100).toFixed(1)).padStart(8),
    String(d.tepeOlu).padStart(14));
}

console.log('\ntemizlemenin maliyeti ve gecikmesi');
console.log('yöntem            tembel silinen  ortalama gecikme  en kötü  etkin silinen  örneklenen');
for (const [ad, , d] of sonuc) {
  const ort = d.tembelSilinen ? (d.gecikmeToplam / d.tembelSilinen).toFixed(1) : '0.0';
  console.log(ad.padEnd(17), String(d.tembelSilinen).padStart(14), (ort + ' sn').padStart(17),
    (d.gecikmeEnKotu + ' sn').padStart(8), String(d.etkinSilinen).padStart(14),
    String(d.ornekleneni).padStart(11));
}

const t = sonuc[0][2], y = sonuc[2][2];
console.log('\nerişim başına ek iş: tembel 0 (erişilen girişle sınırlı) |',
  'etkin, 20 örnek:', (y.ornekleneni / 216000).toFixed(3), 'giriş,',
  y.tur, 'tur /', 3600, 'saniye');
console.log('yalnız tembelde bellek:', t.bayt, 'bayt | etkin, 20 örnekte:', y.bayt, 'bayt |',
  'fark', t.bayt - y.bayt, 'bayt (%' + (((t.bayt - y.bayt) / t.bayt) * 100).toFixed(1) + ')');

bir saatlik trafik: 72000 anahtar konur, 216000 erişim yapılır, tohum 20260731
yöntem            tutulan giriş  ölü giriş  ölü bayt  ölü pay  tepe ölü bayt
yalnız tembel             39714      29205   2963642    %73.6        2963642
etkin, 5 örnek            20891      10382   1053264    %49.7        1112990
etkin, 20 örnek           14460       3951    400775    %27.4         414019
etkin, 100 örnek          12539       2030    205831    %16.2         212789

temizlemenin maliyeti ve gecikmesi
yöntem            tembel silinen  ortalama gecikme  en kötü  etkin silinen  örneklenen
yalnız tembel              32286          421.4 sn  3500 sn              0           0
etkin, 5 örnek             23572          206.5 sn  3009 sn          27537       62375
etkin, 20 örnek            16649           68.1 sn  1563 sn          40891      167200
etkin, 100 örnek           12772           30.7 sn   781 sn          46689      362500

erişim başına ek iş: tembel 0 (erişilen girişle sınırlı) | etkin, 20 örnek: 0.774 giriş, 8360 tur / 3600 saniye
yalnız tembelde bellek: 4027669 bayt | etkin, 20 örnekte: 1464802 bayt | fark 2562867 bayt (%63.6)

Tembel Temizlemenin Sınırı

Birinci satır, tembel temizlemenin çalışmadığı anlamına gelmez. Tam tersine çalışır: koşum boyunca 32.286 giriş erişim sırasında yakalanıp silindi. Sorun, temizlemenin yalnız erişilen girişe dokunmasıdır. Bir saatin sonunda depoda 39.714 giriş kalır ve bunların 29.205’i süresi dolmuş girişlerdir; kapladıkları 2.963.642 bayt, deponun tuttuğu belleğin yüzde 73,6’sıdır. Bu girişler süreleri dolduktan sonra bir daha istenmedi, dolayısıyla hiçbir zaman kontrol edilmediler.

İkinci tablo gecikmeyi verir. Tembel yolla silinen girişler, süreleri dolduktan ortalama 421,4 saniye sonra bellekten düştü; en kötü durumda 3.500 saniye, yani koşumun neredeyse tamamı boyunca yer tuttu. Kütüphanenin ölçüsüyle: altmış saniyelik bir ödünç kilidi, işini bitirdikten yaklaşık yedi dakika sonra hâlâ bellekte duruyor.

Bu, süre sonunun tek başına bir bellek aracı olmadığını doğrular. Tazelik penceresi sözleşmesini tutar — dolmuş bir giriş asla okunmaz — ama sözleşmenin bellek tarafı boşta kalır. Bir saatlik trafikte deponun dörtte üçü hiç kimsenin isteyemeyeceği veriye gider.

Etkin Temizlemenin Fiyatı

Etkin temizleme bu boşluğu kapatır ve bedelini hiçbir istemcinin istemediği bir işle öder. Turda yirmi anahtar örnekleyen düzen, ölü payı yüzde 73,6’dan yüzde 27,4’e indirir ve deponun toplam belleğini 4.027.669 bayttan 1.464.802 bayta, yani yüzde 63,6 aşağı çeker. Gecikmenin ortalaması 421,4 saniyeden 68,1 saniyeye iner.

Maliyet, örneklenen giriş sayısıyla ölçülür: 167.200 giriş. Aynı saatte yapılan erişim sayısı 216.000 olduğuna göre, temizleme her erişime karşılık 0,774 giriş dokunuşu ekler. Turların sayısı 8.360’tır — saniyede ortalama 2,3 tur. Eşik kuralı burada görünür: dolmuş giriş yoğunken tur yinelenir ve temizleme hızlanır, alan seyrekleştiğinde tek turla biter. Örnekleme turu, deponun erişimlere ayırdığı zamandan alınır; bu yüzden tur başına örnek sayısı ve tur sayısının üst sınırı birer yanıt süresi kararıdır.

Örnekleme boyunun etkisi doğrusal değildir. Beşten yirmiye çıkmak 104.825 ek örnekleme karşılığında ölü belleği 1.053.264 bayttan 400.775 bayta indirdi: örnek başına 6,2 bayt. Yirmiden yüze çıkmak 195.300 ek örnekleme karşılığında 400.775 bayttan 205.831 bayta indirdi: örnek başına 1,0 bayt. Marjinal getiri altıda birine düşer. Nedeni doğrudandır: alan temizlendikçe rastgele seçilen bir anahtarın dolmuş çıkma olasılığı azalır, örnekleme boş dönmeye başlar.

Ölü payının hiçbir düzende sıfıra inmemesi de aynı nedendendir. Yüz örneklik turlarda bile 2.030 giriş dolmuş olarak kalır; rastgele örnekleme bir girişi eninde sonunda bulur, ama “eninde sonunda” bir zaman aralığıdır ve bu aralık bellekte bayt olarak durur.

Seçim

İki yöntem birbirinin yerine geçmez; birlikte kullanılır ve iki farklı şeyi güvence altına alırlar. Tembel temizleme doğruluğu güvence altına alır: süresi dolmuş bir giriş, etkin temizleme onu henüz bulmamış olsa da okunamaz. Etkin temizleme belleği güvence altına alır: hiç erişilmeyecek girişlerin yerini geri kazanır.

Örnekleme boyu ise bir bütçe ayarıdır. Kütüphanenin ödünç kilitleri gibi kısa ömürlü ve yoğun üretilen anahtarlarda alan hızla dolduğu için büyük örnek karşılığını verir. Oturum kayıtları gibi uzun ömürlü ve seyrek anahtarlarda aynı örnekleme çoğunlukla boş döner ve harcanan iş yanıt süresine ödenmiş olur. Yirmi örneklik tur, bu koşumda ölü belleğin yüzde 86’sını erişim başına 0,774 giriş dokunuşuyla geri aldı; yüz örneklik tur kalan payın yarısını daha aldı ve maliyeti iki katına çıkardı.

Özet

• Tembel temizleme yalnız erişilen girişe dokunur: koşum sonunda 39.714 girişin 29.205’i süresi dolmuş kaldı ve belleğin yüzde 73,6’sını tuttu.
• Tembel yolla düşen girişler süreleri dolduktan ortalama 421,4 saniye, en kötü durumda 3.500 saniye sonra bellekten çıktı.
• Turda yirmi anahtar örnekleyen etkin temizleme ölü payı yüzde 27,4’e, toplam belleği 4.027.669 bayttan 1.464.802 bayta indirdi; bedeli erişim başına 0,774 giriş dokunuşudur.
• Örnekleme boyunu artırmanın getirisi azalır: beşten yirmiye geçiş örnek başına 6,2 bayt, yirmiden yüze geçiş 1,0 bayt kazandırdı.
• Tembel temizleme doğruluğu, etkin temizleme belleği güvence altına alır; süre sonu tek başına ne birini ne diğerini karşılar.

Sonraki Adım

Bu konu deponun kendine bakma biçimlerini kurdu: durumunu diske yazmak, yazmalarını kaydetmek, hangisini seçeceğine kurtarma ve kayıp penceresine bakarak karar vermek, bellek sınırına ulaşınca hangi anahtarı atacağını bilmek ve süresi dolanı yerinde bırakmamak. Ölçülen her sayı tek bir sürecin içinden okundu.

Bu kararların hepsinin ortak bir varsayımı var: düğüm çalışıyor. Anlık görüntü diske yazıldı ama o disk o makinenin diski; kayıp penceresi hesaplandı ama süreç yeniden başlayabildiği varsayıldı; tahliye politikası bellek sınırını korudu ama o bellek tek bir makinenin belleği. Makinenin kendisi durduğunda — ya da erişilemez hâle geldiğinde — kurtarma dosyaları oradadır, depoyu isteyen istemciler ise başka yerdedir. Sonraki konu bu soruyu açar: verinin ikinci bir kopyası nasıl tutulur, o kopya ne kadar geride kalır, ve devralma sırasında kabul edilmiş ama henüz yayılmamış bir yazmaya ne olur.