Традиционная форма BitTorrent, которую мы только что описали, использует равноранговые передачи и централизованный трекер для каждого роя. Именно трекер в системе равноправных узлов трудно децентрализовать. Ключевая проблема в том, как выяснить, какие пиры имеют определенный искомый контент. Например, каждый пользователь может иметь один или несколько элементов данных, например песен, фотографий, программ, файлов и т. д., которые другие пользователи, возможно, хотели бы получить. Как другие пользователи находят их? Создать один перечень того, у кого что есть — просто, но централизовано. Наличие у каждой пира собственного перечня не помогает. Правда, они распространяются. Однако работа для поддержания актуальности перечней контента для пиров (так как контент перемещается по системе) необходима такая большая, что это безнадежная попытка.
Вопрос, за который взялось исследовательское сообщество, — возможно ли построить для P2P такие индексы, которые были бы полностью распределенными и имели бы хорошие характеристики. Мы имеем в виду три вещи. Во-первых, каждый узел хранит только небольшой объем информации о других узлах. Данное свойство означает, что поддержание актуальности индекса не потребует больших затрат. Во-вторых, каждый узел может быстро найти записи в индексе. В противном случае, это не очень полезный индекс. В-третьих, каждый узел может использовать индекс, даже когда другие узлы появляются и исчезают. Это свойство означает рост производительности индекса с ростом числа узлов.
Ответ на этот вопрос: «Да». Четыре различных решения были получены в 2001 году. Это Chord (Stoicа и др., 2001), CAN (Rаtnаsаmy и др., 2001), Pastry (Rowstron и Drusхel, 2001) и Tapestry (Zhаo и другие., 2004). Другие решения были разработаны немного позже, в том числе ^dem^, который используется на практике (Mаymounkov и Mаzieres, 2002). Эти решения известны как DHT (Distributed Hash Tables — распределенные хэш-таблицы), поскольку основная функциональность индекса — устанавливать соответствие между ключом и значением. Это похоже на хэш-таблицу, и решения, конечно, являются распределенными версиями.
DHT выполняют свою работу располагая регулярную структуру коммуникации между узлами, как мы увидим далее. Это поведение существенно отличается от традиционных Р2Р-сетей, которые используют все связи пиров. По этой причине DHT называются структурированными P2P-сетями. Традиционные протоколы P2P строят неструктурированные P2P-сети.
Опишем DHT Chord. В качестве сценария расмотрим, как заменить централизованный трекер, традиционно используемый в BitTorrent, на полностью распределенный трекер. Для решения этой задачи может использоваться Chord. В этом сценарии полный индекс — это список всех роев, к которым компьютер может присоединиться, чтобы загрузить контент. Ключ, используемый для просмотра индекса, — это описание контента торрентом. Он уникально идентифицирует рой, из которого может быть загружен контент, как хэш-функция от всех составляющих контент сегментов. Значение, сохраненное в индексе для каждого ключа, представляет собой список пиров, которые входят в рой. Эти пиры — компьютеры, с которыми можно контактировать, чтобы загрузить контент. Человек, желающий загрузить контент, например кинофильм, имеет только описание торрента. Вопрос, на который должна ответить DHT, — как при отсутствии центральной базы данных человек найдет, с каких именно пиров (из миллионов узлов BitTorrent) загрузить фильм?
Chord DHT состоит из n участвующих узлов. Это узлы, на которых запущен BitTorrent в нашем сценарии. Каждый узел имеет IP-адрес, по которому с ним можно связаться. Полный индекс распределен по узлам. Это подразумевает, что каждый узел хранит сегменты и части индекса для использования другими узлами. Ключевая роль Chord состоит в том, что он управляет этими индексами, используя идентификаторы в виртуальном пространстве, не IP-адреса узлов или имена контента, например фильма. Концепция идентификаторов состоит в том, что они являются просто ш-битными числами, которые упорядочены по возрастанию в кольцо. Чтобы превратить адрес узла в идентификатор, ему с помощью хэш-функции hash сопоставляется ш-разрядное двоичное число. Chord использует в качестве hash SHA-1. Это та же хэш-функция, которую мы упомянули, описывая BitTorrent. Мы рассмотрим ее, когда будем обсуждать криптографию в главе 8. Пока достаточно сказать, что это просто функция, которая отображает строку байт переменной длины в сильно случайное 160-разрядное двоичное число. Поэтому мы можем использовать ее, чтобы превратить любой IP-адрес в 160-разрядное число, называемое идентификатор узла (node identifier).
На рис. 7.43, а показан круг идентификаторов узлов для ш = 5. (Просто проигнорируйте пока что дуги в середине.) Некоторые из идентификаторов соответствуют узлам,
но большая часть — нет. В этом примере узлы с идентификаторами 1, 4, 7, 12, 15, 20, и 27 соответствуют фактическим узлам и заштрихованы; остальных не существует.
Теперь давайте определим функцию
как идентификатор первого ре
ально существующего узела, следующего за k по кругу, по часовой стрелке. Например,
Ключ также строится получением 160-разрядного числа — хэшированием имени контента с помощью hash (то есть SHA-1). В нашем сценарии имя контента — торрент. Поэтому, для того чтобы преобразовать torrent (файл описания торрента) в его ключ, мы вычисляем
Это вычисление — просто локальное к процедуре
hash.Чтобы запустить новый рой, узлу нужно вставить в индекс новую пару ключ-значение, состоящую из (torrent, my-IP-address).
Рис. 7.43. Набор из 32 идентификаторов узлов, упорядоченных по кругу (а). Заштрихованные соответствуют фактическим машинам. Дуги соответствуют указателям от узлов 1,4 и 12. Метки на дугах — индексы таблиц. Примеры таблиц указателей (б)
Чтобы сделать это, узел просит successor (hash(torrent)) сохранить my-IP-address. Таким образом, индекс случайным образом распространяется между узлами. Для устойчивости к ошибкам могут использоваться p различных хэш-функций для хранения данных наp узлах, но здесь мы не будем рассматривать тему устойчивости к ошибкам.
Через некоторое время после того, как DHT построена, другой узел хочет найти торрент, присоединиться к рою и скачать контент. Узел ищет torrent, сначала хэшируя его, чтобы получить key, а затем используя successor (key), чтобы найти IP-адрес узла, хранящего соответствующее значение. Значение — это список пиров в рое; узел может добавить свой IP-адрес к списку и контактировать с другими пирами, чтобы загрузить контент по протоколу BitTorrent.
Первый шаг прост, а второй — нет. Чтобы было возможно найти IP-адрес узла, соответствующего определенному ключу, каждому узлу необходимо поддерживать определенные административные структуры данных. Одна из них — IP-адрес его узла-преемника в круге идентификаторов узлов. Например, на рис. 7.43 7 — это преемник для узла 4, а 12 — преемник для узла 7.
Поиск может происходить следующим образом. Запрашивающий узел направляет своему преемнику пакет, содержащий IP-адрес и ключ, который он ищет. Пакет продвигается по кругу, пока не обнаруживает преемника к идентификатору искомого узла. Этот узел проверяет, есть ли у него информация, соответствующая ключу, и если это так, возвращает ее непосредственно к запросившему узлу, IP-адрес которого у него есть. Однако линейный поиск всех узлов в большой равноранговой системе очень неэффективен, так как среднее число узлов, требуемых при поиске, составляет n/2. Чтобы повысить скорость поиска, каждый узел поддерживает то, что в Chord называется таблица указателей (finger table). Таблица указателей имеет m записей, проиндексированных от 0 до m - 1, каждая указывающая на свой реальный узел. Каждая запись имеет два поля: start и IP-адрес преемника, как показано для трех узлов на рис. 7.43, б. Значениями полей для записи номер i в узле с идентификатором k являются:
