Диссертация (1137145), страница 3
Текст из файла (страница 3)
Ripeanu, 2001], [E. Adar, B. A. Huberman, 2000].Второй раздел «Алгоритмы распределенных систем хранения свозможностью поиска ближайшего соседа в Евклидовых пространствах»содержит описание алгоритмов позволяющих строить P2P системыимеющие более сильные поисковые возможности в сравнении салгоритмами первого раздела. Вполне закономерно, что исторически этиалгоритмы появились позднее. В отличии поиска на точное совпадение,реализуемого в DHT, рассматриваемые в главе алгоритмы позволяютпроизводить поиск ближайшего соседа с логарифмической сложностью наплоскости (VoroNet 1.2.3) или в m-мерном вектором пространстве севклидовой метрикой (RayNet 1.2.4). В качестве алгоритма поиска во всехслучаях используется алгоритм с «жадной стратегией» GreedyWalk (2.1).1.1Алгоритмыраспределенныхсистемвозможностью поиска на точное совпадение13храненияс1.1.1 Концепция распределенной хэш-таблицыРаспределенные хэш-таблицы (англ.
Distribute Hash Table сокр. DHT) –это класс децентрализованных систем предназначенных для хранения ипоиска информации на распределенном оборудовании. ФункциональностьDHT предполагает три базовые операции: добавление информации в видеупорядоченной пары <ключ, значение>, извлечение <значения> позаданному ключу и удаления пары <ключ, значение> по заданному ключу.Главной особенностью DHT - является то, что ответственность за хранениеи поиск информации распределена среди множества узлов, объединенныхв равноправную (одноранговую) сеть посредством логических ссылок (см.рисунок 1).Каждый участвующий в сети узел способен инициировать поискинформации во всей сети на основании заданного ключа. При этомкаждый узел ответственен за хранение множества пар <ключ, значение> изопределенного диапазона ключей.
Для обеспечения целостности сети иреализации функциональности поиска, в каждом узле хранится таблицамаршрутизации (routing table или по-другому finger table), представленнаявиде списка ссылок на другие узлы сети.Поиск в сети узла ответственного за диапазон ключей соответствующегозапрашиваемому ключу осуществляется посредством последовательнойпересылки поискового сообщения от одного узла к другому на основаниитаблицы маршрутизации. Алгоритм пересылки сообщений, структуратаблицы маршрутизации и алгоритм её формирование определяетсяконкретным протоколом реализующим концепцию DHT.В отдельных реализациях DHT размер таблицы маршрутизации исреднее число узлов, которое проходит поисковое сообщение пред тем какдостигнуть адресата, пропорционален логарифму от общего числа узловучаствующих в сети.
В этом случае, класс таких систем принято считатьмасштабируемыми.14Рис. 1. Схематичное изображение концепции распределённой хэш-таблицы. Хэшфункция используется для того, чтобы обеспечить равномерное распределениепоисковых ключеDHTиспользуетсявкачествеинфраструктурыдляпостроенияраспределенных файловых систем, кооперативного WEB-кэша, системраспространения контента, сервиса доменных имен, систем мгновенныхсообщений и д.р.1.1.2 Протокол ChordПротокол Chord является одной из первых наиболее простых иинтуитивно понятных реализацией концепции DHT.
Chord позволяетосуществлять поиск и хранение информации в виде <ключ, значение>среди множества узлов объединенных общей физической сетью [Stoica,2001]. Протокол был создан в рамках MIT и впервые был описан в 2001году авторами Ion Stoica, Robert Morris, David Karger, Frans Kaashoek и HariBalakrishnan.Как и любой другой протокол реализующий концепцию DHT, протоколChord специфицирует алгоритм маршрутизации поисковых сообщений, атак же алгоритм формирования и поддержания таблицы маршрутизации вактуальном виде на каждом узле.15В качестве ключей однозначно ассоциируемых с каждой элементарнойединицей информации хранимой в системе, а так же для адресации узлов, вChord используются m-битные идентификаторы. Узлам идентификаторыназначаются, вычисляя хэш-функцию SHA-1 (FIPS 180-1, 1995) от их IPадреса.
Таким образом, ключи и идентификаторы узлов могут приниматьзначения от 0 до 2! . Для удобства их мысленно располагают на кольцепространства ключей в порядке обхода по часовой стрелке (см. рисунок 2).Посколькувтакойсистемемаксимальноевозможноечислоидентификаторов 2! , соответственно и максимальное возможное числодоступных узлов так же равно 2! .Узел p называют (), если он является первым доступнымузлом, чей идентификатор встретится первым при движении по часовойстрелке от ключа k на кольце пространства ключей. При добавлении ключk размещается на узел = () .
Таким образом, узел cидентификатором ответственен за хранение информации связанной сключами из интервала (’, ], где ’ – идентификатор предшествующегоузла (первый доступный узел встретившейся при движении противчасовой стрелки от ключа − 1 на кольце пространства ключей).Например, на рис. 1.1.2 изображено пространство 8 ключей (m = 3).Доступными узлами являются узлы с идентификаторами 0, 1 и 3.
Узел сидентификатором 3, ответственен за хранение информации связанной сключами из диапазона [2,3] т.к. он является successor для ключей из этогодиапазона.Соответственно, узел с идентификатором 0 ответственен задиапазон [4,8] . Размещение ключей подобным образом аналогично,размещению ключа на узле, чей идентификатор является ближайшимпо метрике − 2! среди всех узлов присутствующих в данныймомент в системе.16Рис.
2. Расположение узлов и ключей на кольце пространстве идентификаторов Chord.Серым цветом выделены доступные узлы.1.1.2.1 Таблица маршрутизацииДля того чтобы поддерживать целостность сети, каждый узел хранитинформацию об узлахпредшествующимначей идентификатор является следующим икольцепространстваключейотносительнособственного идентификатора.Чтобы поиск информации в сети был эффективным, каждый узел храниттаблицу маршрутизации представленную списком из m ссылок на другиеузлы (finger table), формируемый следующим образом. Пусть значениеидентификатора данного узла равно p, тогда ссылка с номером i указываетна узел( + 2! 2! ) .
Такая организация таблицмаршрутизации позволяет, каждый раз пересылая поисковое сообщение,сокращать расстояние до искомого узла минимум в два раза, что позволяетсообщению достигать узла адресата за логарифмическое число шагов.Пример таблицы маршрутизации на узле «N8» для = 6 изображенрисунке 3.17(a)(б)Рис. 3. (а) Пример таблицы маршрутизации узла «N8». (б) Путь поискового сообщениядля ключа 54 от узла «N8».1.1.2.2 Алгоритм поискаВ качестве алгоритма поиска Chord использует жадный алгоритм. Нарисунке 4 приводится псевдокод алгоритма поиска узла ответственного захранение ключа , т.е. узла (). Узел , получивший поисковоесообщение find_successor(), либо обнаруживает, что следующий узелявляется искомым и возвращает его, либо пересылает сообщение узлу чей,идентификатор находится ближе всего к по метрики − 2! .Пример пути, пройденного поисковым сообщением _(54)от узла «N8», приведен на рис. 3(б).
Используя таблицу маршрутизацииизображенной на рисунок 3(а), узел «N8» пересылает сообщениеближайшему к ключу 54 известному узлу.01 //asknodentofindsuccessorofx02 n.find_successor(x)03 if x ∈ (n, n. successor])04return n. successor;05 else06y = closest_preceding_node(x);07return y. find_successor(x);Рис. 4 Алгоритм поиска узла ответственного за хранения ключа 1801 //nodensearchinthelocaltableforhighestpredecessorofx02 n.closest_preceding_node(x)03 for i = m downto 104if finger[i] ∈ (n, x))05return finger i ;06 return n;Рис. 5.
Алгоритм поиска в локальной таблице маршрутизации ближайшегопредшествующего узла к .1.1.3 Протокол KademliaKademlia – peer-to-peer протокол реализующий концепцию DHT.Протокол был впервые описан Петаром Маймаунковым и Дэвидом Мазьером в [Maymounkov & Mazieres, 2002] Он описывает структуру peerto-peer сети и алгоритм обмена информацией между узлами участвующимив ней. Узлы Kademlia для коммуникации используют UDP протокол.
Вкачестве ключей и адресации узлов в Kademlia используются 160-битныедвоичные идентификаторы. Для узлов идентификаторы генерируютсяслучайным образом, и при этом обеспечивается их уникальность.Главным отличием Kademlia является то, что в качестве меры близостидвух идентификаторов и используется XOR-метрика , = ⨁ ,котораяудовлетворяетвсемтрёмаксиомамметрики:тождества,симметрии и аксиоме треугольника (неравенство треугольника). Важноотметить,чторасстояниемявляетсярезультатоперацииXOR,интерпретируемый, как число, а не количество различающихся бит (такойкритерийтожеможетпорождатьметрикувпространствеключей/идентификаторов). Т.е.
при длине ключа 4 бита: 2,5 = 0010XOR 0101 = 0111 = 7.Аналогично метрике Chord, XOR метрика – однозначная. Для любойданной точки и расстояния ∆ > 0, существует ровно одна точка такая,что , = ∆. Отличие XOR-метрики от метрики, используемой в Chordв том, что она симметрична, т.е. , = , для любых и .19Длянаглядногопредставленияпространстваидентификаторовиспользуется двоичное дерево. В нём каждому идентификатору ставится всоответствие лист, соответствующий кратчайшему уникальному префиксу.Например, на рисунке 6 на двоичном дереве изображена позиция узла, чейидентификатор имеет кратчайший уникальный префикс 0011.Каждый узел ответственен за хранение информации связанной сключами, для каждого из которых идентификатор данного узла будетодним из k-ближайших среди всего множества узлов, присутствующих вданный момент в системе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
