Консистентное хеширование
Перевод статьи "Consistent hashing, a guide & Go library".
Понятие и сам метод консистентного хеширования выглядит достаточно простым и мощным, но я все никак не мог с ним разобраться, пока мне не пришлось погрузиться в эту тему с головой. Для начала, стоит определить какие проблемы могут быть решены при его использовании:
Как определить какой из серверов использовать для хранения и извлечения ключей в распределенной системе? При условии, что все ноды получают примерно одинаковое количество ключей и при добавлении и удалении нод необходимо перемещать минимальное количество ключей.
Давайте предположим, что у нас есть четыре сервера: Chico, Harpo, Groucho и Zeppo. Эти серверы идентичны и ничего не знают друг о друге.
Для простоты, будем считать, что ключи представляют собой простой инкремент. Обычно, вы можете получить некоторое число по ключу и проверочной сумме. И затем можете взять модуль по количеству нод(в нашем случае mod4) для этого числа. Пример проиллюстрирован в табличке на рисунке. На удивление, это работает когда сеть достаточно стабильна и ноды не добавляются/пропадают.
Но что делать, если одна из нод, например Harpo, отвалится и вообще будет предрасположена к отключениям? У нас будет куча проблем. Используя ту же хеш-функцию, у нас будет похожий результат, но затем нам придется использовать взятие по модулю для трех нод, и результат будет совсем другой.
В этом случае придется перераспределить почти все ключи для всех нод. Но в этом нет никакого смысла, зачем менять кючи для серверов, которые прекрасно работают? Это лишняя работа, которая не дает профита. Теперь понятна причина, по которой стоит использовать консистентное хеширование.
Консистентное хеширование - способ создания распределенных хеш- таблиц, при котором вывод из строя одного или более серверов-хранилищ не приводит к необходимости полного переразмещения всех хранимых ключей и значений Взято отсюда: https://en.wikipedia.org/wiki/Consistent_hashing
Если мы будем использовать консистентное хеширование, то перераспределять нужно будет только те ключи, которые использовались сервером Harpo. Как правило, в большинстве статей, объясняющих такой тип хеширования, присутствует картинка с единичной окружностью и все объяснение ведется в соответствующих терминах. Давайте не будем отходить от традиции:
Временно, не будем обращать внимание как ноды расположены на единичной окружности. Давайте разместим ключи на той же окружности, как будто мы применили взятие по модулю для них (я понимаю, что пока это выглядит как размахивание руками, но я скоро вернусь к реализации). Для определения какие ключи к какой ноде относятся, просто будем перемещаться по часовой стрелке. Таким образом, ключ 1, например, относится к ноде Harpo.
В таком случае, что произойдет если упадет нода Harpo? Тогда вам придется работать с ключем 1 на другой ноде, которая будет по часовой стрелке за Harpo, но нет нужды перераспределять все ключи. Вуаля! Так же, это прекрасно работает с добавлением новых нод. Скажем, вы добавили сервер Gummo в вашу сеть. Вам все равно не нужно перераспределять ключи, мы сразу узнаем, какие из них теперь будут работать с новой нодой.
Консистентное хеширование прекрасно работает, если ваши ноды могут работать с различным количеством ключей(ноды разной "емкости"). В зависимости от хеш-функции, вы можете разместить "виртуальные" ноды по единичной окружности в случайном порядке. Для нод с большей "емкостью" нам нужно добавить больше "виртуальных" нод. Таким образом, в случае выхода из строя одного узла, ключи не просто переходят на следующую ноду, а равномерно распределяются по нескольким следующим нодам.
Реализация
Мы разобрались с теорией и теперь готовы перейти к практической части. Давайте реализуем библиотеку для консистентного хеширования. Мне было проблематично сделать это, пока я не нашел хорошую реализацию, поигрался с кодом, расставил логирование в разных местах. Наша реализация будет в значительной степени схожа с реализацией от stathat. Согласно оригинальному описанию алгоритма, необходимо использовать деревья, но мне больше нравится как это реализованно у stathat.
Давайте начнем с общего описания:
// Инициализация новой распределенной сеть из нод (готовим кольцо).
func NewRing() *Ring
// Добавление ноды в наше кольцо.
func (r *Ring) AddNode(id string)
// Удаление существующей ноды из кольца, если ноды нет,
// то возвращаем ErrNodeNotFound.
func (r *Ring) RemoveNode(id string) error
// Получение ноды, которая работает с указанным ключем. Возвращаемое
// значение это идентификатор ноды, который возвращает ф-ция `AddNode`.
func (r *Ring) Get(key string) string
Мы будем использовать алгоритм crc32 для генерации проверочной суммы наших ключей. К сожалению, объяснение что такое crc32 и как этот алгоритм работает выходят за рамки этой статьи. Просто знайте, что при любом входящем значении на выходе получится 32 битный юнит. В этом случае, на вход подается ip адрес ноды.
Суть в том, что мы будем хранить полученные проверочные суммы в массиве. Для каждого ключа также будем получать проверочную сумму и по ее значению определять местоположение этого ключа, точнее, с какая нода должна с ним работать. Если это значение будет выходить за рамки массива с нодами, то по умолчанию будет использоваться первая нода.
Для начала определим наше кольцо Ring, в котором будут собраны ноды Node
package consistenthash
// Ring это сеть из распределенных нод.
type Ring struct {
Nodes Nodes
}
// Nodes массив с нодаси.
type Nodes []Node
// Node определение одной ноды.
type Node struct {
Id string
HashId uint32
}
Теперь пишем функцию для инициализации Ring и Node:
package consistenthash
func NewRing() *Ring {
return &Ring{Nodes : Nodes{}}
}
func NewNode(id string) *Node{
return &Node{
Id : id,
hashedKey : crc32.Checksum([]byte(id)),
}
}
И необходимо реализовать функцию AddNode:
func (r *Ring) AddNode(id string) {
node := NewNode(id)
r.Nodes = append(r.Nodes, node)
sort.Sort(r.Nodes)
}
Почему мы используем sort.Sort? Тут стоит вернуться к единичной окружности. Как максимально точно реализовать эту самую единичную окружность? Одни из вариантов, это массив, в котором последний элемент указывает на первый. Для этого мы могли бы использовать связанные списки, но чуть позже вы заметите что это лишнее.
Если вы попытаетесь все это запустить, Go компилятор ругнется, потому что Nodes не реализуют sort.Sort интерфейс. Давайте быстро это исправим:
package consistenthash
func (n Nodes) Len() int { return len(n) }
func (n Nodes) Less(i, j int) bool { return n[i].HashId < n[j].HashId }
func (n Nodes) Swap(i, j int) { n[i], n[j] = n[j], n[i] }
И последнее, что нам осталось, это реализация метода Get:
func (r *Ring) Get(key string) string {
searchfn := func(i int) bool {
return r.Nodes[i].HashId >= crc32.Checksum([]byte(key))
}
i := sort.Search(r.Nodes.Len(), searchfn)
if i >= r.Nodes.Len() {
i = 0
}
return r.Nodes[i].Id
}
В методе sort.Search используется бинарный поиск для определения необходимой ноды в массиве. Если такой ноды не существует, то возвращается значение, указывающее куда ее нужно было бы добавить(в данной реализации нам это не нужно). Таким образом, если значение контрольной суммы выходит за рамки массива с нодами, мы просто указываем первую ноду. И на этом все.
Если вы хотите посмотреть как это работает, то можете найти исходники тут. Тесты в комплекте.
Помните, в начале статьи говорилось что консистентное хеширование это довольно простая, но достаточно мощная практика? Уверен, теперь вы мне верите. Вам следует знать, что консистентное хеширование впервые упоминается в исследованиях Akamai. Значительно более продвинутая версия консистентного хеширования используется в Chord алгоритме, который, по сути, представляет собой работу с хеш таблицей (ранее считалось, что Chord появился в результате разработки амазоновской dynamodb, что не совсем верно).
В данный момент, я все еще пытаюсь разобраться с Chord алгоритмом, понять как он работает(не говоря уже о реализации). Надеюсь, как только у меня получится, то напишу еще одну статью. Я получил много удовольствия, изучая консистентное хеширования и написав этот пост. Надеюсь, вам то же понравилось. Если вы нашли ошибки или у вас есть что сказать по этому поводу, обязательно пишите мне в твиттер @sent-hil.