Storage Architecture

Общий вид,

note seealso:

TODO

TODO картинка

summary tldr:

expand block

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nulla et euismod nulla. Curabitur feugiat, tortor non consequat finibus, justo purus auctor massa, nec semper lorem quam in massa.

info todo:

Info

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nulla et euismod nulla. Curabitur feugiat, tortor non consequat finibus, justo purus auctor massa, nec semper lorem quam in massa.

tip hint important:

Hint

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nulla et euismod nulla. Curabitur feugiat, tortor non consequat finibus, justo purus auctor massa, nec semper lorem quam in massa.

Основы : Транспорт , Paxos , Raft

Архитектура нацелена на производительность и на гибкость использования.

Мы хотели, чтобы одна эта система перекрывала широкий фронт задач от disk kv lib до rdbms и BigData и могла быть использована в разных частях server side систем.

Также, одна из основных задачь системы : быть подсистемой ввода-вывода (IO) для CPVM (todo ссылка). Отсюда и требование поддерживать транзакции , работающие с очень большими объёмами данных.

Мы использовали https://github.com/real-logic/Aeron для обмена даными между узлами системы, это позволяет увеличить скорость операций в KV узле до миллиона в секунду и более на специальном железе . [todo ссылка а производительность].

Сам по себе Aeron это просто транспорт, но в сочетании с paxos и Raft алгоритмами консенсуса и оптимальными протоколами получается универсальный продукт.

При проектировании системы придерживались следующих принципов:

  • лучший запрос - отсутствие запроса , протоколы спроектированы с небольшой избыточностью, что позволяет экономить время на числе запросов
  • использование оптимального транспорта в каждом отдельном случае
  • Lock Free алгоритмы, non blocked структуры данных
  • и приципы дизайна Aeron https://github.com/real-logic/Aeron/wiki/Design-Principles

Обычно мы в продуктах используем AJRPC , но в данном продукте отказались даже от него, для ещё бОльшей производительности. Малая задержка при работе с такими системами очень важна, ведь они являются низким слоем поверх которого строятся сруктуры данных верхнего уровня, для них задержка возростает на порядок и она не должна выходить за пределы разумного, иначе теряется смысл в построениии структур верхнего уровня поверх Key-Value.

Paxos implementation

Отличие нашего Paxos от канонического Paxos

  • идентификатор of Proposer состоит из двух частей (счётчик, номер of Proposer). Это даёт уникальные идентификаторы для всех Proposers, даже если счётчик у них в данный момент одиниковый. Весь этот составной идентификатор является версией значения ключа.
  • в статье нет ни слова про выбор лидера. У нас это происходит так: выбирается самый старший (с большим номером) пропозер из тех, которые сейчас живы (пингуются нодой, которая делает выбор). Часть пропозеров может отваливаться.

В остальном все так же. Система общается внутри себя поверх быстрого транспорта Aeron и сериализации без reflection (custom message passing). Внешняя часть бинарного протокола будет описана отдельно , как binary API. TODO.

Конфигурация кластера храниться на выбор администратора в :

  • consul проверенная временем система. Работает не шустро, но и конфигурация кластера обычно меняется с малой частотой.
  • ARaft (todo описать) - наша собственная система распределения конфигурации, работающая по протоколу raft. Умеет 200_000 обновлений ключей в секунду, каждый ключ хранится на всех узлах, очень оперативное управление репликами элементов конфигурации.

Наверное , ARaft - самая быстрая из всех raft реализаций, которые существуют. ARaft распространяет replicated log не целиком, а вводит внутри него адресацию для каждого элемента конфигураации и распространяет log по частям.

Транзакции

A_Storage может работать как обычными операциями set, get,так и позволяет применять большие наборы данных транзакционным образом.

Объём данных в транзакции "ничем не ограничен" т.к. устанавливается в систему множеством отдельных запросов.

В теории это BigData масштабы изменяемых за транзакцию объёмах данных.

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

Одна система версионирования работает с версиями реплик ключей , другая сиситема версионирования работает с версиями наборов данных (transaction index).

Пользоваться этими транзакциями сложнее чем транзакциями в RDBMS, но это малая плата за бОльшие возможности.

Чтобы пользоваться транзакциями A_Storage нужен опыт работы как с rdbms, так и с nosql. Однако CPVM делает сам всё необходимое управление IO транзакции, поэтому пользователь CPVM получает ACID автоматически

Использование транзакций

Транзакция это некоторая работа логически ограниченная с начала и с конца. В википелии её называют группой операций с базой данных Смысл этой работы в чтении значений, некторые выводы или вычисления с использованием прочитанных данных и запись результатов или выводов обратно в БД.

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

Поэтому транзакции нужно изолировать друг от друга. Эта изоляция может быть полной или не полной и защищает от ряда нежелательных эффектов.

Для разных вычислений требуются различные минимальные уровни изоляции транзакций, которые они вправе потребовать от БД.

  • 0 — Чтение неподтверждённых данных (грязное чтение) (Read Uncommitted, Dirty Read) — чтение незафиксированных изменений как своей транзакции, так и параллельных транзакций. Нет гарантии, что данные, изменённые другими транзакциями, не будут в любой момент изменены в результате их отката, поэтому такое чтение является потенциальным источником ошибок. Невозможны потерянные изменения (lost changes), возможны неповторяемое чтение и фантомы.
  • 1 — Чтение подтверждённых данных (Read Committed) — чтение всех изменений своей транзакции и зафиксированных изменений параллельных транзакций. Потерянные изменения и грязное чтение не допускается, возможны неповторяемое чтение и фантомы.
  • 2 — Повторяемое чтение (Repeatable Read, Snapshot) — чтение всех изменений своей транзакции, любые изменения, внесённые параллельными транзакциями после начала своей, недоступны. Потерянные изменения, грязное и неповторяемое чтение невозможны, возможны фантомы.
  • 3 — Сериализуемый (Serializable) сериализуемые транзакции. Результат параллельного выполнения сериализуемой транзакции с другими транзакциями должен быть логически эквивалентен результату их какого-либо последовательного выполнения. Проблемы синхронизации не возникают.

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

В A_Storage транзакции распределены на несколько запросов/соединений т.е. операций, поэтому не требуется всё, что надо для транзакции отдавать БД в виде одного большого запроса.

БД управляет ходом транзакции, обозначенной неким tr_id , который БД дал пользователь. Генерация идентификаторов транзакций внешняя по отношению в A_Storage и относится к архитектуре в которой используется A_Storage.

При генерации transaction index (элемент tr_id) можно использовать быстрые счетчики (например, ключ с 10-ю репликами в A_Storage) или просто использовать генерацию UUID. Storage внутри сравнивает идентификаторы конфликтующий транзакций, считая, что транзакция с меньшим номером была начата раньше.

  • Если использовать счетчики, то это даёт приемущество : в случае конфликта доступа последовательность вынужденного отката транзакций логична. В противном случае она "не логична" , но данные в БД это не портит. Можно использовать индивидульаный счетчик для каждой группы ключей так, чтобы заранее было известно , что работы по этим группам никогда не пересекаются между собой, это уменьшает "бутылочное горлышко" такого элемента как счетчик.
  • Если использовать uuid в качестве идентификатора транзакции, то данные будут корректны, но откатываться в случае конфликта будет транзакция с меньшим uuid, т.е. непредсказуемо случайная. Такое решение не имеет проблемы "бутылочного горлышка" в виде счетчика транзакций.

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

Каждая транзакция завершается итоговым multicas commit запросм, который может состоять из нескольких CAS запросов по несколько ключей в каждом.

Система имеет внутренние блокировки и watch операции для организакции оптимистических блокировок.

Раздел про полное API

Уровни изоляции транзакций в KV

У нас есть всего три уровня изоляции:

  • NULL
  • RU Read Uncommited
  • RC Read Commited

Важно :

  • Нигде не написано какой у изоляции уровень транзакции, всё работает из-за комбинации флагов и операций.
  • Транзакция с меньшим индексом может прервать транзакцию с большим индексом, а не наоборот
  • ключи могут быть залокированы

NULL isolation

get (uncommited flag)
set

get uncommited. На данном уровне вы читаете, а другая транзакция туда пишет и ничего, всё нормально.

При set , если lock на ключах - операция заблокируется set тут работает быстрее за счет такой внутреней ллогики : ""

Commit тут не нужен, rollback тоже не нужен.

Максимально похоже на Riak KV, get вызывает get а реплики и на кворум, set вызывает дополнительно 1 get , и если тебе повезло, то нет ожиданияи сразу set на реплики.

RU Read Uncommited (не теряем обновления)

На этом уровне обновления мы не теряем, но они могут конфликтовать друг с другом. Одна из конфликтующих транзакций будет отменена.

Ваш набор данных будет применен весь, но не факт, что он будет консистентен из-за того, что а) get был не консистентен б) нет проверки, что в ключах на момент записи все ещё старые значения (возможно их поменяла другая транзакция)

Требуется уже создавать объёкт транзакции. 

create(idx)
get (uncommited)
set , cas
commit | rollback

Get можно делать все еще uncommited,

Cas применяет с проверкой прошлой версии, но в Read Uncommited можно перемешивать cas и set. Set не проверит прошлую версию ключа, а просто установит.

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

TODO описание "" чтобы очередь запроов не росла бесконечно (все на таймаутах висит) есть способ чтобы это ограничить.

RC Read Commited

Идентифактор trid должен быть уникальным для всех транзакций. Он на всегда сохраняется, пока "сборка мусора" не соберет.

В cas должны попадать все версии прочитанных ячеек.

RC if R_Only если транзакция только читает

create(idx)
R : watch 
get -> check 
commit | rollback

Тут надо чтобы данные прочиталиссь консистентно, а не записались консистентно. Поэтому нельзя использовать ни get commtited ни get uncommited, потому что есть вариант когда другая транзакция проскочит и что то напортит в наборе данных.

  • Используем операцию watch, которая сразу блокирует ключ с самого начала.
  • или используем get а потом check т.е. читаем , а потом в конце транзакции все прочитанное быстро проверяем "не изменилось ли ?"

Другие транзакции будут читать заблокированные ключи, они читают в заблокированном ключе "старое значение"

RC if RW , если транзакция читает и пишет

create(idx)
get watch 
cas , check 
commit | rollback

Любой get попадает в cas, чтобы в конце убедиться, что предпосылки по вычислениям , результаты которых транзакция записывает, до сих верны на момент записи (не изменились).

get можно делать uncommited, расчитывая, на то , что другая транзакция поставила watch.

В конце транзакции cas проверяет версии на соответствие.

check это по сути такой cas, который без "нового значения". Он просто версию сравнивает

важно, про deadlock : порядок чтения ключей и блокировки не важен. т.к. решение "кто кого блокирует" принимается на основе индексов транзакций trid. Это избавляет пользователя от необходимости следить за порядком доступа к ключам.

Способы защиты от нежелательных эффектов

(подробно работа с транзакциями рассмотрена ниже на примерах todo)

Потерянное обновление

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

Решение: При использовании наших транзакций такое невозможно. Одна из транзакций будет прервана и её нужно будет повторить.

защита от него в том, что итоговый multicas (todo ссылку) транзакции не пройдет если old версия хоть одного ключа не совпадет и будет применена только одна из конфликтующих транзакций. RDBMS повторил бы запуск транзакции сам, здесь это долджен сделать пользователь явно т.к. транзакции могут быть очень большими

"Грязное" чтение

Суть проблемы: Чтение данных, добавленных или изменённых транзакцией, которая впоследствии не подтвердится (откатится).

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

защита от грязного чтения двойная: во-первых для перезаписанных другой транзакцией ключей изменится версия и текущая траназкция не сможет в конце примениться, но транзакции могут быть длинными и ждать конца текущей транзакции долго, во вторых, есть еще один механизм, предупреждающий, что у текущей транзакции нарушена изоляция и она (если её требования выше Read commited) может прерваться по желанию, или попытаться не включать в итоговый multicas набор ключей данный ключ. (транзакция в этом случае если ей не требуется read commited может завершиться успешно). ??? TODO изменить текст, сделать яснее

Неповторяющееся чтение

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

Решение: Для предотвращения этой проблемы существует два варианта.

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

Разница между этими способами в моменте установки блокировки: первый блокирует значения в начале транзакции, второй - в конце транзакции. Выбор зависит от продолжительности транзакции и уровня конкуренции по обрабатываемым в транзакции ключам (будет ли блокировка мешать другим транзакциям).

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

"Фантомное" чтение

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

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

У нас отсутствует понятие "набора данных", такая ситуация просто не возникает. Дополнение : DT, в котором есть последовательности сам реализован поверх KV и имеет внутри ссылочную древовидную структуру, также охвачем KV логикой видимости изменений, т.е. его последовательность изолирована от других транзакций и является набором данных в смысле recordset.

Управление доступностью

KV позволяет для каждого ключа индивидуально указать числа N,R,W - число реплик и кворум на текущую операцию.

Это позволяет для важных данных иметь много одинаковых реплик с большим числом кворума и увеличивать число реплик для данных которые часто нужны пользователям. Для не важных и временных данных указывать малое число реплик.

Этот элемент дизайна нам понравился у Riak .

Replication

A_Storage KV построен как multi node cluster. Он распределеяет данные между несколькими физическими серверами, это позволяет получить строгие гарантии устойчивости к сбоям.

CAP_theorem определяет ключевые для распределенного хранилища свойства , недостижимые одновременно : "доступнось", "устойчиость к разделению кластера" , "консистентность".
Вместе эти свойства не могут достигаться в одной "информационной системе". Часто разработчики систем выбирают только две опции : или "CP" (консистентность, устойчивость), или "AP" (доступность, устойчивость), в последнем случае консистентность гарантируется в "конечном счете" Eventual Consistency.

Также CAP теоремадиктует необходимость компромисса между доступностью (Avilability) и консистентностью (Consistency).

Индивидуальные настройки репликации

Если использовать A_Storage KV в манере Eventual Consistencyможно удобно регулировать этот компромисс. Эта возможность фундаментально отличает A_Storage от других хранилищ.

Фактически настроки NRW позволяют выбирать баланс между P и A (Partition Tolerance & Availability).

Три параметра N, W и R определяют баланс между надежностью и скоростью работы кластера.

Значение N и репликация

Каждый ключ сохраняемй в A_Storage KV сохраняется на нескольких физических серверах кластера. Число этих серверов для каждого ключа задаётся в параметре N. По умолчанию, это число N==3. Это означает, что ключ будет сохранен на трёх серверах, т.е. будет реплицирован, и будут предприняты попытки записать три реплики в трех разных местах.

Значение R и устойчивость чтения к сбоям

Например мы записали 2 в реплики ключа предыдущей командой.

Можно запросить это значение обратно. По умолчанию A_Storage постарается прочесть данные со всех N нод, но при запросе указывается еще один параметр R. Он определяет, с какого количества нод нужно успешно прочесть данные, чтобы можно было их отправить клиенту. Значение R будет указывать при запросе число реплик, от которых требуется дождаться ответа, чтобы кворумом решить какое именно значение отдать пользователю. Система не отдаст ответ пока не откликнется заданное число серверов, хранящих реплики данного ключа.

Это позволяет регулировать Read Availability даже для случая если часть нод системы выключено или не отвечает.

Значение W и устойчивость записи к сбоям

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

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

Баланс между A и P и возможно С

AP (Availability & Partition tollerance) подход гарантирует доступность и устойчивость к разделению кластера ценой согласованности данных.

Представим кластер из четырех машин — две машины в одном дата-центре и две в другом.

Мы пишем данные с N=3, R=2, W=2. Все идет хорошо, пока связь между центрами не рвется.

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

Для его разрешения применяется алгоритм last write wins: для каждой пары ключ-значение хранятся временные метки (версии) и запись, которая была последней, выигрывает и становится истинной.

CAP теорема

A_Storage находится в AP зоне, но имет полные возможности CP зоны. Одна и та же система может быть развернута для этих обоих целей : доступности и консистентности и она позволит работать с одними и теми же данными.

В случае использования CP API Availability не гарантируется.

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

Это уже лучше чем полный отказ в обслуживании, который в таких случаях пользователь получит от CP систем.

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

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

В чём же гибкость ?

Можно настраивать параметры NRW для разных типов данных:

  • важные данные можно писать на большее количество машин для надежности,
  • а малозначимые — на меньшее, для скорости и экономии ресурсов.

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

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

Если данные меняются редко а читаются часто : число N можно постепенно увеличивать (перезаписывать с большим N). так можно снизить нагрузку на узлы и уменьшить время отклика.

Если данные важно сохранить как можно дольше и надежнее : увеличить N.

Если данные мало-значительны , и/или требуется быстро их записать уменьшать , например N=1 (так бывает в момент быстрого накопления логов или отладочной информации. ).

Если с информацией идет работа с помощью CP API : R и W не могут быть меньше или равны половины N, в этом случае они поменяются автоматически внутри кластера. Больше N/2- они быть могут.

Если важно прочитать данные даже если "конец света" : уменьшать R можно даже до 1 , лучше это делать поступательно, малыми шагами, в случае отказа. Не рекомендуется, но часто допустимо, уменьшать R ниже половины N (пользователь не хочет даже знать о состоянии кластера, ему важно получить хотябыодну реплику)

Если важно убедиться, что запись прошла успешно на все заданные реплики : сделать R==N или незначительно меньше.