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.

6 files changed, 72 insertions, 20 deletions

diff --git a/src/init.cpp b/src/init.cpp
index f06c9e1100..3a112fdc93 100644
--- a/src/init.cpp
+++ b/src/init.cpp
@@ -213,6 +213,7 @@ void Shutdown()
 
     if (fFeeEstimatesInitialized)
     {
+        ::feeEstimator.FlushUnconfirmed(::mempool);
         fs::path est_path = GetDataDir() / FEE_ESTIMATES_FILENAME;
         CAutoFile est_fileout(fsbridge::fopen(est_path, "wb"), SER_DISK, CLIENT_VERSION);
         if (!est_fileout.IsNull())
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<std::vector<double>> confAvg; // confAvg[Y][X]
 
-    std::vector<std::vector<double>> 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<std::vector<double>> 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<double>& 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<uint256, TxStatsInfo>::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<uint256> 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;
diff --git a/src/rpc/mining.cpp b/src/rpc/mining.cpp
index 6851f21004..74e5ba5f44 100644
--- a/src/rpc/mining.cpp
+++ b/src/rpc/mining.cpp
@@ -893,6 +893,7 @@ UniValue estimaterawfee(const JSONRPCRequest& request)
             "  \"withintarget\" : x.x,   (numeric) number of txs over history horizon in the feerate range that were confirmed within target\n"
             "  \"totalconfirmed\" : x.x, (numeric) number of txs over history horizon in the feerate range that were confirmed at any point\n"
             "  \"inmempool\" : x.x,      (numeric) current number of txs in mempool in the feerate range unconfirmed for at least target blocks\n"
+            "  \"leftmempool\" : x.x,    (numeric) number of txs over history horizon in the feerate range that left mempool unconfirmed after target\n"
             "}\n"
             "\n"
             "A negative feerate is returned if no answer can be given.\n"
@@ -927,11 +928,13 @@ UniValue estimaterawfee(const JSONRPCRequest& request)
     result.push_back(Pair("pass.withintarget", round(buckets.pass.withinTarget * 100.0) / 100.0));
     result.push_back(Pair("pass.totalconfirmed", round(buckets.pass.totalConfirmed * 100.0) / 100.0));
     result.push_back(Pair("pass.inmempool", round(buckets.pass.inMempool * 100.0) / 100.0));
+    result.push_back(Pair("pass.leftmempool", round(buckets.pass.leftMempool * 100.0) / 100.0));
     result.push_back(Pair("fail.startrange", round(buckets.fail.start)));
     result.push_back(Pair("fail.endrange", round(buckets.fail.end)));
     result.push_back(Pair("fail.withintarget", round(buckets.fail.withinTarget * 100.0) / 100.0));
     result.push_back(Pair("fail.totalconfirmed", round(buckets.fail.totalConfirmed * 100.0) / 100.0));
     result.push_back(Pair("fail.inmempool", round(buckets.fail.inMempool * 100.0) / 100.0));
+    result.push_back(Pair("fail.leftmempool", round(buckets.fail.leftMempool * 100.0) / 100.0));
     return result;
 }
 
diff --git a/src/test/policyestimator_tests.cpp b/src/test/policyestimator_tests.cpp
index 942efce0f7..94de72ba47 100644
--- a/src/test/policyestimator_tests.cpp
+++ b/src/test/policyestimator_tests.cpp
@@ -159,16 +159,16 @@ BOOST_AUTO_TEST_CASE(BlockPolicyEstimates)
             txHashes[j].pop_back();
         }
     }
-    mpool.removeForBlock(block, 265);
+    mpool.removeForBlock(block, 266);
     block.clear();
     BOOST_CHECK(feeEst.estimateFee(1) == CFeeRate(0));
     for (int i = 2; i < 10;i++) {
-        BOOST_CHECK(feeEst.estimateFee(i).GetFeePerK() > origFeeEst[i-1] - deltaFee);
+        BOOST_CHECK(feeEst.estimateFee(i) == CFeeRate(0) || feeEst.estimateFee(i).GetFeePerK() > origFeeEst[i-1] - deltaFee);
     }
 
-    // Mine 200 more blocks where everything is mined every block
+    // Mine 400 more blocks where everything is mined every block
     // Estimates should be below original estimates
-    while (blocknum < 465) {
+    while (blocknum < 665) {
         for (int j = 0; j < 10; j++) { // For each fee multiple
             for (int k = 0; k < 4; k++) { // add 4 fee txs
                 tx.vin[0].prevout.n = 10000*blocknum+100*j+k;
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index ac842da6bf..a83805267b 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -448,7 +448,7 @@ void CTxMemPool::removeUnchecked(txiter it, MemPoolRemovalReason reason)
     mapLinks.erase(it);
     mapTx.erase(it);
     nTransactionsUpdated++;
-    if (minerPolicyEstimator) {minerPolicyEstimator->removeTx(hash);}
+    if (minerPolicyEstimator) {minerPolicyEstimator->removeTx(hash, false);}
 }
 
 // Calculates descendants of entry that are not already in setDescendants, and adds to