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