Skip to content

Commit 3ee76d6

Browse files
morcosmorcos
committed
Introduce a scale factor
For the per confirmation number tracking of data, introduce a scale factor so that in the longer horizones confirmations are bucketed together at a resolution of the scale. (instead of 1008 individual data points for each fee bucket, have 42 data points each covering 24 different confirmation values.. (1-24), (25-48), etc.. )
1 parent 5f1f0c6 commit 3ee76d6

File tree

4 files changed

+45
-35
lines changed

4 files changed

+45
-35
lines changed

‎src/policy/fees.cpp‎

Lines changed: 34 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -53,13 +53,14 @@ class TxConfirmStats
5353

5454
double decay;
5555

56+
// Resolution (# of blocks) with which confirmations are tracked
5657
unsigned int scale;
5758

5859
// Mempool counts of outstanding transactions
5960
// For each bucket X, track the number of transactions in the mempool
6061
// that are unconfirmed for each possible confirmation value Y
6162
std::vector<std::vector<int> > unconfTxs; //unconfTxs[Y][X]
62-
// transactions still unconfirmed after MAX_CONFIRMS for each bucket
63+
// transactions still unconfirmed after GetMaxConfirms for each bucket
6364
std::vector<int> oldUnconfTxs;
6465

6566
void resizeInMemoryCounters(size_t newbuckets);
@@ -73,7 +74,7 @@ class TxConfirmStats
7374
* @param decay how much to decay the historical moving average per block
7475
*/
7576
TxConfirmStats(const std::vector<double>& defaultBuckets, const std::map<double, unsigned int>& defaultBucketMap,
76-
unsigned int maxConfirms, double decay);
77+
unsigned int maxPeriods, double decay, unsigned int scale);
7778

7879
/** Roll the circular buffer for unconfirmed txs*/
7980
void ClearCurrent(unsigned int nBlockHeight);
@@ -113,7 +114,7 @@ class TxConfirmStats
113114
EstimationResult *result = nullptr) const;
114115

115116
/** Return the max number of confirms we're tracking */
116-
unsigned int GetMaxConfirms() const { return confAvg.size(); }
117+
unsigned int GetMaxConfirms() const { return scale * confAvg.size(); }
117118

118119
/** Write state of estimation data to a file*/
119120
void Write(CAutoFile& fileout) const;
@@ -128,17 +129,17 @@ class TxConfirmStats
128129

129130
TxConfirmStats::TxConfirmStats(const std::vector<double>& defaultBuckets,
130131
const std::map<double, unsigned int>& defaultBucketMap,
131-
unsigned int maxConfirms, double _decay)
132+
unsigned int maxPeriods, double _decay, unsigned int _scale)
132133
: buckets(defaultBuckets), bucketMap(defaultBucketMap)
133134
{
134135
decay = _decay;
135-
scale = 1;
136-
confAvg.resize(maxConfirms);
137-
for (unsigned int i = 0; i < maxConfirms; i++) {
136+
scale = _scale;
137+
confAvg.resize(maxPeriods);
138+
for (unsigned int i = 0; i < maxPeriods; i++) {
138139
confAvg[i].resize(buckets.size());
139140
}
140-
failAvg.resize(maxConfirms);
141-
for (unsigned int i = 0; i < maxConfirms; i++) {
141+
failAvg.resize(maxPeriods);
142+
for (unsigned int i = 0; i < maxPeriods; i++) {
142143
failAvg[i].resize(buckets.size());
143144
}
144145

@@ -172,8 +173,9 @@ void TxConfirmStats::Record(int blocksToConfirm, double val)
172173
// blocksToConfirm is 1-based
173174
if (blocksToConfirm < 1)
174175
return;
176+
int periodsToConfirm = (blocksToConfirm + scale - 1)/scale;
175177
unsigned int bucketindex = bucketMap.lower_bound(val)->second;
176-
for (size_t i = blocksToConfirm; i <= confAvg.size(); i++) {
178+
for (size_t i = periodsToConfirm; i <= confAvg.size(); i++) {
177179
confAvg[i - 1][bucketindex]++;
178180
}
179181
txCtAvg[bucketindex]++;
@@ -202,6 +204,7 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
202204
double totalNum = 0; // Total number of tx's that were ever confirmed
203205
int extraNum = 0; // Number of tx's still in mempool for confTarget or longer
204206
double failNum = 0; // Number of tx's that were never confirmed but removed from the mempool after confTarget
207+
int periodTarget = (confTarget + scale - 1)/scale;
205208

206209
int maxbucketindex = buckets.size() - 1;
207210

@@ -236,9 +239,9 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
236239
newBucketRange = false;
237240
}
238241
curFarBucket = bucket;
239-
nConf += confAvg[confTarget - 1][bucket];
242+
nConf += confAvg[periodTarget - 1][bucket];
240243
totalNum += txCtAvg[bucket];
241-
failNum += failAvg[confTarget - 1][bucket];
244+
failNum += failAvg[periodTarget - 1][bucket];
242245
for (unsigned int confct = confTarget; confct < GetMaxConfirms(); confct++)
243246
extraNum += unconfTxs[(nBlockHeight - confct)%bins][bucket];
244247
extraNum += oldUnconfTxs[bucket];
@@ -339,6 +342,7 @@ double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
339342
result->pass = passBucket;
340343
result->fail = failBucket;
341344
result->decay = decay;
345+
result->scale = scale;
342346
}
343347
return median;
344348
}
@@ -358,15 +362,15 @@ void TxConfirmStats::Read(CAutoFile& filein, int nFileVersion, size_t numBuckets
358362
// Read data file and do some very basic sanity checking
359363
// buckets and bucketMap are not updated yet, so don't access them
360364
// If there is a read failure, we'll just discard this entire object anyway
361-
size_t maxConfirms;
365+
size_t maxConfirms, maxPeriods;
362366

363367
// The current version will store the decay with each individual TxConfirmStats and also keep a scale factor
364368
if (nFileVersion >= 149900) {
365369
filein >> decay;
366370
if (decay <= 0 || decay >= 1) {
367371
throw std::runtime_error("Corrupt estimates file. Decay must be between 0 and 1 (non-inclusive)");
368372
}
369-
filein >> scale; //Unused for now
373+
filein >> scale;
370374
}
371375

372376
filein >> avg;
@@ -378,22 +382,24 @@ void TxConfirmStats::Read(CAutoFile& filein, int nFileVersion, size_t numBuckets
378382
throw std::runtime_error("Corrupt estimates file. Mismatch in tx count bucket count");
379383
}
380384
filein >> confAvg;
381-
maxConfirms = confAvg.size();
385+
maxPeriods = confAvg.size();
386+
maxConfirms = scale * maxPeriods;
387+
382388
if (maxConfirms <= 0 || maxConfirms > 6 * 24 * 7) { // one week
383389
throw std::runtime_error("Corrupt estimates file. Must maintain estimates for between 1 and 1008 (one week) confirms");
384390
}
385-
for (unsigned int i = 0; i < maxConfirms; i++) {
391+
for (unsigned int i = 0; i < maxPeriods; i++) {
386392
if (confAvg[i].size() != numBuckets) {
387393
throw std::runtime_error("Corrupt estimates file. Mismatch in feerate conf average bucket count");
388394
}
389395
}
390396

391397
if (nFileVersion >= 149900) {
392398
filein >> failAvg;
393-
if (maxConfirms != failAvg.size()) {
399+
if (maxPeriods != failAvg.size()) {
394400
throw std::runtime_error("Corrupt estimates file. Mismatch in confirms tracked for failures");
395401
}
396-
for (unsigned int i = 0; i < maxConfirms; i++) {
402+
for (unsigned int i = 0; i < maxPeriods; i++) {
397403
if (failAvg[i].size() != numBuckets) {
398404
throw std::runtime_error("Corrupt estimates file. Mismatch in one of failure average bucket counts");
399405
}
@@ -449,8 +455,9 @@ void TxConfirmStats::removeTx(unsigned int entryHeight, unsigned int nBestSeenHe
449455
blockIndex, bucketindex);
450456
}
451457
}
452-
if (!inBlock && blocksAgo >= 1) {
453-
for (size_t i = 0; i < blocksAgo && i < failAvg.size(); i++) {
458+
if (!inBlock && (unsigned int)blocksAgo >= scale) { // Only counts as a failure if not confirmed for entire period
459+
unsigned int periodsAgo = blocksAgo / scale;
460+
for (size_t i = 0; i < periodsAgo && i < failAvg.size(); i++) {
454461
failAvg[i][bucketindex]++;
455462
}
456463
}
@@ -490,9 +497,9 @@ CBlockPolicyEstimator::CBlockPolicyEstimator()
490497
bucketMap[INF_FEERATE] = bucketIndex;
491498
assert(bucketMap.size() == buckets.size());
492499

493-
feeStats = new TxConfirmStats(buckets, bucketMap, MED_BLOCK_CONFIRMS, MED_DECAY);
494-
shortStats = new TxConfirmStats(buckets, bucketMap, SHORT_BLOCK_CONFIRMS, SHORT_DECAY);
495-
longStats = new TxConfirmStats(buckets, bucketMap, LONG_BLOCK_CONFIRMS, LONG_DECAY);
500+
feeStats = new TxConfirmStats(buckets, bucketMap, MED_BLOCK_PERIODS, MED_DECAY, MED_SCALE);
501+
shortStats = new TxConfirmStats(buckets, bucketMap, SHORT_BLOCK_PERIODS, SHORT_DECAY, SHORT_SCALE);
502+
longStats = new TxConfirmStats(buckets, bucketMap, LONG_BLOCK_PERIODS, LONG_DECAY, LONG_SCALE);
496503
}
497504

498505
CBlockPolicyEstimator::~CBlockPolicyEstimator()
@@ -864,7 +871,7 @@ bool CBlockPolicyEstimator::Read(CAutoFile& filein)
864871

865872
std::map<double, unsigned int> tempMap;
866873

867-
std::unique_ptr<TxConfirmStats> tempFeeStats(new TxConfirmStats(tempBuckets, tempMap, MED_BLOCK_CONFIRMS, tempDecay));
874+
std::unique_ptr<TxConfirmStats> tempFeeStats(new TxConfirmStats(tempBuckets, tempMap, MED_BLOCK_PERIODS, tempDecay, 1));
868875
tempFeeStats->Read(filein, nVersionThatWrote, tempNum);
869876
// if nVersionThatWrote < 139900 then another TxConfirmStats (for priority) follows but can be ignored.
870877

@@ -884,9 +891,9 @@ bool CBlockPolicyEstimator::Read(CAutoFile& filein)
884891
if (numBuckets <= 1 || numBuckets > 1000)
885892
throw std::runtime_error("Corrupt estimates file. Must have between 2 and 1000 feerate buckets");
886893

887-
std::unique_ptr<TxConfirmStats> fileFeeStats(new TxConfirmStats(buckets, bucketMap, MED_BLOCK_CONFIRMS, MED_DECAY));
888-
std::unique_ptr<TxConfirmStats> fileShortStats(new TxConfirmStats(buckets, bucketMap, SHORT_BLOCK_CONFIRMS, SHORT_DECAY));
889-
std::unique_ptr<TxConfirmStats> fileLongStats(new TxConfirmStats(buckets, bucketMap, LONG_BLOCK_CONFIRMS, LONG_DECAY));
894+
std::unique_ptr<TxConfirmStats> fileFeeStats(new TxConfirmStats(buckets, bucketMap, MED_BLOCK_PERIODS, MED_DECAY, MED_SCALE));
895+
std::unique_ptr<TxConfirmStats> fileShortStats(new TxConfirmStats(buckets, bucketMap, SHORT_BLOCK_PERIODS, SHORT_DECAY, SHORT_SCALE));
896+
std::unique_ptr<TxConfirmStats> fileLongStats(new TxConfirmStats(buckets, bucketMap, LONG_BLOCK_PERIODS, LONG_DECAY, LONG_SCALE));
890897
fileFeeStats->Read(filein, nVersionThatWrote, numBuckets);
891898
fileShortStats->Read(filein, nVersionThatWrote, numBuckets);
892899
fileLongStats->Read(filein, nVersionThatWrote, numBuckets);

‎src/policy/fees.h‎

Lines changed: 7 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -82,6 +82,7 @@ struct EstimationResult
8282
EstimatorBucket pass;
8383
EstimatorBucket fail;
8484
double decay;
85+
unsigned int scale;
8586
};
8687

8788
/**
@@ -93,11 +94,14 @@ class CBlockPolicyEstimator
9394
{
9495
private:
9596
/** Track confirm delays up to 12 blocks medium decay */
96-
static constexpr unsigned int SHORT_BLOCK_CONFIRMS = 12;
97+
static constexpr unsigned int SHORT_BLOCK_PERIODS = 12;
98+
static constexpr unsigned int SHORT_SCALE = 1;
9799
/** Track confirm delays up to 48 blocks medium decay */
98-
static constexpr unsigned int MED_BLOCK_CONFIRMS = 48;
100+
static constexpr unsigned int MED_BLOCK_PERIODS = 24;
101+
static constexpr unsigned int MED_SCALE = 2;
99102
/** Track confirm delays up to 1008 blocks for longer decay */
100-
static constexpr unsigned int LONG_BLOCK_CONFIRMS = 1008;
103+
static constexpr unsigned int LONG_BLOCK_PERIODS = 42;
104+
static constexpr unsigned int LONG_SCALE = 24;
101105
/** Historical estimates that are older than this aren't valid */
102106
static const unsigned int OLDEST_ESTIMATE_HISTORY = 6 * 1008;
103107

‎src/rpc/mining.cpp‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -895,6 +895,7 @@ UniValue estimaterawfee(const JSONRPCRequest& request)
895895
"{\n"
896896
" \"feerate\" : x.x, (numeric) estimate fee-per-kilobyte (in BTC)\n"
897897
" \"decay\" : x.x, (numeric) exponential decay (per block) for historical moving average of confirmation data\n"
898+
" \"scale\" : x, (numeric) The resolution of confirmation targets at this time horizon\n"
898899
" \"pass.\" information about the lowest range of feerates to succeed in meeting the threshold\n"
899900
" \"fail.\" information about the highest range of feerates to fail to meet the threshold\n"
900901
" \"startrange\" : x.x, (numeric) start of feerate range\n"
@@ -932,6 +933,7 @@ UniValue estimaterawfee(const JSONRPCRequest& request)
932933

933934
result.push_back(Pair("feerate", feeRate == CFeeRate(0) ? -1.0 : ValueFromAmount(feeRate.GetFeePerK())));
934935
result.push_back(Pair("decay", buckets.decay));
936+
result.push_back(Pair("scale", (int)buckets.scale));
935937
result.push_back(Pair("pass.startrange", round(buckets.pass.start)));
936938
result.push_back(Pair("pass.endrange", round(buckets.pass.end)));
937939
result.push_back(Pair("pass.withintarget", round(buckets.pass.withinTarget * 100.0) / 100.0));

‎src/test/policyestimator_tests.cpp‎

Lines changed: 2 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -99,13 +99,10 @@ BOOST_AUTO_TEST_CASE(BlockPolicyEstimates)
9999
BOOST_CHECK(origFeeEst[i-1] <= origFeeEst[i-2]);
100100
}
101101
int mult = 11-i;
102-
if (i > 1) {
102+
if (i % 2 == 0) { //At scale 2, test logic is only correct for even targets
103103
BOOST_CHECK(origFeeEst[i-1] < mult*baseRate.GetFeePerK() + deltaFee);
104104
BOOST_CHECK(origFeeEst[i-1] > mult*baseRate.GetFeePerK() - deltaFee);
105105
}
106-
else {
107-
BOOST_CHECK(origFeeEst[i-1] == CFeeRate(0).GetFeePerK());
108-
}
109106
}
110107
// Fill out rest of the original estimates
111108
for (int i = 10; i <= 48; i++) {
@@ -177,7 +174,7 @@ BOOST_AUTO_TEST_CASE(BlockPolicyEstimates)
177174
block.clear();
178175
}
179176
BOOST_CHECK(feeEst.estimateFee(1) == CFeeRate(0));
180-
for (int i = 2; i < 10; i++) {
177+
for (int i = 2; i < 9; i++) { // At 9, the original estimate was already at the bottom (b/c scale = 2)
181178
BOOST_CHECK(feeEst.estimateFee(i).GetFeePerK() < origFeeEst[i-1] - deltaFee);
182179
}
183180

0 commit comments

Comments
 (0)