aboutsummaryrefslogtreecommitdiffstats
path: root/core
diff options
context:
space:
mode:
authorPéter Szilágyi <peterke@gmail.com>2016-01-22 18:05:17 +0800
committerPéter Szilágyi <peterke@gmail.com>2016-01-22 18:33:34 +0800
commita2dc074b1ddffaf4e35758835bafe14cca5f0ea7 (patch)
treeb9aa5c904aea0962eb7c103896b6a4ef4c32971c /core
parent78f196409552466ff878a030e4069495a923c73e (diff)
downloadgo-tangerine-a2dc074b1ddffaf4e35758835bafe14cca5f0ea7.tar.gz
go-tangerine-a2dc074b1ddffaf4e35758835bafe14cca5f0ea7.tar.zst
go-tangerine-a2dc074b1ddffaf4e35758835bafe14cca5f0ea7.zip
core, core/types, miner: fix transaction nonce-price combo sort
Diffstat (limited to 'core')
-rw-r--r--core/transaction_pool.go2
-rw-r--r--core/types/transaction.go85
-rw-r--r--core/types/transaction_test.go57
3 files changed, 127 insertions, 17 deletions
diff --git a/core/transaction_pool.go b/core/transaction_pool.go
index abd5bb7b7..54c0ddebb 100644
--- a/core/transaction_pool.go
+++ b/core/transaction_pool.go
@@ -376,7 +376,7 @@ func (self *TxPool) GetQueuedTransactions() types.Transactions {
ret = append(ret, tx)
}
}
- sort.Sort(types.TxByNonce{ret})
+ sort.Sort(types.TxByNonce(ret))
return ret
}
diff --git a/core/types/transaction.go b/core/types/transaction.go
index 7a6c5e088..4049ae888 100644
--- a/core/types/transaction.go
+++ b/core/types/transaction.go
@@ -17,11 +17,13 @@
package types
import (
+ "container/heap"
"crypto/ecdsa"
"errors"
"fmt"
"io"
"math/big"
+ "sort"
"sync/atomic"
"github.com/ethereum/go-ethereum/common"
@@ -302,27 +304,78 @@ func TxDifference(a, b Transactions) (keep Transactions) {
return keep
}
-type TxByNonce struct{ Transactions }
+// TxByNonce implements the sort interface to allow sorting a list of transactions
+// by their nonces. This is usually only useful for sorting transactions from a
+// single account, otherwise a nonce comparison doesn't make much sense.
+type TxByNonce Transactions
-func (s TxByNonce) Less(i, j int) bool {
- return s.Transactions[i].data.AccountNonce < s.Transactions[j].data.AccountNonce
-}
+func (s TxByNonce) Len() int { return len(s) }
+func (s TxByNonce) Less(i, j int) bool { return s[i].data.AccountNonce < s[j].data.AccountNonce }
+func (s TxByNonce) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
+
+// TxByPrice implements both the sort and the heap interface, making it useful
+// for all at once sorting as well as individually adding and removing elements.
+type TxByPrice Transactions
-type TxByPrice struct{ Transactions }
+func (s TxByPrice) Len() int { return len(s) }
+func (s TxByPrice) Less(i, j int) bool { return s[i].data.Price.Cmp(s[j].data.Price) > 0 }
+func (s TxByPrice) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
-func (s TxByPrice) Less(i, j int) bool {
- return s.Transactions[i].data.Price.Cmp(s.Transactions[j].data.Price) > 0
+func (s *TxByPrice) Push(x interface{}) {
+ *s = append(*s, x.(*Transaction))
}
-type TxByPriceAndNonce struct{ Transactions }
+func (s *TxByPrice) Pop() interface{} {
+ old := *s
+ n := len(old)
+ x := old[n-1]
+ *s = old[0 : n-1]
+ return x
+}
-func (s TxByPriceAndNonce) Less(i, j int) bool {
- // we can ignore the error here. Sorting shouldn't care about validness
- ifrom, _ := s.Transactions[i].From()
- jfrom, _ := s.Transactions[j].From()
- // favour nonce if they are from the same recipient
- if ifrom == jfrom {
- return s.Transactions[i].data.AccountNonce < s.Transactions[j].data.AccountNonce
+// SortByPriceAndNonce sorts the transactions by price in such a way that the
+// nonce orderings within a single account are maintained.
+//
+// Note, this is not as trivial as it seems from the first look as there are three
+// different criteria that need to be taken into account (price, nonce, account
+// match), which cannot be done with any plain sorting method, as certain items
+// cannot be compared without context.
+//
+// This method first sorts the separates the list of transactions into individual
+// sender accounts and sorts them by nonce. After the account nonce ordering is
+// satisfied, the results are merged back together by price, always comparing only
+// the head transaction from each account. This is done via a heap to keep it fast.
+func SortByPriceAndNonce(txs []*Transaction) {
+ // Separate the transactions by account and sort by nonce
+ byNonce := make(map[common.Address][]*Transaction)
+ for _, tx := range txs {
+ acc, _ := tx.From() // we only sort valid txs so this cannot fail
+ byNonce[acc] = append(byNonce[acc], tx)
+ }
+ for _, accTxs := range byNonce {
+ sort.Sort(TxByNonce(accTxs))
+ }
+ // Initialize a price based heap with the head transactions
+ byPrice := make(TxByPrice, 0, len(byNonce))
+ for acc, accTxs := range byNonce {
+ byPrice = append(byPrice, accTxs[0])
+ byNonce[acc] = accTxs[1:]
+ }
+ heap.Init(&byPrice)
+
+ // Merge by replacing the best with the next from the same account
+ txs = txs[:0]
+ for len(byPrice) > 0 {
+ // Retrieve the next best transaction by price
+ best := heap.Pop(&byPrice).(*Transaction)
+
+ // Push in its place the next transaction from the same account
+ acc, _ := best.From() // we only sort valid txs so this cannot fail
+ if accTxs, ok := byNonce[acc]; ok && len(accTxs) > 0 {
+ heap.Push(&byPrice, accTxs[0])
+ byNonce[acc] = accTxs[1:]
+ }
+ // Accumulate the best priced transaction
+ txs = append(txs, best)
}
- return s.Transactions[i].data.Price.Cmp(s.Transactions[j].data.Price) > 0
}
diff --git a/core/types/transaction_test.go b/core/types/transaction_test.go
index 1c0e27d9a..62420e71f 100644
--- a/core/types/transaction_test.go
+++ b/core/types/transaction_test.go
@@ -117,3 +117,60 @@ func TestRecipientNormal(t *testing.T) {
t.Error("derived address doesn't match")
}
}
+
+// Tests that transactions can be correctly sorted according to their price in
+// decreasing order, but at the same time with increasing nonces when issued by
+// the same account.
+func TestTransactionPriceNonceSort(t *testing.T) {
+ // Generate a batch of accounts to start with
+ keys := make([]*ecdsa.PrivateKey, 25)
+ for i := 0; i < len(keys); i++ {
+ keys[i], _ = crypto.GenerateKey()
+ }
+ // Generate a batch of transactions with overlapping values, but shifted nonces
+ txs := []*Transaction{}
+ for start, key := range keys {
+ for i := 0; i < 25; i++ {
+ tx, _ := NewTransaction(uint64(start+i), common.Address{}, big.NewInt(100), big.NewInt(100), big.NewInt(int64(start+i)), nil).SignECDSA(key)
+ txs = append(txs, tx)
+ }
+ }
+ // Sort the transactions and cross check the nonce ordering
+ SortByPriceAndNonce(txs)
+ for i, txi := range txs {
+ fromi, _ := txi.From()
+
+ // Make sure the nonce order is valid
+ for j, txj := range txs[i+1:] {
+ fromj, _ := txj.From()
+
+ if fromi == fromj && txi.Nonce() > txj.Nonce() {
+ t.Errorf("invalid nonce ordering: tx #%d (A=%x N=%v) < tx #%d (A=%x N=%v)", i, fromi[:4], txi.Nonce(), i+j, fromj[:4], txj.Nonce())
+ }
+ }
+ // Find the previous and next nonce of this account
+ prev, next := i-1, i+1
+ for j := i - 1; j >= 0; j-- {
+ if fromj, _ := txs[j].From(); fromi == fromj {
+ prev = j
+ break
+ }
+ }
+ for j := i + 1; j < len(txs); j++ {
+ if fromj, _ := txs[j].From(); fromi == fromj {
+ next = j
+ break
+ }
+ }
+ // Make sure that in between the neighbor nonces, the transaction is correctly positioned price wise
+ for j := prev + 1; j < next; j++ {
+ fromj, _ := txs[j].From()
+ if j < i && txs[j].GasPrice().Cmp(txi.GasPrice()) < 0 {
+ t.Errorf("invalid gasprice ordering: tx #%d (A=%x P=%v) < tx #%d (A=%x P=%v)", j, fromj[:4], txs[j].GasPrice(), i, fromi[:4], txi.GasPrice())
+ }
+ if j > i && txs[j].GasPrice().Cmp(txi.GasPrice()) > 0 {
+ t.Errorf("invalid gasprice ordering: tx #%d (A=%x P=%v) > tx #%d (A=%x P=%v)", j, fromj[:4], txs[j].GasPrice(), i, fromi[:4], txi.GasPrice())
+ }
+ }
+ }
+}