CockroachDB V19.1发布了，提供了很多新的特性，其中包括了follower read，在没有阅读设计文档之前，我们自己推演要实现一致性的历史读取功能起始还是蛮复杂的，我认为核心的原因在于，在一个分布式的系统中，对于两个不相干的事务，version（通常都是时间戳）的大小比较没有任何意义，也就是说事务A的version Va和事务B的version Vb，无论谁比谁大或者小都不能反映真实的提交顺序（从上帝视角看），因此在从副本上读取的时候，很难保证当前的读取时间戳T到达从副本并开始执行读操作的时候不会有比T小的事务要提交（假如正好我们要这个即将提交事务的参与数据条目），因为我们无法预测未来发生的事情。

以下是我阅读理解cockroachDB的follower read的设计文档follower read并结合自己的理解整理成文，方便需要的同学学习研究。这里说一点儿题外话，我在阅读很多计算机相关的论文的时候，发现西方人的叙述逻辑（也许是语言特点造成的）中喜欢“补充”。比如加勒比海盗3中的一段台词，我印象特别深刻：A dangerous song to be singing For anyone are ignorant of his meaning. Particularly a woman；Particularly a woman alone.（唱这首歌会很危险的，如果不知道它的意思的话。特别对一个女人，更特别是对独自一人的女人。） ，这种风格在很多的欧美电影中都有，这一点在圣经中也是比比皆是。细细评味，确实有一种东方不具有的美感。

摘要

读从副本是指客户端（通常是网关代理）可以在从副本上获得一致性的基于历史时间戳的读取能力。这个特性特别适合那些长时间运行的分析查询，同时可以减轻leaseholder的负载，提升集群读性能。

       提供一致性读从副本的关键技术是节点（Node&&store）之间交换closed timestamp update（CT update）。它指明不会发生任何小于这个时间戳的事务提交（如果出现，leaseholder会拒绝）。CT update会复制给其他的副本，其他的副本用这些信息在本地构建state，以确定从副本可以提供哪个边界以内的一致性读服务。

       这个特性仅仅适用于epoch based leases。

动机

       一致的历史读取对于分析查询是非常有用的，可以提升query执行效率，通过适当的配置，可以避免流量集中（分散流量）。在地理分布的集群中，历史读取可以有效的降低关联table的外健检查的延时。它有助于恢复集群失去法定副本数之后一个一致的快照。同时它也是CDC的一个参与因子。

指导级解释

       CockroachDB为数据提供了多个副本，这些副本拥有全部的数据，因此可以从这些从副本上读取数据，但是存在复制和应用的滞后性，因此直接在从副本上读取不能保证一致性读取。

       CockroachDB在每一个store上维护一个closed timestamp（CT），CT会定期交换到其他的store（通常是几秒），因此我们可以利用这个机制来实现一致性历史读取。实际上每一个store维护一个最小提案跟踪器（MPT），由它负责维护CT。

       当一个从副本提供历史读取服务的时候，它必须知道给定的timestamp是安全的，即确定没有in-flight 或者未提交的数据（prepare已经完成）。每一个stroe都维护一个数据结构MPT，后面会专门介绍它的构建。

       比如一个range的leaseholder 在宣布一个CT之前将一条数据提交到raft log（log index P）中，那么从副本必须等到log index P的raft log应用之后才可以提供一个安全的读取时间CT。为了提供这些信息，每一个store还需要维护其上所有的range 的从副本在安全上一用CT之前必须达到的最小raft log index。

       只有当给定范围内有写操作的时候才提供这些信息，因为维护CT是影响性能的关键因素，一个stroe可以容纳超过50000个range副本，如果每次发生写都更新CT的话，那么这个开销太大了，不能接受。

       这类似于非活动range（没有写操作）的优化思路，避免非活动range副本之间的raft心跳，非活动range副本本来就可以提供历史读取，因此并不需要交换CT。也就是说并不需要每一个range都更新CT，只有那些发生了写操作的range 更新CT即可。

       从上面的描述中我们可以看到我们需要处理raft log index，但是由于技术原因，我们不能处理raft log index，而是lease Applied index（主要是因为每次都处理raft log index影响性能，并且也比较复杂）。

参考级解释

       本节介绍closed timestamp的技术细节，重点是正确性论证。

       Closedtimestamp update包含如下信息（由源store发送）：

       liveness epoch

       closed timestamp

      sequence number（用于识别更新丢失）

      range的最小lease applied index（MLAI）map

            MLAI用来更新CT。每一个store 开始时state是空的，通过合并MLAI更新state（覆盖已经存在的MLAI）。如果store接受到的sequence number跟上次不一样（出现了跳变），那么reset state 为空state，sequeue number跳变说明所有在update中未提及的MLAI已经丢失。类似的，如果epoch出现跳变，之前epoch的state直接丢弃，并且将更新应用于新时期的空状态。

       我们可以将问题分解成三个子问题分别处理。

1.    如何汇总发送CT update，这部分主要发生在副本写流程中。

2.    如何使用收到的CT update以及可以提供哪些读取。这部分主要发生在副本读流程中。

3.    如果将读请求路由到符合条件的副本上，它同时存在于DistSender以及DistSQL物理执行计划中。

我们先讨论如何使用，因为这是方案正确性最自然的起点。

服务一个读取时间戳T的历史读取请求，副本需要执行如下流程：

1.    查看lease，注意它所属的store（以及节点）和epoch。

2.    查看已知此节点的CT state以及epoch。

3.    检查时间戳T是否小于等于CT。

4.    检查Lease Applied Index是否匹配或者超过range的MLAI（如果range没有MLAI，默认时检查失败）

如果检查没有问题，那么从副本可以提供本次读服务（并不需要更新timestamp

cache），否则返回NotLeaseholderError。

注意：如果因为range缺失MLAI导致读取失败，系统需要积极尝试发送MLAI。这是因为如果range上没有写操作，lease holder range副本并不会发送CT update。

隐式保证

       收到CT update即代表如下基本保证：

1. 在任何时间，lease holder range拥有一个liveness update，它的CT落在停滞期之前。 这保证了没有任何其他节点可以在小于或者等于closed timestamp的时间戳上强行接管lease。换句话说，更新中的range map具有权威性，只要：

2. MLAI map包含任何具备在最近一次更新之前所有的提案都已经提交的range CT update。

3. 原始的store不会（永远）发起另一个节点在关闭时间戳或低于封闭时间戳写入的租约转移。换句话说，就是下一个租约将以大于closed timestamp的时间戳开始。这在实践中可能是不可能的，因为传输时间戳和建议的关闭时间戳取自相同的混合逻辑时钟，但是为了以防万一，将添加明确的安全措施。

如果此规则被破坏，另一个租约持有者可以提出违反原节点发送的closed timestamp的命令。

租约转移也需要更新MLAI map；它需要在服务将来的历史读取之前强制从副本看到新的租约（我认为租约转移一般也意味着raft leader的转移，因此此后原range变成了从副本，从一致性的角度出发，确保新的租约持有者已经继位，此时才开始提供新的历史读取服务）。租约转移需要一个有效的Lease Applied Index，同样的它强制从副本追赶raft log以及应用新的租约。这要求我们等到MLAI达到closed timestamp，直到我们决定要查询哪个节点的状态。

注意：节点重启意味着活跃时间的更改，这反过来使得重启之前发送的所有信息无效。

从丢失的更新中恢复

要在首次接收更新时（或在重置对等节点的状态之后）重新获得完全填充的MLAI映射，有两种策略：

1.    特殊情况序列号为零，以便包含所有持有租约的range副本的MLAI。当错过更新时，收件人通知发件人并将其序列号重置为零（因此接下来发送完整更新）。

2.    每当从副本读取请求因MLAI丢失而失败时，请求更新个别范围。

我们选择实施这两种策略，第一种是完成大部分工作。第一个策略是值得的，因为:

1.    有效载荷基本上是每个范围的两个变量，在线上不超过20个字节，在50000个租户副本上增加了1MB的有效载荷（但实际上可能要少得多）。即使有10倍的数量，一个罕见的10MB有效载荷似乎没有问题，特别是因为它可以流式传输。

2.    如果没有积极的追赶raft log，追随者将不得不“按需”热身，但路由层无法洞察这个过程，并盲目地将读取路由到追随者，这会导致节点重启后的体验不佳。

但是，当租约转移到其他非活动range时，此策略可能会错过必要的更新。为了防范这些罕见情况，第二种策略可作为后备：更新的接收者可以指定他们希望在下次更新时接收MLAI的range。当他们观察到一个range状态表明错过了更新时，他们会这样做，特别是当副本没有为（非最近的）租约存储已知的MLAI时。

构建outgoing更新

       我们通过简化处理，构建这样一个场景，即store没有任何待处理或者未来的写操作，也就是说没有（以及将来）in-flight的raft提案。现在我们想要把一个初始的CT update发送到另一个store，这意味着两件事情：

1.    这个store需要“关闭”一个timestamp，即阻止任何在这个时间戳可见的由此store作为租约持有者（对于当前的epoch）发起的raft提案。

2.    跟踪每一个副本的饿MLAI（持有这个epoch的租约）

第一个要求大致相当于将timestamp

cache的低水位线调整到高于closed timestamp（虽然这样做在实践中性能不佳）。

第二个要求也很简单：读取每一个副本的饿Lease Applied Index；因为没有in-flight raft提案，所有的副本都需要知道这个信息。

实际上，有时候会对我们想要获得MLAI的副本进行持续写入，因此1)和2)变得很复杂。

为此，我们不是调整timestamp cache，而是引入专门的数据结构，即最小提案跟踪器（MPT），它跟踪（粗粒度）仍在进行的提案的时间戳，它可以决定何时close一个比以前的closed timestamp的时间戳是安全的。

假设一个副本的Lease Applied Index是12，但是还有三个提案in-flight，同时另外有两个正在申请latches（被评估）。我们可以推测In-flight提案大概会分配的Lease Applied Index是13到15，被评估的将分配到15和16（这取决于他们进入raft的顺序）。MPT的第二个功能就是：它跟踪写入直到它们（raft提案）分配Lease Applied Index，并确保每一个closed timestamp返回一个权威的MLAI增量delta。它反应了最大可提交的于新的closed timestamp相关的MLAI（相比于前一个closed timestamp）。

因此当我们说一个提案被跟踪，我们说的是确定请求时间戳（在申请latches之后的时间戳）和确定提案Lease Applied Index之间的间隔。

这里很自然的有一个疑问：是否存在误报，即某些lease applied index指示的提案是否可能永远不会从raft返回并且更新相应的range的状态。答案是这是不可能的：raft提案要么被重复执行直到Lease Applied Index已经被明确超过（这种情况没有问题）或者租约持有者因为到期而退出（这种情况下会产生新的租约持有者，之前未被写入的日志则无所谓）。

跟踪最大分配Lease Applied Index是存在问题，试想这样一个场景，一个store想要close一个大约5秒钟之前的timestamp，但是存在一些高吞吐的写操作，根据最大Lease Applied Index直到我们close时间戳now()-5s，这意味着从副本在追赶上最后5秒的日志以前是不能提供读服务的，尽管副本也许根本没有相关的读服务。因此我们设计了两个相关的“桶”，它们在时间上向前移动：一个跟踪与next closed timestamp相关的提案，一个跟踪next closed timestamp之后（即大于next closed timestamp）的提案。

MPT包含当前的closed timestamp（初始化为0）和预期的next closed timestamp，我们命名为next（总是大于closed timestamp），在该时间点或者之下不接受新的写入，它还包含两个引用计数和MLAI maps各自关联next的前后。

它的API大致如下：

注意：在所有的提案上使用这个API就可以保证我们在前文中提到的对从副本的承诺。会有一点儿冗余的信息被发送（即跟踪从副本的租约请求），但是这些信息发送的很不频繁，不会对系统造成伤害（稳定性和性能的影响）。

下面我们通过一个例子来说明，我们假设所有的写都发生在一个range上，这样可以简化我们的流程以便说明问题。如下图所示，有三个提案的时间戳小于next，一个提案的时间戳大于next，next的左边的MLAI是8，右边是17.

下面我们通过一个例子来看看MPT是如何工作的。我们假设只有一个单一的副本活动。一开始closde和next之间有一些时间间隔。三个提案到达，next右侧的引用计数增加3（我们知道store只接受大于next的提案）。

接下来，我们来构建一个CT update。Next的左边的引用计数是0说明左边没有未处理的提案了，因此closed = next，next向前移动到一个合适的位置。如下图所示：

从图上看next的左边的引用计数现在是3，右边是0，虽然有一个提案的时间戳大于next，但是它仍然被next的左边跟踪，这个是可以的，它只意味着我们在正确性要求之前考虑了一个提案。

然后完成了两个提案（在LAI，比如10和11），next左边的引用计数减去2并且将MLAI的条目设置为11（10和11中最大的那个）。另外来了两个新提案（12和13），它们肯定在next的右边），next首先强制执行这两个提案，这两个提案很快执行完成，因此右边的引用计数归零。

现在还剩余一个命令在评估中，如下图所示。这个时候正好进行一次CT update，因为next左边的引用计数还不是0，因此我们还不能close next，只能发送一个空的MLAI map（表示维持原来的closed timestamp）。

最后剩余的提案在LAI 14时处理完成，同时一个新的提案进入了，next右侧的引用计数加一，这个时候我们可以看到一个比较奇怪的现象，next左边的LAI 14大于next右边的LAI 13，这个没有问题，当从副本收到LAI 14之后，需要追赶应用raft log index到14之后才能提供新的历史读取服务（即按照新的closed timestamp提供读取服务）。

下次CT update的时候，我们终于可以close next（即发送LAI 14的CT update），并将其移动到now-target duration，同时将next右边的引用计数和MLAI移动到next的左边，如下图所示。

最初的追赶

       传播MLAI的主要机制是通过写提案触发。当初始更新创建的时候，必须为从副本应该能够提供读取服务的所有的range的有效MLAI。这样就提出两个实际问题：为那个副本创建MLAI，怎样创建一个MLAI。

       我们为所有的租约由本地store持有（在检查时）的range创建MLAI（这既有误报和漏报，但是没关系，一个遗漏的从副本可以主动单独更新对应range的MLAI（上文中提到过这个策略））。

       初始追赶很简单：在close 一个timestamp（通过MPT），遍历所有的ranges（本地store持有租约），以及给MPT一个提案以便获得这个副本的最新的Lease Applied Index。

这个副本的Lease Applied Index可能会被其他的提案修改，但是MPT会追踪最大的那个。

Timestamp前移和intents

前文提到我们需要保证在CT之前不允许有新的写操作，但是对于未提交的数据则稍微比较隐晦一些。

       一个事务一般有两个相关的时间戳：OrigTimestamp（事务开始时间戳，也是读取时间戳）以及Timestamp（事务提交时间戳），事务prepare的时候，未提交的数据都以OrigTimestamp写到store中（提交的时候会修改时间戳为提交时间戳），这在快照隔离中可以防止异常。

       这样看起来似乎违法了我们的约束，事实上，读取的时候首先就会处理internts，因此如果事务已经提交，那么可以读取，否则可以丢弃（这个过程本来就是如此，这里的解释就是为了证明这个方案在这种场景下是正确的）。

       注意：对于CDC用例，此closed timestamp机制是必要不充分的解决方案，特别是CDC消费者必须在closed timestamp下处理internts（CDC的逻辑不是很清楚，这部分大致按照原文理解）。

分裂合并

       分裂没啥影响，一个range分裂成两个，只要复制原来的MLAI给两边即可。重点是合并，因为存在合并的两个range的closed timestamp不一样的问题，这样就会导致从副本的读服务收到影响。

       举个例子，两个range A，B合并，A的closed timestamp是500，而B的closed timestamp是1000，那么问题就来了，合并后按照closed timestamp 500，那么B上面的数据的历史读取服务就有问题，反过来，A上面的历史读取就有问题。为了解决这个问题，Subsume操作将返回原始store的closed timestamp，合并的副本会将其考虑在内（这部分说的不是很明确，如何考虑在内？？）。开始的时候，分裂触发器（合并流程没有研究过）将会填充B的timestamp cache；如果这对timestamp cache影响太大，我们也可以在副本上存储时间戳通过手动来转发提案。（没有特别理解这个做法）

路由层

       主要由DistSender和DistSQL负责处理历史读取。当一个读取时间戳R与当前的时间戳C满足C-R>T(C一定大于R，T是指定的时间间隔，会根据历史读取情况适当的动态调整)，那么就会把这个读取请求发送到最近的目标副本（通过健康状况，延迟等情况综合判定）。

       如果读取失败（因为副本比较滞后）那么返回NotLeaseHolderError，同时其他相同的批处理请求也不会在发往这个副本，以避免不必要的浪费。