I agree with Andy that having a pluggable consensus service in the operating system would be an interesting avenue for reducing complexity for application developers.
However I am much more familiar with those algorithms than I am at kernel development. The benefits are clear but I'm not positive that this is a good idea. It might be best if they were implement as user-land services for now until there is a better idea of how these things should work.
The problem with Paxos for example is that it is actually a handful of protocols such as Synod. The reason for its complexity is that it tries to present a total-order for all messages to all replicas despite operating in an environment where the network cannot guarantee the order of messages to all nodes and processes can come and go. It works well but the implementation to make it happen is difficult to describe.
Conversely there are algorithms derived from a model of eventual-consistency where assumptions about the order of network delivery are not made and restrictions are instead placed on the programs (as far as I've seen). As long as you write your state transition functions with certain identities and use appropriate data structures to represent your state you can guarantee a partial ordering for messages and an eventually-consistent state (the only assumption is that all messages are delivered to the replica at some point).
(Interestingly I've seen a bit of research into tuning the bounds of when things will be consistent in eventually-consistent systems).
The reason I think that building these services into the kernel could be a bad idea is that they are still not battle-hardened and they are not well understood yet. I am not a kernel developer but I imagine it would be rather difficult to design and support a "consistent" API that would allow users to plug in their desired algorithm. Thoughts?
> As long as you write your state transition functions with certain identities and use appropriate data structures to represent your state you can guarantee a partial ordering for messages and an eventually-consistent state (the only assumption is that all messages are delivered to the replica at some point).
CRDTs are one such approach. Commutativity solves the problem of ordering in a very different way, and turns the consensus problem into a "set membership" rather than a "membership and order" problem. CRDTs have some really nice properties, and are a very active area of research.
However I am much more familiar with those algorithms than I am at kernel development. The benefits are clear but I'm not positive that this is a good idea. It might be best if they were implement as user-land services for now until there is a better idea of how these things should work.
The problem with Paxos for example is that it is actually a handful of protocols such as Synod. The reason for its complexity is that it tries to present a total-order for all messages to all replicas despite operating in an environment where the network cannot guarantee the order of messages to all nodes and processes can come and go. It works well but the implementation to make it happen is difficult to describe.
Conversely there are algorithms derived from a model of eventual-consistency where assumptions about the order of network delivery are not made and restrictions are instead placed on the programs (as far as I've seen). As long as you write your state transition functions with certain identities and use appropriate data structures to represent your state you can guarantee a partial ordering for messages and an eventually-consistent state (the only assumption is that all messages are delivered to the replica at some point).
(Interestingly I've seen a bit of research into tuning the bounds of when things will be consistent in eventually-consistent systems).
The reason I think that building these services into the kernel could be a bad idea is that they are still not battle-hardened and they are not well understood yet. I am not a kernel developer but I imagine it would be rather difficult to design and support a "consistent" API that would allow users to plug in their desired algorithm. Thoughts?