Lib.rs

› Network programming
#consensus #protocols #replication #non-deterministic #request #single #client

viewstamped-replication

A Rust-based implementation of the Viewstamped Replication consensus protocol

by Miguel D. Salcedo

8 breaking releases

0.9.0 Mar 10, 2024
0.7.0 Feb 12, 2024

#578 in Network programming

Download history 1/week @ 2024-01-01 4/week @ 2024-01-08 8/week @ 2024-01-15 2/week @ 2024-02-05 31/week @ 2024-02-12 10/week @ 2024-02-26 276/week @ 2024-03-04 41/week @ 2024-03-11 33/week @ 2024-04-01 120/week @ 2024-04-15

153 downloads per month

Apache-2.0

72KB
2K SLoC

Viewstamped Replication

A Rust-based implementation of the viewstamped replication consensus protocol.

Concurrency

The basic protocol assumes a single concurrent request per client. Client applications can achieve higher concurrency by utilizing multiple client identifiers for a single client application instance.

Non-determinism

Supports non-determinism by querying the service from the primary for a predicted value and passing that value on prepare to all replicas. Currently, there is no support for other solutions mentioned in the literature such as sending a predict message, waiting for f responses and deterministically merging the values.

Log Compaction

Supports log compaction by regularly taking checkpoints of the service state to be durably stored. A service must be restore-able from a checkpoint. Once a large enough suffix of checkpoints exists, the log may be compacted to remove all operations included in the last checkpoint before the suffix.

For example, imagine a configuration that takes a checkpoint every 5 minutes and keeps the last 3 checkpoints. The log will be compacted on the 4th checkpoint and any operations whose application state is reflected in 1st checkpoint will be removed from the log.

Simulation

A simulation of the protocol using async tasks and channels is included in the examples.

cargo run --example simulation

State Transfers

  • The protocol does not state what to do when a replica receives a GetState message for a newer operation than is in its log. For now, we drop the message.

TODOs

  • Define mechanism for recovering replicas to fetch configuration upon receiving a protocol message.
  • Support an optional pre-step for non-determinism that fetches predictions from f backups.
  • Support stale read-only requests on backups.
  • Support for configuration changes.
  • Support for networked communication.
  • Support fetching the checkpoints from other replicas when recovering.
  • Support copy-on-write semantics in log compaction to reduce the cost of checkpoints.
  • Make non-determinism and checkpointing optional for services to implement.
  • Evicting client table to limit memory usage.

Dependencies

~1–1.7MB
~34K SLoC