Ölçekte Birleştirme

Bir önceki dersin bütün ölçümleri tek bir veri kümesi üzerinde yapıldı: 2200 satır bölüştü, yeniden bölüştü ve taşınan satır sayıldı. Dağıtık işlerin çoğu ise tek bir kümeyi değil iki kümeyi karşı karşıya getirir: büyük bir olgu tarafı ile ona bağlanan bir boyut tarafı. Birleştirmenin çalışması için eşleşecek iki satırın aynı işçide bulunması gerekir, yoksa karşılaşamazlar.

Bunu sağlamanın iki yolu vardır ve bedelleri farklı cinstendir. Küçük taraf her işçiye kopyalanabilir — o zaman hiçbir satır taşınmaz ama küçük taraf işçi sayısı kadar çoğalır. Ya da iki taraf da birleştirme anahtarına göre karıştırılır — o zaman kopya olmaz ama iki tarafın da satırları ağdan geçer. Bu ders iki stratejiyi boyut tarafı büyütülerek karşılaştırır ve kazananın değiştiği noktayı arar.

• DB10. Kaynak, tüketim satırları, boyut tarafı ve küme kurgudur ve ders içinde üretilir. Hiçbir dağıtık işleme çatısı, sorgu motoru ya da dosya sistemi çağrılmaz. Tohum 20260218.
• DB11. Olgu tarafı hattan çıkan 2200 tüketim satırıdır ve bir önceki dersin en dengesiz düzeninde, bolge anahtarıyla bölünmüş durur. Birleştirme anahtarı abone’dir. Olgu ve boyut bağıntısı ayrımı Veritabanları müfredatındaki İlişkisel Veritabanı Yönetimi kursunda kuruldu; tekrarlanmaz.
• DB12. Boyut tarafı bir abone dizinidir: A000’dan başlayan anahtarlar. Büyüklüğü süpürülür; 50 satırlık bir dizin abonelerin bir alt kümesini, 4000 satırlık bir dizin hattın gördüğünden çok daha geniş bir kayıt kütüğünü temsil eder.
• DB13. Yayınlı birleştirme (broadcast join): boyut tarafı her işçiye kopyalanır. Taşınan satır 0, kopya boyut x işçi. Bir kopyanın bedeli bir birimdir ve ağ bedeliyle çarpılmaz; bu bir model seçimidir ve dersin sonucunu doğrudan belirler.
• DB14. Bölümlü birleştirme (partitioned join): iki taraf da birleştirme anahtarına göre karıştırılır. Kopya 0, taşınan satırın her biri AG_BEDELI katı bedel yazar.
• DB15. Boyut tarafı işe tek bir işçide, bölüştürülmemiş girer. Bölümlü stratejide bu yüzden onun da işçi değiştiren satırları taşınana eklenir.
• DB16. Süre en yüklü işçinin işidir, toplam iş ayrı sayılır ve süre bu modelin kendi birimidir. GOREV_SABIT = 50 aynı işçi sayısındaki iki stratejiye de eşit eklenir, dolayısıyla karşılaştırmanın içine girmez.
• DB17. Taban çizgisi tek işçidir: süre 2250, toplam iş 2200.
• DB18. İki strateji her boyut büyüklüğünde aynı satırları eşleştirir; ölçülen tek şey bedeldir.

İki Strateji, İki Cins Bedel

Aşağıdaki blok olgu tarafını bolge ile böler, boyut tarafını altı ayrı büyüklükte üretir ve her büyüklükte iki stratejinin bedelini yan yana yazar. Eşleşen satır sütunu iki strateji için de aynıdır ve tek kez basılır.

# KURGUDUR. Olcum aginin sayac okumalari , tuketim satirlari ve kume ders icinde
# uretilir; hicbir dagitik isleme catisi ya da dosya sistemi cagrilmaz. Tohum 20260218.
TOHUM, M32 = 20260218, 0xFFFFFFFF


def uretec(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def sonraki():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return sonraki


BOLGE = ["dogu", "bati", "kuzey", "guney", "merkez"]
TIP = ["mesken", "isyeri"]
DONEM = [f"2026-{a:02d}" for a in range(1, 13)]
ISCI, AG_BEDELI, GOREV_SABIT = 4, 3, 50
ABONE = {}
for i in range(200):
    r = uretec(TOHUM + 37 * i)
    ABONE[f"A{i + 1:03d}"] = {"bolge": BOLGE[int(r() * 5)], "tip": TIP[int(r() * 2)],
                              "baslangic": 10000 + int(r() * 60000)}


def satirlar():
    """Hattan cikan tuketim satirlari (olgu tarafi). Saglam kaynakta ayikla ve
    tekille asamalari satir dusurmez; tuketim donem farkindan bulunur."""
    ham = []
    for i, (ab, a) in enumerate(ABONE.items()):
        e = a["baslangic"]
        for d in DONEM:
            r = uretec(TOHUM + 101 * i + 7 * DONEM.index(d))
            e += 4 + int(r() * 46)
            ham.append({"abone": ab, "donem": d, "bolge": a["bolge"], "tip": a["tip"],
                        "endeks": e, "birim": "m3"})
    tablo, cikti = {(k["abone"], k["donem"]): k for k in ham}, []
    for k in ham:
        i = DONEM.index(k["donem"])
        onceki = tablo.get((k["abone"], DONEM[i - 1])) if i else None
        if onceki is not None:
            cikti.append(dict(k, m3=k["endeks"] - onceki["endeks"]))
    return cikti


def izno(m):
    h = 2166136261
    for c in str(m):
        h = ((h ^ ord(c)) * 16777619) & 0xFFFFFFFF
    return h


def dagit(kayitlar, anahtar, isci=ISCI):
    """Satirlari anahtara gore isciye atar. Ayni anahtar hep ayni isciye gider."""
    kova = {i: [] for i in range(isci)}
    for k in kayitlar:
        kova[izno(k[anahtar]) % isci].append(k)
    return kova


def karistir(kova, yeni_anahtar, isci=ISCI):
    """Yeniden bolustur. Isci degistiren satir agdan gecer."""
    yeni, tasinan = {i: [] for i in range(isci)}, 0
    for eski, kayitlar in kova.items():
        for k in kayitlar:
            hedef = izno(k[yeni_anahtar]) % isci
            if hedef != eski:
                tasinan += 1
            yeni[hedef].append(k)
    return yeni, tasinan


def yayinli_birlestirme(kova, boyut, isci=ISCI):
    """Boyut her isciye kopyalanir. Karistirma yok , kopya var."""
    kopya = len(boyut) * isci
    n = [len(v) for v in kova.values()]
    return {"tasinan": 0, "kopya": kopya,
            "sure": max(n) + kopya // isci + GOREV_SABIT,
            "toplam_is": sum(n) + kopya}


def bolumlu_birlestirme(kova, boyut, anahtar="abone", isci=ISCI):
    """Iki taraf da anahtara gore karistirilir."""
    _, tasinan = karistir(kova, anahtar, isci)
    boyut_tasinan = sum(1 for a in boyut if izno(a) % isci != 0)
    n = [len(v) for v in kova.values()]
    t = tasinan + boyut_tasinan
    return {"tasinan": t, "kopya": 0,
            "sure": max(n) + t * AG_BEDELI // isci + GOREV_SABIT,
            "toplam_is": sum(n) + t * AG_BEDELI}


def boyut_uret(n):
    """Abone dizini: n anahtar. Tek bir iscide , bolusturulmemis duruyor."""
    return [f"A{i:03d}" for i in range(n)]


TUM = satirlar()
KOVA = dagit(TUM, "bolge")
print(f"olgu tarafi {len(TUM)} satir , bolge anahtariyla bolunmus ,"
      f" isci yuku {[len(v) for v in KOVA.values()]}")
print(f"tek iscilik taban: sure {len(TUM) + GOREV_SABIT} , toplam is {len(TUM)}")
print(f"birlestirme anahtari abone , isci {ISCI} , ag bedeli {AG_BEDELI}")
print("\nboyut  eslesen  kopya  y.sure  y.toplam   tasinan  b.sure  b.toplam   kazanan")
for n in (50, 200, 400, 800, 1600, 4000):
    b = boyut_uret(n)
    y, p = yayinli_birlestirme(KOVA, b), bolumlu_birlestirme(KOVA, b)
    es = sum(1 for k in TUM if k["abone"] in set(b))
    print(f"{n:>5} {es:>8} {y['kopya']:>6} {y['sure']:>7} {y['toplam_is']:>9}"
          f" {p['tasinan']:>9} {p['sure']:>7} {p['toplam_is']:>9}"
          f"   {'yayinli' if y['sure'] < p['sure'] else 'bolumlu'}")

olgu tarafi 2200 satir , bolge anahtariyla bolunmus , isci yuku [374, 0, 0, 1826]
tek iscilik taban: sure 2250 , toplam is 2200
birlestirme anahtari abone , isci 4 , ag bedeli 3

boyut  eslesen  kopya  y.sure  y.toplam   tasinan  b.sure  b.toplam   kazanan
   50      539    200    1926      2400      1775    3207      7525   yayinli
  200     2189    800    2076      3000      1888    3292      7864   yayinli
  400     2200   1600    2276      3800      2038    3404      8314   yayinli
  800     2200   3200    2676      5400      2338    3629      9214   yayinli
 1600     2200   6400    3476      8600      2938    4079     11014   yayinli
 4000     2200  16000    5876     18200      4738    5429     16414   bolumlu

Eşleşen satır sütunu tablonun ön koşuludur. Aynı boyut büyüklüğünde iki strateji aynı satırları eşleştirir: 50 satırlık dizinde 539, 200 satırlıkta 2189, 400’den sonra 2200. Sütunun boyutla büyümesinin nedeni dizinin gitgide daha çok aboneyi kapsamasıdır; 400 satırdan sonra bütün aboneler kapsandığı için sabitlenir. Ölçülen şey doğruluk değildir, çünkü doğruluk iki stratejide de aynıdır.

İlk satır bölümlü stratejinin en önemli özelliğini verir: bir tabanı vardır. Boyut yalnız 50 satır olsa bile bölümlü birleştirme olgu tarafının 1738 satırını taşımak zorundadır, çünkü olgu tarafı bolge ile bölünmüşken birleştirme abone üzerinden yapılır. Bu yüzden bölümlü süre hiçbir boyut büyüklüğünde 3207’nin altına inemez. Yayınlı stratejinin ise tabanı yoktur; boyut küçüldükçe bedeli sıfıra yaklaşır ve 50 satırda süre yalnız 1926’dır. Küçük boyutta yayınlı birleştirmenin kazanması bir eğilim değil, yapısal bir sonuçtur.

İki sütunun büyüme hızı kararı belirler. Yayınlı stratejide boyutun her satırı işçi sayısı kadar kopyalanır, kopyalar işçilere bölündüğü için süreye satır başına bir birim ekler: 1876 artı boyut satırı. Bölümlü stratejide boyutun dörtte üçü işçi değiştirir, her taşınan satır ağ bedeliyle çarpılır ve işçilere bölünür — süreye eklenen satır başına dörtte üç birimdir. Yayınlı daha dik büyür ama sıfırdan başlar; bölümlü daha yavaş büyür ama 1303 birimlik bir yükseklikten. İki doğrunun kesişmesi kaçınılmazdır ve kesiştiği yer bu dersin aradığı sayıdır.

Toplam iş sütunu aynı hikâyeyi başka bir birimle anlatır. 1600 satırlık boyutta yayınlı 8600, bölümlü 11014 birim iş yapar; 4000’de sıralama ters döner (18200’e karşı 16414). Kursun kuralı süre ile toplam işin ayrı yönlere gidebileceğini söyler; bu karşılaştırmada gitmezler, çünkü her iki stratejinin de süresi toplam işinin işçi sayısına bölünmüş hâlidir ve bölen ikisinde de aynıdır. Kuralın buradaki karşılığı şudur: ikisinin uyuştuğu da gösterilmelidir, yoksa hangisinin ölçüldüğü bilinmez.

Dönüş Noktası

Altı büyüklük dönüşün 1600 ile 4000 arasında olduğunu söyler, yerini söylemez. Aşağıdaki blok boyut büyüklüğünü tek tek tarar. Tarama hızlı olsun diye boyut tarafının taşınan satırı bir önek toplamıyla tutulur; ilk satır bu kısayolun ilk bloktaki işlevlerle aynı sonucu verdiğini doğrular.

# Bu blok ilk bloktaki izno() , dagit() , karistir() , yayinli_birlestirme() ,
# bolumlu_birlestirme() , boyut_uret() , TUM ve KOVA tanimlarini surdurur.
ONEK = [0]                       # ONEK[n]: ilk n boyut satirinin kaci isci degistirir
for a in boyut_uret(4000):
    ONEK.append(ONEK[-1] + (1 if izno(a) % ISCI else 0))
_, OLGU_TASINAN = karistir(KOVA, "abone")
YUK = [len(v) for v in KOVA.values()]


def olcum(n, ag=AG_BEDELI):
    """Ilk bloktaki iki islevle ayni hesap; tek fark ag bedelinin disaridan
    verilmesi ve boyut tarafinin onek toplamiyla hizlandirilmasidir.
    Doner: yayinli sure , bolumlu sure , yayinli toplam is , bolumlu toplam is."""
    t = OLGU_TASINAN + ONEK[n]
    return (max(YUK) + n + GOREV_SABIT, max(YUK) + t * ag // ISCI + GOREV_SABIT,
            sum(YUK) + n * ISCI, sum(YUK) + t * ag)


d = boyut_uret(4000)
print(f"dogrulama , boyut 4000: islevlerle {yayinli_birlestirme(KOVA, d)['sure']}"
      f"/{bolumlu_birlestirme(KOVA, d)['sure']} , onek toplamiyla"
      f" {olcum(4000)[0]}/{olcum(4000)[1]}")
print("\nag bedeli 3'te donus noktasinin iki yani")
for n in (2978, 2979, 2980, 2981):
    y, b, _, _ = olcum(n)
    print(f"boyut {n}   yayinli {y}   bolumlu {b}   "
          f"{'yayinli' if y < b else 'bolumlu' if b < y else 'esit'}")
ilk_is = next(n for n in range(1, 4001) if olcum(n)[3] < olcum(n)[2])
print(f"\ntoplam is olculdugunde bolumlunun one gectigi ilk boyut: {ilk_is}")
print("\nag bedeli   sure olculdugunde bolumlunun one gectigi ilk boyut (4000'e kadar)")
for ag in (1, 3, 6, 12):
    ilk = next((n for n in range(1, 4001) if olcum(n, ag)[1] < olcum(n, ag)[0]), None)
    print(f"{ag:>9}   {ilk if ilk else 'hic'}")

dogrulama , boyut 4000: islevlerle 5876/5429 , onek toplamiyla 5876/5429

ag bedeli 3'te donus noktasinin iki yani
boyut 2978   yayinli 4854   bolumlu 4854   esit
boyut 2979   yayinli 4855   bolumlu 4855   esit
boyut 2980   yayinli 4856   bolumlu 4855   bolumlu
boyut 2981   yayinli 4857   bolumlu 4856   bolumlu

toplam is olculdugunde bolumlunun one gectigi ilk boyut: 2980

ag bedeli   sure olculdugunde bolumlunun one gectigi ilk boyut (4000'e kadar)
        1   535
        3   2980
        6   hic
       12   hic

Kesişme noktası 2980‘dir. 2978 ve 2979’da iki strateji eşittir, 2980’de bölümlü bir birim öne geçer. Kesişimin keskin olmaması modelin tam sayı bölmesinden gelir: yayınlı süre satır başına tam bir birim, bölümlü süre dörtte üç birim büyüdüğü için iki doğru birkaç satır boyunca aynı tam sayıda buluşur. Kararın pratik okuması “boyut üç bine yaklaşınca strateji değişir” değil, yaklaşık üç binde iki stratejinin farkı ölçülemez hâle gelir; farkın anlamlı olduğu tek yer uçlardır. 50 satırda yayınlı 1281 birim öndedir, 4000 satırda bölümlü 447 birim.

Toplam iş satırı dönüşün aynı yerde olduğunu doğrular: 2980. Bu tesadüf değildir. Yayınlı stratejinin toplam işi boyut başına dört birim, süresi bir birim büyür; bölümlü stratejinin toplam işi boyut başına 2,25 birim, süresi bunun dörtte biri kadar büyür. İki ölçünün oranı ikisinde de işçi sayısıdır, dolayısıyla sıralamaları aynı noktada döner. Bu, kursun kuralının bir istisnası değil, kuralın neden yazılması gerektiğinin kanıtıdır: uyuştukları ancak ikisi de ölçüldüğünde bilinir.

Son tablo kararın hangi seçime asıldığını gösterir ve bu dersin en sert bulgusudur. Ağ bedeli 1 olduğunda kesişme noktası 535’e iner; 2980 satırlık bir dizin için verilen karar, aynı veriyle, aynı işçi sayısıyla, yalnız bir sabit değiştiği için tersine döner. Ağ bedeli 6 ve 12 olduğunda ise bölümlü birleştirme taranan hiçbir boyut büyüklüğünde öne geçemez. Bunun nedeni okunabilir: bölümlü süre boyut satırı başına ağ bedelinin on altıda üçü kadar büyür, yayınlı süre bir birim; ağ bedeli beşte kaldığı sürece bölümlü daha yavaş büyür, altıya çıkınca daha hızlı büyür ve bir daha asla yetişemez. Yani “büyük boyutta bölümlü kazanır” cümlesi ağ bedeli 3 için doğru, 6 için yanlıştır.

Buradan çıkan kural şudur: bir birleştirme stratejisi veriye bakılarak seçilemez. İki taraf da aynı satırları eşleştirir, aynı sonucu verir ve doğruluk denetimi ikisini de geçer. Seçim boyut tarafının büyüklüğüne, olgu tarafının hangi anahtarla bölünmüş olduğuna ve ağ bedeline bakılarak yapılır; üç girdiden biri yazılmadan verilen karar ölçülmemiş sayılır.

Özet

• Yayınlı birleştirme boyut tarafını her işçiye kopyalar (taşınan 0), bölümlü birleştirme iki tarafı da karıştırır (kopya 0). Bedeller ayrı cinstendir: biri kopya, öbürü taşınan satır.
• Bölümlü stratejinin bir tabanı vardır: olgu tarafı bolge ile bölünmüşken birleştirme abone üzerinden yapıldığı için 1738 satır her koşulda taşınır ve süre 3207’nin altına inmez. Yayınlının tabanı yoktur; 50 satırlık boyutta süre 1926’dır.
• Yayınlı süre boyut satırı başına bir birim, bölümlü süre dörtte üç birim büyür. İki doğru kesişir: 2978 ve 2979’da süreler eşittir, 2980‘de bölümlü öne geçer. 4000’de fark 5876’ya karşı 5429’dur.
• Toplam iş ölçüldüğünde kesişme noktası yine 2980 çıkar, çünkü iki ölçünün oranı her iki stratejide de işçi sayısıdır. Uyuştukları ancak ikisi de ölçüldüğünde bilinir.
• Karar ağ bedeline asılıdır: bedel 1 iken kesişme noktası 535, 3 iken 2980, 6 ve 12 iken bölümlü hiçbir boyutta öne geçemez. İki strateji her boyutta aynı satırları eşleştirdiği için doğruluk denetimi bu farkın hiçbirini göstermez.

Sonraki Adım

Bu dersin bütün tablolarında bir sayı sessizce duruyordu: olgu tarafının işçi yükü [374, 0, 0, 1826] olarak basılmıştı. Dört işçinin ikisi hiç satır almamıştı ve bütün süre hesapları en yüklü işçinin 1826 satırı üzerinden yapılmıştı. Yayınlı stratejinin 1876 birimlik tabanı da, bölümlü stratejinin 3207’lik tabanı da bu tek sayıdan besleniyordu. İki ders boyunca yavaşlığın kaynağı hareket olarak arandı; oysa bu düzende işçilerin yarısı hiç çalışmıyordu ve bu, hareketten bağımsız bir kayıptır. Sonraki ders bölüşümün kendisine bakar: bir anahtarın işçiler arasında ne kadar dengesiz dağıldığını çarpıklık olarak ölçer, aynı işi doğru ve yanlış anahtarla bölüştürür ve dengesiz bir bölüşümde işçi eklemenin ne işe yaradığını sayar.