Akışlar

Önceki yapıların hiçbiri sırayı ve okuma konumunu birlikte tutmuyordu. Küme üyeyi tutar ama girişlerin hangi sırayla eklendiğini unutur; sayaç toplamı tutar ama geçmişi bırakmaz; liste sırayı tutar ama okuyan her tarafın nerede kaldığını okuyanın kendisine bırakır. Kütüphanenin üç ayrı işi — raf yerleştirme, gecikme bildirimi ve arama dizini güncellemesi — aynı olay dizisini oldukları sırayla ve her biri kendi kaldığı yerden görmek zorunda.

Akış bunu tek bir yapıda birleştirir: girişler eklendikleri sırayla durur, her girişin sıralanabilir bir kimliği vardır ve her tüketici grubu yalnız bir sınır kimliği tutarak nerede kaldığını hatırlar. Bu ders akışı bir ileti kanalı olarak değil, bellekte yer tutan bir veri yapısı olarak ele alır: giriş kaç bayt, kimlik ne işe yarıyor ve girişler ne zaman atılıyor.

Giriş Kimliği

Kimlik iki parçadan kurulur: girişin eklendiği andaki saat ve o saat içindeki sıra. Saat ilerlemediğinde sıra ilerler, dolayısıyla ayrı bir sayaç yapısına gerek kalmadan iki giriş asla aynı kimliği almaz.

// giris-kimligi.mjs — akis girisinin kimligi ve bayti. Kimlik <zaman>-<sira> biciminde
// uretilir: saat ilerlemediginde sira ilerler, boylece ayni milisaniyede cakisma olmaz.
const uretec = () => { let sonMs = -1, sira = 0;
  return (ms) => { if (ms === sonMs) sira += 1; else { sonMs = ms; sira = 0; } return `${ms}-${sira}`; }; };
const uret = uretec();
const kimlikler = [999, 1000, 1000, 1000, 1001, 1001].map(uret);
console.log("bir yigilmada uretilen kimlikler: " + kimlikler.join("  "));

const cozumle = (k) => k.split("-").map(Number);
const kucukMu = (a, b) => { const [x, y] = cozumle(a), [p, q] = cozumle(b);
  return x !== p ? x < p : y < q; };
console.log(`sayisal karsilastirma  999-0 < 1000-0: ${kucukMu("999-0", "1000-0")}`);
console.log(`dizgi karsilastirmasi  999-0 < 1000-0: ${"999-0" < "1000-0"} (kimlik dizgi olarak siralanmaz)`);
const sinir = "1000-1";                       // tuketici grubunun en son onayladigi kimlik
console.log(`${sinir} sonrasi okunacak giris: ` + kimlikler.filter((k) => kucukMu(sinir, k)).join(" "));

const USTVERI = 24, GOSTERGE = 8;             // kimlik 16 + zincir gostergesi 8; alan basina 8
const g = { tur: "odunc", okur: "418302", kitap: "9780000041173", sube: "sube-3" };
let toplam = USTVERI;
console.log("\nalan".padEnd(8) + "ad".padStart(4) + "deger".padStart(7) + "gosterge".padStart(10) +
  "bayt".padStart(6));
for (const [a, v] of Object.entries(g)) {
  const b = Buffer.byteLength(a) + Buffer.byteLength(v) + GOSTERGE; toplam += b;
  console.log(a.padEnd(8) + String(Buffer.byteLength(a)).padStart(4) +
    String(Buffer.byteLength(v)).padStart(7) + String(GOSTERGE).padStart(10) + String(b).padStart(6));
}
console.log(`ustveri`.padEnd(8) + "".padStart(4) + "".padStart(7) + "".padStart(10) +
  String(USTVERI).padStart(6));
console.log(`giris toplami: ${toplam} bayt; ayni veri alan adlari olmadan ` +
  `${toplam - Object.keys(g).reduce((s, a) => s + Buffer.byteLength(a), 0)} bayt tutardi`);

bir yigilmada uretilen kimlikler: 999-0  1000-0  1000-1  1000-2  1001-0  1001-1
sayisal karsilastirma  999-0 < 1000-0: true
dizgi karsilastirmasi  999-0 < 1000-0: false (kimlik dizgi olarak siralanmaz)
1000-1 sonrasi okunacak giris: 1000-2 1001-0 1001-1

alan     ad  deger  gosterge  bayt
tur        3      5         8    16
okur       4      6         8    18
kitap      5     13         8    26
sube       4      6         8    18
ustveri                          24
giris toplami: 102 bayt; ayni veri alan adlari olmadan 86 bayt tutardi

Kimliğin üç işi var. Birincisi sıra: girişler kimliğe göre sıralanır ve bu sıra ekleme sırasıdır. İkincisi sınır: bir tüketici grubunun tuttuğu tek şey en son onayladığı kimliktir; “1000-1 sonrası” ifadesi grubun okuma konumunu on altı bayta indirir. Üçüncüsü çakışmazlık: aynı milisaniyeye düşen üç giriş 1000-0, 1000-1 ve 1000-2 olur.

Karşılaştırmanın sayısal olduğu satır ihmal edilecek bir ayrıntı değil. Kimlik bir dizgi gibi karşılaştırılırsa 999-0 ile 1000-0 ters sıralanır, çünkü basamak sayıları farklıdır; sıra güvencesi kimliğin biçiminden değil, çözümlenerek karşılaştırılmasından gelir.

Bayt tablosu bir tasarım kararını görünür kılıyor. Girişin 102 baytının 16’sı alan adlarıdır ve bu adlar her girişte yeniden yazılır. Günde 600.000 giriş için bu, yalnız dört sözcüğün tekrarı olarak 9,15 MiB demektir. Kısa alan adları ya da konuma dayalı bir düzen bu payı düşürür; karşılığında akışı okuyan tarafın alan sırasını bilmesi gerekir, yani günlüğün kendi kendini açıklaması kaybedilir.

Bir Günün Akışı

Akışın bellek maliyeti giriş baytı ile kaç girişin tutulduğunun çarpımıdır ve ikinci çarpanı belirleyen şey kırpma politikasıdır.

Kod	Varsayım	Değer	Gerekçe
BY14	günlük etkinlik girişi	600.000	bütün şubelerin ödünç, iade, ayırtma ve raf hareketi
BY15	giriş üstverisi	24 bayt	kimlik 16 bayt, zincir göstergesi 8 bayt
BY16	tüketici grubu	3 grup, 1500 / 1000 / 700 giriş/dk	üç işin işleme hızı ayrı
BY17	saatlik yoğunluk eğrisi	tepe çarpanı 2,8	kütüphane gündüz açık, gece neredeyse durgun

BY16 bu dersin karar verdiren varsayımıdır: üç grubun hızı eşit olsaydı kırpma politikası tek başına belleği belirlerdi, eşit olmadığı için belleği en yavaş grup belirliyor.

// akis.mjs — bir gunluk etkinlik akisi: kirpma politikalari ve okunmamis payin bellege etkisi.
// Gun 1440 dakikalik adima bolunur, varislar saat carpanlarindan uretilir, tohum gorunur.
const OLAY = 600_000, TOHUM = 20260731, DK = 1440, USTVERI = 24, GOSTERGE = 8;
const CARPAN = [0.05, 0.03, 0.02, 0.02, 0.03, 0.08, 0.2, 0.6, 1.6, 2.2, 2.6, 2.4,
                1.8, 2.0, 2.6, 2.8, 2.5, 2.0, 1.4, 0.9, 0.5, 0.3, 0.15, 0.08];
const GRUP = [["raf yerlestirme", 1500], ["gecikme bildirimi", 1000], ["arama dizini", 700]];
let d = TOHUM;
const rast = () => { d = (d + 0x6D2B79F5) | 0; let t = Math.imul(d ^ (d >>> 15), 1 | d);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32; };
const TUR = ["odunc", "iade", "ayirtma", "raf-degisimi"];
const giris = (i) => ({ tur: TUR[Math.floor(rast() * 4)], okur: String(100000 + (i % 900000)),
  kitap: String(9780000000000 + (i % 120000)), sube: `sube-${1 + Math.floor(rast() * 6)}` });
const bayt = (g) => USTVERI + Object.entries(g)
  .reduce((s, [a, v]) => s + Buffer.byteLength(a) + Buffer.byteLength(v) + GOSTERGE, 0);

const olcek = CARPAN.reduce((s, c) => s + c, 0) * 60;
const gb = new Uint16Array(OLAY * 2), gt = new Uint16Array(OLAY * 2);
let n = 0;
for (let t = 0; t < DK; t += 1) {
  const k = Math.round((OLAY * CARPAN[Math.floor(t / 60)]) / olcek);
  for (let i = 0; i < k; i += 1) { gb[n] = bayt(giris(n)); gt[n] = t; n += 1; }
}
const on = new Float64Array(n + 1);                          // kumulatif bayt
for (let i = 0; i < n; i += 1) on[i + 1] = on[i] + gb[i];
const tr = (x) => x.toLocaleString("tr-TR", { maximumFractionDigits: 2 });
const saatDk = (t) => `${Math.floor(t / 60)}:${String(t % 60).padStart(2, "0")}`;
let enAz = gb[0], enCok = gb[0];
for (let j = 1; j < n; j += 1) { if (gb[j] < enAz) enAz = gb[j]; if (gb[j] > enCok) enCok = gb[j]; }
console.log(`model: ${tr(n)} giris/gun, ${DK} dakikalik adim, tohum ${TOHUM}`);
console.log(`giris bayti: ortalama ${tr(on[n] / n)}, en kucuk ${enAz}, en buyuk ${enCok}; ` +
  `gunun tamami ${tr(Math.round(on[n] / 1024 ** 2))} MiB\n`);

function kos(ad, kirp, durakla = null) {
  const imlec = GRUP.map(() => 0);
  let bas = 0, son = 0, i = 0, tepe = 0, tepeBayt = 0, tepeDk = 0, kayip = 0;
  for (let t = 0; t < DK; t += 1) {
    while (i < n && gt[i] === t) { i += 1; son += 1; }
    for (let g = 0; g < GRUP.length; g += 1) {
      const durgun = durakla && g === durakla[0] && t >= durakla[1] && t < durakla[2];
      if (!durgun) imlec[g] = Math.min(son, imlec[g] + GRUP[g][1]);
    }
    bas = Math.max(bas, kirp(son, t, imlec));
    for (let g = 0; g < GRUP.length; g += 1)
      if (imlec[g] < bas) { kayip += bas - imlec[g]; imlec[g] = bas; }
    if (son - bas > tepe) { tepe = son - bas; tepeBayt = on[son] - on[bas]; tepeDk = t; }
  }
  console.log(ad.padEnd(26) + tr(son - bas).padStart(11) + tr(tepe).padStart(11) +
    tr(Math.round(tepeBayt / 1024)).padStart(11) + saatDk(tepeDk).padStart(9) +
    tr(kayip).padStart(11));
}
const ilkAdim = (t, T) => { let l = 0, r = n; while (l < r) {
  const m = (l + r) >> 1; if (gt[m] < t - T) l = m + 1; else r = m; } return l; };
console.log("politika".padEnd(26) + "gun sonu".padStart(11) + "tepe giris".padStart(11) +
  "tepe KiB".padStart(11) + "tepe dk".padStart(9) + "kacirilan".padStart(11));
kos("kirpma yok", () => 0);
kos("uzunluk 50.000", (son) => son - 50_000);
kos("sure 60 dk", (son, t) => ilkAdim(t, 60));
kos("guvenli (en yavas grup)", (son, t, im) => Math.min(...im));
kos("guvenli + 30 dk duraklama", (son, t, im) => Math.min(...im), [2, 1020, 1050]);

console.log("\ngrup".padEnd(26) + "hiz/dk".padStart(9) + "tepe okunmamis".padStart(16) +
  "tepe KiB".padStart(11) + "tepe dk".padStart(9) + "gun sonu".padStart(10));
const imlec = GRUP.map(() => 0), tepe = GRUP.map(() => [0, 0, 0]);
let son = 0, i = 0;
for (let t = 0; t < DK; t += 1) {
  while (i < n && gt[i] === t) { i += 1; son += 1; }
  for (let g = 0; g < GRUP.length; g += 1) {
    imlec[g] = Math.min(son, imlec[g] + GRUP[g][1]);
    if (son - imlec[g] > tepe[g][0]) tepe[g] = [son - imlec[g], on[son] - on[imlec[g]], t];
  }
}
for (let g = 0; g < GRUP.length; g += 1)
  console.log(GRUP[g][0].padEnd(26) + tr(GRUP[g][1]).padStart(9) + tr(tepe[g][0]).padStart(16) +
    tr(Math.round(tepe[g][1] / 1024)).padStart(11) + saatDk(tepe[g][2]).padStart(9) +
    tr(son - imlec[g]).padStart(10));

model: 600.000 giris/gun, 1440 dakikalik adim, tohum 20260731
giris bayti: ortalama 104, en kucuk 101, en buyuk 109; gunun tamami 60 MiB

politika                     gun sonu tepe giris   tepe KiB  tepe dk  kacirilan
kirpma yok                    600.000    600.000     60.935    23:59          0
uzunluk 50.000                 50.000     50.000      5.078     8:45     38.920
sure 60 dk                      1.856     63.488      6.447    15:59     46.220
guvenli (en yavas grup)             0     88.920      9.031    17:59          0
guvenli + 30 dk duraklama           0    109.920     11.163    17:59          0

grup                        hiz/dk  tepe okunmamis   tepe KiB  tepe dk  gun sonu
raf yerlestirme               1.500               0          0     0:00         0
gecikme bildirimi             1.000           2.520        256    15:59         0
arama dizini                    700          88.920      9.031    17:59         0

Bu sayılar ölçüm sınıfındadır; girişlerin dağılımı saat eğrisine ve tohuma bağlı, politikalar arasındaki fark bağlı değil.

Okunmamış Pay

Üst tablo dört politikayı aynı gün üzerinde karşılaştırıyor. Kırpma yok akışı 60.935 KiB’ye çıkarıyor ve hiçbir girişi kaçırmıyor: geçmiş sorgulanabilir kalıyor, bedeli günün tamamının bellekte durması. Uzunluk 50.000 belleği 5.078 KiB’de sabitliyor — on iki kat az — ama arama dizini 38.920 girişi hiç görmeden kaybediyor. Süre 60 dk ilk bakışta daha ölçülü görünüyor, gün sonunda yalnız 1.856 giriş tutuyor; oysa tepede 63.488 girişe çıkıyor ve 46.220 giriş kaçırıyor. Aradaki fark politikanın neyi sabitlediğidir: uzunluk sınırı belleği sabitler, süre sınırı yaşı sabitler ve belleği varış hızına bırakır. Yoğunluk üç katına çıkarsa süre sınırlı akış üç kat yer tutar.

Güvenli kırpma dördüncü seçenektir: bir giriş, bütün gruplar onu okuyana kadar silinmez. Kaçırılan sıfıra iner, tutulan bayt 9.031 KiB’de tepe yapar ve gün sonunda sıfırlanır. Ama tavan artık operatörün elinde değildir. Alt tablo bunu gösteriyor: raf yerleştirme hiç geride kalmıyor, gecikme bildirimi tepede 2.520 giriş biriktiriyor, arama dizini 88.920. Akışın tuttuğu 9.031 KiB’nin tamamı en yavaş grubun okumadığı paydır — akış bir kuyruk olduğu için değil, en gerideki sınır kimliğinden öncesini atamadığı için.

Son satır bunun ne kadar keskin olduğunu ölçüyor. Arama dizini tepe saatte otuz dakika duraksa akış 109.920 girişe çıkıyor: tam 21.000 giriş ve 2.132 KiB fazla, yani duraklama süresi çarpı grubun hızı. Bellek maliyeti burada akışın değil, akışı okumayan tarafın kararıdır.

Bunun karşıtı da aynı ölçüde nettir: okuyan taraf sayısı belleği artırmaz. Üç grup üç sınır kimliği tutar, on altışar bayttan kırk sekiz bayt; akışa dördüncü, beşinci, onuncu grup eklemek 60 MiB’lik gövdeye on altı bayt ekler. Akışı bir listeden ayıran şey budur: liste okundukça tüketilir ve ikinci okuyucu için ikinci bir kopya gerekir, akış bir kez tutulur ve konum okuyanın tarafında durur.

Özet

• Giriş kimliği zaman ile sıradan kurulur ve üç iş görür: ekleme sırasını verir, aynı milisaniyedeki girişleri ayırır ve bir tüketici grubunun okuma konumunu on altı bayta indirir; karşılaştırma sayısal olmak zorundadır, dizgi karşılaştırması 999-0 ile 1000-0’ı ters sıralar.
• Giriş baytının bir payı her seferinde tekrarlanan alan adlarıdır: 102 baytın 16’sı, günde 9,15 MiB. Kısaltmak akışın kendi kendini açıklamasını kaybettirir.
• Uzunluk sınırı belleği sabitler (5.078 KiB), süre sınırı yaşı sabitler ve belleği varış hızına bırakır (tepede 63.488 giriş); ikisi de en yavaş grubu bilmediği için 38.920 ve 46.220 giriş kaçırır.
• Güvenli kırpmada kaçırma sıfırdır ama tavan operatörün elinde değildir: tutulan 9.031 KiB’nin tamamı en yavaş grubun okunmamış payıdır ve o grup otuz dakika duraklarsa akış 21.000 giriş (2.132 KiB) büyür.
• Okuyan taraf sayısı belleği artırmaz, okumayan taraf artırır: üç grubun toplam defter maliyeti kırk sekiz bayttır.

Sonraki Adım

Akışın kimliği sıralanabilir olduğu için “şu andan sonrası” sorusu bir arama değil, bir konum belirlemesiydi. Kütüphanenin bir sorusu daha var ve o sorunun sıralanabilir bir anahtarı yok: okur bulunduğu noktaya en yakın toplama noktasını istiyor. İki boyutlu bir konumu tek bir eksende sıralamanın her yolu bazı komşuları birbirinden uzağa düşürür, dolayısıyla ne sıralı küme ne de akış bu soruya doğrudan yanıt verir. Sonraki ders aynı yakınlık sorgusunu bellek içi bir yapıyla kurar ve düz taramanın taradığı aday sayısıyla karşılaştırır.