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.

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) {