crdt-sequences-observed-remove

Answer

The core data structure is an RGA (Replicated Growable Array) — a CRDT that represents the sequence as a tree of nodes rooted at a sentinel. The visible sequence is a DFS traversal visiting children in descending site-ID / counter order, which provides deterministic interleaving of concurrent inserts. Deletions are observed-remove tombstones (nodes are never physically removed until GC). Tombstone garbage collection uses causal stability: a tombstone is safe to collect only when every peer's version vector proves they have processed all operations up to at least that node's sequence number.

Implementation (rga-sequence.js)

export class RGASequence {
  constructor(siteId) {
    this.siteId = siteId;
    this.counter = 0;
    this.nodes = new Map();
    // Sentinel root
    const rootId = { site: '', seq: -1 };
    this.nodes.set(':-1', new RGANode(rootId, null, null));
    this.vv = {};
    this.vv[siteId] = 0;
  }

  _key(id) { return `${id.site}:${id.seq}`; }
  _nextId() {
    const id = { site: this.siteId, seq: this.counter };
    this.counter += 1;
    return id;
  }

  /** Insert at visible position pos (0-based). Returns node id or null. */
  insert(pos, value) {
    const visible = this._visibleNodes();
    if (pos < 0 || pos > visible.length) return null;
    const parent = pos === 0
      ? this.nodes.get(':-1')
      : visible[pos - 1];
    const id = this._nextId();
    const node = new RGANode(id, value, parent.id);
    this.nodes.set(this._key(id), node);
    this.vv[this.siteId] = this.counter;
    return id;
  }

  /** Delete at visible position pos. Returns true on success. */
  delete(pos) {
    const visible = this._visibleNodes();
    if (pos < 0 || pos >= visible.length) return false;
    visible[pos].deleted = true;
    return true;
  }

  /** Return the visible sequence as an array of values. */
  get() { return this._visibleNodes().map(n => n.value); }

  /** DFS traversal with child ordering (siteId desc, seq desc). */
  _traverse() {
    const children = new Map();
    for (const [, node] of this.nodes) {
      if (!node.parentId) continue;
      const pk = this._key(node.parentId);
      if (!children.has(pk)) children.set(pk, []);
      children.get(pk).push(node);
    }
    for (const [, list] of children) {
      list.sort((a, b) => {
        if (a.id.site !== b.id.site) return a.id.site < b.id.site ? 1 : -1;
        return b.id.seq - a.id.seq;
      });
    }
    const result = [];
    const dfs = (key) => {
      const kids = children.get(key) || [];
      for (const child of kids) {
        result.push(child);
        dfs(this._key(child.id));
      }
    };
    dfs(':-1');
    return result;
  }

  _visibleNodes() { return this._traverse().filter(n => !n.deleted); }

  /** Merge from another RGASequence. */
  merge(other) {
    for (const [site, seq] of Object.entries(other.vv)) {
      this.vv[site] = Math.max(this.vv[site] || 0, seq);
    }
    for (const [key, remoteNode] of other.nodes) {
      if (key === ':-1') continue;
      const local = this.nodes.get(key);
      if (!local) {
        this.nodes.set(key, new RGANode(
          { ...remoteNode.id }, remoteNode.value,
          remoteNode.parentId ? { ...remoteNode.parentId } : null,
        ));
        if (remoteNode.deleted) this.nodes.get(key).deleted = true;
      } else if (remoteNode.deleted) {
        local.deleted = true;  // once deleted, always deleted
      }
    }
  }

  /**
   * Garbage-collect tombstones that are causally stable.
   * A tombstone is stable when every peer's VV has seen counter >= node.id.seq.
   */
  gc(peerVVs) {
    const toRemove = [];
    for (const [key, node] of this.nodes) {
      if (key === ':-1' || !node.deleted) continue;
      let stable = true;
      for (const [, peerVV] of Object.entries(peerVVs)) {
        const seen = peerVV[node.id.site];
        if (seen === undefined || seen < node.id.seq) { stable = false; break; }
      }
      if (stable) toRemove.push(key);
    }
    for (const key of toRemove) this.nodes.delete(key);
    return toRemove.length;
  }
}

class RGANode {
  constructor(id, value, parentId) {
    this.id = id;
    this.value = value;
    this.parentId = parentId;
    this.deleted = false;
  }
}

Key design decisions: