Хэширование рандеву

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

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

История

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

O (log n ) время выполнения посредством иерархического хеширования рандеву на основе скелета

Описанная выше стандартная версия Rendezvous Hashing работает вполне хорошо для умеренных n, но когда $n$ чрезвычайно велик, иерархическое использование хэширования рандеву достигает $O(\log n)$ время бега. ^[23]^[24]^[25] Этот подход создает виртуальную иерархическую структуру (называемую «скелетом») и обеспечивает $O(\log n)$ время работы, применяя HRW на каждом уровне, спускаясь по иерархии. Идея состоит в том, чтобы сначала выбрать некоторую константу $m$ и организовать $n$ сайты в $c=\lceil n/m\rceil$ кластеры $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$ Далее постройте виртуальную иерархию, выбрав константу $f$ и представляя себе эти $c$ гроздья, размещенные на листьях дерева $T$ виртуальных узлов, каждый с разветвлением $f$ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Согласованное хеширование — это особый случай хеширования рандеву.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хэширование рандеву широко используется в реальных системах. Неполный список включает базу данных Oracle в памяти, ^[9] балансировщик нагрузки GitHub, ^[10] распределенная база данных Apache Ignite, ^[11] хранилище файлов Tahoe-LAFS, ^[12] сервис распространения больших файлов CoBlitz, ^[13] Апач Друид, ^[14] Облачное хранилище объектов IBM, ^[15] система управления данными Arvados, ^[16] Апач Кафка, ^[17] и паб-платформой Twitter EventBus. ^[18]

Выполнение

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

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

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

import mmh3
import math
from dataclasses import dataclass
from typing import List

def hash_to_unit_interval(s: str) -> float:
    """Hashes a string onto the unit interval (0, 1]"""
    return (mmh3.hash128(s) + 1) / 2**128

@dataclass
class Node:
    """Class representing a node that is assigned keys as part of a weighted rendezvous hash."""
    name: str
    weight: 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):
    """Determines which node of a set of nodes of various weights is responsible for the provided key."""
    return max(
        nodes, key=lambda node: node.compute_weighted_score(key), default=None)

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

>>> import wrh
>>> node1 = wrh.Node("node1", 100)
>>> node2 = wrh.Node("node2", 200)
>>> node3 = wrh.Node("node3", 300)
>>> str(wrh.determine_responsible_node([node1, node2, node3], "foo"))
"Node(name='node1', weight=100)"
>>> str(wrh.determine_responsible_node([node1, node2, node3], "bar"))
"Node(name='node2', weight=300)"
>>> str(wrh.determine_responsible_node([node1, node2, node3], "hello"))
"Node(name='node2', weight=300)"
>>> nodes = [node1, node2, node3]
>>> from collections import Counter
>>> responsible_nodes = [wrh.determine_responsible_node(
...     nodes, f"key: {key}").name for key in range(45_000)]
>>> print(Counter(responsible_nodes))
Counter({'node3': 22487, 'node2': 15020, 'node1': 7493})

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Талер, Дэвид; Чинья Равишанкар. «Схема сопоставления рандеву на основе имени» (PDF) . Технический отчет Мичиганского университета CSE-TR-316-96 . Проверено 15 сентября 2013 г.
^ Jump up to: ^а ^б ^с ^д Талер, Дэвид; Чинья Равишанкар (февраль 1998 г.). «Использование схем сопоставления на основе имен для увеличения количества попаданий». Транзакции IEEE/ACM в сети . 6 (1): 1–14. CiteSeerX 10.1.1.416.8943 . дои : 10.1109/90.663936 . S2CID 936134 .
^ «Объяснение хэширования рандеву — рандоритмы» . randorithms.com . Проверено 29 марта 2021 г.
^ «Хеширование рандеву: мой базовый «последовательный» метод распределения — Пол Хуонг: немного Lisp» . pvk.ca. Проверено 29 марта 2021 г.
^ Анируддха (08 января 2020 г.). «Хэширование рандеву» . Середина . Проверено 29 марта 2021 г.
^ Маянк, Ануп; Равишанкар, Чинья (2006). «Поддержка связи мобильных устройств при наличии серверов вещания» (PDF) . Международный журнал сенсорных сетей . 2 (1/2): 9–16. дои : 10.1504/IJSNET.2007.012977 .
^ Го, Даньхуа; Бхуян, Лакшми; Лю, Бинь (октябрь 2012 г.). «Эффективный параллельный L7-фильтр для многоядерных серверов». Транзакции IEEE/ACM в сети . 20 (5): 1426–1439. дои : 10.1109/TNET.2011.2177858 . S2CID 1982193 .
^ Jump up to: ^а ^б Ван, Пэн; Равишанкар, Чинья (2015). «Атаки по подделке и краже ключей в сенсорных сетях» ( PDF) . Международный журнал сенсорных сетей .
^ Jump up to: ^а ^б Мукерджи, Нилой; и др. (август 2015 г.). «Распределенная архитектура базы данных Oracle в памяти». Труды Фонда VLDB . 8 (12): 1630–1641. дои : 10.14778/2824032.2824061 .
^ Jump up to: ^а ^б ^с GitHub Engineering (22 сентября 2016 г.). «Представляем балансировщик нагрузки GitHub» . Блог на GitHub . Проверено 1 февраля 2022 г.
^ Jump up to: ^а ^б ^с «Apache Ignite» , Arc.Ask3.Ru , 18 августа 2022 г. , получено 9 декабря 2022 г.
^ Jump up to: ^а ^б «Тахо-ЛАФС» . tahoe-lafs.org . Проверено 2 января 2023 г.
^ Jump up to: ^а ^б Пак, КёнСу; Пай, Вивек С. (2006). «Масштаб и производительность службы распространения больших файлов CoBlitz». Усеникс Нсди .
^ Jump up to: ^а ^б «Процесс маршрутизатора · Apache Druid» . druid.apache.org . Проверено 2 января 2023 г.
^ Jump up to: ^а ^б «IBM Cloud Object Storage System, версия 3.14.11, Руководство по расширению пула носителей» (PDF) . Версия IBM Cloud Object Storage SystemTM . Проверено 2 января 2023 г.
^ Jump up to: ^а ^б «Арвадос | Удержать клиентов» . doc.arvados.org . Проверено 2 января 2023 г.
^ Jump up to: ^а ^б «Горизонтальное масштабирование потребителей Kafka с помощью рандеву-хеширования» . Tinybird.co . Проверено 15 февраля 2023 г.
^ Jump up to: ^а ^б ^с Анируддха (08 января 2020 г.). «Хэширование рандеву» . я0исключение . Проверено 9 декабря 2022 г.
^ Блажевич, Любица (21 июня 2000 г.). «Распределенная базовая многоадресная рассылка (DCM): протокол маршрутизации для многих небольших групп с применением к мобильной IP-телефонии» . Проект IETF . IETF . Проверено 17 сентября 2013 г.
^ Феннер, Б. (август 2006 г.). «Независимая от протокола многоадресная рассылка — разреженный режим (PIM-SM): спецификация протокола (пересмотренная)» . IETF RFC . IETF . Проверено 17 сентября 2013 г.
^ Jump up to: ^а ^б Валлоппилиль, Винод; Кеннет Росс (27 февраля 1998 г.). «Протокол маршрутизации кэш-массива v1.0» . Интернет-проект . Проверено 15 сентября 2013 г.
^ «Протокол маршрутизации кэш-массива и прокси-сервер Microsoft 2.0» (PDF) . Майкрософт. Архивировано из оригинала (PDF) 18 сентября 2014 года . Проверено 15 сентября 2013 г.
^ Яо, Цзычжэнь; Равишанкар, Чинья; Трипати, Сатиш (13 мая 2001 г.). Виртуальные иерархии на основе хэша для кэширования в гибридных сетях доставки контента (PDF) . Риверсайд, Калифорния: Департамент CSE, Калифорнийский университет, Риверсайд . Проверено 15 ноября 2015 г.
^ Ван, Вэй; Чинья Равишанкар (январь 2009 г.). «Виртуальные иерархии на основе хэша для масштабируемой службы определения местоположения в мобильных одноранговых сетях». Мобильные сети и приложения . 14 (5): 625–637. дои : 10.1007/s11036-008-0144-3 . S2CID 2802543 .
^ Маянк, Ануп; Пхатак, Тривикрам; Равишанкар, Чинья (2006), Децентрализованная координация распределенных мультимедийных кэшей на основе хэша (PDF) , Proc. 5-я Международная конференция IEEE по сетевым технологиям (ICN'06), Маврикий: IEEE
^ ДеКандиа, Дж.; Хасторун, Д.; Джампани, М.; Какулапати, Г.; Лакшман, А.; Пильчин А.; Сивасубраманиан, С.; Восшалл, П.; Фогельс, В. (2007). «Динамо» (PDF) . Обзор операционных систем ACM Sigops . 41 (6): 205–220. дои : 10.1145/1323293.1294281 . Проверено 7 июня 2018 г.
^ Jump up to: ^а ^б ^с Джейсон Реш. «Новые алгоритмы хеширования для хранения данных» (PDF) .
^ Сейдж А. Вейль; и др. «CRUSH: контролируемое, масштабируемое, децентрализованное размещение реплицируемых данных» (PDF) . Архивировано из оригинала (PDF) 20 февраля 2019 г.
^ Р. Дж. Хоники, Итан Л. Миллер. «Репликация при масштабируемом хешировании: семейство алгоритмов масштабируемого децентрализованного распределения данных» (PDF) .
^ Цеф. «Карты разгрома» .
^ Кристиан Шиндельхауэр, Гуннар Шомакер (2005). «Взвешенные распределенные хеш-таблицы»: 218. CiteSeerX 10.1.1.414.9353 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

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

Хеширование рандеву: альтернатива последовательному хешированию

[:0-1] Jump up to: ^а ^б ^с ^д ^и ^ж Талер, Дэвид; Чинья Равишанкар. «Схема сопоставления рандеву на основе имени» (PDF) . Технический отчет Мичиганского университета CSE-TR-316-96 . Проверено 15 сентября 2013 г.

[:1-2] Jump up to: ^а ^б ^с ^д Талер, Дэвид; Чинья Равишанкар (февраль 1998 г.). «Использование схем сопоставления на основе имен для увеличения количества попаданий». Транзакции IEEE/ACM в сети . 6 (1): 1–14. CiteSeerX 10.1.1.416.8943 . дои : 10.1109/90.663936 . S2CID 936134 .

[3] «Объяснение хэширования рандеву — рандоритмы» . randorithms.com . Проверено 29 марта 2021 г.

[4] «Хеширование рандеву: мой базовый «последовательный» метод распределения — Пол Хуонг: немного Lisp» . pvk.ca. Проверено 29 марта 2021 г.

[5] Анируддха (08 января 2020 г.). «Хэширование рандеву» . Середина . Проверено 29 марта 2021 г.

[6] Маянк, Ануп; Равишанкар, Чинья (2006). «Поддержка связи мобильных устройств при наличии серверов вещания» (PDF) . Международный журнал сенсорных сетей . 2 (1/2): 9–16. дои : 10.1504/IJSNET.2007.012977 .

[7] Го, Даньхуа; Бхуян, Лакшми; Лю, Бинь (октябрь 2012 г.). «Эффективный параллельный L7-фильтр для многоядерных серверов». Транзакции IEEE/ACM в сети . 20 (5): 1426–1439. дои : 10.1109/TNET.2011.2177858 . S2CID 1982193 .

[foisting-8] Jump up to: ^а ^б Ван, Пэн; Равишанкар, Чинья (2015). «Атаки по подделке и краже ключей в сенсорных сетях» ( PDF) . Международный журнал сенсорных сетей .

[:5-9] Jump up to: ^а ^б Мукерджи, Нилой; и др. (август 2015 г.). «Распределенная архитектура базы данных Oracle в памяти». Труды Фонда VLDB . 8 (12): 1630–1641. дои : 10.14778/2824032.2824061 .

[:2-10] Jump up to: ^а ^б ^с GitHub Engineering (22 сентября 2016 г.). «Представляем балансировщик нагрузки GitHub» . Блог на GitHub . Проверено 1 февраля 2022 г.

[:3-11] Jump up to: ^а ^б ^с «Apache Ignite» , Arc.Ask3.Ru , 18 августа 2022 г. , получено 9 декабря 2022 г.

[:6-12] Jump up to: ^а ^б «Тахо-ЛАФС» . tahoe-lafs.org . Проверено 2 января 2023 г.

[:7-13] Jump up to: ^а ^б Пак, КёнСу; Пай, Вивек С. (2006). «Масштаб и производительность службы распространения больших файлов CoBlitz». Усеникс Нсди .

[:8-14] Jump up to: ^а ^б «Процесс маршрутизатора · Apache Druid» . druid.apache.org . Проверено 2 января 2023 г.

[:9-15] Jump up to: ^а ^б «IBM Cloud Object Storage System, версия 3.14.11, Руководство по расширению пула носителей» (PDF) . Версия IBM Cloud Object Storage SystemTM . Проверено 2 января 2023 г.

[:10-16] Jump up to: ^а ^б «Арвадос | Удержать клиентов» . doc.arvados.org . Проверено 2 января 2023 г.

[:11-17] Jump up to: ^а ^б «Горизонтальное масштабирование потребителей Kafka с помощью рандеву-хеширования» . Tinybird.co . Проверено 15 февраля 2023 г.

[:4-18] Jump up to: ^а ^б ^с Анируддха (08 января 2020 г.). «Хэширование рандеву» . я0исключение . Проверено 9 декабря 2022 г.

[19] Блажевич, Любица (21 июня 2000 г.). «Распределенная базовая многоадресная рассылка (DCM): протокол маршрутизации для многих небольших групп с применением к мобильной IP-телефонии» . Проект IETF . IETF . Проверено 17 сентября 2013 г.

[20] Феннер, Б. (август 2006 г.). «Независимая от протокола многоадресная рассылка — разреженный режим (PIM-SM): спецификация протокола (пересмотренная)» . IETF RFC . IETF . Проверено 17 сентября 2013 г.

[carp-21] Jump up to: ^а ^б Валлоппилиль, Винод; Кеннет Росс (27 февраля 1998 г.). «Протокол маршрутизации кэш-массива v1.0» . Интернет-проект . Проверено 15 сентября 2013 г.

[22] «Протокол маршрутизации кэш-массива и прокси-сервер Microsoft 2.0» (PDF) . Майкрософт. Архивировано из оригинала (PDF) 18 сентября 2014 года . Проверено 15 сентября 2013 г.

[CSE_Technical_Report_UCR-CS_2001-05062-23] Яо, Цзычжэнь; Равишанкар, Чинья; Трипати, Сатиш (13 мая 2001 г.). Виртуальные иерархии на основе хэша для кэширования в гибридных сетях доставки контента (PDF) . Риверсайд, Калифорния: Департамент CSE, Калифорнийский университет, Риверсайд . Проверено 15 ноября 2015 г.

[24] Ван, Вэй; Чинья Равишанкар (январь 2009 г.). «Виртуальные иерархии на основе хэша для масштабируемой службы определения местоположения в мобильных одноранговых сетях». Мобильные сети и приложения . 14 (5): 625–637. дои : 10.1007/s11036-008-0144-3 . S2CID 2802543 .

[25] Маянк, Ануп; Пхатак, Тривикрам; Равишанкар, Чинья (2006), Децентрализованная координация распределенных мультимедийных кэшей на основе хэша (PDF) , Proc. 5-я Международная конференция IEEE по сетевым технологиям (ICN'06), Маврикий: IEEE

[Amazon2007-26] ДеКандиа, Дж.; Хасторун, Д.; Джампани, М.; Какулапати, Г.; Лакшман, А.; Пильчин А.; Сивасубраманиан, С.; Восшалл, П.; Фогельс, В. (2007). «Динамо» (PDF) . Обзор операционных систем ACM Sigops . 41 (6): 205–220. дои : 10.1145/1323293.1294281 . Проверено 7 июня 2018 г.

[wrh-27] Jump up to: ^а ^б ^с Джейсон Реш. «Новые алгоритмы хеширования для хранения данных» (PDF) .

[crush-28] Сейдж А. Вейль; и др. «CRUSH: контролируемое, масштабируемое, децентрализованное размещение реплицируемых данных» (PDF) . Архивировано из оригинала (PDF) 20 февраля 2019 г.

[rush-29] Р. Дж. Хоники, Итан Л. Миллер. «Репликация при масштабируемом хешировании: семейство алгоритмов масштабируемого децентрализованного распределения данных» (PDF) .

[30] Цеф. «Карты разгрома» .

[31] Кристиан Шиндельхауэр, Гуннар Шомакер (2005). «Взвешенные распределенные хеш-таблицы»: 218. CiteSeerX 10.1.1.414.9353 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]