P2P и жизнь

часть 2. P2P сеть Kademlia.

И так, пришло время рассказать про эту замечательную п2п-компазицию :D
Сеть Kademlia (она же Kad, Overnet и возможно еще что-то) представляет собой в каком-то смысле идеальную p2p сеть, по ходу дела ты поймешь почему, и возможно даже протащишься от ее красоты :DD

---- топология

Схематично топология сети представлена на рисунке:

топология сети Kademlia

Как ясно из картинки - в сети полностью отсутствует какая-либо централизация либо вобще топология :D Попросту каждый из узлов в сети связан произвольным образом с неким количеством других узлов.
Кстати, на картинке присутсвует условность в том, что каждый узел на самом деле связан не с несколькими узлами а примерно с парой тысяч. Правда связь не подразумевает наличие постоянного соединения (TCP), а просто означает что в списке контактов у данного узла есть несколько тысяч адресов других узлов.

Помимо (само собой) IP-адреса и порта, каждый узел обладает уникальным ID. ID должен быть рандомным, но от запуска к запуску узла не меняться (это не принципиально, но достаточно важно). Длина ID в битах может быть порядка 32-256.

[Хеш-таблица]

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

Пример хеш-таблицы

Поле DATA - собственно даннные которые у нас хранятся. Они могут быть любой длины. Поле HASH - соответственно хеш (например md5) от данных, т.е своеобразный идентификатор данных, фиксированной длины. Это может быть например MD5 хеш, или CRC32 контрольная сумма от данных.
Данная конструкция удобна при хранении разного рода данных, которые легко извлекаются (т.е сопоставляются) из таблицы по известному хешу.

[-------------]

Так вот - сеть Kad представляет собой распределенную хеш-таблицу - Distributed Hash Table (DHT). Прикол в том, что у каждого узла хранится кусок одной большой таблицы (причем один и тот же кусок обычно хранится у нескольких узлов для большей устойчивости сети к отключениям), но об этом побазарим немного позже, а пока абстрагируемся от этого.

Каждый узел может производить следующие действия:
1) Добавлять в сеть записи (пары хеш:данные)
2) По известному хешу искать в сети соответстующие ему данные.

Пример возможных операций в сети Kad

На картинках показано, как данные действия выглядят со стороны юзера, без углубления в тонкости протокола и механику сети (не беспокойся, етим мы еще займемся :-D).
Разберем компазицию подробнее. На картинках присуствует: юзер (ака юзерская прога), злая КАД библиотека.so.666, посредством которой и осуществляется процесс, а так же схематичное изображение сети Кад.

В случае сохранения данных, юзер вызывает (1) функцию библиотеки public() с соответствующими параметрами. Далее начинается работа библиотеки - она совершает довольно много телодвижений (2) по отношению к сети (важно понять, что операция сохранения не выглядит как отправка одного сообщения в сеть и получения ответа с результатом). После того как процесс будет завершен, юзерская прога получает уведомление (3) от библиотеки.

Поиск данных выглядит аналогично. юзерская прога вызывает (1) функцию поиска (у нас это как видишь find()) с одним параметром - хешем, данные к которому надо найти. Далее библиотека работает с сетью (2) и вытаскивает оттуда (если они там есть) нужные нам данные, которые затем возвращаются (3) юзеру.

В этих двух действиях и заложена суть сети. Пример работы сети Кад для файлообмена:
К каждому файлу на каждом узле считается хеш. Затем каждый узел производит сохранение полученных пар хеш:данные в сети (на самом деле все немного сложнее, т.к гонять многомегабайтные файлы в качестве данных по сети никто не хочет, но это не принципиально). После этого, если какому-либо узлу понадобятся некий файл, он легко находит его в сети (зная хеш).

Так работа сети выглядит внешне. Внутри все немного сложнее, но мы умеем объяснять, и если ты не клинический долбоёб, то все поймешь, будь спокоен :DD.

---- устройство сети Кад.

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

Первая особенность

Это понятие некоего расстояния между ID двух узлов, или между ID узла и неким хешем (помнишь что длина в битах у ID и хеша одинакова ?), и это расстояние, как ни странно, вовсе не разность чисел :D. Расстояние чисто условно, так что не заморачивайся сильно. Считается оно так:

Где xor - соответствующая побитовая операция.

Таким образом, к примеру расстояние от узла до него самого равно 0 (можешь проверить в калькуляторе виндовс, поксорив любое число само с собой). а расстояние между узлами с ID 01011011 и 10110101 равно 11101110. на этом вся математика заканчивается, что очень хорошо :D И заклинаю, посылай нахуй тех кто будет рекомендовать читать официальный пдф по этой теме, он написан специально так, чтобы заебать мозг и ты ничего не понял ;-D

Вторая особенность

Это возможность поиска в сети некоего количества (например N) узлов, ID которых наиболее близки к любому заданному. Это основная операция сети. В целом, процесс выглядит так:

Исходный узел (который хочет найти), из своего списка узлов извлекает N ближайших к искомому хешу. Затем отсылает каждому из них специальный запрос, содержащий хеш, на который узел должен ответить списком из N узлов из своего контакт-листа, которые максимально близки к полученному в запросе хешу. Затем исходный узел, собрав все ответы, сортирует полученные контакты, и выбирает из них N ближайших. Затем им отправляются аналогичные запросы - процесс повторяется. И повторяется до тех пор, пока будут возвращаться адреса узлов, чьи ID ближе к искомому хешу чем уже имеющиеся. Таким образом процесс итеративный, и на каждом шаге ты все ближе приближаешься к искомому :D Заметь, что в конце ты получаешь именно ближайшие узлы, а вовсе не адрес узла, чей ID совпадает с искомым. Это вообще фактически недостижимое совпадение, когда в сети находится узел, чей ID совпадает с неким хешем от данных. Эта операция поиска ближайших узлов используется для всех операций более высокого уровня - сохранения и поиска данных.


Таким образом, операция сохранения высшего уровня выглядит так:
1) Узел находит N узлов, максимально близких к публикуемому хешу.
2) Узел отсылает всем этим узлам запрос на сохранение пары хеш:данные.

Может показаться, что операция поиска сделана аналогично - ищется N узлов, наиболее близких к хешу, и затем у всех них запрашиваются данные с искомым хешем. Но на деле все по-другому. Поиск данных происходит непосредственно в процессе поиска ближайших узлов. А конкретно - ищется узел, с хешем равным хешу искомых данных. И в процессе, если у запрашиваемого узла оказались в наличии соответствующие данные - он возвращает их, и собственно на этом поиск прекращается. Если данных нет - то он как обычно возвращает максимально близкие узлы из своего списка и поиск продолжается.

Конец хуйни

Собственно на этом креатив о теоретической стороне дела заканчивается. В следующей части мы более подробно расскажем о практической стороне изучения сети, а так же покажем как на практике реализовать сеть Kad, с конкретным примером реализации на языке C.

---- сцылка

официальный pdf автора сети (осторожно, ебут мозг):

http://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf

для захуяривания каментоф надо зайти в систему.

---

ГОСПЛАН!		100%	[1 голос]
Дико		0%	[ни одного]
Зачет		0%	[ни одного]
Так се..		0%	[ни одного]
КГ/АМ		0%	[ни одного]