Рандеву или хеширование наивысшего случайного веса (HRW) [1] [2] - это алгоритм, который позволяет клиентам достигать распределенного соглашения по набору варианты из возможного набора параметры. Типичное приложение - это когда клиентам необходимо согласовать, каким сайтам (или прокси-серверам) назначены объекты.
Рандеву-хеширование намного проще и более общее, чем последовательное хеширование , которое становится частным случаем (для) рандеву хеширования.
История
Рандеву-хеширование было изобретено Дэвидом Талером и Чиней Равишанкар в Мичиганском университете в 1996 году. [1] Последовательное хеширование появилось в литературе годом позже.
Учитывая его простоту и универсальность, рандеву-хеширование теперь предпочтительнее согласованного хеширования в реальных приложениях. [3] [4] [5] Рандеву-хеширование очень рано использовалось во многих приложениях, включая мобильное кэширование, [6] проектирование маршрутизатора, [7] создание безопасного ключа , [8], а также сегментирование и распределенные базы данных . [9]
Одним из первых приложений хеширования рандеву было позволить клиентам многоадресной рассылки в Интернете (в таких контекстах, как MBONE ) определять точки встречи многоадресной рассылки распределенным образом. [10] [11] В 1998 году он использовался Microsoft Cache Array Routing Protocol (CARP) для координации и маршрутизации распределенного кэша. [12] [13] Некоторые протоколы независимой от протокола многоадресной маршрутизации используют хеширование рандеву для выбора точки встречи. [1]
Обзор
Алгоритм
Рандеву-хеширование решает проблему распределенной хеш-таблицы : как может набор клиентов, учитывая объект, договоритесь о том, где в наборе сайтов (скажем, серверов) для размещения ? Каждый клиент должен выбрать сайт независимо, но все клиенты должны в конечном итоге выбрать один и тот же сайт. Это нетривиально, если мы добавим ограничение минимального нарушения и потребуем, чтобы только объекты, сопоставленные с удаленным сайтом, могли быть переназначены другим сайтам.
Основная идея - дать каждому сайту оценка ( вес ) для каждого объектаи назначьте объект сайту с наивысшей оценкой. Все клиенты сначала согласовывают хэш-функцию. Для объекта, сайт определяется как имеющий вес . HRW назначает на сайт чей вес самый большой. С оговаривается, каждый клиент может самостоятельно рассчитать веса и выберите самый большой. Если цель распределяется-согласие, клиенты могут самостоятельно подбирать сайты с наибольшие значения хеш-функции.
Если сайт добавляется или удаляется, только объекты, сопоставленные с переназначаются на разные сайты, удовлетворяя указанное выше ограничение минимального прерывания. Назначение HRW может быть вычислено независимо любым клиентом, так как оно зависит только от идентификаторов для набора сайтов. и присваиваемый объект.
HRW легко размещает разные мощности между сайтами. Если сайт имеет вдвое большую емкость, чем другие сайты, мы просто представляем дважды в списке, скажем, как . Очевидно, что теперь в два раза больше объектов будет отображаться что касается других сайтов.
Характеристики
Сначала может показаться достаточным рассматривать n сайтов как сегменты в хеш-таблице и хешировать имя объекта O в эту таблицу. Однако, если какой-либо из сайтов выходит из строя или становится недоступным, размер хеш-таблицы изменяется, что требует переназначения всех объектов. Это серьезное нарушение делает такое прямое хеширование неработоспособным. Однако при рандеву хеширования клиенты обрабатывают сбои сайтов, выбирая сайт, который имеет следующий по величине вес. Повторное сопоставление требуется только для объектов, которые в настоящее время сопоставлены с отказавшим сайтом, и нарушения минимальны. [1] [2]
Хеширование рандеву имеет следующие свойства:
- Низкие накладные расходы: используемая хеш-функция эффективна, поэтому накладные расходы клиентов очень низкие.
- Балансировка нагрузки : Так как хэшфункция рандомизации, каждый из п сайтов с равной вероятностью может получить объект O . Нагрузки равномерны по площадкам.
- Емкость сайта: Сайты с разной емкостью могут быть представлены в списке сайтов с кратностью, пропорциональной емкости. Сайт, емкость которого в два раза больше, чем у других сайтов, будет представлен в списке дважды, а все остальные сайты будут представлены один раз.
- Высокая частота попаданий : поскольку все клиенты соглашаются разместить объект O на одном и том же сайте S O , каждая выборка или размещение объекта O в S O дает максимальную полезность с точки зрения частоты совпадений. Объект O всегда можно найти , если это не выселили некоторой замены алгоритма на S O .
- Минимальные нарушения: когда сайт выходит из строя, необходимо переназначить только объекты, сопоставленные с этим сайтом. Разрушение находится на минимально возможном уровне, как показано в [1] [2]
- Распределенное k- соглашение: клиенты могут достичь распределенного соглашения по k сайтам, просто выбрав k лучших сайтов в заказе. [8]
Сравнение с последовательным хешированием
Согласованное хеширование работает путем равномерного и случайного сопоставления сайтов с точками на единичном круге, называемыми токенами. Объекты также сопоставляются с единичным кругом и помещаются на участок, чей жетон является первым встреченным, движущимся по часовой стрелке от местоположения объекта. Когда сайт удаляется, объекты, которыми он владеет, передаются сайту, которому принадлежит следующий токен, движущийся по часовой стрелке. При условии, что каждый сайт сопоставлен с большим количеством (скажем, 100–200) токенов, это позволит переназначить объекты между оставшимися сайтами относительно единообразно.
Если сайты сопоставляются с точками на круге случайным образом путем хеширования 200 вариантов идентификатора сайта, скажем, назначение любого объекта требует сохранения или пересчета 200 значений хеш-функции для каждого сайта. Однако токены, связанные с данным сайтом, могут быть предварительно вычислены и сохранены в отсортированном списке, для чего требуется только одно применение хеш-функции к объекту и двоичный поиск для вычисления назначения. Однако даже с большим количеством токенов на сайт, базовая версия согласованного хеширования может не сбалансировать объекты равномерно по сайтам, поскольку при удалении сайта каждый назначенный ему объект распределяется между тем количеством других сайтов, сколько у сайта есть токенов (скажем, 100 –200).
Варианты согласованного хеширования (например, Dynamo от Amazon ), которые используют более сложную логику для распределения токенов по единичному кругу, предлагают лучшую балансировку нагрузки, чем базовое согласованное хеширование, уменьшают накладные расходы на добавление новых сайтов и уменьшают накладные расходы на метаданные, а также предлагают другие преимущества. [14]
Напротив, рандеву-хеширование (HRW) намного проще концептуально и на практике. Он также равномерно распределяет объекты по всем сайтам с помощью единой хеш-функции. В отличие от согласованного хеширования, HRW не требует предварительных вычислений или хранения токенов. Объект помещается в один из места путем вычисления хеш-значения и выбор сайта что дает наивысшее значение хеш-функции. Если новый сайт добавлен, новые размещения объектов или запросы будут вычисляться хеш-значения и выберите наибольшее из них. Если объект уже в системе на карты на этот новый сайт , он будет получен заново и кэширован в . Отныне все клиенты будут получать его с этого сайта, а старую кэшированную копию по адресув конечном итоге будет заменен алгоритмом управления локальным кешем. Если переводится в автономный режим, его объекты будут равномерно переназначены на оставшиеся места.
Варианты алгоритма HRW, такие как использование скелета (см. Ниже), могут уменьшить время для размещения объекта , за счет меньшей однородности размещения. Когда не слишком большой, однако стоимость размещения базовой HRW вряд ли будет проблемой. HRW полностью избегает всех накладных расходов и сложности, связанных с правильной обработкой нескольких токенов для каждого сайта и связанных метаданных.
Рандеву-хеширование также имеет большое преимущество в том, что оно обеспечивает простые решения других важных проблем, таких как распределенное -соглашение.
Согласованное хеширование - это особый случай хеширования Rendezvous.
Рандеву-хеширование проще и более универсально, чем последовательное хеширование. Последовательное хеширование можно показать как частный случай HRW путем соответствующего выбора двухзначной хеш-функции. По идентификатору сайта простейшая версия согласованного хеширования вычисляет список позиций токенов, например, где хеширует значения в местоположения на единичном круге. Определите двухзначную хеш-функцию быть где обозначает расстояние по единичной окружности от к (поскольку имеет какое-то минимальное ненулевое значение, нет проблем с переводом этого значения в уникальное целое число в некотором ограниченном диапазоне). Это будет точно дублировать присвоение, произведенное последовательным хешированием.
Однако невозможно свести HRW к согласованному хешированию (при условии, что количество токенов на сайт ограничено), поскольку HRW потенциально переназначает объекты с удаленного сайта на неограниченное количество других сайтов.
Взвешенные вариации
В стандартной реализации хеширования рандеву каждый узел получает статически равную долю ключей. Однако такое поведение нежелательно, когда узлы имеют разные возможности для обработки или хранения назначенных им ключей. Например, если один из узлов имеет вдвое большую емкость хранилища, чем другие, было бы полезно, если бы алгоритм мог учесть это так, чтобы этот более мощный узел получил бы вдвое больше ключей, чем каждый из других.
Простой механизм для обработки этого случая - назначить этому узлу два виртуальных местоположения, так что, если какое-либо из виртуальных местоположений этого более крупного узла имеет наивысший хэш, этот узел получит ключ. Но эта стратегия не работает, когда относительные веса не являются целыми кратными. Например, если у одного узла емкость хранилища на 42% больше, потребуется добавить много виртуальных узлов в разных пропорциях, что приведет к значительному снижению производительности. Было предложено несколько модификаций хеширования рандеву для преодоления этого ограничения.
Протокол маршрутизации массива кэша
Массив кэша маршрутизации протокола (КАРП) представляет собой проект IETF , что одна тысяча девятьсот девяносто восемь описан способ вычисления коэффициентов загрузки , которые могут быть умножены на каждого узла хеш - счет , чтобы получить произвольный уровень точности для взвешивания узлов по- разному. [12] Однако одним из недостатков этого подхода является то, что при изменении веса любого узла или при добавлении или удалении любого узла все коэффициенты нагрузки должны быть повторно вычислены и относительно масштабированы. Когда коэффициенты нагрузки изменяются относительно друг друга, это запускает перемещение ключей между узлами, вес которых не изменился, но коэффициент нагрузки которых изменился относительно других узлов в системе. Это приводит к чрезмерному перемещению клавиш. [15]
Контролируемая репликация
Управляемая репликация при масштабируемом хешировании или CRUSH [16] является расширением RUSH [17], которое улучшает хеширование рандеву за счет построения дерева, в котором псевдослучайная функция (хеш) используется для навигации вниз по дереву, чтобы найти, какой узел в конечном итоге отвечает для данного ключа. Он обеспечивает идеальную стабильность для добавления узлов, однако он не совсем стабилен при удалении или повторном взвешивании узлов, поскольку избыточное перемещение ключей пропорционально высоте дерева.
Алгоритм CRUSH используется системой хранения данных ceph для отображения объектов данных на узлы, ответственные за их хранение. [18]
Скелетный вариант
Когда очень большой, вариант на основе скелета может сократить время работы. [19] [20] [21] Этот подход создает виртуальную иерархическую структуру (называемую «скелетом») и достигаетвремя работы, применяя HRW на каждом уровне при спуске по иерархии. Идея состоит в том, чтобы сначала выбрать некоторую постоянную и организовать сайты в кластеры Затем постройте виртуальную иерархию, выбрав константу и представляя эти кластеры на листьях дерева виртуальных узлов, каждый с разветвлением .
На прилагаемой диаграмме размер кластера равен , а разветвление скелета . Предполагая для удобства 108 сайтов (реальных узлов), мы получаем трехуровневую виртуальную иерархию. С, каждый виртуальный узел имеет восьмеричную натуральную нумерацию. Таким образом, 27 виртуальных узлов на самом нижнем уровне будут пронумерованы. в восьмеричной системе счисления (мы, конечно, можем изменять разветвление на каждом уровне - в этом случае каждый узел будет идентифицирован соответствующим числом со смешанным основанием).
Вместо того, чтобы применять HRW ко всем 108 реальным узлам, мы можем сначала применить HRW к 27 виртуальным узлам нижнего уровня, выбрав один. Затем мы применяем HRW к четырем реальным узлам в его кластере и выбираем победивший сайт. Нам нужно только хешей, а не 108. Если мы применим этот метод, начиная на один уровень выше в иерархии, нам понадобится хеши, чтобы попасть на сайт-победитель. На рисунке показано, как, начиная с корня скелета, мы можем последовательно выбирать виртуальные узлы., , а также , и, наконец, попадете на сайт 74.
Мы можем начать с любого уровня виртуальной иерархии, а не только с корня. Для запуска с более низкого уровня иерархии требуется больше хешей, но может улучшить распределение нагрузки в случае сбоев. Кроме того, виртуальную иерархию не нужно хранить, но ее можно создавать по запросу, поскольку имена виртуальных узлов являются просто префиксом базовых значений.(или смешанные) представления. При необходимости мы можем легко создать из цифр строки, отсортированные соответствующим образом. В этом примере мы будем работать со строками (на уровне 1), (на уровне 2) и (на уровне 3). Четко, имеет высоту , поскольку а также обе константы. Работа, проделанная на каждом уровне,, поскольку является константой.
Для любого данного объекта ясно, что метод выбирает каждый кластер и, следовательно, каждый из сайтов, с равной вероятностью. Если окончательно выбранный сайт недоступен, мы можем выбрать другой сайт в том же кластере обычным способом. В качестве альтернативы, мы могли бы подняться на один или несколько уровней в скелете и выбрать альтернативу из числа родственных виртуальных узлов на этом уровне и снова спуститься по иерархии к реальным узлам, как указано выше.
Значение могут быть выбраны на основе таких факторов, как ожидаемая частота отказов и степень желаемой балансировки нагрузки. Более высокое значение приводит к меньшему перекосу нагрузки в случае сбоя за счет увеличения накладных расходов на поиск.
Выбор эквивалентен неиерархическому хешированию рандеву. На практике хеш-функция очень дешево, так что может работать достаточно хорошо, если очень высокий.
Другие варианты
В 2005 году Кристиан Шиндельхауэр и Гуннар Шомакер описали логарифмический метод повторного взвешивания хэш-оценок таким образом, чтобы не требовалось относительное масштабирование коэффициентов нагрузки при изменении веса узла или при добавлении или удалении узлов. [22] Это дало возможность получить двойное преимущество - идеальную точность при взвешивании узлов, а также идеальную стабильность, так как только минимальное количество ключей требовалось переназначить на новые узлы.
Аналогичная стратегия хеширования на основе логарифмов используется для назначения данных узлам хранения в системе хранения данных Cleversafe , теперь IBM Cloud Object Storage . [15]
Выполнение
Реализация проста, если хеш-функция выбрано (в оригинальной работе по методу HRW дается рекомендация по хэш-функции). [1] [2] Каждому клиенту нужно только вычислить хеш-значение для каждого изсайтов, а затем выберите самый крупный. Этот алгоритм работает ввремя. Если хеш-функция эффективна, время работы не проблема, если очень большой.
Взвешенный хэш рандеву
Код Python, реализующий взвешенный хэш рандеву: [15]
#! / usr / bin / env python3 import mmh3 import mathdef int_to_float ( value : int ) -> float : "" "Преобразует равномерно случайное [[64-битное вычисление | 64-битное]] целое в равномерно случайное число с плавающей запятой на интервале ""». fifty_three_ones = 0xFFFFFFFFFFFFFFFF >> ( 64 - 53 ) fifty_three_zeros = поплавка ( 1 << 53 ) возврата ( значение & fifty_three_ones ) / fifty_three_zerosclass Node : "" "Класс, представляющий узел, которому назначены ключи как часть взвешенного хэша рандеву." "" def __init__ ( self , name : str , seed , weight ) -> None : self . имя , я . семя , сам . вес = имя , семя , вес def __str__ ( self ): return "[" + self . name + "(" + str ( self . seed ) + "," + str ( self . weight ) + ")]" def compute_weighted_score ( self , key ): hash_1 , hash_2 = mmh3 . hash64 ( str ( ключ ), 0xFFFFFFFF & self . seed ) hash_f = int_to_float ( hash_2 ) score = 1.0 / - math . log ( hash_f ) вернуть себя . вес * баллЗащиту determine_responsible_node ( узлы , ключ ): «» «Определяет , какой узел из множества узлов различных весов, отвечает за предоставленный ключ» «» highest_score , чемпионом = - 1 , None для узла в узлах : оценка = узел . compute_weighted_score ( ключ ), если оценка > наивысший_счет : чемпион , наивысший_счет = узел , чемпион по возврату очков
Пример вывода WRH:
[GCC 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.39)] на darwin Введите "help", "copyright", "credits" или "license" для получения дополнительной информации. >>> import wrh >>> node1 = wrh . Узел ( "узел1" , 123 , 100 ) >>> узел2 = wrh . Узел ( "узел2" , 567 , 200 ) >>> узел3 = wrh . Узел ( "node3" , 789 , 300 ) >>> ул ( WRH . Determine_responsible_node ([ узел1 , узел2 , node3 ], 'Foo' )) '[node3 (789, 300)]' >>> ул ( WRH . Determine_responsible_node ([ узел1 , узел2 , node3 ], 'бар' )) '[node3 (789, 300)]' >>> ул ( WRH . determine_responsible_node ([ узел1 , узел2 , node3 ], 'Привет' )) «[узел2 ( 567, 200)] '
Рекомендации
- ^ a b c d e f Талер, Дэвид; Чинья Равишанкар. «Схема сопоставления на основе имени для рандеву» (PDF) . Технический отчет Мичиганского университета CSE-TR-316-96 . Проверено 15 сентября 2013 .
- ^ а б в г Талер, Дэвид; Чинья Равишанкар (февраль 1998 г.). «Использование схем сопоставления на основе имен для увеличения числа совпадений». Транзакции IEEE / ACM в сети . 6 (1): 1–14. CiteSeerX 10.1.1.416.8943 . DOI : 10.1109 / 90.663936 .
- ^ «Объяснение хеширования рандеву - Randorithms» . randorithms.com . Проверено 29 марта 2021 .
- ^ «Рандеву-хеширование: мой базовый« согласованный »метод распределения - Пол Кхыонг: немного Лиспа» . pvk.ca . Проверено 29 марта 2021 .
- ^ Анируддха (08.01.2020). «Хеширование рандеву» . Средний . Проверено 29 марта 2021 .
- ^ Маянк, Ануп; Равишанкар, Чинья (2006). «Поддержка связи мобильных устройств при наличии широковещательных серверов» (PDF) . Международный журнал сенсорных сетей . 2 (1/2): 9–16. DOI : 10.1504 / IJSNET.2007.012977 .
- ^ Го, Даньхуа; Бхуян, Лакшми; Лю, Бинь (октябрь 2012 г.). «Эффективный параллельный L7-фильтр для многоядерных серверов». Транзакции IEEE / ACM в сети . 20 (5): 1426–1439. DOI : 10.1109 / TNET.2011.2177858 .
- ^ а б Ван, Пэн; Равишанкар, Чинья (2015). «Ключ навязывает и Key Кража Атаки в сенсорных сетях ' » (PDF) . Международный журнал сенсорных сетей .
- ^ Мукерджи, Нилой; и другие. (Август 2015 г.). «Распределенная архитектура Oracle Database In-memory». Труды эндаумента VLDB . 8 (12): 1630–1641. DOI : 10.14778 / 2824032.2824061 .
- ^ Блажевич, Любица. «Распределенная базовая многоадресная передача (DCM): протокол маршрутизации для многих небольших групп с приложением для мобильной IP-телефонии» . Проект IETF . IETF . Проверено 17 сентября 2013 года .
- ^ Феннер, Б. «Независимая от протокола многоадресная передача - разреженный режим (PIM-SM): спецификация протокола (пересмотренная)» . IETF RFC . IETF . Проверено 17 сентября 2013 года .
- ^ а б Валлоппиллил, Винод; Кеннет Росс. "Протокол маршрутизации массива кэша v1.0" . Интернет-проект . Проверено 15 сентября 2013 года .
- ^ «Протокол маршрутизации массива кэша и Microsoft Proxy Server 2.0» (PDF) . Microsoft. Архивировано из оригинального (PDF) 18 сентября 2014 года . Проверено 15 сентября 2013 года .
- ^ DeCandia, G .; Hastorun, D .; Jampani, M .; Какулапати, G .; Лакшман, А .; Пильчин, А .; Sivasubramanian, S .; Vosshall, P .; Фогельс, В. (2007). «Dynamo: высокодоступный магазин ключевых значений Amazon» (PDF) . Материалы 21-го симпозиума ACM по принципам операционных систем . DOI : 10.1145 / 1323293.1294281 . Проверено 7 июня 2018 .
- ^ а б в Джейсон Реш. «Новые алгоритмы хеширования для хранения данных» (PDF) .
- ^ Мудрец А. Вейль; и другие. «CRUSH: контролируемое, масштабируемое, децентрализованное размещение реплицированных данных» (PDF) . Архивировано из оригинального (PDF) 20 февраля 2019 года.
- ^ Р. Дж. Хоники, Итан Л. Миллер. «Репликация при масштабируемом хешировании: семейство алгоритмов масштабируемого децентрализованного распределения данных» (PDF) .
- ^ Ceph. «Раздавить карты» .
- ^ Яо, Цзычжэнь; Равишанкар, Чинья; Трипати, Сатиш (13 мая 2001 г.). Виртуальные иерархии на основе хэша для кэширования в гибридных сетях доставки контента (PDF) . Риверсайд, Калифорния: Департамент CSE, Калифорнийский университет, Риверсайд . Проверено 15 ноября 2015 года .
- ^ Ван, Вэй; Чинья Равишанкар (январь 2009 г.). «Виртуальные иерархии на основе хэша для масштабируемой службы определения местоположения в мобильных одноранговых сетях». Мобильные сети и приложения . 14 (5): 625–637. DOI : 10.1007 / s11036-008-0144-3 .
- ^ Маянк, Ануп; Фатак, Тривикрам; Равишанкар, Чинья (2006 г.), Децентрализованная координация распределенных мультимедийных кэшей на основе хэша (PDF) , Proc. 5-я Международная конференция по сетям IEEE (ICN'06), Маврикий: IEEE
- ^ Кристиан Шиндельхауэр, Гуннар Шомакер (2005). «Взвешенные распределенные хеш-таблицы»: 218. CiteSeerX 10.1.1.414.9353 . Цитировать журнал требует
|journal=
( помощь )
Внешние ссылки
- Хеширование рандеву: альтернатива последовательному хешированию