Kümeleme

Önceki iki ders veri kümesinin tamamının tek düğüme sığdığını varsaydı. Çoğaltma o kümenin kopyalarını çıkardı, devralma kopyalardan birini göreve aldı; ikisi de saklanan baytı çarptı, hiçbiri bölmedi. Katalog ve ödünç kayıtları bir düğümün bellek bütçesini aştığında geriye tek yol kalır: anahtar alanını bölmek ve her düğüme yalnız bir payı vermek.

Bu ders o bölmeyi ele alır. Parçalama ve parça anahtarı seçimi İleri Veri Ölçekleme ve NoSQL kurslarında ölçüldü; burada tekrarlanmaz. Buranın sorusu farklıdır: bölme kararı bellek içi deponun işlem semantiğini nasıl kısıtlar, ve o kısıtı kaldırmanın bellek bütçesindeki karşılığı nedir.

Anahtardan Düğüme

Bölümleme iki adımdır. Anahtar bir karma işlevinden geçirilir ve sabit sayıdaki yuvadan birine düşer; yuva aralıkları düğümlere dağıtılır. Aradaki yuva katmanı, düğüm eklendiğinde yalnız yuva aralıklarının taşınmasını sağlar — anahtarların yeniden karmalanması gerekmez. Aşağıdaki düzenekte 16.384 yuva vardır ve karma işlevi kendi yazılmıştır.

Bunun doğrudan sonucu şudur: iki anahtarın hangi düğüme düşeceği birbirinden bağımsızdır. Bir ödünç işlemi katalog girişine, ödünç sayacına ve bekleme kuyruğuna birlikte dokunuyorsa, bu üç anahtarın aynı düğümde olması bir tasarım kararı değil, bir rastlantıdır. Aynı düğümde olmadıklarında işlem tek bir düğümde yürütülemez — çok anahtarlı işlemin küme kısıtı budur.

Düzenek

Düzenek bir modeldir: gerçek küme, ağ ya da düğüm kurulmaz; düğüm bir sayıdır ve anahtarın hangi düğüme düştüğü karmadan hesaplanır.

BK6 — şube payları eşit değildir: altı şube ödünçlerin yüzde 34, 24, 16, 12, 9 ve 5’ini taşır. Gerekçe: kütüphane şubeleri eşit büyüklükte değildir ve etiketleme kararının bedeli tam olarak bu eşitsizlikte görünür. BK7 — iki işlem biçimi ölçülür: T1 katalog girişi, ödünç sayacı ve bekleme kuyruğuna dokunur; T2 buna şubenin eşzamanlı ödünç sayacını ekler. Gerekçe: sınır denetimi olmayan bir ödünç ile şube sınırını denetleyen bir ödünç farklı sayıda anahtara dokunur ve küme kısıtı anahtar sayısına üstel bağlıdır.

// kumeleme/model.mjs — anahtar alani bolumlemesi SUREC ICI MODELDIR. Gercek kume, ag ya da
// dugum kurulmaz; dugum bir sayidir ve anahtarin hangi dugume dustugu karmadan hesaplanir.
// Karma islevi (FNV-1a, 32 bit) burada kendi yazilmistir.
export const YUVA = 16384, KATALOG_BAYT = 240, ODUNC_BAYT = 96, KUYRUK_BAYT = 128, SAYAC_BAYT = 64;

export function karma(s) {
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i += 1) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193) >>> 0; }
  return h >>> 0;
}
export function yuvaNo(anahtar) {          // anahtarda etiket varsa YALNIZ etiket karmalanir
  const a = anahtar.indexOf("{"), b = anahtar.indexOf("}");
  return karma(a >= 0 && b > a + 1 ? anahtar.slice(a + 1, b) : anahtar) % YUVA;
}
export const dugumu = (yuva, n) => Math.floor(yuva * n / YUVA);   // esit yuva araligi

export function uretec(tohum) {            // dogrusal esleskli uretec; tohum gorunurdur
  let s = tohum >>> 0;
  return () => { s = (Math.imul(s, 1103515245) + 12345) >>> 0; return s / 4294967296; };
}

// Sube paylari esit degildir: buyuk sube odunclerin ucte birini tasir.
export const PAY = [0.34, 0.24, 0.16, 0.12, 0.09, 0.05];

export function veri({ kitap = 3000, odunc = 12000, kuyrukPay = 0.25, tohum = 20260731 }) {
  const rnd = uretec(tohum), kayit = [], kuyruk = new Set();
  const esik = PAY.map((p, i) => PAY.slice(0, i + 1).reduce((a, b) => a + b, 0));
  for (let i = 0; i < odunc; i += 1) {
    const x = rnd(), s = esik.findIndex((e) => x < e);
    kayit.push([s < 0 ? PAY.length - 1 : s, Math.floor(rnd() * kitap)]);
  }
  for (let k = 0; k < kitap; k += 1) if (rnd() < kuyrukPay) kuyruk.add(k);
  return { kitap, kayit, kuyruk };
}

// Uc etiketleme semasi. Etiket, anahtarin hangi parcasinin karmalanacagini belirler.
export const SEMA = {
  yok: { katalog: (k) => `katalog:${k}`, odunc: (s, k) => `odunc:${s}:${k}`,
         kuyruk: (k) => `kuyruk:${k}`, sayac: (s) => `sube:${s}:acikOdunc` },
  sube: { katalog: (k, s) => `{sube:${s}}katalog:${k}`, odunc: (s, k) => `{sube:${s}}odunc:${k}`,
          kuyruk: (k, s) => `{sube:${s}}kuyruk:${k}`, sayac: (s) => `{sube:${s}}acikOdunc` },
  kitap: { katalog: (k) => `{kitap:${k}}katalog:${k}`, odunc: (s, k) => `{kitap:${k}}odunc:${s}`,
           kuyruk: (k) => `{kitap:${k}}kuyruk:${k}`, sayac: (s) => `sube:${s}:acikOdunc` },
};

export function kosum({ sema, dugum, d }) {
  const S = SEMA[sema], bayt = new Map(), yuvalar = new Set();
  const ekle = (anahtar, b) => { bayt.set(anahtar, b); yuvalar.add(yuvaNo(anahtar)); };
  let t1 = 0, t2 = 0;
  for (const [s, k] of d.kayit) {
    ekle(S.katalog(k, s), KATALOG_BAYT);                 // etiket sube ise katalog girisi COGALIR
    ekle(S.odunc(s, k), ODUNC_BAYT);
    if (d.kuyruk.has(k)) ekle(S.kuyruk(k, s), KUYRUK_BAYT);
    ekle(S.sayac(s), SAYAC_BAYT);
    const g = [S.katalog(k, s), S.odunc(s, k), S.kuyruk(k, s)].map((a) => dugumu(yuvaNo(a), dugum));
    if (g.every((x) => x === g[0])) t1 += 1;              // T1: katalog + odunc + kuyruk
    if (g.every((x) => x === g[0]) && dugumu(yuvaNo(S.sayac(s)), dugum) === g[0]) t2 += 1;
  }
  const yuk = Array(dugum).fill(0), sayi = Array(dugum).fill(0);
  for (const [anahtar, b] of bayt) {
    const n = dugumu(yuvaNo(anahtar), dugum);
    yuk[n] += b; sayi[n] += 1;
  }
  const toplam = yuk.reduce((a, b) => a + b, 0);
  return { yuvalar: yuvalar.size, anahtar: bayt.size, toplam, yuk, sayi,
           enYuklu: Math.max(...yuk), dengesizlik: Math.max(...yuk) / (toplam / dugum),
           t1: t1 / d.kayit.length, t2: t2 / d.kayit.length };
}

// kumeleme/olc.mjs — ayni veri kumesi: once dugum sayisi, sonra uc etiketleme semasi
import { veri, kosum, yuvaNo, dugumu, YUVA } from "./model.mjs";

const s = (x, n) => String(x).padStart(n);
const kib = (b, n = 8) => s((b / 1024).toFixed(1), n);
const yuz = (x, n = 7) => s((x * 100).toFixed(2) + "%", n);
const d = veri({});

console.log("3.000 kitap, 6 sube, 12.000 odunc kaydi (tohum 20260731). Katalog girisi 240,");
console.log("odunc 96, kuyruk 128, sube sayaci 64 bayt. " + YUVA + " yuva, dugume esit araliklarla.");
console.log("T1 = katalog + odunc + kuyruk; T2 = T1 + sube sayaci. Etiket yok:\n");
console.log("dugum | anahtar | toplam bayt | en yuklu dugum | dengesizlik | T1 tek dugumde | T2");
console.log("------|---------|-------------|----------------|-------------|----------------|--------");
for (const n of [3, 4, 6, 8]) {
  const r = kosum({ sema: "yok", dugum: n, d });
  console.log(`${s(n, 5)} | ${s(r.anahtar, 7)} | ${kib(r.toplam, 7)} KiB | ${kib(r.enYuklu, 10)} KiB | ` +
    `${s(r.dengesizlik.toFixed(3), 11)} | ${yuz(r.t1, 14)} | ${yuz(r.t2)}`);
}

console.log("\n6 dugum sabit; etiketleme semasi degisiyor:");
console.log("sema  | kullanilan yuva | anahtar | toplam bayt | en yuklu | dengesizlik | T1     | T2");
console.log("------|-----------------|---------|-------------|----------|-------------|--------|--------");
for (const sema of ["yok", "sube", "kitap"]) {
  const r = kosum({ sema, dugum: 6, d });
  console.log(`${sema.padEnd(5)} | ${s(r.yuvalar, 15)} | ${s(r.anahtar, 7)} | ${kib(r.toplam, 7)} KiB | ` +
    `${kib(r.enYuklu, 6)} K | ${s(r.dengesizlik.toFixed(3), 11)} | ${yuz(r.t1)} | ${yuz(r.t2)}`);
}

console.log("\n6 dugum, etiket = sube. Dugum basina yuk (sube paylari 34/24/16/12/9/5):");
const b = kosum({ sema: "sube", dugum: 6, d });
console.log("dugum   : " + b.yuk.map((_, i) => s("d" + i, 9)).join(""));
console.log("anahtar : " + b.sayi.map((x) => s(x, 9)).join(""));
console.log("KiB     : " + b.yuk.map((x) => s((x / 1024).toFixed(1), 9)).join(""));

console.log("\nkosumdan bagimsiz nicelikler:");
console.log("  K anahtarli islemin tek dugume dusme olasiligi = (1/n)^(K-1), etiket yokken");
console.log("  n       : " + [3, 4, 6, 8].map((n) => s(n, 8)).join(""));
console.log("  K=3     : " + [3, 4, 6, 8].map((n) => s((100 / n ** 2).toFixed(2) + "%", 8)).join(""));
console.log("  K=4     : " + [3, 4, 6, 8].map((n) => s((100 / n ** 3).toFixed(2) + "%", 8)).join(""));
console.log("  etiket = sube  -> kullanilabilir yuva sayisi = sube sayisi = 6");
console.log("  etiket = kitap -> kullanilabilir yuva sayisi = kitap sayisi = 3000");
console.log("  ornek yuva no  : sube:0 -> " + yuvaNo("{sube:0}katalog:7") +
  ", kitap:7 -> " + yuvaNo("{kitap:7}katalog:7") + ", etiketsiz katalog:7 -> " + yuvaNo("katalog:7"));
console.log("  6 dugumde bu yuvalarin dugumleri: " + [
  dugumu(yuvaNo("{sube:0}katalog:7"), 6), dugumu(yuvaNo("{kitap:7}katalog:7"), 6),
  dugumu(yuvaNo("katalog:7"), 6)].join(", "));

3.000 kitap, 6 sube, 12.000 odunc kaydi (tohum 20260731). Katalog girisi 240,
odunc 96, kuyruk 128, sube sayaci 64 bayt. 16384 yuva, dugume esit araliklarla.
T1 = katalog + odunc + kuyruk; T2 = T1 + sube sayaci. Etiket yok:

dugum | anahtar | toplam bayt | en yuklu dugum | dengesizlik | T1 tek dugumde | T2
------|---------|-------------|----------------|-------------|----------------|--------
    3 |   11758 |  1539.6 KiB |      553.0 KiB |       1.078 |         11.43% |   3.15%
    4 |   11758 |  1539.6 KiB |      408.4 KiB |       1.061 |          5.97% |   1.09%
    6 |   11758 |  1539.6 KiB |      284.4 KiB |       1.108 |          2.32% |   0.30%
    8 |   11758 |  1539.6 KiB |      210.6 KiB |       1.094 |          1.22% |   0.13%

6 dugum sabit; etiketleme semasi degisiyor:
sema  | kullanilan yuva | anahtar | toplam bayt | en yuklu | dengesizlik | T1     | T2
------|-----------------|---------|-------------|----------|-------------|--------|--------
yok   |            8709 |   11758 |  1539.6 KiB |  284.4 K |       1.108 |   2.32% |   0.30%
sube  |               6 |   18151 |  2899.0 KiB | 1452.5 K |       3.006 | 100.00% | 100.00%
kitap |            2813 |   11758 |  1539.6 KiB |  266.0 K |       1.036 | 100.00% |  16.83%

6 dugum, etiket = sube. Dugum basina yuk (sube paylari 34/24/16/12/9/5):
dugum   :        d0       d1       d2       d3       d4       d5
anahtar :         0        0        0     9052     9099        0
KiB     :       0.0      0.0      0.0   1446.6   1452.5      0.0

kosumdan bagimsiz nicelikler:
  K anahtarli islemin tek dugume dusme olasiligi = (1/n)^(K-1), etiket yokken
  n       :        3       4       6       8
  K=3     :   11.11%   6.25%   2.78%   1.56%
  K=4     :    3.70%   1.56%   0.46%   0.20%
  etiket = sube  -> kullanilabilir yuva sayisi = sube sayisi = 6
  etiket = kitap -> kullanilabilir yuva sayisi = kitap sayisi = 3000
  ornek yuva no  : sube:0 -> 11178, kitap:7 -> 8777, etiketsiz katalog:7 -> 15851
  6 dugumde bu yuvalarin dugumleri: 4, 3, 5

Küme Kısıtının Büyüklüğü

Bölmek dengelidir; kısıtlayan şey denge değildir. İlk tablonun dengesizlik sütunu dört düğüm sayısında da 1,06 ile 1,11 arasındadır: en yüklü düğüm ortalamanın yüzde on bir üstündedir. Karma dağıtımı işini yapıyor ve tutulan bayt gerçekten bölünüyor — üç düğümde en yüklü düğüm 553,0 KiB, sekiz düğümde 210,6 KiB tutuyor. Bu, çoğaltmanın yapamadığı şeydir.

Kaybedilen şey işlemdir. Aynı tablonun son iki sütunu bunu sayıyor: üç düğümlü kümede T1 işlemlerinin yüzde 11,43’ü, T2 işlemlerinin yüzde 3,15’i tek düğüme düşüyor. Sekiz düğümde oranlar yüzde 1,22 ve yüzde 0,13’e iniyor. Beklenen değer koşumdan bağımsız satırlarda: (1/n)^(K-1). Ölçülen sayılar bu beklentinin yakınındadır — ödünç kayıtları bağımsız değildir, aynı kitap–şube çifti birden çok kez geçer, bu yüzden sapma vardır — ama eğilim aynıdır: düğüm eklemek işlemin tek düğümde kalma şansını üstel olarak düşürür ve dokunulan anahtar sayısı üsttedir. T2, T1’e tek bir anahtar ekliyor ve oranı sekiz düğümde dokuz kat düşürüyor.

Bu, kümeye geçişin gerçek bedelidir. Şube sınırını denetleyen bir ödünç işlemi bin denemesinden birinde tek düğümde yürütülebiliyorsa, o işlem küme kurulumunda uygulama tarafından yürütülmek zorundadır ve atomikliği kalmaz.

Etiketin Taneliği

İkinci tablo kısıtı kaldırmanın üç yolunu karşılaştırıyor. Etiket, anahtarın yalnız belirli bir parçasının karmalanmasıdır; aynı etiketi taşıyan bütün anahtarlar aynı yuvaya, dolayısıyla aynı düğüme düşer.

Etiket şube olduğunda küme kısıtı tamamen kalkar ve bölümleme de kalkar. T1 ve T2 yüzde 100’e çıkıyor. Karşılığında kullanılan yuva sayısı 8.709’dan 6’ya iniyor: altı şube, altı yuva. Üçüncü blok sonucu açıkça gösteriyor — altı düğümün dördü tamamen boştur, bütün veri iki düğümde toplanmıştır ve dengesizlik 3,006’dır. Bellek sınırına çarpacak düğüm bellidir.

İkinci bir kalem daha var ve doğrudan bellek bütçesindendir: toplam tutulan bayt 1.539,6 KiB’den 2.899,0 KiB’ye çıkıyor, anahtar sayısı 11.758’den 18.151’e. Nedeni, katalog girişinin artık şube etiketiyle yazılmasıdır — aynı kitabın kaydı, o kitabın ödünç verildiği her şubede ayrıca durur. Etiketleme yalnız yeri değil, kopya sayısını da belirler.

Etiket kitap olduğunda ölçüler tersine döner. Kullanılan yuva 2.813’e çıkar, dengesizlik 1,036’ya iner — etiketsiz dağıtımdan bile daha dengelidir — ve toplam bayt hiç büyümez, çünkü katalog girişi çoğalmaz. T1 yüzde 100’dür: bir kitabın katalog girişi, ödünç kaydı ve bekleme kuyruğu her zaman aynı düğümdedir. T2 ise yüzde 16,83’te kalır, çünkü şubenin eşzamanlı ödünç sayacı kitap etiketini taşımaz ve altı düğümden birine rastgele düşer.

Buradan çıkan kural, etiketin kendisiyle değil işlemle ilgilidir: etiket bir işlemi tek düğüme sığdırmaz, işlemin kapsamını belirler. Şube sayacını da aynı düğüme çekmek için ya sayacı kitap etiketine bağlamak — ki o zaman şube başına tek bir sayaç kalmaz — ya da sınır denetimini işlemin dışına çıkarmak gerekir. Küme kurulumunda hangi işlemlerin atomik kalacağına anahtar adlandırması karar verir.

Özet

• Anahtar önce karmayla 16.384 yuvadan birine, yuva sonra düğüme eşlenir; iki anahtarın aynı düğüme düşmesi bir tasarım kararı değil, rastlantıdır.
• Etiketsiz bölümleme dengelidir (dengesizlik 1,06–1,11) ve tutulan baytı gerçekten böler: en yüklü düğüm üç düğümde 553,0 KiB, sekiz düğümde 210,6 KiB.
• Çok anahtarlı işlemin tek düğüme düşme oranı (1/n)^(K-1)‘e uyar: T1 için yüzde 11,43’ten yüzde 1,22’ye, T2 için yüzde 3,15’ten yüzde 0,13’e iner.
• Etiket şube olduğunda T1 ve T2 yüzde 100’e çıkar; bedeli kullanılan yuvanın 6’ya inmesi, altı düğümün dördünün boş kalması ve dengesizliğin 3,006 olmasıdır.
• Şube etiketi katalog girişini şube başına çoğalttığı için toplam tutulan bayt 1.539,6 KiB’den 2.899,0 KiB’ye, anahtar sayısı 11.758’den 18.151’e çıktı.
• Kitap etiketi dengeyi 1,036’ya çeker ve baytı hiç büyütmez ama yalnız T1’i yüzde 100 yapar; şube sayacını içeren T2 yüzde 16,83’te kalır — etiket, işlemin kapsamını belirler.

Sonraki Adım

Bu ders bir işlemin bütün anahtarlarının aynı düğümde toplanabildiğini gösterdi, ama toplandıktan sonra ne olacağını hiç sormadı. Bir ödünç işlemi şubenin eşzamanlı ödünç sayacını okur, sınırı aşıp aşmadığına bakar ve ancak öyle artırır; okuma ile artırma arasında geçen sürede başka bir şube görevlisi aynı sayacı değiştirmiş olabilir. Bellek içi depoda bu boşluğu kapatmanın yolu kilit almak değil, anahtarı izlemek ve değiştiyse işlemi düşürüp yeniden denemektir. Sonraki ders bu izleme tabanlı denetimi eşzamanlılık altında ölçer: çakışma oranı, işlem başına yeniden deneme sayısı, izlenen anahtarın tuttuğu üstveri ve işlem yürürken bütün istemcilerin bekletildiği turlar.