31:T941,{ const handlers = { onStart: n => { viewof playhead.cut(); viewof execution.cut(); viewof execution.cluster.nodes[n.id].start(); }, onStop: n => { viewof playhead.cut(); viewof execution.cut(); viewof execution.cluster.nodes[n.id].stop(); }, onAddLog: n => { viewof playhead.cut(); viewof execution.cut(); viewof execution.cluster.nodes[n.id].addLog(); }, onTimeout: n => { viewof playhead.cut(); viewof execution.cut(); if (n.state == State.LEADER) { viewof execution.cluster.nodes[n.id].heartbeat(); } else { viewof execution.cluster.nodes[n.id].becomeCandidate(); } }, onNetwork: ([a, b]) => { viewof playhead.cut(); viewof execution.cut(); viewof execution.cluster.toggleConnection(a, b); viewof execution.run(); }, onFocus: () => viewof playback.pause() }; const onToggle = () => viewof playback.toggle(); const onSpeed = v => viewof playhead.speed = v; return render(() => { const [selected, setSelected] = useState(); return jsx`

<${Legends} />

time: ${cursor.toFixed(2)}ms

<${Network} nodes=${snapshot.nodes} network=${snapshot.network} linkSelected=${selected} messages=${snapshot.messages} time=${cursor} size=${300} />

<${Panel} nodes=${snapshot.nodes} networks=${snapshot.network} handlers=${handlers} onLinkSelect=${setSelected} />

<${SystemInfos} data=${snapshot} cursor=${cursor} />

`; }); }32:T762,{ const lineHeight = 16, lifelineHeight = lineHeight * 0.35; const paddingTop = (lineHeight - lifelineHeight) / 2; const events = mapEntries(execution.events, es => es.map(([t, e]) => { return [t, e.type.startsWith('handle') ? e.type.substring(6) : e.type]; })); const { margin } = layout; const height = lineHeight * Object.keys(execution.states).length + paddingTop; const onScale = (x, s) => { viewof layout.scaleAt(x, s); }; const onTranslate = x => { const range = viewof layout.range, domain = viewof domain.value.current; viewof cursor.value = math.fit(x, range[0], range[1], domain[0], domain[1]); viewof playback.pause(); }; const onUp = x => { const range = viewof layout.range, domain = viewof domain.value.current; viewof playhead.current = math.fit(x, range[0], range[1], domain[0], domain[1]); }; const onOut = x => { viewof cursor.value = viewof playhead.value.current; }; return render(() => { const drag = useRef(); const onDragStart = useCallback(() => drag.current = [viewof layout.offset, viewof layout.scale], []); const onDrag = useCallback(e => viewof layout.offset = -e.dx / drag.current[1] + drag.current[0], []); return jsx`<${SVG} width=${layout.width + margin.left + margin.right} height=${height + margin.bottom}> <${TimingDiagram} data=${{ ...execution, events }} layout=${layout} domain=${domain.current} cursor=${cursor} playhead=${playhead} /> <${LayoutControl} height=${height+margin.bottom} width=${layout.width} onScale=${onScale} onTranslate=${onTranslate} onUp=${onUp} onOut=${onOut} onDragStart=${onDragStart} onDrag=${onDrag} /> `; }); }33:T450,class View { static subs(unsubs) { return () => unsubs.forEach(unsub => unsub()); } constructor() { Object.defineProperties(this, { _list: { value: {}, writable: true }, _subs: { value: [], writable: true }, }); this.addEventListener('input', e => this._subs.forEach(sub => sub(e.value))); } get value() { return this; } observe(sub) { this._subs.push(sub); sub(this.value); // give out the current value on subscription return () => this._subs = this._subs.filter(l => l !== sub); } notify() { this.dispatchEvent({ type: "input", value: this.value }); } addEventListener(type, listener) { if (!this._list[type]) this._list[type] = []; if (this._list[type].includes(listener)) return; this._list[type] = [listener].concat(this._list[type]); } removeEventListener(type, listener) { this._list[type] = this._list[type].filter(l => l !== listener); } dispatchEvent(event) { if (!this._list[event.type]) return; const p = Promise.resolve(event); this._list[event.type].forEach(l => p.then(l)); } }34:T646,viewof playhead = { const playhead = new class Playhead extends View { constructor() { super(); this.update = this.update.bind(this); Object.defineProperties(this, { _current: { value: 0, writable: true }, _max: { value: 0, writable: true }, _speed: { value: 0.01, writable: true }, _paused: { value: true, writable: true } }) this.speedRange = [0, 0.1]; } update(delta) { this.current += delta * this.speed; } cut() { this._max = this._current; this.notify(); } reset(val) { this._max = this._current = val; this.notify(); } set current(val) { if (this._paused) { this._current = Math.min(val, this.max); } else { this._max = this._current = val; } this.notify(); } get current() { return this._current; } set paused(val) { this._paused = val; this.notify(); } get paused() { return this._paused; } set speed(val) { this._speed = val; this.notify(); } get speed() { return this._speed; } set max(val) { this._max = val; this.notify(); } get max() { return this._max; } get value() { const { current, speed, paused, max } = this; return { current, speed, paused, max }; } } invalidation.then(View.subs([ viewof playback.observe(p => playhead.paused = p), viewof clock.observe(playhead.update), ])); return playhead; }35:T413,viewof domain = { const domain = new class Domain extends View { constructor() { super(); Object.defineProperties(this, { _minSize: { value: 100, writable: true }, _value: { value: [0, 100], writable: true }, _playhead: { value: undefined, writable: true }, }); } set playhead(val) { this._playhead = val; this.rectify(); } reset(end) { this._value = [0, Math.max(end, this._minSize)]; this.notify(); } rectify() { const { _value: [lo, hi], _playhead: { current, paused }, _minSize } = this; const factor = paused ? 0 : current > hi ? 1 : 0.05; const hi1 = hi + (current - hi) * factor; this._value = [lo, Math.max(lo + _minSize, hi1)]; this.notify(); } get value() { const { _value, _minSize } = this; return { current: _value, ratio: (_value[1] - _value[0]) / _minSize }; } } invalidation.then(viewof playhead.observe(p => domain.playhead = p)); return domain; }36:Tb99,viewof layout = { const layout = new class Layout extends View { constructor(width) { super(); this.margin = { left: 18, right: 0, top: 0, bottom: 21 }; const contentWidth = width - this.margin.left - this.margin.right; Object.defineProperties(this, { _width: { value: width, writable: true }, _playhead: { value: undefined, writable: true }, _offset: { value: 0, writable: true }, _scale: { value: 1, writable: true }, _maxScale: { value: 4, writable: true }, _domain: { value: undefined, writable: true }, _range: { value: [0, contentWidth], writable: true }, _extent: { value: [0, contentWidth], writable: true }, _constraint: { value: [0, contentWidth], writable: true }, }); } reset() { this._offset = 0; this._scale = 1; this.notify(); } set offset(val) { this._offset = val; this.notify(); } get offset() { return this._offset; } set scale(val) { this._scale = val; this.notify(); } get scale() { return this._scale; } set playhead(val) { this._playhead = val; this.notify(); } get playhead() { return this._playhead; } set domain(val) { this._domain = val; this.notify(); } get domain() { return this._domain; } get range() { return this._range; } get maxScale() { return this._maxScale; } project(x) { return (x - this._offset) * this._scale; } invert(x) { return x / this._scale + this._offset; } scaleAt(x, scale) { const scale1 = math.clamp(scale * this.scale, 1, this._maxScale); this._offset += x * (scale1 / this.scale - 1) / scale1; this._scale = scale1; this.notify(); } constrain() { const dx0 = this.invert(this._extent[0]) - this._constraint[0], dx1 = this.invert(this._extent[1]) - this._constraint[1]; const dx = dx1 >= dx0 ? (dx0 + dx1) / 2 : Math.min(0, dx0) || Math.max(0, dx1); this._offset -= dx; } _update() { const { margin, playhead } = this; if (!playhead.paused) { this._scale += (1 - this._scale) * 0.02; } this._maxScale = 4 * this._domain.ratio; const width = this._width - margin.left - margin.right; this._range = [0, width].map(v => this.project(v)); this.constrain(); } get value() { this._update(); const { margin, range, offset, scale, maxScale } = this; const width = this._width - margin.left - margin.right; return { width, scale, margin, maxScale, range, offset }; } }(width); invalidation.then(View.subs([ viewof playhead.observe(p => layout._playhead = p), viewof domain.observe(d => layout.domain = d), ])); return layout; }37:T14bd,viewof execution = { const execution = new class Execution extends View { constructor(n = 5) { super(); this.prefetch = 200; Object.defineProperties(this, { _offset: { value: 0.3, writable: true }, _timed: { value: {}, writable: true }, _times: { value: {}, writable: true }, _maxTime: { value: 0, writable: true }, _states: { value: {}, writable: true }, _events: { value: {}, writable: true }, _messages: { value: [], writable: true }, _networks: { value: [], writable: true }, _msgs: { value: {}, writable: true }, _playhead: { value: undefined, writable: true }, }); this._onEvent = this._onEvent.bind(this); this._onMessage = this._onMessage.bind(this); this._onNetwork = this._onNetwork.bind(this); this.numNodes = n; } set numNodes(n) { const nodes = Object.fromEntries(d3.range(n).map(i => [`n${i+1}`,{}])); this.setup({ defaultDistance: 10, nodes }); } _cleanup() { if (this.cluster) { this.cluster.removeEventListener('event', this._onEvent); this.cluster.removeEventListener('message', this._onMessage); this.cluster.removeEventListener('network', this._onNetwork); } } setup(opts) { this._cleanup(); this._timed = mapEntries(opts.nodes, () => []); this._times = mapEntries(opts.nodes, () => ({})); this._states = mapEntries(opts.nodes, () => [[0, State.FOLLOWER]]); this._events = mapEntries(opts.nodes, () => []); this._msgs = mapEntries(opts.nodes, () => []); this._messages = []; this._networks = []; this._maxTime = 0; this.cluster = new Cluster(opts); this.cluster.addEventListener('event', this._onEvent); this.cluster.addEventListener('message', this._onMessage); this.cluster.addEventListener('network', this._onNetwork); this.cluster.start(); } _onEvent({ detail: e }) { const { _timed, _times, _states, _messages, _events } = this; let time = e.epoch; if (_timed[e.node].length > 0) { const last = arrays.last(_timed[e.node]); if (Math.floor(last[0]) == Math.floor(e.epoch)) time = last[0] + this._offset; } _timed[e.node].push([time, e]); _times[e.node][e.clock] = time; this._maxTime = Math.max(this._maxTime, time); const lastState = arrays.last(_states[e.node]); if (lastState[1] != e.state.state) _states[e.node].push([time, e.state.state]); if (e.type.startsWith('handle')) { const from = [e.meta.from, _times[e.meta.from][e.meta.clock]]; _messages.push([from, [e.node, time], e.meta.msg]); } if (e.type != 'init') _events[e.node].push([time, e]); this.notify(); } _onMessage({ detail: msg }) { this._msgs[msg[1][0]].push(msg); } _onNetwork({ detail }) { this._networks.push(detail); } set playhead(val) { if (this._playhead && val.paused != this._playhead.paused) { if (this._playhead.current != this._playhead.max) this.cut(); } this._playhead = val; if (!val.paused) this.run(); } run() { const n = Math.ceil(this._playhead.current) + this.prefetch - this.cluster.epoch; this.cluster.tick(n); } cut() { const cur = this._playhead.current; // cut history this._maxTime = cur; this._timed = mapEntries(this._timed, evts => evts.filter(([t,_]) => t <= cur)); this._events = mapEntries(this._events, evts => evts.filter(([t, _]) => t <= cur)); this._messages = this._messages.filter(m => m[1][1] <= cur); this._states = mapEntries(this._states, vs => vs.filter(([t, _]) => t <= cur)); this._msgs = mapEntries(this._msgs, msgs => msgs.filter(m => m[0][1] <= cur)); this._networks = this._networks.filter(n => n[0] <= cur); // rewind cluster state const c = this.cluster; c.epoch = Math.floor(cur); c.queues = mapEntries( this._msgs, msgs => msgs.filter(m => cur <= m[1][1]).map(m => [m[1][1], m[2]])); for (const [id, evts] of Object.entries(this._timed)) { const node = c.nodes[id]; node.apply(arrays.last(evts)[1]); const elapsed = Math.floor(cur - node.epoch); if (node.state == State.LEADER) { node.heartbeatElapsed += elapsed; } else { node.electionElapsed += elapsed; } node.epoch = c.epoch; } c.conns = arrays.last(this._networks)[1]; this.notify(); } get value() { const states = mapEntries(this._states, ds => { const last = [this._maxTime, arrays.last(ds)[1]]; return d3.pairs(ds.concat([last]), (a, b) => [[a[0],b[0]],a[1]]); }); return { cluster: this.cluster, events: this._events, messages: this._messages, timed: this._timed, networks: this._networks, states, maxTime: this._maxTime }; } } invalidation.then(viewof playhead.observe(p => execution.playhead = p)); return execution; }38:T796,scenarios = ({ restart: n => { viewof playback.pause(); viewof execution.numNodes = n; viewof layout.reset(); viewof playhead.reset(0); viewof domain.reset(0); }, basic: () => { viewof playback.pause(); viewof execution.numNodes = 3; const c = viewof execution.cluster; c.tick(20); c.nodes['n1'].becomeCandidate(); c.tick(50); c.nodes['n1'].addLog(); c.tick(10); c.nodes['n1'].heartbeat(); c.tick(30); c.nodes['n1'].heartbeat(); c.tick(100); viewof layout.reset(); viewof playhead.reset(140); viewof domain.reset(140); }, leaderDownRestart: () => { viewof playback.pause(); viewof execution.numNodes = 5; const c = viewof execution.cluster; c.tick(20); c.nodes['n1'].becomeCandidate(); c.tick(50); c.nodes['n1'].stop(); c.tick(10); c.nodes['n3'].becomeCandidate(); c.tick(50); c.nodes['n1'].start(); c.tick(100); viewof layout.reset(); viewof playhead.reset(180); viewof domain.reset(180); }, networkSplit: () => { viewof playback.pause(); viewof execution.numNodes = 5; const c = viewof execution.cluster; c.tick(20); c.nodes['n1'].becomeCandidate(); c.tick(50); c.toggleConnection('n1', 'n3'); c.toggleConnection('n1', 'n4'); c.toggleConnection('n1', 'n5'); c.toggleConnection('n2', 'n3'); c.toggleConnection('n2', 'n4'); c.toggleConnection('n2', 'n5'); c.tick(10); c.nodes['n5'].becomeCandidate(); c.tick(50); c.nodes['n1'].addLog(); c.nodes['n5'].addLog(); c.tick(50); c.toggleConnection('n1', 'n3'); c.toggleConnection('n1', 'n4'); c.toggleConnection('n1', 'n5'); c.toggleConnection('n2', 'n3'); c.toggleConnection('n2', 'n4'); c.toggleConnection('n2', 'n5'); c.tick(100); viewof layout.reset(); viewof playhead.reset(240); viewof domain.reset(240); } })39:T1201,TimingDiagram = { const lineHeight = 14, lifelineHeight = lineHeight * 0.3; const paddingTop = (lineHeight - lifelineHeight) / 2; const Context = createContext(); const Labels = component(({ data }) => { const { scales, n2i } = useContext(Context); return data.map((key, i) => { const props = { key: i, y: scales.y(i), fontFamily: "Open Sans", fontSize: 10, textAnchor: "left", alignmentBaseline: "central", }; return jsx`${key}`; }); }); const Messages = component(({ data }) => { const { scales, n2i, playhead } = useContext(Context); const path1 = d3.path(), path2 = d3.path(); data.forEach(([from, to]) => { const x1 = scales.x(from[1]), x2 = scales.x(to[1]); const y1 = scales.y(n2i[from[0]]), y2 = scales.y(n2i[to[0]]); if (to[1] < playhead.current) { path1.moveTo(x1, y1); path1.lineTo(x2, y2); } else { path2.moveTo(x1, y1); path2.lineTo(x2, y2); } }); return jsx` `; }); const compMap = { becomeCandidate: icons.Become, becomeLeader: icons.Become, RequestVote: icons.Message, RequestVoteResp: icons.Message, AppendEntries: icons.Message, AppendEntriesResp: icons.Message, addLog: icons.AddLog, heartbeat: icons.Timeout, start: icons.Start, stop: icons.Stop, connect: icons.Network, disconnect: icons.Network }; const Marks = component(({ data }) => { const { scales, n2i, timeRange, playhead } = useContext(Context); return g(Object.entries(data).map(([node, evts]) => { const mks = evts.filter(([t, _]) => timeRange[0] - 1 < t || t < timeRange[1] + 1) .map(([t, type], i) => { // if (t < timeRange[0] - 1 || timeRange[1] + 1 < t) return null; const props = { key: i, size: 10, state: t < playhead.current ? 'enabled' : 'disabled', transform: `translate(${scales.x(t)},${scales.y(n2i[node])})` }; return jsx`<${compMap[type]} ...${props} />`; }); return jsx`${mks}`; })); }); const Lifelines = component(({ data, sep }) => { const { scales, n2i } = useContext(Context); const minMaxs = data.map(d => [d[0][0][0], d[d.length-1][0][1]]); const lower = d3.min(minMaxs, a => a[0]), upper = d3.max(minMaxs, a => a[1]); const x = scales.x(lower), width = scales.x(upper) - x; return g(data.map((ints, i) => { const props = { key: i, data: ints, width, height: lifelineHeight, sep: sep - x, transform: `translate(${x},${scales.y(i) - lifelineHeight / 2})` }; return jsx`<${Lifeline} ...${props} />`; })); }); return component(({ data, layout, cursor, playhead, domain }) => { const { width, margin, range } = layout; const peers = Object.keys(data.states); const n2i = Object.fromEntries(peers.map((n,i) => [n,i])); const n = peers.length; const height = lineHeight * n + paddingTop; const scales = { x: d3.scaleLinear(domain, range), y: d3.scaleLinear([0, n - 1], [0, n - 1].map(n => (n + 0.5) * lineHeight)) }; const timeRange = [0, width].map(v => scales.x.invert(v)); const context = { scales, n2i, timeRange, playhead, cursor, peers }; const axis = jsx`<${Axis} width=${width} domain=${timeRange} transform="translate(0,${height})"/>`; const cursorLine = jsx``; const ph = scales.x(playhead.current); const playheadLine = jsx``; const clipWidth = math.clamp(scales.x(playhead.max), 0, width); return jsx`<${Context.Provider} value=${context}> <${Labels} data=${peers} /> <${ClipArea} id="tg" width=${width} height=${height}> <${ClipArea} id="tl" width=${clipWidth} height=${height}> <${Lifelines} data=${Object.values(data.states)} sep=${ph} /> <${Messages} data=${data.messages} /> <${Marks} data=${data.events} /> ${cursorLine} ${playheadLine} ${axis} `; }); }3a:T459,LayoutControl = { return component(({ onScale, onTranslate, onUp, onOut, onDragStart, onDrag, width, height }) => { const ref = useRef(); useNonPassive(ref, 'wheel', useCallback(e => { e.preventDefault(); const x = e.clientX - e.target.getBoundingClientRect().left; const s = 2 ** (-e.deltaY * 0.01); onScale(x, s); }, [onScale])); const onMove = useCallback(e => { const x = e.clientX - e.target.getBoundingClientRect().left; onTranslate(x); }, [onTranslate]); const dragging = useRef(false); const onMouseUp = useCallback(e => { const x = e.clientX - e.target.getBoundingClientRect().left; if (dragging.current) { dragging.current = false; } else { onUp(x); } }, []); useDrag(ref, useConst(() => ({ onStart: e => { onDragStart(e); dragging.current = true; }, onDrag, }))); return jsx``; }); }3b:T1757,Network = { const nodeR = 18, lh = 14, logSize = 11, logGap = 4; const textProps = { fontFamily: "Open Sans", textAnchor: "middle", alignmentBaseline: "central", style: { userSelect: 'none' }, fontSize: 12, fill: 'white', stroke: 'white', strokeWidth: 0.5 }; const arc = d3.arc().innerRadius(nodeR-3).outerRadius(nodeR-2).startAngle(0); const getPos = (nodes, radius) => Object.fromEntries(nodes.map((n, i, a) => { const theta = i / a.length * math.TAU - math.HALF_PI; return [n.id, [Math.cos(theta) * radius, Math.sin(theta) * radius]]; })); const infoKeys = ['term','votedFor']; const Timer = component(({ node, time }) => { const elapsed = node.state == State.STOPPED ? 0 : node.state == State.LEADER ? (time - node.epoch + node.heartbeatElapsed) / node.opts.heartbeatTimeout : (time - node.epoch + node.electionElapsed) / node.electionTimeout; const props = { d: arc.endAngle(math.TAU * elapsed)(), fill: 'white', stroke: 'white' }; return jsx``; }); const NodeInfos = component(({ node, keys }) => keys.map((k, i) => { const props = { key: i, y: lh * i, fontFamily: 'monospace', fontSize: 10, fill: 'hsl(0,0%,20%)' }; return jsx`${k}: ${node[k]}`; })); const Context = createContext(); const NodeStates = component(({ data, time, selected }) => { const { pos } = useContext(Context); return g(data.map(n => { const highlight = selected && selected.some(v => v == n.id); const props = { stroke: 'black', strokeWidth: highlight ? 1 : 0.1, }; return jsx` <${Timer} node=${n} time=${time} /> ${n.id} `; })); }); const NodeDetails = component(({ data }) => { const { pos } = useContext(Context); return g(data.map(n => jsx` <${NodeInfos} node=${n} keys=${infoKeys} /> `)); }); const Connections = component(({ data, selected }) => { const { pos } = useContext(Context); return g(combinations(Object.keys(data)).map(([a, b]) => { const highlight = selected && selected.some(u => u == a) && selected.some(u => u == b); const connected = data[a][b] > 0; const [x1, y1] = pos[a], [x2, y2] = pos[b]; const props = { key: `${a}:${b}`, x1, x2, y1, y2, stroke: highlight ? 'black' : connected ? 'hsl(0,0%,85%)' : 'none', strokeDasharray: !highlight ? '7,4' : 'none' }; return jsx``; })); }); const charMap = { RequestVote: 'R', RequestVoteResp: 'Rr', AppendEntries: 'A', AppendEntriesResp: 'Ar', }; const Message0 = component(({ data, onSelect = noop }) => { const [from, to, msg] = data; const { pos, time } = useContext(Context); const [x1, y1] = pos[from[0]], [x2, y2] = pos[to[0]]; const t = math.clamp01(math.norm(time, from[1], to[1])); const x = math.mix(x1, x2, t), y = math.mix(y1, y2, t); const [active, setActive] = useState(false); const props = { char: charMap[msg.constructor.name], size: 13, transform: `translate(${x},${y})`, state: active ? 'active' : 'enabled', handlers: { onMouseOver: useCallback(e => (setActive(true), onSelect([from, to, msg])), []), onMouseOut: useCallback(e => (setActive(false), onSelect(undefined)), []) } }; return jsx`<${Message} ...${props} />`; }); const msgFields = { RequestVote: ['term','candidateId','lastLogIndex','lastLogTerm'], RequestVoteResp: ['term', 'voteGranted'], AppendEntries: ['term', 'leaderId', 'prevLogIndex', 'prevLogTerm', 'leaderCommit', ['logs', v => v.map(l => `[${l}]`).join(',')]], AppendEntriesResp: ['term', 'success', 'nextIndex'] }; const MessageHighlight = component(({ data }) => { if (!data) return null; const [from, to, msg] = data; const { pos, time } = useContext(Context); const [x1, y1] = pos[from[0]], [x2, y2] = pos[to[0]]; const t = math.clamp01(math.norm(time, from[1], to[1])); const x = math.mix(x1, x2, t), y = math.mix(y1, y2, t); const textProps = { fontFamily: "monospace", alignmentBaseline: "top", style: { userSelect: 'none' }, fontSize: 10, fill: 'black', }; const fields = msgFields[msg.constructor.name].map((f, i) => { const val = Array.isArray(f) ? f[1](msg[f[0]]) : msg[f]; const field = Array.isArray(f) ? f[0] : f; return jsx`<${BGText} key=${i} text="${field}: ${val}" transform=translate(0,${14*i-2}) />`; }) return jsx` ${fields} `; }); return component(({ nodes, network, linkSelected, messages, time, size }) => { const radius = size / 2 - nodeR; const context = { pos: getPos(nodes, radius), time }; const [msgSelected, setMsgSelected] = useState(); const width = size + nodeR + 80; return jsx`<${SVG} width=${width} height=${size}> <${Context.Provider} value=${context}> <${Connections} data=${network} selected=${linkSelected} /> <${NodeDetails} data=${nodes} /> ${messages.map((m,i) => jsx` <${Message0} key="${m[0][0]},${m[0][1]},${m[1][0]},${m[1][1]}" data=${m} onSelect=${setMsgSelected} />`)} <${NodeStates} data=${nodes} time=${time} selected=${linkSelected} /> <${MessageHighlight} data=${msgSelected} /> `; }); }3c:T235a,Panel = { const jointSize = 5, rowHeight = 26, w = rowHeight * 0.6; const getJointPos = (nodes, w, h) => { const pos = {}; for (let i = 0; i < nodes.length;i++) { if (!pos[nodes[i].id]) pos[nodes[i].id] = {}; for (let j = i; j < nodes.length; j++) pos[nodes[i].id][nodes[j].id] = [-(j-i) * w, i * h + (j-i-1) * h / 2]; } return pos; }; const defaultHandlers = { onStart: noop, onStop: noop, onTimeout: noop, onAddLog: noop, onNetwork: noop, onLinkSelect: noop, onFocus: noop }; const Context = createContext(); const Joint = component(({ a, b }) => { const { pos, networks, selected, setSelected, handlers, changeNetwork } = useContext(Context); const fill = networks[a.id][b.id] > 0 ? 'hsl(0,0%,85%)' : 'white'; const highlight = selected && selected[0] == a.id && selected[1] == b.id; const sw = highlight ? 2 : 1; return jsx` setSelected([a.id,b.id]), [])} onMouseOut=${useCallback(() => setSelected(undefined), [])} onClick=${useCallback(() => handlers.onNetwork([a.id, b.id]) )} /> `; }); const Joints = component(() => { const { nodes } = useContext(Context); return g(arrays.mapcat(nodes, (a,i) => nodes.filter((_,j) => j > i).map(b => { return jsx`<${Joint} key="${a.id},${b.id}" a=${a} b=${b} />`; }))); }); const Links = component(() => { const { pos, nodes, selected } = useContext(Context); const links1 = nodes.map((n, i, a) => { if (i == a.length - 1) return null; const [x1, y1] = pos[n.id][n.id], [x2, y2] = pos[n.id][nodes[nodes.length-1].id]; return jsx``; }); const links2 = nodes.map((n, i) => { if (i == 0) return null; const [x1, y1] = pos[n.id][n.id], [x2, y2] = pos[nodes[0].id][n.id]; return jsx``; }); let linksHighlight; if (selected) { const [u, v] = selected; const a = pos[u][u], b = pos[u][v], c = pos[v][v]; linksHighlight = jsx``; } const linkEnds = nodes.map(({ id },i) => { const highlight = selected && (selected.some(v => v == id)); const [x, y] = pos[id][id]; const props = { key: i, x1: x, x2: x + rowHeight * (highlight ? 6 : 2) / 8, y1: y, y2: y, stroke: highlight ? 'hsl(0,0%,0%)' : 'hsl(0,0%,70%)', strokeWidth: 1.1 }; return jsx``; }); return jsx`<${Fragment}> ${links1} ${links2} ${linksHighlight} ${linkEnds} `; }); const textProps = { fontFamily: "Open Sans", textAnchor: "middle", alignmentBaseline: "central", style: { userSelect: 'none' }, fontSize: 8, fill: 'hsl(0,0%,100%)', stroke: 'white', strokeWidth: 0.6 }; const Lables = component(() => { const { pos, nodes, selected } = useContext(Context); return g(nodes.map((n,i) => { const highlight = selected && (selected[0] == n.id || selected[1] == n.id); const props = { stroke: 'black', strokeWidth: highlight ? 1 : 0.1 }; return jsx` ${n.id} `; })); }); const size = 12, gap = 24; const btnProps = { x: -size / 2, y: -size / 2, width: size, height: size, fill: 'transparent' }; const OpStartStop = component(({ node, setDesc, ...props }) => { const { handlers } = useContext(Context); const onStart = useCallback(() => { node.state == State.STOPPED && handlers.onStart(node); }, [node.state]); const onStop = useCallback(() => { node.state != State.STOPPED && handlers.onStop(node); }, [node.state]); const [active, setActive] = useState(false); const onMouseOver = useCallback(() => { setActive(true); handlers.onFocus(); setDesc(node.state == State.STOPPED ? 'start' : 'stop'); }, []); const onMouseOut = useCallback(() => (setActive(false), setDesc('')), []); const state = active ? 'active' : 'enabled'; const btn = node.state == State.STOPPED ? jsx`<${icons.Start} size=${size} state=${state} />` : jsx`<${icons.Stop} size=${size} state=${state} />`; const onClick = node.state == State.STOPPED ? onStart : onStop; return jsx` ${btn} `; }); const OpTimeout = component(({ node, setDesc, ...props }) => { const { handlers } = useContext(Context); const [active, setActive] = useState(false); const onMouseOver = useCallback(() => { if (node.state != State.STOPPED) { setActive(true); handlers.onFocus(); setDesc(node.state != State.LEADER ? 'start election' : 'send heartbeat'); } }, [node.state]); const onMouseOut = useCallback(() => (setActive(false), setDesc('')), []); const state = active ? 'active' : node.state != State.STOPPED ? 'enabled' : 'disabled'; const onClick = useCallback(() => { node.state != State.STOPPED && handlers.onTimeout(node); }, [node.state]); const cursor = node.state != State.STOPPED ? 'pointer' : 'auto'; return jsx` <${icons.Timeout} size=${size} state=${state} /> `; }); const OpAddLog = component(({ node, setDesc, ...props }) => { const { handlers } = useContext(Context); const [active, setActive] = useState(false); const onMouseOver = useCallback(() => { if (node.state == State.LEADER) { setActive(true); handlers.onFocus(); setDesc('add log entry'); }; }, [node.state]); const onMouseOut = useCallback(() => (setActive(false), setDesc('')), []); const state = active ? 'active' : node.state == State.LEADER ? 'enabled' : 'disabled'; const onClick = useCallback(() => { node.state == State.LEADER && handlers.onAddLog(node); }, [node.state]); const cursor = node.state == State.LEADER ? 'pointer' : 'auto'; return jsx` <${icons.AddLog} size=${size} state=${state} /> `; }); const NodeOps = component(({ node, ...props }) => { const [desc, setDesc] = useState(''); const textProps = { fontFamily: "Open Sans", alignmentBaseline: "central", style: { userSelect: 'none' }, fontSize: 12, fill: 'hsl(0,0%,30%)', }; return jsx` <${OpStartStop} node=${node} setDesc=${setDesc} transform="translate(${gap*0},0)" /> <${OpTimeout} node=${node} setDesc=${setDesc} transform="translate(${gap*1},0)" /> <${OpAddLog} node=${node} setDesc=${setDesc} transform="translate(${gap*2},0)" /> ${desc} `; }); const Ops = component(() => { const { nodes } = useContext(Context); const ops = nodes.map( (n, i) => jsx`<${NodeOps} key=${i} node=${n} transform=translate(0,${i * rowHeight}) />`) return jsx`${ops}`; }); return component(({ nodes, networks, handlers: handlers0, onLinkSelect }) => { const pos = getJointPos(nodes, w, rowHeight); const [selected, setSelected] = useState(); const handlers = { ...defaultHandlers, ...handlers0 }; const context = { pos, nodes, networks, selected, handlers, setSelected: useCallback(link => { setSelected(link); onLinkSelect(link); handlers.onFocus(); }, []) }; const w0 = (nodes.length - 1) * w + jointSize + 1 + rowHeight * 1.5 + 3 * gap + 100; return jsx`<${SVG} width=${w0} height=${nodes.length * rowHeight}> <${Context.Provider} value=${context}> <${Links} /> <${Joints} /> <${Lables} /> <${Ops} /> `; }); }3d:T5a8,SystemInfos = { const logSize = 12, logGap = 4;; const textProps = { fontFamily: "Open Sans", textAnchor: "middle", alignmentBaseline: "central", style: { userSelect: 'none' }, fontSize: 9, fill: 'black', stroke: 'none' }; const Logs = component(({ node, y }) => node.logs.filter(l => l[0] > 0).map(log => { const x = (log[0] - 1) * logSize + logGap * 2 * (log[0] <= node.commitIndex ? 0 : 1); return jsx` ${log[1]} `; })); const CommitIndex = component(({ node }) => { const x = node.commitIndex * logSize + logGap; const props = { x1: x, x2: x, y2: logSize, stroke: 'hsl(0,0%,10%)', strokeWidth: 1 }; return jsx``; }); return component(({ data, cursor }) => { const height = data.nodes.length * 16 + 18; const logs = data.nodes.map((node, i) => { return jsx` <${Text}>${node.id} <${Logs} node=${node}/> <${CommitIndex} node=${node} /> `; }); return jsx`<${SVG} width=${100} height=${height}> <${Text}>logs ${logs} `; }); }3e:T48f,Legends = { const items = [ [icons.Message, 'message'], [icons.AddLog, 'add log'], [icons.Start, 'start node'], [icons.Stop, 'stop node'], [icons.Timeout, 'timeout'], [icons.Become, 'role change'], [icons.Network, 'network change'], ] return component(() => { const size = 8, lh = 13; const textProps = { fontSize: 9, fontFamily: 'Open Sans', y: 3, x: 10, fill: 'hsl(0,0%,30%)' }; const entries = items.map(([Comp, desc], i) => { return jsx` <${Comp} size=${size} /> ${desc} `; }); const states = ['follower','candidate','leader'].map((s,i) => { return jsx` ${s} `; }); return jsx`<${SVG} width=${90} height=${(items.length + 3) * lh}> ${states} ${entries} ` }); }3f:T469,Message = { const style = { icon: { enabled: { stroke: 'hsl(0,0%,40%)', fill: 'hsl(0,0%,30%)', strokeWidth: 0.9 }, disabled: { stroke: 'hsl(0,0%,75%)', fill: 'hsl(0,0%,75%)', strokeWidth: 0.7 }, active: { stroke: 'black', fill: 'black', strokeWidth: 0 }, }, rect: { enabled: { stroke: 'hsl(0,0%,40%)', strokeWidth: 0.8, fill: 'white' }, disabled: { stroke: 'hsl(0,0%,80%)', strokeWidth: 0.8, fill: 'white' }, active: { stroke: 'hsl(0,0%,30%)', strokeWidth: 1.5, fill: 'white' }, } }; const textProps = size => ({ fontFamily: "Open Sans", fontSize: size * 0.8, textAnchor: "middle", alignmentBaseline: "central", stroke: 'none', style: { userSelect: 'none' } }); return component(({ char, size, state = 'enabled', handlers, ...other }) => { return jsx` ${char} `; }); }40:T43b,html``41:Tc69,icons = { const style = { enabled: { stroke: 'hsl(0,0%,50%)', fill: 'white', strokeWidth: 0.9 }, disabled: { stroke: 'hsl(0,0%,80%)', fill: 'white', strokeWidth: 0.9 }, active: { stroke: 'black', fill: 'black', strokeWidth: 0.9 }, }; const Become = component(({ size, state = 'enabled', ...other }) => { const w = size * 0.7, h = size; return jsx``; }); const Message = component(({ size, state = 'enabled', ...other }) => { return jsx``; }); const AddLog = component(({ size, state = 'enabled', ...other }) => { const h = size / 2, g = (size * 0.35) / 2; const path = d3.path(); path.moveTo(-h, -g); path.lineTo(-g, -g); path.lineTo(-g, -h); // upper left path.lineTo(g, -h); path.lineTo(g, -g); path.lineTo(h, -g); // upper right path.lineTo(h, g); path.lineTo(g, g); path.lineTo(g, h); // bottom right path.lineTo(-g, h); path.lineTo(-g, g); path.lineTo(-h, g); // bottom left path.closePath(); return jsx``; }); const Stop = component(({ size, state = 'enabled', ...other }) => { const h = size * 0.5, g = (size * 0.3) / Math.SQRT2; const path = d3.path(); path.moveTo(-g, 0); path.lineTo(-h, -h + g); path.lineTo(-h + g, -h); path.lineTo(0, -g); path.lineTo(h - g, -h); path.lineTo(h, -h + g); path.lineTo(g, 0); path.lineTo(h, h - g); path.lineTo(h - g, h); path.lineTo(0, g); path.lineTo(-h + g, h); path.lineTo(-h, h - g); path.closePath(); return jsx``; }); const Start = component(({ size, state = 'enabled', ...other }) => { const h = size * 0.5; const path = d3.path(); path.moveTo(-h * 0.7, -h); path.lineTo(h * 0.9, 0); path.lineTo(-h * 0.7, h) path.closePath(); return jsx``; }); const Timeout = component(({ size, state = 'enabled', ...other }) => { const h = size * 0.3; const path = d3.path(); path.moveTo(0, -h); path.lineTo(0, 0); path.lineTo(h, 0); const pathStroke = state == 'active' ? 'white' : style[state].stroke; return jsx` `; }); const Network = component(({ size, state = 'enabled', ...props }) => { const h = size * 0.5, w = size * 0.3, h3 = h / 3, h2 = h / 2; const path = d3.path(); path.moveTo(h2 - w, -h); path.lineTo(-h2, -h3); path.lineTo(h2 - w, h3); path.lineTo(-h2, h); path.moveTo(h2, -h); path.lineTo(-h2 + w, -h3); path.lineTo(h2, h3); path.lineTo(-h2 + w, h); const points = [[h2-w,-h],[-h2,-h3],[h2-w,h3],[-h2,h],[-h2+w,h],[h2,h3],[-h2+w,-h3],[h2,-h]]; return jsx` `; }); return { Become, Message, AddLog, Stop, Start, Timeout, Network }; }42:T5bd,viewof patterns = { const size = 3.5; const ids = Object.values(State); const patterns = ids.map(id => jsx` `); const width = 60, height = 30, margin = 1; const props = { bg: id => ({ width: width - margin, height: height - margin, stroke: 'hsl(0,0%,30%)', strokeWidth: 0.2, fill: `url(#${id})` }), txt: { x: width / 2, y: height / 2, fontSize: 10, fontFamily: "Open Sans", textAnchor: "middle", alignmentBaseline: "central", }, shade: id => { const w = id.length * 5.8; return { x: width / 2 - w / 2, y: height / 2 - 5, width: w, height: 12, fill: 'white' }; } }; return render(({ useSetter }) => { useSetter(Object.fromEntries(ids.map(id => [id, `url(#${id})`]))); return jsx`<${SVG} width=${(width + 10) * ids.length} height=${height}> ${patterns} ${ids.map((id, i) => jsx` ${id} `)} `; }); }43:T1f99,class Node extends EventDispatcher { constructor(id, peers, opts = {}) { super(); this.opts = { electionTimeoutRange: [80,150], heartbeatTimeout: 50, ...opts }; this.id = id; this.peers = new Set(peers); const [etMin, etMax] = this.opts.electionTimeoutRange; this.randomElectionTimeout = d3.randomInt(etMin, etMax); this.reset(); } reset() { this.term = 0; this.votedFor = ''; this.state = State.FOLLOWER; this.heartbeatElapsed = 0; this.logs = [[0,0]]; // [index, term] this.commitIndex = 0; this.votesGranted = new Set(); this.matchIndex = {}; this.nextIndex = {}; this.epoch = 0; this.clock = 0; // Lamport clock this.restartElectionTimer(); } restartElectionTimer() { this.electionElapsed = 0; this.electionTimeout = this.randomElectionTimeout(); } notify(type, meta = {}) { const { term, epoch, peers, clock, votedFor, state, heartbeatElapsed, electionElapsed, electionTimeout, commitIndex, opts } = this; const detail = { node: this.id, epoch, clock, type, meta, state: { term, votedFor, state, heartbeatElapsed, electionElapsed, electionTimeout, opts, commitIndex, peers: new Set(peers), votesGranted: new Set(this.votesGranted), matchIndex: { ...this.matchIndex }, nextIndex: { ...this.nextIndex }, logs: [...this.logs], } }; this.dispatchEvent(new CustomEvent('event', { detail })); } apply({ state, epoch, clock }) { this.term = state.term; this.peers = new Set(state.peers); this.votedFor = state.votedFor; this.state = state.state; this.heartbeatElapsed = state.heartbeatElapsed; this.electionElapsed = state.electionElapsed; this.electionTimeout = state.electionTimeout; this.commitIndex = state.commitIndex; this.logs = [...state.logs]; this.votesGranted = new Set(state.votesGranted); this.matchIndex = { ...state.matchIndex }; this.nextIndex = { ...state.nextIndex }; this.epoch = epoch; this.clock = clock; } start() { if (this.state != State.STOPPED) return; this.becomeFollower(); this.clock++; this.notify('start'); } stop() { if (this.state == State.STOPPED) return; this.state = State.STOPPED; this.clock++; this.notify('stop'); } connect(peer) { this.notify('connect', { peer }); } disconnect(peer) { this.notify('disconnect', { peer }); } addLog() { if (this.state != State.LEADER) return; this.clock++; this.logs.push([this.logs.length, this.term]); this.matchIndex[this.id] = this.logs.length - 1; this.notify('addLog'); } becomeFollower() { this.state = State.FOLLOWER; this.restartElectionTimer(); } becomeCandidate() { this.state = State.CANDIDATE; this.restartElectionTimer(); this.term++; this.votedFor = this.id; this.votesGranted = new Set([this.id]); this.clock++; this.peers.forEach(p => p != this.id && this.requestVote(p)); this.notify('becomeCandidate'); this.checkVotes(); } becomeLeader() { this.state = State.LEADER; this.nextIndex = Object.fromEntries(Array.from(this.peers.values()).map(p => [p, this.logs.length])); this.matchIndex = Object.fromEntries(Array.from(this.peers.values()).map(p => [p, 0])); this.heartbeatElapsed = 0; this.clock++; this.peers.forEach(p => p != this.id && this.appendEntries(p)); this.notify('becomeLeader'); } checkVotes() { if (this.state == State.CANDIDATE && this.votesGranted.size > Math.floor(this.peers.size / 2)) this.becomeLeader(); } send(to, payload) { const detail = { from: this.id, to, payload, clock: this.clock }; this.dispatchEvent(new CustomEvent('message', { detail })); } requestVote(peer) { const [idx, term] = arrays.last(this.logs); this.send(peer, new RPC.RequestVote(this.term, this.id, idx, term)); } appendEntries(peer) { const [idx, term] = this.logs[this.nextIndex[peer]-1]; const logs = this.logs.slice(this.nextIndex[peer]); this.send(peer, new RPC.AppendEntries(this.term, this.id, idx, term, logs, this.commitIndex)); } heartbeat() { this.heartbeatElapsed = 0; this.clock++; this.peers.forEach(p => p != this.id && this.appendEntries(p)); this.notify('heartbeat'); } tick() { this.epoch++; if (this.state == State.STOPPED) return; if (this.state == State.LEADER) { ++this.heartbeatElapsed >= this.opts.heartbeatTimeout && this.heartbeat(); } else { ++this.electionElapsed >= this.electionTimeout && this.becomeCandidate(); } } recv(msg) { if (this.state == State.STOPPED) return; this.clock = Math.max(this.clock, msg.clock) + 1; if (msg.payload instanceof RPC.RequestVote) { this.handleRequestVote(msg); } else if (msg.payload instanceof RPC.RequestVoteResp) { this.handleRequestVoteResp(msg); } else if (msg.payload instanceof RPC.AppendEntries) { this.handleAppendEntries(msg); } else if (msg.payload instanceof RPC.AppendEntriesResp) { this.handleAppendEntriesResp(msg); } } updateTerm(term) { if (term <= this.term) return false; this.term = term; this.votedFor = ''; this.becomeFollower(); return true; } handleRequestVote({ from, payload: msg, clock }) { const { term, lastLogTerm, lastLogIndex, candidateId } = msg; this.updateTerm(term); const last = arrays.last(this.logs); const logOK = lastLogTerm > last[1] || (lastLogTerm == last[1] && lastLogIndex >= last[0]); const granted = this.term == term && logOK && (this.votedFor == candidateId || this.votedFor == ""); if (granted) this.votedFor = candidateId; this.send(from, new RPC.RequestVoteResp(this.term, granted)); this.notify('handleRequestVote', { from, msg, clock }); } handleRequestVoteResp({ from, payload: msg, clock }) { if (!this.updateTerm(msg.term) && msg.voteGranted) { this.votesGranted.add(from); this.notify('handleRequestVoteResp', { from, msg, clock }); this.checkVotes(); } else { this.notify('handleRequestVoteResp', { from, msg, clock }); } } handleAppendEntries({ from, payload: msg, clock }) { const { term, prevLogIndex, prevLogTerm, logs, leaderCommit } = msg; if (this.state == State.CANDIDATE) this.becomeFollower(); this.updateTerm(term); this.restartElectionTimer(); const logOK = prevLogIndex < this.logs.length && this.logs[prevLogIndex][1] == prevLogTerm; if (this.term == term && logOK) { // accept this.updateLogs(logs); if (leaderCommit > this.commitIndex) this.commitIndex = logs.length > 0 ? Math.min(leaderCommit, arrays.last(logs)[0]) : leaderCommit; this.send(from, new RPC.AppendEntriesResp(this.term, true, prevLogIndex + logs.length + 1)); } else { // reject this.send(from, new RPC.AppendEntriesResp(this.term, false, this.logs.length)); } this.notify('handleAppendEntries', { from, msg, clock }); } handleAppendEntriesResp({ from, payload: msg, clock }) { if (!this.updateTerm(msg.term)) { if (msg.success) { this.nextIndex[from] = msg.nextIndex; this.matchIndex[from] = msg.nextIndex - 1; this.advanceCommitIndex(); } else { this.nextIndex[from] = Math.min(msg.nextIndex, this.nextIndex[from]-1); } } this.notify('handleAppendEntriesResp', { from, msg, clock }); } updateLogs(logs) { for (const [idx, term] of logs) { if (idx < this.logs.length) { if (this.logs[idx][1] != term) { this.logs.length = idx; this.logs.push([idx, term]); } } else { this.logs.push([idx, term]); } } } advanceCommitIndex() { const vals = Object.values(this.matchIndex); vals.sort(); this.commitIndex = Math.max(this.commitIndex, vals[vals.length/2|0]); } }44:T9af,{ (function testElectionTimeout() { const r = new Node("r1", ["r1","r2"], { electionTimeoutRange: [1,1] }); const msgs = []; r.addEventListener('message', e => msgs.push(e.detail)); expect(r.state).toBe(State.FOLLOWER); expect(r.term).toBe(0); r.tick(); expect(r.clock).toBe(1); expect(r.state).toBe(State.CANDIDATE); expect(r.term).toBe(1); expect(msgs[0].from).toBe("r1"); expect(msgs[0].to).toBe("r2"); expect(msgs[0].payload).toBeInstanceOf(RPC.RequestVote); expect(msgs[0].payload.term).toBe(1); expect(msgs[0].payload.candidateId).toBe("r1"); })(); (function testVote() { const r = new Node("r1", ["r1","r2"]); r.recv({ from: "r2", to: "r1", payload: new RPC.RequestVote(1, "r2", 0, 0), clock: 1 }); expect(r.clock).toBe(2); expect(r.term).toBe(1); expect(r.votedFor).toBe("r2"); })(); (function testCandidateStepDown() { const r = new Node("r1", ["r1","r2"]); r.becomeCandidate(); r.recv({ from: "r2", to: "r1", payload: new RPC.RequestVote(1, "r2", 0, 0), clock: 1 }); expect(r.votedFor).toBe("r1"); // ignore outdated request r.recv({ from: "r2", to: "r1", payload: new RPC.RequestVote(2, "r2", 0, 0), clock: 1 }); expect(r.votedFor).toBe("r2"); expect(r.state).toBe(State.FOLLOWER); })(); (function testWinElection() { const r = new Node("r1", ["r1","r2"]); r.becomeCandidate(); r.recv({ from: "r2", to: "r1", payload: new RPC.RequestVoteResp(1, true), clock :1 }); expect(r.state).toBe(State.LEADER); })(); (function testSendHeartbeat() { const r = new Node("r1", ["r1","r2"], { heartbeatTimeout: 1 }); const msgs = []; r.addEventListener('message', e => msgs.push(e.detail)); r.becomeLeader(); expect(r.heartbeatElapsed).toBe(0); expect(msgs.length).toBe(1); expect(msgs[0].payload).toBeInstanceOf(RPC.AppendEntries); expect(msgs[0].payload.leaderId).toBe("r1"); r.tick(); expect(msgs.length).toBe(2); expect(msgs[1].payload).toBeInstanceOf(RPC.AppendEntries); expect(msgs[1].payload.leaderId).toBe("r1"); })(); (function testRecvHeartbeatFollower() { const r = new Node("r1", ["r1","r2"]); expect(r.electionElapsed).toBe(0); r.tick(); expect(r.electionElapsed).toBe(1); r.recv({ from: "r2", to: "r1", payload: new RPC.AppendEntries(1, "r2", 0, 0, [], 0), clock: 1 }); expect(r.electionElapsed).toBe(0); })(); return "Test Node"; }45:T9b1,class Cluster extends View { constructor(spec) { super(); this.spec = { defaultDistance: 10, ...spec }; const peers = Object.keys(this.spec.nodes); this.epoch = 0; this.queues = Object.fromEntries(peers.map(p => [p, []])); Object.defineProperties(this, { _conns: { value: {}, writable: true } }); for (const x of peers) { if (!this._conns[x]) this._conns[x] = {}; for (const y of peers) { if (!this._conns[y]) this._conns[y] = {}; this._conns[x][y] = this._conns[y][x] = this.spec.defaultDistance; } } this.nodes = Object.fromEntries(peers.map(id => { const node = new Node(id, peers, this.spec.nodes[id]); node.addEventListener('event', e => this.dispatch('event', e.detail)); node.addEventListener('message', e => { const msg = e.detail; const d = this.conns[id][msg.to]; if (d > 0) { const time = this.epoch + d; this.queues[msg.to].push([time, msg]); this.dispatch('message', [[id, this.epoch],[msg.to, time], msg]); } }); return [id, node]; })); } dispatch(type, detail) { this.dispatchEvent(new CustomEvent(type, { detail })); } dispatchNetwork() { this.dispatch('network', [this.epoch, mapEntries(this.conns, vals => ({ ...vals }))]); } start() { Object.values(this.nodes).forEach(n => n.notify('init')); this.dispatchNetwork(); } set conns(val) { this._conns = mapEntries(val, vals => ({ ...vals })) } get conns() { return this._conns; } toggleConnection(a, b) { if (this.conns[a][b] > 0) this.disconnect(a, b); else this.connect(a, b); } connect(a, b) { this._conns[a][b] = this._conns[b][a] = this.spec.defaultDistance; this.nodes[a].connect(b); this.nodes[b].connect(a); this.dispatchNetwork(); } disconnect(a, b) { this.conns[a][b] = this.conns[b][a] = 0; this.nodes[a].disconnect(b); this.nodes[b].disconnect(a); this.dispatchNetwork(); } tick(k = 1) { const nodes = Object.values(this.nodes); for (let i = 0; i < k; i++) { this.epoch++; nodes.forEach(n => n.tick()); nodes.forEach(n => { const q = this.queues[n.id]; while (q.length && q[0][0] <= this.epoch) { const msg = q.shift()[1]; if (this.conns[msg.from][n.id] > 0) { n.recv(msg); } } }); } } }46:T64c,{ (function testElection() { const nodes = { r1: { electionTimeoutRange: [3, 3] }, r2: {}, r3: {} }; const c = new Cluster({ defaultDistance: 1, nodes }); c.tick(3); expect(c.nodes['r1'].state).toBe(State.CANDIDATE); c.tick(1); expect(c.nodes['r2'].votedFor).toBe('r1'); expect(c.nodes['r3'].votedFor).toBe('r1'); c.tick(1); expect(c.nodes['r1'].state).toBe(State.LEADER); })(); (function testAgreement() { const nodes = { r1: { electionTimeoutRange: [3, 3], heartbeatTimeout: 3 }, r2: {}, r3: {} }; const c = new Cluster({ defaultDistance: 1, nodes }); c.tick(5); expect(c.nodes['r1'].state).toBe(State.LEADER); c.tick(1); c.nodes['r1'].addLog(); expect(c.nodes['r1'].logs[1]).toEqual([1,1]); c.tick(4); expect(c.nodes['r1'].commitIndex).toBe(1); expect(c.nodes['r2'].commitIndex).toBe(0); expect(c.nodes['r3'].commitIndex).toBe(0); c.tick(3); expect(c.nodes['r2'].commitIndex).toBe(1); expect(c.nodes['r3'].commitIndex).toBe(1); })(); (function testRelectionAfterCrach() { const nodes = { r1: { electionTimeoutRange: [3, 3] }, r2: { electionTimeoutRange: [5, 5] }, r3: {} }; const c = new Cluster({ defaultDistance: 1, nodes }); c.tick(5); expect(c.nodes['r1'].state).toBe(State.LEADER); c.nodes['r1'].stop(); c.tick(6); // r2 becomeCandidate c.tick(1); expect(c.nodes['r3'].votedFor).toBe("r2"); c.tick(1); expect(c.nodes['r2'].state).toBe(State.LEADER); })(); return "Test Cluster" }47:T566,useDrag = { const noevent = e => { e.preventDefault(); e.stopImmediatePropagation(); }; return (ref, { onStart = noop, onDrag = noop, onStop = noop, distance = 5 }) => useEffect(() => { const d2 = distance ** 2; const downed = e => { e.stopImmediatePropagation(); const x = e.clientX, y = e.clientY; const { top, left } = e.target.getBoundingClientRect(); const p = [x - left, y - top]; let started = false; const event = e => ({ p, x, y, dx: e.clientX - x, dy: e.clientY - y }); const moved = e => { if (!started) { if ((e.clientX - x) ** 2 + (e.clientY - y) ** 2 > d2) { started = true; noevent(e); onStart(event(e)); } } else { noevent(e); onDrag(event(e)); } }; const upped = e => { noevent(e); onStop(event(e)); e.view.removeEventListener('pointermove', moved, true); e.view.removeEventListener('pointerup', upped, true); }; e.view.addEventListener('pointermove', moved, true); e.view.addEventListener('pointerup', upped, true); }; ref.current.addEventListener('pointerdown', downed); return () => ref.current.removeEventListener('pointerdown', downed); }, [onStart, onDrag, onStop]); }48:Td0e,md`### Papers, Specs, Courses * [Raft Consensus Algorithm](https://raft.github.io/) * [Consensus: Bridging Theory and Practice](https://github.com/ongardie/dissertation) * [ARC: Analysis of Raft Consensus](https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-857.pdf) * [Raft Refloated: Do We Have Consensus?](https://www.cl.cam.ac.uk/~ms705/pub/papers/2015-osr-raft.pdf) * [ongardie/raft.tla: TLA+ specification for the Raft consensus algorithm](https://github.com/ongardie/raft.tla) * [ongardie/raft-pseudocode: attempt at summarizing Raft in one page of pseudo-code](https://github.com/ongardie/raft-pseudocode) * [MIT 6.824: Distributed Systems](https://pdos.csail.mit.edu/6.824/index.html) * [Students' Guide to Raft :: Jon Gjengset](https://thesquareplanet.com/blog/students-guide-to-raft/) * [Instructors' Guide to Raft :: Jon Gjengset](https://thesquareplanet.com/blog/instructors-guide-to-raft/) * [[2004.05074] Paxos vs Raft: Have we reached consensus on distributed consensus?](https://arxiv.org/abs/2004.05074) ### Implementations * [datatechnology/cornerstone: C++ implementation of raft consensus](https://github.com/datatechnology/cornerstone) * [eliben/raft: Raft implementation in Go](https://github.com/eliben/raft/) * [etcd/raft: Go implementation used in etcd](https://github.com/etcd-io/etcd/tree/master/raft) * [tikv/raft-rs: Raft distributed consensus algorithm implemented in Rust.](https://github.com/tikv/raft-rs) * [rabbitmq/ra: A Raft implementation for Erlang and Elixir that strives to be efficient and make it easier to use multiple Raft clusters in a single system.](https://github.com/rabbitmq/ra/) * [pablosmedina/ckite: CKite - A JVM implementation of the Raft distributed consensus algorithm written in Scala](https://github.com/pablosmedina/ckite) ### Related Works * [ongardie/runway-model-raft: Raft model for Runway](https://github.com/ongardie/runway-model-raft) * [CloudScope](http://bbengfort.github.io/cloudscope/) * [Visualizing Distributed Systems – Benjamin Bengfort](http://www.cs.umd.edu/~bengfort/research/visualizing-distributed-systems/) * [The TSViz visualization engine](https://bestchai.bitbucket.io/tsviz/) * [WaveDrom - Digital timing diagram everywhere](https://wavedrom.com/) * [Introduction — TimingAnalyzer Documentation](https://www.timing-diagrams.com/) * [Timing Diagram - an overview | ScienceDirect Topics](https://www.sciencedirect.com/topics/computer-science/timing-diagram) * [UML Timing Diagrams - Overview of Graphical Notation](https://www.uml-diagrams.org/timing-diagrams.html) ### Misc * [Implementing Raft: Part 0 - Introduction - Eli Bendersky's website](https://eli.thegreenplace.net/2020/implementing-raft-part-0-introduction/) * [You. Must. Build. A. Raft! Consul's Consensus Protocol Explained](https://www.hashicorp.com/resources/raft-consul-consensus-protocol-explained) * [RAFT Explained – Part 1/3: Introduction to the Consensus Problem](https://blog.container-solutions.com/raft-explained-part-1-the-consenus-problem) * [分散合意アルゴリズム Raft を理解する - Qiita](https://qiita.com/torao@github/items/5e2c0b7b0ea59b475cce) * [Raft(分散合意アルゴリズム)について](https://gist.github.com/sile/ad435262c17eb79f133d) * [Lamport's Logical Clocks](https://mwhittaker.github.io/blog/lamports_logical_clocks/) `49:[] 2f:{"title":"Raft Consensus Simulator","cells":[{"id":0,"value":"md`# Raft Consensus Simulator`","pinned":false,"hidden":false,"mode":"ojs"},{"id":989,"value":"md`[Raft](https://raft.github.io/) is a distributed consensus algorithm that is widely adopted by many distributed systems like [Kubernetes](https://kubernetes.io/) (through [etcd](https://etcd.io/)).\n\nIt is a consensus algorithm that is designed to be easy to understand, but once you set out to implement it, it is still quite [tricky](https://thesquareplanet.com/blog/students-guide-to-raft/) to get it correct. There are still corner cases not easy to grasp mentally, especially when it comes to network splitting.\n\nInspired by Bret Victor's [Ladder of Abstraction](http://worrydream.com/LadderOfAbstraction/) and learning from the [prior](https://github.com/ongardie/raftscope) [arts](http://thesecretlivesofdata.com/raft/), I build this simulator, hopefully helpful to anyone interested in this algorithm.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":18057,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":17160,"value":"{\n const onToggle = () => viewof playback.toggle();\n const onSpeed = v => viewof playhead.speed = v;\n return render(() => jsx`

\n <${PlaybackControl} paused=${playback} speed=${playhead.speed} \n onToggle=${onToggle} onSpeed=${onSpeed} />\n

\n <${NodesControl} onTrigger=${scenarios.restart} />\n

`);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":9544,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":7470,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":17953,"value":"md`Here are some typical scenarios to get started.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":17859,"value":"{\n const content = md`\n* #### [Basic](#basic)
\nA simple 3 nodes cluster with leader election and log replication.\n\n* #### [Leader Down And Restart](#leaderDownRestart)
\nLeader re-election in a 5 nodes cluster when the previous leader down.\n\n* #### [Network Split](#networkSplit)
\nA 5 nodes cluster experiencing network split.\n`;\n \n const onClick = e => {\n e.preventDefault();\n const scenario = e.target.href.match(/#(.*)$/)[1];\n scenarios[scenario]();\n }\n for (const a of content.querySelectorAll('h4 a')) {\n a.addEventListener('click', onClick);\n }\n return content;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":336,"value":"md`\n---\n## Code`","pinned":false,"hidden":false,"mode":"ojs"},{"id":15718,"value":"md`### App State`","pinned":false,"hidden":false,"mode":"ojs"},{"id":17965,"value":"md`Heavily abusing [Synchronized Views](https://observablehq.com/@mbostock/synchronized-views) to mimic a stateful data flow.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":6381,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":6974,"value":"viewof playback = new class Playback extends View {\n constructor() {\n super();\n this.paused = false;\n }\n \n pause() {\n this.paused = true;\n this.notify();\n }\n \n start() {\n this.paused = false;\n this.notify();\n }\n \n toggle() {\n this.paused ? this.start() : this.pause();\n }\n \n get value() {\n return this.paused;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":7005,"value":"viewof clock = {\n const clock = new class Clock extends View {\n constructor() {\n super();\n this.tick = this.tick.bind(this);\n this.toggle = this.toggle.bind(this);\n this.prev = undefined;\n this.delta = 0;\n this.handle = undefined;\n }\n\n toggle(paused) {\n if (paused) {\n cancelAnimationFrame(this.handle);\n this.prev = undefined;\n } else {\n this.handle = requestAnimationFrame(this.tick);\n }\n }\n\n tick() {\n const now = Date.now();\n this.delta = now - (this.prev || now);\n this.prev = now;\n this.notify();\n this.handle = requestAnimationFrame(this.tick);\n }\n\n get value() {\n return this.delta;\n }\n }\n \n invalidation.then(viewof playback.observe(clock.toggle));\n return clock;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":7007,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":12987,"value":"viewof cursor = {\n const cursor = new class Cursor extends View {\n constructor() {\n super();\n Object.defineProperties(this, {\n _value: { value: 0, writable: true },\n _playhead: { value: undefined, writable: true },\n });\n }\n \n reset() {\n this._value = 0;\n this.notify();\n }\n \n set playhead(val) {\n this._playhead = val;\n if (!val.paused) \n this._value = val.current;\n \n this.notify();\n }\n \n set value(val) {\n if (this._playhead.paused) \n this._value = Math.min(this._playhead.max, val);\n \n this.notify();\n }\n \n get value() {\n return this._value;\n }\n }\n \n invalidation.then(viewof playhead.observe(p => cursor.playhead = p));\n return cursor;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":13056,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":11701,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":12826,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":12867,"value":"makeSnapshot = ({ timed, messages, networks }, cursor) => {\n const nodes = Object.entries(timed).map(([id, evts]) => {\n let node;\n evts.forEach(([t, e]) => {\n if (t <= cursor) node = { id: e.node, ...e.state, epoch: e.epoch };\n });\n const elapsed = Math.floor(cursor - node.epoch);\n if (node.state == State.LEADER) {\n node.heartbeatElapsed += elapsed;\n } else {\n node.electionElapsed += elapsed;\n }\n node.epoch = Math.floor(cursor);\n return node;\n })\n \n const msgs = messages.filter(([from, to, _]) => from[1] <= cursor && cursor <= to[1]);\n let network;\n networks.forEach(([t, net]) => {\n if (t <= cursor) network = net;\n });\n return { nodes, network, messages: msgs };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":12468,"value":"snapshot = makeSnapshot(execution, cursor)","pinned":false,"hidden":false,"mode":"ojs"},{"id":17680,"value":"$38","pinned":false,"hidden":false,"mode":"ojs"},{"id":1055,"value":"md`### UI`","pinned":false,"hidden":false,"mode":"ojs"},{"id":15835,"value":"md`#### Components`","pinned":false,"hidden":false,"mode":"ojs"},{"id":7844,"value":"$39","pinned":false,"hidden":false,"mode":"ojs"},{"id":11466,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs"},{"id":16598,"value":"PlaybackControl = component(({ paused, speed, onToggle, onSpeed }) => {\n return jsx`

\n <${PlaybackButton} size=12 paused=${paused} onClick=${onToggle} />\n <${Slider} min=0 max=0.05 step=0.001 value=${speed} onChange=${onSpeed} />\n ${speed.toFixed(3)}x\n

`;\n});","pinned":false,"hidden":false,"mode":"ojs"},{"id":16455,"value":"PlaybackButton = component(({ size, paused, onClick = noop }) => {\n const [hover, setHover] = useState(false);\n const h = size * 0.5;\n const path = d3.path();\n if (paused) {\n path.moveTo(-h * 0.7, -h); path.lineTo(h, 0); path.lineTo(-h * 0.7, h)\n path.closePath();\n } else {\n const w = h * 0.5, g = h * 0.2;\n path.moveTo(-w-g,-h); path.lineTo(-g,-h); path.lineTo(-g,h); path.lineTo(-w-g,h);\n path.closePath();\n path.moveTo(w+g,-h); path.lineTo(g,-h); path.lineTo(g,h); path.lineTo(w+g,h);\n path.closePath();\n }\n const props = {\n onMouseOver: useCallback(() => setHover(true), []),\n onMouseOut: useCallback(() => setHover(false), []),\n onClick,\n };\n const fill = hover ? 'hsl(0,0%,30%)' : 'white';\n return jsx`<${Button} ...${props}>\n <${SVG} width=${size} height=${size}>\n \n \n `\n});","pinned":false,"hidden":false,"mode":"ojs"},{"id":18030,"value":"NodesControl = component(({ onTrigger }) => {\n const [num, setNum] = useState(5);\n return jsx`

\n nodes\n <${Slider} min=1 max=7 step=1 value=${num} onChange=${setNum} />\n ${num}\n <${Button} onClick=${() => onTrigger(num)}>reset\n

`;\n});","pinned":false,"hidden":false,"mode":"ojs"},{"id":9546,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs"},{"id":10052,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs"},{"id":17010,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs"},{"id":16946,"value":"$3e","pinned":false,"hidden":false,"mode":"ojs"},{"id":15103,"value":"BGText = {\n const textProps = {\n fontFamily: \"monospace\", \n style: { userSelect: 'none' }, fontSize: 10,\n fill: 'black',\n };\n\n return component(({ text, ...props }) => {\n return jsx`\n \n ${text}\n `;\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":7472,"value":"Lifeline = component(({ data = [], width, height, sep, ...props }) => {\n if (!data.length) return null;\n const start = data[0][0][0], end = data[data.length-1][0][1];\n const scale = d3.scaleLinear([start, end], [0, width]);\n\n const sections = data.map(([[t0, t1], state], i) => {\n const x1 = scale(t0), x2 = scale(t1);\n return jsx`\n \n \n `;\n });\n\n return jsx`${sections}`;\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":7257,"value":"Axis = {\n const lh = 12, sw = 0.5, stroke = 'hsl(0,0%,30%)';\n const textProps = {\n fontFamily: \"Open Sans\", fontSize: 8,\n textAnchor: \"middle\", alignmentBaseline: \"central\",\n stroke: 'none', style: { userSelect: 'none' }\n };\n \n return component(({ width, domain, ...props }) => {\n const scale = d3.scaleLinear(domain, [0, width]);\n const ticks = d3.ticks(domain[0], domain[1], 10);\n \n const minor = ticks.map(scale)\n .map((x, i) => jsx``);\n const major = ticks.map((v, i) => jsx`${v}`);\n \n return jsx`\n \n ${minor}\n ${major}\n `;\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":10733,"value":"ClipArea = component(({ id, width, height, children }) => jsx`\n <${Fragment}>\n \n ${children}\n `)","pinned":false,"hidden":false,"mode":"ojs"},{"id":17229,"value":"Text = component(({ children, ...rest }) => {\n const props = {\n fontFamily: \"monospace\", alignmentBaseline: \"hanging\",\n style: { userSelect: 'none' }, fontSize: 12,\n fill: 'black'\n };\n return jsx`${children}`;\n});","pinned":false,"hidden":false,"mode":"ojs"},{"id":4725,"value":"$3f","pinned":false,"hidden":false,"mode":"ojs"},{"id":16430,"value":"Slider = component(({ min, max, value, step, onChange }) => {\n const props = {\n type: 'range', className: cls('slider'),\n min, max, step, value,\n onChange: useCallback(e => onChange(e.target.valueAsNumber), [onChange]),\n };\n return jsx``;\n});","pinned":false,"hidden":false,"mode":"ojs"},{"id":16419,"value":"Button = component(({ onMouseOver = noop, onMouseOut = noop, onClick = noop, children }) => {\n const props = { className: cls('button'), onMouseOver, onMouseOut, onClick };\n return jsx`

${children}

`;\n});","pinned":false,"hidden":false,"mode":"ojs"},{"id":796,"value":"SVG = component(({ width, height, children }) => \n jsx``)","pinned":false,"hidden":false,"mode":"ojs"},{"id":11196,"value":"g = children => jsx`${children}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":6053,"value":"md`#### Assets`","pinned":false,"hidden":false,"mode":"ojs"},{"id":16370,"value":"$40","pinned":false,"hidden":false,"mode":"ojs"},{"id":14469,"value":"$41","pinned":false,"hidden":false,"mode":"ojs"},{"id":1339,"value":"styles = ({\n state: {\n [State.FOLLOWER]: d3.schemeSet3[4],\n [State.CANDIDATE]: d3.schemeSet3[6],\n [State.LEADER]: d3.schemeSet3[3],\n [State.STOPPED]: 'hsl(0,0%,60%)'\n },\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":8105,"value":"$42","pinned":false,"hidden":false,"mode":"ojs"},{"id":333,"value":"md`### Raft Core`","pinned":false,"hidden":false,"mode":"ojs"},{"id":255,"value":"State = Object.freeze({\n FOLLOWER: \"follower\",\n CANDIDATE: \"candidate\",\n LEADER: \"leader\",\n STOPPED: \"stopped\"\n});","pinned":false,"hidden":false,"mode":"ojs"},{"id":164,"value":"RPC = {\n class RequestVote {\n constructor(term, candidateId, lastLogIndex, lastLogTerm) {\n this.term = term;\n this.candidateId = candidateId;\n this.lastLogIndex = lastLogIndex;\n this.lastLogTerm = lastLogTerm;\n }\n }\n class RequestVoteResp {\n constructor(term, voteGranted) {\n this.term = term;\n this.voteGranted = voteGranted;\n }\n }\n class AppendEntries {\n constructor(term, leaderId, prevLogIndex, prevLogTerm, logs, leaderCommit) {\n this.term = term;\n this.leaderId = leaderId;\n this.prevLogIndex = prevLogIndex;\n this.prevLogTerm = prevLogTerm;\n this.logs = logs;\n this.leaderCommit = leaderCommit;\n }\n }\n class AppendEntriesResp {\n constructor(term, success, nextIndex) {\n this.term = term;\n this.success = success;\n this.nextIndex = nextIndex;\n }\n }\n \n return { RequestVote, RequestVoteResp, AppendEntries, AppendEntriesResp };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":118,"value":"$43","pinned":false,"hidden":false,"mode":"ojs"},{"id":253,"value":"$44","pinned":false,"hidden":false,"mode":"ojs"},{"id":423,"value":"$45","pinned":false,"hidden":false,"mode":"ojs"},{"id":437,"value":"$46","pinned":false,"hidden":false,"mode":"ojs"},{"id":1475,"value":"md`### Utils`","pinned":false,"hidden":false,"mode":"ojs"},{"id":8739,"value":"md`#### React Hooks`","pinned":false,"hidden":false,"mode":"ojs"},{"id":9440,"value":"useConst = f => useState(f)[0];","pinned":false,"hidden":false,"mode":"ojs"},{"id":8727,"value":"useNonPassive = (ref, type, listener) => useEffect(() => {\n ref.current.addEventListener(type, listener, { passive: false });\n return () => ref.current.removeEventListener(type, listener);\n}, [listener]);","pinned":false,"hidden":false,"mode":"ojs"},{"id":9301,"value":"$47","pinned":false,"hidden":false,"mode":"ojs"},{"id":8736,"value":"md`#### Misc`","pinned":false,"hidden":false,"mode":"ojs"},{"id":18103,"value":"class EventDispatcher {\n constructor() {\n this._listeners = [];\n }\n\n hasEventListener(type, listener) {\n return this._listeners.some(item => item.type === type && item.listener === listener);\n }\n\n addEventListener(type, listener) {\n if (!this.hasEventListener(type, listener)) {\n this._listeners.push({type, listener, options: {once: false}});\n }\n return this\n }\n\n removeEventListener(type, listener) {\n let index = this._listeners.findIndex(item => item.type === type && item.listener === listener);\n if (index >= 0) this._listeners.splice(index, 1);\n return this;\n }\n\n removeEventListeners() {\n this._listeners = [];\n return this;\n }\n\n dispatchEvent(evt) {\n this._listeners\n .filter(item => item.type === evt.type)\n .forEach(item => {\n const {type, listener, options: {once}} = item;\n listener.call(this, evt);\n if (once === true) this.removeEventListener(type, listener)\n });\n return this\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":16540,"value":"cls = name => `scope-${name}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1573,"value":"math = {\n // some math utils stolen from @thi.ng/math\n \n const DEG2RAD = Math.PI / 180;\n const norm = (x, a, b) => b !== a ? (x - a) / (b - a) : 0;\n const clamp = (x, min, max) => x < min ? min : x > max ? max : x;\n const clamp01 = x => clamp(x, 0, 1);\n const mix = (a, b, t) => a + (b - a) * t;\n const fit = (x, a, b, c, d) => mix(c, d, norm(x, a, b));\n const fit01 = (x, a, b) => mix(a, b, clamp01(x));\n \n return {\n DEG2RAD,\n EPS: 1e-6,\n TAU: Math.PI * 2,\n HALF_PI: Math.PI * 0.5,\n SQRT3: Math.sqrt(3),\n COS30: Math.cos(30 * DEG2RAD),\n \n norm, clamp, clamp01, mix, fit, fit01,\n step: (edge, x) => x < edge ? 0 : 1,\n frac: v => v % 1,\n fitClamped: (x, a, b, c, d) => fit01(norm(x, a, b), c, d),\n };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":7206,"value":"polygons = ({\n triangle: size => d3.range(3).map(i => {\n const r = size * math.SQRT3 / 2;\n const theta = i / 3 * math.TAU - math.HALF_PI;\n return [Math.cos(theta) * r, Math.sin(theta) * r];\n })\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":15858,"value":"arrays = ({\n last: arr => arr.length > 0 ? arr[arr.length-1] : undefined,\n mapcat: (arr, fn) => [].concat.apply([], arr.map(fn))\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":4518,"value":"combinations = arr => {\n const res = [];\n for (let i = 0; i < arr.length; i++) {\n for (let j = i + 1; j < arr.length; j++ ) {\n res.push([arr[i],arr[j]]);\n }\n }\n return res;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":12368,"value":"mapEntries = (obj, f) => Object.fromEntries(Object.entries(obj).map(([k, v]) => [k, f(v)]))","pinned":false,"hidden":false,"mode":"ojs"},{"id":16404,"value":"noop = () => {}","pinned":false,"hidden":false,"mode":"ojs"},{"id":12231,"value":"fps = {\n let t = performance.now(), delta = 0;\n const last = [t];\n return cell => {\n last.length >= 10 && last.shift();\n t = performance.now();\n delta = (t - last[0]) / last.length;\n last.push(t);\n return Math.round(1000 / delta);\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"md`### Appendix`","pinned":false,"hidden":false,"mode":"ojs"},{"id":49,"value":"import {jsx, component, Fragment, render, useState, useEffect, useRef, useMemo, useCallback, useReducer, useContext, createContext} from '@j-f1/react'","pinned":false,"hidden":false,"mode":"ojs"},{"id":242,"value":"expect = require('expect@25.1.0')","pinned":false,"hidden":false,"mode":"ojs"},{"id":32,"value":"md`\n---\n## References`","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"$48","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W49","stdlib":"1","titling":"auto"}