Yük Dengeleme Algoritmaları

Ö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:

# öğ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

"""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.