[comp.prog] Amazon’s Dynamo: версионность объектов

Так вот о статье Dynamo: Amazon's Highly Available Key-value Store (о которой я неделю назад говорил). Статья большая. Для меня оказалась интересной. Информации в ней много, всего не перескажешь. Так что, если кому-то эта тема интересна, то советую прочитать статью целиком. Я же у себя в блоге перескажу только то, что сам из нее запомнил.

Amazon Dynamo является быстрым, высоконадежным, распределенным хранилищем информации, представленной в виде пар ключ-значение. Это хранилище используется такими требовательными к быстродействию и надежности сервисами Amazon, как списки бестселлеров, корзины покупок, предпочтения пользователей, каталог продуктов и пр. Для этих сервисов не нужны сложные реляционные модели данных. Им вполне хватает всего двух операций, предоставляемых Dynamo: put для (пере)записи данных и get для чтения.

Главной особенностью Dynamo является отношение к целостности данных. Известная четверка свойств транзакции в БД - ACID (Atomicity, Consistency, Isolation, Durability) - в Dynamo обеспечивается своеобразно. Поскольку невозможно обеспечить высокую производительность и высокую надежность (смотрим на CAP-теорему), то подход к согласованности данных в Dynamo свой собственный.

Например, пусть приложение A выполняет обновление значения для ключа K и приложение B в тот же самый момент выполняет обновление значения для того же самого ключа. Оба эти изменения будут приняты Dynamo. Каждое изменение объекта приводит к сохранению нового, неизменяемого значения. Этому значению будет приписана временная метка в виде вектора (см. vector clock). Элементами в векторе являются номера версий и имена узлов, которые сохраняли новую копию.
Например, пусть на узле S1 зафиксировали первую версию объекта D - временная метка для него будет иметь вид [[S1,1]] - т.е. первая версия на узле S1. Затем на этом же узле объект D перезаписали, и у него метка изменилась, приняла значение [[S1,2]] - получилась вторая версия на узле S1. Затем объект D модифицировало приложение A, но модификация пошла не через узел S1, как раньше, а через узел S2. Новое значение объекта получило метку [[S2,1],[S1,2]] - т.е. первая версия на узле S2 после второй версии на узле S1. В это же время объект D перезаписало приложение B, но запись пошла через узел S3. Так получилась еще одна, независимая, копия D с временной меткой [[S3,1],[S1,2]].

Так вот главная особенность Dynamo в том, что когда приложение запросит последнюю версию объекта D, то оно (при нормальной работе Dynamo), получит сразу две копии объекта - одну с меткой [[S2,1],[S1,2]], а вторую с меткой [[S3,1],[S1,2]]. И вот тут возникает вопрос: кто и как будет делать согласование этих версий?

Dynamo позволяет ответить на этот вопрос двумя способами:

• такое согласование выполняет само Dynamo. Это очень негибкий способ, самым разумным выбором в котором будет оставление самого последнего изменения и выбрасывание всех предыдущих (т.н. last write win);
• такое согласование выполняет запросившее данные приложение. Т.е. приложение создается так, чтобы быть способным получить несколько версий одного и того же объекта, после чего "слить" изменения из разных версий в одну согласованную версию.

Так вот, самым удивительным для меня оказалось то, что такой сервис Amazon, как "корзина покупок" как раз умеет сливать "параллельные" версии корзинки в одну.

Но вернемся к временным меткам. У нас оказался объект D с двумя разными значениями и разными временными метками. Приложение, которое такой объект получило, должно создать и сохранить его новую согласованную версию. Пусть оно это значение сделало и записало через узел S1. Тогда временная метка нового значения примет вид [[S1,3],[S2,1],[S3,1]]. Если же новое значение было сохранено через узел S4, то временная метка, подозреваю, примет вид [[S4,1],[S2,1],[S3,1],[S1,2]] (тут я не уверен на 100%, т.к. такого примера в статье не было, но думаю, что должно быть так).

Наличие имен серверов и версий во временной метке позволяет приложениям отслеживать отношения между версиями, скажем, находить общие корни (так, в приведенном выше примере было видно, что для [[S2,1],[S1,2]] и [[S3,1],[S1,2]] был общий предок - версия [S1,2]). Но, с другой стороны, временные метки могут расти в случае сбоев в сети, когда обновление версии объекта все время выполняется разными серверами. Поэтому в Dynamo используется простая схема ограничения роста временной метки: когда какой-то узел достигает определенного порога (например, во временную метку добавляется пара [Si,10], т.е. на узле Si объект модифицировался уже 10 раз), то самый старый элемент временной метки выбрасывается вообще. Потенциально, такая схема может создать сложности при слиянии версий, но на практике эта проблема ни разу не проявилась (или о ней решили не говорить ;).

Нужно еще сказать, что одна из основных целей, которые преследуются Dynamo - это высокая доступность для записи (т.н. always writable). Т.е. если приложение желает сохранить свои данные, то оно должно это сделать. Всегда. По определению ;) Именно поэтому разрешение конфликтов Dynamo выполняет не во время записи (поскольку из-за сбоев не все узлы, хранящие реплики объектов могут быть доступны для записи), а во время чтения. Поэтому-то приложения, запросив значение объекта, могут получить несколько значений с разными временными метками.

Из-за этого, как я понимаю, может произойти следующая ситуация: приложение прочитало объект D с узла S1, обновило его и попыталось записать обратно. Но узел S1 уже недоступен. Запись пошла на узел S2. После чего приложение вновь запросило объект D, но на этот раз узел S2 уже не доступен, а доступен S3, на котором лежит старая реплика с узла S1. Т.е. приложение вычитало старое значение после того, как успешно записало новое!

В принципе, если подумать, в подобной распределенной системе это вполне нормальное дело. Все довольно логично. Что меня в этом всем удивляет, так это то, что Amazon-овская "корзина покупок" работает с Dynamo. Ведь что может получиться: положил я себе в корзину книгу по Ruby (запись на S1), потом книгу по Java (запись на S2), только-только собрался класть книгу по C# (чтение объекта с S3) - глядь, а у меня в корзине только книга по Ruby. А где Java, спрашивается? ;) Вот это для меня оказалось очень и очень неожиданным, что "корзина покупок" в Amazon допускает такие коллизии (как раз они и разрешаются приложением посредством слияния параллельных веток объекта). Если бы я его проектировал, то я бы счел подобное поведение неприемлимым (и, вероятно, был бы не прав).

Пожалуй, пока на этом стоит остановиться. В следующий раз расскажу, как в Amazon Dynamo поддерживается распределение объектов между узлами и как выполняется репликация значений объектов.

Disclaimer: все вышеизложенное может являться следствием моих искренних заблуждений из-за неверного восприятия текста оригинальной статьи ;)