Ответ 1
Хорошо, это принципиально простая идея. DHT предоставляет вам словарь-подобный интерфейс, но узлы распределяются по сети. Трюк с DHT заключается в том, что node, который получает для хранения определенного ключа, определяется путем хэширования этого ключа, так что ваши ведра хэш-таблицы теперь являются независимыми узлами в сети.
Это дает много отказоустойчивости и надежности и, возможно, некоторую производительность, но также вызывает множество головных болей. Например, что происходит, когда node покидает сеть, отказывая или иным образом? И как вы перераспределяете ключи, когда присоединяется node, так что загрузка грубо сбалансирована. Подумайте об этом, как вы равномерно распределите ключи? И когда присоединяется node, как вы избегаете переигрывать все? (Помните, что вам придется делать это в обычной хэш-таблице, если вы увеличиваете количество ковшей).
Одним из примеров DHT, который решает некоторые из этих проблем, является логическое кольцо из n узлов, каждый из которых берет на себя ответственность за 1/n пространства ключей. Как только вы добавите в сеть node, он найдет место на ринге, чтобы сидеть между двумя другими узлами, и берет на себя ответственность за некоторые из ключей в своих дочерних узлах. Красота этого подхода заключается в том, что ни один из других узлов в кольце не затронут; только два узла-брата должны перераспределять ключи.
Например, скажем, в три кольца node первый node имеет ключи 0-10, второй 11-20 и третий 21-30. Если четвертый node приходит и вставляет себя между узлами 3 и 0 (помните, что они находятся в кольце), он может взять на себя ответственность за половину из 3-х ключей, поэтому теперь он имеет дело с 26-30 и node 3 - 21-25.
Существует много других структур наложения, которые используют маршрутизацию на основе контента, чтобы найти правильный node, на котором будет храниться ключ. Поиск ключа в кольце требует одновременного поиска по кольцу node (если вы не держите локальную таблицу поиска, проблемную в DHT из тысяч узлов), которая представляет собой маршрутизацию O (n) -hop. Другие структуры, в том числе дополненные кольца, гарантируют маршрутизацию O (log n) -hop и некоторые претензии к маршрутизации O (1) -hop за счет большего обслуживания.
Прочитайте страницу wikipedia, и если вы действительно хотите узнать немного, посмотрите эту курс в Гарварде, где есть довольно полный список литературы.