1. 交易的签名
  2. 理解收据receipt
  3. 理解区块
  4. 理解交易
  5. blockchain核心
  6. forkId 解读
  7. oracle 原理和实现
  8. 交易池分析
  9. 布隆过滤器原理
  10. TxList 解读
  11. MPT树
  12. 区块同步
  13. geth源码学习——介绍
  14. How Geth starts its server

本文旨在分析清楚 tx_list.go 中这个工具包里面的重要代码

堆排序

以下为tx_list.go中的heap.Interface的全部实现代码，非常标准，和默认的一样；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//heap的整个实现过程
type nonceHeap []uint64

func (h nonceHeap) Len() int           { return len(h) }
func (h nonceHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h nonceHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *nonceHeap) Push(x interface{}) {
	*h = append(*h, x.(uint64))
}

func (h *nonceHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

以下展示heap.Interface的结构：

1
2
3
4
5
type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}

其中sort.Interface这个接口里包含Len() Less() Swap()这三个方法，也就是对应上面的前三个方法；

加上后面的Push() Pop()两个方法，也就是我们实现了heap.Interface这个接口；

然后我们就可以使用heap包里面的相关功能性函数（因为他们的参数要求基本上都包含heap.Interface这个接口)，heap包代码量非常少，算上注释才一百多行，很容易也推荐看完；

在这里附上一段试验的源码以供参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package main

import (
	"container/heap"
	"fmt"
	"sort"
)

type intHeap []int

func (a intHeap) Len() int           { return len(a) }
func (a intHeap) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a intHeap) Less(i, j int) bool { return a[i] < a[j] }

func (s *intHeap) Push(x interface{}) {
	*s = append(*s, x.(int))
}

func (s *intHeap) Pop() interface{} {
	old := *s
	n := len(old)
	x := old[n-1]
	*s = old[0 : n-1]
	return x
}
func main() {
	//必须要是初始化为指针类型的 这样才算是实现了该接口 因为上面的参数有指针类型的
	res := &intHeap{2,1,4,6,3}
	//s:=heap.Interface(res)
	heap.Init(res)
	fmt.Println(res)
	heap.Push(res,3)
	fmt.Println(res)
	fmt.Println((*res)[4])
	sort.Sort(res)
	fmt.Println(res)
}

函数功能解析

txSortedMap

具体的结构如下：

1
2
3
4
5
6
type txSortedMap struct {
	//建立一个nonce->transaction的map
	items map[uint64]*types.Transaction // Hash map storing the transaction data
	index *nonceHeap                    // Heap of nonces of all the stored transactions (non-strict mode)
	cache types.Transactions            // Cache of the transactions already sorted
}

以下为其对应的所有方法：

  1. newTxSortedMap() 进行初始化并返回初始化后的*txSortedMap

  2. Get(nonce uint64)获取指定nonce的交易并返回该笔交易

  3. Put(tx *types.transaction)将该笔交易该笔交易添加到txSortedMap中，无论之前是否存在

  4. Foward(threshold uint64)将低于这个门槛的nonce的交易全部剔除

  5. reheap()根据当前的map重新进行nonceheap的排序

  6. filter(filter func(*types.Transaction) bool)其中的参数filter func(*types.Transaction) bool)

    它的源码是func(tx *types.Transaction) bool { return tx.Nonce() > lowest }

    我们可以发现该函数的作用其实为了过滤nonce小于最低要求的交易，而Filter(filter func(*types.Transaction) bool)调用了以上的函数，所以功能差不多

  7. Cap(threshold int)如果该map中的交易数量超过了限制，就删除最高nonce的交易直至数量达到要求，并返回删除掉的drops

  8. Remove(nonce uint64)删除成功则返回true,没有找到就返回false

  9. Ready(start uint64)准备好nonce高于start并且连续的交易

  10. Len()返回map的大小

  11. Flatten()获取全部的交易，flatten()将全部按照nonce排序好的交易进行缓存

  12. LastElement()返回cashe中nonce值最高的交易

txList

具体结构如下：

1
2
3
4
5
6
7
8
9
type txList struct {
    //nonce是否严格连续
	strict bool         // Whether nonces are strictly continuous or not
	//nonce
    txs    *txSortedMap // Heap indexed sorted hash map of the transactions

	costcap *big.Int // Price of the highest costing transaction (reset only if exceeds balance)
	gascap  uint64   // Gas limit of the highest spending transaction (reset only if exceeds block limit)
}

重要函数如下：

  1. Overlaps(tx *types.Transaction)若是已有这笔交易就返回true，否则返回false
  2. Add(tx *types.Transaction,priceBump uint64)若是已有这笔交易就尝试加入，不存在就直接加入，返回交易true old
  3. Filter(costLimit *big.Int,gasLimit uint64)过滤掉拥有过高的cost或者gas的交易，同时过滤掉后面nonce不连续的交易
  4. Remove(tx *types.Transaction)尝试移除掉指定的交易并移除后面nonce值不连续的交易

priceHeap

具体结构如下：

1
2
3
4
type priceHeap struct {
	baseFee *big.Int // heap should always be re-sorted after baseFee is changed
	list    []*types.Transaction
}

实现了heap.Interface这个接口，排序方式是先比较gasFee,再之tipFee

txPricedList

具体结构如下：

1
2
3
4
5
6
7
8
type txPricedList struct {
    //一个过时的计数器
	stales int64

	all              *txLookup  // Pointer to the map of all transactions
	urgent, floating priceHeap  // Heaps of prices of all the stored **remote** transactions
	reheapMu         sync.Mutex // Mutex asserts that only one routine is reheaping the list
}

首先提一下，本部分源码中大量使用了原子操作，Go语言中提供的原子操作都是非侵入式的，在标准库代码包sync/atomic中提供了相关的原子函数,具体功能如下：

原子操作即是进行过程中不能被中断的操作，针对某个值的原子操作在被进行的过程中，CPU 绝不会再去进行其他的针对该值的操作。为了实现这样的严谨性，原子操作仅会由一个独立的 CPU 指令代表和完成。原子操作是无锁的，常常直接通过 CPU 指令直接实现。 事实上，其它同步技术的实现常常依赖于原子操作。

现在理解不来为何 priceHeap里要有urgent 和 floating这两个 ，（注意：应该是新增的，网上找不到资料；）