概述

CockRoachDB 19.2 alpha版本中有一个重大的改进：并行提交，据其官方文档说明，可以减少分布式事务一半的延时，下面就看着CockRoachDB的并行提交是如何做的。
本文是基于cockroachdb并行设计文档的一些阐述和理解。

CockRoachDB 19.2 alpha之前的版本有个缺点：不允许最终事务的提交操作与其他写入操作并行执行。这个缺点在19.2 alpha版本中得到了解决，从而允许并行执行，将最终事务需要达成共识的操作由两次变成了一次。因此将最终事务的提交延时缩小了一半。

这是通过引入新的事务状态“STAGED”来实现的，该事务状态可以与最终批次并行写入。这种事务状态通常是短暂的;在出现故障的且事务处于“STAGED”状态的时候，则事务可以被放弃退出，并通过新引入的status resolution process来恢复事务。

通过适当的批处理，可以直接降低写入的延迟。

由于意向写（intents write）仍然保持两轮共识操作，因此意向写的延时仍然保持不变，且相互之间有依赖和竞争关系的操作也不会有太多改善。

动机

CockroachDB通过共识协议来提供一致性保证，但是为了达成共识也导致了额外的延时。在单片或者NoSQL数据库上通常也不会使用共识协议，因此由于使用共识协议而导致的延时性通常会成为CockRoachDB的最大缺陷，而导致很多人放弃使用CockRoachDB。

作为一个以地理分布用例为傲的数据库，我们必须努力将常见OLTP事务引起的延迟降低到理论最小值附近：所有读取延迟加上一个共识延迟。

在撰写本文时，这远非如此：由于一开始的时候底层实现比较简单，繁琐的事务设计会在每次写入时都产生共识延迟（除非它们可以使用RETURNING NOTHING）。

如下面的（隐式）事务

INSERT INTO t VALUES (1, 'x'), (2, 'y'), (3, 'z');

其中表t具有简单的KV模式，并且已经在key值为：2和3处进行了range 拆分。由于这是一个隐式事务，因此SQL层会将该insert操作作为一个KV批处理发送

BeginTransaction(1)
CPut(1)
CPut(2)
CPut(3)
EndTransaction(1)

并且，当按range边界划分时，DistSender会考虑subbatches

BeginTransaction(1)
CPut(1)
EndTransaction(1)

CPut(2)

CPut(3)

为了最大限度地减少延迟，您可能希望将这三个insert操作作为三个批次并发发出。但是，现在还不是这样做的。

要知道为什么不这样做，那是因为若分三个批次并行执行，那么就有可能前两个批次操作成功而第三个批次失败（这样，就违反了唯一性约束）。

第一个批次创建并提交了事务记录，因此任意的意向写都会生效。但是，第三个写却未执行，因此丢失了一个写入。

要解决此问题，DistSender会检测所有尝试提交事务的批次，并在必要的时候强制将commit作为一个单独的批次执行。这样将会首先按照如下方式并行发送请求：

BeginTransaction(1)
CPut(1)

CPut(2)

CPut(3)

然后，基于上述并行请求是否执行成功，在执行如下请求，

EndTransaction(1)

这样反而会使延迟加倍（忽略客户端< - >网关延迟）。

这个RFC是针对于＃16026 issue提出的，可以避免针对于commit的写入延迟。＃16026中提出：事务延迟大致等于读取延迟的总和，再加上两轮共识的时间。该提案将其降至可能的最小值：读取延迟的总和，加上共识的结果。

总述

如上一节所示，基本问题就是在有证据表明最后一批写入成功之前，事务不能标记为已提交。

新的事务状态“STAGED”通过在事务记录中填充具有足够多的信息以证明（或反驳）这些写入已经完成或者保证可以完成。如果证明这些写入完成，则必须将该事务标记为committed;否则，它可以标记为aborted。这意味着协调器若知道这些写操作成功时可以提前返回到client，并且可以异步lazily地执行实际的commit操作，这样可以缩短从事务提交到返回到client端的延时。

目前我们先不考虑错误处理，我们希望coordinator能够：
1.将状态为“STAGED”的EndTransaction与最后一批写入并行发送与执行。
2.所有写入成功后，返回客户端，
3.异步发送状态为“COMMITTED”的EndTransaction
4.解决intents读写。

为了实现这一点，我们需要搞清楚commit change意味着什么语义。就目前而言，这意味着：

当且仅当存在一条状态为COMMITTED的事务记录时，我们才认为该事务的状态是committed

建议的提交条件（也叫做 commit condition）是：

当且仅当 a）存在一条状态为COMMITTED的事务记录 或 b）一条状态为STAGED的事务记录并且在该事务的最后一批中所有intent write都存在时，才提交事务。

若一个事务所处的状态为STAGED，则该事务的提交条件（commit condition ）我们称之为隐式提交（implicitly committed）。

若存在一条状态为COMMITTED事务记录时，它被成为显式提交（ explicitly committed）。在典型的操作中，遇到的事务记录通常是显式提交。

但是，当coordinator崩溃或断开连接时，则不能够进行显示提交，因此我们需要STAGED事务记录来包含足够的信息进而检查是否满足提交条件（commit condition）。为实现此目的，最后一批次中的涉及多个写入的的意向写要包含在EndTransaction请求中;我们称这些意向写为promised writes。

实际上，为了达到后续的一致的COMMITTED记录（需要包含所有的写入），它还将单独包含所有先前批次的意向写。

本文档中提到的变更主要影响“DistSender”和冲突解决机制。 STAGED事务状态绝对不会出现在DistSenders的消费者中，也绝对不能被DistSenders的消费者使用。

示例说明

同时示例来说明上述理论。在示例中，key ：ki位于range i上;时间从左向右流动，每条线对应一个goroutine（可以重复使用以实现紧凑性）。针对单个range的批次按花括号分组。垂直线表示右边的事件等待左边的事件完成。 Write（ki），Stage（ki），Commit（ki）是DistSender发送的请求（来自事务中的最后一批）。从包含transaction recode的副本的intent resolver调用Resolve（ki）。

这些例子附有解释，其中可能包含未在说明中反映的其他细节。

我们现在从DistSender的角度来看一些基本的例子。

Example (正常情况)

该事务将两个write和staged transaction recode并行写入到三个range。当所有操作成功返回时，客户端将收到其提交的确认。会发起异步请求将事务记录标记为committed（这不是为了保证正确性所必需做的）。
请注意，事务在最后一批中没有写入k2，但之前已写入（因为这是锚定事务记录的位置）。我们忽略了作为Commit的一部分而发生的intent resolution。

Write(k1)   ok      |                  |Resolve(k1) ok
Stage(k2)  ok       |Commit(k2)      ok
Write(k3)   ok      |                  |Resolve(k3)   ok
                   ^- ack commit to client

Example (1PC commit)

目前的做法：每当transaction的最后一批请求定位到单一range时，批次就按原样发送。特别是，没有写过“STAGED” transaction record的时候。此外，如果一个transaction只有一个批次，则可以在该transaction对应的range上进行1PC优化（避免在一开始的时候写入transaction record）可以应用于接收它的范围。

1PC transaction (success)

{Begin(k1), Write(k1), Commit(k1)}   ok

1PC transaction (range split then success)

In the below example, the 1PC attempt fails since the range has split.
在下面的例子中，1PC由于range的分裂而失败

                                       .- range key mismatch
                                       v
{Begin(k1), Write(k1, k2) Commit(k1)} err

当失败后，将会以“常规”方式重新发送请求（k1的intent被解析为Commit的一部分）：

{Begin, Write, Stage}(k1)  ok|Commit(k1)
Write(k2)                 ok |          |Resolve(k2)
                             ^- ack commit to client

Failed write

Non-retryable

写入失败很难处理（一个很好的例子是ConditionFailedError，它违反了唯一性约束）;这种错误需要返回到客户端，让客户处理：

{Write,Stage}(k1)   ok
Write(k2)           err <- returned to client
Write(k3)           ok

客户端选择退出（或者重试）transaction：

Abort(k1) ok|
            |Resolve(k2)
            |Resolve(k3)

客户端必须停止使用当前时期的事务（即它必须重新启动txn），或者新的intent write不会反映在staged transaction recode中，因此也不会反映在 commit condition中。

Retryable

最后一批中的写入可以强制进行事务重试，因此：可以推送它们的时间戳，它们可以捕获WriteTooOldFlag，或者它们引起直接的TransactionRetryError。

Stage(k1)   ok
Write(k2)       retry <- returned to client
Write(k3)    ok

从表面上看，这看起来非常类似于不可重试的情况，但是以DistSender的角色从 commit condition的角度来看，这是不同的，因为事务可能是可中止的：它没有在k2处设置可提交的意图。但是，如后面所述，并发事务只会在事务记录被放弃时才使用它，但情况并非如此。

详细说明

设计细节

txnCommitter

并行提交机制主要由名为txnCommitter的txnInterceptor实现。interceptor位于TxnCoordSender的拦截器堆栈中的txnPipeliner下方。当一个包含committing EndTransaction请求的BatchRequest到达时才会触发并行提交。剩余的其他请求可能是BeginTransaction请求、写入请求、QueryIntent请求或任何其他类型的事务请求。

代码首先检查批处理是否符合并行提交的条件。这意味着批次提交不能包含：

• ranged (write) request。在撰写本文时，唯一的此类请求类型是“DeleteRange”，我们倾向于尝试少用它（＃23258）。很难处理ranged request（几乎不可能）。考虑一个DeleteRange，它写入一个span并放下一个intent（在单个受影响的key上），稍后将会（不相关的）想该range上执行一些写入（在一个先前为空的key上）。状态解析过程需要知道与promised write相关的span是以原子方式写入的，这样一旦发现一个intent写入完成，就可以得出所有intent都已经写入完成的结论。这意味着由promised write组成的ranged request一定不能跨越多个range，若跨越多个range就增加了很多不容易解决的复杂性。
• commit trigger。commit trigger仅由内部事务使用，其中事务记录的租约通常与运行事务的客户端共存（因此以慢速执行的方式只需要对follower进行一次额外的网络开销）。稍后可以添加对此的支持：向STAGED proto添加commit trigger，如果​​设置，则在事务明确提交时不允许更改commit trigger。

如果批次不合格，批次将直接从txnCommitter透传，而不做任何改变。它将和以前一样与COMMITTED状态一起发送。

如果批次符合条件，则会创建EndTransaction请求的副本，状态更改为STAGED，并根据下面的protobuf将batch中的其他请求填充到PromisedWrites字段。

  // promised_writes is only set when the transaction record is in
  // status `STAGED` (part of the parallel commit mechanism) and is
  // the set of key spans with associated sequence numbers at which
  // the transaction's writes from the last batch were directed. This
  // is required to be able to determine the true status of a
  // transaction whose coordinator abandoned it in `STAGED` status.
  // The so-called status resolution process needs to decide whether
  // the promised writes are present. If so, the transaction is
  // `COMMITTED`. Otherwise, it is `ABORTED`.
  //
  // The parallel commit mechanism is only active for batches which
  // contain no range requests or commit trigger.
  repeated message SequencedWrite {
    bytes key = 1;
    int32 seq = 3;
  } promised_writes = 17;

理想情况下，所有请求都成功返回。错误（从routing layer上方）会逐层向上抛，客户端（TxnCoordSender）重新启动（包括刷新），或根据需要中止事务（以避免强制并发事务进入状态解析过程）。

请注意，最终批次中的RPC级错误将变为模糊的提交错误（这发生在RPC层，并且不会受到此处提出的更改的影响）。

写完毕之后，则检查它们是否需要重启事务。如果返回的事务已带有时间戳，或者设置了WriteTooOld标志，则会出现这种情况。如果是这种情况，则transaction retry error是一个综合错误并需要将其发送到TxnCoordSender的interceptor stack。

如果事务可以提交，则txnCommitter将最终事务返回给客户端，并异步发送EndTransactionRequest以完成事务记录（后续完成写意图）。对EndTransactionRequest的预期响应是RPC错误（超时等）和成功。特别是，我们可以断言提交不会被拒绝。

当加入到这个新的interceptor时，我们将txnIntentCollector移动到txnPipeliner下面，所以它们之间的新顺序变为：txnPipeliner - > txnIntentCollector - > txnIntentCollector。要想进行正确的刷新，则需要我们将txnSpanRefresher移到所有这三个拦截器之上。

DistSender

如果其状态不是COMMITTED，则调整DistSender以允许EndTransaction请求与其他请求并行发送。实际上，这永远不会与PENDING或ABORTED状态一起使用，但这意味着具有STAGING状态的EndTransaction请求可以与其批次中的其他请求并行发送。

Replica

txnCommitter在堆栈中太高，无法知道committing的EndTransaction请求是否可以跳过STAGING状态并直接转到COMMITTED状态。当请求中的所有 promised writes与事务记录在同一范围内时，就是这种情况。这种检测可以在DistSender中执行，但这是不可取的，因为它泄漏了太多关于DistSender事务的信息。

相反，Replica使用'STAGING状态了解EndTransaction请求。与Replicas如何检测1-PC 提交批次的方式类似，它可以检查“STAGING”状态EndTransaction`请求，这些请求可以跳过“STAGING”阶段并直接转到“COMMITTING”。请求完成后，它将返回到txn协调器，通知它新的事务状态。

Status Resolution Process

status resolution process 处理DistSender写入STAGED事务记录但未能成功完全写入，留下一个废弃的事务（即最近没有心跳的事务）的情况。

它的目标是：要么中止事务，要么通过尝试阻止事务声明的最终批次的promised writes之一来确定它实际上是已提交的，最终批次存储在STAGED事务记录中。

status resolution process会在两种情况下被触发：（1）当reader或者writer遇到intent时（2）让GC Queue尝试清除旧的transaction records时。

随着STAGED事务状态的引入，即使放弃pushee，推送请求也可能失败，因此当放弃一个处于STAGED状态的transaction record时，txn wait queue（位于在STAGED transaction所在的range的leaseholder上）将会触发status resolution process，需要确保每个transaction record中同一时刻只有一个status resolution process在运行。

PushTxn

PushTxn不能简单地改变STAGED事务的状态。相反，它会逐字返回此类交易。 PushTxnResult的所有消费者都会更新以处理此结果，并且必须调用状态解析机制。

另一种需要考虑的方法是返回错误。但是，这对于批量推送请求不起作用。如果在实现过程中我们决定使用第一个选项，我们也可以考虑在进程中删除TransactionPushError。

QueryIntent(Prevent=true)

该过程的核心是在临时提交时间戳处尝试阻止事务的意图（只有在尚未存在的情况下才可能）。为了有效地实现这一目标，我们引入了一个新的点读请求QueryIntent，它可以选择性地防止将来意向写的丢失。此请求填充时间戳缓存（与任何read一样），并返回在特定的事务的给定key，时间戳以及至少指定的序列号上是否存在intent。我们不检查确切的序列号，因为一个批次可能包含重叠writes，在这种情况下，只关心最新的序列号。如果我们相信PromisedWrites已被完全且正确填充，则检查“大于或等于”等同于（但比计算简单）计算并只保存针对于给定key的序列号的最后一次写入。

该请求还返回是否有超出预期时间戳的事务的意图。如果发生这种情况，事务已重新启动或被推送，并应指示调用者检查事务记录以获取新更新（因为除非事务看起来被放弃，否则不会启动状态解析，这在实践中可能不值得） 。

一种优化措施就是，我们可以在intent被阻止（但仍然更新时间戳缓存）时返回结构化错误，以更快地执行批次中的其余部分。

算法

1. 一直等到事务被放弃（以避免虚假中止） - 这是由公共路径中的txn等待队列完成的。
2. 从STAGED 状态的transaction record中获得 promised writes，记录transaction ID 和commit timestamp.
3. 基于commit timestamp构建一个batch，该batch中包含了针对于每个QueryIntent(Prevent=true) 而构建的一个QueryIntent(Prevent=true)、commit timestamp和 transaction ID。
4. 执行batch，并基于如下结果执行下一步动作：
   1. 若一个intent被阻止，则中止事务。但是需要稍微注意的是：事务有可能会被重启并写入一条新的STAGED记录，该 STAGED记录具备更高的commit timestamp，并且状态现在可能变为了 (implicitly 或 explicitly) committed. 这时中止退出的EndTransaction 可能会失败因为时间戳与recode中的时间戳已经不一样了。
   2. 对于其他的错误，需要根据实际情况进行适时的重试，但是在每次重试之前需要检查transaction record是否有update。
   3. 若找到所有的intents，这执行committing EndTransaction。需要注意实际上若一个transaction已经commit了，也就意味着原始client端（若依然存在）只能执行一个 尝试“COMMIT”事务的 EndTransaction。

重建Transaction record

当status resolution机制碰到快速transaction GC时可能导致在错误状态下重建transaction。有两种快速GC方式（尽管差异在这里并不重要）：（1）提交时intent在同一range内的事务记录会被立即删除，（2）在提交后，当intent resolver解析了external intent时，transaction record将被删除（通过额外的共识写入）。

以隐式提交的transaction为例。当一个status resolution正在运行并且无法阻止任何intent，一个并行writer发现了一个intent并且准备提交transaction。在这之前，status resolution已经执行成功，transaction也被提交，intent也被正确解析，并且有快速GC删除了transaction record。 当执行push的时候，将会重建状态为ABORTED的transaction record。这时的intent已经committed了，但是此时的状态还不确定，因为aborter现在很可能会认为transaction已经因为冲突而退出了。当一个事务有可能会想SQL Client端返回模糊的结果时，该事务会尝试中止自己的transaction record。在上述的竞争状态下，即使事务实际提交，它也可能错误地返回事务中止错误。

为了解决这个竞争问题，只有在TxnCoordSender发送了提交或通过GC队列后才会删除transaction record。

示例

Assume that the transaction promised writes at k1, k2, and k3 and is anchored at k1. t1 is its provisional commit timestamp when the record is discovered.
假设一个事务会针对 k1, k2, 和 k3进行写入并且通过t1确定实际数据位置。对应的时间戳是t1

Missing intent (at k2)

QueryIntent(k1, t1)      found|Abort(k1, t1) ok GC(k1) ok
QueryIntent(k2, t1) prevented |
QueryIntent(k3, t1)  found    |

Missing intent racing with restart

在t1时间戳的intent被阻止，但在事务记录可以中止之前，事务重新启动并管理（隐式）提交。由于中止失败，解析过程会观察带有新活动的事务记录并等待，此后不久就会观察到提交。请注意，在整个过程中，将会一直监控事务是否活着因此在正常情况下，状态解决方案不会首先启动。

QueryIntent(k1, t1)  found  | Write(k1, t2)          ok     |
QueryIntent(k2, t1)prevented|{Write,Stage}(k2, t2) ok|      |Commit(k2) ok GC(k2) ok
QueryIntent(k3, t1)  found  | Write(k3, t2)          |    ok|
                              |Abort(k1, t1)           |fail  |Wait       ok
                                                                 ↑
                                            sees either no txn record or committed
                                            one; either way, not `STAGED` any more

在另一种情况下，中止将导致Stage（k2）失败并且整个事务将被中止。

多个 status resolutions 竞争

状态解析仅写入单个键（事务记录）并且有条件地执行，并且仅在此条件写入之后才解析intent。因此，具有多个状态解析竞争不会导致异常。

在下面的记录中，两个status resolution会相互竞争，其中一个会胜出，另一个QueryIntent看到提交版本（并断定它已阻止写入）。当它尝试更新transaction record时，它会失败并意识到事务现在已提交。

QueryIntent(k1, t1) found Commit(k1, t1) Resolve(k1)ok|
QueryIntent'(k1,t1)                                   |prevented Abort(k1, t1) fail

性能影响

由于新引入的中间事务状态，会产生对WAL的额外写入，因此吞吐量可能会降低，而延迟会降低。从长远来看，我们可能能够在其他Raft流量上捎带上committing“EndTransaction”消息，来解决该问题。请参阅＃22349，其中讨论了intent resolution方案中的类似想法。

No-Op Writes

promised writes集合是需要留下写intent的写入操作。这与剩余的* intent spans 形成对比，后者只是实际意向写的超集*。任何成功的“write”命令都会产生intent。

但是，这是对未来的限制：我们绝不能在transaction的最后一批次中执行no-op writes，必须采取适当的措施来保持这种不变性。如 https://github.com/cockroachdb/cockroach/commit/9d7c35f，我们断言这些No-Op Writes会成功地完成点写入。即使有了这种额外的保护级别，我们也需要记住永远不要像promised write的那样发出no-op write。

Error handling

Client 事务可以在最后一批中发出ConditionalPut，可能会接收到ConditionFailedError，并可能决定尝试不同的write。一旦发送了“STAGED”事务记录，promised writes（对于该生命周期）不得改变。客户端必须在发生任何错误后重新启动或回滚事务（但请注意，客户端有限使用read而不是首先使用基于条件的更新，因为后者性能稍差）。

必须小心谨慎。例如，SQLUPSERT处理可能容易受到此类错误的影响。

提升结果的准确性

从'DistSender`的角度来看，我们可能会看到更多模糊的提交。当发送提交操作（包括隐式提交）但是不知道它是否已被处理时，会发生模糊提交。按照这种设计，由于我们与commit并行提交了更多的写入操作，因此也更容易产生此类错误。我们可以利用“STAGED”状态根据需要对其进行改进。在模糊操作之后，我们运行状态解析过程（跳过transaction record查找;我们可能没有写入我们的staged记录，但我们知道promised write和临时提交的时间戳）。如果我们设法阻止write，我们可能会返回到客户端事务重试的错误。否则，如果有transaction record，我们也可以运行希望获得执行成功的结果的流程。

需要注意的是，我们并不只是尝试中止我们自己的transaction record。record可能已经变为了隐式提交，然后由 status resolution process进行显式提交，最后进行垃圾回收。 （即使记录不被垃圾回收，也有可能发生 status resolution process已经证明记录已经提交，但随后会发现它已被中止的情况，这种模棱两可的情况，我们应该极力避免）。

Metrics

将针对状态解析尝试次数以及符合条件/不符合并行提交条件的最终批次数添加度量标准。如果最后一个指标是实质性的，我们需要解除一些关于可受理性的条件。

反观#26599 isuue (transactional write pipelining)

在＃26599 issue之后，当事务尝试提交时，可能存在来自早期批次的未完成的正在执行的RPC。 client.Txn不会等待这些正在执行的rpc的完成，而是将promise write与最后一批次（一起发送，在最后一批次中DistSender将包含在staged transaction record中，并以QueryIntent的形式返回结果（QueryIntent将被作为write对待，也就是说，它们可能最终成为Raft no-ops或者是与另一个请求组成一个对另一个range的batch批量处理 - 这是可以的，但需要进行测试）。这样会产生一些可能的其他结果：

• 一般情况下，不会阻止任何intents（并且它们带有正确的时间戳），因为这些intents已经被赋予过时间戳了; QueryIntent成功了，批次的其余部分也成功了，'DistSender也会向client端反馈成功的结果。
• 阻止intent或者发现intent上带有错误的时间戳。这分别被视为write失败或已推送事务。

需要特别注意批次拆分，该批次拆分中包含了QueryIntent发出的EndTransaction（status = STAGING）'请求，该请求以pipeline的方式将所有的write写入到与transaction record相同的range中。以便将流水线写入写入与txn记录相同的范围。否则，EndTransaction请求将会与其他批次一起被被spanlatch.Manager`阻塞，因此client端将会发现Transaction block住，并不会再有任何变化。实际上，[副本级别检测]（https://github.com/cockroachdb/cockroach/blob/master/docs/RFCS/20180324_parallel_commit.md#replica），与本案例的行为几乎完全相同。
我们可以将同一个range上的多个batch并行执行。

缺点

• 实现特别复杂;尤其是如何在 DistSender 和 EndTransaction之间就事务是否已经提交达成一致意见。当发送意外commits/aborts或客户端不适当地retry时，系统就更容易变得不稳定从而导致事务异常。
• 会增加额外的WAL写入。

替代方案

这种复杂的设计似乎没有可行的替代方案。不这样做就会导致延迟变为现在的两倍。

替代方案

这个实现方式有一个扩展方案，允许intent与commit并行执行（而不是在commit之后）。此替代方案目前还没有完全验证是可行的，因为它需要将transaction ID嵌入到所有已提交的version中（这是状态是并行执行过程所必须的）。这样做需要大量的工作，但此替代方案中的细节很少有变化。

未解决的问题

目前还没有发现其他的基本问题。

参考

https://github.com/cockroachdb/cockroach/blob/master/docs/RFCS/20180324_parallel_commit.md