diff options
author | Haoping Ku <haoping.ku@dexon.org> | 2018-08-13 18:09:30 +0800 |
---|---|---|
committer | GitHub <noreply@github.com> | 2018-08-13 18:09:30 +0800 |
commit | d4228f32b436f551e736079fe0f590405077652c (patch) | |
tree | 49c93c8e1736914a0ba78344408c7fd3ac880740 /core/negative-ack.go | |
parent | 3733e4c72dd1b16626bf257f4acb9a74f795d924 (diff) | |
download | tangerine-consensus-d4228f32b436f551e736079fe0f590405077652c.tar tangerine-consensus-d4228f32b436f551e736079fe0f590405077652c.tar.gz tangerine-consensus-d4228f32b436f551e736079fe0f590405077652c.tar.bz2 tangerine-consensus-d4228f32b436f551e736079fe0f590405077652c.tar.lz tangerine-consensus-d4228f32b436f551e736079fe0f590405077652c.tar.xz tangerine-consensus-d4228f32b436f551e736079fe0f590405077652c.tar.zst tangerine-consensus-d4228f32b436f551e736079fe0f590405077652c.zip |
core: add nack module (#41)
Diffstat (limited to 'core/negative-ack.go')
-rw-r--r-- | core/negative-ack.go | 211 |
1 files changed, 211 insertions, 0 deletions
diff --git a/core/negative-ack.go b/core/negative-ack.go new file mode 100644 index 0000000..13a4832 --- /dev/null +++ b/core/negative-ack.go @@ -0,0 +1,211 @@ +// Copyright 2018 The dexon-consensus-core Authors +// This file is part of the dexon-consensus-core library. +// +// The dexon-consensus-core library is free software: you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation, either version 3 of the License, +// or (at your option) any later version. +// +// The dexon-consensus-core library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the dexon-consensus-core library. If not, see +// <http://www.gnu.org/licenses/>. + +package core + +import ( + "time" + + "github.com/dexon-foundation/dexon-consensus-core/core/types" +) + +type negativeAck struct { + // owner is the ID of proposer itself, this is used when deciding + // a validator to be restricted or not. + owner types.ValidatorID + + numOfValidators int + + // timeDelay and timeExpire are for nack timeout. + timeDelay time.Duration + timeExpire time.Duration + + // restricteds stores validators which has been restricted and the time it's + // restricted. + restricteds map[types.ValidatorID]time.Time + + // lastVotes and lockedVotes store the votes for nack. lastVotes[vid1][vid2] + // and lockedVotes[vid1][vid2] both mean that vid2 votes vid1. The difference + // is lockedVotes works only when vid1 is restricted, so that the votes are + // needed to be locked. + lastVotes map[types.ValidatorID]map[types.ValidatorID]struct{} + lockedVotes map[types.ValidatorID]map[types.ValidatorID]struct{} + + // timeDiffs is the cache for last time stamps. timeDiffs[vid1][vid2] means + // the last updated timestamps vid1 sees vid2. + timeDiffs map[types.ValidatorID]map[types.ValidatorID]map[types.ValidatorID]time.Time +} + +// newNegativeAck creates a new negaticeAck instance. +func newNegativeAck(vid types.ValidatorID) *negativeAck { + n := &negativeAck{ + owner: vid, + numOfValidators: 0, + restricteds: make(map[types.ValidatorID]time.Time), + lastVotes: make(map[types.ValidatorID]map[types.ValidatorID]struct{}), + lockedVotes: make(map[types.ValidatorID]map[types.ValidatorID]struct{}), + timeDiffs: make(map[types.ValidatorID]map[types.ValidatorID]map[types.ValidatorID]time.Time), + } + n.addValidator(vid) + return n +} + +// processNewVote is called when a new "vote" occurs, that is, a validator +// sees that other 2f + 1 validators think a validator is slow. "vid" is the +// validator which propesed the block which the timestamps votes and "h" is +// the validator been voted to be nacked. +func (n *negativeAck) processNewVote( + vid types.ValidatorID, + h types.ValidatorID, +) []types.ValidatorID { + + nackeds := []types.ValidatorID{} + if _, exist := n.restricteds[h]; exist { + n.lockedVotes[h][vid] = struct{}{} + if len(n.lockedVotes[h]) > 2*(n.numOfValidators-1)/3 { + nackeds = append(nackeds, h) + delete(n.restricteds, h) + } + } else { + if n.owner == vid { + n.restrict(h) + } else { + n.lastVotes[h][vid] = struct{}{} + if len(n.lastVotes[h]) > (n.numOfValidators-1)/3 { + n.restrict(h) + } + } + } + return nackeds +} + +// processTimestamps process new timestamps of a block which is proposed by +// validator vid, and returns the validators being nacked. +func (n *negativeAck) processTimestamps( + vid types.ValidatorID, + ts map[types.ValidatorID]time.Time, +) []types.ValidatorID { + + n.checkRestrictExpire() + + nackeds := []types.ValidatorID{} + for h := range n.timeDiffs { + if n.timeDiffs[vid][h][h].Equal(ts[h]) { + votes := 0 + for hh := range n.timeDiffs { + if ts[hh].Sub(n.timeDiffs[vid][h][hh]) >= n.timeDelay { + votes++ + } + } + if votes > 2*((n.numOfValidators-1)/3) { + n.lastVotes[h][vid] = struct{}{} + nack := n.processNewVote(vid, h) + for _, i := range nack { + nackeds = append(nackeds, i) + } + } else { + delete(n.lastVotes[h], vid) + } + } else { + for hh := range n.timeDiffs { + n.timeDiffs[vid][h][hh] = ts[hh] + } + delete(n.lastVotes[h], vid) + } + } + return nackeds +} + +func (n *negativeAck) checkRestrictExpire() { + expired := []types.ValidatorID{} + now := time.Now() + for h, t := range n.restricteds { + if now.Sub(t) >= n.timeExpire { + expired = append(expired, h) + } + } + for _, h := range expired { + delete(n.restricteds, h) + } +} + +func (n *negativeAck) restrict(vid types.ValidatorID) { + if _, exist := n.restricteds[vid]; !exist { + n.restricteds[vid] = time.Now().UTC() + n.lockedVotes[vid] = map[types.ValidatorID]struct{}{} + for h := range n.lastVotes[vid] { + n.lockedVotes[vid][h] = struct{}{} + } + } +} + +func (n *negativeAck) getRestrictedValidators() map[types.ValidatorID]struct{} { + n.checkRestrictExpire() + ret := map[types.ValidatorID]struct{}{} + for h := range n.restricteds { + ret[h] = struct{}{} + } + return ret +} + +func (n *negativeAck) setTimeDelay(t time.Duration) { + n.timeDelay = t +} + +func (n *negativeAck) setTimeExpire(t time.Duration) { + n.timeExpire = t +} + +func (n *negativeAck) addValidator(vid types.ValidatorID) { + n.numOfValidators++ + n.lastVotes[vid] = make(map[types.ValidatorID]struct{}) + n.lockedVotes[vid] = make(map[types.ValidatorID]struct{}) + + newTimeDiff := make(map[types.ValidatorID]map[types.ValidatorID]time.Time) + for h := range n.timeDiffs { + newTimeDiff2 := make(map[types.ValidatorID]time.Time) + for hh := range n.timeDiffs { + newTimeDiff2[hh] = time.Time{} + } + newTimeDiff[h] = newTimeDiff2 + } + n.timeDiffs[vid] = newTimeDiff + for h := range n.timeDiffs { + n.timeDiffs[h][vid] = make(map[types.ValidatorID]time.Time) + } +} + +func (n *negativeAck) deleteValidator(vid types.ValidatorID) { + n.numOfValidators-- + + delete(n.timeDiffs, vid) + + for h := range n.lastVotes { + delete(n.lastVotes[h], vid) + } + delete(n.lastVotes, vid) + delete(n.lockedVotes, vid) + + for h := range n.timeDiffs { + delete(n.timeDiffs[h], vid) + for hh := range n.timeDiffs[h] { + delete(n.timeDiffs[h][hh], vid) + } + } + + delete(n.restricteds, vid) +} |