--- title: 'Eşle-İndirge Modeli' source: 'https://academia.sh/tr/kurslar/dagitik-veri-isleme/esle-indirge-modeli' course: 'Dağıtık Veri İşleme' language: tr updated: '2026-08-17T18:08:51+00:00' license: 'CC BY-SA 4.0' --- # Eşle-İndirge Modeli Bir hesabın satır başına bağımsız işleyen bir adımla anahtar başına toplayan bir adıma ayrılmasının ve iki adımdan yalnız birinin ağa dokunmasının ölçülmesi: eşleme 2200 satırı yerel işleyip 0 satır taşıyor, süre 611 ve toplam iş 2200 kalıyor, aynı sonucu üreten indirgeme adımı abone düzeninden bölge anahtarına 1738 satır taşıyor ve toplam işi 7414'e, süreyi 1914'e çıkarıyor; her işçi kendi payını taşımadan önce indirgediğinde taşınan satır 20 ara satırdan yalnız 15'i oluyor, toplam iş 2245'e ve süre 622'ye iniyor ve üç kurulumun sunduğu beş bölge toplamı birebir aynı kalıyor. Ö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. ```python # 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. ```python 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. ```python 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. ```python 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.