Kademlia

Поделись знанием:
Перейти к: навигация, поиск

Kademlia — это реализация распределённой хеш-таблицы для одноранговых компьютерных сетей, разработанная Петром Маймунковым и Давидом Мазьером (David Mazières). Протокол Kademlia определяет структуру сети, регулирующей связь между узлами, и способ обмена информацией в ней. Узлы сети, работающей по протоколу Kademlia, общаются между собой по протоколу транспортного уровня UDP. Узлы Kademlia хранят данные посредством распределённых хеш-таблиц (DHT). В итоге над существующей LAN/WAN (как интернет) создаётся новая виртуальная или оверлейная сеть, в которой каждый узел обозначается специальным номером («Node ID»). Этот номер также выполняет и другие функции.

Узел, который хочет присоединиться к сети, обязан пройти «загрузочную» процедуру (bootstrap process). В этот момент узел должен знать адрес другого узла (полученный от пользователя или взятый из списка), который уже входит в оверлейную сеть. Если подключаемый узел ещё не входил в эту сеть, то происходит расчет случайного значения ID, которое ещё не принадлежит никакому узлу. ID используется до момента выхода из сети.

Алгоритм Kademlia базируется на расчете «расстояния» между узлами путём применения операции исключающее ИЛИ к ID этих узлов.

Эта «дистанция» не имеет никакого отношения к географическому положению. К примеру, узлы из Германии и Австралии могут быть «соседними» в оверлейной сети.

Информация в Kademlia хранится в так называемых «значениях» (values). Каждое «значение» привязано к «ключу» (key).

При поиске соответствующего ключу значения алгоритм исследует сеть в несколько шагов. Каждый шаг приближает к искомому узлу до полного нахождения «значения» либо до отсутствия таких узлов. Количество контактируемых узлов зависит от размера сети логарифмически: при увеличении количества участников (number of participants) вдвое количество запросов увеличится всего на один.





Использование в файлообменных сетях

Задача хранения индексов файлов в сети Kad раскладывается на всех участников сети. Если узел хочет «расшарить» файл, он обрабатывает его, получая хэш, который идентифицирует этот файл в сети. Затем узел ищет несколько узлов, ID которых близки к хэшу (размеры хешей и идентификаторов узлов должны совпадать), при этом на эти узлы отдается информация об адресе этого узла. Клиент при поиске ищет ID узла, который имеет наименьшую дистанцию к хэшу файла и извлекает из него адреса узлов, которые имеют этот файл. Контакты, хранимые в сети, всегда находятся в постоянном изменении, так как узлы постоянно подключаются и отключаются. Для отказоустойчивости эти контакты реплицируются по нескольким узлам.

Поиск осуществляется по ключевым словам. Имя файла разбивается на составные части. Каждое ключевое слово хэшируется и сохраняется в сети аналогично файловому хэшу, вместе с соответствующим файлом и хэшем файла. Ищущий узел выбирает одно из ключевых слов, соединяется с узлом, чей ID самый близкий к хэшу ключа и запрашивает у него список файлов для этого ключа. Так как каждый файл в списке имеет свой хэш, имя файла легко вычисляется.

Клиенты файлообменных сетей, использующие различные вариации протокола Kademlia

См. также

Напишите отзыв о статье "Kademlia"

Примечания

Литература

  • Klaus Wehrle, Mesut Günes, James Gross. Modeling and Tools for Network Simulation. — Springer Science & Business Media, 2010. — P. 454–. — ISBN 978-3-642-12331-3.
  • Cai, X. S., Devroye, L. A Probabilistic Analysis of Kademlia Networks (англ.). — 2013. — Vol. 8283. — P. 711. — DOI:10.1007/978-3-642-45030-3_66.
  • Juenemann, Konrad. Confidential Data-Outsourcing and Self-Optimizing P2P-Networks: Coping with the Challenges of Multi-Party Systems. — KIT Scientific Publishing, 2015. — P. 81–. — ISBN 978-3-7315-0328-6.
  • Maymounkov, Petar and Mazières, David (2002). "[dl.acm.org/citation.cfm?id=646334.687801 Kademlia: A Peer-to-Peer Information System Based on the XOR Metric]" in IPTPS '01. Revised Papers from the First International Workshop on Peer-to-Peer Systems: 53—65, Springer-Verlag. Проверено 2013-12-06. 


Отрывок, характеризующий Kademlia

Пьер поспешно подошел к ней. Он думал, что она ему, как всегда, подаст руку; но она, близко подойдя к нему, остановилась, тяжело дыша и безжизненно опустив руки, совершенно в той же позе, в которой она выходила на середину залы, чтоб петь, но совсем с другим выражением.
– Петр Кирилыч, – начала она быстро говорить – князь Болконский был вам друг, он и есть вам друг, – поправилась она (ей казалось, что всё только было, и что теперь всё другое). – Он говорил мне тогда, чтобы обратиться к вам…
Пьер молча сопел носом, глядя на нее. Он до сих пор в душе своей упрекал и старался презирать ее; но теперь ему сделалось так жалко ее, что в душе его не было места упреку.
– Он теперь здесь, скажите ему… чтобы он прост… простил меня. – Она остановилась и еще чаще стала дышать, но не плакала.
– Да… я скажу ему, – говорил Пьер, но… – Он не знал, что сказать.
Наташа видимо испугалась той мысли, которая могла притти Пьеру.
– Нет, я знаю, что всё кончено, – сказала она поспешно. – Нет, это не может быть никогда. Меня мучает только зло, которое я ему сделала. Скажите только ему, что я прошу его простить, простить, простить меня за всё… – Она затряслась всем телом и села на стул.
Еще никогда не испытанное чувство жалости переполнило душу Пьера.
– Я скажу ему, я всё еще раз скажу ему, – сказал Пьер; – но… я бы желал знать одно…
«Что знать?» спросил взгляд Наташи.
– Я бы желал знать, любили ли вы… – Пьер не знал как назвать Анатоля и покраснел при мысли о нем, – любили ли вы этого дурного человека?
– Не называйте его дурным, – сказала Наташа. – Но я ничего – ничего не знаю… – Она опять заплакала.
И еще больше чувство жалости, нежности и любви охватило Пьера. Он слышал как под очками его текли слезы и надеялся, что их не заметят.
– Не будем больше говорить, мой друг, – сказал Пьер.
Так странно вдруг для Наташи показался этот его кроткий, нежный, задушевный голос.
– Не будем говорить, мой друг, я всё скажу ему; но об одном прошу вас – считайте меня своим другом, и ежели вам нужна помощь, совет, просто нужно будет излить свою душу кому нибудь – не теперь, а когда у вас ясно будет в душе – вспомните обо мне. – Он взял и поцеловал ее руку. – Я счастлив буду, ежели в состоянии буду… – Пьер смутился.
– Не говорите со мной так: я не стою этого! – вскрикнула Наташа и хотела уйти из комнаты, но Пьер удержал ее за руку. Он знал, что ему нужно что то еще сказать ей. Но когда он сказал это, он удивился сам своим словам.
– Перестаньте, перестаньте, вся жизнь впереди для вас, – сказал он ей.
– Для меня? Нет! Для меня всё пропало, – сказала она со стыдом и самоунижением.
– Все пропало? – повторил он. – Ежели бы я был не я, а красивейший, умнейший и лучший человек в мире, и был бы свободен, я бы сию минуту на коленях просил руки и любви вашей.
Наташа в первый раз после многих дней заплакала слезами благодарности и умиления и взглянув на Пьера вышла из комнаты.
Пьер тоже вслед за нею почти выбежал в переднюю, удерживая слезы умиления и счастья, давившие его горло, не попадая в рукава надел шубу и сел в сани.
– Теперь куда прикажете? – спросил кучер.
«Куда? спросил себя Пьер. Куда же можно ехать теперь? Неужели в клуб или гости?» Все люди казались так жалки, так бедны в сравнении с тем чувством умиления и любви, которое он испытывал; в сравнении с тем размягченным, благодарным взглядом, которым она последний раз из за слез взглянула на него.
– Домой, – сказал Пьер, несмотря на десять градусов мороза распахивая медвежью шубу на своей широкой, радостно дышавшей груди.
Было морозно и ясно. Над грязными, полутемными улицами, над черными крышами стояло темное, звездное небо. Пьер, только глядя на небо, не чувствовал оскорбительной низости всего земного в сравнении с высотою, на которой находилась его душа. При въезде на Арбатскую площадь, огромное пространство звездного темного неба открылось глазам Пьера. Почти в середине этого неба над Пречистенским бульваром, окруженная, обсыпанная со всех сторон звездами, но отличаясь от всех близостью к земле, белым светом, и длинным, поднятым кверху хвостом, стояла огромная яркая комета 1812 го года, та самая комета, которая предвещала, как говорили, всякие ужасы и конец света. Но в Пьере светлая звезда эта с длинным лучистым хвостом не возбуждала никакого страшного чувства. Напротив Пьер радостно, мокрыми от слез глазами, смотрел на эту светлую звезду, которая, как будто, с невыразимой быстротой пролетев неизмеримые пространства по параболической линии, вдруг, как вонзившаяся стрела в землю, влепилась тут в одно избранное ею место, на черном небе, и остановилась, энергично подняв кверху хвост, светясь и играя своим белым светом между бесчисленными другими, мерцающими звездами. Пьеру казалось, что эта звезда вполне отвечала тому, что было в его расцветшей к новой жизни, размягченной и ободренной душе.