Dizgiler ve Sayaçlar

Önceki dersin her yazması bütün değeri baştan yazdı. Kütüphanenin saydığı şeylerin çoğu bu kalıba uymaz: bir kitabın ödünç sayısı, bir şubenin günlük ödünç toplamı, bir üyenin gecikme sayısı — hepsi tek bir sayıdır ve her olayda bir artar. Bu ders o sayıyı iki soruyla ele alıyor: sayacı artırmanın kim tarafından yapıldığı neyi değiştirir, ve tek bir sayı bellekte gerçekte kaç bayta mal olur.

Depo değeri bir bayt dizisi olarak tutar; sayı da bir dizgidir. Ama depo o dizgiyi sayı gibi yorumlayıp tek adımda artırabilir. Bu yeteneğin adı atomik artırmadır ve ilk bakışta bir kolaylık gibi görünür. Ölçüldüğünde bir kolaylık değil, doğruluğun kendisi olduğu çıkar.

Sayacı Kim Artırıyor

İki yol vardır. Oku-değiştir-yaz üç ayrı adımdır: değer okunur, uygulamada bir artırılır, geri yazılır. Atomik artırma tek adımdır: depo değeri okur, ekler ve yazar; arada başka hiçbir iş araya giremez. Fark yalnız eşzamanlılık altında görünür.

Ölçüm için popüler bir kitabın ödünç sayacı kullanılır. BY1: aynı kitabı 1, 2, 4, 8 ve 16 şube eşzamanlı olarak ödünç veriyor ve her şube 500 ödünç kaydediyor; beklenen sayaç değeri şube sayısı × 500’dür. BY2: eşzamanlılık üreteçlerle kurulur, her yield bir kesilme noktasıdır ve zamanlayıcı hazır istemciler arasından tohumu görünür bir üreticiyle seçer; koşum belirlenimlidir.

// bellek/sayac.mjs — ayni odunc sayacinin iki yolla artirilmasi. Istemciler uretec,
// zamanlayici tohumlu; adim sirasi kosumdan bagimsizdir.
class BellekIciDepo {
  #tablo = new Map();
  gidis = 0;
  oku(a) { this.gidis += 1; const s = this.#tablo.get(a); return s === undefined ? 0 : Number(s); }
  ayarla(a, v) { this.gidis += 1; this.#tablo.set(a, String(v)); }
  artir(a, d) {                                // tek adimda okur, ekler, yazar
    this.gidis += 1;
    const v = (this.#tablo.has(a) ? Number(this.#tablo.get(a)) : 0) + d;
    this.#tablo.set(a, String(v)); return v; }
}

function* okuDegistirYaz(d, a, kez) {
  for (let i = 0; i < kez; i += 1) { const v = d.oku(a); yield; d.ayarla(a, v + 1); yield; }
}
function* atomik(d, a, kez) {
  for (let i = 0; i < kez; i += 1) { d.artir(a, 1); yield; }
}

const TOHUM = 20240115, KEZ = 500, ANAHTAR = "kitap:100427:odunc";
function zamanla(uretecler) {                  // hazir istemcilerden tohumlu secim
  let c = TOHUM;
  const rast = () => (c = (c * 1103515245 + 12345) % 2147483648) / 2147483648;
  const canli = [...uretecler];
  while (canli.length > 0) {
    const i = Math.floor(rast() * canli.length);
    if (canli[i].next().done) canli.splice(i, 1);
  }
}

console.log(`tohum ${TOHUM}; her sube ${KEZ} odunc kaydeder, anahtar ${ANAHTAR}`);
console.log(`${"sube".padStart(5)}${"beklenen".padStart(10)}${"oku-degistir-yaz".padStart(18)}` +
  `${"kayip".padStart(7)}${"gidis".padStart(8)}${"atomik artirma".padStart(16)}${"kayip".padStart(7)}${"gidis".padStart(7)}`);
for (const sube of [1, 2, 4, 8, 16]) {
  const beklenen = sube * KEZ;
  const d1 = new BellekIciDepo();
  zamanla(Array.from({ length: sube }, () => okuDegistirYaz(d1, ANAHTAR, KEZ)));
  const d2 = new BellekIciDepo();
  zamanla(Array.from({ length: sube }, () => atomik(d2, ANAHTAR, KEZ)));
  const s1 = d1.oku(ANAHTAR), s2 = d2.oku(ANAHTAR);
  console.log(String(sube).padStart(5) + String(beklenen).padStart(10) + String(s1).padStart(18) +
    String(beklenen - s1).padStart(7) + String(d1.gidis - 1).padStart(8) + String(s2).padStart(16) +
    String(beklenen - s2).padStart(7) + String(d2.gidis - 1).padStart(7));
}

tohum 20240115; her sube 500 odunc kaydeder, anahtar kitap:100427:odunc
 sube  beklenen  oku-degistir-yaz  kayip   gidis  atomik artirma  kayip  gidis
    1       500               500      0    1000             500      0    500
    2      1000               620    380    2000            1000      0   1000
    4      2000               747   1253    4000            2000      0   2000
    8      4000               871   3129    8000            4000      0   4000
   16      8000               938   7062   16000            8000      0   8000

Tek şube çalışırken iki yol da doğru sonucu veriyor; ayrım ikinci şubeyle başlıyor. İki şubede 1.000 ödüncün 380’i kayboluyor, on altı şubede 8.000 ödüncün 7.062’si. Sayaç 938’de kalıyor: kütüphane sekiz bin ödünç verdi, kaydında dokuz yüz otuz sekiz yazıyor. Kaybolan güncelleme bir gecikme ya da yavaşlama değil, yanlış sayıdır ve hiçbir yerde hata olarak görünmez.

Nedeni okuma ile yazma arasındaki aralıktır. Bir şube 41 değerini okuyup 42 yazana kadar başka şubeler de 41 okumuş olur; hepsi 42 yazar ve dördü birden tek bir artırma yapmış olur. Atomik artırmada bu aralık yoktur — depo değeri okur, ekler ve yazar; işlem bölünmez. On altı şubede kayıp sıfırdır.

Gidiş sütunu ikinci kazancı gösteriyor: oku-değiştir-yaz her artırma için iki gidiş harcarken atomik artırma bir gidişte biter, 16.000 yerine 8.000. Aynı doğruluğu oku-değiştir-yaz ile elde etmenin yolu uygulamada bir kilit tutmaktır; o da kilidin kendisini bellekte tutmak ve şubeleri sıraya dizmek demektir. Atomik artırma hem bir gidişi hem de kilidin belleğini ortadan kaldırır — ve karşılığında hiçbir ek bayt istemez, çünkü artırma deponun kendi işidir.

Bir Sayının Bellekteki Fiyatı

Sayaç doğru arttı; şimdi asıl soru gelir. Kataloğun tamamı için ödünç sayacı tutmak bellekte ne kadar yer kaplar. BY3: katalog 200.000 kitap taşır, her kitabın sayaç değeri belirlenimli bir işlevden gelir ve 1 ile 4.096 arasındadır; ödünç kütüğü 119.993 kayıttır ve bellek içi deponun dışındadır — taranması adım sayar, bayt tutmaz. BY4: sorgu yükü 10.000 “bu kitap kaç kez ödünç alındı” sorusudur ve popülerliğe eğiktir; eğim aynı tohumlu üreticiden gelir.

// bellek/sayac-butce.mjs — bir sayacin bellekteki fiyati ve sayac tutmayan iki secenek.
// Odunc kutugu bellek ici deponun disindadir; taranmasi adim sayar, bayt tutmaz.
const USTVERI = 56, KITAP = 200_000, KUTUK = 119_993, SORGU = 10_000, SICAK = 1_000, TOHUM = 20240115;
let c = TOHUM;
const rast = () => (c = (c * 1103515245 + 12345) % 2147483648) / 2147483648;

// sayac degeri: kitap i icin gunluk odunc sayisi (belirlenimli)
const sayacDegeri = (i) => 1 + ((i * 7919) % 4096);
const anahtar = (i) => `kitap:${100_000 + i}:odunc`;

let toplamA = 0, toplamD = 0, toplamU = 0;
for (let i = 1; i <= KITAP; i += 1) {
  toplamA += Buffer.byteLength(anahtar(i));
  toplamD += Buffer.byteLength(String(sayacDegeri(i)));
  toplamU += USTVERI;
}
const tam = toplamA + toplamD + toplamU;
console.log(`${KITAP} kitap, ornek giris "${anahtar(427)}" -> "${sayacDegeri(427)}"`);
console.log(`tam sayac: anahtar ${toplamA} + deger ${toplamD} + ustveri ${toplamU} = ${tam} bayt` +
  ` (giris basina ${(tam / KITAP).toFixed(1)}; degerin payi %${(100 * toplamD / tam).toFixed(1)})`);

// sorgu yuku: "bu kitap kac kez odunc alindi" — populerlige egik, tohumlu
const sorgu = Array.from({ length: SORGU }, () => 1 + Math.floor(KITAP * rast() ** 6));
const sicakSorgu = sorgu.filter((i) => i <= SICAK).length;
const kismi = Array.from({ length: SICAK }, (_, j) =>
  Buffer.byteLength(anahtar(j + 1)) + Buffer.byteLength(String(sayacDegeri(j + 1))) + USTVERI)
  .reduce((t, x) => t + x, 0);

const taban = SORGU * KUTUK;                   // sayac tutulmadigindaki adim
const yol = [
  ["sayac yok, kutuk taramasi", 0, 0, taban],
  [`kismi sayac (ust ${SICAK})`, SICAK, kismi, sicakSorgu + (SORGU - sicakSorgu) * KUTUK],
  ["tam sayac", KITAP, tam, SORGU],
];
console.log(`\n${SORGU} sorgu, ${sicakSorgu} tanesi ilk ${SICAK} kitaba (%${(100 * sicakSorgu / SORGU).toFixed(1)})`);
console.log(`${"yol".padEnd(27)}${"giris".padStart(7)}${"tutulan bayt".padStart(14)}` +
  `${"sorgu basina adim".padStart(19)}${"bayt basina onlenen adim".padStart(26)}`);
for (const [ad, n, b, adim] of yol)
  console.log(ad.padEnd(27) + String(n).padStart(7) + String(b).padStart(14) +
    (adim / SORGU).toFixed(1).padStart(19) + (b === 0 ? "-" : ((taban - adim) / b).toFixed(1)).padStart(26));

200000 kitap, ornek giris "kitap:100427:odunc" -> "2214"
tam sayac: anahtar 3600000 + deger 745901 + ustveri 11200000 = 15545901 bayt (giris basina 77.7; degerin payi %4.8)

10000 sorgu, 4149 tanesi ilk 1000 kitaba (%41.5)
yol                          giris  tutulan bayt  sorgu basina adim  bayt basina onlenen adim
sayac yok, kutuk taramasi        0             0           119993.0                         -
kismi sayac (ust 1000)        1000         77662            70208.3                    6410.4
tam sayac                   200000      15545901                1.0                      77.2

İlk satır dersin başlığını taşır: 200.000 sayaç 15.545.901 bayt tutar, giriş başına 77,7. Oysa saklanan bilgi dört basamaklı bir sayıdır. Sayının kendisi toplamın yalnız %4,8’ini kaplıyor; anahtar adı %23,2’sini, giriş üstverisi %72’sini. Bellek içi depoda bir sayı tutmak dört bayt değil yetmiş yedi bayttır. Bu oran her küçük değer için geçerlidir ve tek kaldıraç değerin kendisi değil, kaç anahtar açıldığıdır.

Alt tablo üç seçeneği aynı yükte karşılaştırıyor. Sayaç hiç tutulmazsa bellek sıfırdır, her sorgu 119.993 kayıtlık kütüğü tarar. Tam sayaçla bellek 15,5 MB’a çıkar ve sorgu başına adım 1’e iner: 15,5 MB, sorgu başına 119.992 adım satın alıyor.

Son sütun kararı asıl kuran sayıdır. Yalnız ilk 1.000 kitap için sayaç tutmak 77.662 bayt ister — tam sayacın iki yüzde biri — ve sorguların %41,5’ini tek adıma indirir. Tuttuğu her bayt 6.410 adım önlüyor; tam sayaçta aynı rakam 77,2. Kısmi sayaç bayt başına seksen üç kat verimli. Ama mutlak sayı hâlâ acımasızdır: sorgu başına 70.208 adım, çünkü ıskalayan %58,5’in her biri bütün kütüğü tarar. Bellek bütçesi darsa kısmi sayaç en verimli alımdır; sorgu başına sabit adım gerekiyorsa 15,5 MB’ın alternatifi yoktur. İkisi arasında karar veren şey “hız” değil, ıskalama oranı ile bütçenin çarpımıdır.

Özet

• Sayacın iki güncelleme yolu vardır: oku-değiştir-yaz üç adımdır ve okuma ile yazma arasında başka istemcilere açıktır; atomik artırma deponun tek bölünmez adımıdır.
• Eşzamanlılık arttıkça kayıp büyür: 2 şubede 1.000 ödüncün 380’i, 16 şubede 8.000 ödüncün 7.062’si kayboluyor ve sayaç 938’de kalıyor. Atomik artırmada kayıp her düzeyde sıfırdır.
• Atomik artırma gidişi de yarıya indirir (16.000 yerine 8.000) ve doğruluk için uygulamada kilit tutmayı gereksiz kılar; kilit hem bellek hem bekleme demektir.
• 200.000 ödünç sayacı 15.545.901 bayt tutar. Sayının kendisi bunun %4,8’i, anahtar adı %23,2’si, giriş üstverisi %72’sidir: bellek içi depoda bir sayı 77,7 bayttır.
• Üç seçenek aynı yükte: sayaçsız 0 bayt ve sorgu başına 119.993 adım; kısmi sayaç 77.662 bayt ve 70.208 adım; tam sayaç 15.545.901 bayt ve 1 adım.
• Bayt başına önlenen adım kısmi sayaçta 6.410, tam sayaçta 77,2. Kısmi sayaç bütçe başına çok daha verimlidir ama sorgu başına sabit adım güvencesi vermez.

Sonraki Adım

Sayaç “kaç” sorusunu tek bayt mertebesinde yanıtlıyor, ama kütüphanenin ikinci sorusunu hiç karşılamıyor: popüler bir kitabı bekleyenler kimler ve hangi sırada. Bekleme listesi bir sayı değil bir dizidir; sıra bilgisinin kendisi bilginin bir parçasıdır ve depo onu koruyacaksa her üyeyi ayrı ayrı tutmak zorundadır. Sonraki ders listeyi ele alıyor ve üç şeyi ölçüyor: iki uçtan ekleme ile çıkarmanın adım sayısı, listenin büyümesinin belleğe etkisi ve sınırlı bir listenin — belli bir uzunlukta kırpılanın — sınırsız olana göre neyi ucuzlattığı ile neyi sessizce kaybettirdiği.