Source file src/go.etcd.io/etcd/raft/v3/log_test.go

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

     1  // Copyright 2015 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 raft
    16  
    17  import (
    18  	"reflect"
    19  	"testing"
    20  
    21  	pb "go.etcd.io/etcd/raft/v3/raftpb"
    22  )
    23  
    24  func TestFindConflict(t *testing.T) {
    25  	previousEnts := []pb.Entry{{Index: 1, Term: 1}, {Index: 2, Term: 2}, {Index: 3, Term: 3}}
    26  	tests := []struct {
    27  		ents      []pb.Entry
    28  		wconflict uint64
    29  	}{
    30  		// no conflict, empty ent
    31  		{[]pb.Entry{}, 0},
    32  		// no conflict
    33  		{[]pb.Entry{{Index: 1, Term: 1}, {Index: 2, Term: 2}, {Index: 3, Term: 3}}, 0},
    34  		{[]pb.Entry{{Index: 2, Term: 2}, {Index: 3, Term: 3}}, 0},
    35  		{[]pb.Entry{{Index: 3, Term: 3}}, 0},
    36  		// no conflict, but has new entries
    37  		{[]pb.Entry{{Index: 1, Term: 1}, {Index: 2, Term: 2}, {Index: 3, Term: 3}, {Index: 4, Term: 4}, {Index: 5, Term: 4}}, 4},
    38  		{[]pb.Entry{{Index: 2, Term: 2}, {Index: 3, Term: 3}, {Index: 4, Term: 4}, {Index: 5, Term: 4}}, 4},
    39  		{[]pb.Entry{{Index: 3, Term: 3}, {Index: 4, Term: 4}, {Index: 5, Term: 4}}, 4},
    40  		{[]pb.Entry{{Index: 4, Term: 4}, {Index: 5, Term: 4}}, 4},
    41  		// conflicts with existing entries
    42  		{[]pb.Entry{{Index: 1, Term: 4}, {Index: 2, Term: 4}}, 1},
    43  		{[]pb.Entry{{Index: 2, Term: 1}, {Index: 3, Term: 4}, {Index: 4, Term: 4}}, 2},
    44  		{[]pb.Entry{{Index: 3, Term: 1}, {Index: 4, Term: 2}, {Index: 5, Term: 4}, {Index: 6, Term: 4}}, 3},
    45  	}
    46  
    47  	for i, tt := range tests {
    48  		raftLog := newLog(NewMemoryStorage(), raftLogger)
    49  		raftLog.append(previousEnts...)
    50  
    51  		gconflict := raftLog.findConflict(tt.ents)
    52  		if gconflict != tt.wconflict {
    53  			t.Errorf("#%d: conflict = %d, want %d", i, gconflict, tt.wconflict)
    54  		}
    55  	}
    56  }
    57  
    58  func TestIsUpToDate(t *testing.T) {
    59  	previousEnts := []pb.Entry{{Index: 1, Term: 1}, {Index: 2, Term: 2}, {Index: 3, Term: 3}}
    60  	raftLog := newLog(NewMemoryStorage(), raftLogger)
    61  	raftLog.append(previousEnts...)
    62  	tests := []struct {
    63  		lastIndex uint64
    64  		term      uint64
    65  		wUpToDate bool
    66  	}{
    67  		// greater term, ignore lastIndex
    68  		{raftLog.lastIndex() - 1, 4, true},
    69  		{raftLog.lastIndex(), 4, true},
    70  		{raftLog.lastIndex() + 1, 4, true},
    71  		// smaller term, ignore lastIndex
    72  		{raftLog.lastIndex() - 1, 2, false},
    73  		{raftLog.lastIndex(), 2, false},
    74  		{raftLog.lastIndex() + 1, 2, false},
    75  		// equal term, equal or lager lastIndex wins
    76  		{raftLog.lastIndex() - 1, 3, false},
    77  		{raftLog.lastIndex(), 3, true},
    78  		{raftLog.lastIndex() + 1, 3, true},
    79  	}
    80  
    81  	for i, tt := range tests {
    82  		gUpToDate := raftLog.isUpToDate(tt.lastIndex, tt.term)
    83  		if gUpToDate != tt.wUpToDate {
    84  			t.Errorf("#%d: uptodate = %v, want %v", i, gUpToDate, tt.wUpToDate)
    85  		}
    86  	}
    87  }
    88  
    89  func TestAppend(t *testing.T) {
    90  	previousEnts := []pb.Entry{{Index: 1, Term: 1}, {Index: 2, Term: 2}}
    91  	tests := []struct {
    92  		ents      []pb.Entry
    93  		windex    uint64
    94  		wents     []pb.Entry
    95  		wunstable uint64
    96  	}{
    97  		{
    98  			[]pb.Entry{},
    99  			2,
   100  			[]pb.Entry{{Index: 1, Term: 1}, {Index: 2, Term: 2}},
   101  			3,
   102  		},
   103  		{
   104  			[]pb.Entry{{Index: 3, Term: 2}},
   105  			3,
   106  			[]pb.Entry{{Index: 1, Term: 1}, {Index: 2, Term: 2}, {Index: 3, Term: 2}},
   107  			3,
   108  		},
   109  		// conflicts with index 1
   110  		{
   111  			[]pb.Entry{{Index: 1, Term: 2}},
   112  			1,
   113  			[]pb.Entry{{Index: 1, Term: 2}},
   114  			1,
   115  		},
   116  		// conflicts with index 2
   117  		{
   118  			[]pb.Entry{{Index: 2, Term: 3}, {Index: 3, Term: 3}},
   119  			3,
   120  			[]pb.Entry{{Index: 1, Term: 1}, {Index: 2, Term: 3}, {Index: 3, Term: 3}},
   121  			2,
   122  		},
   123  	}
   124  
   125  	for i, tt := range tests {
   126  		storage := NewMemoryStorage()
   127  		storage.Append(previousEnts)
   128  		raftLog := newLog(storage, raftLogger)
   129  
   130  		index := raftLog.append(tt.ents...)
   131  		if index != tt.windex {
   132  			t.Errorf("#%d: lastIndex = %d, want %d", i, index, tt.windex)
   133  		}
   134  		g, err := raftLog.entries(1, noLimit)
   135  		if err != nil {
   136  			t.Fatalf("#%d: unexpected error %v", i, err)
   137  		}
   138  		if !reflect.DeepEqual(g, tt.wents) {
   139  			t.Errorf("#%d: logEnts = %+v, want %+v", i, g, tt.wents)
   140  		}
   141  		if goff := raftLog.unstable.offset; goff != tt.wunstable {
   142  			t.Errorf("#%d: unstable = %d, want %d", i, goff, tt.wunstable)
   143  		}
   144  	}
   145  }
   146  
   147  // TestLogMaybeAppend ensures:
   148  // If the given (index, term) matches with the existing log:
   149  //  1. If an existing entry conflicts with a new one (same index
   150  //     but different terms), delete the existing entry and all that
   151  //     follow it
   152  //  2. Append any new entries not already in the log
   153  //
   154  // If the given (index, term) does not match with the existing log:
   155  //
   156  //	return false
   157  func TestLogMaybeAppend(t *testing.T) {
   158  	previousEnts := []pb.Entry{{Index: 1, Term: 1}, {Index: 2, Term: 2}, {Index: 3, Term: 3}}
   159  	lastindex := uint64(3)
   160  	lastterm := uint64(3)
   161  	commit := uint64(1)
   162  
   163  	tests := []struct {
   164  		logTerm   uint64
   165  		index     uint64
   166  		committed uint64
   167  		ents      []pb.Entry
   168  
   169  		wlasti  uint64
   170  		wappend bool
   171  		wcommit uint64
   172  		wpanic  bool
   173  	}{
   174  		// not match: term is different
   175  		{
   176  			lastterm - 1, lastindex, lastindex, []pb.Entry{{Index: lastindex + 1, Term: 4}},
   177  			0, false, commit, false,
   178  		},
   179  		// not match: index out of bound
   180  		{
   181  			lastterm, lastindex + 1, lastindex, []pb.Entry{{Index: lastindex + 2, Term: 4}},
   182  			0, false, commit, false,
   183  		},
   184  		// match with the last existing entry
   185  		{
   186  			lastterm, lastindex, lastindex, nil,
   187  			lastindex, true, lastindex, false,
   188  		},
   189  		{
   190  			lastterm, lastindex, lastindex + 1, nil,
   191  			lastindex, true, lastindex, false, // do not increase commit higher than lastnewi
   192  		},
   193  		{
   194  			lastterm, lastindex, lastindex - 1, nil,
   195  			lastindex, true, lastindex - 1, false, // commit up to the commit in the message
   196  		},
   197  		{
   198  			lastterm, lastindex, 0, nil,
   199  			lastindex, true, commit, false, // commit do not decrease
   200  		},
   201  		{
   202  			0, 0, lastindex, nil,
   203  			0, true, commit, false, // commit do not decrease
   204  		},
   205  		{
   206  			lastterm, lastindex, lastindex, []pb.Entry{{Index: lastindex + 1, Term: 4}},
   207  			lastindex + 1, true, lastindex, false,
   208  		},
   209  		{
   210  			lastterm, lastindex, lastindex + 1, []pb.Entry{{Index: lastindex + 1, Term: 4}},
   211  			lastindex + 1, true, lastindex + 1, false,
   212  		},
   213  		{
   214  			lastterm, lastindex, lastindex + 2, []pb.Entry{{Index: lastindex + 1, Term: 4}},
   215  			lastindex + 1, true, lastindex + 1, false, // do not increase commit higher than lastnewi
   216  		},
   217  		{
   218  			lastterm, lastindex, lastindex + 2, []pb.Entry{{Index: lastindex + 1, Term: 4}, {Index: lastindex + 2, Term: 4}},
   219  			lastindex + 2, true, lastindex + 2, false,
   220  		},
   221  		// match with the the entry in the middle
   222  		{
   223  			lastterm - 1, lastindex - 1, lastindex, []pb.Entry{{Index: lastindex, Term: 4}},
   224  			lastindex, true, lastindex, false,
   225  		},
   226  		{
   227  			lastterm - 2, lastindex - 2, lastindex, []pb.Entry{{Index: lastindex - 1, Term: 4}},
   228  			lastindex - 1, true, lastindex - 1, false,
   229  		},
   230  		{
   231  			lastterm - 3, lastindex - 3, lastindex, []pb.Entry{{Index: lastindex - 2, Term: 4}},
   232  			lastindex - 2, true, lastindex - 2, true, // conflict with existing committed entry
   233  		},
   234  		{
   235  			lastterm - 2, lastindex - 2, lastindex, []pb.Entry{{Index: lastindex - 1, Term: 4}, {Index: lastindex, Term: 4}},
   236  			lastindex, true, lastindex, false,
   237  		},
   238  	}
   239  
   240  	for i, tt := range tests {
   241  		raftLog := newLog(NewMemoryStorage(), raftLogger)
   242  		raftLog.append(previousEnts...)
   243  		raftLog.committed = commit
   244  		func() {
   245  			defer func() {
   246  				if r := recover(); r != nil {
   247  					if !tt.wpanic {
   248  						t.Errorf("%d: panic = %v, want %v", i, true, tt.wpanic)
   249  					}
   250  				}
   251  			}()
   252  			glasti, gappend := raftLog.maybeAppend(tt.index, tt.logTerm, tt.committed, tt.ents...)
   253  			gcommit := raftLog.committed
   254  
   255  			if glasti != tt.wlasti {
   256  				t.Errorf("#%d: lastindex = %d, want %d", i, glasti, tt.wlasti)
   257  			}
   258  			if gappend != tt.wappend {
   259  				t.Errorf("#%d: append = %v, want %v", i, gappend, tt.wappend)
   260  			}
   261  			if gcommit != tt.wcommit {
   262  				t.Errorf("#%d: committed = %d, want %d", i, gcommit, tt.wcommit)
   263  			}
   264  			if gappend && len(tt.ents) != 0 {
   265  				gents, err := raftLog.slice(raftLog.lastIndex()-uint64(len(tt.ents))+1, raftLog.lastIndex()+1, noLimit)
   266  				if err != nil {
   267  					t.Fatalf("unexpected error %v", err)
   268  				}
   269  				if !reflect.DeepEqual(tt.ents, gents) {
   270  					t.Errorf("#%d: appended entries = %v, want %v", i, gents, tt.ents)
   271  				}
   272  			}
   273  		}()
   274  	}
   275  }
   276  
   277  // TestCompactionSideEffects ensures that all the log related functionality works correctly after
   278  // a compaction.
   279  func TestCompactionSideEffects(t *testing.T) {
   280  	var i uint64
   281  	// Populate the log with 1000 entries; 750 in stable storage and 250 in unstable.
   282  	lastIndex := uint64(1000)
   283  	unstableIndex := uint64(750)
   284  	lastTerm := lastIndex
   285  	storage := NewMemoryStorage()
   286  	for i = 1; i <= unstableIndex; i++ {
   287  		storage.Append([]pb.Entry{{Term: i, Index: i}})
   288  	}
   289  	raftLog := newLog(storage, raftLogger)
   290  	for i = unstableIndex; i < lastIndex; i++ {
   291  		raftLog.append(pb.Entry{Term: i + 1, Index: i + 1})
   292  	}
   293  
   294  	ok := raftLog.maybeCommit(lastIndex, lastTerm)
   295  	if !ok {
   296  		t.Fatalf("maybeCommit returned false")
   297  	}
   298  	raftLog.appliedTo(raftLog.committed)
   299  
   300  	offset := uint64(500)
   301  	storage.Compact(offset)
   302  
   303  	if raftLog.lastIndex() != lastIndex {
   304  		t.Errorf("lastIndex = %d, want %d", raftLog.lastIndex(), lastIndex)
   305  	}
   306  
   307  	for j := offset; j <= raftLog.lastIndex(); j++ {
   308  		if mustTerm(raftLog.term(j)) != j {
   309  			t.Errorf("term(%d) = %d, want %d", j, mustTerm(raftLog.term(j)), j)
   310  		}
   311  	}
   312  
   313  	for j := offset; j <= raftLog.lastIndex(); j++ {
   314  		if !raftLog.matchTerm(j, j) {
   315  			t.Errorf("matchTerm(%d) = false, want true", j)
   316  		}
   317  	}
   318  
   319  	unstableEnts := raftLog.unstableEntries()
   320  	if g := len(unstableEnts); g != 250 {
   321  		t.Errorf("len(unstableEntries) = %d, want = %d", g, 250)
   322  	}
   323  	if unstableEnts[0].Index != 751 {
   324  		t.Errorf("Index = %d, want = %d", unstableEnts[0].Index, 751)
   325  	}
   326  
   327  	prev := raftLog.lastIndex()
   328  	raftLog.append(pb.Entry{Index: raftLog.lastIndex() + 1, Term: raftLog.lastIndex() + 1})
   329  	if raftLog.lastIndex() != prev+1 {
   330  		t.Errorf("lastIndex = %d, want = %d", raftLog.lastIndex(), prev+1)
   331  	}
   332  
   333  	ents, err := raftLog.entries(raftLog.lastIndex(), noLimit)
   334  	if err != nil {
   335  		t.Fatalf("unexpected error %v", err)
   336  	}
   337  	if len(ents) != 1 {
   338  		t.Errorf("len(entries) = %d, want = %d", len(ents), 1)
   339  	}
   340  }
   341  
   342  func TestHasNextEnts(t *testing.T) {
   343  	snap := pb.Snapshot{
   344  		Metadata: pb.SnapshotMetadata{Term: 1, Index: 3},
   345  	}
   346  	ents := []pb.Entry{
   347  		{Term: 1, Index: 4},
   348  		{Term: 1, Index: 5},
   349  		{Term: 1, Index: 6},
   350  	}
   351  	tests := []struct {
   352  		applied uint64
   353  		hasNext bool
   354  	}{
   355  		{0, true},
   356  		{3, true},
   357  		{4, true},
   358  		{5, false},
   359  	}
   360  	for i, tt := range tests {
   361  		storage := NewMemoryStorage()
   362  		storage.ApplySnapshot(snap)
   363  		raftLog := newLog(storage, raftLogger)
   364  		raftLog.append(ents...)
   365  		raftLog.maybeCommit(5, 1)
   366  		raftLog.appliedTo(tt.applied)
   367  
   368  		hasNext := raftLog.hasNextEnts()
   369  		if hasNext != tt.hasNext {
   370  			t.Errorf("#%d: hasNext = %v, want %v", i, hasNext, tt.hasNext)
   371  		}
   372  	}
   373  }
   374  
   375  func TestNextEnts(t *testing.T) {
   376  	snap := pb.Snapshot{
   377  		Metadata: pb.SnapshotMetadata{Term: 1, Index: 3},
   378  	}
   379  	ents := []pb.Entry{
   380  		{Term: 1, Index: 4},
   381  		{Term: 1, Index: 5},
   382  		{Term: 1, Index: 6},
   383  	}
   384  	tests := []struct {
   385  		applied uint64
   386  		wents   []pb.Entry
   387  	}{
   388  		{0, ents[:2]},
   389  		{3, ents[:2]},
   390  		{4, ents[1:2]},
   391  		{5, nil},
   392  	}
   393  	for i, tt := range tests {
   394  		storage := NewMemoryStorage()
   395  		storage.ApplySnapshot(snap)
   396  		raftLog := newLog(storage, raftLogger)
   397  		raftLog.append(ents...)
   398  		raftLog.maybeCommit(5, 1)
   399  		raftLog.appliedTo(tt.applied)
   400  
   401  		nents := raftLog.nextEnts()
   402  		if !reflect.DeepEqual(nents, tt.wents) {
   403  			t.Errorf("#%d: nents = %+v, want %+v", i, nents, tt.wents)
   404  		}
   405  	}
   406  }
   407  
   408  // TestUnstableEnts ensures unstableEntries returns the unstable part of the
   409  // entries correctly.
   410  func TestUnstableEnts(t *testing.T) {
   411  	previousEnts := []pb.Entry{{Term: 1, Index: 1}, {Term: 2, Index: 2}}
   412  	tests := []struct {
   413  		unstable uint64
   414  		wents    []pb.Entry
   415  	}{
   416  		{3, nil},
   417  		{1, previousEnts},
   418  	}
   419  
   420  	for i, tt := range tests {
   421  		// append stable entries to storage
   422  		storage := NewMemoryStorage()
   423  		storage.Append(previousEnts[:tt.unstable-1])
   424  
   425  		// append unstable entries to raftlog
   426  		raftLog := newLog(storage, raftLogger)
   427  		raftLog.append(previousEnts[tt.unstable-1:]...)
   428  
   429  		ents := raftLog.unstableEntries()
   430  		if l := len(ents); l > 0 {
   431  			raftLog.stableTo(ents[l-1].Index, ents[l-1].Term)
   432  		}
   433  		if !reflect.DeepEqual(ents, tt.wents) {
   434  			t.Errorf("#%d: unstableEnts = %+v, want %+v", i, ents, tt.wents)
   435  		}
   436  		w := previousEnts[len(previousEnts)-1].Index + 1
   437  		if g := raftLog.unstable.offset; g != w {
   438  			t.Errorf("#%d: unstable = %d, want %d", i, g, w)
   439  		}
   440  	}
   441  }
   442  
   443  func TestCommitTo(t *testing.T) {
   444  	previousEnts := []pb.Entry{{Term: 1, Index: 1}, {Term: 2, Index: 2}, {Term: 3, Index: 3}}
   445  	commit := uint64(2)
   446  	tests := []struct {
   447  		commit  uint64
   448  		wcommit uint64
   449  		wpanic  bool
   450  	}{
   451  		{3, 3, false},
   452  		{1, 2, false}, // never decrease
   453  		{4, 0, true},  // commit out of range -> panic
   454  	}
   455  	for i, tt := range tests {
   456  		func() {
   457  			defer func() {
   458  				if r := recover(); r != nil {
   459  					if !tt.wpanic {
   460  						t.Errorf("%d: panic = %v, want %v", i, true, tt.wpanic)
   461  					}
   462  				}
   463  			}()
   464  			raftLog := newLog(NewMemoryStorage(), raftLogger)
   465  			raftLog.append(previousEnts...)
   466  			raftLog.committed = commit
   467  			raftLog.commitTo(tt.commit)
   468  			if raftLog.committed != tt.wcommit {
   469  				t.Errorf("#%d: committed = %d, want %d", i, raftLog.committed, tt.wcommit)
   470  			}
   471  		}()
   472  	}
   473  }
   474  
   475  func TestStableTo(t *testing.T) {
   476  	tests := []struct {
   477  		stablei   uint64
   478  		stablet   uint64
   479  		wunstable uint64
   480  	}{
   481  		{1, 1, 2},
   482  		{2, 2, 3},
   483  		{2, 1, 1}, // bad term
   484  		{3, 1, 1}, // bad index
   485  	}
   486  	for i, tt := range tests {
   487  		raftLog := newLog(NewMemoryStorage(), raftLogger)
   488  		raftLog.append([]pb.Entry{{Index: 1, Term: 1}, {Index: 2, Term: 2}}...)
   489  		raftLog.stableTo(tt.stablei, tt.stablet)
   490  		if raftLog.unstable.offset != tt.wunstable {
   491  			t.Errorf("#%d: unstable = %d, want %d", i, raftLog.unstable.offset, tt.wunstable)
   492  		}
   493  	}
   494  }
   495  
   496  func TestStableToWithSnap(t *testing.T) {
   497  	snapi, snapt := uint64(5), uint64(2)
   498  	tests := []struct {
   499  		stablei uint64
   500  		stablet uint64
   501  		newEnts []pb.Entry
   502  
   503  		wunstable uint64
   504  	}{
   505  		{snapi + 1, snapt, nil, snapi + 1},
   506  		{snapi, snapt, nil, snapi + 1},
   507  		{snapi - 1, snapt, nil, snapi + 1},
   508  
   509  		{snapi + 1, snapt + 1, nil, snapi + 1},
   510  		{snapi, snapt + 1, nil, snapi + 1},
   511  		{snapi - 1, snapt + 1, nil, snapi + 1},
   512  
   513  		{snapi + 1, snapt, []pb.Entry{{Index: snapi + 1, Term: snapt}}, snapi + 2},
   514  		{snapi, snapt, []pb.Entry{{Index: snapi + 1, Term: snapt}}, snapi + 1},
   515  		{snapi - 1, snapt, []pb.Entry{{Index: snapi + 1, Term: snapt}}, snapi + 1},
   516  
   517  		{snapi + 1, snapt + 1, []pb.Entry{{Index: snapi + 1, Term: snapt}}, snapi + 1},
   518  		{snapi, snapt + 1, []pb.Entry{{Index: snapi + 1, Term: snapt}}, snapi + 1},
   519  		{snapi - 1, snapt + 1, []pb.Entry{{Index: snapi + 1, Term: snapt}}, snapi + 1},
   520  	}
   521  	for i, tt := range tests {
   522  		s := NewMemoryStorage()
   523  		s.ApplySnapshot(pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: snapi, Term: snapt}})
   524  		raftLog := newLog(s, raftLogger)
   525  		raftLog.append(tt.newEnts...)
   526  		raftLog.stableTo(tt.stablei, tt.stablet)
   527  		if raftLog.unstable.offset != tt.wunstable {
   528  			t.Errorf("#%d: unstable = %d, want %d", i, raftLog.unstable.offset, tt.wunstable)
   529  		}
   530  	}
   531  }
   532  
   533  // TestCompaction ensures that the number of log entries is correct after compactions.
   534  func TestCompaction(t *testing.T) {
   535  	tests := []struct {
   536  		lastIndex uint64
   537  		compact   []uint64
   538  		wleft     []int
   539  		wallow    bool
   540  	}{
   541  		// out of upper bound
   542  		{1000, []uint64{1001}, []int{-1}, false},
   543  		{1000, []uint64{300, 500, 800, 900}, []int{700, 500, 200, 100}, true},
   544  		// out of lower bound
   545  		{1000, []uint64{300, 299}, []int{700, -1}, false},
   546  	}
   547  
   548  	for i, tt := range tests {
   549  		func() {
   550  			defer func() {
   551  				if r := recover(); r != nil {
   552  					if tt.wallow {
   553  						t.Errorf("%d: allow = %v, want %v: %v", i, false, true, r)
   554  					}
   555  				}
   556  			}()
   557  
   558  			storage := NewMemoryStorage()
   559  			for i := uint64(1); i <= tt.lastIndex; i++ {
   560  				storage.Append([]pb.Entry{{Index: i}})
   561  			}
   562  			raftLog := newLog(storage, raftLogger)
   563  			raftLog.maybeCommit(tt.lastIndex, 0)
   564  			raftLog.appliedTo(raftLog.committed)
   565  
   566  			for j := 0; j < len(tt.compact); j++ {
   567  				err := storage.Compact(tt.compact[j])
   568  				if err != nil {
   569  					if tt.wallow {
   570  						t.Errorf("#%d.%d allow = %t, want %t", i, j, false, tt.wallow)
   571  					}
   572  					continue
   573  				}
   574  				if len(raftLog.allEntries()) != tt.wleft[j] {
   575  					t.Errorf("#%d.%d len = %d, want %d", i, j, len(raftLog.allEntries()), tt.wleft[j])
   576  				}
   577  			}
   578  		}()
   579  	}
   580  }
   581  
   582  func TestLogRestore(t *testing.T) {
   583  	index := uint64(1000)
   584  	term := uint64(1000)
   585  	snap := pb.SnapshotMetadata{Index: index, Term: term}
   586  	storage := NewMemoryStorage()
   587  	storage.ApplySnapshot(pb.Snapshot{Metadata: snap})
   588  	raftLog := newLog(storage, raftLogger)
   589  
   590  	if len(raftLog.allEntries()) != 0 {
   591  		t.Errorf("len = %d, want 0", len(raftLog.allEntries()))
   592  	}
   593  	if raftLog.firstIndex() != index+1 {
   594  		t.Errorf("firstIndex = %d, want %d", raftLog.firstIndex(), index+1)
   595  	}
   596  	if raftLog.committed != index {
   597  		t.Errorf("committed = %d, want %d", raftLog.committed, index)
   598  	}
   599  	if raftLog.unstable.offset != index+1 {
   600  		t.Errorf("unstable = %d, want %d", raftLog.unstable.offset, index+1)
   601  	}
   602  	if mustTerm(raftLog.term(index)) != term {
   603  		t.Errorf("term = %d, want %d", mustTerm(raftLog.term(index)), term)
   604  	}
   605  }
   606  
   607  func TestIsOutOfBounds(t *testing.T) {
   608  	offset := uint64(100)
   609  	num := uint64(100)
   610  	storage := NewMemoryStorage()
   611  	storage.ApplySnapshot(pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: offset}})
   612  	l := newLog(storage, raftLogger)
   613  	for i := uint64(1); i <= num; i++ {
   614  		l.append(pb.Entry{Index: i + offset})
   615  	}
   616  
   617  	first := offset + 1
   618  	tests := []struct {
   619  		lo, hi        uint64
   620  		wpanic        bool
   621  		wErrCompacted bool
   622  	}{
   623  		{
   624  			first - 2, first + 1,
   625  			false,
   626  			true,
   627  		},
   628  		{
   629  			first - 1, first + 1,
   630  			false,
   631  			true,
   632  		},
   633  		{
   634  			first, first,
   635  			false,
   636  			false,
   637  		},
   638  		{
   639  			first + num/2, first + num/2,
   640  			false,
   641  			false,
   642  		},
   643  		{
   644  			first + num - 1, first + num - 1,
   645  			false,
   646  			false,
   647  		},
   648  		{
   649  			first + num, first + num,
   650  			false,
   651  			false,
   652  		},
   653  		{
   654  			first + num, first + num + 1,
   655  			true,
   656  			false,
   657  		},
   658  		{
   659  			first + num + 1, first + num + 1,
   660  			true,
   661  			false,
   662  		},
   663  	}
   664  
   665  	for i, tt := range tests {
   666  		func() {
   667  			defer func() {
   668  				if r := recover(); r != nil {
   669  					if !tt.wpanic {
   670  						t.Errorf("%d: panic = %v, want %v: %v", i, true, false, r)
   671  					}
   672  				}
   673  			}()
   674  			err := l.mustCheckOutOfBounds(tt.lo, tt.hi)
   675  			if tt.wpanic {
   676  				t.Errorf("#%d: panic = %v, want %v", i, false, true)
   677  			}
   678  			if tt.wErrCompacted && err != ErrCompacted {
   679  				t.Errorf("#%d: err = %v, want %v", i, err, ErrCompacted)
   680  			}
   681  			if !tt.wErrCompacted && err != nil {
   682  				t.Errorf("#%d: unexpected err %v", i, err)
   683  			}
   684  		}()
   685  	}
   686  }
   687  
   688  func TestTerm(t *testing.T) {
   689  	var i uint64
   690  	offset := uint64(100)
   691  	num := uint64(100)
   692  
   693  	storage := NewMemoryStorage()
   694  	storage.ApplySnapshot(pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: offset, Term: 1}})
   695  	l := newLog(storage, raftLogger)
   696  	for i = 1; i < num; i++ {
   697  		l.append(pb.Entry{Index: offset + i, Term: i})
   698  	}
   699  
   700  	tests := []struct {
   701  		index uint64
   702  		w     uint64
   703  	}{
   704  		{offset - 1, 0},
   705  		{offset, 1},
   706  		{offset + num/2, num / 2},
   707  		{offset + num - 1, num - 1},
   708  		{offset + num, 0},
   709  	}
   710  
   711  	for j, tt := range tests {
   712  		term := mustTerm(l.term(tt.index))
   713  		if term != tt.w {
   714  			t.Errorf("#%d: at = %d, want %d", j, term, tt.w)
   715  		}
   716  	}
   717  }
   718  
   719  func TestTermWithUnstableSnapshot(t *testing.T) {
   720  	storagesnapi := uint64(100)
   721  	unstablesnapi := storagesnapi + 5
   722  
   723  	storage := NewMemoryStorage()
   724  	storage.ApplySnapshot(pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: storagesnapi, Term: 1}})
   725  	l := newLog(storage, raftLogger)
   726  	l.restore(pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: unstablesnapi, Term: 1}})
   727  
   728  	tests := []struct {
   729  		index uint64
   730  		w     uint64
   731  	}{
   732  		// cannot get term from storage
   733  		{storagesnapi, 0},
   734  		// cannot get term from the gap between storage ents and unstable snapshot
   735  		{storagesnapi + 1, 0},
   736  		{unstablesnapi - 1, 0},
   737  		// get term from unstable snapshot index
   738  		{unstablesnapi, 1},
   739  	}
   740  
   741  	for i, tt := range tests {
   742  		term := mustTerm(l.term(tt.index))
   743  		if term != tt.w {
   744  			t.Errorf("#%d: at = %d, want %d", i, term, tt.w)
   745  		}
   746  	}
   747  }
   748  
   749  func TestSlice(t *testing.T) {
   750  	var i uint64
   751  	offset := uint64(100)
   752  	num := uint64(100)
   753  	last := offset + num
   754  	half := offset + num/2
   755  	halfe := pb.Entry{Index: half, Term: half}
   756  
   757  	storage := NewMemoryStorage()
   758  	storage.ApplySnapshot(pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: offset}})
   759  	for i = 1; i < num/2; i++ {
   760  		storage.Append([]pb.Entry{{Index: offset + i, Term: offset + i}})
   761  	}
   762  	l := newLog(storage, raftLogger)
   763  	for i = num / 2; i < num; i++ {
   764  		l.append(pb.Entry{Index: offset + i, Term: offset + i})
   765  	}
   766  
   767  	tests := []struct {
   768  		from  uint64
   769  		to    uint64
   770  		limit uint64
   771  
   772  		w      []pb.Entry
   773  		wpanic bool
   774  	}{
   775  		// test no limit
   776  		{offset - 1, offset + 1, noLimit, nil, false},
   777  		{offset, offset + 1, noLimit, nil, false},
   778  		{half - 1, half + 1, noLimit, []pb.Entry{{Index: half - 1, Term: half - 1}, {Index: half, Term: half}}, false},
   779  		{half, half + 1, noLimit, []pb.Entry{{Index: half, Term: half}}, false},
   780  		{last - 1, last, noLimit, []pb.Entry{{Index: last - 1, Term: last - 1}}, false},
   781  		{last, last + 1, noLimit, nil, true},
   782  
   783  		// test limit
   784  		{half - 1, half + 1, 0, []pb.Entry{{Index: half - 1, Term: half - 1}}, false},
   785  		{half - 1, half + 1, uint64(halfe.Size() + 1), []pb.Entry{{Index: half - 1, Term: half - 1}}, false},
   786  		{half - 2, half + 1, uint64(halfe.Size() + 1), []pb.Entry{{Index: half - 2, Term: half - 2}}, false},
   787  		{half - 1, half + 1, uint64(halfe.Size() * 2), []pb.Entry{{Index: half - 1, Term: half - 1}, {Index: half, Term: half}}, false},
   788  		{half - 1, half + 2, uint64(halfe.Size() * 3), []pb.Entry{{Index: half - 1, Term: half - 1}, {Index: half, Term: half}, {Index: half + 1, Term: half + 1}}, false},
   789  		{half, half + 2, uint64(halfe.Size()), []pb.Entry{{Index: half, Term: half}}, false},
   790  		{half, half + 2, uint64(halfe.Size() * 2), []pb.Entry{{Index: half, Term: half}, {Index: half + 1, Term: half + 1}}, false},
   791  	}
   792  
   793  	for j, tt := range tests {
   794  		func() {
   795  			defer func() {
   796  				if r := recover(); r != nil {
   797  					if !tt.wpanic {
   798  						t.Errorf("%d: panic = %v, want %v: %v", j, true, false, r)
   799  					}
   800  				}
   801  			}()
   802  			g, err := l.slice(tt.from, tt.to, tt.limit)
   803  			if tt.from <= offset && err != ErrCompacted {
   804  				t.Fatalf("#%d: err = %v, want %v", j, err, ErrCompacted)
   805  			}
   806  			if tt.from > offset && err != nil {
   807  				t.Fatalf("#%d: unexpected error %v", j, err)
   808  			}
   809  			if !reflect.DeepEqual(g, tt.w) {
   810  				t.Errorf("#%d: from %d to %d = %v, want %v", j, tt.from, tt.to, g, tt.w)
   811  			}
   812  		}()
   813  	}
   814  }
   815  
   816  func mustTerm(term uint64, err error) uint64 {
   817  	if err != nil {
   818  		panic(err)
   819  	}
   820  	return term
   821  }
   822  

View as plain text