Veri Çarpıklığı

Bir önceki dersin bütün tablolarında bir sayı sessizce duruyordu: olgu tarafının işçi yükü [374, 0, 0, 1826]. 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ı. İ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.

Bu ders bölüşümün kendisine bakar. Ölçülen şey satırların işçilere ne kadar dengesiz dağıldığı, bu dengesizliğin nereden geldiği ve dengesiz bir bölüşümde işçi eklemenin ne işe yaradığıdır. Sonuncusu bu kursun ikinci iddiasının en açık örneğidir.

• DB19. 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 dosya sistemi çağrılmaz. Tohum 20260218.
• DB20. Veri çarpıklığı (data skew) en yüklü işçinin işçi başına düşen ortalamaya oranıdır. 1,00 kusursuz dengedir; büyüdükçe bir işçi ötekilerden fazla iş yapıyor demektir.
• DB21. Süre en yüklü işçinin işidir, dolayısıyla çarpıklık doğrudan süreye yazılır. Süre bu modelin kendi birimidir. Toplam iş ayrı sayılır.
• DB22. Bölüşüm anahtarın karmasıyla yapılır ve aynı anahtar değeri hep aynı işçiye gider. Bunun iki sonucu vardır: bir anahtar değerinin satırları bölünemez, ve iki ayrı değer aynı işçiye çakışabilir.
• DB23. İndirgeme bütün tablolarda abone anahtarı üzerinden yapılır; değişen tek şey satırların hangi anahtarla bölüştürüldüğüdür. abone bu yüzden doğru, bolge yanlış bölüşüm anahtarıdır.
• DB24. AG_BEDELI = 3 ve GOREV_SABIT = 50 birer seçimdir. Bu dersin çarpıklık sayıları ikisinden de bağımsızdır; süre ve toplam iş sayıları değildir.
• DB25. Taban çizgisi tek işçidir: karıştırma yok, çarpıklık 1,00, süre 2250, toplam iş 2200.
• DB26. Bütün bölüşümler birebir aynı sonucu üretir; ölçülen tek şey bedeldir.
• DB27. Kümenin çözünürlüğü: satır 2200, işçi en çok 16. Dört işçide çarpıklığın adımı 0,0018’dir; bu ölçüde okunan farklar bu adımın çok üstündedir.

Çarpıklık Bölüşümün Ölçüsüdür

Aşağıdaki blok aynı 2200 satırı üç ayrı anahtarla dört işçiye böler, her bölüşümün çarpıklığını hesaplar ve üçünün ürettiği bölge toplamlarını karşılaştırır.

# KURGUDUR. Olcum aginin sayac okumalari , tuketim satirlari ve kume ders icinde
# uretilir; hicbir dagitik isleme catisi ya da kaynak yoneticisi 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. Saglam kaynakta ayikla ve tekille asamalari
    satir dusurmez; tuketim onceki donemin endeksinden cikarilarak 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 yuk(kova):
    """Carpiklik: en yuklu iscinin ortalamaya orani."""
    n = [len(v) for v in kova.values()]
    return {"toplam": sum(n), "en_yuklu": max(n), "en_az": min(n),
            "carpiklik": round(max(n) / (sum(n) / len(n)), 4)}


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 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}


def bolge_toplam(kova):
    """Her isci once kendi payinin bolge toplamini cikarir , sonra birlestirilir."""
    son = {}
    for kayitlar in kova.values():
        ara = {}
        for k in kayitlar:
            ara[k["bolge"]] = ara.get(k["bolge"], 0) + k["m3"]
        for b, v in ara.items():
            son[b] = son.get(b, 0) + v
    return tuple(sorted(son.items()))


TUM = satirlar()
print(f"hattan cikan satir {len(TUM)} , isci {ISCI} , ag bedeli {AG_BEDELI}")
print("bolge basina satir: "
      + " , ".join(f"{b} {sum(1 for k in TUM if k['bolge'] == b)}" for b in BOLGE))
print("bolge hangi isciye dusuyor: " + " , ".join(f"{b} {izno(b) % ISCI}" for b in BOLGE))
print("\nanahtar  farkli deger   isci yuku                en yuklu  en az  carpiklik")
for a in ("abone", "bolge", "donem"):
    k, y = dagit(TUM, a), yuk(dagit(TUM, a))
    print(f"{a:<8} {len(set(x[a] for x in TUM)):>12}   {str([len(v) for v in k.values()]):<24}"
          f"{y['en_yuklu']:>6} {y['en_az']:>6} {y['carpiklik']:>10}")
SONUC = {a: bolge_toplam(dagit(TUM, a)) for a in ("abone", "bolge", "donem")}
print(f"\nuc bolusumun urettigi sonuc tek mi: {len(set(SONUC.values())) == 1}")
print("bolge toplami: " + " , ".join(f"{b} {v}" for b, v in SONUC["abone"]))

hattan cikan satir 2200 , isci 4 , ag bedeli 3
bolge basina satir: dogu 374 , bati 341 , kuzey 506 , guney 440 , merkez 539
bolge hangi isciye dusuyor: dogu 0 , bati 3 , kuzey 3 , guney 3 , merkez 3

anahtar  farkli deger   isci yuku                en yuklu  en az  carpiklik
abone             200   [539, 550, 561, 550]       561    539       1.02
bolge               5   [374, 0, 0, 1826]         1826      0       3.32
donem              11   [600, 600, 400, 600]       600    400     1.0909

uc bolusumun urettigi sonuc tek mi: True
bolge toplami: bati 9164 , dogu 9695 , guney 11721 , kuzey 13338 , merkez 14536

Son iki satır bütün dersin ön koşuludur. Üç bölüşüm de birebir aynı bölge toplamlarını üretir; hangi anahtarla bölüşüldüğünden bağımsız olarak her satır hesaba tam bir kez girer. Bu kursun üçüncü iddiasıdır ve buradaki biçimi en sert olanıdır: sonucu denetleyen hiçbir sınama bolge bölüşümündeki dengesizliği göremez. Çarpıklık bir doğruluk sorunu değil, yalnızca sayıldığında görünen bir bedeldir.

İlk tablo çarpıklığın nereden geldiğini gösterir. abone anahtarında 200 farklı değer vardır, dört işçiye 539 ile 561 arasında dağılırlar ve çarpıklık 1,02’dir. donem anahtarında 11 farklı değer vardır — hattın ilk dönemi tüketim hesaplanamadığı için düşmüştür — ve 11 değer dört işçiye 3, 3, 2, 3 olarak bölündüğü için yük 600, 600, 400, 600 ve çarpıklık 1,0909 olur. bolge anahtarında ise yalnız 5 farklı değer vardır ve çarpıklık 3,32’ye çıkar.

Üçüncü satırın nedeni ikinci satırda yazılıdır. Beş bölgenin dördü de üçüncü işçiye düşer: 341 artı 506 artı 440 artı 539 tam olarak 1826 eder. Geriye kalan tek bölge dogu, tek başına sıfırıncı işçidedir ve iki işçi hiç satır almaz. Burada iki ayrı mekanizma üst üste biner. Birincisi anahtarın azlığıdır: beş farklı değer en çok beş işçiyi doldurabilir. İkincisi karma çakışmasıdır: beş değerden dördü aynı kovaya düşmüştür.

Bunun ayırt edilmesi gereken bir sonucu var. Bölgeler kendi içlerinde çok dengesiz değildir; en küçüğü 341, en büyüğü 539 satır taşır ve aralarındaki oran ikinin altındadır. Yani veri, kendi başına, çarpık değildir. Çarpıklığı üreten şey anahtar ile işçi sayısının birlikte davranışıdır. “Veri çarpıktı” cümlesi bu yüzden eksiktir; çarpıklık verinin bir özelliği değil, bölüşümün bir özelliğidir ve bölüşüm bir karardır.

İşçi Eklemek Bir Çözüm Değildir

Dengesiz bir bölüşümde akla gelen ilk düzeltme daha çok işçidir. Aşağıdaki blok aynı süpürmeyi iki anahtarla yapar: yanlış olanla (bolge) ve doğru olanla (abone). İndirgeme her ikisinde de abone üzerindendir.

# Bu blok ilk bloktaki satirlar() , izno() , dagit() , yuk() , karistir() ,
# maliyet() ve TUM tanimlarini surdurur. Indirgeme her iki tabloda da abone
# anahtari uzerinden yapiliyor; degisen tek sey bolusum anahtari.
def supur(bolusum):
    print(f"bolusum anahtari {bolusum} , indirgeme abone")
    print("isci  carpiklik  en yuklu  bos isci  tasinan   sure  toplam is")
    for isci in (1, 2, 4, 8, 16):
        k = dagit(TUM, bolusum, isci)
        _, t = karistir(k, "abone", isci)
        m, y = maliyet(k, t, isci), yuk(k)
        print(f"{isci:>4} {y['carpiklik']:>10} {y['en_yuklu']:>9}"
              f" {sum(1 for v in k.values() if not v):>9}"
              f" {t:>8} {m['sure']:>6} {m['toplam_is']:>10}")


supur("bolge")
print()
supur("abone")

bolusum anahtari bolge , indirgeme abone
isci  carpiklik  en yuklu  bos isci  tasinan   sure  toplam is
   1        1.0      2200         0        0   2250       2200
   2       1.66      1826         0     1210   3691       5830
   4       3.32      1826         2     1738   3179       7414
   8       6.64      1826         6     1958   2610       8074
  16       6.88       946        13     2145   1398       8635

bolusum anahtari abone , indirgeme abone
isci  carpiklik  en yuklu  bos isci  tasinan   sure  toplam is
   1        1.0      2200         0        0   2250       2200
   2        1.0      1100         0        0   1150       2200
   4       1.02       561         0        0    611       2200
   8       1.04       286         0        0    336       2200
  16        1.2       165         0        0    215       2200

İlk tablonun ikinci satırı bu kursun ikinci iddiasıdır: tek işçide süre 2250 iken, ikinci işçi eklendiğinde 3691‘e çıkar. İşçi eklemek işi kötüleştirmiştir. Nedeni okunabilir: tek işçide karıştırma yoktur, çünkü bütün satırlar zaten aynı yerdedir. İkinci işçi ortaya çıktığı anda indirgeme anahtarı bölüşüm anahtarından ayrışır, 1210 satır ağdan geçer ve toplam iş 2200’den 5830’a sıçrar. Paralellik bedava değildir ve bu düzende ilk adımı negatiftir.

Süre ancak dörtten sonra inmeye başlar, ama tek işçilik tabanın altına ancak on altı işçide iner (1398). Dört işçide 3179, sekiz işçide 2610 — her ikisi de 2250’nin üstündedir. Yani bolge anahtarıyla bölüştürülmüş bir iş, sekiz işçilik bir kümede tek bir işçiden hâlâ yavaştır. Bu tablo yazılmadan “kümeyi büyüttük, hızlandı” cümlesinin doğru olup olmadığı bilinemez.

En yüklü işçi sütunu bunun mekanizmasını verir ve tablonun en çarpıcı sayısı odur: iki, dört ve sekiz işçide en yüklü işçinin yükü 1826’da sabittir. İşçi sayısı dört katına çıkarken o işçi tek bir satır bile devretmez, çünkü ona düşen dört bölge her üç bölüşümde de aynı kovada kalır. Süredeki iniş (3691, 3179, 2610) yükün azalmasından değil, yalnızca taşıma payının daha çok işçiye bölünmesinden gelir. Yük ilk kez on altı işçide kırılır ve 946’ya iner.

Çarpıklık sütunu işçi eklendikçe kötüleşir: 1,66, 3,32, 6,64, 6,88. Boş işçi sayısı 0’dan 2’ye, 6’ya ve 13’e çıkar. On altı işçilik kümede yalnız üç işçi satır almaktadır. Bunun sınırı anahtarın kendisinde yazılıdır: bolge beş farklı değer taşır, dolayısıyla kaç işçi eklenirse eklensin en çok beş işçi satır alabilir. Bir anahtar değerinin satırları bölünemediği için en yüklü işçi de en büyük bölgenin altına, yani 539 satırın altına inemez. Süre bu yüzden kaç işçi eklenirse eklensin görev sabitiyle birlikte 589’un altına inemez. İkinci tablonun on altıncı satırı bunu bir karşılaştırmaya çevirir: abone anahtarıyla süre zaten 215’tir ve o eşiğin çok altındadır. Bölüşüm anahtarı yanlışsa işçi sayısı bir çözüm değildir, çünkü yanlış anahtar kümeye bir tavan koyar.

Çarpıklığın artarken sürenin azalması ilk bakışta çelişkili görünür ve ayrı ayrı okunması gerekir. Çarpıklık bir orandır: işçi sayısı arttıkça ortalama küçülür, en yüklü işçinin yükü ise aynı hızda küçülmez, dolayısıyla oran büyür. Süre bir mutlak sayıdır ve taşıma payı işçilere dağıldığı için düşer. İkisi aynı şeyi söylemez: süre işin ne zaman bittiğini, çarpıklık kaç işçinin boşa ayrıldığını ölçer. On altı işçide 1398 süre, on üç işçinin boş beklemesi ve 8635 birimlik toplam iş karşılığında alınmıştır.

İki tablo yan yana konduğunda kursun kuralı görünür. bolge tablosunda süre 3691’den 1398’e inerken toplam iş 5830’dan 8635’e çıkar; iki ölçü ters yönlere gider ve “dört kat hızlandı” gibi bir cümle hangisinin ölçüldüğü yazılmadan eksiktir. abone tablosunda ise toplam iş beş satırda da 2200’de durur, çünkü taşınan satır her işçi sayısında sıfırdır. Doğru anahtarın kazandırdığı şey yalnız süre değildir: kümeye eklenen her işçinin karşılığında bir şey ürettiği tek düzen budur.

Özet

• Veri çarpıklığı en yüklü işçinin ortalamaya oranıdır: abone bölüşümünde 1,02, donem bölüşümünde 1,0909, bolge bölüşümünde 3,32. Son düzende dört işçinin ikisi boştur ve yük [374, 0, 0, 1826]’dır.
• Çarpıklık verinin değil bölüşümün özelliğidir. Bölgeler 341 ile 539 satır arasındadır, yani veri kendi başına dengelidir; çarpıklığı üreten şey anahtarın yalnız 5 farklı değer taşıması ve bu beş değerden dördünün aynı işçiye çakışmasıdır (341 + 506 + 440 + 539 = 1826).
• İşçi eklemek işi kötüleştirebilir: tek işçide süre 2250, iki işçide 3691‘dir, çünkü ikinci işçiyle birlikte 1210 satır ağdan geçer ve toplam iş 2200’den 5830’a çıkar. Süre tek işçilik tabanın altına ancak on altı işçide iner.
• Yanlış anahtarla işçi eklendikçe çarpıklık 1,66’dan 6,88‘e, boş işçi 0’dan 13’e çıkar. Beş farklı değerli bir anahtar en çok beş işçi doldurabilir ve en büyük bölge 539 satır olduğu için süre 589’un altına hiçbir işçi sayısında inemez; abone anahtarıyla süre on altı işçide zaten 215’tir.
• Üç bölüşüm de bölge toplamlarının birebir aynısını üretir. Doğruluğu denetleyen hiçbir sınama bu farkı göstermez; bolge tablosunda süre 3691’den 1398’e inerken toplam iş 5830’dan 8635‘e çıkar, abone tablosunda toplam iş beş satırda da 2200’de durur.

Sonraki Adım

Üç derste yavaşlığın kaynağı iki başlıkta toplandı: satırların hareketi ve işçilerin dengesizliği. Her iki ölçüde de tek bir hesabın tek bir kez yapıldığı varsayıldı; aynı ara sonuca iki ayrı sorunun ihtiyaç duyması ya da bir işçinin iş bitmeden düşmesi hiç konuşulmadı. Oysa dağıtık bir işte aynı hesabın iki kez yapılması sık rastlanan bir kalemdir ve bir işçinin düşmesi, o ana kadar yapılmış işin ne kadarının geri isteneceği sorusunu doğurur. Sonraki ders ara sonucun saklanmasını ölçer: aynı veriyi iki kez hesaplamakla bir kez hesaplayıp tutmak arasındaki farkı sayar ve tutmanın kendi bedelini yazar.