Intro
现代数据库通过副本复制和分区来实现系统的高可用和扩展性．然而，大多数实现需要使用两阶段提交(2PC)解决由并发控制中的不确定性事件(如系统故障和竞争条件)引起的问题．这会增加分布式事务的延迟并降低系统的可用性和扩张性(由于协调节点宕机等原因)．
确定性并发控制算法(Deterministic concurrency control algorithms)提供了一种构建分布式和高可用性数据库系统的新方法。它们通过确保不同的副本总是独立地产生相同的结果，避免使用昂贵的提交和复制协议，只要给定相同的输入事务。因此，确定性数据库不需要复制和同步分布式事务的更新，而只需跨不同副本复制输入事务，这可以异步完成，而且通常需要更少的通信．
本文的主要贡献如下:提出了一种快速实用的确定性OLTP数据库Aria。它支持确定性事务执行，而不需要预先了解输入事务。引入了一个确定性的重排序方案来减少Aria提交阶段的冲突。我们将描述Aria的实现，并报告对两个流行基准的详细评估。总的来说，Aria在单个节点上的性能远远超过最先进的确定性数据库，在由8个节点组成的集群上的性能最高可达两倍。
Background
Replication in Nondeterministic Databases
高可用性系统通常跨多台机器复制数据，这样当一台或多台服务器发生故障时，系统仍然提供某种程度的可用性。现有的复制策略大致分为两类:(1)异步复制和(2)同步复制。在异步复制中，数据在副本之间异步传播，这意味着可以在写入到达所有副本之前提交事务。异步复制减少了提交事务的延迟，但在发生故障时可能会损失数据.相反，在同步复制中，写操作在事务提交之前跨所有副本传播。同步复制增加了延迟，但确保了副本之间的强一致性，这已经成为研究社区最近关注的焦点.
大多数事务系统都提供可串行性，这要求事务产生遵循某种串行顺序的结果。大多数并发控制算法(例如乐观并发控制和严格两阶段锁定是不确定的，这意味着当给定相同的输入时，不同的副本可能会产生不一致(diverge)，这是因为在并行执行事务的副本上的时间和性能差异。因此，需要注意保证副本之间的一致性;大多数复制协议要么采用主备份方案[7]，要么采用状态机副本.在主备份系统中，主备份系统运行事务并将结果发送给一个或多个备份。备份将对数据库应用更改，并定期确认对主数据库的写操作。事务可以在备份确认写操作之后提交。在使用状态机复制的系统中，事务可以运行在任何副本上，但是读/写操作需要使用共识协议(例如Paxos或Raft)进行排序。因此，非确定性系统能够保持一致，但会受到一些限制，包括需要多轮同步通信来提交事务，以及需要同步通常较大的输出值而不是较小的输入操作。
Deterministic Concurrency Control
为了解决这些问题，提出了确定性并发控制算法。在确定性数据库中，每个副本都确定性地运行相同的有序事务集，并将数据库从相同的初始状态转换为相同的最终状态。通常，在这些系统中，事务在执行之前首先要经过一个排序层。这个排序层充当客户端和数据库之间的中间层，决定客户端提交的事务的总顺序。通常，排序层在多台机器上运行，以避免出现单点故障，并通过构建在Paxos或Raft实例之上的复制日志达成共识。为了避免非确定性(例如，由于系统调用获取当前时间或生成随机数)，排序层对传入事务进行预处理，在传递给副本之前用常量值替换此类函数调用，以消除这种非确定性。因此，副本之间不需要相互通信以保持一致，从而使复制更加简单和高效。此外，确定性数据库还通过避免两阶段提交减少了分布式事务的开销．在非确定性数据库中，2PC用于确保分布式事务的参与者达到单个提交/中止决策。相反，在确定性数据库中，一个参与节点的故障不会影响提交/中止决策．
最近，基于依赖图或有序锁的确定性协议被提出，以提供更多的并行性，同时确保确定性。尽管上面的系统在构建确定性数据库方面迈出了重要的一步，但它们仍然有一个限制，使它们不切实际:依赖分析要求事务的读/写集(即主键集合)必须在执行之前已知。对于具有二级索引查找或其他数据依赖关系的事务，可能无法提前确定读/写。在这种情况下，事务必须运行数据库以确定其读/写集。然后事务中止并使用这些预计算的读/写集重新执行。但是，如果读/写中的任何键在重新执行期间发生变化，事务可能会被执行多次。
System Overview
与现有的确定性数据库一样，Aria中的副本不需要彼此通信，也不需要独立地运行事务。这是因为在确定性执行下总是会产生相同的结果。每个事务通过一个排序层，并被分配一个惟一的事务ID (TID)。TID指示事务之间的总排序;默认情况下，它指示事务的提交顺序．Aria在两个不同的阶段分批运行事务:一个执行阶段和一个提交阶段，由barrier分隔。在一个批处理中，每个Aria副本使用多个工作线程以并行和任意顺序运行事务。事务以循环的方式分配给工作线程．Aria采用单版本方法，即它为事务缓冲写操作，直到批处理结束。一旦批处理中的所有事务在副本上完成执行，它就进入提交阶段。副本上的提交阶段也在多个工作线程上运行，每个工作线程独立执行。在提交阶段，线程会中止执行与早期事务(即那些具有较小tid的事务)相冲突的操作的事务。例如，如果一个事务读取了由某个早期事务修改的记录，那么它将中止。除非事务被显式地中止(例如，因为违反某些完整性约束)，中止的事务将在下一批执行的开始自动调度。如果一个事务与以前的事务没有冲突，系统将其更改应用到数据库。
除了在输入事务排序之后解决冲突之外，Aria还使用了确定性的重新排序技术，该技术可以减少提交阶段的冲突。例如，考虑一个n个事务的序列，其中Ti读取记录i并更新记录i + 1，对于0 < in。因此，每个事务(除了T1)读取一个已经被前一个事务修改的记录。按照Aria中的默认算法，第一个事务是唯一可以提交的事务。然而，这些冲突事务仍然可以在串行顺序Tn Tn 1···T1下提交。使用确定性重新排序，Aria不会在物理上重新排序输入事务。相反，它提交更多事务，这样结果仍然是可序列化的，但相当于不同的顺序。
Deterministic Batch Execution
The Execution Phase
在此阶段，每个事务从数据库的当前快照中读取数据，执行其逻辑，并将结果写入本地写集。由于事务所做的更改保存在本地，不直接提交给数据库，因此每个事务在执行阶段读取的快照总是相同的。一旦事务完成执行，它将通过它的本地写集，并为它的写集中的每个条目进行write reservations．只有当reserving transaction具有比之前的reserver较小的TID时，才可以对先前保留的值进行write reservation．如果来自较大TID的reservation已经存在，那么旧的reservation将被取消，而使用较小TID的新reservation将被执行。如果事务不能进行reservation，则事务必须中止。此外，作为性能优化，事务还可以跳过提交阶段，因为它知道至少有一个reservation没有成功。
The Commit Phase
Aria将并发控制与事务执行分离开来。在提交阶段，每个事务都根据执行阶段所做的write reservation确定是提交还是中止。与在非确定性数据库中不同，Aria不需要两阶段提交来提交分布式事务.原因有两个:(1)在执行阶段所做的写保留不会影响数据库中每条记录的值，即不需要回滚;(2)即使发生失败，事务总是可以提交(即，通过对数据库应用写操作)，因为决定论保证在重新执行之后总是会产生相同的结果．Aria用来确定事务是否可以提交的三种依赖类型:(1) write-after-write (WAW)(2)write-afterread(WAR)(3)read-after-write(RAW)，通过检查一个事务Ti是否与早期的任何事务Tj (j < i)有特定类型的依赖关系来决定它是否可以提交.注意，通过中止具有waw依赖项或raw依赖项的事务，Aria确保提交事务的串行顺序与输入顺序相同。
Rule 1. A transaction commits if it has no WAW-dependencies or RAW-dependencies on any earlier transaction.
Aria不必检查所有早期的事务来检查waw依赖项和raw依赖项。相反，它使用事务的读集和写集来探测write reservation 表。注意，有些事务可能已经在执行阶段中止，可以简单地跳过提交阶段，例如，对某些写失败的reservation。当事务的读集和写集中的键都不存在于写 reservation 表中时，function HasConflicts返回false。当不存在依赖项时，事务提交和所有写操作都应用到数据库。
与在执行阶段一样，检查依赖项的过程可以对每个事务以任意顺序并行完成。除非事务被显式地中止(例如，违反某些完整性约束)，中止的事务将在下一批执行的开始自动调度。中止事务的相对顺序保持不变。因此，每个事务最终都可以提交，因为批处理中的第一个事务总是提交，而中止的事务的位置总是跨批向前移动。
Determinism and Serializability
Theorem 1. Aria following Rule 1 enforces determinism and serializability.
确定性:在执行阶段，系统构建一个给定一批事务的write reservation表。reservation表是键-值对的集合。键x是被某个事务修改的记录，而值T是用最小TID修改记录x的事务。在提交阶段，reservation表不会更改，系统使用它来检测事务之间的依赖关系。事务是否提交仅取决于它的读/写集和reservation表，而不管事务在提交阶段以什么顺序运行。由于每个副本在相同的数据库快照上运行相同的事务批次，不同的副本将产生相同的读/写集和reservation表。
Limitations
在Aria中，前一批事务必须在开始新批处理之前完成执行，因为批处理之间存在barrier。由于事务之间的工作负载不平衡，系统可能会有不理想的性能。
deterministic reordering
The Reordering Algorithm
Rule 2. A transaction commits if two conditions are met:
(1) it has no WAW-dependencies on any earlier transaction,
and (2) it does not have both WAR-dependencies and RAWdependencies on earlier transactions with smaller TIDs
由于此算法允许具有raw依赖关系的事务提交，只要它们没有war依赖关系，它可能导致不同于输入顺序的串行顺序。waw和raw依赖关系是使用write reservation表检测的。为了支持war依赖关系检测，系统还需要在执行阶段做出read reservation。使用read reservation表，对于数据库中的每条记录，系统都知道是哪个事务首先读取它，即具有最小TID的事务。在提交阶段，如果一个事务的写集中有任何键出现在read reservation表中，并且读来自不同的事务，那么war依赖关系将被检测到.
Theorem 2. Aria following Rule 2 enforces determinism and serializability.
The FallBack Strategy
因为Aria不需要预先确定读/写设置，并且可以在副本中的多个线程上并行运行，所以当批处理中的事务之间存在少量原始依赖关系和waw依赖关系时，它提供了比现有确定性数据库更好的性能。确定性重排序机制可以将原始依赖关系转换为war依赖关系，允许许多冲突事务在可串行性下提交．
Aria在由于waw依赖而导致工作负载中断率高时采用的一种回退策略，关键思想是，在提交阶段的末尾添加一个新的回退阶段，并根据冲突事务之间的依赖关系重新运行中止的事务.每个事务在执行阶段从数据库的当前快照中读取数据，然后决定是否可以在提交阶段提交。这里需要注意的是，当提交阶段结束时，每个事务都知道其完整的读/写集。每个事务的读/写集可用于分析冲突事务之间的依赖关系。因此，许多冲突事务不需要在下批处理中重新调度。相反，Aria可以使用与现有确定性数据库中相同的机制来重新运行那些冲突事务。用一种类似Calvin的方法，它自然支持分布式事务，尽管任何确定性并发控制都是潜在可行的。在回退阶段，一些工作线程作为锁管理器，按照TID顺序向每个事务授予读/写锁。事务被分配给一个可用的工作线程，并在它获得所有锁后对当前数据库执行(即，对具有较小TIDs的事务所做的更改)。事务提交后，它释放所有锁。只要事务的读/写集没有改变，事务就仍然可以确定地提交。否则，它将在下一次批处理中以确定的方式被调度和执行。
Calvin最初的设计只使用一个线程按照预先确定的顺序授予锁。然而，在现代的多核节点上，这个单线程锁管理器不能使所有可用的worker[44]都饱和。为了更好地利用更多的CPU资源，使用多个锁管理器线程来授予锁。每个锁管理器负责数据库的不同部分。我们的新设计在逻辑上等同于但比原始设计更有效，后者在单个节点上运行多个Calvin实例。这是因为工作线程现在通过共享内存相互通信，而不是通过套接字。注意，回退策略保证在最坏的情况下，Aria至少与现有的确定性数据库一样有效，因为非冲突事务只运行一次。然而，现有的确定性数据库至少运行输入事务两次:一次用于确定读/写集，一次用于执行查询。
Implemention
Data Structures
Aria是一个分布式确定性OLTP数据库。它提供了一个关系模型，其中每个表都有一个预定义的模式，具有类型化和命名的属性。客户端通过调用带有不同参数的预编译存储过程与系统进行交互，就像许多流行的系统。存储过程是用c++实现的，其中支持任意逻辑(例如，读/写操作)。系统的目标是一次性的短期事务，不支持多轮和交互式事务。它不提供SQL接口。
每个表都有一个主键和一些属性。表目前实现为主哈希表，零个或多个辅助哈希表作为索引，这意味着不支持范围查询。这很容易适应树结构[6,36,57]。通过探测主哈希表来访问记录。对于次查找，需要两个探测，一个在次哈希表中查找记录的主键，然后在主哈希表中查找。
事务在执行阶段对读写进行reservations，用于提交阶段的冲突检测。本质上，这些reservations是键-值对的集合。键是事务访问的表的主键，值是事务的TID。
Distributed Transactions
Aria通过分区支持分布式事务。每个表在所有节点上进行水平分区，每个分区随机散列到一个节点。注意，排序层允许将事务发送到任何节点执行。但是，如果一个事务被发送到它访问的数据最多的节点，网络通信可能会减少。在实际场景中，事务访问的分区在某些情况下可以从存储过程的参数推断出来(例如，TPC-C上的新订单事务)。否则，事务可以发送到任意节点执行．
如前所述，执行阶段和提交阶段用barriers分开。在分布式设置中，这些barriers是通过网络往返旅行实现的。例如，指定的coordinator(从所有节点中选择)决定，一旦所有节点完成执行阶段，系统就可以进入提交阶段。
在执行阶段，当事务读取本地节点上不存在的记录时，将发送远程读请求。类似地，读/写reservation请求也被发送到相应的节点。在提交阶段，还需要网络通信来检测事务之间的冲突。注意，同一节点内的工作线程不通过交换消息进行通信。相反，所有操作都直接在主存中进行。Aria对这些请求进行批处理，以减少延迟并提高网络性能。事务一旦提交，写入请求也会被执行
Fault Tolerance
在确定性数据库中，容错性得到了显著的简化。这是因为不需要维护物理的undo/redo日志记录，相反，系统只需要使输入事务在排序层中持久。此外，副本之间不进行通信，这意味着副本之间不存在全局barriers.
每个事务首先进入排序层，在排序层中分配一个批ID和一个事务ID。接下来排序层将相同的输入事务转发给所有副本。在执行阶段开始之前，副本中的每个节点将接收一批事务的不同部分。一旦所有事务完成执行，副本将再次与排序层通信，通知它每个事务的结果。如果事务由于冲突而中止，排序层将把事务放到下一个批处理中。提交事务的结果可以在提交阶段一提交就发布给客户端。这是因为它的输入在执行之前是持久的。一旦发生故障，由于确定性执行的本质，每个事务都将再次运行并以相同的顺序提交。
要限制恢复时间，可以将系统配置为定期对数据库进行磁盘检查点。在检查点期间，副本会停止处理事务，并将数据库的一致快照保存到磁盘。只要有多个副本，客户端就不会意识到检查点发生时的暂停，因为每个副本都可以独立检查点，事务总是由系统通过其他可用副本运行。在恢复时，副本将从磁盘加载最新的检查点到数据库，并replays自检查点以来的所有事务。
网友评论