Gömme ve Referans

Önceki ders tek bir belgenin içine baktı: alan adının ve tip etiketinin bayt bedeli sayıldı, aynı alanın iki tipte yazılmasının aralık sorgusunda 3.990 yerine 3.491 ya da 5.991 belge döndürdüğü görüldü. Katalog ise tek bir belgeden ibaret değildir. Kitap, kopya, üye ve ödünç kayıtları birbirine bağlıdır ve belge modeli bu bağı iki yoldan kurmaya izin verir.

Gömme (embedding), ilgili veriyi belgenin içine, iç içe bir belge ya da dizi olarak koymaktır. Referans (referencing), veriyi ayrı bir derlemde tutup belgede yalnız anahtarını taşımaktır. İkisi de aynı katalogu saklar; ayrıldıkları yer okuma yolunda kaç gidiş yapıldığı, ne kadar bayt okunduğu, bir güncellemede kaç belgenin yeniden yazıldığı ve belgenin ne kadar büyüdüğüdür. Bu ders o dört sayıyı üretir. Normalleştirme ile denormalizasyonun aritmetiği Veri Modelleme ve İlişkisel Kuram ile Veri Katmanı Ölçekleme kurslarında ölçüldü; burada tekrarlanmaz, ölçülen şey belge modeline özgü olan yandır.

Sayan Bir Depo

Ölçüm için küçük bir belge deposu yazılır. Depo derlemleri tutar, anahtarla erişimi ve tam taramayı ayırır, her erişimde gidiş sayısını, okunan belge sayısını ve okunan baytı sayar. Bir de belge boyutu sınırı vardır: sınırı aşan yazma reddedilir. Eşitlik eşlemesi yalnız karşılaştırmanın adil olması için bulunur; dizinin kendi aritmetiği bu konunun beşinci dersinin konusudur.

// belgedepo.mjs — kucuk bir belge deposu: derlemler, anahtarla erisim, tarama, esitlik
// eslemesi ve belge boyutu siniri. Her erisim gidis, okunan belge ve bayt olarak sayilir.

// 01. dersin kodlamasinin bayt kurali: sabit boylu tip boyunu etiketinden alir,
// degisken boylu tip 4 baytlik uzunluk on eki tasir, her alan 1 bayt etiket + ad + NUL.
export function bayt(d) {
  if (d === null) return 0;
  if (typeof d === "boolean") return 1;
  if (typeof d === "number") return Number.isInteger(d) ? 4 : 8;
  if (d instanceof Date) return 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(sinir = 16384) {
    this.derlem = new Map();
    this.dizin = new Map();
    this.sinir = sinir;
    this.sifirla();
  }
  sifirla() {
    this.o = { gidis: 0, okunanBelge: 0, okunanBayt: 0, yazilanBelge: 0, yazilanBayt: 0 };
  }
  d(ad) {
    if (!this.derlem.has(ad)) this.derlem.set(ad, new Map());
    return this.derlem.get(ad);
  }
  yaz(ad, belge) {
    const n = bayt(belge);
    if (n > this.sinir) throw new Error(`belge boyutu siniri asildi: ${n} > ${this.sinir}`);
    this.d(ad).set(belge._k, belge);
    this.o.yazilanBelge += 1;
    this.o.yazilanBayt += n;
    return n;
  }
  oku(b) {
    this.o.okunanBelge += 1;
    this.o.okunanBayt += bayt(b);
    return b;
  }
  bul(ad, k) {                                   // anahtarla erisim: bir gidis, bir belge
    this.o.gidis += 1;
    const b = this.d(ad).get(k);
    return b ? this.oku(b) : undefined;
  }
  tara(ad, kosul) {                              // tam tarama: derlemin tamami okunur
    this.o.gidis += 1;
    return [...this.d(ad).values()].filter((b) => kosul(this.oku(b)));
  }
  esitlikEslemesi(ad, alan) {                    // dizin aritmetigi 05. dersin konusu
    const m = new Map();
    for (const b of this.d(ad).values()) {
      const v = b[alan];
      if (!m.has(v)) m.set(v, []);
      m.get(v).push(b._k);
    }
    this.dizin.set(`${ad}.${alan}`, m);
  }
  ara(ad, alan, deger) {
    this.o.gidis += 1;
    const anahtarlar = this.dizin.get(`${ad}.${alan}`).get(deger) ?? [];
    return anahtarlar.map((k) => this.oku(this.d(ad).get(k)));
  }
}

Üç İş, İki Şema

NS7 (varsayım): katalogda 20.000 kitap vardır, her kitabın 1–5 kopyası bulunur, tohum 424242’dir. NS9 (varsayım): kütüphanenin üç işi vardır — kitap sayfasını açmak (bir kitap ve bütün kopyaları), bir şubedeki onarımdaki kopyaları listelemek ve bir kopyanın durumunu değiştirmek. Üçü de iki şemada koşturulur.

// gomme-referans.mjs — ayni katalog iki semada kurulur: kopyalar kitaba gomulu, ya da
// ayri derlemde referansli. Uc is her iki semada kosturulur ve fark sayilir.
// Ayni dizinde belgedepo.mjs bulunur.
import { Depo, bayt } from "./belgedepo.mjs";

let cekirdek = 424242;                                   // gorunur tohum
const rast = () => (cekirdek = (cekirdek * 1103515245 + 12345) % 2147483648) / 2147483648;
const SUBE = ["Merkez", "Bahcelievler", "Kadikoy", "Beyoglu", "Konak", "Nilufer"];
const DURUM = ["rafta", "oduncte", "onarimda"];
const N = 20000;

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() * SUBE.length)],
      durum: DURUM[Math.floor(rast() * DURUM.length)] });
  ham.push({ _k: `K-${String(i).padStart(5, "0")}`, baslik: `Kitap ${i} uzerine incelemeler`,
    yazar: `Yazar ${i % 4000}`, yayin_yili: 1950 + (i % 75), kopya });
}
const KOPYA_SAYISI = ham.reduce((t, b) => t + b.kopya.length, 0);

const gomulu = new Depo();
for (const b of ham) gomulu.yaz("kitap", b);
const referansli = new Depo();
for (const b of ham) {
  referansli.yaz("kitap", { _k: b._k, baslik: b.baslik, yazar: b.yazar, yayin_yili: b.yayin_yili });
  for (const k of b.kopya)
    referansli.yaz("kopya", { _k: k.barkod, kitap: b._k, sube: k.sube, durum: k.durum });
}
referansli.esitlikEslemesi("kopya", "kitap");
referansli.esitlikEslemesi("kopya", "sube");

const yaz = (baslik, o) => console.log(`${baslik.padEnd(26)} gidis ${String(o.gidis).padStart(2)}` +
  `  okunan belge ${String(o.okunanBelge).padStart(6)}  okunan bayt ${String(o.okunanBayt).padStart(8)}`);

console.log(`kitap ${N}, kopya ${KOPYA_SAYISI} (kitap basina ${(KOPYA_SAYISI / N).toFixed(2)})`);
console.log(`derlem boyutu: gomulu kitap ${[...gomulu.d("kitap").values()].reduce((t, b) => t + bayt(b), 0)}` +
  `  referansli kitap+kopya ${[...referansli.d("kitap").values()].reduce((t, b) => t + bayt(b), 0)
  + [...referansli.d("kopya").values()].reduce((t, b) => t + bayt(b), 0)}`);

// IS 1 — kitap sayfasi: bir kitap ve butun kopyalari.
gomulu.sifirla(); referansli.sifirla();
gomulu.bul("kitap", "K-04242");
yaz("is1 gomulu", gomulu.o);
referansli.bul("kitap", "K-04242");
referansli.ara("kopya", "kitap", "K-04242");
yaz("is1 referansli", referansli.o);

// IS 2 — bir subedeki onarimdaki kopyalar.
gomulu.sifirla(); referansli.sifirla();
const g2 = gomulu.tara("kitap", (b) => b.kopya.some((k) => k.sube === "Kadikoy" && k.durum === "onarimda"));
yaz("is2 gomulu", gomulu.o);
const r2 = referansli.ara("kopya", "sube", "Kadikoy").filter((k) => k.durum === "onarimda");
yaz("is2 referansli", referansli.o);
console.log(`is2 sonuc: gomulu ${g2.length} kitap belgesi, referansli ${r2.length} kopya belgesi`);

// IS 3 — 5.000 kopyanin durumu degisir.
gomulu.sifirla(); referansli.sifirla();
for (let i = 0; i < 5000; i += 1) {
  const kitap = ham[(i * 7) % N];
  const hedef = kitap.kopya[i % kitap.kopya.length];
  const g = gomulu.bul("kitap", kitap._k);
  g.kopya.find((k) => k.barkod === hedef.barkod).durum = "rafta";
  gomulu.yaz("kitap", g);
  const r = referansli.bul("kopya", hedef.barkod);
  referansli.yaz("kopya", { ...r, durum: "rafta" });
}
console.log(`is3 gomulu     yazilan belge ${gomulu.o.yazilanBelge}  yazilan bayt ${gomulu.o.yazilanBayt}`);
console.log(`is3 referansli yazilan belge ${referansli.o.yazilanBelge}  yazilan bayt ${referansli.o.yazilanBayt}`);

kitap 20000, kopya 58595 (kitap basina 2.93)
derlem boyutu: gomulu kitap 6149233  referansli kitap+kopya 6612373
is1 gomulu                 gidis  1  okunan belge      1  okunan bayt      454
is1 referansli             gidis  2  okunan belge      6  okunan bayt      502
is2 gomulu                 gidis  1  okunan belge  20000  okunan bayt  6149233
is2 referansli             gidis  1  okunan belge  10066  okunan bayt   781096
is2 sonuc: gomulu 2934 kitap belgesi, referansli 3092 kopya belgesi
is3 gomulu     yazilan belge 5000  yazilan bayt 1541395
is3 referansli yazilan belge 5000  yazilan bayt 381255

Üç iş üç ayrı yöne işaret eder. Kitap sayfasında gömme kazanır: tek gidişte 454 bayt okunur, referanslı şemada aynı bilgi iki gidiş ve altı belge ile, 502 bayt okunarak toplanır. Fark bayt tarafında küçüktür (%10,6), gidiş tarafında iki katıdır — ve gidiş, depoya uzaktan bağlanan bir uygulama için baytdan pahalı bir birimdir.

Şube sorgusunda yön tersine döner. Gömülü şemada kopya, kitabın içindedir; bir şubenin kopyalarını bulmak için 20.000 kitap belgesinin tamamı okunur, 6.149.233 bayt. Referanslı şemada kopya kendi derlemindedir ve şubeye göre eşlenebilir: 10.066 belge, 781.096 bayt. Aynı soruya yanıt için okunan bayt 7,9 kat düşer. İki sonucun farklı sayıda olması da öğreticidir: gömülü tarama 2.934 kitap döndürür, referanslı sorgu 3.092 kopya — aynı kitabın aynı şubede onarımdaki iki kopyası olabilir ve gömülü şemada bu ayrım belgenin içinde kalır.

Yazma yolu üçüncü yönü verir. Bir kopyanın durumu değiştiğinde gömülü şemada kitabın tamamı yeniden yazılır: 5.000 değişiklik 1.541.395 bayt yazar, değişiklik başına 308 bayt. Referanslı şemada yalnız kopya belgesi yeniden yazılır: 381.255 bayt, değişiklik başına 76 bayt. Oran 4,04’tür ve kitabın alan sayısı arttıkça büyür, çünkü değişen alanın yanındaki her alan da yeniden yazılır. Saklanan yer tarafında karar tersine çalışır: referanslı şema 6.612.373 bayt tutar, gömülü şema 6.149.233 — fark, her kopya belgesinin kendi anahtarını ve kitap anahtarını tekrar taşımasıdır.

Sınırsız Büyüyen Dizi

Gömmenin en pahalı biçimi, sonu olmayan bir diziyi gömmektir. Ödünç geçmişi böyledir: kitap sabit kalır, geçmiş sürekli uzar. NS10 (varsayım): deponun belge boyutu sınırı 16.384 bayttır. NS11 (varsayım): üç yılda 1.406.280 ödünç verilir ve dağılım Zipf biçimindedir — r. sıradaki kitabın payı 1/r ile orantılıdır.

// buyume.mjs — odunc gecmisi kitap belgesine gomulurse belge buyur. Sinirsiz gomme ile
// son 20 kaydi gomup gerisini ayri derleme birakan karar karsilastirilir.
// Ayni dizinde belgedepo.mjs bulunur.
import { Depo, bayt } from "./belgedepo.mjs";

const SINIR = 16384, N = 20000, ODUNC = 1406280, SON = 20;
const taban = (i) => ({ _k: `K-${String(i).padStart(5, "0")}`,
  baslik: `Kitap ${i} uzerine incelemeler`, yazar: `Yazar ${i % 4000}`,
  yayin_yili: 1950 + (i % 75), odunc: [] });
const kayit = (n) => ({ uye: `U-${String(n % 90000).padStart(5, "0")}`,
  alis: new Date(2023, 0, 1 + (n % 1095)), iade: new Date(2023, 0, 15 + (n % 1095)) });

// Zipf dagilimi: r. siradaki kitabin payi 1/r ile orantili. Rastgelelik yok.
const H = Array.from({ length: N }, (_, i) => 1 / (i + 1)).reduce((a, b) => a + b);
const pay = Array.from({ length: N }, (_, i) => Math.round(ODUNC / ((i + 1) * H)));
const bosBelge = bayt(taban(1));
const birKayit = bayt({ ...taban(1), odunc: [kayit(1)] }) - bosBelge;
const derlemBayt = (d) => [...d.values()].reduce((t, b) => t + bayt(b), 0);
console.log(`bos kitap belgesi ${bosBelge} bayt, bir odunc kaydi ${birKayit} bayt`);
console.log(`sinir ${SINIR} bayt, kaba hesap: ${Math.floor((SINIR - bosBelge) / birKayit)} kayit`);

// A karari: gecmisin tamami gomulur. Boyut artimli izlenir; n. oge diziye
// 2 + sira adinin uzunlugu + kayit bayti ekler.
const depoA = new Depo(SINIR);
let dayanan = 0, ilk = null, sigmayan = 0;
for (let i = 1; i <= N; i += 1) {
  const b = taban(i);
  let boyut = bosBelge, sigan = 0;
  for (let n = 0; n < pay[i - 1]; n += 1) {
    const ek = String(n).length + birKayit - 1;
    if (boyut + ek > SINIR) break;
    boyut += ek;
    b.odunc.push(kayit(n));
    sigan += 1;
  }
  if (sigan < pay[i - 1]) {
    dayanan += 1;
    sigmayan += pay[i - 1] - sigan;
    ilk ??= { sira: i, kayit: sigan, boyut: bayt(b), istenen: pay[i - 1] };
  }
  depoA.yaz("kitap", b);
}
console.log(`A sinirsiz gomme: sinira dayanan kitap ${dayanan}, sigmayan odunc kaydi ${sigmayan}`);
console.log(`  ilk dayanan ${ilk.sira}. kitap: ${ilk.kayit} kayit ${ilk.boyut} bayt, istenen ${ilk.istenen}`);
console.log(`  kitap derlemi ${derlemBayt(depoA.d("kitap"))} bayt`);

// B karari: son 20 kayit gomulur, gerisi odunc derleminde durur.
const depoB = new Depo(SINIR);
for (let i = 1; i <= N; i += 1) {
  const b = taban(i);
  for (let n = Math.max(0, pay[i - 1] - SON); n < pay[i - 1]; n += 1) b.odunc.push(kayit(n));
  depoB.yaz("kitap", b);
}
const enBuyuk = Math.max(...[...depoB.d("kitap").values()].map(bayt));
console.log(`B son ${SON} kayit gomulu: en buyuk belge ${enBuyuk} bayt, sinira uzaklik ${SINIR - enBuyuk}`);
console.log(`  kitap derlemi ${derlemBayt(depoB.d("kitap"))} bayt, ayri derleme kalan kayit ` +
  `${pay.reduce((t, p) => t + Math.max(0, p - SON), 0)}`);

bos kitap belgesi 108 bayt, bir odunc kaydi 53 bayt
sinir 16384 bayt, kaba hesap: 307 kayit
A sinirsiz gomme: sinira dayanan kitap 451, sigmayan odunc kaydi 763673
  ilk dayanan 1. kitap: 297 kayit 16333 bayt, istenen 134178
  kitap derlemi 36942774 bayt
B son 20 kayit gomulu: en buyuk belge 1184 bayt, sinira uzaklik 15200
  kitap derlemi 17256316 bayt, ayri derleme kalan kayit 1125534

Kaba hesap 307 kayıt der, gerçekte 297 kayıt sığar. Aradaki 10 kayıtlık fark, dizinin kendi alan adlarından gelir: 100. ögeden sonra sıra adı üç haneye çıkar ve her öge bir bayt daha yer kaplar. Bu, önceki dersin bulgusunun bir sonucudur — dizide bile alan adı saklanır.

Asıl sayı ikinci satırdadır. 20.000 kitabın 451’i üç yıl içinde sınıra dayanır ve 763.673 ödünç kaydı belgeye yazılamaz. En çok ödünç alınan kitap 134.178 kayıt ister, 297 tanesini alabilir. Sınır bir başarım sorunu değil, bir veri kaybı sorunudur: gömme kararı burada sessizce geri döndürülemez bir sınıra çarpar. İkinci karar sınırı ortadan kaldırır — son 20 kayıt gömülür, gerisi ayrı derlemde durur. En büyük kitap belgesi 1.184 bayta iner, sınıra 15.200 bayt uzaklık kalır, ayrı derleme 1.125.534 kayıt taşınır. Kitap sayfası hâlâ tek gidişte son 20 ödüncü gösterir; tam geçmiş isteyen ekran ikinci bir gidiş öder.

Kararın kuralı bu üç ölçümden çıkar: birlikte okunan ve birlikte değişen veri gömülür, ayrı sorgulanan veya sınırsız büyüyen veri referansla tutulur. “Daha esnek” ya da “daha doğal” cümleleri bu kararı taşımaz; taşıyan şey gidiş sayısı, okunan bayt, yeniden yazılan bayt ve sınıra uzaklıktır.

Özet

• Gömme ilgili veriyi belgenin içine koyar, referans ayrı derlemde tutup anahtarını taşır; ikisi aynı katalogu farklı erişim maliyetiyle saklar.
• Kitap sayfası gömülü şemada 1 gidiş ve 454 bayt, referanslı şemada 2 gidiş ve 502 bayt tutar; kazanç bayt değil gidiştir.
• Şube sorgusu gömülü şemada 20.000 belge ve 6.149.233 bayt okur, referanslı şemada 10.066 belge ve 781.096 bayt; oran 7,9 kattır.
• Bir kopyanın durum değişikliği gömülü şemada kitabın tamamını yeniden yazar: 5.000 değişiklik 1.541.395 bayt, referanslı şemada 381.255 bayt (oran 4,04).
• Sınırsız büyüyen dizi belge boyutu sınırına dayanır: 20.000 kitabın 451’i sınırı aşar ve 763.673 ödünç kaydı yazılamaz; son 20 kaydı gömen karar en büyük belgeyi 1.184 bayta indirir.

Sonraki Adım

Şemanın kurulduğu iki karar sayıldı; sıra o şema üzerinde soru sormaya geldi. Şube sorgusu bu derste elle yazılmış bir koşul işleviyle çalıştırıldı, oysa depo koşulu kendisi değerlendirir ve bunu bir işleç kümesiyle yapar: karşılaştırma, mantıksal bağlaç ve dizi işleçleri. Dizi işleçleri bu derste ortaya çıkan bir belirsizliği taşır — gömülü kopya dizisine iki koşul birden sorulduğunda koşulların aynı ögede mi yoksa belgenin herhangi iki ögesinde mi karşılanması gerektiği, aynı sorgunun iki farklı yanıtı demektir. Sonraki ders işleçleri kendi değerlendiricisinde kurar ve bu farkı sayar.