摘要：本文简述了一种在No-SQL数据库中实现ACID事务性的方法，这种方法只需要底层No-SQL DB实现MGET和MUPDATE两个原语就可以保证完整的ACID事务性，在API层，则将复杂的事务性的读写操作归纳为WALK和MUPDATE两个原语，方便使用。
题图是Redis的ASCII Logo，Redis服务器在启动的时候，会把这个Logo连带着一些运行信息打印到服务的日志里。因为这个功能，一名愤怒的用户在Github上提了一个issue，强烈要求取消这个功能，因为在他的syslog转义了换行符，然后这条日志就变成了这个样子：
Aug 14 09:40:07 ww3-ukc redis[1898]: . #12 .-`_ ''-._ #12 .-. . ''-._ Redis 2.8.9 (00000000/0) 64 bit#012 .-.-.\/ _.,_ ''-._ #012 ( ' , .- | , ) Running in stand alone mode#012 |-._-...- _...-.-.|'_.-'| Port: 6379#012 |-. . / .-' | PID: 1898#012-. -._-./ .-' _.-' #12 |-.-._-..-' .-'.-'| #12 | -._-._ .-'.-' | http://redis.io #12 -._-._-..-'.-' _.-' #12 |-.-._-..-' .-'.-'| #12 | -._-._ .-'.-' | #12 -._-._-..-'.-' _.-' #12 -. -.__.-' _.-' #012-._ .-' #12 -._.-' #12
在跟开发激烈争吵之后，作者认为这个Logo是Redis文化的一部分，但是用户的需求也的确存在，于是很小心的改了好几行代码，只在确实必要的时候把启动信息改成纯文字的格式。相关的链接：
Please... no childish ASCII art in the syslogs ! · Issue #1935 · antirez/redis · GitHub
当然这跟我们这篇文章的主题没有任何关系，只是在接下来的部分提到No-SQL的时候，我会用Redis做一个例子。Redis是一个优秀的KV数据库，最新的版本里已经开始支持集群化，最重要的是足够简单，单线程（所以原子性极其理想）。在需要集群化的情况下，我们有另一个优秀的开源软件ZooKeeper可以替代，别担心，我们只需要使用它功能的一个非常小的子集。
首先我们来做一些合理的假设，一般来说我们在No-SQL数据库中存储的数据有以下的特点：
每个存储的值都有一个唯一的键（Key），这个Key在这个值的生命周期中不能发生变化。Key是一个字符串。
值是个序列化的对象（比如采用JSON），序列化后的大小不太大，一般为KB量级，也就是说，将整个对象读出再重新写会并不会带来很大的性能瓶颈
值的对象中可能包含：独立的数值；和其他对象相关联的数值；其他对象的Key（外键）
Redis支持一些复杂的数据类型来做专门的用途，另外一些更“高级”的比如Mongodb支持复杂的对象格式，但这些我们并不关心，由于我们总是假设存储的对象可以很容易的序列化/反序列化，我们永远假设这些值在No-SQL数据库内部表示为一个字符串，我们在读取时反序列化得到对象，写入时重新序列化变成字符串。
关系型数据库的事务性被总结为ACID四点，分别是：
A - Atomicity 原子性：事务要么全执行，要么全不执行（失败），不能出现执行一半的情况
C - Consistency 连续性：从事务执行前到事务执行后，数据库的状态的改变始终满足预先设定的约束性条件，也就是说，如果有多个状态是处于某种相互匹配的状态的，他们在事务执行的过程中将始终处于这种相互匹配的状态
I - Isolation 隔离性：不同事务是串行执行的，或者看上去是串行执行的，一个事务执行的过程不会影响到另一个事务，不会出现一个事务执行的途中读到了另一个事务的中间状态
D - Durability 持久化：一旦事务执行完成，结果就会被持久化到永久存储，这样即使出现掉电等情况，也不会发生已经完成的事务被回退的情况
一般来说普通的KVDB例如Redis是无法在任意的复杂逻辑下同时保证ACID全部四条的，但实际使用中，我们经常会发现一个不稳定的DB代表着业务出现各种不可预知的异常的风险，事实上事务性对于一个稳健的系统来说是很重要的。但是放弃No-SQL选用关系型数据库，我们放弃的不仅仅是性能，还包括：非结构化数据的使用，海量数据的支持，等等。这四条中，D一般可以通过各种手段保证，比如说Redis支持使用AOF文件来保证数据几乎不会丢失，所以重点在于前三条。
对于我们在No-SQL数据库中的一个事务来说，首先一定是涉及到多个Key的读写的，单个Key的读写一般很容易实现事务性。那么最基础的，对底层No-SQL DB来说，我们至少要有一致性地读取多个Key的能力，这就是第一个原语MGET：
MGET(key1, key2, key3, ...)
要求同时获取key1，key2，key3，...的值，保证在获取这些值的过程中这些值本身不会被其他命令修改，从而满足C连续性的要求。
显然这直接对应Redis的MGET命令，在Redis中很容易得到满足。对于没有这种底层能力的DB来说，可以用一个分布式的锁系统来实现，这个锁系统简单到只需要支持Lock和Unlock两个操作：
Lock key，给一个key加锁，如果已经锁住则等待锁释放
Unlock key，释放key上的锁，使其他Lock key过程可以进入
稍复杂一些则可以引入读写锁(R/W Lock），提高并发读的性能。当使用MGET过程的时候，将所有的Key按字典顺序排序，按字典序从小到大的顺序对Key进行加锁，读取完成后，按照相反的顺序解锁。可以证明由于字典顺序的保证，任意同时操作Key1和Key2的事务，对Key1和Key2（Key1 < Key2）的加锁顺序都是先加Key1，再加Key2，这样可以保证不会产生死锁。当然像Redis这样无需锁来保证一致性的系统就更好了。
对于写的情况略有些复杂，首先由于C一致性的要求，我们至少要支持MGET相反的MSET操作，才能保证任何时候读取到的数据都是一致的。但仅仅是MSET仍然是不够的，我们还需要保证I隔离性，也就是说我们在读取到数据并将数据写回的过程中，刚刚读取的数据不可以发生变化。我们把这个过程抽象为一个原语MUPDATE：
MUPDATE(updater, key1, key2, ...)
其中updater是一个自定义函数，它的格式为：
def updater(keys, values, timestamp):
...
return (write_keys, write_values)其中keys是传入的key1, key2, ...的列表，values是取回的key1,key2,...对应的值的列表，timestamp是取回时服务器的时间，这个参数在某些复杂的情况下可能会有用，比如说，我们经常会给新创建的对象打上时间戳，来区分新对象和之前删除了的某个对象。返回值write_keys是要写回到No-SQL数据库的Key的列表，write_values是相应的值。特别的，如果updater在执行过程中抛出了异常，整个MUPDATE过程会被中止。
这个过程可以用Redis的WATCH/MULTI/EXEC结构来实现：
while True:
WATCH key1, key2, ...
MGET key1, key2, ...
TIME
try:
updater(keys, values, timestamp)
except:
UNWATCH
raise
else:
MULTI
MSET wkey1, wvalue1, wkey2, wvalue2, ...
try:
EXEC
except RedisError: # Watch keys changed
continue
else:
break首先WATCH，然后用MGET获取keys，这些值可以保证C一致性；获取到的值变成本地的副本，交给updater，在updater中保证了I隔离性；当写回Redis时，WATCH设置了乐观锁，如果keys全部没有被修改过，MSET会成功，否则若至少一个key被修改了，MSET会失败，这样我们在写回Redis的时候也实现了I隔离性。我们在外层加入一个循环来重试这个过程，直到MSET成功或者updater抛出异常。一般来说，Redis的MULTI/EXEC过程并不实现原子性，如果有多条语句，前面的语句成功、后面的语句失败的情况下，前面的语句并不会被回滚，不过没有关系，我们的MULTI/EXEC中只有一条语句MSET，因此可以保证A原子性。因此，MUPDATE过程是一个满足ACID要求的事务过程。
这样我们就在Redis中实现了MUPDATE语义。对其他No-SQL系统来说，ZooKeeper使用版本号的方式与Redis的乐观锁是非常相似的，代码结构只有很小的差异；对于其他No-SQL来说，也可以使用前文中的锁系统的方式，改为先按Key的字典序加写入锁，然后读取所有Key的值，通过updater计算需要写入的值，写入，然后按相反的顺序解开锁。当write_keys包含keys中未出现过的Key的时候，我们可以解开当前的锁然后自动进行一次重试，将write_keys加入到下次加锁的列表中，直到所有的write_keys都在已经加过锁的Key的列表中。
要注意，传入的updater有可能被调用多次，应当保证每次调用的执行过程相同，没有额外的副作用。
=========================分割线===========================
有了MGET和MUPDATE两个原语，我们接下来讨论具体的业务需求。当我们要获取的Key是个固定的列表的时候，我们通过MGET直接就满足了要求，但是通常业务都没有这么简单，我们设想下面的情形：
我们有一个Key A，其中的值保存了另一个Key，指向了Key B，我们需要的是B中的值，而我们只有读取到A的值之后，才知道我们接下来应该去读取的B是哪个Key。
如果我们简单用MGET A, MGET B两条语句来读取，我们就会遇到事务性被破坏的情况，因为在MGET A之后，我们发现应该读取B，然后在实际读取B之前，有可能A的值已经被修改为了指向C，而B甚至可能已经被删除，那么我们读取B，就会得到一个不连续的结果。
那么要怎么解决这个问题呢？
正确的解决方法是我们首先使用MGET A，获取A的值，然后从中找到了B的Key；接下来，我们执行：
MGET A,B
同时获取A和B的值。在获取回这两个值之后，我们重新检查A的值，看A的值是否仍然指向B，如果仍然指向B，事务执行成功；否则，从A新的值中，获取最新的Key C，然后重新执行MGET A,C，直到获得一致的结果为止。
可以看到，这同样是一个乐观锁的思路，这也是唯一的正确方法。如果我们用游戏买卖加锁的方法，先给A加锁，获取到结果后再给B加锁，我们就会遇到严重的问题：死锁。因为另一个过程中，我们完全有可能先锁了B，再从B的结果中得到A，然后尝试给A加锁，这样我们就进入了一个死锁的过程。innodb就是因为这样的设计所以经常发生死锁，以至于需要有专门的死锁解开的引擎。
由于业务通常会比我们举的例子更复杂，对每个业务需要都实现这样复杂的逻辑显然是很让人头疼的事情，我们把这个过程抽象成一个新的原语WALK：
WALK(walker, key1, key2, ...)
walker是如下格式的函数：
def walker(keys, values, walk, save):
...其中keys是指定的key的列表key1, key2, ...，values是相应的值的列表。walk是个函数：walk(key)->value，接受一个key作为参数，返回key对应的值，key既可以在keys中，也可以不在keys中。当key在keys中时，walk保证返回的值与values中对应的值相同；当key不在keys中时，walk有两种行为：
返回相应的value
抛出特定的异常KeyError，表示这个值还没有从No-SQL数据库取回，walker应该捕获这个异常并忽略任何后续的步骤
save是个函数save(key)，接受一个key作为参数，保存这个key和相应的值。
WALK原语的返回值是所有经过save保存的key和值的列表。
我们之前提到的业务场景，用walker描述，大致会写成这样：
def A_walker(keys, values, walk, save):
# 取回A的值
(valueA,) = values
# 获取B的key
keyB = valueA.getB()
try:
# 通过walk方法获取B的值
valueB = walk(keyB)
except KeyError:
# B尚未取回，忽略后续步骤
pass
else:
# 成功取回了B，保存B的值
save(keyB)WALK方法的实现大致如下：
def WALK(walker, *keys):
# 存储需要额外获取的keys
extrakeys = set()
while True:
allkeys = list(keys) + list(extrakeys)
allvalues = MGET(*allkeys)
# 将所有的key-value对存储到字典
valuedict = dict(zip(allkeys, allvalues))
values = allvalues[:len(keys)]
savedkeys = []
savedvalues = []
morekeys = [False]
# Walk方法，从当前的valuedict中查找，找不到抛出KeyError
def walk(key):
if key not in keys:
# 我们用到了一个不在原始列表中的key，保存下来
extrakeys.add(key)
if key in valuedict:
return valuedict[key]
else:
# 至少有一个key没有获取到，我们要等下一次MGET，看是否取回了所有需要的key
morekeys[] = True
raise KeyError('Not retrieved')
def save(key):
savedkeys.append(key)
savedvalues.append(valuedict[key])
walker(keys, values, walk, save)
if not morekeys[]:
# 我们没有需要重新获取的key了
return (savedkeys, savedvalues)用WALK原语，我们可以很容易实现上面描述的连续MGET的过程。注意与updater相似，walker也有可能被连续调用多次。
我们可以很容易证明WALK原语的事务性：除了最后一次MGET以外，前面的若干次MGET，只起到预测需要的Key的列表的作用，不会影响最后结果，最后结果是由一次独立的MGET完全产生的， 由于MGET满足ACID事务性，因此WALK也满足ACID事务性。
在写数据时，大部分情况下我们都很明确需要写的是哪些Key，我们需要写入的值从需要从另一些Key中获取。这个时候我们可以直接使用MUPDATE进行写入操作。
对于更复杂的情况，我们可以仿照WALK，定义一种新的操作WRITEWALK：
WRITEWALK（walker, key1, key2, ...)
其中walker是如下格式的函数：
def walker(key, value, walk, write, timestamp):
...除了将save替换为write和加入了timestamp参数外，与WALK中的walker类似。write为函数write(key, value)，将value写入key。一个示例如下：
def A_writewalker(keys, values, walk, write, timestamp):
# 取回A的值
(valueA,) = values
# 获取B的key
keyB = valueA.getB()
try:
# 通过walk方法获取B的值
valueB = walk(keyB)
except KeyError:
# B尚未取回，忽略后续步骤
pass
else:
# 成功取回了B，修改B的值
valueB.count += 1
valueB.updatetime = timestamp
write(keyB, valueB)WRITEWALK可以由一次WALK和一次MUPDATE拼成，不需要直接调用MGET，只需要一点小技巧：
def WRITEWALK(walker, *keys):
savedkeys = ()
# 临时使用的timestamp，因为只有MUPDATE方法才会返回真正的timestamp
lasttimestamp = [TIME]
while True:
# 创建一个WALK的walker，在其中调用传入的walker
def write_walker(keys2, values, walk, save)
# 给walker用的walk方法，调用WALK中的walk
def walk2(key):
r = walk(key)
# 所有成功获取的key，我们都通过save保存下来
if key not in keys:
save(key)
return r
# 给walker用的伪造的write方法
def write(key, value):
pass
walker(keys2[:len(keys)], values[:len(keys)], walk2, write, lasttimestamp[])
savedkeys, _ = WALK(write_walker, *(keys + savedkeys))
def updater(keys2, values, timestamp):
# 将获取到的值存入字典
valuedict = dict(zip(keys2, values))
morekeys = [False]
# 给walker用的walk方法
def walk(key):
if key not in valuedict:
morekeys[] = True
raise KeyError('Not retrieved')
else:
return valuedict[key]
writedict = {}
# 给walker用的write方法
def write(key, value):
writedict[key] = value
lasttimestamp[] = timestamp
walker(keys2[:len(keys)], values[:len(keys)], walk, write, timestamp)
if morekeys[]:
# 中止MUPDATE，从WALK开始重试
raise MoreKeysException()
else:
return zip(*writedict.items())
try:
MUPDATE(updater, *(keys + savedkeys))
except MoreKeysException:
continue
else:
break通过两次调用walker传入不同的回调函数，可以实现WALK和MUPDATE的不同功能，实现复杂的写入业务。
与之前WALK的讨论相似，真正的操作只有最后一次MUPDATE，之前可能出现的多次WALK和MUPDATE的结果都被丢弃且没有产生数据库状态的变化，由于MUPDATE满足ACID事务性，因此WRITEWALK也满足ACID事务性。
结论：
我们使用简单的乐观锁的方法实现了任意No-SQL数据库中的事务性，只要数据库原生支持或经过改造后支持MGET和MUPDATE两种操作，并给出了相应的伪代码，可以发现，事务性其实并没有我们想象的那么复杂。由于所有的操作都只会锁住使用到的Key，在存储海量的相互关联的数据时，这些事务性操作将会有比较理想的性能。
要注意的是，我们虽然实现了完整的ACID事务性，但业务中的索引、外键等关系型数据库的常用逻辑需要有自定义的数据结构进行支持。例如，我们可以将所有特定类型Key的列表存入一个特殊的Key当中，比如把所有的myprogram.myobject.obj001这样的key，存进myprogram.myobjectlist的列表中，在创建和删除myobject时同步修改myobjectlist，我们就获得了一个简单的myobject的索引，可以很容易地通过WALK来同时获取所有的myobject，甚至按照myobject的值进行筛选，相当于SQL中的全表扫描。我们还可以进一步按照myobject中存储的特定字段创建索引，在必要时进一步优化查找性能。当然如果这样的需求非常多，也许你最开始就应该选用关系型数据库。
