Page MenuHomePhabricator

[avalanche] Maintain a radix tree of the proofs

Authored by Fabien on May 11 2022, 20:56.


Group Reviewers
Restricted Project
rABC87b4609c7efe: [avalanche] Maintain a radix tree of the proofs

This will be used to send the short proof ids of our proofs to our peers. The radix tree is copy-on-write, which makes it possible to store a copy of the tree in the remote node data, so even if the proof set keep evolving we can retrieve the missing proofs based on an index snapshoted at the time of the copy, while only duplicating the subset of the tree that has changed.

Test Plan
ninja check-avalanche

Diff Detail

rABC Bitcoin ABC
Lint Not Applicable
Tests Not Applicable

Event Timeline

Fabien requested review of this revision.May 11 2022, 20:56
Fabien retitled this revision from [avalanche] Maintain a radix tree of the proof ids to [avalanche] Maintain a radix tree of the proofs.May 11 2022, 20:59
sdulfari requested changes to this revision.May 12 2022, 00:34
sdulfari added a subscriber: sdulfari.

Generally true throughout this diff: the naming is too dependent on the underlying proofs database being a radix tree. A simple example at the peer manager interface is getProofRadixTree(). Does the caller care that the DB is a radix tree? If we change to some other COW DB, we'll end up with a lot of renaming to do.

319 ↗(On Diff #33486)

Is synchronize necessary on insertions?

1654 ↗(On Diff #33486)

In addition to counting the leaves, is it worth keeping a list of proofs you built and ensuring each leaf can be found in that list?

1698 ↗(On Diff #33486)

The above comment is even more relevant here.

This revision now requires changes to proceed.May 12 2022, 00:34

Rename to shareableProofs and getShareableProofsSnapshot(), because these proofs are intended to be shared with our peers.
Update the test to check against a list of expeced proofs rather than relying on the count.

319 ↗(On Diff #33486)

The insertion might have copied part of the tree and the previous content can be released after readers are done

Make the ProofElement public

deadalnix requested changes to this revision.May 12 2022, 18:52
deadalnix added a subscriber: deadalnix.
deadalnix added inline comments.
319 ↗(On Diff #33494)

It is not needed. If it is needed, it is almost certainly a bug. Did ASAN yell at you before you put these barriers in place?

513 ↗(On Diff #33494)


699 ↗(On Diff #33494)

You probably want a way to early exit the iteration, no?

162 ↗(On Diff #33494)

Something doesn't make sense. The proof are duplicated between here and the various pools, no?

That makes no sense, you want a tree of proofs, not a tree of gizmos that copy the proofs.

If the main problem is that you want a Uint256KeyWrapper (which is a pretty bad name, what is this wrapper, why would I want to wrap my Uint256? What does this do?), then just pass an adapter to the radix tree to tell it how to get the id.

376 ↗(On Diff #33494)

You probably don't want to eagerly copy and leave that to the caller, considering there is a synchronize operation involved.

This revision now requires changes to proceed.May 12 2022, 18:52
162 ↗(On Diff #33494)

See D11456

160 ↗(On Diff #33525)

This needs to move or get abstracted somehow so we don't have to know the underlying of the radix tree everywhere

Move the adapter to its own header, rebase

deadalnix requested changes to this revision.May 19 2022, 17:36
deadalnix added inline comments.
365–371 ↗(On Diff #33550)

I don't see how any of this makes any sense. It's not even wrong.

This revision now requires changes to proceed.May 19 2022, 17:36
Fabien planned changes to this revision.May 23 2022, 11:08

Return a const reference to the tree

deadalnix requested changes to this revision.May 24 2022, 14:33
deadalnix added inline comments.
162 ↗(On Diff #33494)

Isn't ProofRef and RCUPtr now? You don't need this.

1 ↗(On Diff #33684)


This revision now requires changes to proceed.May 24 2022, 14:33
162 ↗(On Diff #33494)

Sorry, I missed it during the rebase

1 ↗(On Diff #33684)

Good catch !

162 ↗(On Diff #33494)

Something is wrong because my local branch doesn't have this code anymore....

162 ↗(On Diff #33494)

You commented on a previous revision of the diff

Some includes need cleanup

16 ↗(On Diff #33686)

This include is no longer needed

9 ↗(On Diff #33686)

Is this include necessary?

This revision is now accepted and ready to land.May 25 2022, 16:30