Version:

Merkle Tree Architecture

Developing Merkle Trees for ACE is driven by the following requirements:

Table-diff is efficient for one-off or infrequent checks, but rerunning it regularly recomputes block hashes across the entire table every time.
When most data is unchanged, re-hashing every block is wasteful—especially on very large tables (think ~1 TB or ~1B rows) where hash scans dominate runtime and resource use.
A Merkle tree lets us cache and reuse block hashes between runs. Unchanged subtrees are skipped; only branches covering modified rows are rehashed and compared, reducing I/O, CPU, and network load for recurring diffs.
The goal is fast, incremental validation for operators who need frequent consistency checks without paying the full-block hashing cost each run.

What Is a Merkle Tree?

A Merkle tree is a hash tree: leaves hold hashes of data blocks; every internal node combines its children’s hashes into a parent hash. The root represents the entire dataset—if any leaf changes, all ancestors (and the root) change.
ACE optimisation: parent nodes are computed as XORs of child hashes rather than hashing the concatenation. XOR is fast, associative, and easy to update incrementally when a child changes, making rebuilds cheaper for large trees.

flowchart TB
  ROOT["Root = (h1 XOR h2) XOR (h3 XOR h4)"]:::root

  N12["Parent = h1 XOR h2"]:::node
  N34["Parent = h3 XOR h4"]:::node

  L1["Leaf 1<br/>hash = h1"]:::leaf
  L2["Leaf 2<br/>hash = h2"]:::leaf
  L3["Leaf 3<br/>hash = h3"]:::leaf
  L4["Leaf 4<br/>hash = h4"]:::leaf

  ROOT --> N12
  ROOT --> N34
  N12 --> L1
  N12 --> L2
  N34 --> L3
  N34 --> L4

  classDef leaf fill:#eef2f7,stroke:#5b6f82,color:#0f1c2d;
  classDef node fill:#e8f0ff,stroke:#3b73b9,color:#0f1c2d;
  classDef root fill:#fff6e0,stroke:#d39b00,color:#1f2a44;

How Merkle Trees Work in ACE

Initial build (full scan once): ACE partitions the table into PK-ordered blocks (like table-diff) and computes leaf hashes for every block on each node—this is the only full-table scan. Parent hashes are built upward using XOR to form the root.
Change capture (pgoutput + replication slot): The table is added to a publication; pgoutput changes are streamed into a logical replication slot. ACE marks affected blocks as dirty based on PK ranges (no full re-scan).
Update step: UpdateMtree reads accumulated changes from the slot, splits or merges blocks if needed, recomputes hashes only for dirty/new leaves, rebuilds parent XORs, and clears dirty flags. Block size is recovered from metadata to stay consistent with the build.
Diff step: DiffMtree first runs an update (to fold recent changes into the tree), then traverses trees across nodes. Matching hashes at a node mean “skip subtree”; mismatches recurse until leaves are reached, where row-level diffs are fetched if required. When every mismatched block for a node pair compares clean at row level, the diff refreshes those stale leaf hashes from live data (a write to the ace_mtree_* tables) so the phantom mismatch does not recur.

flowchart TD
  Build["Build: full table scan<br/>compute leaf hashes<br/>build XOR parents"]:::build --> Slot["Logical replication slot<br/>(pgoutput changes)"]:::cdc
  Slot --> Update["Update: mark dirty blocks<br/>split/merge if needed<br/>rehash dirty leaves<br/>rebuild parents"]:::update
  Update --> Diff["Diff: compare roots<br>→ if mismatch, recurse<br>→ fetch rows at leaves"]:::diff

  classDef build fill:#eef2f7,stroke:#5b6f82,color:#0f1c2d;
  classDef cdc fill:#e8f0ff,stroke:#3b73b9,color:#0f1c2d;
  classDef update fill:#fff6e0,stroke:#d39b00,color:#1f2a44;
  classDef diff fill:#fdeaea,stroke:#d14343,color:#1f1a1a;

CDC Pipeline and Dirty Block Detection

Capture: Each node adds the table to a publication; pgoutput changes are streamed via a logical replication slot (see UpdateFromCDC). Inserts/deletes/updates are mapped to PK ranges; affected blocks are marked dirty—no rehash yet.
Persist: The slot retains WAL until ACE consumes it; long delays can bloat WAL. Ensure slot retention is acceptable and the service role has replication/publication privileges.
Apply: On UpdateMtree, ACE reads the slot, updates per-block counters/dirty flags, and resets range_end to NULL for the tail when new rows arrive past the last bound. Splits/merges are then decided from those dirty flags.
Options: --no-cdc skips slot consumption (not recommended before a diff); CDCProcessingTimeout bounds how long ACE waits while applying changes.
User reminders
Keep the slot healthy: monitor lag to avoid WAL buildup; drop/recreate only if you rebuild trees.
Run update before diff (ACE does this automatically for diff) so trees include recent changes.
Ensure the publication still includes the table and that the slot isn’t removed by maintenance.

flowchart LR
  WAL["WAL (pgoutput)"]:::wal --> Slot["Logical slot<br/>(retains changes)"]:::cdc --> Apply["UpdateFromCDC:<br/>mark dirty blocks<br/>update tail bound"]:::apply --> Update["UpdateMtree:<br/>split/merge decisions<br/>rehash dirty leaves"]:::update

  classDef wal fill:#eef2f7,stroke:#5b6f82,color:#0f1c2d;
  classDef cdc fill:#e8f0ff,stroke:#3b73b9,color:#0f1c2d;
  classDef apply fill:#fff6e0,stroke:#d39b00,color:#1f2a44;
  classDef update fill:#fdeaea,stroke:#d14343,color:#1f1a1a;

Updates: Why Splits and Merges Matter

Why split? Hot ranges can grow far beyond the intended block size due to concentrated inserts (e.g., sequential PKs). Oversized blocks slow hashing and make diff localisation coarse. Splitting restores a balanced fan-out and keeps leaf work bounded.
Why merge? Sparse/deleted ranges can shrink, leaving tiny blocks that add overhead with little data. Merging adjacent small blocks reduces hash tasks and tree depth.
Update flow: During UpdateMtree, ACE identifies dirty/new blocks from CDC, then:
Finds overfull blocks and splits them (with re-sequencing of node positions).
Optionally merges underfull blocks if Rebalance is enabled.
Rehashes only the affected leaves and rebuilds parents.
Clears dirty flags so future updates skip unchanged blocks.

flowchart LR
  CDC["CDC marks dirty blocks"]:::cdc --> SplitCheck{"Over block_size?"}:::split
  SplitCheck -->|yes| Split["Split block<br/>adjust ranges"]:::op
  SplitCheck -->|no| MergeCheck{"Under merge threshold?"}:::split
  MergeCheck -->|yes| Merge["Merge adjacent small blocks"]:::op
  MergeCheck -->|no| Skip["No shape change"]:::op

  Split --> Rehash["Rehash affected leaves"]:::rehash
  Merge --> Rehash
  Skip --> Rehash
  Rehash --> Parents["Rebuild parent XORs<br/>clear dirty flags"]:::rehash

  classDef cdc fill:#e8f0ff,stroke:#3b73b9,color:#0f1c2d;
  classDef split fill:#fff6e0,stroke:#d39b00,color:#1f2a44;
  classDef op fill:#eef2f7,stroke:#5b6f82,color:#0f1c2d;
  classDef rehash fill:#fdeaea,stroke:#d14343,color:#1f1a1a;

Examples: Splitting and Merging Merkle Tree Nodes

Splitting
A split block is appended at the end (new node_position = max + 1) to avoid immediate parent-hash churn; afterward ACE re-sequences leaves by PK start so positions are contiguous for later maintenance.
Parent nodes are dropped and rebuilt after splits so XOR hashes reflect the new leaf layout.
Rationale: inserting the new block adjacent to the original would change hashes for every ancestor along that branch, forcing deeper traversal even though only two leaves changed. Appending preserves most parent-child hashes until the controlled rebuild, which limits needless tree churn.
Why adjacency hurts
Inserting the split block next to the original forces a cascade of parent hash changes, so diff traversal cannot prune early.

flowchart TB
  TitleBad["Bad: insert adjacent (parent churn)"]:::title
    AROOT["p6' (root changed)"]:::root
    AP4["p4'"]:::node
    AP5["p5'"]:::node
    AP1["p1'"]:::node
    AP2["p2'"]:::node
    AP3["p3'"]:::node
    AX1["x1"]:::leaf
    AM["m (new)"]:::leaf
    AN["n (new)"]:::leaf
    AX3["x3"]:::leaf
    AX4["x4"]:::leaf
    AX5["x5"]:::leaf

    AROOT --> AP4
    AROOT --> AP5
    AP4 --> AP1
    AP4 --> AP2
    AP5 --> AP3
    AP1 --> AX1
    AP1 --> AM
    AP2 --> AN
    AP2 --> AX3
    AP3 --> AX4
    AP3 --> AX5

  classDef root fill:#fff6e0,stroke:#d39b00,color:#1f2a44;
  classDef node fill:#e8f0ff,stroke:#3b73b9,color:#0f1c2d;
  classDef leaf fill:#eef2f7,stroke:#5b6f82,color:#0f1c2d;
  classDef title fill:transparent,stroke:none,color:#0f1c2d;

Why appending helps
Appending the new block leaves most parents intact; only the split branch and ancestors that include it change. Diff traversal prunes more quickly.

flowchart TB
  TitleGood["Good: append split block (minimal churn)"]:::title
    RROOT["p6' (root changed)"]:::root
    RP4["p4'"]:::node
    RP5["p5'"]:::node
    RP1["p1'"]:::node
    RP2["p2 (unchanged)"]:::node
    RP3["p3'"]:::node
    RX1["x1"]:::leaf
    RM["m (split part)"]:::leaf
    RX3["x3"]:::leaf
    RX4["x4"]:::leaf
    RX5["x5"]:::leaf
    RN["n (appended)"]:::leaf

    RROOT --> RP4
    RROOT --> RP5
    RP4 --> RP1
    RP4 --> RP2
    RP5 --> RP3
    RP1 --> RX1
    RP1 --> RM
    RP2 --> RX3
    RP2 --> RX4
    RP3 --> RX5
    RP3 --> RN

  classDef root fill:#fff6e0,stroke:#d39b00,color:#1f2a44;
  classDef node fill:#e8f0ff,stroke:#3b73b9,color:#0f1c2d;
  classDef leaf fill:#eef2f7,stroke:#5b6f82,color:#0f1c2d;
  classDef title fill:transparent,stroke:none,color:#0f1c2d;

Merging
ACE merges a block with its immediate successor when their combined row count is under ~1.5× block_size. The merged block keeps the lower position; the successor is deleted. After each merge pass, positions are re-sequenced (same temp-offset trick) to keep positions contiguous for later splits/merges.
Parent nodes are dropped and rebuilt post-merge.
Re-sequencing uses a large temporary offset (1,000,000) to avoid position collisions during moves; this is safe up to ~100B rows, but is disruptive and can change parent-child relationships, so heavy rebalancing is recommended only when absolutely necessary and during maintenance windows.

flowchart TB
  subgraph BeforeMerge["Before merge"]
    M0["pos=0  [1..80] (small)"]:::leaf --> M1["pos=1  [81..120] (small)"]:::leaf --> M2["pos=2  [121..300]"]:::leaf --> M3["pos=3  [301..nil]"]:::leaf
  end

  subgraph MergeStep["Merge step"]
    MM0["pos=0  [1..120] (merged)"]:::leaf
    MM2["pos=2  [121..300]"]:::leaf
    MM3["pos=3  [301..nil]"]:::leaf
  end

  subgraph AfterResequence["After resequence"]
    RM0["pos=0  [1..120]"]:::leaf --> RM1["pos=1  [121..300]"]:::leaf --> RM2["pos=2  [301..nil]"]:::leaf
  end

  M3 -.-> MM0
  MM3 -.-> RM0

  classDef leaf fill:#eef2f7,stroke:#5b6f82,color:#0f1c2d;

Additional Split/Merge Considerations

Open-ended last block handling
The trailing block often has range_end = NULL so new inserts beyond the current max PK land there. When splitting an unbounded block, ACE temporarily discovers a max PK to create a split point, then ensures the final leaf is unbounded again so future inserts keep hitting a single tail block. This prevents new rows from “falling off” the tree after a split.

flowchart LR
  Before["pos=0 [1..100]"]:::leaf --> Tail["pos=1 [101..nil] (tail)"]:::leaf
  After["pos=0 [1..100]"]:::leaf --> Mid["pos=1 [101..500]"]:::leaf --> Tail2["pos=2 [500..nil] (tail reset)"]:::leaf
  classDef leaf fill:#eef2f7,stroke:#5b6f82,color:#0f1c2d;

Composite PK split points
For composite keys, split points are chosen using ordered tuples (ROW(col1, col2, ...)) at roughly the midpoint of the block’s row count. Bounds and inserts are bound component-wise. If a final “sliver” block would be too small, ACE drops the last split point to avoid creating a tiny trailing leaf.
Simple PKs pick a single midpoint value; composite PKs load and register the composite type so range updates and inserts stay consistent with the PK ordering.
Thresholds and rebalance guidance
Splits fire when a block grows beyond ~2× block_size; merges apply when neighbouring blocks together are under ~1.5× block_size (or ~25% thresholds in Python reference). This keeps leaf sizes within a sensible band.
Re-sequencing and parent rebuilds are cheap compared to leaf rehashing, but they do perturb parent-child relationships. Use heavy rebalancing (--rebalance) sparingly—ideally in maintenance windows—to avoid churn on hot tables.

Diff Traversal Algorithm

ACE compares Merkle trees across node pairs top-down. If root hashes match, the entire table is considered in sync. When a parent hash mismatches, ACE descends to its children; matching subtrees are pruned, mismatching subtrees recurse until leaves are reached. If leaves don’t align (one side has extra splits/merges), the extra leaves are treated as mismatches.
Parent hashes are XORs of child hashes (fast to recompute). Leaf hashes are cryptographic hashes of table blocks; XOR collisions at parent levels are acceptable because leaf hashes still guard correctness.
Edge cases:
Unbalanced trees: If one node split/merged more, traversal still walks each subtree; missing peers are flagged as mismatches.
Early pruning: Large identical subtrees are skipped after a single hash compare.
Diff materialisation: Only at mismatching leaves; ACE then fetches block rows and aligns by PK.

flowchart TB
  %% Two trees with a mismatching branch and extra leaf on right
  subgraph TreeL["Node A"]
    LRoot["root_A"]:::root
    LA["A1"]:::node
    LB["A2"]:::node
    L1["L1"]:::leaf
    L2["L2"]:::leaf
    L3["L3"]:::leaf
    L4["L4"]:::leaf
    LRoot --> LA
    LRoot --> LB
    LA --> L1
    LA --> L2
    LB --> L3
    LB --> L4
  end

  subgraph TreeR["Node B"]
    RRoot["root_B"]:::root
    RA["B1"]:::node
    RB["B2"]:::node
    R1["R1"]:::leaf
    R2["R2"]:::leaf
    R3["R3"]:::leaf
    R4["R4"]:::leaf
    RExtra["R_extra"]:::leaf
    RRoot --> RA
    RRoot --> RB
    RA --> R1
    RA --> R2
    RB --> R3
    RB --> R4
    RB --> RExtra
  end

  %% Traversal annotations
  LRoot -. "hash mismatch" .- RRoot
  LA -. "hash match (prune)" .- RA
  LB -. "hash mismatch" .- RB
  L3 -. "leaf mismatch" .- R3
  L4 -. "leaf mismatch" .- R4
  RB -. "extra leaf" .-> RExtra

  classDef root fill:#fff6e0,stroke:#d39b00,color:#1f2a44;
  classDef node fill:#e8f0ff,stroke:#3b73b9,color:#0f1c2d;
  classDef leaf fill:#eef2f7,stroke:#5b6f82,color:#0f1c2d;

flowchart TB
  %% Balanced trees where only one leaf differs
  subgraph TreeL2["Node A"]
    LRoot2["root_A"]:::root
    LA2["A1"]:::node
    LB2["A2"]:::node
    L1a["L1"]:::leaf
    L2a["L2"]:::leaf
    L3a["L3"]:::leaf
    L4a["L4"]:::leaf
    LRoot2 --> LA2
    LRoot2 --> LB2
    LA2 --> L1a
    LA2 --> L2a
    LB2 --> L3a
    LB2 --> L4a
  end

  subgraph TreeR2["Node B"]
    RRoot2["root_B"]:::root
    RA2["B1"]:::node
    RB2["B2"]:::node
    R1a["R1"]:::leaf
    R2a["R2_diff"]:::leaf
    R3a["R3"]:::leaf
    R4a["R4"]:::leaf
    RRoot2 --> RA2
    RRoot2 --> RB2
    RA2 --> R1a
    RA2 --> R2a
    RB2 --> R3a
    RB2 --> R4a
  end

  LRoot2 -. "hash mismatch" .- RRoot2
  LA2 -. "hash mismatch" .- RA2
  LB2 -. "hash match (prune)" .- RB2
  L1a -. "match" .- R1a
  L2a -. "leaf mismatch" .- R2a

  classDef root fill:#fff6e0,stroke:#d39b00,color:#1f2a44;
  classDef node fill:#e8f0ff,stroke:#3b73b9,color:#0f1c2d;
  classDef leaf fill:#eef2f7,stroke:#5b6f82,color:#0f1c2d;

Notes: - Traversal proceeds until leaves are aligned or exhausted; missing peers (extra leaves) are flagged. - Parent XOR hashes speed pruning; leaf cryptographic hashes guard correctness. - Diffs are materialised only at mismatching leaves, limiting database reads. - In the unbalanced example above, the right-side tree has an extra leaf (R_extra). ACE descends until it exhausts matching parents; when it sees that RB has a child with no peer, it records that entire extra leaf as a mismatch (representing rows present only on Node B). Similarly, if Node A had more leaves, those would be marked as present-only-on-A. This ensures asymmetric splits/merges still surface as drift.

Operational Details and Limits

Schema objects and lifecycle: Build creates ace_mtree_<schema>_<table> plus a composite PK type when needed, metadata rows (block size, counts, timestamps), and adds the table to a publication/slot. Teardown drops these. Updates/diffs reuse the metadata; changing block_size requires a rebuild.
Block size reuse: UpdateMtree reads block size from metadata; you cannot “resize” a tree via update. Rebuild if you need a different block size.
CDC drift and slot health: If the logical slot is dropped or lags, WAL can bloat and trees become stale. Recover by rebuilding (init + build) and recreating the slot/publication entry. --no-cdc means you are diffing stale trees unless you run a rebuild first.
Rebalance caveats: --rebalance re-sequences leaves with a large temp offset and rebuilds parents; this is disruptive to parent/child hashes and can slow subsequent diffs temporarily. Use it sparingly, ideally in maintenance windows.
XOR vs hash-of-hash: Parent XORs are chosen for speed and incremental updates. Leaf hashes remain cryptographic; XOR parents are for pruning, not integrity on their own. Collisions at parent levels are extremely unlikely to hide a leaf difference because leaves are still compared directly on mismatch paths.
Mtree-specific tuning knobs: max_cpu_ratio influences worker count and pool sizing; batch_size controls how many ranges are compared per DB round-trip in diffs. Higher values increase throughput but raise DB and network load.
Error handling: If splits/merges or parent rebuilds fail (e.g., type issues, missing metadata), update/diff aborts; the remedy is usually to fix the schema/state and rerun, or rebuild the tree when metadata and actual table diverge.

Primary Key Types and the Postgres Type Boundary

ACE hashes and compares rows inside Postgres, but it decides which rows to compare in Go. It reads the block bounds out of the tree, sorts and merges them in the ACE process, then sends them back as parameters of the next query. So every primary key value crosses from one type system into the other. On the Go side it is no longer a Postgres value: it is whatever the driver turned it into.

That conversion loses information in three ways, and ACE has hit all three:

Representation. What the driver returns is not always something it will take back. A uuid comes back as a plain [16]byte, which Go prints as [17 17 ...]. Used as a query parameter, that gives invalid input syntax for type uuid. Any value that ACE reads from a tree and sends back as a bound has to survive this round trip.
Ordering. Postgres cuts the blocks with ORDER BY <pkey>, but ACE merges and sorts the bounds of the mismatched blocks in Go. The two orders agree only when the btree order of the type is also the natural Go order for the decoded value. When they do not agree, some pairs of neighbouring bounds end up the wrong way round and the range condition selects no rows, so those blocks are never compared and the diff under-reports. The loss is partial and depends on the data: measured on PostgreSQL 17 with 9 differing rows, restoring the pre-fix uuid ordering reported 6 of them, and a text key in en_US.utf8 reported 4. A wrong order often only widens a range instead of emptying it, which is why this shows up as quietly missing rows rather than as an error.
Identity. Postgres can treat two values as equal where Go sees two different ones. In numeric, 1.5 and 1.50 are the same value for the database, but the driver returns two different (digits, exponent) pairs. Row hashing already handles this, because it casts through trim_scale(...)::text. Bounds do not go through that cast.

So a Merkle tree only works over a primary key whose values ACE can sort and rebuild correctly outside the database:

Primary key type	Status in `mtree`
`smallint`, `integer`, `bigint`, `real`, `double precision`, `boolean`	Supported
`uuid`, `bytea`	Supported; compared as bytes, like `uuid_cmp` and `byteacmp`
`timestamp`, `timestamptz`, `date`	Supported
`text`, `varchar`, `char`	Supported only under the `C` or `POSIX` collation; see below
`numeric`, `time`, and any type the driver decodes into a struct	Not supported. The tree builds and a clean run still reports a match, but the moment a block mismatches, the row identity cannot be built and the comparison stops with an error
`enum`, `citext`, domains over any of the above, and types the driver has no codec for	Accepted, but the order is not guaranteed; see below

The two halves of that table fail differently, and the difference matters.

A type the driver decodes into a struct -- numeric, time -- has no row identity ACE can build, so as soon as a block mismatches and the rows have to be matched up, the comparison stops with an error. The pair is recorded in incomplete_pairs, TABLES MATCH is not printed, and the command exits non-zero. Nothing is silently dropped, but note what is not covered: a run that finds no mismatching block at all still reports a match, and the bounds that led to that conclusion were ordered by their Go rendering. A clean verdict over such a key is worth no more than the ordering behind it.

A string-like type whose collation Go cannot reproduce -- text outside C, enum, citext -- is the worse case, because identity works fine and only the order is wrong. There is nothing to refuse and nothing to report: the run completes, prints a verdict, and can be missing rows. A warning naming the type is logged once per task when the comparator meets a type it cannot order, but that warning does not fire for these, because Go will happily compare two strings.

That second half is a known gap, not a supported setup, and it is reproducible: tests/integration/mtree_pkey_types_test.go carries a case for it, skipped until the fix lands. A text primary key in any collation other than C sorts differently in the database than byte by byte in Go: under en_US.UTF-8 the database puts 'a' before 'B', while ACE puts 'B' first. How much that costs depends on the keys -- the same collation over hex strings loses nothing, while keys that alternate case lost 5 of 9 differing rows in testing -- so a run that finds differences is not evidence that it found all of them. An enum sorts by enumsortorder and not by its label, but it reaches ACE as a plain string. The same is true for any type the driver has no codec for: it arrives as raw bytes or as text and is compared byte by byte, which need not be the order the type really uses. ACE does not detect any of this today. The proper fix is to sort the bounds in SQL instead of in Go, which removes the whole group of problems at once. Adding more comparison cases in Go only makes more types look supported than they are.

table-diff has none of these problems, because it never sorts or merges block bounds in Go. It stays the fallback for a table whose primary key mtree cannot sort reliably.

Observability and Teardown

Task records: Mtree runs are recorded in ace_tasks.db (table ace_tasks) with context about block size, nodes, and statuses. Check logs for counts of dirty blocks, splits/merges applied, parent rebuilds, and extra-leaf mismatches during diff traversal.
Slot health: Monitor logical slot lag/WAL retention; a bloated slot suggests update hasn’t consumed changes. If the slot is dropped or stale, rebuild (init + build) and recreate the slot/publication entry.
Teardown/reset: Prefer the built-in teardown/teardown-table commands to remove mtree artifacts (mtree table, composite type, metadata, publication entry). Use manual drops only if automation fails, then rebuild with the desired block size and resume CDC.