Последовательное хеширование - Consistent hashing - Wikipedia

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

История

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

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

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

Базовая техника

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

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

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

Практические дополнения

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

Сравнение с Rendezvous Hash и другими альтернативами

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

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

Сложность

Асимптотический временные сложности за ${ displaystyle N}$ узлы (или слоты) и ${ displaystyle K}$ ключи
	Классическая хеш-таблица	Последовательное хеширование
добавить узел	${ Displaystyle О (К)}$	${ Displaystyle О (К / N + журнал N)}$
удалить узел	${ Displaystyle О (К)}$	${ Displaystyle О (К / N + журнал N)}$
добавить ключ	${ displaystyle O (1)}$	${ Displaystyle О ( журнал N)}$
удалить ключ	${ displaystyle O (1)}$	${ Displaystyle О ( журнал N)}$

В ${ Displaystyle О (К / Н)}$ средняя стоимость перераспределения ключей и ${ Displaystyle О ( журнал N)}$ сложность согласованного хеширования связана с тем, что бинарный поиск между углами узлов требуется найти следующий узел на кольце.^{[нужна цитата ]}

Примеры

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

Диван автоматическое разбиение данных ^[5]
OpenStack's Служба хранилища объектов Swift^[6]
Компонент секционирования системы хранения Amazon Динамо^[7]
Разделение данных в Apache Cassandra^[8]
Разделение данных в Волдеморт^[9]
Акка согласованный маршрутизатор хеширования^[10]
Риак, распределенная база данных "ключ-значение"^[11]
Gluster, файловая система сетевого хранилища^[12]
Акамай сеть доставки контента^[13]
Раздор приложение чата^[14]
Балансировщик сетевой нагрузки Maglev^[15]
Разделение данных в Azure Cosmos DB

внешняя ссылка

[KargerEtAl1997-1] а ^б ^c Karger, D .; Lehman, E .; Лейтон, Т.; Panigrahy, R .; Левин, М .; Левин, Д. (1997). Согласованное хеширование и случайные деревья: протоколы распределенного кэширования для устранения горячих точек во всемирной паутине. Материалы двадцать девятой ежегодной ACM Симпозиум по теории вычислений. ACM Press Нью-Йорк, Нью-Йорк, США. С. 654–663. Дои:10.1145/258533.258660.

[nuggets-2] а ^б ^c ^d ^е ^ж ^грамм Брюс Мэггс и Рамеш Ситараман (2015). «Алгоритмические самородки в доставке контента» (PDF). Обзор компьютерных коммуникаций ACM SIGCOMM. 45 (3).

[3] Nygren., E .; Ситараман Р. К .; Солнце, Дж. (2010). «Сеть Akamai: платформа для высокопроизводительных интернет-приложений» (PDF). Обзор операционных систем ACM SIGOPS. 44 (3): 2–19. Дои:10.1145/1842733.1842736. S2CID 207181702. В архиве (PDF) из оригинала 13 сентября 2012 г.. Получено 19 ноября, 2012.

[KargerEtAl1999-4] Karger, D .; Шерман, А .; Berkheimer, A .; Bogstad, B .; Dhanidina, R .; Iwamoto, K .; Kim, B .; Маткинс, Л .; Йерушалми Ю. (1999). «Веб-кеширование с постоянным хешированием». Компьютерная сеть. 31 (11): 1203–1213. Дои:10.1016 / S1389-1286 (99) 00055-9. Архивировано из оригинал на 2008-07-21. Получено 2008-02-05.

[5] "Что такое Membase?". Получено 2020-10-29.

[6] Холт, Грег (февраль 2011 г.). «Построение последовательного хэширующего кольца». openstack.org. Получено 2019-11-17.

[Amazon2007-7] DeCandia, G .; Hastorun, D .; Jampani, M .; Какулапати, G .; Лакшман, А .; Пильчин, А .; Sivasubramanian, S .; Vosshall, P .; Фогельс, Вернер (2007). «Dynamo: высокодоступный магазин ключевых значений Amazon» (PDF). Материалы 21-го симпозиума ACM по принципам операционных систем. 41 (6): 205–220. Дои:10.1145/1323293.1294281. Получено 2018-06-07.

[Lakshman2010b-8] Лакшман, Авинаш; Малик, Прашант (2010). «Кассандра: децентрализованная структурированная система хранения». Обзор операционных систем ACM SIGOPS. 44 (2): 35–40. Дои:10.1145/1773912.1773922.

[9] «Дизайн - Волдеморт». www.project-voldemort.com/. Архивировано из оригинал 9 февраля 2015 г.. Получено 9 февраля 2015. Последовательное хеширование - это метод, позволяющий избежать этих проблем, и мы используем его для вычисления местоположения каждого ключа в кластере.

[akka-routing-10] «Маршрутизация Akka». akka.io. Получено 2019-11-16.

[riak-consistent-hashing-11] "Концепции Риака". Архивировано из оригинал в 2015-09-19. Получено 2016-12-06.

[GlusterFS_Algorithms:_Distribution-12] «Алгоритмы GlusterFS: Распределение». gluster.org. 2012-03-01. Получено 2019-11-16.

[13] Roughgarden, Тим; Валиант, Грегори (28 марта 2016). «Современный алгоритмический инструментарий» (PDF). stanford.edu. Получено 2019-11-17.

[how_discord_scaled_elixir_to_5,000,000_concurrent_users-14] Вишневский, Станислав (06.07.2017). «Как Discord масштабировал Эликсир до 5 000 000 одновременных пользователей». Получено 2019-11-17.

[maglev-15] Eisenbud, Daniel E .; Йи, Ченг; Контавалли, Карло; Смит, Коди; Кононов, Роман; Манн-Хильшер, Эрик; Чилингироглу, Ардас; Чейни, Бин; Шан, Вентао; Хосейн, Джинна Дилан. "Maglev: быстрый и надежный программный балансировщик сетевой нагрузки" (PDF). Получено 2019-11-17.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]