Простое базовое объяснение распределенной хэш-таблицы (DHT)
может ли кто-нибудь дать объяснение о том, как работает DHT?
ничего слишком тяжелого, только основы.
5 ответов:
хорошо, они в основном довольно простая идея. DHT дает вам словарь-подобный интерфейс, но узлы распределены по сети. Трюк с DHTs заключается в том, что узел, который получает для хранения определенного ключа, находится путем хэширования этого ключа, поэтому в действительности ваши ведра хэш-таблицы теперь являются независимыми узлами в сети.
Это дает много отказоустойчивости и надежности, и, возможно, некоторое преимущество в производительности, но это также вызывает много головных болей. Например, что происходит, когда узел покидает сеть, отказав или иным образом? И как вы перераспределяете ключи, когда узел присоединяется, чтобы нагрузка была примерно сбалансирована. Подумайте об этом, как вы равномерно распределяете ключи в любом случае? И когда узел присоединяется, как вы избегаете перефразирования всего? (Помните, что вам придется сделать это в обычной хэш-таблице, если вы увеличите количество ведер).
одним из примеров DHT, который решает некоторые из этих проблем, является логическое кольцо из n узлов, каждый из которых принимает ответственность за 1/n пространства ключей. Как только вы добавляете узел в сеть, он находит место на кольце, чтобы сидеть между двумя другими узлами, и берет на себя ответственность за некоторые ключи в своих родственных узлах. Красота этого подхода заключается в том, что ни одно из других узлов в кольце; только две вершины должны распространять ключи.
например, скажем, в кольце из трех узлов первый узел имеет ключи 0-10, второй 11-20 и третий 21-30. Если появляется четвертый узел и вставляет себя между узлами 3 и 0 (помните, что они находятся в кольце), он может взять на себя ответственность за половину пространства ключей 3, поэтому теперь он имеет дело с 26-30, а узел 3-с 21-25.
существует много других структур наложения, таких как эта, которые используют маршрутизацию на основе содержимого, чтобы найти правильный узел для хранения ключа. Поиск ключа в кольце требует поиска по кольцу по одному узлу за раз (если вы не держите локальную таблицу поиска, проблемную в DHT тысяч узлов), который является маршрутизацией o (n)-hop. Другие структуры, в том числе дополненной кольца - гарантия o(зарегистрируйте N)-хоп маршрутизации, и некоторые претензии к O(1)-хоп маршрутизации за счет большего ухода.
прочитайте страницу Википедии, и если вы действительно хотите узнать немного глубже, проверьте это coursepage в Гарварде, который имеет довольно полный список чтения.
DHTs предоставляют пользователю тот же тип интерфейса, что и обычная хэш-таблица (поиск значения по ключу), но данные распределяются по произвольному числу подключенных узлов. Википедия имеет хорошее базовое введение, которое я по существу буду извергать, если я напишу больше -
Я хотел бы добавить к полезному ответу HenryR, поскольку у меня только что было понимание последовательного хэширования. Обычный / наивный поиск хэша-это функция двух переменных, одна из которых-количество сегментов. Красота последовательного хэширования заключается в том, что мы исключаем число ведер "n" из уравнения.
в наивном хэшировании первая переменная является ключом объекта, который будет храниться в таблице. Мы назовем ключ "x". Вторая переменная - это количество ведер, "n". Итак, чтобы определите, в каком ведре / машине хранится объект, вы должны вычислить: hash(x) mod(n). Поэтому при изменении количества сегментов вы также изменяете адрес, по которому хранится почти каждый объект.
сравните это с последовательной хеширования. Определим "R" как диапазон хэш-функции. R-это просто некоторая константа. В последовательном хэшировании адрес объекта находится в hash(x) / R. поскольку наш поиск больше не является функцией количества ведер, мы заканчиваем с меньшим переназначением, когда мы меняем количество ведер.
проверить эта статья в Википедии Или это powerpoint слайд