RFC: Support user-specific log index

[TennyZhuang]

Background

In the original raft algorithm, log index is an increasing consequent integer generated by term leader, and is not exported to raft library user. After introducing follower reader, it's reasonable to allow client read by a specific old version (from MVCC) instead of latest entry. This feature will introduce a large latency improvement for large OLAP transaction. The learner need not to keep latest for every read request in a large transaction.

Implementation

To implement this feature, we need maintain the mapping from MVCC version to raft log index, which is heavy to implementation. An alternative solution is allow client to specific an increasing log index in propose request. Client should ensure the user-specific index is unique and increasing in order (For TiKV, the user-specific index is version generated in PD, these properties is already guaranteed in MVCC). Then we can implement follower-read-by-specific-version easily.

TBD

1. Log Index for some raft internal operation (conf change) still needs a log index, how to generate it?
2. The user-specific index is guaranteed to be increasing and unique, but not consequent. This will break some raft optimization that allow gap in log such as Parallel raft in PolarFS.

This is a very early idea, and I have not found it in any other implementation or publication.

[Fullstop000]

Can you provide a more specific scenario for this feature? I think the MVCC style of reading could be more easily achieved out of the raft lib.

[TennyZhuang]

How to achieve it out of raft lib? We don’t know the mapping from a version to a log index out of the raft lib, so we cannot directly read an outdated log even with an very old version. It seems that now the follower read have to wait the follower keep latest with leader. Hetian Zhu <notifications@github.com>于2019年9月2日 周一09:46写道：

…

Can you provide a more specific scenario for this feature? I think the MVCC style of reading could be more easily achieved out of the raft lib. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#281>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACF4VXWVCUGSSSBOYHBXQ63QHRV53ANCNFSM4ISWJIMQ> .

[TennyZhuang]

A MVCC style read can be performed correctly on a follower iff it has followed enough logs to the read version, but because of lack of the mapping from version to log index, we have to read on the latest log entry to get an older version entry, which increase the latency. Hetian Zhu <notifications@github.com>于2019年9月2日 周一09:46写道：

…

Can you provide a more specific scenario for this feature? I think the MVCC style of reading could be more easily achieved out of the raft lib. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#281>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACF4VXWVCUGSSSBOYHBXQ63QHRV53ANCNFSM4ISWJIMQ> .

[Fullstop000]

It seems that now the follower read have to wait the follower keep latest with leader.

Is the key point that we don't have a mapping like index => version where the version is an application layer abstract?
What about maintaining the mapping applied index => version in the state machine so that when you want an old version reading you can just check the applied index.

Maybe I misunderstand your description.