Önbellekleme ve Kalıcılık

Önceki üç ders yavaşlığın kaynağını iki başlıkta topladı: veri hareket ediyordu ve yük dengesiz dağılmıştı. Karıştırma 1738 satırı ağdan geçirip toplam işi 2200’den 7414’e çıkardı, birleştirme stratejisi seçimi kesişme noktasını 1600 ile 4000 satır arasına koydu, bolge anahtarı dört işçinin ikisini boş bıraktı ve çarpıklığı 3,32’ye taşıdı. Üçünde de ölçülen şey tek bir işin bir kez koşmasıydı.

Bir küme üzerinde ara sonuçlar bir kez okunmaz. Aynı 2200 satırlık tüketim tablosunu bir sorgu bölge toplamı için, bir başkası abone dökümü için ister. Bu ders iki soruyu sorar: aynı hesabın iki kez yapılması ne kadar tutuyor, ve o hesabı bir kez yapıp saklamaya karar verdiğinizde saklanan şey gerçekten orada duruyor mu.

• DB41. Kaynak, hattın ilk üç aşaması ve dağıtık kurulum kurgudur ve ders içinde üretilir. Hiçbir dağıtık işleme çatısı, küme yöneticisi ya da önbellek ürünü çağrılmaz. Tohum 20260218.
• DB42. Önbellek isabeti, tahliye politikası ve önbellek boyutlandırma yordamı Veritabanları müfredatındaki Bellek İçi Depolar ve Önbellek Sistemleri kursunda, çağrı önbelleği ise Yapay Zekâ Mühendisliği müfredatındaki Model API’leri ile Uygulama Geliştirme kursunda ölçüldü; tekrarlanmaz. Buradaki tek ölçü ara sonucun yeniden kullanılmasıdır.
• DB43. Süre ve toplam iş bu modelin kendi birimidir, ham milisaniye değildir.
• DB44. iki_sorgu hazırlığı toplam iş olarak (bütün satırlar), sorgu adımını işçi başına pay olarak sayar. Bu karışık bir ölçüdür; dersin son bölümü onu ikiye ayırır.
• DB45. Taban çizgisi önbelleksiz kurulumdur: ara sonuç her sorguda yeniden hesaplanır. AG_BEDELI = 3 ve GOREV_SABIT = 50 birer seçimdir.
• DB46. Ara sonucun bellekte tutulması iş olarak sayılmaz; bedeli tutulan satırdır ve o satırlar tutuldukları işçiyle birlikte yiter.

Aynı Hesabın İki Kez Yapılması

İlk blok kaynağı, hattın tüketime kadarki üç aşamasını ve iki sorgunun ölçüsünü kurar. iki_sorgu kursun ortak tanımından gelir; onbellekli onun genellemesidir ve iki uçta aynı sayıları verir.

# KURGUDUR. Olcum aginin sayac okumalari , hattin ilk uc asamasi ve dagitik
# kurulum ders icinde uretilir; hicbir dagitik isleme catisi , kume yoneticisi
# ya da onbellek urunu 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 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
        cikti.append(dict(k, m3=int(k["endeks"]) - int(onceki["endeks"])))
    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 iki_sorgu(kayitlar, onbellek=False, isci=ISCI):
    hazirlik = len(kayitlar)
    if onbellek:
        return {"hesaplama": hazirlik, "sorgu": 2 * (hazirlik // isci),
                "toplam": hazirlik + 2 * (hazirlik // isci)}
    return {"hesaplama": 2 * hazirlik, "sorgu": 2 * (hazirlik // isci),
            "toplam": 2 * hazirlik + 2 * (hazirlik // isci)}


# ---- Ayni olcunun genellemesi: q sorgu , tutulan satir kadar ara sonuc ayakta.
def onbellekli(n, q, tutulan, isci=ISCI):
    """Hazirlik toplam is , sorgu adimi isci basina pay olarak sayilir."""
    hazirlik = n + (q - 1) * (n - tutulan)
    return {"hazirlik": hazirlik, "sorgu": q * (n // isci),
            "toplam": hazirlik + q * (n // isci)}


ARA = satirlar()
N = len(ARA)
print(f"ara sonuc {N} satir , isci {ISCI}")
print(f"iki sorgu  onbelleksiz {iki_sorgu(ARA)['toplam']} "
      f"({iki_sorgu(ARA)['hesaplama']} hazirlik + {iki_sorgu(ARA)['sorgu']} sorgu)"
      f"  onbellekli {iki_sorgu(ARA, True)['toplam']} "
      f"({iki_sorgu(ARA, True)['hesaplama']} + {iki_sorgu(ARA, True)['sorgu']})")
print(f"genelleme  {onbellekli(N, 2, 0)['toplam']} ve {onbellekli(N, 2, N)['toplam']}")
print("\nsorgu sayisi  onbelleksiz  onbellekli  fark")
for q in (1, 2, 3, 4):
    a, b = onbellekli(N, q, 0)["toplam"], onbellekli(N, q, N)["toplam"]
    print(f"{q:>12}  {a:>11}  {b:>10}  {a - b:>4}")

ara sonuc 2200 satir , isci 4
iki sorgu  onbelleksiz 5500 (4400 hazirlik + 1100 sorgu)  onbellekli 3300 (2200 + 1100)
genelleme  5500 ve 3300

sorgu sayisi  onbelleksiz  onbellekli  fark
           1         2750        2750     0
           2         5500        3300  2200
           3         8250        3850  4400
           4        11000        4400  6600

Önbelleksiz kurulumda hazırlık iki kez yapılır: 4400 birimlik hesaplamanın yarısı, ilk sorgunun zaten ürettiği bir tabloyu yeniden üretmektir. Önbellek bu ikinci üretimi siler ve toplam 5500’den 3300’e iner. Kazanılan 2200, ara sonucun kendi satır sayısıdır — daha fazlası değil.

İlk satır bunun sınırını gösterir. Tek sorguda önbelleksiz ve önbellekli kurulum aynı 2750’yi öder; kazanç sıfırdır, çünkü yeniden kullanılan bir hesap yoktur. Önbellek dördüncü sorguda 6600 kazandırır, ama ilkinde yalnız 2200 satırı bellekte tutar ve karşılığında hiçbir şey vermez. Önbelleğin kazancı ara sonucun büyüklüğünden değil, kaç kez okunduğundan gelir. Bir kez okunan sonucu önbelleğe almak, bedeli olan ve kazancı olmayan bir karardır.

Önbellek Tutulmadığında

Buraya kadarki iki sayı önbelleğin orada durduğunu varsaydı. İkinci blok o varsayımı kaldırır. Ara sonuç abone anahtarıyla dört işçiye dağılmıştır ve her işçi kendi payını kendi belleğinde tutar; bir işçi düştüğünde yalnız o pay yiter.

# Bu blok ilk bloktaki ARA , N , ISCI , GOREV_SABIT ve onbellekli tanimlarini surdurur.
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


KOVA = dagit(ARA, "abone")
PAY = [len(KOVA[i]) for i in range(ISCI)]
print(f"ara sonucun isci paylari {PAY}")
print("ayakta isci  tutulan satir  iki sorgunun toplami  onbelleksize gore")
for ayakta in (4, 3, 2, 1, 0):
    t = sum(PAY[:ayakta])
    top = onbellekli(N, 2, t)["toplam"]
    print(f"{ayakta:>11}  {t:>13}  {top:>20}  {top - 5500:>15}")
print("tek isci duserse toplam "
      + " , ".join(str(onbellekli(N, 2, N - p)["toplam"]) for p in PAY))


# ---- Ayni kurulum , iki ayri olcu: sure (isci basina) ve toplam is.
def sure_is(n, q, tutulan, isci=ISCI):
    hazirlik = n + (q - 1) * (n - tutulan)
    return {"sure": hazirlik // isci + q * (n // isci) + q * GOREV_SABIT,
            "toplam_is": hazirlik + q * n}


bos, dolu = sure_is(N, 2, 0), sure_is(N, 2, N)
print("\nolcu          onbelleksiz  onbellekli  kazanc")
for ad, a, b in (("karma toplam", 5500, 3300),
                 ("toplam is", bos["toplam_is"], dolu["toplam_is"]),
                 ("sure", bos["sure"], dolu["sure"])):
    print(f"{ad:<12}  {a:>11}  {b:>10}  {round((a - b) / a * 100, 2):>5} %")

ara sonucun isci paylari [539, 550, 561, 550]
ayakta isci  tutulan satir  iki sorgunun toplami  onbelleksize gore
          4           2200                  3300            -2200
          3           1650                  3850            -1650
          2           1089                  4411            -1089
          1            539                  4961             -539
          0              0                  5500                0
tek isci duserse toplam 3839 , 3850 , 3861 , 3850

olcu          onbelleksiz  onbellekli  kazanc
karma toplam         5500        3300   40.0 %
toplam is            8800        6600   25.0 %
sure                 2300        1750  23.91 %

İlk tablonun son satırı dersin çekirdeğidir: hiç tutulmayan bir önbellek tam olarak 5500 öder, yani önbelleksiz kurulumun bedelini. Ne bir birim fazla ne bir birim eksik. Ama planı yapan kişi 3300’e bakarak karar vermiştir; iş bittiğinde çıkan sonuç aynıdır, sorgular doğrudur, hiçbir denetim ateşlemez ve tek fark ödenen bedeldir. Bu, kursun üçüncü iddiasının bu derse düşen biçimidir: yanlış giden şey çıktıda değil, yalnız sayıda görünür.

Ara satırlar kazancın nasıl eridiğini gösterir. Tutulan satır azaldıkça toplam doğrusal olarak tırmanır ve kazanç her zaman tutulan satır kadardır: 2200 satır ayaktaysa 2200, 1089 satır ayaktaysa 1089. Dörtte üçü ayakta kalan bir önbellek kazancın dörtte üçünü verir. Tek bir işçinin düşmesi bile toplamı 3300’den 3839 ile 3861 arasına taşır; hangi işçinin düştüğü 22 birimlik bir fark yaratır, çünkü paylar 539 ile 561 arasında eşit değildir.

Kalıcılık bu tablonun altındaki karardır. Ara sonucu bellekte tutmak onu işçinin ömrüne bağlar; kalıcı bir yere yazmak, işçi düştüğünde tutulan satırı 2200’de bırakır. Karşılığında yazma işi eklenir ve o iş, satırların ne kadarının gerçekten yeniden okunacağından bağımsız olarak kesin biçimde ödenir. Önbelleğin kazancı olasılıklı, kalıcılığın bedeli kesindir.

Önbelleğin Düzeni

Buraya kadar önbellek bir satır kümesi gibi ele alındı. Dağıtık bir kümede öyle değildir: ara sonuç işçilere bir anahtara göre dağılmış hâlde durur ve o düzen, onu okuyacak sorgunun karıştırmaya ihtiyaç duyup duymayacağını belirler. Üçüncü blok iki sorguyu adlandırır — biri bölge toplamı ister, öbürü abone dökümü — ve önbelleğin hangi düzende tutulduğunu değiştirir.

# Bu blok ilk iki bloktaki ARA , N , KOVA , ISCI , AG_BEDELI , izno ve dagit
# tanimlarini surdurur.
def karistir(kova, yeni_anahtar, isci=ISCI):
    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


BOLGELI, ab_bo = karistir(KOVA, "bolge")
_, bo_ab = karistir(BOLGELI, "abone")
print(f"abone duzeninden bolgeye tasinan {ab_bo} , bolge duzeninden aboneye {bo_ab}")
print("onbellek duzeni     tutulan  4 sorguda tasinan  ag isi")
for ad, tutulan, tasinan in (("abone", N, 2 * ab_bo), ("bolge", N, 2 * bo_ab),
                             ("iki kopya", 2 * N, ab_bo)):
    print(f"{ad:<18}  {tutulan:>7}  {tasinan:>17}  {tasinan * AG_BEDELI:>6}")

abone duzeninden bolgeye tasinan 1738 , bolge duzeninden aboneye 1738
onbellek duzeni     tutulan  4 sorguda tasinan  ag isi
abone                  2200               3476   10428
bolge                  2200               3476   10428
iki kopya              4400               1738    5214

İki yön de aynı 1738 satırı taşır; hangi düzende saklandığı, hangi sorgunun bedava olacağını seçmekten başka bir şey yapmaz. Dört sorgunun ikisi bölge, ikisi abone soruyorsa tek düzenli önbellek 3476 satır taşır ve AG_BEDELI = 3 ile 10428 birimlik ağ işi doğurur. İki kopya tutmak bu sayıyı 5214’e indirir, çünkü ikinci kopya bir kez kurulur ve sonra hiç karıştırılmaz.

Bedel bellekte görünür: tutulan satır 2200’den 4400’e çıkar ve bir önceki bölümün tablosuna göre düşen her işçi artık iki kopyadan da pay götürür. Önbellek burada bir satır kümesi değil, bir satır kümesi artı bir düzendir; ikinci düzeni saklamak ikinci bir önbellek tutmaktır.

Hangi Sayı İndi

İkinci bloğun son tablosu tek bir önbellek kararını üç ölçüyle yazar ve üçü de doğrudur. Karma toplam yüzde 40 kazanç gösterir, çünkü hazırlığı bütün satırlarla, sorguyu işçi başına payla sayar. Toplam iş yüzde 25 gösterir: 8800’den 6600’e inen sayıda sorgu adımı da bütün satırlarla sayılmıştır ve önbellek ona dokunmaz. Süre yüzde 23,91 gösterir; işçi başına düşen hazırlık 1100’den 550’ye iner, ama her sorgu kendi GOREV_SABIT = 50 bedelini yine öder.

Aynı değişikliğin üç ayrı hızlanma sayısı vardır ve aralarındaki en büyük fark yüzde 16’dır. Bir kurulum için “önbellek işi yüzde kırk hızlandırdı” cümlesi, hangi sayının indiğini yazmadıkça doğrulanabilir bir iddia değildir. Süre ile toplam iş ayrı ölçülür; ikisi bu derste aynı yöne gitti, ama bu bir kural değil, bu kurulumun sonucudur.

Özet

• 2200 satırlık ara sonucu paylaşan iki sorgunun toplamı önbelleksiz 5500, önbellekli 3300’dür; kazanılan 2200, ara sonucun kendi satır sayısıdır.
• Tek sorguda iki kurulum da 2750 öder. Önbelleğin kazancı ara sonucun büyüklüğünden değil, kaç kez okunduğundan gelir; bir kez okunan sonucu önbelleğe almak bedeli olan ve kazancı olmayan bir karardır.
• Ara sonuç dört işçide 539, 550, 561 ve 550 satır olarak durur. İşçiler düştükçe toplam 3300’den 3850, 4411, 4961 ve 5500’e çıkar; hiç tutulmayan önbellek tam olarak önbelleksiz kurulumun bedelini öder.
• Kazanç her zaman tutulan satır kadardır ve tek bir işçinin düşmesi toplamı 3839 ile 3861 arasına taşır. Kalıcı yazma tutulan satırı 2200’de bırakır, karşılığında yazma bedeli kesin ödenir.
• Önbellek bir satır kümesi değil, bir satır kümesi artı bir düzendir: iki yön de aynı 1738 satırı taşır, dört sorguda tek düzen 3476 satır ve 10428 birimlik ağ işi doğurur, iki kopya bunu 5214’e indirirken tutulan satırı 2200’den 4400’e çıkarır.
• Aynı önbellek karma toplamda yüzde 40, toplam işte yüzde 25, sürede yüzde 23,91 kazanç gösterir; hangisinin ölçüldüğü yazılmayan hızlanma iddiası eksiktir.

Sonraki Adım

Bu dersin son tablosu bir işçinin düşmesini yalnız önbelleğin yitmesi olarak saydı: kaybolan şey saklanmış bir ara sonuçtu ve yeniden hesaplanabiliyordu. Oysa sürekli akan bir işte işçinin belleğinde duran şey ara sonuç değil, hesabın o ana kadarki durumudur ve o durum yeniden hesaplanmak istendiğinde nereden başlanacağı belli değildir. Sonraki ders düşen işçinin ne kadarını geri istediğini sayar: durumu hiç kaydetmeyen bir işte kaç satırın yeniden hesaplandığını, kayıt sıklığını artırmanın bu sayıyı ne kadar indirdiğini ve aynı satırın iki kez sayılmasını önlemenin neye mal olduğunu.