Продолжение рассказа о статье Dynamo: Amazon's Highly Available Key-value Store. Начало можно найти здесь.
Инфраструктура Dynamo состоит из сотен тысяч серверов, разбросанных по разным дата-центрам. Это полностью децентрализованная система, узлы которой используют основанные на gossip протоколы для установления взаимосвязей и обнаружения сбойных узлов.
Dynamo рассматривает ключи и значения сохраняемых объектов как непрозрачные блоки данных, структура которых Dynamo не интересует. Получив ключ объекта Dynamo строит его MD5 хеш и этот хеш потом используется для распределения объекта по узлам Dynamo.
Распределение ключей между узлами выполняется с помощью несколько модифицированной схемы consistent hashing. Все “адресное пространство” MD5 значений разбивается на диапазоны. И каждому узлу Dynamo случайным образом выделяется номер диапазона. Когда для какого-то конкретного ключа вычисляется MD5 хеш, то по значению хеша устанавливается номер диапазона, к которому принадлежит ключ. И запрос на обработку этого объекта передается соответствующему узлу.
Узлы провязываются в кольцо. Т.е. узел, обслуживающий первый диапазон, связывается с узлом, обслуживающим второй и последний диапазоны (второй узел связывается с первым и третьим узлами и т.д.). Т.е. если последовательно двигаться от одного узла к другому, то можно вернуться к самому первому узлу.
Каждый узел в кольце хранит значения объектов с (N-1) предшествующих ему узлов кольца. Например, пусть N=3 и есть часть кольца с узлами A, B, C, D. Узел D будет хранить объекты с ключами, попадающими в диапазон (C,D], а так же будет хранить копии объектов с ключами из диапазонов (A,B], (B,C]. Таким образом, значения объектов реплицируются на N узлов.
Такая схема хороша тем, что при изъятии или добавлении в кольцо нового узла, задействуются только соседи слева и справа от него (для обмена репликами). А остальные узлы остаются нетронутыми.
В Dynamo введено так же понятие виртуального узла. Т.е. в действительности каждый физический узел обслуживает не один диапазон из глобального адресного пространства, а несколько. Поэтому каждый физический узел выглядит как несколько виртуальных узлов. Такое отличие от схемы consistent hashing по мнению разработчиков более выгодно, поскольку позволяет эффективнее распределять нагрузку при добавлении или изъятии узла. И, что очень важно, количество виртуальных узлов, которые будет обслуживать физический узел, может определяться мощностью физического узла. Т.е. мощная машина может обслуживать 10 виртуальных узлов, а более слабая - всего 5.
Список узлов, отвечающих за хранение конкретного ключа, называется списком предпочтений (preference list). Благодаря тому, что по ключу можно определить номер диапазона, а узлы, обслуживающие соседние диапазоны провязаны в кольцо, каждый узел способен построить список предпочтений для своего диапазона.
Со списком предпочтений связана маленькая деталь. Список предпочтений содержит N элементов. Но из-за наличия виртуальных узлов может оказаться так, что количество физических узлов в списке предпочтений будет меньше. Поэтому список предпочтений строится так, чтобы в нем находились только разные физические узлы.
Для обеспечения согласованности и надежного хранения данных Dynamo использует схемы на основе кворума. При конфигурации системы задаются параметры N (количество реплик), R (минимальное количество узлов, которые должны участвовать в операции чтения данных) и W (минимальное количество узлов, которые должны участвовать в операции записи данных). Для обеспечения кворума значения R и W выбираются так, чтобы (R+W)>N. При этом, однако, слишком большие значения будут отрицательно влиять на отзывчивость системы.
Узел, на который Dynamo адресует запрос put или get, называется узлом-координатором. Обычно в качестве узла-координатора выбирается один из первых узлов в списке предпочтений для ключа.
Получив запрос get, узел-координатор адресует его первым живым N узлам из списка предпочтений. Затем ожидает R первых ответов. Получив их, узел-координатор возвращает ответ клиенту. Если же координатор получает несколько независимых версий объекта, то он возвращает клиенту все полученные версии, чтобы клиент сам выполнил их слияние.
Получив запрос put, узел-координатор модифицирует временную метку объекта и сохраняет ее локально. После чего передает эту версии первым живым N узлам из списка предпочтений и ожидает подтверждений от них. Получив W-1 подтверждение, координатор считает запись успешной.
Пожалуй, на этот раз достаточно. В следующий раз затрону тему репликации данных и восстановления после сбоев.
Комментариев нет:
Отправить комментарий