Продолжение рассказа о статье Dynamo: Amazon's Highly Available Key-value Store. Предыдущие части: Amazon's Dynamo: версионность объектов и Amazon's Dynamo: распределение объектов по узлам системы.
Одним из главных требований к Amazon Dynamo является высокая доступность. Как следствие, в Dynamo не используется традиционная система кворумов. Поскольку при сбое в системе кворум может не набраться – просто не будет достаточного количества живых узлов для репликации данных.
Поэтому в Dynamo используется т.н. sloppy quorum: все операции чтения и записи выполняются на первых N живых узлах из списка предпочтений. А эти узлы не обязательно будут первыми N узлами при последовательном обходе кольца узлов с диапазонами хеш-значений.
Например, пусть есть кольцо с узлами A, B, C, D, ..., Z и N=3 (N – это количество узлов, на которых должно быть зафиксировано значение объекта). Нужно сохранить ключ, который попадает в диапазон (Z,A]. Этот ключ должен храниться на узле A. Но если узел A сейчас недоступен, то его реплика может быть записана на узле D (поскольку N=3, то в обычное время реплика объекта попадает только на узлы A, B и C, но не D). При этом в метаданных реплики помечается, что она не принадлежит D и должна быть передана на узел A. Когда такая реплика попадает на узел D, он начинает периодически опрашивать узел A. И когда обнаруживает, что A опять вернулся в строй, то передает эту реплику узлу A, уничтожая ее у себя.
Такой подход позволяет Dynamo оставаться работоспособным даже при выходе из строя изрядного количества узлов. В некоторых случаях, для оптимизации быстродействия можно пойти даже на то, чтобы установить значение W (количество узлов, которые должны подтвердить запись объекта) равным 1. В таком случае запись будет завершаться успешно даже если в сети оказывается всего один узел, подтвердивший запись объекта.
Еще одно важное дополнение к общей схеме распределения ключей по кольцу узлов и репликации: поскольку Dynamo должна выдерживать оказ не только отдельных узлов, но и целых дата-центров, то список предпочтений для ключа формируется таким образом, чтобы в него входили узлы из разных дата-центров. Поэтому даже если один дата-центр выходит из строя, то значение объекта оказывается доступным на узлах в других дата-цетров. При этом сами дата-центры соединены между собой высокоскоростными магистралями для того, чтобы справляться с большими объемами реплицируемых данных.
Другой стороной системы репликации в Dynamo является снижение расходов на синхронизацию реплик после ввода отказавшего узла в строй. Поскольку каждый узел в Dynamo хранит большое количество объектов, то нужно быстро выбрать те из них, значение которых изменилось с момента последней репликации. Для этого в Dynamo используется механизм на основе хеш-деревьев (они же Merkle tree).
Смысл хэш-дерева в том, что значение родителя является хешем от значений его потомков. Т.е., если изменяется значение самого нижнего узла дерева (объекта), то изменяются хеши во всех родителях этого узла и, в конце-концов, в вершине дерева. Поскольку дерево состоит из нескольких независимых друг от друга поддеревьев, то это позволяет распараллеливать сравнение двух хэш-деревьев -- ведь их поддеревья можно сравнивать независимо друг от друга. Например, пусть есть два хэш-дерева у вершины которых два потомка. Если значение в вершине двух деревьев совпадают – значит деревья одинаковые (синхронизации реплик не требуется). Если не совпадает, значит можно отдельно сравнить левые поддеревья и правые поддеревья и т.д.
Этот принцип и используется в Dynamo: каждый узел хранит хэш-дерево для всех своих ключей. Когда приходит время синхронизации, узлы обмениваются сначала вершинами своих хэш-деревьев. Затем, при необходимости, вершинами поддеревьев и т.д. Такой механизм успешно работает. Однако для этого разработчикам Dynamo пришлось подумать над эффективной системой распределения ключей по узлам. Поскольку в худших случаях при перераспределении диапазонов (при вводе в строй новых узлов, например) перестройка хэш-деревьев оказывалась слишком дорогостящей операцией.
С темой репликации данных связана и еще одна тема – определение сбойных узлов во время работы Dynamo.
Ввод новых узлов и плановое отключение старых узлов выполняется в Dynamo только явным образом администратором: с помощью специального инструмента администратор подключает или отключает узел к кольцу. Получивший соответствующую команду узел использует Gossip-подобный протокол для извещения остальных узлов о своем статусе. Этот протокол позволяет узлам согласовывать свое видение текущего состояния кольца узлов. Так же каждый узел периодически связывается с любым другим случайным узлом для того, чтобы синхронизировать информацию о состоянии истории подключения/отключения узлов (почему-то эта история подлежит долговременному хранению и нуждается в синхронизации).
При обслуживании запросов пользователей узлы Dynamo используют только "локальное видение" состояния других узлов. Например, если A отсылает реплики узлам B и C, а получает ответ только от C, то A спокойно считает, что узел B вышел из строя. Даже если с узлом B все нормально и узел B успешно отвечает на запросы узла C. Для узла A все это не важно – узел B не ответил, значит он мертв. Узел A больше не будет адресовать запросы B, вместо этого он будет задействовать другие доступные узлы. Но узел A будет периодически пинговать B и, когда B ответит на пинг, узел A вновь занесет B в свой список живых узлов.
Для того, чтобы в Dynamo не произошло расщепления на несколько независимых колец (т.н. logical partition вследствие сбоев нескольких узлов, связывавших разные группы), используются т.н. seed-узлы. Это узлы с фиксированными именами, про которые знают все остальные узлы Dynamo. Периодически каждый узел должен связаться с одним из seed-ов и обменяться с ним информацией о доступных узлах. Благодаря этому узлы, оказавшиеся в независимых кольцах, узнают о существовании других колец и, тем самым, устраняется возникший разрыв.
В Dynamo используется децентрализованный протокол обнаружения сбоев, за деталями которого авторы статьи адресуют читателя к работе On Scalable and efficient distributed failure detectors.
За сим данную часть рассказа об Amazon Dynamo можно закончить. Пожалуй, затем последует еще одна маленькая заметка с несколькими моментами, которые меня в статье об Amazon Dymano зацепили.
