【分散式系統設計】：漫談冪等

• 2020 年 3 月 5 日
• 筆記

引言

因為筆者對分散式系統有著狂熱的興趣，因此開了【分散式系統設計】這一專題，不僅可以分享學習成果，幫助大家面試，根據費曼方法，還能在寫文章的過程過發現自己認識的不足。

分散式系統與單機編程有著巨大的區別，一台電腦上的任何錯誤（硬體錯誤，kernel panic）可以讓電腦直接宕機(single point of failure)，這意味著單機程式沒有任何容錯性，而這是對可用性有著極高要求的互聯網公司們絕對無法容忍的。而在大部分分散式系統中，一台甚至多台機器的宕機以及機器之間的網路中斷(network partition, 這個問題將在之後的文章中分析)並不會影響到整個系統的運作。然而，分散式系統中各種各樣的錯誤都有可能發生，圍繞著分散式系統的容錯性，可用性，以及一致性，許多精妙的設計與演算法被提出。這個專題將分析和總結分散式資料庫，分散式快取，分散式計算和分散式事務等話題。作為第一篇文章，本文將介紹冪等(idempotency)這個概念以及其重要性，並且討論幾個實現冪等的方法，讓大家對分散式系統有一個初步的認識。

冪等

筆者有過一個真實的經歷（聽著很像為了寫文章編出來的，但是千真萬確），之前跟朋友們約好旅行，在網上買機票的過程中，有一個朋友在最後一步也就是VISA支付介面點擊付款時被通知付款失敗，於是他重新點了一次支付，然後成功了。這個過程聽上去很正常，可是當他檢查郵箱和自己的銀行賬戶時，發現自己付款了兩次，於是開始了漫長的與航空公司扯皮的過程（最後成功退款）。

當時並不明白為什麼會出現這種情況，因為如果VISA告訴我支付失敗，那麼支付一定是失敗了，為什麼我仍然付款了呢？這就引入了電腦通訊的不可靠性了，筆者將支付的幾種情況畫出來：

支付成功

這種情況展示了在一個小小的分散式系統中（你的電腦和visa的伺服器）一次完整且正常的通訊，用戶提交訂單，VISA處理訂單並通知用戶成功。

訂單提交丟失

這種情況展示了提交訂單請求在不穩定的網路環境中的丟失，用戶並不知道自己的請求丟失了，一直等下去是肯定不行的，所以在分散式系統中，所有的API介面都會設置一個超時機制（timeout）。在此例中，用戶點擊付款，於是電腦調用VISA的支付介面，但是請求丟失，過了一段時間後調用超時了，客戶端返回用戶一個超時錯誤。用戶此時也許會重試，但是這種情況下的重試不會出問題，因為訂單並沒有真正提交。

訂單處理失敗

這種情況中，VISA支付伺服器出錯（寫資料庫失敗或者下游服務宕機），於是給用戶返回了一個錯誤。用戶也許會重試，但是同樣也沒有問題，因為訂單並沒有真正提交。

訂單處理成功，但是回復丟失

這是最為棘手的一種情況，訂單處理成功，然後伺服器給用戶電腦的回復丟失了，用戶電腦對支付介面的調用將會超時，此時一旦用戶重試提交訂單並且成功，兩次支付將會發生！

冪等(idempotency)正是為了應對這種情況而提出的一種機制。在數學中，冪等意味著函數的多次調用將返回相同結果：f(x)=f(f(x))。在分散式系統中有著相似的意味：介面的多次調用將返回相同的系統狀態。簡單地舉例來說，我們不管幾次調用支付介面，銀行賬戶都只應該有一次扣款。

接下來將會介紹冪等的幾種實現方法。

實現方法

天然冪等

有很多操作是天然冪等的，比如SQL中的 SELECT, DELETE， 部分 UPDATE語句和精心設計的 INSERT語句。

SELECT作為一個只讀操作，每次調用自然不會改變系統狀態。

對於 DELETE語句來說，當我們要執行 DELETE FROM some_table WHERE id=1234，第一次執行將會把 id為1234的行刪除，而當執行第二次時，因為此行已經被刪除，SQL執行不會影響到任何行，所以 DELETE語句也是冪等的。

為什麼說只有部分 UPDATE語句是冪等的呢？比方說 UPDATE user_table SET username='Rick'WHERE id=1234語句就是冪等的，因為無論執行多少次，用戶1234的用戶名都會是Rick。但是對於 UPDATE item_stock_table SET stock=stock-1WHERE id=1234語句就是不冪等的，因為每次執行都會將商品的庫存減少1件。

對於 INSERT操作，如果我們對於給要插入的表加入一個unique field, 並且在插入時附上這個field。比方說有一個表叫做 user_table，id在創表時設為唯一，那麼 INSERT INTO user_table(id,username)VALUES(1234,"rick")語句在id為1234的用戶不存在時會插入成功，而一旦插入成功，第二次重試一定會返回一個 ERR_DUPLICATE錯誤。

樂觀鎖

樂觀鎖指在操作之前，向伺服器索要一個版本號，在隨後的實際操作請求中附上版本號，如果請求中的版本號與伺服器當前版本號一致，那麼視為有效操作，當操作成功時，伺服器會生成一個新的版本號。因此當客戶端重試時，請求會帶著舊的版本號，伺服器發現版本號不一致時會返回一個錯誤。

舉個例子，就如之前我們說到的支付問題，當用戶的電腦發送支付100元的請求前，可以向伺服器索要當前賬戶餘額，假如伺服器返回了1000元的賬戶餘額，那麼這個請求將會附上這個餘額，當伺服器收到請求時，將執行以下邏輯：

def transaction(request):    if request.balance == account.balance:      account.balance -= request.transaction_amount      return SUCCESS    else      return ERR_INVALID_REQUEST

因此，一旦第一次請求成功，第二次請求發生時請求中的餘額已經和真實餘額不一致，所以會收到一個錯誤返回。

當然，這只是一個非常簡化的例子來幫助大家理解樂觀鎖，真實的支付系統非常複雜，比如大部分系統使用最終一致性模型（以後筆者會撰文詳細分析），支付成功時餘額並不會馬上減少，而是後台有一個狀態機來管理交易的整個life cycle。

全局唯一request id

樂觀鎖會帶來一個問題，那就是要求在獲取版本號之後系統狀態不能發生任何改變，然而在高並發系統中，系統狀態隨時可能被其他請求改變，這將導致本請求被其他獨立的請求干擾。比方說有一個搶票網站以票的當前存量為版本號，假如用戶電腦第一次拿到的存量為100, 而發出搶票請求後系統中的存量因為另外一個用戶的搶票請求變成了99，此時因為100對不上99，這個請求就會失敗，導致了不相干的請求之間互相干擾。

這時我們回想起在上一冪等方法中提到的 INSERT操作，如果說我們給每個請求附上一個隨機生成的 reuqest id，並且在伺服器上維護一個存儲reuqest id的資料庫（reuqest id設為唯一），處理請求前將這個 request id插入資料庫，如果說插入成功，說明這個請求還沒有被處理過，如果插入失敗，意味著此請求已經被處理，系統將返回一個錯誤回復。具體流程可以由以下偽程式碼展示：

def transaction(request):    err = database.insert(request.request_id)    if err != Null:      return err    process_request(request)    return SUCCESS

總結

在這篇文章中我們分析了冪等的重要性與實現方法。在分散式系統中，因為網路的不穩定性，重試是一個非常頻繁的操作，冪等將幫助我們在不穩定的網路中維護一個正確的系統狀態。

相信讀者已經理解了分散式系統中錯誤的不可避免性。然而，不要就這麼認為分散式系統是不靠譜的，我們仍然有著許許多多巧妙的機制與演算法來實現其整體的可靠性。後續文章中筆者將分享更多的分散式原理，來讓大家感受到分散式系統的精妙之處。