Use Merkle trees in ACE #253
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
* Also minimise critical section in compare_checksums
* Merges happen only when --rebalance=true is passed
mmols
requested changes
Jun 12, 2025
* Group mtree cmds into a sub-cmd * Treat each of table-diff, -repair, etc. as a top-level sub-cmd
* Rename 'override-block-size' to 'skip-block-size-check' to free up -o * Add back 'block_rows' as an alias of 'block_size' * Add back 'behavior' in rerun and mark as deprecated * Improve merkle tree help text
mmols
approved these changes
Jun 25, 2025
mmols
added a commit
that referenced
this pull request
Jun 26, 2025
* Added build-mtree to build a merkle tree for a table * Fix node_list population * Also minimise critical section in compare_checksums * Use same block ranges on all nodes * Breakthrough: extending a merkle tree on new inserts works * Sweeping optimisations in table-diff * Use an optimised sql query instead of get_pkey_offsets * Fix pkey offsets query * Added feature to merge blocks on large deletes * Handle blocks splits and merges inside ACE * Fix some rebalancing bugs * Integrate merkle trees into ACE cli * Update mtree only splits blocks * Merges happen only when --rebalance=true is passed * Adding mtree diff * First version of mtree diff ready * Add progress bar for splits and merges * Use always trigger for tracking dirty blocks * Update cryptography to address CVE * No longer using OrderedSet for comparisons * Handle mismatching tree levels * Use generic trigger functions * Initialise mtree objects once per DB node * More cleanup * Tweaks to get all base tests to pass A3D4 * Use SQL composables; fix rebalance issues * Unify pkey offset computations * Add support for specifying a ranges file * Remove node len check for mtree build * Update leaf hash during mtree update * Temp fix for range boundary issue * Address boundary issues using a lookup table * Use prepared statements * Sunset batches option and async rerun * Add block boundary and repset-diff tests * Remove explicit stmt.close() * Add support for composite keys; use stmt triggers * SQL cleanup * Add mtree init, teardown; fix block size usage * Added merkle tree tests * Use mogrify during repairs * Prior use of executemany would internally call execute multiple times, thereby making repairs slow because of statement triggers from mtrees * Fix write-ranges to use str by default * Add support for non-numeric datatypes in tracking triggers * Fix conn establishment in cleanup * Address codacy issues * Addressed more codacy issues * String literal fix * Codacy fix #4 * Codacy fix #5 * Use nosemgrep * More nosemgreps * Add mtree cli helptext * Fix metadata task type * Add metadata tracking for mtree modules * Move error codes out of config file * Use a separate consts file * Revamp ACE CLI invocation * Group mtree cmds into a sub-cmd * Treat each of table-diff, -repair, etc. as a top-level sub-cmd * Update tests * Fix table names in mtree test * Minor fixes * Help texts mostly fixed * fix fire.py helptext generation for mtree submodule * generate help for ace mtree submodule * Backward compatibility fixes * Rename 'override-block-size' to 'skip-block-size-check' to free up -o * Add back 'block_rows' as an alias of 'block_size' * Add back 'behavior' in rerun and mark as deprecated * Improve merkle tree help text * Fix tests * update generated helptext * Ensure pgcrypto is present * Fix spock diff --------- Co-authored-by: Matthew Mols <matt@pgedge.com>
mmols
added a commit
that referenced
this pull request
Jun 27, 2025
* Added build-mtree to build a merkle tree for a table * Fix node_list population * Also minimise critical section in compare_checksums * Use same block ranges on all nodes * Breakthrough: extending a merkle tree on new inserts works * Sweeping optimisations in table-diff * Use an optimised sql query instead of get_pkey_offsets * Fix pkey offsets query * Added feature to merge blocks on large deletes * Handle blocks splits and merges inside ACE * Fix some rebalancing bugs * Integrate merkle trees into ACE cli * Update mtree only splits blocks * Merges happen only when --rebalance=true is passed * Adding mtree diff * First version of mtree diff ready * Add progress bar for splits and merges * Use always trigger for tracking dirty blocks * Update cryptography to address CVE * No longer using OrderedSet for comparisons * Handle mismatching tree levels * Use generic trigger functions * Initialise mtree objects once per DB node * More cleanup * Tweaks to get all base tests to pass * Use SQL composables; fix rebalance issues * Unify pkey offset computations * Add support for specifying a ranges file * Remove node len check for mtree build * Update leaf hash during mtree update * Temp fix for range boundary issue * Address boundary issues using a lookup table * Use prepared statements * Sunset batches option and async rerun * Add block boundary and repset-diff tests * Remove explicit stmt.close() * Add support for composite keys; use stmt triggers * SQL cleanup * Add mtree init, teardown; fix block size usage * Added merkle tree tests * Use mogrify during repairs * Prior use of executemany would internally call execute multiple times, thereby making repairs slow because of statement triggers from mtrees * Fix write-ranges to use str by default * Add support for non-numeric datatypes in tracking triggers * Fix conn establishment in cleanup * Address codacy issues * Addressed more codacy issues * String literal fix * Codacy fix #4 * Codacy fix #5 * Use nosemgrep * More nosemgreps * Add mtree cli helptext * Fix metadata task type * Add metadata tracking for mtree modules * Move error codes out of config file * Use a separate consts file * Revamp ACE CLI invocation * Group mtree cmds into a sub-cmd * Treat each of table-diff, -repair, etc. as a top-level sub-cmd * Update tests * Fix table names in mtree test * Minor fixes * Help texts mostly fixed * fix fire.py helptext generation for mtree submodule * generate help for ace mtree submodule * Backward compatibility fixes * Rename 'override-block-size' to 'skip-block-size-check' to free up -o * Add back 'block_rows' as an alias of 'block_size' * Add back 'behavior' in rerun and mark as deprecated * Improve merkle tree help text * Fix tests * update generated helptext * Ensure pgcrypto is present * Fix spock diff --------- Co-authored-by: Matthew Mols <matt@pgedge.com>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This PR introduces the use of Merkle trees in table-diff with
mtree-diff. Furthermore, it also adds several optimisations to regulartable-diffto enable it to run on medium-sized tables. To use this feature:Initialise the Merkle tree objects using:
--analyse=truecan be very time-consuming depending on the size of the table. It's recommended to manually perform anANALYZE <table>in Postgres and avoid using this flag.Diff can be performed using:
Performing an
mtree-diffautomatically updates the Merkle tree before performing the diff. It's also possible to separately update the trees using:--rebalance=truewill perform splits and merges of blocks based on changes in the underlying keyspace. It's not necessary to perform rebalancing unless it's essential. The default update operation inmtree-difftakes care of block splits and updates but defers merges. This is to preserve parent-child relationships and avoid costly recursions due to merged blocks.