Простое базовое объяснение распределенной хэш-таблицы (DHT)

Может ли кто-нибудь объяснить, как работает DHT?

Ничего слишком тяжелого, только основы.

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

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

Одним из примеров DHT, который решает некоторые из этих проблем, является логическое кольцо из n узлов, каждый из которых берет на себя ответственность за 1 / n пространства ключей. Как только вы добавляете узел в сеть, он находит в кольце место между двумя другими узлами и берет на себя ответственность за некоторые ключи в своих одноуровневых узлах. Прелесть этого подхода в том, что ни один из других узлов в кольце не затронут; только два родственных узла должны перераспределить ключи.

Например, скажем, в кольце из трех узлов первый узел имеет ключи 0-10, второй 11-20 и третий 21-30. Если появляется четвертый узел и вставляется между узлами 3 и 0 (помните, они находятся в кольце), он может взять на себя ответственность, скажем, за половину пространства ключей 3, так что теперь он имеет дело с 26-30, а узел 3 - с 21 -25.

Существует много других наложенных структур, таких как эта, которые используют маршрутизацию на основе содержимого, чтобы найти правильный узел, на котором следует хранить ключ. Поиск ключа в кольце требует поиска по кольцу по одному узлу за раз (если только вы не ведете локальную справочную таблицу, проблематичную в DHT тысяч узлов), что является маршрутизацией O (n) -hop. Другие структуры, включая расширенные кольца, гарантируют маршрутизацию O (log n) -хоп, а некоторые претендуют на маршрутизацию O (1) -Hop за счет дополнительного обслуживания.

Прочитайте страницу википедии, и если вы действительно хотите узнать немного подробнее , посмотрите эту страницу курса в Гарварде, которая имеет довольно полный список для чтения.

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

http://en.wikipedia.org/wiki/Distributed_hash_table

Я хотел бы добавить к полезному ответу HenryR, поскольку я только что получил представление о последовательном хешировании. Обычный / наивный поиск хеша - это функция двух переменных, одной из которых является количество сегментов. Прелесть согласованного хеширования заключается в том, что мы исключаем количество сегментов "n" из уравнения.

В наивном хешировании первая переменная - это ключ объекта, который будет сохранен в таблице. Мы назовем ключ «х». Вторая переменная - это количество сегментов, «n». Итак, чтобы определить, в какой корзине / машине хранится объект, вы должны вычислить: hash (x) mod (n). Поэтому, когда вы меняете количество сегментов, вы также изменяете адрес, по которому хранится почти каждый объект.

Сравните это с последовательным хешированием. Давайте определим «R» как диапазон хеш-функции. R это просто некоторая постоянная. В согласованном хешировании адрес объекта находится в хэш (х) / R. Поскольку наш поиск больше не является функцией количества сегментов, мы получаем меньше переопределений при изменении количества сегментов.

http://michaelnielsen.org/blog/consistent-hashing/