Karma Yapılar

Buraya kadar depoya konan her şey tek parçaydı: oturum kaydı bir bütün, sayaç bir sayı, liste girişi bir dizgi. Kütüphanenin asıl kaydı böyle değildir. Bir kitabın adı, yazarı, raf kodu, durumu, ödünç sayısı, eklenme tarihi ve numarası vardır. Bu alanların değişme sıklıkları da birbirinin aynı değil: durum gün içinde defalarca değişir, ad hiç değişmez.

Bütünsel değerde depo alan diye bir kavram tanımaz; tek bir alanı güncellemek bütün kaydı okuyup geri yazmak demektir — ve önceki derste ölçülen kayıp güncelleme sorunu tam buradan doğar. Karma yapı bunun alternatifidir: depo kaydın alanlarını bilir, adıyla okur, adıyla yazar. Bu ders o bilginin fiyatını sorar.

Aynı Kayıt, Üç Biçim

Üç biçim karşılaştırılır. Bütünsel değer kaydı tek bir seri hale getirilmiş dizgide tutar. Yoğun karma alanları ardışık olarak tek bir blokta tutar ama depo alan sınırlarını bilir; tek alan isteği bloğun taranmasıyla karşılanır. Karma yapı her alanı ayrı bir giriş olarak tutar ve alan adıyla tek adımda erişir.

BY1: katalog 200.000 kitap taşır, her kayıt yedi alandır ve alan değerleri belirlenimli işlevlerden gelir. BY2: yapı başına üstveri 56, alan başına üstveri 40 bayttır (karma kovası göstergesi, alan adı ve değeri için göstergeler, uzunluk alanları). BY3: okunan ve yazılan deponun o işlem için dokunduğu bayttır, gidiş istemcinin çağrı sayısıdır, adım çözülen ya da karşılaştırılan alan sayısıdır. BY4: gün içinde 119.993 ödünç–iade olayı iki alanı günceller (durum ve ödünç sayacı), 400.000 durum sorgusu tek alan okur, 60.000 kitap sayfası bütün kaydı okur.

// bellek/karma.mjs — ayni kitap kaydi uc bicimde. okunan/yazilan = deponun dokundugu bayt,
// gidis = istemcinin cagri sayisi, adim = alan arama karsilastirmasi. Is yuku belirlenimlidir.
const USTVERI = 56, ALAN_USTVERI = 40, KITAP = 200_000;   // BY2
const bl = (x) => Buffer.byteLength(String(x));
const anahtar = (i) => `kitap:${100_000 + i}`;
const kayit = (i) => ({
  ad: `Kitap ${100_000 + i} uzerine notlar`, yazar: `Yazar ${i % 997}`,
  raf: `K-${1 + (i % 20)}-${String(i % 400).padStart(3, "0")}`,
  durum: i % 3 === 0 ? "oduncte" : "raftaki", odunc: String(1 + (i * 7919) % 4096),
  eklenme: `20${10 + (i % 15)}-${String(1 + (i % 12)).padStart(2, "0")}-14`,
  isbn: String(9_780_000_000_000 + i),
});

class ButunselDepo {                            // deger tek parcadir: depo alan tanimaz
  #t = new Map(); okunan = 0; yazilan = 0; gidis = 0; adim = 0;
  koy(a, o) { this.#t.set(a, JSON.stringify(o)); }
  tamOku(a) { this.gidis += 1; const s = this.#t.get(a); this.okunan += bl(s);
    const o = JSON.parse(s); this.adim += Object.keys(o).length; return o; }   // her alan cozulur
  alanOku(a, alan) { return this.tamOku(a)[alan]; }        // butun deger okunur, biri kullanilir
  alanYaz(a, alan, v) { const o = this.tamOku(a); o[alan] = v;                 // oku-degistir-yaz
    const s = JSON.stringify(o); this.gidis += 1; this.yazilan += bl(a) + bl(s); this.#t.set(a, s); }
  bayt() { let b = 0; for (const [a, s] of this.#t) b += bl(a) + bl(s) + USTVERI; return b; }
}

class YogunKarmaDepo {                          // alanlar tek blobda ardisik; depo alan tanir
  #t = new Map(); okunan = 0; yazilan = 0; gidis = 0; adim = 0;
  koy(a, o) { this.#t.set(a, Object.entries(o).map(([k, v]) => `${k}=${v}`).join(";")); }
  #ara(s, alan) { for (const p of s.split(";")) { this.adim += 1; if (p.startsWith(`${alan}=`)) return p; } return null; }
  tamOku(a) { this.gidis += 1; const s = this.#t.get(a); this.okunan += bl(s);
    return Object.fromEntries(s.split(";").map((p) => p.split("="))); }
  alanOku(a, alan) { this.gidis += 1; const s = this.#t.get(a); this.okunan += bl(s);
    const p = this.#ara(s, alan); return p === null ? undefined : p.slice(alan.length + 1); }
  alanYaz(a, alan, v) { this.gidis += 1; const s = this.#t.get(a); this.okunan += bl(s);
    const y = s.split(";").map((p) => { this.adim += 1; return p.startsWith(`${alan}=`) ? `${alan}=${v}` : p; }).join(";");
    this.yazilan += bl(a) + bl(y); this.#t.set(a, y); }                        // blob yeniden yazilir
  bayt() { let b = 0; for (const [a, s] of this.#t) b += bl(a) + bl(s) + USTVERI; return b; }
}

class KarmaDepo {                               // her alan ayri giristir: adiyla erisilir
  #t = new Map(); okunan = 0; yazilan = 0; gidis = 0; adim = 0;
  koy(a, o) { this.#t.set(a, new Map(Object.entries(o).map(([k, v]) => [k, String(v)]))); }
  tamOku(a) { this.gidis += 1; const m = this.#t.get(a);
    for (const [k, v] of m) { this.adim += 1; this.okunan += bl(k) + bl(v); } return Object.fromEntries(m); }
  alanOku(a, alan) { this.gidis += 1; this.adim += 1;
    const v = this.#t.get(a).get(alan); this.okunan += bl(v); return v; }
  alanYaz(a, alan, v) { this.gidis += 1; this.adim += 1; this.yazilan += bl(a) + bl(alan) + bl(v);
    this.#t.get(a).set(alan, String(v)); }
  bayt() { let b = 0;
    for (const [a, m] of this.#t) { b += bl(a) + USTVERI;
      for (const [k, v] of m) b += bl(k) + bl(v) + ALAN_USTVERI; }
    return b; }
}

const bir = kayit(427);
console.log(`ornek ${anahtar(427)}: ${Object.keys(bir).length} alan, JSON ${bl(JSON.stringify(bir))} bayt, ` +
  `alan adlari ${Object.keys(bir).reduce((t, k) => t + bl(k), 0)} bayt, ` +
  `alan degerleri ${Object.values(bir).reduce((t, v) => t + bl(v), 0)} bayt`);

const depo = [["butunsel deger", new ButunselDepo()], ["yogun karma", new YogunKarmaDepo()],
  ["karma yapi", new KarmaDepo()]];
for (const [, d] of depo) for (let i = 1; i <= KITAP; i += 1) d.koy(anahtar(i), kayit(i));

// gunluk yuk: 119.993 odunc/iade iki alani gunceller, 400.000 durum sorgusu, 60.000 tam okuma
const ODUNC = 119_993, DURUM = 400_000, SAYFA = 60_000;
for (const [, d] of depo) {
  for (let j = 0; j < ODUNC; j += 1) { const i = 1 + (j * 4241) % KITAP;
    d.alanYaz(anahtar(i), "durum", j % 2 === 0 ? "oduncte" : "raftaki");
    d.alanYaz(anahtar(i), "odunc", String(1 + (i * 7919) % 4096)); }
  for (let j = 0; j < DURUM; j += 1) d.alanOku(anahtar(1 + (j * 7919) % KITAP), "durum");
  for (let j = 0; j < SAYFA; j += 1) d.tamOku(anahtar(1 + (j * 4241) % KITAP));
}

console.log(`\n${KITAP} kitap; gunluk yuk ${2 * ODUNC} alan yazma, ${DURUM} alan okuma, ${SAYFA} tam okuma`);
console.log(`${"bicim".padEnd(16)}${"tutulan bayt".padStart(14)}${"kayit basina".padStart(13)}` +
  `${"yazilan".padStart(10)}${"okunan".padStart(11)}${"gidis".padStart(9)}${"adim".padStart(9)}`);
for (const [ad, d] of depo)
  console.log(ad.padEnd(16) + String(d.bayt()).padStart(14) + (d.bayt() / KITAP).toFixed(1).padStart(13) +
    String(d.yazilan).padStart(10) + String(d.okunan).padStart(11) + String(d.gidis).padStart(9) +
    String(d.adim).padStart(9));

ornek kitap:100427: 7 alan, JSON 151 bayt, alan adlari 31 bayt, alan degerleri 77 bayt

200000 kitap; gunluk yuk 239986 alan yazma, 400000 alan okuma, 60000 tam okuma
bicim             tutulan bayt kayit basina   yazilan     okunan    gidis     adim
butunsel deger        43833793        219.2  39158258  105816147   939972  4899902
yogun karma           37833793        189.2  31958678   84816567   699986  3279902
karma yapi            91233793        456.2   5367227    9290135   699986  1059986

Karma yapının fiyatı ilk sütunda duruyor: aynı 200.000 kayıt bütünsel değerde 43,8 MB tutarken karma yapıda 91,2 MB tutuyor, kayıt başına 219,2 bayta karşılık 456,2 bayt. Fark tek bir kalemdir: yedi alanın her biri kendi girişidir ve her giriş 40 baytlık üstveri ile alan adının kopyasını taşır. Kayıt başına 237 baytlık artışın 280 baytı alan üstverisidir — yani kaydın kendisinden fazla yer, alanların ayrı ayrı tanınmasına gidiyor.

Karşılığında alınan şey öteki dört sütundadır. Tek alan güncellemesi bütünsel değerde bütün kaydı yazdırır; gün boyunca 39,2 MB yazılır. Karma yapıda yalnız anahtar, alan adı ve yeni değer yazılır: 5,4 MB, yedi kat az. Okuma tarafındaki fark daha büyüktür. 400.000 durum sorgusunun her biri bütünsel değerde 151 baytlık kaydın tamamını okutur; toplam 105,8 MB’a karşı karma yapıda 9,3 MB — on bir kat. Gidiş sayısı da düşer: bütünsel değerde alan güncellemesi oku-değiştir-yaz olduğu için iki çağrı ister, 939.972’ye karşı 699.986. Bu 239.986 fazladan gidiş yalnız bir trafik kalemi değildir; önceki dersin kaybolan güncellemesi tam o aralıkta doğar. Karma yapıda alan güncellemesi tek çağrıdır ve bölünmez.

Ortadaki satır dersin sürprizini taşıyor. Yoğun karma alanları tek blokta tutmasına rağmen hem bütünsel değerden az yer kaplıyor (189,2 bayt, çünkü ayraç ve tırnak yükü yok) hem de alan kavramını koruyor: gidiş 699.986’ya iniyor, güncelleme bölünmez oluyor. Yedi alanlık bir kayıtta bütünsel değerin yoğun karmaya karşı kazandığı tek bir sütun yok. Yoğun karmanın ödediği bedel adım sütunudur: tek alan bulmak için blok taranır, 3.279.902 adım. Karma yapı aynı işi 1.059.986 adımda bitirir.

Eşik Nerede

Yedi alanda yoğun karma iyi bir seçimdir; tarama dört adımdır. Alan sayısı büyüdükçe bu değişir. BY5: karşılaştırma için alan adı 8, alan değeri 7 bayttır ve kayıt türleri katalogda dört farklı boydadır.

// bellek/esik.mjs — alan sayisi buyudukce yogun gosterim ile karma gosterimin ayrismasi
// ve esik politikasinin katalog genelindeki bedeli. Butun sayilar yapisal.
const USTVERI = 56, ALAN_USTVERI = 40;
const alanAdi = (j) => `alan_${String(j).padStart(3, "0")}`;
const alanDeger = (j) => String(1_000_000 + j * 7919);
const bl = (x) => Buffer.byteLength(String(x));
const ANAHTAR = bl("kitap:100427");

const yogunBayt = (f) => ANAHTAR + USTVERI +
  bl(Array.from({ length: f }, (_, j) => `${alanAdi(j)}=${alanDeger(j)}`).join(";"));
const karmaBayt = (f) => ANAHTAR + USTVERI +
  Array.from({ length: f }, (_, j) => bl(alanAdi(j)) + bl(alanDeger(j)) + ALAN_USTVERI).reduce((t, x) => t + x, 0);

console.log(`alan adi ${bl(alanAdi(0))} bayt, alan degeri ${bl(alanDeger(0))} bayt, ` +
  `alan ustverisi ${ALAN_USTVERI} bayt, anahtar ${ANAHTAR} bayt`);
console.log(`\n${"alan".padStart(6)}${"yogun bayt".padStart(12)}${"karma bayt".padStart(12)}${"oran".padStart(7)}` +
  `${"yogun erisim adimi".padStart(20)}${"yogun alan yazma".padStart(18)}${"karma alan yazma".padStart(18)}`);
for (const f of [4, 7, 16, 64, 256]) {
  const y = yogunBayt(f), k = karmaBayt(f);
  console.log(String(f).padStart(6) + String(y).padStart(12) + String(k).padStart(12) +
    (k / y).toFixed(2).padStart(7) + `${((f + 1) / 2).toFixed(1)} / ${f}`.padStart(20) +
    String(y - USTVERI).padStart(18) +
    String(ANAHTAR + bl(alanAdi(0)) + bl(alanDeger(0))).padStart(18));
}

// katalog: dort kayit turu, uc politika
const tur = [["kitap kaydi", 200_000, 7], ["uye profili", 20_000, 12],
  ["sube gunluk sayac", 5, 24], ["populer kitap etiket sayaci", 2_000, 256]];
console.log(`\n${"kayit turu".padEnd(29)}${"adet".padStart(8)}${"alan".padStart(6)}` +
  `${"hepsi yogun".padStart(13)}${"hepsi karma".padStart(13)}${"esik 64".padStart(13)}`);
let ty = 0, tk = 0, te = 0;
for (const [ad, n, f] of tur) {
  const y = n * yogunBayt(f), k = n * karmaBayt(f), e = f <= 64 ? y : k;
  ty += y; tk += k; te += e;
  console.log(ad.padEnd(29) + String(n).padStart(8) + String(f).padStart(6) +
    String(y).padStart(13) + String(k).padStart(13) + String(e).padStart(13));
}
console.log("toplam".padEnd(29) + "".padStart(8) + "".padStart(6) +
  String(ty).padStart(13) + String(tk).padStart(13) + String(te).padStart(13));
console.log(`esik 64: hepsi karmanin %${(100 * te / tk).toFixed(1)}'i, hepsi yogunun ` +
  `%${(100 * te / ty).toFixed(1)}'i; en kotu alan erisimi ${64} adim`);

alan adi 8 bayt, alan degeri 7 bayt, alan ustverisi 40 bayt, anahtar 12 bayt

  alan  yogun bayt  karma bayt   oran  yogun erisim adimi  yogun alan yazma  karma alan yazma
     4         135         288   2.13             2.5 / 4                79                27
     7         186         453   2.44             4.0 / 7               130                27
    16         339         948   2.80            8.5 / 16               283                27
    64        1155        3588   3.11           32.5 / 64              1099                27
   256        4419       14148   3.20         128.5 / 256              4363                27

kayit turu                       adet  alan  hepsi yogun  hepsi karma      esik 64
kitap kaydi                    200000     7     37200000     90600000     37200000
uye profili                     20000    12      5420000     14560000      5420000
sube gunluk sayac                   5    24         2375         6940         2375
populer kitap etiket sayaci      2000   256      8838000     28296000     28296000
toplam                                          51460375    133462940     70918375
esik 64: hepsi karmanin %53.1'i, hepsi yogunun %137.8'i; en kotu alan erisimi 64 adim

Üst tablo iki eğriyi yan yana koyuyor. Bellek oranı alan sayısıyla birlikte 2,13’ten 3,20’ye çıkıyor — yoğun gösterimin kazancı büyük kayıtlarda daha da artıyor. Ama iki sütun ters yönde büyüyor. Yoğun gösterimde bir alan bulmak ortalama (f+1)/2 adımdır ve 256 alanlı kayıtta 128,5 adıma, en kötü durumda 256 adıma çıkar. Daha da sert olan tek alan yazmadır: yoğun gösterimde bütün blok yeniden yazılır, 256 alanda 4.363 bayt. Karma yapıda aynı yazma alan sayısından bağımsız olarak 27 bayttır. Yani liste dersindeki yazma çarpanı burada geri geliyor ve alan sayısıyla doğru orantılı büyüyor.

Alt tablo kararı katalog ölçeğinde veriyor. Her şeyi yoğun tutmak 51,5 MB, her şeyi karma tutmak 133,5 MB ister. Alan sayısı 64’ün altındaysa yoğun, üstündeyse karma tutan eşik politikası 70,9 MB’da kalır: her şeyi karma tutmanın %53,1’i. Aradaki 62,5 MB’lık tasarrufun bedeli 200.000 kitap kaydında en fazla 7 adımlık taramadır. Aynı politika, 2.000 etiket sayacını karma yapıda tutarak 256 adımlık taramayı ve 4.363 baytlık yazmayı önler. Eşik politikası, her şeyi yoğun tutmaya göre %37,8 fazla bellek harcar ve karşılığında en kötü alan erişimini 256 adımdan 64 adıma bağlar. Karar bir gösterimi öteki üzerine seçmek değil, sınırın nereden geçtiğini seçmektir.

Özet

• Bütünsel değerde depo alan tanımaz: tek alan güncellemesi kaydın tamamını okutup yazdırır ve iki gidiş ister; kaybolan güncelleme tam bu aralıkta doğar.
• 200.000 kayıt bütünsel değerde 43,8 MB, karma yapıda 91,2 MB tutar. Kayıt başına 237 baytlık artışın büyük bölümü alan başına 40 baytlık üstveridir.
• Karma yapının satın aldığı şey günlük yazma trafiğinde 39,2 MB’dan 5,4 MB’a, okuma trafiğinde 105,8 MB’dan 9,3 MB’a, gidişte 939.972’den 699.986’ya iniştir.
• Yoğun karma yedi alanlık kayıtta bütünsel değere göre hiçbir sütunda kaybetmez: 189,2 bayt, aynı gidiş sayısı ve bölünmez alan güncellemesi. Ödediği tek bedel tarama adımıdır (3.279.902’ye karşı 1.059.986).
• Alan sayısı büyüdükçe yoğun gösterimin bellek kazancı artar (oran 2,13’ten 3,20’ye) ama erişim ortalama (f+1)/2 adıma, tek alan yazması 256 alanda 4.363 bayta çıkar; karma yapıda aynı yazma 27 bayttır.
• Eşik politikası (64 alana kadar yoğun) katalogda 70,9 MB tutar: her şeyi karma tutmanın %53,1’i, her şeyi yoğun tutmanın %137,8’i. Satın alınan şey en kötü erişimin 64 adıma bağlanmasıdır.

Sonraki Adım

Karma yapı bir kaydın alanlarını ayırdı ama hepsi hâlâ tek bir kayda aitti. Kütüphanenin bazı soruları tek kayda ait değildir: “bu kitap şu an ödünçte olanlar arasında mı”, “bu üye ceza listesinde var mı”, “en çok ödünç alınan yirmi kitap hangileri”. Birincisi bir üyelik sorusudur ve yanıtı evet ya da hayırdır; sonuncusu bir sıra sorusudur ve yanıtı sıralı bir listedir. Sonraki ders bu iki yapıyı ele alıyor ve üçünü ölçüyor: üyelik denetiminin adımı, sıralı kümede sıra sorgusunun adımı ve ikisinin giriş başına bayt maliyeti.