Karıştırma Maliyeti

Beş derste iş bölündü. Sürücü çalışmayı görevlere ayırdı, işçiler bölümlerini aldı, kaynak yöneticisi görevleri sıraya soktu ve dağıtık kurulum tek makinedeki hattın ürettiği sonucun birebir aynısını üretti. Bölüşümün çalıştığı ölçüldü; nerede yavaşladığı hiç sorulmadı.

Bu ders o soruyu sorar ve yanıtını tek bir yerde arar: bir satır bir işçiden başka bir işçiye geçtiğinde ne oluyor. Dağıtık bir işte hesabın kendisi her yerde aynıdır — toplama toplamadır, karşılaştırma karşılaştırmadır. Ayrışan tek şey verinin nerede durduğudur, ve veriyi yerinden oynatmak yerinde işlemekten pahalıdır. Ölçülen şey bu derste o farktır.

• DB1. Kaynak, tüketim satırları ve küme kurgudur ve ders içinde üretilir. Hiçbir dağıtık işleme çatısı, kaynak yöneticisi ya da dağıtık dosya sistemi çağrılmaz. Tohum 20260218.
• DB2. Süre bu modelin kendi birimidir, ham milisaniye değildir. Süre en yüklü işçinin işidir, çünkü işçiler paralel çalışır ve iş en geç bitenle biter. Toplam iş bütün işçilerin işinin toplamıdır. İkisi ayrı ölçülür ve ayrı yönlere gidebilir.
• DB3. Karıştırma (shuffle) satırları yeni bir anahtara göre yeniden bölüştürmektir. İşçi değiştiren satır ağdan geçer ve taşınan satır olarak sayılır; işçisi değişmeyen satır ağa hiç dokunmaz.
• DB4. Ağdan geçen bir satırın bedeli yerel işlemin AG_BEDELI katıdır, öntanımlı değeri 3’tür ve bu bir seçimdir. Bu ders onu 1, 3, 6 ve 12 değerleriyle süpürür.
• DB5. Her işçiye iş vermenin sabit bedeli GOREV_SABIT = 50’dir ve o da bir seçimdir. Aynı işçi sayısındaki iki kurulum karşılaştırılırken bu sabit ikisine de eşit eklenir, dolayısıyla farkın içine girmez.
• DB6. Bölüşüm anahtarın karmasıyla yapılır: aynı anahtar değeri her zaman aynı işçiye gider. İndirgeme bunu gerektirir; bir anahtarın satırları tek bir işçide toplanmazsa o anahtarın toplamı hesaplanamaz.
• DB7. Bölüm (partition) burada bir işçiye verilen satır kümesidir. Bölümleme yordamı Veritabanları müfredatındaki İlişkisel Veritabanı Yönetimi kursunda ve bu müfredattaki Veri Depolama Mimarileri kursunda ölçüldü; tekrarlanmaz. Parçalama (sharding) ayrı bir kavramdır ve bölümlemeyle karıştırılmaz.
• DB8. Taban çizgisi tek işçidir: karıştırma yok, süre 2250, toplam iş 2200.
• DB9. Bu dersteki bütün kurulumlar birebir aynı sonucu üretir; ölçülen tek şey bedeldir.

Karıştırmanın İki Sayısı

Aşağıdaki blok hattan çıkan 2200 tüketim satırını abone anahtarıyla dört işçiye böler, sonra aynı satırları üç ayrı anahtara göre yeniden bölüştürür ve her seferinde kaç satırın işçi değiştirdiğini sayar.

# KURGUDUR. Olcum aginin sayac okumalari , bes asamali hat ve kume ders icinde
# uretilir; hicbir dagitik isleme catisi , kaynak yoneticisi 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)]
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 kaynak_uret():
    kayit = []
    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)
            kayit.append({"abone": ab, "donem": d, "bolge": a["bolge"], "tip": a["tip"],
                          "endeks": e, "birim": "m3"})
    return kayit


def satirlar():
    """Hattan cikan tuketim satirlari. Saglam kaynakta ayikla ve tekille asamalari
    satir dusurmez; tuketim onceki donemin endeksinden cikarilarak bulunur."""
    ham, cikti = kaynak_uret(), []
    tablo = {(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


ISCI = 4
AG_BEDELI = 3          # bir satiri agdan tasimanin bedeli , yerel islemin kac kati
GOREV_SABIT = 50       # her isciye is vermenin sabit bedeli


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 = {i: [] for i in range(isci)}
    tasinan = 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 maliyet(kova, tasinan=0, isci=ISCI):
    """Sure = en yuklu iscinin isi (paralel). Toplam is ayrica sayilir."""
    n = [len(v) for v in kova.values()]
    return {"sure": max(n) + tasinan * AG_BEDELI // isci + GOREV_SABIT,
            "toplam_is": sum(n) + tasinan * AG_BEDELI,
            "tasinan": tasinan}


TUM = satirlar()
TEK = maliyet(dagit(TUM, "abone", 1), 0, 1)
KOVA = dagit(TUM, "abone")
print(f"hattan cikan satir {len(TUM)} , isci {ISCI} , ag bedeli {AG_BEDELI} ,"
      f" gorev sabiti {GOREV_SABIT}")
print(f"tek iscilik taban: sure {TEK['sure']} , toplam is {TEK['toplam_is']} , tasinan 0")
print(f"baslangic duzeni abone , isci yuku {[len(v) for v in KOVA.values()]}")
print("\nyeni anahtar   tasinan  yerinde   sure  toplam is   yeni isci yuku")
for hedef in ("abone", "donem", "bolge"):
    yeni, t = karistir(KOVA, hedef)
    m = maliyet(KOVA, t)
    print(f"{hedef:<12} {t:>9} {len(TUM) - t:>8} {m['sure']:>6} {m['toplam_is']:>10}"
          f"   {[len(v) for v in yeni.values()]}")

hattan cikan satir 2200 , isci 4 , ag bedeli 3 , gorev sabiti 50
tek iscilik taban: sure 2250 , toplam is 2200 , tasinan 0
baslangic duzeni abone , isci yuku [539, 550, 561, 550]

yeni anahtar   tasinan  yerinde   sure  toplam is   yeni isci yuku
abone                0     2200    611       2200   [539, 550, 561, 550]
donem             1651      549   1849       7153   [600, 600, 400, 600]
bolge             1738      462   1914       7414   [374, 0, 0, 1826]

İlk satır bir sınır çizer: karıştırmasız bir dağıtık iş mümkündür. abone düzenindeki satırlar yine abone anahtarına bölüştürüldüğünde hiçbir satır işçi değiştirmez. Taşınan satır 0, süre 611, toplam iş 2200. Toplam iş tek işçilik tabanla birebir aynıdır — dört işçi aynı 2200 birimlik işi paylaşmıştır, ne eksik ne fazla. Süre 2250’den 611’e inmiştir ve inişin tamamı paylaşmadan gelir.

Üçüncü satır aynı verinin, aynı işçi sayısında, aynı sonucu üretmek için ödediği bambaşka bir bedeli gösterir. bolge anahtarına geçmek 2200 satırın 1738‘ini ağdan geçirir; yalnız 462 satır yerinde kalır. Süre 611’den 1914‘e, toplam iş 2200’den 7414’e çıkar. Hesap değişmemiştir: aynı toplamlar, aynı bölgeler, aynı çıktı. Değişen tek şey satırların nerede durduğudur ve o taşınma, işin kendisinden büyük bir kalem yazmıştır. Toplam işin 5214 birimi, yani üçte ikisinden fazlası, hiçbir hesap yapmayan saf hareket bedelidir.

Sürenin neyden oluştuğu burada açık yazılmalıdır. bolge satırındaki 1914 üç kalemin toplamıdır: en yüklü işçinin 561 satırı, taşınan 1738 satırın ağ bedeliyle çarpılıp işçi sayısına bölünmesinden gelen 1303 birim, ve 50 birimlik görev sabiti. Taşıma bedelinin işçi sayısına bölünmesi bir modelleme seçimidir ve ağ trafiğinin işçiler arasında eşit paylaşıldığını varsayar. Gerçek bir kümede tek bir işçi taşımanın büyük payını üstlenebilir ve süre bundan yüksek çıkar. Model bu yüzden karıştırmanın bedelini olduğundan az gösterir; buradaki fark bir alt sınırdır.

Ortadaki satır taşınan satırın anahtardan anahtara değiştiğini gösterir: donem anahtarına geçmek 1651 satır taşır, bolge’ye geçmek 1738. Fark küçüktür ama nedeni açıktır. Bir satırın yerinde kalması, eski anahtarının ve yeni anahtarının aynı işçiye düşmesi demektir. Dört işçi varken bunun beklenen payı dörtte bir, yani 550 satırdır. donem’de yerinde kalan 549 satır tam bu payı verir; bolge’de kalan 462 satır ondan azdır, çünkü bölgeler işçilere eşit dağılmamıştır. Karıştırmanın taşımadığı satır, kurtarılan satır değil, tesadüfen aynı yere düşen satırdır.

Son sütun karıştırmanın ikinci yüzünü açar ve bir sonraki iki dersin konusunu kurar. abone anahtarında dört işçinin yükü 539 ile 561 arasındadır; donem anahtarında 400 ile 600; bolge anahtarında ise 374 ile 1826 arasında ve iki işçi tamamen boştur. Karıştırma yalnız veriyi taşımaz, yeni bir dengesizlik de üretir — sürenin en yüklü işçiye bağlı olması bu dengesizliği doğrudan faturaya yazar.

Tablonun yazılmayan sütunu doğruluktur. Üç kurulumun ürettiği bölge toplamları birebir aynıdır; hangi anahtarla bölüşüldüğünden bağımsız olarak her satır hesaba tam bir kez girer. Bu kursun üçüncü iddiasıdır: sonuç her kurulumda aynıdır, değişen yalnız bedeldir. Çıktıyı denetleyen bir sınama üç kurulumu da geçer ve bolge bölüşümünün 5214 birimlik hareket bedeli hakkında hiçbir şey söylemez. Yanlış bölüşüm bir hata değil bir fiyattır, ve fiyat ancak sayılırsa görünür.

Ağ Bedeli Bir Seçimdir

Yukarıdaki bütün sayıların içinde AG_BEDELI = 3 duruyor. Bu sayı bir ölçüm değildir; ağdan bir satır geçirmenin yerel bir satırı işlemeye göre kaç katına mal olduğunu tek birime indirmek için verilmiş bir karşılıktır. Gerçek bir kümede bu oran ağın hızına, satırın boyuna ve serileştirmenin maliyetine göre değişir. O yüzden sonucun ona ne kadar bağlı olduğu yazılmadan hiçbir şey ölçülmüş sayılmaz. Aşağıdaki blok aynı üç karıştırmayı dört ayrı ağ bedeliyle tekrarlar.

# Bu blok ilk bloktaki satirlar() , izno() , dagit() , karistir() , TUM , KOVA ,
# ISCI ve GOREV_SABIT tanimlarini surdurur. Degisen tek sey AG_BEDELI'dir.
def maliyet_ag(kova, tasinan, ag, isci=ISCI):
    """maliyet() ile ayni hesap , yalniz ag bedeli disaridan veriliyor."""
    n = [len(v) for v in kova.values()]
    return {"sure": max(n) + tasinan * ag // isci + GOREV_SABIT,
            "toplam_is": sum(n) + tasinan * ag}


HEDEF = [(h, karistir(KOVA, h)[1]) for h in ("abone", "donem", "bolge")]
print("ag bedelinden bagimsiz olanlar: tasinan satir " +
      " , ".join(f"{h} {t}" for h, t in HEDEF))
print("\nag bedeli" + "".join(f"{h + ' sure/toplam is':>26}" for h, _ in HEDEF)
      + "   bolge/abone sure")
for ag in (1, 3, 6, 12):
    m = [maliyet_ag(KOVA, t, ag) for _, t in HEDEF]
    print(f"{ag:>9}" + "".join(f"{str(x['sure']) + '/' + str(x['toplam_is']):>26}"
                               for x in m)
          + f"{round(m[2]['sure'] / m[0]['sure'], 2):>19}")

ag bedelinden bagimsiz olanlar: tasinan satir abone 0 , donem 1651 , bolge 1738

ag bedeli      abone sure/toplam is      donem sure/toplam is      bolge sure/toplam is   bolge/abone sure
        1                  611/2200                 1023/3851                 1045/3938               1.71
        3                  611/2200                 1849/7153                 1914/7414               3.13
        6                  611/2200                3087/12106                3218/12628               5.27
       12                  611/2200                5564/22012                5825/23056               9.53

Tablonun ilk satırı, yani başlıktan önceki satır, süpürmenin ön koşuludur: taşınan satır ağ bedelinden bağımsızdır. 0, 1651 ve 1738 dört değerde de aynıdır, çünkü bir satırın işçi değiştirip değiştirmediği anahtarın karmasına bağlıdır, ağın hızına değil. Ağ bedeli yalnızca o sayının kaç birim yazdığını belirler. Ölçümün kendisi ile ölçümün fiyatlandırılması bu tabloda ayrılmıştır.

İkinci duyarsızlık abone sütunundadır: 611 ve 2200 dört satırda da değişmez. Hiç satır taşımayan bir kurulum ağ bedelini hiç ödemez, dolayısıyla o seçime tamamen kayıtsızdır. Bu, bir karar kuralı verir: ağın maliyeti belirsizse, belirsizliğe dokunmayan plan güvenli olandır. Karıştırmasız kurulumun değeri hızlı olmasından çok, tahmininin seçime bağlı olmamasıdır.

Üçüncü sütun duyarlı olanı verir. bolge karıştırmasının süresi 1045’ten 5825‘e, toplam işi 3938’den 23056‘ya taşınır. Son sütun bunu tek sayıya indirir: karıştırmalı kurulum karıştırmasız olana göre ağ bedeli 1’de 1,71 kat, 3’te 3,13 kat, 6’da 5,27 kat, 12’de 9,53 kat pahalıdır. Ağ bedelini iki katına çıkarmak farkı iki katına çıkarmaz, çünkü sürenin içinde bedelden bağımsız bir taban vardır (en yüklü işçinin 561 satırı ve 50 birimlik görev sabiti); büyüyen yalnız taşıma payıdır.

Süpürmenin değiştirmediği son şey sıralamadır. Dört ağ bedelinin hepsinde abone en ucuz, donem ortada, bolge en pahalıdır. Bunun nedeni sürenin taşınan satırda tekdüze artmasıdır: AG_BEDELI pozitif olduğu sürece daha çok taşıyan plan daha pahalıdır ve sıralama değişmez. Dolayısıyla “hangi anahtar daha az taşır” sorusu seçime duyarsız, “ne kadar pahalıya mal olur” sorusu seçime tümüyle duyarlıdır. Bir sonraki derste bu ayrımın sonucu değiştirdiği bir karar görülecek: orada iki plandan biri taşınan satır öder, öbürü ödemez ve hangisinin kazandığı doğrudan AG_BEDELI’nin değerine bağlanır.

Özet

• Karıştırma satırları yeni bir anahtara göre yeniden bölüştürmektir; ölçüsü taşınan satırdır. abone düzeninden abone’ye geçmek 0 satır taşır, donem’e geçmek 1651, bolge’ye geçmek 1738 satır.
• Aynı 2200 satır, aynı dört işçi ve aynı sonuç için süre 611’den 1914’e, toplam iş 2200’den 7414’e çıkar. Toplam işin 5214 birimi hiçbir hesap yapmayan saf hareket bedelidir; hesap üç kurulumda da aynıdır.
• Karıştırmasız bir dağıtık iş mümkündür ve toplam işi tek işçilik tabanla birebir aynı kalır (2200); süre 2250’den 611’e yalnız paylaşmayla iner.
• Karıştırma ikinci bir bedel daha üretir: yeni işçi yükü abone’de 539–561, bolge‘de 374–1826’dır ve iki işçi boş kalır. Süre en yüklü işçiye bağlı olduğu için bu dengesizlik doğrudan faturaya girer.
• Ağ bedeli 1, 3, 6 ve 12 süpürüldüğünde taşınan satır ve karıştırmasız kurulumun 611/2200’ü hiç değişmez; karıştırmalı kurulum 1045/3938’den 5825/23056’ya taşınır ve fark 1,71 kattan 9,53 kata çıkar. Sıralama dört değerde de aynıdır: büyüklük seçimin cinsindendir, sıralama değildir.

Sonraki Adım

Bu dersin bütün ölçümleri tek bir veri kümesi üzerinde yapıldı: 2200 satır bölüştürüldü, yeniden bölüştürüldü ve taşınan satır sayıldı. Oysa dağıtık işlerin çoğu tek bir kümeyi değil, iki kümeyi karşı karşıya getirir — büyük bir olgu tarafı ile küçük bir boyut tarafı. İki tarafın da aynı anahtara göre bölüştürülmüş olması gerekir, yoksa eşleşecek satırlar farklı işçilerde durur. Bunu sağlamanın iki ayrı yolu vardır ve bedelleri bambaşka cinstendir: küçük tarafın her işçiye kopyalanması ya da iki tarafın da karıştırılması. Sonraki ders bu iki stratejiyi boyut tarafı büyütülerek karşılaştırır ve hangisinin ne zaman kazandığını, kazananın değiştiği kesişme noktasını sayarak arar.