During the last semester of my college, we were asked to read the (chord paper) and implement it without fault tolerance. We built it with the following feature:

  1. A new node can join.
  2. A client can query a key in any node.
  3. A client can query a get request in any node.
  4. The current system has no replication. Keys are stored in only once place.

I want to add fault tolerance to the existing system. There is what I want,

  1. Each key is replicated in one or more nodes with some predefined rules.
  2. The replicated nodes talk to each other for consistency among them.

I also read raft paper and thinking in the direction of adding raft logic in the replicated nodes. For example node A has 5 replication, A1,A2,A3,A4,A5, these five nodes will execute raft logic to maintain consistency.

How the system ends up losing availability (because from the raft logic, a node can not directly reply to the client without replicating the keys to more than 50% of the nodes. )? How should I trade-off?

Please suggest design choices for merging chord DHT and raft logic together.


Here are some of the links on Raft and Chord. raft_ref chord_ref

  • 1
    I can't help you with the theory, but in systems like Redis you can specify both the number of replicas you need in total, and the number of replicas that need to exist before a successful response when changing values. For example a system can have 5 replicas required, but return the update request after only two nodes have the data. The idea is that the cluster will be eventually consistent. There is always a risk that at any given moment in time the total number of replicas are not written yet. Nov 1, 2019 at 14:48
  • 1
    But that's OK, since for most systems you don't need ACID updates on a cache server. If you have a cache hit, you return the response immediately, and if not you build your response as per normal. Typically the next time the resource is requested the full set of replicas are present. Nov 1, 2019 at 14:50

1 Answer 1


Let me rephrase your question - how is CAP theorem applicable for a raft based system.

For the context: CAP says that in case partitioning is happening, then you have to pick either consistency or availability. Raft (or other consensus based system) allows you to tolerate some partitioning; or, in the spirit of CAP, some nodes can get disconnected, but from system point of view we won't call that partitioning.

Let's say a raft cluster has 5 nodes. If two nodes are down, that's ok - the system still is not partitioned - availability and consistency is still there.

But if three nodes goes offline (not partitioned way, but actually offline), then the system is in partitioned state and we have to decide - do we give up consistency in favour of availability?

Clarification on picking consistency or availability in case of consensus based system:

A consensus based system gives a strong consistency, and it never compromises it - in case something gos wrong - e.g. majority of nodes goes offline - the system will stop being available. In that case, being available over being consistent brakes the main property of a consensus based system.

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.