--- title: 'Dengeleme Algoritmaları' source: 'https://academia.sh/tr/kurslar/trafik-katmani/dengeleme-algoritmalari' course: 'Trafik Katmanı' language: tr updated: '2026-08-17T18:11:03+00:00' license: 'CC BY-SA 4.0' --- # Dengeleme Algoritmaları Dağıtım kuralının kendisinin değiştirilmesi: sıralı ile en az bağlantı kuralının eşit ve yavaşlamış kopyalarda bekleme ve kuyruk cinsinden karşılaştırılması, bölme kalanı ile tutarlı karmanın düğüm değiştiğinde yer değiştiren anahtar oranının sayılması, sanal düğüm sayısının dağılıma etkisi ve yer değiştirmenin önbellek isabet oranı üzerinden giriş kursu hesabına dönmesi. 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. ```js // 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. ```js // 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.