Parçalama

Federasyon deponun işini böldü ama her bağlamın kendi verisi hâlâ bütün olarak tek bir düğümde duruyor. Teslimat operasyonu deposu 624,88 GB taşıyor ve saniyede 250,00 işlem alıyor; bu sayılar bağlam bölünerek küçülmez, çünkü bölünecek bağlam kalmadı. Kalan tek yol veriyi kendi içinde bölmektir.

Parçalama (sharding), aynı bağlamın kayıtlarını bir anahtara göre bağımsız düğümlere dağıtmaktır. İlişkisel Veritabanı Yönetimi kursundaki bölümleme ile karıştırılmamalıdır: bölümleme bir tabloyu aynı motorun içinde parçalara ayırır, parçalama parçaları ayrı motorlara ve ayrı makinelere dağıtır. O kurs parçalamanın uygulamaya dayattığı bedelleri saydı — birleştirme, benzersizlik ve işlem sınırı, dağıt–topla kalıbının kuyruğu bozması, yeniden dengelemede eşleme yönteminin taşıma oranını belirlemesi. Burada o bedeller yeniden anlatılmaz. Bu dersin sorusu bir ölçekleme kararıdır: hangi anahtar seçilir ve seçim erişim örüntülerine ne yapar.

Anahtar Adayları ve Dağılımları

Gönderi verisinde üç aday vardır ve üçü de gerçek bir sorunun anahtarıdır: takip numarası (P1’in anahtarı), taşıyıcı (P2’nin anahtarı) ve satıcı (P3’ün anahtarı). Adayları ayıran şey iki özelliktir — kaç farklı değer aldıkları ve değerlerin ne kadar eşit dağıldığı.

VD6 — üç aday anahtarın dağılımı. Takip numarası tekdüzedir ve her gönderi için ayrıdır; taşıyıcı 12 farklı değer alır ve en büyük taşıyıcının payı 0,35’tir; satıcı 4000 farklı değer alır ve en büyük yüzde 1’lik dilim (40 satıcı) gönderilerin 0,30’unu üretir. Gerekçe: takip numarası üretilmiş bir kimliktir; taşıma az sayıda büyük oyuncu arasında bölünür; satıcı hacmi az sayıda büyük satıcıda yoğunlaşır. Satıcı sayısı K01’in hesabından gelir (günde 4000 fatura satırı = 4000 satıcı), ötekiler bu dersin varsayımıdır ve K01’in tablosuna eklenmez. Duyarlılık aşağıda taşıyıcı payı 0,50 ile verilir.

Anahtarın düğüme eşlenmesi tutarlı karma ile yapılır. Kuralın kendisi ve düğüm sayısı değiştiğinde yer değiştiren anahtar oranı Trafik Katmanı kursunda ölçüldü; burada yalnız veri yerleşimi için kullanılıyor ve o ölçüm tekrarlanmıyor.

// parcalama/anahtar.mjs — uc aday parca anahtarinin veri dagilimi, sicak noktasi, dokundugu dugum
// ve yeniden dengeleme maliyeti. Yerlestirme kurali tutarli karmadir; kuralin kendisi ve yer
// degistirme orani M19/K02'de olculdu, burada yalnizca veri yerlesimi icin kullaniliyor. MODELDIR.
const GONDERI = 100_000, PARCA = 8, SANAL = 200;      // model parametreleri
const TASIYICI = 12, TASIYICI_PAY = 0.35;             // VD6
const SATICI = 4000, BUYUK = 40, BUYUK_PAY = 0.30;    // VD6
let s = 20260731 % 2147483647;
const rast = () => (s = (s * 48271) % 2147483647) / 2147483647;

function karma(metin) {                                // FNV-1a; islev M01/K03'te kuruldu
  let h = 2166136261;
  for (let i = 0; i < metin.length; i += 1) h = Math.imul(h ^ metin.charCodeAt(i), 16777619) >>> 0;
  h ^= h >>> 15; h = Math.imul(h, 2246822507) >>> 0; h ^= h >>> 13;
  return h >>> 0;
}
const halka = (n) => {
  const h = [];
  for (let d = 0; d < n; d += 1) for (let v = 0; v < SANAL; v += 1) h.push([karma(`d${d}#${v}`), d]);
  return h.sort((a, b) => a[0] - b[0]);
};
const yerlestir = (anahtar, h) => {
  const c = karma(anahtar);
  if (c > h[h.length - 1][0]) return h[0][1];
  let alt = 0, ust = h.length - 1;
  while (alt < ust) { const o = (alt + ust) >> 1; if (h[o][0] < c) alt = o + 1; else ust = o; }
  return h[alt][1];
};

const kayitlar = [];
for (let i = 0; i < GONDERI; i += 1) kayitlar.push({
  no: `TR-${1_000_000 + i}`,
  tasiyici: `T${rast() < TASIYICI_PAY ? 0 : 1 + Math.floor(rast() * (TASIYICI - 1))}`,
  satici: `S${rast() < BUYUK_PAY ? Math.floor(rast() * BUYUK) : BUYUK + Math.floor(rast() * (SATICI - BUYUK))}`,
});

const ADAY = ["no", "tasiyici", "satici"];
const h8 = halka(PARCA), h9 = halka(PARCA + 1);
const OKUMA = 41.67, YAZMA = 97.22;                   // K01: P1 ve P2'nin depoya ulasan istek/s'si
const GB = 624.88, GUNLUK_MB = 856;                   // 03. ders: teslimat operasyonu deposu
const DOKUNAN = { no: [1, 1, PARCA], tasiyici: [PARCA, 1, PARCA], satici: [PARCA, PARCA, 1] };
const b = (x, n = 2) => x.toFixed(n);

console.log(`model: ${GONDERI.toLocaleString("tr-TR")} gonderi, ${PARCA} parca, ${SANAL} sanal dugum`);
console.log(`\n${"parca anahtari".padEnd(16)}${"farkli anahtar".padStart(15)}${"sicak nokta".padStart(13)}` +
  `${"en yuklu GB".padStart(13)}${"en yuklu islem/s".padStart(18)}${"8->9 oynayan".padStart(14)}${"tasinan GB".padStart(12)}`);
for (const a of ADAY) {
  const y8 = kayitlar.map((k) => yerlestir(k[a], h8)), y9 = kayitlar.map((k) => yerlestir(k[a], h9));
  const say = new Array(PARCA).fill(0);
  for (const d of y8) say[d] += 1;
  const enYuklu = Math.max(...say) / GONDERI, sicak = enYuklu * PARCA;
  const oynayan = y8.filter((d, i) => d !== y9[i]).length / GONDERI;
  console.log(`${a.padEnd(16)}${String(new Set(kayitlar.map((k) => k[a])).size).padStart(15)}` +
    `${b(sicak, 3).padStart(13)}${b(GB * enYuklu).padStart(13)}` +
    `${b((OKUMA + YAZMA) * enYuklu).padStart(18)}${b(oynayan, 4).padStart(14)}${b(GB * oynayan).padStart(12)}`);
}
console.log(`kusursuz dagilimda sicak nokta 1,000; ${PARCA} parcada dugum basina ` +
  `${b(GB / PARCA)} GB ve ${b((OKUMA + YAZMA) / PARCA)} islem/s`);
{
  const y8 = kayitlar.map((k) => yerlestir(k.no, h8)), y9 = kayitlar.map((k) => yerlestir(k.no, h9));
  const oynayan = y8.filter((d, i) => d !== y9[i]).length / GONDERI, tasinan = GB * oynayan * 1000;
  console.log(`takip numarasi anahtarinda tasinan ${b(tasinan / 1000)} GB = teslimat deposunun ` +
    `${b(tasinan / GUNLUK_MB, 1)} gunluk artisi (03. ders: ${GUNLUK_MB} MB/gun)`);
}

console.log(`\n${"parca anahtari".padEnd(16)}${"P1 dugum".padStart(10)}${"P2 dugum".padStart(10)}` +
  `${"P3 dugum".padStart(10)}${"cevrimici dokunus/s".padStart(21)}${"taban kati".padStart(12)}`);
for (const a of ADAY) {
  const [p1, p2, p3] = DOKUNAN[a], dokunus = OKUMA * p1 + YAZMA * p2;
  console.log(`${a.padEnd(16)}${String(p1).padStart(10)}${String(p2).padStart(10)}${String(p3).padStart(10)}` +
    `${b(dokunus).padStart(21)}${b(dokunus / (OKUMA + YAZMA)).padStart(12)}`);
}
console.log(`parcalanmamis depoda cevrimici dokunus ${b(OKUMA + YAZMA)} /s = K01'in depoya ulasan istek/s'si`);

// VD6 duyarliligi: en buyuk tasiyicinin payi 0,35 yerine 0,50 olsaydi (tasiyici alani yeniden uretilir)
{
  const say = new Array(PARCA).fill(0);
  for (const k of kayitlar)
    say[yerlestir(`T${rast() < 0.5 ? 0 : 1 + Math.floor(rast() * (TASIYICI - 1))}`, h8)] += 1;
  const enYuklu = Math.max(...say) / GONDERI;
  console.log(`\nduyarlilik: en buyuk tasiyicinin payi 0,50 olsaydi sicak nokta ` +
    `${b(enYuklu * PARCA, 3)} ve en yuklu dugum ${b(GB * enYuklu)} GB olurdu (tabloda 0,35 ile ` +
    `${b(3.748, 3)} ve ${b(292.78)} GB)`);
}

model: 100.000 gonderi, 8 parca, 200 sanal dugum

parca anahtari   farkli anahtar  sicak nokta  en yuklu GB  en yuklu islem/s  8->9 oynayan  tasinan GB
no                       100000        1.116        87.14             19.37        0.1193       74.54
tasiyici                     12        3.748       292.78             65.07        0.1182       73.85
satici                     4000        1.148        89.63             19.92        0.1100       68.74
kusursuz dagilimda sicak nokta 1,000; 8 parcada dugum basina 78.11 GB ve 17.36 islem/s
takip numarasi anahtarinda tasinan 74.54 GB = teslimat deposunun 87.1 gunluk artisi (03. ders: 856 MB/gun)

parca anahtari    P1 dugum  P2 dugum  P3 dugum  cevrimici dokunus/s  taban kati
no                       1         1         8               138.89        1.00
tasiyici                 8         1         8               430.58        3.10
satici                   8         8         1              1111.12        8.00
parcalanmamis depoda cevrimici dokunus 138.89 /s = K01'in depoya ulasan istek/s'si

duyarlilik: en buyuk tasiyicinin payi 0,50 olsaydi sicak nokta 4.713 ve en yuklu dugum 368.15 GB olurdu (tabloda 0,35 ile 3.748 ve 292.78 GB)

Bu sayılar hesap sınıfındadır: belirlenimlidirler, sabit tohumlu bir üreteçten ve sabit bir yerleştirme kuralından çıkarlar, makineye bağlı değildirler.

Sıcak Nokta Anahtarın Kaç Değer Aldığına Bağlı

Birinci tablonun sıcak nokta sütunu üç adayı hemen ayırıyor. Sıcak nokta (hot spot), en yüklü düğümün payının kusursuz paya oranıdır; 1,000 kusursuz dağılımdır.

Takip numarası 1,116 ve satıcı 1,148 veriyor; ikisi de kabul edilebilir. Taşıyıcı 3,748 veriyor: en yüklü düğüm kusursuz payın neredeyse dört katını taşıyor, 292,78 GB ve saniyede 65,07 işlem. Sekiz düğümlü bir kümede düğüm başına 78,11 GB ve 17,36 işlem/s beklenirken bir düğüm bunun dört katını alıyor — parçalama o düğüm için hiç yapılmamış gibidir.

Nedeni anahtarın kaç farklı değer aldığıdır. Taşıyıcı yalnız 12 değer alıyor ve en büyüğü tek başına yükün 0,35’ini taşıyor; hiçbir yerleştirme kuralı bir anahtarı iki düğüme bölemez, çünkü anahtar bölünmezlik biriminin kendisidir. Satıcı da çarpıktır — 40 satıcı hacmin 0,30’unu üretiyor — ama 4000 farklı değere yayıldığı için çarpıklık yerleştirmede erir; en büyük satıcının tek başına payı 0,0075’tir ve tek bir düğümü ele geçiremez. Kural şudur: sıcak noktayı yaratan çarpıklık değil, çarpıklığın az sayıda anahtar değerinde toplanmasıdır. Duyarlılık satırı bunu doğruluyor; taşıyıcı payı 0,50’ye çıkarsa sıcak nokta 4,713’e ve en yüklü düğüm 368,15 GB’ye çıkıyor.

Dokunulan Düğüm Sayısı Örüntüye Göre Değişiyor

İkinci tablo seçimi tersine çeviriyor. Bir istek, parça anahtarını süzemiyorsa bütün düğümlere gitmek zorundadır.

Takip numarası anahtar olduğunda P1 ve P2 birer düğüme dokunuyor: takip sorgusu numarayı zaten biliyor, durum olayı da numarayı taşıyor. Çevrimiçi dokunuş hızı 138,89 düğüm-dokunuşu/s’de kalıyor ve bu, K01’in depoya ulasan istek/s sayısının kendisidir — parçalama çevrimiçi yola hiçbir ek dokunuş eklemiyor. Taşıyıcı anahtar olduğunda P1 numaradan taşıyıcıyı bilemediği için sekiz düğüme birden soruyor ve hız 430,58’e, tabanın 3,10 katına çıkıyor. Satıcı anahtar olduğunda hem P1 hem P2 sekiz düğüme gidiyor: 1111,12 dokunuş/s, tabanın tam sekiz katı.

Üçüncü örüntü tabloyu tamamlıyor. P3 yalnız satıcı anahtarında tek düğümde kalıyor; ötekilerde sekiz düğüme dağılıyor. Ama P3 günde bir kez koşan ve dört saatlik penceresi olan bir iştir; sekiz düğüme dağılması onun için bir gecikme sorunu değil, bir eşgüdüm işidir. P1 ve P2 ise saniyede 138,89 istekle sürekli akar ve takip okumasının 200 milisaniyelik eşiği vardır.

Karar bu iki tablonun kesişiminden çıkıyor ve tek bir cümleyle söylenebilir: parça anahtarı, en sık gelen ve eşiği en sıkı olan örüntünün süzdüğü alandır. Takip numarası her iki tabloda da kazanıyor — sıcak noktası 1,116, çevrimiçi dokunuşu taban değerde. Taşıyıcı P2’yi tek düğümde tutuyor ama P1’i sekize dağıtıp üstüne 3,748 sıcak nokta getiriyor; satıcı P3’ü kurtarıyor ama çevrimiçi yolu sekiz katına çıkarıyor.

Yeniden Dengelemenin Bedeli

Son iki sütun düğüm eklendiğinde ne olduğunu veriyor. Sekiz parçadan dokuza geçişte takip numarası anahtarında anahtarların 0,1193’ü yer değiştiriyor — kuramsal alt sınır olan 1/9, yani 0,1111’e yakın. Oranın kendisi Trafik Katmanı kursunun ölçtüğü şeydi; burada bayta çevriliyor: 624,88 GB’lik depoda 74,54 GB.

Sayının büyüklüğü tek başına anlaşılmaz; bir ölçüye bağlanması gerekir. Teslimat operasyonu deposu günde 856 MB büyüyor (03. ders), yani 74,54 GB o deponun 87,1 günlük artışına denktir. Bir düğüm eklemek, üç aylık büyümenin tamamını ağ üzerinden bir kez daha taşımak demektir. Yeniden dengelemenin planlı bir iş olmasının, kesintisiz yapılabilmesinin ve kendi bant genişliği payını istemesinin nedeni budur — anlık bir yapılandırma değişikliği değil, veri taşıma işidir.

Taşıyıcı anahtarında oran benzer (0,1182) ama anlamı değişir: 12 anahtardan biri yer değiştirdiğinde o anahtarın bütün verisi tek seferde taşınır ve taşıma sırasında iki düğüm birden yükün büyük bir payını taşır. Az sayıda değer alan anahtarın ikinci bedeli budur.

Özet

• Parçalama aynı bağlamın kayıtlarını ayrı motorlara dağıtır; tablo bölümlemesi ise aynı motorun içinde kalır ve ikisi ayrı kararlardır.
• Sıcak noktayı çarpıklık değil, çarpıklığın az sayıda anahtar değerinde toplanması yaratıyor: 12 değerli taşıyıcıda sıcak nokta 3,748 (292,78 GB, 65,07 işlem/s), 4000 değerli satıcıda 1,148, tekdüze takip numarasında 1,116.
• Parça anahtarını süzemeyen örüntü bütün düğümlere gidiyor: çevrimiçi dokunuş hızı takip numarası anahtarında 138,89/s (taban), taşıyıcıda 430,58 (3,10 kat), satıcıda 1111,12 (8,00 kat).
• Anahtar, en sık gelen ve eşiği en sıkı olan örüntünün süzdüğü alandır; dört saatlik penceresi olan toplu tarama dağıt–topla maliyetini karşılayabilir, saniyede 138,89 isteklik çevrimiçi yol karşılayamaz.
• Sekiz parçada düğüm başına 78,11 GB ve 17,36 işlem/s düşüyor; VD6’da taşıyıcı payı 0,50 olsaydı en yüklü düğüm 368,15 GB’ye çıkardı.
• Sekizden dokuza geçişte anahtarların 0,1193’ü yer değiştiriyor ve bu 74,54 GB eder — teslimat operasyonu deposunun 87,1 günlük artışı.

Sonraki Adım

Parçalama kararı verildi ve anahtar seçildi: takip numarası. Ama bir soru açık kaldı ve bu derste tek bir yanıtla geçiştirildi — anahtarın hangi kurala göre parçalara dağıtılacağı. Burada tutarlı karma kullanıldı, çünkü Trafik Katmanı kursunda ölçülmüştü; oysa bu tek seçenek değildir. Anahtar bir aralığa göre bölünebilir, karmasına göre dağıtılabilir ya da anahtardan parçaya eşlemeyi ayrı bir dizin tablosunda tutmak da bir seçenektir. Üçü aynı veriyi aynı düğümlere farklı biçimlerde yerleştirir ve üçü yeniden dengelemeyi başka türlü etkiler: birinde aralık taraması tek düğümde kalır ama yeni kayıtlar hep aynı düğüme düşer, ötekinde dağılım düzelir ama aralık taraması dağılır, üçüncüsünde eşleme serbestçe değiştirilebilir ama her arama bir dolaylılık katmanından geçer. Sonraki ders bu üç stratejiyi karşılaştırır.