Skip to main content

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>;