From c7447ec30348b338e77bc6429fbfac9f93549ef6 Mon Sep 17 00:00:00 2001 From: Alex Morcos Date: Thu, 9 Mar 2017 15:26:05 -0500 Subject: Track failures in fee estimation. Start tracking transactions which fail to confirm within the target and are then evicted or otherwise leave mempool. Fix slight error in unit test. --- src/policy/fees.cpp | 72 ++++++++++++++++++++++++++++++++++++++++++----------- src/policy/fees.h | 6 ++++- 2 files changed, 63 insertions(+), 15 deletions(-) (limited to 'src/policy') diff --git a/src/policy/fees.cpp b/src/policy/fees.cpp index a9a8335c61..e9d137e7f0 100644 --- a/src/policy/fees.cpp +++ b/src/policy/fees.cpp @@ -40,7 +40,9 @@ private: // Track the historical moving average of theses totals over blocks std::vector> confAvg; // confAvg[Y][X] - std::vector> failAvg; // future use + // Track moving avg of txs which have been evicted from the mempool + // after failing to be confirmed within Y blocks + std::vector> failAvg; // failAvg[Y][X] // Sum the total feerate of all tx's in each bucket // Track the historical moving average of this total over blocks @@ -89,7 +91,7 @@ public: /** Remove a transaction from mempool tracking stats*/ void removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, - unsigned int bucketIndex); + unsigned int bucketIndex, bool inBlock); /** Update our estimates by decaying our historical moving average and updating with the data gathered from the current block */ @@ -135,6 +137,10 @@ TxConfirmStats::TxConfirmStats(const std::vector& defaultBuckets, for (unsigned int i = 0; i < maxConfirms; i++) { confAvg[i].resize(buckets.size()); } + failAvg.resize(maxConfirms); + for (unsigned int i = 0; i < maxConfirms; i++) { + failAvg[i].resize(buckets.size()); + } txCtAvg.resize(buckets.size()); avg.resize(buckets.size()); @@ -179,6 +185,8 @@ void TxConfirmStats::UpdateMovingAverages() for (unsigned int j = 0; j < buckets.size(); j++) { for (unsigned int i = 0; i < confAvg.size(); i++) confAvg[i][j] = confAvg[i][j] * decay; + for (unsigned int i = 0; i < failAvg.size(); i++) + failAvg[i][j] = failAvg[i][j] * decay; avg[j] = avg[j] * decay; txCtAvg[j] = txCtAvg[j] * decay; } @@ -193,6 +201,7 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal, double nConf = 0; // Number of tx's confirmed within the confTarget double totalNum = 0; // Total number of tx's that were ever confirmed int extraNum = 0; // Number of tx's still in mempool for confTarget or longer + double failNum = 0; // Number of tx's that were never confirmed but removed from the mempool after confTarget int maxbucketindex = buckets.size() - 1; @@ -229,6 +238,7 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal, curFarBucket = bucket; nConf += confAvg[confTarget - 1][bucket]; totalNum += txCtAvg[bucket]; + failNum += failAvg[confTarget - 1][bucket]; for (unsigned int confct = confTarget; confct < GetMaxConfirms(); confct++) extraNum += unconfTxs[(nBlockHeight - confct)%bins][bucket]; extraNum += oldUnconfTxs[bucket]; @@ -237,7 +247,7 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal, // (Only count the confirmed data points, so that each confirmation count // will be looking at the same amount of data and same bucket breaks) if (totalNum >= sufficientTxVal / (1 - decay)) { - double curPct = nConf / (totalNum + extraNum); + double curPct = nConf / (totalNum + failNum + extraNum); // Check to see if we are no longer getting confirmed at the success rate if ((requireGreater && curPct < successBreakPoint) || (!requireGreater && curPct > successBreakPoint)) { @@ -250,6 +260,7 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal, failBucket.withinTarget = nConf; failBucket.totalConfirmed = totalNum; failBucket.inMempool = extraNum; + failBucket.leftMempool = failNum; passing = false; } continue; @@ -265,6 +276,8 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal, passBucket.totalConfirmed = totalNum; totalNum = 0; passBucket.inMempool = extraNum; + passBucket.leftMempool = failNum; + failNum = 0; extraNum = 0; bestNearBucket = curNearBucket; bestFarBucket = curFarBucket; @@ -309,16 +322,17 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal, failBucket.withinTarget = nConf; failBucket.totalConfirmed = totalNum; failBucket.inMempool = extraNum; + failBucket.leftMempool = failNum; } - LogPrint(BCLog::ESTIMATEFEE, "FeeEst: %d %s%.0f%% decay %.5f: need feerate: %g from (%g - %g) %.2f%% %.1f/(%.1f+%d mem) Fail: (%g - %g) %.2f%% %.1f/(%.1f+%d mem)\n", + LogPrint(BCLog::ESTIMATEFEE, "FeeEst: %d %s%.0f%% decay %.5f: need feerate: %g from (%g - %g) %.2f%% %.1f/(%.1f+%d mem+%.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f+%d mem+%.1f out)\n", confTarget, requireGreater ? ">" : "<", 100.0 * successBreakPoint, decay, median, passBucket.start, passBucket.end, - 100 * passBucket.withinTarget / (passBucket.totalConfirmed + passBucket.inMempool), - passBucket.withinTarget, passBucket.totalConfirmed, passBucket.inMempool, + 100 * passBucket.withinTarget / (passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool), + passBucket.withinTarget, passBucket.totalConfirmed, passBucket.inMempool, passBucket.leftMempool, failBucket.start, failBucket.end, - 100 * failBucket.withinTarget / (failBucket.totalConfirmed + failBucket.inMempool), - failBucket.withinTarget, failBucket.totalConfirmed, failBucket.inMempool); + 100 * failBucket.withinTarget / (failBucket.totalConfirmed + failBucket.inMempool + failBucket.leftMempool), + failBucket.withinTarget, failBucket.totalConfirmed, failBucket.inMempool, failBucket.leftMempool); if (result) { @@ -376,6 +390,19 @@ void TxConfirmStats::Read(CAutoFile& filein, int nFileVersion, size_t numBuckets if (nFileVersion >= 149900) { filein >> failAvg; + if (maxConfirms != failAvg.size()) { + throw std::runtime_error("Corrupt estimates file. Mismatch in confirms tracked for failures"); + } + for (unsigned int i = 0; i < maxConfirms; i++) { + if (failAvg[i].size() != numBuckets) { + throw std::runtime_error("Corrupt estimates file. Mismatch in one of failure average bucket counts"); + } + } + } else { + failAvg.resize(confAvg.size()); + for (unsigned int i = 0; i < failAvg.size(); i++) { + failAvg[i].resize(numBuckets); + } } // Resize the current block variables which aren't stored in the data file @@ -394,7 +421,7 @@ unsigned int TxConfirmStats::NewTx(unsigned int nBlockHeight, double val) return bucketindex; } -void TxConfirmStats::removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, unsigned int bucketindex) +void TxConfirmStats::removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, unsigned int bucketindex, bool inBlock) { //nBestSeenHeight is not updated yet for the new block int blocksAgo = nBestSeenHeight - entryHeight; @@ -422,6 +449,11 @@ void TxConfirmStats::removeTx(unsigned int entryHeight, unsigned int nBestSeenHe blockIndex, bucketindex); } } + if (!inBlock && blocksAgo >= 1) { + for (size_t i = 0; i < blocksAgo && i < failAvg.size(); i++) { + failAvg[i][bucketindex]++; + } + } } // This function is called from CTxMemPool::removeUnchecked to ensure @@ -429,14 +461,14 @@ void TxConfirmStats::removeTx(unsigned int entryHeight, unsigned int nBestSeenHe // tracked. Txs that were part of a block have already been removed in // processBlockTx to ensure they are never double tracked, but it is // of no harm to try to remove them again. -bool CBlockPolicyEstimator::removeTx(uint256 hash) +bool CBlockPolicyEstimator::removeTx(uint256 hash, bool inBlock) { LOCK(cs_feeEstimator); std::map::iterator pos = mapMemPoolTxs.find(hash); if (pos != mapMemPoolTxs.end()) { - feeStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex); - shortStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex); - longStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex); + feeStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock); + shortStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock); + longStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock); mapMemPoolTxs.erase(hash); return true; } else { @@ -511,7 +543,7 @@ void CBlockPolicyEstimator::processTransaction(const CTxMemPoolEntry& entry, boo bool CBlockPolicyEstimator::processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry* entry) { - if (!removeTx(entry->GetTx().GetHash())) { + if (!removeTx(entry->GetTx().GetHash(), true)) { // This transaction wasn't being tracked for fee estimation return false; } @@ -766,6 +798,18 @@ bool CBlockPolicyEstimator::Read(CAutoFile& filein) return true; } +void CBlockPolicyEstimator::FlushUnconfirmed(CTxMemPool& pool) { + int64_t startclear = GetTimeMicros(); + std::vector txids; + pool.queryHashes(txids); + LOCK(cs_feeEstimator); + for (auto& txid : txids) { + removeTx(txid, false); + } + int64_t endclear = GetTimeMicros(); + LogPrint(BCLog::ESTIMATEFEE, "Recorded %u unconfirmed txs from mempool in %ld micros\n",txids.size(), endclear - startclear); +} + FeeFilterRounder::FeeFilterRounder(const CFeeRate& minIncrementalFee) { CAmount minFeeLimit = std::max(CAmount(1), minIncrementalFee.GetFeePerK() / 2); diff --git a/src/policy/fees.h b/src/policy/fees.h index f42fe7bda7..03adbac4d2 100644 --- a/src/policy/fees.h +++ b/src/policy/fees.h @@ -74,6 +74,7 @@ struct EstimatorBucket double withinTarget = 0; double totalConfirmed = 0; double inMempool = 0; + double leftMempool = 0; }; struct EstimationResult @@ -145,7 +146,7 @@ public: void processTransaction(const CTxMemPoolEntry& entry, bool validFeeEstimate); /** Remove a transaction from the mempool tracking stats*/ - bool removeTx(uint256 hash); + bool removeTx(uint256 hash, bool inBlock); /** Return a feerate estimate */ CFeeRate estimateFee(int confTarget) const; @@ -166,6 +167,9 @@ public: /** Read estimation data from a file */ bool Read(CAutoFile& filein); + /** Empty mempool transactions on shutdown to record failure to confirm for txs still in mempool */ + void FlushUnconfirmed(CTxMemPool& pool); + private: CFeeRate minTrackedFee; //!< Passed to constructor to avoid dependency on main unsigned int nBestSeenHeight; -- cgit v1.2.3