Merge #9942: Refactor CBlockPolicyEstimator

68af651 MOVEONLY: move TxConfirmStats to cpp (Alex Morcos)
2332f19 Initialize TxConfirmStats in constructor (Alex Morcos)
5ba81e5 Read and Write fee estimate file directly from CBlockPolicyEstimator (Alex Morcos)
14e10aa Call estimate(Smart)Fee directly from CBlockPolicyEstimator (Alex Morcos)
dbb9e36 Give CBlockPolicyEstimator it's own lock (Alex Morcos)
f6187d6 Make processBlockTx private. (Alex Morcos)
ae7327b Make feeEstimator its own global instance of CBlockPolicyEstimator (Alex Morcos)

Tree-SHA512: dbf3bd2b30822e609a35f3da519b62d23f8a50e564750695ddebd08553b4c01874ae3e07d792c6cc78cc377d2db33b951ffedc46ac7edaf5793f9ebb931713af

1 files changed, 176 insertions, 33 deletions

diff --git a/src/policy/fees.cpp b/src/policy/fees.cpp
index 38e07dc345..f3f7f8378e 100644
--- a/src/policy/fees.cpp
+++ b/src/policy/fees.cpp
@@ -7,14 +7,121 @@
 #include "policy/policy.h"
 
 #include "amount.h"
+#include "clientversion.h"
 #include "primitives/transaction.h"
 #include "random.h"
 #include "streams.h"
 #include "txmempool.h"
 #include "util.h"
 
-void TxConfirmStats::Initialize(std::vector<double>& defaultBuckets,
-                                unsigned int maxConfirms, double _decay)
+/**
+ * We will instantiate an instance of this class to track transactions that were
+ * included in a block. We will lump transactions into a bucket according to their
+ * approximate feerate and then track how long it took for those txs to be included in a block
+ *
+ * The tracking of unconfirmed (mempool) transactions is completely independent of the
+ * historical tracking of transactions that have been confirmed in a block.
+ */
+class TxConfirmStats
+{
+private:
+    //Define the buckets we will group transactions into
+    std::vector<double> buckets;              // The upper-bound of the range for the bucket (inclusive)
+    std::map<double, unsigned int> bucketMap; // Map of bucket upper-bound to index into all vectors by bucket
+
+    // For each bucket X:
+    // Count the total # of txs in each bucket
+    // Track the historical moving average of this total over blocks
+    std::vector<double> txCtAvg;
+    // and calculate the total for the current block to update the moving average
+    std::vector<int> curBlockTxCt;
+
+    // Count the total # of txs confirmed within Y blocks in each bucket
+    // Track the historical moving average of theses totals over blocks
+    std::vector<std::vector<double> > confAvg; // confAvg[Y][X]
+    // and calculate the totals for the current block to update the moving averages
+    std::vector<std::vector<int> > curBlockConf; // curBlockConf[Y][X]
+
+    // Sum the total feerate of all tx's in each bucket
+    // Track the historical moving average of this total over blocks
+    std::vector<double> avg;
+    // and calculate the total for the current block to update the moving average
+    std::vector<double> curBlockVal;
+
+    // Combine the conf counts with tx counts to calculate the confirmation % for each Y,X
+    // Combine the total value with the tx counts to calculate the avg feerate per bucket
+
+    double decay;
+
+    // Mempool counts of outstanding transactions
+    // For each bucket X, track the number of transactions in the mempool
+    // that are unconfirmed for each possible confirmation value Y
+    std::vector<std::vector<int> > unconfTxs;  //unconfTxs[Y][X]
+    // transactions still unconfirmed after MAX_CONFIRMS for each bucket
+    std::vector<int> oldUnconfTxs;
+
+public:
+    /**
+     * Create new TxConfirmStats. This is called by BlockPolicyEstimator's
+     * constructor with default values.
+     * @param defaultBuckets contains the upper limits for the bucket boundaries
+     * @param maxConfirms max number of confirms to track
+     * @param decay how much to decay the historical moving average per block
+     */
+    TxConfirmStats(const std::vector<double>& defaultBuckets, unsigned int maxConfirms, double decay);
+
+    /** Clear the state of the curBlock variables to start counting for the new block */
+    void ClearCurrent(unsigned int nBlockHeight);
+
+    /**
+     * Record a new transaction data point in the current block stats
+     * @param blocksToConfirm the number of blocks it took this transaction to confirm
+     * @param val the feerate of the transaction
+     * @warning blocksToConfirm is 1-based and has to be >= 1
+     */
+    void Record(int blocksToConfirm, double val);
+
+    /** Record a new transaction entering the mempool*/
+    unsigned int NewTx(unsigned int nBlockHeight, double val);
+
+    /** Remove a transaction from mempool tracking stats*/
+    void removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight,
+                  unsigned int bucketIndex);
+
+    /** Update our estimates by decaying our historical moving average and updating
+        with the data gathered from the current block */
+    void UpdateMovingAverages();
+
+    /**
+     * Calculate a feerate estimate.  Find the lowest value bucket (or range of buckets
+     * to make sure we have enough data points) whose transactions still have sufficient likelihood
+     * of being confirmed within the target number of confirmations
+     * @param confTarget target number of confirmations
+     * @param sufficientTxVal required average number of transactions per block in a bucket range
+     * @param minSuccess the success probability we require
+     * @param requireGreater return the lowest feerate such that all higher values pass minSuccess OR
+     *        return the highest feerate such that all lower values fail minSuccess
+     * @param nBlockHeight the current block height
+     */
+    double EstimateMedianVal(int confTarget, double sufficientTxVal,
+                             double minSuccess, bool requireGreater, unsigned int nBlockHeight) const;
+
+    /** Return the max number of confirms we're tracking */
+    unsigned int GetMaxConfirms() const { return confAvg.size(); }
+
+    /** Write state of estimation data to a file*/
+    void Write(CAutoFile& fileout) const;
+
+    /**
+     * Read saved state of estimation data from a file and replace all internal data structures and
+     * variables with this state.
+     */
+    void Read(CAutoFile& filein);
+};
+
+
+TxConfirmStats::TxConfirmStats(const std::vector<double>& defaultBuckets,
+                               unsigned int maxConfirms, double _decay)
 {
     decay = _decay;
     for (unsigned int i = 0; i < defaultBuckets.size(); i++) {
@@ -77,7 +184,7 @@ void TxConfirmStats::UpdateMovingAverages()
 // returns -1 on error conditions
 double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
                                          double successBreakPoint, bool requireGreater,
-                                         unsigned int nBlockHeight)
+                                         unsigned int nBlockHeight) const
 {
     // Counters for a bucket (or range of buckets)
     double nConf = 0; // Number of tx's confirmed within the confTarget
@@ -173,7 +280,7 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
     return median;
 }
 
-void TxConfirmStats::Write(CAutoFile& fileout)
+void TxConfirmStats::Write(CAutoFile& fileout) const
 {
     fileout << decay;
     fileout << buckets;
@@ -290,9 +397,10 @@ void TxConfirmStats::removeTx(unsigned int entryHeight, unsigned int nBestSeenHe
 // of no harm to try to remove them again.
 bool CBlockPolicyEstimator::removeTx(uint256 hash)
 {
+    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);
+        feeStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex);
         mapMemPoolTxs.erase(hash);
         return true;
     } else {
@@ -310,11 +418,17 @@ CBlockPolicyEstimator::CBlockPolicyEstimator()
         vfeelist.push_back(bucketBoundary);
     }
     vfeelist.push_back(INF_FEERATE);
-    feeStats.Initialize(vfeelist, MAX_BLOCK_CONFIRMS, DEFAULT_DECAY);
+    feeStats = new TxConfirmStats(vfeelist, MAX_BLOCK_CONFIRMS, DEFAULT_DECAY);
+}
+
+CBlockPolicyEstimator::~CBlockPolicyEstimator()
+{
+    delete feeStats;
 }
 
 void CBlockPolicyEstimator::processTransaction(const CTxMemPoolEntry& entry, bool validFeeEstimate)
 {
+    LOCK(cs_feeEstimator);
     unsigned int txHeight = entry.GetHeight();
     uint256 hash = entry.GetTx().GetHash();
     if (mapMemPoolTxs.count(hash)) {
@@ -343,7 +457,7 @@ void CBlockPolicyEstimator::processTransaction(const CTxMemPoolEntry& entry, boo
     CFeeRate feeRate(entry.GetFee(), entry.GetTxSize());
 
     mapMemPoolTxs[hash].blockHeight = txHeight;
-    mapMemPoolTxs[hash].bucketIndex = feeStats.NewTx(txHeight, (double)feeRate.GetFeePerK());
+    mapMemPoolTxs[hash].bucketIndex = feeStats->NewTx(txHeight, (double)feeRate.GetFeePerK());
 }
 
 bool CBlockPolicyEstimator::processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry* entry)
@@ -367,13 +481,14 @@ bool CBlockPolicyEstimator::processBlockTx(unsigned int nBlockHeight, const CTxM
     // Feerates are stored and reported as BTC-per-kb:
     CFeeRate feeRate(entry->GetFee(), entry->GetTxSize());
 
-    feeStats.Record(blocksToConfirm, (double)feeRate.GetFeePerK());
+    feeStats->Record(blocksToConfirm, (double)feeRate.GetFeePerK());
     return true;
 }
 
 void CBlockPolicyEstimator::processBlock(unsigned int nBlockHeight,
                                          std::vector<const CTxMemPoolEntry*>& entries)
 {
+    LOCK(cs_feeEstimator);
     if (nBlockHeight <= nBestSeenHeight) {
         // Ignore side chains and re-orgs; assuming they are random
         // they don't affect the estimate.
@@ -389,7 +504,7 @@ void CBlockPolicyEstimator::processBlock(unsigned int nBlockHeight,
     nBestSeenHeight = nBlockHeight;
 
     // Clear the current block state and update unconfirmed circular buffer
-    feeStats.ClearCurrent(nBlockHeight);
+    feeStats->ClearCurrent(nBlockHeight);
 
     unsigned int countedTxs = 0;
     // Repopulate the current block states
@@ -399,7 +514,7 @@ void CBlockPolicyEstimator::processBlock(unsigned int nBlockHeight,
     }
 
     // Update all exponential averages with the current block state
-    feeStats.UpdateMovingAverages();
+    feeStats->UpdateMovingAverages();
 
     LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy after updating estimates for %u of %u txs in block, since last block %u of %u tracked, new mempool map size %u\n",
              countedTxs, entries.size(), trackedTxs, trackedTxs + untrackedTxs, mapMemPoolTxs.size());
@@ -408,14 +523,15 @@ void CBlockPolicyEstimator::processBlock(unsigned int nBlockHeight,
     untrackedTxs = 0;
 }
 
-CFeeRate CBlockPolicyEstimator::estimateFee(int confTarget)
+CFeeRate CBlockPolicyEstimator::estimateFee(int confTarget) const
 {
+    LOCK(cs_feeEstimator);
     // Return failure if trying to analyze a target we're not tracking
     // It's not possible to get reasonable estimates for confTarget of 1
-    if (confTarget <= 1 || (unsigned int)confTarget > feeStats.GetMaxConfirms())
+    if (confTarget <= 1 || (unsigned int)confTarget > feeStats->GetMaxConfirms())
         return CFeeRate(0);
 
-    double median = feeStats.EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBestSeenHeight);
+    double median = feeStats->EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBestSeenHeight);
 
     if (median < 0)
         return CFeeRate(0);
@@ -423,22 +539,28 @@ CFeeRate CBlockPolicyEstimator::estimateFee(int confTarget)
     return CFeeRate(median);
 }
 
-CFeeRate CBlockPolicyEstimator::estimateSmartFee(int confTarget, int *answerFoundAtTarget, const CTxMemPool& pool)
+CFeeRate CBlockPolicyEstimator::estimateSmartFee(int confTarget, int *answerFoundAtTarget, const CTxMemPool& pool) const
 {
     if (answerFoundAtTarget)
         *answerFoundAtTarget = confTarget;
-    // Return failure if trying to analyze a target we're not tracking
-    if (confTarget <= 0 || (unsigned int)confTarget > feeStats.GetMaxConfirms())
-        return CFeeRate(0);
-
-    // It's not possible to get reasonable estimates for confTarget of 1
-    if (confTarget == 1)
-        confTarget = 2;
 
     double median = -1;
-    while (median < 0 && (unsigned int)confTarget <= feeStats.GetMaxConfirms()) {
-        median = feeStats.EstimateMedianVal(confTarget++, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBestSeenHeight);
-    }
+
+    {
+        LOCK(cs_feeEstimator);
+
+        // Return failure if trying to analyze a target we're not tracking
+        if (confTarget <= 0 || (unsigned int)confTarget > feeStats->GetMaxConfirms())
+            return CFeeRate(0);
+
+        // It's not possible to get reasonable estimates for confTarget of 1
+        if (confTarget == 1)
+            confTarget = 2;
+
+        while (median < 0 && (unsigned int)confTarget <= feeStats->GetMaxConfirms()) {
+            median = feeStats->EstimateMedianVal(confTarget++, SUFFICIENT_FEETXS, MIN_SUCCESS_PCT, true, nBestSeenHeight);
+        }
+    } // Must unlock cs_feeEstimator before taking mempool locks
 
     if (answerFoundAtTarget)
         *answerFoundAtTarget = confTarget - 1;
@@ -454,19 +576,40 @@ CFeeRate CBlockPolicyEstimator::estimateSmartFee(int confTarget, int *answerFoun
     return CFeeRate(median);
 }
 
-void CBlockPolicyEstimator::Write(CAutoFile& fileout)
+bool CBlockPolicyEstimator::Write(CAutoFile& fileout) const
 {
-    fileout << nBestSeenHeight;
-    feeStats.Write(fileout);
+    try {
+        LOCK(cs_feeEstimator);
+        fileout << 139900; // version required to read: 0.13.99 or later
+        fileout << CLIENT_VERSION; // version that wrote the file
+        fileout << nBestSeenHeight;
+        feeStats->Write(fileout);
+    }
+    catch (const std::exception&) {
+        LogPrintf("CBlockPolicyEstimator::Write(): unable to read policy estimator data (non-fatal)\n");
+        return false;
+    }
+    return true;
 }
 
-void CBlockPolicyEstimator::Read(CAutoFile& filein, int nFileVersion)
+bool CBlockPolicyEstimator::Read(CAutoFile& filein)
 {
-    int nFileBestSeenHeight;
-    filein >> nFileBestSeenHeight;
-    feeStats.Read(filein);
-    nBestSeenHeight = nFileBestSeenHeight;
-    // if nVersionThatWrote < 139900 then another TxConfirmStats (for priority) follows but can be ignored.
+    try {
+        LOCK(cs_feeEstimator);
+        int nVersionRequired, nVersionThatWrote, nFileBestSeenHeight;
+        filein >> nVersionRequired >> nVersionThatWrote;
+        if (nVersionRequired > CLIENT_VERSION)
+            return error("CBlockPolicyEstimator::Read(): up-version (%d) fee estimate file", nVersionRequired);
+        filein >> nFileBestSeenHeight;
+        feeStats->Read(filein);
+        nBestSeenHeight = nFileBestSeenHeight;
+        // if nVersionThatWrote < 139900 then another TxConfirmStats (for priority) follows but can be ignored.
+    }
+    catch (const std::exception&) {
+        LogPrintf("CBlockPolicyEstimator::Read(): unable to read policy estimator data (non-fatal)\n");
+        return false;
+    }
+    return true;
 }
 
 FeeFilterRounder::FeeFilterRounder(const CFeeRate& minIncrementalFee)