Современные методы распределённых вычислений

1.

СОВРЕМЕННЫЕ
МЕТОДЫ
РАСПРЕДЕЛЁННЫХ
ВЫЧИСЛЕНИЙ
Бритвина В.В., 2019

2.

Постановка задачи о
глобальной интеграции
информационных ресурсов
Тема 1

3.

Примеры глобальных распределённых
приложений
• Военно-промышленный комплекс
Имитационное моделирование военных действий (HLA)
Удаленное управление военной техникой («война роботов»)
Глобальные цепи поставки
Сети распределения ресурсов (энергетика, финансы)
Маркетинг в глобальной информационной сети
Международные исследовательские проекты (LHC)
Прогнозирование погоды
Расшифровка генома
Общемировые виртуальные библиотеки
Глобальные социальные сети
Мониторинг местонахождения человека («Большой Брат»)
• Экономика
• Наука
• Социум

4.

Характеристики масштаба систем
• Большое количество компонентов (104-108 ед.)
• Географическая протяжённость объектов (102-104 км)
• Высокая частота изменений состояния объектов (10-510-6 с)
• Техническая неоднородность компонентов (102
наименований)
• Административная и политическая разобщённость (102
организаций)

5.

Особенности разработки
крупномасштабных систем
• Крупномасштабная технологическая инфраструктура
Вычислительные кластеры и Grid-системы
Анализ больших массивов данных (OLAP)
Управление глобальными потоками данных реального времени
Переход на IPv6
• Технологии комплексирования разнородных компонентов
Контрактный подход к проектированию многократно
используемых компонентов
Универсальные платформы исполнения байт-кода (Java, .Net)
«Тонкие» клиенты (Web-интерфейс)
Администрирование на основе универсальных политик
Проектирование метаданных и онтологий предметных
областей (Semantic Web/Grid)

6.

Особенности разработки
крупномасштабных систем
(продолжение)
• Технологии повышения уровня адаптивности систем
Автоматический мониторинг состояния окружения
Автоматическое реагирование на изменения в окружении
Автоматическое восстановление после сбоев
Автоматизированное сопровождение
Адаптивный инкрементальный технологический цикл создания
систем
Разработка программных агентов
• Модельно-управляемая разработка (model-driven
development)
Автоматическая генерация программного кода по формальным
моделям
Формализация нефункциональных требований
Интеграция разнородных архитектурных разрезов
(структурный, объектный, аспектный)
Соответствие шаблонам анализа и проектирования
Разработка горизонтальных метамоделей, параметризованных
формальной моделью предметной области

7.

Математические основы
инженерии распределённых
систем
Тема 2

8.

Коммуникационное время
Сценарий выполнения системы – множество T
состояний либо событий
Система составляется из взаимодействующих
последовательных процессов
Частичный порядок t t', где t, t' T:
(1)
(3)
t и t' - последовательные шаги выполнения одного
процесса, либо
имеет место акт передачи данных с источником t и
назначением t', либо
между t и t' имеется конечная цепь шагов вида (1) или (2).
Параллельные (не взаимодействующие)
Последовательные (линейно упорядоченные)
Асинхронные (отделимые)
(2)
Выполнение системы – гомоморфизм : T |R
Развертывание системы – отображение c : |T
|T| C, где
C – множество компонентов
Подсистемы

9.

Шаблоны проектирования
распределённых систем
Клиент-сервер:
С = {c
{c, s}
t: c(t) = s t', t": (c
(c(t') = c(t") = c) & t [t
[t', t"]
(интервальное замыкание сценария клиента включает
сценарий сервера)
Многослойная архитектура:
С=
t, t': t < t' ( n: n [c
[c(t), c(t')] ( u: u [t
[t, t'] & c(u) = n))
(отображение c непрерывно в интервальной топологии)
Параллельное выполнение:
С произвольно
t, t': ¬c
¬c(t) = c(t') ¬t
¬t < t' & ¬t
¬t' < t
(сценарий каждого компонента является объединением
компонент связности)

10.

Принципы компонентного
проектирования
Явное описание семантики состояний/событий
Основные понятия:
Компоненты (components)
Связки (connectors)
Конфигурации (configurations)
Ограничения (constraints)
Глубокая детализация процесса взаимодействия
G.port1 G.role1 G.glue G.role2 G.port2
--------- ---------------------------------------------------- ---------С1.port
|
С2.port
|
С1.role
|
С2.role
компонент С1 взаимодействует с С2 посредством связки
G

11.

Языки описания архитектуры
Wright
Концептуальное обогащение CSP
Формализация систем распределённого имитационного
моделирования (стандарт HLA)
Rapide
Глубоко формализованная семантика событий
Верификация обработки транзакций
CHAM
Представление динамики как отклонения от равновесного
состояния
Аналог законов ле Шателье химического равновесия
Моделирование многокомпонентных систем,
подчиняющихся статистическим законам устойчивости
xADL
XML-описания структурных и поведенческих атрибутов
Интеграция моделей компонентов, описанных на
различных языках

12.

Анализ эффективности
распределённых систем
Тема 3

13.

Квалиметрические модели
программных систем
Показатели эффективности программных изделий (ISO9126)
Характер изменения во времени
Характер изменения ресурсов
Квалиметрическое моделирование – определение
значений показателей эффективности на этапе
проектирования
Квалиметрическая модель – зависимость значений
показателей эффективности от параметров окружения
Пример:

14.

Методы оценки эффективности
• Аналитические методы
Составление и решение уравнений динамики
Проблема: отсутствие аналитической теории динамики
программных систем в своем окружении
• Эмпирические методы
Измерение поведения копий, воспроизводящих оригиналы в
малом масштабе
Проблема: отсутствие теории подобия для программных
систем
• Статистические методы
Оценки средних значений показателей, полученных в большом
числе испытаний
Проблема: «плохие» статистические характеристики
поведения программных систем (фрактальное распределение с
бесконечной дисперсией)

15.

Анализ зависимостей
• Представление сценария поведения системы графом,
оснащенным значениями сложности вершин/дуг
• Описание системы как класса сценариев
Помеченные структуры событий
Сети Петри
• Выявление зависимостей по элементам данных
• Информационная зависимость: out in
• Прочие зависимости: in in, out out, in out
• Выделение взаимно независимых подсценариев
(распараллеливание)
• Построение критических путей в графах сценариев
• Вычисление длительности выполнения шагов
(построение гомоморфизма выполнения : T |R)
|R)

16.

Моделирование вычислений
• Отображение вычислительных задач на архитектуру
вычислительных средств
• Редукция бесконечных информационных объектов (таких
как множества чисел) на конечные множества доступных
ресурсов
Арифметика целых чисел по модулю 2n
Арифметика с переполнением
IEEE-754
• Представление вычислительных операций формулами
алгебры логики
Двузначная логика (двоичная арифметика)
Многозначная логика
• Оценка сложности формул по длине (количеству
базисных операций)
• Оптимизация формул алгебры логики

17.

Статистические методы теории
очередей
• Вероятностная модель обмена данными
• Представление функционирования системы
совокупностью последовательных стохастических
потоков запросов между компонентами
• Статистические показатели
– скорость потока запросов
w – количество ожидающих запросов
Tw – время ожидания запроса
Ts – время обработки запроса
• Производные показатели
= Ts – коэффициент загрузки
Tr = Tw + Ts – время жизни запроса
r = Tr – коэффициент использования (формула Литтла)

18.

Статистические методы теории
очередей (продолжение)
• Пуассоновское распределение входных запросов:
• Pr[N
Pr[N(t) = k] = (( t)k/k!)e- t
• r = /(1 – )
• Пример:
Если = 1/3, Ts = 0,6, то Tr = Ts/(1 – ) = Ts/(1 – Ts) = 0,75
• Если входные потоки запросов распределены по Пуассону,
то все потоки в системе будут распределены по
Пуассону (теорема Джексона)
• На практике потоки данных в сетях имеют фрактальное
распределение
a–Hx(at)
at) статистически подобно x(t), где H – параметр Хёрста
r = 1/(2(1 – H))/(1 – )H/(1 – H)
совпадает с Пуассоновским случаем при H = ½, но значительно
больше при H 1

19.

Интеграция данных
Тема 4

20.

Семантическая иерархия данных
Уровень
Формат
семантическ
ой иерархии
Представлен
ие
Управлени Пример
е
языка
доступа
Данные
(data)
Поток байтов
Значение
переменной
Файл
Регулярн
ые
выражени
я
Информация
(information)
Типизированна Схема
я структура
данных
База
данных
SQL
Знания
(knowledge)
Правило
вывода
Экспертн
ая
система
Prolog
Онтология

21.

Шаблоны интеграции распределённых
хранилищ данных
• Склад (warehouse)
Репликация в единое хранилище
Пример: учетная система регионального масштаба
Достоинства: непосредственный доступ
Недостатки: большой объем, задержка актуализации
Общий интерфейс доступа (медиатор) к разнородным базам
Пример: распределённая электронная библиотека
Достоинства: отсутствие копий, актуальность
Недостатки: высокий уровень готовности каждой базы
Унификация данных согласно онтологии предметной области
Пример: глобальный атлас наук о Земле
Доступ к данным в соответствие с моделью рабочих
процессов по их сбору и обработке
Пример: European datagrid (ЦЕРН)
• Федерация (federation)
• Семантическая интеграция (semantic integration)
• Интеграция, основанная на модели (model-based
integration)

22.

Метаданные
• Структурированное описание структуры
Схема данных (диаграмма «сущность–связь»)
XML схема (ранее DTD)
Аннотация документа
Список прав доступа (ACL)
Язык описания интерфейса программного доступа (IDL, WSDL)
Участник [процесса создания] (contributor)
Область (coverage)
Создатель (creator)
Дата (date)
Описание (description)
Формат (format)
Идентификатор (identifier)
Язык (language)
Издатель (publisher)
Ссылка (relation)
Права (rights)
• Стандарт Dublin core

23.

Semantic Web
• XML
• RDF
Язык описания метаданных web-ресурсов
Базовая единица языка – ресурс (URI)
Основная конструкция – тройка <субъект, объект, предикат>
Тройка также является ресурсом
Правила вывода троек задаются схемой (RDF Schema)
• OWL
Формальное описание онтологий предметных областей
(онтология – совокупность терминов и отношений, вытекающих из
определений)
Обогащение языка RDF понятиями первого порядка
Классы, свойства, отношения
Встроенные типы данных (число, строка и т.д.)
Перечислимые классы
Свойства отношений (функциональность, транзитивность и
т.д.)
Дедуктивный вывод свойств (дескриптивная логика)

24.

Организация совместной
работы ресурсов
Тема 5

25.

Рабочие процессы
• Организация программных, человеческих и других
ресурсов для выполнения общей функции
• Структурная модель: преобразование входных данных
(input) в выходные (output) под управлением (control) при
помощи механизма (mechanism)
• Событийная модель: асинхронный поток событий между
обработчиками
• Формальная модель: сеть Петри определенного вида
Наличие завершающего состояния
Все переходы достижимы

26.

Управление ресурсами предприятия
(АСУП)
• Цепь поставки (business-to-business)
Планирование
Склад
Логистика
Отбор поставщиков
Маркетинг
Продажи
Обслуживание
Настройка
Предметно-ориентированные функции (MES)
Финансы
Юридическая поддержка
Кадры
Поддержка принятия управленческих решений
• Взаимодействие с клиентами
• Управление производством
• Администрирование

27.

Шаблоны проектирования рабочих
процессов
• Основные шаблоны
Последовательность
Распараллеливание
Синхронизация
Исключающий выбор
Схождение
Множественный выбор
Синхронизирующее схождение
Множественное схождение
Дискриминатор
Объединение «N из M»
Цикл
Завершение процесса
Клонирование действия
Интерливинг
Отмена
• Дополнительные шаблоны
• Структурные шаблоны
• Прочие шаблоны

28.

Языки управления рабочими
процессами
Язык
Разработч
ик
Формат
Поддержка
подпроцесс
ов
Поддержк Описание
а доп.
сценариев
шаблонов выполнени
я
SADT SofTech
Диаграммны Вложенност Нет
й
ь блоков
Невозможн
о
COS
A
Диаграммны Привязка
й,
произвольн
текстовый ого графа
Есть
Возможно
XPDL WfMC
XML
Частично Невозможн
о
BPEL IBM +
Microsoft
XML,
Вложенност Частично Возможно
диаграммны ь блоков
й
Transflow
Привязка
произвольн
ого графа

29.

Интеграция ресурсов
реального времени
Тема 6

30.

Реализация требований реального
времени
• Время реакции на запрос не должно превышать
установленного порога
• Виды требований реального времени
Мягкое: нарушение приводит к ухудшению удобства
Жёсткое: нарушение равносильно отказу
Системы управления (физические процессы): 10-8-10-3 с
Мультимедиа (биологические процессы): 10-3-10-1 с
Информационный обмен (когнитивные процессы): 10-1-102 с
Циклическая обработка входящих запросов
Реактивная модель:
Периодическая модель:
• Шкала ограничений реального времени
• Архитектура систем реального времени
запрос обработка воздействие
тик_таймера сбор обработка воздействие

31.

Распределённые системы реального
времени
• (Почти) автономные узлы реального времени,
соединённые сетью (возможно, также реального
времени)
• Количество узлов может быть ограничено пропускной
способностью сети
• Примеры
Встроенная система управления автомобилем
SCADA
• Интерфейсы узлов
Интерфейс реального времени (к внешнему миру)
Интерфейс интеграции (к другим узлам)
Интерфейс конфигурирования (к управляющему воздействию)
• Часто требуется единое астрономическое время на всех
узлах (СОЕВ)

32.

Измерительные сети
Стандарт IEEE-1451 (1997 г.)
Базовый уровень крупномасштабных распределённых
информационно-измерительных систем
Измерительные устройства обладают «интеллектом»
(Smart Transducers)
Память устройства и набор его конфигурационных
параметров имеют фиксированный формат доступа
(Transducer Electronic Data Sheet)
Программные узлы (Network Capable Application Processors)
объединяются с устройствами и между собой в
произвольные графы
Взаимодействие программных узлов происходит согласно
шаблонам «клиент-сервер» или «издатель-подписчик»
Архитектура NCAP:
Драйвера (Transducer Interface Modules)
Модули управления драйверами (Transducer blocks)
Модули обработки (Function blocks)

33.

Верификация требований реального
времени
• Тестирование
Функциональное
Покрывающее
Имитационное
Нагрузочное
• Проверка условий корректности во время исполнения
• Аудит процесса разработки (ISO-9001)
• Структурный анализ (определение длительности
наихудшего сценария)
Анализ зависимостей
Имитационное моделирование
• Формальные методы (временна
(временная модальная логика)
• Компьютерный анализ (model checking)

34.

Синхронный подход
Моделирование систем реального времени следующего
вида:
Дискретное время
Конечные вычислительные процедуры в фиксированной конечной
памяти
Детерминированная конкуренция
Язык Lustre
Моделирование потоковой обработки данных
Периодическая модель архитектуры
Переменные – типизированные потоки (бесконечные
последовательности значений на различных шагах выполнения
системы)
a = <a0, a1, …>
Каждое значение определяется в точности один раз явным
вычислением
Пример – счетчик шагов:
nat = pre(
pre(nat)
nat) + 1,
где
pre(<
a0, a1, …>) = <nil
pre(<a
<nil,, a0, a1, …>

35.

Синхронный подход (продолжение)
• Язык Esterel
Моделирование многопроцессной обработки
Реактивная модель архитектуры
Вычисление делится на параллельные потоки: T1 || T2
Потоки синхронизируются сигналами: await S; emit S
Выполнение потоков управляется сигналами:
suspend <motion> when Stop
Время – периодический сигнал
• Язык Signal
Объединение возможностей Lustre и Esterel

36.

Агентные и автономные
системы
Тема 7

37.

Требования к программным
агентам
• Стандарты FIPA (Foundation for Intellectual Physical
Agents)
• Требования
Способность действовать для достижения заданной цели
Способность к обучению
Способность к рассуждению
Автономность (самодостаточность)
Коммуникативность
Коллаборативность (назначение ролей и соблюдение ролевых
ограничений)
Мобильность (миграция по аппаратным узлам)
• Классы приложений
Информационные агенты: адаптивный поиск, электронный
секретарь
Интерфейсные агенты: адаптация интерфейса под
предпочтения индивидуальных пользователей
Мониторинговые агенты: антивирусное ПО

38.

Мультиагентные системы
• Интеграция на основе коллаборативности
• Технологическая платформа поддержки агентов
Создание агентов
Удаление
Ведение списка
Поиск
Цель сообщения
Отправитель
Получатель
Онтология предметной области сообщения
Метаданные (ср. Dublin Core)
Содержимое сообщение
Пример сообщения:
• Взаимодействие путем обмена сообщениями
• Язык взаимодействия агентов
INFORM, catalog@http://lib.ru, ivanov@http://mail.ru,
literature, Prolog, author(Dostoyevsky, Idiot)

39.

Принципы организации
агентов
• Цели сообщений
INFORM (сообщение об истинности утверждения)
QUERY-IF (запрос об истинности утверждения)
QUERY-REF (запрос на получение ресурса)
CFP (запрос на получение предложений)
PROPOSE (предложение)
ACCEPT-PROPOSAL (принятие предложения)
REJECT-PROPOSAL (отклонение предложения)
REQUEST (запрос на выполнение действия)
SUBSCRIBE (подписка на источник информации)
Логический вывод по внутренней модели мира
Ограничение по мощности машины вывода
Реакция на внешние источники
Ограничение по многообразию сценариев реагирования
Комбинация ассоциативных и реактивных агентов
• Ассоциативные агенты
• Реактивные агенты
• Гибридные агенты

40.

Автономные вычисления
• Цель: нивелировать выход уровня сложности
программных систем за рамки когнитивных
возможностей человека
• Разработчик: IBM, 2000
• Подход: децентрализация функций между реактивными
компонентами
• Рабочий цикл: автоматический непрерывный мониторинг
и регулирование параметров качества
• Класс систем: гибридная агентная система
• Приложение: автоматизация рутинной работы по
эксплуатации программных систем
• Реализация: Autonomic Computing Tool Kit
• Архитектура
Ресурс + менеджер
Интерфейс ресурса: сенсоры и эффекторы
Рабочий цикл менеджера:
Мониторинг анализ планирование воздействие

41.

Автономные вычисления
(продолжение)
• Уровни автономности (autonomy maturity model)
Базовый: ручная эксплуатация
Контролируемый: автоматизация сбора данных
Прогностический: + автоматизация анализа
Адаптивный: + автоматизация воздействия
Автономный: полная автоматизация эксплуатационного цикла

42.

Пользовательский
интерфейс распределённых
систем
Тема 8

43.

Принципы организации единой точки
доступа
• Требования к порталам
Интегрированная точка доступа пользователей к
распределённым разнородным ресурсам
Однократная аутентификация для входа во все ресурсы (single
sign-on)
Эффективность: мягкое реальное время
Удобство: пользовательский интерфейс стиля Web
Сопровождаемость: масштабируемость по составу доступных
ресурсов
• Функции порталов
Управление внешним видом
Управление содержанием
Управление пользователями
Поиск ресурсов
Ведение каталога ресурсов
Интеграция приложений
Карта распределения ресурсов
Виртуальные сообщества (социальные сети)
Корпоративный документ (электронная Россия)
Высокопроизводительные вычисления (научные проекты)
• Классы задач

44.

Архитектура портала
• Логическая архитектура: 3-слойная (3 layers)
Интегрируемые ресурсы
Модули формирования и обработки видеокадров
Пользовательский интерфейс
• Физическая архитектура: 3-опорная (3 tiers)
Узлы развёртывания интегрируемых ресурсов
Сервер портала
Пользовательские рабочие станции
• Шаблон «Model-View-Controller»
Модель: управление визуализацией
Представление: пользовательский интерфейс
Контроллер: передача пользовательского ввода в модель
«2½»-слойная архитектура
• Прочие шаблоны
Request Processor
Application Controller

45.

Технологические подходы к созданию
порталов
• Контейнерный подход: портал как контейнер
презентационных компонентов, опосредующих
интегрируемые ресурсы
• Обработка каждого пользовательского запроса по
отдельности
• Функции контейнера
Предварительное резервирование системного окружения
(например, пул соединений с БД)
Управление жизненным циклом компонентов
Управление транзакциями
Авторизация и аутентификация
IBM WebSphere
BEA WebLogic
Постоянная готовность к пиковой нагрузке
Высокая стоимость «пустого» портала
• Реализация: J2EE (EJB-компоненты + Web-компоненты)
• Примеры
• Недостатки

46.

Технологические подходы к созданию
порталов (продолжение)
• Канальный подход: портал как система сбора и
маршрутизации цифровых сущностей
• Документо-ориентированное управление видеокадрами и
пакетами пользовательского ввода на базе SemanticWeb
• Обработка целостных сценариев взаимодействия
пользователей с ресурсами
• Логические каналы с потоковой обработкой
Мультиплексирование
Демультиплексирование
Маршрутизация в зависимости от содержания
Перевод (например, на различные языки)
Журналирование
• Аналогия: сеть с коммутацией каналов (контейнерный
подход – сеть с коммутацией пакетов)
• Адаптивное использование системного окружения
• Гибкий технологический процесс создания портала

47.

Защита информации в
распределённых системах
Тема 9

48.

Моделирование защиты информации
• Виды моделей
Модель угроз
Модель защит
Матрица контроля доступа
Карта доверенных узлов
• Механизмы защиты
Шифрование
Идентификация
Аутентификация
Авторизация
Аудит

49.

Технологические подходы к
обеспечению защиты
• Операционные системы и СУБД: управление
пользователями
Пароли
Цифровые сертификаты (x.509)
• Сети: шифрование во время передачи
Secure Socket Layer
IPSec
Secure/Multipurpose Internet Mail Extensions
• Среды исполнения приложений: «песочница» (sandbox)
• Защищённые участки сети: межсетевой экран (firewall)
Разрешение установления сессий по адресам и протоколам
Фильтрация опасных запросов
Трансляция сетевых адресов
Ограничение пропускной способности низкоприоритетных
сессий
Журналирование и анализ сессий

50.

Средства управления защитой
• Цифровой сертификат – публичный ключ субъекта,
заверенный электронной подписью независимого
доверенного центра
• Доверенная группа субъектов – группа получателей
приватного ключа, расширяемая только при условия
консенсуса всех участников
• Делегирование привилегий – предоставление внешним
сущностям прокси-разрешения, содержащего привилегии
субъекта (полные или частичные)
• Безопасное управление данными защиты – Secure
Association Context Management (Generic Security Service
API)

51.

Примеры средств комплексной
защиты распределённых систем
• Kerberos
Генерация идентификатора права доступа субъекта (ticket) на
каждую сессию
Генерация сессионного приватного ключа по идентификатору
• SESAME (Secure European System for Application in a Multivendor Environment)
Сервер аутентификации: хранение приватных ключей в
специализированной БД (Security Management Information Base)
Сервер атрибутов привилегий: выдача сертификатов
атрибутов привилегий
Сервер распространения ключей (опциональный): выдача
сессионных приватных ключей
Клиент доступа к аутентификации и привилегиям:
программное обеспечение для клиентов
• SET (Secure Electronic Transactions)
Раздельное шифрование содержательных и платежных данных
заказов в системах электронной коммерции

52.

Технологии Grid
Тема 10

53.

Организация Grid-систем
Технология Grid: интегрированная технология
разработки многоаспектных крупномасштабных
динамических распределённых систем «под ключ»
Класс решаемых задач: однородная обработка
однородных потоков информации
Пример: переборные (brute-force) вычислительные
алгоритмы
Принцип работы Grid-системы: бесконечное
клонирование небольшого числа функциональных
компонентов, динамически развёртываемых на
изменяющейся неоднородной аппаратной
инфраструктуре, связанной глобальной сетью
Управление: непрерывный процесс принятия решений о
динамическом развёртывании исходя из потребностей
задачи и возможностей аппаратного уровня в целях
максимизации эффективности

54.

Условия динамического
развёртывания
• Поддержка большого количества компонентов
При 106 ресурсов даже ведение каталога требует
высокопроизводительной распределённой СУБД
• Поддержка географически распределённых компонентов
Глобальная сеть не может обеспечить коммуникации в
реальном времени
• Поддержка высокой частоты изменений состояния
объектов
При 106 ресурсов с коэффициентом готовности 99% 104
ресурсов не функционируют в любой момент времени
• Поддержка технически неоднородных узлов
Универсальная платформа исполнения машинно-независимого
байт-кода так и не создана (конкурирующие платформы – Java
и .Net)
• Поддержка административной разобщённости
Политики доступа могут противоречить функциональным
требованиям

55.

Классификация Grid-систем
Класс Gridсистем
Подход к решению
задач
Пример
задачи
Пример
Gridсистемы
Вычислительны Расширение
е
аппаратной базы
вместо оптимизации
алгоритмов (P
(P = NP ?)
Расшифровка
генома
CEPAR
Ориентированн
ые на данные
Сбор и фильтрация
больших массивов
данных
Обработка
European
эксперименто Datagrid
в в физике
высоких
энергий
Коммуникационн
ые
Управление сложными
интенсивными
потоками данных
Международн Access
ые
Grid
мультимедиаконференции
Вертикально
интегрированны
е
Автоматизация
исследования целой
предметной области
Разработка
алгоритмов
анализа
Data
Mining
Grid

56.

Этапы развития Grid-технологий
• Первая демонстрация – I-WAY (1995 г.)
Конференция SuperComputing-95
Развёртывание вычислительной задачи из области ядерной
физики на 17 узлов
• «Домашние» Grid-системы с добровольным подключением
Распознавание структуры белков (Folding@Home)
Поиск радиосигналов внеземных цивилизаций (SETI@Home)
Расшифровка RSA-64 (2002 г., более 300 тыс. рабочих станций)
• Интеграция аппаратных ресурсов
Платформа Globus Toolkit v2
Система Condor
• Сервисная архитектура
Open Grid Service Architecture
• Адаптивные и автономные Grid-системы
Semantic Grid
Самоконфигурирование и самовосстановление

57.

Проектирование Gridсистем
Тема 11

58.

Архитектура Grid-систем
• Аппаратный уровень (fabric)
Высокопроизводительные компьютеры
Мощные хранилища данных
Высокоскоростные сети передачи данных
Универсальные сетевые протоколы (TCP/IP)
Средства однократной аутентификации (сертификаты x.509)
Метаданные ресурсов
Мониторинг загрузки узлов
Средства автоматического развёртывания приложений
Динамический поиск ресурсов
Составление и выполнение расписаний работы ресурсов
Портал пользователя Grid-системы
Среды решения задач (problem solving environments)
• Уровень связи (connectivity)
• Уровень ресурсов (resource)
• Уровень интеграции (collective)
• Уровень приложений (applications)

59.

Формальный подход к
проектированию Grid-систем
• Абстрактные машины состояний
Состояния – многосортные алгебры
Переходы – изменения значений функций, состава основного
множества
• Основные сорта алгебраического представления Gridсистем
Приложения: App
Процессы: Proc
Ресурсы: Res
Узлы: N
Bool = {true
{true,, false}
false}
• Основные функции
Потребность процесса в ресурсе: req : Proc Res Bool
Использование ресурса процессом: uses : Proc Res Bool
Отображение процесса на узел: map : Proc N
Принадлежность ресурса узлу: BelongsTo : Res N Bool

60.

Спецификация алгоритма
динамического развёртывания
• Алгоритм статического развёртывания
if ( p Proc, r Res): req(
req(p, r) & BelongsTo(
BelongsTo(r, map(
map(r))
then
uses(
uses(p, r) := true
req(
req(p, r) := false
• Абстракция ресурса
Атрибуты ресурсов и узлов: сорт Attr
Функция вычисления атрибута: attr : Res + N Attr
Функция проверки совместимости: compat : Attr Attr Bool
Разделение абстрактных и физических ресурсов: Res = ARes +
PRes
Функция отображения абстрактных ресурсов: mapres : Proc
ARes PRes
if ( p Proc, ar ARes): req(
req(p, ar)
ar) & mapres(
mapres(p, ar)
ar) = undef
then
choose r PRes: compat(
compat(attr(
attr(ar),
ar), attr(
attr(r))
mapres(
mapres(p, ar)
ar) := r

61.

Спецификация алгоритма
динамического развёртывания
(продолжение)
• Абстракция пользователя
Пользователи: сорт U
Функция определения пользователя процесса: user : Proc U
Функция аутентификации: CanLogin : U N Bool
Функция авторизации: CanUse : U Res Bool
Функция выбора пользователя по умолчанию: handler : PRes
Proc
Функция отображения пользователей: usermap : Proc PRes U
let r = mapres(
mapres(p, ar)
ar)
if ( p Proc, ar ARes): req(
req(p, ar)
ar) & r != undef & CanUse(
CanUse(user(
user(p), r)
then
if handler(
handler(r) = undef
then
choose u U: ( n N) BelongsTo(
BelongsTo(r, n) CanLogin(
CanLogin(u, n)
usermap(
usermap(p, r) := u
else
usermap(
usermap(p, r) := user(
user(handler(
handler(r))

62.

Спецификация алгоритма
динамического развёртывания
(продолжение)
• Алгоритм динамического развёртывания
if ( p Proc, ar ARes): req(
req(p, ar)
ar) & usermap(
usermap(p, mapres(
mapres(p, ar))
ar)) != undef
then
uses(
uses(p, mapres(
mapres(p, ar))
ar)) := true
req(
req(p, ar)
ar) := false
• Обогащение модели
Жизненный цикл процесса: сорт LC = {starting
{starting,, waiting,
waiting, running,
running,
terminated},
terminated}, функция status : Proc LC
Межпроцессные коммуникации: сорт сообщений M, атрибуты
from,
from, to : M Proc и т.д.

63.

Реализация Grid-систем
Тема 12

64.

Технологические подходы к созданию
Grid-систем
• Основные аспекты Grid-систем
Переносимость
Обнаружение компонентов
Производительность
Устойчивость к сбоям
Защита от несанкционированного доступа
• Механизмы реализации Grid-систем
Разделяемое состояние (Linda)
Обмен сообщениями (MPICH-G2)
Удалённый вызов процедур (GridRPC)
Точечные взаимодействия (JXTA)
Распределённые объекты (CORBA)
Web-службы (Globus Toolkit v3)
Управление рабочими процессами (BPEL)

65.

Платформа Globus Toolkit
• Управление ресурсами
Grid Resource Information Protocol
Grid Resource Registration Protocol
Monitoring and Discovery Services (LDAP)
Grid Resource Access and Management (GRAM)
• Защита от несанкционированного доступа
Grid Security Infrastructure (x.509)
• Передача больших массивов данных
GridFTP
Globus Replica Management

66.

Дополнительные средства
• Поддержка Grid-систем, ориентированных на данные
Grid Data Management Pilot
Global Access to Secondary Storage
Storage Resource Broker + Metadata Catalog
• Порталы пользователей Grid-систем
Grid Portal Development Kit
GridPort
• Мониторинг загрузки узлов и каналов
Grid Monitoring Architecture
NetLogger
• Управление пакетными заданиями
Portable Batch Scheduler
• Адаптивное управление ресурсами
Agent-based Resource Management for Grid Computing
G-commerce

67.

Открытая архитектура Grid-служб
• Инкапсуляция ресурсов и процессов в службы (services)
• Реализация брокера ресурсов как организатора
совместной работы служб (services orchestrator)
• Поддержка метаданных динамических служб с
состояниями (модификация WSDL)
• Интерфейс GridService
• FindServiceData()
• SetTerminationTime()
• Destroy()
• Интерфейс создания служб Factory
• CreateService()
• Интерфейсы поддержки уведомлений
• NotificationSource
• NotificationSink
• Идентификация и адресация служб
GridServiceHandle
GridServiceReference
FindByHandle()

68.

Комплексирование
крупномасштабных
распределённых систем
Тема 13

69.

Принципы комплексирования
программных систем
• Комплексирование компонентов – неразрушающая
адаптация к совместному функционированию
• Ключевой фактор многократного использования
компонентов
• Критерии оптимальности
Минимизация межкомпонентных связей
Максимизация внутрикомпонентных связей
• Подходы к комплексированию
Статическое: редактирование связей (link)
Динамическое: подгрузка библиотек, взаимодействие
• Математическая база
Теория категорий (система – копредел диаграммы, состоящей
из компонентов и межкомпонентных связей)
Мереология (математическая теория отношения «частьцелое»)

70.

Принципы комплексирования
программных систем (продолжение)
Техника
комплексирования
Пример
(ООП)
Единица
многократн
ого
использован
ия
Тип
шаблона
Действие
Встраиван Операт EJB
ие
ор new
компонент
а
Массив
данных
Создающие
шаблоны
Изменени
е целого
Подстанов Наслед
ка
о-вание
Webпрокси
Библиотека
Поведенческ Изменени
ие шаблоны е части
Взаимодействие
MOM
Приложение
Структурн Склеиван
ые шаблоны ие
Вызов
метода
Пример
(распределённы
е
систем
ы)

71.

Аспектно-ориентированный подход
• Разделение классов задач (concerns), пересекающих
границы единиц модульной архитектуры
• Разработчики: Kiczales и др., 1997
• Примеры аспектов
Защита информации
Пользовательский интерфейс
Нефункциональные характеристики качества по ISO-9126
Статическая: генерация исходного кода приложения по
исходным кодам аспектов и спецификациям точек соединения
Динамическое: проверка предикатов, идентифицирующих точки
соединения, во время исполнения и динамическая подгрузка
присоединяемых аспектов
• Выделение точек соединения (join points)
• Подходы к композиции аспектов (weaving – сплетение)
• Пример технологии АОП: AspectJ
• АОП в распределённых системах
Аспекты – интегрируемые ресурсы
Сплетение – интеграция

72.

Аспектная декомпозиция
распределённых систем
технологического управления
• Информационная модель (онтология предметной
области объекта управления)
• Интерфейс к слою реального времени (IEEE-1451)
• Математическое обеспечение (Grid)
• Мониторинг объекта и системы (автономные
вычисления)
• Пользовательский интерфейс (портал)
• Информационный обмен (электронный документооборот)
• Модель защиты (однократная аутентификация)
• Метрологическая аттестация измерительного слоя:
= model + method + tool + conditions + user

73.

Технологический процесс
разработки
крупномасштабных
распределённых систем
Тема 14

74.

Инженерия предметной области
• Ведение множества проектов, объединённых общей
целевой задачей и общим технологическим подходом
Покрытие маркетинговой ниши (линейка продуктов)
Комплексирование крупномасштабной системы
• Технологический цикл инженерии предметной области
(domain)
Идентификация предметной области
Моделирование предметной области
Проектирование предметной области
Реализация предметной области
• Технологический цикл инженерии приложений
(applications) – разработка частных приложений

75.

Инженерные принципы разработки
• Выполнение требований открытости компонентов и
протоколов (неограниченное масштабирование)
• Привлечение специализированных средств и технологий
моделирования, программирования и комплексирования
систем (неограниченное распределение)
• Ведение гибкого технологического цикла разработки
(неограниченная динамичность)
• Обеспечение высокой степени переносимости
программных компонентов (неограниченное
развёртывание)
• Применение стандартных форматов представления
данных и протоколов информационного обмена
(неограниченная коллаборативность)

76.

Особенности моделирования
• Объединённая фаза анализа и проектирования
• Результаты
Техническое задание
Технический проект
Рабочая документация
Организационная
Архитектурная
Аспектная
Построение онтологии предметной области
Формализация модели качества
Извлечение схемы БД из понятий предметной области
Моделирование рабочих процессов
Выбор открытых коммуникационных протоколов
Выявление точек изменения системы
Многомерная декомпозиция

77.

Особенности реализации и
эксплуатации
• Принципы реализации
Максимизация степени многократного использования
компонентов
«Обёртывание» унаследованных приложений
Задействование готовых компонентов (лучше всего с
открытым исходным кодом)
Применение разнородных программных технологий по
необходимости
• Принципы эксплуатации
Мониторинг: сбор событий, диагностика компонентов во время
выполнения
Анализ: фиксация и предсказание сбоев
Планирование: определение действий по восстановлению после
сбоев
Воздействие: восстановление после сбоев
Функциональные возможности
Надежность
Практичность
Эффективность
Сопровождаемость
Мобильность (переносимость)
• Характеристики качества (ISO-9126)

78.

Список основной литературы
• Воеводин В.В., Воеводин Вл.В. Параллельные
вычисления. СПб.: БХВ-Петербург, 2002.
• Ковалёв С.П. Архитектура времени в распределенных
информационных системах // Вычислительные
технологии. Т. 7, №6, 2002. С. 38–53.
• Столлингс В. Современные компьютерные сети. 2-е
изд. СПб.: Питер, 2003.
• Таненбаум Э., ван Стеен М. Распределенные системы.
Принципы и парадигмы. СПб.: Питер, 2003.
• Sotomayor B. The Globus Toolkit 3 programmer's tutorial.
The Globus Alliance, 2004.