Dizin Yaşam Döngüsü

Birleştirme bölüt sayısını denetler, dizinin büyümesini denetlemez. Kırk altı parti sonunda elde kalan tek bölüt, dört yüz partiden sonra dört yüz partilik bir bölüt olur ve her birleştirme onun tamamını yeniden kopyalar. Sürekli akan veride asıl soru şudur: dizin neden tek bir nesne olmak zorunda olsun.

Bu ders dizini zamana göre bölmenin etkisini ölçer. Belirli bir aralıkta yeni bir dizin açmaya devretme denir; eski dizinler yerinde kalır, sorgular gerektiğinde onlara da gider ve saklama süresi dolduğunda dizin bütün olarak düşürülür. Üç şey sayılır: sorgunun kaç dizine gitmek zorunda kaldığı, eski veriyi silmenin kaç bayta mal olduğu ve katmanlı bir yerleşimin bellekte ne tuttuğu.

Zaman Damgalı Dizin ve Devretme

AK13. Yaşam döngüsü kararı zaman damgalı veride anlamlıdır; bu yüzden ders katalog kayıtlarını değil, katalog üzerindeki erişim günlüğünü dizinler. Her kayıt bir günün bir şubesinde belirli terimlerle yapılan erişimi ve o kaydın erişim sayısını taşır. Sorgunun sırası ilgililik puanına değil bu ölçüte göredir: en çok erişilen kayıt başta gelir.

AK16. Gönderi listeleri zaman için ayrıca dizinlenmemiştir; tek dizinde bir gün penceresini uygulamak bütün girişleri taramayı gerektirir. Gerçek bir gerçekleştirim bölüt düzeyinde en küçük ve en büyük günü tutarak dizin içinde de atlayabilir — bu, aşağıdaki atlamanın daha ince taneli hâlidir.

Derlem 180 gün boyunca günde 400 kayıttır: 72.000 belge, tohum 20260731.

// gunluk.mjs — zaman damgalı katalog erişim günlüğü ve devretilebilir dizin
export function uretec(tohum) {               // belirlenimci sözde rastgele üreteç
  let a = tohum >>> 0;
  return () => {
    a = (a + 0x6d2b79f5) >>> 0;
    let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

const KONU = ('edebiyat öykü roman deneme şiir tarih coğrafya felsefe psikoloji ekonomi mimarlık ' +
  'müzik sinema gezi biyografi anı kurgu polisiye folklor dilbilim').split(' ');
const SIFAT = 'sessiz uzak kırık yitik beyaz kara ince derin sarı uzun'.split(' ');
const AD = 'kapı deniz yol ev şehir bahçe ada defter ırmak kuyu'.split(' ');
const SUBE = 'merkez kadıköy bornova çankaya nilüfer'.split(' ');

// her kayıt bir katalog erişimidir: hangi gün, hangi şube, hangi terimlerle, kaç görüntüleme
export function gunlukUret(gunSayisi, gunluk, tohum) {
  const r = uretec(tohum), kayit = [];
  for (let g = 0; g < gunSayisi; g++)
    for (let i = 0; i < gunluk; i++) {
      const terim = [KONU[Math.floor(r() * 20)], SIFAT[Math.floor(r() * 10)],
        AD[Math.floor(r() * 10)], SUBE[Math.floor(r() * 5)]];
      if (r() < 0.4) terim.push(KONU[Math.floor(r() * 20)]);
      kayit.push({ id: 'e' + String(kayit.length).padStart(6, '0'), gun: g, terim,
        erisim: Math.ceil(2 / Math.sqrt(r())) });   // AK14: uzun kuyruklu erişim sayısı
    }
  return kayit;
}

export class Dizin {
  constructor(ad, ilkGun) { this.ad = ad; this.ilkGun = ilkGun; this.sonGun = ilkGun;
    this.sozluk = new Map(); this.belge = new Map(); this.silinen = new Set(); }
  ekle(k) {
    this.sonGun = k.gun; this.belge.set(k.id, k);
    for (const t of new Set(k.terim)) {
      if (!this.sozluk.has(t)) this.sozluk.set(t, []);
      this.sozluk.get(t).push([k.id, k.erisim, k.gun]);   // gönderi girişi: kimlik, ölçüt, gün
    }
  }
  get giris() { let n = 0; for (const g of this.sozluk.values()) n += g.length; return n; }
  get bayt() {
    let s = '';
    for (const [t, g] of this.sozluk) s += t + '\t' + g.map((p) => p.join(':')).join(' ') + '\n';
    for (const id of this.silinen) s += '-\t' + id + '\n';
    return Buffer.byteLength(s);
  }
  yerlesikBayt(katman) {                      // AK15: sözlük girişi terim baytı + 32,
    if (katman === 'soğuk') return 128;       // gönderi girişi 16 bayt; kapalı dizin 128 bayt
    let b = 0;
    for (const t of this.sozluk.keys()) b += Buffer.byteLength(t) + 32;
    return katman === 'ılık' ? b : b + this.giris * 16;
  }
}

export function devret(kayitlar, gunAdim) {   // gunAdim gün dolunca yeni dizin açılır
  const dizinler = [];
  for (const k of kayitlar) {
    const no = Math.floor(k.gun / gunAdim);
    if (!dizinler[no]) dizinler[no] = new Dizin('gunluk-' + no, k.gun);
    dizinler[no].ekle(k);
  }
  return dizinler;
}

// sorgu: gün penceresiyle örtüşmeyen dizin hiç açılmaz; sıra erişim sayısına göredir
export function ara(dizinler, terimler, pencere = null, k = 10) {
  let dokunulan = 0, sozlukAramasi = 0, taranan = 0;
  const aday = new Map();
  for (const d of dizinler) {
    if (pencere && (d.sonGun < pencere[0] || d.ilkGun > pencere[1])) continue;
    dokunulan++;
    for (const t of terimler) {
      sozlukAramasi++;
      const g = d.sozluk.get(t);
      if (!g) continue;
      for (const [id, erisim, gun] of g) {
        taranan++;
        if (pencere && (gun < pencere[0] || gun > pencere[1])) continue;
        if (d.silinen.has(id)) continue;
        aday.set(id, [erisim, gun]);
      }
    }
  }
  const sira = [...aday].sort((a, b) => b[1][0] - a[1][0] || b[1][1] - a[1][1] ||
    (a[0] < b[0] ? -1 : 1));
  return { dokunulan, sozlukAramasi, taranan, eslesen: sira.length,
    ilkK: sira.slice(0, k).map(([id, v]) => [id, v[1]]) };
}

Devretmenin Sorgu Kapsamına Etkisi

Aynı 72.000 kayıt üç dizilime konur: tek dizin, otuz günlük devretme (6 dizin) ve yedi günlük devretme (26 dizin). Her dizilimde aynı sorgu iki kez koşar — bir kez son on dört güne sınırlanmış, bir kez pencere olmadan.

// devretme.mjs — devretme aralığının sorgu kapsamına etkisi
import { gunlukUret, devret, ara } from './gunluk.mjs';

const KAYIT = gunlukUret(180, 400, 20260731);
const SORGU = ['polisiye', 'kadıköy'];

console.log('günlük: 180 gün x 400 kayıt = 72000 kayıt, tohum 20260731 | sorgu: polisiye kadıköy');
console.log('dizilim     dizin  sorgu        dokunulan  sözlük araması  taranan  eşleşen');
for (const [ad, adim] of [['tek dizin', 180], ['30 günlük', 30], ['7 günlük', 7]]) {
  const d = devret(KAYIT, adim);
  for (const [etiket, pencere] of [['son 14 gün', [166, 179]], ['pencere yok', null]]) {
    const c = ara(d, SORGU, pencere);
    console.log(ad.padEnd(11), String(d.length).padStart(5), '', etiket.padEnd(12),
      String(c.dokunulan).padStart(8), String(c.sozlukAramasi).padStart(15),
      String(c.taranan).padStart(8), String(c.eslesen).padStart(8));
  }
}

günlük: 180 gün x 400 kayıt = 72000 kayıt, tohum 20260731 | sorgu: polisiye kadıköy
dizilim     dizin  sorgu        dokunulan  sözlük araması  taranan  eşleşen
tek dizin       1  son 14 gün          1               2    19476     1406
tek dizin       1  pencere yok         1               2    19476    18456
30 günlük       6  son 14 gün          1               2     3188     1406
30 günlük       6  pencere yok         6              12    19476    18456
7 günlük       26  son 14 gün          3               6     1993     1406
7 günlük       26  pencere yok        26              52    19476    18456

Pencereli sorgu üç dizilimde de 1.406 kayıt döndürür: küme değişmez. Değişen, o kümeye ulaşmak için yapılan iştir. Tek dizinde 19.476 gönderi girişi taranır ve bunların yüzde 92’si gün süzgecinde elenir. Yedi günlük devretmede sorgu 26 dizinden yalnız 3’ünü açar ve 1.993 giriş tarar — onda bir. Kazanç taramanın hızlanmasından değil, hiç açılmayan dizinden gelir: örtüşmeyen bir dizinin sözlüğü okunmaz, gönderi listesi belleğe alınmaz.

Aynı tablonun ikinci satırları bedeli gösterir. Pencere olmayan sorguda taranan giriş üç dizilimde de 19.476’dır, ama sözlük araması 2’den 52’ye çıkar. Devretme, zaman penceresi olmayan her sorguya dizin sayısı kadar sabit maliyet ekler; her dizinde terim ayrı ayrı aranır ve her dizinden gelen kısmi sonuç ayrıca birleştirilir. Devretme aralığı bu iki sorgu biçimi arasında bir seçimdir: pencereli sorgular sıklaştıkça kısa aralık kazanır, pencereye sığmayan sorgular ağır bastıkça uzun aralık.

Eski Veriyi Silmenin İki Yolu

Saklama penceresi son 100 gündür (gün 80–179). Tek dizinde bunu uygulamanın tek yolu, 80. günden önceki her belgeye silme işareti koymak ve dizini temizlemektir. Devretmede eski dizinler bütün olarak düşürülür — ama yalnız tamamı pencere dışında kalanlar.

// saklama.mjs — 100 günlük saklama penceresinin iki uygulanışı ve katman yerleşimi
import { gunlukUret, devret, ara } from './gunluk.mjs';

const KAYIT = gunlukUret(180, 400, 20260731);
const ESIK = 80;                              // son 100 gün tutulur: 80..179
const SORGU = ['polisiye', 'kadıköy'];

function temizle(adim) {
  const dz = devret(KAYIT, adim);
  if (adim === 180) {                         // tek dizin: her eski belge silme işareti alır
    const d = dz[0];
    for (const k of KAYIT) if (k.gun < ESIK) d.silinen.add(k.id);
    const okunan = d.bayt;
    const yeni = devret(KAYIT.filter((k) => k.gun >= ESIK), 180);
    return { kalan: yeni, dusen: 0, isaret: d.silinen.size, kopyalanan: okunan + yeni[0].bayt,
      fazla: 0 };
  }
  const kalan = dz.filter((d) => d.sonGun >= ESIK);   // tamamı eski olan dizin düşürülür
  return { kalan, dusen: dz.length - kalan.length, isaret: 0, kopyalanan: 0,
    fazla: kalan.reduce((n, d) => n + [...d.belge.values()].filter((k) => k.gun < ESIK).length, 0) };
}

console.log('saklama penceresi: son 100 gün (gün 80-179), 180 gün x 400 kayıt, tohum 20260731');
console.log('dizilim     düşen dizin  silme işareti  kopyalanan bayt  fazladan tutulan  eşleşen  ilk onda pencere dışı');
const yerlesim = new Map();
for (const [ad, adim] of [['tek dizin', 180], ['30 günlük', 30], ['7 günlük', 7]]) {
  const t = temizle(adim);
  yerlesim.set(ad, t.kalan);
  const c = ara(t.kalan, SORGU, null);
  console.log(ad.padEnd(11), String(t.dusen).padStart(12), String(t.isaret).padStart(14),
    String(t.kopyalanan).padStart(16), String(t.fazla).padStart(17),
    String(c.eslesen).padStart(8), String(c.ilkK.filter(([, g]) => g < ESIK).length).padStart(22));
}

const kalan = yerlesim.get('7 günlük');       // katman yerleşimi 7 günlük devretme üzerinde
const yas = (d) => 179 - d.sonGun;
console.log('\nkatman yerleşimi (7 günlük devretme, temizlik sonrası):');
console.log('yerleşim     sıcak  ılık  soğuk  yerleşik bayt  açılması gereken bayt');
for (const [ad, katmanla] of [['hepsi sıcak', () => 'sıcak'],
  ['üç katman', (d) => (yas(d) < 7 ? 'sıcak' : yas(d) < 30 ? 'ılık' : 'soğuk')]]) {
  const sayi = { sıcak: 0, ılık: 0, soğuk: 0 };
  let bayt = 0, acilacak = 0;
  for (const d of kalan) {
    const k = katmanla(d);
    sayi[k]++; bayt += d.yerlesikBayt(k);
    if (k === 'soğuk') acilacak += d.bayt;
  }
  console.log(ad.padEnd(12), String(sayi['sıcak']).padStart(5), String(sayi['ılık']).padStart(5),
    String(sayi['soğuk']).padStart(6), String(bayt).padStart(14), String(acilacak).padStart(22));
}

saklama penceresi: son 100 gün (gün 80-179), 180 gün x 400 kayıt, tohum 20260731
dizilim     düşen dizin  silme işareti  kopyalanan bayt  fazladan tutulan  eşleşen  ilk onda pencere dışı
tek dizin              0          32000          6985595                 0    10262                      0
30 günlük              2              0                0              8000    12274                      2
7 günlük              11              0                0              1200    10545                      0

katman yerleşimi (7 günlük devretme, temizlik sonrası):
yerleşim     sıcak  ılık  soğuk  yerleşik bayt  açılması gereken bayt
hepsi sıcak     15     0      0        2913702                      0
üç katman        2     3     10         346802                1685859

Maliyet farkı tek satırda görünür. Tek dizinde silme 32.000 belgeye işaret koyar ve temizlik 6.985.595 bayt okuyup yazar; silinen veriden kurtulmanın yolu, kalan verinin tamamını yeniden yazmaktan geçer. Devretmede aynı silme sıfır bayt kopyalar: dizin düşürülür, dosya bütün olarak gider. Bu, bir önceki dersteki birleştirme bedelinin doğrudan kardeşidir — orada kopyalanan bayt bölüt başına ödendi, burada silme başına ödenir.

Devretmenin bedeli granülerliktedir. Otuz günlük aralıkta 60–89 aralığını kapsayan dizinin bir bölümü pencerenin içinde kaldığı için dizin düşürülemez ve 8.000 kayıt saklama penceresi dışında tutulmayı sürdürür; yedi günlük aralıkta bu sayı 1.200’e iner. Fark, ölçülebilir biçimde yanıta sızar. Aynı sorgu tek dizinde 10.262, yedi günlük dizilimde 10.545, otuz günlük dizilimde 12.274 kayıt döndürür: küme yüzde 20 büyümüştür. Sıra da değişir: otuz günlük dizilimde ilk on sonucun ikisi saklama penceresi dışından, silinmiş olması gereken günlerden gelir. Beklenen büyüklük de bunu doğrular — eşleşen kümenin yaklaşık altıda biri pencere dışıdır, ilk onda iki kayıt bu oranla uyumludur. “Yüz günlük veri tutuyoruz” cümlesi, devretme aralığı otuz gün olduğunda 120 güne kadar veri tutmak anlamına gelir.

Sıcak, Ilık ve Soğuk Katmanlar

Kalan on beş dizinin hepsi eşit ilgi görmez: son bir haftanın dizini sürekli sorgulanır, üç ay öncesinin dizini ayda birkaç kez. Katmanlı yerleşim bunu kaynak kararına çevirir. Sıcak katmanda sözlük ve gönderi listeleri bellekte durur; ılık katmanda yalnız sözlük tutulur, gönderi listesi her sorguda diskten okunur; soğuk katmanda dizin kapatılır ve geriye yalnız gün aralığını taşıyan üstveri kalır.

İkinci tablo bunun bedelini verir. Hepsi sıcak yerleşimde on beş dizin 2.913.702 bayt yerleşik bellek tutar. Üç katmanlı yerleşimde iki dizin sıcak, üçü ılık, onu soğuk kalır ve yerleşik bellek 346.802 bayta iner: sekizde bir. Karşılığında soğuk katmandaki on dizine giden bir sorgu, 1.685.859 baytı diskten açmak zorundadır. Katman kararı bu iki sayı arasındadır ve doğrudan bir önceki bölümdeki sorgu biçimine bağlıdır: pencereli sorgular soğuk dizinleri hiç açmaz, pencere olmayan sorgu her seferinde hepsini açar.

Özet

• Zamana göre devretme kümeyi değiştirmez; pencereli sorgu üç dizilimde de 1.406 kayıt döndürdü, ama taranan gönderi girişi 19.476’dan 1.993’e indi çünkü örtüşmeyen dizin hiç açılmadı.
• Devretmenin sabit bedeli pencere olmayan sorgudadır: sözlük araması 2’den 52’ye çıktı, çünkü her dizinde terim ayrı ayrı aranır.
• Tek dizinde 32.000 eski belgeyi silmek 6.985.595 bayt kopyalattı; devretmede aynı silme dizin düşürerek sıfır bayta yapıldı.
• Devretme aralığı saklama granülerliğidir: otuz günlük aralık 8.000 kaydı pencere dışında tuttu, küme 10.262’den 12.274’e çıktı ve ilk on sonucun ikisi silinmiş olması gereken günlerden geldi; yedi günlük aralıkta fazladan tutulan 1.200 kayda indi.
• Üç katmanlı yerleşim yerleşik belleği 2.913.702 bayttan 346.802 bayta indirdi; bedeli, soğuk katmana giden sorgunun açmak zorunda kaldığı 1.685.859 bayttır.

Sonraki Adım

Devretme, dizin düşürmeyi ucuzlattığı gibi bir başka işi de değiştirir. Bölütler ve tamamlanmış dizinler bir daha yazılmaz; yedeklenecek şey durmadan değişen tek bir dosya değil, değişmez dosyalardan oluşan bir kümedir. Sonraki ders bunu ele alır: bir dizinin anlık görüntüsü bölüt düzeyinde artımlı çalışabilir, ama arka planda çalışan birleştirme artımlılığı bozar. Aynı derste geri yükleme ile kaynaktan yeniden dizinleme karşılaştırılır; ölçülecek olan, görüntü başına kopyalanan bayt, geri yüklemenin taşıdığı bayt ile yeniden dizinlemenin işlediği belge sayısı ve çözümleyici değiştiğinde yeniden dizinlemenin kümeyle sırayı nasıl kaydırdığıdır.