xiang90
commented
10 years ago @aphyr Thanks for the testing. I have replied for this once at https://gist.github.com/xiangli-cmu/d6c59c42d72d3582db9d. I was thinking you were talking about the linearization of CAS operation on twitter, which made a a little confused. Anyway, I realized what you were talking about.
I think Consistency != linearization. etcd provides sequential consistency for all the write and read operations(in etcd we do not have write operation: we only have write and read/ read) that go thorough the state machine. We never aim at strict consistency (one-copy semantics). We do a read redirection to leader just to ensure the client that send out the previous write operation can see the result by a subsequent read operation.
I totally understand the problem you are saying and am aware of how to fix this. But it is just a tradeoff we made long time ago. Actually not only the leader changes can cause the problem, two concurrency write/read operations from different clients can also lead to stale read in etcd.
How to fix? We can just simply let read also go through raft without persistent it to disk. We do not even need to record that in memory anyway. If we want we can make it happen very soon.
How to handle this in etcd:
In etcd, we attach an index to each response. It is the logical clock in etcd. We ensure linearization in logical clock perspective. You can see write k->foo index = 1, read k->bar index = 0, read k->foo index=1 in the real time perspective. But when you reorder them with the etcd time(index) and analyze them, they should be linearizable.
Again: etcd tries to ensure sequential consistency, which means each replica have the same command execution ordering. With consistent read, we ensure the strict consistency for each separated client in most cases (leader dies, new leader might has the command but not commit yet.).
aphyr
glycerine
bmizerany
kelseyhightower
ptomasroos
chadharrington
jefferai
philips
Etcd aims to provide linearizable registers supporting reads, writes, and CAS operations. In a linearizable system, all operations must appear to take place at a specific, atomic point in time between the invocation and completion of that operation. This is not the case: reads in etcd can return stale versions of nodes.
In short, it's possible to write "foo", write "bar", then read "foo".
Is this a theoretical or real problem?
Real. I can reproduce it reliably on a five-node cluster with only a small number of clients performing five concurrent ops per second. Since leadership transitions occur rapidly in etcd, even a transient hiccup in network or host latency can cause this issue. I have a failing case in Jepsen which triggers this behavior in roughly 20 seconds; see the client, test, and a sample run with analysis.
The window of inconsistency is relatively short--sub-second--but appears reliably during transition.
Why does this happen?
For performance reasons, when a read request arrives on a node which believes itself to be the leader, etcd reads the current state from the Raft FSM and returns it to the client. This is fast and simple, but not quite correct.
Raft allows multiple nodes to believe themselves the leader concurrently. If a client makes a request to a leader which has recently been isolated, that leader may believe itself to be the leader even though a new leader has been elected and is accepting new writes. Clients writing to one side of etcd will find that their writes are not reflected on the old leader, until the old leader steps down.
How do we fix this?
Consistent reads must wait for at least one network round-trip; the leader needs acknowledgement from a quorum of followers that it is still the leader in order to service a read. One way to do this is to make a entry for the read operation to the Raft log, and when it has been committed, send the read back to the client.
A more subtle way to fix this problem is to (invisibly) piggyback the read on the state of transactions the leader is already executing. In particular, the leader can track an outgoing unrelated log entry, and if it successfully commits, use that information to assert that it is still the leader. I believe the linearizability window for this strategy allows reads to proceed concurrently with writes; the leader looks at its local FSM, chooses the value X it thinks is valid, waits for a commit to propagate, then returns X to the client.
It might also be possible to simply wait for a heartbeat from all follower nodes, confirming that they still believe the leader is valid. I'm not quite sure about the safety of this one.
What are the costs?
At least one round-trip latency for each read. This makes reads only a little less expensive than writes, in latency terms, but since they don't need to touch the log directly, doesn't balloon the size of the log. All required state can be kept in a single leader's memory.
Since the HTTP API terms these reads "consistent", I strongly advise making them consistent. It may be worth having three consistency tiers:
any, which allows arbitrary nodes to serve arbitrarily stale requests,leader, which allows a short window of inconsistency but requires no network round trip. This is the currentconsistentmode, and remains useful for systems doing CAS loops where the reduced inconsistency window dramatically reduces contention, but does not impact correctness, andconsistent, which performs a consistent (i.e. linearizable) read.Incidentally, I believe Consul is subject to a similar problem, but haven't verified experimentally yet. I hope you find this helpful! :)