Стиль этой статьи неэнциклопедичен или нарушает нормы русского языка. |
DHT (англ. distributed hash table — «распределённая хеш-таблица») — это класс децентрализованных распределённых систем поисковой службы, работающей подобно хеш-таблице. Как структура данных, хеш-таблица может представлять собой ассоциативный массив, содержащий пары (ключ-значение). Также, с термином DHT связан ряд принципов и алгоритмов, позволяющих записывать данные, распределяя информацию среди некоторого набора узлов-хранителей, и восстанавливать их путём распределённого поиска по ключу. Особенностью распределённой таблицы является возможность распределить информацию среди некоторого набора узлов-хранителей таким образом, что каждый участвующий узел смог бы найти значение, ассоциированное с данным ключом. Ответственность за поддержание связи между именем и значением распределяется между узлами, в силу чего изменение набора участников является причиной минимального количества разрывов. Это позволяет легко масштабировать DHT, а также постоянно отслеживать добавление и удаление узлов и ошибки в их работе.
DHT — это инфраструктура, которая может быть использована для построения многих сложных служб, таких как распределённые файловые системы, пиринговое распространение файлов и сети доставки содержимого, кооперативный web-кэш, многоадресное вещание (multicast), anycast, служба доменных имен и система мгновенных сообщений. Основные распределённые сети, которые используют DHT: сеть I2P, BitTorrent, eDonkey network (Kad Network)[источник не указан 1574 дня], YaCy, Tox и Coral Content Distribution Network. Существует возможность создания поисковых машин по сети DHT.
Исследования в области DHT изначально были мотивированы в частности пиринговыми системами, такими, как I2P, Napster, Gnutella, Freenet, которые использовали распределённые в интернете ресурсы для создания одного единственного приложения. В частности они использовали широкополосный интернет и пространство на жёстких дисках для предоставления сервиса распространения файлов.
Эти системы различаются тем, как они находили данные пиров:
DHT используют маршрутизацию на базе более структурированного ключа, чтобы достигнуть децентрализации I2P, Gnutella и Freenet, а также эффективности и гарантируемых результатов Napster. Один из недочётов в том, что, как Freenet, DHT поддерживает только поиск по точному совпадению, а не по ключевым словам, хотя эти возможности могут наслаиваться поверх DHT.
Первые четыре DHT — CAN, Chord, Pastry и Tapestry (англ. Tapestry) — были введены приблизительно в 2001 году. С тех пор эта область изысканий была достаточно активна. Вне научных кругов DHT-технологию приняли как компонент BitTorrent и Coral Content Distribution Network.
DHT характеризуется следующими свойствами:
Ключевая методика достижения цели заключается в том, что любой узел должен координировать работу только с несколькими узлами в системе — как правило, О(logn), где n — количество участников (смотри ниже) — так, чтобы только ограниченный объём работы был сделан для каждого изменения количества участников.
Некоторые DHT-проекты стремятся обеспечить защиту от вредоносных пользователей и позволять участникам оставаться анонимными, хотя это меньше распространено, чем во многих других P2P-системах (особенно при распространении файлов); см. Анонимные сети.
Наконец, DHT приходится иметь дело с более традиционными распределёнными системами, такими как распределение нагрузки, целостность данных и производительность (в частности, гарантируя, что операции, такие как маршрутизация и хранение данных или поиск, завершаются быстро).
Структура DHT может быть разбита на несколько основных компонентов. Она основывается на абстрактном пространстве ключей (keyspace), таком как набор 160-битных строк (количество бит может варьироваться). Схема разбиения пространства ключей распределяет принадлежность ключей среди участвующих узлов. Затем оверлейная сеть соединяет узлы, помогая найти владельца любого ключа в пространстве ключей.
Когда все компоненты на месте, типичное использование DHT для хранения и выдачи информации происходит следующим образом:
предположим, keyspace составляют 160-битные строки. Чтобы сохранить файл с данным именем и информацией в DHT, находится SHA1-хеш (160-битное значение) от имени файла, из которого формируется 160-битный ключ k (хеш), после чего формируется сообщение put(k, data), где data - содержание самого файла
и посылается любому участвующему узлу в DHT. Послание идёт от одного узла к другому через оверлейную сеть до тех пор, пока оно не достигнет единственного узла, ответственного за ключ k, в соответствии со схемой разбиения keyspace, где и будет храниться пара (k, data).
Любой другой клиент может получить содержание файла, сделав ключ (k), т. е. получив хеш имени файла, для того, чтобы найти данные, связанные с ключом, послав сообщение get(k)
. Сообщение снова пройдёт через оверлей к узлу, ответственному за ключ, который ответит, что нужные данные есть в наличии.
Компоненты разбиения пространства ключей и оверлейной сети описаны ниже с целью представления основных идей обычных для большинства DHT систем. Многие разработки отличаются в деталях.
Большинство DHT используют различные варианты консистентного хеширования для отображения ключей в узлы. В основе этого способа разбиения лежит функция , определяющая абстрактное понятие расстояния между ключами и , которое не имеет никакого отношения к географическому расстоянию или к сетевой задержке. Каждому узлу присваивается единичный ключ, называемый его идентификатором (ID). Узел с ID владеет всеми ключами , для которых — ближайший ID, вычисленный с помощью .
Пример. Chord DHT рассматривает ключи как точки на окружности, а — это расстояние, пройденное по часовой стрелке по окружности от ключа к . Таким образом круг пространства ключей разделён на смежные сегменты, чьи концы являются идентификаторами узлов. Если и смежные ID, то узел с ID содержит все ключи, которые находятся между и .
Консистентное хеширование имеет основное свойство: удаление или прибавление только одного набора ключей, принадлежащих узлам смежных ID, не влияет на другие узлы.
И DHT, и PEX фактически выполняют основную функцию BitTorrent-трекера — помогают участникам файлообмена узнать друг о друге. Они могут:
В публичных (открытых) трекерах, где каждый желающий может скачать торрент и участвовать в раздаче, DHT и PEX служат на благо всех участников.
Частным (закрытым) трекерам в первую очередь важно, чтобы в раздачах могли участвовать только зарегистрированные пользователи и чтобы они соблюдали определённые правила. При первом обращении клиента частный трекер имеет возможность не допустить его к раздаче, просто не сообщая ему адреса других клиентов-участников. Поэтому для закрытого трекера важно, чтобы клиенты не получали эти адреса через DHT/PEX.
DHT и PEX появились в клиентах Azureus и BitComet примерно летом 2005 года. Администраторы многих частных трекеров были недовольны такой новой функциональностью и поэтому стали запрещать на трекере эти новые версии клиентов.
Тогда разработчики клиентов предложили новый ключ внутри торрент-файла: private. Если он равен 1, то клиент обязан для этого торрента автоматически отключать DHT/PEX независимо от желания пользователя. Такой торрент называют Secure Torrent.
Практически все современные частные трекеры сами принудительно вставляют private:1 во все торренты, выкладываемые на трекере, а также запрещают несколько устаревших версий клиентов, поддерживающих DHT или PEX, но ещё не знающих про private key. Считается, что пользователи трекера просто не могут на раздачах использовать DHT/PEX, и проблемы нет. На самом же деле для того, чтобы не учитывался рейтинг, достаточно заменить свой passkey на любой другой. И даже не надо его воровать. Достаточно зарегистрировать ещё одну учётную запись, чтобы взять из неё passkey.
Этот раздел касается только закрытых трекеров, на которых private key в торренты принудительно не вставляется, и на некоторых раздачах (в зависимости от того, вставил ли раздающий сам в торрент private key) можно использовать DHT и PEX.
Часто встречается мнение, что включённый в клиенте DHT влияет на учёт статистики клиента трекером, например «раздавал через DHT, значит статистика шла мимо трекера». Это неверно.
Во-первых, DHT/PEX используется только для получения адресов пиров. Ни файлообмена, ни какого-либо учёта статистики по ним не ведётся. Клиент рапортует статистику скачанного и отданного только на трекер.
То есть «раздавал через DHT» фактически означает «о некоторых (или о всех) пирах получил информацию по DHT, и, вероятно, некоторые пиры тоже нашли меня через DHT».
Во-вторых, хотя клиенты обычно и знают, откуда ими получены адреса пиров, ни один клиент не разделяет трафик на «полученный/отданный DHT пирам» и «полученный/отданный пирам, полученным от трекера». Даже при желании это было бы клиенту сделать затруднительно — некоторые пиры могут быть получены и от трекера и через DHT или PEX, и часто клиент не знает, как его адрес получил пир, сам начинающий к нему соединение.
Клиент рапортует трекеру суммарные данные об объёмах им скачанного и отданного всем пирам, с которыми он общался, независимо от того, узнал клиент об отдельных пирах через трекер, DHT или PEX, или тот пир вообще начал соединение сам. То есть даже если из-за DHT/PEX на раздаче появятся «левые» пользователи (не обращающиеся к трекеру), клиент всё равно сообщит на трекер всё, что у них скачал и отдал.
Правильный учёт статистики зависит только от состояния трекера: работает трекер — статистика учитывается, не работает — не учитывается. Только в случае длительно неработающего трекера DHT/PEX может играть косвенную роль, не давая постепенно затухнуть файлообмену на такой «раздаче без учёта статистики».
Реализация распределённой сети в BitTorrent-клиентах основана на варианте DHT, называемом Kademlia. А вообще говоря, DHT (Distributed hash table) означает децентрализованную распределённую систему для объединения большого количества постоянно исчезающих и появляющихся узлов и эффективной передачи сообщений между ними. На основе структур DHT строят разные более сложные системы, такие как файлообмен P2P, кооперативное веб-кэширование, службы DNS и т. п.
DHT использует протокол UDP. Клиенты BitTorrent «слушают» тот же номер порта UDP, который они используют для входящих TCP-соединений. Если вы активно используете DHT, то открытие этого UDP-порта для доступа снаружи желательно, но не обязательно — DHT будет работать и так.
Каждый подключённый клиент является в сети DHT отдельным узлом. У него есть свой уникальный ID (идентификатор), случайно выбираемый из того же 160-битного пространства, что и infohash’и торрентов.
Каждый узел хранит таблицу маршрутизации, содержащую контактную информацию о многих «ближайших» к нему узлах, и о нескольких более далёких. «Близость» двух узлов вычисляется из «сходства» их ID, и не имеет никакого отношения к их географической близости.
Когда узел хочет найти пиров для раздачи, он сравнивает infohash этой раздачи с ID известных ему узлов, и затем посылает запрос тому узлу, чей ID наиболее похож на этот infohash. Тот узел возвращает ему адрес узла, чей ID ещё ближе к infohash торрента.
Тогда наш узел посылает запрос тому новому узлу, и получает от него адрес следующего узла, чей ID ещё более похож на infohash торрента.
Таким образом, запросы от клиентов, участвующих в раздаче торрента с определённым infohash, постепенно стекаются к узлам, чьи ID наиболее похожи на этот infohash. Эти узлы помнят предыдущие запросы, и всем следующим запрашивающим узлам вернут адреса предыдущих пиров с той же раздачи.
Эту статью следует викифицировать. |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .