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