1/* âââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââ 2 Simulators: quorums, vector clocks, Count-Min Sketch, gossip 3 Same contract as the other simulator files: { id, title, slugs, blurb, render(), mount(root), unmount(root) } 4 âââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââ */ 5 6window.SIMULATORS = window.SIMULATORS || {}; 7 8(() => { 9 const esc = s => String(s).replace(/[&<>"']/g, c => ({ '&': '&', '<': '<', '>': '>', '"': '"', "'": ''' }[c])); 10 const pickRandom = (arr, k) => [...arr].sort(() => Math.random() - 0.5).slice(0, k); 11 12 // Tracks listeners/timers per mount so unmount can always clean up 13 function lifecycle() { 14 const offs = []; 15 const timers = new Set(); 16 return { 17 on(el, ev, fn) { if (!el) return; el.addEventListener(ev, fn); offs.push(() => el.removeEventListener(ev, fn)); }, 18 every(ms, fn) { const t = setInterval(fn, ms); timers.add(t); return t; }, 19 stop(t) { clearInterval(t); timers.delete(t); }, 20 dispose() { offs.splice(0).forEach(f => f()); timers.forEach(t => clearInterval(t)); timers.clear(); } 21 }; 22 } 23 24 // ââ Quorum reads and writes (N, R, W) âââââââââââââââââââââââ 25 window.SIMULATORS['quorum-nrw'] = { 26 id: 'quorum-nrw', 27 title: 'Quorum Explorer (N, R, W)', 28 slugs: ['case-amazon-dynamo'], 29 blurb: 'Tune N, R and W, fail replicas, and see when a read can return stale data.', 30 render() { 31 return ` 32 <div class="simulator-card" id="sim-quorum"> 33 <div class="simulator-card__header"> 34 <div class="simulator-card__title">Quorum Explorer (N, R, W)</div> 35 <span class="simulator-card__status" id="q-rule"></span> 36 </div> 37 <p class="simulator-card__description">A write is acknowledged once W replicas store it; the rest catch up only when you run anti-entropy. A read asks R live replicas and returns the highest version. Click a replica to fail or recover it.</p> 38 <div class="simulator-card__grid"> 39 <label><span class="simulator-card__label">N replicas: <b id="q-n-val">3</b></span><input type="range" id="q-n" min="3" max="7" value="3"></label> 40 <label><span class="simulator-card__label">W write quorum: <b id="q-w-val">2</b></span><input type="range" id="q-w" min="1" max="3" value="2"></label> 41 <label><span class="simulator-card__label">R read quorum: <b id="q-r-val">2</b></span><input type="range" id="q-r" min="1" max="3" value="2"></label> 42 </div> 43 <div class="sim-row" id="q-replicas"></div> 44 <div class="simulator-card__controls"> 45 <button class="btn btn--primary btn--sm" id="q-write">Write next version</button> 46 <button class="btn btn--outline btn--sm" id="q-read">Read</button> 47 <button class="btn btn--outline btn--sm" id="q-sync">Run anti-entropy</button> 48 <button class="btn btn--sm" id="q-reset">Reset</button> 49 </div> 50 <div class="simulator-card__log" id="q-log"><div class="simulator-card__log-header">Event log</div></div> 51 </div>`; 52 }, 53 mount(root) { 54 const lc = this._lc = lifecycle(); 55 const $ = s => root.querySelector(s); 56 let N = 3, W = 2, R = 2, latest = 0, replicas = []; 57 const reset = () => { latest = 0; replicas = Array.from({ length: N }, (_, i) => ({ id: i + 1, v: 0, up: true, hit: '' })); }; 58 const log = (msg, kind = '') => { const d = document.createElement('div'); d.className = 'sim-log-line ' + kind; d.textContent = msg; $('#q-log').insertBefore(d, $('#q-log').children[1] || null); }; 59 60 const draw = () => { 61 $('#q-n-val').textContent = N; $('#q-w-val').textContent = W; $('#q-r-val').textContent = R; 62 const strict = R + W > N; 63 const rule = $('#q-rule'); 64 rule.textContent = `R + W = ${R + W} ${strict ? '>' : 'â¤'} N = ${N} â ${strict ? 'read and write sets always overlap' : 'stale reads possible'}`; 65 rule.style.color = strict ? 'var(--success)' : 'var(--warning)'; 66 $('#q-replicas').innerHTML = replicas.map(r => ` 67 <button class="sim-node ${r.up ? '' : 'is-down'} ${r.hit}" data-id="${r.id}" title="Click to ${r.up ? 'fail' : 'recover'} replica ${r.id}">
68 <span class="sim-node__name">Replica ${r.id}</span> 69 <span class="sim-node__value">${r.up ? 'v' + r.v : 'down'}</span> 70 </button>`).join(''); 71 }; 72 const clearHits = () => replicas.forEach(r => { r.hit = ''; }); 73 const syncSliders = () => { 74 $('#q-w').max = N; $('#q-r').max = N; 75 W = Math.min(W, N); R = Math.min(R, N); 76 $('#q-w').value = W; $('#q-r').value = R; 77 }; 78 79 lc.on($('#q-n'), 'input', e => { N = +e.target.value; syncSliders(); reset(); clearHits(); draw(); }); 80 lc.on($('#q-w'), 'input', e => { W = +e.target.value; draw(); }); 81 lc.on($('#q-r'), 'input', e => { R = +e.target.value; draw(); }); 82 lc.on($('#q-replicas'), 'click', e => { 83 const b = e.target.closest('.sim-node'); if (!b) return; 84 const r = replicas.find(x => x.id === +b.dataset.id); r.up = !r.up; 85 log(`Replica ${r.id} ${r.up ? 'recovered (still holds v' + r.v + ')' : 'failed'}`); 86 clearHits(); draw(); 87 }); 88 lc.on($('#q-write'), 'click', () => { 89 clearHits(); 90 const live = replicas.filter(r => r.up); 91 if (live.length < W) { log(`Write v${latest + 1} FAILED: only ${live.length} live replicas, W = ${W}`, 'is-bad'); draw(); return; } 92 latest++; 93 pickRandom(live, W).forEach(r => { r.v = latest; r.hit = 'is-write'; }); 94 log(`Write v${latest} acknowledged by ${W} replica(s); ${N - W} still hold older data`); 95 draw(); 96 }); 97 lc.on($('#q-read'), 'click', () => { 98 clearHits(); 99 const live = replicas.filter(r => r.up); 100 if (live.length < R) { log(`Read FAILED: only ${live.length} live replicas, R = ${R}`, 'is-bad'); draw(); return; } 101 const asked = pickRandom(live, R); asked.forEach(r => { r.hit = 'is-read'; }); 102 const got = Math.max(...asked.map(r => r.v)); 103 const stale = got < latest; 104 log(`Read asked replicas ${asked.map(r => r.id).join(', ')} â v${got}${stale ? ` (STALE, latest is v${latest})` : ' (latest)'}`, stale ? 'is-bad' : 'is-good'); 105 draw(); 106 }); 107 lc.on($('#q-sync'), 'click', () => { 108 clearHits(); 109 let n = 0; replicas.forEach(r => { if (r.up && r.v < latest) { r.v = latest; n++; } }); 110 log(`Anti-entropy repaired ${n} live replica(s) to v${latest}`); 111 draw(); 112 }); 113 lc.on($('#q-reset'), 'click', () => { reset(); draw(); log('Reset'); }); 114 reset(); syncSliders(); draw(); 115 }, 116 unmount() { this._lc?.dispose(); } 117 }; 118 119 // ââ Vector clocks vs Lamport clocks âââââââââââââââââââââââââ 120 window.SIMULATORS['vector-clocks'] = { 121 id: 'vector-clocks', 122 title: 'Vector Clocks vs Lamport Clocks', 123 slugs: ['clocks-and-ordering', 'clock-skew-and-id-ordering'], 124 blurb: 'Create events and messages between three processes, then compare any two events.', 125 render() { 126 const procs = ['A', 'B', 'C']; 127 return ` 128 <div class="simulator-card" id="sim-vc"> 129 <div class="simulator-card__header"> 130 <div class="simulator-card__title">Vector Clocks vs Lamport Clocks</div> 131 <button class="btn btn--sm" id="vc-reset">Reset</button> 132 </div> 133 <p class="simulator-card__description">Each event gets a Lamport timestamp L and a vector clock [A, B, C]. Lamport order is consistent with causality, but only vector clocks can tell you two events are concurrent.</p> 134 <div class="sim-cols"> 135 ${procs.map(p => ` 136 <div class="sim-col"> 137 <div class="sim-col__head">Process ${p}</div> 138 <div class="simulator-card__controls"> 139 <button class="btn btn--outline btn--sm" data-act="local" data-p="${p}">Local event</button> 140 ${procs.filter(q => q !== p).map(q => `<button class="btn btn--outline btn--sm" data-act="send" data-p="${p}" data-to="${q}">Send â ${q}</button>`).join('')} 141 </div> 142 <div class="sim-col__events" id="vc-events-${p}"></div> 143 </div>`).join('')} 144 </div> 145 <div class="simulator-card__controls"> 146 <label>Compare <select class="simulator-card__input sim-select" id="vc-a"></select></label> 147 <label>with <select class="simulator-card__input sim-select" id="vc-b"></select></label> 148 </div> 149 <div class="sim-verdict" id="vc-verdict">Create a few events, then pick two to compare.</div> 150 </div>`; 151 }, 152 mount(root) { 153 const lc = this._lc = lifecycle(); 154 const $ = s => root.querySelector(s); 155 const P = ['A', 'B', 'C']; 156 let events, clocks, lamport, seq; 157 const reset = () => { events = []; clocks = { A: [0, 0, 0], B: [0, 0, 0], C: [0, 0, 0] }; lamport = { A: 0, B: 0, C: 0 }; seq = 0; }; 158 const record = (p, label, vc, L) => { const e = { id: 'e' + (++seq), p, label, vc: [...vc], L }; events.push(e); return e; }; 159 160 const tick = p => { clocks[p][P.indexOf(p)]++; lamport[p]++; }; 161 const local = p => { tick(p); record(p, 'local', clocks[p], lamport[p]); }; 162 const send = (p, q) => { 163 tick(p); 164 const msgVc = [...clocks[p]], msgL = lamport[p]; 165 record(p, `send â ${q}`, clocks[p], lamport[p]); 166 // receiver merges: element-wise max, then its own tick 167 clocks[q] = clocks[q].map((v, i) => Math.max(v, msgVc[i])); 168 lamport[q] = Math.max(lamport[q], msgL); 169 tick(q); 170 record(q, `recv â ${p}`, clocks[q], lamport[q]); 171 }; 172 const leq = (a, b) => a.every((v, i) => v <= b[i]); 173 const compare = (x, y) => { 174 if (x.id === y.id) return 'Same event.'; 175 const lam = `Lamport: ${x.id} L=${x.L}, ${y.id} L=${y.L}.`; 176 if (leq(x.vc, y.vc)) return `<b>${x.id} â ${y.id}</b>: ${x.id} happened-before ${y.id} (every entry of [${x.vc}] ⤠[${y.vc}]). ${lam}`; 177 if (leq(y.vc, x.vc)) return `<b>${y.id} â ${x.id}</b>: ${y.id} happened-before ${x.id} (every entry of [${y.vc}] ⤠[${x.vc}]). ${lam}`; 178 const lamNote = x.L === y.L 179 ? 'Their Lamport timestamps tie (a process-id tiebreak would order them arbitrarily).' 180 : `Lamport still puts ${x.L < y.L ? x.id : y.id} first, which looks like causality but is not.`; 181 return `<b>${x.id} ⥠${y.id}: concurrent.</b> Neither vector dominates ([${x.vc}] vs [${y.vc}]). ${lam} ${lamNote}`; 182 }; 183 const draw = () => { 184 P.forEach(p => { 185 $('#vc-events-' + p).innerHTML = events.filter(e => e.p === p).map(e => 186 `<div class="sim-event"><span class="sim-event__id">${e.id}</span> ${esc(e.label)}<span class="sim-event__vc">L=${e.L} · [${e.vc.join(', ')}]</span></div>`).join('') || '<div class="sim-muted">no events</div>'; 187 }); 188 const opts = events.map(e => `<option value="${e.id}">${e.id} (${e.p}: ${esc(e.label)})</option>`).join(''); 189 const a = $('#vc-a').value, b = $('#vc-b').value; 190 $('#vc-a').innerHTML = opts; $('#vc-b').innerHTML = opts; 191 if (events.length) { 192 $('#vc-a').value = events.some(e => e.id === a) ? a : events[0].id; 193 $('#vc-b').value = events.some(e => e.id === b) ? b : events[events.length - 1].id; 194 verdict(); 195 } else $('#vc-verdict').textContent = 'Create a few events, then pick two to compare.'; 196 }; 197 const verdict = () => { 198 const x = events.find(e => e.id === $('#vc-a').value), y = events.find(e => e.id === $('#vc-b').value); 199 if (x && y) $('#vc-verdict').innerHTML = compare(x, y); 200 }; 201 lc.on(root.querySelector('#sim-vc'), 'click', e => { 202 const b = e.target.closest('button[data-act]'); if (!b) return; 203 if (b.dataset.act === 'local') local(b.dataset.p); else send(b.dataset.p, b.dataset.to); 204 draw(); 205 }); 206 lc.on($('#vc-a'), 'change', verdict); 207 lc.on($('#vc-b'), 'change', verdict); 208 lc.on($('#vc-reset'), 'click', () => { reset(); draw(); }); 209 reset(); 210 // seed a small scenario with one concurrent pair 211 local('A'); send('A', 'B'); local('C'); 212 draw(); 213 },
214 unmount() { this._lc?.dispose(); } 215 }; 216 217 // ââ Count-Min Sketch ââââââââââââââââââââââââââââââââââââââââ 218 window.SIMULATORS['count-min'] = { 219 id: 'count-min', 220 title: 'Count-Min Sketch', 221 slugs: ['count-min-sketch', 'top-k-heavy-hitters'], 222 blurb: 'Stream items into a d à w counter grid and compare estimated vs true counts.', 223 render() { 224 return ` 225 <div class="simulator-card" id="sim-cms"> 226 <div class="simulator-card__header"> 227 <div class="simulator-card__title">Count-Min Sketch (d = 3 rows)</div> 228 <span class="simulator-card__status" id="cms-bound"></span> 229 </div> 230 <p class="simulator-card__description">Each item increments one counter per row. The estimate is the minimum across its rows, so it never under-counts; collisions only push it up. Narrow grids collide more.</p> 231 <div class="simulator-card__grid"> 232 <label><span class="simulator-card__label">Width w: <b id="cms-w-val">8</b></span><input type="range" id="cms-w" min="4" max="32" step="4" value="8"></label> 233 <label><span class="simulator-card__label">Item</span><input class="simulator-card__input" id="cms-item" value="cats" maxlength="24"></label> 234 </div> 235 <div class="simulator-card__controls"> 236 <button class="btn btn--primary btn--sm" id="cms-add">Add item</button> 237 <button class="btn btn--outline btn--sm" id="cms-query">Estimate item</button> 238 <button class="btn btn--outline btn--sm" id="cms-stream">Stream 500 Zipf items</button> 239 <button class="btn btn--sm" id="cms-reset">Reset</button> 240 </div> 241 <div class="sim-grid-wrap"><table class="sim-grid" id="cms-grid"></table></div> 242 <div class="sim-verdict" id="cms-verdict">Add items or stream a skewed workload.</div> 243 <div class="sim-topk" id="cms-topk"></div> 244 </div>`; 245 }, 246 mount(root) { 247 const lc = this._lc = lifecycle(); 248 const $ = s => root.querySelector(s); 249 const D = 3, SEEDS = [0x9e3779b1, 0x85ebca6b, 0xc2b2ae35]; 250 const WORDS = ['cats', 'dogs', 'kafka', 'redis', 'raft', 'paxos', 'bloom', 'shard', 'cache', 'queue', 'index', 'btree', 'lsm', 'quorum', 'gossip', 'vector', 'lease', 'fence', 'saga', 'retry']; 251 let w = 8, grid, truth, total; 252 const hash = (s, seed) => { let h = seed >>> 0; for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193) >>> 0; } h ^= h >>> 15; h = Math.imul(h, 0x2c1b3c6d) >>> 0; return ((h ^ (h >>> 12)) >>> 0) % w; }; 253 const reset = () => { grid = Array.from({ length: D }, () => new Array(w).fill(0)); truth = new Map(); total = 0; }; 254 const add = (item, n = 1) => { for (let d = 0; d < D; d++) grid[d][hash(item, SEEDS[d])] += n; truth.set(item, (truth.get(item) || 0) + n); total += n; }; 255 const estimate = item => Math.min(...Array.from({ length: D }, (_, d) => grid[d][hash(item, SEEDS[d])])); 256 const draw = (highlight) => { 257 $('#cms-w-val').textContent = w; 258 const eps = Math.E / w; 259 $('#cms-bound').textContent = `error ⤠e/w à total = ${(eps * total).toFixed(0)} (with prob â ${(100 * (1 - Math.exp(-D))).toFixed(0)}%)`; 260 const cols = highlight ? Array.from({ length: D }, (_, d) => hash(highlight, SEEDS[d])) : []; 261 $('#cms-grid').innerHTML = grid.map((row, d) => `<tr><th>h${d + 1}</th>${row.map((c, i) => `<td class="${cols[d] === i ? 'is-hit' : ''}">${c}</td>`).join('')}</tr>`).join(''); 262 const ranked = [...truth.keys()].map(k => ({ k, est: estimate(k), real: truth.get(k) })).sort((a, b) => b.est - a.est).slice(0, 5); 263 $('#cms-topk').innerHTML = ranked.length ? `<div class="simulator-card__label">Top 5 by estimate (estimate / true)</div>` + 264 ranked.map(r => `<div class="sim-topk__row"><span>${esc(r.k)}</span><span>${r.est} / ${r.real}${r.est > r.real ? ` <em>+${r.est - r.real}</em>` : ''}</span></div>`).join('') : ''; 265 }; 266 const query = () => { 267 const item = $('#cms-item').value.trim(); if (!item) return; 268 const est = estimate(item), real = truth.get(item) || 0; 269 $('#cms-verdict').innerHTML = `<b>${esc(item)}</b>: estimate ${est}, true ${real}${est > real ? ` â over by ${est - real} from collisions` : ' â exact'}. Highlighted cells are its three counters; the answer is their minimum.`; 270 draw(item); 271 }; 272 lc.on($('#cms-w'), 'input', e => { w = +e.target.value; reset(); draw(); $('#cms-verdict').textContent = 'Width changed: sketch cleared.'; }); 273 lc.on($('#cms-add'), 'click', () => { const item = $('#cms-item').value.trim(); if (!item) return; add(item); query(); }); 274 lc.on($('#cms-query'), 'click', query); 275 lc.on($('#cms-stream'), 'click', () => { 276 // Zipf(s=1): item k is picked with probability â 1/k 277 const weights = WORDS.map((_, k) => 1 / (k + 1)), sum = weights.reduce((a, b) => a + b, 0); 278 for (let i = 0; i < 500; i++) { let r = Math.random() * sum, k = 0; while ((r -= weights[k]) > 0) k++; add(WORDS[k]); } 279 $('#cms-verdict').textContent = `Streamed 500 items (total ${total}). Heavy hitters stay accurate; rare items absorb the collision error.`; 280 draw(); 281 }); 282 lc.on($('#cms-reset'), 'click', () => { reset(); draw(); $('#cms-verdict').textContent = 'Cleared.'; }); 283 reset(); draw(); 284 },
285 unmount() { this._lc?.dispose(); } 286 }; 287 288 // ââ Gossip dissemination ââââââââââââââââââââââââââââââââââââ 289 window.SIMULATORS['gossip-spread'] = { 290 id: 'gossip-spread', 291 title: 'Gossip Dissemination', 292 slugs: ['gossip-protocol'], 293 blurb: 'Spread a rumor with push gossip and watch it reach every node in about log N rounds.', 294 render() { 295 return ` 296 <div class="simulator-card" id="sim-gossip"> 297 <div class="simulator-card__header"> 298 <div class="simulator-card__title">Gossip Dissemination (push)</div> 299 <span class="simulator-card__status" id="g-status"></span> 300 </div> 301 <p class="simulator-card__description">Every round, each informed node tells <i>fanout</i> random peers. Coverage grows roughly exponentially, so even large clusters converge in a handful of rounds, and dropped messages only slow it down slightly.</p> 302 <div class="simulator-card__grid"> 303 <label><span class="simulator-card__label">Nodes: <b id="g-n-val">64</b></span><input type="range" id="g-n" min="16" max="256" step="16" value="64"></label> 304 <label><span class="simulator-card__label">Fanout: <b id="g-f-val">2</b></span><input type="range" id="g-f" min="1" max="4" value="2"></label> 305 <label><span class="simulator-card__label">Message loss: <b id="g-l-val">0</b>%</span><input type="range" id="g-l" min="0" max="50" step="10" value="0"></label> 306 </div> 307 <div class="simulator-card__controls"> 308 <button class="btn btn--primary btn--sm" id="g-run">Run</button> 309 <button class="btn btn--outline btn--sm" id="g-step">Step one round</button> 310 <button class="btn btn--sm" id="g-reset">Reset</button> 311 </div> 312 <div class="sim-dots" id="g-dots"></div> 313 <div class="sim-bars" id="g-bars"></div> 314 </div>`; 315 }, 316 mount(root) { 317 const lc = this._lc = lifecycle(); 318 const $ = s => root.querySelector(s); 319 let N = 64, F = 2, loss = 0, informed, round, history, timer = null; 320 const reset = () => { if (timer) { lc.stop(timer); timer = null; } informed = new Uint8Array(N); informed[0] = 1; round = 0; history = [1]; $('#g-run').textContent = 'Run'; }; 321 const count = () => informed.reduce((a, b) => a + b, 0); 322 const step = () => { 323 if (count() === N) return false; 324 const next = informed.slice(); 325 for (let i = 0; i < N; i++) { 326 if (!informed[i]) continue; 327 for (let f = 0; f < F; f++) { 328 let peer = Math.floor(Math.random() * (N - 1)); if (peer >= i) peer++; 329 if (Math.random() * 100 >= loss) next[peer] = 1; 330 } 331 } 332 informed = next; round++; history.push(count()); 333 return true; 334 }; 335 const draw = () => { 336 $('#g-n-val').textContent = N; $('#g-f-val').textContent = F; $('#g-l-val').textContent = loss; 337 const c = count(); 338 $('#g-status').textContent = `round ${round} · ${c}/${N} informed · logâN â ${Math.log2(N).toFixed(1)}`; 339 $('#g-dots').innerHTML = Array.from(informed, (v, i) => `<span class="sim-dot ${v ? 'is-on' : ''}${i === 0 ? ' is-seed' : ''}"></span>`).join(''); 340 $('#g-bars').innerHTML = history.map((h, r) => `<div class="sim-bar" title="round ${r}: ${h} nodes"><div style="height:${(100 * h / N).toFixed(1)}%"></div><span>${r}</span></div>`).join(''); 341 }; 342 const toggleRun = () => { 343 if (timer) { lc.stop(timer); timer = null; $('#g-run').textContent = 'Run'; return; } 344 $('#g-run').textContent = 'Pause'; 345 timer = lc.every(550, () => { if (!step()) { lc.stop(timer); timer = null; $('#g-run').textContent = 'Run'; } draw(); }); 346 }; 347 const param = (sel, set) => lc.on($(sel), 'input', e => { set(+e.target.value); reset(); draw(); }); 348 param('#g-n', v => { N = v; }); 349 param('#g-f', v => { F = v; }); 350 param('#g-l', v => { loss = v; }); 351 lc.on($('#g-run'), 'click', toggleRun); 352 lc.on($('#g-step'), 'click', () => { step(); draw(); }); 353 lc.on($('#g-reset'), 'click', () => { reset(); draw(); }); 354 reset(); draw(); 355 },
356 unmount() { this._lc?.dispose(); } 357 }; 358})();
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.