Toplama Boru Hattı

Önceki ders bir belgenin koşulu sağlayıp sağlamadığını söyleyen değerlendiriciyi kurdu. Kütüphanenin sorularının çoğu bununla bitmez: “hangi yazarın kaç kopyası onarımda”, “en çok ödünç alınan beş kitap”, “şube başına rafta duran kopya sayısı”. Bu soruların ortak yanı, yanıtın tek tek belgelerde değil belgelerin toplamında olmasıdır ve bir koşul ifadesi toplama yapamaz.

Belge modeli bu işi toplama boru hattıyla (aggregation pipeline) yapar: sıralı aşamalardan (stage) oluşan bir zincir. Her aşama bir kayıt akışı alır, dönüştürür ve bir sonrakine verir. Sözcük kabuk komutlarını birbirine bağlayan boru hattıyla aynıdır ve benzerlik gerçektir; ayrıldıkları yer akışın birimidir — kabukta akan şey bayttır, burada akan şey kayıttır ve aşamalar kayıt üzerinde çalışır. Bu dersin sorusu aşamaların ne yaptığı değil, sıralarının ne kadara mal olduğudur.

Akış Aşaması ve Engelleyici Aşama

Aşamalar iki sınıfa ayrılır. Akış aşaması kaydı alır, işler, bırakır: süzme, dizi açma ve yansıtma böyledir; bellekte bir anda tek bir kayıt tutulur. Engelleyici aşama ise sonucunu üretebilmek için akışın tamamını görmek zorundadır: sıralama akışı bütünüyle bellekte tutar, gruplama ise grup tablosunu tutar. Bir boru hattının bellek maliyeti, engelleyici aşamalarının o anda tuttuğu kayıt sayısıdır.

// boruhatti.mjs — asamali donusum. Her asama bir kayit akisi alir, donusturur, sonrakine
// verir. Asama basina giren/cikan kayit ve o asamanin bellekte tuttugu kayit sayilir.
export function calistir(kaynak, asamalar) {
  let akis = kaynak, doruk = 0, islenen = 0;
  const rapor = [];
  for (const asama of asamalar) {
    const ad = Object.keys(asama)[0], giren = akis.length;
    let bellek = 1;                                    // akis asamasi: tek kayit tutar
    if (ad === "suz") akis = akis.filter(asama.suz);
    else if (ad === "ac") {                            // diziyi ogelerine acar
      const alan = asama.ac;
      akis = akis.flatMap((b) => (b[alan] ?? []).map((o) => ({ ...b, [alan]: o })));
    } else if (ad === "grupla") {
      const m = new Map();
      for (const b of akis) {
        const k = asama.grupla.anahtar(b);
        m.set(k, asama.grupla.topla(m.get(k) ?? asama.grupla.bos(k), b));
      }
      akis = [...m.values()];
      bellek = m.size;                                 // engelleyici: grup tablosu bellekte
    } else if (ad === "sirala") {
      bellek = giren;                                  // engelleyici: akisin tamami bellekte
      akis = [...akis].sort(asama.sirala);
    } else if (ad === "sinirla") akis = akis.slice(0, asama.sinirla);
    else if (ad === "yansit") akis = akis.map(asama.yansit);
    islenen += giren;
    doruk = Math.max(doruk, bellek);
    rapor.push({ ad, giren, cikan: akis.length, bellek });
  }
  return { sonuc: akis, rapor, islenen, doruk };
}

export function yazdir(baslik, c) {
  console.log(`${baslik}: islenen kayit ${c.islenen}, doruk bellek ${c.doruk} kayit`);
  for (const r of c.rapor)
    console.log(`  ${r.ad.padEnd(8)} giren ${String(r.giren).padStart(6)}` +
      ` -> cikan ${String(r.cikan).padStart(6)}   bellek ${r.bellek}`);
}

Dizi açma aşaması belge modeline özgüdür ve boru hattının en pahalı aşamasıdır: bir kopya dizisi taşıyan kitap belgesi, dizinin öge sayısı kadar kayda dönüşür. 20.000 kitap belgesi, açıldığında 59.494 kayıt olur. Bu aşamadan sonra gelen her aşama üç kat fazla kayıt işler.

Aynı Soru, Üç Sıra

NS7 (varsayım): katalog 20.000 kitap belgesidir, kitap başına 1–5 kopya ve 2–4 etiket bulunur, tohum 424242’dir. Soru sabittir: Kadıköy şubesinde onarımdaki kopya sayısına göre en yüksek beş yazar. Üç boru hattı bu soruyu yanıtlar. A süzmeyi en başa koyar; B önce diziyi açıp sonra süzer; C hiç süzmeden gruplar ve süzmeyi grupların üstünde yapar. Üçünün de doğru yanıtı vermesi gerekir — ölçülen şey doğruluk değil, bedel.

// sira-olcum.mjs — ayni soru uc farkli asama sirasiyla yanitlanir. Sonuc ayni, islenen
// kayit ve doruk bellek farkli. Ayni dizinde boruhatti.mjs bulunur.
import { calistir, yazdir } from "./boruhatti.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 ETIKETLER = ["roman", "tarih", "cocuk", "siir", "bilim", "basvuru"];

const KATALOG = [];
for (let i = 1; i <= 20000; i += 1) {
  const kopya = [], etiket = [];
  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: DURUM[Math.floor(rast() * 3)] });
  for (let j = 0, n = 2 + Math.floor(rast() * 3); j < n; j += 1)
    etiket.push(ETIKETLER[Math.floor(rast() * 6)]);
  KATALOG.push({ _k: `K-${String(i).padStart(5, "0")}`, yazar: `Yazar ${i % 4000}`,
    yayin_yili: 1950 + (i % 75), etiket, kopya });
}
console.log(`katalog ${KATALOG.length} kitap, ` +
  `${KATALOG.reduce((t, b) => t + b.kopya.length, 0)} kopya`);

// Soru: Kadikoy subesinde onarimdaki kopya sayisina gore en yuksek 5 yazar.
const ONARIM = (k) => k.sube === "Kadikoy" && k.durum === "onarimda";
const GRUP = { anahtar: (b) => b.yazar, bos: (k) => ({ yazar: k, sayi: 0 }),
  topla: (g, b) => ({ ...g, sayi: g.sayi + 1 }) };
const SIRALA = (a, b) => b.sayi - a.sayi || (a.yazar < b.yazar ? -1 : 1);

const A = calistir(KATALOG, [
  { suz: (b) => b.kopya.some(ONARIM) },                 // once suz: kitap duzeyinde
  { ac: "kopya" },
  { suz: (b) => ONARIM(b.kopya) },                      // acilan ogeyi suz
  { grupla: GRUP }, { sirala: SIRALA }, { sinirla: 5 },
]);
const B = calistir(KATALOG, [
  { ac: "kopya" },
  { suz: (b) => ONARIM(b.kopya) },
  { grupla: GRUP }, { sirala: SIRALA }, { sinirla: 5 },
]);
const C = calistir(KATALOG, [
  { ac: "kopya" },
  { grupla: { anahtar: (b) => `${b.yazar}|${b.kopya.sube}|${b.kopya.durum}`,
    bos: (k) => ({ yazar: k.split("|")[0], sube: k.split("|")[1],
      durum: k.split("|")[2], sayi: 0 }),
    topla: (g, b) => ({ ...g, sayi: g.sayi + 1 }) } },
  { suz: (g) => g.sube === "Kadikoy" && g.durum === "onarimda" },
  { sirala: SIRALA }, { sinirla: 5 },
]);

yazdir("A once suz", A);
yazdir("B ac sonra suz", B);
yazdir("C once grupla sonra suz", C);
const ozet = (c) => c.sonuc.map((g) => `${g.yazar}=${g.sayi}`).join(" ");
console.log(`A sonuc: ${ozet(A)}`);
console.log(`ucu ayni mi: ${ozet(A) === ozet(B) && ozet(B) === ozet(C)}`);
console.log(`islenen kayit  A ${A.islenen}  B ${B.islenen}  C ${C.islenen}` +
  `   B/A ${(B.islenen / A.islenen).toFixed(2)}  C/A ${(C.islenen / A.islenen).toFixed(2)}`);
console.log(`doruk bellek   A ${A.doruk}  B ${B.doruk}  C ${C.doruk}` +
  `   C/A ${(C.doruk / A.doruk).toFixed(1)} kat`);

katalog 20000 kitap, 59494 kopya
A once suz: islenen kayit 43610, doruk bellek 2418 kayit
  suz      giren  20000 -> cikan   3340   bellek 1
  ac       giren   3340 -> cikan  11926   bellek 1
  suz      giren  11926 -> cikan   3508   bellek 1
  grupla   giren   3508 -> cikan   2418   bellek 2418
  sirala   giren   2418 -> cikan   2418   bellek 2418
  sinirla  giren   2418 -> cikan      5   bellek 1
B ac sonra suz: islenen kayit 87838, doruk bellek 2418 kayit
  ac       giren  20000 -> cikan  59494   bellek 1
  suz      giren  59494 -> cikan   3508   bellek 1
  grupla   giren   3508 -> cikan   2418   bellek 2418
  sirala   giren   2418 -> cikan   2418   bellek 2418
  sinirla  giren   2418 -> cikan      5   bellek 1
C once grupla sonra suz: islenen kayit 124606, doruk bellek 40276 kayit
  ac       giren  20000 -> cikan  59494   bellek 1
  grupla   giren  59494 -> cikan  40276   bellek 40276
  suz      giren  40276 -> cikan   2418   bellek 1
  sirala   giren   2418 -> cikan   2418   bellek 2418
  sinirla  giren   2418 -> cikan      5   bellek 1
A sonuc: Yazar 1068=4 Yazar 111=4 Yazar 1530=4 Yazar 1580=4 Yazar 1618=4
ucu ayni mi: true
islenen kayit  A 43610  B 87838  C 124606   B/A 2.01  C/A 2.86
doruk bellek   A 2418  B 2418  C 40276   C/A 16.7 kat

Sıranın Bedeli

Üç boru hattı aynı beş yazarı aynı sayılarla döndürür; ucu ayni mi satırı bunu doğrular. Ayrıldıkları yer bedeldir ve bedel iki ayrı sayıyla ölçülür.

İşlenen kayıt sayısı A’da 43.610, B’de 87.838, C’de 124.606’dır. A ile B arasındaki fark yalnız ilk süzmeden gelir: A, dizi açma aşamasına 20.000 kitabın 3.340’ını sokar, B ise tamamını sokar. Açma aşaması A’da 11.926, B’de 59.494 kayıt üretir — beş kat fazla. Buna karşılık A fazladan bir aşama koşturur ve ilk süzme 20.000 belgeye bakar. Toplamda oran 2,01’dir. Kural şudur: süzme, akışı en çok daraltacağı yere değil, kaydı çoğaltan aşamadan önceye konur; dizi açma bir çoğaltıcıdır.

A’nın ilk süzmesi öge düzeyinde değil belge düzeyindedir ve önceki dersin ölçtüğü gevşek biçimdedir: 3.340 belge döndürür. Ardından açılan 11.926 kaydın yalnız 3.508’i ikinci süzmeden geçer. Bu gevşeklik bir hata değil, kasıtlı bir seçimdir — belge düzeyi süzme doğru sonucu kaçırmaz, yalnız fazladan kayıt geçirir. Boru hattında öne konan süzmenin tek koşulu budur: kapsayıcı olmalı, daraltıcı olması gerekmez.

İkinci sayı belleği verir. A ve B’de doruk bellek 2.418 kayıttır — grup tablosunun boyu, yani Kadıköy’de onarımda kopyası olan farklı yazar sayısı. C’de aynı sayı 40.276’dır, 16,7 kat fazla. C’nin yaptığı hata gruplamayı süzmeden önce koymaktır: gruplama artık yalnız ilgilenilen yazarları değil, yazar–şube–durum üçlüsünün bütün birleşimlerini tutar. Bu sayı derlem büyüdükçe grup anahtarının çarpımıyla büyür ve engelleyici aşamanın bellek sınırını aşması, boru hattının diske taşmasına ya da tümden reddedilmesine yol açar.

Son aşama olan sinirla üçünde de aynı yerdedir ve hiçbirinde işi azaltmaz: sıralama zaten 2.418 kaydın tamamını görmüştür. Sınırlama, kendisinden önceki engelleyici aşamanın işini küçültmez — bunu ancak sıralamanın kendisinin ilk beşi tutan bir biçimi yapabilir ve o da sıralama aşamasının içinde bir karardır, boru hattının sırasında değil.

Özet

• Toplama boru hattı sıralı aşamalardan oluşur; akış aşamaları tek kayıt tutar, engelleyici aşamalar (gruplama, sıralama) akışın tamamını ya da grup tablosunu bellekte tutar.
• Dizi açma aşaması kaydı çoğaltır: 20.000 kitap belgesi 59.494 kayda dönüşür.
• Aynı soru üç sırayla aynı yanıtı verir, ama 43.610, 87.838 ve 124.606 kayıt işler; süzmeyi çoğaltıcı aşamadan önceye almak işlenen kaydı yarıya indirir.
• Öne konan süzmenin kapsayıcı olması yeter; A’nın belge düzeyi süzmesi 3.340 belge geçirir, bunların açılmasından çıkan 11.926 kaydın 3.508’i sonuca kalır.
• Gruplamayı süzmeden önce koymak doruk belleği 2.418 kayıttan 40.276 kayda çıkarır (16,7 kat).

Sonraki Adım

Üç boru hattının ortak yanı gözden kaçtı: üçü de ilk aşamada derlemin tamamını, 20.000 belgeyi okudu. Aşama sırası işlenen kaydı ve tutulan belleği değiştirdi, okunan belge sayısını değiştirmedi. Onu değiştiren tek şey dizindir. Belge modelinde dizin, ilişkisel kursta ölçülen dizinden yapı olarak ayrılmaz — ama üstüne kurulduğu veri ayrılır: dizi alanı bir belge için birden çok giriş üretir, gömülü alan noktalı bir yolla adreslenir ve dizinin yalnız belgelerin bir bölümünü kapsaması istenebilir. Sonraki ders bu üç durumu kurar ve dizin boyutu ile yazma bedelini sayar.