Kademlia DHT: Основы

    Здравствуйте!
    В этой статье, как и, надеюсь, в последующих, я хочу рассказать об одной из современных структурированных пиринговых сетей. Данный материал включает в себя мою переработку документаций, описаний и статей, найденных по теме. В качестве введения представлена общая краткая теория p2p-сетей, DHT, а уж затем следует основная часть, которой посвящена заметка.


    1. Общая теория p2p


    Распределение данных, процессорного времени и других ресурсов между пользователями заставляют искать решения организации сетей разного уровня и взаимодействия.
    На смену клиент-серверному взаимодействую приходят сети p2p (point-to-point), чтобы предоставить больший уровень масштабируемости, автономности, анонимности, отказоустойчивости.
    Далее будет приведена общая классификация.

    По степени централизации можно выделить следующие типы p2p сетей:
    • Централизованные
    • Гибридные
    • Полностью децентрализованные
    Централизованные — Сети, которые для маршрутизации и поиска используют один или несколько серверов. Печально известный Napster — классический пример централизованной p2p сети.

    Минусы сети этого типа:
    • Сервер представляет узкое место сети. Отказ приводит к полной потере работоспособности системы.
    • Законодательная уязвимость сервера
    • При значительном росте популяции сети сервер подвергнется своего рода DDoS атаке, приводящей к его отказу.
    Плюсы:
    • Весь процесс от поиска до получения файла проходит по максимально короткой схеме: поисковый запрос к серверу, выдача результатов от сервера, соединение с нужным узлом.
      При этом вполне возможен поиск не только по точным совпадениям, что немаловажно, как будет показано далее.

    Гибридные — Сети, которые содержат два типа узлов: общего назначения и супер-узлы (Super Peer). Последние назначаются динамически в зависимости от определенных условий и позволяют управлять маршрутизацией и индексацией данных в сети.

    Минусы и плюсы зависят от степени «гибридности» — какие характеристики она наследует от централизованных, а какие от децентрализованных (о которых речь пойдет далее).

    Децентрализованные — Данный тип сетей подразумевает полное отсутствие серверов. Таким образом, исключается узкое место из сети.

    Минусы:
    • Необходимы определенные алгоритмы маршрутизации и поиска, порою не гарантирующие достоверности результата.
    • Для включения в такую сеть нужно знать координаты хотя бы одного узла, следовательно, списки с определенным количеством адресных данных участников сети необходимо публиковать в общедоступных источниках (например, на сайтах). Сам процесс подклчючения подразумевает стадию начальной загрузки/инициализации (bootstrap), поэтому такие списки еще называются bootstrap-листами.
    Плюсы:
    • Исключение сервера позволяет сети быть отказоустойчивой, даже при быстро растущем/падающем количестве участников.
    • Большая степень защищенности от цензуры

    Децентрализованные сети можно разделить на структурированные и неструктурированные. В первом случае, топология сети строится по определенным правилам, позволяющим организовывать быстрый поиск данных, однако, увы, только по точному совпадению. Каждый узел, фактически, ответственен за свою область данных (как выделяются такие области, их вид, устройство таблиц маршрутизации — все это зависит уже от конкретной топологии сети). В неструктурированных сетях заранее неизвестно, куда можно отправить запрос, поэтому в самом простом варианте используется вариант flood-запросов: узел рассылает запрос соседям, те своим и т.п.). Важно, что для таких запросов определен TTL (Time To Live), позволяющий отсекать их после определенного количества скачков по сети. Очевидно, что при низком TTL сеть будет выдавать ложные результаты поиска (не достигая некоторых источников), а при высоком — время на запросы, да и количество трафика могут непозволительно возрасти. Однако, в отличии от структурированных сетей, возможен поиск не только по точным совпадениям, что немаловажно для файлообменных систем. Масштабируемость неструктурированных сетей если не отсутствует, то весьма проблематична (наличие TTL и растущее время поиска данных).

    При проектировании топологии и протоколов структурированных сетей оптимальным считается выполнение соотношений:
    — Размер таблицы маршрутизации на каждом узле: O(log(n))
    — Сложность поиска: O(log(n))

    2. DHT


    DHT (Distributed Hash Table) — распределенная хэш-таблица. Данная структура зачастую используется для децентрализованных топологий. Однако, это не единственный выбор (как подсказывает литература, впрочем, здесь лучше заняться дальнейшим самостоятельным поиском).
    Для каждого значения (данных) на каждом узле вычисляется по определенным правилам хэш (например, с помощью SHA-1), который становится ключом. Также, вычисляется идентификатор узла (той же длины, что и хэш, а зачастую, той же функцией). Таким образом, каждый узел сети обладает своим идентификатором. Ключи публикуются в сети. Узел несет ответственность за ключи таблицы, которые близки к нему по определенной метрике (т.е. расстоянию), здесь подразумевается «похожесть» ключа на идентификатор, если опустить язык математики. Благодаря этому, каждый узел занимает свою зону ответственности при хранении ключей и связанных с ней информации (координаты узла, на котором расположено значение). Это позволяет определенным образом организовать алгоритм поиска по точным значениям (сначала вычислить ключ значения для поиска, например, имени файла, а затем искать этот ключ, направляя запросы к узлу, ответственному за него через посредников, предоставляющих полный путь).
    DHT в полной степени обеспечивает отказоустойчивость и масштабируемость. В сочетании с Peer Exchange, например, DHT позволяет перехватить функции Torrent-трекера.

    3. Kademlia



    Метрика


    Создателями данной топологии являются Petar Maymounkov и David Mazières. В основе работы протокола и построения таблиц лежит определения расстояния между узлами через XOR-метрику:
    d(x, y) = x XOR y. Важно отметить, что расстоянием является результат операции XOR, интерпретируемый, как число, а не количество различающихся бит (такой критерий тоже может порождать метрику в пространстве ключей/идентификаторов). Т.е. при длине ключа 4 бита: d(2,5) = 0010 XOR 0101 = 0111 = 7.
    XOR метрика удовлетворяет всем аксиомам метрики:

    1. d(x, y) >= 0 // Неотрицательность
    2. d(x, y) == 0 <=> x == y
    3. d(x, y) = d(y, x) // Симметричность
    4. d(x, y) <= d(x, z) + d(z, y) // Неравенство треугольника

    Данное свойство отмечают в связи с возможностью формального доказательства тезисов о размерах таблиц маршрутизации и сложности поиска. (Справедливости ради, предоставляемого в виде наброска).

    Таблица маршрутизации


    На вычислении расстояний между узлами (посредством применения метрики к их идентификаторам) базируется алгоритм построения таблиц маршрутизации.
    Каждый i-ый столбец таблицы ответственен за хранение информации об узлах на расстоянии от 2^(i+1) до 2^i. Таким образом, последний столбец для узла 0111 может содержать информацию о любых узлах 1xxx, предпоследний об узлах 00xx, еще на уровень ближе — об узлах 010x.

    Конечно, в реальной сети, применяется обычно длина ключа в 128, либо в 160 бит. Зависит от реализации.

    Далее, вводится ограничение на число хранимых узлов на каждом уровне, K. Поэтому столбцы таблицы, ограниченные таким K, называют K-buckets (к сожалению, русский эквивалент, звучит совсем неблагозвучно).

    Если рассмотреть бинарное дерево поиска, в листах которого лежат идентификаторы узлов, становится понятно, что такая структура K-buckets не случайна: каждый узел (а на примере 110) получает знания хотя бы об одном участнике каждого поддерева (для 110 выделенных залитыми овалами). Таким образом, каждый K-bucket отражает связь узла с не более, чем K участниками поддерева на уровне i.




    Протокол


    Протокол Kademlia содержит 4 типа сообщений:
    • PING
    • STORE
    • FIND_VALUE
    • FIND_NODE

    PING нужен для проверки существования конкретного узла в сети. Например, он применяется при попытке добавления узла в K-bucket, когда тот уже заполнен: опрашиваются существующие узлы, если нет ответа, то узел вставляется. Стоит отметить, что более старые узлы находятся внизу K-bucket, это основывается на экспериментальных данных, говорящих о том, что чем дольше узел остается в сети, тем меньше вероятности, что он ее покинет. Поэтому они будут опрошены только после более новых.

    STORE запрос, позволяющий разместить информацию на заданном узле. Перед выполнением STORE узел должен найти K ближайших к ключу значения, которое он собирается опубликовать, а лишь потом отправить каждому STORE с ключом и своими координатами. Хранение сразу на K узлах позволяет повысить доступность информации.

    FIND_VALUE запрос, который, зачастую, повторяется для образования итерации, позволяющий найти значение по ключу. Реализует поиск значения в сети. Возвращает либо K ближайших узлов, либо само значение, в зависимости от достижения узла, хранящего искомые данные. Итерации прекращают как раз либо при возвращении значения (успех), либо при возврате уже опрошенных K узлов (значения нет в сети).

    FIND_NODE запрос, используемый для поиска ближайших K к заданному идентификатору (поведение сходно с FIND_VALUE, только никогда не возвращает значение, всегда узлы!). Используется, например, при присоединении узла к сети по следующей схеме:
    — Контакт с bootstrap узлом
    — Посылка запроса FIND_NODE со своим идентификатором к bs узлу, дальнейшая итеративная рассылка
    — Обновление K-buckets (при этом обновляются как K-buckets нового узла, так и всех, мимо которых проходил запрос (здесь на руку симметричность метрики XOR))

    Как видно, протокол в своей спецификации практически не покрывает вопросы безопасности, что нашло отражение в исследованиях и работах по атаке Kademlia-based сетей.
    Из особенностей стоит подчеркнуть наличие репликации, времени жизни значения (необходимость повторного размещения через определенный промежуток времени), параллелизм при посылке запросов FIND_*, дабы достигнуть нужных узлов за более короткое время (обозначается α, в реализациях обычно равно 3). При каждом прохождении запросов происходит попытка обновить K-bucket, что позволяет держать таблицы маршрутизации максимально оптимальными.

    4. Реализации


    Прежде всего, самой известной сетью, базирующейся на Kademlia является Kad Network, доступная в aMule/eMule. Для bootstrap используются существующие узлы в eDonkey.
    Khashmir — Kademlia-реализация на Python, использующаяся в BitTorrent
    Из ныне развивающихся и активных библиотек я бы еще отметил
    maidsafe-dht — C++ реализация инфраструктуры с поддержкой UDT и NAT Traversal.
    Mojito — Java библиотека от LimeWire.

    5. Что дальше?


    Хотел бы получить комментарии о том, во что следует углубиться подробнее, т.к. статья носит чрезвычайно поверхностный характер. Дабы пробудить интерес, а не выложить все карты разом на стол. Сам планирую в следующей заметке о Kademlia рассказать о проблемах безопасности, атаках и их предотвращении.

    6. Материалы и ссылки


    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 35

      –3
        +4
        Простите, а в чем вопрос? :)
        +14
        очень давно занимаюсь децентрализованными сетями и даже веду свои теоретические и практические разработки в этом направлении, если тема будет интересна, могу опубликовать обзор Chord DHT и своих наработок
          +1
          Как Вы понимаете, лично мне было бы очень интересно!
            +9
            Да всем однозначно будет интересно. Последнее время на Хабре маловато интересных технических статей. Все больше новости проскакивают…
              +1
              Тысяча чертей, конечно же да!
              +1
              Тема очень актуальная, ждём Вашего обзора!
                0
                Надеюсь, что в ближайшую неделю выкрою время. Сам весьма заинтересован в накоплении и переработке материала :)
                +1
                Интересная тема, буду ждать продолжения.
                Не подскажете, на каком этапе развития находится протокол JXTA?
                  0
                  Продолжение будет!
                  Про JXTA не слыхивал даже ранее, спасибо за ссылку, гляну. Пугает вот только отсутствие новостей и старые бренды Sun на сайте.
                • UFO just landed and posted this here
                    0
                    Не без этого. Лично мне добавляет интереса к сабжу.
                      +1
                      Да какой матан, просто немного алгебры.
                      +1
                      Было бы очень интересно узнать ваше мнение на счет реализации «растущего файла» в p2p-сети, попросту говоря — форума.
                        0
                        На основе DHT? Т.е., например, Kademlia?
                        Ну я бы вводил тогда три типа сущностей: разделы, темы, сообщения.
                        Соответственно, привязал бы темы к разделам, сообщения к темам. Таким образом, можно отправлять запросы на поиск каждой сущности. Запрос на добавление сообщения к теме обрабатывается узлами, хранящими ее (они просто дополняют список сообщений внутри себя). Модерировать тему имеет право только создатель, как я думаю. Идентифицировать его можно с помощью публичного ключа.
                        Клиенту не помешало бы поддерживать закладки, любимое и т.п., дабы сделать итоговый продукт удобоваримым и оправданным.
                        Вопрос, конечно, интересный, надеюсь, я правильно его понял?..
                        Что Вы сами думаете о своей идее (наработки, черновики)?
                        //
                        Да, забыл заметить в заметке, что в структурированных сетях на Kademlia (да и в других) проблема поиска по ключевым словам и тегам следующим образом: пользователь, публикующий файл должен определить набор тегов и ключевых слов, связанных с файлом, тогда будет вызвать специальный вариант STORE для ключей, произведенных ключевыми словами, который разместит ссылку на настоящий ключ. Того же эффекта, в-принципе, можно добиться, создав в файловой системе символические ссылки на нужный файл с именами-тегами.
                          0
                          Правильно понимаю, что каждое сообщение имеет указатель на «родителя-тему»? Т.е. поиск по хешу, как если бы искали торрент в DHT? Не будет ли слишком накладно искать таким способом? Обычный торрент однозначно идентифицируется по хэшу: хэш = содержимое, а здесь придется добавлять какой-то список, и каким-то образом передавать его в запросе, чтобы в ответ не присылали те сообщения, которые уже у вас есть.
                          Самый простой был бы вариант со счетчиком, просто сообщать максимальный номер сообщения, который у вас есть. Посколько сообщения появляются по очереди, то это хороший вариант. Но есть проблема: два пользователя одновременно могут создать сообщения с одинаковым номером думая, что дают максимальное значение. Да еще хотелось бы передавать сообщения при создании (получении), а не получать послав запрос, т.е. сократив два движения в одно.
                          Поиск по тегам вещь безусловная нужная, но без нее получается достаточно изолированная и «секретная» система: не зная хэш не найдешь тему. Это хорошая защита от спама.
                          Модерировать можно просто: каждый может отключить отображение сообщений от определенного пользователя (можно даже передавать специальное сообщение "-1" для пользователя, чтобы был общий рейтинг и новоподключившиеся могли бы оценивать собеседников сразу, однако это ведет к злоупотреблениям — хабр тому пример; )
                          Набросков нет, никак не могу продумать эту систему.
                          Я не уверен, что понял правильно, но кажется вы предлагаете синхронизировать тему через «держателя», обычно пользователя, который начал разговор? У вас список «узлов, хранящие тему» это все участники? Проблема как идентифицировать сообщения, чтобы у всех участников они были одинаковыми, чтобы запрашивать только недостающие сообщения. Хэш не подходит, придется отсылать большой список того, что у вас уже есть. Порядковый номер не подходит, потому что может сбоить, если два клиента будут иметь разные максимальные номера (не до конца скачали), либо просто отправят сообщение одновременно. Может быть подойдет временная метка (точно покажет последовательность), но нужна синхронизация времени, которая не факт что проще, чем синхронизация количества сообщений в теме.
                      0
                      >Правильно понимаю, что каждое сообщение имеет указатель на «родителя-тему»?
                      Ага. С каждым сообщением опять же связать набор тегов, поэтому хешировать не каждое слово сообщения, а только ключевые. При этом чтобы не получать повторные данные можно в заголовки ответа включать время модификации (при условии наличия единого времени), т.е. проводить банальное кеширование.
                      Думаю, что чаще все-таки ищут по темам, а не сообщениям.

                      > Да еще хотелось бы передавать сообщения при создании (получении), а не получать послав запрос, т.е. сократив два движения в одно.
                      Передавать кому? Сразу всем участникам? Это дикий трафик. Вы предлагаете хранить у каждого свою копию форума? Это как-то сумбурно и очень накладно.

                      >Поиск по тегам вещь безусловная нужная, но без нее получается достаточно изолированная и «секретная» система: не зная хэш не найдешь тему. Это хорошая защита от спама.
                      Не знаю, это еще и защита от пользователя…

                      >Я не уверен, что понял правильно, но кажется вы предлагаете синхронизировать тему через «держателя», обычно пользователя, который начал разговор?
                      Нет, держатель имеет право ее модифицировать (удалять неугодные, цензурить и т.п.)

                      У вас список «узлов, хранящие тему» это все участники? — Нет. Это узлы, ответственные за хэш названия темы.

                      >Проблема как идентифицировать сообщения, чтобы у всех участников они были одинаковыми, чтобы запрашивать только недостающие сообщения.

                      Я вообще предлагаю стягивать только нужное по поиску :) знать только список разделов форума на первом этапе, все остальное — поиск…

                        0
                        > Передавать кому? Сразу всем участникам? Это дикий трафик. Вы предлагаете хранить у каждого свою копию форума? Это как-то сумбурно и очень накладно

                        Это еще одна проблема. Передавать нужно не всем, а каким-то определенным участникам. Например «ближайшим» через XOR. Например двум: выше(+1) и ниже(-1) вашего идентификатора. Каждый из них передает так же, но тогда вам дважды придет ваше же сообщени.
                        А вот хранить придется все сообщения из темы у каждого участника темы. Конечно все-все-все сообщения системы хранить ни к чему. Хотя предусмотреть передачу сообщений через клиента-не-участника-темы все же желательно.

                        > Не знаю, это еще и защита от пользователя…
                        Конечно. Варианты: 1) по приглашению, а значит тегов никаких нет, и поиска не получится; 2) с тегами, с «подключением» к старшему уровню (теме)

                        > Нет, держатель имеет право ее модифицировать (удалять неугодные, цензурить и т.п.)
                        Понял. Тогда придется предусмотреть набор команд для удаления у остальных (а клиент может ее и не выполнять). И вообще я против вахтеров; ) Каждый должен сам решать, что ему читать.

                        > знать только список разделов форума на первом этапе, все остальное — поиск…

                        Т.е. единственный вариант: запрашивать хэш темы(раздела, форума) и получать сообщения из нее? Тогда вопрос: как указать, какие у вас сообщения уже есть, чтобы их не присылали?
                        У меня пока что единственная мысль, которая может сработать: ограничить количество сообщений в теме. Допустим 256 блоков, по 256 сообщений. Тогда можно сделать как bittorrent: при запросе посылать битовую маску блоков, которые уже есть. И, если блок не полный, то еще одну маску обозначающую имеющиеся сообщения. Хотя тут все равно остается проблема, как давать сообщению «место» в битовой маске, т.е. его номер, чтобы несколько клиентов не создали разные сообщения одновременно с одним номером.
                          +2
                          Еще раз, соль моего варианта, что весь форум именно распределен, а не скопирован по узлам сети. Боюсь, что мы говорим об абсолютно разных вещах. Сообщения темы пользователь получает либо целиком, либо порциями, но только через поиск! Чтобы предотвратить лишний трафик, у темы есть дата изменения — это банально.

                          Просто расскажу, как я вижу работу своего варианта:
                          Я захожу, вижу список разделов… Ищу тему «куплю пылесос», у меня считается хэш этой фразы. Мне присылается тема/несколько, удовлетворяющих поиску, я выбираю нужную, подтягиваются сообщения из нее. Я постю ответ, при этом мое сообщение не остается у меня, а уходит на узел/узлы, ответственные за его хэш, я могу также определить теги для этого сообщения, если вдруг кто захочет искать по сообщениям, далее сообщение также регистрируется в теме (информация о его хэше).
                            0
                            > Сообщения темы пользователь получает либо целиком, либо порциями, но только через поиск!
                            Согласитесь, что читать нужно все целиком. Другое дело, когда участник получает новые сообщения, тогда ему целиком качать не нужно все сообщения сразу. Но если он только подключился, то скачать надо все.
                            Не могу понять, как можно не хранить все сообщения темы, если их все нужно читать.

                            > Я постю ответ, при этом мое сообщение не остается у меня, а уходит на узел/узлы, ответственные за его хэш, я могу также определить теги для этого сообщения, если вдруг кто захочет искать по сообщениям, далее сообщение также регистрируется в теме (информация о его хэше).

                            «Отвественные узлы» хранят большое количество несвязанных сообщений? По близости хэша?
                            Разумно, для децентрализации и чтобы концов не найти. Но нет ли тут одной проблемы и одной странной недоработки.
                            1) Не участник темы, который хранит сообщения не имеет выгоды. Поясню: человек не читает конретную ветку (он и не знает, что она есть) и просто отключается. Навсегда. По вашей схеме получается, что сообщения хранятся у тех, кто их не читает, а значит и срок доступности сообщений уменьшается. Причем при таком раскладе бд на клиенте постоянно растет до бесконечности.
                            2) Клиент, который читает и пишет в тему не хранит сообщения. Но на компьютере у него они все равно будут (ну не качать же их каждый раз заново при подключении), только по его хэшу в вашей схеме у него никто не будет запрашивать сообщения, хотя у него, как у участника темы спросить их было бы проще всего.
                            Ну и непонятно, какая должна быть избыточность (на скольких клиентах хранить), чтобы тема была постоянно доступна целиком, а не частично. А то возникнет ситуация, что часть сообщений появляется (а то и совсем не появляется) в процессе чтения темы, причем в произвольном порядке.
                            В противовес, случай когда тема целиком хранится у участников темы. Сразу понятно у кого запрашивать. Сразу можно получать большие куски — несколько идущих подряд сообщений. Т.е. гонять не по одному килобайту, а сразу хорошую порцию.

                            Я так понял, ваша схема ничем не отличается от комментариев в Kad. Только дополнена поиском именно по комментариям и деревянной структурой комментарием. Т.е. получить новые сообщения, можно только полным опросом сети. Я же говорил о неком интерактиве: сообщение отсылается участникам по какой-то схеме в момент его создания. Для примера можно посмотреть Streamerp2p (там правда чат). Не знаю как там реализовано конкретно, но сообщения рассылаются в момент создания, и похоже, что блоком. И последний блок новый клиент получает в момент подключения. А в форуме должна быть возможность скачать тему от начала.
                              0
                              >Согласитесь, что читать нужно все целиком.
                              Не согласен :) Я про пейджер говорил, т.е. сначала скачать первые 50, потом, при желании пользователя, еще 50 и т.п.

                              >«Отвественные узлы» хранят большое количество несвязанных сообщений? По близости хэша?
                              Да.

                              >1) Не участник темы, который хранит сообщения не имеет выгоды. Поясню: человек не читает конретную ветку (он и не знает, что она есть) и просто отключается. Навсегда. По вашей схеме получается, что сообщения хранятся у тех, кто их не читает, а значит и срок доступности сообщений уменьшается. Причем при таком раскладе бд на клиенте постоянно растет до бесконечности.

                              Да, частично проблему решит хранение сразу на нескольких ближайших. (Как и сделано в той же Kademlia). Однако, я не думаю, что интерес участника увеличивается, если он хранит только свои сообщения. Ведь нужно, чтоб их читали => опять же оставаться в сети. Понимаете? Тут в любом случае необходимо пребывание.

                              >2) Клиент, который читает и пишет в тему не хранит сообщения. Но на компьютере у него они все равно будут (ну не качать же их каждый раз заново при подключении), только по его хэшу в вашей схеме у него никто не будет запрашивать сообщения, хотя у него, как у участника темы спросить их было бы проще всего.

                              Резонно. Он может от них избавляться при публикации.

                              >Ну и непонятно, какая должна быть избыточность (на скольких клиентах хранить), чтобы тема была постоянно доступна целиком, а не частично. А то возникнет ситуация, что часть сообщений появляется (а то и совсем не появляется) в процессе чтения темы, причем в произвольном порядке.

                              Экспериментально :)

                              >В противовес, случай когда тема целиком хранится у участников темы. Сразу понятно у кого запрашивать. Сразу можно получать большие куски — несколько идущих подряд сообщений. Т.е. гонять не по одному килобайту, а сразу хорошую порцию.

                              Т.е. поступать как с файлами? Хранить у ближайших к хешу только информацию о нахождении сообщения? :) Можно и так.

                              >Т.е. получить новые сообщения, можно только полным опросом сети.
                              Не то что бы полным… опросить содержимое темы, по содержимому опросить записанные хэши новых сообщений у ответственных узлов.

                                0
                                > Не согласен :) Я про пейджер говорил, т.е. сначала скачать первые 50, потом, при желании пользователя, еще 50 и т.п.

                                Ладно. Первые 50 ведь все нужно? И желательно подряд.

                                > Да, частично проблему решит хранение сразу на нескольких ближайших. (Как и сделано в той же Kademlia). Однако, я не думаю, что интерес участника увеличивается, если он хранит только свои сообщения. Ведь нужно, чтоб их читали => опять же оставаться в сети. Понимаете? Тут в любом случае необходимо пребывание.

                                О том и речь, поэтому я и говорю, что копия темы должна быть у каждого участника, а не только у некоторых клиентов с похожим хэшем. Тогда получится, что 1) хранит он все не зря, 2) при наличии хотя бы одного участника в сети есть возможность получить тему. Хотя это не исключает возможности хранения сообщений разбросанными согласно хэшу по другим клиентам не участникам темы.

                                > Т.е. поступать как с файлами? Хранить у ближайших к хешу только информацию о нахождении сообщения? :) Можно и так.
                                Ага.
                                А можно и совместить: хранить сообщения и хранить адрес где их можно взять в полном объеме.

                                Тут момент еще один есть: уместно ли вообще хранить сообщения не у участника темы. Т.е. при нешифрованных несекретных сообщениях проблем нет. А если хочется сделать относительно защищенную (хотя бы против дурака) систему?
                                Нужно шифровать. А там нужно как-то передавать ключ. А там еще что-нибудь. Т.е. это уже более прикладные вопросы. Но они зависят от общей концепции архитектуры.

                                > опросить содержимое темы, по содержимому опросить записанные хэши новых сообщений у ответственных узлов.

                                Смущает, что надо будет опрашивать сеть о наличии новых сообщений с какой-то периодичностью. Т.е. реально сотня мертвых тем, а клиент все равно просит поискать что-то новенькое. В идеале: запрашивать о новых сообщениях не нужно, ввести «подписчика темы» и новые сообщения рассылаются между подписчиками. Плюс возможность для новых участников получать содержимое темы по запросу (также полезно для старых участников, которые уже опредленное время не получали новых сообщений).
                                  0
                                  >Ладно. Первые 50 ведь все нужно? И желательно подряд.

                                  Да.

                                  >О том и речь, поэтому я и говорю, что копия темы должна быть у каждого участника, а не только у некоторых клиентов с похожим хэшем. Тогда получится, что 1) хранит он все не зря, 2) при наличии хотя бы одного участника в сети есть возможность получить тему. Хотя это не исключает возможности хранения сообщений разбросанными согласно хэшу по другим клиентам не участникам темы.

                                  Так или иначе, она у него появится, когда он ее запросит :) Поэтому участник темы сразу становится обладателем ее копии. Тогда можно внутри файла темы записать и его контакты, чтобы получать сообщения. Ведь он тоже может и будет делать STORE от своего лица! Всего того, что он скачал :)

                                  >Тут момент еще один есть: уместно ли вообще хранить сообщения не у участника темы. Т.е. при нешифрованных несекретных сообщениях проблем нет. А если хочется сделать относительно защищенную (хотя бы против дурака) систему?
                                  Нужно шифровать. А там нужно как-то передавать ключ. А там еще что-нибудь. Т.е. это уже более прикладные вопросы. Но они зависят от общей концепции архитектуры.

                                  Да, не секурно, если это критично :) Приходим опять же к хранению не самих данных, а контактной информации о них…

                                  >В идеале: запрашивать о новых сообщениях не нужно, ввести «подписчика темы» и новые сообщения рассылаются между подписчиками.

                                  Хороший вариант.
                                    +1
                                    На том и порешили :)
                        +1
                        Было бы ещё здорово, если бы вы проиллюстрировали аргументы сообщений (ping, store, find_value, find_node) в виде списка формальных параметров к каждому «методу». Трудно воспринимается, не очень понятно, где что передаётся.

                        И я правильно понял, что данные (в виде хэшей) хранятся на ближайших к ним (к их хэшам) узлам, а не на ближайших к нашему идентификатору?
                          +1
                          >И я правильно понял, что данные (в виде хэшей) хранятся на ближайших к ним (к их хэшам) узлам, а не на ближайших к нашему идентификатору?

                          Да. Только сами данные остаются у того, кто делает запрос STORE. Узлы, ближайшие к хэшу хранят кэш и контактную информацию узла, сделавшего STORE.
                            0
                            кэш = хэш
                            +1
                            Так, ну для каждого типа сообщений есть REQ и RES вариант. В зависимости от того, запрос это или ответ, т.е.:

                            PING_REQ/PING_RES
                            STORE_REQ/STORE_RES
                            и т. п.

                            Для каждого REQ создается уникальный ID сообщения, чтобы при получении RES с тем же ID запрос можно было считать завершенным. Поэтому про ID запроса я дальше уже упоминать не буду, он есть у каждого запроса и ответа.
                            Аргумент PING — IP:Port. Банально :) Скорее всего, опять же есть какой-то time-out. Вернется через RES статус.
                            Аргумент STORE — hash, ip:port владельца. Т.е. запрос на сохранение ключа(хэша), значение которого лежит по заданному адресу. Через RES вернет K узлов, опубликовавших файл, в виде кортежей (см. далее).
                            Аргумент FIND_NODE — hash. Это ID узла, который, например, присоединяется в сеть (как в описанном ранее случае), с помощью RES возвращается кортеж из не более K элементов, вида <NODE_ID, IP:Port>
                            Аргумент FIND_VALUE — hash. Будет возвращать либо кортежи, либо IP:Port, по которому лежат данные.

                            Как-то вот получается…

                            +1
                            Хорошо, что эти давние задумки наконец-то развиваются.

                            По-хорошему, задача такова: нужна прозрачная интеграция псевдонимичной децентрализованной сети обмена данными поверх стандартного TCP/IP таким образом, чтобы для пользователя это был обычный обмен файлами — как WebDAV, например.
                            Ну то есть чтобы пользоваться этой сетью могла любая блондинка, не устанавливая дополнительного софта. Либо чтобы это было удобно и красиво, как uTorrent, например.
                              0
                              Да-да! Я сам хожу погруженным в эти мысли уже пару дней. Что наличие Javascript реализации p2p + поддержка в браузерах протокола p2p:// могла бы перевернуть мир, если какая-нибудь соц. сеть взялась бы отвечать за bootstrap (поддержка в виде поля в профиле пользователя)…
                                +1
                                Зачем такая сложность, браузеры и прочее?
                                Может, сервис или демон, следит за событиями системы, когда пользователь вставляет магнет ссылку, как файл, — начинается закачка. Вызвал контекстное меню любого файла, выбрал «создать магнет ссылку» — запустилась раздача и сгенерирована ссылка для публикации. То же можно делать и с торрент файлами.
                                Помотрите на Wuala — p2p хранилище и обмен.
                                  +1
                                  PS не обязательно вставлять ссылку, можно, также, запускать закачку, когда кто-то или что-то пытается открыть файл у которого имя является магнет ссылкой — по мере загрузки открывается содержимое раздачи.
                                  PS2 Для «блондинок» необходимо, чтобы данная служба/демон следили за рейтингом и, даже если пользователь удалит загруженный контент, — наименее доступные части раздаются из кеша. IMHO: учитывая возможности современной техники — пользователь, даже, не должен знать такого слова, как «рейтинг».
                                  PS3 Была бы интересна возможность, кроме содержимого раздачи, получать актуальную информацию о новых версиях и о месте данной раздачи в иерархии: лежала ссылка месяц, поставил на закачку, и тут же узнаешь, что это продолжение какой-то раздачи и уже есть новая версия… Возможностей появляется куча! От публикации и хранения документов, до информации о новых качественных раздачах.
                                0
                                > сети p2p (point-to-point)

                                Peer-to-peer
                                  0
                                  > В сочетании с Peer Exchange, например, DHT позволяет перехватить функции Torrent-трекера

                                  ?

                                  Only users with full accounts can post comments. Log in, please.