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資料庫中存儲的資料有以下的特點：

每個存儲的值都有一個唯一的鍵（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中存儲的特定字段建立索引，在必要時進一步優化查找性能。當然如果這樣的需求非常多，也許你最開始就應該選用關系型資料庫。