Potential stale reads

[rystsov]

Hi folks,

I've read the Building a Strongly Consistent Cassandra with Better Performance post and it seems under some conditions YugaByte may return stale data.

In the post written that YugaByte serves read request directly from a leader without consulting the other nodes:

Because of the use of the RAFT consensus protocol, the data held by the quorum leader is guaranteed to be consistent. So a read operation requires only a single read (1x) from the leader.

As far as I know, it isn't completely true and if the reads don't go through the Raft/Paxos rounds there are possibilities for returning stale data. For example, there was a similar bug in Etcd which forces them to introduce ?quorum=true parameter.

Let me describe the conditions which may lead to this behavior. As I understand you use leases to make sure that a leader is still a leader. So imagine that we have three nodes: A (leader), B (follower), C (follower) then the following events happen

1. A client successfully writes key:=1.
2. A network partitioning happens which isolates A from its peers.
3. Just after partitioning the whole machine A freezes.
4. On the B, C side of the network leases expire and B becomes a new leader.
5. The client successfully writes key:=2
6. The A machine unfreezes
7. The client reads and the request lands node A
8. From the A's perspective leases haven't expired yet (the local time was frozen) and it answers key=1
9. The client receives an inconsistent result

Please point to an error in my reasoning if I got the situation wrong.

[mbautin]

Hi @rystsov,

Thank you for your detailed post! Our leader lease algorithm works as follows:

• With every leader-to-follower message (AppendEntries in Raft's terminology), whether replicating new entries or even an empty heartbeat message, the leader sends a "leader lease" request as a time interval, e.g. could be "I want a 2 second lease". This number is usually a system-wide parameter. For each peer, the leader also keeps track of the lease expiration time corresponding to each pending request (i.e. time when the request was sent + lease duration), which is stored in terms of local monotonic time (CLOCK_MONOTONIC in Linux). The leader considers itself as a special case of a "peer" for this purpose. Then, as it receives responses from followers, it maintains the majority-replicated watermark of these expiration times as stored at request sending time. The leader adopts this majority-replicated watermark as its lease expiration time, and uses it when deciding whether it can serve consistent read requests or accept writes.

• When a follower receives the above Raft RPC, it reads the value of its current monotonic clock, adds the provided lease interval to that, and remembers this lease expiration time, also in terms of its local monotonic time. If this follower becomes the new leader, it is not allowed to serve consistent reads or accept writes until any potential old leader's lease expires.

• To guarantee that any new leader is aware of any old leader's lease expiration, another bit of logic is necessary. Each Raft group member records the latest expiration time of an old leader that it knows about (in terms of this server's local monotonic time). Whenever a server sends a response to a RequestVote RPC, it includes the largest remaining amount of time of any known old leader's lease with its vote. This is handled similarly to the lease duration from AppendEntries on the receiving server: at least this amount of time has to pass since the receipt of this request before the recipient can service requests in case it becomes a leader. This part of the algorithm is needed so that we can prove that a new leader will always know about any old leader's majority-replicated leader. This is analogous to Raft's correctness proof: there is always a server ("the voter") that received a lease request from the old leader and voted for the new leader, because the two majorities must overlap.

Note that we are not relying on any kind of clock synchronization for this leader lease implementation, as we're only sending time intervals over the network, and each server operates in terms of its local monotonic clock. The only two requirements to the clock implementation are:

• Bounded monotonic clock drift rate between different servers. E.g. if we use the standard Linux assumption of less than 500us per second drift rate, we could account for it by multiplying all delays mentioned above by 1.001.

• The monotonic clock does not freeze. E.g. if we're running on a VM which freezes temporarily, the hypervisor needs to refresh the VM's clock from the hardware clock when it starts running again.

Also, I would like mention out that a faulty local clock will likely cause problems in many different software systems, including the user's application. I believe that our assumption of the availability of a local monotonic clock with a bounded drift relative to any other such clock within the same cluster is quite reasonable. And to quote the Spanner paper:

Our machine statistics show that bad CPUs are 6 times more likely than bad clocks. That is, clock issues are extremely infrequent, relative to much more serious hardware problems. As a result, we believe that TrueTime’s implementation is as trustworthy as any other piece of software upon which Spanner depends.

That said, we are working on verifying our assumptions about the clock performance in a variety of configurations. However, if you could clarify what you meant by "clock freezing" more precisely or point out scenarios in which it is likely to happen, or ways to reproduce it, that would be very helpful!

[rystsov]

As I understand one of the situation when time may freeze is cloud deployment with live migration happening behind the scenes. In this case we can't guarantee that:

• hypervisor refreshes the VM's clock
• clocks on both hypervisors are in sync

[mbautin]

@rystsov: thanks for pointing out the live migration case. Looking at this thread, AWS did not support live migration as of Aug 2016, and I cound not find any indication that this has changed, and Google Cloud Platform supports live migration, which can be turned on or off for each instance. We will make sure to update our documentation to mention the interaction between clocks and live migration, and will look into what various cloud environments supporting live migration guarantee regarding clock behavior in that case. However, given that the underlying platform provides bounded-drift monotonic clocks, we believe that YugaByteDB's architecture allows reading the latest value without querying a majority of replicas (a "quorum read"), so I will close this issue for now.