4 ms·

I think that in the specific case of a key-value store (with just a get/put API), there is a more scaleable way to get consensus than putting a KV store on Raft

I think that in the specific case of a key-value store (with just a get/put API), there is a more scaleable way to get consensus than putting a KV store on Raft. Raft (and multi-paxos) present a shared log abstraction, which is good if you want to impose a single ordering (what a replicated state machine needs). But writes to different keys are order independent, and you don't need ordering (between keys) to get a linearizable kv store. By going through raft or multi-decree paxos or VS replication, you pay a penalty for ensuring that all writes are sequentialised via the log. The penalty includes having to go through a single leader for all reads and writes, and lots of jitter when a leader fails up until the new leader becomes stable. In contrast, if you simply use the equivalent of basic (single-decree) paxos per key, the writes can be leaderless. Of course, for performance reasons, each server must batch network and disk i/o.

alexandre_m 3y ago
> if you simply use the equivalent of basic (single-decree) paxos per key, the writes can be leaderless Is there any writes acknowledgements in what you describe when replication factor > 1? How do you ensure that I always read the last written value to the same key?
- sriram_malhar 3y ago
  Both reads and writes go through the basic paxos protocol, so the answer to both is yes.
  - alexandre_m 3y ago
    I've never taken the time to really learn paxos in depth, so forgive my ignorance. I'm not sure that leaderless mode with basic paxos would be really better in the K/V scenario we're talking about. There would be a lot of round-trips for each request, so there's higher latency than the raft counterpart, especially for reads. I suppose better availability in the case of node outages would be one advantage. Anything else I miss?
    - sriram_malhar 3y ago
      Nope; latency would be about the same, since it requires two rounds for consensus for all ops. Note that Raft itself has no clue about the specifics of the op, whether it is a read or a write, and for leader to be sure it is still the leader, it needs to wait for an answer from a majority of servers. Of course, this is not done for every single op, but batched. Similar methods will have to be used for my suggestion as well. Now, in many production cases, one tends to put a lease on leader election. Until the lease is valid, the leader is guaranteed that it is still the leader and no one else has a more up to date state. This allows reads to be served from the leader's state machine without having to touch Raft at all.

alexandre_m 3y ago

> if you simply use the equivalent of basic (single-decree) paxos per key, the writes can be leaderless Is there any writes acknowledgements in what you describe when replication factor > 1? How do you ensure that I always read the last written value to the same key?

sriram_malhar 3y ago
Both reads and writes go through the basic paxos protocol, so the answer to both is yes.
- alexandre_m 3y ago
  I've never taken the time to really learn paxos in depth, so forgive my ignorance. I'm not sure that leaderless mode with basic paxos would be really better in the K/V scenario we're talking about. There would be a lot of round-trips for each request, so there's higher latency than the raft counterpart, especially for reads. I suppose better availability in the case of node outages would be one advantage. Anything else I miss?
  - sriram_malhar 3y ago
    Nope; latency would be about the same, since it requires two rounds for consensus for all ops. Note that Raft itself has no clue about the specifics of the op, whether it is a read or a write, and for leader to be sure it is still the leader, it needs to wait for an answer from a majority of servers. Of course, this is not done for every single op, but batched. Similar methods will have to be used for my suggestion as well. Now, in many production cases, one tends to put a lease on leader election. Until the lease is valid, the leader is guaranteed that it is still the leader and no one else has a more up to date state. This allows reads to be served from the leader's state machine without having to touch Raft at all.