Bölünmüş Beyin Sorunu

Önceki ders kopyaların aynı belgeleri taşıdığını varsaydı ve bu varsayımla kopyanın kaybolan kümeyi geri getirdiğini ölçtü. Varsayım yalnızca kopyalar birbirini görebildiği sürece geçerlidir. Ağ ikiye ayrıldığında beş kopyalı bir dizin iki ayrı dizine dönüşür: her yarı kendi ters dizinini büyütmeye devam eder, iki yarının gönderi listeleri ayrışır ve aynı sorgu iki farklı sıra döndürmeye başlar. Bu duruma bölünmüş beyin denir. Aynı olgu lider seçimi anlatısında iki liderli tur adıyla ölçülmüştü; seçim mekaniği ve otomatik devralma orada kuruldu ve burada tekrarlanmaz. Buradaki soru arama tarafındandır: azınlıkta kabul edilen bir dizinleme işleminden geriye ne kalır, ve bölünme sürerken sorgu hangi belgeleri döndürmez.

Düzenek

Dizinin beş kopyası var ve ağ üç düğümlük A yarısıyla iki düğümlük B yarısına ayrılıyor. Bölünme sürerken kataloğa 600 yeni kayıt geliyor — tek konudan gelen bir bağış partisi, yani sorgunun tam ortasına düşen belgeler. Bir yazmanın kabul edilmesi için kaç kopyanın onaylaması gerektiği bir ayardır: çoğunluk gerekliliği kapalıyken bir onay yeter, açıkken beş kopyanın çoğunluğu olan üç onay gerekir.

Ölçüt, bölünme hiç olmasaydı oluşacak 4600 belgelik dizinin aynı sorguya verdiği yanıttır. Küme burada da süreç içi bir modeldir: yarılar aynı süreçte ayrı ters dizinlerdir, ağ yerine bir yönlendirme kuralı vardır.

AK5 — bölünme sürerken gelen 600 kaydın yüzde 65’i üç düğümlük yarıya, yüzde 35’i iki düğümlük yarıya ulaşır. Gerekçe: istemciler düğümlere dağıtılmışsa bölünme onları düğüm sayısına göre ayırır. Doğrusal etkilidir. AK6 — bölünme onarıldığında çoğunluk yarısının dizini kanonik kabul edilir. Bir tarafın kazanması gerekir; hangi taraf kazanırsa kazansın öbür tarafın kabul ettiği yazmalar kaybolur.

// kume/derlem.mjs — kutuphane katalogu derlemi ve ters dizin (onceki derslerle ayni uretec ve
// ayni tohum; bu ders yalnizca kullandigi parcalari tasir). Dizin bir sozluk tutar: terim ->
// gonderi listesi; gonderi burada bir belge girisidir (belge kimligi + terim sikligi).
const ORTAK = ["kitap", "yazar", "eser", "metin", "bolum", "baski", "sayfa", "dil", "cilt", "yayin"];
const OZEL = {
  cocuk: ["masal", "resimli", "okul", "oyun", "hayvan", "cizgi"], oyku: ["kisa", "anlati", "derleme", "gunluk", "yalnizlik", "kasaba"],
  roman: ["kahraman", "kent", "kusak", "ev", "yolculuk", "mektup"], tarih: ["imparatorluk", "belge", "arsiv", "savas", "yuzyil", "vakayiname"],
  gezi: ["deniz", "yol", "harita", "sehir", "liman", "gemi"], siir: ["dize", "olcu", "imge", "ses", "sessizlik", "kafiye"],
  deneme: ["dusunce", "elestiri", "okuma", "zaman", "not", "soylesi"], bilim: ["olcum", "deney", "kuram", "veri", "gozlem", "denklem"],
};
const NADIR = ["fener", "kuyu", "ipek", "kule", "bahce", "kar", "ada", "koru", "tas", "cinar", "kirlangic", "demirci", "pusula", "kehribar"];
const KONU = Object.keys(OZEL);

export function derlem({ adet = 4000, tohum = 20260731 } = {}) {
  let s = tohum % 2147483647;
  const r = () => (s = (s * 48271) % 2147483647) / 2147483647;
  const sec = (a) => a[Math.floor(r() * a.length)], belge = [];
  for (let i = 1; i <= adet; i += 1) {
    const konu = sec(KONU), oz = OZEL[konu], soz = [sec(oz), sec(NADIR)];
    if (r() < 0.5) soz.push(sec(ORTAK));
    for (let j = 0, n = 10 + Math.floor(r() * 7); j < n; j += 1)
      soz.push(r() < 0.45 ? sec(ORTAK) : r() < 0.85 ? sec(oz) : sec(NADIR));
    belge.push({ id: i, konu, yil: 1990 + Math.floor(r() * 36), metin: [soz[0], soz[1], konu, ...soz.slice(2)].join(" ") });
  }
  return belge;
}

export function dizinle(belge) {
  const gonderi = new Map(), uzunluk = new Map();
  let bayt = 0;
  for (const d of belge) {
    const t = d.metin.split(" "), sayim = new Map();
    for (const x of t) sayim.set(x, (sayim.get(x) ?? 0) + 1);
    uzunluk.set(d.id, t.length);
    for (const [x, n] of sayim) {
      if (!gonderi.has(x)) { gonderi.set(x, []); bayt += x.length + 4; }
      gonderi.get(x).push([d.id, n]); bayt += 8;                        // kimlik + siklik
    }
  }
  const ort = [...uzunluk.values()].reduce((a, b) => a + b, 0) / (belge.length || 1);
  return { gonderi, uzunluk, N: belge.length, ort, bayt };
}

// Puanlama: terim sikligi, ters belge sikligi ve belge uzunlugu; istatistik bu dizinden okunur.
export function ara(dz, terim, k) {
  const N = dz.N, ort = dz.ort, puan = new Map();
  let taranan = 0;
  for (const t of terim) {
    const g = dz.gonderi.get(t) ?? [], df = g.length;
    const idf = Math.log(1 + (N - df + 0.5) / (df + 0.5));
    for (const [id, tf] of g) {
      taranan += 1;
      const norm = tf + 1.2 * (0.25 + 0.75 * dz.uzunluk.get(id) / ort);
      puan.set(id, (puan.get(id) ?? 0) + idf * tf * 2.2 / norm);
    }
  }
  const sirali = [...puan].sort((a, b) => b[1] - a[1] || a[0] - b[0]).slice(0, k);
  return { aday: sirali.map(([id, p]) => ({ id, p })), taranan, eslesen: puan.size };
}

// kume/bolunme.mjs — bes kopyali bir dizinin uc ve iki dugumluk iki yariya bolunmesi. Kume
// SUREC ICI BIR MODELDIR: yarilar ayni surecte ayri ters dizinlerdir, ag yerine bir yonlendirme
// kurali vardir. Olcut, bolunme hic olmasaydi olusacak dizinin ilk on sonucudur.
import { derlem, dizinle, ara } from "./derlem.mjs";

const N0 = 4000, YENI = 600, KOPYA = 5, AD = 3, BD = 2, K = 10;
const SORGU = ["kisa", "oyku", "yalnizlik"];
const s = (x, n) => String(x).padStart(n);

const taban = derlem({ adet: N0 });
// Bolunme sirasinda kataloglanan yeni parti: tek konudan gelen bir bagis. Ayri bir tohumla
// uretilir, kimlikler N0 sonrasina tasinir; icerigine el degdirilmez.
const parti = derlem({ adet: 9000, tohum: 20260801 }).filter((d) => d.konu === "oyku")
  .slice(0, YENI).map((d, i) => ({ ...d, id: N0 + i + 1 }));
const aYeni = parti.filter((d) => d.id % 20 < 13);   // istemcilerin %65'i uc dugumluk yariya
const bYeni = parti.filter((d) => d.id % 20 >= 13);  // %35'i iki dugumluk yariya
const olcut = dizinle([...taban, ...parti]), olcutSon = ara(olcut, SORGU, K);
const olcutIlk = olcutSon.aday.map((x) => x.id), hedef = olcutSon.eslesen;

const bak = (belge) => {                       // bir dizinin bu sorguya verdigi kume ve sira
  const dz = dizinle(belge), r = ara(dz, SORGU, K);
  const ilk = r.aday.map((x) => x.id);
  return { adet: belge.length, eslesen: r.eslesen, ilk, ortak: ilk.filter((x) => olcutIlk.includes(x)).length };
};

console.log(`${N0} belge dizinde, bolunme sirasinda ${YENI} yeni kayit geliyor. ${KOPYA} kopya,`);
console.log(`yarilar ${AD} ve ${BD} dugum. Tohum 20260731. Olcut: bolunme olmasaydi ${N0 + YENI} belgelik dizin,`);
console.log(`sorgu "kisa oyku yalnizlik", eslesen ${hedef} belge.\n`);

console.log("cogunluk | W | A kabul | B kabul | B red | onarimda kaybolan | yazma iletisi | onarim sonrasi belge");
console.log("---------|---|---------|---------|-------|-------------------|---------------|---------------------");
const sonuc = {};
for (const cogunluk of [false, true]) {
  const W = cogunluk ? Math.floor(KOPYA / 2) + 1 : 1;
  const bKabul = cogunluk && BD < W ? 0 : bYeni.length;
  const bRed = bYeni.length - bKabul;
  const kayip = cogunluk ? 0 : bKabul;                   // onarimda cogunluk yarisinin dizini kanonik
  const ileti = aYeni.length * Math.min(W, AD) + bKabul * Math.min(W, BD) + bRed * BD;
  const sonrasi = taban.length + aYeni.length + (cogunluk ? bRed : 0);   // red edilenler yeniden gonderilir
  sonuc[cogunluk] = { W, bKabul, sonrasi };
  console.log(`${(cogunluk ? "acik" : "kapali").padEnd(8)} | ${s(W, 1)} | ${s(aYeni.length, 7)} | ${s(bKabul, 7)} | ` +
    `${s(bRed, 5)} | ${s(kayip, 17)} | ${s(ileti, 13)} | ${s(sonrasi, 20)}`);
}

console.log("\nbolunme surerken ayni sorgu (olcut: bolunme olmasaydi donecek ilk 10):");
console.log("cogunluk | yari | dugum | dizindeki belge | eslesen | eksik | ilk 10 ortak | ilk 5 sonuc");
for (const cogunluk of [false, true]) {
  for (const [ad, dugum, ek] of [["A", AD, aYeni], ["B", BD, sonuc[cogunluk].bKabul ? bYeni : []]]) {
    const r = bak([...taban, ...ek]);
    console.log(`${(cogunluk ? "acik" : "kapali").padEnd(8)} | ${ad.padEnd(4)} | ${s(dugum, 5)} | ${s(r.adet, 15)} | ` +
      `${s(r.eslesen, 7)} | ${s(hedef - r.eslesen, 5)} | ${s(r.ortak + "/10", 12)} | ${r.ilk.slice(0, 5).join(" ")}`);
  }
}

console.log("\nonarimdan sonra:");
console.log("cogunluk | dizindeki belge | eslesen | ilk 10 ortak | ilk 5 sonuc");
for (const cogunluk of [false, true]) {
  const ek = cogunluk ? [...aYeni, ...bYeni] : aYeni;
  const r = bak([...taban, ...ek]);
  console.log(`${(cogunluk ? "acik" : "kapali").padEnd(8)} | ${s(r.adet, 15)} | ${s(r.eslesen, 7)} | ` +
    `${s(r.ortak + "/10", 12)} | ${r.ilk.slice(0, 5).join(" ")}`);
}
console.log(`olcut    | ${s(olcut.N, 15)} | ${s(hedef, 7)} | ${s("10/10", 12)} | ${olcutIlk.slice(0, 5).join(" ")}`);
console.log(`\nkosumdan bagimsiz: ${KOPYA} kopyada cogunluk ${Math.floor(KOPYA / 2) + 1}'tur ve iki ayrik yari` +
  ` ayni anda cogunluk olamaz, cunku ${Math.floor(KOPYA / 2) + 1} + ${Math.floor(KOPYA / 2) + 1} > ${KOPYA}.`);

4000 belge dizinde, bolunme sirasinda 600 yeni kayit geliyor. 5 kopya,
yarilar 3 ve 2 dugum. Tohum 20260731. Olcut: bolunme olmasaydi 4600 belgelik dizin,
sorgu "kisa oyku yalnizlik", eslesen 1115 belge.

cogunluk | W | A kabul | B kabul | B red | onarimda kaybolan | yazma iletisi | onarim sonrasi belge
---------|---|---------|---------|-------|-------------------|---------------|---------------------
kapali   | 1 |     390 |     210 |     0 |               210 |           600 |                 4390
acik     | 3 |     390 |       0 |   210 |                 0 |          1590 |                 4600

bolunme surerken ayni sorgu (olcut: bolunme olmasaydi donecek ilk 10):
cogunluk | yari | dugum | dizindeki belge | eslesen | eksik | ilk 10 ortak | ilk 5 sonuc
kapali   | A    |     3 |            4390 |     905 |   210 |         8/10 | 4544 3159 3544 2689 2362
kapali   | B    |     2 |            4210 |     725 |   390 |         8/10 | 4457 4534 3159 3544 2689
acik     | A    |     3 |            4390 |     905 |   210 |         8/10 | 4544 3159 3544 2689 2362
acik     | B    |     2 |            4000 |     515 |   600 |         6/10 | 3159 3544 2689 2362 3370

onarimdan sonra:
cogunluk | dizindeki belge | eslesen | ilk 10 ortak | ilk 5 sonuc
kapali   |            4390 |     905 |         8/10 | 4544 3159 3544 2689 2362
acik     |            4600 |    1115 |        10/10 | 4457 4534 4544 3159 3544
olcut    |            4600 |    1115 |        10/10 | 4457 4534 4544 3159 3544

kosumdan bagimsiz: 5 kopyada cogunluk 3'tur ve iki ayrik yari ayni anda cogunluk olamaz, cunku 3 + 3 > 5.

Azınlıkta Kabul Edilen Yazma

Birinci tablo iki ayarın yazma tarafını gösteriyor. Çoğunluk kapalıyken her iki yarı da yazma kabul ediyor: A 390, B 210. Kütüphaneci açısından bu 600 kaydın altı yüzü de başarıyla kataloglanmıştır — her biri onay almıştır. Onarımda AK6 devreye giriyor ve azınlık yarısının kabul ettiği 210 kayıt kayboluyor. Bu kayıtlar hata döndürmedi, bir kuyrukta beklemiyor, yeniden gönderilecek bir listede değil; onay verilmiş ve sonra yok olmuşlardır.

Çoğunluk açıkken aynı 210 istek en baştan reddediliyor. Fark, kaybın nereye düştüğüdür: reddedilen bir istek istemcinin elinde kalır ve bölünme onarıldığında yeniden gönderilebilir. Kaybolan sütunu 0, onarım sonrası dizin 4600 belge. İki ayar aynı ağ arızasını yaşadı ve biri 210 kaydı sessizce yuttu, öbürü 210 kez görünür biçimde reddetti.

Bedel yazma iletisi sütununda: 600 iletiden 1590’a. Çoğunluk her kabul edilen yazma için üç onay ister, üstelik reddedilen istekler de azınlık yarısında iki düğüme dokunduktan sonra başarısız olur. Bu, yazma başına yaklaşık 2,65 katlık bir ileti artışıdır ve gecikmeye doğrudan yansır.

Son satırdaki koşumdan bağımsız sayı bu ayarın neden işe yaradığını söyler: beş kopyada çoğunluk üçtür ve iki ayrık yarı aynı anda çoğunluk olamaz, çünkü 3 + 3 beşten büyüktür. Bu bir ayar değil, bir aritmetik.

Bölünme Sürerken Sorgu

İkinci tablo aynı sorgunun bölünme sürerken ne döndürdüğünü sayıyor. Bölünme hiç olmasaydı 1115 belge eşleşecekti.

Çoğunluk kapalıyken iki yarı da yanıt veriyor ve ikisi de eksik: A 905 belge (210 eksik), B 725 belge (390 eksik). İlk beş sıralamaları da ayrışıyor. A yarısı 4544 ile başlıyor, B yarısı 4457 ve 4534 ile. Bu üç kayıt da bağış partisinden geliyor ve her biri yalnızca kendi yarısında var. Aynı katalog sorusunu iki farklı uçtan soran iki kütüphaneci, aynı anda, birbiriyle çelişen iki liste alır. Bölünmüş beynin arama tarafındaki karşılığı budur: yanlış bir yanıt değil, iki ayrı doğru.

Çoğunluk açıkken B yarısının dizini 4000 belgede donuyor: 515 eşleşme, 600 eksik belge ve ilk onda ölçütle ortak yalnızca 6 belge. Azınlık yarısı yanıt vermeyi sürdürüyor ama bayat bir dizinden yanıt veriyor. Bu ayarın verdiği güvence dönen kümenin eksiksizliği değildir; verdiği güvence, azınlığın dizini ileriye taşımamasıdır.

Onarımdan Sonra

Üçüncü tablo son durumu ölçütle karşılaştırıyor. Çoğunluk kapalıyken dizin 4390 belgede kalıyor: 905 eşleşme, ilk onda 8/10 ve ilk beşte ölçütün ilk iki kaydı (4457, 4534) hiç yok. Bu iki kayıt geri gelmez; onları yeniden dizine sokmanın tek yolu bağış partisinin kaynağına dönüp 210 kaydı elden yeniden kataloglamaktır.

Çoğunluk açıkken onarımdan sonraki dizin 4600 belge, 1115 eşleşme ve ilk on ölçütle birebir aynı. Reddedilen 210 istek yeniden gönderildiği için sonuç, bölünme hiç yaşanmamış gibi. Çoğunluk gerekliliği arızayı önlemedi — ağ yine bölündü ve azınlık yarısı 600 kayıt boyunca eksik yanıt verdi. Önlediği şey, arızanın kalıcı olmasıydı.

Özet

• Çoğunluk kapalıyken iki yarı da yazma kabul etti (390 ve 210) ve onarımda azınlığın kabul ettiği 210 kayıt kayboldu; bu kayıtlar istemciye onay verilmiş kayıtlardır.
• Çoğunluk açıkken aynı 210 istek reddedildi, kaybolan 0 oldu ve istekler onarımdan sonra yeniden gönderilerek dizin 4600 belgeye çıktı.
• Çoğunluğun bedeli yazma iletisidir: 600 iletiden 1590’a, yazma başına yaklaşık 2,65 kat.
• Bölünme sürerken çoğunluk kapalıyken A yarısı 905, B yarısı 725 belge döndürdü ve ilk beş listeleri ayrıştı: A 4544 ile, B 4457 ile başladı. Aynı soru iki çelişik yanıt aldı.
• Çoğunluk açıkken azınlık yarısı 4000 belgelik bayat dizinden 515 eşleşme döndürdü: 600 eksik belge ve ilk onda 6/10. Güvence eksiksiz yanıt değil, azınlığın dizini ilerletmemesidir.
• Onarım sonrası çoğunluk kapalı ayarda 905 eşleşme ve 8/10 kaldı; açık ayarda sonuç bölünme hiç olmamış gibi 1115 eşleşme ve 10/10 oldu.

Sonraki Adım

Bu ders 600 kaydı tek tek, her biri ayrı bir istekmiş ve kabul edilir edilmez aranabilir olurmuş gibi saydı. İki varsayım da ölçülmedi. Bir katalog partisi gerçekte tek tek değil yığın hâlinde gelir ve her kaydı ayrı bir istekle göndermekle hepsini tek istekte göndermek aynı şey değildir: istek sayısı, oluşan bölüt sayısı ve toplam süre değişir. Dizine giren bir belgenin aranabilir hâle gelmesi de anlık değildir; belge önce bir tampona yazılır ve ancak bir yenileme işlemiyle sorgulara görünür. Sonraki ders aynı 4000 belgelik derlemi tek tek ve toplu olarak dizinler, istek ile bölüt sayısını karşılaştırır, sonra yenileme aralığını değiştirip görünürlük gecikmesiyle yazma verimi arasındaki takası sayar.