中文 算法设计
Domino（Decrease cOnflict, assist comMIt, NO rollback）是构建在HBase上的分布式事务引擎，支持完整的ACID事务特性。在架构上，Domino与HBase完全松耦合，使用HBase Coprocessor作为运行时框架，因此可以与任何升级后的HBase版本兼容。事务系统的核心为并发控制，Domino的并发控制机制称之为Stateless and Statefull update Concurrency Control（SSCC）. SSCC具备三大特征：降低冲突Decrease cOnflict（支持高并发）、辅助提交assist comMIt（提高吞吐率）、无需回滚No rollback（减少IO）。Domino的开源协议为Apache License。
Domino的关键算法是其并发控制机制，称之为Stateless and Stateful update Concurrency Control（SSCC，旧名为SUCC）。SSCC的核心思想是把写入（更新）操作分为两类：“有状态更新stateful update”和“无状态更新stateless update”。“有状态更新”是指写入（更新）的数据内容是基于当前已有数据的值，如w(x)=x+1;“无状态更新”是指写入（更新）的数据和当前数据无关，即“纯”写入。
无状态更新操作在最近兴起的大数据环境中广泛存在，特别是在web应用方面，其以文本和二进制数据为主，不涉及基于当前数值的更新操作。例如，搜索引擎的索引更新，一篇文档的更新涉及到原始数据和倒排链的多处改动，无论原始数据表还是索引数据表，其旧数据被直接覆盖或自动删除，和数据当前的值（内容）无关，正因为如此，Google提出了事务引擎Percolator来处理索引更新；再如，一些数据管理系统使用二级索引表进行数据查询，其对二级索引表的维护大部分为无状态更新操作。另外，一些互联网应用中，旧的文本数据往往被新的文本数据直接覆盖，例如微博系统中最热门的消息或最新消息都是直接被新来的数据覆盖掉。
实际上，blind-write (write-only)事务类型在20年前就被讨论过。这种事务类型包含的操作和数据对象的状态无关，而是直接对数据进行改动（Such transactions consist of operations that do not observe the states of the objects instead they “blindly” modify the object states.），所对应的写入操作被称之为blind-write操作：A blind write is when a transaction writes to an object without ever reading the object。Write-only事务包含的操作全部是blind-write。在大数据环境下，这种操作显得比以前更加频繁和重要。我们定义的无状态更新操作和blind-write是一致的，只不过我们讨论的事务可以任意包含各种操作，而不仅限于write-only事务。
Domino在架构上由两部分组成：底层的数据模型与上层的并发控制机制。在特点上可以归纳为如下三点：
-
3M数据模型（Multi-dimension Multi-version Map）。该数据模型的设计支持无锁并发写入，且冲突无需回滚。
-
一阶段提交（One Phase Commit）。不同于传统的分布式事务的2PC，Domino无需Coordinator，无需参与节点vote，其整个读取过程和单机版事务机制一样。
-
基于状态的并发更新。Domino的并发控制把写入分为有状态和无状态两种，无状态写入实现了完全无锁的并发控制，出错后自动辅助完成提交。对应的事务隔离级称之为SUI，可以屏蔽P0/P1/P2/P3/P4/A5A异常。
Domino的数据模型是一张多维有序表，该表由多个对象组成，表的各维度包括表（Table），对象主键（ObjectKey），对象属性（Column），时间戳（Timestamp），时间戳对应的对象值（Value）。可表示为:
<Table,<ObjectKey,<Column,<Timestamp, Value>>>>
除上述表示外，也可直观的表示为类似RDBMS的一张表，如下表所示。
数据模型存储的对象的值可以有多个版本，不同版本用其时间戳区分。对象x的版本a表示为x[a]。因为数据模型是一个“有序”表，除了时间戳维度外，其他维度均以键值按照字典升序。时间戳维度则按照降序排列，因此系统默认把最新的数据返回给客户端。一个事务需要获得两个事务号：起始事务号i和提交事务号c，根据起始事务号i，事务被标记为Ti。起始事务号在事务初始化时获得，早于任何一个读写操作；提交事务号在事务提交时获得，晚于任何一个读写操作。事务号的产生是严格按照时间顺序递增的。事务Ti对数据对象x的a版本读操作表示为ri(x[a])，写操作表示为wi(x[a])。
每个数据对象x包含两个内置属性（Build-in Column）：x.status和x.version，这两列属性被载入到内存中，以便提高读写性能。
- x.status存储对象的事务状态，其值为stateless、stateful或NULL。若x.status[i]被赋值为stateless，表示事务Ti对x进行了无状态更新；若为stateful，表示事务Ti对x进行了有状态更新；若为NULL表示当前没有任何一个活动的事务更新了x；
- x.version存储对象的可用版本。所有事务的读操作是根据x.version中存储的版本进行读取的。x.version的值是某事务的起始事务号（因为事务是由起始事务号标记的），其自身时间戳是该事务的提交事务号。如x.version[c]=i，表示事务Ti对x进行了更新并在c时刻成功提交，x[i]成为已提交数据。新来的事务可以由x.version[c]定位到x[i]，从而获取到相应数据。
上图给出了Domino数据模型的运行时快照，事务Ti1、Ti2、Ti3都对数据项row1进行写入，起始事务号分别为i1、i2、i3，时间顺序上i1<i2<i3，即事务Ti1最早开始、其次是Ti2，最晚开始的是事务Ti3。在该图的例子中，T2已经成功提交，数据项的写入状态已经被清除，即row1.status[i2]=null（本例中，我们以行键row1代表数据对象的标识），数据的提交事务号为c2，指向的可用数据版本为i2，即row1.version[c2]=i2。T1和T3还没有成功提交即row1.status[i1]和row1.status[i3]为null，数据项状态均为stateless。
Domino的数据模型使用分布式存储引擎进行存储，并要求存储引擎提供单行事务的读写功能。分布式存储引擎的设计不在本文讨论范围内，在Domino的系统实现中使用HBase作为数据模型的存储引擎。HBase的时间戳维度和单行事务读写功能可以很好的满足Domino的要求。
事务的状态对应以下三类中的一类：活动的（ACTIVE）、已提交（COMMITTED）、已放弃（ABORTED）。事务的状态连同其他基本信息存储在元信息表MetaTable中（如下图所示），其他信息包括提交事务号和故障检测字段。为了避免局部过热，我们并不直接使用事务号作为该表的行键，而是使用哈希和事务号结合的生成方式生成行键K：
K=(t%HASH)<<64+t;
其中，t为64位的起始事务号，HASH为常量。为了保证K的分散程度，我们将HASH值选为65536（该值仅为经验值），长度为2字节。因此通过上述运算，行键K的最终长度为10字节。
由于该表存储的数据量较少（行数为正在进行的事务数，列数仅有4个），我们把该表的列放入到内存中以便提升效率，分布式存储引擎对该表提供持久性保证。
不同于传统的两阶段提交，SSCC为一阶段提交，其不需要协调者以及参与者投票。具体而言，一个事务初始化后获得起始事务号i，该事务被标记为Ti，在MetaTable中Ti的状态被置为ACTIVE。在进行任何读写操作之前，算法都会检查要操作的数据对应的情况，以帮助执行失败的事务进行恢复，该过程我们在下文的“故障检测与恢复”章节阐述。接下来要进行读写操作，我们把Ti的写操作分为两类，一类为有状态更新，表示为φ(x)，另一类为无状态更新,表示为θ(x)。下图中我们给出了写入（更新）操作的伪代码。对于有状态更新首先检查对象x的状态，如果发现任一版本的状态不为NULL，说明当前存在其他事务正在更新x，则认为检测到冲突事务并回滚（line 38）；其次检查x的版本信息，如果发现某一版本号大于i，说明比Ti更新的事务已经提交，则认为发生冲突执回滚（line 913）。如果上述情况均未出现则对x进行写入，并把x相应的状态置为stateful（line 14）。对于无状态更新，只有一种情况需要回滚，即存在有状态更新对x进行操作（line 15~20），如果没有则进行数据写入，并把x相应状态置为stateless（line 21）。
对于读操作，先检查是否是本事务刚写过的数据，即检查x.status为stateful或stateless的版本中是否包含本事务号（起始事务号），如果是则以该值为读取结果；否则读取小于本事务的最新数据。
完成上述写入读取操作后，事务进行提交程序。提交过程的主要工作是获得提交事务号，把该提交事务号填入到元信息表Meta中，并在元信息表Meta中把事务状态置为COMMITED(下图伪代码的line112)。虽然Domino提供显式的回滚操作，但其内部的执行过程并不涉及数据的删除与迁移，仅是在元信息表Meta中对事务状态进行ABORTED的标记，同时清除操作对象的状态信息以免对其他写入操作造成影响（下图伪代码中line1520）。这样的设计极大的减少了IO操作对性能的影响。
事务发生意外终止导致失败可以分为两类，一类是已经进入提交或回滚程序，但是发生意外终止；另一类还没有进入提交程序，在读写过程中发生了意外终止，本节对着两种情况进行阐述。
这种机制是针对已经进入提交或回滚的事务意外终止的情况。上文提到，在进行任何读写的开始阶段，算法都会检查要操作的数据对应的状态，以帮助执行失败的事务进行提交或回滚。具体而言，对于要操作的对象x，读取x.status中的所有不为NULL的版本，即当前正在对x进行操作的事务号。根据这些事务号，对每个事务检查其在元数据表Meta中的状态，如果为ACTIVE说明该事务正在进行中，不必帮助其提交或回滚；如果为ABORTED，则帮助其完成回滚，即清除其在x.status中的状态；如果为COMMITED，则帮助其完成提交，即在x.version中填入相应的数据版本，同时清除其在x.status中的信息。通过上述操作，我们可以对提交失败或回滚失败事务进行辅助完成。
这里有人会提出疑问，在每个读写操作时都要进行上述检测和恢复，是否会对效率产生影响。在“数据模型”设计中，我们已经提到，元数据表Meta和数据对象的status、version属性都被放置在内存中，上述检测是恢复操作不涉及到任何IO，因此在效率上基本没有影响。
辅助提交与回滚可以处理提交或回滚失败的事务，如果在读写阶段事务发生意外终止，那么它对数据做的更改会被遗留在系统中，包括数据对象本身和对象的status信息，以及处于ACTIVE状态的事务元信息。根据事务处理过程，这些脏数据会被读操作忽略掉，但是遗留下来的.status信息将对写操作产生较大影响，任何尝试更新该对象的写操作都有可能检测到冲突而出发回滚。若不对.status进行处理，该对象将会成为永久不可更新。
为了避免该情况的发生，Domino为事务加入了超时机制，即每个事务都需要在其生命周期内定期更新自己的活动时间戳存储在元信息表Meta的Last_touched中。当一个Domino客户端由于意外中止后，Last-touched列将不再被定期刷新，事务元信息管理模块会因为Last-touched中存储的时间戳过期而把该事务标记为ABORTED，并告知读写这个数据项的事务。当下一个读写操作遭遇.status数据后，会尝试读取这个异常中断的事务元信息，此时因为该事务标记为ABORTED，进而.status信息将被清理掉，脏数据也会被清除。
系统实现详见：https://github.com/domino-succ/domino/wiki/%E4%B8%AD%E6%96%87-%E7%B3%BB%E7%BB%9F%E5%AE%9E%E7%8E%B0
SSCC对应的隔离级称之为状态更新隔离级State Update Isolation (SUI)。SUI是与SI平级的隔离级，能够屏蔽P0,P1,P2,P3,P4,P4B,A5A，无法屏蔽A5B。相比之下，SI无法屏蔽P4B和A5B。和SI类似，SUI为较高级别的隔离级，适用于对A5B不敏感的应用类型，能够适用于大多数应用场景。特别适用于无状态更新较多的应用，例如网页内容更新，文本数据处理等场景。