İşlemler

Önceki dersin geriye dönük düzeltmesi 3.200 belgeye tek tek dokundu ve konunun şimdiye kadar söylenmemiş bir varsayımını görünür kıldı: her yazma tek bir belgeyi kapsıyordu. Belge modelinin atomiklik güvencesi de tam olarak buradadır. Tek belge atomikliği (single-document atomicity), bir belgeye yapılan yazmanın ya bütünüyle ya hiç gerçekleşmesidir — belge kaç alan, kaç iç içe belge ve kaç dizi ögesi taşırsa taşısın. İki belgeye yapılan iki yazma arasında böyle bir bağ yoktur.

Bu dersin sorusu, kütüphanenin günlük işinin bu güvenceye sığıp sığmadığıdır. Ödünç verme işi bir kopyanın durumunu değiştirir ve bir ödünç kaydı yazar. İki değişikliğin arasında korunması gereken bir değişmez vardır: bir kopya aynı anda birden çok açık ödünçte olamaz. Bu değişmezin tek bir belgenin içine sığıp sığmaması, şemanın kararına bağlıdır.

Bölünmez Yazma ve Çok Belgeli İşlem

Tek belge atomikliğinin sorgu tarafındaki karşılığı koşullu yazmadır: okuma, denetim ve yazma bölünmez tek bir adımdır. İki iş aynı belgeye aynı anda koşullu yazma denerse biri kazanır, öteki koşulun artık sağlanmadığını görür ve hiçbir şey yazmaz.

Çok belgeli işlem (multi-document transaction) aynı güvenceyi birden çok belgeye yayar. Bedeli üç kalemdir: dokunulan her belge için bir geri alma imgesi tutulur, belgeler işlem boyunca kilitli kalır, ve kilidi başkasının elinde bulan işlem iptal edilip baştan denenir. İşlemlerin, yalıtım düzeylerinin ve kilitlemenin kuramı Veri Modelleme ve İlişkisel Kuram ile İlişkisel Veritabanı Yönetimi kurslarında kuruldu; burada ölçülen şey kapsamdır — güvencenin kaç belgeyi sardığı ve bunun neye mal olduğu.

// islem.mjs — tek belge atomikligi ve cok belgeli islem. Tek belge yazmasi kosulludur ve
// bolunmez: okuma, denetim ve yazma tek adimdir. Cok belgeli islem dokundugu her belgeyi
// okurken kilitler, yazmayi hemen uygular ama geri alma imgesini saklar; kilit baskasinin
// elindeyse islem iptal edilir ve imgeler geri yazilir.

export function bayt(d) {                          // 01. dersin kodlama kurali
  if (d === null || d === undefined) return 0;
  if (typeof d === "boolean") return 1;
  if (typeof d === "number") return Number.isInteger(d) ? 4 : 8;
  if (typeof d === "string") return 4 + Buffer.byteLength(d) + 1;
  const oge = Array.isArray(d) ? d.map((v, i) => [String(i), v]) : Object.entries(d);
  return 5 + oge.reduce((t, [a, v]) => t + 2 + Buffer.byteLength(a) + bayt(v), 0);
}

export class Depo {
  constructor() {
    this.derlem = new Map();
    this.kilit = new Map();
    this.o = { yazilanBelge: 0, yazilanBayt: 0, geriAlmaBayt: 0, iptal: 0 };
  }
  d(ad) {
    if (!this.derlem.has(ad)) this.derlem.set(ad, new Map());
    return this.derlem.get(ad);
  }
  bul(ad, k) {                                     // okuma belgenin bir kopyasini verir
    const b = this.d(ad).get(k);
    return b === undefined ? undefined : structuredClone(b);
  }
  yaz(ad, b) {
    this.o.yazilanBelge += 1;
    this.o.yazilanBayt += bayt(b);
    this.d(ad).set(b._k, b);
  }
  // Tek belge atomikligi: oku-denetle-yaz bolunmez. Kosul saglanmazsa hicbir sey olmaz.
  kosulluYaz(ad, k, kosul, uygula) {
    const b = this.bul(ad, k);
    if (b === undefined || !kosul(b)) return false;
    this.yaz(ad, uygula(b));
    return true;
  }
}

export class Islem {
  constructor(depo) {
    Object.assign(this, { depo, kilitli: [], imge: [] });
  }
  kilitle(ad, k) {
    const a = `${ad}/${k}`, sahip = this.depo.kilit.get(a);
    if (sahip === this) return true;
    if (sahip) return false;                       // baskasinin elinde: catisma
    this.depo.kilit.set(a, this);
    this.kilitli.push(a);
    return true;
  }
  oku(ad, k) {                                     // kilitli okuma
    return this.kilitle(ad, k) ? this.depo.bul(ad, k) : this.geriAl();
  }
  yaz(ad, b) {
    if (!this.kilitle(ad, b._k)) return this.geriAl();
    const eski = this.depo.d(ad).get(b._k);
    this.imge.push([ad, b._k, eski]);
    this.depo.o.geriAlmaBayt += bayt(eski);
    this.depo.yaz(ad, b);
    return true;
  }
  isle() {
    this.birak();
    return true;
  }
  geriAl() {                                       // imgeler ters sirada geri yazilir
    for (const [ad, k, eski] of [...this.imge].reverse())
      if (eski === undefined) this.depo.d(ad).delete(k);
      else this.depo.d(ad).set(k, eski);
    this.depo.o.iptal += 1;
    this.birak();
    return undefined;
  }
  birak() {
    for (const a of this.kilitli) this.depo.kilit.delete(a);
    this.kilitli = [];
  }
}

Aynı İş, Üç Düzen

NS7 (varsayım): katalog 20.000 kitap belgesidir, her kitabın 1–5 kopyası vardır, tohum 424242’dir. NS11 (varsayım): ödünç isteklerinin kitaplara dağılımı Zipf biçimindedir. NS29 (varsayım): iş yükü 20.000 ödünç isteğidir, üye sayısı 2.000’dir ve eşzamanlılık modeli her turda 8 isteğin birlikte işlenmesidir; aynı belgeye dokunan ikinci istek çatışma sayılır. Gerekçe: tur genişliği ve üye sayısı çatışmanın mutlak sayısını ölçekler, düzenler arasındaki oranı değiştirmez.

İade modellenmez; ölçülen şey verilen ödüncün bedelidir ve üç düzen de aynı isteklere aynı sırayla yanıt verir. Eş zamanlılık, adım adım ilerleyen iki işin bütün sıralamalarının sayılmasıyla gösterilir — bu bir modeldir, gerçek iş parçacığı kurulmaz.

// islem-olcum.mjs — ayni odunc verme isi uc duzende kosturulur: gomulu semada tek belge
// kosullu yazmasi, referansli semada iki ayri tek belge yazmasi, referansli semada cok
// belgeli islem. Once iki es zamanli odunc butun adim siralamalarinda denenir, sonra
// 20.000 istegin yazma hacmi ile catisma sayisi olculur. Ayni dizinde islem.mjs bulunur.
import { Depo, Islem } from "./islem.mjs";

let cekirdek = 424242;                                   // gorunur tohum
const rast = () => (cekirdek = (cekirdek * 1103515245 + 12345) % 2147483648) / 2147483648;
const SUBE = ["Merkez", "Bahcelievler", "Kadikoy", "Beyoglu", "Konak", "Nilufer"];
const N = 20000, UYE = 2000, ISTEK = 20000, TUR = 8;

const HAM = [];
for (let i = 1; i <= N; i += 1) {
  const kopya = [];
  for (let j = 0, n = 1 + Math.floor(rast() * 5); j < n; j += 1)
    kopya.push({ barkod: `B${String(i * 10 + j).padStart(7, "0")}`,
      sube: SUBE[Math.floor(rast() * 6)], durum: "rafta" });
  HAM.push({ _k: `K-${String(i).padStart(5, "0")}`, yazar: `Yazar ${i % 4000}`,
    yayin_yili: 1950 + (i % 75), kopya });
}
const kur = (kume = HAM) => {
  const depo = new Depo();
  for (const b of kume) {
    depo.d("kitap").set(b._k, structuredClone(b));
    for (const k of b.kopya) depo.d("kopya").set(k.barkod, { _k: k.barkod, kitap: b._k, ...k });
  }
  return depo;
};

// Uc duzen. Her biri uc adimdan olusur; adimlar arasindaki yield es zamanlilik noktasidir.
function* gomulu(depo, kitapK, barkod, uye, no) {
  const kitap = depo.bul("kitap", kitapK);
  const k = kitap.kopya.find((x) => x.barkod === barkod);
  yield;
  if (k.durum !== "rafta") return false;
  yield;
  return depo.kosulluYaz("kitap", kitapK,               // atomik: oku-denetle-yaz bolunmez
    (b) => b.kopya.find((x) => x.barkod === barkod).durum === "rafta",
    (b) => {
      Object.assign(b.kopya.find((x) => x.barkod === barkod),
        { durum: "oduncte", uye, odunc: no });
      return b;
    });
}
function* referansli(depo, kitapK, barkod, uye, no) {
  const kopya = depo.bul("kopya", barkod);
  yield;
  if (kopya.durum !== "rafta") return false;
  depo.yaz("kopya", { ...kopya, durum: "oduncte" });
  yield;
  depo.yaz("odunc", { _k: `O-${no}`, kopya: barkod, uye, acik: true });
  return true;
}
function* islemli(depo, kitapK, barkod, uye, no) {
  const t = new Islem(depo);
  const kopya = t.oku("kopya", barkod);                 // kilitli okuma
  yield;
  if (kopya === undefined) return false;                // catisma: islem iptal edildi
  if (kopya.durum !== "rafta") { t.isle(); return false; }
  if (!t.yaz("kopya", { ...kopya, durum: "oduncte" })) return false;
  yield;
  if (!t.yaz("odunc", { _k: `O-${no}`, kopya: barkod, uye, acik: true })) return false;
  t.isle();
  return true;
}
const DUZEN = [["A gomulu tek belge", gomulu], ["B referansli islemsiz", referansli],
  ["C referansli islem", islemli]];

// 1. olcum: ayni kopya icin iki es zamanli odunc, butun adim siralamalarinda.
const siralamalar = (n, m) => n === 0 ? [Array(m).fill(1)] : m === 0 ? [Array(n).fill(0)]
  : [...siralamalar(n - 1, m).map((s) => [0, ...s]),
    ...siralamalar(n, m - 1).map((s) => [1, ...s])];
const SIRA = siralamalar(3, 3);
const acikOdunc = (depo, barkod) =>
  [...depo.d("kitap").values()].filter((b) =>
    b.kopya.some((k) => k.barkod === barkod && k.durum === "oduncte")).length
  + [...depo.d("odunc").values()].filter((o) => o.kopya === barkod && o.acik).length;

console.log(`ayni kopya icin iki es zamanli odunc, ${SIRA.length} adim siralamasi`);
for (const [ad, duzen] of DUZEN) {
  let ihlal = 0, verilen = 0, iptal = 0;
  for (const s of SIRA) {
    const depo = kur(HAM.slice(0, 1));                  // tek kitap yeter
    const isler = [duzen(depo, "K-00001", "B0000010", "U-0001", 1),
      duzen(depo, "K-00001", "B0000010", "U-0002", 2)];
    const cevap = [undefined, undefined];
    const ilerle = (i) => {
      if (cevap[i] !== undefined) return;
      const r = isler[i].next();
      if (r.done) cevap[i] = r.value === true;
    };
    for (const secim of s) ilerle(secim);
    for (const i of [0, 1]) while (cevap[i] === undefined) ilerle(i);
    const kabul = cevap.filter(Boolean).length, acik = acikOdunc(depo, "B0000010");
    verilen += kabul;
    iptal += depo.o.iptal;
    if (kabul !== acik || acik > 1) ihlal += 1;
  }
  console.log(`  ${ad.padEnd(22)} ihlalli siralama ${String(ihlal).padStart(2)}/${SIRA.length}` +
    `  verilen odunc ${verilen}  iptal ${iptal}`);
}

// 2. olcum: 20.000 odunc istegi. Kitap secimi Zipf, uye 2.000, tur basina 8 istek.
const H = Array.from({ length: N }, (_, i) => 1 / (i + 1)).reduce((a, b) => a + b);
const kumulatif = [];
for (let i = 0, s = 0; i < N; i += 1) kumulatif.push((s += 1 / ((i + 1) * H)));
const cek = (u) => {
  let alt = 0, ust = N - 1;
  while (alt < ust) {
    const orta = (alt + ust) >> 1;
    if (kumulatif[orta] < u) alt = orta + 1; else ust = orta;
  }
  return alt;
};
const ISTEKLER = [];
for (let n = 0; n < ISTEK; n += 1) {
  const kitap = HAM[cek(rast())];
  ISTEKLER.push({ kitapK: kitap._k, barkod: kitap.kopya[n % kitap.kopya.length].barkod,
    uye: `U-${String(n % UYE).padStart(4, "0")}`, no: n });
}
console.log(`${ISTEK} odunc istegi, en cok istenen kitap ` +
  `${ISTEKLER.filter((s) => s.kitapK === "K-00001").length} kez isteniyor`);
for (const [ad, duzen] of DUZEN) {
  const depo = kur();
  let verilen = 0;
  for (const s of ISTEKLER) {
    const g = duzen(depo, s.kitapK, s.barkod, s.uye, s.no);
    let r = g.next();
    while (!r.done) r = g.next();
    if (r.value === true) verilen += 1;
  }
  const o = depo.o;
  console.log(`  ${ad.padEnd(22)} verilen ${verilen}  yazilan belge ${String(o.yazilanBelge).padStart(5)}` +
    `  yazilan bayt ${String(o.yazilanBayt).padStart(7)}  geri alma ${String(o.geriAlmaBayt).padStart(6)} bayt`);
}
// Kilit hedefi duzene gore degisir: gomulu semada kitap belgesi, referansli semada kopya.
const catisma = (hedef) => {
  let n = 0;
  for (let i = 0; i < ISTEK; i += TUR) {
    const gorulen = new Set();
    for (const s of ISTEKLER.slice(i, i + TUR))
      if (gorulen.has(hedef(s))) n += 1; else gorulen.add(hedef(s));
  }
  return n;
};
console.log(`  ${TUR}'li turda catisan istek: kitap belgesi hedefli ${catisma((s) => s.kitapK)}` +
  `, kopya belgesi hedefli ${catisma((s) => s.barkod)}`);

ayni kopya icin iki es zamanli odunc, 20 adim siralamasi
  A gomulu tek belge     ihlalli siralama  0/20  verilen odunc 20  iptal 0
  B referansli islemsiz  ihlalli siralama 12/20  verilen odunc 32  iptal 0
  C referansli islem     ihlalli siralama  0/20  verilen odunc 20  iptal 18
20000 odunc istegi, en cok istenen kitap 1980 kez isteniyor
  A gomulu tek belge     verilen 6212  yazilan belge  6212  yazilan bayt 2102524  geri alma      0 bayt
  B referansli islemsiz  verilen 6212  yazilan belge 12424  yazilan bayt 1009960  geri alma      0 bayt
  C referansli islem     verilen 6212  yazilan belge 12424  yazilan bayt 1009960  geri alma 604903 bayt
  8'li turda catisan istek: kitap belgesi hedefli 1021, kopya belgesi hedefli 296

Değişmezin Sığdığı Yer

İlk üç satır dersin asıl bulgusudur. Gömülü düzende ödünç bilgisi kopyanın içinde, kopya kitap belgesinin içindedir; değişmez tek bir belgenin sınırları içine sığar ve koşullu yazma onu yirmi sıralamanın yirmisinde de korur. Yirmi sıralamada toplam 20 ödünç verilir — her sıralamada tam olarak bir tane. Kaybeden iş bir hata almaz, yalnız koşulun artık sağlanmadığını görür.

Referanslı düzende aynı değişmez iki belgeye yayılır ve yirmi sıralamanın on ikisinde bozulur: iki üye de kopyayı “rafta” okur, ikisi de yazar, ortaya aynı kopya için iki açık ödünç kaydı çıkar. Toplam 32 ödünç verilmiştir, oysa doğru sayı 20’dir. Bu 12 sıralamanın hiçbirinde hata görünmez — iki iş de başarıyla döner, veri sessizce tutarsızlaşır.

Çok belgeli işlem bu on ikiyi kapatır: ihlal 0’a, verilen ödünç 20’ye iner. Bedeli son sütundadır. Yirmi sıralamanın on sekizinde bir iptal olur; yalnız iki sıralamada — iki işin baştan sona ayrı koştuğu sıralamalarda — iptal gerekmez. İşlem, on iki sessiz tutarsızlığı on sekiz görünür iptale çevirir. İptal edilen iş kaybolmaz, yeniden denenir; ama her yeniden deneme bir turluk gecikme ve boşa harcanmış bir yazma demektir.

Kapsamın Bedeli

İkinci ölçüm bedeli iş yükü ölçeğinde verir. Üç düzen de aynı 6.212 ödüncü verir; 20.000 isteğin geri kalanı, istenen kopyanın zaten ödünçte olması yüzünden reddedilir — Zipf dağılımı isteklerin büyük bölümünü aynı birkaç kitaba yığar ve en çok istenen kitap tek başına 1.980 istek alır.

Yazma hacmi ikinci dersin bulgusunu tekrar üretir. Gömülü düzen ödünç başına tek belge yazar ama o belge kitabın tamamıdır: 6.212 yazma, 2.102.524 bayt. Referanslı düzen iki belge yazar, ikisi de küçüktür: 12.424 yazma, 1.009.960 bayt. Belge sayısı iki katına çıkarken bayt yarıya iner.

Çok belgeli işlemin kendi kalemi geri alma imgesidir: 604.903 bayt, yazılan baytın %59,9’u. Bu bayt hiçbir sorguya yanıt vermez, yalnız iptal olasılığı için tutulur ve işlem sona erdiğinde atılır. İşlemin ikinci kalemi çatışmadır ve şemaya bağlıdır. Kilit hedefi gömülü düzende kitap belgesidir, referanslı düzende kopya belgesidir. Sekizli turlarda kitap belgesi hedefli çatışma 1.021, kopya belgesi hedefli çatışma 296’dır — 3,4 kat fark. Gömme okuma yolunu kısaltırken kilit tanesini de büyütür: aynı kitabın farklı kopyalarına yapılan iki ödünç, ayrı belgelerde çatışmazken tek belgede çatışır.

Kararın kuralı buradan çıkar: değişmez hangi belgelere yayılıyorsa kapsam odur, ve şema bu yayılmayı belirler. Tek belgeye sığdırılabilen bir değişmez için çok belgeli işlem kurmak, geri alma imgesini ve iptali karşılıksız ödemektir; sığmayan bir değişmezi işlemsiz bırakmak ise hatasız görünen bir tutarsızlıktır.

Özet

• Tek belge atomikliği, belgeye yapılan yazmanın bütünüyle ya da hiç gerçekleşmesidir; kaç alan ve kaç dizi ögesi değiştiği bunu değiştirmez.
• Değişmez tek belgeye sığdığında koşullu yazma yeter: yirmi adım sıralamasının yirmisinde de tam bir ödünç verilir, iptal olmaz.
• Değişmez iki belgeye yayıldığında yirmi sıralamanın on ikisi bozulur ve 20 yerine 32 ödünç verilir; iki iş de hatasız döner, tutarsızlık sessizdir.
• Çok belgeli işlem ihlali sıfıra indirir ve karşılığında on sekiz iptal ile yazılan baytın %59,9’u kadar (604.903 bayt) geri alma imgesi ödetir.
• Kilit tanesi şemadan gelir: aynı iş yükünde kitap belgesi hedefli çatışma 1.021, kopya belgesi hedefli çatışma 296’dır.

Sonraki Adım

Bu konu belge modelini tip sisteminden çok belgeli işleme kadar götürdü ve her adımda bir kararı sayıya bağladı: gömme kararının okuma yolunu kaç isteğe indirdiği, işleç semantiğinin kaç belge döndürdüğü, boru hattı sırasının kaç kayıt işlettiği, dizinin taranan giriş sayısını nereye çektiği, doğrulama kuralının kaç ihlal ürettiği ve çok belgeli bir işlemin neye mal olduğu. Bütün bu ölçümlerin ortak bir sınırı var: hepsi tek bir düğümde yapıldı. 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 ve bu derste ölçülen kilit, iptal ve atomiklik kavramlarının hepsi orada yeniden tanımlanır. Sonraki konu depoyu dağıtık kuruluma taşır ve ilk soruyu sorar: aynı veri birden çok üyede duruyorsa, bunlardan hangisinin yazma kabul ettiğine kim karar verir.