Multi-region active-active: حل الـ conflicts بـ HLC و CRDTs

أهلًا بيك. النهارده هنكمّل الـ multi region، بس المرة دي active active: كل region بيقبل writes، مش region واحد primary والباقي بيقرا بس. بص على replica dot naive dot js. كل region عنده rows، والـ write بيحط updatedAt بالـ wall clock. ولما الـ replication بتوصل، اللي updatedAt بتاعه أكبر يكسب. ده اسمه last write wins. الـ code قصير وشكله منطقي. بس فيه مشكلتين كبار. الأولى: الـ row كله بيتبعت. يعني لو region عدّل الـ price و region تاني عدّل الـ stock، واحد بس هيكسب، والتعديل التاني يضيع خالص. التانية: الـ wall clock. الساعات في الـ servers عمرها ما بتبقى مضبوطة بالزبط. NTP بيقرّبها، بس ممكن يبقى فيه فرق مِلّي seconds، وساعات seconds، ولو الـ NTP وقع، دقايق. فاللي كتب الأول ممكن يكسب لمجرد إن ساعته قدّام.

ليه active active أصلًا؟ الـ latency: المستخدم في مصر يكتب على القاهرة، والمستخدم في ألمانيا يكتب على فرانكفورت. والـ availability: لو region وقع أو الـ link بينهم اتقطع، كل region يفضل شغّال لوحده. بس التمن: نفس الـ row ممكن يتعدّل في مكانين في نفس الوقت، ومفيش lock مشترك. ده الـ conflict، ولازم نحلّه بطريقة كل region يوصل بيها لنفس النتيجة من غير ما يكلّم التاني.

أول حاجة: نتجنّب الـ conflict لو نقدر. أسهل حل: كل row ليه home region. الـ orders بتاعة مستخدم مصري بتتكتب على القاهرة بس، وفرانكفورت تبعتها للقاهرة. كده مفيش conflict خالص على الـ orders دي. بس فيه data لازم تتكتب من أي مكان، زي الـ stock بتاع منتج بيتباع في البلدين، أو الـ cart بتاع مستخدم مسافر. دي اللي محتاجة conflict resolution.

المشكلة الأولى: الوقت. الحل اسمه HLC، يعني hybrid logical clock. كل timestamp فيه تلات حاجات: l، وده أكبر wall clock شفناه لحد دلوقتي. و c، وده counter. و node، اسم الـ region. الفكرة: الـ HLC قريب من الساعة الحقيقية، فتقدر تقراه كوقت. بس عمره ما بيرجع لورا، ولما بييجي له message من region تاني، بيتقدّم بعدها. فلو القاهرة شافت write من فرانكفورت وبعدين كتبت، الـ write بتاع القاهرة هيبقى أكبر، حتى لو ساعة القاهرة متأخرة.

الـ now بيشتغل إزاي؟ بناخد الساعة. لو أكبر من l، يبقى الوقت اتحرك: l بقى الساعة، و c صفر. لو الساعة زي l أو أقل منه، يعني اتنين writes في نفس الـ ms، أو الساعة رجعت لورا بسبب NTP، يبقى l زي ما هو و c يزيد واحد. والـ recv لما message يوصل: l الجديد هو أكبر واحد من تلاتة: l بتاعنا، و l بتاع الـ message، والساعة. والـ c بيكمّل من اللي كسب. ولو التلاتة اتعادلوا، بناخد أكبر c ونزوّد واحد.

وفيه حماية مهمة: الـ drift. لو جالك message ساعته قدّامك بساعة، وقبلته، الـ HLC بتاعك هيقفز ساعة لقدّام، وكل الـ writes الجاية هتبقى بالوقت ده. ولو الـ message ده كان من node ساعته بايزة، كل الـ cluster هيتبعه. فبنحط حد، maxDriftMs، دقيقة مسلًا. أي message قدّامنا بأكتر من كده بنرفضه بـ CLOCK DRIFT، ونعمل alert، لأن فيه ساعة لازم تتصلّح.

المشكلة التانية: الـ row كله بيكسب أو يخسر. الحل: نقسّم الـ row لـ fields، وكل field نوعه بيحدد الـ merge بتاعه. ده اللي اسمه CRDT، يعني conflict free replicated data type. data type ليه merge بيحقق تلات حاجات: commutative: merge a مع b زي b مع a. associative: الترتيب ما يفرقش لو عندك تلات regions. idempotent: لو نفس الـ state وصل مرتين، النتيجة ما تتغيّرش. لو التلاتة دول متحققين، أي region يعمل merge لأي حاجة وصلته بأي ترتيب، هيوصل لنفس النتيجة.

أول نوع: LWW register. ده لـ fields زي الـ name أو الـ price، اللي فيها قيمة واحدة بس، ومنطقي إن آخر تعديل يكسب. القيمة ومعاها HLC timestamp، والـ merge بياخد اللي الـ timestamp بتاعه أكبر. ولو اتعادلوا، الـ node بيفك التعادل، فالنتيجة واحدة في كل مكان. الفرق عن الـ naive: هنا الـ field لوحده هو اللي بيكسب، مش الـ row كله، والوقت من الـ HLC مش من الساعة.

بس LWW غلط تمامًا للـ stock. الـ stock عشرة. القاهرة باعت اتنين، فكتبت تمانية. فرانكفورت باعت واحد، فكتبت تسعة. الـ LWW هيختار واحد منهم، والصح سبعة. الحل: PN counter. بدل ما نخزّن الرقم، كل region بيخزّن قد إيه زوّد وقد إيه نقّص هو بس. p للزيادة، و n للنقص، ولكل واحد map من اسم الـ region لرقم. القيمة هي مجموع p ناقص مجموع n. والـ merge بياخد الأكبر لكل region، لأن العدّاد بتاع region واحد عمره ما بيقل، فالأكبر هو الأجدد.

تالت نوع: OR set، يعني observed remove set. ده للـ tags، أو الـ items في cart. المشكلة: القاهرة شالت tag اسمه new، وفي نفس الوقت فرانكفورت حطّته تاني. مين يكسب؟ في الـ OR set، كل add بياخد tag فريد، id مش متكرر. والـ remove بيشيل الـ tags اللي شافها بس. فالـ add الجديد في فرانكفورت ليه tag القاهرة ما شافتوش، فبيفضل. ده اسمه add wins. وده اللي المستخدم متوقعه غالبًا: لو حطّيت حاجة في الـ cart، ما تختفيش. والـ document كله: fields و counters و sets. الـ mergeDoc بيلف على كل key في الناحيتين. لو field موجود في region واحد بس، بيعدّي زي ما هو. ولو موجود في الاتنين، بيتعمل merge بالنوع بتاعه. والـ view بيحوّل الـ state ده لـ object عادي تبعته للـ client.

حاجات لازم تعرفها قبل ما تستخدم ده في الـ production. الـ tombstones بتكبر: كل remove بيسيب tag. محتاج garbage collection بعد ما تتأكد إن كل الـ regions شافته. الـ stock ممكن يبقى سالب: الـ PN counter بيجمع صح، بس لو القاهرة وفرانكفورت باعوا آخر قطعة في نفس الوقت، هتبقى سالب واحد. ده مش conflict resolution، ده invariant، ومحتاج يا إما reservation لكل region من الـ stock، يا إما write على الـ home region. الـ uniqueness، زي email مش متكرر، برضه CRDT ما يحلّوش.

وفي الـ databases الحقيقية؟ Postgres مع BDR أو pgactive بيعمل last update wins لكل row، وتقدر تكتب conflict handlers. CockroachDB و Spanner بيتجنّبوا الـ conflict أصلًا بـ consensus بين الـ regions، بس كل write بياخد latency الـ round trip. DynamoDB global tables بيعمل last writer wins. و Redis Enterprise active active بيستخدم CRDTs زي اللي هنكتبها. فالـ CRDTs بتاعتك مفيدة لما الـ database ما بتحلّش ده لوحدها، أو لما تحب تحط الـ merge في الـ application. التحدي. عندك lab dot js بيعمل region في القاهرة وواحد في فرانكفورت، والـ link بينهم بيقع، و test dot js. والمطلوب crdt dot js. كل التفاصيل في الكومنت: compareHlc، و createHlc بالـ now والـ recv والـ CLOCK DRIFT، و LWW register، و PN counter، و OR set، و mergeDoc و view. وكل حاجة بترجّع object جديد.

الحل. compareHlc بيقارن l وبعدين c وبعدين node. الـ HLC فيه l و c، والـ now بيزوّد c لو الساعة ما اتحركتش. الـ recv بيرفض الـ drift الكبير، وبياخد الأكبر من تلاتة. الـ counter بيعمل copy لـ p و n وبيزوّد ناحية واحدة. الـ counterMerge بياخد الأكبر لكل node. الـ OR set: الـ remove بيحط كل الـ tags بتاعة الـ element في tombs، والـ merge بيجمع الاتنين. والـ mergeDoc بيلف على الـ keys بـ mergeEach. نشغّل lab dot js.

// crdt.js: HLC و LWW register و PN counter و OR set: كل merge بيوصل لنفس النتيجة في كل region
export function compareHlc(a, b) {
  if (a.l !== b.l) return a.l < b.l ? -1 : 1;
  if (a.c !== b.c) return a.c < b.c ? -1 : 1;
  if (a.node === b.node) return 0;
  return a.node < b.node ? -1 : 1;
}

export function createHlc(node, now = Date.now, { maxDriftMs = 60_000 } = {}) {
  let l = 0, c = 0;
  const tick = () => {
    const pt = now();
    if (pt > l) { l = pt; c = 0; } else c++;
    return { l, c, node };
  };
  const recv = (remote) => {
    const pt = now();
    if (remote.l - pt > maxDriftMs) {
      throw Object.assign(new Error(`clock drift ${remote.l - pt}ms from ${remote.node}`), { code: "CLOCK_DRIFT" });
    }
    const m = Math.max(l, remote.l, pt);
    if (m === l && m === remote.l) c = Math.max(c, remote.c) + 1;
    else if (m === l) c++;
    else if (m === remote.l) c = remote.c + 1;
    else c = 0;
    l = m;
    return { l, c, node };
  };
  return { now: tick, recv };
}

// LWW register: { value, ts }
export const lwwSet = (value, ts) => ({ value, ts });
export function lwwMerge(a, b) {
  if (!a) return b;
  if (!b) return a;
  return compareHlc(a.ts, b.ts) >= 0 ? a : b;
}

// PN counter: { p: { node: n }, n: { node: n } }
export const counterNew = () => ({ p: {}, n: {} });
export function counterAdd(s, node, by) {
  if (!Number.isInteger(by)) throw new TypeError("counter delta must be an integer");
  const side = by >= 0 ? "p" : "n";
  const next = { p: { ...s.p }, n: { ...s.n } };
  next[side][node] = (next[side][node] ?? 0) + Math.abs(by);
  return next;
}
const sum = (o) => Object.values(o).reduce((x, y) => x + y, 0);
export const counterValue = (s) => sum(s.p) - sum(s.n);
function maxMap(a, b) {
  const out = { ...a };
  for (const [k, v] of Object.entries(b)) out[k] = Math.max(out[k] ?? 0, v);
  return out;
}
export const counterMerge = (a, b) => ({ p: maxMap(a.p, b.p), n: maxMap(a.n, b.n) });

// OR set: { adds: { tag: element }, tombs: { tag: true } } ← add wins
export const setNew = () => ({ adds: {}, tombs: {} });
export function setAdd(s, el, tag) {
  return { adds: { ...s.adds, [tag]: el }, tombs: { ...s.tombs } };
}
export function setRemove(s, el) {
  const tombs = { ...s.tombs };
  for (const [tag, e] of Object.entries(s.adds)) if (e === el) tombs[tag] = true;
  return { adds: { ...s.adds }, tombs };
}
export function setValues(s) {
  const live = Object.entries(s.adds).filter(([tag]) => !s.tombs[tag]).map(([, e]) => e);
  return [...new Set(live)].sort();
}
export const setMerge = (a, b) => ({ adds: { ...a.adds, ...b.adds }, tombs: { ...a.tombs, ...b.tombs } });

// document: { fields: { name: lww }, counters: { name: pn }, sets: { name: orset } }
function mergeEach(a = {}, b = {}, merge, empty) {
  const out = {};
  for (const k of new Set([...Object.keys(a), ...Object.keys(b)])) out[k] = merge(a[k] ?? empty(), b[k] ?? empty());
  return out;
}
export function mergeDoc(a, b) {
  return {
    fields: mergeEach(a.fi
…

$ node lab.js
① الـ naive: الـ row كله بيتبعت، واللي updatedAt بتاعه أكبر يكسب
   البداية: {"name":"Mug","price":100,"stock":10,"tags":["new"]}
   ✂️  الـ link بين الـ regions وقع
   فرانكفورت: price ← 120، وطلب واحد (stock ناقص واحد)
   القاهرة: طلبين (stock ناقص اتنين)، و tag اسمه sale
   🔗 الـ link رجع، وكل region بعت الـ row بتاعه للتاني
   القاهرة: {"price":120,"stock":9,"tags":["new"]}
   فرانكفورت: {"price":120,"stock":9,"tags":["new"]}
   المفروض: price 120 و stock سبعة و tags فيها new و sale
   ❌ القاهرة اتكتبت آخر واحدة، بس ساعتها متأخرة، ففرانكفورت كسبت كل حاجة: طلبين اتنسوا و sale راح

② بالـ CRDTs: كل field ليه merge خاص بيه، وكل region عنده HLC
   البداية: {"name":"Mug","price":100,"stock":10,"tags":["new"]}
   ✂️  الـ link وقع
   🔗 الـ link رجع: كل region عمل merge للتاني
   القاهرة: {"name":"Mug","price":120,"stock":7,"tags":["new","sale"]}
   فرانكفورت: {"name":"Mug","price":120,"stock":7,"tags":["new","sale"]}
   ✅ الاتنين واحد، ومفيش طلب ضاع

③ remove و add في نفس الوقت على نفس الـ tag
   القاهرة شالت new، وفرانكفورت حطّت new تاني من غير ما تشوف الـ remove
   بعد الـ merge: ["new","sale"] ← الـ add كسب، لأن الـ remove ما شافش الـ tag الجديد

④ الساعة اللي رجعت 
…

الأول الـ naive: فرانكفورت غيّرت الـ price وباعت قطعة، والقاهرة باعت قطعتين وحطّت sale. القاهرة كتبت آخر واحدة، بس ساعتها متأخرة دقيقتين، ففرانكفورت كسبت كل حاجة: الـ stock تسعة بدل سبعة، والـ sale راح. التاني بالـ CRDTs: الاتنين وصلوا لنفس الـ state، والـ price عشرين ومِيّة، والـ stock سبعة، والـ tags الاتنين. التالت: remove و add في نفس الوقت، والـ add كسب. والرابع: الساعة رجعت لورا، والـ HLC ما رجعش. نشغّل test dot js.

$ node test.js
✅ 1 compareHlc: الـ l الأول، وبعدين الـ c، وبعدين اسم الـ node 
✅ 2 now: نفس الوقت يزوّد c، والساعة لو رجعت لورا الـ HLC ما يرجعش [{"l":1000,"c":0,"node":"cai"},{"l":1000,"c":1,"node":"cai"},{"l":1000,"c":2,"node":"cai"},{"l":2000,"c":0,"node":"cai"}]
✅ 3 recv: الـ l = أكبر واحد، والـ c بيكمّل من اللي كسب [{"l":9000,"c":5,"node":"fra"},{"l":9000,"c":6,"node":"fra"},{"l":9000,"c":7,"node":"fra"},{"l":20000,"c":0,"node":"fra"}]
✅ 4 recv برسالة ساعتها قدّام أكتر من maxDriftMs ← CLOCK_DRIFT، والـ default دقيقة 
✅ 5 LWW: القاهرة ساعتها متأخرة دقيقتين، بس كتبت بعد ما شافت فرانكفورت ← القاهرة تكسب {"l":220000,"c":2,"node":"cai"}
✅ 6 LWW: نفس الـ l والـ c ← الـ node الأكبر يكسب في الاتجاهين، و null يرجّع التاني 
✅ 7 PN counter: الزيادة في p والنقص في n لكل node {"p":{"cai":10,"fra":3},"n":{"cai":2,"fra":1}}
✅ 8 counterMerge: طلبين في القاهرة وطلب في فرانكفورت ← سبعة، والـ merge commutative و idempotent {"p":{"cai":10},"n":{"cai":2,"fra":1}}
✅ 9 counterAdd و counterMerge ما بيغيّروش الـ state الأصلي 
✅ 10 OR set: setValues مترتّبة ومن غير تكرار، و remove بيشيل كل الـ tags اللي شافها 
✅ 11 remove و add في نفس الوقت ← الـ add يكسب في الاتجاهين 
✅ 12 setMerge: associative و idem
…

كله نجح. لو حابب تجرّب بإيدك، فيه try dot js: اعمل HLC، وشوف الـ now مرتين ورا بعض في نفس الـ ms، واعمل counter في region وواحد في التاني، واعمل merge. الدرس الجاي: readiness و liveness و startup probes. إزاي Kubernetes يعرف إن الـ pod جاهز ولا عايش.

// replica.naive.js: كل region بيكتب لوحده، ولما الـ replication ترجع: اللي updatedAt بتاعه أكبر يكسب
export function createReplica(region, now = Date.now) {
  const rows = new Map();
  return {
    region,
    write(id, patch) {
      const row = { ...(rows.get(id) ?? {}), ...patch, updatedAt: now() };
      rows.set(id, row);
      return row;
    },
    read: (id) => rows.get(id),
    // الـ replication: الـ row كله بيتبعت، واللي ساعته أحدث يكسب
    receive(id, remote) {
      const local = rows.get(id);
      if (!local || remote.updatedAt > local.updatedAt) rows.set(id, remote);
    },
  };
}

// lab.js: region في القاهرة و region في فرانكفورت، بيكتبوا الاتنين في نفس الوقت، والـ link بينهم واقع
import { createReplica } from "./replica.naive.js";
import { createHlc, lwwSet, counterNew, counterAdd, setNew, setAdd, setRemove, mergeDoc, view } from "./crdt.js";

let real = 1_700_000_000_000;
const cairoClock = () => real - 120_000; // ساعة القاهرة متأخرة دقيقتين
const fraClock = () => real;
const step = (ms) => { real += ms; };

console.log("① الـ naive: الـ row كله بيتبعت، واللي updatedAt بتاعه أكبر يكسب");
const cai = createReplica("cairo", cairoClock);
const fra = createReplica("frankfurt", fraClock);
const start = { name: "Mug", price: 100, stock: 10, tags: ["new"] };
cai.write("p1", start); fra.receive("p1", cai.read("p1"));
console.log("   البداية:", JSON.stringify(start));
console.log("   ✂️  الـ link بين الـ regions وقع");
step(1000); fra.write("p1", { price: 120 });
step(1000); fra.write("p1", { stock: fra.read("p1").stock - 1 });
step(1000); cai.write("p1", { stock: cai.read("p1").stock - 2 });
step(1000); cai.write("p1", { tags: [...cai.read("p1").tags, "sale"] });
console.log("   فرانكفورت: price ← 120، وطلب واحد (stock ناقص واحد)");
console.log("   القاهرة: طلبين (stock ناقص اتنين)، و tag اسمه sale");
console.log("   🔗 الـ link رجع، وكل region بعت الـ row بتاعه للتاني");
const a = cai.read("p1"), b = fra.read("p1");
cai.receive("p1", b); fra.receive("p1", a);
const show = (r) => JSON.stringify({ price: r.price, stock: r.stock, tags: r.tags });
console.log("   القاهرة:", show(cai.read("p1")));
console.log("   فرانكفورت:", show(fra.read("p1")));
console.log("   المفروض: price 120 و stock سبعة و tags فيها new و sale");
console.log("   ❌ القاهرة اتكتبت آخر واحدة، بس ساعتها متأخرة، ففرانكفورت كسبت كل حاجة: طلبين اتنسوا و sale راح");

console.log("\n② بالـ CRDTs: كل field ليه merge خاص بيه، وكل region عنده HLC");
real = 1_700_000_000_000;
const hc = createHlc("cairo", cairoClock), hf = createHlc("frankfurt", fraClock);
let dc = { fields: { name: lwwSet("Mug", hc.now()), price: lwwSet(100, hc.now()) }, counters: { stock: counterAdd(counterNew(), "cairo", 10) }, sets: { tags: setAdd(setNew(), "new", "cairo:1") } };
hf.recv(dc.fields.price.ts);
let df = mergeDoc({}, dc);
console.log("   البداية:", JSON.stringify(view(df)));
console.log("   ✂️  الـ link وقع");
step(1000); df = { ...df, fields: { ...df.fields, price: lwwSet(120, hf.now()) } };
step(1000); df = { ...df, counters: { stock: counterAdd(df.counters.stock, "frankfurt", -1) } };
step(1000); dc = { ...dc, counters: { stock: counterAdd(dc.counters.stock, "cairo", -2) } };
step(1000); dc = { ...dc, sets: { tags: setAdd(dc.sets.tags, "sale", "cairo:2") } };
console.log("   🔗 الـ link رجع: كل region عمل merge للتاني");
const m1 = mergeDoc(dc, df), m2 = mergeDoc(df, dc);
console.log("   القاهرة:", JSON.stringify(view(m1)));
console.log("   فرانكفورت:", JSON.stringify(view(m2)));
console.log("  ", JSON.stringify(view(m1)) === JSON.stringify(view(m2)) ? "✅ الاتنين واحد، ومفيش طلب ضاع
…