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

178

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

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

Густаво Каррено
источник

Ответы:

238

Хорошо, в принципе, это довольно простая идея. 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 за счет дополнительного обслуживания.

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

HenryR
источник
23
+1 Хороший ответ. Что вы имеете в виду в третьем абзаце («Одним из примеров DHT, который решает некоторые из этих проблем, является логическое кольцо из n узлов»), является согласованное хеширование. Это действительно интересная тема, используемая в Apache Cassandra, распределенной базе данных, созданной Facebook. Ссылка на статью (стоит прочитать): cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf
santiagobasulto,
5
Протокол поиска на основе кольца, который довольно легко понять, - это Chord: pdos.csail.mit.edu/papers/chord:sigcomm01
ThomasWeiss,
Можете ли вы рассказать, как ключ-значение хранится на узле? Это будет какая-то форма хеш-таблицы или БД?
Жезл
@HenryR, Разве «узел кольца» не просто древовидная структура?
Pacerier
Университет Иллинойса обучает аккордовому протоколу каждый семестр как часть своего класса распределенных систем, если кто-то хочет больше материалов для чтения - courses.engr.illinois.edu/ece428/sp2018/lectures.html
Siddhartha
11

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

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

Питер
источник
7

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

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

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

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

thebiggestlebowski
источник
1
Тебе все равно нужно мод, не так ли? Скажем, у вас есть 3 сервера. hash(x)/Rдает 34500. Вам все еще нужно сделать 34500% 3 .
Pacerier
Ваш блог неясен, кстати, вы должны перечислить пошаговый снимок рабочего примера, где добавляются и удаляются узлы, а также добавляются и удаляются строки.
Pacerier