Önbellek Anahtarı Tasarımı

Önceki derste anahtar üç ayrı biçim aldı: önce kitap:7, sonra sürüm taşıyan bir biçim, sonra şubenin nesil sayacını taşıyan bir liste anahtarı. Her seferinde anahtar dizgi birleştirmesiyle elle kuruldu.

Anahtar, önbelleğin tek adresleme mekanizmasıdır. Yanlış kurulduğunda önbellek sessizce yanlış yanıt döndürür — hata vermez, yavaşlamaz, yalnız başka birinin verisini sunar. Bu ders elle birleştirmenin iki kusurunu koşturarak gösterir, ardından anahtarı bir tasarım nesnesi olarak ele alan bir üreteç yazar.

İki Kusur

Ölçümler yedi kitaplık bir katalog üzerinde yapılır. Kitaplardan biri, başlığında iki nokta üst üste taşır; bu, birinci kusuru ortaya çıkarmak için gerekli.

# kur.sh — arama ve liste sorgulari icin kitap verisi (M16/K04 tohumu)
rm -f kutuphane.db
sqlite3 kutuphane.db <<'SQL'
CREATE TABLE sube (sube_id INTEGER PRIMARY KEY, ad TEXT NOT NULL, sehir TEXT NOT NULL);
CREATE TABLE kitap (kitap_id INTEGER PRIMARY KEY, baslik TEXT NOT NULL, yazar TEXT NOT NULL,
                    basim_yili INTEGER, sube_id INTEGER REFERENCES sube(sube_id));
INSERT INTO sube VALUES (1,'Merkez','Ankara'),(2,'Bahçelievler','Ankara'),(3,'Kadıköy','İstanbul');
INSERT INTO kitap VALUES
  (1,'Körlük','José Saramago',1995,1),(2,'Tutunamayanlar','Oğuz Atay',1972,1),
  (3,'Kum Kitabı','Jorge Luis Borges',1975,2),(4,'Yaban','Yakup Kadri',1932,2),
  (5,'Sessiz Ev','Orhan Pamuk',1983,3),(6,'Anayurt Oteli','Yusuf Atılgan',1973,3),
  (7,'Kum: Borges Seçkisi','Derleme',2010,1);
SQL
sqlite3 kutuphane.db "SELECT sube_id, count(*) FROM kitap GROUP BY sube_id;"

1|3
2|2
3|2

Aşağıdaki blok iki senaryo koşturur. Birincisinde arama ölçütleri iki nokta üst üste ile birleştirilir; ikincisinde şube listesi anahtarı yalnız sayfa numarasını taşır.

// carpisma.mjs — elle birlestirilmis anahtarin iki kusuru: cakisma ve kiraci sizintisi
import { DatabaseSync } from "node:sqlite";

const db = new DatabaseSync("kutuphane.db");
const ara = (baslik, yazar) => db.prepare(
  "SELECT baslik FROM kitap WHERE baslik LIKE ? AND yazar LIKE ? ORDER BY kitap_id")
  .all(`%${baslik}%`, `%${yazar}%`).map((k) => k.baslik);
const subeListesi = (subeId, sayfa) => db.prepare(
  "SELECT baslik FROM kitap WHERE sube_id = ? ORDER BY kitap_id LIMIT 2 OFFSET ?")
  .all(subeId, (sayfa - 1) * 2).map((k) => k.baslik);

const kutu = new Map();
const onbellekli = (anahtar, uret) => {
  if (kutu.has(anahtar)) return { anahtar, sonuc: kutu.get(anahtar), kaynak: "onbellek" };
  const sonuc = uret();
  kutu.set(anahtar, sonuc);
  return { anahtar, sonuc, kaynak: "kaynak" };
};

console.log("--- cakisma: iki farkli sorgu ayni anahtara dusuyor");
const a = onbellekli(`arama:Kum:Borges`, () => ara("Kum", "Borges"));
const b = onbellekli(`arama:Kum:Borges`, () => ara("Kum: Borges", ""));
console.log(`A baslik="Kum" yazar="Borges"   anahtar=${a.anahtar} ${a.kaynak}: ${a.sonuc.join(", ")}`);
console.log(`B baslik="Kum: Borges" yazar=""  anahtar=${b.anahtar} ${b.kaynak}: ${b.sonuc.join(", ")}`);
console.log(`B'nin kaynaktan alacagi dogru sonuc: ${ara("Kum: Borges", "").join(", ")}`);

console.log("--- kiraci sizintisi: anahtar sube bilgisini tasimiyor");
const s2 = onbellekli("liste:sayfa:1", () => subeListesi(2, 1));
const s3 = onbellekli("liste:sayfa:1", () => subeListesi(3, 1));
console.log(`sube 2 sayfa 1 -> ${s2.kaynak}: ${s2.sonuc.join(", ")}`);
console.log(`sube 3 sayfa 1 -> ${s3.kaynak}: ${s3.sonuc.join(", ")}`);
const dogru = subeListesi(3, 1);
const sizan = s3.sonuc.filter((x) => !dogru.includes(x));
console.log(`sube 3'e sunulan ama sube 3'e ait olmayan kayit: ${sizan.length} -> ${sizan.join(", ")}`);
db.close();

--- cakisma: iki farkli sorgu ayni anahtara dusuyor
A baslik="Kum" yazar="Borges"   anahtar=arama:Kum:Borges kaynak: Kum Kitabı
B baslik="Kum: Borges" yazar=""  anahtar=arama:Kum:Borges onbellek: Kum Kitabı
B'nin kaynaktan alacagi dogru sonuc: Kum: Borges Seçkisi
--- kiraci sizintisi: anahtar sube bilgisini tasimiyor
sube 2 sayfa 1 -> kaynak: Kum Kitabı, Yaban
sube 3 sayfa 1 -> onbellek: Kum Kitabı, Yaban
sube 3'e sunulan ama sube 3'e ait olmayan kayit: 2 -> Kum Kitabı, Yaban

Birinci kusur bir çakışmadır: ayırıcı olarak kullanılan karakter değerin kendi içinde geçtiği anda iki farklı ölçüt kümesi aynı dizgiyi üretir. İkinci arama önbellekten ilkinin yanıtını aldı ve kimse bunu fark etmedi.

İkinci kusur bir kiracı sızıntısıdır. Kütüphane sisteminde şube bir kiracıdır (tenant): her şube kendi verisini görür. Anahtar şubeyi taşımadığı için Kadıköy şubesinin listesi Bahçelievler’in kitaplarını gösterdi. Kimlik Doğrulama ve Yetkilendirme kursunda sunucu tarafında kurulan yetkilendirme denetimi burada devrede değildir; sorgu hiç çalışmadı, yanıt önbellekten geldi. Önbellek, yetkilendirme denetiminin arkasından dolaşabilen tek katmandır.

Anahtarın Parçaları

İki kusur da anahtarın elle birleştirilmesinden doğdu. Anahtarı üreten tek bir işlev, kuralları tek yerde toplar.

// anahtar.mjs — ad alani, kiraci ve kurallı olcutlerden onbellek anahtari ureten islev
import { createHash } from "node:crypto";

const BICIM = 1;                                   // anahtar bicimi surumu
const kacir = (m) => encodeURIComponent(String(m));

export function anahtarUret({ adAlani, islem, kiraci, nesil = 1, olcutler = {} }) {
  const olcut = Object.entries(olcutler)
    .filter(([, d]) => d !== undefined && d !== null && d !== "")
    .sort(([a], [b]) => (a < b ? -1 : 1))          // sira bagimsiz: ayni olcut kumesi ayni anahtar
    .map(([ad, d]) => `${kacir(ad)}=${kacir(d)}`)
    .join("&");
  const govde = `${kacir(adAlani)}:b${BICIM}:n${nesil}:k${kacir(kiraci)}:${kacir(islem)}`;
  const kuyruk = olcut.length <= 48 ? olcut : `o_${createHash("sha256").update(olcut).digest("hex").slice(0, 16)}`;
  return kuyruk ? `${govde}:${kuyruk}` : govde;
}

if (import.meta.url === `file://${process.argv[1]}`) {
  const A = (o) => anahtarUret({ adAlani: "kutuphane", nesil: 4, ...o });

  console.log("--- cakisan iki sorgu artik ayri anahtarda");
  console.log(A({ islem: "arama", kiraci: "sube-2", olcutler: { baslik: "Kum", yazar: "Borges" } }));
  console.log(A({ islem: "arama", kiraci: "sube-2", olcutler: { baslik: "Kum: Borges", yazar: "" } }));

  console.log("--- kiraci anahtarda: ayni sorgu, ayri sube");
  console.log(A({ islem: "liste", kiraci: "sube-2", olcutler: { sayfa: 1 } }));
  console.log(A({ islem: "liste", kiraci: "sube-3", olcutler: { sayfa: 1 } }));

  console.log("--- olcut sirasi anahtari degistirmiyor");
  const s1 = A({ islem: "arama", kiraci: "sube-1", olcutler: { yazar: "Atay", baslik: "Tutunamayanlar" } });
  const s2 = A({ islem: "arama", kiraci: "sube-1", olcutler: { baslik: "Tutunamayanlar", yazar: "Atay" } });
  console.log(`${s1}\nesit mi: ${s1 === s2}`);

  console.log("--- uzun olcut kumesi ozetleniyor");
  const uzun = A({ islem: "arama", kiraci: "sube-1", olcutler: {
    baslik: "Tutunamayanlar", yazar: "Oğuz Atay", yilBas: 1970, yilSon: 1980,
    dil: "tr", durum: "rafta", siralama: "baslik", sayfa: 3 } });
  console.log(`${uzun}\nuzunluk=${uzun.length}`);
}

--- cakisan iki sorgu artik ayri anahtarda
kutuphane:b1:n4:ksube-2:arama:baslik=Kum&yazar=Borges
kutuphane:b1:n4:ksube-2:arama:baslik=Kum%3A%20Borges
--- kiraci anahtarda: ayni sorgu, ayri sube
kutuphane:b1:n4:ksube-2:liste:sayfa=1
kutuphane:b1:n4:ksube-3:liste:sayfa=1
--- olcut sirasi anahtari degistirmiyor
kutuphane:b1:n4:ksube-1:arama:baslik=Tutunamayanlar&yazar=Atay
esit mi: true
--- uzun olcut kumesi ozetleniyor
kutuphane:b1:n4:ksube-1:arama:o_f350218d0caedc9e
uzunluk=48

Anahtar beş bölümden oluşuyor. Ad alanı aynı önbellek deposunu paylaşan farklı uygulamaları ayırır. Biçim sürümü anahtar yapısının kendisini sürümler: değer biçimi değiştiğinde bu sayı artırılır ve eski biçimdeki bütün girdiler tek hamlede erişilemez olur. Nesil önceki dersteki toplu geçersizleştirmeyi taşır. Kiracı yetki sınırını anahtarın içine yerleştirir. İşlem ve kurallı ölçütler ise sorgunun kimliğidir.

Kurallılık üç kuralla sağlanıyor: boş ölçütler atılır, ölçütler ada göre sıralanır, ad ve değer kaçırılır. Sıralama, aynı sorgunun farklı sırayla gelen ölçütlerle iki ayrı girdi üretmesini engeller. Kaçırma, birinci kusurdaki çakışmayı yapısal olarak imkânsız kılar: değerin içindeki iki nokta üst üste %3A olur ve ayırıcı olmaktan çıkar.

Son bölüm uzunluk sınırıdır. Ölçüt kümesi uzadığında özetlenir, ama anahtarın okunabilir gövdesi korunur. Bu ayrım işletim sırasında değerlidir: önbellekteki bir girdinin hangi uygulamaya, hangi şubeye ve hangi işleme ait olduğu anahtara bakılarak görülür; yalnız hangi ölçütlerle üretildiği görünmez.

Fazla Alan ve Eksik Alan

Anahtarın hangi alanları taşıyacağı bir doğruluk kararıdır ve iki yönde de bozulur.

// kardinalite.mjs — anahtara fazla alan koymak isabeti, eksik alan koymak dogrulugu bozar
import { DatabaseSync } from "node:sqlite";
import { anahtarUret } from "./anahtar.mjs";

const db = new DatabaseSync("kutuphane.db");
const liste = (subeId, sayfa) => db.prepare(
  "SELECT baslik FROM kitap WHERE sube_id = ? ORDER BY kitap_id LIMIT 2 OFFSET ?")
  .all(subeId, (sayfa - 1) * 2).map((k) => k.baslik).join(", ");

const istekler = [];                               // 400 istek, 3 sube x 2 sayfa
for (let i = 0; i < 400; i++) istekler.push([(i % 3) + 1, (i % 2) + 1, `i-${i}`]);

function kosu(ad, anahtarla) {
  const kutu = new Map();
  const o = { isabet: 0, iska: 0, yanlis: 0 };
  for (const [subeId, sayfa, istekKimligi] of istekler) {
    const anahtar = anahtarla(subeId, sayfa, istekKimligi);
    let deger;
    if (kutu.has(anahtar)) { o.isabet += 1; deger = kutu.get(anahtar); }
    else { o.iska += 1; deger = liste(subeId, sayfa); kutu.set(anahtar, deger); }
    if (deger !== liste(subeId, sayfa)) o.yanlis += 1;
  }
  const oran = ((o.isabet / istekler.length) * 100).toFixed(1);
  return `${ad.padEnd(26)}${String(o.isabet).padStart(8)}${String(o.iska).padStart(8)}` +
    `${(oran + "%").padStart(10)}${String(o.yanlis).padStart(9)}${String(kutu.size).padStart(8)}`;
}

const temel = { adAlani: "kutuphane", islem: "liste", nesil: 1 };
console.log(["anahtar bicimi", "isabet", "iska", "oran", "yanlis", "girdi"]
  .map((b, i) => (i === 0 ? b.padEnd(26) : b.padStart(i === 3 ? 10 : i === 4 ? 9 : 8))).join(""));
console.log(kosu("dogru (kiraci + olcut)", (s, y) =>
  anahtarUret({ ...temel, kiraci: `sube-${s}`, olcutler: { sayfa: y } })));
console.log(kosu("fazla alan (istek kimligi)", (s, y, k) =>
  anahtarUret({ ...temel, kiraci: `sube-${s}`, olcutler: { sayfa: y, istek: k } })));
console.log(kosu("eksik alan (kiraci yok)", (s, y) =>
  anahtarUret({ ...temel, kiraci: "ortak", olcutler: { sayfa: y } })));
db.close();

anahtar bicimi              isabet    iska      oran   yanlis   girdi
dogru (kiraci + olcut)         394       6     98.5%        0       6
fazla alan (istek kimligi)       0     400      0.0%        0     400
eksik alan (kiraci yok)        398       2     99.5%      200       2

Fazla alan isabeti sıfırlar. İstek kimliği her istekte farklı olduğu için hiçbir anahtar ikinci kez aranmaz; önbellek dört yüz girdiyle dolar ve tek bir isabet üretmez. Aynı sonucu zaman damgası, oturum kimliği ya da yanıtı etkilemeyen bir başlık da doğurur.

Eksik alanın satırı daha tehlikelidir. İsabet oranı en yüksek olan satır odur — %99,5 — ve dört yüz isteğin ikisi hariç hepsi iki girdiden karşılanmıştır. Aynı satırda iki yüz yanlış yanıt vardır. En yüksek isabet oranı, yanlış gerçekleştirime aittir. İsabet oranı tek başına bir kalite ölçütü değildir; doğruluk ayrıca kanıtlanmalıdır.

Bundan çıkan kural şudur: anahtar, yanıtı değiştiren her girdiyi taşımalı ve değiştirmeyen hiçbir girdiyi taşımamalıdır. Yanıtı değiştirenler arasında yetki bağlamı — kiracı, rol, görünürlük düzeyi — her zaman bulunur. Yanıtı değiştirmeyenler arasında istek kimliği, izleme başlıkları ve oturum belirteci bulunur. Belirtecin anahtara girmesi ayrıca bir güvenlik kusurudur: gizli bir değer, önbellek anahtarlarını listeleyen herkesin görebileceği bir yere yazılmış olur.

Özet

• Ayırıcı karakterle elle birleştirilen anahtar, değerin kendisi o karakteri taşıdığında çakışır; iki farklı arama aynı girdiden karşılandı.
• Anahtar kiracıyı taşımadığında önbellek yetkilendirme denetiminin arkasından dolaşır: bir şubenin listesi başka bir şubeye sunuldu.
• Anahtar üreteci beş bölüm taşır: ad alanı, biçim sürümü, nesil, kiracı ve kurallı ölçütler. Kaçırma çakışmayı, sıralama ise aynı sorgunun iki girdiye bölünmesini önler.
• Uzun ölçüt kümeleri özetlenir, ama okunabilir gövde korunur; girdinin hangi uygulamaya ve hangi kiracıya ait olduğu anahtardan okunabilir kalır.
• Anahtara fazla alan koymak isabeti sıfırladı, eksik alan koymak %99,5 isabetle 200 yanlış yanıt üretti. İsabet oranı tek başına doğruluk kanıtı değildir.

Sonraki Adım

Bu derse kadar bütün ölçümler tek bir işlem sırasında yapıldı: bir istek ıska alır, kaynağa gider, girdiyi koyar, sıradaki istek isabet alır. Gerçek bir sunucuda aynı anahtarı aynı anda yüzlerce istek arar. O anahtarın girdisi düştüğü anda hepsi birden ıska alır ve hepsi birden kaynağa gider; önbelleğin koruduğu kaynak, tam da önbelleğin boşaldığı anda en yüksek yükü görür. Sonraki ders bu davranışı eşzamanlı isteklerle ölçer ve aynı anahtar için kaynağa giden çağrıyı tek bir üretime indiren kilidi kurar.