Çoğaltma Kümeleri

Önceki konu belge modelini tek belge atomikliğine kadar götürdü ve orada durdu. Buraya kadarki her ölçüm tek bir düğümde yapıldı: bir gömme kararının okuma yolunu kaç isteğe indirdiği, bir dizinin taranan giriş sayısını nereye çektiği, çok belgeli bir işlemin neye mal olduğu. Belge modelinin vaatlerinin çoğu ise tek düğümde sınanamaz — yatay ölçekleme de, bir makine kaybedildiğinde hizmetin sürmesi de birden çok düğüm ister.

Bu konu deponun dağıtık kurulumdaki davranışını ele alır ve ilk soru şudur: aynı veri birden çok üyede duruyorsa, bunlardan hangisinin yazma kabul ettiğine kim karar verir. Kütüphane katalog ve ödünç veritabanı bu konuda da örnek alandır; ölçülen iş, ödünç kayıtlarının yazılmasıdır.

Kümenin Kendi Seçimi

Aynı veriyi birden çok üyede tutan bu düzene çoğaltma kümesi (replica set) denir. Üyelerden biri birincildir (primary) ve yazmaları kabul eder; ötekiler ikincildir (secondary), aynı değişiklikleri uygular ve ayarlara göre okuma karşılar. Bu, İleri Veri Ölçekleme kursundaki ana–kopya düzeninin kendisidir; iki ad aynı kalıbı adlandırır ve ikisi arasında bir mekanik farkı yoktur.

Çoğaltmanın mekaniği o kursta ve İlişkisel Veritabanı Yönetimi kursunda kuruldu: günlük akışı, çoğaltma gecikmesi, kopya eklemenin azalan kazancı ve bayat okuma orada ölçüldü. Burada tekrarlanmaz. Bu dersin sorusu kümenin kendi başına verdiği karardır: birincil durduğunda yerine kimin geçeceğine üyeler kendi aralarında karar verir ve bu kararın iki ölçülebilir sonucu vardır — kararın verilemediği süre boyunca hiçbir yazma kabul edilmez, ve yeni birincil eskisinden geride olduğunda aradaki fark kadar yazma geri alınır.

Kararı bağlayan kural çoğunluk kuralıdır (quorum): bir üye ancak üye sayısının yarısından fazlasının oyunu alarak birincil olabilir. Bu kural ikiye bölünmüş bir kümede iki tarafın birden kendini birincil sanmasını engeller. Bedeli de aynı kuralın içindedir: çoğunluk toplanamıyorsa seçim hiç başlamaz.

Düzenek

Aşağıdaki düzenek bir modeldir: gerçek küme, kapsayıcı ya da bulut kurulmaz, üyeler birer sayıdır. Tur soyut bir adımdır; yayılım gecikmesi, algılama eşiği ve seçim süresi tur cinsinden parametrelerdir, ölçülmüş süre değildir. Modelin tek gerçekçi varsayımı yayılımın çekme yönlü olmasıdır: ikincil, birincilin günlüğünü okur. Birincil durduğunda henüz okunmamış yazma hiçbir üyeye ulaşamaz; geri alınan yazmanın kaynağı budur.

NS14 — üye başına yayılım gecikmesi 2, 3, 3 ve 5 turdur. Gerekçe: ikincillerin birinciliye uzaklığı eşit değildir. NS15 — algılama eşiği 2 tur, seçim 2 turdur. Gerekçe: birincilin durduğuna karar vermek ve oy toplamak ayrı adımlardır. İki varsayım da doğrusal etkilidir: gecikme iki katına çıkarsa geri alınan yazma da yaklaşık iki katına çıkar.

// kume/model.mjs — cogaltma kumesi MODELIDIR. Tur soyut bir adimdir; yayilim gecikmesi,
// algilama esigi ve secim suresi tur cinsinden parametrelerdir, olculmus sure degildir.
// Gercek kume kurulmaz. Yayilim CEKME yonludur: ikincil birincilin gunlugunu okur, birincil
// durdugunda henuz okunmamis yazma hicbir uyeye ulasmaz.
export function kosum({ uye, gecikme, dusen = [], kural = "en-guncel", oncelikli = 3,
                        ariza = 13, algilama = 2, secim = 2, hiz = 3, tur: N = 24 }) {
  const cogunluk = Math.floor(uye / 2) + 1;
  const kapali = new Set();
  const kayit = [0];                       // tur -> birincilin o turda kabul ettigi son sira
  const uygulanan = Array(uye).fill(0);
  let birincil = 0, sira = 0, bekleme = 0, esik = algilama + secim, red = 0;
  let yazmasiz = 0, kabulEski = null, yeni = null, geriAlinan = null;

  for (let t = 1; t <= N; t += 1) {
    if (t === ariza) {                     // birincil ve varsa ikinci uye ayni turda duser
      kabulEski = sira;
      for (const i of [birincil, ...dusen]) kapali.add(i);
      birincil = null;
    }
    if (birincil === null) {
      yazmasiz += 1; bekleme += 1;
      const oy = [...Array(uye).keys()].filter((i) => !kapali.has(i));
      if (oy.length < cogunluk || bekleme !== esik) continue;   // cogunluk yoksa secim hic baslamaz
      const enGuncel = oy.reduce((a, b) => (uygulanan[b] > uygulanan[a] ? b : a));
      const aday = kural === "oncelikli" && red === 0 && !kapali.has(oncelikli) ? oncelikli : enGuncel;
      if (oy.some((i) => uygulanan[i] > uygulanan[aday])) {     // cogunluk kurali adayi reddeder
        red += 1; esik += secim; continue;                      // ikinci secim turu
      }
      yeni = aday;
      geriAlinan = kabulEski - uygulanan[yeni];
      sira = uygulanan[yeni];
      for (let x = 0; x < kayit.length; x += 1) kayit[x] = Math.min(kayit[x], sira); // gunluk kirpilir
      birincil = yeni;
      continue;
    }
    sira += hiz;                            // her turda hiz kadar odunc kaydi birincile yazilir
    kayit[t] = sira;
    for (let i = 0; i < uye; i += 1) {
      if (kapali.has(i)) continue;
      uygulanan[i] = i === birincil ? sira : Math.max(uygulanan[i], kayit[t - gecikme[i]] ?? 0);
    }
  }
  return { cogunluk, oy: uye - kapali.size, yazmasiz, geriAlinan, yeni, kabulEski, red, uygulanan };
}

Modelin bir satırı bütün ödünleşimi taşıyor: aday, oy veren hiçbir üyeden geride olamaz. Çoğunluk kuralının gerçek işlevi oy saymak değil, seçilen üyenin elindeki günlüğün oy veren çoğunluğunkinden eski olmamasını güvence altına almaktır.

// kume/olc.mjs — ayni ariza, dort kume ayari; sonra ayni kumede iki secim kurali
import { kosum } from "./model.mjs";

const G = [0, 2, 3, 3, 5];                 // uye basina yayilim gecikmesi (tur)
const s = (x, n) => String(x).padStart(n);
console.log("24 tur, her turda 3 odunc kaydi. Birincil 13. turda durur; algilama 2, secim 2 tur.");
console.log("durmadan once 36 kayit kabul edilmisti.\n");
console.log("kume | dusen uye | cogunluk | oy verebilen | secim | yazmasiz tur | geri alinan | yeni birincil");
console.log("-----|-----------|----------|--------------|-------|--------------|-------------|--------------");
const AYAR = [
  [3, [], "u0"], [3, [1], "u0+u1"], [4, [1], "u0+u1"], [5, [1], "u0+u1"], [5, [4], "u0+u4"],
];
for (const [uye, dusen, ad] of AYAR) {
  const r = kosum({ uye, gecikme: G.slice(0, uye), dusen });
  console.log(`${s(uye, 4)} | ${ad.padEnd(9)} | ${s(r.cogunluk, 8)} | ${s(r.oy, 12)} | ` +
    `${(r.yeni === null ? "yok" : "var").padStart(5)} | ${s(r.yazmasiz, 12)} | ` +
    `${s(r.geriAlinan === null ? "-" : r.geriAlinan, 11)} | ${r.yeni === null ? "yok" : "u" + r.yeni}`);
}

console.log("\n5 uyeli kume, u0+u4 duser; aday secme kurali degisiyor:");
console.log("kural      | reddedilen aday | secim turu | yazmasiz tur | geri alinan | yeni birincil");
console.log("-----------|-----------------|------------|--------------|-------------|--------------");
for (const kural of ["en-guncel", "oncelikli"]) {
  const r = kosum({ uye: 5, gecikme: G, dusen: [4], kural, oncelikli: 3 });
  console.log(`${kural.padEnd(10)} | ${s(r.red, 15)} | ${s(r.red + 1, 10)} | ${s(r.yazmasiz, 12)} | ` +
    `${s(r.geriAlinan, 11)} | u${r.yeni}`);
}

console.log("\nkosumdan bagimsiz: cogunluk = floor(n/2)+1, katlanilan uye kaybi = n - cogunluk");
console.log("n        : " + [3, 4, 5, 6, 7].map((n) => s(n, 3)).join(""));
console.log("cogunluk : " + [3, 4, 5, 6, 7].map((n) => s(Math.floor(n / 2) + 1, 3)).join(""));
console.log("kayip    : " + [3, 4, 5, 6, 7].map((n) => s(n - (Math.floor(n / 2) + 1), 3)).join(""));

24 tur, her turda 3 odunc kaydi. Birincil 13. turda durur; algilama 2, secim 2 tur.
durmadan once 36 kayit kabul edilmisti.

kume | dusen uye | cogunluk | oy verebilen | secim | yazmasiz tur | geri alinan | yeni birincil
-----|-----------|----------|--------------|-------|--------------|-------------|--------------
   3 | u0        |        2 |            2 |   var |            4 |           6 | u1
   3 | u0+u1     |        2 |            1 |   yok |           12 |           - | yok
   4 | u0+u1     |        3 |            2 |   yok |           12 |           - | yok
   5 | u0+u1     |        3 |            3 |   var |            4 |           9 | u2
   5 | u0+u4     |        3 |            3 |   var |            4 |           6 | u1

5 uyeli kume, u0+u4 duser; aday secme kurali degisiyor:
kural      | reddedilen aday | secim turu | yazmasiz tur | geri alinan | yeni birincil
-----------|-----------------|------------|--------------|-------------|--------------
en-guncel  |               0 |          1 |            4 |           6 | u1
oncelikli  |               1 |          2 |            6 |           6 | u1

kosumdan bagimsiz: cogunluk = floor(n/2)+1, katlanilan uye kaybi = n - cogunluk
n        :   3  4  5  6  7
cogunluk :   2  3  3  4  4
kayip    :   1  1  2  2  3

Sayıların Okunması

Çift sayılı küme fazladan hiçbir şey katmıyor. Son bloktaki üç satır koşumdan bağımsızdır ve yalnız aritmetiktir: dört üyeli kümede çoğunluk 3, üç üyeli kümede 2; ikisi de tek bir üye kaybına dayanır. Dördüncü üye saklanan veriyi bir kat artırır ve katlanılan kaybı hiç büyütmez. Tabloda bu doğrudan görünüyor: üç üyeli ve dört üyeli kümeler iki üye düştüğünde aynı sonucu veriyor — seçim yok, yazmasız tur 12.

Seçimin gerçekleşmediği satırlarda ölçülen şey bir kesintidir. İki üyesi düşen üç üyeli kümede ayakta kalan tek üye vardır ve elinde en yeni veri de olabilir; yine de birincil olamaz, çünkü çoğunluk 2’dir. Bu, kaybedilmiş bir fırsat değil, kuralın kendisidir: ayakta kalan üye komşusunun kendisinden habersiz bir yazma almadığını doğrulayamaz. Kalan 12 turda tek bir ödünç kaydı kabul edilmez.

Geri alınan yazma sayısını hangi üyenin düştüğü belirliyor. Beş üyeli kümenin iki satırı bunu tek başına gösteriyor. u0+u1 düştüğünde en güncel ayakta üye u2’dir ve 27. kayda kadar uygulamıştır: 36 − 27 = 9 ödünç kaydı geri alınır. u0+u4 düştüğünde ise u1 ayaktadır ve 30. kayda kadar uygulamıştır: geri alınan 6. Aynı küme, aynı arıza süresi, aynı çoğunluk — tek fark düşen ikinci üyenin kimliği ve sonuç yüzde elli daha fazla geri alınan yazma. Bu sayı, birincilin kabul ettiği ama hiçbir hayatta kalan üyeye ulaşmamış yazmaların sayısıdır.

Geri alınan yazma bir veri kaybı değildir, ondan daha sinsi bir şeydir: kabul edilmiş ve başarılı diye bildirilmiş bir ödünç kaydının sonradan yok sayılmasıdır. Üye tarafından yazılan istek yanıt almıştır; ödünç işlemi kayıtta yoktur. Bu farkın nasıl kapatılacağı bu dersin değil, onay düzeyi ayarlarının konusudur.

Adayın Seçilmesi

İkinci tablo aynı kümede aynı arızayı iki aday seçme kuralıyla koşturuyor. en-guncel kuralında aday, oy verenler arasındaki en güncel üyedir ve çoğunluk kuralı onu ilk turda kabul eder. oncelikli kuralında belirli bir üye — örneğin ana binadaki üye — aday olarak öne çıkarılır; model bu üyeyi u3 olarak alıyor ve u3 27. kayda kadar uygulamıştır.

Sonuç, çoğunluk kuralının ne yaptığını gösteriyor: u1 üyesi 30. kayda kadar uygulamış olduğu için u3‘ün adaylığı reddediliyor. Reddedilen aday sütunu 1, seçim turu 2 oluyor ve yazmasız tur 4’ten 6’ya çıkıyor. Geri alınan yazma iki kuralda da 6’dır ve bu tesadüf değildir: kural, adayın geride olmasına izin vermediği için sonuçta yine en güncel üye birincil olur. Öncelik ayarının ödediği bedel veri değil, iki tur fazladan kesintidir.

Buradan bir işletme kuralı çıkar: öncelik ayarı ancak öne çıkarılan üye gerçekten güncel kalabiliyorsa ücretsizdir. Yayılım gecikmesi yüksek bir üyeyi öne çıkarmak, her arızada bir seçim turu daha ödemek demektir.

Özet

• Çoğaltma kümesi birincil–ikincil topolojisidir ve İleri Veri Ölçekleme kursundaki ana–kopya düzeniyle aynı kalıptır; iki ad tek bir mekaniği adlandırır.
• Çoğunluk kuralı floor(n/2)+1 oydur ve katlanılan üye kaybı n − çoğunluk’tur: üç ve dört üyeli kümeler tek bir kayba, beş ve altı üyeli kümeler iki kayba dayanır — çift sayılı üye eklemek dayanıklılığı büyütmez.
• İki üyesi düşen üç ve dört üyeli kümelerde seçim hiç başlamadı ve kalan 12 tur boyunca tek bir ödünç kaydı kabul edilmedi; ayakta kalan üyenin elindeki verinin güncelliği bunu değiştirmiyor.
• Aynı arızada geri alınan yazmayı düşen üyenin kimliği belirledi: beş üyeli kümede u0+u1 düştüğünde 9, u0+u4 düştüğünde 6 ödünç kaydı geri alındı.
• Geri alınan yazma, kabul edilmiş ve başarılı diye bildirilmiş bir yazmanın sonradan yok sayılmasıdır; kaynağı, hiçbir hayatta kalan üyeye ulaşmamış olmasıdır.
• Öncelikli aday kuralı çoğunluk kuralınca reddedildiğinde geri alınan yazmayı değiştirmedi ama yazmasız turu 4’ten 6’ya çıkardı.

Sonraki Adım

Bu ders kümenin bir üyeyi kaybettiğinde ne yaptığını ölçtü, ama ölçtüğü her sayı aynı örtük varsayıma dayandı: bütün veri her üyede duruyor. Bu varsayım, çoğaltmanın hiçbir zaman çözemeyeceği bir sınırı beraberinde getirir — kümeye üye eklemek okumayı böler, yazmayı ve saklanan veriyi bölmez. Katalog belge sayısıyla büyüdüğünde ve ödünç kayıtları tek bir üyenin diskine sığmaz olduğunda veriyi üyeler arasında bölmek gerekir. Bölme kararının kendisi tek bir alan seçimine iner ve bu seçim belgenin içinden yapılır. Sonraki ders o alanı seçmenin ölçütlerini sayar: seçilen alanın tekilliği parça başına düşen belge sayısını nasıl dengesizleştirir, artan bir alan neden bütün yazmayı tek parçaya yığar ve aynı sorgu kümesi iki farklı seçimde kaç parçaya dokunur.