С первого дня, когда я начал понимать, как работает большинство финансовых процессов, мучительное «Так жить нельзя!» крутилось в моей голове.
Но теперь концепция того, как можно попытаться жить, похоже, обрела форму.
Вам нужна строгая согласованность на N репликах без линейной потери скорости? Хранить состояния в блокчейнах? 
Введение
Данная статья представляет собой «сухой остаток» размышлений о том, как подойти к решению некоторых неизбежных проблем в системе распределенного хранения и изменения состояний, в частности финансовой обработки.Статья не преследует цели «отлить в гранит» какую-то одну точку зрения, а скорее для обмена мнениями и конструктивной критики.
Сразу уточню: описанные подходы работают в соответствии с теоремой CAP, не позволяют данным перемещаться со скоростью, превышающей скорость света, и не опровергают никаких других фундаментальных законов природы.
Проблема с обработкой
Финансовый процессинг «с высоты птичьего полета» представляет собой структуру данных, хранящую набор состояний (балансов счетов) и историю изменения этих состояний.К этой структуре «привязывается» программа, определяющая логику, в соответствии с которой производятся изменения состояний.
Это не кажется особенно трудным.
Но процессинг необходим для того, чтобы иметь возможность осуществлять транзакции максимально быстро, поскольку его основным пользователем является не Алиса, отправившая Бобу 10 рублей, а интернет-магазины с тысячами и десятками тысяч клиентов, которые в случае падения конверсии должны до аварии или тормоза, не раздумывая пойду к конкурентам.
(На самом деле, это, по-видимому, основная причина, по которой частный процессинг не может поглотить Биткойн).
Для примерного понимания существующих потребностей можно начать с отчетов VISA о том, как они готовятся к новогодним пикам .
Но как только мы попытаемся разделить нагрузку, сделать обработку распределенной (каждый узел имеет копию данных и возможность выполнять транзакции), мы столкнемся с проблемой непротиворечивости данных.
Какова реальная проблема? При создании базы данных со многими репликами всегда возникает вопрос, как разрешить возникающую неоднозначность (несогласованность) данных, когда данные уже были изменены на некоторых узлах системы, но изменения еще не «дошли» до других.
узлы.
При параллельном потоке изменений система, состоящая более чем из одного узла, просто не может постоянно находиться в согласованном состоянии (если не использовать механизмы, описанные ниже).
Существующая терминология определяет несколько типов согласованности:
- Строгая согласованность – после изменения данных обновленная версия сразу доступна на всех узлах системы.
- Слабая согласованность — система не гарантирует, что последующие обращения к данным вернут обновленное значение.
Прежде чем будет возвращено обновленное значение, должен быть выполнен ряд условий.
Период между обновлением и моментом, в котором каждый наблюдатель гарантированно всегда будет видеть обновленное значение, называется окном несоответствия.
- Итоговая непротиворечивость — это частный случай слабой непротиворечивости.
Система гарантирует, что при отсутствии новых обновлений данных все запросы в конечном итоге будут возвращать последнее обновленное значение.
При отсутствии сбоев максимальный размер окна несогласованности можно определить на основе таких факторов, как задержка связи, загрузка системы и количество реплик по схеме репликации.
Наиболее популярной системой, реализующей итоговую согласованность, является DNS. Обновленная запись распространяется в соответствии с параметрами конфигурации и настройками интервала кэширования.
Со временем все клиенты увидят обновление.
Если мы пренебрегаем согласованностью, мы получим уязвимость, называемую «состояние гонки».
На практике это эксплуатируется как «двойная трата» (Double Spending — самый очевидный способ, но далеко не единственный), когда на одни и те же деньги совершаются две покупки, если время между покупками меньше времени репликации.
Например тебе не нужно далеко ходить .
Как с этим справиться? Современные распределенные системы хранения данных поддерживают разные условия, при которых смена состояния (коммит) считается успешной, то есть одно и то же состояние доступно на всех узлах сети и признается ими корректным.
При правильном «приготовлении» эти условия могут значительно облегчить жизнь.
Например, cassandra db поддерживает следующие режимы:
- общий коммит — изменения прошли без ошибок на всех узлах
- коммит по кворуму — на большинстве нод изменения произошли без ошибок
- коммит по количеству успешных — на N узлах изменения произошли без ошибок
- Он плохо масштабируется, поскольку соотношение времени, необходимого для успешного коммита, линейно (в лучшем случае) зависит от количества узлов в кластере.
- На всех узлах обрабатывается одна и та же транзакция, что не решает проблему распределения нагрузки.
Частично из-за этого большая часть сегодняшних успешных (т.е.
крупных и растущих) переработок Очень страдают в районе базы.
Задача
Из всего написанного мы можем вывести свойства, которыми должна обладать распределенная структура, чтобы квалифицироваться как часть современной обработки:- Невозможность состояния гонки при проведении транзакций
- Строгая последовательность при фиксации баланса во время транзакции
- Равномерное распределение вычислительной нагрузки
- Увеличение узлов с влиянием на скорость оптимально, чем линейное
- Нет единой точки отказа
Операции по списанию средств в ней осуществляют в 95-99% случаев живые люди, которым не особо нужна немедленная готовность системы к следующей транзакции (10-60с).
Более того, быстрый поток транзакций на списание иногда блокируется намеренно, так как это признак быстрого вывода в случае кражи (когда существует ограничение на размер одной транзакции).
Если вернуться к примеру интернет-магазина с тысячами клиентов, то каждый отдельный клиент платит не часто.
На основе этого свойства мы можем описать систему, которая позволяет нам использовать время после транзакции для окна несогласованности.
То есть после каждой транзакции с конкретного аккаунта у нас будет некоторый промежуток времени Т, который будет меньше или равен скорости репликации данных в системе и в течение которого транзакции с этого и только этого аккаунта будут невозможны.
, но не более того, что повлияет на пользовательский опыт 95-99% клиентов.
Сначала несколько терминов.
Понятия и определения
Необходимо для удобства восприятия.
- Транзакция – изменение статуса счета.
То же, что перевод.
- Аккаунт — это некий идентификатор, с которым связано определенное состояние (баланс), изменяемое транзакциями.
- Цепочка – цепочка транзакций по списанию средств, связанных с идентификатором.
Он структурирован так же, как классический блокчейн.
Технически это журнал транзакций по списанию, где в каждой последующей транзакции присутствует хеш-сумма предыдущих; такое соединение обеспечивает два важных свойства
- Проверенная последовательность транзакций
- Контроль целостности (не путать с контролем подлинности!).
Если какая-либо из транзакций была изменена, это сразу станет заметно посредством хеш-проверки.
- Запрос транзакции — это структура данных, содержащая информацию, необходимую для проведения транзакции (кому и в каком объеме), но в соответствии с которой транзакция еще не была проведена и какое-то решение о корректности еще не принято.
- Узел — это программа, хранящая реплики всех цепочек в системе, обеспечивающая актуальность реплики, обрабатывающая транзакции, создающая новые блоки (транзакции и маршрутизирующая запросы на транзакции.
Набор узлов образует сеть, или систему.
- Система — это набор узлов, которые образуют сеть и получают на вход запросы транзакций.
Система работает в доверенной среде: узлы доверяют друг другу, то есть никак не решают византийскую проблему.
Как защитить себя от состояния гонки
Сначала рассмотрим частный случай, когда система находится в согласованном состоянии, то есть цепочка для атакующего аккаунта одинакова на всех узлах в момент создания двух конфликтующих запросов на транзакции на разных узлах системы.Чтобы исключить возможность одновременной обработки запроса транзакции на двух разных узлах, введем маршрутизацию в сеть, создаваемую узлами.
Причём таким образом, чтобы 2 конфликтующих запроса на транзакцию не могли быть обработаны и включены в цепочку на 2 разных узлах.
Как это сделать? Чтобы система не имела единой точки отказа и масштабировалась по горизонтали (а также имела кучу других приятных свойств), разумно сделать маршрутизацию на основе хорошо изученного протокола DHT — Kademlia. Что такое ДГТ и почему он здесь? Если коротко, то DHT — это пространство значений (например, всех возможных значений хеш-функции md5), которое поровну поделено между узлами сети.
На картинке показан пример пространства значений 0-1000, которое распределено между узлами A, B, C, D, E, в данном случае не равномерно.
В сети DHT узлы содержат информацию о N ближайших соседних узлах, и если вам необходимо найти конкретный хеш из разделенного пространства значений, то, отправив запрос в такую сеть, вы сможете сравнительно быстро найти узел, ответственный за это.
часть пространства значений, в которой находится искомый хэш.
Чтобы понять насколько это быстро, вот 2 графика, показывающие зависимость количества хопов при поиске классической реализации Kademlia: 
И оптимизировано: 
Поскольку количество прыжков маршрутизации растет логарифмически, сеть имеет выдающийся потенциал горизонтального масштабирования.
Кстати, DHT используется в Cassandra DB и Dynamo от Amazon, но с важным отличием: там он используется только для навигации по шардированным данным, а в случае изменения реплицируемых данных используются методы, описанные во введении.
Как я могу быть уверен, что при изменении данных в зеркальных репликах я смогу предотвратить параллельное изменение данных на разных репликах? Для этого мы прочитаем хэш последней транзакции в цепочке и будем использовать его как значение из пространства имен, которое разделено между узлами сети.
Таким образом, на обоих узлах, где были созданы конфликтующие запросы транзакций, результирующее значение будет одинаковым (поскольку цепочка соответствует узлам в согласованном состоянии).
Далее, используя это значение в функции DHTsearch, наши запросы будут «направлены» на один и только один узел, на котором запросы будут обрабатываться последовательно.
Но это случай изначальной консистенции, которая в реальном мире существует только на бумаге :) Теперь рассмотрим общий случай, когда система находится в несогласованном состоянии, то есть количество транзакций в цепочке конкретного аккаунта может отличаться от узла к узлу.
Поэтому возможно, что 2 противоречивые транзакции будут получены на узлах N1 и N2, где цепочки имеют разную степень релевантности (разные недавние транзакции, от которых рассчитывается хеш), из-за чего запросы на транзакции будут казаться «направленными».
к узлам N3 и N4 соответственно, где они будут обработаны, что приведет к «разветвлению» цепочки, чего допускать нельзя.
Если рассматривать эту проблему подробно, то ее не существует, так как мы имеем однозначную связь: .
> транзакция > узел обработки > следующая транзакция > .
что для разных транзакций одной цепочки можно изобразить так: р – маршрут (значение из общего пространства имен) Н – узел, на котором обрабатывается следующая транзакция Т – транзакция хеш(T0)=R1 – пункт назначения или маршрут к узлу, где будет обрабатываться T1 R1 -> Нх - нацелиться на узел Nx -> хэш (T1) — создать новый маршрут, если Т1 успешно обработан и включен в цепочку 
Из этого следует, что если запрос транзакции поступает на «отстающий» узел, где имеется устаревшая версия цепочки, то этот запрос транзакции будет «направлен» на узел, где уже создана и сохранена более свежая транзакция.
, т.е.
хеши последних транзакций не будут точно совпадать, и запрос будет отклонен.
Цепь не будет разветвляться.
Лучше зайти сюда на чай.
Строгое соблюдение баланса
Был описан метод безопасного изменения состояния, но этого недостаточно для работы обработки; нам необходимо однозначное знание того, из какого состояния мы переходим в какое:- Локальная однозначность – на узле, на котором обрабатывается транзакция, должна быть возможность однозначно «зафиксировать баланс» и исключить возможность повторного использования средств.
- Согласованность поступивших средств - исключение возможности двойного использования поступивших средств в случае несоответствия данных о поступлении средств на узлах при проведении двух последовательных транзакций (которые в соответствии с маршрутизацией будут выполняться на разных узлах, а контроль через маршрутизируемость одной цепи никоим образом не гарантирует согласованность других, маршрутизируемых независимо).
Как все это достигается, когда идет передача из IDa и IDb в IDc, а потом IDc делает передачу в IDd? Исходное состояние (здесь для простоты оно представлено в виде таблицы, где каждая транзакция, добавляемая в цепочку одного из аккаунтов, представляет собой добавленную внизу строку):
| Хэш предыдущий | ИДЕНТИФИКАТОР отправитель | ИДЕНТИФИКАТОР получатель | Перевод | Баланс | Подтверждение | Контроль сумма входящий | Хэш предыдущего подтвержденный |
|---|---|---|---|---|---|---|---|
| Ба | Ида | ИДЦ | Ха | Да | НУЛЕВОЙ | Ха | НУЛЕВОЙ |
| Бб | IDb | ИДЦ | Хб | Ыб | НУЛЕВОЙ | Hb | НУЛЕВОЙ |
Все последующие входящие переводы в этом понимании никак не включаются в «связанный» перевод и существуют только как исходящие переводы по цепочкам счетов отправителей.
Подтверждения обработки - поле, в котором указывается, были ли использованы средства данной транзакции, то есть если при переводе A и B на C, то в этих переводах это значение устанавливается в NULL, а после того, как C переходит на D, то это значение для A и B будет изменено на хеш транзакции, в которой принимали участие эти средства (C => D).
В поле «Хеш предыдущей подтвержденной» для каждой цепочки А и Б будет введен хеш от предыдущей подтвержденной транзакции в этих цепочках, у которых поле «подтверждение обработки» не равно нулю соответственно.
(почему это описано ниже) Баланс в C=> D рассчитывается в следующие этапы:
- ВЫБЕРИТЕ `Перевод` ИЗ транзакций, ГДЕ `Идентификатор получателя` = IDc И `подтверждение обработки` = NULL; Таким образом мы получаем сумму всех входящих средств, которые были переведены за период времени с момента предыдущего исходящего перевода из IDc.
- Мы рассчитываем общий баланс, складывая значение, полученное на шаге 1, со значением баланса, записанным в последнем переводе IDc.
- Проверяем целостность цепочек отправителей и соответствие запрошенного перевода всем необходимым условиям, как минимум, чтобы результат не был отрицательным.
Вычитаем перевод из суммы, полученной на шаге 2.
- Если все ок, то записываем в таблицу еще один перевод, и для всех найденных на шаге 1 задаем хеш этого перевода в поле «подтверждение обработки» и «хеш предыдущего подтвержденного».
Yc — баланс IDc сразу после этого перевода.
Когда мы говорим о распределенной системе, возможно, что данные о входящих переводах на узле, на котором будет выполняться следующая передача, будут несогласованы с данными от узла, на котором была выполнена предыдущая передача: «подтверждение обработки».
Поле также будет установлено в NULL для переводов, которые использовались для расчета баланса в предыдущем переводе, в результате эти переводы могут быть зачислены повторно, чего допускать нельзя.
Для обнаружения таких условий используется поле «входящая контрольная сумма», в котором хранится хэш хэшей всех входящих переводов, которые использовались в рамках исходящей обработки.
Используя это значение, перед обработкой нового перевода N можно проверить согласованность входящих переводов для перевода N-1, собрав их (по значению из поля «подтверждение обработки»), вычислив их хеш HASH(CONCAT(INCOME_BLOCKS)) и сравниваем его с хешем в поле «Входящая контрольная сумма» в передаче N-1. В случае несоответствия запрос на перевод отклоняется.
Поскольку описанный метод проверяет целостность последних входящих переводов, существует вероятность того, что из-за ошибочного (или намеренного) обнуления поля подтверждения в каком-то старом входящем переводе, который использовался для расчета баланса когда-то в прошлом, это старый входящий перевод при обработке нового перевода может быть засчитан получателем повторно, чего допускать нельзя.
Чтобы предотвратить такую ситуацию, используется поле «предыдущий подтвержденный хеш», где задается хеш предыдущего перевода с ненулевым подтверждением, рассчитанный по значению из этого поля («предыдущий подтвержденный хеш»), таким образом мы создаем двойной связность в цепочке отправителя по состоянию: по факту передачи и факту получения, т.е.
использования получателем.
И если из-за обнуления (что разрушит одно из соединений) подтверждения этот перевод «всплывет» при подсчете входящих, то он будет отклонен на этапе контроля целостности цепочки отправителя.
В результате окончательный перевод IDc => IDd будет выглядеть так:
| Хэш предыдущий | ИДЕНТИФИКАТОР отправитель | ИДЕНТИФИКАТОР получатель | Перевод | Баланс | Подтверждение | Контроль сумма входящий | Хэш предыдущего подтвержденный |
|---|---|---|---|---|---|---|---|
| Ба | Ида | ИДЦ | Ха | Да | ХЕШ(LAST_C_BLOCK) | Ха | ХЕШ(LAST_CONFIRMD_A_BLOCK) |
| Бб | IDb | ИДЦ | Хб | Ыб | ХЕШ(LAST_C_BLOCK) | Hb | ХЕШ(LAST_CONFIRMD_A_BLOCK) |
| До н.
э |
ИДЦ | IDd | Хс | Yc | НУЛЕВОЙ | ХЭШ(CONCAT(INCOME_BLOCKS)) | НУЛЕВОЙ |
О распределении нагрузки
Если для маршрутизации используется криптографическая хэш-функция, то есть такая, которая обладает свойством равномерного распределения значений, то все запросы транзакций от разных аккаунтов будут распределяться равномерно по всем узлам, где они будут обрабатываться независимо друг от друга, т.е.нагрузка будет распределяться равномерно.
Отказоустойчивость
Потеря одного узла в сети приведет к тому, что система не сможет обрабатывать только транзакции, направленные на этот узел.Эту проблему можно решить, создав резервную копию для каждого узла в простом случае, либо динамически перераспределив пространство имен между остальными узлами (что нужно делать ОЧЕНЬ осторожно).
Заключение
Несмотря на сложность изложения, надеюсь, мне удалось передать принципиальные отличия от традиционных систем.Если вы нашли в себе силы дочитать эти строки, то наверняка ждете ссылку на GitHub, где уже будет собранный концепт? К сожалению, практического PoC пока нет, однако публикация этой статьи — это попытка собрать подводные камни, которые я мог непредвзято пропустить.
А чтобы стать на шаг ближе к практической реализации, поэтому все комментарии, конструктивная критика и возможные ошибки очень приветствуются!
Рекомендации
- «Динамо» Amazon
- Кассандра(DHT)
- Кадемлия
- Влияние геометрии маршрутизации DHT на устойчивость и близость
- Валюта данных в реплицируемых DHT
- Повышение производительности поиска в широко распространенном DHT
-
5 Советов По Написанию Лучшего Веб-Текста
19 Oct, 24 -
Пол Грэм: Ненавистники
19 Oct, 24 -
Партнерская Программа Минкомсвязи России
19 Oct, 24
