Performance fix propositions for CNB in case of #6312 merging

NicolasDorier commented at 1:14 am on December 6, 2015: contributor

I’m just moving a discussion of #6312. Basically #6898 removed CCoinView queries in CNB for performance reason. But #6312 need more information to check LockTime validty which require CCoinView queries, nullifying performance improvement of .#6898 .

This issue is for brainstorming solutions without polluting #6312 .

NicolasDorier referenced this in commit 4a010348d8 on Dec 6, 2015

NicolasDorier referenced this in commit b13f47535c on Dec 6, 2015

NicolasDorier commented at 6:03 am on December 6, 2015: contributor

Created https://github.com/NicolasDorier/bitcoin/commit/b13f47535cc24304176dfb9cd3f12511cf095055 to demonstrate a way to CNB perf issue without changing consensus code of CSV. It does not compile yet, but explain the idea.

However, I’m surprised that there is a way where finality is violated, because reorg actually check the locktime already : https://github.com/NicolasDorier/bitcoin/commit/b13f47535cc24304176dfb9cd3f12511cf095055#diff-ca74c4b28865382863b8fe7633a85cd6L507

sdaftuar commented at 8:37 pm on December 7, 2015: member

I’ve coded up an alternate idea (as @morcos mentioned in #6312) for making removeForReorg fast, which in turn also makes CreateNewBlock fast, even right after a reorg. This approach is to cache the prevHeights for all inputs that are using a sequence lock, and whenever we have a reorg that disconnects a block that is older than the maximum height of a previous height, we redo the prevHeights calculation. Otherwise we call CheckLockTime and instruct it to use the cached values of prevHeights.

To optimize this so that we don’t needlessly recalculate prevHeights, I modified LockTime so that it will indicate to the caller which inputs are sequence-locked. Only when a sequence-locked input height is above the height of a block disconnected in a reorg do we recalculate all the prevHeights.

Code is here: https://github.com/maaku/bitcoin/compare/sequencenumbers...sdaftuar:6312-modifications

I haven’t tested it yet, I plan to do so as part of my testing of #6312.

morcos commented at 9:04 pm on December 7, 2015: member

OK I have two approaches now

The first approach mentioned in #6312 is to make the minimal changes to the existing code that has some review necessary to extract information necessary to efficiently maintain mempool consistency during a reorg. https://github.com/maaku/bitcoin/compare/sequencenumbers...morcos:refactorb

The second approach is change the implementation BIP 68 to instead add another function SequenceLocks and use that in addition to IsFinalTx rather than attempting to combine them both into one function. That approach is seen in #7184.
CreateNewBlock is untouched and remains fast in #7184, but reorgs require recalculating all sequence locks. This can easily be changed by applying the additional commits from the refactorb branch above.

NicolasDorier commented at 3:10 am on December 8, 2015: contributor

Can someone explain me why the mempool finality can become inconsistent since CheckLockTime is called in removeForReorg ? Also, what is the downside of my approach ? it seems way easier to just check locktime invalidation in CNB.

morcos commented at 3:31 am on December 8, 2015: member

@NicolasDorier After MTP locks in, it won’t be possible for the mempool to contain inconsistent txs. None of my branches do anything in CNB. But calling CheckLockTime (or CheckSequenceLocks) on the whole mempool during a reorg without caching either the vector like @sdaftuar does or the lock heights like I do is incredibly expensive and blows out your cache.

Checking locktime in CNB is a pretty good approach, but we’ll have forever limited ourselves from optimizing it if we don’t get the information we’d need from the calculation of the sequence locks initially. In the worse case you might have to recalculate every single sequence lock in CNB after a reorg. The way its constructed in your branch you only need to do it for the first block worth of txs, but that puts a constraint on the types of block assembly algorithms you might use in CNB.

NicolasDorier commented at 4:16 am on December 8, 2015: contributor

Understood, I’m not convinced that the complexity added is worth the performance hit. A reorg is a rare occurence. @sdaftuar, your condition for reusing cached height is wrong. There is possibility that this returns false, but still need a refresh. I think there is a simpler thing to do : Storing only the block hash of the youngest input in the mempool. If this block hash is still in the main chain during reorg, then no need to CheckSequenceLock for the entry. I’ll try to do something along these lines by following your example.

laanwj added the label Validation on Dec 8, 2015

NicolasDorier commented at 2:22 pm on December 8, 2015: contributor

Actually, in the plane a simpler idea came in my mind : Saving the Block Id of the tip during insertion in mempool in AcceptMempool.

During reorg, if the old tip is still in the current chain do nothing, else, recalculate LockTime. For performance reason only check if old tip is in the 10 last block from the new tip. (no need to check all headers)

This address all point, without touching current code.

I’m working on it.

EDIT : https://github.com/NicolasDorier/bitcoin/compare/9e8c7be9bc94...8670ce84fd01 might be good idea to combine with #7184. EDIT2 : my commit does not work, test failing, debugging…

jtimon commented at 8:42 pm on December 8, 2015: contributor

First of all, thank you for miving this out of #6312. @NicolasDorier approaches don’t seem to require to touch the consensus code further and are thefore less disruptive to consensus encapsulation and safer at the same time. With similar performance gains (although we still lack benchmarks for all the approaches being discussed), I will always prefer the change that is less disruptive to #6312 and consensus encapsulation.

morcos commented at 9:26 pm on December 8, 2015: member

Please see #7187 for my suggestion on how to keep the mempool consistent efficiently.
If people agree that BIP 68 should assume MTP for its comparison, I will make that change in #7184 and rebase #7187 on that.

btcdrak commented at 9:41 pm on December 8, 2015: contributor

I already commented on the PR and in IRC but recording it here: I think assuming MTP is not only reasonable but sane, because we’re planning to deploy BIP68 with BIP113.

jtimon commented at 9:47 pm on December 8, 2015: contributor

@btcdrak agreed. But as said in #7187 it would be much simpler to review the differences if all the proposals build on top of #6312 (we can always squash before merging if the concern is a cleaner history),

jtimon commented at 9:49 pm on December 8, 2015: contributor

Also, if we’re merging the changes together, is it really necessary to change the name of LockTime()?

NicolasDorier commented at 7:54 am on December 9, 2015: contributor

I just made PR #7190 . It builds upon #6312 and fix performance concerns in CNB & removeForReorg. It keeps CheckLockTime and LockTime functions unchanged.

morcos commented at 10:41 pm on January 14, 2016: member

To summarize the approach we are proceeding with. #7184 provides an implementation of sequence locks with median time past enforced already. It also includes code to keep the mempool consistent in that all txs are sequence lock final if they are int he mempool even after reorgs. #7187 includes code to make those reorgs fast. Neither pull touches the mining code because the mining code can rely on the mempool for sequence lock checks. Once MTP is enforced we could also remove the IsFinalTx checks from the mempool and enforce mempool consistency, but those are very efficient anyway.

NicolasDorier commented at 3:20 am on January 15, 2016: contributor

Do I close this issue ? I think we should go on your PR.

btcdrak commented at 8:36 am on January 15, 2016: contributor

Yes, close this.

NicolasDorier closed this on Jan 15, 2016

MarcoFalke locked this on Sep 8, 2021

Performance fix propositions for CNB in case of #6312 merging #7176