Изменения

Рассмотрим пример полностью децентрализованной структурированной P2P сети. Предположим, что мы пытаемся поддерживать какую-то DHT: Distributed Hash Table,и хотим, чтобы система была децентрализованная. Скажем, что ключами нашей хеш-таблицы будут, например, 160-битные числа (какой-то хеш объекта). Назначимкаждому узлу 160-битное число (например, случайно), и каждый узел будет отвечатьза объекты, для ключей которых число в этой вершине ближайшее среди всех чиселвершин.  Для инициализации можно считать, что у нас достаточно мало узлов в сети, каждый узнает ключи других узлов, и инициализирует свою часть хеш-таблицы. Предположим, что клиент подключился к одному из узлов сети, и хочет найти сервер,отвечающий за какой-то ключ k. Простой способ -- заставим каждый узел хранитьследующий и предыдущий (по ассоциированному ключу) узлы, и тогда, если ключнаходится не в зоне нашей ответственности, можно спокойно передать запрос следующей вершине. Если какой-то узел хочет выйти из сети, он говорит своим соседям, что больше работать не будет, и передает им свои части таблицы. Подключение новых узлов работает аналогично. К сожалению, это работает медленно: пробегать для каждого запроса в среднемполовину серверов -- не лучшая идея. Вместо этого можно хранить что-то вродедвоичных подъемов: не только ссылку на следующий сервер, но и ссылку на сервера,отвечающие за ключ (k+2^0)%2^160, (k+2^1)%2^160), etc. Таким образом, мы сможемдойти до нужного сервера всего за логарифм операций.  Для увеличения надежности можно хранить ссылку не только на предыдущую/следующуювершины, но на несколько (3-5) ближайших. Это нужно для того, чтобы при внезапномотключении узла, который не успел договориться с соседями, не прерывать связностьсети. Кроме того, нужно периодически отсылать сообщения серверам, на которые у нас ведут быстрые ссылки: при добавлении вершины честно пересчитать всепереходы на 2^n во всех узлах сети не представляется возможным, а вот отдатьэту задачу самим узлам, чтобы они периодически проверяли корректность своихданных -- нормальная идея. Таким образом, мы рассмотрели пример децентрализованной структурированной P2P сети.