Из Википедии, бесплатной энциклопедии
  (Перенаправлено из стабильного хеширования )
Перейти к навигации Перейти к поиску

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

История [ править ]

Термин «согласованное хеширование» был введен Дэвидом Каргером и др. в MIT для использования в распределенном кэшировании. В этой академической статье 1997 года был введен термин «согласованное хеширование» как способ распределения запросов между изменяющейся популяцией веб-серверов. Затем каждый слот представлен сервером в распределенной системе. Добавление сервера и удаление сервера (скажем, из-за сбоя) требует только перетасовки элементов при изменении количества слотов (т. Е. Серверов). Авторы упоминают линейное хеширование и его способность обрабатывать последовательное добавление и удаление серверов, в то время как согласованное хеширование позволяет добавлять и удалять серверы в произвольном порядке. [1]

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

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

Базовая техника [ править ]

Рассмотрим проблему балансировки нагрузки, когда набор объектов (скажем, веб-страниц или сегментов видео) должен быть назначен набору серверов. Одним из способов равномерного распределения объектов по серверам является использование стандартной хеш-функции и размещение объекта на сервере с идентификатором. Однако, если сервер добавляется или удаляется (т. Е. Изменяется), назначение сервером почти каждого объекта в системе может менять. Это проблематично, поскольку серверы часто выходят из строя или запускаются, и для каждого такого события потребуется переназначить почти все объекты и перенести их на новые серверы.

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

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

Практические дополнения [ править ]

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

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

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

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

Сложность [ править ]

Асимптотические временные сложности для узлов (или слотов) и ключей
Классическая хеш-таблицаПоследовательное хеширование
добавить узел
удалить узел
добавить ключ
удалить ключ

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

Примеры [ править ]

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

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

Ссылки [ править ]

  1. ^ a b Karger, D .; Lehman, E .; Лейтон, Т .; Panigrahy, R .; Левин, М .; Левин, Д. (1997). Согласованное хеширование и случайные деревья: протоколы распределенного кэширования для устранения горячих точек во всемирной паутине . Материалы двадцать девятого ежегодного симпозиума ACM по теории вычислений . ACM Press Нью-Йорк, Нью-Йорк, США. С. 654–663. DOI : 10.1145 / 258533.258660 .
  2. ^ Б с д е е г Брюс Maggs и Рамеш Ситараман (2015). «Алгоритмические самородки в доставке контента» (PDF) . Обзор компьютерных коммуникаций ACM SIGCOMM . 45 (3).
  3. ^ Nygren., E .; Ситараман РК; Солнце, Дж. (2010). «Сеть Akamai: платформа для высокопроизводительных Интернет-приложений» (PDF) . Обзор операционных систем ACM SIGOPS . 44 (3): 2–19. DOI : 10.1145 / 1842733.1842736 . S2CID 207181702 . Архивировано 13 сентября 2012 года (PDF) . Проверено 19 ноября 2012 года .   CS1 maint: обескураженный параметр ( ссылка )
  4. ^ Karger, D .; Шерман, А .; Berkheimer, A .; Bogstad, B .; Dhanidina, R .; Iwamoto, K .; Kim, B .; Matkins, L .; Йерушалми Ю. (1999). «Веб-кеширование с последовательным хешированием» . Компьютерные сети . 31 (11): 1203–1213. DOI : 10.1016 / S1389-1286 (99) 00055-9 . Архивировано из оригинала на 2008-07-21 . Проверено 5 февраля 2008 .
  5. ^ "Что такое Membase?" . Проверено 29 октября 2020 . CS1 maint: обескураженный параметр ( ссылка )
  6. ↑ Холт, Грег (февраль 2011 г.). «Построение последовательного хэширующего кольца» . openstack.org . Проверено 17 ноября 2019 .
  7. ^ DeCandia, G .; Hastorun, D .; Jampani, M .; Какулапати, G .; Лакшман, А .; Пильчин, А .; Sivasubramanian, S .; Vosshall, P .; Фогельс, Вернер (2007). «Dynamo: высокодоступный магазин ключевых значений Amazon» (PDF) . Материалы 21-го симпозиума ACM по принципам операционных систем . 41 (6): 205–220. DOI : 10.1145 / 1323293.1294281 . Проверено 7 июня 2018 .
  8. ^ Лакшман, Авинаш; Малик, Прашант (2010). «Кассандра: децентрализованная структурированная система хранения». Обзор операционных систем ACM SIGOPS . 44 (2): 35–40. DOI : 10.1145 / 1773912.1773922 .
  9. ^ «Дизайн - Волан-де-Морт» . www.project-voldemort.com/ . Архивировано из оригинала 9 февраля 2015 года . Дата обращения 9 февраля 2015 . Последовательное хеширование - это метод, позволяющий избежать этих проблем, и мы используем его для вычисления местоположения каждого ключа в кластере. CS1 maint: обескураженный параметр ( ссылка )
  10. ^ "Маршрутизация Akka" . akka.io . Проверено 16 ноября 2019 .
  11. ^ "Концепции Риака" . Архивировано из оригинала на 2015-09-19 . Проверено 6 декабря 2016 .
  12. ^ "Алгоритмы GlusterFS: Распределение" . gluster.org . 2012-03-01 . Проверено 16 ноября 2019 .
  13. ^ Roughgarden, Тим; Валиант, Грегори (28.03.2016). «Современные алгоритмические инструменты» (PDF) . stanford.edu . Проверено 17 ноября 2019 .
  14. ^ Вишневский, Станислав (2017-07-06). «Как Discord масштабировал Эликсир до 5 000 000 одновременных пользователей» . Проверено 17 ноября 2019 .
  15. ^ Eisenbud, Daniel E .; Йи, Ченг; Контавалли, Карло; Смит, Коди; Кононов, Роман; Манн-Хильшер, Эрик; Чилингироглу, Ардас; Чейни, Бин; Шан, Вентао; Хосейн, Джинна Дилан. «Maglev: быстрый и надежный программный балансировщик сетевой нагрузки» (PDF) . Проверено 17 ноября 2019 .

Внешние ссылки [ править ]

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