protocol/consensus_node_manager.go

   1 package protocol
   2
   3 import (
   4         "encoding/hex"
   5         "sort"
   6         "sync"
   7         "time"
   8
   9         "github.com/vapor/errors"
  10         "github.com/vapor/protocol/state"
  11 )
  12
  13 const (
  14         numOfConsensusNode = 21
  15         roundVoteBlockNums = 1000
  16
  17         // BlockTimeInterval indicate product one block per 500 milliseconds
  18         BlockTimeInterval = 500
  19         BlockNumEachNode  = 3
  20 )
  21
  22 var (
  23         errHasNoChanceProductBlock     = errors.New("the node has no chance to product a block in this round of voting")
  24         errNotFoundConsensusNode       = errors.New("can not found consensus node")
  25         errVoteResultIsNotfinalized    = errors.New("vote result is not finalized")
  26         errPublicKeyIsNotConsensusNode = errors.New("public key is not consensus node")
  27 )
  28
  29 type consensusNode struct {
  30         pubkey  string
  31         voteNum uint64
  32         order   uint64
  33 }
  34
  35 type consensusNodeSlice []*consensusNode
  36
  37 func (c consensusNodeSlice) Len() int           { return len(c) }
  38 func (c consensusNodeSlice) Less(i, j int) bool { return c[i].voteNum > c[j].voteNum }
  39 func (c consensusNodeSlice) Swap(i, j int)      { c[i], c[j] = c[j], c[i] }
  40
  41 type consensusNodeManager struct {
  42         consensusNodeMap     map[string]*consensusNode
  43         effectiveStartHeight uint64
  44         store                Store
  45         blockIndex           *state.BlockIndex
  46         sync.RWMutex
  47 }
  48
  49 func newConsensusNodeManager(store Store, blockIndex *state.BlockIndex) *consensusNodeManager {
  50         return &consensusNodeManager{
  51                 consensusNodeMap:     make(map[string]*consensusNode),
  52                 effectiveStartHeight: 1,
  53                 store:                store,
  54                 blockIndex:           blockIndex,
  55         }
  56 }
  57
  58 func (c *consensusNodeManager) getConsensusNode(height uint64, pubkey string) (*consensusNode, error) {
  59         defer c.RUnlock()
  60         c.RLock()
  61         if height >= c.effectiveStartHeight+roundVoteBlockNums {
  62                 return nil, errors.New("the vote has not been completed for the specified block height ")
  63         }
  64
  65         var err error
  66         consensusNodeMap := c.consensusNodeMap
  67         // query history vote result
  68         if height < c.effectiveStartHeight {
  69                 consensusNodeMap, err = c.getConsensusNodesByVoteResult(height)
  70                 if err != nil {
  71                         return nil, err
  72                 }
  73         }
  74
  75         node, exist := consensusNodeMap[pubkey]
  76         if !exist {
  77                 return node, errNotFoundConsensusNode
  78         }
  79         return node, nil
  80 }
  81
  82 func (c *consensusNodeManager) isBlocker(height uint64, blockTimestamp uint64, pubkey string) (bool, error) {
  83         prevVoteRoundLastBlock := c.blockIndex.NodeByHeight(height - 1)
  84         startTimestamp := prevVoteRoundLastBlock.Timestamp + BlockTimeInterval
  85
  86         consensusNodeMap, err := c.getConsensusNodesByVoteResult(height)
  87         if err != nil {
  88                 return false, err
  89         }
  90
  91         blockerNode, exist := consensusNodeMap[pubkey]
  92         if !exist {
  93                 return false, nil
  94         }
  95
  96         begin := getLastBlockTimeInTimeRange(startTimestamp, blockTimestamp, blockerNode.order)
  97         end := begin + BlockNumEachNode*BlockTimeInterval
  98         return blockTimestamp >= begin && blockTimestamp < end, nil
  99 }
 100
 101 func (c *consensusNodeManager) nextLeaderTimeRange(pubkey []byte, bestBlockTimestamp, bestBlockHeight uint64) (uint64, uint64, error) {
 102         defer c.RUnlock()
 103         c.RLock()
 104
 105         startHeight := c.effectiveStartHeight
 106         prevRoundLastBlock := c.blockIndex.NodeByHeight(startHeight - 1)
 107         startTime := prevRoundLastBlock.Timestamp + BlockTimeInterval
 108         endTime := bestBlockTimestamp + (roundVoteBlockNums-bestBlockHeight%roundVoteBlockNums)*BlockTimeInterval
 109
 110         consensusNode, exist := c.consensusNodeMap[hex.EncodeToString(pubkey)]
 111         if !exist {
 112                 return 0, 0, errPublicKeyIsNotConsensusNode
 113         }
 114
 115         nextLeaderTime, err := nextLeaderTimeHelper(startTime, endTime, uint64(time.Now().UnixNano()/1e6), consensusNode.order)
 116         if err != nil {
 117                 return 0, 0, err
 118         }
 119
 120         return nextLeaderTime, nextLeaderTime + BlockNumEachNode*BlockTimeInterval, nil
 121 }
 122
 123 func nextLeaderTimeHelper(startTime, endTime, now, nodeOrder uint64) (uint64, error) {
 124         nextLeaderTimestamp := getLastBlockTimeInTimeRange(startTime, now, nodeOrder)
 125         roundBlockTime := uint64(BlockNumEachNode * numOfConsensusNode * BlockTimeInterval)
 126
 127         if int64(now-nextLeaderTimestamp) >= BlockNumEachNode*BlockTimeInterval {
 128                 nextLeaderTimestamp += roundBlockTime
 129                 if nextLeaderTimestamp >= endTime {
 130                         return 0, errHasNoChanceProductBlock
 131                 }
 132         }
 133
 134         return nextLeaderTimestamp, nil
 135 }
 136
 137 // updateConsensusNodes used to update consensus node after each round of voting
 138 func (c *consensusNodeManager) updateConsensusNodes(bestBlockHeight uint64) error {
 139         defer c.Unlock()
 140         c.Lock()
 141
 142         consensusNodeMap, err := c.getConsensusNodesByVoteResult(bestBlockHeight)
 143         if err != nil && err != errVoteResultIsNotfinalized {
 144                 return err
 145         }
 146
 147         if err == errVoteResultIsNotfinalized {
 148                 return nil
 149         }
 150
 151         c.consensusNodeMap = consensusNodeMap
 152         c.effectiveStartHeight = bestBlockHeight / roundVoteBlockNums * roundVoteBlockNums
 153         return nil
 154 }
 155
 156 func getLastBlockTimeInTimeRange(startTimestamp, endTimestamp, order uint64) uint64 {
 157         // One round of product block time for all consensus nodes
 158         roundBlockTime := uint64(BlockNumEachNode * numOfConsensusNode * BlockTimeInterval)
 159         // The start time of the last round of product block
 160         lastRoundStartTime := startTimestamp + (endTimestamp-startTimestamp)/roundBlockTime*roundBlockTime
 161         // The time of product block of the consensus in last round
 162         return lastRoundStartTime + order*(BlockNumEachNode*BlockTimeInterval)
 163 }
 164
 165 func (c *consensusNodeManager) getConsensusNodesByVoteResult(blockHeight uint64) (map[string]*consensusNode, error) {
 166         defer c.RUnlock()
 167         c.RLock()
 168         if blockHeight >= c.effectiveStartHeight+roundVoteBlockNums {
 169                 return nil, errors.New("the given block height is greater than current vote start height")
 170         }
 171
 172         if blockHeight >= c.effectiveStartHeight {
 173                 return c.consensusNodeMap, nil
 174         }
 175
 176         voteResult, err := c.store.GetVoteResult(blockHeight / roundVoteBlockNums)
 177         if err != nil {
 178                 return nil, err
 179         }
 180
 181         if !voteResult.Finalized {
 182                 return nil, errVoteResultIsNotfinalized
 183         }
 184
 185         var nodes []*consensusNode
 186         for pubkey, voteNum := range voteResult.NumOfVote {
 187                 nodes = append(nodes, &consensusNode{
 188                         pubkey:  pubkey,
 189                         voteNum: voteNum,
 190                 })
 191         }
 192         // In principle, there is no need to sort all voting nodes.
 193         // if there is a performance problem, consider the optimization later.
 194         // TODO not consider the same number of votes
 195         sort.Sort(consensusNodeSlice(nodes))
 196
 197         result := make(map[string]*consensusNode)
 198         for i := 0; i < numOfConsensusNode; i++ {
 199                 node := nodes[i]
 200                 node.order = uint64(i)
 201                 result[node.pubkey] = node
 202         }
 203         return result, nil
 204 }