Оверлейная сеть для распределенного точного и интервального поиска в одномерном пространстве

Аннотация

Пономаренко Александр Александрович - научный сотрудник, Лаборатория алгоритмов и технологий анализа сетевых структур Национальный исследовательский университет «Высшая школа экономики»    
Адрес: Российская Федерация, 603093, г. Нижний Новгород, ул. Родионова, 136
E-mail: aponomarenko@hse.ru

Мальков Юрий Андреевич - младший научный сотрудник, Институт прикладной физики, Российская академия наук  
Адрес: Российская Федерация, 603950, г. Нижний Новгород, ул. Ульянова, 46
E-mail: yurymalkov@mail.ru

Логвинов Андрей Александрович - руководитель проектов, ООО «МераЛабс»
Адрес: Российская Федерация, 603093, г. Нижний Новгород, ул. Родионова, 192
E-mail: alogvinov@meralabs.com

Крылов Владимир Владимирович - доктор технических наук, профессор, заведующий лабораторией больших данных, Нижегородский государственный технический университет им. Р.Е.Алексеева
Адрес: Российская Федерация, 603950, г. Нижний Новгород, ул. Минина, 24
E-mail: vkrylov@heterarchica.com

      Для современной компьютерной системы возможность масштабироваться является необходимым бизнес-требованием. Распределенные системы явно демонстрируют это свойство, как и способность легко обрабатывать сверхбольшие объемы данных. Многие системы с распределенной архитектурой имеют в основе распределенную хэш-таблицу (distributed hash table, DHT), которая используется в качестве дополнительной логической сети, объединяющей множество распределенных серверов. Эта логическая сеть используется для поиска узлов и распределения задач между ними. Главное преимущество такого подхода – отсутствие какого-либо центрального элемента или узла, который обладал бы информацией о структуре всей сети. Поиск узлов в сети происходит путем передачи поискового сообщения от одного узла к другому. Несмотря на то, что каждый узел «знает» только небольшое число других узлов, сеть организованна таким образом, что процедура поиска затрагивает логарифмическое число узлов.
      Существует несколько реализаций концепции DHT, которые регламентируют, каким образом логическая сеть строится и поддерживается. В этой работе мы демонстрируем, как такая сеть может быть сконструирована очень простым способом, с применением (с небольшими изменениями) недавно опубликованного алгоритма метризованного тесного мира (Metrized Small World) для случая одномерного метрического пространства. В работе мы приводим теоретический анализ для случая равномерного распределения данных и эмпирический анализ для других распределений. Главным преимуществом предложенного алгоритма перед аналогами является его устойчивость к различным распределениям данных и отсутствие необходимости поддержания распределения длин ссылок, определенного явным образом.
      Также в работе описывается, каким образом можно полностью отделить физическое размещение данных от поисковой функциональности. Это разделение важно, например, для построения глобальных хранилищ данных, данными которых владеют несколько сторон, причем каждая сторона заинтересована в том, чтобы иметь полный контроль над физическим размещением и доступу к своим данным. В отличие от DHT, добавление новых данных не требует их перемещение на другие узлы.