Geniş Sütun Depoları

Önceki iki ailede kaydın bütün alanları diskte yan yana duruyordu. Anahtar–değer deposunda değer tek bir bayt dizisiydi; belge veritabanı ağacı tanıdı ama belgeyi yine tek yerde tuttu. Bunun bir sonucu vardı: yalnız iki alanı isteyen bir sorgu, o kayıtların tamamının bulunduğu yeri okur. Geniş sütun deposu (wide column store) yerleşimi bu noktadan böler.

Model şudur: bir satır anahtarıyla adlanır, satırın sütunları önceden bildirilmiş sütun ailelerine (column family) ayrılır ve aynı ailenin sütunları diskte birlikte durur. Bu ders üç şeyi ölçer: yerleşimin okunan bayta etkisi, tek anahtarın altında binlerce sütunun toplanması, ve yazma yolunun yerinde değiştirme yerine eklemeli olması.

Yerleşim Neyi Değiştirir

Okuma birimi baytın kendisi değildir; depo diski sayfa sayfa okur. Bu yüzden yerleşim sorusunun karşılığı “kaç alan okundu” değil, kaç sayfaya dokunuldudur. NS1: katalog 20.000 kayıt taşır ve dört aileye ayrılır — kimlik, basim, dolasim, metin; özet alanı kaydın en büyük parçasıdır. NS2: sayfa 4096 bayttır ve okuma bir sayfanın herhangi bir baytına dokunduğunda o sayfanın tamamını okur.

// sutun/yerlesim.mjs — ayni kayitlarin satir yerlesiminde ve sutun ailesi yerlesiminde
// diske serilmesi, sonra iki sorgunun dokundugu 4096 baytlik sayfalarin sayilmasi.
// Okuma birimi sayfadir; sutun ailesi yerlesiminde erisim birimi ailedir, sutun degil.
const KAYIT = 20_000, SAYFA = 4096;
const AILE = { kimlik: ["kitap_id", "baslik", "yazar"], basim: ["yil", "dil", "isbn"],
               dolasim: ["odunc_sayisi", "sube_id", "durum"], metin: ["ozet"] };
const kitap = (i) => ({ kitap_id: i, baslik: `Kitap ${i} ${"a".repeat(30)}`,
  yazar: `Yazar ${i % 500} ${"b".repeat(12)}`, yil: 1960 + (i % 65), dil: i % 4 === 0 ? "en" : "tr",
  isbn: `978-${String(1000000000 + i)}`, odunc_sayisi: i % 97, sube_id: 1 + (i % 9),
  durum: i % 3 === 0 ? "rafta" : "oduncte", ozet: `${"c".repeat(280)} ${i}` });

function seril(satirYerlesimi) {           // her alan icin [baslangic, bitis] bayt araligi
  const yer = new Map(); let ofset = 0;
  const koy = (i, alan) => { const n = Buffer.byteLength(String(kitap(i)[alan]));
    yer.set(`${i}|${alan}`, [ofset, ofset + n]); ofset += n; };
  if (satirYerlesimi) { for (let i = 1; i <= KAYIT; i += 1)
      for (const a of Object.values(AILE)) for (const alan of a) koy(i, alan); }
  else { for (const a of Object.values(AILE))
      for (let i = 1; i <= KAYIT; i += 1) for (const alan of a) koy(i, alan); }
  return { yer, boyut: ofset };
}
const sayfaSayisi = (araliklar) => { const s = new Set();
  for (const [b, u] of araliklar)
    for (let p = b / SAYFA | 0; p <= (u - 1) / SAYFA | 0; p += 1) s.add(p);
  return s.size; };

const satir = seril(true), aile = seril(false);
console.log(`${KAYIT} kayit, toplam ${satir.boyut} bayt, ${Math.ceil(satir.boyut / SAYFA)} sayfa`);
for (const [ad, alanlar] of Object.entries(AILE)) {
  let n = 0; for (let i = 1; i <= KAYIT; i += 1) for (const alan of alanlar)
    n += aile.yer.get(`${i}|${alan}`)[1] - aile.yer.get(`${i}|${alan}`)[0];
  console.log(`  aile ${ad.padEnd(8)} ${String(n).padStart(9)} bayt`);
}

const H = 4244;
const S1 = [], A1 = [];                    // S1: butun kayitlarda dolasim ailesi
for (let i = 1; i <= KAYIT; i += 1) for (const alan of AILE.dolasim) {
  S1.push(satir.yer.get(`${i}|${alan}`)); A1.push(aile.yer.get(`${i}|${alan}`)); }
const S2 = [], A2 = [];                    // S2: tek kaydin butun alanlari
for (const a of Object.values(AILE)) for (const alan of a) {
  S2.push(satir.yer.get(`${H}|${alan}`)); A2.push(aile.yer.get(`${H}|${alan}`)); }

console.log(`\n${"sorgu".padEnd(38)}${"satir yerlesimi".padStart(17)}${"aile yerlesimi".padStart(16)}${"oran".padStart(7)}`);
for (const [ad, s, a] of [["butun kitaplarin dolasim ozeti", S1, A1], [`tek kitabin (${H}) butun alanlari`, S2, A2]]) {
  const ps = sayfaSayisi(s), pa = sayfaSayisi(a);
  console.log(ad.padEnd(38) + `${ps} sayfa`.padStart(17) + `${pa} sayfa`.padStart(16) +
    (ps / pa).toFixed(2).padStart(7));
}

20000 kayit, toplam 7646881 bayt, 1867 sayfa
  aile kimlik     1353388 bayt
  aile basim       400000 bayt
  aile dolasim     184599 bayt
  aile metin      5708894 bayt

sorgu                                   satir yerlesimi  aile yerlesimi   oran
butun kitaplarin dolasim ozeti               1867 sayfa        46 sayfa  40.59
tek kitabin (4244) butun alanlari               1 sayfa         4 sayfa   0.25

Sayılar ölçüm sınıfındadır: iki yerleşim de gerçekten serildi, sayfalar gerçekten sayıldı.

İki satır birbirinin tersini söylüyor ve modelin tamamı bu iki satırdadır. Bütün kayıtların dolaşım özetini almak satır yerleşiminde 1.867 sayfa, aile yerleşiminde 46 sayfa okuyor: kırk kat fark. Neden basit bir orandır — dolaşım ailesi verinin 184.599 baytıdır, geri kalan 7,4 MB’ın çoğu özet metnidir ve satır yerleşiminde her dolaşım alanı bir özet metninin yanında durduğu için o metin de sayfayla birlikte okunur.

İkinci satır bedeli gösteriyor. Tek bir kitabın bütün alanlarını okumak satır yerleşiminde tek sayfa, aile yerleşiminde dört sayfadır — her aile ayrı bir yerdedir, dolayısıyla kaydı toplamak için dört ayrı yere gitmek gerekir. Oran 0,25: aile yerleşimi bu sorguda dört kat kötüdür. Yerleşim kararı bir sorgu sınıfını ucuzlatırken ötekini pahalılaştırır; ailenin sınırı, birlikte okunan alanların sınırı olmalıdır.

Geniş Satır

Modelin ikinci ayırt edici yanı satırın genişliğinin sınırsız olmasıdır. Bir satır anahtarının altında binlerce, on binlerce sütun toplanabilir ve sütun adı bir şema alanı değil, bir veridir: kütüphane örneğinde her ödünç, kitap satırının altında bir sütundur ve sütun adı ödüncün zaman damgasıdır. Sütunlar satır içinde ada göre sıralı durduğu için bir zaman aralığı tek istekte dilimlenir. Bunun adı geniş satırdır (wide row).

// sutun/genis-satir.mjs — odunc gecmisinin genis satir olarak tutulmasi. Sutunlar satir
// icinde sirali durur, aralik dilimi tek istektir; ayni soru baska bir bolum anahtariyla
// sorulunca taramaya duser. Sayilar kosumdan bagimsizdir.
const KITAP = 5_000, POPULER = 4_000;      // ilk bes kitap POPULER kez odunc verilir
class GenisSutunDeposu {
  #satir = new Map();
  gidis = 0; sutun = 0; girdi = 0;
  yaz(anahtar, ad, deger) { if (!this.#satir.has(anahtar)) this.#satir.set(anahtar, new Map());
    this.#satir.get(anahtar).set(ad, deger); this.girdi += 1; }
  dilim(anahtar, alt, ust) {               // satir icinde sirali aralik: tek istek
    this.gidis += 1; const s = this.#satir.get(anahtar) ?? new Map(); const c = [];
    for (const [ad, d] of [...s].sort(([x], [y]) => (x < y ? -1 : 1)))
      if (ad >= alt && ad < ust) { this.sutun += 1; c.push(d); }
    return c; }
  tara(sart) { this.gidis += 1; const c = [];
    for (const [a, s] of this.#satir) for (const [ad, d] of s) { this.sutun += 1;
      if (sart(a, ad, d)) c.push(d); }
    return c; }
  enGenis() { let e = 0, k = null;
    for (const [a, s] of this.#satir) if (s.size > e) { e = s.size; k = a; }
    return [k, e]; }
  sifirla() { this.gidis = 0; this.sutun = 0; }
}

const kitapDepo = new GenisSutunDeposu(), uyeDepo = new GenisSutunDeposu();
for (let i = 1; i <= KITAP; i += 1)
  for (let j = 0, n = i <= 5 ? POPULER : 1 + (i % 97); j < n; j += 1) {
    const ay = 1 + ((i + j) % 12), gun = 1 + ((i * 3 + j * 7) % 28), uye = 1 + ((i * 13 + j) % 20_000);
    const t = `2024-${String(ay).padStart(2, "0")}-${String(gun).padStart(2, "0")}`;
    kitapDepo.yaz(`kitap:${i}`, `odunc|${t}|${j}`, uye);        // bolum anahtari kitap
    uyeDepo.yaz(`uye:${uye}`, `odunc|${t}|${i}|${j}`, i);       // bolum anahtari uye
  }
const [ea, es] = kitapDepo.enGenis();
console.log(`${KITAP} kitap, ${kitapDepo.girdi} odunc girdisi; ortalama satir ` +
  `${(kitapDepo.girdi / KITAP).toFixed(1)} sutun, en genis satir ${ea} ${es} sutun`);

const H = 3, ALT = "odunc|2024-03", UST = "odunc|2024-04";
const yaz = (ad, depo, sonuc) => console.log(ad.padEnd(36) + String(depo.gidis).padStart(7) +
  String(depo.sutun).padStart(14) + String(sonuc).padStart(7));
console.log(`\n${"yol".padEnd(36)}${"gidis".padStart(7)}${"okunan sutun".padStart(14)}${"sonuc".padStart(7)}`);
kitapDepo.sifirla(); let r = kitapDepo.dilim(`kitap:${H}`, ALT, UST);
yaz("kitap bolumu, aralik dilimi", kitapDepo, r.length);
kitapDepo.sifirla(); r = kitapDepo.dilim(`kitap:${H}`, "odunc|", "odunc}");
yaz("kitap bolumu, butun satir", kitapDepo, r.length);
uyeDepo.sifirla(); r = uyeDepo.tara((a, ad, d) => ad.startsWith(ALT) && d === H);
yaz("uye bolumu, ayni soru", uyeDepo, r.length);

console.log(`\niki erisim oruntusu birden: ${kitapDepo.girdi} + ${uyeDepo.girdi} = ` +
  `${kitapDepo.girdi + uyeDepo.girdi} girdi yazilir, yazma carpani ` +
  `${((kitapDepo.girdi + uyeDepo.girdi) / kitapDepo.girdi).toFixed(1)}`);

5000 kitap, 263867 odunc girdisi; ortalama satir 52.8 sutun, en genis satir kitap:1 4000 sutun

yol                                   gidis  okunan sutun  sonuc
kitap bolumu, aralik dilimi               1           333    333
kitap bolumu, butun satir                 1          4000   4000
uye bolumu, ayni soru                     1        263867    333

iki erisim oruntusu birden: 263867 + 263867 = 527734 girdi yazilir, yazma carpani 2.0

Bir ayın ödünçleri, dört bin sütunluk satırın içinden 333 sütun okunarak alınıyor: sütunlar sıralı olduğu için depo aralığın başına inip sonuna kadar yürüyor, satırın geri kalanına hiç dokunmuyor. Aynı satırın tamamı istendiğinde okunan sütun 4.000’e çıkıyor — geniş satır bir avantaj değil, doğru dilimlendiğinde avantajdır.

Üçüncü satır bölüm anahtarının ne kadar belirleyici olduğunu gösteriyor. Aynı veri üye anahtarıyla bölümlendiğinde bir kitabın ödünçleri hiçbir satırın içinde bir arada değildir ve soru 263.867 sütunluk bir taramaya düşer. Karşılığı bilinen bir karardır: aynı veri ikinci bir bölüm anahtarıyla ikinci kez yazılır — Veri Katmanı Ölçekleme kursunda bu karar sorgu sayısı üzerinden ölçülmüştü, buradaki karşılığı yazma tarafındadır ve tam olarak iki katıdır.

Geniş satırın kendi sınırı da bu tabloda duruyor. Satır bölümlemenin birimi olduğu için tek bir satır sınırsız büyüyemez: en geniş satır 4.000 sütun taşırken ortalama satır 52,8 sütundur. Sınırsız büyüyen bir satır, Veri Katmanı Ölçekleme kursunda adı konan sıcak noktanın ta kendisidir; çözüm satır anahtarına bir zaman kutusu eklemektir.

Eklemeli Yazma Yolu

Bu ailenin yazma başarımı yerleşimden değil yazma yolundan gelir. Yazma yerinde değişiklik yapmaz: her yazma yeni bir girdidir ve sıraya eklenir. Bellekteki tablo dolduğunda değiştirilemez bir dosyaya çevrilir ve bir daha dokunulmaz. Silme de bir yazmadır — kaydın üstüne silme işareti (tombstone) konur. Okuma, dosyaları yeniden eskiye doğru tarar ve ilk bulduğu sürümü döndürür. Geçersiz sürümleri ve silme işaretlerini düşürmek ayrı bir işin — toparlamanın (compaction) — konusudur.

// sutun/eklemeli.mjs — eklemeli yazma yolu: her yazma yeni girdidir, silme bir silme
// isaretidir. Bellek tablosu dolunca degistirilemez bir dosyaya cevrilir. Okuma dosyalari
// yeniden eskiye tarar. Toparlama, gecersiz surumleri ve silme isaretlerini duser.
const DOSYA_BOYU = 25_000, SILME = Symbol("silme isareti");
class EklemeliDepo {
  #bellek = new Map(); #dosyalar = []; yazilanGirdi = 0;
  bakilanDosya = 0; okunanGirdi = 0;
  #cevir() { if (this.#bellek.size >= DOSYA_BOYU) { this.#dosyalar.push(this.#bellek); this.#bellek = new Map(); } }
  yaz(k, d) { this.#bellek.set(k, d); this.yazilanGirdi += 1; this.#cevir(); }
  sil(k) { this.yaz(k, SILME); }
  #yeniden() { return [this.#bellek, ...this.#dosyalar.slice().reverse()]; }   // yeniden eskiye
  oku(k) { const kaynak = this.#yeniden();
    for (const s of kaynak) { this.bakilanDosya += 1;
      if (s.has(k)) { this.okunanGirdi += 1; const d = s.get(k); return d === SILME ? undefined : d; } }
    return undefined; }
  tara() { const gorulen = new Set(), c = [];
    for (const s of this.#yeniden()) { this.bakilanDosya += 1;
      for (const [k, d] of s) { this.okunanGirdi += 1;
        if (gorulen.has(k)) continue; gorulen.add(k); if (d !== SILME) c.push(k); } }
    return c; }
  toparla() { const y = new Map();
    for (const s of [...this.#dosyalar, this.#bellek]) for (const [k, d] of s) y.set(k, d);
    for (const [k, d] of y) if (d === SILME) y.delete(k);
    this.#dosyalar = []; this.#bellek = new Map();
    for (const [k, d] of y) this.yaz(k, d);
    this.yazilanGirdi = y.size; return y.size; }
  durum() { return [this.#dosyalar.length + 1, this.yazilanGirdi]; }
  sifirla() { this.bakilanDosya = 0; this.okunanGirdi = 0; }
}

const depo = new EklemeliDepo(), N = 100_000;
for (let i = 1; i <= N; i += 1) depo.yaz(`odunc:${i}`, { kitap: i % 5000, iade: null });
for (let i = 1; i <= N; i += 1) if (i % 5 < 2) depo.yaz(`odunc:${i}`, { kitap: i % 5000, iade: "2024-06-01" });
for (let i = 1; i <= N; i += 1) if (i % 5 === 4) depo.sil(`odunc:${i}`);
const [dosya, girdi] = depo.durum();
const canli = N - Math.floor(N / 5);
console.log(`${N} kayit, ${girdi} yazilan girdi, ${canli} canli kayit; ` +
  `${dosya} dosya, yer carpani ${(girdi / canli).toFixed(2)}`);

const olcum = (ad, is) => { depo.sifirla(); const r = is();
  console.log(ad.padEnd(30) + String(depo.bakilanDosya).padStart(15) +
    String(depo.okunanGirdi).padStart(15) + String(r).padStart(9)); };
console.log(`\n${"okuma".padEnd(30)}${"bakilan dosya".padStart(15)}${"okunan girdi".padStart(15)}${"sonuc".padStart(9)}`);
olcum("guncellenen anahtar", () => (depo.oku("odunc:99996") ? "bulundu" : "yok"));
olcum("hic dokunulmamis anahtar", () => (depo.oku("odunc:2") ? "bulundu" : "yok"));
olcum("silinmis anahtar", () => (depo.oku("odunc:99994") ? "bulundu" : "yok"));
olcum("hic yazilmamis anahtar", () => (depo.oku("odunc:999999") ? "bulundu" : "yok"));
olcum("butun kayitlarin taranmasi", () => depo.tara().length);

const sonra = depo.toparla();
console.log(`\ntoparlama sonrasi: ${sonra} girdi, ${depo.durum()[0]} dosya, ` +
  `yer carpani ${(sonra / canli).toFixed(2)}`);
depo.sifirla(); const t = depo.tara();
console.log(`ayni tarama artik ${depo.okunanGirdi} girdi okuyor, sonuc ${t.length}`);

100000 kayit, 160000 yazilan girdi, 80000 canli kayit; 7 dosya, yer carpani 2.00

okuma                           bakilan dosya   okunan girdi    sonuc
guncellenen anahtar                         2              1  bulundu
hic dokunulmamis anahtar                    7              1  bulundu
silinmis anahtar                            1              1      yok
hic yazilmamis anahtar                      7              0      yok
butun kayitlarin taranmasi                  7         160000    80000

toparlama sonrasi: 80000 girdi, 4 dosya, yer carpani 1.00
ayni tarama artik 80000 girdi okuyor, sonuc 80000

Yazma tarafı ucuzdur ve bu tablo nedenini gösteriyor: hiçbir yazma bir okuma gerektirmedi, hiçbir dosya değiştirilmedi. Bedel okuma tarafında ve yerdedir. 80.000 canlı kayıt için diskte 160.000 girdi duruyor; yer çarpanı 2,00. Silinen 20.000 kayıt hâlâ oradadır — silme işareti yeri boşaltmaz, doldurur.

Okuma satırları maliyetin nereye dağıldığını gösteriyor. Yakın zamanda güncellenen bir anahtar 2 dosyada bulunuyor. Uzun süredir dokunulmamış bir anahtar 7 dosya gezdiriyor, çünkü en eski dosyadadır ve ondan yenisinde olmadığı ancak hepsine bakılarak anlaşılır. En pahalısı hiç yazılmamış anahtardır: 7 dosyanın hepsi taranır ve sonuç yoktur. Silinmiş anahtar ise tek dosyada biter — silme işareti en yeni girdidir ve okuma orada durur.

Tarama satırı silme işaretinin asıl bedelini taşıyor: 80.000 canlı kayıt için 160.000 girdi okunuyor. Toparlama bu iki sayıyı eşitliyor — girdi 80.000’e, yer çarpanı 1,00’e, dosya sayısı 7’den 4’e iniyor ve aynı tarama 80.000 girdi okuyor. Toparlamanın kendisi bütün veriyi bir kez daha yazar; yani eklemeli yazma yolu yazma işini ucuzlatmaz, arka plana erteler.

Özet

• Geniş sütun modelinde satır bir anahtarla adlanır, sütunlar sütun ailelerine ayrılır ve aynı ailenin sütunları diskte birlikte durur.
• Yerleşim iki yönlü çalışıyor: dolaşım özeti satır yerleşiminde 1.867, aile yerleşiminde 46 sayfa okuyor (40,6 kat); tek kaydın bütün alanları ise 1 sayfaya karşı 4 sayfadır.
• Geniş satırda sütun adı bir veridir ve sütunlar sıralıdır: 4.000 sütunluk satırdan bir ayın 333 ödüncü tek istekte dilimleniyor, aynı soru başka bir bölüm anahtarıyla 263.867 sütunluk taramaya düşüyor.
• İki erişim örüntüsünü birden karşılamak aynı verinin ikinci kez yazılmasıdır: 263.867 girdi 527.734’e çıkar, yazma çarpanı 2,0.
• Eklemeli yazma yolunda hiçbir yazma okuma gerektirmez; bedeli yer çarpanı 2,00 ve hiç yazılmamış bir anahtarın 7 dosya gezdirmesidir. Silme işareti yeri boşaltmaz.
• Toparlama girdi sayısını 160.000’den 80.000’e, yer çarpanını 1,00’e indirir; karşılığında bütün veriyi bir kez daha yazar.

Sonraki Adım

Üç ailenin üçü de aynı varsayımı paylaşıyordu: sorgunun konusu kaydın kendisidir. Anahtar biliniyorsa kayıt gelir, bir alan üzerinde koşul varsa dizin kurulur, bir aralık isteniyorsa yerleşim ona göre seçilir. Kütüphane verisinde ise bazı sorular kayıtlarla değil kayıtlar arasındaki bağlarla ilgilidir: aynı kitabı ödünç almış üyeler üzerinden iki üye arasındaki uzaklık, bir yazarın ortak çalıştığı yazarlardan yürüyerek ulaşılan yazarlar. İlişkisel modelde bu bağ bir birleştirme tablosudur ve her adım yeni bir birleştirme demektir. Sonraki ders bağın kendisini birinci sınıf nesne yapan aileyi ele alıyor ve şunu ölçüyor: aynı soruda komşuluk listesinin ve birleştirme tablosunun dokunduğu kayıt sayısı, ve bu sayının derinlik arttıkça nasıl büyüdüğü.