From 46a84bff9ac419853550f7c17b13fb8633e507c9 Mon Sep 17 00:00:00 2001 From: Wei-Ning Huang Date: Wed, 18 Jul 2018 13:20:20 +0800 Subject: core: refactor acking relationship (#3) * core: refactor acking relationship Use AckBy only, and remove IndirectAcks. Also fix the issue where validator is not filling Height when proposing block. --- core/blocklattice.go | 104 +++++++------------------ core/blocklattice_test.go | 192 +++++++++++++++++++++++++--------------------- core/types/block.go | 5 +- 3 files changed, 135 insertions(+), 166 deletions(-) (limited to 'core') diff --git a/core/blocklattice.go b/core/blocklattice.go index 10f4b51..0da09d6 100644 --- a/core/blocklattice.go +++ b/core/blocklattice.go @@ -126,9 +126,8 @@ func (l *BlockLattice) getBlock(hash common.Hash) *types.Block { // processAcks updates the ack count of the blocks that is acked by *b*. func (l *BlockLattice) processAcks(b *types.Block) { - if b.IndirectAcks == nil { - b.IndirectAcks = make(map[common.Hash]struct{}) - } + // Always acks it's own parent. + b.Acks[b.ParentHash] = struct{}{} for ackBlockHash := range b.Acks { ackedBlock, ok := l.blocks[ackBlockHash] @@ -140,36 +139,24 @@ func (l *BlockLattice) processAcks(b *types.Block) { panic(fmt.Sprintf("failed to get block: %v", ackBlockHash)) } - // Populate IndirectAcks. - for a := range ackedBlock.Acks { - if _, exists := b.Acks[a]; !exists { - b.IndirectAcks[a] = struct{}{} - } - } - for a := range ackedBlock.IndirectAcks { - if _, exists := b.Acks[a]; !exists { - b.IndirectAcks[a] = struct{}{} - } + // Populate Ackeds. + if ackedBlock.Ackeds == nil { + ackedBlock.Ackeds = make(map[common.Hash]struct{}) } - - // Populate AckedBy. - if ackedBlock.AckedBy == nil { - ackedBlock.AckedBy = make(map[common.Hash]bool) - } - ackedBlock.AckedBy[b.Hash] = true + ackedBlock.Ackeds[b.Hash] = struct{}{} bp := ackedBlock for bp != nil && bp.State < types.BlockStatusAcked { - if bp.AckedBy == nil { - bp.AckedBy = make(map[common.Hash]bool) + if bp.Ackeds == nil { + bp.Ackeds = make(map[common.Hash]struct{}) } - if _, exists := bp.AckedBy[b.Hash]; !exists { - bp.AckedBy[b.Hash] = false + if _, exists := bp.Ackeds[b.Hash]; !exists { + bp.Ackeds[b.Hash] = struct{}{} } // Calculate acked by nodes. ackedByNodes := make(map[types.ValidatorID]struct{}) - for hash := range bp.AckedBy { + for hash := range bp.Ackeds { bp := l.getBlock(hash) ackedByNodes[bp.ProposerID] = struct{}{} } @@ -180,6 +167,18 @@ func (l *BlockLattice) processAcks(b *types.Block) { } bp = l.getBlock(bp.ParentHash) } + + var populateAckBy func(bx, target *types.Block) + populateAckBy = func(bx, target *types.Block) { + for ab := range bx.Acks { + abb := l.getBlock(ab) + if abb.State < types.BlockStatusFinal { + abb.Ackeds[target.Hash] = struct{}{} + populateAckBy(abb, target) + } + } + } + populateAckBy(ackedBlock, b) } } @@ -312,28 +311,9 @@ func (l *BlockLattice) ProposeBlock(b *types.Block) { l.ackCandidateSet = make(map[types.ValidatorID]*types.Block) } -// DetectNack implements the NACK detection. -func (l *BlockLattice) DetectNack() { - -} - -func (l *BlockLattice) setAHV( - block common.Hash, vID types.ValidatorID, v uint64) { - - if l.AHV[block] == nil { - l.AHV[block] = make(map[types.ValidatorID]uint64) - } - l.AHV[block][vID] = v -} +// detectNack implements the NACK detection. +func (l *BlockLattice) detectNack() { -func (l *BlockLattice) pushABS(block *types.Block, vID types.ValidatorID) { - if l.ABS[block.Hash] == nil { - l.ABS[block.Hash] = make(map[types.ValidatorID]uint64) - } - v, exists := l.ABS[block.Hash][vID] - if !exists || block.Height < v { - l.ABS[block.Hash][vID] = block.Height - } } func (l *BlockLattice) abs() map[types.ValidatorID]struct{} { @@ -353,7 +333,7 @@ func (l *BlockLattice) calculateABSofBlock(b *types.Block) { var calculateABSRecursive func(target *types.Block) calculateABSRecursive = func(target *types.Block) { - for hash := range target.AckedBy { + for hash := range target.Ackeds { ackedByBlock := l.getBlock(hash) if ackedByBlock.State != types.BlockStatusToTo { continue @@ -419,40 +399,13 @@ func (l *BlockLattice) totalOrdering(b *types.Block) { } } - abs := l.abs() if acksOnlyFinal { l.candidateSet[b.Hash] = b - /* - for r := range abs { - l.setAHV(b.Hash, r, infinity) - } - */ } - /* - q := b.ProposerID - if _, exists := abs[q]; !exists { - for _, bp := range l.candidateSet { - if bp.Hash.Equal(b.Hash) { - continue - } - - _, directlyAckedBy := b.Acks[bp.Hash] - _, indirectlyAckedBy := b.IndirectAcks[bp.Hash] - - if directlyAckedBy || indirectlyAckedBy { - l.setAHV(bp.Hash, q, b.Height) - l.pushABS(bp, q) - } else { - l.setAHV(bp.Hash, q, infinity) - } - } - } - */ - // Update ABS and AHV. l.updateABSAHV() - abs = l.abs() + abs := l.abs() // Calculate preceding set. precedingSet := make(map[common.Hash]*types.Block) @@ -584,7 +537,8 @@ func (l *BlockLattice) totalOrdering(b *types.Block) { } acksOnlyFinal := true for ackedBlockHash := range block.Acks { - if !l.blockDB.Has(ackedBlockHash) { + bp := l.getBlock(ackedBlockHash) + if bp.State != types.BlockStatusFinal { acksOnlyFinal = false break } diff --git a/core/blocklattice_test.go b/core/blocklattice_test.go index e462b8a..380dc38 100644 --- a/core/blocklattice_test.go +++ b/core/blocklattice_test.go @@ -57,7 +57,7 @@ func (a *TestApp) ValidateBlock(b *types.Block) bool { } func (a *TestApp) Deliver(blocks []*types.Block, early bool) { - a.Outputs = blocks + a.Outputs = append(a.Outputs, blocks...) a.Early = early } @@ -201,7 +201,6 @@ func (s *BlockLatticeTest) SetupTest() { Height: 3, Acks: map[common.Hash]struct{}{ b12.Hash: struct{}{}, - b22.Hash: struct{}{}, b32.Hash: struct{}{}, }, } @@ -270,8 +269,7 @@ func (s *BlockLatticeTest) TestAckAndStateTransition() { s.Require().Equal(0, len(lattice.stronglyAckedSet)) s.Require().Equal(0, len(lattice.pendingSet)) - s.Require().Equal(0, len(b01.IndirectAcks)) - s.Require().Equal(0, len(b01.AckedBy)) + s.Require().Equal(0, len(b01.Ackeds)) // B12 lattice.ProcessBlock(b12) @@ -288,12 +286,10 @@ func (s *BlockLatticeTest) TestAckAndStateTransition() { lattice.ProcessBlock(b11) // b01 is acked. - s.Require().Equal(1, len(b01.AckedBy)) - s.Require().NotNil(b01.AckedBy[b11.Hash]) + s.Require().Equal(1, len(b01.Ackeds)) + s.Require().NotNil(b01.Ackeds[b11.Hash]) // b11 indirect acks. - s.Require().Equal(1, len(b11.IndirectAcks)) - s.Require().Equal(0, len(b11.AckedBy)) - s.Require().NotNil(b11.IndirectAcks[genesises[0].Hash]) + s.Require().Equal(0, len(b11.Ackeds)) // Set status check. s.Require().Equal(1, len(lattice.waitingSet)) @@ -311,11 +307,10 @@ func (s *BlockLatticeTest) TestAckAndStateTransition() { s.Require().Equal(0, len(lattice.pendingSet)) // b01 is acked. - s.Require().Equal(2, len(b01.AckedBy)) - s.Require().NotNil(b01.AckedBy[b21.Hash]) + s.Require().Equal(2, len(b01.Ackeds)) + s.Require().NotNil(b01.Ackeds[b21.Hash]) // b21 indirect acks. - s.Require().Equal(1, len(b21.IndirectAcks)) - s.Require().Equal(0, len(b21.AckedBy)) + s.Require().Equal(0, len(b21.Ackeds)) // B31 lattice.ProcessBlock(b31) @@ -330,23 +325,23 @@ func (s *BlockLatticeTest) TestAckAndStateTransition() { s.Require().Equal(types.BlockStatusToTo, b01.State) // b01 is acked. - s.Require().Equal(3, len(b01.AckedBy)) - s.Require().NotNil(b01.AckedBy[b31.Hash]) + s.Require().Equal(4, len(b01.Ackeds)) + s.Require().NotNil(b01.Ackeds[b31.Hash]) // b11 is acked. - s.Require().Equal(1, len(b11.AckedBy)) - s.Require().NotNil(b11.AckedBy[b31.Hash]) + s.Require().Equal(2, len(b11.Ackeds)) + s.Require().NotNil(b11.Ackeds[b31.Hash]) + s.Require().NotNil(b11.Ackeds[b12.Hash]) // b31 indirect acks. - s.Require().Equal(2, len(b31.IndirectAcks)) - s.Require().Equal(1, len(b31.AckedBy)) - s.Require().NotNil(b31.AckedBy[b12.Hash]) + s.Require().Equal(1, len(b31.Ackeds)) + s.Require().NotNil(b31.Ackeds[b12.Hash]) // b21 & b31 is acked by b12 (which is previously in waiting set). - s.Require().Equal(1, len(b21.AckedBy)) - s.Require().NotNil(b21.AckedBy[b12.Hash]) - s.Require().Equal(1, len(b31.AckedBy)) - s.Require().NotNil(b31.AckedBy[b12.Hash]) + s.Require().Equal(1, len(b21.Ackeds)) + s.Require().NotNil(b21.Ackeds[b12.Hash]) + s.Require().Equal(1, len(b31.Ackeds)) + s.Require().NotNil(b31.Ackeds[b12.Hash]) // B02 lattice.ProcessBlock(b02) @@ -355,19 +350,22 @@ func (s *BlockLatticeTest) TestAckAndStateTransition() { s.Require().Equal(0, len(lattice.waitingSet)) s.Require().Equal(4, len(lattice.ackCandidateSet)) s.Require().Equal(0, len(lattice.stronglyAckedSet)) - s.Require().Equal(1, len(lattice.pendingSet)) + s.Require().Equal(2, len(lattice.pendingSet)) + + s.Require().NotNil(lattice.pendingSet[b01.Hash]) + s.Require().NotNil(lattice.pendingSet[b11.Hash]) // b11 is acked. - s.Require().Equal(2, len(b11.AckedBy)) - s.Require().NotNil(b11.AckedBy[b02.Hash]) + s.Require().Equal(3, len(b11.Ackeds)) + s.Require().NotNil(b11.Ackeds[b02.Hash]) // b21 is acked. - s.Require().Equal(2, len(b21.AckedBy)) - s.Require().NotNil(b21.AckedBy[b02.Hash]) - s.Require().NotNil(b21.AckedBy[b12.Hash]) + s.Require().Equal(2, len(b21.Ackeds)) + s.Require().NotNil(b21.Ackeds[b02.Hash]) + s.Require().NotNil(b21.Ackeds[b12.Hash]) // b31 is acked. - s.Require().Equal(2, len(b31.AckedBy)) - s.Require().NotNil(b31.AckedBy[b02.Hash]) - s.Require().NotNil(b31.AckedBy[b12.Hash]) + s.Require().Equal(2, len(b31.Ackeds)) + s.Require().NotNil(b31.Ackeds[b02.Hash]) + s.Require().NotNil(b31.Ackeds[b12.Hash]) // B32 lattice.ProcessBlock(b32) @@ -376,17 +374,19 @@ func (s *BlockLatticeTest) TestAckAndStateTransition() { s.Require().Equal(0, len(lattice.waitingSet)) s.Require().Equal(4, len(lattice.ackCandidateSet)) s.Require().Equal(0, len(lattice.stronglyAckedSet)) - s.Require().Equal(2, len(lattice.pendingSet)) + s.Require().Equal(4, len(lattice.pendingSet)) s.Require().NotNil(lattice.pendingSet[b01.Hash]) + s.Require().NotNil(lattice.pendingSet[b11.Hash]) s.Require().NotNil(lattice.pendingSet[b21.Hash]) + s.Require().NotNil(lattice.pendingSet[b31.Hash]) // b02 is acked. - s.Require().Equal(1, len(b02.AckedBy)) - s.Require().NotNil(b02.AckedBy[b32.Hash]) + s.Require().Equal(1, len(b02.Ackeds)) + s.Require().NotNil(b02.Ackeds[b32.Hash]) // b12 is acked. - s.Require().Equal(1, len(b12.AckedBy)) - s.Require().NotNil(b12.AckedBy[b32.Hash]) + s.Require().Equal(1, len(b12.Ackeds)) + s.Require().NotNil(b12.Ackeds[b32.Hash]) // B22 lattice.ProcessBlock(b22) @@ -407,18 +407,14 @@ func (s *BlockLatticeTest) TestAckAndStateTransition() { s.Require().Equal(types.BlockStatusToTo, b31.State) // b02 is acked. - s.Require().Equal(2, len(b02.AckedBy)) - s.Require().NotNil(b02.AckedBy[b22.Hash]) + s.Require().Equal(2, len(b02.Ackeds)) + s.Require().NotNil(b02.Ackeds[b22.Hash]) // b12 is acked. - s.Require().Equal(2, len(b12.AckedBy)) - s.Require().NotNil(b12.AckedBy[b22.Hash]) + s.Require().Equal(2, len(b12.Ackeds)) + s.Require().NotNil(b12.Ackeds[b22.Hash]) // b31 is acked. - s.Require().Equal(3, len(b31.AckedBy)) - s.Require().NotNil(b31.AckedBy[b22.Hash]) - - // b22 indirect acks. - s.Require().NotNil(b22.IndirectAcks[b11.Hash]) - s.Require().NotNil(b22.IndirectAcks[b01.Hash]) + s.Require().Equal(4, len(b31.Ackeds)) + s.Require().NotNil(b31.Ackeds[b22.Hash]) // B13, B33, B03, B23 lattice.ProcessBlock(b13) @@ -434,17 +430,15 @@ func (s *BlockLatticeTest) TesttotalOrdering() { // B01 -> B12 -> B11 -> B21 -> B31 -> B02 -> B32 -> B22 -> B13 -> B33 // -> B03 -> B23 - lattice.ProcessBlock(b01) - lattice.ProcessBlock(b12) - lattice.ProcessBlock(b11) - lattice.ProcessBlock(b21) + lattice.ProcessBlock(b01, true) + lattice.ProcessBlock(b12, true) + lattice.ProcessBlock(b11, true) + lattice.ProcessBlock(b21, true) // B01 in pendingSet after b31 is recieved. - lattice.ProcessBlock(b31) + lattice.ProcessBlock(b31, true) s.Require().NotNil(lattice.pendingSet[b01.Hash]) - // Run total ordering for b01. - lattice.totalOrdering(b01) s.Require().Equal(0, len(s.app.Outputs)) s.Require().Equal(1, len(lattice.candidateSet)) s.Require().Equal(1, len(lattice.pendingSet)) @@ -453,67 +447,89 @@ func (s *BlockLatticeTest) TesttotalOrdering() { // ABS & AHV s.Require().Equal(1, len(lattice.AHV[b01.Hash])) - lattice.ProcessBlock(b02) - lattice.ProcessBlock(b32) + lattice.ProcessBlock(b02, true) + lattice.ProcessBlock(b32, true) // B21 in pendingSet after b32 is recieved. - s.Require().Equal(2, len(lattice.pendingSet)) - s.Require().NotNil(lattice.pendingSet[b01.Hash]) + s.Require().Equal(3, len(lattice.pendingSet)) + s.Require().NotNil(lattice.pendingSet[b11.Hash]) s.Require().NotNil(lattice.pendingSet[b21.Hash]) + s.Require().NotNil(lattice.pendingSet[b31.Hash]) - // Run total ordering for b21. - lattice.totalOrdering(b21) - s.Require().Equal(2, len(lattice.pendingSet)) - s.Require().Equal(0, len(s.app.Outputs)) + s.Require().Equal(3, len(lattice.pendingSet)) + s.Require().Equal(1, len(s.app.Outputs)) + s.Require().Equal(b01.Hash, s.app.Outputs[0].Hash) // ABS & AHV - s.Require().Equal(uint64(1), lattice.ABS[b01.Hash][b21.ProposerID]) - s.Require().Equal(uint64(1), lattice.AHV[b01.Hash][b21.ProposerID]) + lattice.updateABSAHV() - lattice.ProcessBlock(b22) - s.Require().Equal(4, len(lattice.pendingSet)) + s.Require().Equal(2, len(lattice.ABS[b11.Hash])) + s.Require().Equal(uint64(1), lattice.ABS[b11.Hash][validators[1]]) + s.Require().Equal(uint64(1), lattice.ABS[b11.Hash][validators[3]]) + s.Require().Equal(1, len(lattice.ABS[b21.Hash])) + s.Require().Equal(uint64(1), lattice.ABS[b21.Hash][validators[2]]) - // Run total ordering for b31. - lattice.totalOrdering(b31) - s.Require().Equal(1, len(s.app.Outputs)) - s.Require().Equal(b01.Hash, s.app.Outputs[0].Hash) - s.Require().Equal(false, s.app.Early) - lattice.updateABSAHV() - s.Require().Equal(3, len(lattice.abs())) - s.Require().Equal(2, len(lattice.candidateSet)) - s.app.Clear() + s.Require().Equal(uint64(1), lattice.AHV[b11.Hash][validators[1]]) + s.Require().Equal(infinity, lattice.AHV[b11.Hash][validators[2]]) + s.Require().Equal(uint64(1), lattice.AHV[b11.Hash][validators[3]]) + + s.Require().Equal(infinity, lattice.AHV[b21.Hash][validators[1]]) + s.Require().Equal(uint64(1), lattice.AHV[b21.Hash][validators[2]]) + s.Require().Equal(infinity, lattice.AHV[b21.Hash][validators[3]]) - lattice.totalOrdering(b22) + // B22 + s.app.Clear() + lattice.ProcessBlock(b22, true) s.Require().Equal(0, len(s.app.Outputs)) + s.Require().Equal(3, len(lattice.pendingSet)) s.Require().Equal(2, len(lattice.candidateSet)) + + // ABS & AHV + lattice.updateABSAHV() s.Require().Equal(3, len(lattice.abs())) + // B13 + s.app.Clear() lattice.ProcessBlock(b13, true) s.Require().Equal(2, len(s.app.Outputs)) s.Require().Equal(b21.Hash, s.app.Outputs[0].Hash) s.Require().Equal(b11.Hash, s.app.Outputs[1].Hash) s.Require().Equal(false, s.app.Early) - s.app.Clear() + s.Require().Equal(1, len(lattice.candidateSet)) + s.Require().NotNil(lattice.candidateSet[b31.Hash]) + + // ABS & AHV + lattice.updateABSAHV() + s.Require().Equal(3, len(lattice.abs())) + + // B33 + s.app.Clear() lattice.ProcessBlock(b33, true) s.Require().Equal(0, len(s.app.Outputs)) + s.Require().Equal(1, len(lattice.candidateSet)) + s.Require().Equal(3, len(lattice.pendingSet)) + s.Require().NotNil(lattice.candidateSet[b31.Hash]) - lattice.ProcessBlock(b03, true) - s.Require().Equal(1, len(s.app.Outputs)) - s.Require().Equal(b31.Hash, s.app.Outputs[0].Hash) - s.Require().Equal(false, s.app.Early) + // ABS & AHV + lattice.updateABSAHV() + s.Require().Equal(3, len(lattice.abs())) + + // B03 s.app.Clear() + lattice.ProcessBlock(b03, true) + s.Require().Equal(0, len(s.app.Outputs)) + // B23 + s.app.Clear() lattice.ProcessBlock(b23, true) - s.Require().Equal(2, len(s.app.Outputs)) - s.Require().Equal(b02.Hash, s.app.Outputs[0].Hash) - s.Require().Equal(b12.Hash, s.app.Outputs[1].Hash) + s.Require().Equal(1, len(s.app.Outputs)) + s.Require().Equal(b31.Hash, s.app.Outputs[0].Hash) s.Require().Equal(0, len(lattice.waitingSet)) s.Require().Equal(0, len(lattice.stronglyAckedSet)) - s.Require().Equal(2, len(lattice.pendingSet)) - lattice.updateABSAHV() - s.Require().Equal(2, len(lattice.abs())) + s.Require().Equal(4, len(lattice.pendingSet)) + s.Require().Equal(2, len(lattice.candidateSet)) } func TestBlockLattice(t *testing.T) { diff --git a/core/types/block.go b/core/types/block.go index 8808312..91b71da 100644 --- a/core/types/block.go +++ b/core/types/block.go @@ -45,9 +45,8 @@ type Block struct { Timestamps map[ValidatorID]time.Time Acks map[common.Hash]struct{} - IndirectAcks map[common.Hash]struct{} - AckedBy map[common.Hash]bool // bool: direct - State State + Ackeds map[common.Hash]struct{} + State State } func (b *Block) String() string { -- cgit v1.2.3