Skip to content

Commit 7c0c507

Browse files
jangkojangko
authored
TxPool: simplify byPriceAndNonce algorithm (#2978)
Remove the intermediate bySender table usage. This will lower the memory and CPU usage. Also add more comments about how algorithm works.
1 parent 5182a08 commit 7c0c507

3 files changed

Lines changed: 99 additions & 43 deletions

File tree

‎nimbus/core/tx_pool.nim‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,32 @@
88
# at your option. This file may not be copied, modified, or distributed except
99
# according to those terms.
1010

11+
## Pool coding
12+
## ===========
13+
## A piece of code using this pool architecture could look like as follows:
14+
## ::
15+
## # see also unit test examples, e.g. "Block packer tests"
16+
## var chain: ForkedChainRef # to be initialised
17+
##
18+
##
19+
## var xp = TxPoolRef.new(chain) # initialise tx-pool
20+
## ..
21+
##
22+
## xq.addTx(txs) # add transactions ..
23+
## .. # .. into the buckets
24+
##
25+
## let bundle = xp.assembleBlock # fetch current block
26+
##
27+
## xp.removeNewBlockTxs(bundle.blk) # remove used transactions
28+
##
29+
## Why not remove used transactions in `assembleBlock`?
30+
## ::
31+
## There is probability the block we proposed is rejected by
32+
## by network or other client produce an accepted block.
33+
## The block param passed through `removeNewBlockTxs` can be
34+
## a block newer than the the one last produced by `assembleBlock`.
35+
36+
1137
{.push raises: [].}
1238

1339
import

‎nimbus/core/tx_pool/tx_desc.nim‎

Lines changed: 13 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -293,6 +293,19 @@ proc addTx*(xp: TxPoolRef, ptx: PooledTransaction): Result[void, TxError] =
293293
return err(txErrorInvalidSignature)
294294
nonce = xp.getNonce(sender)
295295

296+
# The downside of this arrangement is the ledger is not
297+
# always up to date. The comparison below
298+
# does not always filter out transactions with lower nonce.
299+
# But it will not affect the correctness of the subsequent
300+
# algorithm. In `byPriceAndNonce`, once again transactions
301+
# with lower nonce are filtered out, for different reason.
302+
# But the end result is same, transactions packed in a block only
303+
# have consecutive nonces >= than current account's nonce.
304+
#
305+
# Calling something like:
306+
# if xp.chain.latestHash != xp.parentHash:
307+
# xp.updateVmState()
308+
# maybe can solve the accuracy but it is quite expensive.
296309
if ptx.tx.nonce < nonce:
297310
return err(txErrorNonceTooSmall)
298311

@@ -313,7 +326,6 @@ proc addTx*(xp: TxPoolRef, ptx: PooledTransaction): Result[void, TxError] =
313326
proc addTx*(xp: TxPoolRef, tx: Transaction): Result[void, TxError] =
314327
xp.addTx(PooledTransaction(tx: tx))
315328

316-
317329
iterator byPriceAndNonce*(xp: TxPoolRef): TxItemRef =
318330
for item in byPriceAndNonce(xp.senderTab, xp.idTab,
319331
xp.vmState.ledger, xp.baseFee):

‎nimbus/core/tx_pool/tx_tabs.nim‎

Lines changed: 60 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -38,66 +38,84 @@ template insertOrReplace*(sn: TxSenderNonceRef, item: TxItemRef) =
3838
sn.list.findOrInsert(item.nonce).
3939
expect("insert txitem ok").data = item
4040

41-
func last*(sn: TxSenderNonceRef): auto =
42-
sn.list.le(AccountNonce.high)
43-
4441
func len*(sn: TxSenderNonceRef): auto =
4542
sn.list.len
4643

4744
iterator byPriceAndNonce*(senderTab: TxSenderTab,
4845
idTab: var TxIdTab,
4946
ledger: LedgerRef,
5047
baseFee: GasInt): TxItemRef =
51-
template removeFirstAndPushTo(sn, byPrice) =
52-
let rc = sn.list.ge(AccountNonce.low).valueOr:
53-
continue
54-
discard sn.list.delete(rc.data.nonce)
55-
byPrice.push(rc.data)
56-
57-
var byNonce: TxSenderTab
58-
for address, sn in senderTab:
59-
var
60-
nonce = ledger.getNonce(address)
61-
sortedByNonce: TxSenderNonceRef
62-
63-
# Remove item with nonce lower than current account.
48+
49+
## This algorithm and comment is taken from ethereumjs but modified.
50+
##
51+
## Returns eligible txs to be packed sorted by price in such a way that the
52+
## nonce orderings within a single account are maintained.
53+
##
54+
## Note, this is not as trivial as it seems from the first look as there are three
55+
## different criteria that need to be taken into account (price, nonce, account
56+
## match), which cannot be done with any plain sorting method, as certain items
57+
## cannot be compared without context.
58+
##
59+
## This method first sorts the list of transactions into individual
60+
## sender accounts and sorts them by nonce.
61+
## -- This is done by senderTab internal algorithm.
62+
##
63+
## After the account nonce ordering is satisfied, the results are merged back
64+
## together by price, always comparing only the head transaction from each account.
65+
## This is done via a heap to keep it fast.
66+
##
67+
## @param baseFee Provide a baseFee to exclude txs with a lower gasPrice
68+
##
69+
70+
template getHeadAndPushTo(sn, byPrice, nonce) =
71+
let rc = sn.list.ge(nonce)
72+
if rc.isOk:
73+
let item = rc.get.data
74+
item.calculatePrice(baseFee)
75+
byPrice.push(item)
76+
77+
# HeapQueue needs `<` to be overloaded for custom object
78+
# and in this case, we want to pop highest price first.
79+
# That's why we use '>' instead of '<' in the implementation.
80+
func `<`(a, b: TxItemRef): bool {.used.} = a.price > b.price
81+
var byPrice = initHeapQueue[TxItemRef]()
82+
83+
# Fill byPrice with `head item` from each account.
84+
# The `head item` is the lowest allowed nonce.
85+
for address, sn in senderTab:
86+
let nonce = ledger.getNonce(address)
87+
88+
# Remove item with nonce lower than current account's nonce.
6489
# Happen when proposed block rejected.
90+
# removeNewBlockTxs will also remove this kind of txs,
91+
# but in a less explicit way. And probably less thoroughly.
92+
# EMV will reject the transaction too, but we filter it here
93+
# for efficiency.
6594
var rc = sn.list.lt(nonce)
6695
while rc.isOk:
6796
let item = rc.get.data
6897
idTab.del(item.id)
6998
discard sn.list.delete(item.nonce)
7099
rc = sn.list.lt(nonce)
71-
72-
# Check if the account nonce matches the lowest known tx nonce
73-
rc = sn.list.ge(nonce)
74-
while rc.isOk:
75-
let item = rc.get.data
76-
item.calculatePrice(baseFee)
77-
78-
if sortedByNonce.isNil:
79-
sortedByNonce = TxSenderNonceRef.init()
80-
byNonce[address] = sortedByNonce
81100

82-
sortedByNonce.insertOrReplace(item)
83-
# If there is a gap, sn.list.eq will return isErr
84-
nonce = item.nonce + 1
85-
rc = sn.list.eq(nonce)
86-
87-
# HeapQueue needs `<` to be overloaded for custom object
88-
# and in this case, we want to pop highest price first
89-
func `<`(a, b: TxItemRef): bool {.used.} = a.price > b.price
90-
var byPrice = initHeapQueue[TxItemRef]()
91-
for _, sn in byNonce:
92-
sn.removeFirstAndPushTo(byPrice)
101+
# Check if the account nonce matches the lowest known tx nonce.
102+
sn.getHeadAndPushTo(byPrice, nonce)
93103

94104
while byPrice.len > 0:
95-
# Retrieve the next best transaction by price
105+
# Retrieve the next best transaction by price.
96106
let best = byPrice.pop()
97107

98-
# Push in its place the next transaction from the same account
99-
let sn = byNonce.getOrDefault(best.sender)
100-
if sn.isNil.not and sn.len > 0:
101-
sn.removeFirstAndPushTo(byPrice)
108+
# Push in its place the next transaction from the same account.
109+
let sn = senderTab.getOrDefault(best.sender)
110+
if sn.isNil.not:
111+
# This algorithm will automatically reject
112+
# transaction with nonce gap(best.nonce + 1)
113+
# EVM will reject this kind transaction too, but
114+
# why do expensive EVM call when we can do it cheaply here.
115+
# We don't remove transactions with gap like we do with transactions
116+
# of lower nonce? because they might be packed by future blocks
117+
# when the gap is filled. Worst case is they will expired and get purged by
118+
# `removeExpiredTxs`
119+
sn.getHeadAndPushTo(byPrice, best.nonce + 1)
102120

103121
yield best

0 commit comments

Comments
 (0)