Математическое моделирование средств управления ресурсами и данными в распределенных и виртуализованных средах
Создание распределенных и виртуализованных сред, ориентированных на размещение, хранение и управление ресурсами. Построение математических моделей, описывающих компоненты такой среды. Математические модели интегрированных средств контроля доступа.
| Рубрика | Математика |
| Вид | автореферат |
| Язык | русский |
| Дата добавления | 02.03.2018 |
| Размер файла | 393,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
21
Размещено на http://www.allbest.ru/
Тормасов Александр Геннадьевич
Математическое моделирование средств управления ресурсами и данными в распределенных и виртуализованных средах
Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ
Автореферат
диссертации на соискание ученой степени
доктора физико-математических наук
Москва - 2008
Работа выполнена на кафедре информатики Московского физико-технического института (государственного университета)
Официальные оппоненты:
доктор технических наук, профессор Семенихин Сергей Владимирович, Институт электронных управляющих машин,
доктор физико-математических наук, профессор Семёнов Виталий Адольфович, Институт системного программирования РАН
доктор физико-математических наук, профессор Серебряков Владимир Алексеевич, Вычислительный центр имени А.А. Дородницына РАН
Ведущая организация: Институт автоматизации проектирования РАН
Защита состоится 27 июня 2008 года в 10-00 часов на заседании диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу: 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.
С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).
Автореферат разослан _____________________________ 2008 года.
Ученый секретарь диссертационного совета Д 212.156.05
кандидат физико-математических наук Федько О.С.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
математический модель виртуализованный ресурс
Актуальность темы
Темп развития современной вычислительной техники и коммуникационных сред имеет практически экспоненциальный характер по большинству параметров (например, более 20 лет каждые 18 месяцев происходит удвоение мощности процессоров - закон Мура). Ситуация с использованием компьютеров достаточно сложна - общепризнано, что рост потребностей превышает предоставляемые средой возможности. Существенным аспектом ограничения темпа развития стала безопасность систем и сложность управления компьютерной инфраструктурой.
Существенные изменения происходят и в алгоритмах, используемых современными операционными системами (ОС), которые являются основой для успешного использования компьютеров потребителем. Невозможно говорить о качестве обслуживания пользователя локальной или распределенной вычислительной системы, не рассматривая процессы, происходящие внутри ОС, особенно процессы выделения ресурсов. Включение в состав всех современных ОС средств виртуализации потребовало появления новых понятий и новых моделей процессов, происходящих в системах, как ключа к эффективному использованию возможностей и технологий.
Следующим шагом в эволюции технологии организации компьютеров становится их объединение в сеть. В последние годы резко возрос интерес к решению проблемы организации современных распределенных сред, призванных хоть как то решить проблемы потребителей, возникающие при использовании современной компьютерной инфраструктуры. Разрастание коммуникационной инфраструктуры, появление и активное использование одноранговых сетей доставки файлов и живого обмена аудио- и видео- данными (технологии Skype, BitTorrent, Kazaa и др), факты злоупотребления компьютерными технологиями, происходящий сдвиг в принципах использования современных компьютеров - все это заставило задуматься о сути происходящих процессов и попытаться переосмыслить применяемые в разработке компьютерных систем и программ подходы, перейдя от автономного компьютера к их объединению в виде единой распределенной среды виртуализованных вычислительных ресурсов.
Такие интенсивно развивающиеся в последние годы направления исследований, как GRID, Internet2, Web 2.0/3.0, реализация поддержки во всех современных ОС технологий аппаратной виртуализации компаний Intel и AMD подтверждают актуальность темы диссертационного исследования в области математического моделирования средств управления ресурсами и данными в распределенных и виртуализованных средах.
Цель работы и объект исследования
Цель диссертационной работы - разработка нового подхода к созданию распределенных и виртуализованных сред, ориентированных на размещение, хранение и управление ресурсами и данными, построение и анализ математических моделей, описывающих компоненты такой среды, в том числе математических моделей интегрированных средств контроля доступа для таких сред.
Задачи исследования:
– Анализ набора требований к распределенной и виртуализованной среде и их классификация;
– Разработка метода реализации и алгоритмов функционирования подсистем среды, удовлетворяющих большинству сформулированных требований;
– Разработка математических моделей, необходимых для описания поведения компонентов среды и обоснования выбора параметров и алгоритмов;
– Разработка интегрированной системы контроля доступа распределенной среды, создание ее математической модели и доказательство корректности функционирования системы в рамках сформулированных ограничений.
Объект исследования - методы и алгоритмы управления распределением ресурсов, методы и алгоритмы организации и работы распределенных систем, децентрализованные интегрированные системы контроля доступа, математические модели потребления вычислительных ресурсов, технологии виртуализации и их моделирование.
Методы исследования
В ходе научных исследований по разработке математических моделей и алгоритмов управления ресурсами и данными в распределенных и виртуализованных средах использовались методы дискретной математики и алгебры, вычислительной математики, методы математической статистики, методы теории операционных систем и системного программирования.
Научная новизна
В работе впервые предложены:
· Модель виртуализации объектов уровня операционной системы путем разделения их в пространстве имен;
· Обобщенная математическая модель и алгоритмы группового многоуровневого управления ресурсами, необходимые для виртуализации уровня ОС и других технологий виртуализации;
· Математическая модель вычислительных ресурсов компьютера и способа их потребления, использующая алгебраические и дифференциальные уравнения в частных производных гиперболического типа;
· Технология и алгоритмы организации, а также классификация требований к новому поколению распределенных сред управления данными;
· Метод использования для построения такой среды (n,k)-схемы разделения данных и его эффективная реализация в конечных полях Галуа;
· Принципы создания и алгоритмы функционирования распределенных виртуализованных сред на несимметричных серверах и каналах связи с открытой коммуникационной инфраструктурой, ориентированных на размещение, хранение и управление ресурсами и данными;
· Математические модели децентрализованных систем контроля доступа.
Теоретическая и практическая значимость
Разработанная система хранения и управления данными может быть использована как часть программного обеспечения (ПО) центров данных предприятий и организации услуг по размещению сервисов в глобальной сети (сервисов хостинга), а также для создания децентрализованной высокомасштабируемой системы хранения данных с количеством узлов, сопоставимым с общим количеством компьютеров в мировой сети Интернет. Предложенные алгоритмы реализации (n,k)-схемы могут быть использованы как усовершенствованный вариант RAID-технологий как для локального, так и для распределенного хранения и восстановления данных. Разработанные математические модели и алгоритмы могут быть использованы в качестве самостоятельных решений задач планирования и распределения ресурсов в современных ОС и распределенных системах, включая поддержку средств виртуализации. Предложенные математические модели контроля доступа могут применяться в распределенных системах с открытой коммуникационной инфраструктурой в условиях отсутствия доверенного центра, который разрешал или запрещал бы доступ к данным.
Результаты работы внедрены в крупных компаниях - производителях ПО (SWsoft/Parallels, Acronis - в этих компаниях совокупно работает более 1000 инженеров). На основании разработок диссертанта создана новая отрасль индустрии ПО - «виртуализация ОС». ПО, включающее в себя алгоритмы, разработанные диссертантом, установлено у более чем 700,000 потребителей в 125 странах на 17000 серверах (технология Virtuozzo®).
По результатам работы получено 14 патентов США и подано более 80 заявок на патенты США. Эти патенты являются международными объектами интеллектуальной собственности в странах, входящих в World Patent Organization, в том числе в России. Результаты работы могут быть использованы в учебном процессе при подготовке специалистов в области ОС, виртуализации и распределенных сред.
Публикации и апробация результатов работы
По теме диссертации опубликовано 54 работа, из них 11 статей [1-11] - в ведущих рецензируемых научных журналах и изданиях, рекомендованных ВАК РФ для публикации материалов докторских диссертаций, 7 публикаций в сборниках трудов международных конгрессов, симпозиумов, конференций [21,25,26,30,33,36,41]. В работах, опубликованных с соавторами, личный вклад соискателя приведен после списка публикаций в конце автореферата.
Результаты работ по диссертации докладывались и обсуждались на многочисленных научно-исследовательских семинарах и конференциях, основные из них: «Ottawa Linux Symposium» (Оттава, Канада, 2000); VE on PC 2001 Virtual Environment on a PC Cluster Workshop 2001 Protvino (Протвино, Россия, 2001); научный семинар кафедры вычислительной математики МФТИ (Москва, 1989-1999); научный семинар кафедры информационных технологий Лундского университета, (Лунд, Швеция 2002); научный семинар по теории кодирования ИППИ РАН (Москва, 2002); научный семинар Института Системного Программирования РАН (Москва, 2005); научный семинар Вычислительного Центра РАН под руководством акад. А.А. Петрова (Москва, 2008); Перспективы систем информатики - Шестая международная конференция памяти академика А.П. Ершова (Новосибирск, 2006), Международная конференция “Математика, компьютер, образование” (Москва, 2001); Международная научно-практическая конференция по программированию компании Microsoft (Москва, 2003); XL - XLIX ежегодные научные конференции Московского физико-технического института (Москва-Долгопрудный, 1997-2007гг) и др.
Структура и объем работы
Диссертация состоит из введения, трех глав, заключения и списка использованных источников, включающего 110 наименований.
Общий объем работы составляет 285 страниц машинописного текста.
Содержание работы
Во введении формулируются цели и задачи исследования, обосновывается актуальность проблемы, указываются объекты и методы исследования, научная новизна, объясняется теоретическая и практическая ценность исследования, приводятся публикации соискателя по теме работы и апробация.
В работе проведен анализ существующих решений, которые можно применить для создания части распределенной среды, связанной с хранением данных (далее будем назвать его распределенным хранилищем). Отдельно проанализированы системы обеспечения безопасности в распределенных системах, подходы и системы хранения данных с избыточностью, а так же рассмотрены подходы, предложенные авторами Grid технологий, их применимость к поставленной задаче, а также те проблемы, которые Grid технология сама по себе порождает и те, которые она решить не может.
Принципиальным отличием предложенного подхода от подхода Grid является вопрос о централизованности. Grid подразумевает идею VO - virtual organization, централизованность управления и системы безопасности, а также рассматривает преимущественно исполнение «большой» задачи на множестве вычислителей. Предложенный автором подход рассматривает в качестве нагрузки исполнение «потока» небольших задач на множестве разнородных коммуницирующих вычислителей и принципиально не содержит администрирующего центра и системы выдачи полномочий.
Анализируя решения, которые можно использовать для вычислительной компоненты среды, автор рассмотрел самые разнообразные системы, и как самый перспективный выбрал подход виртуализации вычислительных сервисов.
В главе 1 предложена классификация и анализ требований, которые, по мнению автора, должны быть выдвинуты современным потребителем компьютерных сервисов. В качестве основы решений предложено использование понятия «мобильности» как ключа к организации компьютерной среды:
Мобильность пользователя - оказываемый пользователю сервис не должен зависеть от доступности пользователя около компьютера, так и от наличия у пользователя специфических устройств;
Мобильность вычислительных ресурсов - вычислительные ресурсы должны прозрачным образом «следовать» за пользователем - перемещаться между физическими носителями;
Мобильность данных - они, так же как и вычислительные ресурсы, должны «следовать» за пользователем и иметь возможность перемещаться от одного физического носителя к другому;
Независимость сетевого доступа от внешних параметров, когда доступ к сети и сетевым источникам практически не зависит от состояния внешней среды.
Для осуществления требования мобильности на уровне процессов операционной системы автором предложено использовать новую модель виртуализации операционной системы - виртуализацию на уровне пространства имен объектов внутри ядра ОС. Она предполагает изоляцию «виртуальных сред» (ВС - являющихся основным понятием модели и представляющим собой группу процессов-потребителей ресурсов ОС) путем иерархического разделения имен между разными средами. Имена объектов одной среды существуют только внутри собственного виртуального пространства, и не существует технических средств воздействовать (открыть, удалить и т.д.) на объекты другой среды. Более подробно предложенная технология описана в [35,39,40,42,49,52,54].
Предложенная модель виртуализации существенно отличается от существующих стандартных моделей низкоуровневой виртуализации оборудования (виртуальных машин - ВМ) тем, что предоставляя практически такие же возможности, как и ВМ, позволяет добиться существенно более высокой «плотности» размещения виртуальных серверов на оборудовании (в сотни раз выше), не теряя в уровне безопасности и изоляции, и более эффективна для запуска и миграции вычислительных процессов.
Существенным отличием предложенной модели виртуализации является разделение всеми ВС одного ядра ОС, что накладывает дополнительные требования на технологии управления ресурсами ОС. Как показал опыт, даже в высокоразвитых коммерческих ОС имеющихся средств управления ресурсами недостаточно для групповых гарантий и лимитов выделения ресурсов потребителям, и особенно для осуществления взаимной изоляции виртуальных серверов по производительности (в частности, для защиты от случайных или намеренных атак типа «отказа в обслуживании»). Особо следует отметить, что использованные в существующих ядрах ОС алгоритмы управления ресурсами предназначены для управления сотнями, максимум тысячами объектов, тогда как, например, для 25 тысяч виртуальных серверов, запущенных на одной машине (такой эксперимент проводился на стандартном сервере архитектуры Intel), общее количество процессов и потоков превысило 200 тысяч.
Для адаптации созданной на основе предложенной модели новой технологии виртуализации к промышленному использованию автор разработал систему математических моделей, предназначенных для эффективного группового наложенного управления ресурсами (более подробно рассмотренных ниже).
Промышленная реализация технологии для основных коммерческих ОС (технология Virtuozzo® компании Parallels - для Microsoft Windows, Linux, Unix) подтвердила, что уровень накладных расходов по сравнению с виртуальными машинами оказался в 3-10 раз ниже из за высокой эффективности разделения ресурсов ядром ОС и управления ресурсами.
В главе 2 обсуждается схема манипуляции данными, которая ляжет в основу технологии организации распределенного хранилища данных, являющегося основой для предложенной автором схемы организации распределенной среды.
Саморегулируемая виртуальная вычислительная среда.
Поставленные в работе вопросы могут быть решены разными способами, но один из наиболее перспективных путей решения, по мнению автора работы, это создание полностью децентрализованного «саморастущего» хранилища без единого административного центра. Это относится как к серверам системы (не должно быть «разрешения на подключение к системе» - возможности подключившихся к системе серверов должны автоматически быть использованы), так и к «полномочиям» (не должно быть центра, который разрешает кому то или запрещает доступ к данным).
Рассмотрим вычислительную среду как совокупность сервисов и данных, расположенных на узлах сети. Компьютер пользователя может соединяться с серверами, отсылать запросы и получать ответы. При обработке запросов сервис может использовать локальные данные, а также может рассылать запросы сервисам, расположенным на узлах, соединенных со своим узлом через каналы.
Выделим важный класс таких сетей, когда все сервисы на системе равнозначны с точки зрения потребителя. Используя предложенную автором схему хранения данных (файлов) с регулируемой избыточностью, удается уйти от необходимости доступа к конкретному серверу для получения данных.
Хранилище работает на уровне файлов, то есть единицей информации, с которой оперирует пользователь хранилища и сервер является один файл, который используется для разборки (генерации) кусков.
Каждый файл предлагается хранить в виде некоторого набора частей (кусков), количество которых может меняться во времени. Всегда в любой момент времени для существующих в системе n частей выполняется условие, что из любых k кусков можно полностью собрать файл - (n,k)-схема хранения данных. Это условие будем называть далее условием избыточности. Размер каждого куска порядка 1/k от размера хранящегося файла (с точностью до округления). Количество кусков файла, содержащихся в системе - n, может меняться в зависимости от ее конфигурации, от количества компьютеров в ней, интенсивности работы с данным файлом и т.д. Причем, при изменении числа n уже существующие куски никак не изменяются.
Для того, чтобы получить файл, пользователю необходимо получить любые k кусков из существующих в данный момент в системе, из которых он сможет восстановить исходный файл. Размер каждого куска будет 1/k от размера исходного файла, поэтому общий объем полученной информации будет равен объему файла - тем самым общая нагрузка на сеть не будет увеличена.
Организуем хранилище таким образом, чтобы куски (или, как минимум k из них) помещаемого на хранение файла оказались каждый на отдельном сервере.
Рис. 1.Обработка запроса пользователя для k-=-3.
На рисунке показано работа запроса на чтение файла при k=3. Для удовлетворения запроса пользователь будет получать k “ближайших” с точки зрения загрузки в данный момент сети и пропускной способности каналов связи.
Такая модель позволяет динамически контролировать избыточность данных в системе и поддерживать ее для каждого файла на уровне, необходимом для равномерной загрузки сети и стабильного времени доступа к нему при заданной потребности пользователей
В дальнейшем делается предположение, что у нас количество кусков в системе равно количеству потенциально доступных серверов. Тем не менее, могут существовать и другие распределения, например, можно разложить на один сервер k кусков, так, чтобы все необходимое для сборки (восстановления) файла можно было получить с одного сервера, а на остальные k серверов мы раскладываем куски только для осуществления сборки в случае недоступности первого сервера (ассиметричная схема). Также возможна балансировка по средней загруженности серверов (например, разложить куски в соответствие со средней загрузкой серверов - больше частей на серверы с меньшей загрузкой).
Масштабируемость и отказоустойчивость подобной системы определяется многими факторами, особенно алгоритмами, требующими потенциально работы на всех серверах. Существенным является следующее утверждение: все алгоритмы и имена, действующие в такой топологии связей серверов друг с другом, должны носить локальный характер, то есть в системе нигде не должно быть никаких мест, содержащих сколь нибудь полный список серверов системы, или процедур верификации уникальности имени.
Для подбора пар соединений серверов и клиентов между собой автором было разработано несколько итеративных алгоритмов, которые могут обеспечить требуемые квазиоптимальные параметры локальных соединений.
Потоки данных в предложенной схеме идут по лучшим, наименее загруженным каналам, которые и обеспечивают быструю доставку. Более того, время получения всей информации, необходимой для сборки файла, на одном сервере может оказаться значительно меньше, чем для закачки файла целиком с одного из серверов. Таким образом, за счет параллельного использования нескольких каналов удается улучшить использование сетевой пропускной способности и получить систему, в которой эффективно используется факт отсутствия симметрии в производительности серверов и сетевых соединений.
Один из вариантов модели «саморегулирующейся» организации серверов, предложенный автором работы, использует введенную метрику над сетью, в которой расположены наши серверы. Она отражает сетевое «расстояние» от одного сервера до другого, например, в качестве подобной метрики может выступать время отклика от одного сервера к другому или реальная производительность канала между ними. Организуем серверы в группы таким образом, что расстояние между любой парой по указанной метрике не более некоторого заранее фиксированного порога. Размер группы не должен быть большим и обычно составляет несколько серверов (типичное значение 5-10 - см рис. 2).
Разрешим группам перекрываться - один сервер может участвовать в нескольких группах. Назовем граничными серверы, входящие в две или более групп. Пусть существует путь из любой группы в любую через посредство таких граничных серверов. Тогда их можно использовать для рассылки широковещательных сообщений - теоретическая и практическая оценка производительности и времени поиска в такой системе также проводилась в работах [10,17].
Рис. 2. Пример объединения серверов в группы.
Автором работы описана технология реализации системы (включая протоколы обмена, способ хранения и представления данных, метод реализации предложенной системы безопасности и др), подробно описанная в диссертационной работе и работах [1,3,4,10,17,23].
Решения задач по организации алгоритмов сборки-разборки
В предыдущем разделе была вкратце описана идеология хранения данных, базирующаяся на (n,k) схеме (по-видимому, впервые предложена М.Рабином в 1989 и, независимо, автором работы в то же время). В представленной работе предложены эффективные алгоритмы сборки и разборки данных, которые можно использовать для организации хранилища.
Для организации вычислений рассматриваются операции над полями Галуа размером N=2n. Стандартное представление такого поля - многочлены степени не выше n-1, коэффициенты которых - элементы поля GF(2) остатков от деления на 2 (то есть 0 или 1). Используя факт существования генератора поля p и наличие логарифма в поле, можно свести умножение к сложению, а деление к вычитанию. Для больших значений n (более 16) операции над большими числами сводятся к операциям над числами в поле GF(216) - например, одно умножение в GF(232) можно выразить через 5 умножений в GF(216) [12].
Рассмотрим k-мерное пространство векторов L над полем P. Каждый элемент этого пространства - это k элементов поля P. Теперь каждый файл можно представить в виде последовательности векторов из L. Пусть есть файл f, который представляет собой последовательность векторов l1, l2, … lm из L. И пусть есть набор Е из n векторов из L: Е={е1,e2,… en}. Причем этот набор такой, что любые k из них образуют базис в L. Тогда каждому вектору еi из E можно поставить в соответствие часть (l1 ,ei) , ( l2 , ei) , … ( lm , ei) , где (lj ,ei) - скалярное произведение векторов lj и ei. Скалярное произведение любых двух векторов из L есть элемент из P. Поэтому размер такого куска равен n бит. Размер же исходного файла равен (mkn) бит. Т. е. размер каждой из полученных частей равен mn, то есть 1/k от размера самого файла.
Пусть у нас есть теперь произвольные k частей из построенного набора. Обозначим вектора, которым соответствуют части, через 1, 2,… k, а сами части через 1, 2,… k, По условию набора Е, эти вектора образуют базис в L. Поэтому матрица А размером kk, строки которой - вектора 1, 2,… k , имеет обратную, которую мы обозначим через A-1. Тогда Ali - столбец, состоящий из i-тых элементов всех кусков. Обозначим такой столбец через Si. Т.е. для любого i[1,m]: li=A-1Si. , т.е. из этих частей можно восстановить исходный файл.
Итак, для решения задачи нам осталось просто указать алгоритм построения набора векторов, любые k из которого образуют базис. Для каждого ненулевого элемента p поля P строим вектор (1,p,p2, … pk). Таким образом, мы можем построить N-1 вектор. Любые k из них образуют базис - детерминант образуемой ими матрицы - определитель Вандермонда, который равен нулю только, когда некоторые из знаменателей прогрессий совпадают. Указанным способом мы легко строим набор из N-1 векторов, любые k из которых образуют базис. Для того, чтобы описать вектор, по которому построена часть, достаточно задать знаменатель прогрессии, который занимает n бит.
Отдельно следует отметить, что матрицу преобразования, которую надо строить из соответствующих векторов количеством k, можно привести к виду, когда первые k по порядку номеров дадут единичную матрицу. Тогда операция сборки для кусков, имеющих первые k номеров, существенно облегчается вычислительно и фактически состоит в конкатенации данных (т.н. «оптимальные» куски). Эту асимметрию можно использовать для построения более эффективных хранилищ данных, размещая части, соответствующие «оптимальным» кускам на серверах с наилучшим доступом.
В диссертационной работе проведены оценки количества операций, необходимых для работы алгоритмов - например, оценено, что для 1-мб данных и k=5 требуется приблизительно 171 000 000 тактов. Экспериментальная реализация подтверждает данный результат.
Используя SIMD расширения процессора (команды SSE), удалось достичь высоких скоростей сборки-разборки. Например, для системы на базе 2 x Intel P6 3GHz и (n,k)=(10,3) были получена скорость сборки 628 MB/sec для «оптимальных» и 157 MB/sec для остальных кусков в поле 24, и 326/120 MB/sec в поле 28.
Принципы представления данных в децентрализованном хранилище
Автором работы предложены следующие новые принципы:
1. Добавление и удаление серверов хранилища должно быть полностью добровольным и не требовать разрешений - все операции в нем выполняются исключительно «по желанию».
2. В системе нет ни одного сервера, недоступность которого означала бы невозможность получения какого либо файла данных.
3. Предоставляемый сервис может быть получен от любого сервера системы.
4. В хранилище заложены критерии функционирования, использующие в качестве параметра отказоустойчивости «количество доступных северов».
5. Система безопасности базируется на «декларируемых» полномочиях, то есть клиент хранилища перед началом работы декларирует наличие каких либо полномочий, на основании которых и происходит дальнейшая работа.
6. В случае любых действий клиента или сервера системы права и возможности других пользователей системы не должны меняться.
Топология и организация взаимодействия серверов
Предложенная автором [1,3] технология организации распределенной среды (далее обозначается как система) предлагает использовать набор серверов.
Все компьютеры в глобальной сети можно разбить на три группы:
· компьютеры, на которых функционирует распределенное хранилище
· компьютеры, с которых пользователи осуществляют доступ к хранилищу
· остальные компьютеры
Определение. Компьютеры первой группы будем называть нодами, компьютеры второй группы будем называть клиентскими компьютерами.
Так как изменение файла хранилища подразумевало бы изменение данных на разных и, возможно, не все время подключенных к сети компьютерах, была выбрана схема, при которой записанные в систему блоки являются неизменными (immutable). При записи измененного файла в систему записывается новая транзакция (версия) файла, причем сам файл не перезаписывается, а записываются лишь измененные блоки. В системе реализовано упорядочение транзакций файла по времени (TSO - timestamp ordering), когда каждой транзакции приписывается уникальная временная метка, которая позволяет разделить и упорядочить независимо возникшие от разных источников транзакции.
Определение. назовем покрытием файла на момент T содержимое файла на момент T, то есть это исходный файл с учетом всех изменений, проведенных в соответствие с транзакциями, завершенными к моменту T. Далее будем называть процедуру чтения файла - собиранием покрытия файла.
Определение FileID - файловый идентификатор. Используется в хранилище для однозначной идентификации файла внутри системы. Генерируется директорным сервером в процессе создания файла. Методика генерации выбрана так, чтобы по возможности гарантировать уникальность данного FileID в системе.
Определение BlockID - идентификатор блока в файле
Определение Слайс - каждый из множества кусков, в виде которых представляются блоки файлов в системе
Определение SliceID - идентификатор слайса в блоке. Одновременно является и задающим вектором для данного слайса
Определение 0-Блок - разновидность метаданных в системе. В 0-Блоке наравне со стандартными данными (время создания файла, длина файла, режим доступа, тип файла) находятся также данные, специфичные для хранилища (идентификатор файла, идентификатор транзакции, размер блока, диапазон измененных блоков).
Определение TransactionID - идентификатор транзакции. В состав входит время начала транзакции - пригоден для упорядочения транзакций.
Процедура сбора покрытия имеет простую геометрическую интерпретацию. Суть процедуры в том, чтобы представляя изменения в файле как последовательность перекрывающихся слоев, построить его покрытие (snapshot) - состояние файла на момент записи транзакции с заданным TID как «огибающую» всех доступных транзакций.
Отметим, что в покрытие входят не только блоки, TID которых равен заданному. На рис. 3 изображено покрытие файла, соответствующее транзакции TID3: при записи транзакции TID2 был изменен второй блок файла, при записи TID3 - третий. По оси Х отложены «координаты» внутри файла, или Bid - block id, представляющий собой диапазон байт, упорядоченный по возрастанию.
Рис. 3. Содержимое файла и сборка покрытия
Блоки различных транзакций файла одновременно существуют в системе до тех пор, пока блоки, относящиеся к наиболее «старой» из них не будут удалены сборщиком мусора (перед этим, например, они могут быть вытеснены на DVD диски). Перед удалением (блоков) транзакции файла сборщик мусора должен убедиться, что файл может быть собран полностью без данной транзакции.
Для обеспечения расширяемости, переносимости и защищенности системы автором предлагается использовать принцип активной директории, описанный в [1]. Суть его заключается в том, что в отличие от обычной директории, которая представляют собой файл с данными о своем содержимом, активная директорий состоит из файла с содержимым самой директории (обычный файл нашей системы), и из файлов с исполняемым кодом для разных платформ. Файл с кодом для конкретной платформы и является, собственно, директорным сервером на ней. Для старта корневой директории (root) используется договоренность о том, что файл с содержимым root-директории имеет идентификатор (Fid) 0. Он же является «корневой точкой доверия» - «root of trust» для системы контроля доступа хранилища.
Для изоляции потенциально небезопасного исполняемого кода директории можно использовать несколько подходов -использовать виртуальные машины или виртуальные серверы (VE) с изоляцией, ограниченный с точки зрения безопасности мобильный код для Java и .Net машин, выделенные серверы и др
Алгоритм упорядочения идентификаторов относительно числа
Для размещения и поиска какого либо файла по его числовому идентификатору (FileID) предполагается, что нам необходимо как то перебрать серверы, упорядоченные по двухуровневому принципу - группа серверов и сервер. Встает вопрос о том, каким образом можно для произвольного FileID осуществить поиск «наиболее подходящих» групп, которые могут существенно сэкономить время поиска и размещения файла (при предположении что файл с наибольшей вероятностью будет размещен в наиболее подходящей группе, затем в следующей по вероятности и тд). Отметим, что если алгоритм выбора группы будет давать разное значение для разных FileID, то появляется возможность автоматической «балансировки нагрузки», когда все файлы будут практически равномерно распределены по серверам и группам серверов системы псевдослучайным образом.
Более того, при необходимости частичного группирования файлов можно ввести групповые идентификаторы файлов, одинаковые группы файлов - например, для одной копии виртуального изолированного сервера. Тогда, используя предложенные алгоритмы можно добиться, чтобы большинство файлов для такой группы располагалось в одном месте (группе серверов или сервере), и существенно сократить время поиска и размещения файлов.
Автором был предложен алгоритм упорядочения идентификаторов (рассматриваемых как большое целое число) относительно одного выделенного идентификатора. Целью алгоритма является такое упорядочение, которое позволяет ввести отношение “один идентификатор больше или равен другого” относительно выделенного идентификатора и при этом не меняет относительного порядка при появлении или исчезновении идентификаторов в системе.
В работе доказано, что предложенный алгоритм «устойчив» к пропаданию и появлению идентификаторов в системе - с его помощью можно упорядочить идентификаторы, и при удалении или добавлении новых идентификаторов старые не будут менять свой порядок относительно друг друга.
Соответствие предложенного метода набору требований.
Отметим, что в предложенной системе акцент делается на возможностях хранения данных, а не собственно вычислений. В качестве «облегченного» варианта вычислителей предложены «активные» директорные сервисы, которые содержат свой код и данные внутри хранилища, но собираются и запускаются на любом сервере, который запросил файл из обслуживающейся этим директорным сервисом директории. В принципе, возможно запустить в качестве директорного сервиса или вообще «вычислительной компоненты системы» виртуальную машину или виртуальную среду, например, полный эмулятор компьютера Parallels VM, Java JVM или VE (виртуальный изолированный сервер) технологии Virtuozzo® компании Parallels [47,48]. Тем не менее, система полностью функциональна в виде хранилища данных и без использования виртуальных машин.
В работе рассматривается и анализируется вопрос соответствия предложенной вычислительной среды и системы хранения данных сформулированным требованиям, в предположении использования виртуальных сред или машин для вычислений, и использования (n,k)-схемы для управления данными. Делается вывод о соответствии большинству требований, и предложения по использованию соответствующих технических средств и технологий для улучшения системы, например, технологии создания защищенных виртуальных машин Intel Trusted Execution Technology - TXT / AMD SVM.
Имитационная математическая модель поиска данных
В работе [10] получено выражение для продолжительности поиска кусков, необходимых для сборки блока некоторого файла, точнее распределение этого времени, как случайной величины, при нескольких меняющихся параметрах: центрального узла, на котором запускается процедура сборки, и расположения кусков собираемого блока файла. На основании полученного выражения построена имитационная модель, и проведены тестовые расчеты, подтвердившие корректность модели. Например, для тестовой сети в 20 узлов с довольно высокой вероятностью недоступности сервера 0.1, время поиска данных с вероятностью 0.8 укладывается в диапазон от 1.5 до 3 секунд.
Глава 3 посвящена формальной математической модели децентрализованной системы безопасности. Автором предложено использование криптографических средств для реализации системы контроля доступа, в рамках которой злоумышленники или даже администраторы серверов не смогут прочитать не разрешенный к чтению файл пользователя или изменить к нему права доступа.
Математические модели контроля доступа для децентрализованного хранилища с открытой коммуникационной инфраструктурой
В работе предложены несколько формальных математических моделей контроля доступа для распределенной децентрализованной системы с открытой коммуникационной инфраструктурой и доказано гарантированное выполнение правил разграничения доступа в рамках построенных математических моделей (модель, названная «анонимной», модель с протоколированием, модель, включающая «владельца» и без такового). Материалы этого раздела описаны детально в [3,30]. В предложенной модели безопасности хранилища удалось перенести контроль доступа с серверов системы на компьютеры пользователей.
Базовые понятия для системы контроля доступа
В хранилище возможно два типа доступа к файлам: запись и чтение. Для контроля доступа типа «запись» используется электронная цифровая подпись (ЭЦП), для контроля доступа типа «чтение» используется шифрование с открытым ключом. Базовые свойства системы хранилища, существенные для построения математических моделей контроля доступа, можно сформулировать в виде следующих определений (О) и аксиом (А):
А1. Компьютеры могут взаимодействовать друг с другом через каналы связи.
А2. Существует дерево директорий для преобразования пути к файлу в числовой идентификатор файла (Fid). Содержимое директории хранится как файл.
А3. (Отказоустойчивость) части файла хранятся на различных серверах.
При записи файла в хранилище он делится на последовательные блоки, а затем каждый из блоков делится на n частей так, что любых k из них достаточно, чтобы восстановить блок.
О1. Пользователь хранилища - сущность, обладающая некоторым идентификатором и двумя парами открытый ключ/секретный ключ - для шифрования информации и проверки/генерации электронной цифровой подписи (ЭЦП).
О2. Пусть - некоторый пользователь. ЭВМ с установленной на ней ОС называется компьютером пользователя , если одновременно выполнено:
1. соответствует некоторому пользователю “user” операционной системы;
2. Субъекты, порождаемые от имени “user”, могут совершать криптографические преобразования с использованием секретных ключей пользователя ;
3. Невозможен не санкционированный доступ к объектам пользователя “user”.
А4. Для каждого пользователя существует его «компьютер пользователя».
Автор постулирует существование защищенной ПЭВМ для каждого пользователя системы.
А5. На компьютере пользователя есть некоторая априорная и корректная информация, необходимая для работы системы и обеспечения контроля доступа.
Такой информацией, в частности, является идентификатор корневой директории и открытый ключ для проверки ЭЦП корневой директории.
А6. По идентификатору любого пользователя системы можно получить соответствующие открытые ключи.
Будем считать, что используются «идеализированные» (не взламываемые) криптосистемы, системы электронной цифровой подписи и криптографические хэш-функции. Для того, чтобы дать некоторому пользователю право доступа к информации, хранящейся в системе, необходимо знать его идентификатор и открытый ключ шифрования.
Пользователи системы «декларируют» знание набора ключей, а система на основании декларации предоставляет сами данные. Если декларация некорректна, то пользователь просто не сможет раскодировать данные.
Математическая модель контроля доступа, названная «анонимной»
В математической модели контроля доступа, названной анонимной, после изменений файлов нельзя сказать, кто из пользователей, которым была разрешена запись, в действительности записал измененные файлы в систему. Доступ к файлу определяется списком контроля доступа (ACL - access control list), в котором открытыми ключами пользователей зашифрованы соответствующие ключи доступа к файлу. Список контроля доступа хранится в директорной записи, соответствующей данному файлу. Более детально и формально технология организации и доказательства корректности изложена в [3,30].
Всё содержимое файлов и часть служебной информации подвергается шифрованию. Для каждого файла генерируется две пары «открытый ключ/секретный ключ»: одна для шифрования, вторая - для ЭЦП. Для выполнения операции чтения необходимо знать открытый ключ для проверки подписи на файле и секретный ключ для расшифрования файла. Для записи, наоборот, необходимо знать открытый ключ - для шифрования файла и секретный ключ - для генерации ЭЦП.
Файл хранится как совокупность транзакций. Блоки каждой транзакции шифруются при помощи «ключа транзакции» («ключа сессии») симметричной криптосистемы, который генерируется заново для каждой транзакции. Зашифрованные блоки транзакции делятся на (n,k)-части. Для контроля целостности блоков транзакции в нулевой блок помещается список значений хэш-функции от шифротекстов данных блоков. Кроме этого, он содержит зашифрованный открытым ключом ключ транзакции. Служебный блок подписывается ЭЦП. Нулевой блок хранится в открытом (незашифрованном) виде.
Для того, чтобы воссоздать файл на локальной машине, пользователь собирает «покрытие», проверяет аутентичность блоков файла, после чего расшифровывает их и получает файл.
Директории предназначены для сопоставления текстового пути к файлу и Fid. Содержимое директории хранится в виде файла. Файл директории состоит из записей вида: «FileName--Fid--ACL», то есть списки контроля доступа для файлов хранятся в директорных записях для данного файла. Каждая запись представляет из себя отдельный блок файла директории, что способствует «атомарности» операций добавления/удаления директорных записей. Директорные записи (блоки), добавленные/модифицированные в результате одной транзакции, зашифрованы на ключе данной транзакции.Схема хранения ACL в директориях и доказательство корректности приводятся в [3].
В работе доказаны положения (леммы - Л), обосновывающие безопасность системы в рамках сделанных предположений:
Л1 Для доступа на чтение к содержимому файла необходимо и достаточно, чтобы у пользователя было «право на чтение файла».
Л2 «Право на запись в файл» не дает «права на чтение».
Л3 Если у пользователя нет «права записи в файл - директорию», содержащую файл, то для того, чтобы корректно записать новую транзакцию файла, необходимо и достаточно иметь «право на запись данного файла».
Л4 если у пользователя нет «права записи в директорию», содержащую файл, то «право на чтение» не дает «права на запись» в файл.
Право создания файла фактически есть право на запись в директорию, в которую помещается файл.
Л5 Для того, чтобы удалить файл необходимо и достаточно иметь «право на запись в директорию», где находится файл.
Л6 Для того, чтобы дать другому пользователю «право чтения» (текущей и последующих транзакций) файла, необходимо и достаточно одновременно:
* иметь «право на чтение» данного файла или знать его содержимое;
* иметь «право на запись в директорию», содержащую файл.
Л7 Для того, чтобы при неизменных ключах доступа к файлу дать другому пользователю «право на запись данного файла», необходимо и достаточно:
* иметь «право на запись» этого файла; и
* иметь «право на запись в директорию», содержащую файл
Явного запрещения выполнения операций записи/чтения не существует. Пользователь может иметь или не иметь права записи/чтения. Если нужно отозвать у пользователя право на запись/чтение, то необходимо сменить две пары ключей файла: шифрования и ЭЦП.
Для сделанных предположений в работе доказывается теорема (Т)
Т1. В модели 1 предписания пользователя о способе доступа выполняются.
Аналогичные утверждения и теоремы доказаны и для другой модели с введенным понятием собственника файла, близкой к традиционным моделям безопасности, применяемых в коммерческих ОС и центрах данных [3,31].
В главе четыре рассматриваются математические модели вычислительных ресурсов компьютера, использованные при реализации вычислительной компоненты системы.
Как уже отмечалось, при создании вычислительной среды одним из чрезвычайно существенных факторов, определяющих возможность ее практического применения, является эффективный контроль за распределением ресурсов системы между потребителями. Обычно это все описывается в терминах «уровня сервиса» - Service Level Agreement (SLA), который содержит описание долей ресурсов (в абсолютных или относительных единицах), и условия, при которых потребитель будет получать эти ресурсы.
Автором предложено и проанализировано несколько математических моделей, которые могут быть использованы для построения систем управления вычислительными ресурсами - как в распределенной среде, так и автономно. Некоторые из этих моделей (в частности, предложенная автором модель группового наложенного управления) были внедрены и использованы как часть технологии виртуализации операционных систем Virtuozzo® [47,48].
Математическая модель группового наложенного управления ресурсами
Важным элементом технологии виртуализации является разграничение ресурсов между виртуальными серверами. Для обеспечения надлежащего качества обслуживания возникает необходимость ограничения потребления ресурсов группами процессов, тогда как ОС дает обычно только возможность управления одним процессом или потоком, причем не предоставляет гарантий или пределов потребления процессом или группой. Операционная система, запущенная на компьютере, обладает определенным набором ресурсов, необходимых для запуска и работы процессов и нитей. Введем классификацию ресурсов на основе возможности перераспределения:
возобновляемые - для таких ресурсов система может запретить потребления и передать возможность потребить освобожденные ресурсы другому процессу или процессам (пример - CPU, полоса пропускания сети).
невозобновляемые - для них можно запретить потребление ресурса, но нет возможности освободить потребленные ресурсы (дисковое пространство).
частично возобновляемые - для таких ресурсов можно запретить потребление данного ресурса и через некоторое время освободить ресурсы для использования другими процессами (рабочий набор памяти процесса).
Пусть управление называется наложенным, если оно:
· Для достижения целей распределения ресурсов осуществляет управление, используя механизмы, предоставляемые, явно или неявно, системой управления нижележащего уровня ОС (пользуясь средствами управления ресурсами операционных систем или «микроуправлением»)
...Подобные документы
Операторы преобразования переменных, классы, способы построения и особенности структурных моделей систем управления. Линейные и нелинейные модели и характеристики систем управления, модели вход-выход, построение их временных и частотных характеристик.
учебное пособие [509,3 K], добавлен 23.12.2009Особенности математических моделей и моделирования технического объекта. Применение численных математических методов в моделировании. Методика их применения в системе MathCAD. Описание решения задачи в Mathcad и Scilab, реализация базовой модели.
курсовая работа [378,5 K], добавлен 13.01.2016Возникновение и развитие теории динамических систем. Развитие методов реконструкции математических моделей динамических систем. Математическое моделирование - один из основных методов научного исследования.
реферат [35,0 K], добавлен 15.05.2007Процесс выбора или построения модели для исследования определенных свойств оригинала в определенных условиях. Стадии процесса моделирования. Математические модели и их виды. Адекватность математических моделей. Рассогласование между оригиналом и моделью.
контрольная работа [69,9 K], добавлен 09.10.2016Примеры основных математических моделей, описывающих технические системы. Математическая модель гидроприводов главной лебедки и механизма подъема-опускания самоходного крана. Описание динамики гидропривода механизма поворота стрелы автобетононасоса.
реферат [3,9 M], добавлен 23.01.2015Изучение вопросов применения теории множеств, их отношений и свойств и теории графов, а также математических методов конечно-разностных аппроксимаций для описания конструкций РЭА (радиоэлектронной аппаратуры) и моделирования протекающих в них процессов.
реферат [206,9 K], добавлен 26.09.2010Моделирование непрерывной системы контроля на основе матричной модели объекта наблюдения. Нахождение передаточной функции формирующего фильтра входного процесса. Построение графика зависимости координаты и скорости от времени, фазовой траектории системы.
курсовая работа [1,5 M], добавлен 25.12.2013Анализ динамических процессов в системе на основе использования построенной аналитической модели. Моделирование с использованием пакета расширения Symbolic Math Tolbox. Построение модели в виде системы дифференциальных уравнений, записанных в форме Коши.
курсовая работа [863,4 K], добавлен 21.06.2015Разработка проекта системы автоматического управления тележкой, движущейся в боковой плоскости. Описание и анализ непрерывной системы, создание ее математических моделей в пространстве состояний и модели "вход-выход". Построение графиков реакций объекта.
курсовая работа [1,7 M], добавлен 25.12.2010Математическое моделирование задач коммерческой деятельности на примере моделирования процесса выбора товара. Методы и модели линейного программирования (определение ежедневного плана производства продукции, обеспечивающей максимальный доход от продажи).
контрольная работа [55,9 K], добавлен 16.02.2011Вводные понятия. Классификация моделей. Классификация объектов (систем) по их способности использовать информацию. Этапы создания модели. Понятие о жизненном цикле систем. Модели прогнозирования.
реферат [36,6 K], добавлен 13.12.2003Моделирование как метод познания. Классификаций и характеристика моделей: вещественные, энергетические и информационные. Математическая модель "хищники-жертвы", ее сущность. Порядок проверки и корректировки модели. Решение уравнений методом Рунге-Кутта.
методичка [283,3 K], добавлен 30.04.2014Основные свойства геологических объектов как пространственных переменных. Виды математических моделей геологических объектов. Вариограмма и ее аппроксимации. Вероятностные модели геологических полей. Влияние на вариограмму геометрической базы измерений.
презентация [345,8 K], добавлен 17.07.2014Наименование разрабатываемой модели, основание для разработки. Состав и параметры аппаратного обеспечения системы. Выбор и обоснование средств реализации. Построение, расчет, разбиение модели на конечные элементы. Графическое представление решения.
курсовая работа [674,0 K], добавлен 30.09.2010Признаки некоторых четырехугольников. Реализация моделей геометрических ситуаций в средах динамической геометрии. Особенности динамической среды "Живая геометрия", особенности построения в ней моделей параллелограмма, ромба, прямоугольника и квадрата.
курсовая работа [862,0 K], добавлен 28.05.2013Моделирование входного заданного сигнала, построение графика, амплитудного и фазового спектра. Моделирование шума с законом распределения вероятностей Рэлея, оценка дисперсии отсчетов шума и проверка адекватности модели шума по критерию Пирсона.
курсовая работа [2,3 M], добавлен 25.11.2011Математические модели технических объектов и методы для их реализации. Анализ электрических процессов в цепи второго порядка с использованием систем компьютерной математики MathCAD и Scilab. Математические модели и моделирование технического объекта.
курсовая работа [565,7 K], добавлен 08.03.2016Математическое моделирование динамики биологических видов (популяций) Т. Мальтусом. Параметры и основное уравнение модели "хищник-жертва", ее практическое применение. Качественное исследование элементарной и обобщенной модификаций модели В. Вольтерра.
курсовая работа [158,1 K], добавлен 22.04.2011Приемы построения математических моделей вычислительных систем, отображающих структуру и процессы их функционирования. Число обращений к файлам в процессе решения средней задачи. Определение возможности размещения файлов в накопителях внешней памяти.
лабораторная работа [32,1 K], добавлен 21.06.2013Знакомство с особенностями построения математических моделей задач линейного программирования. Характеристика проблем составления математической модели двойственной задачи, обзор дополнительных переменных. Рассмотрение основанных функций новых переменных.
задача [656,1 K], добавлен 01.06.2016
