No-SQL資料庫中的事務性設計

摘要：本文簡述了一種在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資料庫中存儲的數據有以下的特點：

1. 每個存儲的值都有一個唯一的鍵（Key），這個Key在這個值的生命周期中不能發生變化。Key是一個字元串。
2. 值是個序列化的對象（比如採用JSON），序列化後的大小不太大，一般為KB量級，也就是說，將整個對象讀出再重新寫會並不會帶來很大的性能瓶頸
3. 值的對象中可能包含：獨立的數值；和其他對象相關聯的數值；其他對象的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有兩種行為：

1. 返回相應的value
2. 拋出特定的異常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[0] = True raise KeyError("Not retrieved") def save(key): savedkeys.append(key) savedvalues.append(valuedict[key]) walker(keys, values, walk, save) if not morekeys[0]: # 我們沒有需要重新獲取的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[0]) 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[0] = True raise KeyError("Not retrieved") else: return valuedict[key] writedict = {} # 給walker用的write方法 def write(key, value): writedict[key] = value lasttimestamp[0] = timestamp walker(keys2[:len(keys)], values[:len(keys)], walk, write, timestamp) if morekeys[0]: # 中止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中存儲的特定欄位創建索引，在必要時進一步優化查找性能。當然如果這樣的需求非常多，也許你最開始就應該選用關係型資料庫。

注意：本文中所有代碼均為示意用偽代碼，實際使用時請加以適當的修改

推薦閱讀：