cocagne/paxos

Plain Paxos Implementations in Python & Java

Essential Paxos

Tom Cocagne <[email protected]>
v2.0, January 2013

Introductory Note

This repository contains the results of my first foray into providing both a useful and educational Paxos implementation. The repository is in pretty good shape and still fills its intended role but the design includes explicit support for sending network messages. I now consider this something of an anti-pattern for Paxos implementations and recommend using an even more tightly constrained library that implements the core algorithm and nothing else, including messaging. To that end, I've put together the python-composable-paxos repository and a multi-paxos-example based upon it. Those repositories should generally be preferred over this one. Additionally, I've written an introductory paper on Paxos and Multi-Paxos that may be useful for individuals like myself that find the existing papers somewhat opaque.

Overview

Essential Paxos provides basic implementations of the Paxos algorithm. The distinguishing characteristic of this implementation, as compared to other freely available and open-source implementations, is that this library is independent of application domains and networking infrastructures. Whereas most Paxos implementations are deeply and inextricably embedded within application-specific logic, this implementation focuses on encapsulating the Paxos algorithm within opaque and easily re-usable classes.

This library provides an algorithmically correct Paxos implementation that may be used for educational purposes in addition to direct use in networked applications. This implementation is specifically designed to facilitate understanding of both the essential Paxos algorithm as well as the practical considerations that must be taken into account for real-world use.

Implementations in both Python and Java are provided.

Python Installation

$ easy_install essential-paxos

Implementations

Python

essential.py

This module provides a direct and minimal implementation of the essential Paxos algorithm. The primary purpose of this module is educational as it allows for easy contrast between the implementation of the pure algorithm and that of the one enhanced for practicality.

practical.py

This module enhances the essential Paxos algorithm and adds support for such things as leadership tracking, NACKs, and state persistence.

functional.py

This module provides a fully-functional Paxos implementation that employs a simple heartbeating mechanism to detect leadership failure and initiate recovery.

external.py

This module provides an enhanced version of practical.py that supports the use of external failure detectors to drive leadership management. This module does not provide a fully-functional solution to leadership management, as does functional.py. However, it may serve as the basis for much more flexible, application-specific leadership management.

durable.py

Correct implementations of the Paxos algorithm require saving Acceptor state to persistent media prior to sending Promise and Accepted messages over the network. This is necessary to ensure that promises made to external entities will never be reneged upon should the application crash and recover at an inopportune time. This module implements a very simple mechanism for efficiently saving application state to disk.

Java

The Java implementation is functionally identical to that of the Python implementation and is broken out into Java packages that mirror the python modules. Refer to the corresponding Python APIs for class and method documentation.

cocagne.paxos.essential

cocagne.paxos.practical

cocagne.paxos.functional

Testing

The test directory of the root source code repository contains the unittest files used to exercise the implementation. The primary tests are written in Python and correspond to the essential, practical, functional, and durable modules. The Java tests, which are also written in Python, wrap the Java classes with a compatible interface and use the Python unit tests to exercise the Java implementation. The Jython interpreter is required for running these tests but it is not required at runtime.

paxos's Issues

License?

Can you include information about what license this is offered under (suggest MIT style if you have no preference).

Thanks

Tom

Could you tell me how to run it?

what should I do if I want to running it as the beginning of the Paxos algorithm？

distutils package.

Hi there,

I'd like to use your implementation in a Python project, preferably without copying it. Would it be possible to add a setup.py, register a PyPI account, and "python setup.py sdist upload"?

I can submit a pull request if you prefer.

Proposing a PR to fix a few small typos

Issue Type

[x] Bug (Typo)

Steps to Replicate and Expected Behaviour

• Examine paxos/durable.py and observe likelyhood, however expect to see likelihood.
• Examine README.md and observe excersise, however expect to see exercise.
• Examine paxos/practical.py and observe exectued, however expect to see executed.
• Examine paxos/external.py and observe delcaring, however expect to see declaring.
• Examine paxos/practical.py and observe aquired, however expect to see acquired.

Notes

Semi-automated issue generated by
https://github.com/timgates42/meticulous/blob/master/docs/NOTE.md

To avoid wasting CI processing resources a branch with the fix has been
prepared but a pull request has not yet been created. A pull request fixing
the issue can be prepared from the link below, feel free to create it or
request @timgates42 create the PR. Alternatively if the fix is undesired please
close the issue with a small comment about the reasoning.

https://github.com/timgates42/paxos/pull/new/bugfix_typos

Thanks.

Arguments reversed in durable.py's lseek calls (lines 99 and 131).

For example, the code is currently

def write( fd, serial_number, pyobject ):
    os.lseek(fd, os.SEEK_SET, 0)

...but should be...

def write( fd, serial_number, pyobject ):
    os.lseek(fd, 0, os.SEEK_SET)

Yes, it is not technically a bug (as os.SEEK_SET == 0), but the function prototype for os.lseek is (fd, pos, how).

Same problem in the read function.