CAP Theorem — Senior chuqurlik

// KVORUM: N ta replika, W ta yozuv tasdig'i, R ta o'qish javobi
//
//   R + W > N   ->  o'qish va yozuv kvorumlari KESISHADI
//               ->  har o'qish kamida bitta ENG SO'NGGI nusxani ko'radi (kuchli)
//   W > N/2     ->  ikki yozuv bir vaqtda ajralgan to'plamga tushmaydi (tartib)
//
// N=3 misollar:
//   W=3, R=1  -> yozuv sekin (hammani kutadi), o'qish tez;  durable, past mavjudlik
//   W=1, R=1  -> ikkalasi tez;  R+W=2 <= 3 -> ESKIRISH mumkin (AP)
//   W=2, R=2  -> R+W=4 > 3 -> KUCHLI izchil, VA bittasi o'lsa ham ishlaydi (muvozanat)

PACELC: if P then A or C, Else L or C. Ya’ni ikki o‘q — bo‘linishda (A/C) va normal holatda (L/C):

Nega konsensus = CP

Paxos/Raft kabi konsensus algoritmlari amalni faqat ko‘pchilik (majority quorum) tasdiqlagach "committed" deb belgilaydi. Bu linearizability beradi. Lekin oqibati:

Ozchilik tomonda qolgan node’lar ko‘pchilikka yeta olmaydi, demak yangi amalni tasdiqlay olmaydi — o‘sha tomon mavjud emas (rad etadi/bloklaydi). Faqat ko‘pchilik tomon ishlaydi.

Asosiy hiyla — TrueTime

Taqsimlangan izchillikning tub muammosi — vaqt: node’lar soatlari mos kelmaydi, "qaysi yozuv oldin bo‘ldi?" aniq emas. Spanner buni TrueTime bilan hal qiladi: GPS + atom soatlari orqali vaqtni chegaralangan noaniqlik (ε) bilan biladi — TT.now() aniq nuqta emas, [eng erta, eng kech] oralig‘ini qaytaradi.

Commit-wait: Spanner tranzaksiyani commit qilganda, timestamp’ning noaniqlik oralig‘i o‘tguncha ataylab biroz kutadi. Shunda commit vaqti aniq "o‘tmishda" bo‘ladi — global, real-time tartib (external consistency) kafolatlanadi. Har shard esa Paxos bilan replikatsiya qilinadi.

Qanday ishlaydi

• Consistent hashing ring (4/6-mavzular): kalitlar halqada, har biri keyingi N node’ga replikatsiya qilinadi.
• Tunable izchillik: har amalda darajani tanlaysan — ONE / QUORUM / ALL (kvorum matematikasi, 2-bo‘lim).
• Gossip protocol: node’lar bir-birining holatini o‘zaro "mish-mish" orqali biladi (markaziy koordinatorsiz).
• Hinted handoff: o‘lik node uchun yozuv vaqtincha boshqasida saqlanadi, tuzalganda yetkaziladi.
• Read repair + anti-entropy: o‘qishda eskirgan replika sezilsa tuzatiladi; fonda Merkle daraxti bilan replikalar solishtiriladi.

CRDT g‘oyasi

Conflict-free Replicated Data Types — shunday tuzilganki, ularning birlashish (merge) amali matematik jihatdan kommutativ, assotsiativ va idempotent. Demak node’lar istalgan tartibda, istalgan necha marta sinxronlashsa ham — bir xil natijaga keladi (konvergensiya), hech qanday markaziy koordinatsiyasiz:

// G-COUNTER (grow-only): har node O'Z hisobini yuritadi; MERGE = har node bo'yicha MAX
class GCounter {
  counts: Record<string, number> = {};        // { nodeA: 3, nodeB: 5 }

  inc(node: string) { this.counts[node] = (this.counts[node] ?? 0) + 1; }
  value() { return Object.values(this.counts).reduce((a, b) => a + b, 0); }

  merge(other: GCounter) {                     // KONFLIKTSIZ birlashish
    for (const n in other.counts)
      this.counts[n] = Math.max(this.counts[n] ?? 0, other.counts[n]);
  }
}
// merge kommutativ + assotsiativ + idempotent
//   -> qaysi tartibda/necha marta birlashtirsang ham -> BIR XIL natija (konvergensiya)

Qaror — izchillik modeli va mexanizm tanlash

Senior tayyorlik cheklisti