Последовательное хеширование

Метод хеширования

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

Последовательное хеширование равномерно распределяет ключи кэша по сегментам , даже если некоторые сегменты выходят из строя или становятся недоступными. ^[3]

История

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

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

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

Rendezvous hashing , разработанный в 1996 году, является более простой и более общей техникой ^{[ требуется ссылка ]} . Он достигает целей последовательного хеширования, используя совершенно другой алгоритм с наибольшим случайным весом (HRW).

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

В этом случае использование последовательного хеширования приведет к тому, что «BLOB» будет сохранен на сервере 139. BLOB сопоставляется со следующим сервером, который появляется на круге по часовой стрелке, пока не достигнет сервера, который ${\displaystyle \zeta \leq {\text{server ID}}}$

В задаче балансировки нагрузки , например, когда BLOB должен быть назначен одному из серверов в кластере , стандартная хэш-функция может быть использована таким образом, что мы вычисляем значение хэша для этого BLOB, предполагая, что результирующее значение хэша равно , мы выполняем модульную операцию с количеством серверов ( в данном случае), чтобы определить сервер, на котором мы можем разместить BLOB: ; следовательно, BLOB будет размещен на сервере, преемником которого является в этом случае. Однако, когда сервер добавляется или удаляется во время сбоя или масштабирования (при изменениях), все BLOB на каждом сервере должны быть переназначены и перемещены из-за повторного хэширования , но эта операция является дорогостоящей. ${\displaystyle n}$ ${\displaystyle \beta }$ ${\displaystyle n}$ ${\displaystyle \zeta =\beta \ \%\ n}$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle \zeta }$ ${\displaystyle n}$

Согласованное хеширование было разработано для того, чтобы избежать проблемы необходимости переназначать каждый BLOB при добавлении или удалении сервера по всему кластеру. Основная идея заключается в использовании хеш-функции, которая сопоставляет как BLOB, так и серверы с единичной окружностью, обычно радианной. Например, (где — хэш BLOB или идентификатора сервера, такого как IP-адрес или UUID ). Затем каждый BLOB назначается следующему серверу, который появляется на окружности по часовой стрелке. Обычно алгоритм двоичного поиска или линейный поиск используется для поиска «места» или сервера для размещения этого конкретного BLOB в или сложностях соответственно; и в каждой итерации, которая происходит по часовой стрелке, выполняется операция (где — значение сервера в кластере) для поиска сервера для размещения BLOB. Это обеспечивает равномерное распределение BLOB по серверам. Но, что более важно, если сервер выходит из строя и удаляется из окружности, только BLOB, которые были сопоставлены с отказавшим сервером, необходимо переназначить следующему серверу по часовой стрелке. Аналогично, если добавляется новый сервер, он добавляется в единичный круг, и переназначать нужно только BLOB-объекты, сопоставленные с этим сервером. ${\displaystyle 2\pi }$ ${\displaystyle \zeta =\Phi \ \%\ 360}$ ${\displaystyle \Phi }$ ${\displaystyle O(\log N)}$ ${\displaystyle O(N)}$ ${\displaystyle \zeta \ \leq \ \Psi }$ ${\displaystyle \Psi }$

Важно отметить, что при добавлении или удалении сервера подавляющее большинство BLOB сохраняют свои предыдущие назначения сервера, а добавление сервера приводит к перемещению только части BLOB. Хотя процесс перемещения BLOB между серверами кэширования в кластере зависит от контекста, обычно вновь добавленный сервер кэширования идентифицирует своего «преемника» и перемещает все BLOB, отображение которых принадлежит этому серверу (т. е. чье хэш-значение меньше, чем у нового сервера), с него. Однако в случае кэширования веб-страниц в большинстве реализаций перемещение или копирование не требуется, если кэшированный BLOB достаточно мал. Когда запрос попадает на вновь добавленный сервер кэширования, происходит промах кэширования , и делается запрос к фактическому веб-серверу , а BLOB кэшируется локально для будущих запросов. Избыточные BLOB на ранее используемых серверах кэширования будут удалены в соответствии с политиками вытеснения кэша . ^[10] ${\displaystyle n^{th}}$ ${\displaystyle 1/n}$

Выполнение

Пусть и будут хэш-функциями, используемыми для BLOB и уникального идентификатора сервера соответственно. На практике двоичное дерево поиска (BST) используется для динамического поддержания в пределах кластера или хэширования, а для поиска преемника или минимума в пределах BST используется обход дерева . ${\displaystyle h_{b}(x)}$ ${\displaystyle h_{s}(x)}$ ${\displaystyle {\text{server ID}}}$

Вставка в кластер ${\displaystyle x}$

Пусть будет хэш-значением BLOB, таким что, где и . Чтобы вставить , найдите преемника в BST s. Если больше всех s, BLOB помещается на сервер с наименьшим значением. ${\displaystyle \beta }$ ${\displaystyle h_{b}(x)=\beta \ \%\ 360}$ ${\displaystyle x\in \mathrm {BLOB} }$ ${\displaystyle h_{b}(x)=\zeta }$ ${\displaystyle x}$ ${\displaystyle \zeta }$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle \zeta }$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle {\text{server ID}}}$

Удаление из кластера ${\displaystyle x}$

Найти преемника в BST, удалить BLOB из возвращенного . Если преемника нет, удалить BLOB из наименьшего из s. ^[11] ${\displaystyle \zeta }$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle \zeta }$ ${\displaystyle {\text{server ID}}}$

Вставьте сервер в кластер

Пусть будет хэш-значением идентификатора сервера таким, что, где и . Переместить все BLOB, хэш-значение которых меньше , с сервера, чей преемник . Если является наибольшим из всех s, переместить соответствующие BLOB из наименьшего из s в . ^[12] ${\displaystyle \Phi }$ ${\displaystyle h_{s}(x)=\Phi \ \%\ 360}$ ${\displaystyle x\in \{{\text{IP address, UUID}}\}}$ ${\displaystyle h_{s}(x)=\theta }$ ${\displaystyle \theta }$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle \theta }$ ${\displaystyle \theta }$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle \theta }$

Удалить сервер из кластера

Найти преемника в BST, переместить BLOB-ы из на его сервер-преемник. Если преемника нет, переместить BLOB-ы в наименьший из s. ^[13] ${\displaystyle \theta }$ ${\displaystyle \theta }$ ${\displaystyle \theta }$ ${\displaystyle {\text{server ID}}}$

Сокращение дисперсии

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

Практические расширения

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

Сравнение с рандеву-хешированием и другими альтернативами

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

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

Сложность

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

Примеры

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

• Автоматизированное разделение данных Couchbase ^[15]
• Служба хранения объектов OpenStack Swift ^[16]
• Компонент секционирования системы хранения данных Amazon Dynamo ^[17]
• Разделение данных в Apache Cassandra ^[18]
• Разделение данных в ScyllaDB ^[19]
• Разделение данных в Voldemort ^[20]
• Маршрутизатор Akka с последовательным хешированием ^[21]
• Riak , распределенная база данных «ключ-значение» ^[22]
• Gluster , сетевая файловая система хранения данных ^[23]
• Сеть доставки контента Akamai ^[24]
• Приложение для чата Discord ^[25]
• Балансировка нагрузки gRPC- запросов к распределенному кэшу в SpiceDB ^[26]
• Алгоритм хорды ^[27]
• Система хранения объектов MinIO ^[28]

Ссылки

1. Karger, D.; Lehman, E.; Leighton, T .; Panigrahy, R.; Levine, M.; Lewin, D. (1997). Согласованное хеширование и случайные деревья: распределенные протоколы кэширования для устранения горячих точек во Всемирной паутине. Труды двадцать девятого ежегодного симпозиума ACM по теории вычислений . ACM Press New York, NY, USA. стр. 654–663. doi :10.1145/258533.258660.
2. Брюс Мэггс и Рамеш Ситараман (2015). «Алгоритмические крупицы в доставке контента» (PDF) . Обзор компьютерной связи ACM SIGCOMM . 45 (3).
3. Проектирование распределенных системных шаблонов и парадигм для масштабируемых, надежных сервисов . O'Reilly Media. 2018. ISBN 9781491983607.
4. Roughgarden & Valiant 2021, стр. 2.
5. Roughgarden & Valiant 2021, стр. 7.
6. Roughgarden & Valiant 2021, стр. 8.
7. I. Stoica et al., «Chord: масштабируемый протокол однорангового поиска для интернет-приложений», в IEEE/ACM Transactions on Networking, т. 11, № 1, стр. 17–32, февраль 2003 г., doi: 10.1109/TNET.2002.808407.
8. Nygren., E.; Sitaraman RK; Sun, J. (2010). «Сеть Akamai: платформа для высокопроизводительных интернет-приложений» (PDF) . Обзор операционных систем ACM SIGOPS . 44 (3): 2–19. doi :10.1145/1842733.1842736. S2CID  207181702. Архивировано (PDF) из оригинала 30 ноября 2022 г. . Получено 29 августа 2023 г. .
9. Karger, D.; Sherman, A.; Berkheimer, A.; Bogstad, B.; Dhanidina, R.; Iwamoto, K.; Kim, B.; Matkins, L.; Yerushalmi, Y. (1999). "Web Caching with Consistent Hashing". Computer Networks . 31 (11): 1203–1213. doi :10.1016/S1389-1286(99)00055-9. Архивировано из оригинала 21.07.2008 . Получено 05.02.2008 .
10. Roughgarden & Valiant 2021, стр. 6.
11. Moitra 2016, стр. 2.
12. Moitra 2016, стр. 2–3.
13. Moitra 2016, стр. 3.
14. Roughgarden & Valiant 2021, стр. 6–7.
15. «Что такое Membase?». 16 декабря 2014 г. Получено 29 октября 2020 г.
16. Холт, Грег (февраль 2011 г.). «Создание согласованного кольца хеширования». openstack.org . Получено 17 ноября 2019 г.
17. ДеКандия, Г.; Хасторун, Д.; Джампани, М.; Какулапати, Г.; Лакшман, А.; Пилчин, А.; Сивасубраманиан, С.; Воссхалл, П.; Фогельс, Вернер (2007). "Dynamo" (PDF) . Обзор операционных систем ACM Sigops . 41 (6): 205–220. doi :10.1145/1323293.1294281 . Получено 07.06.2018 .
18. Лакшман, Авинаш; Малик, Прашант (2010). «Кассандра: децентрализованная структурированная система хранения». Обзор операционных систем ACM SIGOPS . 44 (2): 35–40. doi :10.1145/1773912.1773922. S2CID  916681.
19. "Сравнение NoSQL: MongoDB против ScyllaDB". benchant.com . Получено 21 марта 2024 г. .
20. "Design -- Voldemort". www.project-voldemort.com/ . Архивировано из оригинала 9 февраля 2015 г. . Получено 9 февраля 2015 г. . Последовательное хеширование — это метод, который позволяет избежать этих проблем, и мы используем его для вычисления местоположения каждого ключа в кластере.
21. "Akka Routing". akka.io . Получено 2019-11-16 .
22. "Riak Concepts". Архивировано из оригинала 2015-09-19 . Получено 2016-12-06 .
23. "Алгоритмы GlusterFS: Распределение". gluster.org . 2012-03-01 . Получено 2019-11-16 .
24. Рафгарден, Тим; Валиант, Грегори (2016-03-28). "Modern Algorithmic Toolbox" (PDF) . stanford.edu . Получено 2019-11-17 .
25. Вишневский, Станислав (2017-07-06). «Как Discord масштабировал Elixir до 5 000 000 одновременных пользователей» . Получено 2022-08-16 .
26. "Consistent Hash Load Balancing for gRPC". 24 ноября 2021 г. Получено 04.09.2023 г.
27. Stoica, I. ; Morris, R.; Liben-Nowell, D.; Karger, D.; Kaashoek, MF; Dabek, F.; Balakrishnan, H. (25 февраля 2003 г.). «Chord: масштабируемый протокол однорангового поиска для интернет-приложений». IEEE/ACM Transactions on Networking . 11 (1): 17–32. doi :10.1109/TNET.2002.808407. S2CID  221276912.
28. "MinIO Versioning, Metadata and Storage Deep Dive" . Получено 2023-10-24 .

Цитируемые работы

• Moitra, Ankur (10 февраля 2016 г.). "Advanced Algorithms, 6.854" (PDF) . Массачусетский технологический институт . Архивировано (PDF) из оригинала 13 апреля 2021 г. . Получено 8 октября 2021 г. .
• Roughgarden, Tim; Valiant, Gregory (28 марта 2021 г.). «Современный набор алгоритмических инструментов, введение в согласованное хеширование» (PDF) . Стэнфордский университет . Архивировано (PDF) из оригинала 25 июля 2021 г. . Получено 7 октября 2021 г. .

Внешние ссылки

• Понимание последовательного хеширования
• Последовательное хеширование Майкла Нильсена от 3 июня 2009 г.
• Последовательное хеширование, Дэнни Левин и создание Akamai
• Jump Consistent Hashing: быстрый, требующий минимальной памяти, последовательный алгоритм хеширования
• Rendezvous Hashing: альтернатива Consistent Hashing
• Реализации на разных языках:
  • С
  • С++
  • С#
  • Эрланг
  • Идти
  • Ява
  • PHP
  • Рубин
  • Питон
  • Питон (снова)
  • Перл
  • Perl6