blob: 1005bf65cc5f4864050d754ecaf7b0d5ea5577e4 [file] [log] [blame]
William Kurkianea869482019-04-09 15:16:11 -04001// 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 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.
23type 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.
35func (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.
44func (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.
56func (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
77func (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.
96func (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
111func (u *unstable) stableSnapTo(i uint64) {
112 if u.snapshot != nil && u.snapshot.Metadata.Index == i {
113 u.snapshot = nil
114 }
115}
116
117func (u *unstable) restore(s pb.Snapshot) {
118 u.offset = s.Metadata.Index + 1
119 u.entries = nil
120 u.snapshot = &s
121}
122
123func (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
145func (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)
151func (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}