transações atômicas em lojas de valor-chave

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

Pergunta

Por favor, desculpe os erros na terminologia. Em particular, eu estou usando termos de banco de dados relacionais.

Há uma série de lojas de chave-valor persistentes, incluindo CouchDB e Cassandra , junto com a abundância de outros projetos.

Um argumento típico contra eles é que eles geralmente não permitir transações atômicas em várias linhas ou tabelas. Gostaria de saber se há uma abordagem geral que iria resolver esta questão.

Tomemos por exemplo a situação de um conjunto de contas bancárias. Como podemos mover o dinheiro de uma conta bancária para outra? Se cada conta bancária é uma linha, queremos atualizar duas fileiras como parte da mesma transação, reduzindo o valor em um e aumentando o valor em outra.

Uma abordagem óbvia é ter uma tabela separada que descreve transações. Então, movendo-se dinheiro de uma conta bancária para outra consiste em simplesmente inserindo uma nova linha na tabela. Nós não guardamos os saldos atuais de qualquer uma das duas contas bancárias, preferindo recorrer a soma de todas as linhas apropriadas na tabela de transações. É fácil imaginar que isso seria muito trabalho, no entanto; um banco pode ter milhões de transações por dia e uma conta bancária indivíduo pode rapidamente ter vários milhares de 'operações' associados a ela.

Um número (todos?) De lojas de chave-valor será 'para trás roll' uma acção se os dados subjacentes mudou desde a última vez que o agarrou. Possivelmente isso pode ser usado para simular transações atômicas, então, como você poderia, então, indicar que um campo específico está bloqueado. Existem alguns problemas óbvios com esta abordagem.

Quaisquer outras ideias? É inteiramente possível que a minha abordagem é simplesmente incorreto e eu ainda não ter embrulhado meu cérebro em torno da nova maneira de pensar.

Foi útil?

Solução

Se, tendo o seu exemplo, você quer atualizar atomicamente o valor em um única documento (linha na terminologia relacional), você pode fazê-lo em CouchDB. Você vai ter um erro de conflito quando você tenta confirmar a alteração se um outro cliente contenda actualiza o mesmo documento desde que você lê-lo. Você terá então a ler o novo valor, atualização e re-experimentar a cometer. Há uma indeterminado (possivelmente infinito se há um muito de contenção) o número de vezes que você pode ter que repetir este processo, mas você está garantido para ter um documento no banco de dados com um saldo atomicamente atualizado se seu cometer nunca sucede.

Se você precisa atualizar dois saldos (ou seja, uma transferência de uma conta para um outro), então você precisa usar um documento de transação separada (efetivamente outra tabela onde as linhas são transações) que armazena a quantidade e as duas contas (em e fora). Esta é uma prática de contabilidade comum, pelo caminho. Desde CouchDB calcula vistas apenas como necessário, é realmente ainda muito eficiente para calcular o valor atual em uma conta de transações que lista que conta. Em CouchDB, você usaria uma função de mapa que emitia o número da conta como chave eo valor da transação (positivo para entrada, negativo para saída). Sua função reduzir simplesmente somar os valores para cada tecla, emitindo a mesma chave e soma total. Você poderia, então, usar uma exibição com o grupo = True para obter os saldos de conta, fechado pelo número de conta.

Outras dicas

CouchDB não é adequado para sistemas transacionais porque ele não suporta bloqueio e operações atômicas.

Para completar uma transferência bancária você deve fazer algumas coisas:

  1. Validar a transação, assegurando existem fundos suficientes na conta de origem, que ambas as contas estão abertas, não trancada, e em boa posição, e assim por diante
  2. Diminuir o saldo da conta de origem
  3. Aumentar o saldo da conta de destino

Se forem feitas alterações entre qualquer uma dessas etapas o equilíbrio ou estado das contas, a transação pode se tornar inválida após ter sido apresentado, que é um grande problema em um sistema desse tipo.

Mesmo se você usar a abordagem sugerida acima de onde você inserir um registro de "transferência" e usar um mapa / reduzir a vista para calcular o saldo final da conta, você não tem nenhuma maneira de garantir que você não exagerar a conta de origem porque há ainda é uma condição de corrida entre a verificação do saldo da conta de origem e inserir a transação, onde duas operações pode simultânea ser adicionados após a verificação do equilíbrio.

Então ... é a ferramenta errada para o trabalho. CouchDB é provavelmente bom em um monte de coisas, mas isso é algo que realmente não pode fazer.

EDIT: É provavelmente importante notar que os bancos de reais no uso mundo real consistência eventual. Se você exagerar sua conta bancária por tempo suficiente você ter uma taxa de cheque especial. Se você fosse muito bom que você pode até ser capaz de retirar dinheiro de dois caixas eletrônicos diferentes quase ao mesmo tempo e exagerar sua conta porque há uma condição de corrida para verificar o saldo, emitir o dinheiro, e registrar a transação. Quando você depositar um cheque em sua conta que bata com o equilíbrio, mas realmente manter esses fundos por um período de tempo "just in case" da conta de origem realmente não tem dinheiro suficiente.

Para fornecer um exemplo concreto (porque há uma surpreendente falta de exemplos corretos on-line): aqui está como implementar um " banco atômica transferência de saldo "em CouchDB (copiado em grande parte do meu post sobre o mesmo assunto: http://blog.codekills.net/2014/03/13/atomic-bank-balance-transfer-with-couchdb/ )

Primeiro, uma breve recapitulação do problema: como pode um sistema bancário que permite dinheiro a ser transferido entre contas ser concebidos de modo que não há nenhuma raça condições que poderiam deixar saldos inválidos ou sem sentido?

Existem algumas peças para este problema:

Primeiro: o log de transações. Em vez de armazenar o equilíbrio de uma conta em um único gravar ou documento - {"account": "Dave", "balance": 100} - da conta equilíbrio é calculado somando-se todos os créditos e débitos nessa conta. Esses créditos e débitos são armazenados em um log de transações, o que pode parecer algo como isto: 

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

E o CouchDB Map-Reduce funções para calcular o saldo poderia olhar algo como isto: 

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, aqui está a lista de saldos: 

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

Mas isso deixa a pergunta óbvia: como são erros tratado? O que acontece se Alguém tenta fazer uma transferência maior do que o seu equilíbrio?

Com CouchDB (e bases de dados similares) este tipo de lógica de negócios e erro manejo deve ser implementado no nível do aplicativo. Ingènua, tal função de um pode ter esta aparência: 

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

Mas note que se a aplicação trava entre a inserção da transação e verificar os saldos atualizados do banco de dados será deixado em um inconsistente Estado: o remetente pode ficar com um saldo negativo, eo destinatário com dinheiro que não existia anteriormente: 

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

Como isso pode ser corrigido?

Para garantir que o sistema nunca está em um estado inconsistente, dois pedaços de necessidade de informações a ser adicionado a cada transação:

  1. O tempo da transação foi criado (para garantir que há um estrita ordenação total de transações), e

  2. Um estado -. Ou não a transação foi bem sucedida

Há também terá de ser dois pontos de vista - uma que retorna de uma conta disponível equilíbrio (ou seja, a soma de todas as transações "bem sucedidos"), e outra que retorna a mais antiga "pendente" transação: 

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 transferências pode agora ser algo como isto: 

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

Em seguida, a aplicação terá de ter uma função que pode resolver transações, verificando cada transação pendente, a fim de verificar se é válida, em seguida, atualizar seu status de "pendente" para "sucesso" ou "Rejeitado": 

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, o código do aplicativo para corretamente realizar uma transferência: 

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

Um par de notas:

  • Por razões de brevidade, esta implementação específica assume uma certa quantidade de atomicity no do CouchDB Map-Reduce. Atualizando o código para que ele não depende de essa suposição é deixado como um exercício para o leitor.

  • Mestre replicação / master ou documento do CouchDB Sync não foram levados em consideração. Mestre replicação / master e sincronizar fazer este problema significativamente mais difícil.

  • Em um sistema real, usando time() pode resultar em colisões, portanto, usando algo com um pouco mais de entropia pode ser uma boa ideia; talvez "%s-%s" %(time(), uuid()), ou usando _id do documento na ordenação. Incluindo o tempo não é estritamente necessário, mas ajuda a manter uma lógica se várias solicitações vêm em abpara fora ao mesmo tempo.

BerkeleyDB e LMDB são ambas as lojas de valor-chave com suporte para transações ACID. Em BDB txns são opcionais, enquanto LMDB só funciona transactionally.

Um argumento típico contra eles é que eles geralmente não permitir transações atômicas em várias linhas ou tabelas. Gostaria de saber se há uma abordagem geral que iria resolver esta questão.

Um monte de lojas de dados modernos não suportam atualizações multi-chave atômicas (transações) fora da caixa, mas a maioria deles fornecem primitivas que permitem construir as transações do lado do cliente ACID.

Se um armazenamento de dados apoios por transação atômica chave e compará-and-swap ou test-and-set operação, então é suficiente para implementar transações serializáveis. Por exemplo, esta abordagem é usada em Percolator do Google em banco de dados CockroachDB .

No meu blog eu criei o href="http://rystsov.info/2016/03/02/cross-shard-txs.html" visualização passo-a-passo de serializável cruz caco transações do lado do cliente , descreveu os principais casos de uso e links fornecidos para as variantes do algoritmo. Espero que ele vai ajudar você a entender como implementá-los para você armazenamento de dados.

Entre os armazenamentos de dados que suporte por transação atômica chave e CAS são:

  • Cassandra com transações leves
  • Riak com baldes consistentes
  • RethinkDB
  • ZooKeeper
  • ETDC
  • HBase
  • DynamoDB
  • MongoDB

A propósito, se você está bem com Leia nível de isolamento Committed então faz sentido para dar uma olhada em transações RAMP por Peter Bailis. Eles podem também ser implementado para o mesmo conjunto de armazenamentos de dados.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top