Vector Clocks Revisited Part 2: Dotted Version Vectors

В моем предыдущем блоге я писал о Vnode Version Vectors и о том, как они упрощают взаимодействие с Riak, сохраняя при этом небольшой размер логических часов. Я также упомянул о проблеме с «sibling explosion». Сегодняшнее сообщение в блоге будет более подробно описывать проблему sibling explosion и то, как Riak и некоторые ведущие исследователи распределенных систем собрались вместе, чтобы решить эту проблему, используя Dotted Version Vectors.

Vnode Version Vector Recap

В последнем посте мы наблюдали, как Vnode Version Vectors улучшают стандартный version vector. Давайте быстро расскажем, как это сделать.

С помощью ClientId Version Vector Riak генерирует siblings следующим образом:

Если локальный Version Vector descends входящий
- Отказать/игнорировать входящее обновление
Если входящий descends локальный
- Записать новое значение на диск
Если входящий конкурентен с локальным
- Смержить входящий и локальный Version Vectors
- Сохранить входящее значение как sibling

Но с Vnode Version Vectors:

Если входящий descends локальный
- Увеличить запись vnode во входящем version vector
- Записать новое значение на диск
Иначе
- Смержить входящий и локальный version vectors
- Увеличить запись vnode в смерженом version vector
- Записать входящее значение на диск

Мы использует единственный version vector чтобы покрыть полный набор из значений sibling. Но version vector недостаточно, чтобы правильно отслеживать causality, когда actor - vnode - является прокси для нескольких клиентов.

Sibling Explosion

Что такое sibling explosion и как это происходит?

Представьте два клиента X и Y. Оба они обновляют один и тот же ключ. Для простоты эта иллюстрация будет использовать опцию Riak Return Body, что означает, что Riak отвечает каждому PUT с последним результатом, который он хранит на диске в coordinating vnode. Это просто проще, чем выборка клиента после каждого PUT.

На приведенной выше диаграмме мы видим «sibling explosion». Vnode Version Vectors неспособны отслеживать causality достаточно точно, и эти пересекающиеся записи создают false concurrency. Пройдемся по шагам, пронумерованным на диаграмме.

Клиент Y отправляет PUT со значением "Bob" в пустой контекст.
Vnode A видит, что [] descends локального version vector (также []) и увеличивает его значение в входящем version vector, сохраняя значение с новым version vector [{a, 1}]. Значение «Bob» и контекст [{a, 1}] возвращаются клиенту Y.
Клиент X отправляет PUT со значением "Sue" в пустой контекст. Этот PUT является causally concurrent с клиентом Y на шаге 1.
Используя описанный выше алгоритм, vnode A обнаруживает, что контекст [] не descends [{a, 1}] и рассматривает запись как одновременную, увеличивает локальный version vector до [{a, 2}] и сохраняет входящее значение как sibling. Все идет нормально. Vnode version vector правильно зафиксировал параллелизм! Vnode A возвращает sibling значения ["Bob", "Sue"] [{a, 2}] для клиента X.
Клиент Y отправляет PUT "Rita" в контекст [{a, 1}]. Помните, что клиент Y видел результат своего собственного PUT перед тем как клиент X отправил PUT на шаге 3.
Vnode A обнаруживает, что входящий version vector [{a, 1}] не descends локальный version vector [{a, 2}]. Он увеличивает свою запись в локальном version vector и добавляет "Rita" в качестве sibling. Подождите, что? Мы знаем, что клиент Y видел значение "Bob", и отправил PUT с этим значением! Поэтому "Rita" должна хотя бы заменить "Боб". Да, это одновременно с «Sue», но только «Sue».
Клиент X отправляет PUT c новым значением "Michelle" с контекстом [{a, 2}]. Клиент Y имеет ввиду заменить то, что он прочел, sibling значения "Bob" и "Sue" новым значением "Michelle".
Как и раньше, vnode A обнаруживает, что [{a, 2}] не descend [{a, 3}] и добавляет входящее значение в качестве sibling. Опять же, мы можем видеть, что это неправильно. На шаге 4 клиент X увидел как "Bob", так и "Sue", и эта новая запись намеревается заменить эти значения.

Что же случилось?

Vnode A теряет некоторую важную causal информацию. Шаг 4 заканчивается сохранением как "Bob", так и "Sue" с version vector [{a, 2}]. Он «забыл», что "Боб" был связан со временем [{a, 1}]. Когда клиент Y отправляет PUTs снова, с устаревшим контекстом [{a, 1}], vnode не может определить, что этот PUT означает заменить "Bob", так как "Bob" теперь связан с вектором версии [{a , 2}].

Dots To The Rescue

Нам нужен более точный, детальный механизм, чтобы определить, какие siblings удалить обновлением, а какие siblings на самом деле являются конкурентными или не связанными causally. Этот механизм - "dot" (точка).

Вспомните основы version vector: каждый actor должен обновить свою собственную запись в векторе, увеличив счетчик. Этот счетчик представляет собой сводку всех событий участников. Запись {a, 4} сообщает, что actor a выполнил 4 обновления. 4 включает в себя 1, 2, 3, 4. Каждый из этих шагов, которые прошел счетчик, является обновлением. Это и есть dot: это одно обновление, событие. Возьмите обновление {a, 4}. Это событие, обновление, точка. Элемент в version vector {a, 4} можно рассматривать как набор дискретных событий, а точка - как любое из этих событий.

Надеюсь, приведенная выше диаграмма иллюстрирует это. Это два разных визуальных представления одного и того же version vector [{A, 4}, {B, 2}, {C, 3}]. Тот, что справа, это визуализация, которую я впервые увидел при работе с группой ученых из Университета Minho, и он помогает проиллюстрировать идею векторов версий и историю, которую они обобщают. Тот, что слева «взрывает» version vector в свои дискретные события.

Dot The clocks

Как это поможет решить описанную выше проблему? Мы снова меняем алгоритм. Когда мы увеличиваем version vector для сохранения нового значения, мы берем это последнее событие и сохраняем его как dot со значением.

[{a, 2}]
["Bob", "Sue"]

Становится

[{a, 2}]
[{a,1} -> "Bob",
 {a, 2} -> "Sue"]

Вот и все, что мы должны сделать, это добавить более детальное отслеживание causality. Теперь, когда у нас есть пересекающиеся записи, как указано выше, мы можем видеть, какие sibling значения одноуровневого обновление заменит, а какие нет, сравнивая входящий version vector с dot для каждого значения. Если version vector descends dot, клиент увидит это значение и новая запись заменит его. Если version vector совпадает с dot, сохранит это значение в качестве действительно конкурентной записи - sibling.

Эта диаграмма показывает шаг 6 снова, на этот раз с dotted version vectors. Мы видим, что дополнительные метаданные, сохраненная dot со значением, позволяет Riak отбросить значение «Bob», так как входящий Version Vector [{a, 1}] descends dot, хранящуюся с этим значением. Новая dot, созданная в результате этого события обновления {a, 3}, используется для отметки нового sibling «Rita». «Sue» остается sibling, так как он невидим по входящему version vector [{a, 1}], мы знаем, что клиент Y не хотел заменять это значение.

Благодаря этому механизму, Dotted Version Vectors, или DVV для краткости, небольшое увеличение объема хранения метаданных исправляет ошибку Sibling Explosion.

Осталось только взглянуть на первоначальный пример sibling explosion и увидеть, что с помощью Dotted Version Vectors, Riak правильно захватывает только действительно параллельные операции и сохраняет только те значения, которые являются актуальными sibling.

Почему “dot”?

Почему это слово «dot»? Если мы снова задумываемся о шаге 6, в случае Dotted Version Vector, вы можете представить себе vnode A, генерирующий событие {a, 3} и присваивающее его входящему значению сразу. Затем слияние входящего DVV с локальным. Визуализация этого запроса PUT с dot, надеюсь, объясняет название.

Концептуально существует разница между входящим version vector [{a, 1}] и событием {a, 3}, и эта разница приводит к тому, что называется "non-contiguous event a dot" (несмежное событие). Строго говоря, «dot» является несмежным событием, но они используются в других местах (например, CRDT) просто как дискретные теги событий, поэтому простого объяснения достаточно.

Further Material

Эта статья охватывает только Dotted Version Vectors, реализованные в Riak. По необходимости мы просто добавляли dot-per-sibling к объектным метаданным. Dotted Version Vectors в Riak полностью обратно совместимы с предыдущими версиями Riak, и их можно включать или отключать с помощью простого свойства bucket. В Riak 2.0 Dotted Version Vectors являются логическими часами по умолчанию для типов bucket. Однако есть и другие реализации. Ricardo Tomé Gonçalves реализовал оптимизированный вектор Dotted Version Vector, называемый Dotted Version Vector Set. Репозиторий git находится здесь, и его код также в настоящее время используется в Riak для отслеживания метаданных кластера.

Если вы используете Riak, вы просто используете DVV, и вам не нужно знать и можно не заботиться о деталях. С клиентской точки зрения это то же самое, что и Vnode Version Vectors, исключая, конечно, sibling explosions.

Если вы хотите использовать Dotted Version Vectors в вашем собственном распределенном приложении, я рекомендую вам прочитать статью и репозиторий Ricardo Tomé Gonçalves.

With thanks

Для краткости этот пост не рассказывает историю о том, как у нас в Basho Engineering появилась Dotted Version Vectors в Riak. В кратце, некоторые очень блестящие ученые в Portugal придумали Dotted Version Vectors как решение sibling explosion, а затем дали нам это. Это замечательная вещь в исследовательской науке, и я чрезвычайно благодарен за возможность работать с Ricardo Tomé Gonçalves, Valter Balegas, Nuno Preguiça, Carlos Baquero, Paulo Sérgio Almeida и другими, в то время как в Riak исправляли sibling explosion. История sibling explosion и dotted version vectors в Riak действительно является примером академической экспертизы, решающей проблемы реального мира, индустриальные проблемы. Еще раз спасибо!

Summary

Благодаря vnode version vectors, взаимодействие с клиентом Riak просто, Read Your Own Writes не требуется, а version vectors остаются небольшого размера. Благодаря dotted version vector мы можем сохранить все эти преимущества без риска получения крупных объектов от sibling explosion.

Next Time on Logical Clocks

Подобно тому, как Vnode Version Vectors были ответом на неадекватность в Client Version Vectors, а Dotted Version Vector исправили sibling explosion, в следующем блоге мы рассмотрим другую, менее распространенную проблему, которая приведет к прошлому, похожему на будущее.

More Thanks

Кроме того, спасибо Jon Meredith, Zeeshan Lakhani, John Daily и Scott Fritchie (all Basho Engineers), Ricardo Tomé Gonçalves, Nuno Preguiça (снова!) за то, что вы прочитали эту статью и предложили множество улучшений.

Russell Brown

mitallast/dotted-version-vectors.md