blob: 724068da00d4a92426cd148c088412c168423d51 [file] [log] [blame]
Scott Baker8487c5d2019-10-18 12:49:46 -07001// Copyright 2019 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 confchange
16
17import (
18 pb "go.etcd.io/etcd/raft/raftpb"
19 "go.etcd.io/etcd/raft/tracker"
20)
21
22// toConfChangeSingle translates a conf state into 1) a slice of operations creating
23// first the config that will become the outgoing one, and then the incoming one, and
24// b) another slice that, when applied to the config resulted from 1), represents the
25// ConfState.
26func toConfChangeSingle(cs pb.ConfState) (out []pb.ConfChangeSingle, in []pb.ConfChangeSingle) {
27 // Example to follow along this code:
28 // voters=(1 2 3) learners=(5) outgoing=(1 2 4 6) learners_next=(4)
29 //
30 // This means that before entering the joint config, the configuration
31 // had voters (1 2 4) and perhaps some learners that are already gone.
32 // The new set of voters is (1 2 3), i.e. (1 2) were kept around, and (4 6)
33 // are no longer voters; however 4 is poised to become a learner upon leaving
34 // the joint state.
35 // We can't tell whether 5 was a learner before entering the joint config,
36 // but it doesn't matter (we'll pretend that it wasn't).
37 //
38 // The code below will construct
39 // outgoing = add 1; add 2; add 4; add 6
40 // incoming = remove 1; remove 2; remove 4; remove 6
41 // add 1; add 2; add 3;
42 // add-learner 5;
43 // add-learner 4;
44 //
45 // So, when starting with an empty config, after applying 'outgoing' we have
46 //
47 // quorum=(1 2 4 6)
48 //
49 // From which we enter a joint state via 'incoming'
50 //
51 // quorum=(1 2 3)&&(1 2 4 6) learners=(5) learners_next=(4)
52 //
53 // as desired.
54
55 for _, id := range cs.VotersOutgoing {
56 // If there are outgoing voters, first add them one by one so that the
57 // (non-joint) config has them all.
58 out = append(out, pb.ConfChangeSingle{
59 Type: pb.ConfChangeAddNode,
60 NodeID: id,
61 })
62
63 }
64
65 // We're done constructing the outgoing slice, now on to the incoming one
66 // (which will apply on top of the config created by the outgoing slice).
67
68 // First, we'll remove all of the outgoing voters.
69 for _, id := range cs.VotersOutgoing {
70 in = append(in, pb.ConfChangeSingle{
71 Type: pb.ConfChangeRemoveNode,
72 NodeID: id,
73 })
74 }
75 // Then we'll add the incoming voters and learners.
76 for _, id := range cs.Voters {
77 in = append(in, pb.ConfChangeSingle{
78 Type: pb.ConfChangeAddNode,
79 NodeID: id,
80 })
81 }
82 for _, id := range cs.Learners {
83 in = append(in, pb.ConfChangeSingle{
84 Type: pb.ConfChangeAddLearnerNode,
85 NodeID: id,
86 })
87 }
88 // Same for LearnersNext; these are nodes we want to be learners but which
89 // are currently voters in the outgoing config.
90 for _, id := range cs.LearnersNext {
91 in = append(in, pb.ConfChangeSingle{
92 Type: pb.ConfChangeAddLearnerNode,
93 NodeID: id,
94 })
95 }
96 return out, in
97}
98
99func chain(chg Changer, ops ...func(Changer) (tracker.Config, tracker.ProgressMap, error)) (tracker.Config, tracker.ProgressMap, error) {
100 for _, op := range ops {
101 cfg, prs, err := op(chg)
102 if err != nil {
103 return tracker.Config{}, nil, err
104 }
105 chg.Tracker.Config = cfg
106 chg.Tracker.Progress = prs
107 }
108 return chg.Tracker.Config, chg.Tracker.Progress, nil
109}
110
111// Restore takes a Changer (which must represent an empty configuration), and
112// runs a sequence of changes enacting the configuration described in the
113// ConfState.
114//
115// TODO(tbg) it's silly that this takes a Changer. Unravel this by making sure
116// the Changer only needs a ProgressMap (not a whole Tracker) at which point
117// this can just take LastIndex and MaxInflight directly instead and cook up
118// the results from that alone.
119func Restore(chg Changer, cs pb.ConfState) (tracker.Config, tracker.ProgressMap, error) {
120 outgoing, incoming := toConfChangeSingle(cs)
121
122 var ops []func(Changer) (tracker.Config, tracker.ProgressMap, error)
123
124 if len(outgoing) == 0 {
125 // No outgoing config, so just apply the incoming changes one by one.
126 for _, cc := range incoming {
127 cc := cc // loop-local copy
128 ops = append(ops, func(chg Changer) (tracker.Config, tracker.ProgressMap, error) {
129 return chg.Simple(cc)
130 })
131 }
132 } else {
133 // The ConfState describes a joint configuration.
134 //
135 // First, apply all of the changes of the outgoing config one by one, so
136 // that it temporarily becomes the incoming active config. For example,
137 // if the config is (1 2 3)&(2 3 4), this will establish (2 3 4)&().
138 for _, cc := range outgoing {
139 cc := cc // loop-local copy
140 ops = append(ops, func(chg Changer) (tracker.Config, tracker.ProgressMap, error) {
141 return chg.Simple(cc)
142 })
143 }
144 // Now enter the joint state, which rotates the above additions into the
145 // outgoing config, and adds the incoming config in. Continuing the
146 // example above, we'd get (1 2 3)&(2 3 4), i.e. the incoming operations
147 // would be removing 2,3,4 and then adding in 1,2,3 while transitioning
148 // into a joint state.
149 ops = append(ops, func(chg Changer) (tracker.Config, tracker.ProgressMap, error) {
150 return chg.EnterJoint(cs.AutoLeave, incoming...)
151 })
152 }
153
154 return chain(chg, ops...)
155}