restore_test.go

Documentation: go.etcd.io/etcd/raft/v3/confchange

     1  // Copyright 2019 The etcd Authors
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package confchange
    16  
    17  import (
    18  	"math/rand"
    19  	"reflect"
    20  	"sort"
    21  	"testing"
    22  	"testing/quick"
    23  
    24  	pb "go.etcd.io/etcd/raft/v3/raftpb"
    25  	"go.etcd.io/etcd/raft/v3/tracker"
    26  )
    27  
    28  type rndConfChange pb.ConfState
    29  
    30  // Generate creates a random (valid) ConfState for use with quickcheck.
    31  func (rndConfChange) Generate(rand *rand.Rand, _ int) reflect.Value {
    32  	conv := func(sl []int) []uint64 {
    33  		// We want IDs but the incoming slice is zero-indexed, so add one to
    34  		// each.
    35  		out := make([]uint64, len(sl))
    36  		for i := range sl {
    37  			out[i] = uint64(sl[i] + 1)
    38  		}
    39  		return out
    40  	}
    41  	var cs pb.ConfState
    42  	// NB: never generate the empty ConfState, that one should be unit tested.
    43  	nVoters := 1 + rand.Intn(5)
    44  
    45  	nLearners := rand.Intn(5)
    46  	// The number of voters that are in the outgoing config but not in the
    47  	// incoming one. (We'll additionally retain a random number of the
    48  	// incoming voters below).
    49  	nRemovedVoters := rand.Intn(3)
    50  
    51  	// Voters, learners, and removed voters must not overlap. A "removed voter"
    52  	// is one that we have in the outgoing config but not the incoming one.
    53  	ids := conv(rand.Perm(2 * (nVoters + nLearners + nRemovedVoters)))
    54  
    55  	cs.Voters = ids[:nVoters]
    56  	ids = ids[nVoters:]
    57  
    58  	if nLearners > 0 {
    59  		cs.Learners = ids[:nLearners]
    60  		ids = ids[nLearners:]
    61  	}
    62  
    63  	// Roll the dice on how many of the incoming voters we decide were also
    64  	// previously voters.
    65  	//
    66  	// NB: this code avoids creating non-nil empty slices (here and below).
    67  	nOutgoingRetainedVoters := rand.Intn(nVoters + 1)
    68  	if nOutgoingRetainedVoters > 0 || nRemovedVoters > 0 {
    69  		cs.VotersOutgoing = append([]uint64(nil), cs.Voters[:nOutgoingRetainedVoters]...)
    70  		cs.VotersOutgoing = append(cs.VotersOutgoing, ids[:nRemovedVoters]...)
    71  	}
    72  	// Only outgoing voters that are not also incoming voters can be in
    73  	// LearnersNext (they represent demotions).
    74  	if nRemovedVoters > 0 {
    75  		if nLearnersNext := rand.Intn(nRemovedVoters + 1); nLearnersNext > 0 {
    76  			cs.LearnersNext = ids[:nLearnersNext]
    77  		}
    78  	}
    79  
    80  	cs.AutoLeave = len(cs.VotersOutgoing) > 0 && rand.Intn(2) == 1
    81  	return reflect.ValueOf(rndConfChange(cs))
    82  }
    83  
    84  func TestRestore(t *testing.T) {
    85  	cfg := quick.Config{MaxCount: 1000}
    86  
    87  	f := func(cs pb.ConfState) bool {
    88  		chg := Changer{
    89  			Tracker:   tracker.MakeProgressTracker(20),
    90  			LastIndex: 10,
    91  		}
    92  		cfg, prs, err := Restore(chg, cs)
    93  		if err != nil {
    94  			t.Error(err)
    95  			return false
    96  		}
    97  		chg.Tracker.Config = cfg
    98  		chg.Tracker.Progress = prs
    99  
   100  		for _, sl := range [][]uint64{
   101  			cs.Voters,
   102  			cs.Learners,
   103  			cs.VotersOutgoing,
   104  			cs.LearnersNext,
   105  		} {
   106  			sort.Slice(sl, func(i, j int) bool { return sl[i] < sl[j] })
   107  		}
   108  
   109  		cs2 := chg.Tracker.ConfState()
   110  		// NB: cs.Equivalent does the same "sorting" dance internally, but let's
   111  		// test it a bit here instead of relying on it.
   112  		if reflect.DeepEqual(cs, cs2) && cs.Equivalent(cs2) == nil && cs2.Equivalent(cs) == nil {
   113  			return true // success
   114  		}
   115  		t.Errorf(`
   116  before: %+#v
   117  after:  %+#v`, cs, cs2)
   118  		return false
   119  	}
   120  
   121  	ids := func(sl ...uint64) []uint64 {
   122  		return sl
   123  	}
   124  
   125  	// Unit tests.
   126  	for _, cs := range []pb.ConfState{
   127  		{},
   128  		{Voters: ids(1, 2, 3)},
   129  		{Voters: ids(1, 2, 3), Learners: ids(4, 5, 6)},
   130  		{Voters: ids(1, 2, 3), Learners: ids(5), VotersOutgoing: ids(1, 2, 4, 6), LearnersNext: ids(4)},
   131  	} {
   132  		if !f(cs) {
   133  			t.FailNow() // f() already logged a nice t.Error()
   134  		}
   135  	}
   136  
   137  	if err := quick.Check(func(cs rndConfChange) bool {
   138  		return f(pb.ConfState(cs))
   139  	}, &cfg); err != nil {
   140  		t.Error(err)
   141  	}
   142  }
   143
View as plain text