Dağıtık Analiz Motorları

Önceki ders üç işlevi yazdı ve karışım geçişinde taşınan kaydı saydı, ama işlevleri kimin koşturduğunu sormadı. Gerçek bir küme üzerinde bir veri çerçevesi zinciri yazıldığında zinciri yazan kişi işlemleri sıralar; motor ise o sıralamayı aşamalara böler, her aşama için bölümleri tanımlar, görevleri dağıtır, başarısız görevi yeniden dener ve sonuçları toplar.

Bu işlerin hiçbiri satır işlemez ve hiçbiri zincirde yazmaz. Zinciri yazan kişi bir sorgu yazdığını sanır; motor o sorgudan bir görev çizelgesi çıkarır ve çizelgenin uzunluğu sorgunun uzunluğundan değil, sorgunun hangi noktalarda veriyi yeniden dağıtmak zorunda kaldığından gelir. Dersin ölçüsü budur: eşgüdüm kalemi — iş başına eklenen ve iş boyuyla büyümeyen, sayılabilir kalemler. Yanında duran ikinci sayı, bir eşgüdüm kalemine kaç satır düştüğüdür. Dağıtık sistem kuramı, bölümleme ve eşgüdüm M19 ile M22’de kuruldu ve burada tekrarlanmaz; yazılan tek şey sayılan kalemdir.

• OA13. Hiçbir dağıtık işleme motoru kurulmaz ve hiçbir ürün adı yazılmaz. Zincir, aşama ve kalem standart kitaplıkla modellenir. Modeldir.
• OA14. Bir işlem dardır, yani bölüm içinde biter (süzme, seçme, türetme); ya da geniştir, yani karışım geçişi ister (gruplama, sıralama, birleştirme). Aşama sınırı geniş işlemde çekilir.
• OA15. Eşgüdüm kalemi dört türdür: bölüm tanımı, görev gönderimi, görev sonucu ve aşama toplama. İlk üçü aşama başına bölüm sayısı kadar, sonuncusu aşama başına birer tane sayılır.
• OA16. Bir görevin başarısızlık olasılığı bir varsayımdır ve iki değerle sınanır: 0,02 ve 0,15. En çok üç deneme yapılır; her yeniden deneme iki kalem ekler. Üreteç kendi yazılır, tohum 20260218’dir.
• OA17. Bölüm sayısı iş boyundan türetilir: parça boyu 400.000 satır, en az dört bölüm. İkisi de karardır.
• OA18. Kabul edilebilirlik ölçütü bir karardır: bir eşgüdüm kalemine en az 10.000 satır düşmelidir.

Zincir Kaç Aşamaya Bölünüyor

# zincir.py — bir veri cercevesi zinciri asamalara bolunur. MODELDIR: hicbir
# dagitik motor kurulmaz; zincirin islemleri dar (bolum ici biter) ve genis
# (karisim gecisi ister) diye isaretlenir ve asama siniri genis islemde cekilir.
ZINCIR = [("suz: donem 1-3", "dar"), ("turet: tarife basamagi", "dar"),
          ("grupla: abone", "genis"), ("turet: abone ortalamasi", "dar"),
          ("suz: ortalama > 10 m3", "dar"), ("grupla: bolge", "genis"),
          ("sirala: ortalama", "genis"), ("ilk 3", "dar")]
BOLUM = 8


def asamala(zincir):
    asamalar, su = [], []
    for ad, tur in zincir:
        su.append((ad, tur))
        if tur == "genis":
            asamalar.append(su)
            su = []
    if su:
        asamalar.append(su)
    return asamalar


A = asamala(ZINCIR)
print(f"{len(ZINCIR)} islem, {sum(1 for _, t in ZINCIR if t == 'genis')} genis, "
      f"{len(A)} asama, {BOLUM} bolum")
print(f"{'asama':<7}{'islem':>6}{'sinir':>9}  {'icerik'}")
for i, a in enumerate(A, 1):
    print(f"{i:<7}{len(a):>6}{a[-1][1]:>9}  {' -> '.join(ad for ad, _ in a)}")

# Esgudum kalemi: her asamada her bolum icin bolum tanimi, gorev gonderimi ve
# gorev sonucu; her asama icin bir de asama toplama kalemi.
KALEM = (("bolum tanimi", "bolum"), ("gorev gonderimi", "bolum"),
         ("gorev sonucu", "bolum"), ("asama toplama", "asama"))
print(f"{'kalem turu':<18}{'olcek':>8}{'asama':>7}{'bolum':>7}{'kalem':>7}")
toplam = 0
for ad, olcek in KALEM:
    n = len(A) * BOLUM if olcek == "bolum" else len(A)
    toplam += n
    print(f"{ad:<18}{olcek:>8}{len(A):>7}{BOLUM if olcek == 'bolum' else '-':>7}{n:>7}")
print(f"{'toplam':<18}{'':>8}{'':>7}{'':>7}{toplam:>7}")

8 islem, 3 genis, 4 asama, 8 bolum
asama   islem    sinir  icerik
1           3    genis  suz: donem 1-3 -> turet: tarife basamagi -> grupla: abone
2           3    genis  turet: abone ortalamasi -> suz: ortalama > 10 m3 -> grupla: bolge
3           1    genis  sirala: ortalama
4           1      dar  ilk 3
kalem turu           olcek  asama  bolum  kalem
bolum tanimi         bolum      4      8     32
gorev gonderimi      bolum      4      8     32
gorev sonucu         bolum      4      8     32
asama toplama        asama      4      -      4
toplam                                      100

Zinciri yazan kişi sekiz işlem yazdı; motor dört aşama kurdu. Aşama sayısı zincirde yazmaz, üç geniş işlemden türer ve zincirin okunuşunda görünmez. İkinci aşamanın üç işlemi bir arada durması da bir motor kararıdır: iki dar işlem kendinden önceki karışım geçişinin çıktısı üzerinde çalıştığı için ayrı bir aşamaya gerek kalmıyor.

Bir işlemin dar mı geniş mi sayılacağı da verilmiş bir gerçek değil, bölümleme kararının sonucudur. Zincirin üçüncü işlemi abone anahtarıyla gruplama; küme abone anahtarına göre bölümlenmişse bir abonenin bütün satırları zaten aynı bölümdedir ve gruplama karışım geçişi istemez, yani dar olur. Aynı işlem dönem anahtarına göre bölümlenmiş bir kümede geniştir. Tablodaki dört aşama, kümenin abone anahtarına göre bölümlenmediği varsayımına dayanıyor; bölümleme anahtarı değişince aşama sayısı üçe, eşgüdüm kalemi de aynı oranda iner. Aşama sayısı zincirin değil, zincir ile bölümlemenin birlikte verdiği sayıdır.

Alt tablo dersin ölçüsünü veriyor. Dört aşama ve sekiz bölüm, dört kalem türünde toplam 100 eşgüdüm kalemi ediyor. Bu yüz kalemin hiçbiri bir satır okumaz, bir değer toplamaz, bir grup kurmaz. Hepsi işin çevresindedir ve varlıkları zincirde de sorguda da yazmaz. Kalem sayısı iş boyundan tümüyle bağımsızdır: aynı zincir üç bin satırda da üç milyar satırda da yüz kalem ister.

Dört kalem türünün ne olduğunu ayırmak da gerekiyor, çünkü üçü bölüm sayısıyla, biri aşama sayısıyla ölçekleniyor. Bölüm tanımı, bir aşamada bir bölümün hangi satırlardan sorumlu olduğunun belirlenmesidir. Görev gönderimi, o tanımın bir çalıştırıcıya verilmesidir. Görev sonucu, çalıştırıcının bitirdiğini bildirmesi ve çıktısının kaydedilmesidir. Bu üçü her bölüm için ayrı ayrı sayılır ve bölüm sayısıyla çarpılır. Aşama toplama ise aşamanın bütün bölümlerinin bittiğinin görülmesi ve bir sonraki aşamanın açılmasıdır; aşama başına bir tanedir ve bölüm sayısından etkilenmez. Yüz kalemin doksan altısı ilk üç türden, dördü sonuncudan geliyor.

Yeniden Deneme Baskın Kalem Değildir

# deneme.py — gorev basarisizligi ve yeniden deneme kalemi. Uretec kendi
# yazilir, tohum gorunur; cikti kosumdan kosuma aynidir. MODELDIR: gorev
# basarisizlik olasiligi bir varsayimdir ve iki degerle sinanir.
TOHUM, M32, ENCOK = 20260218, 0xFFFFFFFF, 3


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


def kalem_sayisi(asama, bolum):
    return asama * bolum * 3 + asama


def yeniden_deneme(asama, bolum, q, tohum):
    r, yeniden = uretec(tohum), 0
    for _ in range(asama * bolum):
        for _ in range(ENCOK - 1):
            if r() < q:
                yeniden += 1
            else:
                break
    return yeniden


print(f"en cok {ENCOK} deneme; her yeniden deneme 2 kalem ekler "
      f"(yeniden gonderim ve yeniden sonuc)")
print(f"{'bolum':<8}{'gorev':>7}{'temel kalem':>13}{'q=0.02 ek':>11}"
      f"{'q=0.02 artis':>14}{'q=0.15 ek':>11}{'q=0.15 artis':>14}")
for b in (4, 8, 16, 64, 256):
    g, temel = len(A) * b, kalem_sayisi(len(A), b)
    e1 = 2 * yeniden_deneme(len(A), b, 0.02, TOHUM + 91000 + b)
    e2 = 2 * yeniden_deneme(len(A), b, 0.15, TOHUM + 91000 + b)
    print(f"{b:<8}{g:>7}{temel:>13}{e1:>11}{(temel + e1) / temel:>13.2f}x"
          f"{e2:>11}{(temel + e2) / temel:>13.2f}x")

en cok 3 deneme; her yeniden deneme 2 kalem ekler (yeniden gonderim ve yeniden sonuc)
bolum     gorev  temel kalem  q=0.02 ek  q=0.02 artis  q=0.15 ek  q=0.15 artis
4            16           52          0         1.00x         12         1.23x
8            32          100          0         1.00x          8         1.08x
16           64          196          4         1.02x         24         1.12x
64          256          772          6         1.01x         82         1.11x
256        1024         3076         40         1.01x        336         1.11x

Yeniden deneme, dağıtık işlemenin en görünür kalemidir ve tablo onu en küçük kalem olarak gösteriyor. Yüzde 2’lik başarısızlıkta kalem sayısı en çok yüzde 2 artıyor; yüzde 15’lik başarısızlıkta bile artış yüzde 8 ile 23 arasında kalıyor. İlk satırdaki 1,23 katın diğerlerinden yüksek olması bir eğilim değil, on altı görevlik küçük bir sayımın oynamasıdır — aynı oran 1.024 görevde 1,11 kata oturuyor.

Baskın kalem tablonun üçüncü sütunundadır. Bölüm sayısı dörtten 256’ya çıktığında temel kalem 52’den 3.076’ya, altmış kata yakın büyüyor ve bu büyüme başarısızlıktan değil bölümleme kararından geliyor. Bölüm sayısını artırmak paralellik kazandırır ve aynı hareketle eşgüdüm kalemini doğrusal olarak büyütür. Yeniden deneme bu tablonun gürültüsüdür; kararı veren sayı bölüm sayısıdır.

Kalemin ne olmadığını yazmak da gerekiyor. Eşgüdüm kalemi bir iş birimi değildir; hesabı hızlandıran bir kod değişikliği kalem sayısını düşürmez, çünkü kalemler hesabın içinde değil çevresindedir. Bir bölümün işi on kat hızlansa da o bölüm için hâlâ bir bölüm tanımı, bir görev gönderimi ve bir görev sonucu sayılır. Kalem sayısını düşüren üç karar vardır ve üçü de zincirin kendisinde alınır: aşama sayısını azaltmak, bölüm sayısını azaltmak ve gruplama anahtarını bölümleme anahtarıyla hizalamak.

Kalem Başına Düşen Satır

# olcek.py — kalem sayisi is boyundan bagimsizdir, satir sayisi degildir.
# Olcu: bir esgudum kalemine kac satir dusuyor. HEDEF bir karardir.
import math
HEDEF, PARCA_BOYU, EN_AZ = 10000, 400000, 4
ZINCIR_B = [("suz: donem 1-3", "dar"), ("turet: tarife basamagi", "dar"),
            ("grupla: bolge", "genis"), ("ilk 3", "dar")]
B = asamala(ZINCIR_B)


def bolum_sayisi(n):
    return max(EN_AZ, math.ceil(n / PARCA_BOYU))


def kalem(n, asama):
    b = bolum_sayisi(n)
    return kalem_sayisi(asama, b) + 2 * yeniden_deneme(asama, b, 0.02,
                                                       TOHUM + 91000 + b)


print(f"zincir A {len(A)} asama, zincir B {len(B)} asama; parca boyu "
      f"{PARCA_BOYU} satir, en az {EN_AZ} bolum, hedef {HEDEF} satir/kalem")
print(f"{'is boyu':<14}{'bolum':>7}{'A kalem':>9}{'A satir/kalem':>15}"
      f"{'B kalem':>9}{'B satir/kalem':>15}")
for n in (3199, 31990, 319900, 3199000, 31990000, 319900000):
    ka, kb = kalem(n, len(A)), kalem(n, len(B))
    print(f"{n:<14}{bolum_sayisi(n):>7}{ka:>9}{n / ka:>15.1f}{kb:>9}"
          f"{n / kb:>15.1f}")
esik = {}
for ad, asama in (("A", len(A)), ("B", len(B))):
    n = 1000
    while n / kalem(n, asama) < HEDEF and n < 10 ** 9:
        n += 1000
    esik[ad] = n
print(f"hedefe varan en kucuk is boyu: zincir A {esik['A']} satir, "
      f"zincir B {esik['B']} satir; asamayi yariya indirmek esigi "
      f"{esik['A'] / esik['B']:.1f} kat kuculttu")

zincir A 4 asama, zincir B 2 asama; parca boyu 400000 satir, en az 4 bolum, hedef 10000 satir/kalem
is boyu         bolum  A kalem  A satir/kalem  B kalem  B satir/kalem
3199                4       52           61.5       26          123.0
31990               4       52          615.2       26         1230.4
319900              4       52         6151.9       26        12303.8
3199000             8      100        31990.0       50        63980.0
31990000           80      976        32776.6      490        65285.7
319900000         800     9730        32877.7     4866        65741.9
hedefe varan en kucuk is boyu: zincir A 520000 satir, zincir B 260000 satir; asamayi yariya indirmek esigi 2.0 kat kuculttu

Tablo eşgüdümün ne zaman görünmez kaldığını gösteriyor. Kurgu kümenin 3.199 satırında bir eşgüdüm kalemine 61,5 satır düşüyor: iş, kendisini kuran işten çok daha küçük. Yüz kat büyük bir kümede 31.990 satır düşüyor ve oran doyuyor — son iki satırda 32.777 ve 32.878 çıkıyor, çünkü bölüm sayısı da iş boyuyla birlikte büyüyor ve tavan parça boyunun aşama başına düşen payından geliyor.

Doyum sayısı uydurma değil, iki karardan türer. Bölüm sayısı iş boyunun parça boyuna bölümüdür, kalem sayısı da aşama çarpı bölüm çarpı üçtür; ikisi birbirini götürünce kalem başına düşen satır parça boyunun aşama sayısının üç katına bölümüne oturur. Dört aşamada bu 400.000 bölü 12, yani 33.333 eder ve tabloda 32.878 olarak görünür — aradaki fark aşama toplama kalemleri ile yeniden denemelerden gelir. Parça boyunu büyütmeden ya da aşama sayısını azaltmadan bu tavanın üstüne çıkılamaz; iş boyunu büyütmek belli bir noktadan sonra oranı hiç oynatmaz.

Kabul ölçütü kalem başına 10.000 satır olarak yazıldığında dört aşamalı zincir bu ölçütü 520.000 satırda karşılıyor, iki aşamalı zincir 260.000 satırda. Aşama sayısını yarıya indirmek eşiği tam olarak yarıya indiriyor. Aşama sayısı bir motor ayrıntısı gibi görünür, oysa zincirin yazılışında verilen bir karardır: her geniş işlem bir aşama sınırı çeker ve o sınır bütün bölümler için kalem üretir.

İki zincirin aynı soruyu sormadığını da yazmak gerekiyor. Zincir A önce abone anahtarıyla gruplar, zincir B doğrudan bölge anahtarıyla; önceki dersin ölçtüğü fark buradan gelir — doğu ortalaması 24,814 m³ ile 24,674 m³ arasında 0,140 m³ oynar. Aşama azaltmak bedava değildir; azalttığı şey bazen sorunun kendisidir.

Bu ders M26/K04’ün başarım konusundaki eşikle karıştırılmamalıdır. Orada aynı soru iş birimi cinsinden soruldu ve dağıtımın kazanca döndüğü boy dengeli anahtarda 10.833 satır olarak ölçüldü; ölçülen şey analistin kendi makinesindeki başarımdı. Burada ölçülen şey birim değil kalemdir ve sorulan şey dağıtımın ne zaman ucuzladığı değil, eşgüdümün ne zaman görünmez kaldığıdır. İki eşik farklı sorulara ait ve birbirinin yerine yazılamaz. Bir işin dağıtılması bu iki eşiğin ikisini de geçmek zorundadır: kazanç eşiğini geçmeyen bir iş dağıtıldığında yavaşlar, kalem eşiğini geçmeyen bir iş dağıtıldığında ise çalışır ama işin kendisinden çok çevresine harcanır.

Özet

• Sekiz işlemlik bir zincirin üç geniş işlemi dört aşama sınırı çeker; aşama sayısı zincirde yazmaz ve motor kararıdır.
• Dört aşama ve sekiz bölüm dört kalem türünde 100 eşgüdüm kalemi eder; kalemlerin hiçbiri satır işlemez ve sayıları iş boyundan bağımsızdır.
• Yeniden deneme baskın kalem değildir: yüzde 2’lik başarısızlıkta artış en çok yüzde 2, yüzde 15’lik başarısızlıkta yüzde 8 ile 23 arasındadır.
• Baskın kalem bölümlemedir: bölüm dörtten 256’ya çıktığında temel kalem 52’den 3.076’ya çıkar.
• Bir eşgüdüm kalemine düşen satır 3.199 satırlık işte 61,5, 3.199.000 satırlık işte 31.990’dır ve oran 32.878’de doyar.
• Kalem başına 10.000 satır hedefi dört aşamalı zincirde 520.000, iki aşamalı zincirde 260.000 satırda karşılanır; aşamayı yarıya indirmek eşiği yarıya indirir ama sorulan soruyu da değiştirir.

Sonraki Adım

Bu ders hesabın çevresindeki kalemi saydı, ama hesabın okuduğu veriyi hiç açmadı. Bir aşama başladığında bölümler kendi paylarını bir yerden okur ve o yerin düzeni ne kadar değer okunacağını belirler. Sonraki ders sütunlu dosya düzenini ele alır ve ölçüyü okunan değere bağlar: satır kümesi başlıkları ile sütun sınırları kaç değeri atlatıyor, başlığın kendisi kaç değer okutuyor, aynı sorgu üç düzende kaç değer okuyor ve satır kümesi boyutu bu sayıyı hangi yönde oynatıyor.