Otomatik Devralma

Önceki ders çoğaltmayı ana düğümün ayakta olduğu varsayımıyla ölçtü: kopya geride kaldı, tamponu taşırdı, yeniden eşitlendi, ama yazmayı kabul eden düğüm hep aynı kaldı. Bu ders o düğümün durduğu anı ele alır ve iki soruyu birlikte sorar: durduğuna kim karar verir, ve karar verildiğinde elde ne kalır.

Kararı Kim Verir

Bir düğüme ulaşamamak, o düğümün durduğunu göstermez; ulaşamayan taraf da bozulmuş olabilir. Bu yüzden karar tek bir gözlemciye bırakılmaz: gözcü süreçleri ana düğümü ayrı ayrı izler ve devralma ancak gözcü çoğunluğu aynı yönde oy verdiğinde başlar. Çoğunluk floor(g/2)+1 oydur; lider seçimi ile kurtarma kurslarında kurulmuş bu kalıbın mekaniği burada tekrarlanmaz.

Bu dersin sorusu bellek içi deponun kendi kısıtıdır. Depo yazmayı bellekten onaylar, kopyanın uygulamasını beklemez; yedek de tanım gereği ana düğümün gerisindedir. Yerine geçtiği anda elinde olmayan yazmalar kabul edilmiş ve başarılı diye bildirilmiş ödünç kayıtlarıdır. Devralmada kayıp bir olasılık değil, bir garantidir; ölçülecek olan yalnız sayısıdır.

Düzenek

Aşağıdaki düzenek bir modeldir: gerçek gözcü süreci, ağ ya da düğüm kurulmaz. Tur soyut bir adımdır; algılama eşiği, seçim ve yükleme süresi tur cinsinden parametrelerdir, ölçülmüş süre değildir.

BK4 — ana düğümün geçici duraklamaları (2–7 tur) ile gözcülerin kendi ulaşamama aralıkları (3–6 tur) ayrı üreteçlerden gelir ve ayardan bağımsızdır. Gerekçe: aynı arıza dizisi bütün ayarlarda koşturulabilsin diye takvim önceden üretilir, tohum görünürdür; ayrıca gözcünün kendi kusuru, izlediği düğümün duraklamasından ayırt edilemez. BK5 — yanlış devralmadan sonra eski ana düğüm 3 tur boyunca yazma kabul etmeyi sürdürür. Gerekçe: yerinden edildiğini öğrenmesi anlık değildir; o turlarda yazılan kayıtlar bölünmüş yazmadır ve düğüm yedeğe indirildiğinde atılır.

// devralma/model.mjs — gozculu devralma SUREC ICI MODELDIR. Tur soyut bir adimdir; algilama
// esigi, secim ve yukleme suresi tur cinsinden parametrelerdir, olculmus sure degildir. Gercek
// gozcu sureci, ag ya da dugum kurulmaz. Onceki dersin kisiti aynen surer: cogaltma eszamansizdir,
// bu yuzden yedegin uygulamadigi yazmalar KABUL EDILMIS ama ulasmamis yazmalardir.
export const GIRIS_BAYT = 240, KAYIT_BAYT = 96, ANAHTAR = 2000;

export function uretec(tohum) {  // dogrusal esleskli uretec; tohum gorunurdur
  let s = tohum >>> 0;
  return () => { s = (Math.imul(s, 1103515245) + 12345) >>> 0; return s / 4294967296; };
}

export function kosum({ gozcu = 3, dusenGozcu = 0, algilama = 3, secim = 2, gecikme = 2,
                        soguk = null, tur = 300, yazma = 40, ariza = 200, bolunme = 3,
                        duraklamaOlas = 0.02, kendiOlas = 0.03, tohum = 20260731 }) {
  const rnd = uretec(tohum);
  const takvim = (olas, enAz, cesit) => {                  // takvimler ayardan bagimsiz uretilir
    const d = new Uint8Array(tur + 2);
    for (let t = 1; t <= tur; t += 1) {
      if (d[t] || rnd() >= olas) continue;
      for (let x = t, b = enAz + Math.floor(rnd() * cesit); x < t + b && x <= tur; x += 1) d[x] = 1;
    }
    return d;
  };
  const durak = takvim(duraklamaOlas, 2, 6);               // ana dugumun gecici duraklamasi
  const kendi = [...Array(7)].map(() => takvim(kendiOlas, 3, 4));  // gozcunun KENDI ulasamamasi
  const cogunluk = Math.floor(gozcu / 2) + 1, oyVeren = gozcu - dusenGozcu;
  const bekleme = secim + (soguk ? soguk.yukleme : 0), sayac = Array(7).fill(0);
  let kabul = 0, uygulanan = 0, arizaAktif = true, kalan = 0, sebep = null, bolunmeKalan = 0;
  let yazmasiz = 0, gercek = 0, yanlis = 0, kayip = 0, bolunmus = 0, arizaKayip = 0, kesinti = null;

  for (let t = 1; t <= tur; t += 1) {
    if (bolunmeKalan > 0) { bolunmeKalan -= 1; bolunmus += yazma; }  // eski ana dugum hala yaziyor
    const ulasilamaz = (arizaAktif && t >= ariza) || durak[t] === 1;
    if (kalan > 0) {                                       // devralma penceresi: yazma kabul edilmez
      kalan -= 1; yazmasiz += 1;
      if (kalan > 0) continue;
      const taban = soguk                                  // soguk yedek son anlik goruntuden baslar
        ? Math.floor(kabul / (soguk.aralik * yazma)) * soguk.aralik * yazma : uygulanan;
      kayip += kabul - taban;
      if (sebep === "gercek") { gercek += 1; arizaAktif = false; kesinti = t - ariza + 1; arizaKayip = kabul - taban; }
      else { yanlis += 1; bolunmeKalan = bolunme; }
      kabul = taban; uygulanan = taban; sayac.fill(0);
      for (let x = t; x <= tur && durak[x] === 1; x += 1) durak[x] = 0;  // yeni dugum o duraklamada degil
      continue;
    }
    if (ulasilamaz) yazmasiz += 1;
    else { kabul += yazma; uygulanan = Math.max(uygulanan, kabul - gecikme * yazma); }
    let oy = 0;                                            // her gozcu KENDI gorusuyle oy verir
    for (let j = 0; j < oyVeren; j += 1) {
      sayac[j] = ulasilamaz || kendi[j][t] === 1 ? sayac[j] + 1 : 0;
      if (sayac[j] >= algilama) oy += 1;
    }
    if (oy >= cogunluk) { kalan = bekleme; sebep = arizaAktif && t >= ariza ? "gercek" : "yanlis"; }
  }
  return { cogunluk, oyVeren, gercek, yanlis, kayip, arizaKayip, bolunmus, yazmasiz, kesinti,
           veri: (soguk ? 1 : 2) * ANAHTAR * GIRIS_BAYT }; // sicak yedek veri kumesini bellekte tutar
}

// devralma/olc.mjs — ayni arizada uc ayar: gozcu cogunlugu, algilama esigi, yedek turu
import { kosum, GIRIS_BAYT, KAYIT_BAYT, ANAHTAR } from "./model.mjs";

const s = (x, n) => String(x).padStart(n);
const kib = (b) => s((b / 1024).toFixed(1), 8);

console.log("300 tur; her turda 40 odunc kaydi. Ana dugum 200. turda kalici olarak durur. Tohum");
console.log("20260731: ana dugumde 2-7 turluk gecici duraklamalar, her gozcude 3-6 turluk kendi");
console.log("ulasamama araliklari uretilir. Gecikme 2 tur, algilama 3, secim 2 tur.\n");
console.log("gozcu | dusen | cogunluk | oy veren | ariza kesintisi | yanlis devralma | yazmasiz");
console.log("------|-------|----------|----------|-----------------|-----------------|---------");
for (const [g, d] of [[1, 0], [2, 0], [3, 0], [3, 1], [3, 2], [5, 0], [5, 2], [5, 3]]) {
  const r = kosum({ gozcu: g, dusenGozcu: d });
  console.log(`${s(g, 5)} | ${s(d, 5)} | ${s(r.cogunluk, 8)} | ${s(r.oyVeren, 8)} | ` +
    `${s(r.kesinti === null ? "yok" : r.kesinti + " tur", 15)} | ${s(r.yanlis, 15)} | ` +
    `${s(r.yazmasiz, 5)} tur`);
}

console.log("\n3 gozcu, hepsi ayakta; algilama esigi degisiyor:");
console.log("esik | yanlis devralma | bolunmus yazma | ariza kesintisi | yazmasiz | toplam kayip");
console.log("-----|-----------------|----------------|-----------------|----------|-------------");
for (const a of [1, 2, 3, 4, 5, 6]) {
  const r = kosum({ algilama: a });
  console.log(`${s(a, 4)} | ${s(r.yanlis, 15)} | ${s(r.bolunmus, 14)} | ` +
    `${s(r.kesinti + " tur", 15)} | ${s(r.yazmasiz, 5)} tur | ${s(r.kayip, 12)}`);
}

console.log("\nYedek turu. Gecici duraklama kapali: tek arizali devralma. Soguk yedegin verisi");
console.log("bellekte degildir; son anlik goruntu 30 tur oncesine aittir, yuklemesi 12 tur surer:");
console.log("yedek         | tutulan veri | ariza kesintisi | kayip yazma | kayip bayt");
console.log("--------------|--------------|-----------------|-------------|-----------");
for (const g of [1, 2, 4, 8]) {
  const r = kosum({ gecikme: g, duraklamaOlas: 0, kendiOlas: 0 });
  console.log(`sicak, gec. ${g} | ${kib(r.veri)} KiB | ${s(r.kesinti + " tur", 15)} | ` +
    `${s(r.arizaKayip, 11)} | ${s(r.arizaKayip * KAYIT_BAYT, 6)} bayt`);
}
const c = kosum({ duraklamaOlas: 0, kendiOlas: 0, soguk: { yukleme: 12, aralik: 30 } });
console.log(`soguk yedek   | ${kib(c.veri)} KiB | ${s(c.kesinti + " tur", 15)} | ` +
  `${s(c.arizaKayip, 11)} | ${s(c.arizaKayip * KAYIT_BAYT, 6)} bayt`);

console.log("\nkosumdan bagimsiz nicelikler:");
console.log("  gozcu cogunlugu      = floor(g/2)+1; katlanilan gozcu kaybi = g - cogunluk");
console.log("  g       : " + [1, 2, 3, 4, 5, 6, 7].map((n) => s(n, 4)).join(""));
console.log("  cogunluk: " + [1, 2, 3, 4, 5, 6, 7].map((n) => s(Math.floor(n / 2) + 1, 4)).join(""));
console.log("  kayip   : " + [1, 2, 3, 4, 5, 6, 7].map((n) => s(n - (Math.floor(n / 2) + 1), 4)).join(""));
console.log("  devralma basina kayip = gecikme x yazma hizi (sicak yedek)");
console.log("  gecikme : " + [1, 2, 4, 8].map((n) => s(n, 6)).join(""));
console.log("  kayip   : " + [1, 2, 4, 8].map((n) => s(n * 40, 6)).join(""));
console.log("  ariza kesintisi      = algilama esigi + secim (+ soguk yedekte yukleme) tur");
console.log("  soguk yedekte en kotu kayip = anlik goruntu araligi x yazma hizi = 30 x 40 = 1200");
console.log("  sicak yedegin bedeli = " + (ANAHTAR * GIRIS_BAYT / 1024).toFixed(1) +
  " KiB, yani veri kumesinin ikinci tam kopyasi (" + ANAHTAR + " x " + GIRIS_BAYT + " bayt)");

300 tur; her turda 40 odunc kaydi. Ana dugum 200. turda kalici olarak durur. Tohum
20260731: ana dugumde 2-7 turluk gecici duraklamalar, her gozcude 3-6 turluk kendi
ulasamama araliklari uretilir. Gecikme 2 tur, algilama 3, secim 2 tur.

gozcu | dusen | cogunluk | oy veren | ariza kesintisi | yanlis devralma | yazmasiz
------|-------|----------|----------|-----------------|-----------------|---------
    1 |     0 |        1 |        1 |           6 tur |              12 |    40 tur
    2 |     0 |        2 |        2 |           5 tur |               6 |    29 tur
    3 |     0 |        2 |        3 |           5 tur |               9 |    35 tur
    3 |     1 |        2 |        2 |           5 tur |               6 |    29 tur
    3 |     2 |        2 |        1 |             yok |               0 |   115 tur
    5 |     0 |        3 |        5 |           5 tur |               4 |    25 tur
    5 |     2 |        3 |        3 |           5 tur |               4 |    25 tur
    5 |     3 |        3 |        2 |             yok |               0 |   115 tur

3 gozcu, hepsi ayakta; algilama esigi degisiyor:
esik | yanlis devralma | bolunmus yazma | ariza kesintisi | yazmasiz | toplam kayip
-----|-----------------|----------------|-----------------|----------|-------------
   1 |              13 |           1560 |           3 tur |    33 tur |          960
   2 |              11 |           1320 |           5 tur |    34 tur |          880
   3 |               9 |           1080 |           5 tur |    35 tur |          800
   4 |               4 |            480 |           6 tur |    28 tur |          400
   5 |               2 |            240 |           7 tur |    26 tur |          240
   6 |               2 |            240 |           8 tur |    28 tur |          240

Yedek turu. Gecici duraklama kapali: tek arizali devralma. Soguk yedegin verisi
bellekte degildir; son anlik goruntu 30 tur oncesine aittir, yuklemesi 12 tur surer:
yedek         | tutulan veri | ariza kesintisi | kayip yazma | kayip bayt
--------------|--------------|-----------------|-------------|-----------
sicak, gec. 1 |    937.5 KiB |           5 tur |          40 |   3840 bayt
sicak, gec. 2 |    937.5 KiB |           5 tur |          80 |   7680 bayt
sicak, gec. 4 |    937.5 KiB |           5 tur |         160 |  15360 bayt
sicak, gec. 8 |    937.5 KiB |           5 tur |         320 |  30720 bayt
soguk yedek   |    468.8 KiB |          17 tur |         760 |  72960 bayt

kosumdan bagimsiz nicelikler:
  gozcu cogunlugu      = floor(g/2)+1; katlanilan gozcu kaybi = g - cogunluk
  g       :    1   2   3   4   5   6   7
  cogunluk:    1   2   2   3   3   4   4
  kayip   :    0   0   1   1   2   2   3
  devralma basina kayip = gecikme x yazma hizi (sicak yedek)
  gecikme :      1     2     4     8
  kayip   :     40    80   160   320
  ariza kesintisi      = algilama esigi + secim (+ soguk yedekte yukleme) tur
  soguk yedekte en kotu kayip = anlik goruntu araligi x yazma hizi = 30 x 40 = 1200
  sicak yedegin bedeli = 468.8 KiB, yani veri kumesinin ikinci tam kopyasi (2000 x 240 bayt)

Çoğunluğun İki Yüzü

Çoğunluk toplanamadığında devralma hiç başlamaz. Üç gözcüden ikisi ve beş gözcüden üçü düştüğünde ayakta kalan gözcüler ana düğümün durduğunu doğru görüyor; yine de oy sayısı çoğunluğun altındadır. Sonuç son sütunda: 115 yazmasız tur. Bu kuralın kendisidir — bir gözcü, gördüğünü ötekilere doğrulatamadığı sürece kararı veremez.

Çoğunluk asıl olarak gözcünün kendi kusuruna karşıdır. Tek gözcülü satırda çoğunluk 1’dir ve gözcünün kendi ulaşamama aralıkları doğrudan karara dönüşür: 12 yanlış devralma. Beş gözcüde çoğunluk 3’e çıkar ve aynı takvimle yanlış devralma 4’e iner. Ana düğümün arıza takvimi bütün satırlarda aynıdır; değişen, bir gözcünün yanılmasının tek başına yetip yetmediğidir.

Üç gözcülü satır ilk bakışta ters görünüyor: çoğunluk yine 2 iken yanlış devralma 6’dan 9’a çıkıyor. Nedeni oy veren sayısıdır — iki gözcüde ikisinin birden, üç gözcüde herhangi ikisinin yanılması yeter ve bu üç kat daha çok ikilidir. Doğrulaması aynı tablodadır: üç gözcüden biri düştüğünde satır, iki gözcülü satırla birebir aynı sayıları veriyor.

Eşiğin Fiyatı

İkinci tablo algılama eşiğini iki yönde birden ölçüyor. Eşik 1’de gerçek arızanın kesintisi 3 tura iner; aynı satırda yanlış devralma 13, bölünmüş yazma 1.560 kayıttır. Eşik 6’da yanlış devralma 2’ye, bölünmüş yazma 240’a düşer; karşılığında kesinti 8 tura çıkar.

Bölünmüş yazma bu takasın en pahalı kalemidir. Yanlış devralmada eski ana düğüm sağlamdır ve üç tur boyunca ödünç kaydı kabul etmeyi sürdürür; bu kayıtlar yeni ana düğüme hiç ulaşmaz, eski düğüm yedeğe indirildiğinde atılır. Eşik 1 ile eşik 6 arasındaki fark bu kalemde 1.320 kayıttır.

Toplam kayıp sütunu aynı yönde ilerliyor (960’a karşı 240): her devralma, doğru ya da yanlış olsun, kendi kaybını üretir. Yazmasız tur sütunu ise tek yönlü değildir (33, 34, 35, 28, 26, 28) — eşiği yükseltmek gerçek arızadaki kesintiyi uzatır ama yanlış devralmaların açtığı pencereleri kapatır.

Yedeğin Bellek Bedeli

Üçüncü tablo geçici duraklamaları kapatıp tek bir gerçek arızayı yalıtıyor. Sıcak yedek satırlarında kayıp tam olarak gecikme × yazma hızıdır: 40, 80, 160 ve 320 ödünç kaydı. Kesinti dört satırda da 5 turdur; gecikme kesintiyi değil, yalnız kaybı büyütür.

Soğuk yedek satırı bu kursun kuralını doğrudan gösteriyor. Yedeğin verisi bellekte tutulmadığında tutulan veri 937,5 KiB’den 468,8 KiB’ye iner. Karşılığında kesinti 5 turdan 17 tura, kayıp 80 kayıttan 760 kayda (72.960 bayt; en kötü durumda 1.200 kayda kadar) çıkar. Sıcak yedeğin 468,8 KiB’lik bedeli tam olarak bunu satın alır: kesintinin üçte biri ve kaybın onda biri.

Özet

• Gözcü çoğunluğu floor(g/2)+1’dir; üç gözcüden ikisi ya da beş gözcüden üçü düştüğünde devralma hiç başlamadı ve arızadan sonraki 115 turda tek bir ödünç kaydı kabul edilmedi.
• Çoğunluk kuralı asıl olarak gözcünün kendi kusuruna karşıdır: aynı arıza takvimiyle tek gözcüde 12, beş gözcüde 4 yanlış devralma ölçüldü.
• Çoğunluk oranını yükseltmeyen gözcü eklemesi tersine çalışır: iki gözcü (çoğunluk 2) 6, üç gözcü (çoğunluk yine 2) 9 yanlış devralma verdi.
• Algılama eşiği iki yönlüdür: eşik 1’de kesinti 3 tur, yanlış devralma 13, bölünmüş yazma 1.560 kayıt; eşik 6’da kesinti 8 tur, yanlış devralma 2, bölünmüş yazma 240.
• Eşzamansız çoğaltma devralma başına kaybı garanti eder ve sayısı gecikme × yazma hızıdır: 40, 80, 160, 320 ödünç kaydı — hepsi başarılı diye bildirilmiş kayıtlardır.
• Sıcak yedek veri kümesinin ikinci tam kopyasını, 468,8 KiB’yi tutar; karşılığında kesintiyi 17 turdan 5 tura, kaybı 760 kayıttan 80 kayda indirir.

Sonraki Adım

Buraya kadarki iki ders aynı örtük varsayımı taşıdı: veri kümesinin tamamı tek bir düğüme sığıyor. Çoğaltma o kümenin kopyalarını çıkardı, devralma kopyalardan birini göreve aldı; hiçbiri kümeyi bölmedi. Katalog ve ödünç kayıtları bir düğümün bellek bütçesini aştığında geriye tek yol kalır: anahtar alanını bölmek. Bedeli hemen görünür — aynı işlemde geçen iki anahtar farklı düğümlere düşerse o işlem tek bir düğümde yürütülemez. Sonraki ders anahtarın bölüme nasıl eşlendiğini, çok anahtarlı işlemlerin kaçının küme kısıtına takıldığını ve etiketle aynı bölüme toplamanın düğüm başına tutulan baytı ne kadar dengesizleştirdiğini sayar.