1 // 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 15 package confchange 16 17 import ( 18 pb "go.etcd.io/etcd/raft/v3/raftpb" 19 "go.etcd.io/etcd/raft/v3/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. 26 func 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 6) 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 99 func 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. 119 func 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 } 156