В нашей повседневной жизни мы используем понятие времени, чтобы упорядочивать события: вставать перед завтраком, есть перед работой и т.д. Как показывает превосходная статья ACM, время может быть сложным в распределенной системе.
Это первый из трех постов в блоге об изменениях логических часов Riak. Они занимают много места: более 3 лет. Если вы предпочитаете смотреть talk, то есть отличная «Brief History Of Time (In Riak)» Шона Криббса из прошлогоднего RICON охватывает большую часть того, что освещается в этой статье.
Цель состоит в том, чтобы написать о моей последней работе над logical clocks в Riak, но для того, чтобы иметь контекст, нам сначала нужно вернуться назад во времени.
Еще в 2010 году инженеры Basho опубликовали два поста о Vector Clocks и Riak: «Why Vector Clocks Are Easy» и это сопутствующая статья «Why Vector Clocks Are Hard».
Эти два поста по-прежнему очень ценны и заслуживают внимания, но с тех пор многое изменилось. Эта серия постов, мы надеемся, восполнит этот пробел.
Riak KV - это eventually consistent key-value бд, которая поддерживает доступность записи. Чтобы достичь этого, он позволяет нескольким клиентам одновременно писать по одному и тому же ключу. Riak KV использует logical clocks, чтобы отслеживать историю обновлений до значений и обнаруживать конфликтующие записи.
С этих пор эти logical clocks будут называться Version Vectors, благодаря Карлосу Бакеро и этому посту в блоге.
Предметом этого первого поста является существенное изменение logical clocks Riak KV в версии 1.0 еще в сентябре 2011 года. Тогда Riak KV перешел от client IDs к vnode IDs. В статье «Why Vector Clocks Are Hard», упомянутой выше, автор объясняет, что это трудная задача, но выгоды, как оказалось, перевешивают затраты.
Но, прежде всего, некоторые основы.
Всюду по этому посту я использую своего рода синтаксис, похожий на Erlang.
%% комментарий
[] %% спискок
{} %% кортеж
Uppercase_word %% переменная
lowercase %% atom - литерал, константа
1007 %% число
Var = [{atomx, Var1}, {atomz, Var2}] %% это выражение говорит о том, что var равен этому спискуПерейдите к следующему разделу, если вы уже знаете, как работают Version Vectors.
Version vector - это структура данных, которая суммирует историю обновлений для значения. В Riak каждый ключ имеет свой собственный вектор версии. Структура данных - это список пар Actor и Counter.
[{Actor , Counter}]Actor - это некоторый объект в системе, который производит обновления объекта. Actor - это единица параллелизма в системе. Примерами могут быть сервер, клиент, виртуальный узел, процесс, поток. Все, что может быть однозначно идентифицировано и выполняет действия.
Когда Actor обновляет ключ, он увеличивает только свою собственную запись в векторе. Запись Actor-а - это сводка всех обновлений, которые актер исполнил. Если Actor-а нет в векторе, его счетчик согласуется с нулем. Поскольку каждая запись представляет собой сводку обновлений Actor-a, весь version vector суммирует все обновления ключа от всех участников системы.
A = [{a, 3}, {b, 2}, {c, 1}]В version vector A выше три Actor обновили ключ. Actor A имеет три обновления, B два и C один.
Само по себе это не говорит нам много. Version vectors обычно рассматриваются парами.
A = [{a, 3}, {b, 2}, {c, 1}]
B = [{a, 3}, {b, 2}, {c, 1}]Эта пара векторов версий, A и B выше, равна. Они описывают точно такой же набор событий, или историю.
A = [{a, 2}, {b, 2}, {c, 1}]
B = [{a, 3}, {b, 2}, {c, 1}]В паре A есть предок B. Мы говорим, что B доминирует A. B увидел дополнительное событие ({a, 3}), которое означает, что его часы показывают более позднее логическое время, чем A. Вы можете думать о доминировании как о "большем, чем":
B > AКогда Riak рассматривает значения, представленные этими Version Vectors, он может отбросить A, поскольку вся его информация содержится в B. Это более значимо, чем просто большая временная метка времени; c доминирующим Version Vector, мы точно знаем, что события в A вызвали B. Временная метка, полученная от обычных часов, не передает эту информацию.
Доминирование - это более строгие отношения, чем descends. Для любой пары Version Vectors A descends B, если A суммирует все события B. Таким образом, равные Version Vectors, как в вышеприведенной паре, descend друг с другом. Вы можете думать о descend как о "большем или равном". Если B descends A, то B >= A.
A = []
B = [{a, 1}]В паре выше B доминирует A. Все Version Vectors descend с пустым Version Vector, и одно событие, которое включает B, но не A.
A = [{a, 1}]
B = [{b, 1}]Эта пара version vectors конфликтует или конкурентра. Пара version vectors A и B являются параллельными, если A включает события, невидимые B, и B включает события, невидимые A. Акторы a и b обновили значение «одновременно». И это волшебство version vectors. Они позволяют Riak обнаруживать одновременные записи в ключ и сохранять sibling значения. Это было бы невозможно c обычными часами из-за отсутствия идеальной точности, синхронизации и информации о причинности.
Когда есть конфликт, или конкурентность, его необходимо разрешить с помощью записи, а запись это новое событие. Сначала объедините (merge) A и B и предоставьте результирующий вектор версии клиенту как контекст. Это гарантирует, что следующая запись опускается как A, так и B.
A = [{a, 1}]
B = [{b, 1}]
AB = [{a, 1}, {b, 1}]При объединении двух Version Vectors берется попарный максимум каждой записи.
Посмотрите AB выше. Это объединенный Version Vector доминирует над A и B.
Когда Actor c выдает новое обновление, он увеличивает свой счетчик
в этом объединенном Version Vector, гарантируя что новое значение перезапишет
оба конфликтующих значения, поскольку ABC доминирует над A, B и AB.
Riak сохранит объединенный Version Vector с новым значением в качестве последнего логического времени.
ABC = [{a, 1}, {b, 1}, {c, 1}]Подводя итог: Actors, работающие поочередно, обновляют свою собственную запись в векторе, движущем логическое время вперед в дискретных событиях. Конфликты, происхождение и доминантность могут быть установлены путем сравнения логических часов для ключа.
С основами разбираться, на тему этого поста. Прежде чем мы посмотрим, что представляют собой Vnode Version Vectors, зачем мы их хотим?
До Riak 1.0 actor в version vector был предоставлен клиентским приложением. Клиент выполняет чтение, изменяет возвращаемое значение и создает новую запись, отправляет Riak Version Vector, который он читает, client id и новое значение. Потом Riak увеличит запись клиента в version vector, что означает, что эта новая запись доминирует над прочитанными значениями и сохранит ее на диске.
В худшем случае приложение может запустить поток для каждой операции PUT, передать идентификатор потока в Riak в качестве client id, а затем выйти при завершении. Представьте 10 серверов приложений, каждый из которых обслуживает 1000 одновременных запросов, каждый из которых отправляет идентификатор однократного использования. В результате векторы версий намного больше, чем данные, и частая, агрессивная очистка vclock. Помните, что «в реальном мире с долговечными данными каждый элемент данных будет иметь векторные часы с длиной, пропорциональной числу клиентов, которые когда-либо модифицировали ее». Звучит знакомо.
Но это не самое худшее.
Использование client id в version vectors означает, что клиентские приложения требуют инварианты базы данных. Хотя предпочтительнее, чтобы actors были долгожителями, для меньшего количества идентификаторов в version vector существуют инварианты, которые необходимо поддерживать:
- Каждый actor должен быть уникальным.
- Каждое новое обновление должно сопровождаться строгим увеличением счетчика событий. То есть каждое обновление, производимое actor, должно увеличивать счетчик событий в векторе до значения, большего, чем раньше; индивидуальный актор должен всегда выдавать строго возрастающий общий порядок событий.
Наиболее распространенный способ удовлетворить эти инварианты - обеспечить соблюдение следующих условий:
- Actor должен действовать последовательно.
- Actor должен обновять только свою собственную запись в version vector.
Нарушение любого из этих инвариантов ведет к некорректному поведению, худшим из которых является молчащая потеря данных. Это требует от клиентского приложение несколько больше, чем подразумеваемый контракт «предоставить идентификатор и последние векторные часы, которые вы видели для заданного значения».
Хуже того, когда Riak использовал client id, был крайний случай, который делал невозможным сохранение этих инвариантов при определенных сценариях отказа.
Чтобы клиент выдавал строго возрастающий порядок событий, он должен знать последнее выпущенное им событие. Поскольку Riak eventually consistent, нет гарантии, что клиент прочитает свою последнюю запись, если только он не отправит обновление в первичные реплики PW, и не прочитает результат из первичных реплик PR, так что
PW+PR > NГде N это количество реплик для ключа.
Это гарантирует, что некоторые Primary P находятся как в кворуме чтения, так и записи. Это называется строгим кворумом в отличие от неаккуратных настроек кворума Riak по умолчанию.
Если вам нужно больше деталей по этому вопросу, вот исчерпывающая серия постов для вас. Требование строгого кворума снижает доступность Riak в случае сбоев узла или сетевых разделов.
Что происходит, когда вы не читаете свои собственные записи? Прежде чем взглянуть на пример, рассмотрим pre-1.0 алгоритм Riak для version vectors.
- клиент получает значение + version vector по ключу
- клиент отправляет Put Request в Riak со значением, client id и version vector.
- Riak increments the entry for ClientID in Version Vector
- на каждой из N Vnodes:
- читаем локальное значение с диска
- если локальный version vector descends входящий, то игнорируем запись - мы уже видели ее
- если входящий version vector descends локальный, то перезаписываем локальное значие новым
- если входящий version vector конкрурентен локальному, то добавляем новое значение как sibling
Правильная работа зависит от этого первого шага. Этот контекст из GET обязательно должен содержать самое высокое событие, выпущенное идентификатором клиента.
Зачем? Просто добавить одно к вектору версии и для результата быть новым событием, большим счетчиком и более поздним логическим временем для этого актера, чем предыдущие события.
Мы можем придумать довольно простой пример, когда данные теряются. Любое
условие, приводящее к несвязанному чтению и записи, (например, чтение из
[A ', B', C '] и получение not_found, запись в [A, B, C], повторить).
Каждая запись будет иметь один и тот же вектор версии Запись [{X, 1}],
что означает, что после первоначальной записи все последующие записи
будут отброшены в соответствии с алгоритмом выше:
Local = [{X, 1}] %% descends
Incoming = [{X, 1}]И есть много вариантов отказов, partitions, и медленных ответов, которые могут привести к тому, что вы не будете читать свои собственные записи.
Причина проблемы заключается в том, что одно и то же событие {X, 1}
помечено двумя разными вещами. Каждое событие в version vector является
уникальным моментом в логическом времени. Два version vector, которые
являются равными, должны представлять одну и ту же историю. В этом
случае [{X, 1}] может быть одним из двух записей с потенциально
разными значениями! Другими словами, без Read Your Own Writes,
version vector могут не обнаружить одновременные обновления.
По умолчанию Riak не выставляет PW=quorum и PR=quorum: Basho полагает, что люди выбирают Riak для обеспечения доступности. Однако, если вам известно о требовании Read Your Own Write и заданы правильные параметры, была ошибка, которая может означать, что вы не Read Your Own Writes, но считаете наоборот.
Riak 1.0 исправил ошибку, но все равно, у нас есть Vnode Version Vectors.
Чтобы облегчить клиентское приложение от бремени управления идентификаторами, инженеры Basho выяснили, каким образом vnodes являются участниками системы. Это имеет смысл, поскольку vnode уже является единицей параллелизма в Riak.
В статье «Почему векторные часы трудны» автор описывает проблему c Server Actor ID, которая идентична ошибке повторения истории выше. А именно два разных события, которые фактически были параллельными, получают один и тот же вектор версии. Как это произошло?
- Клиенты X и Y оба читают ключ K и получают "Rita" [{a, 1}]`
- Клиент X отправляет запрос PUT “bob”
- Клиент Y отправляет запрос PUT “sue”
- Riak vnode принимает запрос Y PUT, устанавливает version vector
[{a, 2}]и значение “Sue” - Riak vnode принимает запрос X PUT…
Что должен делать vnode? Входящий вектор версии - [{a, 1}].
Vnode может увеличивать свою запись, создавая вектор [{a, 2}], но тогда
у нас есть два разных значения с одним и тем же вектором версии.
Нам не удалось обработать конкурентный запрос, и некоторые записи теряются.
Мы могли бы прочитать локальное значение для K и увидеть, что version
vector [{a, 2}] доминирует над входящим [{a, 1}] и отбросить входящую
запись. Это кажется несправедливым, как в любой гонке, только один клиент
может «выиграть» (некоторые базы данных делают это с обычными часами!)
Мы могли бы изменить алгоритм version vector:
Если локальный Version Vector descends входящему Version Vector, добавьте новое значение как sibling.
Также полезно, чтобы плохо работающие клиенты, которые не извлекают Version Vector перед записью, все равно будут генерировать sibling на PUT, что означает, что их значения записи сохраняются, а не молча отбрасываются, как видно.
What have we achieved? Smaller Version Vectors: in the order of the number of replicas for the key (by default 3 in Riak). Simpler for clients: for best behaviour provide the latest Version Vector you’ve seen when you issue a PUT, but of the Version Vector is stale it doesn’t matter, your value will be stored as a sibling.
Чего мы достигли? Меньшие Version Vectors: в порядке количества реплик для ключа (по умолчанию 3 в Riak). Упрощение для клиентов: за лучшее поведение вы получите последний вектор версии, который вы видели, когда выполняете PUT, но версия Vector устарела, это не имеет значения, ваше значение будет сохранено как sibling.
В кратце:
- Нет необходимости в Read Your Own Writes
- Меньшие Version Vectors
- Меньшие clients
С другой стороны, Vnode Version Vectors теряют идемпотентные PUT.
С идентификаторами клиентов, если какой-либо клиент A посылает PUT с
идентификатором X и часами [{X, 2}, {Y, 3}] и Riak не отвечает, но
сохраняет запись, повторная выдача той же записи будет идемпотентной.
С помощью Vnode Version Vectors перевыпуск записи создает sibling
с идентичным значением. Однако побочным действием Riak будет хранение
набора siblings.
Another downside is that there must be a coordinating vnode to increment the Version Vector. This means that when a request reaches Riak, the preference list must be consulted and a vnode on the preference list is chosen to coordinate the PUT. If the node that received the request is not on the preference list, then the request must be forwarded to a node that is: this introduces some latency to a PUT.
Другой недостаток заключается в том, что должен быть координирующий vnode для инкремента Version Vector. Это означает, что, когда Riak получает запрос, надо свериться с preference list, и vnode должен быть выбран по нему для координации PUT. Если узел, получивший запрос не входит в список предпочтений, то запрос должен быть передан в узел: это вносит некоторую задержку в PUT.
As a result of false concurrency riak is unable to accurately discern truly concurrent writes from interleaved writes, leading in the worst case to an “explosion” of sibling values. This is fixed in Riak 2.0, so don’t panic! This “sibling explosion” is also the subject of the next blog post.
В результате ошибочной конкурентности Riak не в состоянии четко различить подлинно конкурентные записи и чередующиеся записи, что приводит в худшем случае к “взрыву” sibling значений. Это исправлено в riak 2.0, так что не паникуйте! “Sibling explosion” - тема следующего поста.
Поскольку мы выпустили Риак 1.0, мы не должны говорить о “vclocks”, a “causal context” или просто “context”. Vnode Version Vectors решают некоторые сложные вопросы для пользователей Riak с доступностью и управления клиентским процессом, но пришли они с какими-то издержками. Для полноты картины, вот release notes с Vnode Version Vectors.
В следующий раз мы рассмотрим ошибку «sibling explosion» в Vnode Version Vectors и как академическое вмешательство спасло нас.
Russell Brown