2009-07-07 93 views
17

請原諒術語中的任何錯誤。特別是,我正在使用關係數據庫術語。鍵值存儲中的原子交易

有一些持久性鍵值存儲,包括CouchDBCassandra,以及其他大量的項目。

反對它們的典型論據是它們通常不允許跨多行或多表的原子事務。我想知道是否有一個通用的方法可以解決這個問題。

舉例說明一組銀行賬戶的情況。我們如何將資金從一個銀行賬戶轉移到另一個賬戶?如果每個銀行賬戶都是一個行,我們想要更新兩行作爲同一個事務的一部分,減少一個值並增加另一個值。

一個明顯的方法是有一個單獨的表來描述交易。然後,將錢從一個銀行賬戶轉移到另一個銀行賬戶,只需在該表格中插入一個新行。我們不存儲兩個銀行賬戶中任一賬戶的當前餘額,而是依靠彙總交易表中所有適當的行。然而,很容易想象這將是太多的工作。一家銀行可能每天有數百萬筆交易,而且一家銀行賬戶可能會迅速擁有數千筆與之相關的「交易」。

如果底層數據自上次抓取數據後發生了變化,那麼多個(全部?)鍵值存儲將「回滾」一個動作。可能這可以用來模擬原子事務,然後,你可以指出特定的字段被鎖定。這種方法存在一些明顯的問題。

還有其他想法嗎?我的方法完全有可能是不正確的,我還沒有圍繞新的思維方式將我的大腦包裹起來。

+0

CouchDB不是鍵值,它是一個文檔存儲。 – OrangeDog 2017-02-17 10:26:42

回答

10

如果以您的示例爲例,您想自動更新單個文檔(關係術語中的行)中的值,則可以在CouchDB中執行此操作。當您嘗試提交更改時,如果其他競爭客戶端在讀取該文檔後更新了同一文檔,則會出現衝突錯誤。然後您必須讀取新值,更新並重新嘗試提交。有一個不確定的(如果有一個批次)次數,你可能不得不重複這個過程,但如果你的提交成功,你將保證在數據庫中有一個原子更新的平衡文件。

如果您需要更新兩個餘額(即從一個賬戶轉移到另一個賬戶),那麼您需要使用一個單獨的交易憑證(有效的另一個表,其中行是交易)存儲金額和兩個賬戶(進進出出)。順便說一下,這是一種常見的簿記實踐。由於CouchDB僅根據需要計算視圖,因此從列出該帳戶的交易中計算帳戶中的當前金額實際上仍然非常有效。在CouchDB中,您可以使用一個映射函數,該函數將帳號作爲密鑰和交易金額(正向傳入,負向傳出)。您的簡化函數可以簡單地將每個鍵的值相加,併發出相同的鍵和總和。然後,您可以使用group = True的視圖來獲取帳戶餘額,並以帳號爲鍵。

+0

謝謝你解釋這個。你說這個團隊「仍然非常有效」。你能詳細說明一下嗎?對於高流量的關係數據庫,通常會對列進行非規範化處理。我可以想象,CouchDB和其他人存儲數據的方式顯着不同,這意味着交易分組可能會更有效率。但是,你會用10個交易來組合嗎? 100? 100000? – ChrisInEdmonton 2009-07-07 21:12:41

+0

CouchDB使用Map/Reduce範例來查看數據庫中的文檔。由於地圖僅適用於已更改的文檔,因此它的(時間)效率基本上是文檔總數O(1),而O(n)是已更改文檔數量。計算減少的值並將其存儲在b樹中。顯然,所有有更改的子文檔的節點都需要重新計算。因此,運行減少可能會花費更多時間。 CouchDB已經在生產中用數百萬個文檔進行了演示,所以我不認爲這將是一個問題。 – 2009-07-07 22:08:05

5

CouchDB不適用於事務性系統,因爲它不支持鎖定和原子操作。

爲了完成銀行轉賬,你必須做幾件事情:

  1. 驗證交易,確保有源帳戶中有足夠的資金,這兩個賬戶是開放的,沒有上鎖,並處於良好站立,等
  2. 降低源帳戶
  3. 的餘額本期增加目標賬戶的餘額

如果更改任何的之間進行這些步驟是帳戶的餘額或狀態,交易在提交後可能會失效,這是這類系統中的一個大問題。

即使您使用上面建議的方法插入「轉帳」記錄並使用地圖/減少視圖來計算最終賬戶餘額,您也無法確保您不會透支原始賬戶,因爲在檢查來源賬戶餘額和插入可以在檢查餘額之後同時添加兩個交易的交易之間仍存在競爭狀況。

所以......這是這項工作的錯誤工具。 CouchDB可能擅長很多事情,但這是它實際上無法做到的事情。

編輯:這也許值得一提的是,在現實世界中實際使用的銀行最終一致性。如果您透支您的銀行賬戶足夠長時間,您將獲得透支費用。如果你非常好,你甚至可以幾乎同時從兩臺不同的自動櫃員機取錢,並透支你的賬戶,因爲有競爭條件來檢查餘額,發放資金並記錄交易。當您將支票存入您的賬戶時,他們會碰到餘額,但實際持有這些資金一段時間「以防萬一」源代碼賬戶沒有足夠的錢。

2

爲了提供一個具體的例子(因爲有一個令人驚訝的缺乏正確的例子在線):這裏是如何實現「atomic bank balance transfer」 CouchDB中(從同一主題我的博客文章在很大程度上覆制:http://blog.codekills.net/2014/03/13/atomic-bank-balance-transfer-with-couchdb/

首先,問題的簡短回顧:如何能在銀行系統,它允許 錢在帳戶之間轉移被設計成有可能離開無效的或無意義的餘額無種族 條件?

這個問題有幾個部分:

第一個:事務日誌。 {"account": "Dave", "balance": 100} - - 而不是在一個單一的 紀錄或文件存儲的賬戶餘額的賬戶的餘額 由所有的貸方和借方總結該帳戶計算。 這些貸方和借方都存儲在一個事務日誌,它可能看起來 是這樣的:

{"from": "Dave", "to": "Alex", "amount": 50} 
{"from": "Alex", "to": "Jane", "amount": 25} 

與CouchDB的地圖,減少功能來計算餘額可能看起來 是這樣的:

POST /transactions/balances 
{ 
    "map": function(txn) { 
     emit(txn.from, txn.amount * -1); 
     emit(txn.to, txn.amount); 
    }, 
    "reduce": function(keys, values) { 
     return sum(values); 
    } 
} 

爲了完整起見,這裏是平衡的列表:

GET /transactions/balances 
{ 
    "rows": [ 
     { 
      "key" : "Alex", 
      "value" : 25 
     }, 
     { 
      "key" : "Dave", 
      "value" : -50 
     }, 
     { 
      "key" : "Jane", 
      "value" : 25 
     } 
    ], 
    ... 
} 

但這休假顯而易見的問題是:如何處理錯誤?如果 有人試圖讓轉帳大於餘額,會發生什麼情況?

使用CouchDB(以及類似的數據庫),這種業務邏輯和錯誤 處理必須在應用程序級別實現。天真,這樣的功能 可能是這樣的:

def transfer(from_acct, to_acct, amount): 
    txn_id = db.post("transactions", {"from": from_acct, "to": to_acct, "amount": amount}) 
    if db.get("transactions/balances") < 0: 
     db.delete("transactions/" + txn_id) 
     raise InsufficientFunds() 

但要注意的是,如果將交易 並檢查更新的餘額數據庫將處於不一致 狀態留給之間的應用程序崩潰:發送者可能是隻剩下一個負平衡,並與 的錢,以前不存在的收件人:

// Initial balances: Alex: 25, Jane: 25 
db.post("transactions", {"from": "Alex", "To": "Jane", "amount": 50} 
// Current balances: Alex: -25, Jane: 75 

如何這個問題能解決?

爲了確保系統永遠處於不一致的狀態,需要被添加到每一筆交易的 兩條信息:

  1. 交易的創建(保證的時間,有一個strict total ordering的交易)和

  2. 狀態 - 交易是否成功。

還有將需要兩種觀點 - 一個返回賬戶的可用 平衡(即,所有的「成功」交易的總和),而另一個 回報的最古老的「待定」的交易:轉讓

POST /transactions/balance-available 
{ 
    "map": function(txn) { 
     if (txn.status == "successful") { 
      emit(txn.from, txn.amount * -1); 
      emit(txn.to, txn.amount); 
     } 
    }, 
    "reduce": function(keys, values) { 
     return sum(values); 
    } 
} 

POST /transactions/oldest-pending 
{ 
    "map": function(txn) { 
     if (txn.status == "pending") { 
      emit(txn._id, txn); 
     } 
    }, 
    "reduce": function(keys, values) { 
     var oldest = values[0]; 
     values.forEach(function(txn) { 
      if (txn.timestamp < oldest) { 
       oldest = txn; 
      } 
     }); 
     return oldest; 
    } 

} 

列表現在看起來是這樣的:

{"from": "Alex", "to": "Dave", "amount": 100, "timestamp": 50, "status": "successful"} 
{"from": "Dave", "to": "Jane", "amount": 200, "timestamp": 60, "status": "pending"} 

接下來,應用程序將需要有可爲了解決 交易通過檢查每一等待交易的功能,以驗證它是 有效,然後更新其狀態從「待定」要麼「成功」或 「拒絕」:

def resolve_transactions(target_timestamp): 
    """ Resolves all transactions up to and including the transaction 
     with timestamp `target_timestamp`. """ 
    while True: 
     # Get the oldest transaction which is still pending 
     txn = db.get("transactions/oldest-pending") 
     if txn.timestamp > target_timestamp: 
      # Stop once all of the transactions up until the one we're 
      # interested in have been resolved. 
      break 

     # Then check to see if that transaction is valid 
     if db.get("transactions/available-balance", id=txn.from) >= txn.amount: 
      status = "successful" 
     else: 
      status = "rejected" 

     # Then update the status of that transaction. Note that CouchDB 
     # will check the "_rev" field, only performing the update if the 
     # transaction hasn't already been updated. 
     txn.status = status 
     couch.put(txn) 

最後,爲正確地應用程序代碼進行傳輸:

def transfer(from_acct, to_acct, amount): 
    timestamp = time.time() 
    txn = db.post("transactions", { 
     "from": from_acct, 
     "to": to_acct, 
     "amount": amount, 
     "status": "pending", 
     "timestamp": timestamp, 
    }) 
    resolve_transactions(timestamp) 
    txn = couch.get("transactions/" + txn._id) 
    if txn_status == "rejected": 
     raise InsufficientFunds() 

有兩點要注意:

  • 爲了簡潔起見,這個特定的實現假定CouchDB的map-reduce中有一定量的 原子性。更新代碼,以便它不依賴於 ,該假設作爲練習留給讀者。

  • 主/複製或CouchDB的文檔同步尚未考慮到 的考慮。主/主複製和同步使這個問題 明顯更加困難。

  • 在真實的系統中,使用time()可能會導致衝突,所以使用 有點熵的東西可能是一個好主意;也許"%s-%s" %(time(), uuid()),或在排序中使用文檔的_id。 包括時間不是絕對必要的,但它有助於在多個請求幾乎同時進入時保持邏輯 。

1

BerkeleyDB和LMDB都是支持ACID事務的關鍵值存儲。在BDB中,txns是可選的,而LMDB只能以事務方式運行。

1

反對它們的典型論據是它們通常不允許跨多行或多表的原子事務。我想知道是否有一個通用的方法可以解決這個問題。

許多現代數據存儲不支持開箱即用的原子多鍵更新(事務),但其中大多數提供允許您構建ACID客戶端事務的原語。

如果一個數據存儲支持每個關鍵線性化和比較交換或測試設置操作,那麼它足以實現可序列化的事務。例如,這種方法在Google's PercolatorCockroachDB數據庫中使用。

在我的博客中,我創建了step-by-step visualization of serializable cross shard client-side transactions,描述了主要用例並提供了該算法變體的鏈接。我希望它能幫助你理解如何爲你的數據存儲實現它們。

其中每個鍵線性化和CAS支持的數據存儲是:

  • 卡桑德拉用輕質交易
  • 了Riak一致桶
  • RethinkDB
  • 的ZooKeeper
  • Etdc
  • HBase的
  • DynamoDB
  • MongoDB的

順便說一句,如果你是罰款提交讀隔離級別的話很有道理採取由彼得Bailis上RAMP transactions看看。它們也可以用於同一組數據存儲。