Лекция 15. Поиск в пиринговых системах - Лекция, раздел Философия, Распределенные системы и алгоритмы Пиринговые Системы (Peer-To-Peer, P2P) – Это Такие Компьютерные Сети, В Котор...
Пиринговые системы (peer-to-peer, P2P) – это такие компьютерные сети, в которых не используется классическая схема клиент-сервер, разделяющая множество всех узлов на два подмножества – серверов и клиентов. В пиринговой сети все узлы «равны» в том смысле, что каждый из них по отношению к другому (другим) может выполнять функции как клиента, так и сервера. Эти сети называют еще одноранговыми.
Возникновение пиринговых сетей связано с тремя факторами.
1. Процессор обычной клиентской машины мало загружен. Особенно в офисах, где машины используются преимущественно для подготовки документов, для набора текстов и т.п. То же касается и подавляющего большинства домашних компьютеров.
2. Многие пользователи хранят на своих компьютерах коллекции файлов (тексты статей определенной тематики, художественные фотографии и др.), которые могут быть интересны и другим пользователям. Но при этом владельцы этих коллекций не готовы сделать свой компьютер полноценным сервером в сети из-за его недостаточной мощности, необходимости круглосуточной работы, финансовых и других причин.
3. Определенная часть пользователей хотела бы более активно участвовать в «общественной жизни» сети, не ограничиваясь обсуждением различных вопросов на форумах и в чатах. Они готовы участвовать в каком-либо полезном «общем деле».
Пиринговые сети разнообразны. Основной целью одних является обмен музыкальными и видео файлами. В других реализуются проекты поиска лекарства от рака, третьи тренируются во взломе известных шифров на основе распределенных вычислений, четвертые ищут внеземные цивилизации на основе данных, получаемых с радиотелескопов.
С математической точки зрения пиринговая сеть может быть представлена графом неопределенного вида: нет какой-либо стандартной архитектуры сети (например, звезды или кольца). Более того, этот граф – динамический, так как отдельные пользователи включаются в сеть и выходят из ее состава в произвольные моменты времени. Любой пользователь, играющий роль сервера, в любой момент времени может превратиться в клиента на некоторый отрезок времени. Но может и пребывать одновременно в положении и сервера и клиента.
Исследования в области пиринговых сетей начались в связи с успешным функционированием таких систем как Napster, Gnutella и Freenet.
Napster – гибридная система, поскольку использует централизованный индекс для поиска. Система Gnutella – чистая пиринговая система. Ее архитектура такова, что каждый узел с невысокими скоростями коммутации может иметь до четырех соседей, мощные же узлы могут иметь десятки соседей. Понятно, чем больше соседей, тем быстрее может быть поиск. Но здесь имеются такие же технические ограничения, как и в многопроцессорных компьютерах: слишком накладно соединять каждого с каждым. Соединения в системе не направленные (неориентированный граф). Система Gnutella использует поиск в ширину, просматривая сначала все соседние с инициатором узлы. Каждый узел, получивший запрос, распространяет его своим соседям максимум на d шагов.
Преимущество поиска в ширину состоит в том, что просматривая значительную часть сети, он увеличивает вероятность удовлетворения запроса. Недостатком является перегрузка сети лишними сообщениями.
Система Freenet использует поиск в глубину на величину d. Каждый узел отправляет запрос только одному соседу и ждет от него ответа до посылки запроса следующему. Этот метод не отправляет лишних сообщений, но увеличивает время получения ответа.
Янг и Гарсиа-Молина предложили улучшить протокол Gnutella применением одной из трех техник. Первая – итеративное углубление, при которой многократно применяется поиск в ширину с увеличивающимся значением di . Вторая – направленный поиск в ширину, при котором запросы направляются не всем соседям, а только соседям из «полезного» множества. При этом каждый узел должен хранить некоторую информацию о соседях, характеризующую их «полезность». Третья техника – локальное индексирование. При этом каждый узел хранит индексы для данных на узлах, находящихся от него на некотором расстоянии k.
Большинство существующих систем поддерживают только «булевы» запросы. Каждый файл характеризуется его метаданными (например, набором ключевых слов) и запрос формируется как набор ключевых слов. Вследствие этого результат поиска может быть двухвариантным: «найдено», «не найдено».
П.Калнис, В.Нг, Б.Ой, К.-Л.Тан исследовали проблему нечетких запросов, таких, например, как «для данного примера найти m наиболее соответствующих ему образов». Такие запросы часто используются в системах поиска изображений, поскольку человеку трудно точно выразить содержание некоторого изображения ключевыми словами. В связи с этим нельзя создать централизованный индекс, каждый узел (в области распространения запроса) вернет m результатов, и инициатор запроса сам вынужден будет отыскивать глобальный результат. Разумеется, это связано с пересылкой большого числа бесполезных сообщений.
Поскольку запросы являются нечеткими, то и ответы всегда приближенные. Это означает, что если два запроса являются подобными (но не в точности одинаковыми), то и найденные множества из m наиболее соответствующих каждому из них ответов, с большой вероятностью будут совпадать или во многом пересекаться (т.е. содержать одни и те же ответы).
Авторы вводят в рассмотрение систему FuzzyPeer класса P2P, поддерживающую подобные запросы. В этой системе некоторые запросы «берут паузу», т.е. не распространяются дальше, оставаясь внутри некоторого множества узлов. Такие запросы называют «замороженными».
Замороженные запросы получают ответы из потока ответов, проходящих через эти узлы, инициированного оставшимися «действующими» запросами. При тщательном выборе множества «замороженных» запросов, получающих ответы из упомянутого потока данных, можно получить результаты, качество которых и время ответа будут на приемлемом уровне, даже если система перегружена.
Участие узлов в системе FuzzyPeer динамично – они могут подключаться к системе в любой момент времени. Также они могут и покидать систему. В системе имеются специальные серверы Si, поддерживающие эту динамику. Когда узел хочет включиться в систему, сервер определяет, с какими другими узлами он будет соседствовать. Затем запускается протокол соединения, подобный протоколу Gnutella. Если не считать серверов Si , система является полностью распределенной.
Серверы участвуют только в формировании и изменении системы, но не участвуют в передаче и обработке запросов.
Работа в FuzzyPeer происходит следующим образом.
Примем для рассматриваемого примера сети (рис. 31) d = 3. Узлы имеют от одного до трех соседей. Время ожидания узлом ответа ограничим величиной Tmax . Архитектура сети формируется тремя серверами S1 , S2 и S3 . Они задают связи между узлами и присваивают им имена. Сферы влияния серверов показаны пунктирными линиями.
Рис. 31. Пиринговая сеть
Пусть пользователь на узле p1 генерирует запрос q1 = «для данного примера найти 8 наиболее соответствующих ему изображений». Этот узел распространяет запрос среди непосредственных соседей, p2 , p3 и p6 . Они производят поиск в своих базах данных и выдают идентификаторы восьмерки наиболее подходящих изображений, одновременно с величинами различий (должна существовать некая метрика в пространстве изображений).
Одновременно, узлы p2 , p3 и p6 распространяют запрос q1 среди своих соседей. В частности, может случиться, что некоторые из узлов p2 , p3 и p6 являются соседями друг друга. Например, p2 и p6 . Тогда p2 направит запрос q1 соседу p6 . Узел p6 проигнорирует этот запрос ввиду дублирования (такой запрос узлу p6 уже поступал).
Поскольку расстояние распространения запроса ограничено величиной d = 3, то узлы p9 , p10 , p12 и p13 запросов не получат. Узел p5 , получивший запрос q1 через узел p6 , через этот же узел и будет возвращать ответ. Узел p1 ожидает время Tmax . В течение этого времени он принимает приходящие ответы. По окончании срока все опоздавшие ответы игнорируются.
Иногда на некоторых узлах пиринговой сети может возникать перегрузка.
Положим, как и ранее, узел p1 направил в сеть запрос q1 . Запрос еще не выполнен, а узел p2 также направляет в сеть запрос q2 , очень похожий на запрос q1 , но не тождественный ему, q2 ¹ q1 . Запрос q2 направляется соседям p2 , в том числе и узлу p6 . Поскольку узел p6 еще не завершил обработку запроса q1 , на узле p6 возникает перегрузка: узел должен обрабатывать два запроса. Может случиться, что из-за увеличивающейся задержки на узле за время Tmax не будет обработан и первый запрос, q1 . Таким образом, оба запроса могут получить отказ.
В сети FuzzyPeer вместо того, чтобы обрабатывать запрос q2 , его «замораживают».
Когда запрос q1 проходит через узел p6 , он инициирует поток ответов Flow(q1). Все ответы от p4 , p5 и p11 , которым транслировался этот запрос, включаются в поток Flow(q1). Когда запрос q2 также достигает узла p6 , он идентифицируется как «похожий» на запрос q1 . Вследствие этого, он не распространяется дальше, а «замораживается» внутри узла p6 до прохождения обратного потока Flow(q1).
Узел p6 возвращает результаты, находящиеся в потоке Flow(q1), не только инициатору – узлу p1 , но и узлу p2 . Основанием для таких действий является предположение о том, что если запросы близки, то и ответы должны быть близкими в пределах некоторой метрики. Конечно, для каждого приближенного запроса qi можно отыскивать свой (персональный) приближенный ответ f(qi). Тогда для запросов qj » qi , но qj ¹ qi , приближенные ответы могут несколько отличаться друг от друга: f(qj) » f(qi), f(qj) ¹ f(qi). Но если, опять же в смысле некоторой метрики, ответ f(qi) является удовлетворительным для запроса qj , то почему бы им не воспользоваться и уменьшить работу по поиску?
Предложенный метод может быть записан в виде следующего распределенного алгоритма статического «замораживания» запросов.
Переменные – атрибуты запроса q:
frozen: boolean {запрос заморожен или не заморожен} init false,
steps: integer {ограничение на количество шагов}, init ¥,
Распределенные системы и алгоритмы... Курс лекций...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Лекция 15. Поиск в пиринговых системах
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Сосредоточенные и распределенные системы
Во многих случаях термин «распределенная» является альтернативой термину «сосредоточенная». Так бывает, когда существуют (или могут существовать) системы, решающие одинаковые задачи, системы, функц
Тандемы распределенных систем
Рассмотрим две системы, S1 и S2 . Первая система функционирует для достижения некоторой цели G1 . При этом в любой момент времени имеется некот
Лекция 2. Распределенные задачи и алгоритмы
С системой S связана цель G, ради которой система функционирует. Эта цель ставится самой системой (если система – активная), или поставлена извне. Для достижения цели в системе должна
Лекция 3. Надежность и безопасность распределенных систем
Сравним сосредоточенную и распределенную системы с точки зрения надежности и безопасности.
Под надежностью понимается в соответствии с ГОСТ 27.002-89 свойство системы сохранять во в
Структура информационного пространства
Хотя термин «информационное пространство» является лишь метафорой, обратимся к проблеме анализа структуры этого пространства. Математики привыкли связывать с любым пространством некоторую структуру
Структуры РРИСО
Структуру РРИСО можно рассматривать с нескольких точек зрения. Прежде всего, это наиболее очевидная – географически ориентированная структура. Многие (но не все) элементы информационной системы при
Подсистемы. Взаимоотношения структур
Каждая из структур РРИСО строится по своим законам, поэтому, не стоит ожидать изоморфизма между парами структур. Идеально, если одни структуры являются надстройками над другими, использующими механ
Условная корпоративность
Хотя мы называем РРИСО корпоративной системой в силу того, что имеется определенный административный «каркас» на множестве ее пользователей, и у нее довольно четкая целевая направленность, тем не м
Неоднородность
Неоднородность – одна из важнейших характеристик РРИСО. Если многие корпоративные системы являются однородными, или неоднородность имеет место в одном - двух аспектах построения системы, то неоднор
Интегрируемость
Это одно из ключевых свойств в характеристике РРИСО. Это и «врожденное» и приобретаемое свойство.
Невозможно представить себе, чтобы такая система создавалась «с нуля». Существуют базы дан
Лекция 6. Моделирование распределенных систем. Язык Triad
Исследование распределенных систем – трудная задача. Прежде всего, распределенная система должна быть описана, т.е. должна быть построена модель системы. Для этой цели можно использовать различные
For i:= 1 to n do
routine(System2.Node[i]) := Generator
endf.
При этом создается n экземпляров рутины Generator. Для каждого экземпляра рутины создается свой комплект локальных пер
For i:= 1 to n – 1 do
System := System + (System.Node[i] « System.Node[i + 1])
endf;
System := System + (System.Node[n] « System.Node[1])
В цикле к системе добавляются ребра м
Лекция 7. Распределенное имитационное моделирование
В одной из лекций шла речь о методах исследования распределенных систем. В качестве одного из методов рассматривался метод имитационного моделирования.
Если предположить, что предметом исс
Причины для перехода к распределенному моделированию
Использование распределенного моделирования объясняется:
- возможностью использования вычислительных ресурсов нескольких процессоров (компьютеров) для выполнения имитационного эксперимента
Два направления в развитии распределенных систем моделирования
Развитие распределенного имитационного моделирования идет по двум направлениям. Это монолитные системы моделирования и готовые системы моделирования, объединенные с помощью специального программног
Физическое время
Рассмотрим пример: пусть на нескольких компьютерах (клиентах) располагаются директории с файлами – списки товаров, на сервере – сводная директория, которая периодически обновляется. Приложение, рас
Управление временем в распределенном моделировании
Управление временем в распределённом моделировании должно обеспечивать выполнение событий в правильном хронологическом порядке. Более того, на алгоритмы синхронизации возлагается обязанность коррек
Парадоксы времени
Алгоритм управления временем должен следить за тем, чтобы события выполнялись в хронологическом порядке. Эта задача не является тривиальной. Действительно, логический процесс заранее не может знать
Консервативное управление временем
Первые алгоритмы синхронизации использовали консервативный подход. Принципиальная задача консервативного протокола – определить время, когда обработка очередного события из списка необработанных со
Алгоритм с нулевыми сообщениями
Первыми консервативными алгоритмами считаются алгоритмы, разработанные Bryant, Chandy, Misra.
Алгоритм предполагает:
- Топология процессов, которые посылают сообщения друг другу,
Оптимистическое управление временем
В отличие от консервативных алгоритмов, не допускающих нарушения ограничения локальной каузальности, оптимистические методы не следят за этим ограничением. Однако этот подход гарантирует выявление
Лекция 9. Балансировка нагрузки в распределенных системах
Балансировка нагрузки (Load Balancing) применяется для оптимизации выполнения распределённых (параллельных) вычислений с помощью распределённой (параллельной) ВС. Балансировка
Статическая и динамическая балансировки
Следует различать статическую и динамическую балансировки.
Статическая балансировка выполняется до начала выполнения распределенн
Оценка загрузки
На этом этапе осуществляется приблизительная оценка загрузки каждого процессора. Полученная информация о загрузке используется в качестве базы данных для процесса балансировки, во-первых, для опред
Инициализация балансировки загрузки
Слишком частое выполнение балансировки загрузки может привести к тому, что выполнение имитационной модели только замедлится. Затраты на саму балансировку могут превзойти возможную выгоду от ее пров
Балансировка загрузки распределенной имитационной модели
В одной из предыдущих лекций мы рассматривали вопросы реализации распределенных систем имитации. Балансировку необходимо выполнять и при проведении распределённого моделирования. Первоначальная цел
Динамическая балансировка и перенос нагрузки
Алгоритм динамической балансировки использует характеристики состояния системы и принимает решение о том, с какого компьютера и на какой следует перенести работу во время моделирования. Это подход
RCL – cтратегия переноса нагрузки
Рассмотрим три алгоритма динамического переноса нагрузки, предложенные разработчиками SPEEDES:
- случайный алгоритм (random, R);
- алгоритм, основанный на коммуникациях (communica
Действия первого уровня
В начале действий по переносу нагрузки информации все компьютеры прекращают свою работу, и каждый получает информацию о локальной нагрузке в текущий момент времени. Информация о локальной нагрузке
Действия второго уровня
Действия второго уровня охватывают все рабочие станции распределённой системы. Конкретной количество нагрузки посылается с одной рабочей станции на другую. Основные действия связаны с выбором нагру
Реализация
Стратегия динамического переноса нагрузки RCL была разработана для SPEEDES с целью повышения её производительности. Были проведены эксперименты для выявления конкретных параметров, которые влияют н
Распределенные веб-сервисы
В настоящее время веб-сервисы находят все более широкое применение. Они используются в самых разных случаях в Интернет. Быстрое увеличение числа веб-сервисов и пользователей этих сервисов требует в
Использование мобильных агентов
Наряду с традиционными подходами (парадигма обмена сообщениями) рассмотрим другой – мультиагентный подход.
Напомним, что мобильный агент – это программный компонент, который может автомати
Мультиагентный подход к балансировке
Мобильные агенты используются для поддержки балансировки загрузки в параллельных и распределенных вычислениях. Рассмотрим кратко несколько проектов.
Проект Traveller
Проект
Агенты и МАС
Развитие интеллектуальных агентов и МАС очень популярны в среде исследователей ИС.
В области ИС интеллектуальные агенты используются, прежде всего, для интеграции информационных систем, по
Лекция 11. Распределенное хранение информации
Источники информации часто, как говорилось ранее, находятся в различных точках физического пространства. Если информация из этих источников не используется сразу, а потребность в ней возникает лишь
Фрагментация
Реляционные базы данных хранят отношения – таблицы, состоящие из строк и столбцов. Строка отношения называется кортежем и представляет собой запись (record в смысле языка программирования, н
Репликация
Под репликацией понимается создание копий некоторых фрагментов отношений и одновременное хранение нескольких копий на разных сайтах (в разных локальных БД). Репликация используется для того,
Схемы владения данными в распределенной БД
Выше, рассматривая распределенную базу данных, состоящую из локальных сайтов, мы неявно предполагали, что для каждой единицы данных существует вполне определенный единственный сайт, владеющий этими
Лекция 12. Волновые алгоритмы распространения информации
Многие задачи в распределенных системах решаются путем пересылки сообщений согласно некоторой схемы, которая гарантирует участие всех сайтов. Эта схема зависит от топологических особенностей систем
Алгоритм для кольцевой архитектуры
Если сайты распределенной системы соединены однонаправленными каналами связи так, что образуют граф – ориентированный цикл, применим следующий волновой алгоритм.
Суть его в следующем. Один
Алгоритм для структуры – дерева
Предположим, что соединение сайтов распределенной системы каналами образует граф – неориентированное дерево. Из теории графов известны следующие факты для деревьев:
1) дерево – связный аци
Алгоритм голосования
Алгоритм голосования применяется для распределенных систем, имеющих структуры полных графов. В этом случае инициатором может быть любой сайт. Для графа – звезды его тоже можно использовать, но иниц
Фазовый алгоритм
Фазовый алгоритм является децентрализованным алгоритмом для произвольных ориентированных графов. Двунаправленные связи тоже могут присутствовать, но они должны быть заданы парой параллельных встреч
Алгоритм Финна
Алгоритм Финна – еще один волновой алгоритм, который можно использовать в ориентированных сетях произвольной топологии. Он не требует того, чтобы диаметр сети был известен заранее, но подразумевает
Распространение информации с обратной связью
Важным применением волновых алгоритмов является случай, когда некоторая информация должна быть передана всем процессам и определенные процессы должны быть оповещены о завершении передачи. Эта задач
Синхронизация
Волновые алгоритмы могут использоваться для случаев, когда должна быть достигнута глобальная синхронизация процессов. Задача синхронизации формулируется следующим образом. В каждом процессе q
Вычисление нижней грани
Продемонстрируем применение волновых алгоритмов для вычисления функций, значения которых зависят от входов процесса на каждом сайте. В качестве представителей таких функций будут рассмотрены алгори
Лекция 13. Алгоритмы обхода сайтов
Алгоритмом обхода называется алгоритм, обладающий следующими тремя свойствами.
1) В каждом вычислении один сайт-инициатор, который начинает выполнение алгоритма, посылая ровно одно сообщен
Алгоритм обхода тора
Граф вида «тор» представляет собой решетку с дополнительными ребрами, соединяющими вершины из верхнего ряда («строки») решетки с вершинами из нижнего ряда, а также с ребрами, соединяющими вершины и
Алгоритм обхода гиперкуба
В теории графов известен класс графов Qn , называемых кубами размерности n, или гиперкубами. Это семейство описывается формулами Qn = K2
Алгоритм Тарри
Алгоритм обхода для произвольных связных графов был дан Тарри. Алгоритм основан на следующих двух правилах.
1. Процесс никогда не передает маркер дважды по одному и тому же каналу.
Лекция 14. Алгоритмы выбора сайтов
Во многих распределенных системах один из сайтов играет роль координатора при выполнении распределенного алгоритма. Иногда координатором является сайт, который инициировал выполнение алгоритма. Но
Алгоритм смещения
Алгоритм предназначен для динамического выбора координатора на основе локальных оценок сайтов. Предполагается, что каналы связи надежны, а сайты иногда могут прерывать (например, из-за отказов) сво
Выбор с помощью алгоритма для деревьев
Если топология распределенной системы – дерево или доступно остовное дерево системы, выбор можно провести с помощью алгоритма, приведенного в лекции 12. В этом алгоритме требуется, чтобы все концев
Алгоритмы выбора для кольцевых архитектур
В алгоритме Лелана для распределенной системы с архитектурой кольца (ориентированного цикла) каждый инициатор вычисляет список идентификаторов всех инициаторов, после чего выбирается инициатор с на
Лекция 16. Тенденции в области распределенных систем
В одной из своих статей в 2001 году Дж. Бэкус отметил, что компьютерная революция испытала три волны. Первая волна началась с коммерциализацией кремниевых чипов и продолжалась 10-15 лет. Вторая вол
Архитектура Грид
Следуя традиционному построению распределенных систем, можно описать архитектуру Грид, состоящую из четырех слоев:
1. Пользовательские интерфейсы, приложения и среда решения задач (problem
Мобильный компьютинг
Самостоятельным направлением является мобильный компьютинг. В его основе (в дополнение к распределенному компьютингу) лежат:
1) сети, обеспечивающие подключение к ним
Тотальный компьютинг
Английский термин pervasive computing обозначает проникающий, распространяющийся повсюду, всеобъемлющий, глубоко влияющий (компьютинг). Тотальный компьютинг ставит во главу угла конечного пользоват
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов