diff options
author | Mission Liao <mission.liao@dexon.org> | 2018-10-15 09:55:01 +0800 |
---|---|---|
committer | GitHub <noreply@github.com> | 2018-10-15 09:55:01 +0800 |
commit | 26bea95ae8a63e7bee4983e85d00a6ff6ca82f7c (patch) | |
tree | eeef65bc0556c889667e8721b7834df4551f12c2 | |
parent | 17449ca9402c7130d9587abc6f6764df6ad2e12e (diff) | |
download | dexon-consensus-26bea95ae8a63e7bee4983e85d00a6ff6ca82f7c.tar dexon-consensus-26bea95ae8a63e7bee4983e85d00a6ff6ca82f7c.tar.gz dexon-consensus-26bea95ae8a63e7bee4983e85d00a6ff6ca82f7c.tar.bz2 dexon-consensus-26bea95ae8a63e7bee4983e85d00a6ff6ca82f7c.tar.lz dexon-consensus-26bea95ae8a63e7bee4983e85d00a6ff6ca82f7c.tar.xz dexon-consensus-26bea95ae8a63e7bee4983e85d00a6ff6ca82f7c.tar.zst dexon-consensus-26bea95ae8a63e7bee4983e85d00a6ff6ca82f7c.zip |
core: check if flush is required when round switching in total-ordering (#197)
-rw-r--r-- | core/lattice-data.go | 38 | ||||
-rw-r--r-- | core/lattice-data_test.go | 101 | ||||
-rw-r--r-- | core/lattice.go | 32 | ||||
-rw-r--r-- | core/round-based-config.go | 50 | ||||
-rw-r--r-- | core/total-ordering.go | 171 | ||||
-rw-r--r-- | core/total-ordering_test.go | 132 |
6 files changed, 304 insertions, 220 deletions
diff --git a/core/lattice-data.go b/core/lattice-data.go index 95e0f06..50fa1d3 100644 --- a/core/lattice-data.go +++ b/core/lattice-data.go @@ -59,30 +59,21 @@ var ( // latticeDataConfig is the configuration for latticeData for each round. type latticeDataConfig struct { + roundBasedConfig // Number of chains between runs numChains uint32 // Block interval specifies reasonable time difference between // parent/child blocks. minBlockTimeInterval time.Duration maxBlockTimeInterval time.Duration - // roundBeginTime is the beginning of round, as local time. - roundBeginTime time.Time - roundInterval time.Duration - // roundEndTime is a cache for begin + interval. - roundEndTime time.Time } // Initiate latticeDataConfig from types.Config. -func (config *latticeDataConfig) fromConfig(cfg *types.Config) { +func (config *latticeDataConfig) fromConfig(roundID uint64, cfg *types.Config) { config.numChains = cfg.NumChains config.minBlockTimeInterval = cfg.MinBlockInterval config.maxBlockTimeInterval = cfg.MaxBlockInterval - config.roundInterval = cfg.RoundInterval -} - -func (config *latticeDataConfig) setRoundBeginTime(begin time.Time) { - config.roundBeginTime = begin - config.roundEndTime = begin.Add(config.roundInterval) + config.setupRoundBasedFields(roundID, cfg) } // Check if timestamp of a block is valid according to a reference time. @@ -102,15 +93,17 @@ func (config *latticeDataConfig) isValidGenesisBlockTime(b *types.Block) bool { func newGenesisLatticeDataConfig( dMoment time.Time, config *types.Config) *latticeDataConfig { c := &latticeDataConfig{} - c.fromConfig(config) + c.fromConfig(0, config) c.setRoundBeginTime(dMoment) return c } // newLatticeDataConfig constructs a latticeDataConfig instance. -func newLatticeDataConfig(prev, cur *types.Config) *latticeDataConfig { +func newLatticeDataConfig( + prev *latticeDataConfig, cur *types.Config) *latticeDataConfig { c := &latticeDataConfig{} - c.fromConfig(cur) + c.fromConfig(prev.roundID+1, cur) + c.setRoundBeginTime(prev.roundEndTime) return c } @@ -271,7 +264,6 @@ func (data *latticeData) sanityCheck(b *types.Block) error { // lattice and deletes blocks which will not be used. func (data *latticeData) addBlock( block *types.Block) (deliverable []*types.Block, err error) { - var ( bAck *types.Block updated bool @@ -465,26 +457,26 @@ func (data *latticeData) getConfig(round uint64) (config *latticeDataConfig) { // appendConfig appends a configuration for upcoming round. When you append // a config for round R, next time you can only append the config for round R+1. func (data *latticeData) appendConfig( - round uint64, config *latticeDataConfig) (err error) { + round uint64, config *types.Config) (err error) { // Make sure caller knows which round this config belongs to. if round != uint64(len(data.configs)) { return ErrRoundNotIncreasing } // Set round beginning time. - config.setRoundBeginTime(data.configs[len(data.configs)-1].roundEndTime) - data.configs = append(data.configs, config) + newConfig := newLatticeDataConfig(data.configs[len(data.configs)-1], config) + data.configs = append(data.configs, newConfig) // Resize each slice if incoming config contains larger number of chains. - if uint32(len(data.chains)) < config.numChains { - count := config.numChains - uint32(len(data.chains)) + if uint32(len(data.chains)) < newConfig.numChains { + count := newConfig.numChains - uint32(len(data.chains)) for _, status := range data.chains { status.lastAckPos = append( status.lastAckPos, make([]*types.Position, count)...) } - for i := uint32(len(data.chains)); i < config.numChains; i++ { + for i := uint32(len(data.chains)); i < newConfig.numChains; i++ { data.chains = append(data.chains, &chainStatus{ ID: i, blocks: []*types.Block{}, - lastAckPos: make([]*types.Position, config.numChains), + lastAckPos: make([]*types.Position, newConfig.numChains), }) } } diff --git a/core/lattice-data_test.go b/core/lattice-data_test.go index 4636b0f..263474c 100644 --- a/core/lattice-data_test.go +++ b/core/lattice-data_test.go @@ -54,23 +54,21 @@ func (s *LatticeDataTestSuite) genTestCase1() ( err error ) // Setup stuffs. - genesisConfig := &latticeDataConfig{ - numChains: chainNum, - minBlockTimeInterval: 2 * time.Nanosecond, - maxBlockTimeInterval: 1000 * time.Second, - roundInterval: 500 * time.Second, + genesisConfig := &types.Config{ + RoundInterval: 500 * time.Second, + NumChains: chainNum, + MinBlockInterval: 2 * time.Nanosecond, + MaxBlockInterval: 1000 * time.Second, } - genesisConfig.setRoundBeginTime(now) db, err := blockdb.NewMemBackedBlockDB() req.NoError(err) - data = newLatticeData(db, genesisConfig) - config := &latticeDataConfig{ - numChains: chainNum, - minBlockTimeInterval: 2 * time.Nanosecond, - maxBlockTimeInterval: 1000 * time.Second, - roundInterval: 1000 * time.Second, + data = newLatticeData(db, newGenesisLatticeDataConfig(now, genesisConfig)) + config := &types.Config{ + RoundInterval: 1000 * time.Second, + NumChains: chainNum, + MinBlockInterval: 2 * time.Nanosecond, + MaxBlockInterval: 1000 * time.Second, } - config.setRoundBeginTime(now) data.appendConfig(1, config) // Add genesis blocks. addBlock := func(b *types.Block) { @@ -365,25 +363,24 @@ func (s *LatticeDataTestSuite) TestRandomlyGeneratedBlocks() { } // Setup configuration that no restriction on block interval and // round cutting. - genesisConfig := &latticeDataConfig{ - numChains: chainNum, - minBlockTimeInterval: 0, - maxBlockTimeInterval: 1000 * time.Second, - roundInterval: 1000 * time.Second, + genesisConfig := &types.Config{ + RoundInterval: 1000 * time.Second, + NumChains: chainNum, + MinBlockInterval: 0, + MaxBlockInterval: 1000 * time.Second, } - genesisConfig.setRoundBeginTime(genesisTime) // Prepare a randomly generated blocks. db, err := blockdb.NewMemBackedBlockDB() req.NoError(err) gen := test.NewBlocksGenerator(&test.BlocksGeneratorConfig{ - NumChains: genesisConfig.numChains, - MinBlockTimeInterval: genesisConfig.minBlockTimeInterval, - MaxBlockTimeInterval: genesisConfig.maxBlockTimeInterval, + NumChains: genesisConfig.NumChains, + MinBlockTimeInterval: genesisConfig.MinBlockInterval, + MaxBlockTimeInterval: genesisConfig.MaxBlockInterval, }, nil, hashBlock) req.NoError(gen.Generate( 0, genesisTime, - genesisTime.Add(genesisConfig.roundInterval), + genesisTime.Add(genesisConfig.RoundInterval), db)) iter, err := db.GetAll() req.NoError(err) @@ -397,7 +394,8 @@ func (s *LatticeDataTestSuite) TestRandomlyGeneratedBlocks() { for i := 0; i < repeat; i++ { db, err := blockdb.NewMemBackedBlockDB() req.NoError(err) - data := newLatticeData(db, genesisConfig) + data := newLatticeData( + db, newGenesisLatticeDataConfig(genesisTime, genesisConfig)) deliveredHashes := common.Hashes{} revealedHashes := common.Hashes{} revealer.Reset() @@ -479,16 +477,16 @@ func (s *LatticeDataTestSuite) TestPrepareBlock() { ) // Setup configuration that no restriction on block interval and // round cutting. - genesisConfig := &latticeDataConfig{ - numChains: chainNum, - minBlockTimeInterval: 0, - maxBlockTimeInterval: 3000 * time.Second, - roundInterval: 3000 * time.Second, + genesisConfig := &types.Config{ + RoundInterval: 3000 * time.Second, + NumChains: chainNum, + MinBlockInterval: 0, + MaxBlockInterval: 3000 * time.Second, } - genesisConfig.setRoundBeginTime(time.Now().UTC()) db, err := blockdb.NewMemBackedBlockDB() req.NoError(err) - data := newLatticeData(db, genesisConfig) + data := newLatticeData( + db, newGenesisLatticeDataConfig(time.Now().UTC(), genesisConfig)) // Setup genesis blocks. b00 := s.prepareGenesisBlock(0) time.Sleep(minInterval) @@ -568,14 +566,14 @@ func (s *LatticeDataTestSuite) TestNextPosition() { // Test 'NextPosition' method when lattice is empty. // Setup a configuration that no restriction on block interval and // round cutting. - genesisConfig := &latticeDataConfig{ - numChains: 4, - minBlockTimeInterval: 0, - maxBlockTimeInterval: 1000 * time.Second, - roundInterval: 1000 * time.Second, + genesisConfig := &types.Config{ + RoundInterval: 1000 * time.Second, + NumChains: 4, + MinBlockInterval: 0, + MaxBlockInterval: 1000 * time.Second, } - genesisConfig.setRoundBeginTime(time.Now().UTC()) - data = newLatticeData(nil, genesisConfig) + data = newLatticeData( + nil, newGenesisLatticeDataConfig(time.Now().UTC(), genesisConfig)) s.Equal(data.nextPosition(0), types.Position{ChainID: 0, Height: 0}) } @@ -596,24 +594,20 @@ func (s *LatticeDataTestSuite) TestNumChainsChange() { // should be no error when passing to latticeData.sanityCheck // and latticeData.addBlock. // - The delivered blocks should form a valid DAG. - - begin := time.Now().UTC() - fixConfig := func(config *latticeDataConfig) *latticeDataConfig { - config.minBlockTimeInterval = 10 * time.Second - config.maxBlockTimeInterval = time.Hour // We don't care time. - config.roundInterval = 100 * time.Second - config.setRoundBeginTime(begin) - begin = config.roundEndTime + fixConfig := func(config *types.Config) *types.Config { + config.MinBlockInterval = 10 * time.Second + config.MaxBlockInterval = time.Hour // We don't care time. + config.RoundInterval = 100 * time.Second return config } var ( req = s.Require() maxChains = uint32(16) - configs = []*latticeDataConfig{ - fixConfig(&latticeDataConfig{numChains: 13}), - fixConfig(&latticeDataConfig{numChains: 10}), - fixConfig(&latticeDataConfig{numChains: maxChains}), - fixConfig(&latticeDataConfig{numChains: 7}), + configs = []*types.Config{ + fixConfig(&types.Config{NumChains: 13}), + fixConfig(&types.Config{NumChains: 10}), + fixConfig(&types.Config{NumChains: maxChains}), + fixConfig(&types.Config{NumChains: 7}), } randObj = rand.New(rand.NewSource(time.Now().UnixNano())) ) @@ -621,7 +615,8 @@ func (s *LatticeDataTestSuite) TestNumChainsChange() { db, err := blockdb.NewMemBackedBlockDB() req.NoError(err) // Set up latticeData instance. - lattice := newLatticeData(db, configs[0]) + lattice := newLatticeData(db, newGenesisLatticeDataConfig( + time.Now().UTC(), configs[0])) req.NoError(lattice.appendConfig(1, configs[1])) req.NoError(lattice.appendConfig(2, configs[2])) req.NoError(lattice.appendConfig(3, configs[3])) @@ -640,7 +635,7 @@ func (s *LatticeDataTestSuite) TestNumChainsChange() { } c := configs[nextRound] nextRound++ - for i := uint32(0); i < c.numChains; i++ { + for i := uint32(0); i < c.NumChains; i++ { candidateChainIDs = append(candidateChainIDs, i) } } diff --git a/core/lattice.go b/core/lattice.go index ab8aaec..442214b 100644 --- a/core/lattice.go +++ b/core/lattice.go @@ -23,7 +23,6 @@ import ( "github.com/dexon-foundation/dexon-consensus-core/common" "github.com/dexon-foundation/dexon-consensus-core/core/blockdb" - "github.com/dexon-foundation/dexon-consensus-core/core/crypto" "github.com/dexon-foundation/dexon-consensus-core/core/types" ) @@ -34,7 +33,6 @@ type Lattice struct { chainNum uint32 app Application debug Debug - lastConfig *types.Config pool blockPool data *latticeData toModule *totalOrdering @@ -51,19 +49,16 @@ func NewLattice( db blockdb.BlockDatabase) (s *Lattice) { // Create genesis latticeDataConfig. dataConfig := newGenesisLatticeDataConfig(dMoment, cfg) + toConfig := newGenesisTotalOrderingConfig(dMoment, cfg) s = &Lattice{ authModule: authModule, chainNum: cfg.NumChains, app: app, debug: debug, - lastConfig: cfg, pool: newBlockPool(cfg.NumChains), data: newLatticeData(db, dataConfig), - toModule: newTotalOrdering( - uint64(cfg.K), - uint64(float32(cfg.NumChains-1)*cfg.PhiRatio+1), - cfg.NumChains), - ctModule: newConsensusTimestamp(cfg.NumChains), + toModule: newTotalOrdering(toConfig), + ctModule: newConsensusTimestamp(cfg.NumChains), } return } @@ -96,12 +91,11 @@ func (s *Lattice) PrepareBlock( // If some acking blocks don't exists, Lattice would help to cache this block // and retry when lattice updated in Lattice.ProcessBlock. func (s *Lattice) SanityCheck(b *types.Block) (err error) { - // Check the hash of block. - hash, err := hashBlock(b) - if err != nil || hash != b.Hash { - err = ErrIncorrectHash + // Verify block's signature. + if err = s.authModule.VerifyBlock(b); err != nil { return } + // Make sure acks are sorted. for i := range b.Acks { if i == 0 { continue @@ -111,15 +105,7 @@ func (s *Lattice) SanityCheck(b *types.Block) (err error) { return } } - // Check the signer. - pubKey, err := crypto.SigToPub(b.Hash, b.Signature) - if err != nil { - return - } - if !b.ProposerID.Equal(types.NewNodeID(pubKey)) { - err = ErrIncorrectSignature - return - } + // Verify data in application layer. if !s.app.VerifyBlock(b) { err = ErrInvalidBlock return err @@ -227,8 +213,7 @@ func (s *Lattice) AppendConfig(round uint64, config *types.Config) (err error) { defer s.lock.Unlock() s.pool.resize(config.NumChains) - if err = s.data.appendConfig( - round, newLatticeDataConfig(s.lastConfig, config)); err != nil { + if err = s.data.appendConfig(round, config); err != nil { return } if err = s.toModule.appendConfig(round, config); err != nil { @@ -237,6 +222,5 @@ func (s *Lattice) AppendConfig(round uint64, config *types.Config) (err error) { if err = s.ctModule.appendConfig(round, config); err != nil { return } - s.lastConfig = config return } diff --git a/core/round-based-config.go b/core/round-based-config.go new file mode 100644 index 0000000..24ade49 --- /dev/null +++ b/core/round-based-config.go @@ -0,0 +1,50 @@ +// Copyright 2018 The dexon-consensus-core Authors +// This file is part of the dexon-consensus-core library. +// +// The dexon-consensus-core library is free software: you can redistribute it +// and/or modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation, either version 3 of the License, +// or (at your option) any later version. +// +// The dexon-consensus-core library is distributed in the hope that it will be +// useful, but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser +// General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the dexon-consensus-core library. If not, see +// <http://www.gnu.org/licenses/>. + +package core + +import ( + "time" + + "github.com/dexon-foundation/dexon-consensus-core/core/types" +) + +type roundBasedConfig struct { + roundID uint64 + // roundBeginTime is the beginning of round, as local time. + roundBeginTime time.Time + roundInterval time.Duration + // roundEndTime is a cache for begin + interval. + roundEndTime time.Time +} + +func (config *roundBasedConfig) setupRoundBasedFields( + roundID uint64, cfg *types.Config) { + config.roundID = roundID + config.roundInterval = cfg.RoundInterval +} + +func (config *roundBasedConfig) setRoundBeginTime(begin time.Time) { + config.roundBeginTime = begin + config.roundEndTime = begin.Add(config.roundInterval) +} + +// isValidLastBlock checks if a block is a valid last block of this round. +func (config *roundBasedConfig) isValidLastBlock(b *types.Block) bool { + return b.Position.Round == config.roundID && + b.Timestamp.After(config.roundEndTime) +} diff --git a/core/total-ordering.go b/core/total-ordering.go index c8e0b25..a1e2e76 100644 --- a/core/total-ordering.go +++ b/core/total-ordering.go @@ -22,6 +22,7 @@ import ( "math" "sort" "sync" + "time" "github.com/dexon-foundation/dexon-consensus-core/common" "github.com/dexon-foundation/dexon-consensus-core/core/types" @@ -41,9 +42,45 @@ var ( // totalOrderingConfig is the configuration for total ordering. type totalOrderingConfig struct { - k uint64 - phi uint64 + roundBasedConfig + // k represents the k in 'k-level total ordering'. + // In short, only block height equals to (global minimum height + k) + // would be taken into consideration. + k uint64 + // phi is a const to control how strong the leading preceding block + // should be. + phi uint64 + // chainNum is the count of chains. numChains uint32 + // Is round cutting required? + isFlushRequired bool +} + +func (config *totalOrderingConfig) fromConfig( + roundID uint64, cfg *types.Config) { + config.k = uint64(cfg.K) + config.numChains = cfg.NumChains + config.phi = uint64(float32(cfg.NumChains-1)*cfg.PhiRatio + 1) + config.setupRoundBasedFields(roundID, cfg) +} + +func newGenesisTotalOrderingConfig( + dMoment time.Time, config *types.Config) *totalOrderingConfig { + c := &totalOrderingConfig{} + c.fromConfig(0, config) + c.setRoundBeginTime(dMoment) + return c +} + +func newTotalOrderingConfig( + prev *totalOrderingConfig, cur *types.Config) *totalOrderingConfig { + c := &totalOrderingConfig{} + c.fromConfig(prev.roundID+1, cur) + c.setRoundBeginTime(prev.roundEndTime) + prev.isFlushRequired = c.k != prev.k || + c.phi != prev.phi || + c.numChains != prev.numChains + return c } // totalOrderingWinRecord caches which chains this candidate @@ -62,7 +99,6 @@ func (rec *totalOrderingWinRecord) reset() { func newTotalOrderingWinRecord(chainNum uint32) ( rec *totalOrderingWinRecord) { - rec = &totalOrderingWinRecord{} rec.reset() rec.wins = make([]int8, chainNum) @@ -71,10 +107,7 @@ func newTotalOrderingWinRecord(chainNum uint32) ( // grade implements the 'grade' potential function described in white paper. func (rec *totalOrderingWinRecord) grade( - chainNum uint32, - phi uint64, - globalAnsLength uint64) int { - + chainNum uint32, phi uint64, globalAnsLength uint64) int { if uint64(rec.count) >= phi { return 1 } else if uint64(rec.count) < phi-uint64(chainNum)+globalAnsLength { @@ -122,7 +155,6 @@ func newTotalOrderingObjectCache(chainNum uint32) *totalOrderingObjectCache { // candidate (or a global view of acking status of pending set). func (cache *totalOrderingObjectCache) requestAckedStatus() ( acked []*totalOrderingHeightRecord) { - if len(cache.ackedStatus) == 0 { acked = make([]*totalOrderingHeightRecord, cache.chainNum) for idx := range acked { @@ -143,14 +175,12 @@ func (cache *totalOrderingObjectCache) requestAckedStatus() ( // recycleAckedStatys recycles the structure to record acking status. func (cache *totalOrderingObjectCache) recycleAckedStatus( acked []*totalOrderingHeightRecord) { - cache.ackedStatus = append(cache.ackedStatus, acked) } // requestWinRecord requests an totalOrderingWinRecord instance. func (cache *totalOrderingObjectCache) requestWinRecord() ( win *totalOrderingWinRecord) { - win = cache.winRecordPool.Get().(*totalOrderingWinRecord) win.reset() return @@ -159,7 +189,6 @@ func (cache *totalOrderingObjectCache) requestWinRecord() ( // recycleWinRecord recycles an totalOrderingWinRecord instance. func (cache *totalOrderingObjectCache) recycleWinRecord( win *totalOrderingWinRecord) { - if win == nil { return } @@ -168,9 +197,7 @@ func (cache *totalOrderingObjectCache) recycleWinRecord( // requestHeightVector requests a structure to record acking heights // of one candidate. -func (cache *totalOrderingObjectCache) requestHeightVector() ( - hv []uint64) { - +func (cache *totalOrderingObjectCache) requestHeightVector() (hv []uint64) { if len(cache.heightVectors) == 0 { hv = make([]uint64, cache.chainNum) } else { @@ -186,16 +213,13 @@ func (cache *totalOrderingObjectCache) requestHeightVector() ( // recycleHeightVector recycles an instance to record acking heights // of one candidate. -func (cache *totalOrderingObjectCache) recycleHeightVector( - hv []uint64) { - +func (cache *totalOrderingObjectCache) recycleHeightVector(hv []uint64) { cache.heightVectors = append(cache.heightVectors, hv) } // requestWinRecordContainer requests a map of totalOrderingWinRecord. func (cache *totalOrderingObjectCache) requestWinRecordContainer() ( con []*totalOrderingWinRecord) { - if len(cache.winRecordContainers) == 0 { con = make([]*totalOrderingWinRecord, cache.chainNum) } else { @@ -212,14 +236,12 @@ func (cache *totalOrderingObjectCache) requestWinRecordContainer() ( // recycleWinRecordContainer recycles a map of totalOrderingWinRecord. func (cache *totalOrderingObjectCache) recycleWinRecordContainer( con []*totalOrderingWinRecord) { - cache.winRecordContainers = append(cache.winRecordContainers, con) } // requestAckedVector requests an acked vector instance. func (cache *totalOrderingObjectCache) requestAckedVector() ( acked map[common.Hash]struct{}) { - if len(cache.ackedVectors) == 0 { acked = make(map[common.Hash]struct{}) } else { @@ -236,7 +258,6 @@ func (cache *totalOrderingObjectCache) requestAckedVector() ( // recycleAckedVector recycles an acked vector instance. func (cache *totalOrderingObjectCache) recycleAckedVector( acked map[common.Hash]struct{}) { - if acked == nil { return } @@ -270,7 +291,6 @@ type totalOrderingCandidateInfo struct { func newTotalOrderingCandidateInfo( candidateHash common.Hash, objCache *totalOrderingObjectCache) *totalOrderingCandidateInfo { - return &totalOrderingCandidateInfo{ ackedStatus: objCache.requestAckedStatus(), winRecords: objCache.requestWinRecordContainer(), @@ -288,7 +308,6 @@ func (v *totalOrderingCandidateInfo) clean(otherCandidateChainID uint32) { // golangs' GC. func (v *totalOrderingCandidateInfo) recycle( objCache *totalOrderingObjectCache) { - if v.winRecords != nil { for _, win := range v.winRecords { objCache.recycleWinRecord(win) @@ -330,9 +349,7 @@ func (v *totalOrderingCandidateInfo) addBlock(b *types.Block) (err error) { // - k = 1 // then only block height >= 2 would be added to acking node set. func (v *totalOrderingCandidateInfo) getAckingNodeSetLength( - global *totalOrderingCandidateInfo, - k uint64) (count uint64) { - + global *totalOrderingCandidateInfo, k uint64) (count uint64) { var rec *totalOrderingHeightRecord for idx, gRec := range global.ackedStatus { if gRec.count == 0 { @@ -361,12 +378,10 @@ func (v *totalOrderingCandidateInfo) updateAckingHeightVector( k uint64, dirtyChainIDs []int, objCache *totalOrderingObjectCache) { - var ( idx int gRec, rec *totalOrderingHeightRecord ) - // The reason not to merge the two loops is the iteration over map // is expensive when chain count is large, iterating over dirty // chains is cheaper. @@ -420,12 +435,10 @@ func (v *totalOrderingCandidateInfo) updateWinRecord( other *totalOrderingCandidateInfo, dirtyChainIDs []int, objCache *totalOrderingObjectCache) { - var ( idx int height uint64 ) - // The reason not to merge the two loops is the iteration over map // is expensive when chain count is large, iterating over dirty // chains is cheaper. @@ -483,7 +496,6 @@ type totalOrderingGlobalVector struct { func newTotalOrderingGlobalVector( chainNum uint32) *totalOrderingGlobalVector { - return &totalOrderingGlobalVector{ blocks: make([][]*types.Block, chainNum), } @@ -505,14 +517,12 @@ func (global *totalOrderingGlobalVector) addBlock(b *types.Block) (err error) { // updateCandidateInfo udpate cached candidate info. func (global *totalOrderingGlobalVector) updateCandidateInfo( dirtyChainIDs []int, objCache *totalOrderingObjectCache) { - var ( idx int blocks []*types.Block info *totalOrderingCandidateInfo rec *totalOrderingHeightRecord ) - if global.cachedCandidateInfo == nil { info = newTotalOrderingCandidateInfo(common.Hash{}, objCache) for idx, blocks = range global.blocks { @@ -546,17 +556,8 @@ type totalOrdering struct { // pendings stores blocks awaiting to be ordered. pendings map[common.Hash]*types.Block - // k represents the k in 'k-level total ordering'. - // In short, only block height equals to (global minimum height + k) - // would be taken into consideration. - k uint64 - - // phi is a const to control how strong the leading preceding block - // should be. - phi uint64 - - // chainNum is the count of chains. - chainNum uint32 + // The round of config used when performing total ordering. + curRound uint64 // globalVector group all pending blocks by proposers and // sort them by block height. This structure is helpful when: @@ -591,26 +592,22 @@ type totalOrdering struct { configs []*totalOrderingConfig } -func newTotalOrdering(k, phi uint64, chainNum uint32) *totalOrdering { +// newTotalOrdering constructs an totalOrdering instance. +func newTotalOrdering(genesisConfig *totalOrderingConfig) *totalOrdering { + globalVector := newTotalOrderingGlobalVector(genesisConfig.numChains) + objCache := newTotalOrderingObjectCache(genesisConfig.numChains) + candidates := make([]*totalOrderingCandidateInfo, genesisConfig.numChains) to := &totalOrdering{ pendings: make(map[common.Hash]*types.Block), - k: k, - phi: phi, - chainNum: chainNum, - globalVector: newTotalOrderingGlobalVector(chainNum), - dirtyChainIDs: make([]int, 0, chainNum), + globalVector: globalVector, + dirtyChainIDs: make([]int, 0, genesisConfig.numChains), acked: make(map[common.Hash]map[common.Hash]struct{}), - objCache: newTotalOrderingObjectCache(chainNum), + objCache: objCache, candidateChainMapping: make(map[common.Hash]uint32), - candidates: make([]*totalOrderingCandidateInfo, chainNum), - candidateChainIDs: make([]uint32, 0, chainNum), - } - to.configs = []*totalOrderingConfig{ - &totalOrderingConfig{ - k: k, - phi: phi, - numChains: chainNum, - }} + candidates: candidates, + candidateChainIDs: make([]uint32, 0, genesisConfig.numChains), + } + to.configs = []*totalOrderingConfig{genesisConfig} return to } @@ -618,15 +615,12 @@ func newTotalOrdering(k, phi uint64, chainNum uint32) *totalOrdering { // round R, next time you can only add the config for round R+1. func (to *totalOrdering) appendConfig( round uint64, config *types.Config) error { - if round != uint64(len(to.configs)) { return ErrRoundNotIncreasing } - to.configs = append(to.configs, &totalOrderingConfig{ - numChains: config.NumChains, - k: uint64(config.K), - phi: uint64(float32(config.NumChains-1)*config.PhiRatio + 1), - }) + to.configs = append( + to.configs, + newTotalOrderingConfig(to.configs[len(to.configs)-1], config)) return nil } @@ -666,8 +660,8 @@ func (to *totalOrdering) buildBlockRelation(b *types.Block) { } } -// clean would remove a block from working set. This behaviour -// would prevent our memory usage growing infinity. +// clean a block from working set. This behaviour would prevent +// our memory usage growing infinity. func (to *totalOrdering) clean(b *types.Block) { var ( h = b.Hash @@ -699,7 +693,6 @@ func (to *totalOrdering) updateVectors(b *types.Block) (err error) { if err = to.globalVector.addBlock(b); err != nil { return } - // Update acking status of candidates. for candidateHash, chainID = range to.candidateChainMapping { if _, acked = to.acked[candidateHash][b.Hash]; !acked { @@ -720,7 +713,6 @@ func (to *totalOrdering) prepareCandidate(candidate *types.Block) { candidate.Hash, to.objCache) chainID = candidate.Position.ChainID ) - to.candidates[chainID] = info to.candidateChainMapping[candidate.Hash] = chainID // Add index to slot to allocated list, make sure the modified list sorted. @@ -728,7 +720,6 @@ func (to *totalOrdering) prepareCandidate(candidate *types.Block) { sort.Slice(to.candidateChainIDs, func(i, j int) bool { return to.candidateChainIDs[i] < to.candidateChainIDs[j] }) - info.ackedStatus[chainID] = &totalOrderingHeightRecord{ minHeight: candidate.Position.Height, count: uint64(len(to.globalVector.blocks[chainID])), @@ -780,13 +771,11 @@ func (to *totalOrdering) output(precedings map[common.Hash]struct{}) (ret []*typ to.globalVector.blocks[int(chainID)] = to.globalVector.blocks[int(chainID)][1:] ret = append(ret, b) - // Remove block relations. to.clean(b) to.dirtyChainIDs = append(to.dirtyChainIDs, int(chainID)) } sort.Sort(types.ByHash(ret)) - // Find new candidates from tip of globalVector of each chain. // The complexity here is O(N^2logN). // TODO(mission): only those tips that acking some blocks in @@ -815,20 +804,18 @@ func (to *totalOrdering) output(precedings map[common.Hash]struct{}) (ret []*typ // - check if the preceding set deliverable by checking potential function func (to *totalOrdering) generateDeliverSet() ( delivered map[common.Hash]struct{}, early bool) { - var ( chainID, otherChainID uint32 info, otherInfo *totalOrderingCandidateInfo precedings = make(map[uint32]struct{}) + cfg = to.configs[to.curRound] ) - to.globalVector.updateCandidateInfo(to.dirtyChainIDs, to.objCache) globalInfo := to.globalVector.cachedCandidateInfo for _, chainID = range to.candidateChainIDs { to.candidates[chainID].updateAckingHeightVector( - globalInfo, to.k, to.dirtyChainIDs, to.objCache) + globalInfo, cfg.k, to.dirtyChainIDs, to.objCache) } - // Update winning records for each candidate. // TODO(mission): It's not reasonable to // request one routine for each candidate, the context @@ -852,11 +839,10 @@ func (to *totalOrdering) generateDeliverSet() ( }(chainID, info) } wg.Wait() - // Reset dirty chains. to.dirtyChainIDs = to.dirtyChainIDs[:0] - - globalAnsLength := globalInfo.getAckingNodeSetLength(globalInfo, to.k) + // TODO(mission): ANS should be bound by current numChains. + globalAnsLength := globalInfo.getAckingNodeSetLength(globalInfo, cfg.k) CheckNextCandidateLoop: for _, chainID = range to.candidateChainIDs { info = to.candidates[chainID] @@ -865,9 +851,9 @@ CheckNextCandidateLoop: continue } otherInfo = to.candidates[otherChainID] + // TODO(mission): grade should be bound by current numChains. if otherInfo.winRecords[chainID].grade( - to.chainNum, to.phi, globalAnsLength) != 0 { - + cfg.numChains, cfg.phi, globalAnsLength) != 0 { continue CheckNextCandidateLoop } } @@ -876,7 +862,6 @@ CheckNextCandidateLoop: if len(precedings) == 0 { return } - // internal is a helper function to verify internal stability. internal := func() bool { var ( @@ -889,8 +874,9 @@ CheckNextCandidateLoop: } beaten = false for p = range precedings { + // TODO(mission): grade should be bound by current numChains. if beaten = to.candidates[p].winRecords[chainID].grade( - to.chainNum, to.phi, globalAnsLength) == 1; beaten { + cfg.numChains, cfg.phi, globalAnsLength) == 1; beaten { break } } @@ -900,7 +886,6 @@ CheckNextCandidateLoop: } return true } - // checkAHV is a helper function to verify external stability. // It would make sure some preceding block is strong enough // to lead the whole preceding set. @@ -915,7 +900,7 @@ CheckNextCandidateLoop: for _, height = range info.cachedHeightVector { if height != infinity { count++ - if count > to.phi { + if count > cfg.phi { return true } } @@ -923,25 +908,24 @@ CheckNextCandidateLoop: } return false } - // checkANS is a helper function to verify external stability. // It would make sure all preceding blocks are strong enough // to be delivered. checkANS := func() bool { var chainAnsLength uint64 for p := range precedings { + // TODO(mission): ANS should be bound by current numChains. chainAnsLength = to.candidates[p].getAckingNodeSetLength( - globalInfo, to.k) - if uint64(chainAnsLength) < uint64(to.chainNum)-to.phi { + globalInfo, cfg.k) + if uint64(chainAnsLength) < uint64(cfg.numChains)-cfg.phi { return false } } return true } - // If all chains propose enough blocks, we should force // to deliver since the whole picture of the DAG is revealed. - if globalAnsLength != uint64(to.chainNum) { + if globalAnsLength != uint64(cfg.numChains) { // Check internal stability first. if !internal() { return @@ -968,12 +952,11 @@ func (to *totalOrdering) processBlock(b *types.Block) ( // NOTE: I assume the block 'b' is already safe for total ordering. // That means, all its acking blocks are during/after // total ordering stage. - - if b.Position.ChainID >= to.chainNum { + cfg := to.configs[to.curRound] + if b.Position.ChainID >= cfg.numChains { err = ErrChainIDNotRecognized return } - to.pendings[b.Hash] = b to.buildBlockRelation(b) if err = to.updateVectors(b); err != nil { diff --git a/core/total-ordering_test.go b/core/total-ordering_test.go index 262b5d9..55c7cfb 100644 --- a/core/total-ordering_test.go +++ b/core/total-ordering_test.go @@ -102,7 +102,15 @@ func (s *TotalOrderingTestSuite) TestBlockRelation() { Acks: common.NewSortedHashes(common.Hashes{blockB.Hash}), } - to := newTotalOrdering(1, 3, uint32(len(nodes))) + genesisConfig := &totalOrderingConfig{ + roundBasedConfig: roundBasedConfig{ + roundInterval: 1000 * time.Second, + }, + k: 1, + phi: 3, + numChains: uint32(len(nodes)), + } + to := newTotalOrdering(genesisConfig) s.checkNotDeliver(to, blockA) s.checkNotDeliver(to, blockB) s.checkNotDeliver(to, blockC) @@ -283,7 +291,15 @@ func (s *TotalOrderingTestSuite) TestCycleDetection() { b10.Acks = append(b10.Acks, b10.Hash) // Make sure we won't hang when cycle exists. - to := newTotalOrdering(1, 3, uint32(len(nodes))) + genesisConfig := &totalOrderingConfig{ + roundBasedConfig: roundBasedConfig{ + roundInterval: 1000 * time.Second, + }, + k: 1, + phi: 3, + numChains: uint32(len(nodes)), + } + to := newTotalOrdering(genesisConfig) s.checkNotDeliver(to, b00) s.checkNotDeliver(to, b01) s.checkNotDeliver(to, b02) @@ -296,7 +312,15 @@ func (s *TotalOrderingTestSuite) TestCycleDetection() { func (s *TotalOrderingTestSuite) TestNotValidDAGDetection() { nodes := test.GenerateRandomNodeIDs(5) - to := newTotalOrdering(1, 3, uint32(len(nodes))) + genesisConfig := &totalOrderingConfig{ + roundBasedConfig: roundBasedConfig{ + roundInterval: 1000 * time.Second, + }, + k: 1, + phi: 3, + numChains: uint32(len(nodes)), + } + to := newTotalOrdering(genesisConfig) b00 := s.genGenesisBlock(nodes, 0, common.Hashes{}) b01 := &types.Block{ @@ -328,7 +352,15 @@ func (s *TotalOrderingTestSuite) TestEarlyDeliver() { // Even when B is not received, A should // be able to be delivered. nodes := test.GenerateRandomNodeIDs(5) - to := newTotalOrdering(2, 3, uint32(len(nodes))) + genesisConfig := &totalOrderingConfig{ + roundBasedConfig: roundBasedConfig{ + roundInterval: 1000 * time.Second, + }, + k: 2, + phi: 3, + numChains: uint32(len(nodes)), + } + to := newTotalOrdering(genesisConfig) genNextBlock := func(b *types.Block) *types.Block { return &types.Block{ ProposerID: b.ProposerID, @@ -433,7 +465,15 @@ func (s *TotalOrderingTestSuite) TestEarlyDeliver() { func (s *TotalOrderingTestSuite) TestBasicCaseForK2() { // It's a handcrafted test case. nodes := test.GenerateRandomNodeIDs(5) - to := newTotalOrdering(2, 3, uint32(len(nodes))) + genesisConfig := &totalOrderingConfig{ + roundBasedConfig: roundBasedConfig{ + roundInterval: 1000 * time.Second, + }, + k: 2, + phi: 3, + numChains: uint32(len(nodes)), + } + to := newTotalOrdering(genesisConfig) // Setup blocks. b00 := s.genGenesisBlock(nodes, 0, common.Hashes{}) b10 := s.genGenesisBlock(nodes, 1, common.Hashes{}) @@ -767,9 +807,17 @@ func (s *TotalOrderingTestSuite) TestBasicCaseForK0() { // v v v v // o o o <- o Height: 0 var ( - req = s.Require() - nodes = test.GenerateRandomNodeIDs(5) - to = newTotalOrdering(0, 3, uint32(len(nodes))) + nodes = test.GenerateRandomNodeIDs(5) + genesisConfig = &totalOrderingConfig{ + roundBasedConfig: roundBasedConfig{ + roundInterval: 1000 * time.Second, + }, + k: 0, + phi: 3, + numChains: uint32(len(nodes)), + } + req = s.Require() + to = newTotalOrdering(genesisConfig) ) // Setup blocks. b00 := s.genGenesisBlock(nodes, 0, common.Hashes{}) @@ -941,43 +989,75 @@ func (s *TotalOrderingTestSuite) baseTestRandomlyGeneratedBlocks( func (s *TotalOrderingTestSuite) TestRandomlyGeneratedBlocks() { var ( - chainNum = uint32(23) - phi uint64 = 10 - repeat = 15 + numChains = uint32(23) + phi = uint64(10) + repeat = 15 ) if testing.Short() { - chainNum = 7 + numChains = 7 repeat = 3 } ackingCountGenerators := []func() int{ nil, // Acking frequency with normal distribution. - test.MaxAckingCountGenerator(0), // Low acking frequency. - test.MaxAckingCountGenerator(chainNum), // High acking frequency. + test.MaxAckingCountGenerator(0), // Low acking frequency. + test.MaxAckingCountGenerator(numChains), // High acking frequency. } // Test based on different acking frequency. for _, gen := range ackingCountGenerators { // Test for K=0. - constructor := func(chainNum uint32) *totalOrdering { - return newTotalOrdering(0, phi, chainNum) + constructor := func(numChains uint32) *totalOrdering { + genesisConfig := &totalOrderingConfig{ + roundBasedConfig: roundBasedConfig{ + roundInterval: 1000 * time.Second, + }, + k: 0, + phi: phi, + numChains: numChains, + } + return newTotalOrdering(genesisConfig) } - s.baseTestRandomlyGeneratedBlocks(constructor, chainNum, gen, repeat) + s.baseTestRandomlyGeneratedBlocks(constructor, numChains, gen, repeat) // Test for K=1. - constructor = func(chainNum uint32) *totalOrdering { - return newTotalOrdering(1, phi, chainNum) + constructor = func(numChains uint32) *totalOrdering { + genesisConfig := &totalOrderingConfig{ + roundBasedConfig: roundBasedConfig{ + roundInterval: 1000 * time.Second, + }, + k: 1, + phi: phi, + numChains: numChains, + } + return newTotalOrdering(genesisConfig) } - s.baseTestRandomlyGeneratedBlocks(constructor, chainNum, gen, repeat) + s.baseTestRandomlyGeneratedBlocks(constructor, numChains, gen, repeat) // Test for K=2. - constructor = func(chainNum uint32) *totalOrdering { - return newTotalOrdering(2, phi, chainNum) + constructor = func(numChains uint32) *totalOrdering { + genesisConfig := &totalOrderingConfig{ + roundBasedConfig: roundBasedConfig{ + roundInterval: 1000 * time.Second, + }, + k: 2, + phi: phi, + numChains: numChains, + } + return newTotalOrdering(genesisConfig) } - s.baseTestRandomlyGeneratedBlocks(constructor, chainNum, gen, repeat) + s.baseTestRandomlyGeneratedBlocks(constructor, numChains, gen, repeat) // Test for K=3. - constructor = func(chainNum uint32) *totalOrdering { - return newTotalOrdering(3, phi, chainNum) + constructor = func(numChains uint32) *totalOrdering { + genesisConfig := &totalOrderingConfig{ + roundBasedConfig: roundBasedConfig{ + roundInterval: 1000 * time.Second, + }, + k: 3, + phi: phi, + numChains: numChains, + } + return newTotalOrdering(genesisConfig) } - s.baseTestRandomlyGeneratedBlocks(constructor, chainNum, gen, repeat) + s.baseTestRandomlyGeneratedBlocks(constructor, numChains, gen, repeat) } } |