Рандеву хеширование

Рандеву-хеширование с n = 12, k = 4. Клиенты C ₁ и C ₄ независимо выбирают одно и то же случайное подмножество из четырех сайтов {S ₂ , S ₅ , S ₆ , S ₁₀ } из двенадцати вариантов S ₁ , S 2 _, ..., S ₁₂ для размещения реплик или акций объекта O.

Рандеву или хеширование с наивысшим случайным весом (HRW) ^{[1] [2]} — это алгоритм, который позволяет клиентам достигать распределенного соглашения по набору опций из возможного набора опций. Типичное применение — когда клиентам нужно договориться о том, каким сайтам (или прокси) назначаются объекты. ${\displaystyle k}$ ${\displaystyle n}$

Последовательное хеширование решает этот особый случай, используя другой метод. Рандеву-хеширование является и гораздо более простым, и более общим, чем последовательное хеширование (см. ниже). ${\displaystyle k=1}$

История

Метод рандеву-хеширования был изобретен Дэвидом Талером и Чиньей Равишанкаром в Мичиганском университете в 1996 году. ^[1] Последовательное хеширование появилось в литературе годом позже.

Учитывая его простоту и универсальность, хеширование Rendezvous теперь предпочтительнее последовательного хеширования в реальных приложениях. ^{[3] [4] [5]} Хеширование Rendezvous использовалось очень рано во многих приложениях, включая мобильное кэширование, ^[6] проектирование маршрутизаторов, ^[7] безопасное установление ключей , ^[8] а также шардинг и распределенные базы данных . ^[9] Другие примеры реальных систем, которые используют хеширование Rendezvous, включают балансировщик нагрузки Github, ^[10] распределенную базу данных Apache Ignite, ^[11] файловое хранилище Tahoe-LAFS, ^[12] службу распределения больших файлов CoBlitz, ^[13] Apache Druid, ^[14] Cloud Object Store от IBM, ^[15] систему управления данными Arvados, ^[16] Apache Kafka, ^[17] и платформу публикации/подписки Twitter EventBus. ^[18]

Одним из первых применений хеширования рандеву было предоставление возможности клиентам многоадресной рассылки в Интернете (в таких контекстах, как MBONE ) идентифицировать точки рандеву многоадресной рассылки распределенным образом. ^{[19] [20]} Он использовался в 1998 году протоколом маршрутизации кэш-массивов (CARP) компании Microsoft для координации и маршрутизации распределенного кэша. ^{[21] [22]} Некоторые протоколы маршрутизации многоадресной рассылки, независимые от протокола, используют хеширование рандеву для выбора точки рандеву. ^[1]

Определение проблемы и подход

Алгоритм

Хеширование Rendezvous решает общую версию проблемы распределенной хеш-таблицы : нам дан набор сайтов (серверов или прокси, например). Как любой набор клиентов, учитывая объект , может договориться о k- подмножестве сайтов для назначения ? Стандартная версия проблемы использует k = 1. Каждый клиент должен сделать свой выбор независимо, но все клиенты должны в конечном итоге выбрать одно и то же подмножество сайтов. Это нетривиально, если мы добавим ограничение минимального нарушения и потребуем, чтобы при отказе или удалении сайта только объекты, отображаемые на этот сайт, должны были быть переназначены другим сайтам. ${\displaystyle n}$ ${\displaystyle O}$ ${\displaystyle O}$

Основная идея заключается в том, чтобы дать каждому сайту оценку ( вес ) для каждого объекта и назначить объект сайту с наивысшей оценкой. Все клиенты сначала договариваются о хэш-функции . Для объекта сайт определяется как имеющий вес . Каждый клиент независимо вычисляет эти веса и выбирает k сайтов, которые дают k наибольших значений хэша. Таким образом, клиенты достигли распределенного -согласования. ${\displaystyle S_{j}}$ ${\displaystyle O_{i}}$ ${\displaystyle h(\cdot )}$ ${\displaystyle O_{i}}$ ${\displaystyle S_{j}}$ ${\displaystyle w_{i,j}=h(O_{i},S_{j})}$ ${\displaystyle w_{i,1},w_{i,2}\dots w_{i,n}}$ ${\displaystyle k}$

Если сайт добавляется или удаляется, только объекты, сопоставленные с ними, переназначаются на другие сайты, удовлетворяя минимальному ограничению нарушения, указанному выше. Назначение HRW может быть вычислено независимо любым клиентом, поскольку оно зависит только от идентификаторов для набора сайтов и назначаемого объекта. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S_{1},S_{2}\dots S_{n}}$

HRW легко приспосабливает различные мощности между сайтами. Если сайт имеет вдвое большую мощность, чем другие сайты, мы просто представляем дважды в списке, скажем, как . Очевидно, что теперь будет отображаться вдвое больше объектов, чем на других сайтах. ${\displaystyle S_{k}}$ ${\displaystyle S_{k}}$ ${\displaystyle S_{k,1},S_{k,2}}$ ${\displaystyle S_{k}}$

Характеристики

Рассмотрим простую версию проблемы с k = 1, где все клиенты должны договориться об одном сайте для объекта O. Подходя к проблеме наивно, может показаться достаточным рассматривать n сайтов как контейнеры в хэш-таблице и хэшировать имя объекта O в эту таблицу. К сожалению, если какой-либо из сайтов выходит из строя или становится недоступным, размер хэш-таблицы изменяется, заставляя все объекты быть переотображенными. Это огромное нарушение делает такое прямое хэширование неработоспособным.

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

Хеширование Rendezvous имеет следующие свойства:

1. Низкие накладные расходы: используемая хеш-функция эффективна, поэтому накладные расходы на стороне клиентов очень низкие.
2. Балансировка нагрузки : поскольку хэш-функция рандомизируется, каждый из n сайтов с одинаковой вероятностью получит объект O. Нагрузки равномерны по всем сайтам.
   1. Вместимость сайта: Сайты с различной вместимостью могут быть представлены в списке сайтов с кратностью, пропорциональной вместимости. Сайт с вместимостью, вдвое превышающей другие сайты, будет представлен в списке дважды, в то время как каждый другой сайт будет представлен один раз.
3. Высокий процент попаданий : поскольку все клиенты соглашаются разместить объект O на одном и том же сайте S _O , каждое извлечение или размещение O в S _O дает максимальную полезность с точки зрения процента попаданий. Объект O всегда будет найден, если только он не будет вытеснен каким-либо алгоритмом замены в S _O .
4. Минимальное нарушение: когда сайт выходит из строя, необходимо переназначить только объекты, сопоставленные с этим сайтом. Нарушение находится на минимально возможном уровне, как доказано в. ^{[1] [2]}
5. Распределенное k -соглашение: Клиенты могут достичь распределенного соглашения по k сайтам, просто выбрав верхние k сайтов в порядке. ^[8]

О(бревнон) время выполнения с помощью скелетного иерархического хеширования рандеву

Стандартная версия Rendezvous Hashing, описанная выше, работает довольно хорошо для умеренных n, но когда n чрезвычайно велико, иерархическое использование Rendezvous Hashing достигает времени выполнения. ^{[23] [24] [25]} Этот подход создает виртуальную иерархическую структуру (называемую «скелетом») и достигает времени выполнения, применяя HRW на каждом уровне при спуске по иерархии. Идея состоит в том, чтобы сначала выбрать некоторую константу и организовать узлы в кластеры . Затем построить виртуальную иерархию, выбрав константу и представив эти кластеры, размещенные в листьях дерева виртуальных узлов, каждый с разветвлением . ${\displaystyle n}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle c=\lceil n/m\rceil }$ ${\displaystyle C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots }$ ${\displaystyle f}$ ${\displaystyle c}$ ${\displaystyle T}$ ${\displaystyle f}$

Использование скелета для достижения времени выполнения log(n) . Реальные узлы отображаются как квадраты на уровне листьев. Виртуальные узлы скелета отображаются как пунктирные круги. Кластеры на уровне листьев имеют размер m = 4, а скелет имеет разветвление f = 3.

На прилагаемой диаграмме размер кластера равен , а скелет разветвления равен . Предполагая для удобства 108 сайтов (реальных узлов), мы получаем трехуровневую виртуальную иерархию. Поскольку , каждый виртуальный узел имеет естественную нумерацию в восьмеричной системе счисления. Таким образом, 27 виртуальных узлов на самом нижнем уровне будут пронумерованы в восьмеричной системе счисления (мы, конечно, можем изменять разветвление на каждом уровне - в этом случае каждый узел будет идентифицирован соответствующим смешанным числом). ${\displaystyle m=4}$ ${\displaystyle f=3}$ ${\displaystyle f=3}$ ${\displaystyle 000,001,002,...,221,222}$

Самый простой способ понять виртуальную иерархию — начать сверху и спускаться по виртуальной иерархии. Мы последовательно применяем Rendezvous Hashing к набору виртуальных узлов на каждом уровне иерархии и спускаемся по ветви, определяемой победившим виртуальным узлом. Фактически, мы можем начать с любого уровня виртуальной иерархии. Начало с более низкого уровня иерархии требует большего количества хэшей, но может улучшить распределение нагрузки в случае сбоев.

Например, вместо того, чтобы применять HRW ко всем 108 реальным узлам на схеме, мы можем сначала применить HRW к 27 виртуальным узлам самого низкого уровня, выбрав один. Затем мы применяем HRW к четырем реальным узлам в его кластере и выбираем победивший сайт. Нам нужны только хэши, а не 108. Если мы применим этот метод, начиная с одного уровня выше в иерархии, нам понадобятся хэши, чтобы добраться до победившего сайта. На рисунке показано, как, если мы продолжим, начиная с корня скелета, мы можем последовательно выбрать виртуальные узлы , , и , и в конечном итоге остановиться на сайте 74. ${\displaystyle 27+4=31}$ ${\displaystyle 9+3+4=16}$ ${\displaystyle (2)_{3}}$ ${\displaystyle (20)_{3}}$ ${\displaystyle (200)_{3}}$

Виртуальную иерархию не нужно хранить, но ее можно создать по требованию, поскольку имена виртуальных узлов являются просто префиксами представлений с основанием (или смешанным основанием). Мы можем легко создать соответствующим образом отсортированные строки из цифр, как требуется. В этом примере мы будем работать со строками (на уровне 1), (на уровне 2) и (на уровне 3). Очевидно, имеет высоту , так как и являются константами. Работа, выполняемая на каждом уровне, составляет , так как является константой. ${\displaystyle f}$ ${\displaystyle 0,1,2}$ ${\displaystyle 20,21,22}$ ${\displaystyle 200,201,202}$ ${\displaystyle T}$ ${\displaystyle h=O(\log c)=O(\log n)}$ ${\displaystyle m}$ ${\displaystyle f}$ ${\displaystyle O(1)}$ ${\displaystyle f}$

Значение можно выбрать на основе таких факторов, как ожидаемая частота отказов и степень желаемой балансировки нагрузки. Более высокое значение приводит к меньшему перекосу нагрузки в случае отказа за счет более высоких накладных расходов на поиск. ${\displaystyle m}$ ${\displaystyle m}$

Выбор эквивалентен неиерархическому рандеву хэшированию. На практике хэш-функция очень дешева, поэтому может работать довольно хорошо, если только не очень высока. ${\displaystyle m=n}$ ${\displaystyle h(\cdot )}$ ${\displaystyle m=n}$ ${\displaystyle n}$

Для любого заданного объекта очевидно, что каждый кластер листового уровня, а следовательно, и каждое из мест, выбирается с равной вероятностью. ${\displaystyle n}$

Репликация, сбои на сайте и добавления на сайт

Можно повысить устойчивость к отказам, реплицируя каждый объект O по сайтам с наивысшим рейтингом r < m для O, выбирая r на основе желаемого уровня устойчивости. Самая простая стратегия — реплицировать только в пределах кластера листового уровня.

Если сайт листового уровня, выбранный для O, недоступен, мы выбираем следующий по рангу сайт для O в том же кластере листового уровня. Если O был реплицирован в кластере листового уровня, мы обязательно найдем O в следующем доступном сайте в ранжированном порядке r сайтов. Все объекты, которые удерживались отказавшим сервером, появляются в каком-то другом сайте в его кластере. (Другой вариант — подняться на один или несколько уровней в скелете и выбрать альтернативу среди виртуальных узлов-братьев на этом уровне. Затем мы спускаемся по иерархии к реальным узлам, как указано выше.)

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

Если сайты являются серверами, некоторые объекты должны быть переназначены на этот недавно добавленный сайт. Как и прежде, объекты, сопоставленные с другими кластерами, никогда не будут сопоставлены с этим новым сайтом, поэтому нам нужно рассматривать только объекты, удерживаемые сайтами в его кластере. То есть нам нужно переназначить только объекты, которые в данный момент присутствуют на m сайтах в этом локальном кластере, а не весь набор объектов в системе. Новые объекты, сопоставленные с этим сайтом, конечно, будут автоматически назначены ему.

Сравнение с последовательным хешированием

Из-за своей простоты, меньших накладных расходов и общности (работает для любого k < n ), рандеву-хеширование все чаще предпочитают последовательному хешированию. Недавние примеры его использования включают балансировщик нагрузки Github, ^[10] распределенную базу данных Apache Ignite, ^[11] и платформу Twitter EventBus pub/sub. ^[18]

Последовательное хеширование работает путем сопоставления сайтов равномерно и случайным образом с точками на единичной окружности, называемыми токенами. Объекты также сопоставлены с единичной окружностью и помещены в сайт, токен которого является первым встреченным, перемещаясь по часовой стрелке от местоположения объекта. Когда сайт удаляется, объекты, которыми он владеет, переносятся на сайт, владеющий следующим встреченным токеном, перемещаясь по часовой стрелке. При условии, что каждый сайт сопоставлен большому количеству (скажем, 100–200) токенов, это переназначит объекты относительно единообразным образом среди оставшихся сайтов.

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

Варианты последовательного хеширования (например, Dynamo от Amazon ), которые используют более сложную логику для распределения токенов на единичной окружности, предлагают лучшую балансировку нагрузки , чем базовое последовательное хеширование, сокращают накладные расходы на добавление новых сайтов, сокращают накладные расходы на метаданные и предлагают другие преимущества. ^[26]

Преимущества хеширования Rendezvous перед последовательным хешированием

Rendezvous hashing (HRW) гораздо проще концептуально и на практике. Он также равномерно распределяет объекты по всем сайтам, учитывая единую хэш-функцию. В отличие от последовательного хэширования, HRW не требует предварительного вычисления или хранения токенов. Рассмотрим k = 1. Объект помещается на один из сайтов путем вычисления значений хэша и выбора сайта , который дает наибольшее значение хэша. Если добавляется новый сайт , новые размещения объектов или запросы будут вычислять значения хэша и выбирать наибольшее из них. Если объект, уже находящийся в системе в сопоставляется с этим новым сайтом , он будет извлечен заново и кэширован в . Отныне все клиенты будут получать его с этого сайта, а старая кэшированная копия в в конечном итоге будет заменена локальным алгоритмом управления кэшем. Если переводится в автономный режим, его объекты будут переотображены единообразно на оставшиеся сайты. ${\displaystyle O_{i}}$ ${\displaystyle n}$ ${\displaystyle S_{1},S_{2}\dots S_{n}}$ ${\displaystyle n}$ ${\displaystyle h(O_{i},S_{j})}$ ${\displaystyle S_{k}}$ ${\displaystyle S_{n+1}}$ ${\displaystyle n+1}$ ${\displaystyle S_{k}}$ ${\displaystyle S_{n+1}}$ ${\displaystyle S_{n+1}}$ ${\displaystyle S_{k}}$ ${\displaystyle S_{k}}$ ${\displaystyle n-1}$

Варианты алгоритма HRW, такие как использование скелета (см. ниже), могут сократить время нахождения объекта до , за счет меньшей глобальной однородности размещения. Однако, когда не слишком велико, стоимость размещения базового HRW, скорее всего, не будет проблемой. HRW полностью избегает всех накладных расходов и сложности, связанных с правильной обработкой нескольких токенов для каждого сайта и связанных метаданных. ${\displaystyle O(n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle n}$ ${\displaystyle O(n)}$

Хеширование методом рандеву также имеет большое преимущество, поскольку оно обеспечивает простые решения других важных проблем, таких как распределенное соглашение. ${\displaystyle k}$

Последовательное хеширование — это частный случай хеширования Rendezvous.

Рандеву-хеширование проще и универсальнее, чем последовательное хеширование. Можно показать, что последовательное хеширование является частным случаем HRW с помощью соответствующего выбора двухпозиционной хеш-функции. Из идентификатора сайта простейшая версия последовательного хеширования вычисляет список позиций токенов, например, где хеширует значения в местоположения на единичной окружности. Определите двухпозиционную хеш-функцию как где обозначает расстояние вдоль единичной окружности от до (поскольку имеет некоторое минимальное ненулевое значение, то нет проблем с переводом этого значения в уникальное целое число в некотором ограниченном диапазоне). Это будет точно дублировать назначение, произведенное последовательным хешированием. ${\displaystyle S}$ ${\displaystyle t_{s}=h_{c}(S)}$ ${\displaystyle h_{c}}$ ${\displaystyle h(S,O)}$ ${\displaystyle {\frac {1}{\min _{S}(h_{c}(O)-t_{s})}}}$ ${\displaystyle h_{c}(O)-t_{s}}$ ${\displaystyle h_{c}(O)}$ ${\displaystyle t_{s}}$ ${\displaystyle h_{c}(O)-t_{s}}$

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

Взвешенные вариации

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

Простой механизм для обработки этого случая — назначить два виртуальных местоположения этому узлу, так что если любое из виртуальных местоположений этого большего узла имеет самый высокий хэш, этот узел получает ключ. Но эта стратегия не работает, когда относительные веса не являются целыми кратными. Например, если бы один узел имел на 42% больше емкости хранилища, потребовалось бы добавить много виртуальных узлов в разных пропорциях, что привело бы к значительному снижению производительности. Было предложено несколько модификаций хэширования рандеву для преодоления этого ограничения.

Протокол маршрутизации кэш-массива

Протокол маршрутизации массива кэша (CARP) — это проект IETF 1998 года, описывающий метод вычисления коэффициентов нагрузки , которые можно умножить на хэш-счет каждого узла, чтобы получить произвольный уровень точности для разного взвешивания узлов. ^[21] Однако один из недостатков этого подхода заключается в том, что при изменении веса любого узла или при добавлении или удалении любого узла все коэффициенты нагрузки должны быть пересчитаны и относительно масштабированы. Когда коэффициенты нагрузки изменяются относительно друг друга, это вызывает перемещение ключей между узлами, вес которых не изменился, но коэффициент нагрузки которых изменился относительно других узлов в системе. Это приводит к избыточному перемещению ключей. ^[27]

Контролируемая репликация

Управляемая репликация при масштабируемом хешировании или CRUSH ^[28] является расширением RUSH ^[29] , которое улучшает рандеву-хеширование путем построения дерева, где псевдослучайная функция (хеш) используется для навигации вниз по дереву, чтобы найти, какой узел в конечном итоге отвечает за данный ключ. Это обеспечивает идеальную стабильность при добавлении узлов; однако, это не идеально стабильно при удалении или повторном взвешивании узлов, при этом избыточное перемещение ключей пропорционально высоте дерева.

Алгоритм CRUSH используется системой хранения данных ceph для сопоставления объектов данных с узлами, ответственными за их хранение. ^[30]

Другие варианты

В 2005 году Кристиан Шиндельхауэр и Гуннар Шомакер описали логарифмический метод повторного взвешивания оценок хэшей таким образом, что не требуется относительного масштабирования факторов нагрузки при изменении веса узла или при добавлении или удалении узлов. ^[31] Это позволило получить двойное преимущество: идеальную точность при взвешивании узлов, а также идеальную стабильность, поскольку для переназначения на новые узлы требовалось лишь минимальное количество ключей.

Похожая стратегия хеширования на основе логарифма используется для назначения данных узлам хранения в системе хранения данных Cleversafe, теперь IBM Cloud Object Storage . ^[27]

Системы, использующие хеширование Rendezvous

Rendezvous hashing широко используется в реальных системах. Частичный список включает Oracle Database in-memory, ^[9] GitHub load balancer, ^[10] Apache Ignite distributed database, ^[11] Tahoe-LAFS file store, ^[12] CoBlitz large-file distribution service, ^[13] Apache Druid, ^[14] IBM's Cloud Object Store, ^[15] Arvados Data Management System, ^[16] Apache Kafka, ^[17] и Twitter EventBus pub/sub platform. ^[18]

Выполнение

Реализация проста, как только выбрана хэш-функция (оригинальная работа по методу HRW дает рекомендации по хэш-функции). ^{[1] [2]} Каждому клиенту нужно только вычислить хэш-значение для каждого из сайтов, а затем выбрать наибольшее. Этот алгоритм работает со временем. Если хэш-функция эффективна, время работы не является проблемой, если только оно не очень велико. ${\displaystyle h(\cdot )}$ ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)}$ ${\displaystyle n}$

Взвешенный хэш рандеву

Код Python, реализующий взвешенный хэш рандеву: ^[27]

импорт  mmh3 импорт  математики из  классов данных  импорт  класса данных из  ввода  импорт  спискаdef  hash_to_unit_interval ( s :  str )  ->  float : """Хеширует строку на единичном интервале (0, 1]""" return ( mmh3 . hash128 ( s ) + 1 ) / 2 ** 128       @dataclass класс  Узел : """Класс, представляющий узел, которому назначены ключи как часть взвешенного хэша рандеву.""" имя : str вес : float      def  compute_weighted_score ( self ,  key :  str ) :  score  =  hash_to_unit_interval ( f " { self.name } : { key } " ) log_score = 1.0 / - math.log ( score ) return self.weight * log_score​​​​​         def  determine_responsible_node ( nodes :  list [ Node ],  key :  str ): """Определяет, какой узел из набора узлов с различным весом отвечает за предоставленный ключ.""" return max ( nodes , key = lambda node : node . compute_weighted_score ( key ), default = None )        

Примеры выходных данных WRH:

>>> импортировать  wrh >>> node1  =  wrh . Узел ( «узел1» ,  100 ) >>> узел2  =  wrh . Узел ( «узел2» ,  200 ) >>> узел3  =  wrh . Узел ( "node3" ,  300 ) >>> str ( wrh . determine_responsible_node ([ node1 ,  node2 ,  node3 ],  "foo" )) "Узел(имя='node1', вес=100)" >>> str ( wrh . determine_responsible_node ([ node1 ,  node2 ,  node3 ],  "bar" )) "Узел(имя='node2', вес=300)" >>> str ( wrh . determine_responsible_node ([ node1 ,  node2 ,  node3 ],  "привет" )) "Node(name='node2', weight=300)" >>> nodes  =  [ node1 ,  node2 ,  node3 ] >>> from  collections  import  Counter >>> responsibility_nodes  =  [ wrh . determine_responsible_node ( ...  nodes ,  f "key: { key } " ) . имя  для  ключа  в  диапазоне ( 45_000 )] >>> print ( Counter ( respond_nodes )) Counter({'node3': 22487, 'node2': 15020 , 'узел1': 7493})

Ссылки

1. Талер, Дэвид; Чинья Равишанкар. "Схема картографирования на основе имени для рандеву" (PDF) . Технический отчет Мичиганского университета CSE-TR-316-96 . Получено 15 сентября 2013 г.
2. Талер, Дэвид; Чинья Равишанкар (февраль 1998 г.). «Использование схем сопоставления на основе имен для повышения показателей попадания». Труды IEEE/ACM по сетевым технологиям . 6 (1): 1–14. CiteSeerX 10.1.1.416.8943 . doi :10.1109/90.663936. S2CID  936134. 
3. "Объяснение хеширования рандеву - Randorithms". randorithms.com . Получено 29.03.2021 .
4. "Rendezvous hashing: мой базовый "согласованный" метод распределения - Пол Куонг: немного Lisp". pvk.ca . Получено 29.03.2021 .
5. Анируддха (08 января 2020 г.). «Хэширование рандеву». Середина . Проверено 29 марта 2021 г.
6. Mayank, Anup; Ravishankar, Chinya (2006). «Поддержка связи мобильных устройств при наличии широковещательных серверов» (PDF) . International Journal of Sensor Networks . 2 (1/2): 9–16. doi :10.1504/IJSNET.2007.012977.
7. Го, Даньхуа; Бхуян, Лакшми; Лю, Бин (октябрь 2012 г.). «Эффективная параллельная конструкция фильтра L7 для многоядерных серверов». IEEE/ACM Transactions on Networking . 20 (5): 1426–1439. doi :10.1109/TNET.2011.2177858. S2CID  1982193.
8. Wang, Peng; Ravishankar, Chinya (2015). «Атаки на подделку и кражу ключей в сенсорных сетях» (PDF) . Международный журнал сенсорных сетей .
9. Mukherjee, Niloy; et al. (август 2015 г.). «Распределенная архитектура Oracle Database In-memory». Труды VLDB Endowment . 8 (12): 1630–1641. doi :10.14778/2824032.2824061.
10. GitHub Engineering (22 сентября 2016 г.). «Представляем балансировщик нагрузки GitHub». Блог GitHub . Получено 1 февраля 2022 г.
11. "Apache Ignite", Wikipedia , 2022-08-18 , получено 2022-12-09
12. "Тахо-ЛАФС". tahoe-lafs.org . Проверено 2 января 2023 г.
13. Park, KyoungSoo; Pai, Vivek S. (2006). «Масштаб и производительность в службе распространения больших файлов CoBlitz». Usenix Nsdi .
14. "Процесс маршрутизатора · Apache Druid". druid.apache.org . Получено 2023-01-02 .
15. "IBM Cloud Object Storage System, версия 3.14.11, Storage Pool Expansion Guide" (PDF) . Версия IBM Cloud Object Storage SystemTM . Получено 2 января 2023 г. .
16. "Arvados | Keep customers". doc.arvados.org . Получено 2023-01-02 .
17. "Горизонтальное масштабирование потребителей Kafka с рандеву-хешированием". Tinybird.co . Получено 2023-02-15 .
18. Анируддха (08 января 2020 г.). «Хэширование рандеву». я0исключение . Проверено 9 декабря 2022 г.
19. Блажевич, Любица (21 июня 2000 г.). «Распределенная многоадресная передача ядра (DCM): протокол маршрутизации для множества небольших групп с применением к мобильной IP-телефонии». Проект IETF . IETF . Получено 17 сентября 2013 г.
20. Феннер, Б. (август 2006 г.). «Независимая от протокола многоадресная передача — разреженный режим (PIM-SM): спецификация протокола (пересмотренная)». IETF RFC . IETF . Получено 17 сентября 2013 г. .
21. Valloppilil, Vinod; Kenneth Ross (27 февраля 1998 г.). "Протокол маршрутизации кэш-массива v1.0". Интернет-черновик . Получено 15 сентября 2013 г.
22. "Cache Array Routing Protocol and Microsoft Proxy Server 2.0" (PDF) . Microsoft. Архивировано из оригинала (PDF) 18 сентября 2014 г. . Получено 15 сентября 2013 г. .
23. Яо, Зижен; Равишанкар, Чинья; Трипати, Сатиш (13 мая 2001 г.). Виртуальные иерархии на основе хэшей для кэширования в гибридных сетях доставки контента (PDF) . Риверсайд, Калифорния: CSE Department, Калифорнийский университет, Риверсайд . Получено 15 ноября 2015 г. .
24. Ван, Вэй; Чинья Равишанкар (январь 2009 г.). «Виртуальные иерархии на основе хэшей для масштабируемой службы определения местоположения в мобильных беспроводных сетях». Мобильные сети и приложения . 14 (5): 625–637. doi :10.1007/s11036-008-0144-3. S2CID  2802543.
25. Маянк, Ануп; Пхатак, Тривикрам; Равишанкар, Чинья (2006), Децентрализованная координация распределенных мультимедийных кэшей на основе хэша (PDF) , Proc. 5-я Международная конференция IEEE по сетевым технологиям (ICN'06), Маврикий: IEEE
26. ДеКандиа, Г.; Хасторун, Д.; Джампани, М.; Какулапати, Г.; Лакшман, А.; Пильчин А.; Сивасубраманиан, С.; Восшалл, П.; Фогельс, В. (2007). «Динамо» (PDF) . Обзор операционных систем ACM Sigops . 41 (6): 205–220. дои : 10.1145/1323293.1294281 . Проверено 7 июня 2018 г.
27. Джейсон Реш. «Новые алгоритмы хеширования для хранения данных» (PDF) .
28. Sage A. Weil; et al. "CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data" (PDF) . Архивировано из оригинала (PDF) 20 февраля 2019 г.
29. Р. Дж. Хоники, Итан Л. Миллер. «Репликация при масштабируемом хешировании: семейство алгоритмов для масштабируемого децентрализованного распределения данных» (PDF) .
30. Ceph. «Crush Maps».
31. Кристиан Шиндельхауэр, Гуннар Шомакер (2005). «Взвешенные распределенные хэш-таблицы»: 218. CiteSeerX 10.1.1.414.9353 .  {{cite journal}}: Цитировать журнал требует |journal=( помощь )

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

• Rendezvous Hashing: альтернатива Consistent Hashing