GO-HPB源码解读--投票机制

发表于 | 分类于

在挖矿流程的最近一节中，提到了voting.GetHpbNodeSnap的投票机制。投票的目的就是来计算出本节点是否能够签名区块，所以每次在组装区块的时候都会获取上一次的投票结果，如果出现异常或者投票周期到了，则重新计算投票结果。
投票结果是通过结构体进行保存的。
CandAddress 节点地址(当前的授权用户)
VoteNumbers 获得票数
VoteIndexs 获胜者的指标总和
VotePercent 占比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
type Tally struct {
	CandAddress common.Address `json:"candAddress"` // 通过投票的个数
	VoteNumbers *big.Int       `json:"voteNumbers"` // 通过投票的个数
	VoteIndexs  *big.Int       `json:"voteIndexs"`  // 通过投票的个数
	VotePercent *big.Int       `json:"votePercent"` // 通过投票的个数
}

<!-- more -->

type HpbNodeSnap struct {
	config   *config.PrometheusConfig
	sigcache *lru.ARCCache
	//Number  uint64                      `json:"number"`  // 生成快照的时间点
	CheckPointNum  uint64                      `json:"checkPointNum"`  // 最近的检查点
	CheckPointHash common.Hash                 `json:"checkPointHash"` // 生成快照的Block hash
	Signers        map[common.Address]struct{} `json:"signers"`        // 当前的授权用户
	Recents        map[uint64]common.Address   `json:"recents"`        // 最近签名者 spam
	Tally          map[common.Address]Tally    `json:"tally"`          // 目前的计票情况
}

接下来看一下代码实现，其中HpbNodeCheckpointInterval==200

  1. 如果number==0，就先生成一个初始快照并返回
  2. 如果number<200，就从缓存/数据库中取出初始快照，如果取出失败，则生成一个初始快照并返回
  3. 其他情况就是number>=200，如果number正好是200的整数倍数的话，则生成快照，否则从缓存/数据库中获取上一次的快照，如果获取失败则重新生成上一次的快照。举个栗子，number=666，则获取number=600的快照，如果number=800，则生成新的快照。很明显间隔相当于从0开始算的，并不是最近的200个块。但是。。。往下看number是怎么使用的
    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
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    func GetHpbNodeSnap(db hpbdb.Database, recents *lru.ARCCache, signatures *lru.ARCCache, config *config.PrometheusConfig, chain consensus.ChainReader, number uint64, hash common.Hash, parents []*types.Header) (*snapshots.HpbNodeSnap, error) {

    	// 首次要创建
    	if number == 0 {
    		if snapg, err := GenGenesisSnap(db, recents, signatures, config, chain); err == nil {
    			return snapg, err
    		}
    	}

    	//前十轮不会进行投票，前10轮采用区块0时候的数据
    	//先获取缓存，如果缓存中没有则获取数据库，为了提升速度
    	//if(true){
    	if number < consensus.HpbNodeCheckpointInterval {
    		genesis := chain.GetHeaderByNumber(0)
    		hash := genesis.Hash()
    		// 从缓存中获取
    		if snapcd, err := GetDataFromCacheAndDb(db, recents, signatures, config, hash); err == nil {
    			log.Debug("HPB_VOTING： Loaded voting Hpb Node Snap form cache and db", "number", number, "hash", hash)
    			return snapcd, err
    		} else {
    			if snapg, err := GenGenesisSnap(db, recents, signatures, config, chain); err == nil {
    				log.Debug("HPB_VOTING： Loaded voting Hpb Node Snap form genesis snap", "number", number, "hash", hash)
    				return snapg, err
    			}
    		}
    	}

    	// 开始考虑10轮之后的情况，往前回溯3轮，以保证一致性。
    	// 开始计算最后一次的确认区块
    	latestCheckPointNumber := uint64(math.Floor(float64(number/consensus.HpbNodeCheckpointInterval))) * consensus.HpbNodeCheckpointInterval
    	//log.Error("Current latestCheckPointNumber in hpb voting:",strconv.FormatUint(latestCheckPointNumber, 10))

    	header := chain.GetHeaderByNumber(uint64(latestCheckPointNumber))
    	latestCheckPointHash := header.Hash()

    	if number%consensus.HpbNodeCheckpointInterval != 0 {
    		if snapcd, err := GetDataFromCacheAndDb(db, recents, signatures, config, latestCheckPointHash); err == nil {
    			//log.Info("##########################HPB_VOTING： Loaded voting Hpb Node Snap form cache and db", "number", number, "latestCheckPointNumber", latestCheckPointNumber)
    			return snapcd, err
    		} else {
    			if snapa, err := snapshots.CalculateHpbSnap(uint64(1), signatures, config, number, latestCheckPointNumber, latestCheckPointHash, chain); err == nil {
    				//log.Info("@@@@@@@@@@@@@@@@@@@@@@@@HPB_VOTING： CalculateHpbSnap", "number", number, "latestCheckPointNumber", latestCheckPointNumber)
    				if err := StoreDataToCacheAndDb(recents, db, snapa, latestCheckPointHash); err != nil {
    					return nil, err
    				}
    				return snapa, err
    			}
    		}
    	} else {
    		if snapa, err := snapshots.CalculateHpbSnap(uint64(1), signatures, config, number, latestCheckPointNumber, latestCheckPointHash, chain); err == nil {
    			//log.Info("@@@@@@@@@@@@@@@@@@@@@@@@HPB_VOTING： CalculateHpbSnap", "number", number, "latestCheckPointNumber", latestCheckPointNumber)
    			//新轮次计算完高性能节点立即更新节点类型
    			//prometheus.SetNetNodeType(snapa)
    			if err := StoreDataToCacheAndDb(recents, db, snapa, latestCheckPointHash); err != nil {
    				return nil, err
    			}
    			return snapa, err
    		} else {
    			return nil, err
    		}
    	}

    	return nil, nil
    }

具体生成快照的算法是在CalculateHpbSnap中实现的，也就是区块链核的共识算法。先看一下参数含意：
字段|类型|含义|备注
-|-|-|-
index | |投票轮次，CalculateHpbSnap调用时是第一次，所以传1 |
*lru | |最近的签名，使用ARC算法实现 |
config | |共识配置，Prometheus的属性 |
number | |区块序号 |
latestCheckPointNum |最近应该生成快照对应的区块序号，也就是200的整数倍 | |
latestCheckPointHash |最近应该生成快照对应的区块哈希 | |
chain |区块链指针 | |

快照生成主要通过number参数选举出一定的区块生成节点，这块要主算法实现，为了方便理解，假设在生成区块时的number为210、650、1875，也就是调用GetHpbNodeSnap方法传入的number，表示为{210|650|1875}，最后计算得到latestCheckPointNum是{200|600|1800}，将这两个参数传入CalculateHpbSnap，注意此时index传入的是1

  1. 选出一定范围内的区块头集合，区间界线为from到latestCheckPointNum-100，from计算方法是latestCheckPointNum - index*consensus.HpbNodeCheckpointInterval，所以可以得到的范围是{0-100|400-500|1600-1700}
  2. 通过chain取出{0-100|400-500|1600-1700}范围内所有区块头，赋给headers变量，一共100个区块头（理想情况下）。如果在获取头的时候累计出了20次没取到，直接返回异常errors.New(“get hpb snap but missing header”)
  3. 对区块头集合headers进行连续性检查，也就是所有区块头的number必须是连续的，否则返回异常
  4. 初始化快照对象snap，并填装snap的Tally属性，注意snap的Tally是map[common.Address]Tally类型的，key是add，value是Tally，而value的类型Tally本身又是一个结构体。填装过程就是把header对应的所有address作为键put到map中，value是Tally结构体。
    *Tally初始值是
    VoteNumbers: 1,
        VoteIndexs:  header.VoteIndex,
        VotePercent: header.VoteIndex,
    *如果key重复出现，则需要把VoteNumbers和VoteIndexs对应的新旧值进行累加，重新计算VotePercent=VoteIndexs/VoteNumbers并赋值
    这样就得到了100一个header对应的address的Tally，当然结果可能会少于100个，因为有重复的。
  5. 将map再复制到临时变量tallytemp中，分别按照CandAddress和百分比VotePercent从小到大进行排序，排序结果保存到变更finaltally中
  6. 接下来通过当前高性能节点数量来解决是否需要再次进行获取一些headers来进行投票计算，也就是上边1-5步骤
  7. 系统默认的高性能节点个数是consensus.HpbNodenumber=31个，如果finaltally长度大等于31，则把排序后的后边的31个节点地址添加到snap.Signers中，即授权用户，表示可以进行挖矿。
  8. 如果finaltally小于31，而且已经进行了4次投票计算（1-5步骤），就把finaltally中所有的地址进行授权
  9. 如果finaltally小于31，而且进行了不到4次投票计算，则往前回溯再取出一些区块头（地址）进行投票。但是往前回溯有个条件，就是前边有足够的区块头可以获取，如果前边的区块头不够充足了，则只能把当前finaltally的地址全部授权了。是否可以往前回溯的判断条件是index<number/200，比如第一轮投票的时候number={210|650|1875}，投了{0-100|400-500|1600-1700}区间的节点地址，最终结果不够31个高性能节点，那么进行第二轮投票。2<210/200为false，这种情况就不能往前回溯了；2<650/200为true，则可以回溯，然后递归调用CalculateHpbSnap方法，这时传入的index=2，number和latestCheckPointNum分别向前移200个单位，即number={-|450|1675}，latestCheckPointNum={-|400|1600}，递归后可得范围为 {-|200-300|1400-1500}。可以发现每次中间隔100个单位。
  10. 在进行了下一投票计算（递归调用）之后，得到新的节点地址集合，把其中已经存在于上一次finaltally中的地址删除掉，此时如果新的节点地址一个也没有，则结束投票，如果还有的话就对新的节点地址集合进行排序
  11. 排序完了之后，如果新旧集合的长度和小等于31，就把新旧集合合并一下，否则的话把新集合的数据补充到旧集合中，直到旧集合够31个节点了。
  12. 最后把zeroaddr地址删除掉。（不是很清楚，什么情况下会有存在zeroaddr地址）
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
func CalculateHpbSnap(index uint64, signatures *lru.ARCCache, config *config.PrometheusConfig, number uint64, latestCheckPointNum uint64, latestCheckPointHash common.Hash, chain consensus.ChainReader) (*HpbNodeSnap, error) {
	// Allow passing in no headers for cleaner code

	var headers []*types.Header

	// 开始获取之前的所有header
	var from = latestCheckPointNum - index*consensus.HpbNodeCheckpointInterval
	if from == 0 {
		from = from + 1
	}
	for i := from; i < latestCheckPointNum-100; i++ {
		loopcount := 0
	GETCOUNT:
		header := chain.GetHeaderByNumber(uint64(i))
		if header != nil {
			headers = append(headers, header)
		} else {
			if loopcount > 20 {
				return nil, errors.New("get hpb snap but missing header")
			}
			loopcount += 1
			goto GETCOUNT
			//log.Error("get hpb snap but missing header", "number", i)
		}
	}

	// 如果头部为空，直接返回
	if len(headers) == 0 {
		return nil, errors.New("Calculate Hpb Snap headers is 0 ")
	}

	// 检查所有的头部，检查连续性
	for i := 0; i < len(headers)-1; i++ {
		if headers[i+1].Number.Uint64() != headers[i].Number.Uint64()+1 {
			return nil, consensus.ErrInvalidVotingChain
		}
	}

	//signers := make([]common.Address, 0, consensus.HpbNodenumber)
	snap := NewHistorysnap(config, signatures, number, latestCheckPointNum, latestCheckPointHash, nil)
	snap.Tally = make(map[common.Address]Tally)

	for _, header := range headers {

		VoteNumberstemp := big.NewInt(0)
		VoteIndexstemp := big.NewInt(0)
		VotePercenttemp := big.NewInt(0)
		//票的数量与性能之间的关系，获取票的数量表示在线时间长度，所以应该选择在线时间长性能又好的节点。
		if old, ok := snap.Tally[header.CandAddress]; ok {
			VoteNumberstemp.Add(old.VoteNumbers, big.NewInt(1))
			VoteIndexstemp.Add(old.VoteIndexs, header.VoteIndex)
			VotePercenttemp.Div(VoteIndexstemp, VoteNumberstemp)
			snap.Tally[header.CandAddress] = Tally{
				VoteNumbers: VoteNumberstemp,
				VoteIndexs:  VoteIndexstemp,
				VotePercent: VotePercenttemp,
				CandAddress: header.CandAddress,
			}
		} else {
			snap.Tally[header.CandAddress] = Tally{
				VoteNumbers: big.NewInt(1),
				VoteIndexs:  header.VoteIndex,
				VotePercent: header.VoteIndex,
				CandAddress: header.CandAddress,
			}
		}
	}

	var tallytemp []Tally
	for _, v := range snap.Tally {
		tallytemp = append(tallytemp, v)
	}

	for i := 0; i < len(snap.Tally); i++ {
		for j := 0; j < len(snap.Tally)-i-1; j++ {
			if bytes.Compare(tallytemp[j].CandAddress[:], tallytemp[j+1].CandAddress[:]) > 0 {
				tallytemp[j], tallytemp[j+1] = tallytemp[j+1], tallytemp[j]
			}
		}
	}

	for i := 0; i < len(snap.Tally); i++ {
		for j := 0; j < len(snap.Tally)-i-1; j++ {
			if tallytemp[j].VotePercent.Cmp(tallytemp[j+1].VotePercent) > 0 {
				tallytemp[j], tallytemp[j+1] = tallytemp[j+1], tallytemp[j]
			} else if (tallytemp[j].VotePercent.Cmp(tallytemp[j+1].VotePercent) == 0) && (bytes.Compare(tallytemp[j].CandAddress[:], tallytemp[j+1].CandAddress[:]) > 0) {
				tallytemp[j], tallytemp[j+1] = tallytemp[j+1], tallytemp[j]
			}
		}
	}

	finaltally := make([]common.Address, 0, len(tallytemp))
	for _, v := range tallytemp {
		finaltally = append(finaltally, v.CandAddress)
	}

	var hpnodeNO int
	if len(finaltally) >= consensus.HpbNodenumber {
		hpnodeNO = consensus.HpbNodenumber
		goto END

	} else {
		if index == consensus.Hpcalclookbackround+1 { //look back round is consensus.Hpcalclookbackround
			hpnodeNO = len(finaltally)
			goto END
		}

		index = index + 1
		if index < uint64(math.Floor(float64(number/consensus.HpbNodeCheckpointInterval))) { // 往前回溯
			//log.Error("-------- go back for last snap------------", "index", index)
			header := chain.GetHeaderByNumber(uint64(latestCheckPointNum - consensus.HpbNodeCheckpointInterval))
			latestCheckPointHash := header.Hash()
			snaptemp, err := CalculateHpbSnap(index, signatures, config, number-consensus.HpbNodeCheckpointInterval, latestCheckPointNum-consensus.HpbNodeCheckpointInterval, latestCheckPointHash, chain)
			if err != nil {
				log.Debug("recursive call CalculateHpbSnap fail", "err", err)
				hpnodeNO = len(finaltally)
				goto END
			}
			//get last snap hp nodes, set in map
			hpsmaptemp := make(map[common.Address]struct{})
			lastsnap := snaptemp.GetHpbNodes()
			for _, v := range lastsnap {
				hpsmaptemp[v] = struct{}{}
			}
			//delete tallytemp.CandAddress in the map
			for _, v := range finaltally {
				if _, ok := hpsmaptemp[v]; ok {
					delete(hpsmaptemp, v)
				}
			}

			if 0 == len(hpsmaptemp) {
				hpnodeNO = len(finaltally)
				goto END
			}
			//order the hpsmaptemp by put it into []common.address
			delhpsmap := make([]common.Address, len(hpsmaptemp))
			for key, _ := range hpsmaptemp {
				delhpsmap = append(delhpsmap, key)
			}

			//sort by addr
			if 1 < len(delhpsmap) {
				for i := 0; i < len(delhpsmap); i++ {
					for j := 0; j < len(delhpsmap)-i-1; j++ {
						if bytes.Compare(delhpsmap[j][:], delhpsmap[j+1][:]) > 0 {
							delhpsmap[j], delhpsmap[j+1] = delhpsmap[j+1], delhpsmap[j]
						}
					}
				}
			}

			//calc how many last snap hps needing to add the latest snap
			if len(finaltally)+len(delhpsmap) > consensus.HpbNodenumber {
				for i := 0; i < consensus.HpbNodenumber-len(finaltally); i++ {
					finaltally = append(finaltally, delhpsmap[i])
				}
			} else {
				for i := 0; i < len(delhpsmap); i++ {
					finaltally = append(finaltally, delhpsmap[i])
				}
			}

		}
		hpnodeNO = len(finaltally)
	}

END:
	for i := len(finaltally) - 1; i > len(finaltally)-hpnodeNO-1; i-- {
		snap.Signers[finaltally[i]] = struct{}{}
	}

	zeroaddr := common.HexToAddress("0x0000000000000000000000000000000000000000")
	if _, ok := snap.Signers[zeroaddr]; ok {
		delete(snap.Signers, zeroaddr)
	}

	return snap, nil
}

在确定节点地址区间的逻辑比较简单,就是从前往后，隔100,标记100个为可取的,然后从后往前取倒数第一个100，去重后够31个就可以了，不够了再取倒数第2个100。代码算法写的复杂了，还用了递归。。。。。

VoteIndexs这个是从区块头中取出来的，没找到最初是在哪儿set进去的。

真累人………