transacciones atómicas en las tiendas de valores clave

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

Pregunta

Por favor, disculpe cualquier error en la terminología. En particular, estoy usando términos bases de datos relacionales.

Hay una serie de tiendas de valores clave persistentes, incluyendo CouchDB y Cassandra , junto con un montón de otros proyectos.

Un típico argumento en contra de ellos es que por lo general no permiten transacciones atómicas a través de múltiples filas o tablas. Me pregunto si hay un enfoque general sería resolvería este problema.

Tomemos por ejemplo la situación de un conjunto de cuentas bancarias. ¿Cómo nos movemos dinero de una cuenta bancaria a otra? Si cada cuenta bancaria es una fila, queremos actualizar dos filas como parte de la misma transacción, lo que reduce el valor en uno y el aumento del valor en otro.

Un enfoque obvio es tener una tabla separada que describe las transacciones. A continuación, mover dinero de una cuenta bancaria a otra consiste en la simple introducción de una nueva fila en esta tabla. No almacenamos los saldos actuales de cualquiera de las dos cuentas bancarias y en lugar de confiar en que resume todas las filas apropiadas en la tabla de transacciones. Es fácil imaginar que esto sería demasiado trabajo, sin embargo; un banco puede tener millones de transacciones al día y una cuenta bancaria individuo puede tener rápidamente varios miles 'transacciones' asociado a él.

Una serie (todos?) De las tiendas de valores clave será 'hacer retroceder' una acción si los datos subyacentes ha cambiado desde la última vez que lo agarró. Posiblemente esto podría ser utilizado para simular transacciones atómicas, entonces, como usted podría entonces indicar que un campo en particular está bloqueado. Hay algunos problemas obvios con este enfoque.

¿Alguna otra idea? Es muy posible que mi enfoque es simplemente incorrecta y aún no he envuelto mi cerebro alrededor de la nueva forma de pensar.

¿Fue útil?

Solución

Si, tomar su ejemplo, que desea actualizar el valor atómicamente en un solo documento (fila en la terminología relacional), puede hacerlo en CouchDB. Obtendrá un error de conflicto cuando se intenta confirmar el cambio si otro cliente contendientes ha actualizado el mismo documento, ya que lo lea. A continuación, tendrá que leer el nuevo valor, actualizar y volver a intentar el envío de datos. Hay una indeterminada (posiblemente infinita si hay un mucho de la discordia) el número de veces que puede que tenga que repetir este proceso, pero usted está garantizado para tener un documento en la base de datos con un saldo atómicamente actualizado si su cometen cada vez tiene éxito.

Si es necesario actualizar dos balanzas (es decir, una transferencia de una cuenta a otro), entonces es necesario utilizar un documento de transacción por separado (de hecho, otra mesa donde las filas son transacciones) que almacena la cantidad y las dos cuentas (en y fuera). Esta es una práctica común de contabilidad, por cierto. Desde CouchDB calcula vistas sólo cuando sea necesario, en realidad es todavía muy eficiente para calcular la cantidad actual en una cuenta de las transacciones que dan cuenta de que la lista. En CouchDB, se utiliza una función de mapa que emite el número de cuenta como la clave y el importe de la transacción (positivo para entrante, negativo para la salida). Su función reduce simplemente sumar los valores para cada tecla, que emite la misma suma llave y total. A continuación, puede utilizar una vista con el grupo = True para obtener los saldos de las cuentas, cerrado por número de cuenta.

Otros consejos

CouchDB no es adecuado para sistemas transaccionales, ya que no soporta las operaciones de bloqueo y atómicas.

Con el fin de completar una transferencia bancaria debe hacer algunas cosas:

  1. Validar la transacción, asegurando que hay suficientes fondos en la cuenta de origen, que ambas cuentas están abiertas, no bloqueado, y en buen estado, y así sucesivamente
  2. Reducir el saldo de la cuenta de origen
  3. Aumentar el saldo de la cuenta de destino

Si se realizan cambios en el medio alguno de estos pasos el equilibrio o estado de las cuentas, la transacción podría ser válida después de su presentación, que es un gran problema en un sistema de este tipo.

Incluso si se utiliza el enfoque sugerido por encima de donde se inserta un registro de "transferencia" y utiliza un mapa / reducir el fin de calcular el saldo de la cuenta final, que no hay manera de asegurar que no sobregirar la cuenta de origen, porque hay todavía es una condición de carrera entre la comprobación de la saldo de la cuenta de origen y la inserción de la transacción en la que dos transacciones simultáneas podrían añadirse después de comprobar el equilibrio.

Así que ... es la herramienta equivocada para el trabajo. CouchDB es probablemente bueno en muchas cosas, pero esto es algo que en realidad no lo puede hacer.

EDIT: Es probablemente la pena señalar que los bancos reales en el mundo real utilizan consistencia eventual. Si sobregirar su cuenta bancaria durante el tiempo suficiente se obtiene un cargo por sobregiro. Si usted era muy buena que incluso podría ser capaz de retirar dinero de cajeros automáticos dos diferentes casi al mismo tiempo y sobregirar su cuenta porque hay una condición de carrera para comprobar el equilibrio, emitir el dinero, y registrar la transacción. Al depositar un cheque en su cuenta se dan de cabeza el equilibrio, pero en realidad mantener tales fondos por un período de tiempo "por si acaso" la cuenta de origen no tiene realmente el dinero suficiente.

Para dar un ejemplo concreto (porque hay una sorprendente falta de ejemplos correctos en línea): aquí es cómo implementar un " banco atómica de transferencia de saldo "en CouchDB (en gran parte copiado de mi blog sobre el mismo tema: http://blog.codekills.net/2014/03/13/atomic-bank-balance-transfer-with-couchdb/ )

En primer lugar, un breve resumen del problema: ¿cómo puede un sistema bancario que permite dinero para ser transferido de una cuenta a ser diseñados de modo que no hay carrera condiciones que pueden dejar saldos no válidos o sin sentido?

Hay algunas partes de este problema:

En primer lugar: el registro de transacciones. En lugar de almacenar el balance de una cuenta en una sola registro o documento - {"account": "Dave", "balance": 100} - la cuenta de El balance se calcula mediante la suma de todos los créditos y débitos a esa cuenta. Estos créditos y débitos se almacenan en un registro de transacciones, lo que puede tener un aspecto algo como esto: 

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

Y el mapa CouchDB-reducir funciones para calcular el balance podría mirar algo como esto: 

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

Para completar, aquí está la lista de los saldos: 

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

Sin embargo, esto deja la pregunta obvia: ¿cómo se manejan los errores? Qué pasa si alguien trata de hacer una transferencia más grande que su equilibrio?

Con CouchDB (y bases de datos similares) este tipo de lógica de negocio y el error manipulación debe ser implementada a nivel de aplicación. Ingenuamente, una función tal podría tener este aspecto: 

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

Pero notar que si la aplicación se bloquea entre la inserción de la transacción y la comprobación de los saldos actualizados de la base de datos se deja en un inconsistente Estado: el remitente puede quedar con un saldo negativo, y el receptor con dinero que no existía previamente: 

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

¿Cómo se puede arreglar?

Para asegurarse de que el sistema nunca está en un estado incoherente, dos piezas de información necesita ser agregado a cada transacción:

  1. El tiempo se ha creado la transacción (para asegurar que hay un estricta totales de orden de transacciones), y

  2. Un estado -. Si la transacción se ha realizado correctamente

También tendrá que haber dos puntos de vista - uno que devuelve de una cuenta disponible equilibrio (es decir, la suma de todas las transacciones "exitosos"), y otra que devuelve el más antiguo "pendiente" transacción: 

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

}

Lista de transferencias ahora podría ser algo como esto: 

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

A continuación, la aplicación tendrá que tener una función que puede resolver las transacciones realizadas por la comprobación de cada transacción pendiente con el fin de verificar que se trata de válido, entonces la actualización de su estado de "pendiente" a "éxito" o "Rechazado": 

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)

Finalmente, el código de la aplicación para correctamente realizar una transferencia: 

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 par de notas:

  • En aras de la brevedad, esta implementación específica asume una cierta cantidad de atomicidad en un mapa de CouchDB-a reducir. Actualización del código por lo que no se basa en esa suposición se deja como ejercicio para el lector.

  • Master / replicación maestro o documento de sincronización de CouchDB no se han tenido en consideración. Maestro de replicación / maestra y sincronización hacen que este problema significativamente más difícil.

  • En un sistema real, utilizando time() podría dar lugar a colisiones, por lo que usar algo con un poco más de la entropía podría ser una buena idea; tal vez "%s-%s" %(time(), uuid()), o el uso de _id del documento en el ordenamiento. Incluyendo el tiempo no es estrictamente necesario, pero ayuda a mantener una lógica si varias peticiones vienen en aba cabo al mismo tiempo.

BerkeleyDB y LMDB son ambas tiendas clave-valor con soporte para transacciones ACID. En BDB txns son opcionales, mientras que LMDB sólo funciona de forma transaccional.

  

Un típico argumento en contra de ellos es que por lo general no permiten transacciones atómicas a través de múltiples filas o tablas. Me pregunto si hay un enfoque general sería resolvería este problema.

Una gran cantidad de almacenes de datos modernos no son compatibles con las actualizaciones atómicas múltiples claves (transacciones) fuera de la caja, pero la mayoría de ellos ofrecen primitivas, que le permiten construir las transacciones ACID del lado del cliente.

Si un almacén de datos soporta por instrucción atómica llave y de comparación y de intercambio o la operación de prueba-y-juego, entonces es suficiente para implementar las transacciones serializables. Por ejemplo, este enfoque se utiliza en de Google percolador y en CockroachDB base de datos.

En mi blog he creado el visualización paso a paso de serializable operaciones de cruce de fragmento del lado del cliente , describen los casos de uso principales y enlaces proporcionados a las variantes del algoritmo. Espero que le ayudará a entender cómo ponerlas en práctica para la tienda que los datos.

Entre los almacenes de datos que soportan por instrucción atómica llave y CAS son:

  • Cassandra con transacciones ligeros
  • Riak con cubos consistentes
  • RethinkDB
  • ZooKeeper
  • ETDC
  • HBase
  • DynamoDB
  • MongoDB

Por cierto, si estás bien con lectura confirmada nivel de aislamiento, entonces tiene sentido para echar un vistazo en el transacciones RAMP por Peter Bailis. También pueden ser implementadas por el mismo conjunto de almacenes de datos.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top