Атомарные транзакции в хранилищах ключ-значение

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

Вопрос

Пожалуйста, извините за любые ошибки в терминологии.В частности, я использую термины реляционной базы данных.

Существует ряд постоянных хранилищ значений ключей, в том числе CouchDB и Кассандра, наряду с множеством других проектов.

Типичным аргументом против них является то, что они обычно не разрешают атомарные транзакции между несколькими строками или таблицами.Интересно, существует ли общий подход, который мог бы решить эту проблему.

Возьмем, к примеру, ситуацию с набором банковских счетов.Как мы переводим деньги с одного банковского счета на другой?Если каждый банковский счет представляет собой строку, мы хотим обновить две строки как часть одной транзакции, уменьшив значение в одной и увеличив значение в другой.

Один из очевидных подходов заключается в создании отдельной таблицы, описывающей транзакции.Затем перевод денег с одного банковского счета на другой заключается в простой вставке новой строки в эту таблицу.Мы не храним текущие остатки ни на одном из двух банковских счетов и вместо этого полагаемся на суммирование всех соответствующих строк в таблице транзакций.Однако легко представить, что это было бы слишком большой работой;банк может проводить миллионы транзакций в день, а с индивидуальным банковским счетом может быстро быть связано несколько тысяч "транзакций".

Некоторое количество (все?) хранилищ значений ключей "откатит" действие, если базовые данные изменились с момента их последнего извлечения.Возможно, это можно было бы использовать для имитации атомарных транзакций, поскольку тогда вы могли бы указать, что определенное поле заблокировано.Есть несколько очевидных проблем с таким подходом.

Есть еще какие-нибудь идеи?Вполне возможно, что мой подход просто неверен, и я еще не освоил свой мозг с новым способом мышления.

Это было полезно?

Решение

Если, взяв ваш пример, вы хотите атомарно обновить значение в одинокий document (строка в реляционной терминологии), вы можете сделать это в CouchDB.Вы получите сообщение об ошибке конфликта при попытке зафиксировать изменение, если другой конкурирующий клиент обновил тот же документ с тех пор, как вы его прочитали.Затем вам нужно будет прочитать новое значение, обновить и повторно выполнить фиксацию.Существует неопределенное (возможно , бесконечное , если существует много из-за разногласий) количество раз, возможно, вам придется повторить этот процесс, но вы гарантированно получите документ в базе данных с атомарно обновленным балансом, если ваша фиксация когда-либо завершится успешно.

Если вам нужно обновить два баланса (т.е.перевод с одного счета на другой), затем вам нужно использовать отдельный документ транзакции (фактически другую таблицу, строки которой представляют собой транзакции), в которой хранится сумма и два счета (входящий и исходящий).Кстати, это обычная бухгалтерская практика.Поскольку CouchDB вычисляет просмотры только по мере необходимости, на самом деле все еще очень эффективно вычислять текущую сумму на счете из транзакций, в которых указана эта учетная запись.В CouchDB вы бы использовали функцию map, которая выдает номер счета в качестве ключа и сумму транзакции (положительную для входящей, отрицательную для исходящей).Ваша функция reduce просто суммировала бы значения для каждого ключа, выдавая один и тот же ключ и общую сумму.Затем вы могли бы использовать представление с group= True для получения остатков на счетах по номеру счета.

Другие советы

CouchDB не подходит для транзакционных систем, поскольку не поддерживает блокировку и атомарные операции.

Для того чтобы завершить банковский перевод, вы должны выполнить несколько действий:

  1. Подтвердите транзакцию, убедившись, что на исходном счете достаточно средств, что оба счета открыты, не заблокированы и находятся в хорошем состоянии, и так далее
  2. Уменьшите баланс исходного счета
  3. Увеличьте баланс целевого счета

Если в промежутке между любым из этих шагов будут внесены изменения в баланс или статус счетов, транзакция может стать недействительной после ее отправки, что является большой проблемой в системе такого рода.

Даже если вы используете подход, предложенный выше, когда вы вставляете запись "переноса" и используете отображение / уменьшение для вычисления окончательного баланса счета, у вас нет способа гарантировать, что вы не перерасходуете исходный счет, потому что все еще существует условие гонки между проверкой баланса исходного счета и вставкой транзакции, когда две транзакции могут быть добавлены одновременно после проверки баланса.

Итак ...это неподходящий инструмент для этой работы.CouchDB, вероятно, хорош во многих вещах, но это то, чего он действительно не может сделать.

Редактировать:Вероятно, стоит отметить, что реальные банки в реальном мире используют конечную согласованность.Если вы слишком долго пополняете свой банковский счет, вы получаете комиссию за овердрафт.Если бы вы были очень хороши, вы могли бы даже снять деньги в двух разных банкоматах почти одновременно и пополнить свой счет, потому что существует условие гонки для проверки баланса, выдачи денег и записи транзакции.Когда вы вносите чек на свой счет, они увеличивают баланс, но фактически удерживают эти средства в течение определенного периода времени "на всякий случай", если на исходном счете действительно недостаточно денег.

Чтобы привести конкретный пример (потому что в Интернете на удивление не хватает правильных примеров):вот как реализовать "перевод баланса atomic bank" в CouchDB (в основном скопировано из моего поста в блоге на ту же тему: http://blog.codekills.net/2014/03/13/atomic-bank-balance-transfer-with-couchdb/)

Во-первых, краткое изложение проблемы:как может банковская система, которая позволяет переводить деньги между счетами, быть спроектирована таким образом, чтобы не было гонки условий, которые могли бы оставить недействительные или бессмысленные остатки?

Эта проблема состоит из нескольких частей:

Первый:журнал транзакций.Вместо хранения баланса учетной записи в одном файле запись или документ — {"account": "Dave", "balance": 100} — учетная запись баланс рассчитывается путем суммирования всех зачислений и дебетований на эту учетную запись.Эти зачисления и списания хранятся в журнале транзакций, который может выглядеть примерно так:

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

И функции CouchDB map-reduce для вычисления баланса могли бы выглядеть примерно так:

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

Для полноты картины, вот список остатков:

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

Но это оставляет очевидный вопрос:как обрабатываются ошибки?Что произойдет, если кто-то попытается перевести сумму, превышающую его баланс?

С CouchDB (и подобными базами данных) такого рода бизнес-логика и ошибки обработка должна быть реализована на уровне приложения.Наивно, такая функция может выглядеть следующим образом:

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

Но обратите внимание, что если приложение аварийно завершает работу между вставкой сделки и проверять обновление остатков БД останется в несогласованном состояние:отправитель может остаться с отрицательным балансом, а получатель - с деньгами, которых ранее не существовало:

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

Как это можно исправить?

Чтобы убедиться, что система никогда не находится в несогласованном состоянии, к каждой транзакции необходимо добавлять две части информации:

  1. Время создания транзакции (для обеспечения наличия строгий полный порядок сделок), и

  2. Статус — была ли транзакция успешной или нет.

Также должно быть два представления — одно, которое возвращает доступный баланс учетной записи (т. Е. сумму всех "успешных" транзакций), и другое, которое возвращает самую старую "ожидающую" транзакцию:

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

}

Список переводов теперь может выглядеть примерно так:

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

Далее, приложению потребуется функция, которая может разрешать транзакции, проверяя каждую ожидающую транзакцию, чтобы убедиться, что она действительна, затем обновляя ее статус с "ожидающая" либо на "успешная", либо "отклонена":

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)

Наконец, код приложения для правильно выполнение перевода:

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

Пара заметок:

  • Для краткости, эта конкретная реализация предполагает некоторую степень атомарности в CouchDB map-reduce.Обновление кода, чтобы он не полагался на это предположение оставляем в качестве упражнения для читателя.

  • Репликация Master / master или синхронизация документов CouchDB не принимались во внимание .Репликация и синхронизация Master / master делают эту проблему значительно более сложной.

  • В реальной системе, используя time() может привести к столкновениям, поэтому использование что-то с немного большей энтропией может быть хорошей идеей;может быть "%s-%s" %(time(), uuid()), или используя документ _id в упорядочивании.Указание времени не является строго необходимым, но это помогает поддерживать логическую если несколько запросов поступают примерно в одно и то же время.

BerkeleyDB и LMDB являются хранилищами значений ключей с поддержкой транзакций ACID.В BDB txns являются необязательными, в то время как LMDB работает только транзакционно.

Типичным аргументом против них является то, что они обычно не разрешают атомарные транзакции между несколькими строками или таблицами.Интересно, существует ли общий подход, который мог бы решить эту проблему.

Многие современные хранилища данных не поддерживают готовые атомарные обновления с несколькими ключами (транзакции), но большинство из них предоставляют примитивы, которые позволяют создавать транзакции на стороне клиента ACID.

Если хранилище данных поддерживает линеаризуемость для каждого ключа и операции сравнения и замены или тестирования и установки, то этого достаточно для реализации сериализуемых транзакций.Например, этот подход используется в Перколятор Google и в Тараканdb База данных.

В своем блоге я создал пошаговая визуализация сериализуемых транзакций на стороне клиента с перекрестным сегментом, описал основные варианты использования и предоставил ссылки на варианты алгоритма.Я надеюсь, что это поможет вам понять, как реализовать их для вашего хранилища данных.

Среди хранилищ данных, которые поддерживают линеаризуемость по ключу и CAS, являются:

  • Кассандра с легкими транзакциями
  • Riak с постоянными объемами
  • Переосмыслить DB
  • Смотритель зоопарка
  • Etdc
  • HBase ( База данных )
  • DynamoDB ( Динамический модуль )
  • MongoDB

Кстати, если вас устраивает уровень изоляции Read Committed, то имеет смысл взглянуть на НАРАСТАЮЩИЕ транзакции автор: Питер Бейлис.Они также могут быть реализованы для одного и того же набора хранилищ данных.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top