diff options
author | Mission Liao <mission.liao@dexon.org> | 2018-08-21 10:00:05 +0800 |
---|---|---|
committer | GitHub <noreply@github.com> | 2018-08-21 10:00:05 +0800 |
commit | 1ebe7b8729a166745d56203685232cb2e7d41cab (patch) | |
tree | ee5546328ab67c49a8a61de607b783f1102ade58 | |
parent | 1e71e263e063adbe7e44d48818f9c74924a2945d (diff) | |
download | tangerine-consensus-1ebe7b8729a166745d56203685232cb2e7d41cab.tar tangerine-consensus-1ebe7b8729a166745d56203685232cb2e7d41cab.tar.gz tangerine-consensus-1ebe7b8729a166745d56203685232cb2e7d41cab.tar.bz2 tangerine-consensus-1ebe7b8729a166745d56203685232cb2e7d41cab.tar.lz tangerine-consensus-1ebe7b8729a166745d56203685232cb2e7d41cab.tar.xz tangerine-consensus-1ebe7b8729a166745d56203685232cb2e7d41cab.tar.zst tangerine-consensus-1ebe7b8729a166745d56203685232cb2e7d41cab.zip |
core: tune performance total ordering (#66)
- the checking of `internal stability` is more expensive than checking `len(ANS) == validatorCount`. So only check it when `len(ANS) != validatorCount`.
- cache the result of `grade` between candidates.
- cache the `acking height vector` of each candidate.
- add test on total ordering with different acking frequency between blocks.
-rw-r--r-- | core/test/blocks-generator.go | 6 | ||||
-rw-r--r-- | core/test/blocks-generator_test.go | 55 | ||||
-rw-r--r-- | core/total-ordering.go | 373 | ||||
-rw-r--r-- | core/total-ordering_test.go | 529 |
4 files changed, 577 insertions, 386 deletions
diff --git a/core/test/blocks-generator.go b/core/test/blocks-generator.go index a26a901..3cd97ee 100644 --- a/core/test/blocks-generator.go +++ b/core/test/blocks-generator.go @@ -189,6 +189,12 @@ func normalAckingCountGenerator( } } +// MaxAckingCountGenerator return generator which returns +// fixed maximum acking count. +func MaxAckingCountGenerator(count int) func() int { + return func() int { return count } +} + // generateValidatorPicker is a function generator, which would generate // a function to randomly pick one validator ID from a slice of validator ID. func generateValidatorPicker() func([]types.ValidatorID) types.ValidatorID { diff --git a/core/test/blocks-generator_test.go b/core/test/blocks-generator_test.go index 0624da2..43e994f 100644 --- a/core/test/blocks-generator_test.go +++ b/core/test/blocks-generator_test.go @@ -103,6 +103,61 @@ func (s *BlocksGeneratorTestCase) TestGenerate() { } } +func (s *BlocksGeneratorTestCase) TestGenerateWithMaxAckCount() { + var ( + validatorCount = 13 + blockCount = 50 + gen = NewBlocksGenerator(nil, stableRandomHash) + req = s.Require() + ) + + // Generate with 0 acks. + db, err := blockdb.NewMemBackedBlockDB() + req.Nil(err) + req.Nil(gen.Generate( + validatorCount, blockCount, MaxAckingCountGenerator(0), db)) + // Load blocks to check their acking count. + iter, err := db.GetAll() + req.Nil(err) + for { + block, err := iter.Next() + if err == blockdb.ErrIterationFinished { + break + } + req.Nil(err) + if block.IsGenesis() { + continue + } + req.Len(block.Acks, 1) + } + + // Generate with acks as many as possible. + db, err = blockdb.NewMemBackedBlockDB() + req.Nil(err) + req.Nil(gen.Generate( + validatorCount, blockCount, MaxAckingCountGenerator( + validatorCount), db)) + // Load blocks to verify the average acking count. + totalAckingCount := 0 + totalBlockCount := 0 + iter, err = db.GetAll() + req.Nil(err) + for { + block, err := iter.Next() + if err == blockdb.ErrIterationFinished { + break + } + req.Nil(err) + if block.IsGenesis() { + continue + } + totalAckingCount += len(block.Acks) + totalBlockCount++ + } + req.NotZero(totalBlockCount) + req.True((totalAckingCount / totalBlockCount) >= (validatorCount / 2)) +} + func TestBlocksGenerator(t *testing.T) { suite.Run(t, new(BlocksGeneratorTestCase)) } 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 diff --git a/core/total-ordering_test.go b/core/total-ordering_test.go index dca92d7..d0f8741 100644 --- a/core/total-ordering_test.go +++ b/core/total-ordering_test.go @@ -66,6 +66,16 @@ func (s *TotalOrderingTestSuite) checkNotInWorkingSet( s.NotContains(to.acked, b.Hash) } +func (s *TotalOrderingTestSuite) prepareDirtyValidators( + validators []types.ValidatorID) map[types.ValidatorID]struct{} { + + dirties := map[types.ValidatorID]struct{}{} + for _, vID := range validators { + dirties[vID] = struct{}{} + } + return dirties +} + func (s *TotalOrderingTestSuite) TestBlockRelation() { // This test case would verify if 'acking' and 'acked' // accumulated correctly. @@ -117,103 +127,115 @@ func (s *TotalOrderingTestSuite) TestBlockRelation() { func (s *TotalOrderingTestSuite) TestCreateAckingHeightVectorFromHeightVector() { validators := test.GenerateRandomValidatorIDs(5) - global := ackingStatusVector{ - validators[0]: &struct{ minHeight, count uint64 }{ - minHeight: 0, count: 5}, - validators[1]: &struct{ minHeight, count uint64 }{ - minHeight: 0, count: 5}, - validators[2]: &struct{ minHeight, count uint64 }{ - minHeight: 0, count: 5}, - validators[3]: &struct{ minHeight, count uint64 }{ - minHeight: 0, count: 5}, - } + // Generate dirty validator set. + dirties := s.prepareDirtyValidators(validators) + // Prepare global acking status. + global := &totalOrderingCandidateInfo{ + ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{ + validators[0]: &totalOrderingHeightRecord{minHeight: 0, count: 5}, + validators[1]: &totalOrderingHeightRecord{minHeight: 0, count: 5}, + validators[2]: &totalOrderingHeightRecord{minHeight: 0, count: 5}, + validators[3]: &totalOrderingHeightRecord{minHeight: 0, count: 5}, + }} // For 'not existed' record in local but exist in global, // should be infinity. - ahv := ackingStatusVector{ - validators[0]: &struct{ minHeight, count uint64 }{ - minHeight: 0, count: 2}, - }.getAckingHeightVector(global, 0) - s.Len(ahv, 4) - s.Equal(ahv[validators[0]], uint64(0)) - s.Equal(ahv[validators[1]], infinity) - s.Equal(ahv[validators[2]], infinity) - s.Equal(ahv[validators[3]], infinity) + candidate := &totalOrderingCandidateInfo{ + ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{ + validators[0]: &totalOrderingHeightRecord{minHeight: 0, count: 2}, + }} + candidate.updateAckingHeightVector(global, 0, dirties) + s.Len(candidate.cachedHeightVector, 4) + s.Equal(candidate.cachedHeightVector[validators[0]], uint64(0)) + s.Equal(candidate.cachedHeightVector[validators[1]], infinity) + s.Equal(candidate.cachedHeightVector[validators[2]], infinity) + s.Equal(candidate.cachedHeightVector[validators[3]], infinity) // For local min exceeds global's min+k-1, should be infinity - hv := ackingStatusVector{ - validators[0]: &struct{ minHeight, count uint64 }{ - minHeight: 3, count: 1}, - } - ahv = hv.getAckingHeightVector(global, 2) - s.Equal(ahv[validators[0]], infinity) - ahv = hv.getAckingHeightVector(global, 3) - s.Equal(ahv[validators[0]], uint64(3)) - - ahv = ackingStatusVector{ - validators[0]: &struct{ minHeight, count uint64 }{ - minHeight: 0, count: 3}, - validators[1]: &struct{ minHeight, count uint64 }{ - minHeight: 0, count: 3}, - }.getAckingHeightVector(global, 5) - s.Len(ahv, 0) + candidate = &totalOrderingCandidateInfo{ + ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{ + validators[0]: &totalOrderingHeightRecord{minHeight: 3, count: 1}, + }} + candidate.updateAckingHeightVector(global, 2, dirties) + s.Equal(candidate.cachedHeightVector[validators[0]], infinity) + candidate.updateAckingHeightVector(global, 3, dirties) + s.Equal(candidate.cachedHeightVector[validators[0]], uint64(3)) + + candidate = &totalOrderingCandidateInfo{ + ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{ + validators[0]: &totalOrderingHeightRecord{minHeight: 0, count: 3}, + validators[1]: &totalOrderingHeightRecord{minHeight: 0, count: 3}, + }} + candidate.updateAckingHeightVector(global, 5, dirties) + s.Len(candidate.cachedHeightVector, 0) } func (s *TotalOrderingTestSuite) TestCreateAckingNodeSetFromHeightVector() { validators := test.GenerateRandomValidatorIDs(5) - global := ackingStatusVector{ - validators[0]: &struct{ minHeight, count uint64 }{ - minHeight: 0, count: 5}, - validators[1]: &struct{ minHeight, count uint64 }{ - minHeight: 0, count: 5}, - validators[2]: &struct{ minHeight, count uint64 }{ - minHeight: 0, count: 5}, - validators[3]: &struct{ minHeight, count uint64 }{ - minHeight: 0, count: 5}, - } - - local := ackingStatusVector{ - validators[0]: &struct{ minHeight, count uint64 }{ - minHeight: 1, count: 2}, - } + global := &totalOrderingCandidateInfo{ + ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{ + validators[0]: &totalOrderingHeightRecord{minHeight: 0, count: 5}, + validators[1]: &totalOrderingHeightRecord{minHeight: 0, count: 5}, + validators[2]: &totalOrderingHeightRecord{minHeight: 0, count: 5}, + validators[3]: &totalOrderingHeightRecord{minHeight: 0, count: 5}, + }} + + local := &totalOrderingCandidateInfo{ + ackedStatus: map[types.ValidatorID]*totalOrderingHeightRecord{ + validators[0]: &totalOrderingHeightRecord{ + minHeight: 1, count: 2}, + }} s.Len(local.getAckingNodeSet(global, 1), 1) s.Len(local.getAckingNodeSet(global, 2), 1) s.Len(local.getAckingNodeSet(global, 3), 0) } func (s *TotalOrderingTestSuite) TestGrade() { + // This test case just fake some internal structure used + // when performing total ordering. validators := test.GenerateRandomValidatorIDs(5) - to := newTotalOrdering(1, 3, 5) // K doesn't matter when calculating preceding. - + dirtyValidators := s.prepareDirtyValidators(validators) ans := map[types.ValidatorID]struct{}{ validators[0]: struct{}{}, validators[1]: struct{}{}, validators[2]: struct{}{}, validators[3]: struct{}{}, } - - ahv1 := map[types.ValidatorID]uint64{ + candidates := common.Hashes{ + common.NewRandomHash(), + common.NewRandomHash(), + common.NewRandomHash(), + } + candidate1 := newTotalOrderingCandidateInfo() + candidate1.cachedHeightVector = map[types.ValidatorID]uint64{ validators[0]: 1, validators[1]: infinity, validators[2]: infinity, validators[3]: infinity, } - ahv2 := map[types.ValidatorID]uint64{ + candidate2 := newTotalOrderingCandidateInfo() + candidate2.cachedHeightVector = map[types.ValidatorID]uint64{ validators[0]: 1, validators[1]: 1, validators[2]: 1, validators[3]: 1, } - ahv3 := map[types.ValidatorID]uint64{ + candidate3 := newTotalOrderingCandidateInfo() + candidate3.cachedHeightVector = map[types.ValidatorID]uint64{ validators[0]: 1, validators[1]: 1, validators[2]: infinity, validators[3]: infinity, } - s.Equal(to.grade(ahv2, ahv1, ans), 1) - s.Equal(to.grade(ahv1, ahv2, ans), 0) - s.Equal(to.grade(ahv2, ahv3, ans), -1) - s.Equal(to.grade(ahv3, ahv2, ans), 0) + + candidate2.updateWinRecord(candidates[0], candidate1, dirtyValidators) + s.Equal(candidate2.winRecords[candidates[0]].grade(5, 3, ans), 1) + candidate1.updateWinRecord(candidates[1], candidate2, dirtyValidators) + s.Equal(candidate1.winRecords[candidates[1]].grade(5, 3, ans), 0) + candidate2.updateWinRecord(candidates[2], candidate3, dirtyValidators) + s.Equal(candidate2.winRecords[candidates[2]].grade(5, 3, ans), -1) + candidate3.updateWinRecord(candidates[1], candidate2, dirtyValidators) + s.Equal(candidate3.winRecords[candidates[1]].grade(5, 3, ans), 0) } func (s *TotalOrderingTestSuite) TestCycleDetection() { @@ -342,11 +364,11 @@ func (s *TotalOrderingTestSuite) TestEarlyDeliver() { s.checkNotDeliver(to, b01) s.checkNotDeliver(to, b02) - vec := to.candidateAckingStatusVectors[b00.Hash] - s.Require().NotNil(vec) - s.Len(vec, 1) - s.Equal(vec[validators[0]].minHeight, b00.Height) - s.Equal(vec[validators[0]].count, uint64(3)) + candidate := to.candidates[b00.Hash] + s.Require().NotNil(candidate) + s.Len(candidate.ackedStatus, 1) + s.Equal(candidate.ackedStatus[validators[0]].minHeight, b00.Height) + s.Equal(candidate.ackedStatus[validators[0]].count, uint64(3)) s.checkNotDeliver(to, b10) s.checkNotDeliver(to, b11) @@ -358,19 +380,19 @@ func (s *TotalOrderingTestSuite) TestEarlyDeliver() { s.checkNotDeliver(to, b31) // Check the internal state before delivering. - s.Len(to.candidateAckingStatusVectors, 1) // b00 is the only candidate. - - vec = to.candidateAckingStatusVectors[b00.Hash] - s.Require().NotNil(vec) - s.Len(vec, 4) - s.Equal(vec[validators[0]].minHeight, b00.Height) - s.Equal(vec[validators[0]].count, uint64(3)) - s.Equal(vec[validators[1]].minHeight, b10.Height) - s.Equal(vec[validators[1]].count, uint64(3)) - s.Equal(vec[validators[2]].minHeight, b20.Height) - s.Equal(vec[validators[2]].count, uint64(3)) - s.Equal(vec[validators[3]].minHeight, b30.Height) - s.Equal(vec[validators[3]].count, uint64(2)) + s.Len(to.candidates, 1) // b00 is the only candidate. + + candidate = to.candidates[b00.Hash] + s.Require().NotNil(candidate) + s.Len(candidate.ackedStatus, 4) + s.Equal(candidate.ackedStatus[validators[0]].minHeight, b00.Height) + s.Equal(candidate.ackedStatus[validators[0]].count, uint64(3)) + s.Equal(candidate.ackedStatus[validators[1]].minHeight, b10.Height) + s.Equal(candidate.ackedStatus[validators[1]].count, uint64(3)) + s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height) + s.Equal(candidate.ackedStatus[validators[2]].count, uint64(3)) + s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height) + s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2)) blocks, early, err := to.processBlock(b32) s.Require().Len(blocks, 1) @@ -379,35 +401,35 @@ func (s *TotalOrderingTestSuite) TestEarlyDeliver() { s.checkHashSequence(blocks, common.Hashes{b00.Hash}) // Check the internal state after delivered. - s.Len(to.candidateAckingStatusVectors, 4) // b01, b10, b20, b30 are candidates. + s.Len(to.candidates, 4) // b01, b10, b20, b30 are candidates. // Check b01. - vec = to.candidateAckingStatusVectors[b01.Hash] - s.Require().NotNil(vec) - s.Len(vec, 1) - s.Equal(vec[validators[0]].minHeight, b01.Height) - s.Equal(vec[validators[0]].count, uint64(2)) + candidate = to.candidates[b01.Hash] + s.Require().NotNil(candidate) + s.Len(candidate.ackedStatus, 1) + s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height) + s.Equal(candidate.ackedStatus[validators[0]].count, uint64(2)) // Check b10. - vec = to.candidateAckingStatusVectors[b10.Hash] - s.Require().NotNil(vec) - s.Len(vec, 1) - s.Equal(vec[validators[1]].minHeight, b10.Height) - s.Equal(vec[validators[1]].count, uint64(3)) + candidate = to.candidates[b10.Hash] + s.Require().NotNil(candidate) + s.Len(candidate.ackedStatus, 1) + s.Equal(candidate.ackedStatus[validators[1]].minHeight, b10.Height) + s.Equal(candidate.ackedStatus[validators[1]].count, uint64(3)) // Check b20. - vec = to.candidateAckingStatusVectors[b20.Hash] - s.Require().NotNil(vec) - s.Len(vec, 1) - s.Equal(vec[validators[2]].minHeight, b20.Height) - s.Equal(vec[validators[2]].count, uint64(3)) + candidate = to.candidates[b20.Hash] + s.Require().NotNil(candidate) + s.Len(candidate.ackedStatus, 1) + s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height) + s.Equal(candidate.ackedStatus[validators[2]].count, uint64(3)) // Check b30. - vec = to.candidateAckingStatusVectors[b30.Hash] - s.Require().NotNil(vec) - s.Len(vec, 1) - s.Equal(vec[validators[3]].minHeight, b30.Height) - s.Equal(vec[validators[3]].count, uint64(3)) + candidate = to.candidates[b30.Hash] + s.Require().NotNil(candidate) + s.Len(candidate.ackedStatus, 1) + s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height) + s.Equal(candidate.ackedStatus[validators[3]].count, uint64(3)) // Make sure b00 doesn't exist in current working set: s.checkNotInWorkingSet(to, b00) @@ -599,33 +621,33 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { s.Contains(acked, b32.Hash) // Make sure there are 2 candidates. - s.Require().Len(to.candidateAckingStatusVectors, 2) + s.Require().Len(to.candidates, 2) // Check b00's height vector. - vec := to.candidateAckingStatusVectors[b00.Hash] - s.Require().NotNil(vec) - s.NotContains(vec, validators[4]) - s.Equal(vec[validators[0]].minHeight, b00.Height) - s.Equal(vec[validators[0]].count, uint64(2)) - s.Equal(vec[validators[1]].minHeight, b11.Height) - s.Equal(vec[validators[1]].count, uint64(2)) - s.Equal(vec[validators[2]].minHeight, b21.Height) - s.Equal(vec[validators[2]].count, uint64(2)) - s.Equal(vec[validators[3]].minHeight, b31.Height) - s.Equal(vec[validators[3]].count, uint64(2)) + candidate := to.candidates[b00.Hash] + s.Require().NotNil(candidate) + s.NotContains(candidate.ackedStatus, validators[4]) + s.Equal(candidate.ackedStatus[validators[0]].minHeight, b00.Height) + s.Equal(candidate.ackedStatus[validators[0]].count, uint64(2)) + s.Equal(candidate.ackedStatus[validators[1]].minHeight, b11.Height) + s.Equal(candidate.ackedStatus[validators[1]].count, uint64(2)) + s.Equal(candidate.ackedStatus[validators[2]].minHeight, b21.Height) + s.Equal(candidate.ackedStatus[validators[2]].count, uint64(2)) + s.Equal(candidate.ackedStatus[validators[3]].minHeight, b31.Height) + s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2)) // Check b10's height vector. - vec = to.candidateAckingStatusVectors[b10.Hash] - s.Require().NotNil(vec) - s.NotContains(vec, validators[4]) - s.Equal(vec[validators[0]].minHeight, b01.Height) - s.Equal(vec[validators[0]].count, uint64(1)) - s.Equal(vec[validators[1]].minHeight, b10.Height) - s.Equal(vec[validators[1]].count, uint64(3)) - s.Equal(vec[validators[2]].minHeight, b20.Height) - s.Equal(vec[validators[2]].count, uint64(3)) - s.Equal(vec[validators[3]].minHeight, b30.Height) - s.Equal(vec[validators[3]].count, uint64(3)) + candidate = to.candidates[b10.Hash] + s.Require().NotNil(candidate) + s.NotContains(candidate.ackedStatus, validators[4]) + s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height) + s.Equal(candidate.ackedStatus[validators[0]].count, uint64(1)) + s.Equal(candidate.ackedStatus[validators[1]].minHeight, b10.Height) + s.Equal(candidate.ackedStatus[validators[1]].count, uint64(3)) + s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height) + s.Equal(candidate.ackedStatus[validators[2]].count, uint64(3)) + s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height) + s.Equal(candidate.ackedStatus[validators[3]].count, uint64(3)) // Check the first deliver. blocks, early, err := to.processBlock(b02) @@ -638,33 +660,33 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { s.checkNotInWorkingSet(to, b10) // Check if candidates of next round are picked correctly. - s.Len(to.candidateAckingStatusVectors, 2) + s.Len(to.candidates, 2) // Check b01's height vector. - vec = to.candidateAckingStatusVectors[b11.Hash] - s.Require().NotNil(vec) - s.NotContains(vec, validators[4]) - s.Equal(vec[validators[0]].minHeight, b01.Height) - s.Equal(vec[validators[0]].count, uint64(2)) - s.Equal(vec[validators[1]].minHeight, b11.Height) - s.Equal(vec[validators[1]].count, uint64(2)) - s.Equal(vec[validators[2]].minHeight, b21.Height) - s.Equal(vec[validators[2]].count, uint64(2)) - s.Equal(vec[validators[3]].minHeight, b11.Height) - s.Equal(vec[validators[3]].count, uint64(2)) + candidate = to.candidates[b11.Hash] + s.Require().NotNil(candidate) + s.NotContains(candidate.ackedStatus, validators[4]) + s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height) + s.Equal(candidate.ackedStatus[validators[0]].count, uint64(2)) + s.Equal(candidate.ackedStatus[validators[1]].minHeight, b11.Height) + s.Equal(candidate.ackedStatus[validators[1]].count, uint64(2)) + s.Equal(candidate.ackedStatus[validators[2]].minHeight, b21.Height) + s.Equal(candidate.ackedStatus[validators[2]].count, uint64(2)) + s.Equal(candidate.ackedStatus[validators[3]].minHeight, b11.Height) + s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2)) // Check b20's height vector. - vec = to.candidateAckingStatusVectors[b20.Hash] - s.Require().NotNil(vec) - s.NotContains(vec, validators[4]) - s.Equal(vec[validators[0]].minHeight, b02.Height) - s.Equal(vec[validators[0]].count, uint64(1)) - s.Equal(vec[validators[1]].minHeight, b12.Height) - s.Equal(vec[validators[1]].count, uint64(1)) - s.Equal(vec[validators[2]].minHeight, b20.Height) - s.Equal(vec[validators[2]].count, uint64(3)) - s.Equal(vec[validators[3]].minHeight, b30.Height) - s.Equal(vec[validators[3]].count, uint64(3)) + candidate = to.candidates[b20.Hash] + s.Require().NotNil(candidate) + s.NotContains(candidate.ackedStatus, validators[4]) + s.Equal(candidate.ackedStatus[validators[0]].minHeight, b02.Height) + s.Equal(candidate.ackedStatus[validators[0]].count, uint64(1)) + s.Equal(candidate.ackedStatus[validators[1]].minHeight, b12.Height) + s.Equal(candidate.ackedStatus[validators[1]].count, uint64(1)) + s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height) + s.Equal(candidate.ackedStatus[validators[2]].count, uint64(3)) + s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height) + s.Equal(candidate.ackedStatus[validators[3]].count, uint64(3)) s.checkNotDeliver(to, b13) @@ -685,39 +707,39 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { s.checkNotDeliver(to, b14) // Make sure b01, b30, b40 are candidate in next round. - s.Len(to.candidateAckingStatusVectors, 3) - vec = to.candidateAckingStatusVectors[b01.Hash] - s.Require().NotNil(vec) - s.NotContains(vec, validators[4]) - s.Equal(vec[validators[0]].minHeight, b01.Height) - s.Equal(vec[validators[0]].count, uint64(3)) - s.Equal(vec[validators[1]].minHeight, b12.Height) - s.Equal(vec[validators[1]].count, uint64(3)) - s.Equal(vec[validators[2]].minHeight, b21.Height) - s.Equal(vec[validators[2]].count, uint64(2)) - s.Equal(vec[validators[3]].minHeight, b31.Height) - s.Equal(vec[validators[3]].count, uint64(2)) - - vec = to.candidateAckingStatusVectors[b30.Hash] - s.Require().NotNil(vec) - s.NotContains(vec, validators[4]) - s.Equal(vec[validators[0]].minHeight, b03.Height) - s.Equal(vec[validators[0]].count, uint64(1)) - s.Equal(vec[validators[1]].minHeight, b13.Height) - s.Equal(vec[validators[1]].count, uint64(2)) - s.Equal(vec[validators[2]].minHeight, b22.Height) - s.Equal(vec[validators[2]].count, uint64(1)) - s.Equal(vec[validators[3]].minHeight, b30.Height) - s.Equal(vec[validators[3]].count, uint64(3)) - - vec = to.candidateAckingStatusVectors[b40.Hash] - s.Require().NotNil(vec) - s.NotContains(vec, validators[0]) - s.NotContains(vec, validators[1]) - s.NotContains(vec, validators[2]) - s.NotContains(vec, validators[3]) - s.Equal(vec[validators[4]].minHeight, b40.Height) - s.Equal(vec[validators[4]].count, uint64(3)) + s.Len(to.candidates, 3) + candidate = to.candidates[b01.Hash] + s.Require().NotNil(candidate) + s.NotContains(candidate.ackedStatus, validators[4]) + s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height) + s.Equal(candidate.ackedStatus[validators[0]].count, uint64(3)) + s.Equal(candidate.ackedStatus[validators[1]].minHeight, b12.Height) + s.Equal(candidate.ackedStatus[validators[1]].count, uint64(3)) + s.Equal(candidate.ackedStatus[validators[2]].minHeight, b21.Height) + s.Equal(candidate.ackedStatus[validators[2]].count, uint64(2)) + s.Equal(candidate.ackedStatus[validators[3]].minHeight, b31.Height) + s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2)) + + candidate = to.candidates[b30.Hash] + s.Require().NotNil(candidate) + s.NotContains(candidate.ackedStatus, validators[4]) + s.Equal(candidate.ackedStatus[validators[0]].minHeight, b03.Height) + s.Equal(candidate.ackedStatus[validators[0]].count, uint64(1)) + s.Equal(candidate.ackedStatus[validators[1]].minHeight, b13.Height) + s.Equal(candidate.ackedStatus[validators[1]].count, uint64(2)) + s.Equal(candidate.ackedStatus[validators[2]].minHeight, b22.Height) + s.Equal(candidate.ackedStatus[validators[2]].count, uint64(1)) + s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height) + s.Equal(candidate.ackedStatus[validators[3]].count, uint64(3)) + + candidate = to.candidates[b40.Hash] + s.Require().NotNil(candidate) + s.NotContains(candidate.ackedStatus, validators[0]) + s.NotContains(candidate.ackedStatus, validators[1]) + s.NotContains(candidate.ackedStatus, validators[2]) + s.NotContains(candidate.ackedStatus, validators[3]) + s.Equal(candidate.ackedStatus[validators[4]].minHeight, b40.Height) + s.Equal(candidate.ackedStatus[validators[4]].count, uint64(3)) // Make 'Acking Node Set' contains blocks from all validators, // this should trigger not-early deliver. @@ -731,8 +753,8 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { s.checkNotInWorkingSet(to, b30) // Make sure b21, b40 are candidates of next round. - s.Contains(to.candidateAckingStatusVectors, b21.Hash) - s.Contains(to.candidateAckingStatusVectors, b40.Hash) + s.Contains(to.candidates, b21.Hash) + s.Contains(to.candidates, b40.Hash) } func (s *TotalOrderingTestSuite) TestBasicCaseForK0() { @@ -807,30 +829,30 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK0() { s.checkNotDeliver(to, b21) s.checkNotDeliver(to, b31) - // Check status before delivering. - vec := to.candidateAckingStatusVectors[b00.Hash] - s.Require().NotNil(vec) - s.Len(vec, 1) - s.Equal(vec[validators[0]].minHeight, b00.Height) - s.Equal(vec[validators[0]].count, uint64(2)) - - vec = to.candidateAckingStatusVectors[b10.Hash] - s.Require().NotNil(vec) - s.Len(vec, 2) - s.Equal(vec[validators[0]].minHeight, b01.Height) - s.Equal(vec[validators[0]].count, uint64(1)) - s.Equal(vec[validators[1]].minHeight, b10.Height) - s.Equal(vec[validators[1]].count, uint64(2)) - - vec = to.candidateAckingStatusVectors[b20.Hash] - s.Require().NotNil(vec) - s.Len(vec, 3) - s.Equal(vec[validators[1]].minHeight, b11.Height) - s.Equal(vec[validators[1]].count, uint64(1)) - s.Equal(vec[validators[2]].minHeight, b20.Height) - s.Equal(vec[validators[2]].count, uint64(2)) - s.Equal(vec[validators[3]].minHeight, b30.Height) - s.Equal(vec[validators[3]].count, uint64(2)) + // Check candidate status before delivering. + candidate := to.candidates[b00.Hash] + s.Require().NotNil(candidate) + s.Len(candidate.ackedStatus, 1) + s.Equal(candidate.ackedStatus[validators[0]].minHeight, b00.Height) + s.Equal(candidate.ackedStatus[validators[0]].count, uint64(2)) + + candidate = to.candidates[b10.Hash] + s.Require().NotNil(candidate) + s.Len(candidate.ackedStatus, 2) + s.Equal(candidate.ackedStatus[validators[0]].minHeight, b01.Height) + s.Equal(candidate.ackedStatus[validators[0]].count, uint64(1)) + s.Equal(candidate.ackedStatus[validators[1]].minHeight, b10.Height) + s.Equal(candidate.ackedStatus[validators[1]].count, uint64(2)) + + candidate = to.candidates[b20.Hash] + s.Require().NotNil(candidate) + s.Len(candidate.ackedStatus, 3) + s.Equal(candidate.ackedStatus[validators[1]].minHeight, b11.Height) + s.Equal(candidate.ackedStatus[validators[1]].count, uint64(1)) + s.Equal(candidate.ackedStatus[validators[2]].minHeight, b20.Height) + s.Equal(candidate.ackedStatus[validators[2]].count, uint64(2)) + s.Equal(candidate.ackedStatus[validators[3]].minHeight, b30.Height) + s.Equal(candidate.ackedStatus[validators[3]].count, uint64(2)) // This new block should trigger non-early deliver. blocks, early, err := to.processBlock(b40) @@ -842,18 +864,35 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK0() { s.checkNotInWorkingSet(to, b20) // Make sure b10, b30 are candidates for next round. - s.Contains(to.candidateAckingStatusVectors, b10.Hash) - s.Contains(to.candidateAckingStatusVectors, b30.Hash) + s.Contains(to.candidates, b10.Hash) + s.Contains(to.candidates, b30.Hash) } func (s *TotalOrderingTestSuite) baseTestRandomlyGeneratedBlocks( totalOrderingConstructor func() *totalOrdering, - revealer test.Revealer, + validatorCount, blockCount int, + ackingCountGenerator func() int, repeat int) { + var ( + req = s.Require() + gen = test.NewBlocksGenerator(nil, hashBlock) + revealingSequence = make(map[string]struct{}) + orderingSequence = make(map[string]struct{}) + ) + + db, err := blockdb.NewMemBackedBlockDB() + req.Nil(err) + req.Nil(gen.Generate( + validatorCount, blockCount, ackingCountGenerator, db)) + iter, err := db.GetAll() + req.Nil(err) + // Setup a revealer that would reveal blocks forming + // valid DAGs. + revealer, err := test.NewRandomDAGRevealer(iter) + req.Nil(err) + // TODO (mission): make this part run concurrently. - revealingSequence := map[string]struct{}{} - orderingSequence := map[string]struct{}{} for i := 0; i < repeat; i++ { revealed := "" ordered := "" @@ -901,51 +940,45 @@ func (s *TotalOrderingTestSuite) baseTestRandomlyGeneratedBlocks( func (s *TotalOrderingTestSuite) TestRandomlyGeneratedBlocks() { var ( - validatorCount = 19 + validatorCount = 13 blockCount = 50 phi uint64 = 10 - repeat = 10 + repeat = 8 ) - // Prepare a randomly genearated blocks. - db, err := blockdb.NewMemBackedBlockDB("test-total-ordering-random.blockdb") - s.Require().Nil(err) - defer func() { - // If the test fails, keep the block database for troubleshooting. - if s.T().Failed() { - s.Nil(db.Close()) - } - }() - - gen := test.NewBlocksGenerator(nil, hashBlock) - s.Require().Nil(gen.Generate(validatorCount, blockCount, nil, db)) - iter, err := db.GetAll() - s.Require().Nil(err) - // Setup a revealer that would reveal blocks forming - // valid DAGs. - revealer, err := test.NewRandomDAGRevealer(iter) - s.Require().Nil(err) - - // Test for K=0. - constructor := func() *totalOrdering { - return newTotalOrdering(0, phi, uint64(validatorCount)) - } - s.baseTestRandomlyGeneratedBlocks(constructor, revealer, repeat) - // Test for K=1, - constructor = func() *totalOrdering { - return newTotalOrdering(1, phi, uint64(validatorCount)) + ackingCountGenerators := []func() int{ + nil, // Acking frequency with normal distribution. + test.MaxAckingCountGenerator(0), // Low acking frequency. + test.MaxAckingCountGenerator(validatorCount), // High acking frequency. } - s.baseTestRandomlyGeneratedBlocks(constructor, revealer, repeat) - // Test for K=2, - constructor = func() *totalOrdering { - return newTotalOrdering(2, phi, uint64(validatorCount)) - } - s.baseTestRandomlyGeneratedBlocks(constructor, revealer, repeat) - // Test for K=3, - constructor = func() *totalOrdering { - return newTotalOrdering(3, phi, uint64(validatorCount)) + + // Test based on different acking frequency. + for _, gen := range ackingCountGenerators { + // Test for K=0. + constructor := func() *totalOrdering { + return newTotalOrdering(0, phi, uint64(validatorCount)) + } + s.baseTestRandomlyGeneratedBlocks( + constructor, validatorCount, blockCount, gen, repeat) + // Test for K=1, + constructor = func() *totalOrdering { + return newTotalOrdering(1, phi, uint64(validatorCount)) + } + s.baseTestRandomlyGeneratedBlocks( + constructor, validatorCount, blockCount, gen, repeat) + // Test for K=2, + constructor = func() *totalOrdering { + return newTotalOrdering(2, phi, uint64(validatorCount)) + } + s.baseTestRandomlyGeneratedBlocks( + constructor, validatorCount, blockCount, gen, repeat) + // Test for K=3, + constructor = func() *totalOrdering { + return newTotalOrdering(3, phi, uint64(validatorCount)) + } + s.baseTestRandomlyGeneratedBlocks( + constructor, validatorCount, blockCount, gen, repeat) } - s.baseTestRandomlyGeneratedBlocks(constructor, revealer, repeat) } func TestTotalOrdering(t *testing.T) { |