--- title: 'Yük Dengeleme Algoritmaları' source: 'https://academia.sh/tr/kurslar/ag-isletimi/yuk-dengeleme-algoritmalari' course: 'Ağ İşletimi ve Otomasyon' language: tr updated: '2026-08-17T18:07:16+00:00' license: 'CC BY-SA 4.0' --- # Yük Dengeleme Algoritmaları Dört dağıtım kuralı aynı kırk öznede iki ayrı yükte koşturulur; yük 1200'de aşan özne 6 / 0 / 0, yük 2600'de 23 / 40 / 40 ve aşan birim 533 / 245 / 264 çıkar, 1200'de 1160 birim boşta durur ve oransal kuralın aşım sütununu temiz gösteren şey dağıtmadığı 19 birimdir. Önceki ders kuralı sabit tuttu ve yalnız dağıtımın birimini değiştirdi: bağlantı yerine istek. Kırk öznelik kümede kazanç tek bir özneydi. Öyleyse asıl soru birimde değil **kuralın kendisindedir**. Yükü kapasiteye göre bölen ya da her adımda en az yüklü özneyi seçen bir kural, kuyruğu gerçekten kaldırır mı? Bu dersin ölçtüğü şey budur, ve yanıtı tek bir tabloda iki ayrı yükle verilir. Kuralın "iyi" olması bir yükte doğru, başka bir yükte yanıltıcı çıkar. ## Dört Kural Dağıtım kuralı, gelen bir işi kırk özneden birine bağlayan işlevdir. Dört kural ölçülür ve dördü de birbirinden **neyi okuduğuyla** ayrılır. **Sıralı (round robin)** hiçbir şey okumaz. Özneleri sırayla dolaşır ve her işi bir sonrakine verir. Durum tutmaz, kapasiteyi bilmez, anlık yükü bilmez. **Kapasiteye göre** dağıtım her özneye kapasitesiyle orantılı bir pay ayırır. Kapasiteyi okur ama anlık yükü okumaz: payları baştan hesaplar ve öyle dağıtır. **En az bağlantı (least connections)** her adımda o an en az yüklü özneyi seçer. Burada ölçülen biçimi ağırlıklıdır: karşılaştırma ham bağlantı sayısına değil, **bağlantı sayısının kapasiteye oranına** bakar. Hem kapasiteyi hem anlık yükü okur ve bu yüzden dört kuralın en pahalısıdır — her karar için kırk öznenin durumunu görmesi gerekir. **Tutarlı karma (consistent hashing)** işin bir anahtarını — oturum kimliği, istemci adresi — bir halka üzerine düşürür ve halkada saat yönünde ilk özneye verir. Kapasiteyi de anlık yükü de okumaz; okuduğu tek şey anahtardır. Aynı anahtar her zaman aynı özneye gider. Bu kuralların karşılaştırması Sistem Tasarımı müfredatının Trafik Katmanı kursunda yapıldı ve algoritma listesi burada tekrarlanmıyor. Fark tek cümledir: **orada kuralların tasarım ölçütleri karşılaştırıldı, burada tek bir kuralın kapasitesi eşit olmayan kırk öznede bıraktığı kuyruk sayılır.** Kural bir yapılandırma satırıdır ve dördü de aynı yere yazılır: ```text # öğretilen kural sözdizimi, çalıştırılmamıştır havuz ana { kural sirali } havuz ana { kural kapasiteye-gore agirlik ozne-01 22 agirlik ozne-09 99 } havuz ana { kural en-az-baglanti olcut acik-baglanti / agirlik } havuz ana { kural tutarli-karma anahtar oturum-kimligi sanal 128 } ``` ## İki Yük, Tek Küme Kırk öznenin toplam kapasitesi **2336** birimdir. Ölçüm bu sayının iki yanında yapılır. **Yük 1200** toplam kapasitenin yarısından biraz fazladır. Burada sistemde bol yer vardır ve aşım tamamen dağıtımın kusurudur: doğru bölünseydi hiçbir özne aşmazdı. **Yük 2600** toplam kapasitenin üstündedir. Burada aşım kaçınılmazdır ve hiçbir kural onu sıfırlayamaz. Sorulabilecek tek soru, aşımın **kime** ve **ne kadar** düşeceğidir. Arada bir de **yük 2000** ölçülür; kapasitenin altındadır ama sıkışıklık başlamıştır. Ölçümün varsayımları: - **TY7** — Kırk özne kursun sabit kümesidir ve bu derste değiştirilmez; kapasiteler **22** ile **99** arasındadır ve kâhin kümenin kendisidir. - **TY8** — Yük bölünebilir birimlerden oluşur; bir birim bir öznede bir birim kapasite tüketir. Yükün sınıfı ya da gecikmesi bu derste dağıtıma girmez. - **TY9** — Dört kural da **aynı yük ve aynı küme** üzerinde koşturulur. Kurallar arasındaki tek fark okudukları alandır. - **TY10** — Kapasiteye göre dağıtım payları tam sayıya **aşağı yuvarlar**; artan birimler yeniden dağıtılmaz. Bu, kuralın kendi tanımının parçasıdır ve ölçümde ayrı bir sütun olarak sayılır. - **TY11** — En az bağlantı kuralı eşitlik durumunda küçük numaralı özneyi seçer; seçim belirlenimcidir ve koşum yinelendiğinde aynı sonucu verir. - **TY12** — Tutarlı karma her özneyi halka üzerinde **128** sanal nokta ile temsil eder ve anahtar olarak işin sıra numarasını kullanır. Karma işlevi belirlenimcidir. - **TY13** — Ölçüm bir ağ ölçümü değildir; hiçbir bağlantı açılmaz, hiçbir istek gönderilmez. Sayılan şey kurgudaki dağıtımın kendisidir. ## Ölçüm ```python """Dort dagitim kurali ayni kirk oznede: kuyruk kalkmiyor, yer degistiriyor.""" import bisect TOHUM = 20260812 SINIFLAR = ("etkilesim", "toplu", "yedek") HALKA = 1 << 20 def uretec(tohum): d = tohum % 2147483646 + 1 def r(n): nonlocal d d = (d * 48271) % 2147483647 return d % n return r def ozneler(sayi=40, tohum=TOHUM): r, liste = uretec(tohum), [] for i in range(sayi): liste.append({"no": i + 1, "kapasite": 20 + r(81), "gecikme": 5 + r(45), "sinif": SINIFLAR[r(3)], "ozel": r(9) == 0}) return liste def karma(x): x = (x * 2654435761) & 0xFFFFFFFF x ^= x >> 16 x = (x * 2246822507) & 0xFFFFFFFF x ^= x >> 13 return x % HALKA def dagit(yuk, oz, kural, sanal=128): """Tek bir kural kirk ozneye yuk dagitir; anahtar -> ozne eslemesi de doner.""" pay, esle = {o["no"]: 0 for o in oz}, {} if kural == "sirali": for i in range(yuk): esle[i + 1] = oz[i % len(oz)]["no"] pay[esle[i + 1]] += 1 elif kural == "kapasiteye gore": toplam = sum(o["kapasite"] for o in oz) for o in oz: pay[o["no"]] = yuk * o["kapasite"] // toplam elif kural == "en az baglanti": for i in range(yuk): en = min(oz, key=lambda o: (pay[o["no"]] / o["kapasite"], o["no"])) esle[i + 1] = en["no"] pay[en["no"]] += 1 elif kural == "tutarli karma": h = sorted((karma(o["no"] * 7919 + k), o["no"]) for o in oz for k in range(sanal)) nok = [p for p, _ in h] for a in range(1, yuk + 1): esle[a] = h[bisect.bisect_left(nok, karma(a)) % len(h)][1] pay[esle[a]] += 1 return pay, esle def asan(pay, oz): """Kapasitesini asan ozne sayisi ve asan birim toplami.""" sayi = birim = 0 for o in oz: fazla = pay[o["no"]] - o["kapasite"] if fazla > 0: sayi, birim = sayi + 1, birim + fazla return sayi, birim KURALLAR = ("sirali", "kapasiteye gore", "en az baglanti", "tutarli karma") oz = ozneler() print(f"özne {len(oz)} | toplam kapasite {sum(o['kapasite'] for o in oz)} | " f"en küçük {min(o['kapasite'] for o in oz)} en büyük {max(o['kapasite'] for o in oz)}") print() print(f"{'kural':<16s} {'yük':>5s} {'aşan özne':>10s} {'aşan birim':>11s} " f"{'boşta kalan':>12s} {'dağıtılmayan':>13s} {'hiç yük almayan':>16s}") for kural in KURALLAR: for yuk in (1200, 2000, 2600): pay, _ = dagit(yuk, oz, kural) s, b = asan(pay, oz) print(f"{kural:<16s} {yuk:5d} {s:10d} {b:11d} " f"{sum(max(0, o['kapasite'] - pay[o['no']]) for o in oz):12d} " f"{yuk - sum(pay.values()):13d} " f"{sum(1 for o in oz if pay[o['no']] == 0):16d}") kalan = [o for o in oz if o["no"] != 20] print() print(f"{'kural':<16s} {'20 no.lu öznenin payı':>22s} {'çıkarılınca taşınan':>20s}") for kural in ("sirali", "en az baglanti", "tutarli karma"): pay, once = dagit(1200, oz, kural) _, sonra = dagit(1200, kalan, kural) print(f"{kural:<16s} {pay[20]:22d} " f"{sum(1 for a in once if once[a] != sonra[a]):20d}") ``` ``` özne 40 | toplam kapasite 2336 | en küçük 22 en büyük 99 kural yük aşan özne aşan birim boşta kalan dağıtılmayan hiç yük almayan sirali 1200 6 24 1160 0 0 sirali 2000 14 239 575 0 0 sirali 2600 23 533 269 0 0 kapasiteye gore 1200 0 0 1156 20 0 kapasiteye gore 2000 0 0 357 21 0 kapasiteye gore 2600 40 245 0 19 0 en az baglanti 1200 0 0 1136 0 0 en az baglanti 2000 0 0 336 0 0 en az baglanti 2600 40 264 0 0 0 tutarli karma 1200 7 66 1202 0 0 tutarli karma 2000 13 277 613 0 0 tutarli karma 2600 22 559 295 0 0 kural 20 no.lu öznenin payı çıkarılınca taşınan sirali 30 1181 en az baglanti 15 1181 tutarli karma 29 29 ``` ## İyi Kural Kuyruğu Kaldırmadı Yük 1200 satırları kuralı iyileştirmenin işe yaradığını söylüyor. Sıralı dağıtım **6** özneyi aşırıyor; kapasiteye göre dağıtım ve en az bağlantı **hiçbirini**. Aşan birim **24**'ten **0**'a iniyor. Buraya kadar bakan bir okuma, doğru kuralın kuyruğu kaldırdığı sonucuna varırdı. Yük 2600 satırları bunu tersine çeviriyor. Sıralı dağıtım **23** özneyi aşırıyor; kapasiteye göre dağıtım ve en az bağlantı **kırk öznenin kırkını birden**. İyi olduğu söylenen iki kural, aşan özne sayısını sıfırdan kırka çıkardı. Aşan birim sütunu tam ters yönde okunuyor: sıralı **533**, kapasiteye göre **245**, en az bağlantı **264**. Yani sıralı kural az sayıda özneyi çok, ötekiler bütün özneleri az aşırıyor. **Kuyruk kalkmadı; acı herkese yayıldı.** Bu iki okumadan hangisinin doğru olduğu ölçünün kararı değildir. Yirmi üç öznenin ağır aşımı ile kırk öznenin hafif aşımı arasındaki seçim bir **politika** kararıdır: kırk özne biraz yavaşlasın mı, yoksa on yedisi hiç etkilenmesin ve yirmi üçü ağır etkilensin mi? Ölçüm bu soruyu yanıtlamaz, yalnız iki seçeneğin sayısını yan yana koyar. Yükün toplam kapasitenin üstünde olduğu yerde bir alt sınır da vardır. Toplam kapasite **2336**, yük **2600**; aradaki fark **264** birimdir ve yükün tamamını yerleştiren hiçbir kural bunun altına inemez. En az bağlantı kuralının aşan birimi tam olarak **264**'tür — yani bu kural, yerleştirilebilecek en iyi dağıtımı bulmuştur. Daha iyisi yoktur. ## Aşım Sütununun Görmediği O zaman kapasiteye göre dağıtımın **245**'i nedir? Alt sınırın altında bir sayı, ancak yükün tamamı yerleştirilmediğinde çıkabilir. Sağdaki **dağıtılmayan** sütunu bunu söylüyor. Oransal kural her özneye düşen payı tam sayıya aşağı yuvarlıyor ve artan birimleri kimseye vermiyor: yük 2600'de **19** birim, 2000'de **21**, 1200'de **20** birim hiçbir özneye ulaşmıyor. Bu birimler aşım sütununda da görünmüyor, boşta kalan sütununda da — çünkü hiç dağıtılmadılar. Sonuç şudur: kapasiteye göre dağıtımın aşım sütununu en iyi gösteren şey, kuralın **yapmadığı iştir**. Ölçüm iki kuralı yan yana koyarken bu sütun olmasaydı, **245 < 264** karşılaştırması yanlış bir sonuca götürürdü. **Dağıtılmayan birim de bir kuyruktur ve kaldıracın aşım göstergesinde hiç görünmez.** Aynı sütunun bir okuması daha var. Yük 1200'de sıralı dağıtım **6** özneyi aşırırken sistemde **1160** birim boşta duruyor — toplam kapasitenin yarısı. Aşım ile boşluk aynı anda vardır. **Yalnız aşımı sayan bir gösterge, kapasitenin yarısının kullanılmadığını göremez**, ve yalnız kullanımı sayan bir gösterge altı öznenin aştığını göremez. İki sütun ayrı ayrı okunmak zorundadır. ## En Az Bağlantının Göremediği En az bağlantı kuralı ölçümün en iyi sonucunu verdi, ama bu sonuç iki koşula bağlıdır ve ikisi de ölçümün dışındadır. Birincisi maliyettir. Sıralı kural bir sayaç artırır, tutarlı karma bir karma hesaplar; en az bağlantı her karar için kırk öznenin anlık durumunu karşılaştırır ve bunu gelen her iş için yineler. Kararın kendisi bir işe dönüşür. İkincisi ve daha ağır olanı şudur: **"en az" hangi kümede en az?** Ölçümdeki kural kırk öznenin tamamını ve o ana kadar dağıtılmış her birimi görüyor. İşletmede dengeleyici çoğu zaman tek değildir; aynı havuzun önünde birden çok dengeleyici durur ve her biri yalnız **kendi** açtığı bağlantıları sayabilir. Her dengeleyici kendi görüşüne göre en az yüklü özneyi seçer, hepsi aynı anda aynı özneyi seçer ve o özne, kimsenin göstergesinde görünmeden aşar. Bu, önceki dersin düz göstergesinin başka bir biçimidir. Orada kaldıraç **yanlış boyutu** ölçüyordu; burada doğru boyutu **eksik kümede** ölçüyor. Tablodaki **264** birimlik en iyi sonuç, kuralın kırk öznenin tamamını gördüğü varsayımına dayanır — `TY9`. Varsayım düştüğünde sonuç da düşer, ve düştüğünü söyleyen bir sütun tabloda yoktur. ## Tutarlı Karmanın Ödediği Yer Tutarlı karma satırları dağıtım açısından iyi değil: yük 1200'de **7** özne aşıyor, sıralıdan bir fazla; 2600'de aşan birim **559**, sıralının **533**'ünün üstünde. Beklenen bir sonuç, çünkü bu kural da kapasiteyi okumuyor ve üstüne karma dağılımının kendi değişkenliğini ekliyor. Kuralın ödediği yer alt tablodadır. Havuzdan tek bir özne çıkarıldığında sıralı kuralda **1181** anahtar, en az bağlantı kuralında yine **1181** anahtar yer değiştiriyor — bin iki yüzün neredeyse tamamı. Tutarlı karmada yer değiştiren anahtar sayısı **29**, ve bu tam olarak çıkarılan öznenin kendi payıdır. Kalan otuz dokuz öznenin anahtarları yerinde kalır. Fark neden önemli? Çünkü bir anahtarın taşınması yalnız bir isteğin başka bir özneye gitmesi demek değildir. Anahtara bağlı olarak o öznede biriktirilmiş ne varsa — oturum durumu, ısıtılmış bir önbellek — yeni öznede yoktur. Sıralı kuralda bir öznenin havuzdan çıkması kırk öznenin kırkında bu birikimi geçersiz kılar. **Tutarlı karma dağıtımı iyileştirmez; üyelik değiştiğinde kuyruğun boyunu sınırlar.** Bir özneyi havuzdan çıkarmak da bir kaldıraç hareketidir — hem de bu kursun en sık çekilenlerinden biri, çünkü bakım, arıza ve sürüm değişimi hep buradan geçer. Kuralın seçimi, o hareketin kırk özneden kaçını rahatsız edeceğini baştan belirler. ## Özet - Yük 1200'de sıralı dağıtım **6** özneyi **24** birimle aşırır, kapasiteye göre dağıtım ve en az bağlantı **hiçbirini**; kuralı iyileştirmek burada gerçekten kazandırır. - Yük 2600'de aynı iki kural **kırk öznenin kırkını** aşırır, sıralı yalnız **23**'ünü; aşan birim sırasıyla **533**, **245** ve **264**'tür. Kuyruk kalkmadı, acı herkese yayıldı ve hangisinin doğru olduğu bir politika kararıdır. - Toplam kapasite **2336**, yük **2600** olduğunda aşımın alt sınırı **264** birimdir; en az bağlantı kuralı tam bu sayıyı bulur ve daha iyisi yoktur. - Kapasiteye göre dağıtımın **245**'i alt sınırın altındadır çünkü kural payları aşağı yuvarlar ve **19** birimi hiç dağıtmaz; dağıtılmayan birim aşım sütununda da boşta kalan sütununda da görünmez. - Yük 1200'de altı özne aşarken sistemde **1160** birim boştadır; aşım ile boşluk aynı anda bulunur ve tek bir gösterge ikisini birden söylemez. - Tutarlı karma dağıtımda sıralıdan iyi değildir, ama bir özne çıkarıldığında taşınan anahtar **1181** yerine **29**'dur — kuralın ödediği yer dağıtım değil, üyelik değişimidir. ## Sonraki Adım Bu iki derste dengeleyici hep aynı yerde durdu: kırk öznenin önünde, onların adına karar vererek. Yükü kim gönderirse göndersin, kaldıraç öznelerin tarafındaydı ve amacı onları korumaktı. Aynı aracı ters yöne çevrilebilir: istemcilerin önünde durup **onların adına** karar verebilir. Sonraki ders bu iki duruşu — ters vekil ile ileri vekili — yan yana koyar ve tek bir sayının, aynı sınırın, hangi tarafta durduğuna göre nasıl iki ayrı kuyruk ürettiğini sayar.