2009-07-07 102 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看看。它们也可以用于同一组数据存储。