Parçalama

Önceki ders kümeye üye eklemenin neyi çözdüğünü ve neyi çözmediğini gösterdi: bir üye kaybedildiğinde hizmet sürer, ama her üye aynı verinin tamamını taşımayı sürdürür. Katalog büyüdüğünde ve ödünç kayıtları tek bir üyenin diskine sığmaz olduğunda çoğaltmanın yapabileceği bir şey kalmaz; veriyi üyeler arasında bölmek gerekir.

Bölmenin adı parçalamadır (sharding) ve tek bir karara iner: her belgenin hangi parçaya gideceğini belirleyen alanın seçimi. Bu alana parça anahtarı (shard key) denir. Veriyi bölme stratejilerinin aritmetiği — aralığa göre mi karmaya göre mi bölündüğü, yeniden dengelemenin taşıdığı veri — İleri Veri Ölçekleme kursunda ölçüldü ve burada tekrarlanmaz. Buradaki soru, belge modeline özgü olanıdır: anahtar bir belge alanıdır ve o alanın seçimi geri alınması pahalı bir karardır.

Anahtar Belgenin İçinden Gelir

İlişkisel bir tabloda bölümleme sütunu şemanın parçasıdır ve her satırda vardır. Belge modelinde böyle bir güvence yoktur: derlemdeki belgeler farklı alan kümeleri taşıyabilir. Bu, parça anahtarına iki koşul yükler.

Anahtar alanı her belgede bulunmalıdır. Yönlendirici, alanı olmayan bir belgeyi hiçbir parçaya gönderemez. Kütüphane veritabanında bu soyut bir risk değildir: eski dizgeden aktarılan ödünç kayıtlarının bir kısmında şube alanı hiç yoktur.

Anahtarın tekilliği parça sayısını sınırlar. Parçalamanın en küçük tanesi bir anahtar değeridir; aynı değeri taşıyan belgeler bölünemez. Altı farklı değeri olan bir alan altıdan çok parçaya dağıtılamaz ve değerlerden biri belgelerin yarısını taşıyorsa o yığın hiçbir zaman bölünmez. Bu, koşumdan bağımsız bir üst sınırdır.

Üçüncü koşul ölçülecek olandır: anahtar, hem yazmayı parçalara yaymalı hem de sık gelen sorguların tek bir parçaya yönlendirilmesine izin vermelidir. Bir sorgu anahtarın önekini sabitliyorsa yönlendirici onu tek parçaya gönderir; buna hedeflenen sorgu denir. Sabitlemiyorsa yönlendirici bütün parçalara sormak zorundadır; buna dağıtılan sorgu denir. İki tür arasındaki fark, dokunulan parça sayısıdır ve sayılabilir.

Düzenek

NS16 — ödünç kayıtlarının şubelere dağılımı 45, 18, 14, 11, 8 ve 4 birimdir. Gerekçe: merkez şube en büyük derlemi ve en çok üyeyi taşır. NS17 — aktarılan eski kayıtların yüzde 2’sinde şube alanı yoktur. NS18 — sorgu karışımı: üye sorgusu yüzde 45, şube gün sonu listesi yüzde 20, son yedi günün ödünçleri yüzde 15, kayıt kimliğiyle erişim yüzde 15, gecikmiş ödünç taraması yüzde 5. Üç varsayım da doğrusal etkilidir; karışımdaki ağırlıklar değişirse aşağıdaki ağırlıklı ortalama aynı yönde değişir.

// parca/model.mjs — odunc belgeleri ureteci ve parca yerlesimi. Uretec kendi yazilmistir,
// tohum gorunurdur: her kosumda ayni belge kumesi cikar. Parca sayisi P bir parametredir;
// dagitimin araliga mi karmaya mi dayandigi Ileri Veri Olcekleme kursunda olculdu, burada
// degismeyen tek sey her belgenin ANAHTAR ALANININ DEGERINE gore bir parcaya yonlenmesidir.
export const SUBE = [["merkez", 45], ["kadikoy", 18], ["besiktas", 14], ["uskudar", 11],
  ["sisli", 8], ["adalar", 4]];
export const GUN = 180, UYE = 6000;

export function uret({ adet = 20000, tohum = 20260731, eksikSube = 0.02 } = {}) {
  let s = tohum % 2147483647;
  const rast = () => (s = (s * 48271) % 2147483647) / 2147483647;
  const toplam = SUBE.reduce((t, [, w]) => t + w, 0);
  const belge = [];
  for (let i = 1; i <= adet; i += 1) {
    let x = rast() * toplam, sube = SUBE[0][0];
    for (const [ad, w] of SUBE) { if (x < w) { sube = ad; break; } x -= w; }
    const d = { odunc_id: i, uye_id: 1 + Math.floor(rast() * UYE),
      alinma_gunu: 1 + Math.floor(rast() * GUN), iade_edildi: rast() < 0.82 };
    if (rast() >= eksikSube) d.sube = sube;   // eski kayitlarin bir kisminda sube alani yok
    belge.push(d);
  }
  return belge;
}

const kiyas = (a, b) => {                     // anahtar demetlerinin toplam siralamasi
  for (let i = 0; i < a.length; i += 1) if (a[i] !== b[i]) return a[i] < b[i] ? -1 : 1;
  return 0;
};
const karmaDeger = (m) => { let h = 2166136261; for (const c of m) h = Math.imul(h ^ c.charCodeAt(0), 16777619); return h >>> 0; };

// Parca yerlesimi: anahtar degerleri siraya dizilir ve esit belge sayisi hedefiyle P pencereye
// bolunur. Tek bir anahtar degeri bolunemez — parcalamanin en kucuk tanesi bir anahtar degeridir.
export function yerlestir(belge, alanlar, P, karma = false) {
  const anahtar = (d) => alanlar.map((a) => d[a]);
  const tam = belge.filter((d) => alanlar.every((a) => d[a] !== undefined));
  const sayac = new Map();
  for (const d of tam) {
    const k = JSON.stringify(karma ? [karmaDeger(JSON.stringify(anahtar(d)))] : anahtar(d));
    sayac.set(k, (sayac.get(k) ?? 0) + 1);
  }
  const sirali = [...sayac.entries()].sort((a, b) => kiyas(JSON.parse(a[0]), JSON.parse(b[0])));
  const hedef = tam.length / P;
  const yer = new Map();
  let p = 0, birikim = 0;
  for (const [k, n] of sirali) {
    yer.set(k, p);
    birikim += n;
    if (birikim >= hedef * (p + 1) && p < P - 1) p += 1;
  }
  const parca = (d) => yer.get(JSON.stringify(karma ? [karmaDeger(JSON.stringify(anahtar(d)))] : anahtar(d)));
  const dagilim = Array(P).fill(0);
  for (const d of tam) dagilim[parca(d)] += 1;
  return { parca, dagilim, tam, eksik: belge.length - tam.length, farkli: sayac.size };
}

// Sorgu, anahtarin bir ONEKINI sabitliyorsa yonlendirilebilir (hedeflenen sorgu); sabitlemiyorsa
// yonlendirici butun parcalara gitmek zorundadir (dagitilan sorgu). Karma yerlesimde aralik
// kisiti kullanilamaz, cunku bitisik degerler bitisik parcalara dusmez.
export function dokunulan(sorgu, alanlar, karma, y, P) {
  const kullanilir = [];
  for (const a of alanlar) {
    if (sorgu.esit && a in sorgu.esit) { kullanilir.push({ alan: a, tip: "esit" }); continue; }
    if (sorgu.aralik && sorgu.aralik.alan === a && karma === false) kullanilir.push({ alan: a, tip: "aralik" });
    break;
  }
  if (kullanilir.length === 0) return P;
  const uyar = (d) => kullanilir.every((k) => k.tip === "esit"
    ? d[k.alan] === sorgu.esit[k.alan]
    : d[k.alan] >= sorgu.aralik.min && d[k.alan] <= sorgu.aralik.max);
  return new Set(y.tam.filter(uyar).map(y.parca)).size;
}

// parca/olc.mjs — bes parca anahtari adayi: yerlesim dengesi, sicak parca ve dokunulan parca
import { uret, yerlestir, dokunulan, SUBE, GUN, UYE } from "./model.mjs";

const P = 4, ADET = 20000;
const belge = uret({ adet: ADET });
const ADAY = [["sube", ["sube"], false], ["alinma_gunu", ["alinma_gunu"], false],
  ["karma(alinma_gunu)", ["alinma_gunu"], true], ["uye_id", ["uye_id"], false],
  ["{sube,uye_id}", ["sube", "uye_id"], false]];
const SORGU = [
  ["S1 uyenin acik oduncleri", 45, (i) => ({ esit: { uye_id: 1 + (i * 137) % UYE } })],
  ["S2 sube gun sonu listesi", 20, (i) => ({ esit: { sube: SUBE[i % SUBE.length][0], alinma_gunu: 1 + (i * 31) % GUN } })],
  ["S3 son 7 gunun oduncleri", 15, () => ({ aralik: { alan: "alinma_gunu", min: GUN - 6, max: GUN } })],
  ["S4 odunc kaydi id ile", 15, (i) => ({ esit: { odunc_id: 1 + (i * 911) % ADET } })],
  ["S5 gecikmis odunc taramasi", 5, () => ({ esit: {} })],
];
const s = (x, n) => String(x).padStart(n);
const yeni = belge.filter((d) => d.alinma_gunu > GUN - 7);
console.log(`${ADET} odunc belgesi, ${P} parca, ${SUBE.length} sube, ${UYE} uye, ${GUN} gun. Tohum 20260731.`);
console.log(`son 7 gunde alinan: ${yeni.length} belge\n`);
console.log("parca anahtari      | farkli deger | yonlendirilemeyen | parca dagilimi          | en dolu/ort | son 7 gun en dolu parca");
console.log("--------------------|--------------|-------------------|-------------------------|-------------|------------------------");
const yerlesim = new Map();
for (const [ad, alanlar, karma] of ADAY) {
  const y = yerlestir(belge, alanlar, P, karma);
  yerlesim.set(ad, y);
  const enDolu = Math.max(...y.dagilim) / (y.tam.length / P);
  const yd = Array(P).fill(0);
  for (const d of yeni) if (alanlar.every((a) => d[a] !== undefined)) yd[y.parca(d)] += 1;
  const pay = Math.max(...yd) / yd.reduce((t, x) => t + x, 0);
  console.log(`${ad.padEnd(19)} | ${s(y.farkli, 12)} | ${s(y.eksik, 17)} | ` +
    `${y.dagilim.map((x) => s(x, 5)).join(" ").padEnd(23)} | ${s(enDolu.toFixed(2), 11)} | ` +
    `${s("%" + (100 * pay).toFixed(1), 23)}`);
}

console.log("\ndokunulan parca (sorgu basina, 1 = hedeflenen, 4 = dagitilan):");
console.log("parca anahtari      |  S1  |  S2  |  S3  |  S4  |  S5  | agirlikli ortalama");
console.log("--------------------|------|------|------|------|------|-------------------");
for (const [ad, alanlar, karma] of ADAY) {
  const y = yerlesim.get(ad);
  const hucre = [], agirlikli = [];
  for (const [, agirlik, ornek] of SORGU) {
    let t = 0;
    for (let i = 0; i < 12; i += 1) t += dokunulan(ornek(i), alanlar, karma, y, P);
    hucre.push(t / 12);
    agirlikli.push((t / 12) * agirlik);
  }
  const ort = agirlikli.reduce((a, b) => a + b, 0) / SORGU.reduce((a, b) => a + b[1], 0);
  console.log(`${ad.padEnd(19)} | ${hucre.map((x) => s(x.toFixed(2), 4)).join(" | ")} | ${s(ort.toFixed(2), 18)}`);
}
console.log("\nsorgu karisimi: " + SORGU.map(([a, w]) => `${a.slice(0, 2)} %${w}`).join(", "));
console.log(`kosumdan bagimsiz: bir anahtarin farkli deger sayisi parca sayisinin ust siniridir` +
  ` (sube icin ${SUBE.length}).`);

20000 odunc belgesi, 4 parca, 6 sube, 6000 uye, 180 gun. Tohum 20260731.
son 7 gunde alinan: 782 belge

parca anahtari      | farkli deger | yonlendirilemeyen | parca dagilimi          | en dolu/ort | son 7 gun en dolu parca
--------------------|--------------|-------------------|-------------------------|-------------|------------------------
sube                |            6 |               406 |  6950  8867  1597  2180 |        1.81 |                   %45.6
alinma_gunu         |          180 |                 0 |  5022  5031  5031  4916 |        1.01 |                  %100.0
karma(alinma_gunu)  |          180 |                 0 |  5034  4973  5002  4991 |        1.01 |                   %59.6
uye_id              |         5788 |                 0 |  5000  5000  5002  4998 |        1.00 |                   %27.0
{sube,uye_id}       |        13443 |               406 |  4899  4901  4897  4897 |        1.00 |                   %25.8

dokunulan parca (sorgu basina, 1 = hedeflenen, 4 = dagitilan):
parca anahtari      |  S1  |  S2  |  S3  |  S4  |  S5  | agirlikli ortalama
--------------------|------|------|------|------|------|-------------------
sube                | 4.00 | 1.00 | 4.00 | 4.00 | 4.00 |               3.40
alinma_gunu         | 4.00 | 1.00 | 1.00 | 4.00 | 4.00 |               2.95
karma(alinma_gunu)  | 4.00 | 1.00 | 4.00 | 4.00 | 4.00 |               3.40
uye_id              | 1.00 | 4.00 | 4.00 | 4.00 | 4.00 |               2.65
{sube,uye_id}       | 4.00 | 1.50 | 4.00 | 4.00 | 4.00 |               3.50

sorgu karisimi: S1 %45, S2 %20, S3 %15, S4 %15, S5 %5
kosumdan bagimsiz: bir anahtarin farkli deger sayisi parca sayisinin ust siniridir (sube icin 6).

Yerleşim Dengesi ve Sıcak Parça

En sezgisel aday en kötü dengeyi veriyor. Ödünç kayıtlarını şubeye göre bölmek işletme düzenine uygun görünür; ölçüm başka bir şey söylüyor. Altı şube dört parçaya sıkıştığında parçalara 6950, 8867, 1597 ve 2180 belge düşüyor: en dolu parça ortalamanın 1,81 katı. Sebep tekilliktir — bir parçanın taşıdığı en küçük tane bir şubedir ve merkez şube tek başına ödünç kayıtlarının yüzde 45’ini üretir. Dengesizlik daha çok parça eklenerek de düzelmez, çünkü altı farklı değer altı parçanın üst sınırıdır. Bu satırın ikinci sayısı da uyarıdır: 406 belge şube alanını taşımadığı için hiçbir parçaya yönlendirilemez.

Dengeli yerleşim tek başına yeterli değildir. alinma_gunu anahtarı belgeleri neredeyse kusursuz bölüyor — en dolu parça ortalamanın 1,01 katı. Son sütun bu satırı çürütüyor: son yedi günde alınan 782 ödüncün yüzde 100’ü tek bir parçaya düşüyor. Artan bir alan anahtar olduğunda geçmiş veri düzgün dağılır ama bütün yeni yazma en son pencereyi taşıyan parçaya yığılır. Buna sıcak parça denir ve depoda görünen tek belirtisi, kümenin üç üyesi boştayken birinin yazma sırasına girmesidir.

Karma yerleşim sıcak parçayı bir başka şeyle takas ediyor. Aynı alanın karma yerleşimi sıcak parçanın payını yüzde 100’den 59,6’ya indiriyor. Yüzde 25’e inmemesinin sebebi de tekilliktir: yedi günün yedi farklı değeri dört parçaya dağıldığında bazı parçalara iki gün düşer. Bedel ikinci tablodadır ve büyüktür.

En yüksek tekillikli aday en iyi dengeyi veriyor. uye_id anahtarında dağılım 5000, 5000, 5002, 4998 ve son yedi günün payı yüzde 27 — dört parça için ideal olan yüzde 25’e yakın. Bileşik anahtar da aynı dengeyi veriyor ama yönlendirilemeyen 406 belgeyi geri getiriyor, çünkü önekinde şube alanı var.

Hedeflenen ve Dağıtılan Sorgu

İkinci tablo aynı sorgu karışımını beş adayda koşturuyor ve dengeye bakarak verilen kararı tersine çeviriyor.

uye_id anahtarı ağırlıklı ortalamada 2,65 parçayla en iyi sonucu veriyor, çünkü karışımın en ağır sorgusu olan üye sorgusu tam olarak anahtarı sabitliyor: 1,00 parça. Aynı anahtarda şube gün sonu listesi 4,00’e çıkıyor — anahtarı hiç sabitlemediği için dört parçaya birden gidiyor.

{sube,uye_id} bileşik anahtarı bu dersin en öğretici satırıdır. Yerleşim dengesi kusursuz (1,00) ve şube sorgusu 1,50 parçaya iniyor; buna karşın üye sorgusu 4,00. Sebep, bileşik anahtarın soldan sağa çalışmasıdır: üye sorgusu uye_id alanını sabitliyor ama önekteki sube alanını sabitlemiyor, bu yüzden yönlendirici hangi parçaya gideceğini bilemiyor. Ağırlıklı ortalama 3,50 ile beş adayın en kötüsü. Bileşik anahtar eklemek erişimi daraltmaz, önek koşulunu sıkılaştırır.

alinma_gunu ile karma yerleşiminin karşılaştırması ödünleşimi tek bir sütunda gösteriyor. Karma yerleşim sıcak parçayı yüzde 100’den 59,6’ya indirdi; karşılığında son yedi günün ödünçleri sorgusu 1,00’dan 4,00 parçaya çıktı ve ağırlıklı ortalama 2,95’ten 3,40’a yükseldi. Karma yerleşim bitişik değerleri bitişik parçalara koymadığı için aralık sorgusu yönlendirilemez. Yazmayı yayan şeyle okumayı toplayan şey burada doğrudan karşı karşıya gelir.

Son satır koşumdan bağımsız kalan sınırı yineliyor: bir anahtarın farklı değer sayısı, parça sayısının üst sınırıdır. Bu sınır makineye, veriye ya da ayara bağlı değildir.

Özet

• Parça anahtarı bir belge alanıdır ve alanı taşımayan belge yönlendirilemez: şube tabanlı anahtarda 20.000 belgenin 406’sı hiçbir parçaya gidemedi.
• Anahtarın farklı değer sayısı parça sayısının üst sınırıdır; altı şubeye bölünen derlemde en dolu parça ortalamanın 1,81 katı oldu ve daha çok parça eklemek bunu düzeltmez.
• Dengeli yerleşim sıcak parçayı önlemez: alinma_gunu anahtarında yerleşim 1,01 kat dengeliyken son yedi günün 782 ödüncünün yüzde 100’ü tek parçaya düştü.
• Karma yerleşim sıcak parçanın payını yüzde 59,6’ya indirdi ama aralık sorgusunu 1,00 parçadan 4,00 parçaya çıkardı; ağırlıklı ortalama 2,95’ten 3,40’a yükseldi.
• Bileşik anahtar önek koşuluna bağlıdır: {sube,uye_id} yerleşimi kusursuz dengeledi ama önekini sabitlemeyen üye sorgusu 4,00 parçaya dağıldı ve ağırlıklı ortalama 3,50 ile en kötü çıktı.
• Bu karışımda en iyi anahtar uye_id oldu: 1,00 kat denge, yüzde 27 sıcak pay ve 2,65 ağırlıklı parça. Seçim dengeye değil, karışımın en ağır sorgusuna bakılarak yapılır.

Sonraki Adım

Bu ders bir belgenin hangi parçaya gideceğini çözdü, ama parçanın kendisi önceki dersin çoğaltma kümesidir: her parça birden çok üyeden oluşur ve o üyelerden hangilerinin yazmayı görmüş olması gerektiği hâlâ açık. İki ders de aynı boşluğu bıraktı — birinci derste kabul edilmiş 6 ödünç kaydı geri alındı ve bunun nasıl önleneceği söylenmedi. Bir yazmanın “başarılı” sayılması için kaç üyenin onay vermesi gerektiği bir ayardır; aynı biçimde bir okumanın hangi üyeden ve hangi doğrulamayla yanıtlanacağı da bir ayardır. Sonraki ders bu iki ayarı adlandırır ve aynı ödünç senaryosunu üç ayarda koşturur: onay için beklenen tur sayısı, arıza anında kaybolan yazma sayısı ve okumada görülen sürüm nasıl değişiyor.