diff options
Diffstat (limited to 'core/total-ordering.go')
-rw-r--r-- | core/total-ordering.go | 373 |
1 files changed, 235 insertions, 138 deletions
diff --git a/core/total-ordering.go b/core/total-ordering.go index 9f85813..a9ec5b7 100644 --- a/core/total-ordering.go +++ b/core/total-ordering.go @@ -34,25 +34,69 @@ const ( // didn't form a DAG. var ErrNotValidDAG = fmt.Errorf("not a valid dag") -// ackingStatusVector describes the acking status, either globally or just -// for one candidate. +// totalOrderinWinRecord caches which validators this candidate +// wins another one based on their height vector. +type totalOrderingWinRecord map[types.ValidatorID]struct{} + +// grade implements the 'grade' potential function described in white paper. +func (rec totalOrderingWinRecord) grade( + validatorCount, phi uint64, + globalAns map[types.ValidatorID]struct{}) int { + + if uint64(len(rec)) >= phi { + return 1 + } else if uint64(len(rec)) < phi-validatorCount+uint64(len(globalAns)) { + return 0 + } else { + return -1 + } +} + +// totalOrderingHeightRecord records two things: +// - the minimum heiht of block from that validator acking this block. +// - the count of blocks from that validator acking this block. +type totalOrderingHeightRecord struct{ minHeight, count uint64 } + +// totalOrderingCandidateInfo describes proceeding status for one candidate, +// including: +// - acked status as height records, which could keep 'how many blocks from +// one validator acking this candidate. +// - cached height vector, which valid height based on K-level used for +// comparison in 'grade' function. +// - cached result of grade function to other candidates. // -// When block A acks block B, all blocks proposed from the same proposer -// as block A with higher height would also acks block B. Therefore, -// we just need to record: -// - the minimum height of acking block from that proposer -// - count of acking blocks from that proposer -// to repsent the acking status for block A. -type ackingStatusVector map[types.ValidatorID]*struct{ minHeight, count uint64 } - -// addBlock would update ackingStatusVector, it's caller's duty +// Height Record: +// When block A acks block B, all blocks proposed from the same proposer +// as block A with higher height would also acks block B. Therefore, +// we just need to record: +// - the minimum height of acking block from that proposer +// - count of acking blocks from that proposer +// to repsent the acking status for block A. +type totalOrderingCandidateInfo struct { + ackedStatus map[types.ValidatorID]*totalOrderingHeightRecord + cachedHeightVector map[types.ValidatorID]uint64 + winRecords map[common.Hash]totalOrderingWinRecord +} + +// newTotalOrderingCandidateInfo constructs an totalOrderingCandidateInfo +// instance. +func newTotalOrderingCandidateInfo() *totalOrderingCandidateInfo { + return &totalOrderingCandidateInfo{ + ackedStatus: make(map[types.ValidatorID]*totalOrderingHeightRecord), + winRecords: make(map[common.Hash]totalOrderingWinRecord), + } +} + +func (v *totalOrderingCandidateInfo) clean(otherCandidate common.Hash) { + delete(v.winRecords, otherCandidate) +} + +// addBlock would update totalOrderingCandidateInfo, it's caller's duty // to make sure the input block acutally acking the target block. -func (v ackingStatusVector) addBlock(b *types.Block) (err error) { - rec, exists := v[b.ProposerID] +func (v *totalOrderingCandidateInfo) addBlock(b *types.Block) (err error) { + rec, exists := v.ackedStatus[b.ProposerID] if !exists { - v[b.ProposerID] = &struct { - minHeight, count uint64 - }{ + v.ackedStatus[b.ProposerID] = &totalOrderingHeightRecord{ minHeight: b.Height, count: 1, } @@ -77,12 +121,13 @@ func (v ackingStatusVector) addBlock(b *types.Block) (err error) { // - the global minimum acking height = 1, // - k = 1 // then only block height >= 2 would be added to acking node set. -func (v ackingStatusVector) getAckingNodeSet( - global ackingStatusVector, k uint64) map[types.ValidatorID]struct{} { +func (v *totalOrderingCandidateInfo) getAckingNodeSet( + global *totalOrderingCandidateInfo, + k uint64) map[types.ValidatorID]struct{} { ret := make(map[types.ValidatorID]struct{}) - for vID, gRec := range global { - rec, exists := v[vID] + for vID, gRec := range global.ackedStatus { + rec, exists := v.ackedStatus[vID] if !exists { continue } @@ -97,34 +142,105 @@ func (v ackingStatusVector) getAckingNodeSet( return ret } -// getAckingHeightVector would convert 'ackingStatusVector' to -// Acking Height Vector. +// updateAckingHeightVector would cached acking height vector. // // Only block height equals to (global minimum block height + k) would be // taken into consideration. -func (v ackingStatusVector) getAckingHeightVector( - global ackingStatusVector, k uint64) map[types.ValidatorID]uint64 { - - ret := make(map[types.ValidatorID]uint64) - for vID, gRec := range global { - rec, exists := v[vID] +func (v *totalOrderingCandidateInfo) updateAckingHeightVector( + global *totalOrderingCandidateInfo, + k uint64, + dirtyValidators map[types.ValidatorID]struct{}) { + + // The reason not to merge the two loops is the iteration over map + // is expensive when validator count is large, iterating over dirty + // validators is cheaper. + // TODO(mission): merge the code in this if/else if the performance won't be + // downgraded when adding a function for the shared part. + if v.cachedHeightVector == nil { + // Generate height vector from scratch. + v.cachedHeightVector = make(map[types.ValidatorID]uint64) + for vID, gRec := range global.ackedStatus { + rec, exists := v.ackedStatus[vID] + if gRec.count <= k { + delete(v.cachedHeightVector, vID) + continue + } else if !exists { + v.cachedHeightVector[vID] = infinity + } else if rec.minHeight <= gRec.minHeight+k { + // This check is sufficient to make sure the block height: + // + // gRec.minHeight + k + // + // would be included in this totalOrderingCandidateInfo. + v.cachedHeightVector[vID] = gRec.minHeight + k + } else { + v.cachedHeightVector[vID] = infinity + } + } + } else { + // Return the cached one, only update dirty fields. + for vID := range dirtyValidators { + gRec, exists := global.ackedStatus[vID] + if !exists { + continue + } + rec, exists := v.ackedStatus[vID] + if gRec.count <= k { + delete(v.cachedHeightVector, vID) + continue + } else if !exists { + v.cachedHeightVector[vID] = infinity + } else if rec.minHeight <= gRec.minHeight+k { + v.cachedHeightVector[vID] = gRec.minHeight + k + } else { + v.cachedHeightVector[vID] = infinity + } + } + } + return +} - if gRec.count <= k { - continue - } else if !exists { - ret[vID] = infinity - } else if rec.minHeight <= gRec.minHeight+k { - // This check is sufficient to make sure the block height: - // - // gRec.minHeight + k - // - // would be included in this ackingStatusVector. - ret[vID] = gRec.minHeight + k - } else { - ret[vID] = infinity +// updateWinRecord setup win records between two candidates. +func (v *totalOrderingCandidateInfo) updateWinRecord( + otherCandidate common.Hash, + other *totalOrderingCandidateInfo, + dirtyValidators map[types.ValidatorID]struct{}) { + + // The reason not to merge the two loops is the iteration over map + // is expensive when validator count is large, iterating over dirty + // validators is cheaper. + // TODO(mission): merge the code in this if/else if add a function won't + // affect the performance. + win, exists := v.winRecords[otherCandidate] + if !exists { + win = make(map[types.ValidatorID]struct{}) + v.winRecords[otherCandidate] = win + for vID, hFrom := range v.cachedHeightVector { + hTo, exists := other.cachedHeightVector[vID] + if !exists { + continue + } + if hFrom != infinity && hTo == infinity { + win[vID] = struct{}{} + } + } + } else { + for vID := range dirtyValidators { + hFrom, exists := v.cachedHeightVector[vID] + if !exists { + return + } + hTo, exists := other.cachedHeightVector[vID] + if !exists { + return + } + if hFrom != infinity && hTo == infinity { + win[vID] = struct{}{} + } else { + delete(win, vID) + } } } - return ret } // blockVector stores all blocks grouped by their proposers and @@ -144,22 +260,20 @@ func (v blockVector) addBlock(b *types.Block) (err error) { return } -// getAckingStatusVector would convert a blockVector to -// ackingStatusVectorAckingStatus. -func (v blockVector) getAckingStatusVector() ackingStatusVector { - ret := ackingStatusVector{} +// getCandidateInfo would convert a blockVector to +// totalOrderingCandidateInfo. +func (v blockVector) getCandidateInfo() (info *totalOrderingCandidateInfo) { + info = newTotalOrderingCandidateInfo() for vID, vec := range v { if len(vec) == 0 { continue } - ret[vID] = &struct { - minHeight, count uint64 - }{ + info.ackedStatus[vID] = &totalOrderingHeightRecord{ minHeight: vec[0].Height, count: uint64(len(vec)), } } - return ret + return } // totalOrdering represent a process unit to handle total ordering @@ -187,23 +301,29 @@ type totalOrdering struct { // - picking candidates next round globalVector blockVector - // candidateAckingStatusVectors caches ackingStatusVector of candidates. - candidateAckingStatusVectors map[common.Hash]ackingStatusVector + // candidates caches result of potential function during generating + // preceding sets. + candidates map[common.Hash]*totalOrderingCandidateInfo // acked cache the 'block A acked by block B' relation by // keeping a record in acked[A.Hash][B.Hash] acked map[common.Hash]map[common.Hash]struct{} + + // dirtyValidators records which validatorID that should be updated for + // all cached status (win record, acking status). + dirtyValidators map[types.ValidatorID]struct{} } func newTotalOrdering(k, phi, validatorCount uint64) *totalOrdering { return &totalOrdering{ - candidateAckingStatusVectors: make(map[common.Hash]ackingStatusVector), - pendings: make(map[common.Hash]*types.Block), - k: k, - phi: phi, - validatorCount: validatorCount, - globalVector: blockVector{}, - acked: make(map[common.Hash]map[common.Hash]struct{}), + candidates: make(map[common.Hash]*totalOrderingCandidateInfo), + pendings: make(map[common.Hash]*types.Block), + k: k, + phi: phi, + validatorCount: validatorCount, + globalVector: blockVector{}, + dirtyValidators: make(map[types.ValidatorID]struct{}), + acked: make(map[common.Hash]map[common.Hash]struct{}), } } @@ -242,7 +362,10 @@ func (to *totalOrdering) buildBlockRelation(b *types.Block) { func (to *totalOrdering) clean(h common.Hash) { delete(to.acked, h) delete(to.pendings, h) - delete(to.candidateAckingStatusVectors, h) + delete(to.candidates, h) + for _, info := range to.candidates { + info.clean(h) + } } // updateVectors is a helper function to update all cached vectors. @@ -254,79 +377,44 @@ func (to *totalOrdering) updateVectors(b *types.Block) (err error) { } // Update acking status of candidates. - for candidate, vector := range to.candidateAckingStatusVectors { + for candidate, info := range to.candidates { if _, acked := to.acked[candidate][b.Hash]; !acked { continue } - if err = vector.addBlock(b); err != nil { + if err = info.addBlock(b); err != nil { return } } return } -// grade implements the 'grade' potential function described in white paper. -func (to *totalOrdering) grade( - hvFrom, hvTo map[types.ValidatorID]uint64, - globalAns map[types.ValidatorID]struct{}) int { - - count := uint64(0) - for vID, hFrom := range hvFrom { - hTo, exists := hvTo[vID] - if !exists { - continue - } - - if hFrom != infinity && hTo == infinity { - count++ - } - } - - if count >= to.phi { - return 1 - } else if count < to.phi-to.validatorCount+uint64(len(globalAns)) { - return 0 - } else { - return -1 - } -} - -// buildAckingStatusVectorForNewCandidate is a helper function to -// build ackingStatusVector for new candidate. -func (to *totalOrdering) buildAckingStatusVectorForNewCandidate( - candidate *types.Block) (hVec ackingStatusVector) { +// prepareCandidate is a helper function to +// build totalOrderingCandidateInfo for new candidate. +func (to *totalOrdering) prepareCandidate( + candidate *types.Block) (info *totalOrderingCandidateInfo) { blocks := to.globalVector[candidate.ProposerID] - hVec = ackingStatusVector{ - candidate.ProposerID: &struct { - minHeight, count uint64 - }{ - minHeight: candidate.Height, - count: uint64(len(blocks)), - }, + info = newTotalOrderingCandidateInfo() + info.ackedStatus[candidate.ProposerID] = &totalOrderingHeightRecord{ + minHeight: candidate.Height, + count: uint64(len(blocks)), } - ackedsForCandidate, exists := to.acked[candidate.Hash] if !exists { // This candidate is acked by nobody. return } - for vID, blocks := range to.globalVector { if vID == candidate.ProposerID { continue } - for i, b := range blocks { if _, acked := ackedsForCandidate[b.Hash]; !acked { continue } - // If this block acks this candidate, all newer blocks // from the same validator also 'indirect' acks it. - hVec[vID] = &struct { - minHeight, count uint64 - }{ + info.ackedStatus[vID] = &totalOrderingHeightRecord{ minHeight: b.Height, count: uint64(len(blocks) - i), } @@ -358,6 +446,7 @@ func (to *totalOrdering) output(precedings map[common.Hash]struct{}) (ret []*typ // Remove block relations. to.clean(p) + to.dirtyValidators[b.ProposerID] = struct{}{} } sort.Sort(types.ByHash(ret)) @@ -367,20 +456,16 @@ func (to *totalOrdering) output(precedings map[common.Hash]struct{}) (ret []*typ if len(blocks) == 0 { continue } - tip := blocks[0] if _, alreadyCandidate := - to.candidateAckingStatusVectors[tip.Hash]; alreadyCandidate { + to.candidates[tip.Hash]; alreadyCandidate { continue } - if !to.isAckOnlyPrecedings(tip) { continue } - - // Build ackingStatusVector for new candidate. - to.candidateAckingStatusVectors[tip.Hash] = - to.buildAckingStatusVectorForNewCandidate(tip) + // Build totalOrderingCandidateInfo for new candidate. + to.candidates[tip.Hash] = to.prepareCandidate(tip) } return ret } @@ -391,44 +476,56 @@ func (to *totalOrdering) output(precedings map[common.Hash]struct{}) (ret []*typ func (to *totalOrdering) generateDeliverSet() ( delivered map[common.Hash]struct{}, early bool) { - globalAckingStatusVector := to.globalVector.getAckingStatusVector() - ahvs := map[common.Hash]map[types.ValidatorID]uint64{} - for candidate, v := range to.candidateAckingStatusVectors { - ahvs[candidate] = v.getAckingHeightVector(globalAckingStatusVector, to.k) + globalCandidatesInfo := to.globalVector.getCandidateInfo() + for _, info := range to.candidates { + info.updateAckingHeightVector( + globalCandidatesInfo, to.k, to.dirtyValidators) } + // Update winning records for each candidate. + for candidate, info := range to.candidates { + for otherCandidate, otherInfo := range to.candidates { + if candidate == otherCandidate { + continue + } + info.updateWinRecord(otherCandidate, otherInfo, to.dirtyValidators) + } + } + // Reset dirty validators. + to.dirtyValidators = make(map[types.ValidatorID]struct{}) - globalAns := globalAckingStatusVector.getAckingNodeSet( - globalAckingStatusVector, to.k) + globalAns := globalCandidatesInfo.getAckingNodeSet( + globalCandidatesInfo, to.k) precedings := make(map[common.Hash]struct{}) CheckNextCandidateLoop: - for candidate := range to.candidateAckingStatusVectors { - for otherCandidate := range to.candidateAckingStatusVectors { + for candidate := range to.candidates { + for otherCandidate, otherInfo := range to.candidates { if candidate == otherCandidate { continue } - if to.grade(ahvs[otherCandidate], ahvs[candidate], globalAns) != 0 { + if otherInfo.winRecords[candidate].grade( + to.validatorCount, to.phi, globalAns) != 0 { + continue CheckNextCandidateLoop } } precedings[candidate] = struct{}{} } - if len(precedings) == 0 { return } // internal is a helper function to verify internal stability. internal := func() bool { - for candidate := range to.candidateAckingStatusVectors { + for candidate := range to.candidates { if _, isPreceding := precedings[candidate]; isPreceding { continue } beaten := false for p := range precedings { - if beaten = - to.grade(ahvs[p], ahvs[candidate], globalAns) == 1; beaten { + if beaten = to.candidates[p].winRecords[candidate].grade( + to.validatorCount, to.phi, globalAns) == 1; beaten { break } } @@ -445,12 +542,12 @@ CheckNextCandidateLoop: checkAHV := func() bool { for p := range precedings { count := uint64(0) - for _, v := range ahvs[p] { + status := to.candidates[p] + for _, v := range status.cachedHeightVector { if v != infinity { count++ } } - if count > to.phi { return true } @@ -463,24 +560,23 @@ CheckNextCandidateLoop: // to be delivered. checkANS := func() bool { for p := range precedings { - validatorAns := to.candidateAckingStatusVectors[p].getAckingNodeSet( - globalAckingStatusVector, to.k) + validatorAns := to.candidates[p].getAckingNodeSet( + globalCandidatesInfo, to.k) if uint64(len(validatorAns)) < to.validatorCount-to.phi { return false } } - return true } - // Check internal stability first. - if !internal() { - return - } - // If all validators propose enough blocks, we should force // to deliver since the whole picture of the DAG is revealed. if uint64(len(globalAns)) != to.validatorCount { + // Check internal stability first. + if !internal() { + return + } + // The whole picture is not ready, we need to check if // exteranl stability is met, and we can deliver earlier. if checkAHV() && checkANS() { @@ -508,9 +604,10 @@ func (to *totalOrdering) processBlock(b *types.Block) ( return } if to.isAckOnlyPrecedings(b) { - to.candidateAckingStatusVectors[b.Hash] = - to.buildAckingStatusVectorForNewCandidate(b) + to.candidates[b.Hash] = to.prepareCandidate(b) } + // Mark the proposer of incoming block as dirty. + to.dirtyValidators[b.ProposerID] = struct{}{} // Not-Incremental part (yet). // - generate ahv for each candidate |