raft_seedable/lib.rs
1// Copyright 2019 TiKV Project Authors. Licensed under Apache-2.0.
2
3// Copyright 2015 The etcd Authors
4//
5// Licensed under the Apache License, Version 2.0 (the "License");
6// you may not use this file except in compliance with the License.
7// You may obtain a copy of the License at
8//
9// http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing, software
12// distributed under the License is distributed on an "AS IS" BASIS,
13// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14// See the License for the specific language governing permissions and
15// limitations under the License.
16
17/*!
18
19## Creating a Raft node
20
21You can use [`RawNode::new`] to create the Raft node. To create the Raft node, you need to
22provide a [`Storage`] component, and a [`Config`] to the [`RawNode::new`] function.
23
24```rust
25use raft::{
26 Config,
27 storage::MemStorage,
28 raw_node::RawNode,
29};
30use slog::{Drain, o};
31
32// Select some defaults, then change what we need.
33let config = Config {
34 id: 1,
35 ..Default::default()
36};
37// Initialize logger.
38let logger = slog::Logger::root(slog_stdlog::StdLog.fuse(), o!());
39// ... Make any configuration changes.
40// After, make sure it's valid!
41config.validate().unwrap();
42// We'll use the built-in `MemStorage`, but you will likely want your own.
43// Finally, create our Raft node!
44let storage = MemStorage::new_with_conf_state((vec![1], vec![]));
45let mut node = RawNode::new(&config, storage, &logger).unwrap();
46```
47
48## Ticking the Raft node
49
50Use a timer to tick the Raft node at regular intervals. See the following example using Rust
51channel `recv_timeout` to drive the Raft node at least every 100ms, calling
52[`tick()`](RawNode::tick) each time.
53
54```rust
55# use slog::{Drain, o};
56# use raft::{Config, storage::MemStorage, raw_node::RawNode};
57# let config = Config { id: 1, ..Default::default() };
58# let store = MemStorage::new_with_conf_state((vec![1], vec![]));
59# let logger = slog::Logger::root(slog_stdlog::StdLog.fuse(), o!());
60# let mut node = RawNode::new(&config, store, &logger).unwrap();
61# node.raft.become_candidate();
62# node.raft.become_leader();
63use std::{sync::mpsc::{channel, RecvTimeoutError}, time::{Instant, Duration}};
64
65// We're using a channel, but this could be any stream of events.
66let (tx, rx) = channel();
67let timeout = Duration::from_millis(100);
68let mut remaining_timeout = timeout;
69
70// Send the `tx` somewhere else...
71
72loop {
73 let now = Instant::now();
74
75 match rx.recv_timeout(remaining_timeout) {
76 Ok(()) => {
77 // Let's save this for later.
78 unimplemented!()
79 },
80 Err(RecvTimeoutError::Timeout) => (),
81 Err(RecvTimeoutError::Disconnected) => unimplemented!(),
82 }
83
84 let elapsed = now.elapsed();
85 if elapsed >= remaining_timeout {
86 remaining_timeout = timeout;
87 // We drive Raft every 100ms.
88 node.tick();
89 } else {
90 remaining_timeout -= elapsed;
91 }
92# break;
93}
94```
95
96## Proposing to, and stepping the Raft node
97
98Using the `propose` function you can drive the Raft node when the client sends a request to the
99Raft server. You can call `propose` to add the request to the Raft log explicitly.
100
101In most cases, the client needs to wait for a response for the request. For example, if the
102client writes a value to a key and wants to know whether the write succeeds or not, but the
103write flow is asynchronous in Raft, so the write log entry must be replicated to other followers,
104then committed and at last applied to the state machine, so here we need a way to notify the client
105after the write is finished.
106
107One simple way is to use a unique ID for the client request, and save the associated callback
108function in a hash map. When the log entry is applied, we can get the ID from the decoded entry,
109call the corresponding callback, and notify the client.
110
111You can call the `step` function when you receive the Raft messages from other nodes.
112
113Here is a simple example to use `propose` and `step`:
114
115```rust
116# use raft::{Config, storage::MemStorage, raw_node::RawNode, eraftpb::Message};
117# use std::{
118# sync::mpsc::{channel, RecvTimeoutError},
119# time::{Instant, Duration},
120# collections::HashMap
121# };
122# use slog::{Drain, o};
123#
124# let config = Config { id: 1, ..Default::default() };
125# let store = MemStorage::new_with_conf_state((vec![1], vec![]));
126# let logger = slog::Logger::root(slog_stdlog::StdLog.fuse(), o!());
127# let mut node = RawNode::new(&config, store, &logger).unwrap();
128# node.raft.become_candidate();
129# node.raft.become_leader();
130#
131# let (tx, rx) = channel();
132# let timeout = Duration::from_millis(100);
133# let mut remaining_timeout = timeout;
134#
135enum Msg {
136 Propose {
137 id: u8,
138 callback: Box<dyn Fn() + Send>,
139 },
140 Raft(Message),
141}
142
143// Simulate a message coming down the stream.
144tx.send(Msg::Propose { id: 1, callback: Box::new(|| ()) });
145
146let mut cbs = HashMap::new();
147loop {
148 let now = Instant::now();
149
150 match rx.recv_timeout(remaining_timeout) {
151 Ok(Msg::Propose { id, callback }) => {
152 cbs.insert(id, callback);
153 node.propose(vec![], vec![id]).unwrap();
154 }
155 Ok(Msg::Raft(m)) => node.step(m).unwrap(),
156 Err(RecvTimeoutError::Timeout) => (),
157 Err(RecvTimeoutError::Disconnected) => unimplemented!(),
158 }
159
160 let elapsed = now.elapsed();
161 if elapsed >= remaining_timeout {
162 remaining_timeout = timeout;
163 // We drive Raft every 100ms.
164 node.tick();
165 } else {
166 remaining_timeout -= elapsed;
167 }
168 break;
169}
170```
171
172In the above example, we use a channel to receive the `propose` and `step` messages. We only
173propose the request ID to the Raft log. In your own practice, you can embed the ID in your request
174and propose the encoded binary request data.
175
176## Processing the `Ready` State
177
178When your Raft node is ticked and running, Raft should enter a `Ready` state. You need to first use
179`has_ready` to check whether Raft is ready. If yes, use the `ready` function to get a `Ready`
180state:
181
182```rust
183# use slog::{Drain, o};
184# use raft::{Config, storage::MemStorage, raw_node::RawNode};
185#
186# let config = Config { id: 1, ..Default::default() };
187# config.validate().unwrap();
188# let store = MemStorage::new_with_conf_state((vec![1], vec![]));
189# let logger = slog::Logger::root(slog_stdlog::StdLog.fuse(), o!());
190# let mut node = RawNode::new(&config, store, &logger).unwrap();
191#
192if !node.has_ready() {
193 return;
194}
195
196// The Raft is ready, we can do something now.
197let mut ready = node.ready();
198```
199
200The `Ready` state contains quite a bit of information, and you need to check and process them one
201by one:
202
2031. Check whether `messages` is empty or not. If not, it means that the node will send messages to
204other nodes:
205
206 ```rust
207 # use slog::{Drain, o};
208 # use raft::{Config, storage::MemStorage, raw_node::RawNode, StateRole};
209 #
210 # let config = Config { id: 1, ..Default::default() };
211 # config.validate().unwrap();
212 # let store = MemStorage::new_with_conf_state((vec![1], vec![]));
213 # let logger = slog::Logger::root(slog_stdlog::StdLog.fuse(), o!());
214 # let mut node = RawNode::new(&config, store, &logger).unwrap();
215 #
216 # if !node.has_ready() {
217 # return;
218 # }
219 # let mut ready = node.ready();
220 #
221 if !ready.messages().is_empty() {
222 for msg in ready.take_messages() {
223 // Send messages to other peers.
224 }
225 }
226 ```
227
2282. Check whether `snapshot` is empty or not. If not empty, it means that the Raft node has received
229a Raft snapshot from the leader and we must apply the snapshot:
230
231 ```rust
232 # use slog::{Drain, o};
233 # use raft::{Config, storage::MemStorage, raw_node::RawNode};
234 #
235 # let config = Config { id: 1, ..Default::default() };
236 # config.validate().unwrap();
237 # let store = MemStorage::new_with_conf_state((vec![1], vec![]));
238 # let logger = slog::Logger::root(slog_stdlog::StdLog.fuse(), o!());
239 # let mut node = RawNode::new(&config, store, &logger).unwrap();
240 #
241 # if !node.has_ready() {
242 # return;
243 # }
244 # let mut ready = node.ready();
245 #
246 if !ready.snapshot().is_empty() {
247 // This is a snapshot, we need to apply the snapshot at first.
248 node.mut_store()
249 .wl()
250 .apply_snapshot(ready.snapshot().clone())
251 .unwrap();
252 }
253
254 ```
255
2563. Check whether `committed_entries` is empty or not. If not, it means that there are some newly
257committed log entries which you must apply to the state machine. Of course, after applying, you
258need to update the applied index and resume `apply` later:
259
260 ```rust
261 # use slog::{Drain, o};
262 # use raft::{Config, storage::MemStorage, raw_node::RawNode, eraftpb::EntryType};
263 #
264 # let config = Config { id: 1, ..Default::default() };
265 # config.validate().unwrap();
266 # let store = MemStorage::new_with_conf_state((vec![1], vec![]));
267 # let logger = slog::Logger::root(slog_stdlog::StdLog.fuse(), o!());
268 # let mut node = RawNode::new(&config, store, &logger).unwrap();
269 #
270 # if !node.has_ready() {
271 # return;
272 # }
273 # let mut ready = node.ready();
274 #
275 # fn handle_conf_change(e: raft::eraftpb::Entry) {
276 # }
277 #
278 # fn handle_conf_change_v2(e: raft::eraftpb::Entry) {
279 # }
280 #
281 # fn handle_normal(e: raft::eraftpb::Entry) {
282 # }
283 #
284 let mut _last_apply_index = 0;
285 for entry in ready.take_committed_entries() {
286 // Mostly, you need to save the last apply index to resume applying
287 // after restart. Here we just ignore this because we use a Memory storage.
288 _last_apply_index = entry.index;
289
290 if entry.data.is_empty() {
291 // Emtpy entry, when the peer becomes Leader it will send an empty entry.
292 continue;
293 }
294
295 match entry.get_entry_type() {
296 EntryType::EntryNormal => handle_normal(entry),
297 // It's recommended to always use `EntryType::EntryConfChangeV2.
298 EntryType::EntryConfChange => handle_conf_change(entry),
299 EntryType::EntryConfChangeV2 => handle_conf_change_v2(entry),
300 }
301 }
302 ```
303
304 Note, although Raft guarentees only persisted committed entries will be applied,
305 but it doesn't guarentee commit index is persisted before being applied. For example,
306 if application is restarted after applying committed entries before persisting
307 commit index, apply index can be larger than commit index and cause panic. To
308 solve the problem, persisting commit index with or before applying entries.
309 You can also always assign commit index to the `max(commit_index, applied_index)`
310 after restarting, *it may work but potential log loss may also be ignored silently*.
311
3124. Check whether `entries` is empty or not. If not empty, it means that there are newly added
313entries but have not been committed yet, we must append the entries to the Raft log:
314
315 ```rust
316 # use slog::{Drain, o};
317 # use raft::{Config, storage::MemStorage, raw_node::RawNode};
318 #
319 # let config = Config { id: 1, ..Default::default() };
320 # config.validate().unwrap();
321 # let store = MemStorage::new_with_conf_state((vec![1], vec![]));
322 # let logger = slog::Logger::root(slog_stdlog::StdLog.fuse(), o!());
323 # let mut node = RawNode::new(&config, store, &logger).unwrap();
324 #
325 # if !node.has_ready() {
326 # return;
327 # }
328 # let mut ready = node.ready();
329 #
330 if !ready.entries().is_empty() {
331 // Append entries to the Raft log
332 node.mut_store().wl().append(ready.entries()).unwrap();
333 }
334
335 ```
336
3375. Check whether `hs` is empty or not. If not empty, it means that the `HardState` of the node has
338changed. For example, the node may vote for a new leader, or the commit index has been increased.
339We must persist the changed `HardState`:
340
341 ```rust
342 # use slog::{Drain, o};
343 # use raft::{Config, storage::MemStorage, raw_node::RawNode};
344 #
345 # let config = Config { id: 1, ..Default::default() };
346 # config.validate().unwrap();
347 # let store = MemStorage::new_with_conf_state((vec![1], vec![]));
348 # let logger = slog::Logger::root(slog_stdlog::StdLog.fuse(), o!());
349 # let mut node = RawNode::new(&config, store, &logger).unwrap();
350 #
351 # if !node.has_ready() {
352 # return;
353 # }
354 # let mut ready = node.ready();
355 #
356 if let Some(hs) = ready.hs() {
357 // Raft HardState changed, and we need to persist it.
358 node.mut_store().wl().set_hardstate(hs.clone());
359 }
360 ```
361
3626. Check whether `persisted_messages` is empty or not. If not, it means that the node will send messages to
363other nodes after persisting hardstate, entries and snapshot:
364
365 ```rust
366 # use slog::{Drain, o};
367 # use raft::{Config, storage::MemStorage, raw_node::RawNode, StateRole};
368 #
369 # let config = Config { id: 1, ..Default::default() };
370 # config.validate().unwrap();
371 # let store = MemStorage::new_with_conf_state((vec![1], vec![]));
372 # let logger = slog::Logger::root(slog_stdlog::StdLog.fuse(), o!());
373 # let mut node = RawNode::new(&config, store, &logger).unwrap();
374 #
375 # if !node.has_ready() {
376 # return;
377 # }
378 # let mut ready = node.ready();
379 #
380 if !ready.persisted_messages().is_empty() {
381 for msg in ready.take_persisted_messages() {
382 // Send persisted messages to other peers.
383 }
384 }
385 ```
386
3877. Call `advance` to notify that the previous work is completed. Get the return value `LightReady`
388and handle its `messages` and `committed_entries` like step 1 and step 3 does. Then call `advance_apply`
389to advance the applied index inside.
390
391 ```rust
392 # use slog::{Drain, o};
393 # use raft::{Config, storage::MemStorage, raw_node::RawNode};
394 # use raft::eraftpb::{EntryType, Entry, Message};
395 #
396 # let config = Config { id: 1, ..Default::default() };
397 # config.validate().unwrap();
398 # let store = MemStorage::new_with_conf_state((vec![1], vec![]));
399 # let logger = slog::Logger::root(slog_stdlog::StdLog.fuse(), o!());
400 # let mut node = RawNode::new(&config, store, &logger).unwrap();
401 #
402 # if !node.has_ready() {
403 # return;
404 # }
405 # let mut ready = node.ready();
406 #
407 # fn handle_messages(msgs: Vec<Message>) {
408 # }
409 #
410 # fn handle_committed_entries(committed_entries: Vec<Entry>) {
411 # }
412 let mut light_rd = node.advance(ready);
413 // Like step 1 and 3, you can use functions to make them behave the same.
414 handle_messages(light_rd.take_messages());
415 handle_committed_entries(light_rd.take_committed_entries());
416 node.advance_apply();
417 ```
418
419For more information, check out an [example](examples/single_mem_node/main.rs#L113-L179).
420
421Sometimes it's better not to block the raft machine in IO operation, so that latency of
422read/write can be more predictable and the fsync frequencey can be controlled. The crate
423supports async ready to offload the IO operation to other thread. The usage is the same as
424above except:
4251. All writes are not required to be persisted immediately, they can be written into memory caches;
4262. Persisted messages should be sent after all coresponding writes are persisted;
4273. [`advance_append_async`](RawNode::advance_append_async) is used when all writes are finished
428 instead of `advance/advance_append`.
4294. Only persisted entries can be committed and applied, so to make progress, all writes should
430 be persisted at some point.
431
432## Arbitrary Membership Changes
433
434When building a resilient, scalable distributed system there is a strong need to be able to change
435the membership of a peer group *dynamically, without downtime.* This Raft crate supports this via
436**Joint Consensus**
437([Raft paper, section 6](https://web.stanford.edu/~ouster/cgi-bin/papers/raft-atc14)).
438
439It permits resilient arbitrary dynamic membership changes. A membership change can do any or all of
440the following:
441
442* Add peer (learner or voter) *n* to the group.
443* Remove a learner *n* from the group.
444* Promote a learner to a voter.
445* Demote a voter back to learner.
446* Replace a node *n* with another node *m*.
447
448For example to promote a learner 4 and demote an existing voter 3:
449```no_run
450# use raft::{Config, storage::MemStorage, raw_node::RawNode, eraftpb::*};
451# use protobuf::Message as PbMessage;
452# use slog::{Drain, o};
453#
454# let mut config = Config { id: 1, ..Default::default() };
455# let store = MemStorage::new_with_conf_state((vec![1, 2], vec![]));
456# let logger = slog::Logger::root(slog_stdlog::StdLog.fuse(), o!());
457# let mut node = RawNode::new(&mut config, store, &logger).unwrap();
458let steps = vec![
459 raft_proto::new_conf_change_single(4, ConfChangeType::AddNode),
460 raft_proto::new_conf_change_single(3, ConfChangeType::RemoveNode),
461];
462let mut cc = ConfChangeV2::default();
463cc.set_changes(steps.into());
464node.propose_conf_change(vec![], cc).unwrap();
465// After the log is committed and applied
466// node.apply_conf_change(&cc).unwrap();
467```
468
469This process is a two-phase process, during the midst of it the peer group's leader is managing
470**two independent, possibly overlapping peer sets**.
471
472> **Note:** In order to maintain resiliency guarantees (progress while a majority of both peer sets is
473active), it is recommended to wait until the entire peer group has exited the transition phase
474before taking old, removed peers offline.
475
476*/
477
478#![cfg_attr(not(feature = "cargo-clippy"), allow(unknown_lints))]
479#![deny(clippy::all)]
480#![deny(missing_docs)]
481#![recursion_limit = "128"]
482// This is necessary to support prost and rust-protobuf at the same time.
483#![allow(clippy::useless_conversion)]
484// This lint recommends some bad choices sometimes.
485#![allow(clippy::unnecessary_unwrap)]
486// We use `default` method a lot to be support prost and rust-protobuf at the
487// same time. And reassignment can be optimized by compiler.
488#![allow(clippy::field_reassign_with_default)]
489// Arachne D-S1 vendoring: `raft` 0.7.0 predates several lints added in the
490// current toolchain (Rust 1.93). Suppressing them here (rather than editing the
491// upstream source) keeps the vendored tree byte-identical except for the D-S1
492// hook and keeps the workspace build warning-free. See ARACHNE-PATCH.md.
493#![allow(
494 unexpected_cfgs,
495 mismatched_lifetime_syntaxes,
496 unused_mut,
497 unused_imports,
498 dead_code,
499 static_mut_refs
500)]
501
502macro_rules! fatal {
503 ($logger:expr, $msg:expr) => {{
504 let owned_kv = ($logger).list();
505 let s = crate::util::format_kv_list(&owned_kv);
506 if s.is_empty() {
507 panic!("{}", $msg)
508 } else {
509 panic!("{}, {}", $msg, s)
510 }
511 }};
512 ($logger:expr, $fmt:expr, $($arg:tt)+) => {{
513 fatal!($logger, format_args!($fmt, $($arg)+))
514 }};
515}
516
517mod confchange;
518mod config;
519mod errors;
520mod log_unstable;
521mod quorum;
522#[cfg(test)]
523pub mod raft;
524#[cfg(not(test))]
525mod raft;
526mod raft_log;
527pub mod raw_node;
528mod read_only;
529mod status;
530pub mod storage;
531mod tracker;
532pub mod util;
533
534pub use crate::raft::{
535 clear_election_rng_seed, set_election_rng_seed, vote_resp_msg_type, Raft, SoftState,
536 StateRole, CAMPAIGN_ELECTION, CAMPAIGN_PRE_ELECTION, CAMPAIGN_TRANSFER, INVALID_ID,
537 INVALID_INDEX,
538};
539pub use confchange::{Changer, MapChange};
540pub use config::Config;
541pub use errors::{Error, Result, StorageError};
542pub use log_unstable::Unstable;
543pub use quorum::joint::Configuration as JointConfig;
544pub use quorum::majority::Configuration as MajorityConfig;
545pub use raft_log::{RaftLog, NO_LIMIT};
546pub use raft_proto::eraftpb;
547#[allow(deprecated)]
548pub use raw_node::is_empty_snap;
549pub use raw_node::{LightReady, Peer, RawNode, Ready, SnapshotStatus};
550pub use read_only::{ReadOnlyOption, ReadState};
551pub use status::Status;
552pub use storage::{GetEntriesContext, RaftState, Storage};
553pub use tracker::{Inflights, Progress, ProgressState, ProgressTracker};
554pub use util::majority;
555
556pub mod prelude {
557 //! A "prelude" for crates using the `raft` crate.
558 //!
559 //! This prelude is similar to the standard library's prelude in that you'll
560 //! almost always want to import its entire contents, but unlike the standard
561 //! library's prelude you'll have to do so manually:
562 //!
563 //! ```
564 //! use raft::prelude::*;
565 //! ```
566 //!
567 //! The prelude may grow over time as additional items see ubiquitous use.
568
569 pub use raft_proto::prelude::*;
570
571 pub use crate::config::Config;
572 pub use crate::raft::Raft;
573
574 pub use crate::storage::{RaftState, Storage};
575
576 pub use crate::raw_node::{Peer, RawNode, Ready, SnapshotStatus};
577
578 pub use crate::Progress;
579
580 pub use crate::status::Status;
581
582 pub use crate::read_only::{ReadOnlyOption, ReadState};
583}
584
585/// The default logger we fall back to when passed `None` in external facing constructors.
586///
587/// Currently, this is a `log` adaptor behind a `Once` to ensure there is no clobbering.
588#[cfg(any(test, feature = "default-logger"))]
589pub fn default_logger() -> slog::Logger {
590 use slog::{o, Drain};
591 use std::sync::{Mutex, Once};
592
593 static LOGGER_INITIALIZED: Once = Once::new();
594 static mut LOGGER: Option<slog::Logger> = None;
595
596 let logger = unsafe {
597 LOGGER_INITIALIZED.call_once(|| {
598 let decorator = slog_term::TermDecorator::new().build();
599 let drain = slog_term::CompactFormat::new(decorator).build();
600 let drain = slog_envlogger::new(drain);
601 LOGGER = Some(slog::Logger::root(Mutex::new(drain).fuse(), o!()));
602 });
603 LOGGER.as_ref().unwrap()
604 };
605 if let Some(case) = std::thread::current()
606 .name()
607 .and_then(|v| v.split(':').last())
608 {
609 logger.new(o!("case" => case.to_string()))
610 } else {
611 logger.new(o!())
612 }
613}
614
615type DefaultHashBuilder = std::hash::BuildHasherDefault<fxhash::FxHasher>;
616type HashMap<K, V> = std::collections::HashMap<K, V, DefaultHashBuilder>;
617type HashSet<K> = std::collections::HashSet<K, DefaultHashBuilder>;