Содержание к диссертации
Введение
Глава 1. Обзор алгоритмов распределенных систем хранения 13
1.1 Алгоритмы распределенных систем хранения с возможностью поиска на точное совпадение 13
1.1.1 Концепция распределенной хэш-таблицы 14
1.1.2 Протокол Chord 15
1.1.3 Протокол Kademlia 19
1.1.4 Pastry 24
1.1.5 Применения 27
1.2 Алгоритмы распределенных систем хранения с возможностью поиска ближайшего соседа в векторных пространствах 32
1.2.1 Модель навигационного тесного мира Клайнберга 33
1.2.2 VoroNet 35
1.2.3 Ray Net 38
1.3 Выводы 41
Глава 2. MSW - распределённая структура данных ля поиска ближайшего соседа в метрических пространствах 44
2.1 Формулировка задачи поиска ближайшего соседа. Различные вариации 45
2.2 Общее описание предлагаемой структуры данных 47
2.3 Базовый алгоритм поиска ближайшего соседа 49
2.4 Серия поисков 52
2.5 Алгоритм поиска к-ближайших соседей K-NNSearch 53
2.6 Алгоритм добавления 55
2.7 Алгоритм добавления основанный на устранении локальных минимумов 57
2.8 Процедура улучшения поисковых свойств сети за счёт использования информации о запросах 61
2.9 Выводы 61
Глава 3. Исследование свойств предложенных алгоритмов 62
3.1 Наборы данных 63
3.2 Исследование навигационных свойств: распределение длины кратчайшего пути и распределение длины пути совершаемой жадным алгоритмом 64
3.3 Средняя длина пути жадного алгоритма в графе в зависимости от числа элементов в структуре 74
3.4 Распределение степеней вершин 76
3.5 Коэффициент кластеризации 77
3.6 Вычислительная сложность и точность алгоритма поиска 78
3.7 MSW - как структура данных для поиска ближайшего соседа. Сравнительный анализ с другими структурами данных для поиска ближайшего соседа 82
3.7.1 Сравниваемые методы 82
3.7.2 Эксперименты 86
3.7.3 Методология оценки 87
3.8 Улучшения навигационных свойств графа с помощью процедуры RepairByQuery 92
3.9 Выводы 93
Глава 4. Математическая модель оптимальных графов для распределённого поиска 95
4.1 Предпосылки разработки модели 96
4.2 Модель 97
4.3 Алгоритм Табу-поиска решений предложенной модели 99
4.4 Результаты вычислительных экспериментов 101
4.5 Выводы 110
Глава 5. Архитектура программной платформы для исследования свойств распределённых алгоритмов для поиска в метрическом пространстве 111
5.1 Базовый абстрактный класс MetricElement 112
5.2 Интерфейс MetricElementFactory 113
5.3 Работа в n-мерном Евклидовом пространстве 114
5.4 Работа с частотными векторами текстов 114
5.5 Класс AbstractMetricStructure 115
5.6 Класс MetrizedSmallWorld 116
5.7 Класс SelfAdaptedMetrizedSmallWorld 116
5.8 Библиотека алгоритмов AlgoritmLib 117
5.9 Эксперименты над корпусом текстов Тгес-3 117
5.10 Многопоточная реализация экспериментов с точками d-мерного Евклидова пространства 121
5.11 Выводы 124
Заключение 125
Публикации по теме диссертации 127
Список литературы 129
Приложения 136
- Протокол Kademlia
- Исследование навигационных свойств: распределение длины кратчайшего пути и распределение длины пути совершаемой жадным алгоритмом
- Методология оценки
- Эксперименты над корпусом текстов Тгес-3
Протокол Kademlia
Kademlia - peero-peer протокол реализующий концепцию DHT. Протокол был впервые описан Петаром Маймаунковым и Дэвидом -Мазьером в [Maymounkov & Mazieres, 2002] Он описывает структуру peero-peer сети и алгоритм обмена информацией между узлами участвующими в ней. Узлы Kademlia для коммуникации используют UDP протокол. В качестве ключей и адресации узлов в Kademlia используются 160-битные двоичные идентификаторы. Для узлов идентификаторы генерируются случайным образом, и при этом обеспечивается их уникальность.
Главным отличием Kademlia является то, что в качестве меры близости двух идентификаторов х и у используется XOR-метрика d(x, у) = х0у, которая довлетворяет всем трём аксиомам метрики: тождества, симметрии и аксиоме треугольника (неравенство треугольника). Важно отметить, о расстоянием является результат операции XOR, интерпретируемый, как число, а не количество различающихся бит (такой критерий тоже может порождать метрику пространстве ключей/идентификаторов). Т.е. при длине ключа 4 бита: d(2,5) = 0010 XOR 0101 = 0111 = 7.
Аналогично метрике Chord, XOR метрика - однозначная. Для любой данной точки х и расстояния Л 0, существует ровно одна точка у такая, что d(x, у) = Л. Отличие XOR-метрики от метрики, используемой в Chord в том, что она симметрична, т.е. d(x, у) = d(y, х) для любых х и у.
Для наглядного представления пространства идентификаторов используется двоичное дерево. В нём каждому идентификатору ставится в соответствие лист, соответствующий кратчайшему уникальному префиксу. Например, на рисунке 6 на двоичном дереве изображена позиция узла, чей идентификатор имеет кратчайший уникальный префикс 0011.
Каждый узел ответственен за хранение информации связанной с ключами, для каждого из которых идентификатор данного узла будет одним из k-ближайших среди всего множества узлов, присутствующих в данный момент в системе. Параметр принято называть параметром ширины репликации (system-wide replication parameter).
Так же как и в других децентрализованных peero-peer системах, в сети Kademlia поиск узла, чей идентификатор является ближайшим к идентификатору , производится инициатором, путём последовательного опроса узлов в направлении уменьшения значения XOR-метрики до наосновании таблицы маршрутизации, имеющейся у каждого узла. В процессе поиска идентификатора x, узел имеющий идентификатор на запрос узла инициатора сообщает ему IP адрес узла, чей идентификатор будет как можно ближе к на основании XOR-метрики среди множества узлов известных ему узлов. Если таких узлов нет, то ближайшим узлом к является он сам.
Для поддержания целостности сети и для обеспечения возможности поиска, каждый узел Kademlia поддерживает таблицу маршрутизации, в которой хранится структурированная информация о некоторых других узлах.
Таблица маршрутизации строится и поддерживается так , чтобы обеспечить логарифмическую зависимость числа узлов, опрашиваемых во время процедуры поиска, от общего размера системы. Для этого алгоритм использует значение XOR-метрики вычисляемой между идентификаторами узлов. (Далее в работе под словосочетанием "расстояние до узла " будет пониматься расстояние до идентификатора этого узла.
Основная идея быстрой навигации в Kademlia заключается в том, чтобы сформировать таблицу маршрутизации таким образом, чтобы во время процедуры поиска ближайшего узла к идентификатору , каждый узел мог указать на узел, чей идентификатор имеет общий префикс длиннее, по крайней мере, на один бит, чем общий префикс с его собственным.
С этой целью i-я строка таблицы (0 160) хранит информацию об узлах, чьи идентификаторы имеют общий префикс длинной 160 - бит и различаются в 159 - бите, что соответствует расстоянию от 2+1 до 2. Таким образом, последняя строка для узла 0011 может содержать информацию о любых узлах 1xxx, предпоследний об узлах 01xx, еще на уровень ближе — об узлах 000x (см. рис. 1.3.1). Каждая строка хранит не более чем записей, и принято её называть - bucket. Обычно в конкретных реализациях = 20.
Поддержание такой структуры таблицы в актуальном виде обеспечивает сложность поиска в сети за логарифмическое число шагов от общего числа узлов в системе (см. доказательство в оригинальной статье).
Так же как и в других подобных peero-peer системах, в том числе и в Chord, Kademlia использует жадный алгоритм. Координацию поиска осуществляет узел инициатор. Он последовательно опрашивает узлы с всё более уменьшающимся значениям XOR-метрики до искомого идентификатора . Каждый узел на запрос инициатора отвечает списком узлов, чьи идентификаторы являются ближайшими к , или воз вращает информацию, связанную с ключом , если таковая имеется. Поиск останавливается, когда все опрошенные узлы не знают ни одного узла, который бы был ближе к , чем все ранее опрошенные.
На рисунке 7 изображен пример, в котором узел 0011 отыскивает узел 1110 последовательного опрашивания наиближайших к запросу известных ему узлов. После каждого шага инициатор узнает об узле имеющим всё более длинный общий префикс с искомым.
Протокол Kademlia содержит 4 типа сообщений: PING, STORE, FIND_VALUE, FIND_NODE.
PING используется для проверки существования конкретного узла в сети. Например, он применяется при попытке добавления узла в -bucket, когда тот уже заполнен: опрашиваются существующие узлы, если нет ответа, то узел вставляется. Стоит отметить, что бол ее старые узлы находятся внизу -bucket, это основывается на экспериментальных данных, говорящих о том, что чем дольше узел остается в сети, тем меньше вероятности, что он ее покинет. Поэтому они будут опрошены только после более новых.
STORE запрос позволяет разместить информацию на заданном узле. Перед выполнением STORE узел должен найти ближайших к ключу значения, которое он собирается опубликовать, а лишь потом отправить каждому STORE с ключом и своими координатами. Хранение сразу на узлах позволяет повысить доступность информации.
FIND_VALUE запрос, который, зачастую, повторяется для образования итерации, позволяющий найти значение по ключу. Реализует поиск значения в сети. Возвращает либо ближайших узлов , либо само значение, в зависимости от достижения узла, хранящего искомые данные. Итерации прекращают как раз либо при возвращении значения (успех), либо при возврате уже опрошенных узлов (значения нет в сети).
FIND_NODE запрос используется для поиска -ближайших узлов к заданному идентификатору (поведение сходно с FIND_VALUE, только никогда не возвращает значение, всегда узлы). Используется, например, при присоединении узла к сети по следующей схеме:
— Контакт с bootstrap узлом
— Посылка запроса FIND_NODE со своим идентификатором к bs узлу, дальнейшая итеративная рассылка
Исследование навигационных свойств: распределение длины кратчайшего пути и распределение длины пути совершаемой жадным алгоритмом
Одной из важнейших характеристик графа (сети), c точки зрения поиска, является возможность жадным алгоритмом («Greedy Walk»; также употребляется термин «greedy roting») находить вершину, ближайшую к заданному объекту относительно функции расстояния : !. Про граф обладающий данным свойством в литературе принято говорить, что он обладает навигационным свойством [Clauset A., Moore C., 2003], [Chaintreau A., и др. 2008], [Fraigniaud P., 2007], [Kleinberg J. 2000], [Boguna M. и др. 2009], [Liben-Nowell D., и др, 2005], [Sandberg O., 2006].
Эффективность алгоритма Greedy Walk зависит от количества пройденных вершин, другими словами от длинны совершённого пути, иначе от количества совершенных шагов – «хопов». Если среднее число «хопов» пропорционально (log ()!), где n – число вершин, 0, то принято говорить о навигационных свойствах тесного мира. В особенности это характеристика существенно влияет на время работы алгоритма в случае, когда вершины расположены на различных физических узлах и получение списка соседей у соседней вершины (совершение «шага») сопряжено с передачей данных по сети и требует относительно большого времени.
На рисунках 27-33 приведены графики распределения длинны пути совершаемым жадным алгоритмом до момента остановки в точке локального минимума (ряд «GW»). Так же на графиках приведена информация о процентном соотношении количества успешных поисков имеющих определенную длину (ряд «SUCCEED»).
Распределение строилось по данным полученным в результате следующего эксперимента. Строились графы алгоритмом MSWConstruction с параметрами u=2;3;4;10; В качестве входного множества использовались 100 тыс. точек из d-мерного Евклидого пространства, сгенерированные случайно с равномерным распределением в единичном гипер-кубе. Далее с равномерным распределением генерировалось 100 случайных точек (множество ), которые использовались в качестве запросов. Затем от 100 произвольных вершины, выбираемые равновероятно среди всех вершин графа, запускался алгоритм GreedyWalk поиска каждой точки из множества запросов . Таким образом всего производилось 10,000 поисков. После чего эксперимент повторялся 20 раз, значения усреднялись.
Для каждого произведенного поиска собиралась информация о длине пути, а так же информация о том, был ли поиск успешным, то есть был ли в результате поиска обнаружен глобальный минимум. Квадратные маркеры на графике 3
Кроме того для сравнения на графике приводится информация о распределение длин кратчайших путей «GW» от вершины графа являющихся ближайшими к точкам запросам из множества и всеми остальными вершинами графа.
Очевидно, что количество шагов необходимое алгоритму GreedyWalk для нахождения оптимума не может быть меньше, чем длинна кратчайшего пути между глобальным минимумом и вершиной, с которой алгоритм с тартует. Поэтому в полне ожидаемо, что процент успешных «жадных» поисков, имеющих длину менее длины кратчайшего пути, равен нулю. Большому числу коротких неуспешных поисков соответствует левый горб ряда «GW».
Так же закономерно увеличения общего числа успешных поисков с ростом параметра u, уменьшением и исчезновением горба неуспешных коротких «жадных» поисков ряда «GW». Для значения параметра u=10 (4-й сверху график) горб соответствующим коротким «жадным» путям полностью отсутствует и распределение длины пути жадного алгоритма совпадает с процентом успешных поисков, что свидетельствует о том, что каждый поиск завершается успехом.
Стоит отметить, чтобы внести в эксперимент большую определенность, значение параметра w было выбрано достаточно большим (w=20), для того чтобы во время добавления каждый элемент гарантированно соединялся с u ближайшими элементами присутствующих в данный момент времени в структуре.
Эксперимент аналогичный эксперименту со 100,000 случайными точками из единичного отрезка прямой был произведен для размерности 2,3,4,10 и 20. Результаты экспериментов приведены на рисунке 29 для размерности 2 (параметр dim), на рисунке 30 – для размерности 3, на рисунке 31 для размерности 4, на рисунке 32 для размерности 10 и на рисунке 33 для размерности 20.
Методология оценки
Эксперименты производились на Linux Intel Xeon сервере с частотой 3.60 GHz, 32GB оперативной памяти в однопоточном режиме, используя библиотеку Non-Metric Space Library в качестве инструмента для валидации [Boytsov L., Naidan B.]. Программная реализация была написана на C++ и скомпилирована при помощи GNU C++ 4.7 (с ключом оптимизации «-Ofast»).
Использовалась реализация функций расстояний оптимизированные при помощи SSE 4.2 SIMD инструкций. В случае KL-дивергенции дополнительное ускорение достигалось за счёт предварительного вычисления логарифмов элементов векторов на этапе построения индекса [Boytsov L., Naidan B., 2013]. В реализации функции вычисления косинуса угла между векторами, использовалась инструкция сравнения _mm_cmpinstrm «все-против-всех» . Э та реализация около 2.5 раза быстрее, чем реализация на чистом С++.
Для проведения экспериментов случайным образом был разделен каждый тестовый набор на две части. Меньшая часть содержала тол ько 1000 объектов и использовалась в качестве множества запросов. Оставшиеся объекты индексировались. После индексации тестировалась производительность методов, производя поиск 10 ближайших элементов (10-NN search). Все методы полностью размещались в оперативной памяти. Процедура поиска повторялась пять раз для различных значений параметров для того, чтобы получить различные значения точности и иметь некоторое усреднение (значение параметров выбирались вручную).
Большинство методов тестировались на всех тестовых наборах данных. Multi-probe LSH и Список кластеров использовались только для Евклидова расстояния. VP-дерево не использовалась для Wikipedia, связи с высокой размерностью тестового набора, на котором VP-дерево работала чуть лучше полного перебора. Результаты сравнения методов для Евклидова расстояния и для KL-дивергенции приведены на рисунках 40 и 41 соответственно. График в первой строке показывает во сколько раз тот или иной метод делает меньше вычислений функции расстояния в сравнении с полным перебором для различных значений точности. Во второй строке по вертикали отложено значение во сколько раз метод быстрее полного перебора (время работы).
Как видно из графиков на рисунках 40 и 41, метод MSW имеет наилучшее соотношение точности и производительности на всех трёх тестовых наборах данных. Рассмотрим, например, тестовый набор данных CoPhlR (рисунок 40). Для значения точности (recall) 0.9 метод MSW вычисляет в 1000 раз меньше расстояний, чем полный перебор. Остальные методы для этого значения точности превосходят полный перебор менее чем в сто раз. Подобную производительность метод LSH имеет только для значения точности 0.4.
Обычно, чем меньше раз метод вычисляет функцию расстояния, тем быстрее он работает . Однако для «недорогих» функций расстояний, например, Евклидова расстояния, скорость работы метода зависит не напрямую от количества вычисленных функций расстояния. Рассмотрим тестовый набор Unif64 на рис. 1 и Final256 на рис. 41: несмотря на то, что MSW использовал меньше всего вычислений расстояний во всех случаях, однако дополнительные вычислительные расходы, связанные с обходом графа, могут быть высокими. Как результат pivot neighborhood index или multi-probe LSH иногда показывают лучшую итоговую производительность.
Отметим, что MSW и inv. neighborhood index хорошо работают для расстояния KL-дивергенции. Для всех трёх наборов данных с функций расстояния KL-дивергенции они показывают ускорение более чем в 10 раз, по сравнению с полным перебором, для значения точности 0.9.
Результаты сравнения методов на данных Wikipedia представлены на рис. 42(а). Верхний график показывает во сколько раз метод совершает меньше вычислений расстояний по сравнению с полным перебором для различных значений точности. Соответственно, нижний график изображает во сколько раз методы работают быстрее полного перебора для разных значений т очности. Несмотря на то , что использовалась улучшенную реализацию функции вычисления косинуса угла между двумя векторами с помощью инструкций SIMD, которая 2.5 раза быстрее, чем обычная реализацию на чистом C++, вычисление скалярного произведения продолжает оставаться вычислительно затратной операцией. По этой п ричине сокращение количества вычисленных расстояний, напрямую влияет на общую скорость работы методов.
Как видно из графика, на этом наборе данных MSW работает значительно лучше остальных методов. Например, для точности 0.87 MSW примерно в 40 раз быстрее полного перебора. Следующий по производительности метод (pivot neighborhood index) достигает такой производительности при значительной меньшей точности 0.6.
Для того чтобы понять, как производительность методов зависит от размера набора данных, производились эксперименты с Википедией. Производились замеры для подмножеств Википедии, чей размер варьировался от 12.5 тыс. до 3.2 миллионов элементов. На каждом тестовом подмножестве для каждого метода запускалась процедура поиска несколько раз с различными параметрами для того, чтобы получить результаты для различных значений точности. Для MSW использовались параметры, которые давали 0.9, тогда как для других методов использовались параметры, приводившие к точности 0.8. Результаты экспериментов приведены на рис. 42(6). Нижний график включает в себя результаты для всех методов, верхний - только MSW и pivot neighborhood index.
Как видно из рис. 42(6), все сравниваемые методы, основанные на перестановках, имеют зависимость от количества объектов близкую к линейной. В то время как MSW демонстрирует зависимость близкую к логарифмической (добавить график в двойном логарифмическом масштабе) и при этом имеет большую точность (0.9 против 0.8). Таким образом, MSW имеет принципиально другую вычислительную сложность и превосходит в производительности сравниваемые методы тем больше, чем больше набор входных данных.
Эксперименты над корпусом текстов Тгес-3
Чтобы продемонстрировать используются выше описанные классы и как может выглядеть код, основанный на данной иерархии классов , далее приводится детали эксперимента с коллекцией документов Trec-3.
SearchAttemptsTestTrec3.java – файл в котором содержится код, который производит эксперимент.
Данный эксперимент (скрипт, сценарий) состоит из 3-х этапов. Первый этап – считывание частотных векторов из коллекции текстов и считывание множества запросов.
MetricElementFactory elementFactory= new DocumentFileFactory(); elementFactory.setParameterString("dir="+dataPath+";maxDoc="+d ataBaseSize); MetricElementFactory testQueryFactory = new DocumentFileFactory(); testQueryFactory.setParameterString("dir="+queryPath+"; maxDoc="+querySetSize);
После того как элементы были считаны, вызывается конструктор класса представляющий испытываемую структуру данных (испытываемой совокупности алгоритмов) и устанавливаются параметры.
MetrizedSmallWorld db = new MetrizedSmallWorld();
db.setNN(nn);
db.setInitAttempts(initAttempts);
Далее считанные элементы последовательно добавляются в структуру.
for (MetricElement me: elementFactory.getElements()) {db.add(me); }
На втором этапе для чтобы иметь возможность оценивать точность поиска испытываемой структуры данных, необходимо точно знать, какие элементы из индексируемого множества являются k-ближайшими.
Для этого задействуется ст атическая функция из вспомогательного класса TestLib, которая, в конечном итоге вычисляет расстояние от запроса newQuery до каждого элемента из множества.
for (MetricElement newQuery: testQueryFactory.getElements()) {testQueries.add(newQuery); rightResultMap.put(newQuery, TestLib.getKCorrectElements(db.getElements(), newQuery, k)); }
На третьем этапе осуществляется поиск k-ближайших до каждого элемента из множества запросов, используя структуру, построенную на первом этапе. Элементы полученные в результате поиска, сравниваются с эталонными k-ближайшими. Вычисляется значение точности поиска – значение recall. Результаты выводятся в консоль. После чего поиск производится с другими параметрами (в данном сценарии, увеличивается значение числа попыток при поиске).
Для того чтобы сократить время на процесс вычисления точности поиска был написан код, который может исполняться независимо параллельно в разных потоках создаваемых и поддерживаемых операционной системой. Поскольку изначально этот код был создан на момент, когда стандарта java 8 ещё не существовал и был доступен только 7-й стандарт, параллельное исполнение вычислений было имплементировано с использованием механизма «фьючерсов» (анл. Future). Данный механизм позволяет осуществлять отложенные вычисления. В сущности (на практике) этот механизм позволяет создавать множество заданий, описывая их в форме реализации метода call интерфейса Callable в ходящего в состав пакета java.util.concurrent. В данном случае в качестве заданий выступает поиск одного элемента из множества запросов, оформленного в виде внутреннего статического класса MyCallable. Внутри метода call у объекта, который представляет тестируемую структуру данных, вызывается метод поиска и подсчитывает количество правильно найденных k-ближайших элементов т .е. сколько среди элементов возвращенных процедурой поиска, есть во множестве эталонных.
@Override public TestResult call() throws Exception { SearchResult result = db.knnSearch(testQ, k, attempts); int good=0; for (EvaluatedElement ee: result.getViewedList()) if (answer.contains(ee)) good++; return new TestResult(good, result.getViewedList().size(), result.getViewedList().size(), result.getVisitedSet()); }
Внутри основного кода задания создаются как объекты-экземпляры класса MyCallable, различающиеся только одним параметром – элементом до которого производится поиск, более кратко – запросом.
Обработка заданий в многопоточном режиме происходит с помощью executerTreadPool, в котором скрыто взаимодействие с операционной системой.
Задания помещаются в executerTreadPool спомощью метода submit. Метод submit в ответ возвращает фьючерсы (объекты типа Future), объекты которые служат своего-рода семафорами для исполнения основного трэда. У каждого объекта типа Future есть метод get(), исполнение которого завершится только после того, как обработка задачи связанной с фьючерсом завершится. Это позволяет построить модель отложенных вычислений.
После того, как все задачи были загружены в executerTreadPool, исполнение основного потока (трэда) останавливается, до тех пор пока все запущенные задачи не завершатся, что эквивалентно тому, что у всех фьючерсов, не станут известны результаты вычислений, то есть пока не завершит работу метод get у каждого фьючерса.
for (Future TestResult future : searchResultList) { try { TestResult tr = future.get(); good += tr.getRightResutls(); scanned+=tr.getScannedNumber(); } catch (InterruptedException e) { throw new Error(e); } catch (ExecutionException e) { throw new Error(e); } } executor.shutdown();
Так параллельно происходит подсчёт общего количества правильно найденных ближайших соседей. После чего вычисляется значения точности recall (результаты экспериментов приведены в главе 3).