Sıralama ve Bölümleme

Önceki ders teslim sayısı ile etki sayısını ayırdı, ama iki ölçüm de teslimin sırasına hiç bakmadı. Ödünç sisteminde sıranın belirleyici olduğu yerler var. Aynı kitabın “verildi” ve “iade alındı” olayları ters sırayla işlenirse şube stok özeti kitabı hem rafta hem üyede gösterir; kitabın son durumu, olayların gerçek zamanına değil işlenme sırasına göre oluşur.

Bu ders bir gerilimi ölçer. Şimdiye kadar işi hızlandırmanın yolu tüketici eklemekti; tüketici eklemek ise sırayı bozar. Sorunun sayısal karşılığını görmek için önce sıra ihlalini ölçülebilir bir şeye çevirmek gerekiyor.

Sıra İhlali Nasıl Sayılır

Olaylara üretildikleri sırayı veren bir numara verilir. İşlendikten sonra olaylar bitiş zamanlarına göre dizilir. İki olay bu dizide üretim sırasının tersine yerleşmişse bir ters çift (inversion) oluşur; Algoritmalar kursunda sıralama başarımını ölçmek için kullanılan sayının aynısıdır. İki ayrı sayı tutulur: tüm çiftler üzerinden genel ters çift ve yalnız aynı kitabın olayları arasındaki anahtar içi ters çift.

Ayrım önemlidir, çünkü ödünç sistemi genel sıra istemez. İki farklı kitabın olaylarının hangi sırayla bittiği hiçbir şeyi değiştirmez. Bozulması yanlış sonuç üreten şey, aynı kitabın olaylarının sırasıdır.

// bolum.mjs — sabit tohumlu olay dizisi, bolumleme kosumu ve sira ihlali sayaci
export function uretec(tohum) {                 // sabit tohumlu dogrusal eslesmeli uretec
  let x = tohum;
  return () => (x = (x * 1103515245 + 12345) % 2147483648) / 2147483648;
}

export function olaylar(adet = 24, tohum = 20250720) {
  const rast = uretec(tohum);
  const TUR = ["verildi", "iade_alindi", "rezerve_edildi"];
  const liste = [];
  for (let sira = 0; sira < adet; sira++) {
    const kitapId = 1 + Math.floor(rast() * 6);          // 1..6 arasi kitap
    liste.push({ sira, kitapId, tur: TUR[Math.floor(rast() * 3)], sure: 1 + Math.floor(rast() * 3) });
  }
  return liste;
}

const sirala = (a) => [...a].sort((x, y) => x.bitis - y.bitis || x.yer - y.yer);

// Her bolum tek isci tarafindan, gelis sirasiyla islenir.
export function bolumlu(liste, bolumSayisi) {
  const bitis = new Array(bolumSayisi).fill(0);
  const sonuc = liste.map((o) => {
    const b = o.kitapId % bolumSayisi;                    // bolum anahtari: kitap kimligi
    bitis[b] += o.sure;
    return { ...o, yer: b, bitis: bitis[b] };
  });
  return { sonuc: sirala(sonuc), sure: Math.max(...bitis), yuk: bitis };
}

// Bolumleme yok: her ileti o an bosalan isciye gider.
export function rakip(liste, isciSayisi) {
  const musait = new Array(isciSayisi).fill(0);
  const sonuc = liste.map((o) => {
    let k = 0;
    for (let i = 1; i < isciSayisi; i++) if (musait[i] < musait[k]) k = i;
    musait[k] += o.sure;
    return { ...o, yer: k, bitis: musait[k] };
  });
  return { sonuc: sirala(sonuc), sure: Math.max(...musait), yuk: musait };
}

// Bitis sirasina gore dizilmis olaylarda ters cift sayisi.
export function ihlal(bitisSirali) {
  let genel = 0, anahtarIci = 0;
  for (let i = 0; i < bitisSirali.length; i++)
    for (let j = i + 1; j < bitisSirali.length; j++)
      if (bitisSirali[i].sira > bitisSirali[j].sira) {
        genel += 1;
        if (bitisSirali[i].kitapId === bitisSirali[j].kitapId) anahtarIci += 1;
      }
  return { genel, anahtarIci };
}

Tüketici Eklemek Sırayı Bozar

İlk ölçüm rekabet eden tüketici düzenini koşturur: her ileti o an boşalan işçiye gider, bölümleme yoktur. Yirmi dört olay altı farklı kitaba dağılmıştır ve süreleri sabit tohumla üretilmiştir.

// rakip-sira.mjs — bolumleme olmadan isci eklemek: sure duser, anahtar ici sira bozulur
import { olaylar, rakip, ihlal } from "./bolum.mjs";
const liste = olaylar();

console.log(`olay sayisi=${liste.length}  farkli kitap=${new Set(liste.map((o) => o.kitapId)).size}`);
console.log("isci  sure  genel ters cift  anahtar ici ters cift");
for (const n of [1, 2, 3, 4]) {
  const k = rakip(liste, n);
  const i = ihlal(k.sonuc);
  console.log(`${String(n).padStart(4)}${String(k.sure).padStart(6)}` +
              `${String(i.genel).padStart(16)}${String(i.anahtarIci).padStart(23)}`);
}

node rakip-sira.mjs

olay sayisi=24  farkli kitap=6
isci  sure  genel ters cift  anahtar ici ters cift
   1    44               0                      0
   2    22               4                      1
   3    15               9                      1
   4    12              17                      3

Tek işçide iki sayı da sıfır: sıra garantisi bedava değil, tek tüketici koşuluyla geliyor. İşçi sayısı dörde çıktığında toplam süre 44’ten 12’ye iniyor, ama anahtar içi ters çift sayısı üçe çıkıyor. Bu üç çift, aynı kitabın iki olayının ters sırayla bittiği durumlardır — stok özetinin yanlış sonuç ürettiği yer tam burasıdır.

Sonuç bir ödünleşmedir ve her iki uç da kabul edilemez. Tek tüketici sırayı korur ama verim üçte bire iner. Dört tüketici verimi verir ama doğruluğu bozar. Aranan şey ortada bir yerdedir: sıranın yalnız gerektiği yerde korunması.

Anahtara Göre Bölümleme

Gerektiği yer bellidir: aynı kitabın olayları. Öyleyse iletiler işçilere değil, anahtarlara göre dağıtılsın. Her ileti bir bölüm anahtarından (partition key) türetilen bir bölüme (partition) düşsün ve her bölüm tek bir işçi tarafından geliş sırasıyla işlensin.

Kural iki koşulu birden verir. Aynı anahtarın bütün olayları aynı bölüme düşer, dolayısıyla aralarındaki sıra korunur. Farklı bölümler birbirinden bağımsız çalıştığı için bölüm sayısı kadar koşutluk elde edilir.

// bolumlu-sira.mjs — ayni is yuku anahtara gore bolumlenince anahtar ici sira korunur
import { olaylar, bolumlu, ihlal } from "./bolum.mjs";
const liste = olaylar();

console.log("bolum  sure  genel ters cift  anahtar ici ters cift  bolum yukleri");
for (const p of [1, 2, 3, 4, 6]) {
  const k = bolumlu(liste, p);
  const i = ihlal(k.sonuc);
  console.log(`${String(p).padStart(5)}${String(k.sure).padStart(6)}` +
              `${String(i.genel).padStart(16)}${String(i.anahtarIci).padStart(23)}   ${k.yuk.join(" ")}`);
}

node bolumlu-sira.mjs

bolum  sure  genel ters cift  anahtar ici ters cift  bolum yukleri
    1    44               0                      0   44
    2    24              20                      0   24 20
    3    20              24                      0   20 13 11
    4    21              25                      0   3 14 21 6
    6    14              44                      0   14 10 7 6 3 4

Anahtar içi ters çift sütunu bölüm sayısından bağımsız olarak sıfırdır. Genel ters çift ise bölüm sayısıyla birlikte artıp altı bölümde 44’e çıkar. İki sütunun birlikte okunması dersin özüdür: bölümleme, genel sırayı vererek anahtar içi sırayı satın alır. Kaybedilen şeyin zaten değeri yoktu; korunan şey doğruluğu belirliyordu.

Süre sütunu ikinci bir gerçeği söyler. Bölüm sayısı arttıkça süre düşüyor, ama düzenli değil: dört bölümde 21, üç bölümde 20. Bölüm yükleri sütunu nedenini gösteriyor — dört bölümde yükler 3, 14, 21 ve 6; en dolu bölüm işi bitirene kadar diğer üçü boşta bekliyor. Bölüm sayısını artırmak koşutluk kapasitesini artırır, koşutluğun gerçekleşmesini değil. Gerçek koşutluğu belirleyen, yükün bölümlere ne kadar dengeli dağıldığıdır.

Bölüm Anahtarını Seçmek

Anahtar seçimi bir başarım ayarı değil, bir doğruluk kararıdır: sıra garantisi tam olarak anahtarın tanımladığı küme içinde geçerlidir, dışında hiç yoktur.

Kitap kimliği anahtar seçilirse aynı kitabın verilme ve iade olayları sıralı kalır, ama aynı üyenin iki farklı kitaptaki olayları sıralı kalmaz. Üye kimliği seçilirse tersi olur. Ölçütü belirleyen soru şudur: hangi olay çiftinin ters sırayla işlenmesi yanlış sonuç üretir? Stok özeti için yanıt kitaptır, çünkü bir kitabın rafta olup olmadığı yalnız o kitabın olaylarına bağlıdır. Üyenin açık ödünç sayısını tutan bir sayaç için yanıt üyedir.

İkisi de gerekiyorsa tek bir anahtar yetmez. Bu durumda ya daha kaba bir anahtar seçilir — örneğin şube — ve koşutluk düşer, ya da sıraya bağlı olmayan bir etki tasarlanır. İkincisi genelde daha ucuzdur: olaya bir sürüm numarası konur ve tüketici yalnız kendi gördüğünden büyük sürümü uygular. Böyle bir etki geç gelen eski olayı sessizce yok sayar ve sıra garantisine hiç ihtiyaç duymaz.

Sıcak Anahtar

Bölümlemenin dengesizliği rastgele değildir; genellikle tek bir anahtarın diğerlerinden çok daha fazla olay üretmesinden gelir. Çok istenen bir kitap, işlemlerin yarısından fazlasını tek başına doğurabilir. Böyle bir anahtara sıcak anahtar (hot key) denir.

// sicak-anahtar.mjs — tek kitabin yuku tek bolumde toplanir; bolum eklemek onu bolmez
import { uretec, bolumlu } from "./bolum.mjs";

function sicakOlaylar(adet = 30, tohum = 7) {
  const rast = uretec(tohum);
  const liste = [];
  for (let sira = 0; sira < adet; sira++) {
    const kitapId = rast() < 0.6 ? 3 : 1 + Math.floor(rast() * 6);   // kitap 3 cok istenen kitap
    liste.push({ sira, kitapId, sure: 1 + Math.floor(rast() * 3) });
  }
  return liste;
}

const liste = sicakOlaylar();
const toplam = liste.reduce((t, o) => t + o.sure, 0);
const sicakYuk = liste.filter((o) => o.kitapId === 3).reduce((t, o) => t + o.sure, 0);
console.log(`olay=${liste.length}  toplam sure=${toplam}  kitap 3 olay=${liste.filter((o) => o.kitapId === 3).length} yuk=${sicakYuk}`);
console.log("bolum  sure  bolum yukleri");
for (const p of [1, 2, 4, 8]) {
  const k = bolumlu(liste, p);
  console.log(`${String(p).padStart(5)}${String(k.sure).padStart(6)}   ${k.yuk.join(" ")}`);
}

const p = 2;
const sicakBolum = 3 % p;
const bekleme = bolumlu(liste, p).sonuc.map((o) => ({ ...o, bekleme: o.bitis - o.sure }));
const ort = (d) => d.length === 0 ? "-" : (d.reduce((t, o) => t + o.bekleme, 0) / d.length).toFixed(1);
const engellenen = bekleme.filter((o) => o.yer === sicakBolum && o.kitapId !== 3);
let t = 0;                                  // ayni olaylar sicak anahtarsiz bir bolumde olsaydi
const yalniz = [...engellenen].sort((a, b) => a.sira - b.sira).map((o) => { const b = t; t += o.sure; return b; });
console.log(`bolum=2  sicak bolumdeki kitap 3 disi ${engellenen.length} olayin ortalama beklemesi = ${ort(engellenen)}`);
console.log(`         ayni olaylar sicak anahtarsiz bir bolumde olsaydi         = ` +
            `${(yalniz.reduce((a, b) => a + b, 0) / yalniz.length).toFixed(1)}`);

node sicak-anahtar.mjs

olay=30  toplam sure=59  kitap 3 olay=18 yuk=28
bolum  sure  bolum yukleri
    1    59   59
    2    41   18 41
    4    28   9 13 9 28
    8    28   0 10 3 28 9 3 6 0
bolum=2  sicak bolumdeki kitap 3 disi 5 olayin ortalama beklemesi = 11.0
         ayni olaylar sicak anahtarsiz bir bolumde olsaydi         = 5.0

Bölüm sayısını dörtten sekize çıkarmak süreyi hiç değiştirmedi: ikisinde de 28. Sekiz bölümde iki bölüm tamamen boş, biri 28 birimlik yükü tek başına taşıyor. Sayı tesadüf değil, kitap 3’ün toplam yüküne eşit. Sıra garantisi anahtarı bölünmez kıldığı için, sıcak anahtarın yükü sistemin alt sınırıdır; bölüm eklemek o sınırı düşürmez.

Son iki satır ikinci bir maliyeti gösteriyor. Aynı bölüme düşen ve sıcak anahtarla hiç ilgisi olmayan beş olay, ortalama 11 birim bekliyor; kendi başlarına bir bölümde olsalar 5 birim beklerlerdi. Sıcak anahtarın işleri, arkalarındaki ilgisiz işleri de geciktiriyor. Bu davranışa sıra başı engellemesi (head-of-line blocking) denir; ağ katmanlarında karşılaşılan aynı olgunun kuyruk düzlemindeki karşılığıdır.

Çözüm anahtarı değiştirmekten geçer. Sıcak anahtar için sıra garantisi gerçekten gerekliyse tek bölüm kaçınılmazdır ve tek çare o bölümün işini ucuzlatmaktır. Gerekli değilse anahtar inceltilir: kitap yerine “kitap ve olay türü” gibi bileşik bir anahtar, sıcak kitabın olaylarını birden çok bölüme dağıtır — ama bu, verilme ile iade arasındaki sırayı da bırakmak demektir. Karar yine aynı soruya döner: hangi çiftin sırası doğruluğu belirliyor.

Özet

• Sıra ihlali ters çift sayısıyla ölçülür; ödünç sisteminde anlamlı olan genel ters çift değil, aynı kitabın olayları arasındaki anahtar içi ters çifttir.
• Bölümlemesiz rekabet eden tüketicilerde işçi sayısı dörde çıkınca süre 44’ten 12’ye indi, ama anahtar içi ters çift sayısı sıfırdan üçe çıktı.
• Anahtara göre bölümlemede anahtar içi ters çift bölüm sayısından bağımsız olarak sıfır kaldı; genel ters çift altı bölümde 44’e çıktı. Bölümleme genel sırayı vererek anahtar içi sırayı satın alır.
• Bölüm sayısını artırmak koşutluk kapasitesini artırır, koşutluğu değil: dört bölümde yükler 3, 14, 21 ve 6 dağıldığı için süre üç bölümdekinden daha kötü çıktı.
• Sıcak anahtar bölünemediği için sistemin alt sınırını belirler — dört ve sekiz bölümde süre aynı 28 kaldı — ve aynı bölümdeki ilgisiz işlerin ortalama beklemesini 5 birimden 11 birime çıkardı.

Sonraki Adım

Şimdiye kadarki bütün ölçümlerde bir varsayım sessizce sürdü: yeniden denenen iş sonunda başarılı oluyor. Çökme geçiciydi, ikinci deneme işi bitiriyordu. Gerçekte bazı iletiler ikinci denemede de, onuncu denemede de başarısız olur — gövdesi bozuktur, atıfta bulunduğu üye silinmiştir, iş kuralı onu hiçbir zaman kabul etmeyecektir. En az bir kez kipinde böyle bir ileti kuyruktan hiç çıkmaz ve bölümlenmiş bir düzende arkasındaki bütün işleri durdurur. Sonraki ders bu iletileri kuyruktan çıkarıp yalıtan yapıyı kurar: deneme sayacı, eşik ve ölü mektup kuyruğu.