Проблемы информатики Базовая кафедра ФУПМ МФТИ Теоретическая и Прикладная Информатика заведующий д.ф.-м.н., проф. А.Тормасов 2013

О чем эта лекция Представлены направления деятельности и работы сотрудников новой базовой кафедры «Теоретическая и прикладная информатика» В основном, представлены научные направления Базовые организации: - ОС, системы виртуализации Acronis- резервное копирование, данные Runa - венчурный фонд (Сколково/etc) другие организации (инвестируемые Руна и т.д.)

Достижения 16 кандидатских диссертаций 1 докторская Более 100 патентов США и других стран В штатах базовых организаций более 20 кандидатов и докторов наук несмотря на то, что это коммерческие организации! Базы – резиденты Сколково Финансовые успехи компаний

Мощная основа 800+ сотрудников по всему миру 500+ партнеров, включая Microsoft, Apple, Intel, AMD, Dell, HP и IBM 100+ патентов на уникальные технологии Инвесторы: Intel Capital, Bessemer Ventures, Almaz Capital Partners Доказательства успеха В числе 100 крупнейших софтверных компаний мира 12+ миллионов пользователей в 125 странах 1 в сфере ПО для провайдеров облачных вычислений Лучший разработчик виртуализации под Mac 4 Надежная репутация Parallels в мире

Сделано в России Parallels входит в четверку крупнейших софтверных компаний с центром разработки в России (Kaspersky, Acronis, Parallels, АBBYY) Единственная компания в России с экспертизой в области ПО для провайдеров «облачных» вычислений Сознательное размещение R&D центра на территории РФ (более 300 сотрудников в Москве и в Новосибирске) Конкурентоспособные на мировом рынке софтверные продукты Основана выпускниками лучших ВУЗов страны: МФТИ, НГУ, МГУ и академии ФАПСИ 5

Acronis - основные продукты Резервное копирование и восстановление информации: –Семейство Acronis Backup&Recovery (для бизнеса) –Acronis True Image Home (для дома) –Acronis Online Backup Управление жесткими дисками: –Acronis Disk Director. 6

ФОНД размером 70 млн. долларов - инвестиции в посевную стадию, старт-ап и стадию роста – во всех случаях как первый институциональный инвестор. КОМАНДА ПРЕДПРИНИМАТЕЛЕЙ с успешным опытом развития бизнеса – более 20 существенных сделок, несколько миллиардов долларов созданной капитализации. УНИКАЛЬНЫЙ НАБОР КОМПЕТЕНЦИЙ – старт-ап, развитие и масштабирование бизнеса, международное развитие, инвестиции ПОДДЕРЖКА от команд Параллелз, Акронис, United Internet, Акуматика, Софтлайн, Венчурных Партнеров и Советников ОСНОВНАЯ СТРАТЕГИЯ – разработка ПО в России и СНГ, развитие бизнеса на международных рыках – США, Европа, Юго-Восточная Азия. ТЕХНОЛОГИЧЕСКИЙ ФОКУС на разработке Программного Обеспечения, Онлайн-сервисах, Интернет (включая Digital Media), Мобильных приложениях – областях быстрого роста. |7|7 Runa Capital: КОРОТКО О…

Студенческие исследовательские центры Существуют с 1999 г Дополнительное финансирование НИР студентов стипендии за выполненную работу (до 24 тр/мес) Летние работы (больше времени на НИР) Лучший способ попасть на кафедру Сейчас их несколько МФТИ, МГУ, НГУ, Академический Университет при СПб Физтехе

Поддержка студенческих команд ImagineCup/Microsoft Команды Физтеха – 1 место и 2 место в мире за последние годы (финалы в Японии и Бразилии) Набраны новые команды Прошли в Российский финал Мировой финал 2013 – в Санкт Петербурге Проекты этого года Обучение робототехнике на реальном роботе

Интернационализация Начали обучение на англ языке Glauber Costa – бывший сотрудник RedHat, работает ведущим инженером в Parallels, Msk курс по доп главам операционных систем возможно, первые в МФТИ внутри МФТИ) Проект Университет Иннополис (Казань) Установлены связи с Университетом Карнеги Меллон- #1 в Software Engineering CS – SE отделение и другие направления Набор магистров для двойного диплома CMU в 2013 году (годовая проф. программа)! Проф. Д. Гарлан прочтет лекцию по SE в МФТИ 10 апреля Веб каст по средам 18-00

Направления исследований кафедры Виртуализация ОС и компьютеров Групповые иерархические планировщики «живая миграция» процессов ОС и виртуальных машин без их остановки Виртуализация Android (см соц сети!) Облачная инфраструктура(cloud storage) Модели и технологии распределенных отказоустойчивых хранилища данных Системы безопасности распределенных децентрализованных хранилищ новые параметры и типы SLA

Направления… Разработка и оптимизация «сверхпроизводительных» программ на разделяемой памяти Моделирование поведения процесса потребления ресурсов Модели и измерение производительности Поиск неразрешенных условий гонки в программах Формальные модели условий гонки создание новых практических неблокирующих алгоритмов

Направления… Оптимизация хранения данных Дедупликация Улучшение надежности хранения данных Защита информации в виртуальных машинах Непрерывная защита данных Защита данных в распределенном окружении Бизнес инфраструктура с точки зрения защиты данных

Направления… Упаковка приложений в облачный формат (APS – Applications Packaging Standard) Собственные протоколы передачи данных Собственные видео кодеки Разработка собственного масштабируемого rsync Квантовые алгоритмы (адиабатические) …

15 Распределенная среда управления и хранения данными - основа «облачной инфраструктур» (cloud infrastructure)

16 Мотивация Проблемы современного ПО и сетей, в том числе Интернет (централизация, клиент- серверная модель, сложность, невысокий уровень масштабируемости) Проблемы с интеграцией компьютерных систем (новых аппаратно-программных систем) и новых сервисов Проблема с безопасностью и постоянными нарушениями частной жизни

17 Интересы потребителя Локальные сервисы, обслуживающие запросы пользователя (редактор, игра, организатор и тд) Хранение и доступ к персональным данным Доступ к сетевым информационным источникам Персонализованный обмен информацией с абонентами Обслуживание, независимое от физического нахождения потребителя требуется мобильность сервиса Мобильность пользователя Мобильность вычислительных ресурсов Мобильность данных Независимость сетевого доступа от внешних параметров сервис потребителя = Вычислительные ресурсы + Хранимые данные

18 Идеальная среда пользователя Мобильный сервис (оказывается там где надо и когда надо, следует за пользователем) Безопасный (разграничивает пользователей, делает только то что попросили без побочных эффектов, предоставляет только запрошенное, не разглашает лишней информации) Постоянно существующий/надежный (не зависит от оффлайн-онлайн статуса пользователя и состояния аппаратно-программных ресурсов) Легко расширяется на произвольные новые устройства, предлагая удобные средства управления

19 Состав среды и классификация требований Вычислительные ресурсы («активная» часть) Управляемость Утилизация ресурсов Изоляция Безопасность Доступ к данным («пассивная» часть) Локальное хранилище Удаленные хранилища Базируется на коммуникационной инфраструктуре

20 Доступ к данным: хранилище Легкость выделения пространства Изоляция Разделение Прозрачность Коммуникабельность Легкость наращивания Надежность и доступность

21 Расширяемая среда Легкость добавления и удаления нового объекта – при его подключении вычислительные ресурсы и место для хранения данных входят в общий пул и предоставляются для общего пользования Полная автоматизация – не требуется конфигурирование объекта Не требуется авторизация на подсоединение и отсоединение объекта, то есть это может сделать любой желающий При отсоединении любого объекта функциональные возможности системы практически не меняются Прозрачная интеграция локальных и удаленных объектов и сервисов, виртуализация Встроенная система безопасности, не делающая предположений об уровне защиты подсоединяемого устройства (те не нужна сертификация устройств и серверов)

22 Предложенная технология реализации: виртуализация сервиса Отрыв от немобильных физических ресурсов Мобильность сервиса Требуемая изоляция Динамическое деление и разделение ресурсов одного сервера между сервисами хранилища Отрыв от немобильных физических ресурсов и серверов Независимость адреса от места хранения Требуемая изоляция на уровне хранения Мобильность сервисов директории Мобильность защиты Разделение логического и физического доступа Прозрачность реализации Унификация (независимость сервиса от физического носителя) Легкость замены физического носителя Адрес, не зависящий от физического Мобильность сервиса Запуск любых приложений

23 Состояние технологии виртуализации Virtual Machines – технология виртуализации оборудования существует с 90-х годов (VMware/Parallels/Microsoft) Получила новый толчок с выходом процессоров Intel и AMD с аппаратной поддержкой виртуализации – во всех современных CPU Для промышленного применения существенно наличие не только базовой технологии «эмуляции процессоров» или периферии, но и наличие средств управления и контроля за ресурсами Виртуализация уровня ОС – предложена мною в 1999 году; сейчас включена в практически все комм. ОС. Динамическое разделение серверов на сотни виртуальных разделов Управление ресурсами на лету Миграция разделов Массовое управление Виртуализация хранилища данных – на уровне оборудования

24 Математическое моделирование процесса переноса данных без остановки (онлайн миграция)

Онлайн миграция Разработан алгоритм миграции процессов «на лету», без их остановки (включая «предварительную» миграцию данных) Специально оценивается размер «рабочего набора» страниц процесса, и используется специальная методика для детектирования изменений, происходящих с работающим процессом Математические модели оценки времени завершения, оптимизации объема доставляемых данных и тд, легли в основу одной из диссертационных работ

26 Математические модели процесса потребления ресурсов. Групповое планирование.

27 Возобновляемые (CPU); Невозобновляемые (дисковое пространство); Частично возобновляемые (физическая память). Возможные ограничения: гарантия потребления ресурса в среднем; лимит на потребление ресурса в среднем; лимит на интегральное потребление ресурса. Не всегда можно предсказать поведение процесса (потока) по отношению к потребляемым ресурсам (примерняются «инженерные» алгоритмы) Типы ресурсов ОС

28 Групповое наложенное управление Наложенное управление Встроенные механизмы управления распределяемыми ресурсами операционной системы Группа1Группа2ГруппаN … Процесс 1 1 … Процесс K 1 Процесс 1 2 … Процесс K 2 Процесс 1 N … Процесс K N Влияние уровня ОС Ухудшает точность Ухудшает точность Отсутствие гарантий в худшем случае Отсутствие гарантий в худшем случае Невозможность построить мат. модель нижнего уровня: Использование кешей «Инженерные» алгоритмы планирования («бурст») Обратные связи по ресурсам Внешнее ограничение на ввод-вывод Эффекты ОС

29 Модель двухуровневого управления ресурсами Вводится функция потребления: - j-ый ресурс не потребляется i-ой задачей - j-ый ресурс потребляется i-ой задачей - освобождение j-ого ресурса i-ой задачей N задач M ресурсов. 2-ой уровень управления 1-ый уровень управления (встроенный механизм ОС) 1-ый уровень P1P2 P3 P4

30 Каждой вычислительной задачи соответствуют функции: желаемого потребления R i (t * ), t * - собственное время фактического потребления R i * (t), t – физическое время в системе идеального (SLA) потребления R i ** (t ** ), t** - «идеальное» время Заданы функции преобразования времен: t = F i (t * ) t** = S i (t*) В модели учтены эффекты ОС (DR i ) : где - некоторая «реальная» функция потребления без учета неконтролируемых эффектов операционной системы, Модель двухуровневого управления ресурсами )

31 Модель двухуровневого управления ресурсами a - погрешность управления Перейдем к рассмотрению одного ресурса:, Какие ограничения нужно наложить на систему, чтобы «a» удовлетворяло SLA на интервале T 1 -T 2 ? r j – нормировочный коэффициент Критерий качества управления:

32 - для возобновляемых ресурсов - для невозобновляемых/частично возобновляемых ресурсов Критерии качества управления, удовлетворяющие SLA: где Δ=T 2 -T 1, b –гарантия уровня потребления ресурса, Модель двухуровневого управления ресурсами

33 алгоритм управления временем CPU («жесткое») G i - среднее значение функции фактического потребления R i *. g i – лимит на потребление ресурсов в среднем). G i оцен - оценка функции G i T – текущий момент времени γ – интервал управления - значение в след. момент времени - оцен. значение в след. момент времени,

34 Модель группового двухуровневого управления Группа задач – конечное число задач в ОС, которые удовлетворяют критериям: Все задачи в группе потребляют один и тот же ресурс Задачи можно объединить по признаку, например, принадлежности пользователю. В любой момент времени ресурс может потреблять только одна задача группы Функция потребления группы потоков-потребителей ввода-вывода: - Группа не потребляет ресурс - Группа потребляет ресурс

35 Модель группового двухуровневого управления В модели учитываются эффекты ОС DG(F gr (t gr )) : Аппаратный уровень(элеватор диска работает как одна очередь) Особенности реализации нижнего уровня управления (CPU burst, Starvation) Взаимодействие подкомпонент системы и др. Критерий качества есть интегральное отклонение фактического потребления от идеального: A – допустимая погрешность управления Способы управления: Уменьшение скорости потребления полосы пропускания Замедление или остановка собственного времени

36 Процесс потребления ресурсов потоками ОС t - физическое время [0, ), x – степень завершенности или «внутреннее время» потока [0;1], ρ 1 - доля процессорного времени, область определения [0;1]x[0, ), ρ 2 - доля использования сетевой полосы пропускания, ρ 3 - доля использования полосы пропускания жёсткого диска, u - скорость продвижения потока по внутреннему времени. i=1..m, j=1..n

37 Ограничения, наложенные планировщиком ОС ρ 1 max - производительность процессора (max) T j (x,t) - уровень потребления процессорного времени для j го потока S r (x,t) - требуемый уровень потребления ресурса r без учета огр. T r max (x,t) – текущее ограничение планировщиком ресурса r S * r (x,t) - требуемый уровень потребления с учетом ограничений - учтены ограничения по другим ресурсам

38 Процесс потребления ресурсов потоками ОС Тогда и T j (x,t) = S * r (x,t), то есть

ДЕЦЕНТРАЛИЗОВАННОЕ ОТКАЗОУСТОЙЧИВОЕ ХРАНИЛИЩЕ ДАННЫХ 39

40 Представление данных в хранилище - принципы 1. Добавление и удаление серверов хранилища должно быть полностью добровольным и не требовать разрешений 2. В системе нет ни одного сервера, недоступность которого означала бы невозможность получения какого либо файла данных. 3. Сервис, запрошенный от системы, может быть получен от любого сервера системы 4. В хранилище заложены критерии функционирования, использующие в качестве параметра «количество доступных северов». 5. Система безопасности базируется на «декларируемых» полномочиях 6. В случае любых действий клиента или сервера системы права и возможности других пользователей системы не должны меняться («устойчивость»)

41 Метод регулируемого избыточного хранения (N,K) схема хранения – для любого набора хранимых данных F генерируется набор из N слайсов так, что из любых K из них можно восстановить исходные данные F Каждый слайс имеет размер F/K (с точностью до округления) Все слайсы размещается на N независимых серверах Тогда если из них в какой то момент времени недоступны M N-K, то исходные данные F могут быть восстановлены Система кеширования данных не может дублировать содержимого слайса, а может только создавать новые слайсы (то есть увеличивать N) при необходимости локальной буферизации данных Система кеширования создает новые слайсы непосредственно около серверов, которые часто собирают файл => сервис оказывается там где он потребляется => минимизируется сетевой траффик

42 (N,K) схема разборка и сборка данных

43 (N,K) схема Реализация над полем GF(2 n ) используя неразложимые многочлены (пример для n=16: х 16 + х 5 + х 3 + x + 1) Сведение умножения и деления к сложению и вычитанию, используя таблицы log и alog размером 128кб k-мерное пространство векторов L над полем P Файл представляется как последовательность {l i } L E={e i }, i=1..n, и любые k из E образуют базис в L Для p P (p0) строим вектор (1,p,p 2, … p k ), всего N-1 Любые k - базис (детерминант матрицы - определитель Вандермонда) Сопоставим любому e j из E скалярные произведения {(l i, e j )} Пусть есть произвольные к частей {E i } соотв. {ε i } векторам Тогда квадратная матрица А (k x k) со строками {ε i } имеет А -1 Al i - столбец, состоящий из i-тых элементов всех кусков (S i ) для любого i [1,m]: l i = A -1 S i Оптимизированная матрица А для первых к: A E А -1

44 Клиенты и серверы системы

45 Система хранения Обеспечивает доступ к файлам как к целому (операции GET file/PUT file) Хранит файл как набор упорядоченных по времени транзакций, каждая из которых представляет собой неизменяемый файл Имеет встроенную систему безопасности, гарантирующую доступ к данным только декларировавших соответствующие полномочия клиентов Хранит каждую транзакцию по (N,K) схеме для обеспечения гарантированного доступа в случае сбоев сети или серверов Позволяет легко наращивать систему путем добавки новых серверов, предоставляющих свое пространство для хранения слайсов и обслуживание директорных сервисов

46 Организация хранилища данных

47 Группы серверов системы

48 Переключение сервера с одной группы на другую

49 Размещение и поиск информации на графе Граф упорядочен в группы, куда и размещается информация, есть предпочтительные группа G p и сервер S p для клиента Каждая группа имеет уникальные номера серверов, и (псевдо) уникальный Gid группы, для размещаемого набора файлов также есть некий общий Fid (VEid, e.g.) Алгоритм размещения В группе G p размещаем k кусков на сервере S p и по 1 или более (общим количеством k-1, возможно, в соседних группах) Если текущая выделенная группа не может принять всех кусков, размещаем их в следующей (используя алгоритм упорядочения) Алгоритм поиска Определяем выделенный сервер и, если доступно, забираем к кусков Если сервер занят или необходимого количества кусков нет, забираем с других серверов группы Если их нет в группе, забираем их в следующей (используя алгоритм) Алгоритм упорядочения:

50 вероятностная модель поиска информации Имитационная модель N = 10, k = 5; 20 узлов, не более 1 куска на узле d=3 Вероятность успеха при пересылке пакета соседу взята равной 0.9 Длительность поиска и выбор глубины поиска

51 Оценка накладных расходов типовой пример c k = 5 и размером блока S bs = 4Kb получена оценка величины избыточного траффика для процедуры чтения V ad / S F 1.5% +2.5k%, в тестовой реализации ~14% где первый коэффициент отвечает за время поиска кусков, второй за их доставку Для процедуры записи V ad / S F ( 52 k + 10 ) / S bs + 22 / S F, в тестовой реализации ~6.5% Аналитическая оценка избыточного траффика для постоянно работающей сети где V FE нагрузку на каждую ноду сети V F – объем информации проходящей через сервер в среднем N h – количество серверов в системе - константа, для тестовой реализации ~ 0.15

52 Состояние проекта Студентами и аспирантами сделан работающий макет системы, доступен код для Linux/Windows Реализованы базовые алгоритмы Несколько вариантов размещения и поиска на графе с log сложностью Последнее достижение – адаптирована модель «малого мира» для двухуровневого размещения и поиска информации Разработаны и реализуются алгоритмы реализации системы безопасности без выделенного центра Приглашаем к исследованиям в этой бурно развивающейся области!

МОДЕЛЬ БЕЗОПАСНОСТИ ДЕЦЕНТРАЛИЗОВАННОГО ХРАНИЛИЩА 53

54 Модель безопасности децентрализованной среды Принципиальная децентрализованность Нет «разрешительного центра» Декларируемые полномочия Пользователь «декларирует» набор полномочий на основании которых осуществляется его допуск к данным Перенос защиты с серверов на клиенты Открытая коммуникационная инфраструктура Любой сервер может контролироваться или быть захваченным злоумышленником Отсутствие необходимости сертификации Нет требований к уровню безопасности серверов нет ограничений на присоединение к системе любому желающему «Неулучаемость» при любых воздействиях

55 Безопастность: Следствия Нет разрешающего центра => полномочия базируются на «декларируемости», те каждый желающий декларирует себе полномочия и на их основе получает доступ к системе Система с точки зрения клиента представляет собой «набор банковских ячеек», которые он может себе заказать и получить возможность хранить данные и предоставлять доступ другим пользователям Система безопасности на каждом клиенте должна базироваться на простых аксиомах, из которых можно вывести утверждения о целостности/корректности каких либо данных

56 Модель безопасности: структуры хранения

57 Модель безопасности: доступ к директории

58 Модель безопасности: определения и аксиомы Аксиома1. Компьютеры среды могут взаимодействовать друг с другом через каналы связи. Аксиома2. В среде существует дерево директорий для преобразования текстового пути к файлу в числовой идентификатор файла fid. Содержимое каждой директории хранится в виде файла. Аксиома3. Отказоустойчивость среды обеспечивается за счет хранения частей файла на различных компьютерах системы. Аксиома4. Для каждого пользователя среды существует его «компьютер пользователя». Аксиома5. («Аксиома развертывания системы») На каждом компьютере пользователя есть некоторая априорная информация о среде, необходимая для работы системы и обеспечения контроля доступа в ней. Аксиома6. По идентификатору U_i любого пользователя системы можно получить соответствующие U_i открытые ключи.

59 Математические модели контроля доступа на основе криптографических алгоритмов Контроль доступа типа «чтение» Контроль доступа типа «запись» Список контроля доступа

60 Гарантии выполнения заданных правил разграничения доступа Лемма1. Для того, чтобы пользователь мог прочитать содержимое файла, необходимо и достаточно, чтобы у пользователя было право на чтение данного файла. Лемма2. Право на запись в файл не дает права на чтение. Лемма3. Если у пользователя нет права записи в директорию, содержащую файл, то для того, чтобы записать действительную версию файла, необходимо и достаточно иметь право на запись в данный файл. Лемма4. Если у пользователя нет права записи в директорию, содержащую файл, то право на чтение не дает права на запись в файл. Лемма5. Для того, чтобы при неизменных ключах доступа к файлу дать другому пользователю право чтения данного файла, необходимо и достаточно одновременно: а). иметь право на запись в директорию, содержащую файл; б). иметь право на чтение данного файла. Лемма6. Для того, чтобы при неизменных ключах доступа к файлу дать другому пользователю право на запись в данный файл, необходимо и достаточно одновременно: а). иметь право на запись в данный файл; б). иметь право на запись в директорию, содержащую файл.

61 Гарантии для модели безопасности 2 ….. Лемма10. Если у пользователя нет права записи в директорию, содержащую файл, и он не является владельцем файла, то для того, чтобы записать изменение, необходимо и достаточно иметь право на запись в данный файл. Лемма11. Если у пользователя нет права записи в директорию, содержащую файл, и он не является его владельцем, то право на чтение не дает права на запись в файл. Лемма12.Для того, чтобы при неизменных ключах доступа к файлу дать другому пользователю право чтения данного файла, необходимо и достаточно быть его владельцем. Лемма13. Для того, чтобы при неизменных ключах доступа к файлу дать другому пользователю право на запись в файл, необходимо и достаточно быть его владельцем.

Гомоморфное шифрование для облачных систем 62

63 Может ли компьютер вычислять то, что он не понимает? Как сделать так, чтоб процессор, проводя операции, не знал (и не мог вычислить) операндов? Облачные системы требуют этого! Одна из основных проблем – мои секретные данные в руках администратора облака, который имеет физический доступ к компьютеру и может все подсмотреть! Нетривиальные операции с базами данных Среднее между конкурентами – как вычислить не разглашая? Полный набор операций требует подобного подхода Целочисленные арифметические Булевы Плавающие Отчасти сводится к «булеву сложению и умножению»

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ АЛГОРИТМОВ, РАБОТАЮЩИХ НА РАЗДЕЛЯЕМОЙ ПАМЯТИ 64

65 Задачи Моделирование многопоточных алгоритмов, работающих на разделяемой памяти. Разработка критериев наличия состояний конкурентного доступа к памяти, приводящих к некорректной работе алгоритма. Разработка методики автоматизированного тестирования, определяющей наличие состояний конкурентного доступа к памяти, приводящих к некорректной работе многопоточной программы. Оценка сложности методики автоматизированного тестирования в различных случаях.

66 Анализ инструкций потоков Классификация инструкций: Операции чтения. Поток считывает значение одной из общих ячеек памяти. Обозначение – R. Операции записи. Поток записывает значение в одну из общих ячеек памяти. Обозначение – W. Другие операции. Операции, не входящие ни в один из вышеописанных классов. Обозначение – X. Обозначение, где i – номер общей ячейки памяти, j – номер потока исполнения (например, ). Рассмотрим две операции в разных потоках и. Лемма. Состояние исполнения S после выполнения операций может зависеть от их порядка, если j=k A=R, B=W A=W, B=R A=W, B=W Такие операции – некоммутирующие.

67 Моделирование исполнения двух потоков Два потока исполнения Функция корректности задана в виде, где - состояние исполнения после завершения работы потоков (результирующее состояние исполнения). - начальная вершина, - конечная. Уровень вершины - i+j. Ориентированный путь из начальной вершины в конечную - полный путь. Всего таких путей, а. Лемма. Существует взаимно-однозначное соответствие между вариантами совместного исполнения потоков и полными путями в соответствующем графе совместного исполнения потоков. Дуги, где j=1,…,n+1 - представляют i-ую операцию, выполняемую первым потоком. Дуги, где i=1,…,k+1 - представляют j-ую операцию, выполняемую вторым потоком. Полный путь представляет соответствующий ему вариант совместного исполнения потоков. Граф совместного исполнения потоков – ориентированный граф

68 Классы эквивалентности путей на графе

69 Построение представителей классов

70 Анализ графа совместного исполнения Для анализа достаточно вычислить результирующие состояния исполнения S только для одного представителя каждого из классов. Удалив из графа дуги, которые не входят в полные пути, соответствующие выбранным представителям классов, получим редуцированный граф совместного исполнения потоков. Результирующее состояние исполнения потоков может быть вычислено в неопределенных коэффициентах, двигаясь от начальной вершины графа к конечной. Чтобы определить, возможно ли возникновение неразрешенного состояния гонки, остается проанализировать полученное состояние S с помощью функции корректности p.

71 Методика анализа Построение графа совместного исполнения потоков Поиск эквивалентных путей на графе Анализ представителя каждого из классов эквивалентности с помощью функции корректности p Ответ на вопрос о правильной работе многопоточного алгоритма

72 Изменение ячейки в двух потоках Представление состояния исполнения потоков S в виде совокупности векторов (a,b,c), где a – это значение ячейки памяти, b – считанное значение ячейки, которым оперирует первый поток, c – считанное значение ячейки, которым оперирует второй поток. - модификация считанного значения, c помощью функции f. Первый поток выполняет Второй поток выполняет Начальное состояние исполнения (m,-,-). Функция корректности p – требование константности результирующего состояния исполнения потоков. Число вариантов исполнения 20, анализируемых 4.

73 Транзакционное изменение двух ячеек Функция корректности p – требование константности результирующего состояния исполнения потоков. Число вариантов исполнения 28, анализируемых 4.

Дедубликация данных Acronis 74

75 Дедубликация данных Задача: Построить хранилище данных, обеспечивающее минимальную избыточность R хранения данных D с большого (N>10) числа схожих рабочих станций. R(N,D) Дополнительные условия: Минимизировать потери времени на запись и чтение данных из хранилища Tw, Tr Один узел (Компьютер) должен обеспечивать хранение Umax = 16Тб уникальных данных без потери производительности

Декомпозиция задачи Разбиение на элементы Сравнение элементов Допустимое количество хранимых элементов Основные проблемы Решение Результаты Количественные оценки

Разбиение на элементы Использование блоков переменной длины Дает теоретически наилучший результат по уровню избыточности Но, требует одновременного доступа и к сохраняемым данным, и к хранимым Формат офисных фалойв дает порядка 10-15% LCS дляпрактически одинаковых документов. Использование блоков фиксированной длины Во всех случаях идентифицирует точные коппии файлов Существенно упрощает алгоритм поиска дубликатов На ФС начало файла совпадает с началом блока Теоретическая граница Ложной уникальности хвостов файлов: N*Fs*Sb/2 (N – число машин, Fs – количество одинаковых файлов, Sb- размер блока)

Разбиение на элементы Были выбраны блоки фиксированной длины Sb = 4Kb для дискового бекапа (посекторного) Цель – минимизация ложной уникальности хвостов. Минимальный размер блока современных ФС – устойчивость к процессу дефрагментации. Sb = 256Kb для файлового бекапа (каждый файл разбивается на блоки длины Sb) Баланс между избыточностью и количеством уникальных блоков Нет ложной хвостовой уникальности

Сравнение Элементов Элементы считаются равными, если совпадает значение хеш-функции на них В качестве хеш-функции был выбран алгоритм MD5 Исторически сложилось. SHA-1 лучше Дает достаточный уровень вероятности совпадений на заявляемых объемах данных: Менее 10^(-15) – меньше вероятности отказажелеза.

Проблемы: Отсутствие локальности хешей Геометричеки и логически близкие блоки имеют сильно различающиеся хеш-значения Эффективное кеширование невозможно (Ни при HT-, ни при Btree - индексах) Поток запросов к базе моментально вытесняет накопленный кеш страниц – он постоянно обновляется. Вероятность нахождения хеша в кеше ~Sc/Sdb (Sc – размер кеша). Теоретические оценки времени операции с Базой Хешей (при традиционной организации БД): линейная деградация по времени в зависимости от отношения размеров БД: Th ~ (Sdb – const*Sc) LRU-кеш дает малый прирост производительности ~10% на Sdb > 4Gb

Решение Инвертирование роли БД Теперь БД является клиентом по отношению к запросам. БД – страничная хеш-таблица с перехешированием путем удвоения размера Запросы сортируются в порядке расположения хешей в таблице Каждую итерацию БД обходит все свои страницы Для каждой страницы обрабатывает запросы на вставку и чтение по хешам на этой странице (если есть) При достижении Fill-factor ~0.7 производится перехеширование

Результат Время обработки всей очереди запросов стало практически пропорционально Sdb Эффективное время обработки одного запроса ~ Sdb/Q/Dt (Здесь Q – средний размер очереди запросов, Dt – характерная производительность дисковой системы) Недостатки: Крайне неэффективная обработка при малых Q (требуется гибридный алгоритм) Отсутствие предсказуемости перехеширования (особенно неприятна необходимость перехеширования в середине обработки очереди)

Количественные показатели Использование БД по традиционной схеме При Sdb = 32Gb Выполнение запросов на чтение: запросов/c Выполнение запросов на запись: запросов/c – фундаментальная константа (зависит только от скорости врашения диска). При Sdb > RAM Деградация до запросов/c Использование БД по инвертированной схеме Пакетные чтение/запись (Q=1млн запросов): запросов/с. Теоретический предел: ~Dt/Sr/2 (Dt – производительность дисковой системы, Б/c. Sr – размер записи в байтах). т.е. Для уровня записи/чтения порядка 100мб /c и при размере записи БД 32 байт имеем максимально возможную скорость обработки порядка 1.5 Млн запросов в секунду.

84 Практическое использование Отправлено более 200 заявок на патенты, получено 100+ патентов США Результаты работы внедрены в крупных компаниях – производителях ПО (Parallels, Acronis – в этих компаниях совокупно работает более 1000 инженеров). На основании разработок создана новая отрасль индустрии ПО – «виртуализация ОС» Parallels: ПО, включающее разработанные в рамках НИР алгоритмы, установлено у более чем 3М потребителей (персональные системы) в 125 странах, и на более чем серверах.

Спасибо за внимание! © А. Тормасов, 2013 г