From 013a56aa1af985894b3eaf7c325647b0b74e4456 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Wed, 19 Apr 2017 09:34:30 -0700 Subject: Non-atomic flushing using the blockchain as replay journal --- src/coins.cpp | 9 +++-- src/coins.h | 13 +++++- src/init.cpp | 10 +++++ src/txdb.cpp | 48 +++++++++++++++++++++- src/txdb.h | 3 ++ src/validation.cpp | 114 ++++++++++++++++++++++++++++++++++++++++++++++++----- src/validation.h | 5 +++ 7 files changed, 186 insertions(+), 16 deletions(-) diff --git a/src/coins.cpp b/src/coins.cpp index f8df835e9f..4bcafcec8c 100644 --- a/src/coins.cpp +++ b/src/coins.cpp @@ -13,6 +13,7 @@ bool CCoinsView::GetCoin(const COutPoint &outpoint, Coin &coin) const { return false; } bool CCoinsView::HaveCoin(const COutPoint &outpoint) const { return false; } uint256 CCoinsView::GetBestBlock() const { return uint256(); } +std::vector CCoinsView::GetHeadBlocks() const { return std::vector(); } bool CCoinsView::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) { return false; } CCoinsViewCursor *CCoinsView::Cursor() const { return 0; } @@ -21,6 +22,7 @@ CCoinsViewBacked::CCoinsViewBacked(CCoinsView *viewIn) : base(viewIn) { } bool CCoinsViewBacked::GetCoin(const COutPoint &outpoint, Coin &coin) const { return base->GetCoin(outpoint, coin); } bool CCoinsViewBacked::HaveCoin(const COutPoint &outpoint) const { return base->HaveCoin(outpoint); } uint256 CCoinsViewBacked::GetBestBlock() const { return base->GetBestBlock(); } +std::vector CCoinsViewBacked::GetHeadBlocks() const { return base->GetHeadBlocks(); } void CCoinsViewBacked::SetBackend(CCoinsView &viewIn) { base = &viewIn; } bool CCoinsViewBacked::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) { return base->BatchWrite(mapCoins, hashBlock); } CCoinsViewCursor *CCoinsViewBacked::Cursor() const { return base->Cursor(); } @@ -81,13 +83,14 @@ void CCoinsViewCache::AddCoin(const COutPoint &outpoint, Coin&& coin, bool possi cachedCoinsUsage += it->second.coin.DynamicMemoryUsage(); } -void AddCoins(CCoinsViewCache& cache, const CTransaction &tx, int nHeight) { +void AddCoins(CCoinsViewCache& cache, const CTransaction &tx, int nHeight, bool check) { bool fCoinbase = tx.IsCoinBase(); const uint256& txid = tx.GetHash(); for (size_t i = 0; i < tx.vout.size(); ++i) { - // Pass fCoinbase as the possible_overwrite flag to AddCoin, in order to correctly + bool overwrite = check ? cache.HaveCoin(COutPoint(txid, i)) : fCoinbase; + // Always set the possible_overwrite flag to AddCoin for coinbase txn, in order to correctly // deal with the pre-BIP30 occurrences of duplicate coinbase transactions. - cache.AddCoin(COutPoint(txid, i), Coin(tx.vout[i], nHeight, fCoinbase), fCoinbase); + cache.AddCoin(COutPoint(txid, i), Coin(tx.vout[i], nHeight, fCoinbase), overwrite); } } diff --git a/src/coins.h b/src/coins.h index 4774c9f6a6..de3264f46e 100644 --- a/src/coins.h +++ b/src/coins.h @@ -155,6 +155,12 @@ public: //! Retrieve the block hash whose state this CCoinsView currently represents virtual uint256 GetBestBlock() const; + //! Retrieve the range of blocks that may have been only partially written. + //! If the database is in a consistent state, the result is the empty vector. + //! Otherwise, a two-element vector is returned consisting of the new and + //! the old block hash, in that order. + virtual std::vector GetHeadBlocks() const; + //! Do a bulk modification (multiple Coin changes + BestBlock change). //! The passed mapCoins can be modified. virtual bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock); @@ -181,6 +187,7 @@ public: bool GetCoin(const COutPoint &outpoint, Coin &coin) const override; bool HaveCoin(const COutPoint &outpoint) const override; uint256 GetBestBlock() const override; + std::vector GetHeadBlocks() const override; void SetBackend(CCoinsView &viewIn); bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) override; CCoinsViewCursor *Cursor() const override; @@ -289,10 +296,12 @@ private: }; //! Utility function to add all of a transaction's outputs to a cache. -// It assumes that overwrites are only possible for coinbase transactions, +// When check is false, this assumes that overwrites are only possible for coinbase transactions. +// When check is true, the underlying view may be queried to determine whether an addition is +// an overwrite. // TODO: pass in a boolean to limit these possible overwrites to known // (pre-BIP34) cases. -void AddCoins(CCoinsViewCache& cache, const CTransaction& tx, int nHeight); +void AddCoins(CCoinsViewCache& cache, const CTransaction& tx, int nHeight, bool check = false); //! Utility function to find any unspent output with a given txid. const Coin& AccessByTxid(const CCoinsViewCache& cache, const uint256& txid); diff --git a/src/init.cpp b/src/init.cpp index 88084cbeec..51f0d40035 100644 --- a/src/init.cpp +++ b/src/init.cpp @@ -336,6 +336,9 @@ std::string HelpMessage(HelpMessageMode mode) #endif } strUsage += HelpMessageOpt("-datadir=", _("Specify data directory")); + if (showDebug) { + strUsage += HelpMessageOpt("-dbbatchsize", strprintf("Maximum database write batch size in bytes (default: %u)", nDefaultDbBatchSize)); + } strUsage += HelpMessageOpt("-dbcache=", strprintf(_("Set database cache size in megabytes (%d to %d, default: %d)"), nMinDbCache, nMaxDbCache, nDefaultDbCache)); if (showDebug) strUsage += HelpMessageOpt("-feefilter", strprintf("Tell other nodes to filter invs to us by our mempool min fee (default: %u)", DEFAULT_FEEFILTER)); @@ -1426,6 +1429,13 @@ bool AppInitMain(boost::thread_group& threadGroup, CScheduler& scheduler) break; } + if (!ReplayBlocks(chainparams, pcoinsdbview)) { + strLoadError = _("Unable to replay blocks. You will need to rebuild the database using -reindex-chainstate."); + break; + } + pcoinsTip->SetBestBlock(pcoinsdbview->GetBestBlock()); // TODO: only initialize pcoinsTip after ReplayBlocks + LoadChainTip(chainparams); + if (!fReindex && chainActive.Tip() != NULL) { uiInterface.InitMessage(_("Rewinding blocks...")); if (!RewindBlockIndex(chainparams)) { diff --git a/src/txdb.cpp b/src/txdb.cpp index 97e916fd22..f0e5098b11 100644 --- a/src/txdb.cpp +++ b/src/txdb.cpp @@ -21,6 +21,7 @@ static const char DB_TXINDEX = 't'; static const char DB_BLOCK_INDEX = 'b'; static const char DB_BEST_BLOCK = 'B'; +static const char DB_HEAD_BLOCKS = 'H'; static const char DB_FLAG = 'F'; static const char DB_REINDEX_FLAG = 'R'; static const char DB_LAST_BLOCK = 'l'; @@ -68,10 +69,45 @@ uint256 CCoinsViewDB::GetBestBlock() const { return hashBestChain; } +std::vector CCoinsViewDB::GetHeadBlocks() const { + std::vector vhashHeadBlocks; + if (!db.Read(DB_HEAD_BLOCKS, vhashHeadBlocks)) { + return std::vector(); + } + return vhashHeadBlocks; +} + bool CCoinsViewDB::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) { CDBBatch batch(db); size_t count = 0; size_t changed = 0; + size_t batch_size = (size_t)GetArg("-dbbatchsize", nDefaultDbBatchSize); + + + uint256 old_tip = GetBestBlock(); + if (old_tip.IsNull()) { + // We may be in the middle of replaying. + std::vector old_heads = GetHeadBlocks(); + if (old_heads.size() == 2) { + assert(old_heads[0] == hashBlock); + old_tip = old_heads[1]; + } + } + + if (hashBlock.IsNull()) { + // Initial flush, nothing to write. + assert(mapCoins.empty()); + assert(old_tip.IsNull()); + return true; + } + + // In the first batch, mark the database as being in the middle of a + // transition from old_tip to hashBlock. + // A vector is used for future extensibility, as we may want to support + // interrupting after partial writes from multiple independent reorgs. + batch.Erase(DB_BEST_BLOCK); + batch.Write(DB_HEAD_BLOCKS, std::vector{hashBlock, old_tip}); + for (CCoinsMap::iterator it = mapCoins.begin(); it != mapCoins.end();) { if (it->second.flags & CCoinsCacheEntry::DIRTY) { CoinEntry entry(&it->first); @@ -84,10 +120,18 @@ bool CCoinsViewDB::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) { count++; CCoinsMap::iterator itOld = it++; mapCoins.erase(itOld); + if (batch.SizeEstimate() > batch_size) { + LogPrint(BCLog::COINDB, "Writing partial batch of %.2f MiB\n", batch.SizeEstimate() * (1.0 / 1048576.0)); + db.WriteBatch(batch); + batch.Clear(); + } } - if (!hashBlock.IsNull()) - batch.Write(DB_BEST_BLOCK, hashBlock); + // In the last batch, mark the database as consistent with hashBlock again. + batch.Erase(DB_HEAD_BLOCKS); + batch.Write(DB_BEST_BLOCK, hashBlock); + + LogPrint(BCLog::COINDB, "Writing final batch of %.2f MiB\n", batch.SizeEstimate() * (1.0 / 1048576.0)); bool ret = db.WriteBatch(batch); LogPrint(BCLog::COINDB, "Committed %u changed transaction outputs (out of %u) to coin database...\n", (unsigned int)changed, (unsigned int)count); return ret; diff --git a/src/txdb.h b/src/txdb.h index 2a3e4eb696..fa6bce2140 100644 --- a/src/txdb.h +++ b/src/txdb.h @@ -25,6 +25,8 @@ static constexpr int DB_PEAK_USAGE_FACTOR = 2; static constexpr int MAX_BLOCK_COINSDB_USAGE = 10 * DB_PEAK_USAGE_FACTOR; //! -dbcache default (MiB) static const int64_t nDefaultDbCache = 450; +//! -dbbatchsize default (bytes) +static const int64_t nDefaultDbBatchSize = 16 << 20; //! max. -dbcache (MiB) static const int64_t nMaxDbCache = sizeof(void*) > 4 ? 16384 : 1024; //! min. -dbcache (MiB) @@ -74,6 +76,7 @@ public: bool GetCoin(const COutPoint &outpoint, Coin &coin) const override; bool HaveCoin(const COutPoint &outpoint) const override; uint256 GetBestBlock() const override; + std::vector GetHeadBlocks() const override; bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) override; CCoinsViewCursor *Cursor() const override; diff --git a/src/validation.cpp b/src/validation.cpp index eb6ea42b63..f5e31e0a0b 100644 --- a/src/validation.cpp +++ b/src/validation.cpp @@ -96,7 +96,7 @@ namespace { struct CBlockIndexWorkComparator { - bool operator()(CBlockIndex *pa, CBlockIndex *pb) const { + bool operator()(const CBlockIndex *pa, const CBlockIndex *pb) const { // First sort by most total work, ... if (pa->nChainWork > pb->nChainWork) return false; if (pa->nChainWork < pb->nChainWork) return true; @@ -1331,17 +1331,19 @@ int ApplyTxInUndo(Coin&& undo, CCoinsViewCache& view, const COutPoint& out) return DISCONNECT_FAILED; // adding output for transaction without known metadata } } - view.AddCoin(out, std::move(undo), undo.fCoinBase); + // The potential_overwrite parameter to AddCoin is only allowed to be false if we know for + // sure that the coin did not already exist in the cache. As we have queried for that above + // using HaveCoin, we don't need to guess. When fClean is false, a coin already existed and + // it is an overwrite. + view.AddCoin(out, std::move(undo), !fClean); return fClean ? DISCONNECT_OK : DISCONNECT_UNCLEAN; } /** Undo the effects of this block (with given index) on the UTXO set represented by coins. - * When UNCLEAN or FAILED is returned, view is left in an indeterminate state. */ + * When FAILED is returned, view is left in an indeterminate state. */ static DisconnectResult DisconnectBlock(const CBlock& block, const CBlockIndex* pindex, CCoinsViewCache& view) { - assert(pindex->GetBlockHash() == view.GetBestBlock()); - bool fClean = true; CBlockUndo blockUndo; @@ -1946,6 +1948,7 @@ bool static DisconnectTip(CValidationState& state, const CChainParams& chainpara int64_t nStart = GetTimeMicros(); { CCoinsViewCache view(pcoinsTip); + assert(view.GetBestBlock() == pindexDelete->GetBlockHash()); if (DisconnectBlock(block, pindexDelete, view) != DISCONNECT_OK) return error("DisconnectTip(): DisconnectBlock %s failed", pindexDelete->GetBlockHash().ToString()); bool flushed = view.Flush(); @@ -3417,20 +3420,26 @@ bool static LoadBlockIndexDB(const CChainParams& chainparams) pblocktree->ReadFlag("txindex", fTxIndex); LogPrintf("%s: transaction index %s\n", __func__, fTxIndex ? "enabled" : "disabled"); + LoadChainTip(chainparams); + return true; +} + +void LoadChainTip(const CChainParams& chainparams) +{ + if (chainActive.Tip() && chainActive.Tip()->GetBlockHash() == pcoinsTip->GetBestBlock()) return; + // Load pointer to end of best chain BlockMap::iterator it = mapBlockIndex.find(pcoinsTip->GetBestBlock()); if (it == mapBlockIndex.end()) - return true; + return; chainActive.SetTip(it->second); PruneBlockIndexCandidates(); - LogPrintf("%s: hashBestChain=%s height=%d date=%s progress=%f\n", __func__, + LogPrintf("Loaded best chain: hashBestChain=%s height=%d date=%s progress=%f\n", chainActive.Tip()->GetBlockHash().ToString(), chainActive.Height(), DateTimeStrFormat("%Y-%m-%d %H:%M:%S", chainActive.Tip()->GetBlockTime()), GuessVerificationProgress(chainparams.TxData(), chainActive.Tip())); - - return true; } CVerifyDB::CVerifyDB() @@ -3499,6 +3508,7 @@ bool CVerifyDB::VerifyDB(const CChainParams& chainparams, CCoinsView *coinsview, } // check level 3: check for inconsistencies during memory-only disconnect of tip blocks if (nCheckLevel >= 3 && pindex == pindexState && (coins.DynamicMemoryUsage() + pcoinsTip->DynamicMemoryUsage()) <= nCoinCacheUsage) { + assert(coins.GetBestBlock() == pindex->GetBlockHash()); DisconnectResult res = DisconnectBlock(block, pindex, coins); if (res == DISCONNECT_FAILED) { return error("VerifyDB(): *** irrecoverable inconsistency in block data at %d, hash=%s", pindex->nHeight, pindex->GetBlockHash().ToString()); @@ -3538,6 +3548,92 @@ bool CVerifyDB::VerifyDB(const CChainParams& chainparams, CCoinsView *coinsview, return true; } +/** Apply the effects of a block on the utxo cache, ignoring that it may already have been applied. */ +static bool RollforwardBlock(const CBlockIndex* pindex, CCoinsViewCache& inputs, const CChainParams& params) +{ + // TODO: merge with ConnectBlock + CBlock block; + if (!ReadBlockFromDisk(block, pindex, params.GetConsensus())) { + return error("ReplayBlock(): ReadBlockFromDisk failed at %d, hash=%s", pindex->nHeight, pindex->GetBlockHash().ToString()); + } + + for (const CTransactionRef& tx : block.vtx) { + if (!tx->IsCoinBase()) { + for (const CTxIn &txin : tx->vin) { + inputs.SpendCoin(txin.prevout); + } + } + // Pass check = true as every addition may be an overwrite. + AddCoins(inputs, *tx, pindex->nHeight, true); + } + return true; +} + +bool ReplayBlocks(const CChainParams& params, CCoinsView* view) +{ + LOCK(cs_main); + + CCoinsViewCache cache(view); + + std::vector hashHeads = view->GetHeadBlocks(); + if (hashHeads.empty()) return true; // We're already in a consistent state. + if (hashHeads.size() != 2) return error("ReplayBlocks(): unknown inconsistent state"); + + uiInterface.ShowProgress(_("Replaying blocks..."), 0); + LogPrintf("Replaying blocks\n"); + + const CBlockIndex* pindexOld = nullptr; // Old tip during the interrupted flush. + const CBlockIndex* pindexNew; // New tip during the interrupted flush. + const CBlockIndex* pindexFork = nullptr; // Latest block common to both the old and the new tip. + + if (mapBlockIndex.count(hashHeads[0]) == 0) { + return error("ReplayBlocks(): reorganization to unknown block requested"); + } + pindexNew = mapBlockIndex[hashHeads[0]]; + + if (!hashHeads[1].IsNull()) { // The old tip is allowed to be 0, indicating it's the first flush. + if (mapBlockIndex.count(hashHeads[1]) == 0) { + return error("ReplayBlocks(): reorganization from unknown block requested"); + } + pindexOld = mapBlockIndex[hashHeads[1]]; + pindexFork = LastCommonAncestor(pindexOld, pindexNew); + assert(pindexFork != nullptr); + } + + // Rollback along the old branch. + while (pindexOld != pindexFork) { + if (pindexOld->nHeight > 0) { // Never disconnect the genesis block. + CBlock block; + if (!ReadBlockFromDisk(block, pindexOld, params.GetConsensus())) { + return error("RollbackBlock(): ReadBlockFromDisk() failed at %d, hash=%s", pindexOld->nHeight, pindexOld->GetBlockHash().ToString()); + } + LogPrintf("Rolling back %s (%i)\n", pindexOld->GetBlockHash().ToString(), pindexOld->nHeight); + DisconnectResult res = DisconnectBlock(block, pindexOld, cache); + if (res == DISCONNECT_FAILED) { + return error("RollbackBlock(): DisconnectBlock failed at %d, hash=%s", pindexOld->nHeight, pindexOld->GetBlockHash().ToString()); + } + // If DISCONNECT_UNCLEAN is returned, it means a non-existing UTXO was deleted, or an existing UTXO was + // overwritten. It corresponds to cases where the block-to-be-disconnect never had all its operations + // applied to the UTXO set. However, as both writing a UTXO and deleting a UTXO are idempotent operations, + // the result is still a version of the UTXO set with the effects of that block undone. + } + pindexOld = pindexOld->pprev; + } + + // Roll forward from the forking point to the new tip. + int nForkHeight = pindexFork ? pindexFork->nHeight : 0; + for (int nHeight = nForkHeight + 1; nHeight <= pindexNew->nHeight; ++nHeight) { + const CBlockIndex* pindex = pindexNew->GetAncestor(nHeight); + LogPrintf("Rolling forward %s (%i)\n", pindex->GetBlockHash().ToString(), nHeight); + if (!RollforwardBlock(pindex, cache, params)) return false; + } + + cache.SetBestBlock(pindexNew->GetBlockHash()); + cache.Flush(); + uiInterface.ShowProgress("", 100); + return true; +} + bool RewindBlockIndex(const CChainParams& params) { LOCK(cs_main); diff --git a/src/validation.h b/src/validation.h index 82df4cb170..8a721dd7a2 100644 --- a/src/validation.h +++ b/src/validation.h @@ -260,6 +260,8 @@ bool LoadExternalBlockFile(const CChainParams& chainparams, FILE* fileIn, CDiskB bool InitBlockIndex(const CChainParams& chainparams); /** Load the block tree and coins database from disk */ bool LoadBlockIndex(const CChainParams& chainparams); +/** Update the chain tip based on database information. */ +void LoadChainTip(const CChainParams& chainparams); /** Unload database information */ void UnloadBlockIndex(); /** Run an instance of the script checking thread */ @@ -424,6 +426,9 @@ public: bool VerifyDB(const CChainParams& chainparams, CCoinsView *coinsview, int nCheckLevel, int nCheckDepth); }; +/** Replay blocks that aren't fully applied to the database. */ +bool ReplayBlocks(const CChainParams& params, CCoinsView* view); + /** Find the last common block between the parameter chain and a locator. */ CBlockIndex* FindForkInGlobalIndex(const CChain& chain, const CBlockLocator& locator); -- cgit v1.2.3