1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355
// Copyright 2020 TiKV Project Authors. Licensed under Apache-2.0.
use crate::eraftpb::{ConfChangeSingle, ConfChangeType};
use crate::tracker::{Configuration, ProgressMap, ProgressTracker};
use crate::{Error, Result};
/// Change log for progress map.
pub enum MapChangeType {
Add,
Remove,
}
/// Changes made by `Changer`.
pub type MapChange = Vec<(u64, MapChangeType)>;
/// A map that stores updates instead of apply them directly.
pub struct IncrChangeMap<'a> {
changes: MapChange,
base: &'a ProgressMap,
}
impl IncrChangeMap<'_> {
pub fn into_changes(self) -> MapChange {
self.changes
}
fn contains(&self, id: u64) -> bool {
match self.changes.iter().rfind(|(i, _)| *i == id) {
Some((_, MapChangeType::Remove)) => false,
Some((_, MapChangeType::Add)) => true,
None => self.base.contains_key(&id),
}
}
}
/// Changer facilitates configuration changes. It exposes methods to handle
/// simple and joint consensus while performing the proper validation that allows
/// refusing invalid configuration changes before they affect the active
/// configuration.
pub struct Changer<'a> {
tracker: &'a ProgressTracker,
}
impl Changer<'_> {
/// Creates a changer.
pub fn new(tracker: &ProgressTracker) -> Changer {
Changer { tracker }
}
/// Verifies that the outgoing (=right) majority config of the joint
/// config is empty and initializes it with a copy of the incoming (=left)
/// majority config. That is, it transitions from
/// ```text
/// (1 2 3)&&()
/// ```
/// to
/// ```text
/// (1 2 3)&&(1 2 3)
/// ```.
///
/// The supplied changes are then applied to the incoming majority config,
/// resulting in a joint configuration that in terms of the Raft thesis[1]
/// (Section 4.3) corresponds to `C_{new,old}`.
///
/// [1]: https://github.com/ongardie/dissertation/blob/master/online-trim.pdf
pub fn enter_joint(
&self,
auto_leave: bool,
ccs: &[ConfChangeSingle],
) -> Result<(Configuration, MapChange)> {
if super::joint(self.tracker.conf()) {
return Err(Error::ConfChangeError("config is already joint".to_owned()));
}
let (mut cfg, mut prs) = self.check_and_copy()?;
if cfg.voters().incoming.is_empty() {
// We allow adding nodes to an empty config for convenience (testing and
// bootstrap), but you can't enter a joint state.
return Err(Error::ConfChangeError(
"can't make a zero-voter config joint".to_owned(),
));
}
cfg.voters
.outgoing
.extend(cfg.voters.incoming.iter().cloned());
self.apply(&mut cfg, &mut prs, ccs)?;
cfg.auto_leave = auto_leave;
check_invariants(&cfg, &prs)?;
Ok((cfg, prs.into_changes()))
}
/// Transitions out of a joint configuration. It is an error to call this method if
/// the configuration is not joint, i.e. if the outgoing majority config is empty.
///
/// The outgoing majority config of the joint configuration will be removed, that is,
/// the incoming config is promoted as the sole decision maker. In the notation of
/// the Raft thesis[1] (Section 4.3), this method transitions from `C_{new,old}` into
/// `C_new`.
///
/// At the same time, any staged learners (LearnersNext) the addition of which was
/// held back by an overlapping voter in the former outgoing config will be inserted
/// into Learners.
///
/// [1]: https://github.com/ongardie/dissertation/blob/master/online-trim.pdf
pub fn leave_joint(&self) -> Result<(Configuration, MapChange)> {
if !super::joint(self.tracker.conf()) {
return Err(Error::ConfChangeError(
"can't leave a non-joint config".to_owned(),
));
}
let (mut cfg, mut prs) = self.check_and_copy()?;
if cfg.voters().outgoing.is_empty() {
return Err(Error::ConfChangeError(format!(
"configuration is not joint: {:?}",
cfg
)));
}
cfg.learners.extend(cfg.learners_next.drain());
for id in &*cfg.voters.outgoing {
if !cfg.voters.incoming.contains(id) && !cfg.learners.contains(id) {
prs.changes.push((*id, MapChangeType::Remove));
}
}
cfg.voters.outgoing.clear();
cfg.auto_leave = false;
check_invariants(&cfg, &prs)?;
Ok((cfg, prs.into_changes()))
}
/// Carries out a series of configuration changes that (in aggregate) mutates the
/// incoming majority config `Voters[0]` by at most one. This method will return an
/// error if that is not the case, if the resulting quorum is zero, or if the
/// configuration is in a joint state (i.e. if there is an outgoing configuration).
pub fn simple(&mut self, ccs: &[ConfChangeSingle]) -> Result<(Configuration, MapChange)> {
if super::joint(self.tracker.conf()) {
return Err(Error::ConfChangeError(
"can't apply simple config change in joint config".to_owned(),
));
}
let (mut cfg, mut prs) = self.check_and_copy()?;
self.apply(&mut cfg, &mut prs, ccs)?;
if cfg
.voters
.incoming
.symmetric_difference(&self.tracker.conf().voters.incoming)
.count()
> 1
{
return Err(Error::ConfChangeError(
"more than one voter changed without entering joint config".to_owned(),
));
}
check_invariants(&cfg, &prs)?;
Ok((cfg, prs.into_changes()))
}
/// Applies a change to the configuration. By convention, changes to voters are always
/// made to the incoming majority config. Outgoing is either empty or preserves the
/// outgoing majority configuration while in a joint state.
fn apply(
&self,
cfg: &mut Configuration,
prs: &mut IncrChangeMap,
ccs: &[ConfChangeSingle],
) -> Result<()> {
for cc in ccs {
if cc.node_id == 0 {
// Replaces the NodeID with zero if it decides (downstream of
// raft) to not apply a change, so we have to have explicit code
// here to ignore these.
continue;
}
match cc.get_change_type() {
ConfChangeType::AddNode => self.make_voter(cfg, prs, cc.node_id),
ConfChangeType::AddLearnerNode => self.make_learner(cfg, prs, cc.node_id),
ConfChangeType::RemoveNode => self.remove(cfg, prs, cc.node_id),
}
}
if cfg.voters().incoming.is_empty() {
return Err(Error::ConfChangeError("removed all voters".to_owned()));
}
Ok(())
}
/// Adds or promotes the given ID to be a voter in the incoming majority config.
fn make_voter(&self, cfg: &mut Configuration, prs: &mut IncrChangeMap, id: u64) {
if !prs.contains(id) {
self.init_progress(cfg, prs, id, false);
return;
}
cfg.voters.incoming.insert(id);
cfg.learners.remove(&id);
cfg.learners_next.remove(&id);
}
/// Makes the given ID a learner or stages it to be a learner once an active joint
/// configuration is exited.
///
/// The former happens when the peer is not a part of the outgoing config, in which
/// case we either add a new learner or demote a voter in the incoming config.
///
/// The latter case occurs when the configuration is joint and the peer is a voter
/// in the outgoing config. In that case, we do not want to add the peer as a learner
/// because then we'd have to track a peer as a voter and learner simultaneously.
/// Instead, we add the learner to LearnersNext, so that it will be added to Learners
/// the moment the outgoing config is removed by LeaveJoint().
fn make_learner(&self, cfg: &mut Configuration, prs: &mut IncrChangeMap, id: u64) {
if !prs.contains(id) {
self.init_progress(cfg, prs, id, true);
return;
}
if cfg.learners.contains(&id) {
return;
}
cfg.voters.incoming.remove(&id);
cfg.learners.remove(&id);
cfg.learners_next.remove(&id);
// Use LearnersNext if we can't add the learner to Learners directly, i.e.
// if the peer is still tracked as a voter in the outgoing config. It will
// be turned into a learner in LeaveJoint().
//
// Otherwise, add a regular learner right away.
if cfg.voters().outgoing.contains(&id) {
cfg.learners_next.insert(id);
} else {
cfg.learners.insert(id);
}
}
/// Removes this peer as a voter or learner from the incoming config.
fn remove(&self, cfg: &mut Configuration, prs: &mut IncrChangeMap, id: u64) {
if !prs.contains(id) {
return;
}
cfg.voters.incoming.remove(&id);
cfg.learners.remove(&id);
cfg.learners_next.remove(&id);
// If the peer is still a voter in the outgoing config, keep the Progress.
if !cfg.voters.outgoing.contains(&id) {
prs.changes.push((id, MapChangeType::Remove));
}
}
/// Initializes a new progress for the given node or learner.
fn init_progress(
&self,
cfg: &mut Configuration,
prs: &mut IncrChangeMap,
id: u64,
is_learner: bool,
) {
if !is_learner {
cfg.voters.incoming.insert(id);
} else {
cfg.learners.insert(id);
}
prs.changes.push((id, MapChangeType::Add));
}
/// Copies the tracker's config. It returns an error if checkInvariants does.
///
/// Unlike Etcd, we don't copy progress as we don't need to mutate the `is_learner`
/// flags. Additions and Removals should be done after everything is checked OK.
fn check_and_copy(&self) -> Result<(Configuration, IncrChangeMap)> {
let prs = IncrChangeMap {
changes: vec![],
base: self.tracker.progress(),
};
check_invariants(self.tracker.conf(), &prs)?;
Ok((self.tracker.conf().clone(), prs))
}
}
/// Makes sure that the config and progress are compatible with each other.
/// This is used to check both what the Changer is initialized with, as well
/// as what it returns.
fn check_invariants(cfg: &Configuration, prs: &IncrChangeMap) -> Result<()> {
// NB: intentionally allow the empty config. In production we'll never see a
// non-empty config (we prevent it from being created) but we will need to
// be able to *create* an initial config, for example during bootstrap (or
// during tests). Instead of having to hand-code this, we allow
// transitioning from an empty config into any other legal and non-empty
// config.
for id in cfg.voters().ids().iter() {
if !prs.contains(id) {
return Err(Error::ConfChangeError(format!(
"no progress for voter {}",
id
)));
}
}
for id in &cfg.learners {
if !prs.contains(*id) {
return Err(Error::ConfChangeError(format!(
"no progress for learner {}",
id
)));
}
// Conversely Learners and Voters doesn't intersect at all.
if cfg.voters().outgoing.contains(id) {
return Err(Error::ConfChangeError(format!(
"{} is in learners and outgoing voters",
id
)));
}
if cfg.voters().incoming.contains(id) {
return Err(Error::ConfChangeError(format!(
"{} is in learners and incoming voters",
id
)));
}
}
for id in &cfg.learners_next {
if !prs.contains(*id) {
return Err(Error::ConfChangeError(format!(
"no progress for learner(next) {}",
id
)));
}
// Any staged learner was staged because it could not be directly added due
// to a conflicting voter in the outgoing config.
if !cfg.voters().outgoing.contains(id) {
return Err(Error::ConfChangeError(format!(
"{} is in learners_next and outgoing voters",
id
)));
}
}
if !super::joint(cfg) {
// Etcd enforces outgoing and learner_next to be nil map. But there is no nil
// in rust. We just check empty for simplicity.
if !cfg.learners_next().is_empty() {
return Err(Error::ConfChangeError(
"learners_next must be empty when not joint".to_owned(),
));
}
if cfg.auto_leave {
return Err(Error::ConfChangeError(
"auto_leave must be false when not joint".to_owned(),
));
}
}
Ok(())
}