Optimize chain selection in ChainDB #1223
Labels
Milestone
Comments
edsko
added
consensus
|
Dropping priority to medium, since we could release without this: the amount of extra work is not huge. It would however be good to do. Certainly not required for a testnet. |
|
Note: if we trigger chain selection for a block already on the current chain, this optimization should imply that the path we find is the empty path. |
mrBliss
added a commit
that referenced
this issue
Jun 25, 2020
Fixes #1223. When a block fits onto a fork, we construct the fragment all the way going back to the immutable tip instead of just a `ChainDiff` to the most recent intersection with the current chain. For example, when switching to a fork that requires rolling back 2 blocks, previously, we'd construct a fragment containing `k` headers. Now, we'll construct a `ChainDiff` with rollback = 2 and a fragment of 2 headers. * `VolDB`: introduce `ReversePath` and `computeReversePath` which lazily computes a reverse path through the VolatileDB. By using these paths everywhere, we no longer have to think about looking things up in the VolatileDB. * `VolDB`: let `isReachable` return a `PointChainDiff` instead of a list of hashes going all the way back to the immutable tip. This `PointChainDiff` can later be translated to a `ChainDiff`. * Add property tests for `isReachable`, which helped catch a tricky corner case involving EBBs. * `VolDB`: rewrite `computePath` using `computeReversePath`. * `Fragment.Diff`: promote the internal `mkRollback` to the public `mkDiff` smart constructor, now used by chain selection for forks. * We can now use `RealPoint`s instead of `HeaderHash`s in many functions and types: `IteratorBlockGCed`, `ChainDB.Iterator`s, `VolDB.Path`, some trace events, etc. We don't yet take advantage of the `RealPoint` in the implementation of `ChainDB.Iterator`s.
mrBliss
added a commit
that referenced
this issue
Jun 25, 2020
Fixes #1223. When a block fits onto a fork, we construct the fragment all the way going back to the immutable tip instead of just a `ChainDiff` to the most recent intersection with the current chain. For example, when switching to a fork that requires rolling back 2 blocks, previously, we'd construct a fragment containing `k` headers. Now, we'll construct a `ChainDiff` with rollback = 2 and a fragment of 2 headers. * `VolDB`: introduce `ReversePath` and `computeReversePath` which lazily computes a reverse path through the VolatileDB. By using these paths everywhere, we no longer have to think about looking things up in the VolatileDB. * `VolDB`: let `isReachable` return a `PointChainDiff` instead of a list of hashes going all the way back to the immutable tip. This `PointChainDiff` can later be translated to a `ChainDiff`. * Add property tests for `isReachable`, which helped catch a tricky corner case involving EBBs. * `VolDB`: rewrite `computePath` using `computeReversePath`. * `Fragment.Diff`: promote the internal `mkRollback` to the public `mkDiff` smart constructor, now used by chain selection for forks. * We can now use `RealPoint`s instead of `HeaderHash`s in many functions and types: `IteratorBlockGCed`, `ChainDB.Iterator`s, `VolDB.Path`, some trace events, etc. We don't yet take advantage of the `RealPoint` in the implementation of `ChainDB.Iterator`s.
mrBliss
added a commit
that referenced
this issue
Jun 26, 2020
Fixes #1223. When a block fits onto a fork, we construct the fragment all the way going back to the immutable tip instead of just a `ChainDiff` to the most recent intersection with the current chain. For example, when switching to a fork that requires rolling back 2 blocks, previously, we'd construct a fragment containing `k` headers. Now, we'll construct a `ChainDiff` with rollback = 2 and a fragment of 2 headers. * `VolDB`: introduce `VolatilePath` and `computeVolatilePath` which lazily computes a path through the VolatileDB. By using these paths everywhere, we no longer have to think about looking things up in the VolatileDB. * `VolDB`: let `isReachable` return a `PointChainDiff` instead of a list of hashes going all the way back to the immutable tip. This `PointChainDiff` can later be translated to a `ChainDiff`. * Add property tests for `isReachable`, which helped catch a tricky corner case involving EBBs. * `VolDB`: rewrite `computePath` using `computeVolatilePath`. * `Fragment.Diff`: promote the internal `mkRollback` to the public `new` smart constructor, now used by chain selection for forks. * We can now use `RealPoint`s instead of `HeaderHash`s in many functions and types: `IteratorBlockGCed`, `ChainDB.Iterator`s, `VolDB.Path`, some trace events, etc. We don't yet take advantage of the `RealPoint` in the implementation of `ChainDB.Iterator`s.
mrBliss
added a commit
that referenced
this issue
Jun 26, 2020
Fixes #1223. When a block fits onto a fork, we construct the fragment all the way going back to the immutable tip instead of just a `ChainDiff` to the most recent intersection with the current chain. For example, when switching to a fork that requires rolling back 2 blocks, previously, we'd construct a fragment containing `k` headers. Now, we'll construct a `ChainDiff` with rollback = 2 and a fragment of 2 headers. * `VolDB`: introduce `VolatilePath` and `computeVolatilePath` which lazily computes a path through the VolatileDB. By using these paths everywhere, we no longer have to think about looking things up in the VolatileDB. * `VolDB`: let `isReachable` return a `PointChainDiff` instead of a list of hashes going all the way back to the immutable tip. This `PointChainDiff` can later be translated to a `ChainDiff`. * Add property tests for `isReachable`, which helped catch a tricky corner case involving EBBs. * `VolDB`: rewrite `computePath` using `computeVolatilePath`. * `Fragment.Diff`: promote the internal `mkRollback` to the public `new` smart constructor, now used by chain selection for forks. * We can now use `RealPoint`s instead of `HeaderHash`s in many functions and types: `IteratorBlockGCed`, `ChainDB.Iterator`s, `VolDB.Path`, some trace events, etc. We don't yet take advantage of the `RealPoint` in the implementation of `ChainDB.Iterator`s.
mrBliss
added a commit
that referenced
this issue
Jun 26, 2020
Fixes #1223. When a block fits onto a fork, we construct the fragment all the way going back to the immutable tip instead of just a `ChainDiff` to the most recent intersection with the current chain. For example, when switching to a fork that requires rolling back 2 blocks, previously, we'd construct a fragment containing `k` headers. Now, we'll construct a `ChainDiff` with rollback = 2 and a fragment of 2 headers. * `VolDB`: introduce `VolatilePath` and `computeVolatilePath` which lazily computes a path through the VolatileDB. By using these paths everywhere, we no longer have to think about looking things up in the VolatileDB. * `VolDB`: let `isReachable` return a `PointChainDiff` instead of a list of hashes going all the way back to the immutable tip. This `PointChainDiff` can later be translated to a `ChainDiff`. * Add property tests for `isReachable`, which helped catch a tricky corner case involving EBBs. * `VolDB`: rewrite `computePath` using `computeVolatilePath`. * `Fragment.Diff`: promote the internal `mkRollback` to the public `new` smart constructor, now used by chain selection for forks. * We can now use `RealPoint`s instead of `HeaderHash`s in many functions and types: `IteratorBlockGCed`, `ChainDB.Iterator`s, `VolDB.Path`, some trace events, etc. We don't yet take advantage of the `RealPoint` in the implementation of `ChainDB.Iterator`s.
mrBliss
added a commit
that referenced
this issue
Jun 29, 2020
Fixes #1223. When a block fits onto a fork, we construct the fragment all the way going back to the immutable tip instead of just a `ChainDiff` to the most recent intersection with the current chain. For example, when switching to a fork that requires rolling back 2 blocks, previously, we'd construct a fragment containing `k` headers. Now, we'll construct a `ChainDiff` with rollback = 2 and a fragment of 2 headers. * `VolDB`: introduce `ReversePath` and `computeReversePath` which lazily computes a path through the VolatileDB. By using these paths everywhere, we no longer have to think about looking things up in the VolatileDB. * `VolDB`: let `isReachable` return a `ChainDiff` of `HeaderFields` instead of a list of hashes going all the way back to the immutable tip. This `ChainDiff` of `HeaderFields` can later be translated to a `ChainDiff` of `Header`s. * `VolDB`: add `extendWithSuccessors` that will extend a `ChainDiff` of `HeaderFields` with its successors, using `candidates`. * Add property tests for `isReachable`, which helped catch a tricky corner case involving EBBs. * `VolDB`: rewrite `computePath` using `computeReversePath`. * We can now use `RealPoint`s instead of `HeaderHash`s in many functions and types: `IteratorBlockGCed`, `ChainDB.Iterator`s, `VolDB.Path`, some trace events, etc. We don't yet take advantage of the `RealPoint` in the implementation of `ChainDB.Iterator`s.
mrBliss
added a commit
that referenced
this issue
Jun 29, 2020
Fixes #1223. When a block fits onto a fork, we construct the fragment all the way going back to the immutable tip instead of just a `ChainDiff` to the most recent intersection with the current chain. For example, when switching to a fork that requires rolling back 2 blocks, previously, we'd construct a fragment containing `k` headers. Now, we'll construct a `ChainDiff` with rollback = 2 and a fragment of 2 headers. * `VolDB`: introduce `ReversePath` and `computeReversePath` which lazily computes a path through the VolatileDB. By using these paths everywhere, we no longer have to think about looking things up in the VolatileDB. * `VolDB`: let `isReachable` return a `ChainDiff` of `HeaderFields` instead of a list of hashes going all the way back to the immutable tip. This `ChainDiff` of `HeaderFields` can later be translated to a `ChainDiff` of `Header`s. * `VolDB`: add `extendWithSuccessors` that will extend a `ChainDiff` of `HeaderFields` with its successors, using `candidates`. * Add property tests for `isReachable`, which helped catch a tricky corner case involving EBBs. * `VolDB`: rewrite `computePath` using `computeReversePath`. * We can now use `RealPoint`s instead of `HeaderHash`s in many functions and types: `IteratorBlockGCed`, `ChainDB.Iterator`s, `VolDB.Path`, some trace events, etc. We don't yet take advantage of the `RealPoint` in the implementation of `ChainDB.Iterator`s.
mrBliss
added a commit
that referenced
this issue
Jun 29, 2020
Fixes #1223. When a block fits onto a fork, we construct the fragment all the way going back to the immutable tip instead of just a `ChainDiff` to the most recent intersection with the current chain. For example, when switching to a fork that requires rolling back 2 blocks, previously, we'd construct a fragment containing `k` headers. Now, we'll construct a `ChainDiff` with rollback = 2 and a fragment of 2 headers. * `VolDB`: introduce `ReversePath` and `computeReversePath` which lazily computes a path through the VolatileDB. By using these paths everywhere, we no longer have to think about looking things up in the VolatileDB. * `VolDB`: let `isReachable` return a `ChainDiff` of `HeaderFields` instead of a list of hashes going all the way back to the immutable tip. This `ChainDiff` of `HeaderFields` can later be translated to a `ChainDiff` of `Header`s. * `VolDB`: add `extendWithSuccessors` that will extend a `ChainDiff` of `HeaderFields` with its successors, using `candidates`. * Add property tests for `isReachable`, which helped catch a tricky corner case involving EBBs. * `VolDB`: rewrite `computePath` using `computeReversePath`. * We can now use `RealPoint`s instead of `HeaderHash`s in many functions and types: `IteratorBlockGCed`, `ChainDB.Iterator`s, `VolDB.Path`, some trace events, etc. We don't yet take advantage of the `RealPoint` in the implementation of `ChainDB.Iterator`s.
iohk-bors bot
added a commit
that referenced
this issue
Jun 29, 2020
2323: ChainDB: optimise chain selection for forks r=mrBliss a=mrBliss Fixes #1223. When a block fits onto a fork, we construct the fragment all the way going back to the immutable tip instead of just a `ChainDiff` to the most recent intersection with the current chain. For example, when switching to a fork that requires rolling back 2 blocks, previously, we'd construct a fragment containing `k` headers. Now, we'll construct a `ChainDiff` with rollback = 2 and a fragment of 2 headers. * `VolDB`: introduce `ReversePath` and `computeReversePath` which lazily computes a path through the VolatileDB. By using these paths everywhere, we no longer have to think about looking things up in the VolatileDB. * `VolDB`: let `isReachable` return a `ChainDiff` of `HeaderFields` instead of a list of hashes going all the way back to the immutable tip. This `ChainDiff` of `HeaderFields` can later be translated to a `ChainDiff` of `Header`s. * `VolDB`: add `extendWithSuccessors` that will extend a `ChainDiff` of `HeaderFields` with its successors, using `candidates`. * Add property tests for `isReachable`, which helped catch a tricky corner case involving EBBs. * `VolDB`: rewrite `computePath` using `computeReversePath`. * We can now use `RealPoint`s instead of `HeaderHash`s in many functions and types: `IteratorBlockGCed`, `ChainDB.Iterator`s, `VolDB.Path`, some trace events, etc. We don't yet take advantage of the `RealPoint` in the implementation of `ChainDB.Iterator`s. Co-authored-by: Thomas Winant <[email protected]>
iohk-bors bot
added a commit
that referenced
this issue
Jun 30, 2020
2323: ChainDB: optimise chain selection for forks r=mrBliss a=mrBliss Fixes #1223. When a block fits onto a fork, we construct the fragment all the way going back to the immutable tip instead of just a `ChainDiff` to the most recent intersection with the current chain. For example, when switching to a fork that requires rolling back 2 blocks, previously, we'd construct a fragment containing `k` headers. Now, we'll construct a `ChainDiff` with rollback = 2 and a fragment of 2 headers. * `VolDB`: introduce `ReversePath` and `computeReversePath` which lazily computes a path through the VolatileDB. By using these paths everywhere, we no longer have to think about looking things up in the VolatileDB. * `VolDB`: let `isReachable` return a `ChainDiff` of `HeaderFields` instead of a list of hashes going all the way back to the immutable tip. This `ChainDiff` of `HeaderFields` can later be translated to a `ChainDiff` of `Header`s. * `VolDB`: add `extendWithSuccessors` that will extend a `ChainDiff` of `HeaderFields` with its successors, using `candidates`. * Add property tests for `isReachable`, which helped catch a tricky corner case involving EBBs. * `VolDB`: rewrite `computePath` using `computeReversePath`. * We can now use `RealPoint`s instead of `HeaderHash`s in many functions and types: `IteratorBlockGCed`, `ChainDB.Iterator`s, `VolDB.Path`, some trace events, etc. We don't yet take advantage of the `RealPoint` in the implementation of `ChainDB.Iterator`s. Co-authored-by: Thomas Winant <[email protected]>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The chain selection code in the chain DB follows the specification very closely, but of course the specification is not concerned with performance, only efficiency. Chain selection works by finding a set of candidates starting at a particular point; if a new block comes in, and that block fits onto our current chain, the set of candidates is computed from current tip of the chain. However, if that block does not find onto our chain, we construct a prefix path backwards from that block to the tip of the immutable DB, find all candidates starting at the new block, and then construct the set of candidates by prepending that prefix path to those candidates.
We then construct a set of "candidate suffixes", by computing an intersection of that chain with our current chain, and then using that to compute a rollback (in terms of a number of blocks) and a set of new headers. However, of course, the rollback will in fact be the same for all of those candidates, and there was no need to recompute the intersection point at all, because we knew that as soon as we computed the prefix back from the new header to our current chain.
This means that the implementation is correct, but is doing unnecessary work, which will become important once chains are more frequent. Therefore marking this as high priority, but only for shelley.
The text was updated successfully, but these errors were encountered: