zowens/paxos-rs

Paxos implementation in Rust

paxos-rs's Issues

Distinguished Proposer

Implement distinguished proposer role, as defined in Paxos Made Simple.

Phase 1 executed gives the Proposer Phase 1 for instances >= current

Liveness hooks for proposers

Currently, once a distinguished proposer is selected, there is no way to detect failure of the DP from the other replicas. In addition, the proposer itself is unable to know if it still will be able to maintain quorum. The proposer itself is also subject to failing to get Phase 2 quorum if some nodes miss ACCEPT messages.

PigPaxos - eliminate coordination bottleneck

The PigPaxos paper shows a novel idea to use a peer replica to broadcast communication to reduce the computational needs on the Paxos leader. This could be an interesting extension.

Batching Proposals

Batching multiple proposals into a single instance increases throughput of the algorithm. We should attempt to batch multiple into a single algo::Value

A possible issue is the max size of UDP packets

Better support for handling async/sync requests

It is awkward currently to handle a state machine and in the same vein support client requests for proposals. It would be nice to have library-level features to make programming with this model easier.

Replicated Log example

More examples! A replicated log would add an additional example that showcases the library.

It may also be useful to evaluate publishing examples as crates themselves for consumption by other systems.

Proposal batching

The library currently implements proposal pipelining, where multiple instances may be decided concurrently. Add in the option to batch multiple proposals and send these out to the replicas as a single request.

• Change proposal command to take a Vec<Bytes>
• Create an add on replica that will wait for size N bytes or send proposals on tick()

Name of the crate on crates.io

Last step to getting this out into Crates.io! It turns out paxos is taken, so we need a different name.

Some ideas:

• paxos-rs
• pax-rs
• paxi

Snapshot and truncate proposals

When a proposal is executed, the decision command is still held within the SlotWindow. To properly implement truncation, this needs to be propagated to through the Paxos protocol.

Model check the replica implementation

There should be model checking tests that run as unit tests. This can be accomplished with something like stateright.

WPaxos Extensions

Paxos used in a WAN setting would need some additional considerations. The WPaxos paper and Paxi implementation provide a framework for separating the object space for use in a WAN setting.

Reorganize crate structure

Instead of the cli and server being in src/bin, there should be multiple crates for:

• paxos-lib
• paxos-server
• paxos-cli
• paxos-client

Learning old instances

Currently it's possible for a replica to drop out, come back into the cluster and not learn of old instances. In this condition the state machine is not applied at that replica.

Support Flexible Quorums

Allow Phase 1 and Phase 2 quorums to be differently sized. This should be a configuration option.

Limit in-flight proposals and open instances

We currently do not limit the number of in-flight proposals or open instances, which could lead to an OOM condition. In the Paxos Made Simple paper the value alpha is chosen as the max number.

Persistent Storage

The Paxos state must be applied to persistent storage. The easiest to plug in may be RocksDB.

Read leases

In most uses of Paxos, read heavy workloads do not need to traverse the entire Paxos protocol (at least Phase 2). In the Paxos made Live paper, the authors describe a read lease concept wherein reads are cordoned to a leader node. This should reduce the latency impact for most reads.

• Distinguish read commands within the state machine
• Ensure that the leader is always the holder of the lease
• Process the read request on leader (or redirect to leader)

Add default transport implementation

Add a feature-enabled default transport implementation that can be used out-of-the-box.

Allow readonly learners/observers

Add in the configuration learners/observers that do not participate in Phase 1 or Phase 2 quorum, but learn of decisions.

Trait cleanup

The current traits are disjointed between the various stack levels for the core replica and liveness mode. It would be nice to have a unified trait that encompasses the common subset functions needed to be a replica.

The trait for replicas should also contain convenience functions to stack functionality.

pub trait Replica: Commander {
    // leader election functions election
    fn propose_leadership(&mut self);
    fn is_leader(&self) -> bool;

    // move tick over to the replica from Tick trait
    fn tick(&mut self);
    
    // access the decisions
    fn decisions_mut(&mut self) -> DecisionSet;
    
    // Convenience functions to add additional functionality
    fn liveness(self) -> Liveness<Self> { Liveness::new(self) }
    fn logged(self, level: log::Level) -> Logged<Self> { Logged::new(self, level) }
    fn state_machine(self, state: ReplicatedState) -> StateMachine<Self> { StateMachine::new(self, state) }
    fn notify(self, listener: Listener) -> Notified<Self> { Notified::new(self, listener) }
}

Add optional serde feature

Add optional serde feature that adds Serialize and Deserialize implementations for RPC types. In addition, the ReplicatedState trait should be updated to utilize custom types for commands.

Reconfiguration

We need to support reconfiguration at the Paxos protocol layer. In addition, having a JOIN/LEAVE type primitive is necessary for bootstrapping.