tidb_load_based_replica_read_threshold may violate linearizability in point get scenario

[overvenus]

Bug Report

tidb_load_based_replica_read_threshold allows tidb to read on follower when leader is busy.
It may violate linearizability in point get scenario as the diagram shows.

A writes k to 9, B is concurrent to A and reads 9 on follower, C is concurrent to A and happens
after B but reads 8. It is possible when follower applies faster than leader.

  k = 8
  -------------------------> time
A    ---------------
     w(k, 9)

B     ----
      r(k) = 9 on follower

C            ----
             r(k) = 8 on leader

1. Minimal reproduce step (Required)

Run Jepsen tests and inject some errors that cause TiKV busy.
It hard to reproduce in real world though.

2. What did you expect to see? (Required)

Does not violate linearizability.

3. What did you see instead (Required)

May violate linearizability.

4. What is your TiDB version? (Required)

v7.1.0

[cfzjywxk]

@overvenus
It seems to be a follower-read question.
Considering the traditional 2PC write processing, the follower-read may not break linearizability because at least there would be a prewrite lock on the leader replica which is explained in the early design document.

If async-commit or 1PC protocol is used, just consider 1PC for simplicity. If 9 is replicated and replayed or applied on the follower replica, it means the leader MUST have stepped into the async write phase processing the prewrite command.
If the apply processing is slow on the leader replica and it's finished first on the follower replica, the memory lock on the leader is still being held. So a read operation happens later on the leader replica should at least see the memory lock, and an ErrKeyisLocked would be returned to the client triggering leader read instead of returning 8.

So theoretically, there should be no linearizability violation, but I've not written a test case on tikv to verify this, it seems to be worth adding such test cases.

/cc @you06 @zyguan

[overvenus]

IIRC, a point get with ts u64::MAX skips lock, so it can read 8?

[cfzjywxk]

IIRC, a point get with ts u64::MAX skips lock, so it can read 8?

For the autocommit point get, the u64::MAX would be used as read_ts, and the linearizability would be broken in such case:

1. txn1 write 9 in session s1, the log is replicated and applied in replica peer while the apply on leader is slow.
2. session s2 read the key using autocommit point get with replica read, the memory lock check is skipped, 9 is returned.
3. session s2 read the key using autocommit again using leader read, the memory lock check is skipped again, 8 is returned.
4. From the perspective of s2 the linearizability is broken.

It looks a long existing problem for the follower-read feature.

[overvenus]

I think we need to add some caveats on document, since the feature is enable by default, does it mean that TiDB no longer guarantee linearizability in the autocommit point get scenario?

[cfzjywxk]

To make follower-read and autocommit point get compatible, use leader read only for autocommit point get.

[cfzjywxk]

To make follower-read and autocommit point get compatible, use leader read only for autocommit point get.

This may not be a good solution as it may cause read hotspot issues for older clusters upgraded to the latest version.
Another possible solution is to check memory locks processing read index requests in tikv but not skipping them.

[cfzjywxk]

Close this by creating another issue in tikv tikv/tikv#14715.