Bölümleme Stratejileri

Parçalama kararı verildi ve anahtar seçiminin sıcak noktayı belirlediği gösterildi. Karar yarım kaldı. Anahtar seçildikten sonra o anahtarın hangi kurala göre parçalara dağıtılacağı ayrı bir sorudur: aynı takip numarası aralıklara bölünebilir, bir karma işlevinden geçirilebilir ya da her anahtar grubunun yeri ayrı bir tabloda tutulabilir. Üç kural aynı anahtarla üç ayrı yerleşim üretir ve yeniden dengelemeyi üç ayrı biçimde etkiler.

Bölümleme stratejisi (partitioning strategy), bölüm anahtarını bölüm numarasına çeviren kuraldır. İlişkisel Veritabanı Yönetimi kursundaki Tablo Bölümleme dersi aralık, liste ve karma biçimlerinin mekaniğini tek bir motorun içinde kurdu; Parçalama Kalıpları dersi aynı bölümleri ayrı depolara dağıttı. Bu derste mekanik yeniden anlatılmaz — sorulan şey seçimdir: aynı üç erişim örüntüsünde hangi kural hangi sayıyı ne kadar oynatıyor. Terim ayrımı bir cümlede durur: bölümleme tek bir deponun içinde tabloyu parçalara ayırır, parçalama o parçaları ayrı depolara koyar; buradaki kural ikisinde de aynı kuraldır, sonucu farklı yerde görünür.

Üç Kural

Aralık bölümlemesinde (range partitioning) bölüm, anahtarın düştüğü değer aralığıdır. Takip numarası oluşturma sırasına göre artan verildiğinden aralık ekseni zaman eksenidir: ardışık numaralar aynı bölüme düşer.

Karma bölümlemesinde (hash partitioning) bölüm numarası anahtarın karmasından çıkar. Komşu anahtarlar birbirinden uzağa düşer; yerleşimi seçmek diye bir şey yoktur. Önceki dersin kullandığı tutarlı karma bu ailenin bir üyesidir ve yerleşim açısından aynı davranır.

Dizin tablosunda (lookup table) anahtar grubundan bölüm numarasına eşleme ayrı bir tabloda tutulur. Kural aritmetik değil veridir: yerleşim seçilebilir, tek grup için değiştirilebilir ve bir grup gerektiğinde ikiye bölünebilir. Burada grup satıcıdır ve takip numarası satıcı önekini taşır, böylece tekil okuma da dönemsel tarama da aynı eşlemeyi kullanır. Bedel de aynı yerden gelir — her erişim önce eşlemeyi okumak zorundadır.

Ölçüm için üç yeni varsayım gerekir. Bunlar Sistem Tasarımına Giriş kursundaki varsayım tablosuna eklenmez; bu dersin kendi varsayımlarıdır.

Kod	Varsayım	Değer	Gerekçe
D1	satıcı hacim dağılımının üssü	0,9	4000 satıcının (K01: günlük fatura satırı) payı $i^{-0{,}9}$ ile azalır; az sayıda büyük satıcı, uzun bir kuyruk
D2	bölüm sayısı	8	başlangıç kapasitesi; duyarlılığı 16 bölümle ölçülür
D3	etkin pencere	5 gün	okuma ve yazmanın düştüğü gönderi yaşı: teslim edilmiş gönderi ne sorulur ne güncellenir

Üç erişim örüntüsü K01’den gelir: takip numarasına göre tekil okuma, taşıyıcıdan gelen durum olayının yazılması ve satıcının otuz günlük dönem raporu. İlk ikisi D3 nedeniyle aynı gönderi kümesine düşer, bu yüzden aynı dağılımı paylaşır.

// bolum/strateji.mjs — ayni anahtarin uc ayri kuralla bolumlere dagitilmasi.
// MODEL: bolumler birer sayactir, gercek bir kume degildir; sonuclar belirlenimlidir.
export const GUNLUK = 400_000, SAKLAMA = 730, DONEM = 30;   // V3, V12, V11
export const SATICI = 4000, USS = 0.9, PENCERE = 5;         // D1, D3
export const DEPO_ISTEK = 138.89, SAKLANAN_GB = 712.48;     // K01 hesaplari

export function paylar(uss = USS, kat = 1) {
  const p = []; let H = 0;
  for (let i = 1; i <= SATICI; i++) { const a = Math.pow(i, -uss) * (i === 1 ? kat : 1); p.push(a); H += a; }
  return p.map((a) => a / H);
}
export const karma = (n) => {
  let z = Math.imul(n ^ (n >>> 16), 0x21f0aaad) >>> 0;
  z = Math.imul(z ^ (z >>> 15), 0x735a2d97) >>> 0;
  return (z ^ (z >>> 15)) >>> 0;
};
export const oran = (k) => Math.max(...k) / (k.reduce((a, b) => a + b, 0) / k.length);

export function ilkAtama(grup, P) {           // hacme gore azalan sirada en az yuklu bolume
  const yuk = new Array(P).fill(0), yer = new Map();
  for (const x of [...grup].sort((a, b) => b.agirlik - a.agirlik)) {
    let en = 0; for (let p = 1; p < P; p++) if (yuk[p] < yuk[en]) en = p;
    yer.set(x.ad, en); yuk[en] += x.agirlik;
  }
  return yer;
}
export const yukHesap = (grup, yer, P) => {
  const y = new Array(P).fill(0);
  for (const x of grup) y[yer.get(x.ad)] += x.agirlik;
  return y;
};

export function istekAralik(P) {              // bolum = takip numarasinin dustugu numara araligi
  const dilim = (SAKLAMA * GUNLUK) / P, k = new Array(P).fill(0);
  for (let g = SAKLAMA - PENCERE; g < SAKLAMA; g++)
    for (let s = 0; s < GUNLUK; s += 1000) k[Math.floor((g * GUNLUK + s) / dilim)] += 1000;
  return k;
}
export function istekKarma(P) {               // bolum = takip numarasinin karmasi
  const k = new Array(P).fill(0);
  for (let g = SAKLAMA - PENCERE; g < SAKLAMA; g++)
    for (let s = 0; s < GUNLUK; s++) k[karma(g * GUNLUK + s) % P] += 1;
  return k;
}

export function tablo(P) {
  const grup = paylar().map((a, i) => ({ ad: `${i}`, agirlik: a }));
  const D = yukHesap(grup, ilkAtama(grup, P), P);
  const enYuklu = Math.max(...D) / D.reduce((a, b) => a + b, 0);
  return [
    ["aralik", oran(istekAralik(P)), 1, DONEM * GUNLUK, 1],
    ["karma", oran(istekKarma(P)), P, DONEM * GUNLUK, 1],
    ["dizin tablosu", oran(D), 1, Math.round(DONEM * GUNLUK * enYuklu), 2],
  ];
}

if (import.meta.filename === process.argv[1]) {
  const pay = paylar();
  console.log(`D1: ${SATICI} satici, en buyugun payi %${(pay[0] * 100).toFixed(2)}, ` +
    `ilk sekiz %${(pay.slice(0, 8).reduce((a, b) => a + b, 0) * 100).toFixed(2)}, ` +
    `en kucuk gunde ${(GUNLUK * pay[SATICI - 1]).toFixed(1)} gonderi`);
  for (const P of [8, 16]) {
    console.log(`\nP = ${P} bolum`);
    console.log("strateji         istek sicak nokta  donem raporu bolum  taranan kayit  depo dokunusu");
    for (const [ad, i, b, t, d] of tablo(P))
      console.log(ad.padEnd(17) + i.toFixed(2).padStart(17) + String(b).padStart(20) +
        t.toLocaleString("tr-TR").padStart(15) + String(d).padStart(15));
  }
  console.log(`\nK01 donusu: depoya ulasan ${DEPO_ISTEK} istek/s, saklanan ${SAKLANAN_GB} GB, P = 8`);
  for (const [ad, i, , , d] of tablo(8))
    console.log(`  ${ad.padEnd(15)} en yuklu bolum ${(DEPO_ISTEK * i / 8).toFixed(2).padStart(6)} istek/s` +
      ` ve ${(SAKLANAN_GB / 8).toFixed(2)} GB | depoya ulasan toplam ${(DEPO_ISTEK * d).toFixed(2)} istek/s`);
}

D1: 4000 satici, en buyugun payi %7.41, ilk sekiz %21.92, en kucuk gunde 17.0 gonderi

P = 8 bolum
strateji         istek sicak nokta  donem raporu bolum  taranan kayit  depo dokunusu
aralik                        8.00                   1     12.000.000              1
karma                         1.00                   8     12.000.000              1
dizin tablosu                 1.00                   1      1.500.137              2

P = 16 bolum
strateji         istek sicak nokta  donem raporu bolum  taranan kayit  depo dokunusu
aralik                       16.00                   1     12.000.000              1
karma                         1.00                  16     12.000.000              1
dizin tablosu                 1.19                   1        889.566              2

K01 donusu: depoya ulasan 138.89 istek/s, saklanan 712.48 GB, P = 8
  aralik          en yuklu bolum 138.89 istek/s ve 89.06 GB | depoya ulasan toplam 138.89 istek/s
  karma           en yuklu bolum  17.42 istek/s ve 89.06 GB | depoya ulasan toplam 138.89 istek/s
  dizin tablosu   en yuklu bolum  17.36 istek/s ve 89.06 GB | depoya ulasan toplam 277.78 istek/s

Sayılar hesap sınıfındadır: D1–D3 ile K01’in varsayımlarından aritmetikle çıkarlar, hiçbiri ortama bağlı değildir.

Tabloda Kimse Kazanmıyor

Sıcak nokta sütunu en yüklü bölümün yükünü bölüm başına ortalamaya böler; 1,00 tam denge, 8,00 da sekiz bölümün yalnız birinin çalışması demektir.

Aralık bölümlemesi bölünmüş bir depoda hiçbir şeyi bölmüyor. Oran 8,00. Neden D3’tedir: okunan ve yazılan gönderiler son beş günün gönderileridir, ardışık takip numaraları aynı aralığa düştüğü için hepsi son bölüme iner. Diğer yedi bölüm 725 günlük veriyi taşıyor ve hemen hiç istek görmüyor. Saklama sütunu bunu doğruluyor: saklanan 712,48 GB sekiz bölüme eşit bölünmüş, bölüm başına 89,06 GB. Aralık bölümlemesi depolamayı dengeler, isteği dengelemez — ve K01’in oynatmak istediği satır istek satırıdır.

Karma bölümlemesi isteği dengeliyor, sorguyu dağıtıyor. Oran 1,00: on iki milyon takip numarasının karması sekiz bölüme neredeyse eşit düşüyor. Bedel dönem raporu sütununda: satıcının kayıtları sekiz bölüme dağıldığı için otuz günlük rapor sekiz bölüme birden dokunuyor. Toplam taranan kayıt aynı kalıyor (12.000.000), ama sorgu Parçalama Kalıpları dersinde ölçülen dağıt–topla davranışına giriyor.

Dizin tablosu ikisini de veriyor, karşılığında bir dokunuş alıyor. Satıcılar hacme göre azalan sırada en az yüklü bölüme yerleştirildiğinde oran 1,00 çıkıyor ve bir satıcının bütün kayıtları tek bölümde kaldığı için dönem raporu bir bölüme dokunuyor. Taranan kayıt 12.000.000 yerine 1.500.137: taranan pencere aynı otuz gün, ama o bölümde yalnız oraya atanmış satıcıların kayıtları var. Sekiz kat azalma buradan gelir.

Bedel son sütunda duruyor. Her erişim önce eşlemeyi okuyor, sonra veriye gidiyor: erişim başına iki depo dokunuşu. K01’in depoya ulasan istek/s satırı bu yüzden 138,89’dan 277,78’e çıkıyor. İki sayı birlikte okunmalıdır: en yüklü bölümün yükü 138,89’dan 17,36’ya inerken depoya ulaşan toplam istek iki katına çıktı. Üstelik dizin tablosunun kendisi bu isteğin tamamını görüyor, yani sekiz bölümün yükünü dengelemek için dokuzuncu bir sıcak nokta kuruldu. Bu tablonun bellekte tutulup tutulmayacağı bir önbellek kararıdır ve sonraki konunun sorusudur.

P = 16 satırları duyarlılığı veriyor. Aralığın oranı 16,00’ya çıkıyor: bölüm eklemek sıcak noktayı büyütüyor. Dizin tablosunun taranan kaydı 889.566’ya inerken oranı 1,19’a çıkıyor, çünkü en büyük satıcının payı yüzde 7,41 ve bu, bir bölümün payı olan yüzde 6,25’in üstünde.

Yeniden Dengeleme

Yerleşim bir kez kurulup bırakılmaz. Bir satıcı büyüdüğünde üç strateji üç ayrı şey yapar.

// bolum/dengele.mjs — en buyuk satici uc katina ciktiginda uc stratejinin davranisi.
// MODEL: yeniden dengeleyici, mevcut yerlesimden baslayip en yuklu bolumden en az yukluye
// tek grup tasir; tasinan agirlik toplanir. Sonuclar belirlenimlidir.
import { paylar, ilkAtama, yukHesap, oran, istekAralik, istekKarma, SATICI, DONEM }
  from "./strateji.mjs";
const P = 8, KAT = 3, HEDEF = 1.20;

function enAzTasima(grup, yer0, hedef) {
  const yer = new Map(yer0), y = yukHesap(grup, yer, P);
  let tasinan = 0, adim = 0;
  while (oran(y) > hedef) {
    let h = 0, c = 0;
    for (let p = 1; p < P; p++) { if (y[p] > y[h]) h = p; if (y[p] < y[c]) c = p; }
    const aday = grup.filter((x) => yer.get(x.ad) === h && y[c] + x.agirlik < y[h])
      .sort((a, b) => b.agirlik - a.agirlik)[0];
    if (aday === undefined) break;
    yer.set(aday.ad, c); y[h] -= aday.agirlik; y[c] += aday.agirlik;
    tasinan += aday.agirlik; adim += 1;
  }
  return { yer, oran: oran(y), tasinan, adim };
}
const bicim = (r) => `oran ${r.oran.toFixed(3)} | tasinan anahtar %${(r.tasinan * 100).toFixed(2)}` +
  ` | ${r.adim} tasima`;

const once = paylar(), sonra = paylar(0.9, KAT);
const gSonra = sonra.map((a, i) => ({ ad: `${i}`, agirlik: a }));
const yer0 = ilkAtama(once.map((a, i) => ({ ad: `${i}`, agirlik: a })), P);
console.log(`en buyuk satici payi %${(once[0] * 100).toFixed(2)} -> %${(sonra[0] * 100).toFixed(2)}`);
const [oA, oK] = [oran(istekAralik(P)), oran(istekKarma(P))];   // ikisi de saticidan bagimsiz
console.log(`aralik: oran ${oA.toFixed(2)} -> ${oA.toFixed(2)} | tasima yazma sicak noktasini kaldirmaz`);
console.log(`karma:  oran ${oK.toFixed(2)} -> ${oK.toFixed(2)} | bolum takip numarasindan cikar`);
console.log(`dizin tablosu, dokunulmazsa: oran ${oran(yukHesap(gSonra, yer0, P)).toFixed(3)}`);
console.log(`dizin tablosu, grup = satici:     ${bicim(enAzTasima(gSonra, yer0, HEDEF))}`);

const gBol = [];                                  // yalniz sicak satici gun gruplarina bolunur
for (let g = 0; g < DONEM; g++) gBol.push({ ad: `0/${g}`, agirlik: sonra[0] / DONEM });
for (let i = 1; i < SATICI; i++) gBol.push({ ad: `${i}`, agirlik: sonra[i] });
const yerBol = new Map(yer0);
for (let g = 0; g < DONEM; g++) yerBol.set(`0/${g}`, yer0.get("0"));
const r = enAzTasima(gBol, yerBol, HEDEF);
const dagilim = new Set();
for (let g = 0; g < DONEM; g++) dagilim.add(r.yer.get(`0/${g}`));
console.log(`dizin tablosu, grup = satici-gun: ${bicim(r)}`);
console.log(`  bedeli: sicak saticinin donem raporu ${dagilim.size} bolume dokunuyor (digerleri 1),` +
  ` dizin satiri ${SATICI} -> ${gBol.length}`);

console.log("\nD1 duyarliligi: dagilim ussu buyudukce bolunmeyen en buyuk grup bir taban koyar");
for (const uss of [0.9, 1.1, 1.3]) {
  const p = paylar(uss);
  console.log(`  uss ${uss.toFixed(1)}: en buyuk satici payi %${(p[0] * 100).toFixed(2)},` +
    ` ulasilabilir en iyi oran ${Math.max(1, p[0] * P).toFixed(2)}`);
}

en buyuk satici payi %7.41 -> %19.37
aralik: oran 8.00 -> 8.00 | tasima yazma sicak noktasini kaldirmaz
karma:  oran 1.00 -> 1.00 | bolum takip numarasindan cikar
dizin tablosu, dokunulmazsa: oran 1.904
dizin tablosu, grup = satici:     oran 1.549 | tasinan anahtar %4.43 | 468 tasima
dizin tablosu, grup = satici-gun: oran 1.181 | tasinan anahtar %9.04 | 14 tasima
  bedeli: sicak saticinin donem raporu 8 bolume dokunuyor (digerleri 1), dizin satiri 4000 -> 4029

D1 duyarliligi: dagilim ussu buyudukce bolunmeyen en buyuk grup bir taban koyar
  uss 0.9: en buyuk satici payi %7.41, ulasilabilir en iyi oran 1.00
  uss 1.1: en buyuk satici payi %16.07, ulasilabilir en iyi oran 1.29
  uss 1.3: en buyuk satici payi %27.36, ulasilabilir en iyi oran 2.19

Karma satırında satıcı üç katına çıksa da oran 1,00 kalıyor, çünkü bölüm satıcıdan değil takip numarasından çıkıyor. Karma bölümlemesi satıcı kaynaklı sıcak nokta üretmez — ama dönem raporunu da hiçbir zaman tek bölüme indiremez. Aralık satırında taşımanın anlamı yok: sıcak nokta belirli bir satıcıdan değil zaman ekseninden geliyor.

Dizin tablosunun üç satırı asıl ölçümdür. Hiçbir şey yapılmazsa oran 1,904 oluyor. En büyük satıcı olduğu gibi taşınmaya çalışıldığında 468 taşımadan ve anahtarların yüzde 4,43’ünden sonra oran ancak 1,549’a iniyor ve orada duruyor: o bölümde artık tek başına yüzde 19,37’lik bir satıcı var, bölünmediği sürece sekiz bölümün ortalamasının 1,549 katı olmaktan çıkamaz. Bölünmeyen en büyük grup dengenin tabanıdır; duyarlılık satırları aynı şeyi üç dağılım için tekrar ediyor: üs 1,3’te en büyük satıcı tek başına yüzde 27,36 tutuyor ve ulaşılabilecek en iyi oran 2,19.

Tabanı düşürmenin tek yolu grubu yeniden tanımlamaktır. Sıcak satıcı satıcı-gün gruplarına bölündüğünde 14 taşımayla oran 1,181’e iniyor. Taşınan anahtar oranı yüzde 9,04, yani ilk denemenin iki katı; ama sonuç ilk denemede ulaşılamayan bir yerde. Bedeli son satır yazıyor: sıcak satıcının dönem raporu artık sekiz bölüme dokunuyor, yani o satıcı için dizin tablosunun bütün kazancı geri verildi. Diğer 3999 satıcı için rapor hâlâ tek bölüme dokunuyor. Karar bu yüzden şudur: dizin tablosu dengeyi seçici olarak kurar; bedeli yalnız bölünen grubun sorgusuna yazılır. Parçalama Kalıpları dersi parça sayısı değiştiğinde taşınan oranı ölçmüştü; buradaki soru ayrıdır — parça sayısı sabitken yerleşimin düzeltilmesi.

Özet

• Bölümleme stratejisi anahtarı bölüme çeviren kuraldır; anahtar seçimiyle aynı şey değildir ve aynı anahtar üç kuralla üç ayrı yerleşim üretir.
• Aralık bölümlemesi 712,48 GB’ı sekiz bölüme eşit dağıttı ama isteği hiç bölmedi: sıcak nokta oranı 8,00, en yüklü bölüm K01’in 138,89 istek/s’sinin tamamını görüyor.
• Karma bölümlemesi oranı 1,00’a indirdi (bölüm başına 17,42 istek/s) ama satıcının dönem raporunu sekiz bölüme birden dağıttı.
• Dizin tablosu hem oranı 1,00’a indirdi hem raporu tek bölümde tuttu ve taranan kaydı 12.000.000’dan 1.500.137’ye düşürdü; karşılığında erişim başına iki depo dokunuşu istedi ve depoya ulasan istek/s 138,89’dan 277,78’e çıktı.
• Bölünmeyen en büyük grup dengeye taban koyar: en büyük satıcı üç katına çıktığında satıcı düzeyinde en iyi oran 1,549’da kaldı, grup satıcı-güne bölününce yüzde 9,04 anahtar taşınarak 1,181’e indi ve o satıcının raporu sekiz bölüme dağıldı.

Sonraki Adım

Üç stratejinin ortak bir sessizliği var. Hepsi verinin nereye konacağını çözüyor, hiçbiri verinin hangi biçimde durduğunu sormuyor. Dizin tablosunun taradığı 1.500.137 kayıt, satıcının raporunu üretmek için okunan kayıt sayısıdır ve bu sayının bir bölümü şemanın kendisinden gelir: bir raporu tamamlamak için gönderi kaydının yanına tarife, bölge ve sözleşme kayıtları da getirilmek zorundaysa okuma yolu tek bir bölümde bile birden çok tabloya uzanır. Sonraki ders o yolu kısaltmayı ele alır: okunan kaydın yanına neyin kopyalanacağını, kopyanın okumada kaç tabloyu ve kaç kaydı düşürdüğünü, karşılığında yazma yolunun kaç adıma uzadığını ve saklanan 712,48 GB ile günlük 976 MB artışın ne kadar büyüdüğünü sayar.