Dağıtık Dosya Sistemleri

Önceki derste satırlar bir listede hazır duruyordu ve dagit onları işçilere dağıttı. Dağıtmanın bedeli sıfır sayıldı, çünkü liste zaten bellekteydi. Bu varsayım tek makinede doğrudur ve kümede yanlıştır: veri makinelerin diskine dağılmış hâlde durur, bir işçinin işleyeceği satırlar başka bir makinede olabilir ve o satırları görmek için ağdan çekmek gerekir.

Bu ders veriyi bloklara ayırıp kümeye yerleştirir ve tek bir soruyu ölçer: bir bloğu işleyen işçi onu zaten tutuyorsa ne kazanılır. Yanıtın adı veri yerelliğidir (data locality) ve bedeli iki ayrı yerden ödenir, biri süreden biri diskten.

• DH9. Blok yerleşimi ve çoğaltma kurgudur; gerçek bir dağıtık dosya sistemi ürünü, blok sunucusu ya da bulut depolama servisi çağrılmaz. Tohum 20260218.
• DH10. Hattan çıkan 2200 satır sırayla 100 satırlık bloklara ayrılır; 22 blok olur. Blok, bölüşümün çözünürlüğüdür: bir blok bölünmez ve bütünüyle tek bir işçiye gider.
• DH11. Yerleşim kuralı: bir bloğun ilk kopyası anahtarının izinden seçilir, kalan kopyalar halkada sonraki işçilere düşer. Çoğaltma katsayısı (kopya) bir bloğun kaç işçide durduğudur.
• DH12. Bir bloğu okuyan işçi onu tutuyorsa satır başına bedel 1, tutmuyorsa AG_BEDELI yani 3’tür. Bu derste ölçülen her süre ve toplam iş bu seçime duyarlıdır.
• DH13. Çoğaltmanın dayanıklılık yanı, yani bir makine düştüğünde verinin kalması, Veritabanları müfredatının İlişkisel Veritabanı Yönetimi kursunda ve Sistem Tasarımı ve Dağıtık Sistemler müfredatında ölçüldü. Yordam burada tekrarlanmaz; bu ders çoğaltmayı yalnız okumaya olan etkisiyle sayar.
• DH14. Dosya düzeni, sütunlu biçim ve bölümleme Veri Depolama Mimarileri kursunda ölçüldü ve tekrarlanmaz. Buradaki blok bir dosya biçimi değil, yerleştirme birimidir.
• DH15. Taban çizgisi yine tek işçidir: bütün bloklar aynı işçide durur, yerellik tamdır, süre 2250, toplam iş 2200.

Blok ve Yerleşim

Dağıtık bir dosya sisteminin tek makineli bir dosya sisteminden farkı, bir dosyayı bütün olarak saklamamasıdır. Dosya sabit boyutlu bloklara kesilir ve bloklar kümedeki makinelere dağıtılır. Bunun iki sonucu vardır. Birincisi, tek bir makineye sığmayan bir dosya saklanabilir hâle gelir. İkincisi, aynı dosyanın farklı parçaları aynı anda okunabilir, çünkü farklı disklerdedirler.

Blok bir bölünme birimidir, bir bölüm değildir. Blok sınırı satırların anahtarına bakmaz; dosyanın kaçıncı satırında olduğuna bakar. Bu yüzden aynı abonenin satırları iki bloğa yayılabilir ve bir blokta beş bölge birden bulunabilir. Yerleştirme kuralı da veriye bakmaz: bloğun sırasından bir iz üretir ve o izle bir işçi seçer. Kopyalar halkada sonraki işçilere düşer, böylece bir işçinin kaybı tek bir bloğun bütün kopyalarını götürmez.

# KURGUDUR. Kaynak, hat ve dagitik dosya sistemi ders icinde tanimlanir;
# gercek bir dosya sistemi urunu ya da blok sunucusu 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


# ---- KURGU dagitik dosya sistemi: blok , yerlesim , okuma
BLOK = 100


def bloklar(kayitlar, boyut=BLOK):
    """Satirlar sirayla sabit boyutlu bloklara kesilir."""
    return [kayitlar[i:i + boyut] for i in range(0, len(kayitlar), boyut)]


def yerlesim(blok_no, kopya, isci=ISCI):
    """Ilk kopya blogun izinden , kalanlar halkada sonraki isciye."""
    ilk = izno(f"blok{blok_no}") % isci
    return [(ilk + j) % isci for j in range(kopya)]


def okuma(bl, kopya, yerellik, isci=ISCI):
    """Her blogu bir isci okur. Blogu tutmayan isci satirlari agdan ceker."""
    is_yuku = {i: 0 for i in range(isci)}
    yerel = 0
    for b, blok in enumerate(bl):
        tutan = yerlesim(b, kopya, isci)
        okuyan = tutan[0] if yerellik else b % isci
        if okuyan in tutan:
            yerel += 1
            is_yuku[okuyan] += len(blok)
        else:
            is_yuku[okuyan] += len(blok) * AG_BEDELI
    return {"yerel": yerel, "uzak": len(bl) - yerel, "saklanan": len(bl) * kopya,
            "sure": max(is_yuku.values()) + GOREV_SABIT,
            "toplam_is": sum(is_yuku.values())}

Yerellik Bir Rastlantıdır

İlk kurulumda sürücü blokları işçilere sırayla verir: sıfırıncı blok sıfırıncı işçiye, birinci blok birinci işçiye ve böyle devam eder. Bu atama yükü eşitler, çünkü her işçiye yaklaşık aynı sayıda blok düşer. Yerleşimi ise hiç dikkate almaz; bir işçinin okuduğu bloğu tutuyor olması bir rastlantıdır. Aşağıdaki blok o rastlantının kaç blokta gerçekleştiğini çoğaltma katsayısı boyunca sayar.

BL = bloklar(satirlar())
tek = okuma(BL, 1, False, 1)
print("blok:", len(BL), " her biri", BLOK, "satir")
print("tek isci tabani -> sure:", tek["sure"], " toplam is:", tek["toplam_is"])
print()
print(f"{'kopya':>6}{'yerel blok':>12}{'uzak blok':>11}{'saklanan':>10}{'sure':>7}{'toplam is':>11}")
for r in (1, 2, 3, 4):
    o = okuma(BL, r, False)
    print(f"{r:>6}{o['yerel']:>12}{o['uzak']:>11}{o['saklanan']:>10}"
          f"{o['sure']:>7}{o['toplam_is']:>11}")

blok: 22  her biri 100 satir
tek isci tabani -> sure: 2250  toplam is: 2200

 kopya  yerel blok  uzak blok  saklanan   sure  toplam is
     1           5         17        22   1850       5600
     2          17          5        44   1150       3200
     3          22          0        66    650       2200
     4          22          0        88    650       2200

İlk satır dağıtmanın gizli faturasını gösterir. Tek kopyayla yirmi iki bloğun yalnız beşi yerel okunur; kalan on yedi blok ağdan geçer ve her satırı üç kez sayılır. Toplam iş 2200 yerine 5600, süre 1850 olur. Beş sayısı bir rastlantının beklenen değerine yakındır: dört işçide okuyanla tutanın çakışma olasılığı dörtte birdir ve yirmi iki bloğun dörtte biri 5,5’tir. Önceki derste aynı dört işçi süreyi 611’e indirmişti, ama o ölçüm okumayı bedava saymıştı. Okuma sayılınca dört işçili kurulum tek işçilik tabana göre yalnız 2250’den 1850’ye iner; kazanç dörtte bir değil, altıda birden azdır.

İkinci ve üçüncü satırlar çoğaltmanın okumaya ne kattığını verir. Her bloğun iki kopyası olduğunda yerel okunan blok 5’ten 17’ye çıkar ve süre 1150’ye iner; üç kopyada yirmi iki bloğun tamamı yerel okunur, toplam iş 2200’e döner ve süre 650 olur. Ağ trafiği tamamen kaybolur. Bu sayılar AG_BEDELI = 3 seçimine bağlıdır: taşımanın bedeli 1 olsaydı dört satır da aynı toplam işi verirdi ve çoğaltmanın okumaya hiçbir katkısı görünmezdi.

Dördüncü satır çoğaltmanın sınırıdır. Dört kopyada saklanan blok 88’e çıkar, yani veri dört katına, ama yerel blok da süre de üç kopyadakiyle birebir aynı kalır. Üçüncü kopyadan sonra okumaya ödenen hiçbir şey yoktur; dördüncü kopyanın gerekçesi başka bir yerdedir ve o gerekçe dayanıklılıktır. Dayanıklılık bu kursta ölçülmez, önkoşul kurslarda ölçüldü.

Yerellik mi, Denge mi

Yerelliği çoğaltmayla satın almanın bir alternatifi vardır: sürücü blokları sıraya göre değil, onları tutan işçiye verir. Bu atama tek kopyayla bile tam yerellik sağlar. Karşılığında yükün dengesini yerleştirme kuralına devreder ve o kural yükü eşitlemeye çalışmaz. Son blok iki atamayı iki çoğaltma katsayısında karşılaştırır.

print(f"{'atama':<22}{'kopya':>6}{'yerel':>7}{'saklanan':>10}{'sure':>7}{'toplam is':>11}")
for ad, y, r in (("blok sirasi", False, 1), ("blok sirasi", False, 3),
                 ("yerellik farkindali", True, 1), ("yerellik farkindali", True, 3)):
    o = okuma(BL, r, y)
    print(f"{ad:<22}{r:>6}{o['yerel']:>7}{o['saklanan']:>10}"
          f"{o['sure']:>7}{o['toplam_is']:>11}")

atama                  kopya  yerel  saklanan   sure  toplam is
blok sirasi                1      5        22   1850       5600
blok sirasi                3     22        66    650       2200
yerellik farkindali        1     22        22    750       2200
yerellik farkindali        3     22        66    750       2200

Üçüncü satır tek kopyayla tam yerelliği yakalar: yirmi iki bloğun yirmi ikisi yerel okunur, toplam iş 2200’e iner ve saklanan blok 22’de kalır. Aynı sonucu blok sırasına göre atama ancak üç kopyayla, yani 66 blok saklayarak elde eder. Yerellik farkındalı atama üç katı diskten kurtarır.

Buna karşılık süresi 750’dir, blok sırasına göre atamanın üç kopyalı hâlinden 100 birim fazla. Sebep tabloda görünmez ama yerleşim kuralındadır: bloklar işçilere eşit dağılmamıştır ve en çok blok tutan işçi yedi blok, en az tutan dört blok okur. Yerellik farkındalı atama okuyanı seçemez, çünkü seçerse yerellik bozulur. Dördüncü satır bunu bir kez daha yazar: çoğaltmayı üçe çıkarmak yerellik farkındalı atamada süreyi hiç değiştirmez, çünkü ilk kopyayı tutan işçi değişmemiştir.

İki satırın arasındaki seçim tek bir sayıya indirgenemez. Yüz birimlik süre için kırk dört fazla blok saklanır, ya da kırk dört blok yerine yüz birim süre ödenir. Hangisinin daha ucuz olduğu kümenin diskiyle işinin ne kadar sık koştuğuna bağlıdır ve bu karar ancak iki sayı da yazıldığında verilebilir.

Blok Boyutu Bölüşümün Çözünürlüğüdür

Yerellik farkındalı atamanın 750’de kalmasının sebebi tabloda görünmez, çünkü tablo blokların işçilere nasıl düştüğünü yazmaz. Son blok önce o dağılımı basar, sonra blok boyutunu değiştirerek dengenin ne kadarının boyuttan geldiğini ölçer.

S = satirlar()
tutan = {i: 0 for i in range(ISCI)}
for b in range(len(BL)):
    tutan[yerlesim(b, 1)[0]] += 1
print("ilk kopyayi tutan blok sayisi:", [tutan[i] for i in range(ISCI)])
print()
print(f"{'blok boyutu':>12}{'blok':>6}{'yerel':>7}{'sure':>7}{'toplam is':>11}")
for bo in (25, 50, 100, 220, 550):
    bl = bloklar(S, bo)
    o = okuma(bl, 1, True)
    print(f"{bo:>12}{len(bl):>6}{o['yerel']:>7}{o['sure']:>7}{o['toplam_is']:>11}")

ilk kopyayi tutan blok sayisi: [7, 4, 4, 7]

 blok boyutu  blok  yerel   sure  toplam is
          25    88     88    625       2200
          50    44     44    650       2200
         100    22     22    750       2200
         220    10     10    710       2200
         550     4      4    600       2200

İlk satır eksik kalan gerekçeyi verir. Yirmi iki blok dört işçiye 7, 4, 4, 7 olarak düşmüştür; en çok blok tutan işçi yedi blok, yani 700 satır okur ve süre 700 artı 50 sabit bedelle 750 olur. Yerleştirme kuralı yükü eşitlemeye çalışmaz, bloğun izine bakar; dengesizlik bir kusur değil, kuralın doğal sonucudur.

Süpürme bu dengesizliğin blok boyutuyla ilişkisini gösterir. Yirmi beş satırlık bloklarda seksen sekiz blok oluşur ve süre 625’e iner, elli satırlıkta 650 olur: blok küçüldükçe her işçinin payı ortalamaya yaklaşır, çünkü tek bir bloğun yanlış yere düşmesinin ağırlığı azalır. Yerel blok sayısı her satırda blok sayısına eşittir ve toplam iş 2200’de sabittir; blok boyutu ağ trafiğine değil, yalnız dengeye dokunur.

Son iki satır tek yönlü bir kural çıkarmayı engeller. İki yüz yirmi satırlık on blok süreyi 710’a indirir, beş yüz elli satırlık dört blok ise 600’e — yüz satırlık kurulumdan da, yirmi beş satırlıktan da iyidir. Sebebi şudur: dört blok tesadüfen dört ayrı işçiye düşmüştür ve dağılım 1, 1, 1, 1 olmuştur. Küçük blok dengeyi beklenen değerde iyileştirir, tek bir kurulumda garanti etmez. Bu modelde blok küçültmenin görünen bir bedeli de yoktur, çünkü sabit görev bedeli blok başına değil işçi başına bir kez sayılır; gerçek bir kümede her blok bir görev doğurur ve o bedel küçük bloklarda geri gelir.

Özet

• Dağıtık dosya sistemi veriyi sabit boyutlu bloklara keser ve kümeye yayar. 2200 satır 100 satırlık 22 blok olur; blok bölünmez ve bütünüyle tek bir işçiye gider.
• Veri yerelliği, bir bloğu okuyan işçinin onu zaten tutmasıdır. Yerelse satır başına bedel 1, değilse AG_BEDELI yani 3’tür; ölçülen bütün sayılar bu seçime duyarlıdır.
• Blok sırasına göre atamada tek kopyayla 22 bloğun yalnız 5’i yerel okunur: süre 1850, toplam iş 5600. Çoğaltma 2’de yerel blok 17 ve süre 1150, 3’te 22 ve 650 olur.
• Çoğaltmanın okumaya katkısı üçüncü kopyada biter: dört kopyada saklanan blok 88’e çıkar, yerel blok ve süre değişmez. Dördüncü kopyanın gerekçesi dayanıklılıktır ve önkoşul kurslarda ölçüldü.
• Yerellik farkındalı atama tek kopyayla tam yerellik verir (22 yerel blok, 22 saklanan blok) ama yerleşim dengesiz olduğu için süre 650 yerine 750’de kalır. Yerellik ile denge aynı anda satın alınmaz; ikisi de yazılmadan atama seçilemez.
• Blok boyutu dengenin çözünürlüğüdür: 22 blok işçilere 7, 4, 4, 7 düşer, 25 satırlık bloklarda süre 625’e iner. Ama kural tek yönlü değildir; 550 satırlık dört blok tesadüfen dengeli düşerek 600 verir. Küçük blok dengeyi beklenen değerde iyileştirir, garanti etmez.

Sonraki Adım

Bu 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 ancak hesap satır satır yapıldığında mümkündür. Bölge başına toplam gibi bir sonuç istendiğinde aynı bölgenin satırları farklı işçilere dağılmış olur ve toplanmadan önce bir araya gelmeleri gerekir. Sonraki ders hesabı iki adıma ayıran bir modeli kurar ve tek bir soruyu sorar: hangi adım yerel kalıyor, hangisi ağa dokunuyor, ve aynı sonucu üretmenin bedeli bu ayrımla ne kadar değişiyor.