Improve DisconnectTip performance #9208

sdaftuar · 2016-11-23T10:42:21Z

During a reorg, we currently try to add transactions from each disconnected block back to the mempool, even though we are likely to find many of those transactions in the blocks that get connected.

This PR stores those transactions in a separate "disconnect pool" for later processing. This has a few side effects:

There should be many fewer transactions to re-add to the mempool, assuming the reorg is benign and most transactions appear on both forks, which means we'll do less work.
When we do add things to the mempool, we'll do it in one attempt rather than separately for each disconnected block, so mempool chain limits will be calculated and applied differently for reorgs than before. Overall it should be much more efficient, because we will have fewer calls chasing long chains in the mempool to keep track of ancestor and descendant state (both because we will call UpdateTransactionsFromBlock on a smaller set of transactions overall, and because the descendant caching it does isn't reused across calls, so it's more efficient to call UpdateTransactionsFromBlock once for all of a reorg's transactions than multiple times).
Storing the transactions in this new disconnect pool means we use more memory during a reorg. I've added a bound on how much memory can be used, and if we would exceed it we just try to keep the oldest transactions that are disconnected (the idea being that it's more important to ensure that older transactions that are reorged out have an opportunity to be re-mined, compared with newer ones). This could probably be improved in the future, since in such a (rare) scenario, we would probably want to throw out our current mempool in favor of being able to hold more older transactions, or we might want to re-read those transactions off disk to try to pick up everything that is now unconfirmed. But for now I made the memory bound large enough that this shouldn't practically occur.

sdaftuar · 2016-11-29T02:05:12Z

I just realized there's a potential issue here with the callbacks for conflicted transactions; in the case where a disconnected block transaction ends up conflicting with some tx in a block on the reorg, the call to ATMP will fail (because some input is spent) but not be reported via SyncTransaction() as a conflicted transaction.

EDIT: After some discussion with @morcos I think there's not an issue here. Mempool conflict tracking in general is basically just best-efforts and, in the case of reorgs, dependent on mempool policy already.

sdaftuar · 2017-01-04T21:05:25Z

Rebased, and removed WIP tag as this is now ready for review.

dcousens · 2017-01-04T21:48:30Z

concept ACK, will review

gmaxwell · 2017-01-08T09:08:55Z

Needs rebase. utACK.

sdaftuar · 2017-01-08T15:13:24Z

Rebased

ryanofsky · 2017-02-28T22:33:30Z

utACK 37a90f1

PR makes sense, and nothing has changed except a few comments since my last review (for 4d70f47a94cc739e92f7d3f8f4f7b11cf7457ca9).

One thing I don't understand is why the pruning test needs to change when it sounds like you are saying the disconnect pool memory bound is large enough that losing transactions "shouldn't practically occur." Are you just updating the pruning test as a precaution, or are changes there needed because the chain it creates is unusual?

Also this PR has merge conflicts, but they are very minor. The validation.cpp conflict can be fixed by updating AcceptToMemoryPool arguments which changed in edded80 (#9499).

dcousens

utACK 37a90f1

sdaftuar · 2017-03-01T18:34:33Z

Rebased.

@ryanofsky The changes to pruning.py are because:

Policy limits get applied differently than before; we used to ignore some of the chain limits when adding transactions back to the mempool during a reorg (because we wouldn't look for in-mempool descendants until the end).
The pruning test is trying to build really big blocks in a number of places, to make the chain big enough to be pruned, and in particular in a few places it relies on the mempool being populated with disconnected transactions after a reorg (so changes to policy that would prevent that are problematic for the test).

So I mitigated this in part by increasing the chain limits and in part by trying to keep the mempool somewhat populated with a node's wallet transactions at a couple relevant places in the test.

[I actually briefly thought that because we now save the mempool in between restarts, we may not need the resendwallettransactions() calls I added (which I use to populate the mempool somewhat in a couple places), but I tested locally that removing them results in test failure (plausibly because the mined blocks aren't big enough, which I think is due to the reorg behavior change). I do think this test needs to be overhauled now that many of the assumptions around mempool behavior have changed, but I think we should do that in another PR.]

sdaftuar · 2017-03-07T19:38:41Z

Rebased after #9602.

ryanofsky

utACK c8d4c5f if the MemPoolRemovalReason::REORG argument is added back.

Confirmed no other code changes since the previous rebase.

ryanofsky · 2017-03-08T18:15:48Z

src/validation.cpp

+        if ((*it)->IsCoinBase() || !AcceptToMemoryPool(mempool, stateDummy, *it, false, NULL, NULL, true)) {
+            // If the transaction doesn't make it in to the mempool, remove any
+            // transactions that depend on it (which would now be orphans).
+            mempool.removeRecursive(**it);


In commit "Store disconnected block transactions outside mempool during reorg":

It looks like the new MemPoolRemovalReason::REORG argument for removeRecursive got dropped during the rebase. (Shame that we don't a have test that would catch this, and that the argument is optional to begin with.)

Thanks for catching this! Fixed.

I don't see MemPoolRemovalReason::REORG anywhere?

sdaftuar · 2017-03-11T02:27:40Z

Rebased again to pick up the pruning.py fix from #9972

sipa · 2017-03-12T04:53:29Z

src/txmempool.h

 struct mempoolentry_txid
 {
    typedef uint256 result_type;
    result_type operator() (const CTxMemPoolEntry &entry) const
    {
        return entry.GetTx().GetHash();
    }
+
+    result_type operator() (CTransactionRef tx) const


Pass the CTransactionRef by reference? That will avoid an atomic inc/dec when copying/destroing the CTransactionRef.

sipa · 2017-03-12T05:13:35Z

src/txmempool.h

+        return memusage::MallocUsage(sizeof(CTransactionRef) + 6 * sizeof(void*)) * queuedTx.size() + cachedInnerUsage;
+    }
+
+    void addTransaction(CTransactionRef tx)


const CTransactionRef& here as well, or queuedTx.insert(std::move(tx)) below.

sipa · 2017-03-12T06:24:26Z

src/validation.cpp

+        if ((*it)->IsCoinBase() || !AcceptToMemoryPool(mempool, stateDummy, *it, false, NULL, NULL, true)) {
+            // If the transaction doesn't make it in to the mempool, remove any
+            // transactions that depend on it (which would now be orphans).
+            mempool.removeRecursive(**it);


I don't see MemPoolRemovalReason::REORG anywhere?

sdaftuar · 2017-03-13T11:03:42Z

@sipa Thanks for reviewing (yikes, I think I must have done my second rebase on Friday using an older branch). All the comments should be addressed in the last two fixup commits; let me know if I should go ahead and squash.

morcos · 2017-03-13T15:25:53Z

src/validation.cpp

@@ -2402,6 +2444,10 @@ static bool ActivateBestChainStep(CValidationState& state, const CChainParams& c
        }
    }

+    // If any blocks were disconnected, disconnectpool may be non empty.  Add
+    // any disconnected transactions back to the mempool.
+    ReacceptToMemoryPool(disconnectpool);


nit: Any reason to put ReacceptToMemoryPool here and not under if (fBlocksDisconnected)?
It might make the logic slightly clearer.

morcos · 2017-03-13T15:27:42Z

fast review utACK

TheBlueMatt

Strong concept ACK

TheBlueMatt · 2017-02-28T19:31:53Z

src/txmempool.h

+        for (auto const &tx : vtx) {
+            auto it = queuedTx.find(tx->GetHash());
+            if (it != queuedTx.end()) {
+                cachedInnerUsage -= RecursiveDynamicUsage(*it);


DRY: Maybe use removeEntry here?

I'm going to leave this, since removeEntry takes an iterator into a different multi_index index, and I'd rather removeForBlock be as fast as possible.

TheBlueMatt · 2017-03-13T15:46:49Z

src/validation.cpp

    while (chainActive.Tip() && chainActive.Tip() != pindexFork) {
-        if (!DisconnectTip(state, chainparams))
+        if (!DisconnectTip(state, chainparams, disconnectpool)) {
+            // The mempool will be inconsistent, but we're about to shutdown


I dont think this is always true. Callers dont always enforce this (eg ActivateBestChains in net_processing, PreciousBlock from RPC, etc,e tc) and callees dont either (eg DisconnectBlock's UndoReadFromDisk doesnt appear to generate an AbortNode). These might actually also be bugs, but I think you're introducing a stronger assumption than previously here.

Fixed. I do think that a failure in DisconnectTip() should always cause shutdown, as we can no longer be sure we're in consensus, but no need to worry about that here.

TheBlueMatt · 2017-03-13T16:10:48Z

src/validation.cpp

@@ -3697,7 +3751,9 @@ bool RewindBlockIndex(const CChainParams& params)
            // of the blockchain).
            break;
        }
-        if (!DisconnectTip(state, params, true)) {
+        DisconnectedBlockTransactions dummypool;
+        // fBare=true means nothing will actually be added to dummypool


Hmm, thats a super confusing API now....maybe either pass in a pointer to a DisconnectedBlockTransactions as both fBare and the pool?

TheBlueMatt · 2017-03-13T16:11:28Z

src/validation.h

@@ -69,6 +69,8 @@ static const unsigned int DEFAULT_DESCENDANT_LIMIT = 25;
 static const unsigned int DEFAULT_DESCENDANT_SIZE_LIMIT = 101;
 /** Default for -mempoolexpiry, expiration time for mempool transactions in hours */
 static const unsigned int DEFAULT_MEMPOOL_EXPIRY = 336;
+/** Maximum kilobytes for transactions to store for processing during reorg */
+static const unsigned int MAX_DISCONNECTED_TX_POOL_SIZE = 75000;


nit: Yeesh, isnt that a bit high? Maybe like 10MB - if we reorg something larger than 2/3 blocks throwing away tons of txn is fine by me.

Dropping it to 20 (segwit blocks can be bigger).

dcousens · 2017-03-24T07:05:04Z

Needs rebase?

gmaxwell

tested ACK (I previously utACKed, I know longer remember the code but I've used it a bunch and beat on it a bit)

TheBlueMatt · 2017-05-29T21:26:26Z

re-utACK c1235e3

morcos · 2017-05-30T15:20:09Z

re-utACK c1235e3

c1235e3 Add RecursiveDynamicUsage overload for std::shared_ptr (Russell Yanofsky) 71f1903 Store disconnected block transactions outside mempool during reorg (Suhas Daftuar) 9decd64 [qa] Relax assumptions on mempool behavior during reorg (Suhas Daftuar) Tree-SHA512: c160ad853a5cd060d0307af7606a0c77907497ed7033c9599b95e73d83f68fdfcd4214bd8a83db1c5b7a58022722b9de1ed2e6ea2e02f38a7b6c717f079dd0c6

>>> adapts bitcoin#9208 Rather than re-add disconnected block transactions back to the mempool immediately, store them in a separate disconnectpool for later processing, because we expect most such transactions to reappear in the chain that is still to be connected (and thus we can avoid the work of reprocessing those transactions through the mempool altogether).

…ring reorg 2ae953a Store disconnected block transactions outside mempool during reorg (random-zebra) Pull request description: Extracted from #2267. This backports bitcoin#9208. As highlighted by zcash/zcash#2951, this "performance improvement" actually includes a fix for the following bug: > Currently, AcceptToMemoryPool is called inside DisconnectTip after the block has been disconnected, but before chainActive has been updated. This means that height-dependent consensus rules are checked assuming the height is one greater than it actually is, which is a problem when disconnecting the last block before a network upgrade (e.g. during a reorg across the upgrade boundary). This has additional consequences with special transactions (that's why it was discovered in #2267), as, during a reorg, `ProUp*` transactions, included in the block, might not be resurrected in the mempool, due to the inconsistent state of chainActive. ACKs for top commit: furszy: re-ACK 2ae953a. Fuzzbawls: ACK 2ae953a Tree-SHA512: d97d00594acab4db239a162f37a744e7cb6dbf45aef9a8fe6e51db440a26efb93086bc2b7de4c0b4b4adbcce55f5e066f1e8698cac094c3c6d1ba5e94c6f317d

fanquake added the Refactoring label Nov 23, 2016

sdaftuar mentioned this pull request Nov 26, 2016

Share unused mempool memory with coincache #8610

Merged

sdaftuar force-pushed the faster-disconnect-rebased branch from 9906511 to e50b3cf Compare December 26, 2016 11:15

sdaftuar force-pushed the faster-disconnect-rebased branch from e50b3cf to b76dcf1 Compare January 4, 2017 20:45

sdaftuar changed the title ~~[WIP] Improve DisconnectTip performance~~ Improve DisconnectTip performance Jan 4, 2017

sdaftuar force-pushed the faster-disconnect-rebased branch from b76dcf1 to 37a90f1 Compare January 8, 2017 15:02

dcousens approved these changes Feb 28, 2017

View reviewed changes

sdaftuar force-pushed the faster-disconnect-rebased branch from 37a90f1 to 20c2979 Compare March 1, 2017 17:42

sdaftuar force-pushed the faster-disconnect-rebased branch 2 times, most recently from 9dc0b14 to c8d4c5f Compare March 7, 2017 19:38

ryanofsky reviewed Mar 8, 2017

View reviewed changes

sdaftuar force-pushed the faster-disconnect-rebased branch 3 times, most recently from a3b8d73 to 0947338 Compare March 11, 2017 02:27

sipa reviewed Mar 12, 2017

View reviewed changes

morcos reviewed Mar 13, 2017

View reviewed changes

TheBlueMatt reviewed Mar 13, 2017

View reviewed changes

sdaftuar force-pushed the faster-disconnect-rebased branch from 10853b3 to 8422ec0 Compare March 28, 2017 18:15

gmaxwell approved these changes May 22, 2017

View reviewed changes

laanwj merged commit c1235e3 into bitcoin:master May 30, 2017

TheBlueMatt mentioned this pull request Jun 28, 2017

Unbounded reorg memory usage #9027

Open

str4d mentioned this pull request Feb 15, 2018

Ensure AcceptToMemoryPool is only called when chainActive is accurate zcash/zcash#2951

Open

clashicly mentioned this pull request Aug 29, 2018

Orphaning of blocks causes bitcoin-cored/bitcoin-cored#28

Closed

random-zebra mentioned this pull request Mar 25, 2021

[Core] Store disconnected blocks txes outside mempool during reorg PIVX-Project/PIVX#2268

Merged

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

Improve DisconnectTip performance #9208

Improve DisconnectTip performance #9208

Uh oh!

Conversation

sdaftuar commented Nov 23, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sdaftuar commented Nov 29, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sdaftuar commented Jan 4, 2017

Uh oh!

dcousens commented Jan 4, 2017

Uh oh!

gmaxwell commented Jan 8, 2017

Uh oh!

sdaftuar commented Jan 8, 2017

Uh oh!

ryanofsky commented Feb 28, 2017

Uh oh!

dcousens left a comment

Choose a reason for hiding this comment

Uh oh!

sdaftuar commented Mar 1, 2017

Uh oh!

sdaftuar commented Mar 7, 2017

Uh oh!

ryanofsky left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sdaftuar commented Mar 11, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sdaftuar commented Mar 13, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

morcos commented Mar 13, 2017

Uh oh!

TheBlueMatt left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sdaftuar Mar 28, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dcousens commented Mar 24, 2017

Uh oh!

gmaxwell left a comment

Choose a reason for hiding this comment

Uh oh!

TheBlueMatt commented May 29, 2017

Uh oh!

sdaftuar commented Nov 23, 2016 •

edited

Loading

sdaftuar commented Nov 29, 2016 •

edited

Loading

sdaftuar Mar 28, 2017 •

edited

Loading