Народ. Молю, пните меня в сторону публикаций, статей по теме алгоритмов поиска в распределённой хеш-таблицы. Я уже весь мозг себе съел, а задачу решать как-то надо. Велосипед изобретать тоже не хочется. Хотя, нет: применительно к моей задаче лучше построить велосипедный завод. Задача такая: Создать DHT для N узлов, где N >=255 Создать быстрый механизм поиска N узла. фикс
Взял книгу, пролистал. Обиделся на себя, что раньше не внимательно ее читал, но тем не менее про Distributed хеш таблицы там полезного для меня нету. Буду думать дальше.
Я нарисовал картинку, которая показывает структуру. Как найти синий ключ с красным значением? Красными линиями показано, что узлы могут знать, как быстрее найти соседа.
grouzeene Сформулируй задачу получше: что такое узлы в твоей задче? что о них изначально известно ищущему? приведи пример их любого (пусть неоптимального) опроса. поведение узлов можно менять или оно задано кем-то другим? если задано другим, то поподробнее - на какие вопросы может ответить узел? критерий окончания поиска - "в узле найдено требуемое значение" или какой-то другой?
Отошёл временно от задачи. Вернулся. Y_Mur Узел - некоторая сущность с набором данных, имеющая уникальный идентификатор. Среди этих данных могут быть указатели на следующую сущность, причем не на одну, а может и на несколько, в которых целесообразнее искать. Ищущему изначально известен UID одного узла. От него и начинаем искать. Поведение узлов статично, то есть они тупо содержат данные и знают о своих соседях. Критерий - false/true: Найден нужный узел с нужным значением. Я читал Википедию про DHT, даже скачал и начал ковырять Kademlia. Но там еще более тёмный лес. Сейчас сижу курю разные исходники, но пока не просветлел самому хотелось бы хоть пинок под зад получить в нужную сторону. У меня проект висит из-за этого, а я с поском встрял. Ну не могу додуматься, как пройтись по узлам
grouzeene Я что-то не понимаю, что конкретно полезное Вам там нужно. Там полностью описан и даже проиллюстрирован lookup.
grouzeene Правильная постановка задачи - это больше чем половина решения Так в твоей задаче узел это не комп, а просто кусок памяти с данными? - тогда как вообще получилось что у тебя нет их полного перечня? Или это всё таки компы, для общения с которыми нужно знать их UID, а остальные UIDы получать из общения с известными? Тогда если узлы статичны (не могут сами с течением времени узнавать про соседей) то соглаcно твоей диаграмме в #4 - ответ _никак_, поскольку про узел с красной точкой не знает ни один из соседей ) Или всё-таки есть некий "центр" обратившись к которому ты можешь получить полный перечень UIDов завязанных на него узлов, а взаимное знание узлов друг о друге это дополнительная информация? И в любом случае если критерии по которым узлы знают о соседях и взаимосвязь этих критериев с искомым значением неизвестны, то единственный вариант поиска - тупой перебор, а единственно возможная оптимизация - избегать повторного обращения к уже опрошенному узлу.
