Atom-Transaktionen in Schlüsselwert speichert

https://stackoverflow.com/questions/1093115

11-09-2019
|

Frage

Bitte entschuldigen Sie irgendwelche Fehler in der Terminologie. Insbesondere bin ich mit relationalen Datenbank Begriffe.

Es gibt eine Reihe von persistenten Schlüssel-Wert speichert, einschließlich CouchDB und Cassandra , zusammen mit vielen anderen Projekten.

Ein typisches Argument gegen sie ist, dass sie im Allgemeinen nicht atomare Transaktionen über mehrere Zeilen oder Tabellen erlauben es. Ich frage mich, ob es ein allgemeiner Ansatz wäre würde dieses Problem lösen.

Nehmen Sie zum Beispiel die Situation einer Reihe von Bankkonten. Wie wir Geld von einem Bankkonto auf einen anderen verschieben? Wenn jedes Bankkonto eine Zeile ist, wollen wir zwei Reihen als Teil derselben Transaktion aktualisieren, um den Wert in einer zu reduzieren und den Wert in einer anderen zu erhöhen.

Ein offensichtlicher Ansatz ist eine separate Tabelle zu haben, die Transaktionen beschreibt. Dann, um ein anderes Geld von einem Bankkonto zu bewegen besteht aus einfach eine neue Zeile in der Tabelle einzufügen. Wir speichern nicht die aktuellen Salden von einem der beiden Bankkonten und stattdessen verlassen sich auf alle entsprechenden Zeilen in der Tabelle Transaktionen zusammen. Es ist leicht vorstellbar, dass dies viel zu viel Arbeit, aber sein; eine Bank kann Millionen von Transaktionen pro Tag hat und ein individuelles Bankkonto schnell damit verbundenen mehrere tausend ‚Transaktionen‘ haben kann.

Eine Zahl (alle?) Von Schlüssel-Wert-Geschäften wird ‚Rollback‘ eine Aktion, wenn die zugrunde liegenden Daten geändert haben seit dem letzten packt. Möglicherweise könnte dies verwendet wird, atomare Transaktionen zu simulieren, dann, wie man dann zeigen könnte, dass ein bestimmtes Feld gesperrt ist. Es gibt einige offensichtliche Probleme mit diesem Ansatz.

Jede andere Ideen? Es ist durchaus möglich, dass mein Ansatz einfach falsch ist, und ich habe noch nicht mein Gehirn um die neue Art des Denkens eingewickelt.

Lösung

Wenn unter Ihrem Beispiel, Sie wollen den Wert atomar aktualisieren in einem Single Dokument (Zeile in relationaler Terminologie), können Sie so in CouchDB tun können. Sie erhalten einen Konflikt Fehlermeldung erhalten, wenn Sie versuchen, die Änderung zu übernehmen, wenn ein anderer streitenden Client das gleiche Dokument aktualisiert hat, seit Sie es lesen. Sie werden dann den neuen Wert, update lesen müssen und erneut versuchen, das begehen. Es ist ein unbestimmtes (möglicherweise unendlich, wenn es ein ist viel des Anstoßes) Anzahl, wie oft können Sie diesen Vorgang wiederholen müssen, aber Sie werden garantiert mit einem atomar aktualisiert Gleichgewicht ein Dokument in der Datenbank haben, wenn Ihre begehen immer erfolgreich ist.

Wenn Sie zwei Salden aktualisieren (dh eine Übertragung von einem Konto auf ein anderes), dann müssen Sie eine separate Transaktion Dokument verwenden (effektiv eine andere Tabelle, in der Zeilen-Transaktionen sind), die die Menge und die beiden Konten speichert (in und raus). Dies ist eine gemeinsame Buchhaltung Praxis, nebenbei bemerkt. Da CouchDB Ansichten nur bei Bedarf berechnet, ist es eigentlich immer noch sehr effizient den aktuellen Betrag auf einem Konto aus den Transaktionen zu berechnen, die Liste, die erklären. In CouchDB, würden Sie eine Map-Funktion verwenden, die die Kontonummer als Schlüssel und den Betrag der Transaktion (positiv für eingehende, negativ für abgehende) emittieren. Ihre reduzieren Funktion würde einfach Summe der Werte für jeden Schlüssel, den gleichen Schlüssel und Gesamtsumme emittiert. Sie könnten dann eine Ansicht mit Gruppe verwenden = True die Kontensalden zu bekommen, verkeilt durch Kontonummer.

Andere Tipps

CouchDB ist nicht geeignet für Transaktionssysteme, weil es nicht Schließ- und atomare Operationen unterstützt.

Um eine Banküberweisung zu vervollständigen Sie ein paar Dinge tun müssen:

Überprüfen Sie die Transaktion, um sicherzustellen, gibt es genügend Mittel in der Quellkonto, dass beide Konten sind offen und nicht gesperrt ist, und einen guten Ruf, und so weiter
Reduzieren Sie die Balance des Quellkontos
Erhöhen Sie die Balance des Zielkonto

Wenn Änderungen vorgenommen werden zwischen einem dieser Schritte die Waage oder den Status der Konten, könnte die Transaktion ungültig werden, nachdem es eingereicht wird, das ein großes Problem in einem System dieser Art ist.

Auch wenn Sie den Ansatz oben vorgeschlagen verwenden, wo Sie einen „Transfer“ Datensatz einfügen und eine Karte verwenden / verkleinern Ansicht des endgültige Kontostand zu berechnen, haben Sie keine Möglichkeit, sicherzustellen, dass das Quellen Konto nicht überziehen, weil es noch eine race-Bedingung ist die Quelle Kontostand zwischen Kontrolle und Einfügen der Transaktion, bei der zwei Transaktionen simultan hinzugefügt werden könnten, nachdem die Waage zu überprüfen.

Also ... es ist das falsche Werkzeug für den Job. CouchDB ist eine Menge Dinge wahrscheinlich gut, aber das ist etwas, das es nicht wirklich kann.

EDIT: Es ist wahrscheinlich erwähnenswert, dass die tatsächlichen Bänke in der realen Welt Eventual Consistency verwenden. Wenn Sie lange genug, um Ihr Bankkonto überziehen erhalten Sie einen Überziehungsgebühr. Wenn Sie waren sehr gut könnten Sie sogar in der Lage sein, Geld fast zur gleichen Zeit von zwei verschiedenen Geldautomaten abheben und Ihr Konto überziehen, weil es eine Race-Bedingung ist die Balance zu überprüfen, geben das Geld, und die Transaktion aufzuzeichnen. Wenn Sie einen Scheck in Ihr Konto einzahlen stoßen sie das Gleichgewicht, sondern tatsächlich halten diese Mittel für einen bestimmten Zeitraum „nur für den Fall“ -Konto die Quelle wirklich nicht genug Geld.

ein konkretes Beispiel zu liefern (weil es ein überraschender Mangel an richtigen Beispielen ist online): hier ist wie ein „ Atom-Bank Balance Transfer "in CouchDB (weitgehend aus meinem Blog-Post auf dem gleichen Thema kopiert: http://blog.codekills.net/2014/03/13/atomic-bank-balance-transfer-with-couchdb/ )

Zuerst wird eine kurze Zusammenfassung des Problems: wie ein Bankensystem kann das erlaubt Geld transferiert zwischen Konten werden so gestaltet sein, dass es keine Rasse Bedingungen, die ungültig oder unsinnige Salden könnten verlassen?

Es gibt ein paar Teile für dieses Problem:

Erstens: das Transaktionsprotokoll. Statt ein Konto Gleichgewicht in einem einzigen Speicherung Datensatz oder Dokument - {"account": "Dave", "balance": 100} - das Konto des Balance wird durch Addition aller Gutschriften und Belastungen auf dieses Konto berechnet. Diese Gutschriften und Belastungen werden in einem Transaktionsprotokoll gespeichert, die aussehen könnten so etwas wie folgt aus:

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

Und die CouchDB Karten reduzieren Funktionen, um die Balance zu berechnen aussehen könnte so etwas wie folgt aus:

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

Für die Vollständigkeit, hier ist die Liste der Salden:

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

Aber das lässt die offensichtliche Frage: Wie werden Fehler behandelt? Was passiert wenn jemand versucht, eine Übertragung größer als ihr Gleichgewicht zu machen?

Mit CouchDB (und ähnlichen Datenbanken) diese Art von Business-Logik und Fehlern Handhabung ist auf der Anwendungsebene implementiert werden. Naiver, eine solche Funktion aussehen könnte wie folgt aus:

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()

Beachten Sie aber, dass, wenn die Anwendung abstürzt, die Transaktion zwischen Einfügen und Überprüfung der aktualisierten Salden wird die Datenbank in einem inkonsistenten gelassen werden Zustand: der Sender mit einem negativen Saldo bleiben, und der Empfänger kann mit Geld, das vorher nicht vorhanden ist:

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

Wie kann dieses Problem behoben werden?

Um sicherzustellen, dass das System in einem inkonsistenten Zustand nie, zwei Stücke Informationen müssen jede Transaktion hinzugefügt werden:

Die Zeit der Transaktion erstellt wurde (um sicherzustellen, dass es eine Gesamtbestell von Transaktionen), und
Ein Status -., Ob die Transaktion erfolgreich war

Es muß auch zwei Ansichten sein - eine, die wieder ein Konto verfügbar Balance (dh die Summe aller „erfolgreich“ Transaktionen), und eine andere, die gibt die älteste "pending" Transaktion:

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;
    }

}

Liste der Transfers nun in etwa so aussehen:

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

Als nächstes wird die Anwendung benötigt eine Funktion haben, die lösen kann Transaktionen durch jede ausstehende Transaktion, um die Überprüfung, um sicherzustellen, dass es gültig, dann seinen Status von „pending“ entweder „erfolgreich“ zu aktualisieren oder "Abgelehnt":

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)

Schließlich ist der Anwendungscode für richtig Ausführen einer Übertragung:

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()

Ein paar Anmerkungen:

Aus Gründen der Kürze, diese spezifische Implementierung setzt eine gewisse Menge an Unteilbarkeit in CouchDB Karten reduzieren. Aktualisieren Sie den Code, damit es nicht auf angewiesen Diese Annahme ist als Übung dem Leser überlassen.
Master / Master-Replikation oder Dokument sync des CouchDB wurden nicht in genommen Berücksichtigung. Master / Master-Replikation und Synchronisierung machen dieses Problem erheblich erschwert.
In einem realen System time() Verwendung könnte in Kollisionen führen, so mit etwas mit einem bisschen mehr Entropie könnte eine gute Idee sein; vielleicht "%s-%s" %(time(), uuid()) oder des Dokuments _id in der Reihenfolge verwenden. einschließlich der Zeit, ist nicht unbedingt notwendig, aber es hilft, eine logische zu halten wenn mehrere Anfragen kommen in an abaus der gleichen Zeit.

BerkeleyDB und LMDB sind beide Schlüsselwert speichert mit Unterstützung für ACID-Transaktionen. In BDB txns sind optional während LMDB arbeitet nur transaktions.

Ein typisches Argument gegen sie ist, dass sie im Allgemeinen nicht atomare Transaktionen über mehrere Zeilen oder Tabellen erlauben es. Ich frage mich, ob es ein allgemeiner Ansatz wäre würde dieses Problem lösen.

Viele moderne Datenspeicher unterstützen keine atomaren Multi-Key-Updates (Transaktionen) aus der Box, aber die meisten von ihnen Primitiven geben, nach denen Sie ACID clientseitige Transaktionen zu bauen.

Wenn ein Datenspeicher pro Taste Linearisierbarkeit unterstützt und Vergleichs- und Swap-oder Test-and-Set-Operation, dann ist es genug serializable Transaktionen zu implementieren. Zum Beispiel wird dieser Ansatz in Googles Percolator verwendet und in CockroachDB Datenbank.

In meinem Blog habe ich die Schritt-für-Schritt-Visualisierung von serializable Cross Shard clientseitige Transaktionen , die wichtigsten Anwendungsfälle und ausgebrachten Links zu den Varianten des Algorithmus beschrieben. Ich hoffe, es wird Ihnen helfen zu verstehen, wie sie implementieren, um Daten zu speichern.

Unter den Datenspeicher, die pro Schlüssel Linearisierbarkeit und CAS unterstützen, sind:

Cassandra mit leichten Transaktionen
Riak mit gleichbleibenden Eimern
RethinkDB
ZooKeeper
ETDC
HBase
DynamoDB
MongoDB

By the way, wenn Sie mit Lesen in Ordnung sind Committed Isolation Level dann macht es Sinn, einen Blick zu nehmen auf RAMP Transaktionen von Peter Bailis. Sie können auch für den gleichen Satz von Datenspeichern implementiert werden.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow