Eşle-İndirge Modeli

Önceki iki derste her işçi kendi payını okudu ve kendi payını işledi; hiçbir satır bir işçiden ötekine geçmedi. Bu, yapılan hesapların özel bir sınıftan olmasıyla mümkündü: her satır kendi başına işlenebiliyordu. Tüketim farkı hesaplanırken bir abonenin iki dönemi gerekir, ama aynı abone zaten tek bir işçidedir; ayıklama ve tekilleştirme de satırın kendisine bakar.

Bölge başına toplam gibi bir sonuç istendiğinde bu biter. Bir bölgenin satırları iki yüz aboneye yayılmıştır, aboneye göre bölüşülmüş bir kümede dört işçinin dördüne de düşmüştür ve toplanmadan önce bir araya gelmeleri gerekir. Bu ders hesabı iki adıma ayıran bir model kurar ve tek bir şeyi sorar: hangi adım yerel kalıyor, hangisi ağa dokunuyor.

• DH16. Küme, hat ve iki adımlı model kurgudur; gerçek bir dağıtık işleme çatısı, akış motoru ya da bulut servisi çağrılmaz. Tohum 20260218.
• DH17. Eşle-indirge bir model adıdır ve bir ürünü göstermez. Eşleme adımı her satıra bağımsız olarak bir işlev uygular ve bir (anahtar, değer) çifti üretir; indirgeme adımı aynı anahtarın bütün değerlerini tek bir sonuca katlar.
• DH18. Eşleme adımının satırlar arası bağımlılığı yoktur; bu yüzden veriyi bulunduğu yerde işleyebilir ve ağa dokunmaz.
• DH19. İndirgeme adımı bir anahtarın bütün değerlerinin tek bir işçide toplanmasını ister. Veri o düzende değilse karıştırma doğar ve işçi değiştiren her satır ağdan geçer.
• DH20. Karıştırılan bir satırın bedeli AG_BEDELI yani 3’tür; bu bir seçimdir ve bu derste ölçülen her süre ile toplam iş ona duyarlıdır.
• DH21. Taban çizgisi yine tek işçidir: karıştırma yok, süre 2250, toplam iş 2200.
• DH22. Satırlar derse önceki derslerden geldiği düzende, yani abone anahtarına göre bölüşülmüş olarak girer. Karıştırmanın büyüklüğü bu başlangıç düzenine bağlıdır.
• DH23. Süre bu modelin kendi birimidir ve ham milisaniye değildir; sayılar ancak birbirleriyle karşılaştırıldığında anlam taşır.

İki Adımlı Model

Modelin kurduğu ayrım hesabın kendisinden çıkar. Bir hesabın bir satırını yapmak için başka satırlara bakmak gerekiyor mu sorusunun iki yanıtı vardır ve bu iki yanıt iki adım demektir. Eşleme (map) hayır diyen kısımdır: satırdan bir anahtar ve bir değer çıkarır, komşusuna hiç bakmaz. İndirgeme (reduce) evet diyen kısımdır: bir anahtara ait bütün değerleri ister ve onlar elinde olmadan tek bir doğru sayı üretemez.

Bu ayrımın değeri, hesabın hangi kısmının ağa mal olduğunu önceden söylemesidir. Eşleme adımına kaç işçi eklenirse eklensin ağ trafiği doğmaz. İndirgeme adımının trafiği ise anahtarın seçimine ve verinin girdiği düzene bağlıdır. Aşağıdaki blok modeli üç işlevle kurar: esle çift üretir, yerel_indirge bir işçinin kendi payını katlar, indirge karıştırmadan sonra sonucu toplar.

# KURGUDUR. Kaynak, hat ve kume ders icinde tanimlanir; gercek bir dagitik
# isleme catisi, akis motoru ya da bulut servisi cagrilmaz.
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 a1_ayikla(kayit):
    ZOR = ("abone", "donem", "bolge", "endeks", "birim")
    tut = [k for k in kayit if all(a in k for a in ZOR)]
    return tut, len(kayit) - len(tut)


def a2_tekille(kayit):
    gor, tut = set(), []
    for k in kayit:
        ad = (k["abone"], k["donem"])
        if ad in gor:
            continue
        gor.add(ad)
        tut.append(k)
    return tut, len(kayit) - len(tut)


def a3_tuketim(kayit):
    tablo = {(k["abone"], k["donem"]): k for k in kayit}
    cikti, dusen = [], 0
    for k in kayit:
        i = DONEM.index(k["donem"])
        if i == 0:
            continue
        onceki = tablo.get((k["abone"], DONEM[i - 1]))
        if onceki is None:
            dusen += 1
            continue
        try:
            f = int(k["endeks"]) - int(onceki["endeks"])
        except (TypeError, ValueError):
            dusen += 1
            continue
        cikti.append(dict(k, m3=f))
    return cikti, dusen


ISCI, AG_BEDELI, GOREV_SABIT = 4, 3, 50


def satirlar():
    v, _ = a1_ayikla(kaynak_uret())
    v, _ = a2_tekille(v)
    v, _ = a3_tuketim(v)
    return v


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


def dagit(kayitlar, anahtar, isci=ISCI):
    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}


# ---- KURGU esle-indirge: iki adim
def esle(pay, anahtar_islevi, deger_islevi):
    """Her satirdan bir (anahtar , deger) cifti uretir. Yerel , komsuya bakmaz."""
    return [{"anahtar": anahtar_islevi(k), "deger": deger_islevi(k)} for k in pay]


def yerel_indirge(ciftler):
    """Bir iscinin kendi payindaki ciftleri anahtar basina toplar."""
    top = {}
    for c in ciftler:
        top[c["anahtar"]] = top.get(c["anahtar"], 0) + c["deger"]
    return [{"anahtar": a, "deger": v} for a, v in top.items()]


def indirge(kova):
    """Karistirmadan sonra her isci kendi anahtarlarini toplar , surucu birlestirir."""
    son = {}
    for pay in kova.values():
        for c in yerel_indirge(pay):
            son[c["anahtar"]] = son.get(c["anahtar"], 0) + c["deger"]
    return son

Eşleme Yerel Kalır

İlk ölçüm eşleme adımını tek başına sayar. Satırlar derse abone anahtarına göre bölüşülmüş olarak girer ve eşleme her satırdan bölgeyi anahtar, tüketimi değer olarak çıkarır. Hiçbir işçi başka bir işçinin satırına bakmaz, bu yüzden karistir hiç çağrılmaz ve taşınan satır sıfırdır.

S = satirlar()
K = dagit(S, "abone", ISCI)
ESLENMIS = {i: esle(pay, lambda k: k["bolge"], lambda k: k["m3"]) for i, pay in K.items()}
print("tek isci tabani ->", maliyet(dagit(S, "abone", 1), 0, 1))
print("eslenen cift   :", sum(len(v) for v in ESLENMIS.values()))
print("esleme adimi   ->", maliyet(K, 0))

tek isci tabani -> {'sure': 2250, 'toplam_is': 2200, 'tasinan': 0}
eslenen cift   : 2200
esleme adimi   -> {'sure': 611, 'toplam_is': 2200, 'tasinan': 0}

İki bin iki yüz satırdan iki bin iki yüz çift çıkar; eşleme satır sayısını değiştirmez, satırın biçimini değiştirir. Toplam iş tek işçilik tabandaki gibi 2200‘dür ve dört işçi süreyi 2250’den 611’e indirir. Bu, kursun boyunca görülecek en temiz kazançtır ve sebebi eşlemenin tanımıdır: satırlar arası bağımlılık olmadığı için bölüşüm anahtarı ne olursa olsun hesap doğrudur ve hiçbir satır yer değiştirmez.

Buradan çıkan pratik sonuç şudur: bir hesabın ne kadarının eşleme adımına sığdığı, o hesabın ne kadarının bedavaya paralelleşeceğini söyler. Süzme, alan çıkarma, birim çevirme ve satır başına sınıflandırma bu adıma girer. Girmeyen her şey ikinci adıma kalır.

İndirgeme Ağa Dokunur

İkinci adım aynı anahtarın bütün değerlerini ister. Bölge anahtarı dört işçinin dördüne de yayılmıştır, yani merkez toplamını hesaplayacak işçinin elinde merkez çiftlerinin yalnız dörtte biri vardır. Karıştırma bu yüzden doğar. Aşağıdaki blok iki indirgeme kurulumunu karşılaştırır ve her ikisinin sonucunu tek işçilik tabanla denetler.

ONCEDEN = {i: yerel_indirge(c) for i, c in ESLENMIS.items()}
TABAN = indirge({0: esle(S, lambda k: k["bolge"], lambda k: k["m3"])})
print("ara satir , on-indirgemeden sonra:", sum(len(v) for v in ONCEDEN.values()))
print()
print(f"{'kurulum':<26}{'tasinan':>9}{'sure':>7}{'toplam is':>11}{'sonuc':>17}")
for ad, girdi in (("indirgeme , dogrudan", ESLENMIS),
                  ("indirgeme , on-indirgemeli", ONCEDEN)):
    y, t = karistir(girdi, "anahtar", ISCI)
    m = maliyet(K, t)
    esit = "taban ile ayni" if indirge(y) == TABAN else "farkli"
    print(f"{ad:<26}{t:>9}{m['sure']:>7}{m['toplam_is']:>11}{esit:>17}")
print()
print("taban sonuc:", TABAN)

ara satir , on-indirgemeden sonra: 20

kurulum                     tasinan   sure  toplam is            sonuc
indirgeme , dogrudan           1738   1914       7414   taban ile ayni
indirgeme , on-indirgemeli       15    622       2245   taban ile ayni

taban sonuc: {'merkez': 14536, 'kuzey': 13338, 'dogu': 9695, 'bati': 9164, 'guney': 11721}

Birinci satır iki adımın farkını yazar. Aynı iki bin iki yüz çift, eşleme adımında 0 satır taşırken indirgeme adımında 1738 satır taşır; iki bin iki yüz çiftin dörtte üçü işçi değiştirir. Toplam iş 2200’den 7414‘e çıkar ve süre 611’den 1914’e. Ağdan geçen 1738 satırın bedeli satır başına üç birimdir, yani 5214 birim, ve toplam işteki artışın tamamı budur.

Buradaki sayı hesabın zorluğundan gelmiyor. Bölge toplamı almak, tüketim farkı almaktan daha ağır bir işlem değildir; ağır olan, verinin yanlış anahtara göre bölüşülmüş olmasıdır. Önceki derste bolge anahtarıyla bölüşmenin çarpıklığı 3,32’ye çıkardığı ölçülmüştü. Bedava bir anahtar yoktur: abone bölüşümü eşlemeyi dengeler ve indirgemeyi karıştırmaya zorlar, bolge bölüşümü karıştırmayı sıfırlar ve iki işçiyi boş bırakır.

Ön-İndirgeme Aynı Sonucu Ucuza Üretir

İkinci satır modelin asıl kazancını verir. Her işçi kendi payındaki çiftleri taşımadan önce kendi içinde toplarsa, dört işçiden çıkan iki bin iki yüz çift 20 ara satıra iner: dört işçinin her biri en çok beş bölge için birer kısmi toplam üretir. Karıştırma artık bu yirmi satırı taşır ve bunların 15’i işçi değiştirir. Süre 622, toplam iş 2245 olur; doğrudan karıştırmaya göre toplam iş 7414’ten düşmüş, üç kata yakın bir fark kapanmıştır.

Son sütun üç kurulumda da aynı şeyi söyler. Beş bölge toplamı doğrudan karıştırmada da, ön-indirgemede de tek işçilik tabanla birebir aynıdır. Bu, kursun en rahatsız edici gözlemidir: 7414 birimlik kurulumla 2245 birimlik kurulum aynı çıktıyı verir ve çıktıya bakan hiçbir denetim ikisini ayırt edemez. Yanlış olan hesap değil, bedeldir; bedel ise yalnızca sayılırsa görünür.

Yirmi sayısının nereden geldiği kazancın sınırını da verir. Dört işçinin her biri en çok beş ayrı bölge gördüğü için ön-indirgeme 2200 çifti 20 satıra sıkıştırabilmiştir; anahtarın ayrık değer sayısı büyüdükçe sıkışma azalır. Son blok bunu dört indirgeme anahtarı üzerinde ölçer.

ANAHTAR = (("bolge", lambda k: k["bolge"]),
           ("donem", lambda k: k["donem"]),
           ("bolge+donem", lambda k: k["bolge"] + "|" + k["donem"]),
           ("abone", lambda k: k["abone"]))
print(f"{'indirgeme anahtari':<20}{'ayrik':>7}{'ara satir':>11}"
      f"{'dogrudan':>10}{'on-indirgemeli':>16}{'toplam is':>11}")
for ad, f in ANAHTAR:
    E = {i: esle(pay, f, lambda k: k["m3"]) for i, pay in K.items()}
    O = {i: yerel_indirge(c) for i, c in E.items()}
    _, td = karistir(E, "anahtar", ISCI)
    _, t = karistir(O, "anahtar", ISCI)
    print(f"{ad:<20}{len(set(f(k) for k in S)):>7}{sum(len(v) for v in O.values()):>11}"
          f"{td:>10}{t:>16}{maliyet(K, t)['toplam_is']:>11}")

indirgeme anahtari    ayrik  ara satir  dogrudan  on-indirgemeli  toplam is
bolge                     5         20      1738              15       2245
donem                    11         44      1651              33       2299
bolge+donem              55        220      1653             165       2695
abone                   200        200         0               0       2200

Dördüncü ve üçüncü sütun aynı hesabın iki yazımıdır ve aradaki oran anahtarla birlikte kapanır. Beş ayrık değerli bolge anahtarında taşınan satır 1738’den 15‘e iner; elli beş ayrık değerli bolge+donem anahtarında 1653’ten 165’e iner ve toplam iş 2245 yerine 2695 olur. Sıkışma oranı ara satır sayısıyla belirlenir, o da anahtarın ayrık değer sayısını dört işçiyle çarpar. Ayrık değer sayısı satır sayısına yaklaşırsa ön-indirgeme hiçbir şey sıkıştıramaz ve doğrudan karıştırmayla aynı bedeli öder.

Son satır ayrı bir durumdur. İndirgeme anahtarı bölüşüm anahtarıyla aynı olduğunda, yani abone anahtarına indirgendiğinde, doğrudan yazımda bile taşınan satır 0’dır: her abonenin bütün satırları zaten tek bir işçidedir. Karıştırma bir zorunluluk değil, indirgeme anahtarı ile verinin girdiği düzenin uyuşmamasının bedelidir. Bu satırın toplam işi 2200’dür, yani eşleme adımının kendisiyle aynı.

Ön-indirgemenin bir koşulu vardır ve her hesap onu karşılamaz. İşlemin sırası ve gruplaması değiştirilebilir olmalıdır: toplama böyledir, çünkü kısmi toplamların toplamı bütünün toplamına eşittir. En küçük ve en büyük değer de böyledir. Ortanca değer değildir; bir işçinin payının ortancası hesaplanıp öbürleriyle toplanamaz, çünkü ortanca bütün değerleri görmeyi ister. Tekil değer sayımı da değildir: iki işçinin kendi paylarındaki tekil abone sayıları toplandığında ortak aboneler iki kez sayılır. Bu hesaplarda ya bütün satırlar taşınır, ya da yaklaşık bir sonuç kabul edilir. Model her hesabı ucuzlatmaz; hangilerini ucuzlattığını söyler.

Özet

• Eşle-indirge bir hesabı iki adıma ayırır: eşleme her satıra bağımsız uygulanır ve bir (anahtar, değer) çifti üretir, indirgeme bir anahtarın bütün değerlerini tek bir sonuca katlar.
• Eşleme adımı yereldir. 2200 satır 2200 çift üretir, taşınan satır 0’dır, toplam iş 2200‘de kalır ve dört işçi süreyi 2250’den 611’e indirir.
• İndirgeme adımı ağa dokunur. abone düzeninden bolge anahtarına geçerken 1738 satır işçi değiştirir; toplam iş 7414’e, süre 1914’e çıkar. Artışın tamamı taşınan satırın üç birimlik bedelidir.
• Her işçi kendi payını taşımadan önce indirgediğinde 2200 çift 20 ara satıra iner, bunların 15’i taşınır ve aynı sonuç 2245 toplam iş ile 622 süre karşılığında üretilir.
• Üç kurulumun sunduğu beş bölge toplamı birebir aynıdır. Çıktıya bakan bir denetim 7414 birimlik kurulumla 2245 birimliği ayırt edemez; fark yalnız bedeldedir.
• Ön-indirgeme yalnız sırası ve gruplaması değiştirilebilen işlemlerde geçerlidir. Toplam, en küçük ve en büyük değer uygundur; ortanca ve tekil değer sayımı değildir.

Sonraki Adım

Üç derste iş bölündü, yerleştirildi ve çalıştırıldı. Her ölçümde hesabın tamamı koştu: iki bin iki yüz satırın hepsi eşlendi, hepsi taşındı, hepsi indirgendi. Oysa bir raporun yalnız bir bölgeyi ya da son üç dönemi istediği durumda bu satırların çoğuna hiç dokunulmaması gerekirdi ve hangi hesabın gerçekten gerekli olduğu hiç sorulmadı. İşçilerin kümeye nasıl paylaştırıldığı da sorulmadı; dört işçi her ölçümde hazır varsayıldı. Sonraki iki ders bu iki soruyu ölçer: sonuçta kullanılmayan bir hesap ne kadar satırı hiç dokunulmadan bırakır, ve işçi sayısını artırmanın sabit bedeli nerede kazancı yer.