Scott Baker | 2d89798 | 2019-09-24 11:50:08 -0700 | [diff] [blame^] | 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 pb "go.etcd.io/etcd/raft/raftpb" |
| 18 | |
| 19 | // unstable.entries[i] has raft log position i+unstable.offset. |
| 20 | // Note that unstable.offset may be less than the highest log |
| 21 | // position in storage; this means that the next write to storage |
| 22 | // might need to truncate the log before persisting unstable.entries. |
| 23 | type unstable struct { |
| 24 | // the incoming unstable snapshot, if any. |
| 25 | snapshot *pb.Snapshot |
| 26 | // all entries that have not yet been written to storage. |
| 27 | entries []pb.Entry |
| 28 | offset uint64 |
| 29 | |
| 30 | logger Logger |
| 31 | } |
| 32 | |
| 33 | // maybeFirstIndex returns the index of the first possible entry in entries |
| 34 | // if it has a snapshot. |
| 35 | func (u *unstable) maybeFirstIndex() (uint64, bool) { |
| 36 | if u.snapshot != nil { |
| 37 | return u.snapshot.Metadata.Index + 1, true |
| 38 | } |
| 39 | return 0, false |
| 40 | } |
| 41 | |
| 42 | // maybeLastIndex returns the last index if it has at least one |
| 43 | // unstable entry or snapshot. |
| 44 | func (u *unstable) maybeLastIndex() (uint64, bool) { |
| 45 | if l := len(u.entries); l != 0 { |
| 46 | return u.offset + uint64(l) - 1, true |
| 47 | } |
| 48 | if u.snapshot != nil { |
| 49 | return u.snapshot.Metadata.Index, true |
| 50 | } |
| 51 | return 0, false |
| 52 | } |
| 53 | |
| 54 | // maybeTerm returns the term of the entry at index i, if there |
| 55 | // is any. |
| 56 | func (u *unstable) maybeTerm(i uint64) (uint64, bool) { |
| 57 | if i < u.offset { |
| 58 | if u.snapshot == nil { |
| 59 | return 0, false |
| 60 | } |
| 61 | if u.snapshot.Metadata.Index == i { |
| 62 | return u.snapshot.Metadata.Term, true |
| 63 | } |
| 64 | return 0, false |
| 65 | } |
| 66 | |
| 67 | last, ok := u.maybeLastIndex() |
| 68 | if !ok { |
| 69 | return 0, false |
| 70 | } |
| 71 | if i > last { |
| 72 | return 0, false |
| 73 | } |
| 74 | return u.entries[i-u.offset].Term, true |
| 75 | } |
| 76 | |
| 77 | func (u *unstable) stableTo(i, t uint64) { |
| 78 | gt, ok := u.maybeTerm(i) |
| 79 | if !ok { |
| 80 | return |
| 81 | } |
| 82 | // if i < offset, term is matched with the snapshot |
| 83 | // only update the unstable entries if term is matched with |
| 84 | // an unstable entry. |
| 85 | if gt == t && i >= u.offset { |
| 86 | u.entries = u.entries[i+1-u.offset:] |
| 87 | u.offset = i + 1 |
| 88 | u.shrinkEntriesArray() |
| 89 | } |
| 90 | } |
| 91 | |
| 92 | // shrinkEntriesArray discards the underlying array used by the entries slice |
| 93 | // if most of it isn't being used. This avoids holding references to a bunch of |
| 94 | // potentially large entries that aren't needed anymore. Simply clearing the |
| 95 | // entries wouldn't be safe because clients might still be using them. |
| 96 | func (u *unstable) shrinkEntriesArray() { |
| 97 | // We replace the array if we're using less than half of the space in |
| 98 | // it. This number is fairly arbitrary, chosen as an attempt to balance |
| 99 | // memory usage vs number of allocations. It could probably be improved |
| 100 | // with some focused tuning. |
| 101 | const lenMultiple = 2 |
| 102 | if len(u.entries) == 0 { |
| 103 | u.entries = nil |
| 104 | } else if len(u.entries)*lenMultiple < cap(u.entries) { |
| 105 | newEntries := make([]pb.Entry, len(u.entries)) |
| 106 | copy(newEntries, u.entries) |
| 107 | u.entries = newEntries |
| 108 | } |
| 109 | } |
| 110 | |
| 111 | func (u *unstable) stableSnapTo(i uint64) { |
| 112 | if u.snapshot != nil && u.snapshot.Metadata.Index == i { |
| 113 | u.snapshot = nil |
| 114 | } |
| 115 | } |
| 116 | |
| 117 | func (u *unstable) restore(s pb.Snapshot) { |
| 118 | u.offset = s.Metadata.Index + 1 |
| 119 | u.entries = nil |
| 120 | u.snapshot = &s |
| 121 | } |
| 122 | |
| 123 | func (u *unstable) truncateAndAppend(ents []pb.Entry) { |
| 124 | after := ents[0].Index |
| 125 | switch { |
| 126 | case after == u.offset+uint64(len(u.entries)): |
| 127 | // after is the next index in the u.entries |
| 128 | // directly append |
| 129 | u.entries = append(u.entries, ents...) |
| 130 | case after <= u.offset: |
| 131 | u.logger.Infof("replace the unstable entries from index %d", after) |
| 132 | // The log is being truncated to before our current offset |
| 133 | // portion, so set the offset and replace the entries |
| 134 | u.offset = after |
| 135 | u.entries = ents |
| 136 | default: |
| 137 | // truncate to after and copy to u.entries |
| 138 | // then append |
| 139 | u.logger.Infof("truncate the unstable entries before index %d", after) |
| 140 | u.entries = append([]pb.Entry{}, u.slice(u.offset, after)...) |
| 141 | u.entries = append(u.entries, ents...) |
| 142 | } |
| 143 | } |
| 144 | |
| 145 | func (u *unstable) slice(lo uint64, hi uint64) []pb.Entry { |
| 146 | u.mustCheckOutOfBounds(lo, hi) |
| 147 | return u.entries[lo-u.offset : hi-u.offset] |
| 148 | } |
| 149 | |
| 150 | // u.offset <= lo <= hi <= u.offset+len(u.entries) |
| 151 | func (u *unstable) mustCheckOutOfBounds(lo, hi uint64) { |
| 152 | if lo > hi { |
| 153 | u.logger.Panicf("invalid unstable.slice %d > %d", lo, hi) |
| 154 | } |
| 155 | upper := u.offset + uint64(len(u.entries)) |
| 156 | if lo < u.offset || hi > upper { |
| 157 | u.logger.Panicf("unstable.slice[%d,%d) out of bound [%d,%d]", lo, hi, u.offset, upper) |
| 158 | } |
| 159 | } |