-->

Bytepawn - Marton Trencseni – Implementing PaxosLease in Python with HTTP Flask

Bytepawn - Marton Trencseni<br>--><br>Bytepawn

Introduction

In earlier posts I walked through plain Paxos and then Multi-Paxos, writing a toy replicated log implementation in Python. The goal of Paxos is agreeing on values which then become log entries — these can practically be thought of as database commands, which are then executed against local database replicas. In Paxos, once a value is chosen, it's chosen forever, never forgotten — in this sense, each entry of the replicated log is write-once, and all nodes (replicas) see the same sequence of values (commands), which ensures that their local databases executes the same sequence of commands. This is exactly what we want for reliable database replication, but it's overkill for some other common coordination problems in a distributed system, such as master election or lock ownership.

Temporal leases are the underlying primitive for master election and lock ownership. In practice you rarely want a lock that lasts forever; you want a lease : a lock that expires, so if the owner goes down, somebody else can take over. Master election is just a type of lock, with the same desired property: "this node is master for at most T seconds, then we'll see." If that node dies, you don't want the cluster to sit there blocked forever waiting for it to come back and release the lock. You want the lease to just expire and somebody else to take over. PaxosLease is a specialization of Paxos that does exactly that: it negotiates leases using a Paxos-style protocol, but because leases expire, the algorithm can get away with no disk writes and no synchronized clocks.

The code for this article is on Github.

Links:

Paxos (Wikipedia)

Paxos: Lamport's Crown Jewel for Replicated State Machines (Bytepawn)

Multi-Paxos: Building a Simple Replicated Log in Python (Bytepawn)

PaxosLease: Diskless Paxos for Leases (arxiv)

Keyspace: A Consistently Replicated, Highly-Available Key-Value Store (arxiv)

Keyspace source code (Github)

ScalienDB: Designing and Implementing a Distributed Database using Paxos (arxiv)

ScalienDB source code (Github)

Scalien

I originally came up with PaxosLease while working on my startup, Scalien. Scalien built two Paxos-based distributed databases, Keyspace and ScalienDB, roughly between 2008 and 2012. Keyspace was a consistently replicated key-value store that used Paxos to replicate write commands and guarantee strong consistency. ScalienDB was its successor, a bigger C++ system that again used Paxos under the hood, and we put it into production at a few paying customers before we ran out of funding.

In both Keyspace and ScalienDB we needed a way to elect a master inside a small controller quorum. You can absolutely do this with regular Paxos (or even full Multi-Paxos), but it's clunky: you have to write acceptor state to disk, worry about recovery, and you're still just trying to answer a yes/no question: "who's the leader right now?" So I ended up designing PaxosLease as a leaner variant: same majority/quorum logic as Paxos, but optimized for the case where the "value" is a lease with a fixed maximum duration. PaxosLease ended up being used for master lease negotiation in both Keyspace and ScalienDB.

The core realization was that leader/master selection in these systems doesn't need the "once chosen, true forever" property that Paxos is built around. Masters come and go. What we really needed was: at any given moment, there is at most one master, and we're okay forgetting the past as long as we don't overlap leases. That difference in requirements is what let PaxosLease drop disk writes and still remain safe.

PaxosLease

PaxosLease follows classical Paxos: we have proposers and acceptors, and we're trying to reach agreement on the "state" of a tiny replicated state machine:

"no one has the lease"

"node 1 has the lease"

"node 2 has the lease"

The proposer runs a two-phase protocol very similar to Paxos. In the prepare phase it picks a fresh ballot number and asks a majority of acceptors whether they're willing to promise not to accept lower-numbered proposals. In the propose phase it actually proposes "node i has the lease for T seconds." If a majority of acceptors accept that proposal, the proposer believes it now holds the lease for T seconds.

The crucial difference from regular Paxos is that the lease expires . Each acceptor starts a local timer for T seconds when it accepts a lease, and when that timer fires it just forgets the proposal. There's also a globally known maximum lease time M, and proposers are required to choose T . Because leases are bounded in time, acceptors don't have to persist anything to disk: if they crash and lose state, they simply wait M seconds before rejoining. By the time they start answering messages again, any lease they might have been part of before the crash must have already expired. That's the trick that gives PaxosLease...