Key-Value ストアのアトミック トランザクション

StackOverflow https://stackoverflow.com/questions/1093115

質問

用語の間違いについてはご容赦ください。特に、リレーショナル データベースの用語を使用しています。

永続的なキーと値のストアは数多くあります。 カウチDB そして カサンドラ, 、他の多くのプロジェクトとともに。

それらに対する典型的な議論は、複数の行またはテーブルにわたるアトミックなトランザクションを通常は許可しないというものです。この問題を解決する一般的なアプローチがあるかどうかは疑問です。

一連の銀行口座の状況を例に考えてみましょう。ある銀行口座から別の銀行口座にお金を移動するにはどうすればよいでしょうか?各銀行口座が行である場合、同じトランザクションの一部として 2 つの行を更新し、1 つの行の値を減らし、もう 1 つの行の値を増やしたいと考えます。

明らかなアプローチの 1 つは、トランザクションを説明する別のテーブルを用意することです。次に、ある銀行口座から別の銀行口座にお金を移動するには、このテーブルに新しい行を挿入するだけです。2 つの銀行口座のどちらの現在の残高も保存せず、代わりにトランザクション テーブル内の適切な行をすべて合計することに依存します。しかし、これは大変な作業であることは容易に想像できます。銀行では 1 日に数百万件の取引が行われる可能性があり、個々の銀行口座にはすぐに数千件の「取引」が関連付けられる可能性があります。

基になるデータが最後に取得されてから変更されている場合、多数 (すべて?) のキー/値ストアはアクションを「ロールバック」します。おそらく、これを使用してアトミック トランザクションをシミュレートし、特定のフィールドがロックされていることを示すことができます。このアプローチには明らかな問題がいくつかあります。

他に何かアイデアはありますか？私のアプローチが単に間違っていて、新しい考え方をまだ理解できていない可能性は十分にあります。

役に立ちましたか？

解決

例として、値をアトミックに更新したい場合は、 シングル ドキュメント (リレーショナル用語では行) を作成するには、CouchDB を使用します。他の競合クライアントが同じドキュメントを読み取ってから更新している場合、変更をコミットしようとすると競合エラーが発生します。その後、新しい値を読み取り、更新し、コミットを再試行する必要があります。不定値があります (ある場合は無限大になる可能性があります)。 多く このプロセスを何度も繰り返す必要があるかもしれませんが、コミットが成功すれば、残高がアトミックに更新されたドキュメントがデータベース内に存在することが保証されます。

2 つの残高を更新する必要がある場合 (つまり、ある口座から別の口座への送金など）の場合は、金額と 2 つの口座（入金と入金）を保存する別の取引文書（事実上、行が取引である別のテーブル）を使用する必要があります。ちなみに、これは一般的な簿記のやり方です。CouchDB は必要な場合にのみビューを計算するため、実際には、その口座をリストするトランザクションからその口座の現在の金額を計算するのが非常に効率的です。CouchDB では、キーとして口座番号とトランザクション金額 (受信の場合は正、送信の場合は負) を出力するマップ関数を使用します。Reduce 関数は、各キーの値を単純に合計し、同じキーと合計を出力します。その後、group=True を指定したビューを使用して、口座番号をキーとした口座残高を取得できます。

他のヒント

CouchDB はロックやアトミック操作をサポートしていないため、トランザクション システムには適していません。

銀行振込を完了するには、いくつかのことを行う必要があります。

  1. トランザクションを検証し、ソースアカウントに十分な資金があること、両方のアカウントが開いていてロックされていないこと、良好な状態であることなどを確認します。
  2. ソースアカウントの残高を減らす
  3. 宛先口座の残高を増やす

これらのステップのいずれかの間に口座の残高やステータスに変更が加えられた場合、トランザクションは送信後に無効になる可能性があり、これはこの種のシステムでは大きな問題です。

「振替」レコードを挿入し、マップ/リデュース ビューを使用して最終的な口座残高を計算する、上記で提案したアプローチを使用したとしても、ソース口座を超過引き落とししないことを保証する方法はありません。ソースアカウントの残高の確認とトランザクションの挿入の間の競合状態。残高の確認後に 2 つのトランザクションが同時に追加される可能性があります。

それで ...それは仕事には間違ったツールです。CouchDB はおそらく多くのことに優れていますが、これは実際にはできないことです。

編集：おそらく、現実世界の実際の銀行が結果整合性を使用していることは注目に値します。銀行口座を長期間貸越すると、当座貸越手数料がかかります。非常に優秀であれば、残高の確認、お金の発行、取引の記録に競合状態が存在するため、ほぼ同時に 2 つの異なる ATM からお金を引き出し、アカウントを過剰に引き出すこともできるかもしれません。あなたがあなたの口座に小切手を入金すると、彼らは残高を増やしますが、実際には、ソース口座に実際に十分な資金がない場合に備えて、それらの資金を一定期間保持します。

具体的な例を示します (オンラインには正しい例が驚くほど不足しているため):「」を実装する方法は次のとおりです。アトミックバンク残高転送" in 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 Map-Reduce機能は、バランスを計算する機能が次のようになる可能性があります。

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

これはどうすれば修正できますか?

システムが一貫性のない状態にないことを確認するには、各トランザクションに2つの情報を追加する必要があります。

  1. トランザクションが作成された時刻 (トランザクションが存在することを確認するため) 厳密な合計注文 トランザクションの）、および

  2. ステータス — トランザクションが成功したかどうか。

また、2つのビューが必要です。1つはアカウントの利用可能な残高（つまり、すべての「成功した」トランザクションの合計）、もう1つは最も古い「保留中の」トランザクションを返すものです。

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 注文の際に。時間を含めることは厳密に必要ではありませんが、複数のリクエストがほぼ同時に入っている場合、論理的なものを維持するのに役立ちます。

のBerkeleyDBとLMDB両方ACIDトランザクションをサポートするキー値が格納されています。 LMDBのみトランザクション動作しながら、BDBでtxnsはオプションです。

それらに対する典型的な議論は、複数の行またはテーブルにわたるアトミックなトランザクションを通常は許可しないというものです。この問題を解決する一般的なアプローチがあるかどうかは疑問です。

最新のデータ ストアの多くは、そのままではアトミックなマルチキー更新 (トランザクション) をサポートしていませんが、そのほとんどは、ACID クライアント側トランザクションを構築できるプリミティブを提供します。

データ ストアがキーごとの線形化機能と比較と交換またはテストと設定の操作をサポートしている場合は、シリアル化可能なトランザクションを実装するだけで十分です。たとえば、このアプローチは次のような場合に使用されます。 Googleのパーコレーター そしてで ゴキブリDB データベース。

私のブログで作成したのは、 シリアル化可能なクロスシャードのクライアント側トランザクションの段階的な視覚化, では、主な使用例について説明し、アルゴリズムのバリアントへのリンクを提供しました。データ ストアにこれらを実装する方法を理解するのに役立つことを願っています。

キーごとの線形化可能性と CAS をサポートするデータ ストアは次のとおりです。

  • 軽量トランザクションを備えた Cassandra
  • 一貫したバケットを備えた Riak
  • RethinkDB
  • 動物園の飼育員
  • Etdc
  • HBase
  • DynamoDB
  • モンゴDB

ちなみに、Read Committed 分離レベルに問題がない場合は、以下を見てみるのが理にかなっています。 RAMPトランザクション ピーター・ベイリス著。これらは、同じデータ ストアのセットに対して実装することもできます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top