Zamanlama Kısıtları

Önceki dersin zamanlayıcısı tek soru soruyordu: kalan istek yeter mi. Yerleşimin başka yanları da vardır ve hiçbiri kapasiteyle ilgili değildir. Doğrulayıcının hızlı diski olan düğümlerde koşması, aynı servisin iki kopyasının aynı düğüme yığılmaması, faturalamanın doğrulayıcıyla aynı düğümde durması, bir bölge kaybında ayakta kopya kalması — bunların her biri, kapasitesi yeten bir düğümü uygunsuz hâle getirir.

Bu kısıtlar zamanlayıcıyı bir kısıt çözücüye çevirir. Karar aynı kalır (hangi kapsül hangi düğüme), ama karar artık bir arama uzayında yapılır: her kapsül için önce uygun düğüm kümesi hesaplanır, sonra o kümeden biri seçilir. Küme boşalırsa karar verilemez ve kapsül yerleşmez. Bu derste ölçülen şey budur: kısıt eklendikçe küme ne kadar daralıyor, hangi noktada boşalıyor.

Model üç bölgeye yayılmış dokuz düğümdür; iş yükü bölgesel ölçüm ağının (kurgu) üç servisidir. Gerçek bir küme koşturulmaz.

Kısıt Çözücü ve Uygun Düğüm Kümesi

Dört kısıt türü birikimli eklenir. Etiket seçimi düğümün bir etiketini şart koşar, yakınlık başka bir servisin varlığını, uzaklık aynı servisin yokluğunu, topoloji dağılımı ise bölgeler arası kopya farkını sınırlar. Seçim kuralı önceki dersteki gibidir: uygun kümedeki ilk düğüm.

Kısıtlar kendi küçük şemamızla yazılır. Düğüm bildirimi iki etiket taşır: bölge ve disk türü. Kapsül bildirimi üç alanla kısıt koyar — disk alanı düğümün disk etiketini şart koşar, uzaklik alanı aynı servisten kopya bulunmayan bir düğüm ister, yakinlik alanı adı verilen servisin bulunduğu düğümü ister. Topoloji dağılımı kapsüle değil çözücüye ait bir kuraldır ve bir sapma sayısıyla ayarlanır. Çözücü bu alanların dışında hiçbir şey okumaz; okumadığı her şey, düğümde ne kadar gerçek olursa olsun, kararın dışındadır.

// zamanlama/kisit.mjs — zamanlayici bir KISIT COZUCU olarak. Gercek kume degil, model.
// Kisitlar birikimli eklenir; her asamada uygun dugum kumesinin daralmasi olculur.
export const BOLGE = ["b1", "b2", "b3"];
// ZO7: uc bolge x uc dugum, dugum basina 1500 islemci birimi
// ZO8: hizli disk yalniz her bolgenin ilk dugumunde
export const DUGUMLER = BOLGE.flatMap((b, i) =>
  [0, 1, 2].map((j) => ({ ad: `${b}-d${j}`, bolge: b, disk: j === 0 ? "hizli" : "genel",
                          kapasite: 1500 })));

// ZO9: is yuku — dogrulayici hizli disk ister, faturalama dogrulayiciyla ayni dugumu ister
export const ISYUKU = [
  { servis: "dogrulayici", kopya: 6, birim: 650, disk: "hizli", uzaklik: true },
  { servis: "faturalama", kopya: 3, birim: 300, yakinlik: "dogrulayici", uzaklik: true },
  { servis: "okuma-toplayici", kopya: 9, birim: 420 },
];

export const kapsulleriAc = (yuk = ISYUKU) => yuk.flatMap((s) =>
  Array.from({ length: s.kopya }, (_, i) => ({ ...s, ad: `${s.servis}-${i + 1}` })));

// ZO10: topoloji dagilimi — bir servisin bolgeler arasi kopya farki en fazla 1
export const SAPMA = 1;

export function coz(kisit, yuk = ISYUKU, dugumler = DUGUMLER) {
  const durum = dugumler.map((d) => ({ ...d, dolu: 0, kapsul: [] }));
  const bolgeSayim = new Map();          // servis -> bolge -> adet
  const yerlesmeyen = [];
  const uygunlar = [];
  const say = (s, b) => (bolgeSayim.get(s) ?? {})[b] ?? 0;

  for (const k of kapsulleriAc(yuk)) {
    const uygun = durum.filter((d) => {
      if (d.dolu + k.birim > d.kapasite) return false;
      if (kisit.etiket && k.disk && d.disk !== k.disk) return false;
      if (kisit.uzaklik && k.uzaklik && d.kapsul.some((x) => x.servis === k.servis)) return false;
      if (kisit.yakinlik && k.yakinlik && !d.kapsul.some((x) => x.servis === k.yakinlik))
        return false;
      if (kisit.topoloji) {
        const enAz = Math.min(...BOLGE.map((b) => say(k.servis, b)));
        if (say(k.servis, d.bolge) + 1 - enAz > SAPMA) return false;
      }
      return true;
    });
    uygunlar.push(uygun.length);
    if (uygun.length === 0) { yerlesmeyen.push(k); continue; }
    const d = uygun[0];                  // ilk uyan dugum: kural geriye bakmaz
    d.dolu += k.birim; d.kapsul.push(k);
    const m = bolgeSayim.get(k.servis) ?? {};
    m[d.bolge] = (m[d.bolge] ?? 0) + 1; bolgeSayim.set(k.servis, m);
  }
  return { durum, yerlesmeyen, uygunlar, bolgeSayim };
}

export const dagilim = (o, servis) =>
  BOLGE.map((b) => (o.bolgeSayim.get(servis) ?? {})[b] ?? 0);

const ASAMA = [
  ["yalniz kapasite", {}],
  ["+ etiket secimi", { etiket: 1 }],
  ["+ yakinlik", { etiket: 1, yakinlik: 1 }],
  ["+ uzaklik", { etiket: 1, yakinlik: 1, uzaklik: 1 }],
  ["+ topoloji dagilimi", { etiket: 1, yakinlik: 1, uzaklik: 1, topoloji: 1 }],
];

if (process.argv[1].endsWith("kisit.mjs")) {
  const toplam = ISYUKU.reduce((t, s) => t + s.kopya, 0);
  console.log(`model: ${DUGUMLER.length} dugum / ${BOLGE.length} bolge, ${toplam} kapsul, ` +
    `hizli diskli dugum ${DUGUMLER.filter((d) => d.disk === "hizli").length}`);
  const s = (x, n = 13) => String(x).padStart(n);
  console.log(`${"asama".padEnd(22)}${s("uygun ort.")}${s("uygun en az")}${s("yerlesen")}` +
    `${s("yerlesemeyen")}${s("dolu dugum")}`);
  for (const [ad, kisit] of ASAMA) {
    const o = coz(kisit);
    const ort = o.uygunlar.reduce((t, x) => t + x, 0) / o.uygunlar.length;
    console.log(`${ad.padEnd(22)}${s(ort.toFixed(2))}${s(Math.min(...o.uygunlar))}` +
      `${s(toplam - o.yerlesmeyen.length)}${s(o.yerlesmeyen.length)}` +
      `${s(o.durum.filter((d) => d.kapsul.length > 0).length)}`);
  }
  console.log(`\nservis basina bolge dagilimi (${BOLGE.join("/")}):`);
  console.log(`${"asama".padEnd(22)}${s("dogrulayici")}${s("faturalama")}${s("toplayici", 16)}`);
  for (const [ad, kisit] of ASAMA) {
    const o = coz(kisit);
    console.log(`${ad.padEnd(22)}${s(dagilim(o, "dogrulayici").join("/"))}` +
      `${s(dagilim(o, "faturalama").join("/"))}${s(dagilim(o, "okuma-toplayici").join("/"), 16)}`);
  }
}

model: 9 dugum / 3 bolge, 18 kapsul, hizli diskli dugum 3
asama                    uygun ort.  uygun en az     yerlesen yerlesemeyen   dolu dugum
yalniz kapasite                5.83            3           18            0            7
+ etiket secimi                3.83            1           18            0            7
+ yakinlik                     3.17            0           15            3            6
+ uzaklik                      4.28            0           15            3            6
+ topoloji dagilimi            3.00            0           15            3            6

servis basina bolge dagilimi (b1/b2/b3):
asama                   dogrulayici   faturalama       toplayici
yalniz kapasite               6/0/0        0/3/0           0/7/2
+ etiket secimi               2/2/2        3/0/0           4/5/0
+ yakinlik                    2/2/2        0/0/0           6/3/0
+ uzaklik                     1/1/1        1/1/1           7/2/0
+ topoloji dagilimi           1/1/1        1/1/1           3/3/3

Daralma Tek Yönlü Değil

İlk tablo beklenen daralmayı gösteriyor: kapsül başına ortalama uygun düğüm sayısı 5,83’ten etiket seçimiyle 3,83’e, yakınlıkla 3,17’ye iniyor. En az uygun düğüm sayısı sütunu daha keskin — etiket seçimi bir kapsül için kümeyi tek düğüme indiriyor, yakınlık eklenince küme sıfırlanıyor ve üç faturalama kapsülü yerleşemiyor. Nedeni ikinci tabloda: doğrulayıcı kopyaları hızlı diskli üç düğümü ikişer ikişer doldurunca o düğümlerde faturalama için yer kalmıyor. Yakınlık kısıtı yer istemez, ama yer bırakılmasını gerektirir.

Sonraki satır dersin ters sonucudur. Uzaklık kısıtı eklenince ortalama uygun düğüm sayısı düşmüyor, 3,17’den 4,28’e çıkıyor. Kısıt sayısı arttığı hâlde arama uzayının genişlemesinin nedeni şudur: uzaklık, doğrulayıcıyı düğüm başına bir kopyaya indirdiği için üç kopya yerleşemez hâle geliyor ve onların tutmadığı kapasite sonraki kapsüllerin uygun kümesini büyütüyor. Yerleşen kapsül sayısı on beşte kalırken bileşimi değişiyor: faturalamanın üç kapsülü artık yerleşiyor, doğrulayıcının üç kopyası yerleşemiyor. Bir kısıt bir servisi kurtarırken başka bir servisi düşürüyor ve toplam sayı bunu göstermiyor.

Topoloji dağılımı satırında yerleşen sayısı yine on beş, ortalama uygun küme 3,00. Değişen tek şey son sütundadır: okuma toplayıcının bölge dağılımı 7/2/0 iken 3/3/3 oluyor. Bu kısıt hiçbir kapsülü düşürmüyor, yalnız yerleşimin şeklini değiştiriyor — ve karşılığı ancak bir bölge kaybedildiğinde görünür.

Bölge Kaybı, Çözümsüzlük ve Yanlış Etiket

// zamanlama/bolge.mjs — topoloji dagiliminin bolge kaybindaki karsiligi, kisitlarin birbirini
// imkansiz kilmasi ve etiket bildiriminin yanlisligi. Model onceki dosyadan gelir.
import { BOLGE, DUGUMLER, ISYUKU, coz, dagilim } from "./kisit.mjs";

const TAM = { etiket: 1, yakinlik: 1, uzaklik: 1, topoloji: 1 };
const TOPOLOJISIZ = { etiket: 1, yakinlik: 1, uzaklik: 1 };
const s = (x, n = 12) => String(x).padStart(n);
const SERVISLER = ["dogrulayici", "faturalama", "okuma-toplayici"];

// ZO12: bolge kaybi, o bolgedeki uc dugumun ayni anda erisilemez olmasidir.
console.log("bir bolge kaybinda ayakta kalan kopya (yerlesen / kayiptan sonra):");
console.log(`${"ayar".padEnd(16)}${"kayip".padEnd(8)}` +
  ["dogrulayici", "faturalama", "toplayici"].map((x) => s(x, 14)).join("") +
  s("toplam kalan", 14));
for (const [ad, kisit] of [["topoloji yok", TOPOLOJISIZ], ["topoloji var", TAM]]) {
  const o = coz(kisit);
  for (const kayip of BOLGE) {
    const kalan = SERVISLER.map((sv) => {
      const d = dagilim(o, sv), i = BOLGE.indexOf(kayip);
      return [d.reduce((t, x) => t + x, 0), d.reduce((t, x, j) => t + (j === i ? 0 : x), 0)];
    });
    console.log(`${ad.padEnd(16)}${kayip.padEnd(8)}` +
      kalan.map(([t, k]) => s(`${t} / ${k}`, 14)).join("") +
      s(kalan.reduce((t, [, k]) => t + k, 0), 14));
  }
}

// Kisitlarin birbirini imkansiz kilmasi: dogrulayici 6 kopya, hizli diskli dugum 3, her dugumde
// en fazla bir kopya. Ucuncu satir cozumsuzdur; sonuncu satir dugum etiketini genisletir.
const HIZLI6 = DUGUMLER.map((d, i) => ({ ...d, disk: i % 3 < 2 ? "hizli" : "genel" }));
const YALNIZ_D = ISYUKU.filter((x) => x.servis === "dogrulayici");
console.log("\ndogrulayici 6 kopya, kisit bilesimleri:");
console.log(`${"bilesim".padEnd(34)}${s("hizli dugum")}${s("yerlesen")}${s("cozumsuz")}`);
for (const [ad, kisit, dgm] of [
  ["kisitsiz", {}, DUGUMLER],
  ["yalniz etiket secimi", { etiket: 1 }, DUGUMLER],
  ["yalniz uzaklik", { uzaklik: 1 }, DUGUMLER],
  ["etiket + uzaklik", { etiket: 1, uzaklik: 1 }, DUGUMLER],
  ["etiket + uzaklik, 6 hizli dugum", { etiket: 1, uzaklik: 1 }, HIZLI6],
]) {
  const o = coz(kisit, YALNIZ_D, dgm);
  console.log(`${ad.padEnd(34)}${s(dgm.filter((d) => d.disk === "hizli").length)}` +
    `${s(6 - o.yerlesmeyen.length)}${s(o.yerlesmeyen.length)}`);
}

// ZO11: etiket bir bildirimdir, olcum degil. Bir dugumun etiketi eksik yazilirsa ne oluyor.
console.log("\netiket bildirimi bozulunca (tam kisit kumesi):");
console.log(`${"bildirim".padEnd(34)}${s("yerlesen", 14)}${s("yerlesemeyen", 14)}${s("dolu dugum", 14)}`);
for (const [ad, dgm] of [
  ["dogru", DUGUMLER],
  ["b2-d0 hizli etiketi eksik", DUGUMLER.map((d) => d.ad === "b2-d0" ? { ...d, disk: "genel" } : d)],
  ["b3-d1 yanlislikla hizli", DUGUMLER.map((d) => d.ad === "b3-d1" ? { ...d, disk: "hizli" } : d)],
]) {
  const o = coz(TAM, ISYUKU, dgm);
  console.log(`${ad.padEnd(34)}${s(18 - o.yerlesmeyen.length, 14)}${s(o.yerlesmeyen.length, 14)}` +
    `${s(o.durum.filter((d) => d.kapsul.length > 0).length, 14)}`);
}
const etiketKalem = DUGUMLER.length * 2;
const kapsulKalem = ISYUKU.reduce((t, x) =>
  t + x.kopya * ((x.disk ? 1 : 0) + (x.uzaklik ? 1 : 0) + (x.yakinlik ? 1 : 0)) + 1, 0);
console.log(`\nkisit cozucunun okudugu bildirim: ${etiketKalem} dugum etiketi + ` +
  `${kapsulKalem} kapsul kisiti = ${etiketKalem + kapsulKalem}; hicbiri olcum degil`);

bir bolge kaybinda ayakta kalan kopya (yerlesen / kayiptan sonra):
ayar            kayip      dogrulayici    faturalama     toplayici  toplam kalan
topoloji yok    b1               3 / 2         3 / 2         9 / 2             6
topoloji yok    b2               3 / 2         3 / 2         9 / 7            11
topoloji yok    b3               3 / 2         3 / 2         9 / 9            13
topoloji var    b1               3 / 2         3 / 2         9 / 6            10
topoloji var    b2               3 / 2         3 / 2         9 / 6            10
topoloji var    b3               3 / 2         3 / 2         9 / 6            10

dogrulayici 6 kopya, kisit bilesimleri:
bilesim                            hizli dugum    yerlesen    cozumsuz
kisitsiz                                     3           6           0
yalniz etiket secimi                         3           6           0
yalniz uzaklik                               3           6           0
etiket + uzaklik                             3           3           3
etiket + uzaklik, 6 hizli dugum              6           6           0

etiket bildirimi bozulunca (tam kisit kumesi):
bildirim                                yerlesen  yerlesemeyen    dolu dugum
dogru                                         15             3             6
b2-d0 hizli etiketi eksik                     13             5             5
b3-d1 yanlislikla hizli                       16             2             6

kisit cozucunun okudugu bildirim: 18 dugum etiketi + 21 kapsul kisiti = 39; hicbiri olcum degil

Üç Ölçüm

Bölge kaybı. Topoloji dağılımı yokken sonuç kaybedilen bölgeye bağlıdır: b1 düşerse dokuz okuma toplayıcıdan yalnız ikisi kalır, b3 düşerse dokuzu da kalır. Ayakta kalan toplam kopya altı ile on üç arasında salınır ve hangi sayının çıkacağını kimse seçmemiştir. Topoloji dağılımıyla üç satırın üçü de aynıdır: hangi bölge düşerse düşsün altı toplayıcı, toplam on kopya ayakta kalır. Kısıtın kazandırdığı şey ortalama değil, en kötü durumdur — en kötü durum altıdan ona çıkıyor, en iyi durum on üçten ona iniyor.

Çözümsüzlük. İkinci tablo iki kısıtın tek başına zararsız, birlikte çözümsüz olduğunu sayıyla gösteriyor. Yalnız etiket seçimiyle altı kopya yerleşiyor, yalnız uzaklıkla altı kopya yerleşiyor, ikisi birlikte yalnız üçü yerleşiyor ve üç kopya çözümsüz kalıyor. Çarpışan şey kısıtların kendisi değil, bir sayıdır: uzaklık kısıtı kopya sayısı kadar ayrı düğüm ister, etiket seçimi ise uygun düğüm sayısını üçe indirir. Son satır çözümü de sayıyla veriyor — hızlı diskli düğüm sayısı altıya çıkarıldığında altı kopyanın altısı yerleşiyor. Çözümsüzlük bildirimde değil, kümenin donanımındadır.

Yanlış etiket. Üçüncü tablo kısıtların dayandığı bilginin türünü ortaya koyuyor. Otuz dokuz bildirimin hiçbiri ölçüm değildir: on sekiz düğüm etiketi bir insan tarafından yazılmıştır ve yirmi bir kapsül kısıtı da öyle. Bir düğümün hızlı disk etiketi eksik kaldığında yerleşen kapsül on beşten on üçe iniyor; hata görünür, çünkü bir şey yerleşemiyor.

Asıl sorun sonraki satırdadır. Hızlı diski olmayan bir düğüm yanlışlıkla hızlı diye etiketlenince yerleşen kapsül sayısı on altıya çıkıyor. Çözücünün defterinde durum düzelmiştir; gerçekte bir doğrulayıcı kopyası yavaş diskli bir düğümde koşmaktadır ve bunu hiçbir sayaç bildirmez. Zamanlayıcı düğümün diskini ölçmez, etiketini okur. Yanlış kararın kaynağı yine bilgi kaleminin kendisi değil, kalemin bildirim olmasıdır.

Özet

• Kısıt eklendikçe kapsül başına ortalama uygun düğüm sayısı 5,83’ten 3,83’e, sonra 3,17’ye iniyor; yakınlık kısıtında küme sıfırlanıyor ve üç faturalama kapsülü yerleşemiyor.
• Kısıt eklemek arama uzayını her zaman daraltmaz: uzaklık kısıtı ortalamayı 3,17’den 4,28’e çıkarıyor, çünkü yerleşemeyen üç doğrulayıcının tutmadığı kapasite sonraki kapsüllere kalıyor.
• Aynı yerleşen sayısı farklı bileşimleri gizleyebilir: on beş kapsül yerleşirken bir kısıt faturalamanın üçünü kurtarıp doğrulayıcının üçünü düşürüyor.
• Topoloji dağılımı hiçbir kapsülü düşürmeden en kötü durumu düzeltiyor: bölge kaybında ayakta kalan kopya 6–13 aralığından sabit 10’a geçiyor, okuma toplayıcı dağılımı 7/2/0 yerine 3/3/3 oluyor.
• İki kısıt tek başına zararsız, birlikte çözümsüzdür: altı kopya, üç hızlı diskli düğüm ve düğüm başına tek kopya kuralı üç çözümsüz kapsül verir; hızlı düğüm sayısı altıya çıkınca çözümsüzlük biter.
• Çözücünün okuduğu otuz dokuz kalemin hiçbiri ölçüm değildir; yanlış yazılmış bir etiket yerleşen sayısını on beşten on altıya çıkarır ve hatayı görünmez kılar.

Sonraki Adım

Buraya kadarki kısıtlar kapsülün düğüm hakkında ne istediğini yazıyor. Ters yön hiç yazılmadı: düğümün hangi kapsülü kabul edeceği. Bölgesel ölçüm ağında gecelik toplu iş bütün diski ve belleği tüketiyor ve onunla aynı düğüme düşen bir servis kopyası gece boyunca yavaşlıyor. Bu düğümleri toplu işe ayırmanın yolu her kapsüle bir kısıt daha yazmak değildir; düğümün kendisine bir işaret koymak ve yalnız o işarete tolerans gösteren kapsüllerin gelmesine izin vermektir. Sonraki ders bu ayrımı ve ayrılan kapasitenin boş kalma oranını ölçer.