transactions atomiques dans les magasins clé-valeur

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

Question

S'il vous plaît excuser toute erreur de terminologie. En particulier, j'utilise des termes de base de données relationnelles.

Il y a un certain nombre de magasins persistants clé-valeur, y compris CouchDB et Cassandra , ainsi que beaucoup d'autres projets.

Un argument typique contre eux est qu'ils ne permettent généralement pas des transactions atomiques sur plusieurs lignes ou tables. Je me demande s'il y a une approche générale serait résoudrait ce problème.

Prenons par exemple la situation d'un ensemble de comptes bancaires. Comment pouvons-nous transférer de l'argent d'un compte bancaire à un autre? Si chaque compte bancaire est une ligne, nous voulons mettre à jour deux lignes dans le cadre de la même transaction, ce qui réduit la valeur en une et en augmentant la valeur dans un autre.

Une approche évidente est d'avoir une table séparée qui décrit les transactions. Ensuite, transférer de l'argent d'un compte bancaire à un autre consiste à insérer simplement une nouvelle ligne dans ce tableau. Nous ne stockons pas les soldes courants de l'une des deux comptes bancaires et comptent plutôt sur la somme toutes les lignes appropriées dans le tableau des transactions. Il est facile d'imaginer que ce serait le travail beaucoup trop, cependant; une banque peut avoir des millions de transactions par jour et un compte bancaire individuel peut rapidement plusieurs milliers de « transactions » qui lui est associée.

Un numéro (tous?) Des magasins à valeur clé « retrait » d'une action si les données sous-jacente a changé depuis la dernière a saisi. Peut-être cela pourrait être utilisé pour simuler des transactions atomiques, puis, comme vous pouvez alors indiquer qu'un champ particulier est verrouillé. Il y a des problèmes évidents avec cette approche.

D'autres idées? Il est tout à fait possible que mon approche est tout simplement faux et je n'ai pas encore enveloppé mon cerveau autour de la nouvelle façon de penser.

Était-ce utile?

La solution

Si, en prenant votre exemple, vous souhaitez mettre à jour atomiquement la valeur dans une seul document (ligne dans la terminologie relationnelle), vous pouvez le faire en CouchDB. Vous obtiendrez une erreur de conflit lorsque vous essayez de valider le changement si un autre client a mis à jour le soutenant même document depuis que vous avez lu. Vous aurez alors à lire la nouvelle valeur, mise à jour et rejuger la validation. Il y a une période indéterminée (peut-être infini s'il y a un beaucoup de discorde) le nombre de fois que vous pourriez avoir à répéter ce processus, mais vous êtes assuré d'avoir un document dans la base de données avec un solde mis à jour atomiquement si votre commettras jamais réussit.

Si vous avez besoin de mettre à jour deux soldes (à savoir un transfert d'un compte à un autre), vous devez utiliser un document de transaction distincte (effectivement une autre table où les lignes sont des transactions) qui stocke le montant et les deux comptes (en et dehors). Ceci est une pratique comptable commune, par la voie. Depuis CouchDB calcule des vues seulement au besoin, il est en fait encore très efficace pour calculer le montant actuel dans un compte des transactions liste qui compte. Dans CouchDB, vous pouvez utiliser une fonction de carte qui a émis le numéro de compte clé et le montant de la transaction (positive pour les appels entrants, négatif pour les messages sortants). Votre fonction serait de réduire simplement la somme des valeurs pour chaque clé, en émettant la même somme clé et totale. Vous pouvez ensuite utiliser une vue avec le groupe = True pour obtenir les soldes des comptes, calées par numéro de compte.

Autres conseils

CouchDB ne convient pas pour les systèmes transactionnels, car il ne prend pas en charge les opérations de verrouillage et atomiques.

Pour effectuer un virement bancaire, vous devez faire quelques petites choses:

  1. Valider la transaction, assurant qu'il ya suffisamment de fonds dans le compte source, que les deux comptes sont ouverts, non verrouillé, et en règle, etc.
  2. Diminuer le solde du compte source
  3. Augmenter le solde du compte de destination

Si des modifications sont apportées entre l'une de ces étapes l'équilibre ou l'état des comptes, la transaction pourrait devenir invalide après sa présentation qui est un gros problème dans un système de ce genre.

Même si vous utilisez l'approche suggérée ci-dessus lorsque vous insérez un enregistrement « transfert » et utiliser une map / reduce en vue de calculer le solde final du compte, vous avez aucun moyen de vous assurer que vous ne découvert sur pas le compte source, car il est toujours une condition de course entre la vérification du solde du compte source et l'insertion de la transaction où deux transactions pourraient simultanément être ajoutés après vérification de l'équilibre.

Alors ... c'est le mauvais outil pour le travail. CouchDB est probablement bon à beaucoup de choses, mais c'est quelque chose qu'il ne peut vraiment pas faire.

EDIT: Il est probablement intéressant de noter que les banques réelles dans le monde réel utilisent la cohérence éventuelle. Si vous découvert sur votre compte bancaire pour assez longtemps, vous obtenez des frais de découvert bancaire. Si vous étiez très bien que vous pourriez même être en mesure de retirer de l'argent de deux distributeurs automatiques de billets différents à peu près au même moment et overdraw votre compte, car il y a une condition de course pour vérifier le solde, émettre l'argent, et enregistrer la transaction. Lorsque vous déposez un chèque dans votre compte, ils cognent l'équilibre mais en fait détenir ces fonds pour une période de temps « juste au cas où » le compte source n'a pas vraiment assez d'argent.

Pour donner un exemple concret (parce qu'il ya un manque surprenant d'exemples corrects en ligne): voici comment mettre en œuvre un « transfert de solde bancaire atomique « dans CouchDB (largement copié de mon billet de blog sur le même sujet: http://blog.codekills.net/2014/03/13/atomic-bank-balance-transfer-with-couchdb/ )

Tout d'abord, un bref rappel du problème: comment un système bancaire qui permet argent pour être transféré entre les comptes être conçus de sorte qu'il n'y a pas de race conditions qui pourraient laisser des soldes non valides ou insensées?

Il y a quelques pièces à ce problème:

Tout d'abord: le journal des transactions. Au lieu de stocker le solde d'un compte en un seul dossier ou document - {"account": "Dave", "balance": 100} - le compte de solde est calculé en additionnant tous les crédits et les débits à ce compte. Ces crédits et les débits sont stockés dans un journal des transactions, ce qui pourrait ressembler quelque chose comme ceci: 

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

Et les fonctions CouchDB carte-réduire pour calculer l'équilibre pourrait ressembler quelque chose comme ceci: 

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

Pour être complet, voici la liste des soldes: 

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

Mais cela laisse la question évidente: comment les erreurs traitées? Ce qui se passe si quelqu'un essaie de faire un transfert plus grand que leur équilibre?

Avec CouchDB (bases de données similaires) ce genre de logique métier et l'erreur la manipulation doit être mis en œuvre au niveau de l'application. Naïvement, une telle fonction pourrait ressembler à ceci: 

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

Mais remarquez que si l'application se bloque entre l'insertion de la transaction et la vérification des soldes mis à jour la base de données sera laissée dans une contradiction état: l'expéditeur peut être laissé avec un solde négatif, et le destinataire avec l'argent qui n'existait pas auparavant: 

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

Comment cela peut-il être fixé?

Pour que le système est jamais dans un état incohérent, deux morceaux de les informations doivent être ajoutées à chaque transaction:

  1. Le moment où la transaction a été créée (pour assurer qu'il ya un stricte la commande totale des transactions), et

  2. Un état -. Si la transaction a réussi

Il y aura aussi besoin d'être deux points de vue - celui qui renvoie un compte disponible de l'équilibre (c.-à-la somme de toutes les transactions « succès »), et un autre qui retourne la plus ancienne transaction "en attente": 

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 des transferts pourrait ressembler à quelque chose comme ceci: 

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

Ensuite, l'application devra avoir une fonction qui peut résoudre les transactions en vérifiant chaque transaction en cours afin de vérifier qu'il est valide, la mise à jour de son statut de « en attente » soit « succès » ou "Rejeté": 

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)

Enfin, le code d'application pour correctement effectuer un transfert: 

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

Quelques notes:

  • Par souci de concision, cette mise en œuvre spécifique suppose une certaine quantité de atomicité de CouchDB la carte-réduire. Mise à jour du code afin qu'il ne repose pas sur cette hypothèse est laissée en exercice au lecteur.

  • réplication maître / maître ou la synchronisation de documents de CouchDB n'ont pas été prises en considération. Maître / réplication maître et synchronisation font ce problème beaucoup plus difficile.

  • Dans un système réel, en utilisant time() pourrait entraîner des collisions, donc l'utilisation quelque chose avec un peu plus d'entropie peut être une bonne idée; "%s-%s" %(time(), uuid()) peut-être, ou en utilisant le _id du document dans l'ordre. Y compris le temps est pas strictement nécessaire, mais il aide à maintenir une logique si plusieurs demandes viennent à able même temps.

BerkeleyDB et LMDB sont les deux magasins clé-valeur avec prise en charge des transactions ACID. En BDB txns sont en option alors que LMDB ne fonctionne que transactionnellement.

  

Un argument typique contre eux est qu'ils ne permettent généralement pas des transactions atomiques sur plusieurs lignes ou tables. Je me demande s'il y a une approche générale serait résoudrait ce problème.

Beaucoup de magasins de données modernes ne supportent pas les mises à jour multi-clés atomiques (transactions) hors de la boîte, mais la plupart d'entre eux fournissent des primitives qui vous permettent de construire des transactions ACID côté client.

Si un magasin de données prend en charge par linéarisabilité clés et comparer et-échange ou une opération de test et mais il sera alors suffisant pour mettre en œuvre les transactions sérialisables. Par exemple, cette approche est utilisée dans Percolateur Google et dans la base de données CockroachDB .

Dans mon blog j'ai créé le visualisation étape par étape de serializable transactions client latérales croisées tesson , a décrit les principaux cas d'utilisation et fourni des liens vers les variantes de l'algorithme. J'espère que cela vous aidera à comprendre comment les mettre en œuvre pour vous magasin de données.

Parmi les magasins de données qui prennent en charge par linéarisabilité clé et CAS sont:

  • Cassandra avec des transactions légères
  • Riak avec des seaux compatibles
  • rethinkdb
  • ZooKeeper
  • ETDC
  • HBase
  • DynamoDB
  • MongoDB

Par ailleurs, si vous êtes bien avec READ COMMITTED niveau d'isolement alors il est logique de jeter un oeil sur transactions RAMP par Peter Bailis. Ils peuvent également être mis en œuvre pour le même ensemble de magasins de données.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top