4

I have a need for a distributed data store, where existing solutions may not work as the computers these will be running on will be extremely resource limited, for instance 64-128MB RAM. Plus, as a fun exercise.

I'm looking at writing a simple implementation of the RAFT algorithm, however the data store, which will simply be a collection of key/values, may have clients updating any of the nodes at any time, and must keep consistency among the entire cluster.

I was thinking of having a node, every time when updated from a client, calculate a hash, then get consensus/confirmation from the other members of the cluster on the old and new hashes and commit, once that is gotten from a majority. Would that ensure orderly updates when two members are updated simultaneously? Any thoughts on implementing this?

2
  • You want orderly updates while allowing multiple members to be simultaneously updated?? You will either have to serialize updates, accept inconsistency, arbitrarily choose to loose certain updates, and/or constrain to a smaller problem. Any of those might work for your domain, whatever that happens to be. Sometimes getting more clarity on the domain will help reveal a workable solution.
    – Erik Eidt
    Commented Jan 1, 2018 at 16:36
  • How many nodes do you expect to be in a cluster (i.e. involved in the consensus algorithm)? If it is more than, say, 7, or so, then you probably want to take a different approach where a small number of nodes perform the consensus algorithm to appoint some other node as a primary in a primary-backup configuration. This is how Kafka works, for example. If you intend to use this "seriously", I would strongly recommend attempting to get an existing, tested solution to work. These algorithms are very easy to get wrong, and it is very difficult to tell when they are incorrectly implemented. Commented Jan 1, 2018 at 18:04

3 Answers 3

1

My understanding of your question is that at any point in time T, I can ask any of those nodes about that value associated with a given key, and get the same answer.

Similarly I should be able to update any key, on any server, and on my next read of another (or the same node) for that key see the New value (assuming no one else has updated it).

Worse, your program may actually require the ability to update numerous keys (add/delete/modify) atomically, perhaps dependent on the values or presence of other keys. Which is even harder, and vast manuscripts have been written on how to get that right on even a single computer with a single thread.

Importantly RAFT does not guarantee the above by itself. At best it is a way of getting multiple machines to agree on one version of history.

Dirty Reads, Missing Writes, and Data Mayhem

Imagine a scenario where consensus has been reached, you report back that the write was successful. You immediately attempt to read the value back. This time you read it back from another node, it responds with an old value. Why that node hasn't synchronised yet.

Another scenario where two programs write their values to two separate nodes. Both nodes race to get the majority to agree to their write. One will fail. One program re-attempts its write, the other writes to a different key. But, because there can only be one authentic history, they both still race to get the majority. This can effectively lock one node (and its programs) out of the update loop because it can't gain the majority quick enough.

Yet another scenario, a reader and two writers of the same key. The writers have written their values. The reader read the key, which value does the reader see: the old, or one of the two new values? It depends but it is now a race, each node that is asked may have a different answer.

Industry Solutions

Seriously these are not simple issues to overcome. Numerous big name distributed databases state explicitly that these scenarios will happen unless you specifically use a replicated master. Writes can only happen serially on the master, and replicas only serve up known historic versions. The readers are aware that they are reading old data. And writes call out specifically what data should not have changed for the write to be valid.

Before I get told that there are other solutions... Yes they exist. Are they simple to implement correctly? No. Even the big names get it wrong, frequently.

Trade Offs

Do keep RAFT. It is a good idea for getting to a consistent state. It is also reasonably easy to implement correctly and has good recovery and degeneracy properties.

Now what is most important?

If everyone being on the same page is important, only serve up values which your machine knows have been seen by all the other nodes. Even if your log knows a newer value.

If instead reads only need to be consistent to a single time, have the user pick a point in time that is no newer than the newest majority confirmed log entry. Only serve up answers from then or before.

If dirty reads are fine, always serve the latest and greatest.

If losing no writes is important, funnel all writes via a single elected node. Similarly transactions should be handled by this writing node.

If transactions are pretty heavy weight in terms of calculation, number of reads and writes. Then pin the time when all reads where consistent and log what was read and any boundaries (ie. keys don't exist, value was non-existant or null). Ship that log + the writes to the elected transaction host (or become that elected host). The writers job is to verify that the world still looks okay, and then perform the writes, if anything has changed the whole transaction is rejected.

If losing writes is fine, don't even bother confirming that it is committed. Update the raft log and allow consensus to determine a correct history. If it was important to track the writes success, it will be successful if its raft log entry is ratified by the majority, and failed if its raft log entry was discard in favour of an alternate history.

Alternately just don't bother trying to make this a Key/Value store and instead make it a Key/Time/Writer/Value store and let the client sort out the fuss. Nothing is easier than shifting the burden to someone else - it is just not nice.

Client Perspective

Your client code needs to be aware that the nodes in this swarm may become inconsistent for any number of reasons. This means some level of sense about the quality of each node from a read/write perspective. Most of them can answer old queries accurately, but only a few may have access to the latest updates, perhaps even fewer should be consulted for writing.

A simple metric is to semi-regularly check-in with each accessible node and ask for say the hashes of the last 100 log entries. Compare them. If most nodes have the same hashes then they are mostly in agreement and the nodes are stable. If one node has nothing in common it has de-synchronised. If many nodes are out of balance then there is trouble, don't trust anything.

Testing

You will need to test this system setup with multiple nodes. You'll have to address slow connections, split networks, and recovery while checking for transactional guarantees, dirty reads, and missing writes (to name a few) to get any confidence in this system as a reliable data store.

More Knowledge

Seriously find yourself a dry textbook on database architecture and engine design. Others have been wrestling with these problems for 80+ years, go find their knowledge. It will at least tell you what the problems are, even if the solutions aren't readily evident.

0

Usually it's much much easier to have many completely separate little "not distributed at all" databases.

To do this for a key/value store, use the key to calculate a hash value, then do "server_number = hash % number_of_servers". In this case you can completely ignore consensus (e.g. the current version of any piece of data will always be on a specific server and never anywhere else).

If you have a changing number of servers then it gets messier (but you can add adaption to cover this). If the client has to be unaware of the server topology then you can add a "pre-server" to direct requests (at increased latency costs). If you need fault tolerance or parallelism for performance reasons (e.g. many clients requesting the same data from many servers at the same time) then this method quickly becomes a nightmare.

0

If you haven't looking into the CAP theorem, that's where you should start. The solution you propose means that if any node is unable to talk to a majority of the others, it wont be able to handle updates. If you are OK with that, then it should be OK. It would probably be a good idea to elaborate on why orderly updates are important in the design.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.