Согласованное хеширование

В информатике согласованное хеширование является особым видом хеширования таким образом, что при изменении размера хэш-таблицы только $n\; /\; m\; \{\backslash \; displaystyle\; n\; /\; m\}$ключи должны быть переназначены в среднем где $n\; \{\backslash \; displaystyle\; n\}$- количество клавиш, а $m\; \{\backslash \; displaystyle\; m\}$- количество слотов. Напротив, в большинстве традиционных хэш-таблиц изменение количества слотов массива приводит к переназначению почти всех ключей, поскольку отображение между ключами и слотами определяется с помощью модульной операции. Согласованное хеширование - это частный случай рандеву-хеширования, который имеет концептуально более простой алгоритм и был впервые описан в 1996 году. Согласованное хеширование впервые появилось в 1997 году и использует другой алгоритм.

• 1 История
• 2 Базовая техника
• 3 Практические расширения
• 4 Сравнение с рандеву-хешированием и другими альтернативами
• 5 Сложность
• 6 Примеры
• 7 Ссылки
• 8 Внешние ссылки

Термин «согласованное хеширование» был введен Дэвидом Каргером и др. в MIT для использования в распределенном кэшировании. В этой академической статье 1997 года был введен термин «согласованное хеширование» как способ распределения запросов между изменяющейся популяцией веб-серверов. Затем каждый слот представлен сервером в распределенной системе. Для добавления сервера и удаления сервера (например, из-за сбоя) требуется только $num\; \_\; keys\; /\; num\; \_\; slots\; \{\backslash \; displaystyle\; num\; \backslash \; \_keys\; /\; num\; \backslash \; \_slots\}$элементов - перемешивается при изменении количества слотов (то есть серверов). Авторы упоминают линейное хеширование и его способность обрабатывать последовательное добавление и удаление серверов, в то время как согласованное хеширование позволяет добавлять и удалять серверы в произвольном порядке.

Teradata использовали этот метод в своей распределенной базе данных, выпущенной в 1986 году, хотя они не использовали этот термин. Teradata по-прежнему использует концепцию хэш-таблицы для выполнения именно этой цели. Akamai Technologies была основана в 1998 году учеными Дэниелом Левином и Ф. Томсон Лейтон (соавторы статьи, посвященной «согласованному хешированию»). В сети доставки контента Akamai согласованное хеширование используется для балансировки нагрузки внутри кластера серверов ,, а алгоритм стабильного брака используется для балансировки нагрузки между кластерами.

Согласованное хеширование также использовалось для уменьшения воздействия частичных сбоев системы в больших веб-приложениях, чтобы обеспечить надежное кэширование без возникновения общесистемных последствий сбоя. Согласованное хеширование также является краеугольным камнем распределенных хеш-таблиц (DHT), которые используют хеш-значения для разделения пространства ключей по распределенному набору узлов, а затем создают наложенную сеть из подключенных узлов, которые обеспечивают эффективное извлечение узлов по ключу.. Хеширование рандеву, разработанное в 1996 году, представляет собой более простой и общий метод. Он достигает целей согласованного хеширования с использованием совершенно другого алгоритма наивысшего случайного веса (HRW).

Рассмотрим проблему балансировки нагрузки, когда набор объектов (например, веб-страницы или сегменты видео) должен быть назначен набору $n\; \{\backslash \; displaystyle\; n\}$серверов. Один из способов равномерного распределения объектов по серверам $n\; \{\backslash \; displaystyle\; n\}$- использовать стандартную хеш-функцию и поместить объект $o\; \{\backslash \; displaystyle\; o\}$в сервер с идентификатором $hash\; (o)\; (mod\; n)\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{hash\}\}\; (o)\; \backslash ;\; \backslash \; left\; (\{\backslash \; text\; \{mod\}\}\; n\; \backslash \; right)\}$Однако, если сервер добавляется или удаляется (т. Е. Изменяется $n\; \{\backslash \; displaystyle\; n\}$), назначение сервера почти каждому объекту в системе может измениться. Это проблематично, поскольку серверы часто выходят из строя или запускаются, и для каждого такого события потребуется переназначить почти все объекты и переместить их на новые серверы.

Последовательное хеширование сначала сопоставляет объекты и серверы с единичным кругом. Затем объект сопоставляется со следующим сервером, который появляется в круге по часовой стрелке.

Согласованное хеширование было разработано, чтобы избежать проблемы необходимости изменения назначения каждого объекта серверу при добавлении или удалении сервера. Основная идея состоит в том, чтобы использовать хэш-функцию для случайного отображения объектов и серверов в единичный круг. Затем каждый объект назначается следующему серверу, который появляется в круге по часовой стрелке. Это обеспечивает равномерное распределение объектов по серверам. Но, что более важно, если сервер выходит из строя и удаляется из круга, только объекты, которые были сопоставлены с отказавшим сервером, должны быть переназначены следующему серверу в порядке по часовой стрелке. Аналогично, если добавляется новый сервер, он добавляется в единичный круг, и только объекты, сопоставленные с этим сервером, должны быть переназначены. Важно отметить, что при добавлении или удалении сервера подавляющее большинство объектов сохраняют свои предыдущие назначения сервера.

Для эффективного использования согласованного хеширования для балансировки нагрузки на практике необходим ряд расширений базовой техники. В приведенной выше базовой схеме, если сервер выходит из строя, все его объекты переназначаются следующему серверу по часовой стрелке, потенциально удваивая нагрузку на этот сервер. Это может быть нежелательно. Чтобы обеспечить более равномерное перераспределение объектов при сбое сервера, каждый сервер может быть хэширован в нескольких местах на единичном круге. Когда сервер выходит из строя, объекты, назначенные каждой из его реплик в единичном круге, будут переназначены другому серверу по часовой стрелке, таким образом распределяя объекты более равномерно. Другое расширение относится к ситуации Flash Crowd, когда один объект становится «горячим», к нему обращаются большое количество раз, и его придется размещать на нескольких серверах. В этой ситуации объект может быть назначен нескольким смежным серверам путем обхода единичного круга по часовой стрелке. Более сложное практическое рассмотрение возникает, когда два объекта, которые хешируются рядом друг с другом в единичном круге, становятся «горячими» одновременно. В этом случае оба объекта будут использовать один и тот же набор смежных серверов в единичном круге. Эту ситуацию можно улучшить, если каждый объект выбирает другую хеш-функцию для сопоставления серверов с единичным кругом.

Rendezvous hashing, разработанным в 1996 году, проще и более общий метод, и позволяет полностью распределенное соглашение по набору $k\; \{\backslash \; displaystyle\; k\}$вариантов из возможного набора $n\; \{\backslash \; displaystyle\; n\}$варианты. Фактически можно показать, что согласованное хеширование - это частный случай хеширования рандеву. Из-за своей простоты и универсальности Rendezvous Hashing теперь используется вместо согласованного хеширования во многих приложениях.

Если значения ключей всегда будут увеличиваться монотонно, альтернативный подход с использованием хэш-таблицы с монотонными ключами может быть более подходящим, чем согласованное хеширование.

Асимптотическая временная сложность для $N\; \{\backslash \; displaystyle\; N\}$узлов (или слотов) и $K\; \{\backslash \; displaystyle\; K\}$ключи

	Классическая хеш-таблица	Согласованное хеширование
добавить узел	$O\; (K)\; \{\backslash \; displaystyle\; O\; (K)\}$	$O\; (K\; /\; N\; +\; log\; \; N)\; \{\; \backslash \; displaystyle\; O\; (K\; /\; N\; +\; \backslash \; log\; N)\}$
удалить узел	$O\; (K)\; \{\backslash \; displaystyle\; O\; (K)\}$	$O\; (K\; /\; N\; +\; log\; \; N)\; \{\backslash \; displaystyle\; O\; (K\; /\; N\; +\; \backslash \; log\; N)\}$
добавить ключ	$O\; (1)\; \{\backslash \; displaystyle\; O\; (1)\}$	$O\; (log\; \; N)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; N)\}$
удалить ключ	$O\; (1)\; \{\backslash \; displaystyle\; O\; (1)\}$	$O\; (log\; \; N)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; N)\}$

The $O\; (K\; /\; N)\; \{\backslash \; displaystyle\; O\; (K\; /\; N)\}$- средняя стоимость перераспределения ключей и $O\; (log\; \; N)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; N)\}$сложность для согласованного хеширования из того факта, что для поиска следующего узла в кольце требуется двоичный поиск среди углов узлов.

Известные примеры использования согласованного хеширования включают:

• Couchbase автоматическое разделение данных
• OpenStack Object Storage Service Swift
• Компонент разделения системы хранения Amazon Dynamo
• Разделение данных в Apache Cassandra
• Data разделение на разделы в Voldemort
• Akka, согласованном маршрутизаторе хеширования
• Riak, распределенной базе данных «ключ-значение»
• Gluster, файловой системе сетевого хранилища
• Akamai сеть доставки контента
• Discord приложение чата
• балансировщик сетевой нагрузки Maglev
• Разделение данных в Azure Cosmos DB

• Понимание согласованного хеширования
• Согласованное хеширование, Майкл Нильсен 3 июня 2009 г.
• Согласованное хеширование, Дэнни Левин и создание Akamai
• Последовательное хеширование с переходом: быстрое, минимальное количество памяти, согласованное Ха sh Алгоритм
• Рандеву-хеширование: альтернатива согласованному хешированию
• Реализации на разных языках:
  • C
  • C ++
  • C#
  • Erlang
  • Go
  • Java
  • PHP
  • Ruby
  • Python
  • Python ( снова)
  • Perl
  • Perl6