Skip to content

Instantly share code, notes, and snippets.

@rofr

rofr/piggyback-consensus.md

Created October 3, 2017 13:45
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rofr/fff205fdb9502da8adda679979d288d6 to your computer and use it in GitHub Desktop.
Save rofr/fff205fdb9502da8adda679979d288d6 to your computer and use it in GitHub Desktop.
Download ZIP
Thoughts on CAP, consensus and replication in a memstate cluster
Raw
piggyback-consensus.md

OrigoDB

OrigoDB Server is an in-memory database for dotnet written in c#. It's implemented as a replicated state machine using write ahead logging of the mutating operations. The in-memory state model is derived from the sequence of operations persisted to the log. Writes are only accepted by the primary node and syncronously replicated to each of the replica nodes.  OrigoDB has no leader election (because the effort would be massive), promotion to primary is a manual process. https://github.com/devrexlabs/origodb

Memstate

Memstate is a reimplementation/port of OrigoDB based on the same principles but with a fundamentally different approach to logging. By routing the mutating operations (commands) through an underlying stream database (eventstore, kafka, kinesis, etc) message ordering, distribution and durability are guaranteed at the logging level. The key is to apply the commands when they return from the stream database. Using this model it's possible to accept writes at any node. This is the current default behavior of a memstate cluster. In fact, each node is independent and unaware of any other nodes. https://github.com/devrexlabs/memstate   I've been thinking a few months about if it would be possible to implement leader election on top of the stream database by passing messages through the stream. Today I started thinking a bit deeper and after outlining a possible implementation it seems very plausible. In its simplest form any node could just send an ASSUME_LEADERSHIP message to the bus, the key is to use the same message channel as the commands, rejecting commands from non-leader nodes.  

  • Is there any research in this specific area or is it too trivial?
  • For memstate, what value would having a primary + N replicas provide over the current multi-writer model? The replicas would still be updated asynchronously and could possibly lag behind. It feels like this would only sacrifice availability without any gain in consistency. Perhaps in combination with 2PC to keep the replicas in sync memstate could operate in CP mode. Now I will be thinking about how to implement 2PC over a messagebus :)
  • Could leader election over message bus be useful in other applications?
  • Could memstate in its current implementation be classified as an AP system? (Write at any node, read at any node but possibly stale results)
  • The state of a node at any given point in time is a consistent snapshot, but not necessarily the most recent one. Is there a name for  this kind of temporal inconsistency?  
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment