Paralel ve Dağıtık Veri Çerçeveleri

Önceki ders okunan değeri altı buçuk kat düşürdü, ama bütün hesap tek bir yerde yapıldı. O yerin sınırı kaçınılmazdır: okunan değer altıda birine inse de küme bin kat büyüdüğünde tek makinenin okuyacağı değer yine sığmaz. Bu ders işi birden çok bölüme dağıtır ve tek soruyu sorar — dağıtmanın kendisi hesaba ne ekliyor.

Cevap bir kalem listesidir ve listenin adı geçişin bedelidir. Kümeyi bölümlere ayırmak, bölümler arasında satır taşımak ve bölümleri eşgüdümlemek işin kendisinden ayrı birer iştir. Dersin ölçüsü bu kalemleri tek makinenin işiyle aynı birimde sayar ve iki sayıyı yan yana koyar: kazanç, yani dağıtımın kaç kat ucuza indirdiği, ve gizlenen karar, yani bölümleme anahtarı seçilirken sessizce belirlenen denge ile taşıma.

• AB16. Küme kurgudur ve önceki derslerin kümesidir: 3.199 satır, 1.329 abone, üç dönem. Aynı tohumla üretilir ve çıktı koşumdan koşuma aynıdır. Modeldir.
• AB17. İş birimi bir satıra bir kez dokunmaktır; n satırlık iş tek makinede n birimdir.
• AB18. Bir satırı bölümler arasında taşımak 10 birimdir. Bu oran modelin varsayımıdır; değiştiğinde bütün eşikler kayar ve kayma yönü tabloda okunur. Modeldir.
• AB19. Bir bölümün kurulması ve sonucunun toplanması 2.000 birim eşgüdüm gerektirir; p bölüm p çarpı 2.000 birim ekler.
• AB20. Bölümler eşzamanlı çalışır; dağıtık işin kritik yolu en büyük bölümün iş birimidir. Toplam maliyet kritik yol ile taşıma ve eşgüdüm kalemlerinin toplamıdır.

Aynı Kümenin Üç Bölümlemesi

# bolum.py — ayni kurgu kume uc ayri anahtarla bolumlere ayrilir. MODELDIR:
# gercek bir dagitim yerine bolumleme, tasima ve esgudum kalemleri sayilir.
# Olcu birimi bir satira bir kez dokunmaktir.
TOHUM = 1246
BOLGE = ("kuzey", "dogu", "merkez", "guney", "bati")
DONEM = (("2024-01", 1329), ("2024-02", 1035), ("2024-03", 835))
YOGUNLUK = (0, 1, 2, 2, 2, 3, 4, 2, 2, 1)   # merkez agirlikli kurgu olcum agi
TASIMA = 10       # bir satiri baska bolume tasimak on yerel dokunus eder
ESGUDUM = 2000    # bir bolumun kurulmasi ve sonucunun toplanmasi


def uretec(tohum: int):
    s = tohum & 0xFFFFFFFF

    def sonraki() -> float:
        nonlocal s
        s = (1103515245 * s + 12345) & 0xFFFFFFFF
        return s / 4294967296
    return sonraki


def kayitlar() -> list[tuple]:
    r, k = uretec(TOHUM), []
    for donem, adet in DONEM:
        for i in range(adet):
            k.append((10000 + i, f"S-{4000 + i}", donem,
                      BOLGE[YOGUNLUK[i % 10]], round(5 + r() * 32.0, 1)))
    return k


def bolumle(k: list, anahtar) -> dict:
    b = {}
    for x in k:
        b.setdefault(anahtar(x), []).append(x)
    return b


k0 = kayitlar()
ANAHTAR = (("bolge", lambda x: x[3]), ("abone mod 4", lambda x: x[0] % 4),
           ("donem", lambda x: x[2]))
G = (16, 9, 30, 14, 12)
y = lambda h: "".join(str(v).rjust(G[j]) if j else str(v).ljust(G[0])
                      for j, v in enumerate(h))
print(f"kume {len(k0)} satir, {len({x[0] for x in k0})} abone; tasima {TASIMA} "
      f"birim/satir, esgudum {ESGUDUM} birim/bolum")
print(y(["bolumleme anahtari", "bolum", "bolum boyutlari", "en buyuk", "carpiklik"]))
for ad, f in ANAHTAR:
    b = bolumle(k0, f)
    boy = sorted((len(v) for v in b.values()), reverse=True)
    print(y([ad, len(b), str(boy), boy[0], f"{boy[0] / (len(k0) / len(b)):.2f}x"]))

kume 3199 satir, 1329 abone; tasima 10 birim/satir, esgudum 2000 birim/bolum
bolumleme anahtari    bolum               bolum boyutlari      en buyuk   carpiklik
bolge                   5    [1601, 639, 321, 319, 319]          1601       2.50x
abone mod 4             4          [801, 800, 800, 798]           801       1.00x
donem                   3             [1329, 1035, 835]          1329       1.25x

Üç anahtar da savunulabilir ve üçü farklı bir yerleşim veriyor. Abone numarasının kalanına göre bölümleme dengelidir: dört bölüm 798 ile 801 satır arasında, çarpıklık 1,00. Bölgeye göre bölümleme çarpıktır: merkez bölümü 1.601 satır taşır, ortalamanın 2,50 katı. Dönem anahtarı arada durur.

Çarpıklık doğrudan kritik yola yazılır. Bölümler eşzamanlı çalıştığı için işin bitmesi en büyük bölümün bitmesine bağlıdır; beş bölüme ayrılmış bir küme, bölümlerden biri kümenin yarısını taşıyorsa beşte bire değil yarıya iner. Bölümleme anahtarı bir düzenleme ayrıntısı gibi görünür, oysa dağıtımdan beklenen kazancın üst sınırını belirler.

Geçişin Kalemleri

# gecis.py — iki sorgu uc bolumleme uzerinde calistirilir ve gecisin kalemleri
# ayri ayri sayilir: kritik yol (en buyuk bolumun is birimi), tasinan satir ve
# esgudum. Toplam = kritik yol + tasinan * TASIMA + bolum * ESGUDUM.
def indeksle(b: dict) -> dict:
    return {ad: i for i, ad in enumerate(sorted(b, key=str))}


def hizali_mi(b: dict, kimlik) -> bool:
    yer = {}
    for ad, v in b.items():
        for x in v:
            yer.setdefault(kimlik(x), set()).add(ad)
    return all(len(s) == 1 for s in yer.values())


def yeniden_dagit(b: dict, kimlik) -> tuple[dict, int]:
    """Kume kimlik anahtarina gore yeniden bolumlenir, bolum sayisi korunur.
    Hedef bolumu kaynak bolumunden farkli olan her satir tasinir."""
    ix, p = indeksle(b), len(b)
    yeni, tasinan = {i: [] for i in range(p)}, 0
    for ad, v in b.items():
        for x in v:
            h = kimlik(x) % p
            yeni[h].append(x)
            tasinan += h != ix[ad]
    return yeni, tasinan


maliyet = lambda p, kritik, tasinan: kritik + tasinan * TASIMA + p * ESGUDUM
G2 = (16, 9, 12, 12, 12, 12, 9)
y2 = lambda h: "".join(str(v).rjust(G2[j]) if j else str(v).ljust(G2[0])
                       for j, v in enumerate(h))

print("A sorgusu: bolge basina toplam okuma (kismi toplulastirilabilir)")
print(y2(["bolumleme", "bolum", "tasinan", "kritik yol", "esgudum", "dagitik", "oran"]))
for ad, f in ANAHTAR:
    b = bolumle(k0, f)
    tasinan = sum(len({x[3] for x in v}) for v in b.values())   # kismi sonuclar
    kritik = max(len(v) for v in b.values())
    m = maliyet(len(b), kritik, tasinan)
    print(y2([ad, len(b), tasinan, kritik, len(b) * ESGUDUM, m,
              f"{len(k0) / m:.2f}x"]))

print("B sorgusu: donemler arasi artisi 5 m3'u asan abone sayisi (abone butunlugu ister)")
print(y2(["bolumleme", "bolum", "tasinan", "kritik yol", "esgudum", "dagitik", "oran"]))
for ad, f in ANAHTAR:
    b = bolumle(k0, f)
    if hizali_mi(b, lambda x: x[0]):
        tasinan, kritik = len(b), max(len(v) for v in b.values())
    else:
        yeni, tasinan = yeniden_dagit(b, lambda x: x[0])
        tasinan, kritik = tasinan + len(b), max(len(v) for v in yeni.values())
    m = maliyet(len(b), kritik, tasinan)
    print(y2([ad, len(b), tasinan, kritik, len(b) * ESGUDUM, m,
              f"{len(k0) / m:.2f}x"]))

A sorgusu: bolge basina toplam okuma (kismi toplulastirilabilir)
bolumleme           bolum     tasinan  kritik yol     esgudum     dagitik     oran
bolge                   5           5        1601       10000       11651    0.27x
abone mod 4             4          12         801        8000        8921    0.36x
donem                   3          15        1329        6000        7479    0.43x
B sorgusu: donemler arasi artisi 5 m3'u asan abone sayisi (abone butunlugu ister)
bolumleme           bolum     tasinan  kritik yol     esgudum     dagitik     oran
bolge                   5           5        1601       10000       11651    0.27x
abone mod 4             4           4         801        8000        8841    0.36x
donem                   3        2136        1067        6000       28427    0.11x

İki tablo da aynı kümede, aynı bölüm sayısıyla çalışıyor ve ikisinde de dağıtık maliyet tek makinenin 3.199 biriminin üstünde kalıyor. Bu ölçekte dağıtmak kazandırmaz; tablonun işi kaybın nereden geldiğini göstermektir.

A sorgusu kısmi toplulaştırılabilir: her bölüm kendi bölge toplamlarını hesaplar ve yalnız kısmi sonucu gönderir. Taşınan satır 5 ile 15 arasındadır ve küme boyundan bağımsızdır — bölüm sayısı ile grup sayısının çarpımıdır. Maliyetin neredeyse tamamı eşgüdümdür: bölge anahtarında 11.651 birimin 10.000’i, abone anahtarında 8.921 birimin 8.000’i.

B sorgusu bir abonenin bütün satırlarının aynı bölümde olmasını ister ve burada bölümleme anahtarı sonucu belirler. Bölge ve abone anahtarları hizalıdır — her abone tek bir bölgededir — ve taşınan satır bölüm sayısı kadar kalır. Dönem anahtarı hizalı değildir: aynı abonenin üç dönemi üç ayrı bölümdedir, küme yeniden dağıtılır ve 2.136 satır taşınır. Maliyet 7.479’dan 28.427 birime, dört kata çıkar. Gizlenen karar budur: bölümleme anahtarı sorgudan önce seçilir ve sorgunun taşıma kalemini o seçim belirler.

Kazanca Dönme Eşiği

# olcek.py — ayni model buyuyen kume boyunda cozulur. Bolum oranlari olculen
# kumeden alinir; kismi toplulastirilabilir sorguda tasinan satir n'den
# bagimsizdir, hizalanmamis sorguda n ile birlikte buyur.
import math
ORAN = {ad: max(len(v) for v in bolumle(k0, f).values()) / len(k0)
        for ad, f in ANAHTAR}
_b = bolumle(k0, dict(ANAHTAR)["donem"])
_yeni, _tasinan = yeniden_dagit(_b, lambda x: x[0])
PAY = _tasinan / len(k0)            # donem bolumlemesinde yerinde kalmayan pay
B_ORAN = max(len(v) for v in _yeni.values()) / len(k0)

SENARYO = (("A / abone mod 4", 4, ORAN["abone mod 4"], 12, 0.0),
           ("A / bolge", 5, ORAN["bolge"], 5, 0.0),
           ("B / donem", 3, B_ORAN, 3, PAY))
G3 = (18, 14, 15, 15, 15, 13)
y3 = lambda h: "".join(str(v).rjust(G3[j]) if j else str(v).ljust(G3[0])
                       for j, v in enumerate(h))


def dagitik(n, p, oran, sabit, pay):
    tasinan = sabit + pay * n
    return round(oran * n + tasinan * TASIMA + p * ESGUDUM)


print(y3(["kume n", "tek makine", "A/abone mod 4", "A/bolge", "B/donem",
          "en iyi oran"]))
for n in (3199, 31990, 319900, 3199000):
    satir = [dagitik(n, p, o, s, pay) for _, p, o, s, pay in SENARYO]
    print(y3([n, n, satir[0], satir[1], satir[2], f"{n / min(satir):.2f}x"]))
print(y3(["esik n", "-", *[
    (math.ceil((s * TASIMA + p * ESGUDUM) / (1 - o)) if pay * TASIMA + o < 1
     else "hic") for _, p, o, s, pay in SENARYO], "-"]))
print(f"donem bolumlemesinde satirlarin yuzde {100 * PAY:.1f} kadari yerinde "
      f"kalmaz; "
      f"tasima kalemi tek basina tek makine isinin {PAY * TASIMA:.1f} katidir")

kume n                tek makine  A/abone mod 4        A/bolge        B/donem  en iyi oran
3199                        3199           8921          11651          28427        0.36x
31990                      31990          16130          26060         230000        1.98x
319900                    319900          88220         170150        2245730        3.63x
3199000                  3199000         809120        1611050       22403030        3.95x
esik n                         -          10833          20119            hic            -
donem bolumlemesinde satirlarin yuzde 66.7 kadari yerinde kalmaz; tasima kalemi tek basina tek makine isinin 6.7 katidir

Tablo dağıtımın nerede kazanca döndüğünü gösteriyor. Eşgüdüm küme boyundan bağımsız sabit bir kalemdir; küme büyüdükçe payı erir ve kritik yol baskın hale gelir. Dengeli anahtarda eşik 10.833 satırdır: bu boyun altında dağıtmak pahalıdır, üstünde ucuzlar. Çarpık anahtarda eşik 20.119 satıra çıkar — aynı model, aynı sabitler, yalnız bölümleme anahtarı farklı. Çarpıklık eşiği neredeyse ikiye katlar.

Üçüncü sütun eşiği hiç görmez. Hizalanmamış sorguda taşınan satır küme boyuyla birlikte büyür: satırların yüzde 66,7 kadarı yerinde kalmaz ve taşıma kalemi tek başına tek makine işinin 6,7 katına çıkar. n ne kadar büyürse büyüsün oran sabit kalır ve dağıtık maliyet tek makinenin üstünde durur. Ölçek büyütmek bu sorguyu kurtarmaz; kurtaran tek şey kümeyi doğru anahtara göre bölümlemektir.

Kazanç tarafı da sınırlıdır. 3.199.000 satırda en iyi seçenek 809.120 birim tutar ve tek makineye göre 3,95 kat kazandırır — dört bölüme ayrılmış bir işten beklenen dört katın az altı. Fark tamamen taşıma ve eşgüdüm kalemlerinden gelir ve bu kalemler hiçbir küme boyunda sıfırlanmaz. Bölüm sayısını artırmak kazancı bölüm sayısı kadar artırmaz; eşgüdüm kalemi bölüm sayısıyla birlikte büyür.

Bölüm Sayısının Sınırı

# bolum_sayisi.py — ayni is farkli bolum sayilariyla dagitilir. Kritik yol
# bolum sayisiyla kuculur, esgudum bolum sayisiyla buyur; en iyi bolum sayisi
# ikisinin dengelendigi yerdedir. Dengeli anahtar varsayilir.
N = 3199000
G4 = (10, 14, 12, 12, 14, 10)
y4 = lambda h: "".join(str(v).rjust(G4[j]) if j else str(v).ljust(G4[0])
                       for j, v in enumerate(h))
hesap = lambda p: math.ceil(N / p) + (p * 5) * TASIMA + p * ESGUDUM
print(y4(["bolum", "kritik yol", "tasinan", "esgudum", "dagitik", "oran"]))
for p in (2, 4, 16, 40, 64, 256):
    print(y4([p, math.ceil(N / p), p * 5, p * ESGUDUM, hesap(p),
              f"{N / hesap(p):.1f}x"]))
en_iyi = min(range(1, 1001), key=hesap)
print(f"n = {N} icin en iyi bolum sayisi {en_iyi}; maliyet {hesap(en_iyi)} birim, "
      f"kazanc {N / hesap(en_iyi):.1f} kat")
print(f"bolum {en_iyi} yerine {4 * en_iyi} secilirse maliyet {hesap(4 * en_iyi)} "
      f"birime cikar ve kazanc {N / hesap(4 * en_iyi):.1f} kata iner")

bolum         kritik yol     tasinan     esgudum       dagitik      oran
2                1599500          10        4000       1603600      2.0x
4                 799750          20        8000        807950      4.0x
16                199938          80       32000        232738     13.7x
40                 79975         200       80000        161975     19.7x
64                 49985         320      128000        181185     17.7x
256                12497        1280      512000        537297      6.0x
n = 3199000 icin en iyi bolum sayisi 40; maliyet 161975 birim, kazanc 19.7 kat
bolum 40 yerine 160 secilirse maliyet 347994 birime cikar ve kazanc 9.2 kata iner

Bölüm sayısı iki kalemi ters yönde oynatır. Kritik yol bölüm sayısına bölünür, eşgüdüm ise bölüm sayısıyla çarpılır; ilki azalırken ikincisi artar ve toplam bir yerde en küçük değerini alır. 3.199.000 satırlık küme için o yer 40 bölümdür: maliyet 161.975 birim, kazanç 19,7 kat. Dört bölümde kazanç 4,0 kat, 256 bölümde 6,0 kattır — bölüm sayısını artırmak bir yerden sonra kazancı azaltır.

Sayının kendisi modelin sabitlerine bağlıdır ve sabitler AB18 ile AB19’da yazılıdır; taşıma bedeli ya da eşgüdüm değişirse en iyi bölüm sayısı da değişir. Değişmeyen şey biçimdir: dağıtımın kazancı bölüm sayısıyla doğru orantılı değildir ve bir tepe noktası vardır. En iyi bölüm sayısının dört katı seçildiğinde maliyet 347.994 birime çıkar ve kazanç 9,2 kata iner: dört kat fazla bölüm, iki kat fazla maliyet demektir. Bölüm sayısı da bir varsayılan değil, yazılması gereken bir karardır.

Özet

• Dağıtık bir hesabın maliyeti üç kalemdir: en büyük bölümün iş birimi, taşınan satır çarpı taşıma bedeli ve bölüm başına eşgüdüm. Bölümleme anahtarı bölüm dengesini belirler: abone kalanı 1,00 çarpıklık ve 801 satırlık kritik yol, bölge anahtarı 2,50 çarpıklık ve 1.601 satırlık kritik yol verir.
• 3.199 satırda dağıtmak kazandırmaz; en iyi seçenek 8.921 birim tutarken tek makine 3.199 birim harcar.
• Kısmi toplulaştırılabilen sorguda taşınan satır küme boyundan bağımsızdır (5–15 satır); bütünlük isteyen sorguda hizasız anahtar 2.136 satır taşıtır ve maliyeti dört kata çıkarır.
• Kazanca dönme eşiği dengeli anahtarda 10.833, çarpık anahtarda 20.119 satırdır; hizalanmamış sorguda böyle bir eşik yoktur.
• 3.199.000 satırda dört bölümlü dağıtım 3,95 kat kazandırır; aynı kümede en iyi bölüm sayısı 40’tır ve kazanç 19,7 katta doyar, 256 bölümde 6,0 kata geriler.

Sonraki Adım

Bu ders işi birden çok bölüme taşıdı, ama bütün kalemler hâlâ verinin çözümleme ortamına getirilmesi üzerine kuruluydu: satırlar okunuyor, taşınıyor, bölünüyor. Verinin durduğu yer de hesap yapabiliyorsa sıra tersine çevrilebilir — süzgeç ve toplulaştırma kaynağa itilir ve çözümleme ortamına yalnız sonuç gelir. Sonraki ders bunu tek bir sayıyla ölçer: aynı soru için kaynaktan kaç satır çıkıyor, ve toplulaştırma kaynakta yapıldığında hangi karar artık senin elinden çıkmış oluyor.