Простое базовое объяснение распределенной хэш-таблицы (DHT)
https://stackoverflow.com/questions/144360
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Может ли кто-нибудь объяснить, как работает DHT?
Ничего слишком тяжелого, только основы.
Решение
Хорошо, по сути, это довольно простая идея.DHT предоставляет вам интерфейс, похожий на словарь, но узлы распределены по сети.Хитрость с DHT заключается в том, что узел, который может хранить определенный ключ, находится путем хеширования этого ключа, поэтому, по сути, ваши сегменты хеш-таблицы теперь являются независимыми узлами в сети.
Это дает большую отказоустойчивость и надежность и, возможно, некоторый выигрыш в производительности, но также вызывает много головной боли.Например, что происходит, когда узел покидает сеть из-за сбоя или по какой-либо другой причине?И как перераспределить ключи при присоединении ноды, чтобы нагрузка была примерно сбалансирована.Если подумать, как вообще равномерно распределить ключи?А когда присоединяется узел, как избежать всего перефразирования?(Помните, что вам придется сделать это в обычной хеш-таблице, если вы увеличите количество сегментов).
Одним из примеров DHT, который решает некоторые из этих проблем, является логическое кольцо из n узлов, каждый из которых отвечает за 1/n пространства ключей.Как только вы добавляете узел в сеть, он находит место в кольце между двумя другими узлами и берет на себя ответственность за некоторые ключи в своих родственных узлах.Прелесть этого подхода в том, что ни один из других узлов кольца не затрагивается;только два родственных узла должны перераспределять ключи.
Например, скажем, в кольце из трех узлов первый узел имеет ключи 0–10, второй 11–20 и третий 21–30.Если появится четвертый узел и вставит себя между узлами 3 и 0 (помните, они находятся в кольце), он может взять на себя ответственность, скажем, за половину пространства ключей 3, поэтому теперь он имеет дело с 26-30, а узел 3 имеет дело с 21. -25.
Существует множество других накладных структур, подобных этой, которые используют маршрутизацию на основе содержимого для поиска правильного узла для хранения ключа.Поиск ключа в кольце требует поиска по кольцу по одному узлу за раз (если только вы не храните локальную таблицу поиска, что проблематично в DHT, состоящем из тысяч узлов), что представляет собой маршрутизацию с O(n)-прыжками.Другие структуры, в том числе расширенные кольца, гарантируют маршрутизацию с шагом O(log n), а некоторые претендуют на маршрутизацию с шагом O(1) за счет дополнительного обслуживания.
Прочтите страницу в Википедии, и если вы действительно хотите узнать больше, посмотрите это. страница курса в Гарварде, где имеется довольно обширный список литературы.
Другие советы
DHT предоставляют пользователю тот же тип интерфейса, что и обычная хеш-таблица (поиск значения по ключу), но данные распределяются по произвольному количеству подключенных узлов.В Википедии есть хорошее базовое введение, которое я бы, по сути, извергнул, если бы написал больше -
Я хотел бы добавить к полезному ответу ГенриРа, поскольку я только что получил представление о последовательном хешировании.Обычный/наивный поиск по хешу — это функция двух переменных, одна из которых — количество сегментов.Прелесть последовательного хеширования в том, что мы исключаем из уравнения количество сегментов «n».
При простом хешировании первая переменная — это ключ объекта, который будет сохранен в таблице.Мы назовем клавишу «x».Вторая переменная — это количество сегментов, «n».Итак, чтобы определить, в каком ведре/машине хранится объект, вам необходимо вычислить:хэш (х) мод (n).Следовательно, когда вы меняете количество сегментов, вы также меняете адрес, по которому хранится почти каждый объект.
Сравните это с последовательным хешированием.Давайте определим «R» как диапазон хеш-функции.R — это просто некоторая константа.При последовательном хешировании адрес объекта находится по адресу hash(x)/R.Поскольку наш поиск больше не зависит от количества сегментов, при изменении количества сегментов мы получаем меньше переназначений.
Проверить эта статья в ВикипедииИли это слайд PowerPoint
ознакомьтесь с Dynamo от Amazon, там объясняется простая, но новая реализация DHT, основанная на последовательном хешировании по кругу.
