Dengeleme Algoritmaları

Buraya kadarki üç ders dağıtım kuralını sabit tuttu: kopyalar sırayla seçildi. Sıralı kural iki şeyi varsayar — kopyaların birbirinin eşi olduğunu ve her isteğin aynı işi yaptığını. İkisi de her zaman doğru değildir. Bir kopya yavaşlamış olabilir, bir istek ötekinden on kat pahalı olabilir ve bir isteğin hangi kopyaya düştüğü, o kopyanın önbelleğinin işine yarayacak biçimde kararlı tutulmak istenebilir.

Bu ders kuralın kendisini değiştirir. Üç kural ele alınır: sıralı (round robin), en az bağlantı (least connections) ve tutarlı karma (consistent hashing). İlk ikisi yükün nasıl paylaştırılacağını, üçüncüsü aynı anahtarın hep aynı kopyaya düşmesini hedefler.

Kuyruk Modeli

İlk iki kural bir süreç içi modelle karşılaştırılır. Model, isteklerin sabit aralıklarla geldiği ve her kopyanın tek sıralı bir sunucu olduğu bir kuyruktur. Tur soyut bir adımdır; varış aralığı, istek maliyeti ve kopya yavaşlığı model parametreleridir, ölçülmüş süreler değildir. Maliyetler sabit tohumlu bir üreteçten gelir, böylece iki kural aynı istek dizisiyle karşılaşır.

// alg/kuyruk.mjs — sirali ve en az baglanti kurallarinin ayni yuk altinda karsilastirilmasi.
// Bu bir MODELDIR: tur soyut bir adimdir, varis araligi, istek maliyeti ve kopya yavasligi
// model parametreleridir; olculmus sureler degildir.
const KOPYA = 3, ISTEK = 300, VARIS = 2;   // varis araligi (tur)
const TOHUM = 20240730;

function maliyetler(n) {                   // sabit tohumlu uretec: her kosumda ayni dizi
  let s = TOHUM;
  const d = [];
  for (let i = 0; i < n; i += 1) { s = (s * 1103515245 + 12345) % 2147483648; d.push(1 + (s >>> 8) % 10); }
  return d;
}

function kosum(kural, maliyet, carpan) {
  const k = Array.from({ length: KOPYA }, () => ({ bosalma: 0, is: 0, bitis: [], p: 0 }));
  let toplamBekleme = 0, enYuksekKuyruk = 0;
  for (let i = 0; i < maliyet.length; i += 1) {
    const t = i * VARIS;
    for (const c of k) while (c.p < c.bitis.length && c.bitis[c.p] <= t) c.p += 1;
    const acik = k.map((c) => c.bitis.length - c.p);
    enYuksekKuyruk = Math.max(enYuksekKuyruk, ...acik);
    const hedef = kural === "sirali" ? i % KOPYA : acik.indexOf(Math.min(...acik));
    const c = k[hedef];
    const bas = Math.max(t, c.bosalma);
    toplamBekleme += bas - t;
    c.bosalma = bas + maliyet[i] * carpan[hedef];
    c.is += maliyet[i] * carpan[hedef];
    c.bitis.push(c.bosalma);
  }
  return { bekleme: toplamBekleme / maliyet.length, enYuksekKuyruk,
    is: k.map((c) => c.is), bitis: Math.max(...k.map((c) => c.bosalma)) };
}

const maliyet = maliyetler(ISTEK);
const toplamIs = maliyet.reduce((a, b) => a + b, 0);
console.log(`${ISTEK} istek, ${KOPYA} kopya, varis araligi ${VARIS} tur, toplam is ${toplamIs} tur`);
console.log(`esit kopyalarda model dolulugu = ${((toplamIs / (ISTEK * VARIS)) / KOPYA).toFixed(3)}\n`);

for (const [ad, carpan] of [["esit kopyalar", [1, 1, 1]], ["k1 uc kat yavas", [3, 1, 1]]]) {
  console.log(`durum: ${ad}`);
  console.log("  kural            ortalama bekleme  en yuksek kuyruk  bitis turu  kopya basina is");
  for (const kural of ["sirali", "en-az-baglanti"]) {
    const r = kosum(kural, maliyet, carpan);
    console.log(`  ${kural.padEnd(16)} ${r.bekleme.toFixed(2).padStart(16)} ` +
      `${String(r.enYuksekKuyruk).padStart(17)} ${String(r.bitis).padStart(11)}  ${r.is.join("/").padStart(15)}`);
  }
  console.log();
}

300 istek, 3 kopya, varis araligi 2 tur, toplam is 1679 tur
esit kopyalarda model dolulugu = 0.933

durum: esit kopyalar
  kural            ortalama bekleme  en yuksek kuyruk  bitis turu  kopya basina is
  sirali                       4.04                 4         614      545/581/553
  en-az-baglanti               1.90                 2         610      589/567/523

durum: k1 uc kat yavas
  kural            ortalama bekleme  en yuksek kuyruk  bitis turu  kopya basina is
  sirali                     170.97                63        1635     1635/581/553
  en-az-baglanti              56.99                18         843      843/697/701

Eşit kopyalar durumunda iki kural aynı toplam işi yapıyor ve bitiş turları neredeyse aynı: 614’e karşı 610. Fark beklemede: ortalama bekleme 4,04 turdan 1,90 tura, en yüksek kuyruk 4’ten 2’ye iniyor. Sıralı kural bir isteği meşgul bir kopyaya gönderirken bir başkası boş durabiliyor, çünkü sırasını sayarken kopyaların durumuna bakmıyor.

Kopya başına iş sütunu bir ters sonuç taşıyor: en az bağlantı kuralının iş dağılımı daha dengesizdir (589/567/523’e karşı 545/581/553). Kural işi eşitlemeye çalışmıyor, bekleyen istek sayısını eşitliyor; pahalı istekler nereye düşerse toplam iş orada birikir. En az bağlantı bir adalet kuralı değil, bir bekleme kuralıdır.

İkinci durum farkı büyütüyor. Bir kopya üç kat yavaşladığında sıralı kural yine isteklerin üçte birini ona göndermeye devam ediyor: ortalama bekleme 170,97 tura, en yüksek kuyruk 63’e ve bitiş 1635. tura çıkıyor. En az bağlantı kuralında aynı yavaşlamada bekleme 56,99, kuyruk 18, bitiş 843 oluyor — üçü de yaklaşık üç kat düşük. Kural yavaş kopyanın kuyruğunun uzadığını gördüğü için oraya daha az istek gönderiyor. Sağlık denetiminin yakalamadığı arıza biçimi budur: kopya yanıt veriyor, yalnız yavaş yanıt veriyor, dolayısıyla havuzdan düşürülmüyor.

Aynı Anahtar Hep Aynı Kopyaya

Üçüncü kural başka bir soruyu yanıtlıyor. Kopyaların her birinde yerel bir önbellek varsa, aynı takip numarasının hep aynı kopyaya düşmesi o önbelleğin işine yarar; numara her seferinde başka bir kopyaya düşerse aynı kayıt kopya sayısı kadar yerde tutulur. Anahtardan kopyaya bir eşleme gerekir ve en yalın biçimi anahtarın karmasının kopya sayısına bölümünden kalandır.

Karma fonksiyonu Karma Tabloları dersinde kuruldu ve burada yeniden anlatılmaz; aşağıda yalnız bir araç olarak kullanılıyor. Ölçülen şey düğüm sayısı değiştiğinde kaç anahtarın yer değiştirdiğidir. Sayılar belirlenimlidir ve makineden bağımsızdır, bu yüzden ölçüm değil hesap sınıfındadır.

// alg/karma.mjs — bolme kalani ile tutarli karmanin karsilastirilmasi: dugum degistiginde yer
// degistiren anahtar orani, sanal dugum sayisina gore dagilim ve K01 onbellek hesabina etkisi
const ANAHTAR = 100_000;           // takip numarasi sayisi
const OKUMA = 416.67;              // K01 Kabaca Buyukluk Hesabi: tepe okuma istek/s
const YAZMA = 97.22;               // K01: tepe yazma istek/s
const ISABET = 0.90;               // K01 varsayim V9: onbellekten karsilanma orani
const TABAN_DEPO = 138.89;         // K01: depoya ulasan istek/s
const ISINMA_SN = 60;              // varsayim Y5: onbellek isinma penceresi

function karma(metin) {            // FNV-1a + son karistirma adimi; cig etkisi Karma Tablolari
  let h = 2166136261;               // dersinde tanimlandi: benzer anahtarlar uzak degerler vermeli
  for (let i = 0; i < metin.length; i += 1) h = Math.imul(h ^ metin.charCodeAt(i), 16777619) >>> 0;
  h ^= h >>> 15; h = Math.imul(h, 2246822507) >>> 0; h ^= h >>> 13;
  return h >>> 0;
}

const anahtarlar = Array.from({ length: ANAHTAR }, (_, i) => `G${1_000_000 + i}`);

const kalanla = (a, kopya) => kopya[karma(a) % kopya.length];

function halka(kopya, sanal) {     // her kopya icin sanal dugum konumlari, konuma gore sirali
  const h = [];
  for (const k of kopya) for (let v = 0; v < sanal; v += 1) h.push([karma(`${k}#${v}`), k]);
  return h.sort((x, y) => x[0] - y[0]);
}
function halkada(a, h) {           // anahtarin karmasindan sonraki ilk konum, yoksa basa doner
  const c = karma(a);
  let alt = 0, ust = h.length - 1;
  if (c > h[ust][0]) return h[0][1];
  while (alt < ust) { const o = (alt + ust) >> 1; if (h[o][0] < c) alt = o + 1; else ust = o; }
  return h[alt][1];
}

const dengesizlik = (yerlesim, kopya) => {
  const s = new Map(kopya.map((k) => [k, 0]));
  for (const k of yerlesim) s.set(k, s.get(k) + 1);
  return (Math.max(...s.values()) / anahtarlar.length) * kopya.length;
};
const oynayan = (a, b) => a.filter((k, i) => k !== b[i]).length / a.length;

const UC = ["k1", "k2", "k3"], DORT = [...UC, "k4"];
const sonuc = {};

console.log("kural                  3 kopya dengesizlik  4 kopya dengesizlik  3->4 oynayan  4->3 oynayan");
{
  const u = anahtarlar.map((a) => kalanla(a, UC));
  const d = anahtarlar.map((a) => kalanla(a, DORT));
  sonuc["bolme kalani"] = oynayan(u, d);
  console.log(`${"bolme kalani".padEnd(22)} ${dengesizlik(u, UC).toFixed(3).padStart(19)} ` +
    `${dengesizlik(d, DORT).toFixed(3).padStart(20)} ${oynayan(u, d).toFixed(4).padStart(13)} ` +
    `${oynayan(d, u).toFixed(4).padStart(13)}`);
}
for (const sanal of [1, 10, 100, 1000]) {
  const hu = halka(UC, sanal), hd = halka(DORT, sanal);
  const u = anahtarlar.map((a) => halkada(a, hu));
  const d = anahtarlar.map((a) => halkada(a, hd));
  if (sanal === 1000) sonuc["tutarli karma"] = oynayan(u, d);
  console.log(`${`tutarli karma (v=${sanal})`.padEnd(22)} ${dengesizlik(u, UC).toFixed(3).padStart(19)} ` +
    `${dengesizlik(d, DORT).toFixed(3).padStart(20)} ${oynayan(u, d).toFixed(4).padStart(13)} ` +
    `${oynayan(d, u).toFixed(4).padStart(13)}`);
}

console.log(`\nkusursuz dagilimda dengesizlik 1.000, kusursuz tasimada 3->4 oran = ${(1 / 4).toFixed(4)}\n`);
console.log("kural            oynayan   isinmada isabetsizlik   onbellek arkasi okuma/s   depoya ulasan/s   taban kati   fazladan depo istegi");
for (const [ad, oran] of Object.entries(sonuc)) {
  const isabetsiz = oran + (1 - oran) * (1 - ISABET);
  const arka = OKUMA * isabetsiz, depo = arka + YAZMA;
  console.log(`${ad.padEnd(15)} ${oran.toFixed(4).padStart(8)} ${isabetsiz.toFixed(4).padStart(23)} ` +
    `${arka.toFixed(2).padStart(25)} ${depo.toFixed(2).padStart(17)} ` +
    `${(depo / TABAN_DEPO).toFixed(2).padStart(12)} ${((depo - TABAN_DEPO) * ISINMA_SN).toFixed(0).padStart(22)}`);
}
console.log(`taban (isinma yok): onbellek arkasi ${(OKUMA * (1 - ISABET)).toFixed(2)} istek/s, ` +
  `depoya ulasan ${TABAN_DEPO} istek/s`);

kural                  3 kopya dengesizlik  4 kopya dengesizlik  3->4 oynayan  4->3 oynayan
bolme kalani                         1.008                1.004        0.7485        0.7485
tutarli karma (v=1)                  2.021                2.231        0.5577        0.5577
tutarli karma (v=10)                 1.548                1.722        0.1557        0.1557
tutarli karma (v=100)                1.122                1.204        0.2563        0.2563
tutarli karma (v=1000)               1.010                1.059        0.2648        0.2648

kusursuz dagilimda dengesizlik 1.000, kusursuz tasimada 3->4 oran = 0.2500

kural            oynayan   isinmada isabetsizlik   onbellek arkasi okuma/s   depoya ulasan/s   taban kati   fazladan depo istegi
bolme kalani      0.7485                  0.7736                    322.35            419.57         3.02                  16841
tutarli karma     0.2648                  0.3383                    140.96            238.18         1.71                   5957
taban (isinma yok): onbellek arkasi 41.67 istek/s, depoya ulasan 138.89 istek/s

İki Ölçüt Aynı Yönde İyileşmiyor

Birinci tablo iki ayrı ölçüt taşıyor ve kurallar ikisinde ters sıralanıyor.

Dağılım. Bölme kalanı anahtarları neredeyse kusursuz paylaştırıyor: dengesizlik 1,008 ve 1,004. Tutarlı karmanın tek sanal düğümle dağılımı çok kötüdür — üç kopyada 2,021, dört kopyada 2,231, yani bir kopya kusursuz payın iki katından fazlasını taşıyor. Halkadaki konumlar rastgele düştüğü için aralar eşit uzunlukta olmuyor. Sanal düğüm sayısı arttıkça ara sayısı artıyor ve dağılım düzeliyor: 100’de 1,122 ve 1,204, 1000’de 1,010 ve 1,059. Sanal düğüm sayısı tutarlı karmanın dağılım ayarıdır ve bedeli halkanın boyudur: dört kopya ve 1000 sanal düğüm 4000 konum demektir.

Taşıma. Sıralama tersine dönüyor. Üç kopyadan dörde geçildiğinde bölme kalanı anahtarların yüzde 74,85’ini oynatıyor; taşınması gereken oran 0,2500’dür, yani yeni kopyanın payı. Bölme kalanı gerekenin üç katını oynatıyor, çünkü bölen değiştiğinde bütün kalanlar değişir. Tutarlı karma 1000 sanal düğümle 0,2648 oynatıyor ve bu sayı kuramsal 0,2500’e yakındır; az sanal düğümle sapma iki yönde birden büyür (v=1’de dengesizlik 2,021, oynayan 0,5577). Düğüm çıkarma sütunu aynı sayıyı veriyor, çünkü sayılan şey iki yerleşim arasında farklı olan anahtarlardır ve fark iki yönde aynıdır.

İki tablonun birlikte söylediği şudur: bölme kalanı dağılımda iyi, kararlılıkta kötüdür; tutarlı karma kararlılıkta iyidir ve dağılımı sanal düğüm sayısıyla satın alır.

Hesaba Geri Dönüş

Yer değiştiren anahtar oranı tek başına bir tasarım sonucu değildir; sonuç önbellekle birleştiğinde çıkar. K01’in V9 varsayımı takip sorgusunun yüzde 90’ının önbellekten karşılandığını söylüyordu ve o oran depoya ulaşan istek hızını 138,89 istek/s’de tutuyordu. Anahtarına göre yönlendirilen bir kopya kümesinde yer değiştiren anahtarın önbelleği yeni kopyada yoktur; o anahtarların isabet oranı, önbellek yeniden ısınana kadar sıfırdır.

Bunun için bir varsayım daha gerekir. Y5 — önbellek ısınma penceresi: 60 saniye. Gerekçe: taşınan anahtarların yeniden sorulup önbelleğe girmesi için gereken süre; sayı bu konunun kendi varsayımıdır ve K01’in tablosuna eklenmez. Duyarlılığı doğrusaldır — pencere iki katına çıkarsa fazladan depo isteği de iki katına çıkar.

Son tablo ısınma penceresindeki durumu hesap olarak veriyor. Bölme kalanıyla bir kopya eklendiğinde isabetsizlik 0,7736’ya çıkıyor: taşınan yüzde 74,85 hiç isabet etmiyor, kalan yüzde 25,15 ise normal yüzde 10 isabetsizliğiyle geliyor. Önbelleğin arkasındaki okuma 41,67 istek/s’den 322,35 istek/s’ye, depoya ulaşan istek hızı 138,89’dan 419,57’ye çıkıyor — taban değerin 3,02 katı. Altmış saniyelik pencerede depoya fazladan 16 841 istek gidiyor.

Tutarlı karmayla aynı olay isabetsizliği 0,3383’te tutuyor: önbellek arkası okuma 140,96, depoya ulaşan 238,18 istek/s, tabanın 1,71 katı ve pencerede fazladan 5957 istek. İki kural arasındaki fark 10 884 istektir ve bu farkın tamamı bir kopya eklemenin faturasıdır.

Sonucun tasarım karşılığı doğrudandır. Yatay ölçekleme kopya eklemekle olur; kopya eklemek önbelleği bozar; önbelleği bozmak depoya ulaşan yükü kat kat artırır. Yani bir sistemin büyütülebilirliği yalnız kopya sayısına değil, kopya eklendiğinde ne kadar şeyin yer değiştirdiğine de bağlıdır. Bölme kalanı seçilmiş bir tasarımda büyüme anı, sistemin en kırılgan anıdır: yük artışına yanıt olarak eklenen kopya, depoya üç kat yük bindirir.

Özet

• Sıralı kural kopyaların durumuna bakmaz; eşit kopyalarda ortalama bekleme 4,04 tur ve en yüksek kuyruk 4 iken en az bağlantı kuralında 1,90 tur ve 2 oldu.
• En az bağlantı bir bekleme kuralıdır, adalet kuralı değil: beklemeyi yarıya indirirken kopya başına iş dağılımını biraz daha dengesiz yaptı (589/567/523’e karşı 545/581/553).
• Bir kopya üç kat yavaşladığında sıralı kuralda bekleme 170,97 tura ve kuyruk 63’e çıkıyor; en az bağlantıda 56,99 ve 18. Yavaşlama, sağlık denetiminin yakalamadığı arıza biçimidir.
• Bölme kalanı dağılımda neredeyse kusursuz (dengesizlik 1,008) ama kararsız: üç kopyadan dörde geçişte anahtarların yüzde 74,85’i yer değiştiriyor, gereken oran 0,2500.
• Tutarlı karma 1000 sanal düğümle 0,2648 oynatıyor ve dengesizliği 1,010’a iniyor; sanal düğüm sayısı dağılım ayarıdır, tek düğümde dengesizlik 2,021’e çıkar.
• Bir kopya eklendiğinde ısınma penceresinde depoya ulaşan istek hızı bölme kalanıyla 138,89’dan 419,57’ye (3,02 kat), tutarlı karmayla 238,18’e (1,71 kat) çıkıyor; 60 saniyelik pencerede aradaki fark 10 884 istektir.

Sonraki Adım

Bu üç kural da isteği bir kopyaya bağlarken tek bir şeye bakıyordu: sıraya, kuyruk uzunluğuna ya da anahtara. Kararın kendisi hep aynı bileşende, dengeleyicide veriliyordu. Oysa aynı işi yapan başka bir bileşen daha var ve önceki kurslarda kurulmuştu: isteği bir kurala göre arka sunuculardan birine ileten ters vekil. İki bileşenin yaptığı iş büyük ölçüde örtüşüyor; bir süreç ikisini birden üstlenebilir. Sonraki ders bu örtüşmeyi ele alır: iki rolün aynı süreçte toplanmasıyla ayrı süreçlere bölünmesini durak sayısı ve bileşik hizmet erişilebilirliği cinsinden karşılaştırır ve ayrımın nerede olduğunu sorumluluk ile konum üzerinden söyler.