Transazioni atomiche nei negozi di valori-chiave

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

Domanda

Si prega di scusare eventuali errori nella terminologia.In particolare, sto usando i termini del database relazionale.

Esistono numerosi archivi di valori-chiave persistenti, tra cui CouchDB E Cassandra, insieme a molti altri progetti.

Un tipico argomento contro di loro è che generalmente non consentono transazioni atomiche su più righe o tabelle.Mi chiedo se esiste un approccio generale che risolverebbe questo problema.

Prendiamo ad esempio la situazione di una serie di conti bancari.Come trasferiamo i soldi da un conto bancario a un altro?Se ogni conto bancario è una riga, vogliamo aggiornare due righe come parte della stessa transazione, riducendo il valore in una e aumentando il valore in un'altra.

Un approccio ovvio è quello di avere una tabella separata che descriva le transazioni.Quindi, spostare denaro da un conto bancario a un altro consiste semplicemente nell'inserire una nuova riga in questa tabella.Non memorizziamo i saldi correnti di nessuno dei due conti bancari e ci affidiamo invece alla somma di tutte le righe appropriate nella tabella delle transazioni.È facile immaginare, tuttavia, che questo sarebbe un lavoro decisamente eccessivo;una banca può effettuare milioni di transazioni al giorno e un singolo conto bancario può rapidamente avere diverse migliaia di "transazioni" ad esso associate.

Un certo numero (tutti?) di archivi di valori-chiave eseguiranno il rollback di un'azione se i dati sottostanti sono cambiati dall'ultima volta che li hai acquisiti.Forse questo potrebbe essere usato per simulare transazioni atomiche, quindi potresti indicare che un particolare campo è bloccato.Ci sono alcuni problemi evidenti con questo approccio.

Altre idee?È del tutto possibile che il mio approccio sia semplicemente sbagliato e che non abbia ancora assimilato il nuovo modo di pensare.

È stato utile?

Soluzione

Se, prendendo il vostro esempio, si desidera aggiornare atomicamente il valore in un solo documento (riga nella terminologia relazionale), è possibile farlo in CouchDB. Si otterrà un errore di conflitto quando si tenta di commettere il cambiamento, se un altro client contendenti ha aggiornato lo stesso documento in quanto lo si legge. Si avrà quindi a leggere il nuovo valore, aggiornare e ri-provare il commit. C'è un'indeterminata (possibilmente infinita se c'è un molto di contesa) il numero di volte in cui potrebbe essere necessario ripetere questo processo, ma si sono garantiti per avere un documento nel database con un equilibrio atomico aggiornato se il vostro commettere mai successo.

Se è necessario aggiornare due bilance (vale a dire un trasferimento da un conto ad un altro), allora avete bisogno di utilizzare un documento transazione separata (in modo efficace un altro tavolo dove le righe sono operazioni) che memorizza l'importo e le due conti (in e fuori). Questa è una pratica comune contabilità, tra l'altro. Dal momento che CouchDB calcola viste solo se necessario, in realtà è ancora molto efficiente per calcolare la quantità di corrente in un conto dalle operazioni quella lista che rappresentano. In CouchDB, si può usare una funzione di mappa che emetteva il numero di conto come chiave e l'importo della transazione (positivo per l'incoming, negativo per uscita). La funzione di ridurre sarebbe semplicemente sommare i valori per ogni tasto, che emettono la stessa somma chiave e totale. È quindi possibile utilizzare una vista con il gruppo = True per ottenere i saldi dei conti, calettati per numero di conto.

Altri suggerimenti

CouchDB non è adatto per sistemi transazionali perché non supporta le operazioni di bloccaggio e atomiche.

Al fine di completare un bonifico bancario è necessario fare un paio di cose:

  1. Convalida della transazione, garantendo ci sono fondi sufficienti nel conto di origine, che entrambi i conti sono aperti, non bloccato, e in regola, e così via
  2. Diminuire il saldo del conto fonte
  3. Aumentare il saldo del conto di destinazione

Se vengono apportate modifiche tra uno di questi passaggi l'equilibrio o di stato dei conti, l'operazione potrebbe diventare non valida dalla sua presentazione, che è un grosso problema in un sistema di questo tipo.

Anche se si utilizza l'approccio suggerito sopra, dove si inserisce un record "trasferimento" e si utilizza una mappa / ridurre al fine di calcolare il saldo del conto finale, non c'è modo di garantire che non si overdraw l'account di origine, perché ci è ancora una condizione di competizione tra controllando il saldo del conto di origine e di inserire la transazione in cui potrebbero essere aggiunti simultaneamente due operazioni dopo aver controllato l'equilibrio.

Quindi ... è lo strumento sbagliato per il lavoro. CouchDB è probabilmente bravo in un sacco di cose, ma questo è qualcosa che in realtà non può fare.

EDIT: E 'probabilmente la pena notare che le banche reali nel mondo reale usano eventuale consistenza. Se si overdraw tuo conto bancario per un tempo sufficiente ad ottenere una quota di scoperto. Se tu fossi molto bene si potrebbe anche essere in grado di prelevare denaro dal bancomat due differenti quasi allo stesso tempo e overdraw il tuo account perché c'è una condizione di competizione per controllare l'equilibrio, emettere il denaro, e registrare la transazione. Quando si depositare un assegno sul tuo conto urtano l'equilibrio, ma in realtà tenere quei fondi per un periodo di tempo "just in case" l'account di origine in realtà non hanno abbastanza soldi.

Per fornire un esempio concreto (perché c’è una sorprendente mancanza di esempi corretti online):ecco come implementare un "trasferimento del saldo bancario atomico" in CouchDB (in gran parte copiato dal mio post sul blog sullo stesso argomento: http://blog.codekills.net/2014/03/13/atomic-bank-balance-transfer-with-couchdb/)

Innanzitutto un breve riepilogo del problema:Come si può progettare un sistema bancario che consente di trasferire i soldi tra i conti in modo che non vi siano condizioni di razza che potrebbero lasciare saldi non validi o non privilegiati?

Ci sono alcune parti in questo problema:

Primo:il registro delle transazioni.Invece di conservare il saldo di un account in un singolo record o documento - {"account": "Dave", "balance": 100} - Il saldo del conto viene calcolato riassumendo tutti i crediti e gli addebiti su tale conto.Questi crediti e debiti sono archiviati in un registro delle transazioni, che potrebbe assomigliare a questo:

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

E le funzioni di riduzione della mappa di CouchDB per calcolare l'equilibrio potrebbero assomigliare a questo:

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

Per completezza ecco l’elenco dei saldi:

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

Ma questo lascia la domanda ovvia:come vengono gestiti gli errori?Cosa succede se qualcuno cerca di fare un trasferimento più grande del loro equilibrio?

Con COUCHDB (e database simili) questo tipo di logica aziendale e gestione degli errori devono essere implementati a livello di applicazione.Ingenuamente, una tale funzione potrebbe apparire così:

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

Ma si noti che se l'applicazione si blocca tra l'inserimento della transazione e il controllo dei saldi aggiornati, il database verrà lasciato in uno stato incoerente:Il mittente può essere lasciato con un saldo negativo e il destinatario con denaro che non esisteva in precedenza:

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

Come si puo aggiustare?

Per assicurarsi che il sistema non sia mai in uno stato incoerente, è necessario aggiungere due informazioni a ciascuna transazione:

  1. L'ora in cui è stata creata la transazione (per garantire che esista un file ordinamento totale rigoroso delle transazioni) e

  2. Uno stato: indica se la transazione è andata a buon fine o meno.

Dovranno anche esserci due visualizzazioni: una che restituisce il saldo disponibile di un account (cioè la somma di tutte le transazioni "di successo") e un'altra che restituisce la transazione più antica "in sospeso":

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

}

L'elenco dei trasferimenti ora potrebbe assomigliare a questo:

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

Successivamente, l'applicazione dovrà avere una funzione in grado di risolvere le transazioni controllando ogni transazione in sospeso per verificare che sia valida, quindi aggiornando il suo stato da "in sospeso" a "riuscita" o "rifiutato":

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)

Infine, il codice dell'applicazione per correttamente eseguire un trasferimento:

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

Un paio di note:

  • Per motivi di brevità, questa specifica implementazione presuppone una certa quantità di atomicità nel riduzione delle mappe di CouchDB.L'aggiornamento del codice in modo che non si basi su tale ipotesi viene lasciato come esercizio per il lettore.

  • La replica master/master o la sincronizzazione del documento di CouchDB non sono state prese in considerazione.La replicazione e la sincronizzazione master/maestro rendono questo problema significativamente più difficile.

  • In un sistema reale, utilizzando time() Potrebbe provocare collisioni, quindi usare qualcosa con un po 'più entropia potrebbe essere una buona idea;Forse "%s-%s" %(time(), uuid()), o utilizzando il documento _id nell'ordinazione.Includere il tempo non è strettamente necessario, ma aiuta a mantenere una logica se più richieste arrivano all'incirca nello stesso momento.

BerkeleyDB e LMDB sono entrambi i negozi chiave-valore con il supporto per le transazioni ACID. In BDB txns sono opzionali, mentre LMDB opera solo mediante transazioni.

  

Un argomento tipico contro di loro è che in genere non consentono transazioni atomiche su più righe o tabelle. Mi chiedo se c'è un approccio generale potrebbe risolverebbe questo problema.

Un sacco di moderni archivi di dati non supportano gli aggiornamenti multi-chiave atomiche (transazioni), fuori dalla scatola, ma la maggior parte di essi forniscono primitivi che permettono di costruire le transazioni ACID lato client.

Se un archivio di dati supporta per linearizability chiave e confrontare-e-swap o il funzionamento di test-and-set di allora è sufficiente per implementare le transazioni serializzabili. Ad esempio, questo approccio è utilizzato in di Google Percolator in CockroachDB database.

Nel mio blog ho creato la visualizzazione step-by-step di serializzabile transazioni shard croce sul lato client , descritti i principali casi d'uso e forniti collegamenti alle varianti dell'algoritmo. Spero che vi aiuterà a capire come implementare loro per negozio si dati.

Tra gli archivi di dati che supportano per linearizability chiave e CAS sono:

  • Cassandra con transazioni leggeri
  • Riak con secchi consistenti
  • RethinkDB
  • ZooKeeper
  • ETDC
  • HBase
  • DynamoDB
  • MongoDB

A proposito, se stai bene con Leggi commessi livello di isolamento allora ha senso dare un'occhiata su transazioni RAMPA da Peter Bailis. Essi possono essere attuate anche per lo stesso insieme di archivi di dati.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top