--- title: 'Karıştırma Maliyeti' source: 'https://academia.sh/tr/kurslar/dagitik-veri-isleme/karistirma-maliyeti' course: 'Dağıtık Veri İşleme' language: tr updated: '2026-08-17T18:08:51+00:00' license: 'CC BY-SA 4.0' --- # Karıştırma Maliyeti Dağıtık bir işin nerede yavaşladığının ilk kez sayılması: aynı 2200 satır abone anahtarıyla bölünmüşken abone anahtarına yeniden bölüştürüldüğünde taşınan satır 0 kalıyor, süre 611 ve toplam iş 2200 oluyor; aynı satırlar bolge anahtarına karıştırıldığında 1738 satır ağdan geçiyor, süre 1914'e ve toplam iş 7414'e çıkıyor, üstelik üç kurulum da birebir aynı sonucu üretiyor. Ağ bedeli 1, 3, 6 ve 12 değerleriyle süpürüldüğünde taşınan satır hiç değişmiyor ve karıştırmasız kurulumun 611 ile 2200'ü de sabit kalıyor, buna karşılık karıştırmalı kurulumun süresi 1045'ten 5825'e ve toplam işi 3938'den 23056'ya taşınıyor; üç anahtarın sıralaması dört değerde de aynı çıkıyor, dolayısıyla sıralama seçime duyarsız, büyüklük tümüyle seçimin cinsinden. Karıştırmanın bedeli hesabın kendisinden değil verinin yerinden oynatılmasından geliyor. 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. ```python # 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. ```python # 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.