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 TestUnstableMaybeFirstIndex(t *testing.T) { 25 tests := []struct { 26 entries []pb.Entry 27 offset uint64 28 snap *pb.Snapshot 29 30 wok bool 31 windex uint64 32 }{ 33 // no snapshot 34 { 35 []pb.Entry{{Index: 5, Term: 1}}, 5, nil, 36 false, 0, 37 }, 38 { 39 []pb.Entry{}, 0, nil, 40 false, 0, 41 }, 42 // has snapshot 43 { 44 []pb.Entry{{Index: 5, Term: 1}}, 5, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 1}}, 45 true, 5, 46 }, 47 { 48 []pb.Entry{}, 5, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 1}}, 49 true, 5, 50 }, 51 } 52 53 for i, tt := range tests { 54 u := unstable{ 55 entries: tt.entries, 56 offset: tt.offset, 57 snapshot: tt.snap, 58 logger: raftLogger, 59 } 60 index, ok := u.maybeFirstIndex() 61 if ok != tt.wok { 62 t.Errorf("#%d: ok = %t, want %t", i, ok, tt.wok) 63 } 64 if index != tt.windex { 65 t.Errorf("#%d: index = %d, want %d", i, index, tt.windex) 66 } 67 } 68} 69 70func TestMaybeLastIndex(t *testing.T) { 71 tests := []struct { 72 entries []pb.Entry 73 offset uint64 74 snap *pb.Snapshot 75 76 wok bool 77 windex uint64 78 }{ 79 // last in entries 80 { 81 []pb.Entry{{Index: 5, Term: 1}}, 5, nil, 82 true, 5, 83 }, 84 { 85 []pb.Entry{{Index: 5, Term: 1}}, 5, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 1}}, 86 true, 5, 87 }, 88 // last in snapshot 89 { 90 []pb.Entry{}, 5, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 1}}, 91 true, 4, 92 }, 93 // empty unstable 94 { 95 []pb.Entry{}, 0, nil, 96 false, 0, 97 }, 98 } 99 100 for i, tt := range tests { 101 u := unstable{ 102 entries: tt.entries, 103 offset: tt.offset, 104 snapshot: tt.snap, 105 logger: raftLogger, 106 } 107 index, ok := u.maybeLastIndex() 108 if ok != tt.wok { 109 t.Errorf("#%d: ok = %t, want %t", i, ok, tt.wok) 110 } 111 if index != tt.windex { 112 t.Errorf("#%d: index = %d, want %d", i, index, tt.windex) 113 } 114 } 115} 116 117func TestUnstableMaybeTerm(t *testing.T) { 118 tests := []struct { 119 entries []pb.Entry 120 offset uint64 121 snap *pb.Snapshot 122 index uint64 123 124 wok bool 125 wterm uint64 126 }{ 127 // term from entries 128 { 129 []pb.Entry{{Index: 5, Term: 1}}, 5, nil, 130 5, 131 true, 1, 132 }, 133 { 134 []pb.Entry{{Index: 5, Term: 1}}, 5, nil, 135 6, 136 false, 0, 137 }, 138 { 139 []pb.Entry{{Index: 5, Term: 1}}, 5, nil, 140 4, 141 false, 0, 142 }, 143 { 144 []pb.Entry{{Index: 5, Term: 1}}, 5, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 1}}, 145 5, 146 true, 1, 147 }, 148 { 149 []pb.Entry{{Index: 5, Term: 1}}, 5, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 1}}, 150 6, 151 false, 0, 152 }, 153 // term from snapshot 154 { 155 []pb.Entry{{Index: 5, Term: 1}}, 5, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 1}}, 156 4, 157 true, 1, 158 }, 159 { 160 []pb.Entry{{Index: 5, Term: 1}}, 5, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 1}}, 161 3, 162 false, 0, 163 }, 164 { 165 []pb.Entry{}, 5, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 1}}, 166 5, 167 false, 0, 168 }, 169 { 170 []pb.Entry{}, 5, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 1}}, 171 4, 172 true, 1, 173 }, 174 { 175 []pb.Entry{}, 0, nil, 176 5, 177 false, 0, 178 }, 179 } 180 181 for i, tt := range tests { 182 u := unstable{ 183 entries: tt.entries, 184 offset: tt.offset, 185 snapshot: tt.snap, 186 logger: raftLogger, 187 } 188 term, ok := u.maybeTerm(tt.index) 189 if ok != tt.wok { 190 t.Errorf("#%d: ok = %t, want %t", i, ok, tt.wok) 191 } 192 if term != tt.wterm { 193 t.Errorf("#%d: term = %d, want %d", i, term, tt.wterm) 194 } 195 } 196} 197 198func TestUnstableRestore(t *testing.T) { 199 u := unstable{ 200 entries: []pb.Entry{{Index: 5, Term: 1}}, 201 offset: 5, 202 snapshot: &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 1}}, 203 logger: raftLogger, 204 } 205 s := pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 6, Term: 2}} 206 u.restore(s) 207 208 if u.offset != s.Metadata.Index+1 { 209 t.Errorf("offset = %d, want %d", u.offset, s.Metadata.Index+1) 210 } 211 if len(u.entries) != 0 { 212 t.Errorf("len = %d, want 0", len(u.entries)) 213 } 214 if !reflect.DeepEqual(u.snapshot, &s) { 215 t.Errorf("snap = %v, want %v", u.snapshot, &s) 216 } 217} 218 219func TestUnstableStableTo(t *testing.T) { 220 tests := []struct { 221 entries []pb.Entry 222 offset uint64 223 snap *pb.Snapshot 224 index, term uint64 225 226 woffset uint64 227 wlen int 228 }{ 229 { 230 []pb.Entry{}, 0, nil, 231 5, 1, 232 0, 0, 233 }, 234 { 235 []pb.Entry{{Index: 5, Term: 1}}, 5, nil, 236 5, 1, // stable to the first entry 237 6, 0, 238 }, 239 { 240 []pb.Entry{{Index: 5, Term: 1}, {Index: 6, Term: 1}}, 5, nil, 241 5, 1, // stable to the first entry 242 6, 1, 243 }, 244 { 245 []pb.Entry{{Index: 6, Term: 2}}, 6, nil, 246 6, 1, // stable to the first entry and term mismatch 247 6, 1, 248 }, 249 { 250 []pb.Entry{{Index: 5, Term: 1}}, 5, nil, 251 4, 1, // stable to old entry 252 5, 1, 253 }, 254 { 255 []pb.Entry{{Index: 5, Term: 1}}, 5, nil, 256 4, 2, // stable to old entry 257 5, 1, 258 }, 259 // with snapshot 260 { 261 []pb.Entry{{Index: 5, Term: 1}}, 5, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 1}}, 262 5, 1, // stable to the first entry 263 6, 0, 264 }, 265 { 266 []pb.Entry{{Index: 5, Term: 1}, {Index: 6, Term: 1}}, 5, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 1}}, 267 5, 1, // stable to the first entry 268 6, 1, 269 }, 270 { 271 []pb.Entry{{Index: 6, Term: 2}}, 6, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 5, Term: 1}}, 272 6, 1, // stable to the first entry and term mismatch 273 6, 1, 274 }, 275 { 276 []pb.Entry{{Index: 5, Term: 1}}, 5, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 1}}, 277 4, 1, // stable to snapshot 278 5, 1, 279 }, 280 { 281 []pb.Entry{{Index: 5, Term: 2}}, 5, &pb.Snapshot{Metadata: pb.SnapshotMetadata{Index: 4, Term: 2}}, 282 4, 1, // stable to old entry 283 5, 1, 284 }, 285 } 286 287 for i, tt := range tests { 288 u := unstable{ 289 entries: tt.entries, 290 offset: tt.offset, 291 snapshot: tt.snap, 292 logger: raftLogger, 293 } 294 u.stableTo(tt.index, tt.term) 295 if u.offset != tt.woffset { 296 t.Errorf("#%d: offset = %d, want %d", i, u.offset, tt.woffset) 297 } 298 if len(u.entries) != tt.wlen { 299 t.Errorf("#%d: len = %d, want %d", i, len(u.entries), tt.wlen) 300 } 301 } 302} 303 304func TestUnstableTruncateAndAppend(t *testing.T) { 305 tests := []struct { 306 entries []pb.Entry 307 offset uint64 308 snap *pb.Snapshot 309 toappend []pb.Entry 310 311 woffset uint64 312 wentries []pb.Entry 313 }{ 314 // append to the end 315 { 316 []pb.Entry{{Index: 5, Term: 1}}, 5, nil, 317 []pb.Entry{{Index: 6, Term: 1}, {Index: 7, Term: 1}}, 318 5, []pb.Entry{{Index: 5, Term: 1}, {Index: 6, Term: 1}, {Index: 7, Term: 1}}, 319 }, 320 // replace the unstable entries 321 { 322 []pb.Entry{{Index: 5, Term: 1}}, 5, nil, 323 []pb.Entry{{Index: 5, Term: 2}, {Index: 6, Term: 2}}, 324 5, []pb.Entry{{Index: 5, Term: 2}, {Index: 6, Term: 2}}, 325 }, 326 { 327 []pb.Entry{{Index: 5, Term: 1}}, 5, nil, 328 []pb.Entry{{Index: 4, Term: 2}, {Index: 5, Term: 2}, {Index: 6, Term: 2}}, 329 4, []pb.Entry{{Index: 4, Term: 2}, {Index: 5, Term: 2}, {Index: 6, Term: 2}}, 330 }, 331 // truncate the existing entries and append 332 { 333 []pb.Entry{{Index: 5, Term: 1}, {Index: 6, Term: 1}, {Index: 7, Term: 1}}, 5, nil, 334 []pb.Entry{{Index: 6, Term: 2}}, 335 5, []pb.Entry{{Index: 5, Term: 1}, {Index: 6, Term: 2}}, 336 }, 337 { 338 []pb.Entry{{Index: 5, Term: 1}, {Index: 6, Term: 1}, {Index: 7, Term: 1}}, 5, nil, 339 []pb.Entry{{Index: 7, Term: 2}, {Index: 8, Term: 2}}, 340 5, []pb.Entry{{Index: 5, Term: 1}, {Index: 6, Term: 1}, {Index: 7, Term: 2}, {Index: 8, Term: 2}}, 341 }, 342 } 343 344 for i, tt := range tests { 345 u := unstable{ 346 entries: tt.entries, 347 offset: tt.offset, 348 snapshot: tt.snap, 349 logger: raftLogger, 350 } 351 u.truncateAndAppend(tt.toappend) 352 if u.offset != tt.woffset { 353 t.Errorf("#%d: offset = %d, want %d", i, u.offset, tt.woffset) 354 } 355 if !reflect.DeepEqual(u.entries, tt.wentries) { 356 t.Errorf("#%d: entries = %v, want %v", i, u.entries, tt.wentries) 357 } 358 } 359} 360