?

Log in

No account? Create an account
p2p - Олег Етеревский [entries|archive|friends|userinfo]
Oleg Eterevsky

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

p2p [29 January 2006|12:06]
Oleg Eterevsky
[Tags|, ]
[Current Mood |curious]

Последние несколько дней мне не дают покоя странные мысли по поводу возможностей P2P-сетей. P2P-сети на данный момент представляет собой набор компьютеров, которые позволяют качать друг у друга файлы. Как правило, это реализовывается с помощью одного или нескольких серверов, которые помнят, у кого какие файлы есть. Входишь в систему, говоришь серверу: «Здравствуйте, у меня есть то-то и то-то». Потом: «А нужно мне вот это». И сервер тебе говорит: «Вот это есть на таких-то машинах». В случае распространённого BitTorrent'а поступили ещё проще — трекер (так там называется сервер) следит только за теми, у кого есть один из интересующих его файлов.

Итак, файлы больше не лежат на сервере. Следующий логичный шаг — убрать сервера вовсе. Требуется чтобы системы сами могли искать что есть друг у друга, да к тому же поддерживать сеть целостной, самостоятельно, без помощи сервера. Наиболее естественный способ реализации этого — распределённый хэш. Каждая система отвечает за некоторое (небольшое) количество пар ключзначение и есть возможность достаточно быстро её найти. Ключами могут выступать слова, по которым происходит поиск или MD5-хэши лежащих файлов. Такая система реализована, например, в eMule — самой распространённой p2p-программе. Называется такая сеть там KAD и реализует алгоритм Kademlia. Всего есть около полудюжины алгоритмов, реализующих этот механизм. Ссылки почти на все приведены в конце поста.

Предположим, файлами мы меняться научились. А что мешает теперь выкладывать в p2p-сети целые сайты? В принципе, сайт разбивается на файлы, которые можно выкачивать с помощью этого механизма. Встающие проблемы — значительно увеличивается количество требующихся файлов, повышаются требования к скорости отклика и главное: страницы сайта нужно иметь возможность изменять. Ещё в 2002-м году была предпринята попытка реализовать «сайтовую» p2p-сеть с дополнительным требованием обеспечения анонимности. Это Freenet. Проблема в том, что работает оно ну очень медленно. Вчера, когда я с ней экспериментировал, где-то за час мне удалось открыть всего 5–6 страниц. Вероятно, не последнюю роль в торможении играет это самое обеспечение анонимности — из-за него страницы, возвращающиеся по запросу проходят через все промежуточные системы, вместо того, чтобы передаваться напрямую.

Чего хочу я. От того, что уже сделано остался всего один большой шаг до полноценного веба. Это динамический контент и серверные скрипты. Попытка реализовать на распределённой сети серверные скрипты может показаться по меньшей мере амбициозной, но в принципе ничего невозможного тут нет. Давайте посмотрим, чем обычно занимаются эти самые скрипты. Они берут запрос клиента, что-то читают в своей базе данных, что-то пишут и выдают результат. База данных реляционная. Читают и пишут, как правило, мало. Можно наложить ограничение, что все обращения к базе используют поиск только по индексированным колонкам. В таком случае, эти обращения сводятся к константному количеству обращений одному-единственному хэшу, а точнее ассоциативному массиву. (В дальнейшем, я буду везде вместо слов ассоциативный массив писать хэш, потому что так короче. Хотя, надо заметить, что как будет видно из дальнейшего, как раз хэш-то в качестве реализации ассоциативного массива в нужном нам случае никак не подходит.) Таким образом, в принципе, серверные скрипты можно перенести на клиента при условии возможности обращения к общей базе. Конечно, не всё так просто. Имеются следующие требования к реализации этой базы:

  • Вполне естественно разделение всей «пользовательской» (не относящейся к функционированию p2p-сети) части хэша на сайты. Например, все ключи такой базы могут начинаться с префикса "user:имя.сайта:".
  • Пары ключзначение должны лежать в сети не абы как, а должны в какой-то мере группироваться. Во-первых, это нужно для того, чтобы при запросах к «соседним» полям не приходилось каждый раз осуществлять полную процедуру поиска, проходящую по log(N) вершинам (где N — общее количество вершин в сети). Во-вторых, если сущности, ищеющие значение для функционирования сети логично распределять по всем узлам, то сущности, относящиеся к базе данных какого-нибудь частного сайта должны храниться только на узлах этот конкретный сайт поддерживающих. (При этом, естестенно, для того, чтобы запросить информацию с какого-нибудь сайта нужно согласиться его поддерживать.)
  • Требуется возможность эффективного обновления значений. Надо учитывать, что каждое значение хранится на нескольких узлах. Тем самым, они должны знать друг о друге. Можно потребовать, чтобы они организовывали подсеть, составляющую вершнинно-3-связный граф, но тогда в случае большого количества хранимых значений количество поддерживаемых соединений будет недопустимо велико.
  • Выбор значений должен осуществляться не только по условию ключ = v, но и в разумных пределах — по условиям последние k записей с ключём ≤ v и v1 ≤ ключ ≤ v2. Естественно, нельзя позволять выбирать все вообще ключи хэша.
  • Должны быть организованы права доступа. Это как раз реализовать не так сложно, например, подписывая все записи или какие-нибудь группы записей публичным ключём. Предлагается следующий мехнизм: помимо таких объектов, как машины и сайты, в p2p-сети есть пользователи. Каждый пользователь имеет открытый ключ, который общедоступен по всей сети. Каждый сайт имеет своего владельца. Все значения хэша, относящиеся к данному сайту разбиты на несколько групп (несколько интервалов в лексикографическом порядке). Для каждого интервала заданы права доступа: множество пользователей, имеющих к нему доступ на чтение, на добавление записи, на изменение. Множества задаются либо как «все пользователи», либо как набор публичных ключей тех, кто имеет доступ. Правила подписаны цифровой подписью владельца сайта.

Как несложно проверить (поля слишком узки, что полностью выписать обоснование :), в рамках данной технологии можно реализовать: любой сайт, состоящий из более-менее статичных страниц; wiki; blog (даже с френдованием, как в ЖЖ); базу данных типа IMDB или AniDB, форумы. Поисковую систему можно реализовать в виде сайта, но лучше встроить её в общий механизм сети. То же относится к передаче сообщений à la email между пользователями сети. Распределённая структура сети не исключает наличие выделенных серверов, поддерживающих тот или иной сайт. Просто они будут гарантированно хранить часть хэша, относящуюся к данному сайту и тем самым повышать его устойчивость.

Конкретная реализация самой сложной части системы — распределённого хэша мне пока не очевидна. В большинстве использующихся сейчас распределённых хешей то, какая машина будет хранить то или иное значение зависит от её идентификатора. В нашем случае это не подходит, так как тогда будет отсутствовать явная связь между сайтами и поддерживающими их системами. Я склоняюсь к мысли, что решением должен быть некоторый аналог бинарного дерева (как, собственно, и устроены реляционные БД). У меня есть кое-какие намётки по поводу того, как это должно выглядеть, но они настлько сыры, что не поддаются даже неформальному формулированию.

Ссылки. Я ещё пока не всё это прочёл. Собственно, я начал писать пост для того, чтобы их перечислить. :))

  1. статья про DHT в wiki
  2. Chimera and Tapestry
  3. статья в wiki про Kademlia
  4. описание Kademlia
  5. Bamboo DHT
  6. CAN
  7. статья в wiki про Chord
  8. chord
  9. статья про Bunshin
  10. Distributed K-ary System (DKS)
  11. Leopard: A Locality-Aware Peer-To-Peer System With No Hot Spot
  12. Pastry
  13. ещё несколько статей
  14. Farsite
  15. OceanStore и несколько ссылок
LinkReply

Comments:
[User Picture]From: octavarium
2006-01-29 06:24 pm (UTC)
неочень понятно.. зааачееем?
по сути, хранить в p2p сетях можно только редкоизменяющиеся сайты.
а такие сайты и так уже лежат в p2p.
подумаешь, доступ к ним организован чуть по другому.. да и называются такие штуки все-таки не сайтами, а книжками :) но смысл тот же.
(Reply) (Thread)
[User Picture]From: eterevsky
2006-01-29 06:27 pm (UTC)
Именно затем, чтобы снять этого ограничение. Ведь большие нагрузки, из-за которых стоит переходить на P2P бывают и из-за маленьких страниц. И проблемы с копирайтом тоже.
(Reply) (Parent) (Thread)
[User Picture]From: octavarium
2006-01-29 06:39 pm (UTC)
ничего не понял.

>снять этого ограничение

о чем речь?

>проблемы с копирайтом тоже

и все-таки.. о чееееем?
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2006-01-29 06:53 pm (UTC)
Ограничение — это по поводу того, что ты написал, что в P2P выкладывается только слабоизменяющийся контент. Моя цель как раз и состояла в том, чтобы привести способ создания в P2P динамического контента.

По поводу копирайта — статический сайт могут закрыть, а P2P — нет. :)
(Reply) (Parent) (Thread)
[User Picture]From: amarao_san
2006-01-29 07:55 pm (UTC)
ГлавныЙ, принципиальный минус любого p2p - это кошмарный оверхед и стартап. Пока все переконнектятся, съедается прорва трафика и времени. Да и обмен информацией о том, у кого что есть тоже к полезному трафику не относится.

И это принципиальная слабость любого p2p. Если когда-то tcp-протокол казался слишком "жрущим" трафик...

Всё-таки, имхо, у старых фидошных систем был определённый плюс. Например, тот же spb.files жил себе и живёт без всяких копирайтов, а скорость hydra RH1/z-modem IMHO никто ещё не превзошёл.
(Reply) (Thread)
[User Picture]From: eterevsky
2006-01-29 08:09 pm (UTC)
Скорость Гидры, Z-модема и KMP давно превзойдена путём постепенного вымирания модемов.

Зато в отношении скорости в моём варианте есть даже некоторые возможности для выигрыша — серверные скрипты работают на клиенте => страницы строятся прямо на нём же, а не передаются по сети. Плюс почти стопроцентное кэширование.
(Reply) (Parent) (Thread)
[User Picture]From: solo_oboroten
2006-01-30 12:43 am (UTC)

Что-то в этом есть...

Требования к поддерживающим сестемам: симетричное скоросное соединение с дешёвым трафиком.

Модель базы -- скорее деревовидная, чем релиционная.

Возможный вариант: нечто, напоменающее DNS по своим свойствам.
(Reply) (Thread)
[User Picture]From: eterevsky
2006-01-30 07:54 am (UTC)

Re: Что-то в этом есть...

На счёт скорости соединения: она не обязательно высокая, но в идеале должна учитываться при выборе «соседей». По поводу траффика: он должен быть меньше, чем на централизованных серверах за счёт распределения ресурсов по сети. Правда, там будет немаленький overhead.

А что такое «древовидная» база? Всё равно нам нужно будет уметь доставать элемент по ключу, а если это есть, то реляционная база строится без проблем.
(Reply) (Parent) (Thread)
[User Picture]From: solo_oboroten
2006-01-30 11:43 am (UTC)

Re: Что-то в этом есть...

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

См. на файловую систему (один частный случай), реестр win (другой) и структуру DNS (третий). Её приммущества -- простота организации ключей, простота организации хранения и маштабирования (т. к. легко и однозначно бётся по поддеревьям). Недостатки: массовые операции выполнять несколько сложнее.

Правдо, тебе скорее всего многомерное дерево потребуется (незнаю, как назвать правельно: имею в виду, когда 1 лист по нескольким ветьвям доступен).
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2006-01-30 12:12 pm (UTC)

Re: Что-то в этом есть...

>На серверах трафик не критичен
Это только в России так. Почему-то.

Древовидная база менее гибка, чем реляционная. Конечно, её можно реализовывать «буквально», то есть каждая машина поддерживает некоторую вершину, но это делает машины неравноправными и препятствует равномерному распределению траффика. А если структура реализации базы не совпадает с самой структурой дерева, то это фактически сводится к той же реализации распределённого хэша.
(Reply) (Parent) (Thread)
[User Picture]From: solo_oboroten
2006-01-30 01:22 pm (UTC)

Re: Что-то в этом есть...

>>На серверах трафик не критичен
>Это только в России так. Почему-то.

Неуверен: сторана потребляющая трафик -- платит везде (на сколько я знаю). Генераторам -- иногда платит провайдер.

От этого спасает делегирование и кешерование. Как это происходит в DNS:

1. Есть главный сервер зоны. Самая свежая и актуальная информация -- на нём

2. Есть вторичные сервера зоны. Они тоже считаются авторитетными и переодически проверяют (запрашивая главный) -- устарела ли их информация (в некоторых реализациях -- главный их оповещает о изменениях)

3. Все остальные -- кешеруют проходящие запросы и ответы на них.

По факту, наиболее нагруженные сейчас -- корневые сервера (точка обращения если нечего вообще неизвестно) и сервера некоторых зон (com, например).

Описанное тобой, с данной схемой согласуется очень не плохо, хотя тонкие маменты -- разумеется есть.

PS: Не "каждая машина поддерживает некоторую вершину", а "каждую вершину поддерживает несколько машин" + "каждая машина поддерживает множество вершин".
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2006-01-30 02:11 pm (UTC)

Re: Что-то в этом есть...

Основная идея рассматриваемого варианта p2p — бессерверная работа и относительное равноправие всех участвующих систем. А у тебя система ранжированная.
(Reply) (Parent) (Thread)
[User Picture]From: solo_oboroten
2006-01-30 02:28 pm (UTC)

Re: Что-то в этом есть...

А что мешает избавится от корневых серверов? В DNS -- это сложно: там централизация важна. А в том что ты хочеш -- вполне можно.

То что я описал -- это случай с простейшей от подмн (полное описанее зон отдаётся известным серверам), так как в P2P такая задача не стоит (целосность прверяется другими методами) -- описание зоны (контент, или как-его-там) -- можно отдавать любому.

+ Невижу причин, почему любой из клиентов неможет выступать в качестве сервера.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2006-01-30 02:35 pm (UTC)

Re: Что-то в этом есть...

Тогда я не вполне понял твоё предложение.
(Reply) (Parent) (Thread)
[User Picture]From: solo_oboroten
2006-01-30 02:53 pm (UTC)

Re: Что-то в этом есть...

Сейчас каждый DNS сервер имеет список IP корневых серверов, для обеспечения однозначности преобразования (поиск незвестного -- от корня). Если в качестве корневых использовать другие сервера -- можно систему альтернативных имен, ортоганальную существующей (и слышал -- такие есть).

В P2P сетях аждый клиент таскает с собой некий список адресов, куда он обращается за поиском контента (за адресами других серверов/списками доступных файлов).

Не находиш, что похоже?
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2006-01-30 04:06 pm (UTC)

Re: Что-то в этом есть...

Не нахожу. В случае P2P ситуация абсолютно симметрична клиент A обращается к клиенту B для того, чтобы получить какие-то одни данные, а клиент B — к клиенту A, чтобы получить другие. В случае DNS обращение всегда идёт «вверх» по иерархии.
(Reply) (Parent) (Thread)
[User Picture]From: solo_oboroten
2006-01-30 05:09 pm (UTC)

Re: Что-то в этом есть...

Откуда клиент A узнаёт о существовании B (и на оборот)?

Чем ситуация отличается от запроса сервером ns.xxx.yyy адреса ccc.aaa.bbb у сервера ns.aaa.bbb, отвечающего за зону aaa.bbb. И встречного запроса сервером ns.aaa.bbb имени zzz.xxx.yyy у ns.xxx.yyy?

Да, если ns.xxx.yyy и ns.aaa.bbb друг о друге незнают -- они будут искать друг друга через третьи сервера, но если знают -- обратятся напрямую. Но в P2P сетях P2P клиенты тоже находят другдруга спомощью посредников...

PS: В P2P клиентов _несуществует_! Они все сервера (т. к. кажый из них может запрашивать и обрабатывать запросы).
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2006-01-30 08:27 pm (UTC)

Re: Что-то в этом есть...

Ладно, наш спор перешёл в разряд терминологического.
(Reply) (Parent) (Thread)