автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математическое моделирование средств управления ресурсами и данными в распределенных и виртуализованных средах

На правах рукописи

ТОРМАСОВ Александр Геннадьевич

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ СРЕДСТВ УПРАВЛЕНИЯ РЕСУРСАМИ И ДАННЫМИ В РАСПРЕДЕЛЕННЫХ И ВИРТУАЛИЗОВАННЫХ СРЕДАХ

Специальность 05.13.18 - математическое моделирование,

диссертации на соискание ученой степени доктора физико-математических наук

003444963

Москва-2008

003444963

Работа выполнена на кафедре информатики Московского физико-технического института (государственного университета)

Официальные оппоненты:

доктор технических наук, профессор Семенихин Сергей Владимирович Институт электронных управляющих машин

доктор физико-математических наук, профессор

Семенов Виталий Адольфович

Институт системного программирования РАН

доктор физико-математических наук, профессор Серебряков Владимир Алексеевич Вычислительный центр имени А А Дородницына РАН

Ведущая организация:

Институт автоматизации проектирования РАН

Защита состоится 27 июня 2008 года в 10-00 часов на заседании диссертационного совета Д 212 156 05 при Московском физико-техническом институте (государственном университете) по адресу 141700, Московская обл, г Долгопрудный, Институтский пер , д 9, ауд 903 КПМ

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

Автореферат разослан _ ■Л^-ССлЛ^._2008 года

Ученый секретарь диссертационного совета Д 212 15^05 кандидат физико-математических наук у' /

Федько О С

Актуальность темы

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

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

Следующим шагом в эволюции технологии организации компьютеров становится их объединение в сеть В последние годы резко возрос интерес к решению проблемы организации современных распределенных сред, призванных хоть как то решить проблемы потребителей, возникающие при использовании современной компьютерной инфраструктуры Разрастание коммуникационной инфраструктуры, появление и активное использование одноранговых сетей доставки файлов и живого обмена аудио- и видео- данными (технологии Бкуре, ВцТоггегй, Кагаа и др.), факты злоупотребления компьютерными технологиями, происходящий сдвиг в принципах использования современных компьютеров - все это заставило задуматься о сути происходящих процессов и попытаться переосмыслить применяемые в разработке компьютерных систем и про-

3

грамм подходы, перейдя от автономного компьютера к их объединению в виде единой распределенной среды виртуализованных вычислительных ресурсов

Такие интенсивно развивающиеся в последние годы направления исследований, как GRID, Internet2, Web 2 0/3.0, реализация поддержки во всех современных ОС технологий аппаратной виртуализации компаний Intel и AMD подтверждают актуальность темы диссертационного исследования в области математического моделирования средств управления ресурсами и данными в распределенных и виртуализованных средах

Цель работы и объект исследования

Цель диссертационной работы - разработка нового подхода к созданию распределенных и виртуализованных сред, ориентированных на размещение, хранение и управление ресурсами и данными, построение и анализ математических моделей, описывающих компоненты такой среды, в том числе математических моделей интегрированных средств контроля доступа для таких сред Задачи исследования.

- Анализ набора требований к распределенной и виртуализованной среде и их классификация,

- Разработка метода реализации и алгоритмов функционирования подсистем среды, удовлетворяющих большинству сформулированных требований;

- Разработка математических моделей, необходимых для описания поведения компонентов среды и обоснования выбора параметров и алгоритмов;

- Разработка интегрированной системы контроля доступа распределенной среды, создание ее математической модели и доказательство корректности функционирования системы в рамках сформулированных ограничений Объект исследования - методы и алгоритмы управления распределением

ресурсов, методы и алгоритмы организации и работы распределенных систем, децентрализованные интегрированные системы контроля доступа, математические модели потребления вычислительных ресурсов, технологии виртуализации и их моделирование

Методы исследования

В ходе научных исследований по разработке математических моделей и алгоритмов управления ресурсами и данными в распределенных и виртуализо-ванных средах использовались методы дискретной математики и алгебры, вычислительной математики, методы математической статистики, методы теории операционных систем и системного программирования

Научная новизна

В работе впервые предложены

• Модель виртуализации объектов уровня операционной системы путем разделения их в пространстве имен,

• Обобщенная математическая модель и алгоритмы группового многоуровневого управления ресурсами, необходимые для виртуализации уровня ОС и других технологий виртуализации;

• Математическая модель вычислительных ресурсов компьютера и способа их потребления, использующая алгебраические и дифференциальные уравнения в частных производных гиперболического типа,

• Технология и алгоритмы организации, а также классификация требований к новому поколению распределенных сред управления данными;

• Метод использования для построения такой среды (п,к)-схемы разделения данных и его эффективная реализация в конечных полях Галуа;

• Принципы создания и алгоритмы функционирования распределенных вир-туализованных сред на несимметричных серверах и каналах связи с открытой коммуникационной инфраструктурой, ориентированных на размещение, хранение и управление ресурсами и данными,

• Математические модели децентрализованных систем контроля доступа

Теоретическая и практическая значимость

Разработанная система хранения и управления данными может быть использована как часть программного обеспечения (ПО) центров данных пред-

5

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

Результаты работы внедрены в крупных компаниях - производителях ПО (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), научный семинар кафедры вычислительной математики МФТИ (Москва, 19891999), научный семинар кафедры информационных технологий Лундского университета, (Лунд, Швеция 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]

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

Существенным отличием предложенной модели виртуализации является разделение всеми ВС одного ядра ОС, что накладывает дополнительные требования на технологии управления ресурсами ОС Как показал опыт, даже в высокоразвитых коммерческих ОС имеющихся средств управления ресурсами не-

9

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

Для адаптации созданной на основе предложенной модели новой технологии виртуализации к промышленному использованию автор разработал систему математических моделей, предназначенных для эффективного группового наложенного управления ресурсами (более подробно рассмотренных ниже)

Промышленная реализация технологии для основных коммерческих ОС (технология Virtuozzo® компании Parallels - для Microsoft Windows, Linux, Unix) подтвердила, что уровень накладных расходов по сравнению с виртуальными машинами оказался в 3-10 раз ниже из за высокой эффективности разделения ресурсов ядром ОС и управления ресурсами

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

так и к «полномочиям» (не должно быть центра, который разрешает кому то или запрещает доступ к данным)

Рассмотрим вычислительную среду как совокупность сервисов и данных, расположенных на узлах сети Компьютер пользователя может соединяться с серверами, отсылать запросы и получать ответы При обработке запросов сервис может использовать локальные данные, а также может рассылать запросы сервисам, расположенным на узлах, соединенных со своим узлом через каналы Выделим важный класс таких сетей, когда все сервисы на системе равнозначны с точки зрения потребителя Используя предложенную автором схему хранения данных (файлов) с регулируемой избыточностью, удается уйти от необходимости доступа к конкретному серверу для получения данных

Хранилище работает на уровне файлов, то есть единицей информации, с которой оперирует пользователь хранилища и сервер является один файл, который используется для разборки (генерации) кусков

Каждый файл предлагается хранить в виде некоторого набора частей (кусков), количество которых может меняться во времени Всегда в любой момент времени для существующих в системе п частей выполняется условие, что из любых к кусков можно полностью собрать файл - (п,к)-схема хранения данных Это условие будем называть далее условием избыточности Размер каждого куска порядка 1/к от размера хранящегося файла (с точностью до округления) Количество кусков файла, содержащихся в системе - п, может меняться в зависимости от ее конфигурации, от количества компьютеров в ней, интенсивности работы с данным файлом и т д Причем, при изменении числа п уже существующие куски никак не изменяются

Для того чтобы получить файл, пользователю необходимо получить любые к кусков из существующих в данный момент в системе, из которых он сможет восстановить исходный файл Размер каждого куска будет 1/к от размера исходного файла, поэтому общий объем полученной информации будет равен объему файла - тем самым общая нагрузка на сеть не будет увеличена

11

Организуем хранилище таким образом, чтобы куски (или, как минимум к из них) помещаемого на хранение файла оказались каждый на отдельном сервере

Рис 1 Обработка запроса пользователя для к=3

На рисунке показано работа запроса на чтение файла при к=3 Для удовлетворения запроса пользователь будет получать к "ближайших" с точки зрения загрузки в данный момент сети и пропускной способности каналов связи

Такая модель позволяет динамически контролировать избыточность данных в системе и поддерживать ее для каждого файла на уровне, необходимом для равномерной загрузки сети и стабильного времени доступа к нему при заданной потребности пользователей

В дальнейшем делается предположение, что у нас количество кусков в системе равно количеству потенциально доступных серверов Тем не менее, могут существовать и другие распределения, например, можно разложить на один сервер к кусков, так, чтобы все необходимое для сборки (восстановления) файла можно было получить с одного сервера, а на остальные к серверов мы раскладываем куски только для осуществления сборки в случае недоступности первого сервера (ассиметричная схема) Также возможна балансировка по средней загруженности серверов (например, разложить куски в соответствие со средней загрузкой серверов - больше частей на серверы с меньшей загрузкой)

Масштабируемость и отказоустойчивость подобной системы определяется многими факторами, особенно алгоритмами, требующими потенциально работы на всех серверах Существенным является следующее утверждение, все

алгоритмы и имена, действующие в такой топологии связей серверов друг с другом, должны носить локальный характер, то есть в системе нигде не должно быть никаких мест, содержащих сколь нибудь полный список серверов системы, или процедур верификации уникальности имени

Для подбора пар соединений серверов и клиентов между собой автором было разработано несколько итеративных алгоритмов, которые могут обеспечить требуемые квазиоптимальные параметры локальных соединений

Потоки данных в предложенной схеме идут по лучшим, наименее загруженным каналам, которые и обеспечивают быструю доставку. Более того, время получения всей информации, необходимой для сборки файла, на одном сервере может оказаться значительно меньше, чем для закачки файла целиком с одного из серверов Таким образом, за счет параллельного использования нескольких каналов удается улучшить использование сетевой пропускной способности и получить систему, в которой эффективно используется факт отсутствия симметрии в производительности серверов и сетевых соединений

Один из вариантов модели «саморегулирующейся» организации серверов, предложенный автором работы, использует введенную метрику над сетью, в которой расположены наши серверы Она отражает сетевое «расстояние» от одного сервера до другого, например, в качестве подобной метрики может выступать время отклика от одного сервера к другому или реальная производительность канала между ними Организуем серверы в группы таким образом, что расстояние между любой парой по указанной метрике не более некоторого заранее фиксированного порога Размер группы не должен быть большим и обычно составляет несколько серверов (типичное значение 5-10 - см рис 2)

Разрешим группам перекрываться - один сервер может участвовать в нескольких группах Назовем граничными серверы, входящие в две или более групп Пусть существует путь из любой группы в любую через посредство таких граничных серверов Тогда их можно использовать для рассылки широковещательных сообщений - теоретическая и практическая оценка производи-

13

тельности и времени поиска в такой системе также проводилась в работах

Автором работы описана технология реализации системы (включая протоколы обмена, способ хранения и представления данных, метод реализации предложенной системы безопасности и др.), подробно описанная в диссертационной работе и работах [3,4,12,17,23].

Решения задач по организации алгоритмов сборки-разборки В предыдущем разделе была вкратце описана идеология хранения данных, базирующаяся на (п,к) схеме (по-видимому, впервые предложена М.Рабином в 1989 и, независимо, автором работы в то же время). В представленной работе предложены эффективные алгоритмы сборки и разборки данных, которые можно использовать для организации хранилища.

Для организации вычислений рассматриваются операции над полями Галуа размером N=2". Стандартное представление такого поля - многочлены степени не выше п-1, коэффициенты которых - элементы поля ОР(2) остатков от деления на 2 (то есть 0 или 1). Используя факт существования генератора поля р и наличие логарифма в поле, можно свести умножение к сложению, а деление к вычитанию. Для больших значений п (более 16) операции над большими числами сводятся к операциям над числами в поле GF(2м/) - например, одно умножение в ОР(232) можно выразить через 5 умножений в СР(2>6) [4,12].

Рассмотрим Аг-мерное пространство векторов Ь над полем Р. Каждый элемент этого пространства - это к элементов поля Р. Теперь каждый файл можно

14

представить в виде последовательности векторов из Ь Пусть есть файл^ который представляет собой последовательность векторов ¡¡, 12> . 1т из £ И пусть есть набор Е из п векторов из Ь Е={еъе2>... еп} Причем этот набор такой, что любые к из них образуют базис в £ Тогда каждому вектору е, из Е можно поставить в соответствие часть (I, , (12, е^ , (1т, е) , где (Ц ,с) - скалярное произведение векторов 1} и Скалярное произведение любых двух векторов из Ь есть элемент из Р Поэтому размер такого куска равен п бит Размер же исходного файла равен (тхкп) бит Т е размер каждой из полученных частей равен тхп, то есть 1/к от размера самого файла

Пусть у нас есть теперь произвольные к частей из построенного набора Обозначим вектора, которым соответствуют части, через е2, г*, а сами части через Еь Е2, Ек, По условию набора Е, эти вектора образуют базис в Ь. Поэтому матрица А размером кхк, строки которой - вектора еь е2, ек, имеет обратную, которую мы обозначим через А'1. Тогда А11 - столбец, состоящий из г-тых элементов всех кусков Обозначим такой столбец через 5, Т.е для любого 1с[1,т] 1,=А~'5, ,т.е. из этих частей можно восстановить исходный файл

Итак, для решения задачи нам осталось просто указать алгоритм построения набора векторов, любые к из которого образуют базис Для каждого ненулевого элемента р поля Р строим вектор (1,р,р2, рк) Таким образом, мы можем построить N-1 вектор Любые к из них образуют базис - детерминант образуемой ими матрицы - определитель Вандермонда, который равен нулю только, когда некоторые из знаменателей прогрессий совпадают Указанным способом мы легко строим набор из N-1 векторов, любые к из которых образуют базис Для того чтобы описать вектор, по которому построена часть, достаточно задать знаменатель прогрессии, который занимает п бит.

Отдельно следует отметить, что матрицу преобразования, которую надо строить из соответствующих векторов количеством к, можно привести к виду, когда первые к по порядку номеров дадут единичную матрицу Тогда операция сборки для кусков, имеющих первые к номеров, существенно облегчается вы-

15

числительно и фактически состоит в конкатенации данных (т н «оптимальные» куски) Эту асимметрию можно использовать для построения более эффективных хранилищ данных, размещая части, соответствующие «оптимальным» кускам на серверах с наилучшим доступом

В диссертационной работе проведены оценки количества операций, необходимых для работы алгоритмов - например, оценено, что для 1мб данных и к=5 требуется приблизительно 171 ООО ООО тактов Экспериментальная реализация подтверждает данный результат.

Используя SIMD расширения процессора (команды SSE), удалось достичь высоких скоростей сборки-разборки. Например, для системы на базе 2 х Intel Р6 3GHz и (п,к)=(10,3) были получена скорость сборки 628 MB/sec для «оптимальных» и 157 MB/sec для остальных кусков в поле 24, и 326/120 MB/sec в поле 28

Принципы представления данных в децентрализованном хранилище

Автором работы предложены следующие новые принципы

1 Добавление и удаление серверов хранилища должно быть полностью добровольным и не требовать разрешений - все операции в нем выполняются исключительно «по желанию»

2 В системе нет ни одного сервера, недоступность которого означала бы невозможность получения какого либо файла данных

3 Предоставляемый сервис может быть получен от любого сервера системы.

4 В хранилище заложены критерии функционирования, использующие в качестве параметра отказоустойчивости «количество доступных северов»

5. Система безопасности базируется на «декларируемых» полномочиях, то есть клиент хранилища перед началом работы декларирует наличие каких либо полномочий, на основании которых и происходит дальнейшая работа

6 В случае любых действий клиента или сервера системы права и возможности других пользователей системы не должны меняться

Топология и организация взаимодействия серверов

Предложенная автором [4,12] технология организации распределенной среды (далее обозначается как система) предлагает использовать набор серверов

16

Все компьютеры в глобальной сети можно разбить на три группы-

• компьютеры, на которых функционирует распределенное хранилище

• компьютеры, с которых пользователи осуществляют доступ к хранилищу

• остальные компьютеры

Определение Компьютеры первой группы будем называть нодами, компьютеры второй группы будем называть клиентскими компьютерами

Так как изменение файла хранилища подразумевало бы изменение данных на разных и, возможно, не все время подключенных к сети компьютерах, была выбрана схема, при которой записанные в систему блоки являются неизменными (immutable) При записи измененного файла в систему записывается новая транзакция (версия) файла, причем сам файл не перезаписывается, а записываются лишь измененные блоки. В системе реализовано упорядочение транзакций файла по времени (TSO - timestamp ordering), когда каждой транзакции приписывается уникальная временная метка, которая позволяет разделить и упорядочить независимо возникшие от разных источников транзакции.

Определение Назовем покрытием файла на момент Т содержимое файла на момент Т, то есть это исходный файл с учетом всех изменений, проведенных в соответствие с транзакциями, завершенными к моменту Т Далее будем называть процедуру чтения файла - собиранием покрытия файла

Определение FilelD - файловый идентификатор Используется в хранилище для однозначной идентификации файла внутри системы Генерируется дирек-торным сервером в процессе создания файла Методика генерации выбрана так, чтобы по возможности гарантировать уникальность данного FilelD в системе Определение BlockID - идентификатор блока в файле Определение Слайс - каждый из множества кусков, в виде которых представляются блоки файлов в системе

Определение SliceED - идентификатор слайса в блоке Одновременно является и задающим вектором для данного слайса

Определение О-Блок - разновидность метаданных в системе. В О-Блоке наравне со стандартными данными (время создания файла, длина файла, режим доступа, тип файла) находятся также данные, специфичные для хранилища (идентификатор файла, идентификатор транзакции, размер блока, диапазон измененных блоков).

Определение TransactionID - идентификатор транзакции. В состав входит время начала транзакции - пригоден для упорядочения транзакций.

Процедура сбора покрытия имеет простую геометрическую интерпретацию. Суть процедуры в том, чтобы представляя изменения в файле как последовательность перекрывающихся слоев, построить его покрытие (snapshot) - состояние файла на момент записи транзакции с заданным TID как «огибающую» всех доступных транзакций.

Рис. 3. Содержимое файла и сборка покрытия

Отметим, что в покрытие входят не только блоки, TID которых равен заданному. На рис. 3 изображено покрытие файла, соответствующее транзакции ТЮЗ: при записи транзакции TID2 был изменен второй блок файла, при записи ТЮЗ - третий. По оси X отложены «координаты» внутри файла, или Bid - block id, представляющий собой диапазон байт, упорядоченный по возрастанию.

Блоки различных транзакций файла одновременно существуют в системе до тех пор, пока блоки, относящиеся к наиболее «старой» из них не будут удалены

сборщиком мусора (перед этим, например, они могут быть вытеснены на DVD

18

диски) Перед удалением (блоков) транзакции файла сборщик мусора должен убедиться, что файл может быть собран полностью без данной транзакции

Для обеспечения расширяемости, переносимости и защищенности системы автором предлагается использовать принцип активной директории, описанный в [3] Суть его заключается в том, что в отличие от обычной директории, которая представляют собой файл с данными о своем содержимом, активная директорий состоит из файла с содержимым самой директории (обычный файл нашей системы), и из файлов с исполняемым кодом для разных платформ Файл с кодом для конкретной платформы и является, собственно, директорным сервером на ней Для старта корневой директории (root) используется договоренность о том, что файл с содержимым root-директории имеет идентификатор (Fid) 0 Он же является «корневой точкой доверия» - «root of trust» для системы контроля доступа хранилища

Для изоляции потенциально небезопасного исполняемого кода директории можно использовать несколько подходов - использовать виртуальные машины или виртуальные серверы (VE) с изоляцией, ограниченный с точки зрения безопасности мобильный код для Java и Net машин, выделенные серверы и др Алгоритм упорядочения идентификаторов относительно числа Для размещения и поиска какого либо файла по его числовому идентификатору (FilelD) предполагается, что нам необходимо как то перебрать серверы, упорядоченные по двухуровневому принципу - группа серверов и сервер Встает вопрос о том, каким образом можно для произвольного FilelD осуществить поиск «наиболее подходящих» групп, которые могут существенно сэкономить время поиска и размещения файла (при предположении, что файл с наибольшей вероятностью будет размещен в наиболее подходящей группе, затем в следующей по вероятности и тд). Отметим, что если алгоритм выбора группы будет давать разное значение для разных FilelD, то появляется возможность автоматической «балансировки нагрузки», когда все файлы будут прак-

тически равномерно распределены по серверам и группам серверов системы псевдослучайным образом

Более того, при необходимости частичного группирования файлов можно ввести групповые идентификаторы файлов, одинаковые группы файлов - например, для одной копии виртуального изолированного сервера Тогда, используя предложенные алгоритмы можно добиться, чтобы большинство файлов для такой группы располагалось в одном месте (группе серверов или сервере), и существенно сократить время поиска и размещения файлов.

Автором был предложен алгоритм упорядочения идентификаторов (рассматриваемых как большое целое число) относительно одного выделенного идентификатора Целью алгоритма является такое упорядочение, которое позволяет ввести отношение "один идентификатор больше или равен другого" относительно выделенного идентификатора и при этом не меняет относительного порядка при появлении или исчезновении идентификаторов в системе.

В работе доказано, что предложенный алгоритм «устойчив» к пропаданию и появлению идентификаторов в системе - с его помощью можно упорядочить идентификаторы, и при удалении или добавлении новых идентификаторов старые не будут менять свой порядок относительно друг друга Соответствие предложенного метода набору требований. Отметим, что в предложенной системе акцент делается на возможностях хранения данных, а не собственно вычислений В качестве «облегченного» варианта вычислителей предложены «активные» директорные сервисы, которые содержат свой код и данные внутри хранилища, но собираются и запускаются на любом сервере, который запросил файл из обслуживающейся этим дирек-торным сервисом директории В принципе, возможно запустить в качестве ди-ректорного сервиса или вообще «вычислительной компоненты системы» виртуальную машину или виртуальную среду, например, полный эмулятор компьютера Parallels VM, Java JVM или VE (виртуальный изолированный сервер) технологии Virtuozzo® компании Parallels [48,49] Тем не менее, система полно-

20

стью функциональна в виде хранилища данных и без использования виртуальных машин

В работе рассматривается и анализируется вопрос соответствия предложенной вычислительной среды и системы хранения данных сформулированным требованиям, в предположении использования виртуальных сред или машин для вычислений, и использования (п, к)-схемы для управления данными Делается вывод о соответствии большинству требований, и предложения по использованию соответствующих технических средств и технологий для улучшения системы, например, технологии создания защищенных виртуальных машин Intel Trusted Execution Technology - TXT / AMD SVM

Имитационная математическая модель поиска данных

В работе [14] получено выражение для продолжительности поиска кусков, необходимых для сборки блока некоторого файла, точнее распределение этого времени, как случайной величины, при нескольких меняющихся параметрах центрально го узла, на котором запускается процедура сборки, и расположения кусков собираемого блока файла На основании полученного выражения построена имитационная модель, и проведены тестовые расчеты, подтвердившие корректность модели Например, для тестовой сети в 20 узлов с довольно высокой вероятностью недоступности сервера 0 1, время поиска данных с вероятностью 0 8 укладывается в диапазон от 1 5 до 3 секунд

Глава 3 посвящена формальной математической модели децентрализованной системы безопасности Автором предложено использование криптографических средств для реализации системы контроля доступа, в рамках которой злоумышленники или даже администраторы серверов не смогут прочитать не разрешенный к чтению файл пользователя или изменить к нему права доступа

Математические модели контроля доступа для децентрализованного хранилища с открытой коммуникационной инфраструктурой

В работе предложены несколько формальных математических моделей контроля доступа для распределенной децентрализованной системы с открытой коммуникационной инфраструктурой и доказано гарантированное выполнение правил разграничения доступа в рамках построенных математических моделей

21

(модель, названная «анонимной», модель с протоколированием, модель, включающая «владельца» и без такового) Материалы этого раздела описаны детально в [3,31] В предложенной модели безопасности хранилища удалось перенести контроль доступа с серверов системы на компьютеры пользователей. Базовые понятия для системы контроля доступа

В хранилище возможно два типа доступа к файлам, запись и чтение Для контроля доступа типа «запись» используется электронная цифровая подпись (ЭЦП), для контроля доступа типа «чтение» используется шифрование с открытым ключом Базовые свойства системы хранилища, существенные для построения математических моделей контроля доступа, можно сформулировать в виде следующих определений (О) и аксиом (А)

А1. Компьютеры могут взаимодействовать друг с другом через каналы связи А2. Существует дерево директорий для преобразования пути к файлу в числовой идентификатор файла (Fid) Содержимое директории хранится как файл A3. (Отказоустойчивость) части файла хранятся на различных серверах

При записи файла в хранилище он делится на последовательные блоки, а затем каждый из блоков делится на п частей так, что любых к из них достаточно, чтобы восстановить блок

01. Пользователь хранилища - сущность, обладающая некоторым идентификатором U и двумя парами открытый ключ/секретный ключ - для шифрования

информации и проверки/генерации электронной цифровой подписи (ЭЦП)

02. Пусть U - некоторый пользователь ЭВМ с установленной на ней ОС называется компьютером пользователя £Л, если одновременно выполнено.

1. U соответствует некоторому пользователю "user" операционной системы,

2 Субъекты, порождаемые от имени "user", могут совершать криптографические преобразования с использованием секретных ключей пользователя и ,

3 Невозможен не санкционированный доступ к объектам пользователя "user" А4. Для каждого пользователя U существует его «компьютер пользователя»

Автор постулирует существование защищенной ПЭВМ для каждого пользователя системы

А5 На компьютере пользователя есть некоторая априорная и корректная информация, необходимая для работы системы и обеспечения контроля доступа

Такой информацией, в частности, является идентификатор корневой директории и открытый ключ для проверки ЭЦП корневой директории А6. По идентификатору U любого пользователя системы можно получить соответствующие U открытые ключи

Будем считать, что используются «идеализированные» (не взламываемые) криптосистемы, системы электронной цифровой подписи и криптографические хэш-функции Для того чтобы дать некоторому пользователю право доступа к информации, хранящейся в системе, необходимо знать его идентификатор и открытый ключ шифрования

Пользователи системы «декларируют» знание набора ключей, а система на основании декларации предоставляет сами данные. Если декларация некорректна, то пользователь просто не сможет раскодировать данные.

Математическая модель контроля доступа, названная «анонимной»

В математической модели контроля доступа, названной анонимной, после изменений файлов нельзя сказать, кто из пользователей, которым была разрешена запись, в действительности записал измененные файлы в систему Доступ к файлу определяется списком контроля доступа (ACL - access control list), в котором открытыми ключами пользователей зашифрованы соответствующие ключи доступа к файлу Список контроля доступа хранится в директорной записи, соответствующей данному файлу Более детально и формально технология организации и доказательства корректности изложена в [3,31]

Все содержимое файлов и часть служебной информации подвергается шифрованию. Для каждого файла генерируется две пары «открытый ключ/секретный ключ» одна для шифрования, вторая - для ЭЦП Для выполнения операции чтения необходимо знать открытый ключ для проверки подписи на файле и секретный ключ для расшифрования файла Для записи, наоборот, необходимо знать открытый ключ - для шифрования файла и секретный

ключ - длятенерации ЭЦП

Файл хранится как совокупность транзакций. Блоки каждой транзакции

шифруются при помощи «ключа транзакции» («ключа сессии») симметричной

криптосистемы, который генерируется заново для каждой транзакции Зашифрованные блоки транзакции делятся на (п,к)-части Для контроля целостности блоков транзакции в нулевой блок помещается список значений хэш-функции от шифротекстов данных блоков Кроме этого, он содержит зашифрованный открытым ключом ключ транзакции Служебный блок подписывается ЭЦП. Нулевой блок хранится в открытом (незашифрованном) виде

Для того, чтобы воссоздать файл на локальной машине, пользователь собирает «покрытие», проверяет аутентичность блоков файла, после чего расшифровывает их и получает файл

Директории предназначены для сопоставления текстового пути к файлу и Fid Содержимое директории хранится в виде файла Файл директории состоит из записей вида. «FileName—Fid—ACL», то есть списки контроля доступа для файлов хранятся в директорных записях для данного файла. Каждая запись представляет собой отдельный блок файла директории, что способствует «атомарности» операций добавления/удаления директорных записей Директорные записи (блоки), добавленные/модифицированные в результате одной транзакции, зашифрованы на ключе данной транзакции Схема хранения ACL в директориях и доказательство корректности приводятся в [3]

В работе доказаны положения (леммы - JI), обосновывающие безопасность системы в рамках сделанных предположений

Л1 Для доступа на чтение к содержимому файла необходимо и достаточно, чтобы у пользователя было «право на чтение файла». JI2 «Право на запись в файл» не дает «права на чтение». JI3 Если у пользователя нет «права записи в файл - директорию», содержащую файл, то для того, чтобы корректно записать новую транзакцию файла, необходимо и достаточно иметь «право на запись данного файла»

JI4 если у пользователя нет «права записи в директорию», содержащую файл, то «право на чтение» не дает «права на запись» в файл

Право создания файла фактически есть право на запись в директорию, в которую помещается файл

JI5 Для того, чтобы удалить файл необходимо и достаточно иметь «право на запись в директорию», где находится файл

JI6 Для того, чтобы дать другому пользователю «право чтения» (текущей и последующих транзакций) файла, необходимо и достаточно одновременно

• иметь «право на чтение» данного файла или знать его содержимое,

• иметь «право на запись в директорию», содержащую файл

Л7 Для того, чтобы при неизменных ключах доступа к файлу дать другому пользователю «право на запись данного файла», необходимо и достаточно

• иметь «право на запись» этого файла, и

• иметь «право на запись в директорию», содержащую файл

-Явного запрещения выполнения операций записи/чтения не существует Пользователь может иметь или не иметь права записи/чтения Если нужно отозвать у пользователя право на запись/чтение, то необходимо сменить две пары ключей файла шифрования и ЭЦП

Для сделанных предположений в работе доказывается теорема (Т) Т1 В модели 1 предписания пользователя о способе доступа выполняются

Аналогичные утверждения и теоремы доказаны и для другой модели с введенным понятием собственника файла, близкой к традиционным моделям безопасности, применяемых в коммерческих ОС и центрах данных [3,31].

В главе четыре рассматриваются математические модели вычислительных ресурсов компьютера, использованные при реализации вычислительной компоненты системы

Как уже отмечалось, при создании вычислительной среды одним из чрезвычайно существенных факторов, определяющих возможность ее практического применения, является эффективный контроль над распределением ресурсов системы между потребителями Обычно это все описывается в терминах «уровня сервиса» - Service Level Agreement (SLA), который содержит описание

25

долей ресурсов (в абсолютных или относительных единицах), и условия, при которых потребитель будет получать эти ресурсы.

Автором предложено и проанализировано несколько математических моделей, которые могут быть использованы для построения систем управления вычислительными ресурсами - как в распределенной среде, так и автономно Некоторые из этих моделей (в частности, предложенная автором модель группового наложенного управления) были внедрены и использованы как часть технологии виртуализации операционных систем Virtuozzo® [48,49]

Математическая модель группового наложенного управления ресурсами

Важным элементом технологии виртуализации является разграничение ресурсов между виртуальными серверами Для обеспечения надлежащего качества обслуживания возникает необходимость ограничения потребления ресурсов группами процессов, тогда как ОС дает обычно только возможность управления одним процессом или потоком, причем не предоставляет гарантий или пределов потребления процессом или группой Операционная система, запущенная на компьютере, обладает определенным набором ресурсов, необходимых для запуска и работы процессов и нитей Введем классификацию ресурсов на основе возможности перераспределения

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

• Для достижения целей распределения ресурсов осуществляет управление, используя механизмы, предоставляемые, явно или неявно, системой управления нижележащего уровня ОС (пользуясь средствами управления ресурсами операционных систем или «микроуправлением»)

• интервалы воздействия этого управления, как правило, превышают интервалы, характерные для системы управления нижележащего уровня.

26

Рассмотрим обобщенную модель наложенного группового управления и исследуем ограничения, которые надо наложить на функцию потребления процесса между воздействиями макроуправления, чтобы обеспечить надлежащую точность управления Рассмотрим модель наложенного управления единичным потребителем, и после этого обобщим ее на группу потребителей

Пусть функция потребления ~ зависимость потребления процессом одного или нескольких ресурсов от времени Пусть в операционной системе существуют N процессов, и каждому из них соответствует желаемая функция потребления (которая может быть задана в виде вектора) ), где I — порядковый номер процесса в системе, / - собственное время процесса Собственное время процесса совпадает с физическим временем в системе, если нет конкурентных задач (с точностью до операций ввода-вывода) Будем считать, что желаемая функция потребления каждого ресурса принимает в данный момент времени 1 - процесс потребляет дополнительную единицу ресурса О - процесс не потребляет дополнительную единицу -1 - процесс освобождает занятую единицу ресурса

То есть )с {°>1=~1)) и пусть ^ ^ ^ - та же самая функция, но ? - реальное (физическое, системное) время, в котором процесс получал ресурсы В общем случае ^ ) * ) Рассмотрим преобразование ("/*,), которое фактически

«растягивает» временную ось («растяжение» происходит, поскольку рассматриваемому процессу процессорное время может быть не предоставлено в «желаемый» им момент времени) Пусть ^ ^ - та же самая функция Я, но * * -идеальное время, при котором идеально выполняется наложенное нами ограничение (например, гарантия доли процессорного времени) Назовем эту функцию функцией идеального потребления с идеальной функцией "=8{{)

Будем считать критерием качества управления отклонение функции идеального потребления от функции фактического потребления Тогда нашу задачу

можно сформулировать следующим образом - при каких предположениях о

поведении Я//) выполняется условие « , где а -

допустимая погрешность управления, а подынтегральная функция имеет смысл меры вектора отклонения от идеального В работе [15] выводятся интегральные уравнения для оценки компонент погрешности, вводится мера и обосновывается тот факт, что определяющим фактором стабильности нашего управления является функция ОЯ,(Е,(Р), которая, фактически, описывает специфику потребления ОС и связанные с ним эффекты. Доказывается, что можно достичь приемлемой точности наложенного управления путем наложения некоторого набора требований к поведению функции потребления и оценивая некоторые параметры процесса Для невозобновляемых и частично возобновляемых ресурсов обосновано управление путем

• ограничения скорости потребления ресурсов - мягкий способ (за скорость потребления, фактически, отвечает коэффициент ,

• запрещая потреблять ресурсы - жесткий способ (в данном случае это означает, что Я'фФЩО)

В работе [15] рассмотрено приложение полученной абстрактной модели к ресурсу - «доле СРШ, предложен алгоритм наложенного управления и оценена его точность. Результат проведенных измерений, подтверждает сделанные в модели предположения

В работе [16] предложено обобщение модели для группового наложенного управления, для чего введена функция группового потребления, на примере задачи управления дисковыми обменами Группа задач - конечное число задач, удовлетворяющих следующим критериям

• Все задачи в группе потребляют один и тот же ресурс

• Задачи можно объединить по признаку (принадлежности пользователю)

• Ресурс потребляется только одной задачей группы (для любого 1)

Группа задач характеризуется функцией желаемого потребления 011, которая равна 1, если хотя бы одна из задач группы потребляет ресурс, равна 0, если

никакая из задач группы ресурс не потребляет. Для этой задачи также сформулирован критерием качества управления и алгоритм управления

Математическая модель потребления вычислительных ресурсов Автором в [2] предложена новая математическая модель потребления ресурсов операционной системы, использующая систему дифференциальных и алгебраических уравнений (примеры решения таких систем для гиперболических уравнений в частных производных рассмотрены в [5-11]) Модель может быть использована для исследования как процесса микро-планирования на уровне планировщика ОС, так и на уровне макро планирования общего прохождения потока процессов через компьютерную систему, в том числе распределенной системы разной степени связности, и может быть использована при анализе работы предложенной виртуализованной распределенной среды Модельными переменными выбраны время t и расстояние х Переменная времени t традиционно описывает переход системы от прошлого к будущему Переменная х является аналогом «внутреннего времени» процесса или нити исполнения По сути своей оно изменяется только тогда, когда процесс получил долю процессора и описывает решение задачи, имея размерность «количества команд» Физический смысл х продвижение решения задачи от начала к концу (доля решения). Максимальная скорость, с которой может выполняться «поток исполнения» («скорость звука») ограничена максимальной производительностью процессора — числом операций в секунду, которые он может исполнять Планирование «потоков исполнения» ОС можно рассматривать как некую среднюю «скорость» передвижения Абсолютное значение х соответствует текущей стадии выполненного процесса и меняется для каждой задачи от 0 до Хтах

Введем величины p(x,t)~ вектор плотности ресурсов, размерностью [ресурс/операции] Его компоненты означает удельную плотность какого либо ресурса в точке (x,t), и u(x,t) - скорость «потока исполнения», те скорость выполнения команд, или скорость продвижения по внутреннему времени, размерностью [операции/секунды], Q(x,t) = p(xj)*u(x,t)~ вектор потока ресурсов [ресурс/секунды] p(x,t)=0 в точке х, где выполнение не дошло до этой стадии

Рассмотрим в качестве примера ресурса долю CPU. Обозначим долю CPU, которую должен получить данный «поток исполнения» на данном процессоре T(x,t) исходя из внутренней потребности и разрешенной доли потребления (если ее поддерживает планировщик ОС), и реально полученную долю CPU D(x,t)

29

Плотность ресурса p(x,t) определим как долю CPU, которая в момент времени t и долю выполненной работы х была получена «потоком исполнения». Пусть Ртах - максимальная производительность CPU Производная потока Q{x,t) вдоль х представляет собой изменение полученной доли ресурсов в процессе его исполнения. В наших переменных можно считать D(x,t) *Pmax-u(x,t).

Запишем «закон сохранения массы» или уравнение неразрывности в форме

8p(x,t) | dg(x,t)_ 8t дх

/,м

Здесь fi(x,t) описывает поведение «источника» массы Если вспомнить, что р по сути своей есть удельная доля использованного CPU, то фактически fi(x,t) представляет собой функцию «желаемого уровня потребления» ресурсов в дифференциальной форме - то, что предоставил задаче планировщик системы по ее запросу, с учетом уровня SLA и отклонений от него.

Производная скорости выполнения процесса по времени управляется внешней по отношению к процессу функцией выделения планировщиком операционной системы ресурса

dt J ^ '

Существует множество планировщиков ресурсов, работающих по своим законам Их поведение можно измерить на реальной работающей системе, или получить его оценки из приближенных математических моделей

Имеет смысл выделить несколько частных случаев, на которых можно рассмотреть поведение «усредненного планировщика», который при прочих равных условиях стремится скомпенсировать разность между желаемой долей ресурсов каждой нити исполнения T(x,t) и полученной долей D(x,t) Это можно считать «давлением», определяющим изменение потока ресурсов Пример описания планировщика в рамках модели приведен в [2]

В рамках модели естественным образом вводятся две независимые функции

fi(x,t) и f:(x,t), описывающие внутреннюю потребность в ресурсе алгоритма «потока исполнения» и выделение ресурса планировщиком ОС

Для другого класса возобновляемых ресурсов, например, для сетевой полосы пропускания, формулировка модели и модельных параметров может выглядеть так же, за исключением того факта что даже если «поток исполнения» не нуж-

дается в этом ресурсе то он тем не менее может продвигаться вдоль оси х Кроме того, должна быть введена кросс-зависимость Ртах от разности между желаемой полосой пропускания и полученной полосой, так как пропорционально недополученной полосы пропускания мы должны увеличить время, за которое достигается какой то этап в первой группе уравнений для доли CPU

Pcmax(x,t)= Р^ X DN/TN,

где индекс N относится к сетевой полосе пропускания. Не возобновляемые ресурсы можно описать в основном алгебраическими формулами типа р,~р,(х,Х).

Также, используя подобный подход, можно смоделировать последовательность работы разных «потоков исполнения», когда результат работы одного «потока исполнения» может быть использован как начальное условие для другого «потока исполнения», или обмен данными между параллельными нитями, используемыми в одной расчетной программе

Общая система уравнений для j-ro потока и 1-го ресурса выглядит как

fo/M , ди> pf(x,t)_

+ "S!(x,t) mm^-fl'feO)

dt dx' ,max S\(x,t)

duJ(x,t)

dt

требуемый уровень потребления ресурса без учета ограничений, Тта/х,1) текущее ограничение планировщиком, Я, ц - параметры планировщика Решать предложенные уравнения возможно при помощи стандартных методов - например, при помощи монотонных сеточно-характеристических схем [7], которые были использованы автором работы для решения задач моделирования в [5-11,24] Модельные расчеты были проведены по одношаговому явному методу типа Рунге-Кутты, где начальные и граничные значения р, = О,

•^у сиггепиЬгеаЛ

и(х,0)=1 для х 0 [0,1], С = —для п потоков с весом V/* для соответст-

Ы\я

вующего ресурса,

Тт т

и"*' = и" + гЛ(р,т" тщ(5," ~)~и") и расчет велся, пока ]к с/г < 1

Основные результаты, полученные в ходе исследования, приводятся в заключении диссертации

Основные результаты работы

1 Предложены принципы функционирования качественно нового поколения средств размещения и управления ресурсами и данными как децентрализованной распределенной саморегулирующейся виртуализованной мобильной среды, являющейся совокупностью вычислительных ресурсов и хранилищ данных, объединенных коммуникационной инфраструктурой

2 Поставлена и решена задача разработки нового подхода к виртуализации, который может быть использован как способ обеспечения мобильности приложений в виртуализованной среде

3 Разработана система математических и имитационных моделей, а также алгоритмов и методов управления ресурсами, необходимых для функционирования предложенной виртуализованной распределенной среды, в том числе модель группового наложенного управления ресурсами и модель представления вычислительных ресурсов и способа их потребления

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

5 Разработаны принципы функционирования распределенной среды с открытой коммуникационной инфраструктурой и возможностью переноса защиты с серверов и коммуникаций на клиентские узлы путем использования предложенной математической модели интегрированной системы контроля доступа, базирующейся на понятии «декларируемых» полномочий

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи га Перечня ведущих рецензируемых научных журналов и изданий, рекомендованных ВАК Минобрнауки РФ

1 Тормасов А Г, Нижник Е И Математическое моделирование производительности файловой системы NTFS при нагрузке типа «запись дисковых данных» // Вестник НГУ Серия Инф.технологии-2007 -т 5,вып 2-е 67-77

2 Тормасов А Г Модель потребления ресурсов вычислительной системой // Вестник НГУ Серия Инф технологии - 2006 т 4 , вып 1 - с 63-72

3 Тормасов А Г, Обернихин В А Схема контроля доступа для распределенной одноранговой файловой системы (TorFS) // Безопасность информационных технологий -2005 - № 3 — с 68-74

4 Тормасов А Г, Хасин М А , Пахомов Ю И Обеспечение отказоустойчивости в распределенных средах//Программирование-2001 -№5 - с 26-34

5 Тормасов А Г, Иванов В Д, Петров И Б , Пашутин Р А, Холодов А С Сеточно - характеристический метод расчета процессов динамического деформирования на нерегулярных расчетных сетках II Мат моделирование - 1999. т 11, № 7 - с 118-127

6 Тормасов А Г , Петров И Б Численное исследование косого соударения жесткого шарика с двухслойной упругопластической плитой // Мат. моделирование - 1992 т 4, № 3-е 20-27

7 Тормасов А Г, Петров И Б , Холодов АС Об использовании гибридизирован-ных сеточно-характеристических схем для численного решения трехмерных задач динамики деформируемого твердого тела // Журнал вычислительной математики и матем физ -1990 -т 30, №8 — с 1237-1244

8 Тормасов А Г, Петров ИБО численном исследовании трехмерных задач обтекания волнами сжатия препятствия или полости в упругопластическом полупространстве // Докл АН СССР- 1990 -т 314, №4 — с 817-820

9 Тормасов А Г, Петров И.Б , Холодов ACO численном изучении нестационарных процессов в деформируемых средах многослойной структуры // Изв АН СССР сер МТТ- 1989 - №4 — с 89-95

10 Тормасов А Г, Петров ИБО численном решение пространственных задач соударения // Изв. АН СССР, сер МТТ - 1990 - № 1 — с 58-72

11 Тормасов А Г, Жуков Д В Петров И Б Численное и экспериментальное изучение разрушения твердых тел в жидкости // Изв АН СССР, сер МТТ - 1991 - № 3 - с 183-190.

Материалы и тезисы конференций, статьи в научных сборниках и журналах

12 Tormasov A G, Khasin М А , Pakhomov Yu I Ensuring Fault-Tolerance in Distributed Media//Programming and Comp Software-2001 - № 27(5) - p 245-251

13 Тормасов А Г Классификация требований к сервисам по размещению, хранению и управлению ресурсами и данными // Пробл выч математики, мат моделирования и информатики Сб науч тр / МЗ Пресс - М , 2006 —с 282-293

14 Тормасов А Г, Петров В А Доставка информации пользователю в распределенных системах // Пробл выч математики, мат моделирования и информатики Сб науч тр / МЗ Пресс - М, 2006 — с 156-194

15 Тормасов А Г., И В Луковников, К С Коротаев Наложенное управление ресурсами ОС // Пробл выч математики, мат моделирования и информатики Сб науч тр /МЗ Пресс - М, 2006 — с 195-211

16 Тормасов А Г, Кобец А Л, Луковников В В, Модель управления группами потоков ввода/вывода с заданной точностью// Модел процессов обработки информации Сб науч тр /Моек физ -тех ин-т. - М, 2007 - с 272—275

17 Тормасов А Г, Петров В А Расчет времени поиска в распределенной системе, использующей N-k схему при хранении // Процессы и методы обработки информации Сб науч. тр/Моек физ-тех ин-т -М,2005 —с 68-76

18 Тормасов А Г, Нижник Е И Обзор проблем тестирования производительности файловых систем // Проблемы выч математики, математического моделирования и информатики. Сб науч тр /МЗ Пресс - М, 2006 — с 89-113

19. Тормасов А Г., Нижник Е И Тестирование производительности файловых систем на основе прогнозирующей модели // Пробл выч матем, мат моделирования и информатики Сб науч тр / МЗ Пресс - М, 2006 —с 114-135

20 Тормасов А Г, Емельянов П В , Коротаев К С, Луковников И В Основные проблемы обеспечения точности управления при наложенном управлении ресурсами в современных операционных системах // Процессы и методы обработки информации Сб науч тр /Моек физ -тех инст - 2006 — с 237-242

21 Белоусов С М, Тормасов А Г Задачи по распределению ресурсов операционной системы с учетом возможности взаимного перераспределения пулов // Перспективы систем информатики Шестая международная конференция памяти акад А П Ершова Сб тр конф Новосибирск - 2006 - с 35-38

22 Тормасов А Г, Нижник Е И Проблемы тестирования производительности Web-сервера на основе прогнозирующей модели // Процессы и методы обработки информации Сб науч тр /Моек физ -тех инст -М, 2006 — с 249-257

23 Тормасов А Г, Хасин М А, Пахомов Ю И Модель распределенного хранения данных с регулируемой избыточностью // Электронный журнал Исследовано в России-2001 -№035/010315—с 355-364

24 Тормасов А, Петров И Численное изучение волновых процессов в слоистых средах//Сб Методы мат модел и обр инф , МФТИ - М, 1987. - с 101-105

25 Tormasov A G , Ivanov V D. Pashutm R A Petrov IВ A new object-oriented package for scientific computation // Int Open Workshop «Actual Problems of Computational Mechanics Parallel Modeling» (IOW95) - 1995 — p 23.

26 Tormasov A G , Ivanov V D Korutmc S A Petrov IВ A program package for solving system hyperbolic equations m 2-D domain of complex form with many unconnected boundaries // Int Open Workshop «Actual Problems of Computational Mechanics Parallel Modeling» (IOW 95) - 1995 — p 24

27 Тормасов А Г, Иванов В Д Пашутин Р А Петров И Б Объектно-ориентированный подход в создании сред поддержки сложных вычислений // Тезисы Юб научной конф /МФТИ - Долгопрудный, 1996 —с 106

28 Тормасов А Г , Иванов В Д Пашутин Р А Петров И Б Использование объектно-ориентированного подхода для решения задачи численного моделирования взаимодействия упругопластических тел // Совр Пробл фундаментальной и прикладной физики и математики Юб. научн конф МФТИ - 1997 — с 73

29 Тормасов А Г, Жуков Д В, Петров И Б Численное и экспериментальное изучение разрушения твердых тел в жидкости // Информатика и медицина - М Наука. 1997 —с 156-167

30 Tormasov A G, Khasme М Providing Availability of Internet Resources with Adjustable Redundancy // VE on PC 2001 Virtual Environment on a PC Cluster Workshop 2001 Protvino-2001 — с 127-137

31 Тормасов А Г, Обернихин В А Контроль доступа с протоколированием изменений в распределенной децентрализованной файловой системе (TorFS) // Электронный журнал Исследовано в России - 2004 -№203—с 2156-2165

32 Тормасов А Г, Протасов С С , Белоусов С М Архитектура и особенности функционирования современных операционных систем // Объединенный научный журнал - 2004 г, 24 (116) — с 78-83

33 Тормасов А Г, Хасин М А Математическая модель хранения данных на слабосвязанных серверах // Междунар конференция "Математика, компьютер, образование", сборник научных трудов Ч 1 -Москва, Прогресс-традиция, 2001.-е 168-176

34 Тормасов А Г Виртуализация ОС // Открытые системы - 2002 -№ 1— с 27-32

35 Тормасов АГ, Протасов С С , Белоусов С М, Использование виртуальных сред для предоставления услуг по размещению ресурсов в глобальной сети // Объединенный научный журнал - 2004 г, № 24 (116) — с 74-78

36 Тормасов А Г Классификация требований к сервисам по размещению, хранению и управлению ресурсами и данными // Перспективы систем информатики Шес-

тая международная конференция памяти академика АП Ершова Сборник трудов конференции - Новосибирск - 2006 - с 98-101

37 Тормасов А Г Среда для сборки многоплатформных программ // Открытые системы-2002 -№09 —с 19-21

38 Тормасов А Г Виртуализационные технологии и их возможности // BYTE/Poc -2005 - № 5 - с 35-45

39 Тормасов А Г, Николаев А Н Технология виртуализации ОС на предприятиях // BYTE/Poc - 2006 - № 5 - с 37-51

40 Тормасов А.Г, Протасов С С, Белоусов С М Прошлое, настоящее и будущее развитие архитектуры и принципов создания операционных систем // Объединенный научный журнал - 2004 г№ 24 (116) — с 83-86

41 Тормасов А Г Виртуализация сервисов по размещению, хранению и управлению ресурсами и данными // Технологии Microsoft в научных исследованиях и высшем образовании Межд науч -практ конф по программированию (Академические Дни) - 2003 - http //research microsoft сош/collaboration/umversity/europe/Events/ AcademicDays/CISRussia/2003/content aspx903 - 36 с

42 Тормасов А Г, Николаев А Н Виртуализация сегодня задачи, проблемы, технологии, решения//PCWeek/RE, - 2006 -№27 с 12-14

43 Tormasov A G, Kuznetsov А N ТСРЯР options for high-performance data transmission // Builder com - 2002 -http //builder com com/5100-6372J 4-1050878 html - 4 p

44. Tormasov A G, Kuznetsov A N Use sendfile() to optimize data transfer // Builder com -2002 -http//builder com com/5100-6372_14-1044112 html-4 p

45 Tormasov A G, Kuznetsov A N, Plant A Take advantage of TCP/IP options to optimize data transmission // Builder.com - 2002 - http//builder com com/5100-6372_14-1050771 html -3 p

46 Tormasov A, Khassine M, Beloussov S , Protassov S. Fault tolerant storage system and method using a network of servers // Патент - 2005 - № 6,961,868 (США) —12 p

47 Tormasov A, Beloussov S , Tsyphaev M, Lyadvinsky M System and method for using file system snapshots for online data backup II Патент - 2006 - № 7,047,380 (США) -27 p

48 Tormasov A, Beloussov S, Protassov S , Lunev D., Pudgorodsky Y Hosting service providing platform system and method // Патент - 2006 - № 7,076,633 (США) — 13 p

49 Tormasov A, Beloussov S, Protassov S, Lunev D, Pudgorodsky Y. Virtual computing environment // Патент - 2006 - № 7,099,948 (США) — 8 p

50 Tormasov A, Beloussov S, Protassov S, Pudgorodsky Y Distributed network data storage system and method // Патент - 2007 - № 7,209,973 (США) — 17 p

51 Tormasov A, Beloussov S , Protassov S, Method of implementation of data storage quota // Патент - 2008 - № 7,325,017 (США) — 16 p

52 Tormasov A, Beloussov, Protassov, System, method and computer program product for multi-level file-sharing by concurrent users // Патент - 2008 - № 7,328,225 (США) — 25 p

53 Tormasov A, Beloussov S , Tsyphaev M, Lyadvinsky M System and method for online data migration//Патент - 2007. - № 7,281,104 (США)— 17p

54 Tormasov A , Beloussov S , Protassov S , Pudgorodsky Y Common template file system tree for virtual environments and virtual servers // Патент - 2007 - № 7,222,132 (США) —6p

Все основные результаты, изложенные в диссертации, включая постановки задач и их алгоритмические решения, получены автором лично или выполнены под его научным руководством и при непосредственном участии В работе приводятся ссылки на кандидатские диссертации и дипломные работы, выполненные под научным руководством автора

В работах с соавторами лично соискателем выполнено следующее

[1,18,19,22] - мат модель производительности файловой системы, [3,31] - принцип построения децентрализованной системы безопасности без центра авторизации, требования к ней, мат. модель, доказательства безопасности, [4,12,23,30,33,50] -принцип использования (п,к)-технологии и алгоритмы хранения данных для обеспечения отказоустойчивости распределенной системы и способы реализации, [5-11,2429] - адаптация вычислительных схем разного типа для численного решения многомерных гиперболических уравнений для сложных моделей сред и сложной геометрии расчетной области, [1,20] - имитационная модель пересылки информации на графе и ее применение для оценки времени поиска, [15,16,20] - математическая модель и алгоритм наложенного группового управления ресурсами, [35,39,40,42,49,52,54] - типы и модели виртуализации, области ее применения, методы создания виртуальных сред, [43-45] - методика построения оптимальных высокоскоростных сетевых соединений, [46,48] - метод и технология организации распределенных хранилищ, [47,53] - технология онлайн миграции данных и процессов в виртуализованных средах, [51] -технология наложенного управления ресурсами ОС

ТОРМАСОВ Александр Геннадьевич

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ СРЕДСТВ УПРАВЛЕНИЯ РЕСУРСАМИ И ДАННЫМИ В РАСПРЕДЕЛЕННЫХ И ВИРТУАЛИЗОВАННЫХ СРЕДАХ

Автореферат

Подписано в печать 24.03 08. Формат 60x90/16. Уел печ л 2 1. Тираж 100 экз Заказ №37.

Московский физико-технический институт (государственный университет)

Печать на аппарате Rex-Rotaiy Copy Printer 1280 НИЧ МФТИ

141700, г. Долгопрудный, Московская обл., Институтский пер, 9 тел. (095) 4088430, факс (095)5766582 38

ВВЕДЕНИЕ.

В. 1.Актуальность темы.

В.2.Цель работы и объект исследования.

В.З.Методы исследования.

В.4.Научная новизна.

В.5.Теоретическая и практическая значимость.

В.б.Публикации и апробация результатов работы.

В.7.Экскурс в историю развития компьютерных технологий.

В. 8.Виртуализация.

В.8.1.Эмуляция компьютеров.

В.8.2.Виртуализация на высоком уровне.

В.8.3.Цели и задачи виртуализации.

В.9.Необходимость в виртуализации сервисов, что она предоставляет конечному пользователю.

В. 10.Существующие решения, связанные с распределенными хранилищами.

В. 10.1.Хранение данных.

В. 10.2.Кэширование.

ВЛО.З.Выбор оптимальной точки соединения.

В.10.4.Проблемы безопасности.

В. 11.Хранение с регулируемой избыточностью.

B.12.Grid системы.

В. 12.1.Что такое Grid.

В.12.2.Проблемы, которые не решает Grid.

В.12.3.Проблемы, которые порождает система на базе Grid.

ГЛАВА 1. СРЕДА ПОЛЬЗОВАТЕЛЯ.

1.1.Интересы потребителя.

1.1.1.Локальные сервисы, обслуживающие запросы пользователя.

1.1.2.Хранение и доступ к персональным данным.

1.1.3.Доступ к сетевым информационным источникам.

1.1.4.Персонализованный обмен информацией с абонентами.

1.1.5.Обслуживание, независимое от физического нахождения потребителя.

1.2.Мобильность сервиса как подход.

1.2.1.Мобильность пользователя.

1.2.2.Мобильность вычислительных ресурсов.

1.2.3.Мобильность данных.

1.2.4.Независимость сетевого доступа от внешних параметров.

1.2.5.История развития компьютерных сервисов.

1.2.5.1.Эволюция компьютерных сервисов.

1.2.5.2.Потребитель в современной автоматизированной среде.

1.2.5.3.Вычислительная среда потребителя.

1.3.Требования к идеальной среде пользователя.

1.3.1.Состав среды.

1.3.1.1.Вычислительные ресурсы.

1.3.1.2.Доступ к данным.

1.3.2.Расширяемая среда.

1.4.Мобильность и виртуализация сервисов.

1.4.1.Мобильность сервиса.

1.4.2.Виртуализаци я.

1.4.2.1.Виртуализация сервиса.

1.4.2.2.Виртуализация хранилища.

ГЛАВА 2. САМОРЕГУЛИРУЕМАЯ ВИРТУАЛЬНАЯ ВЫЧИСЛИТЕЛЬНАЯ СРЕДА.

2.1.Общие принципы представления данных в децентрализованном хранилище.

2.2.Алгоритм распределенного хранения данных с регулируемой степенью избыточности - (n,k) схема представления данных.

2.2.1.Предложенная модель распределенного представления данных.

2.2.2.Решения задач по организации алгоритмов сборки-разборки.

2.2.2.1.Алгоритмы над полем P=GF(N) и их производительность.

2.2.2.2.Алгоритмы сборки/разборки файлов.

2.3.Метод организации виртуального отказоустойчивого хранилища на базе (n,k) схемы представления данных.

2.3.1.Объединение серверов в группы.

2.3.2.Подключение клиентов.

2.3.3.Классы хранимых файлов.

2.4.Регулируемая отказоустойчивость.

2.5.Оптимальность доставки данных.

2.6.Предложенная технология реализации отказоустойчивого хранилища.

2.6.1.Топология и техническая организация взаимодействия серверов.

2.6.2.Клиентский сервер.

2.6.3.Транзакционная модель изменений и хранение данных.

2.6.4.Использование индексного дерева.

2.6.5.Генерация уникальных идентификаторов.

2.6.6.Директорный сервис.

2.6.7.Файловый сервер.

2.6.8.Топологический сервер.

2.6.9.Сервер кэширования.

2.6.10.3адача выбора оптимального соединения.

2.6.10.1.Локальность задачи.

2.6.10.2.Сущность алгоритма.

2.6.10.3.Оценки.

2.6.11.Алгоритм упорядочения идентификаторов относительно выделенного.

2.6.12.Алгоритм кэширования данных.

2.6.12.1.Предпосылки выбора модели.

2.6.12.2.0писание модели кэширования.

2.6.12.3.Оценка производительности.

2.7.Модель безопасности децентрализованной системы хранения данных, базирующаяся на декларируемых полномочиях.

2.8.Соответствие предложенного метода набору требований к хранилищу.

2.8.1 .Вычислительные ресурсы.

2.8.1.1.Изоляци я.

2.8.1.2.Утилизаци я.

2.8.1.3.Безопасност ь.

2.8.1.4.Управляемост ь.

2.8.2.Доступ к данным.

2.8.2.1.Легкость выделения.

2.8.2.2.Изоляци я.

2.8.2.3.Разделени е.

2.8.2.4.Прозрачност ь.

2.8.2.5.Коммуникабельност ь.

2.8.2.6.Пригодность для поиска.

2.8.2.7.Легкость наращивания.

2.8.2.8.Надежность и доступность.

2.8.3.Расширяемая среда.

2.9.Математическая модель поиска данных.

2.9.1.Описание метода доставки.

2.9.1.1.Предпосылк и.

2.9.1.2.Схема метода.

2.9.2.Прогнозирование времени поиска.

2.9.2.1.Модель для расчетов.

2.9.2.2.0ценка времени поиска.

2.9.2.3.Особенности практического использования выведенного.

2.9.2.4.Пример использования.

2.10.Анализ производительности распределенной системы.

2.10.1.Оценка накладных расходов операций чтения и записи в системе.

2.11.Алгоритм оптимизированного размещения данных в группах серверов.

2.11.1.Сервер поддержки уровня избыточности.

2.12.Выбор алгоритмов работы хранилища в разных условиях.

2.12.1.Реализация хранилища в виде локального связанного кластера.

2.12.2.Реализация хранилища в виде глобального кластера.

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

3.1.Принципиальная децентрализованность системы.

3.2.Декларируемые полномочия.

3.3.Перенос защиты с серверов на клиенты.

3.4.Отсутствие необходимости сертификации серверов и инфраструктуры системы

3.5.Базовые понятия математической модели средств разграничения доступа хранилища.

3.5.1.Определения и аксиомы.

3.5.2.«Правила вывода».

3.6.Математические модели контроля доступа для распределенной децентрализованной файловой системы TorFS.

3.6.1.Используемые обозначения.

3.6.2.Аутентификация пользователей системы.

3.6.3.Математическая модель контроля доступа, названная «анонимной».

3.6.3.1.Фай л.

3.6.3.2.Структура директории.

3.6.3.3.Структура ACL.

3.6.3.4.Корневая директория.

3.6.3.5.Примеры основных операций в системе.

3.6.4.Математическая модель контроля доступа с протоколированием.

3.6.5.Математическая модель контроля доступа, включающая «владельца».

ГЛАВА 4.МАТЕМАТИЧЕСКИЕ МОДЕЛИ ВЫЧИСЛИТЕЛЬНЫХ РЕСУРСОВ

4.1.Математическая модель вычислительных ресурсов компьютера и способа их потребления.

4.1.1.Компьютер и ресурсы операционной системы.

4.1.2.Формализации модели.

4.1.3.Сетевые вычислительные модели для нелинейных систем уравнений гиперболического типа.

4.1.4. Особенности топологии графов в моделировании реальной вычислительной системы.

4.1.5.Пример расчета для связанных параметров.

4.1.5.1.Модел ь.

4.1.5.2.Вычислительный алгоритм.

4.1.5.3. Аппроксимация.

4.1.5.4.Устойчивост ь.

4.1.5.5.Усиление устойчивости.

4.1.5.6.Сходимост ь.

4.1.5.7.Моделирование нагрузки на http-cepBep.

4.1.5.8.Моделирование нагрузки на йр-сервер.

4.1.6.Выводы по разделу.

4.2.Обобщенная математическая модель наложенного управления ресурсами операционных систем.

4.2.1.Математическая модель наложенного управления.

4.2.2.Классификация типов ресурсов.

4.2.2.1.Возобновляемые ресурсы.

4.2.2.2.Невозобновляемые и частично возобновляемые ресурсы.

4.2.3.Выводы по разделу.

4.3.Модель и метод наложенного управления ресурсами CPU.

В. 1. Актуальность темы

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

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

Следующим шагом в эволюции технологии организации компьютеров становится их объединение в сеть. В последние годы резко возрос интерес к решению проблемы организации современных распределенных сред, призванных хоть как то решить проблемы потребителей, возникающие при использовании современной компьютерной инфраструктуры. Разрастание коммуникационной инфраструктуры, появление и активное использование одноранговых сетей доставки файлов и живого обмена аудио- и видеоданными (технологии Skype, BitTorrent, Kazaa и др), факты злоупотребления компьютерными технологиями, происходящий сдвиг в принципах использования современных компьютеров - все это заставило задуматься о сути происходящих процессов и попытаться переосмыслить применяемые в разработке компьютерных систем и программ подходы, перейдя от автономного компьютера к их объединению в виде единой распределенной среды виртуализованных вычислительных ресурсов.

Такие интенсивно развивающиеся в последние годы направления исследований, как GRID, Internet2, Web 2.0/3.0, реализация поддержки во всех современных ОС технологий аппаратной виртуализации компаний Intel и AMD подтверждают актуальность темы диссертационного исследования в области математического моделирования средств управления ресурсами и данными в распределенных и виртуализованных средах.

В.2. Цель работы и объект исследования

Цель диссертационной работы - разработка нового подхода к созданию распределенных и виртуализованных сред, ориентированных на размещение, хранение и управление ресурсами и данными, построение и анализ математических моделей, описывающих компоненты такой среды, в том числе математических моделей интегрированных средств контроля доступа для таких сред. Задачи исследования:

- Анализ набора требований к распределенной и виртуализованной среде и их классификация;

- Разработка метода реализации и алгоритмов функционирования подсистем среды, удовлетворяющих большинству сформулированных требований;

- Разработка математических моделей, необходимых для описания поведения компонентов среды и обоснования выбора параметров и алгоритмов;

- Разработка интегрированной системы контроля доступа распределенной среды, создание ее математической модели и доказательство корректности функционирования системы в рамках сформулированных ограничений.

Объект исследования - методы и алгоритмы управления распределением ресурсов, методы и алгоритмы организации и работы распределенных систем, децентрализованные интегрированные системы контроля доступа, математические модели потребления вычислительных ресурсов, технологии виртуализации и их моделирование.

В.З. Методы исследования

В ходе научных исследований по разработке математических моделей и алгоритмов управления ресурсами и данными в распределенных и виртуализованных средах использовались методы дискретной математики и алгебры, вычислительной математики, методы математической статистики, методы теории операционных систем и системного программирования.

В.4. Научная новизна

В работе впервые предложены: • Модель виртуализации объектов уровня операционной системы путем разделения их в пространстве имен;

• Обобщенная математическая модель и алгоритмы группового многоуровневого управления ресурсами, необходимые для виртуализации уровня ОС и других технологий виртуализации;

• Математическая модель вычислительных ресурсов компьютера и способа их потребления, использующая алгебраические и дифференциальные уравнения в частных производных гиперболического типа;

• Технология и алгоритмы организации, а также классификация требований к новому поколению распределенных сред управления данными;

• Метод использования для построения такой среды (п,к)-схемы разделения данных и его эффективная реализация в конечных полях Галуа;

• Принципы создания и алгоритмы функционирования распределенных виртуализованных сред на несимметричных серверах и каналах связи с открытой коммуникационной инфраструктурой, ориентированных на размещение, хранение и управление ресурсами и данными;

• Математические модели децентрализованных систем контроля доступа.

В.5. Теоретическая и практическая значимость

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

Результаты работы внедрены в крупных компаниях - производителях ПО (SWsoft/Parallels, Acronis - в этих компаниях совокупно работает более 1000 инженеров). На основании разработок диссертанта создана новая отрасль индустрии ПО виртуализация ОС». ПО, включающее в себя алгоритмы, разработанные диссертантом, установлено у более чем 700,000 потребителей в 125 странах на 17000 серверах (технология Virtuozzo®).

По результатам работы получено 14 патентов США и подано более 80 заявок на патенты США. Эти патенты являются международными объектами интеллектуальной собственности в странах, входящих в World Patent Organization, в том числе в России. Результаты работы могут быть использованы в учебном процессе при подготовке специалистов в области ОС, виртуализации и распределенных сред.

В.6. Публикации и апробация результатов работы

По теме диссертации опубликовано 54 работы, из них 11 статей [1-11] - в ведущих рецензируемых научных журналах и изданиях, рекомендованных ВАК РФ для публикации материалов докторских диссертаций, 7 публикаций в сборниках трудов международных конгрессов, симпозиумов, конференций [21; 25; 26; 30; 33; 36; 41].

В работах с соавторами лично соискателем выполнено следующее:

1; 18; 19; 22] - мат. модель производительности файловой системы; [3; 31] - принцип построения децентрализованной системы безопасности без центра авторизации, требования к ней, мат. модель, доказательства безопасности; [4; 12; 23; 30; 50] - принцип использования (п,к)-технологии и алгоритмы хранения данных для обеспечения отказоустойчивости распределенной системы и способы реализации; [5; 11; 24; 29] -адаптация вычислительных схем разного типа для численного решения многомерных гиперболических уравнений для сложных моделей сред и сложной геометрии расчетной области; [14; 17] - имитационная модель пересылки информации на графе и ее применение для оценки времени поиска; [15; 16; 20] - математическая модель и алгоритм наложенного группового управления ресурсами; [35; 39; 40; 42; 49; 52; 54] - типы и модели виртуализации, области ее применения, методы создания виртуальных сред; [43; 44; 45] -методика построения оптимальных высокоскоростных сетевых соединений; [46; 48] -метод и технология организации распределенных хранилищ; [47; 53] - технология онлайн миграции данных и процессов в виртуализованных средах; [51] - технология наложенного управления ресурсами ОС.

Результаты работ по диссертации докладывались и обсуждались на многочисленных научно-исследовательских семинарах и конференциях, основные из них: «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 ежегодные научные конференции Московского физико-технического института (Москва-Долгопрудный, 19972007гг) и др.

В.7. Экскурс в историю развития компьютерных технологий

Интернет как средство общения появился весьма давно, более 30 лет назад. Он не был задуман и создан как единое целое, он просто развивался в соответствии с потребностями общества. Технологическую его основу составил сетевой протокол TCP/IP, получивший столь большую поддержку за то, что позволил построить легко расширяемую инфраструктуру, обеспечивающую отказоустойчивые возможности по доставке данных. Набор сервисов, традиционных для потребителя услуг комплекса "Интернет + компьютер", формировался стихийно, путем, напоминающим искусственный отбор. Новые сервисы появлялись очень часто, но и отмирали не менее часто, так же как и реализующие их программы. Сейчас к основным сервисам Интернет можно отнести сервис гипертекста (WWW), сервис доставки файлов FTP (хотя следует признать что масштаб его использования понемногу уменьшается, так как он дублирован HTTP), почтовый сервис, и, отчасти, сервис обмена немедленными сообщениями. Все большее распространение получает сервис потокового аудио и видео, но его широкому распространению препятствуют проблемы, связанные с недостатком пропускной способности сети.

Развитие вычислительно техники привело к тому, что рост производительности аппаратного обеспечения имеет практически экспоненциальный характер. Так, существуют несколько эмпирических «законов развития», которые выполняются с хорошей точностью в последние годы.

Первый закон Мура (Moore). Сформулирован в 1965 в статье в журнале Electronics [55]одним из основателей корпорации Intel, и, в оригинальной формулировке, гласил, что плотность компонентов электронной техники на одной типовой микросхеме будет удваиваться каждые 12-18 месяцев. В дальнейшем он трансформировался в утверждение, что мощность микропроцессоров при одинаковой цене будет удваиваться каждые 12-18 месяцев. Как ни странно, этот закон действительно выполняется последние 37 лет, и имеет тенденцию к выполнению в будущем. Например, Intel декларирует своей целью выпуск микропроцессора, состоящего из миллиарда транзисторов к 2010 году.

Второй закон Мура, сформулированный в интервью журналу Wired, касается уже стоимости заводов по производству микропроцессорного оборудования, и сводится к утверждению, что рост стоимости заводов будет обгонять стоимость собственно выпушенных микропроцессоров [56]. Например, если в 1995 году стоимость завода по выпуску кремниевых пластин была равна примерно 1 миллиарду долларов и составляла в общей сложности около 1% годового оборота рынка микропроцессоров, то к 2011 году ожидается что стоимость одного завода будет составлять около 70 миллиардов долларов и общая доля затрат на завод будет составлять приблизительно 13%. Кроме того, следует отметить тот факт, что эпоха «экстенсивного роста» средств оптического произодства пластин (оптической литографии) упрется в запреты на «физическом уровне» к 2017 году [57].

Утверждение Шутгарта (Shugart) [58], основателя и руководителя одной из ведущих компаний-производителей винчестеров Seagate, относится к экспоненциальному росту емкости средств хранения данных. В последние 10 лет этот рост идет даже быстрее, чем рост мощности микропроцессоров (закона Мура). Стоимость хранения 1 мегабайта данных упала с 11.54$ в 1988 году до 0.01$ сегодня, причем количество производителей такого оборудования тоже упало с 75 до 13. Тем не менее, потребность в хранилищах данных весьма велика и в последние годы обострилась из-за роста числа потребителей цифровой фотографии (оценка - в год в мире делается около 80 биллионов цифровых фотографий, которые требуют более 400 петабайтов для хранения).

Единственной технологией, относящейся к области электроники, которая не испытывает экспоненциальной рост, является технология беспроводной связи (wireless networking). Тем не менее количество устройств, использующих ее, так же существенно увеличивается и они начинают входить уже буквально во все области повседневной жизни. Так, например, кроме традиционных устройств беспроводного обмена информацией (сотовые телефоны, компьютеры с Wi-Fi, персональные цифровые компьютеры PDA и тд) скоро получит высочайшее распространение технология радиосенсоров, которые призваны заменить так называемые «бар коды», используемые для идентификации продукции в магазинах, на складах и производстве. Таким образом, количество устройств, использующих технологию беспроводной связи, на одного человека, может быть оказаться около десятка или более.

Закон Гилдера (Glider) [59] уже касается производительности оптических средств связи (оптико- волоконных носителей), и был сформулирован в середине 90-х годов. Он гласит, что оптическая емкость одного волокна оптоволоконного кабеля будет утраиваться каждый год. Это дает возможность прокладки все более производительных оптических кабелей (являющихся сейчас основой глобальной инфраструктуры Интернет), которая в своем экспоненциальном развитии следует или даже опережает рост производительности микропроцессоров. Типичный оптический кабель несет возможность передачи до 640 Gb/s. Только в одном городе Нью Йорк общая пропускная способность локальных и глобальных сетей оценивается в 23.5 Tb/s. Стоимость аренды кабеля класса ОСЗ (155 Mb/s) от JIoc Анжелеса до Нью Йорка упала с 18 миллионов долларов в начале 2000 года до 190 тысяч два года спустя, в Европе стоимость аренды каналов с 1990 года до 2002 упала на 85-90%.

Первым количественную оценку значимости сетей дал изобретатель Ethernet Роберт Меткалф. По его наблюдению, которое теперь называют «законом Меткалфа» [60], значение сетей возрастает пропорционально квадрату числа узлов сети. В последние годы появились уточнения. Одни исследователи (Эндрю Одлышко и Бенджамен Тилли [61]), считают, что Меткалф завысил оценку, что зависимость не квадратичная, а логарифмическая, согласно закону Зипфа. Закон, названный в честь Джорджа Зипфа (19021950), был выведен на основании исследования частоты использования слов в тексте. Если наиболее часто используемое слово встречается п раз, то второе по частоте — в к раз реже, то есть n/к, третье — n/к2 и т.д. Применительно к ценности сети имеется в виду, что значение отдельных связей с ростом их числа уменьшается. Другие, подобно Дэвиду Риду, автору одноименного закона, учитывающие социальную сторону сетей, придерживаются противоположного мнения. Они утверждают, что оценка Меткалфа занижена, что зависимость не квадратичная, а экспоненциальная. Какой бы не была истинная оценка, значение сетевого эффекта для развития компьютеров не вызывает сомнения.

Сейчас в инфраструктуру Интернет входит более 2000 крупных центров данных по всему миру, 140 мировых точек обмена трафика, и практически все потребители переходят на широкополосное подключение - так, например, в Корее 85% подключений Интернет являются широкополосными, а в Китае запланировано к 2005 году подключить 1М домов соединениями по сети Ethernet.

Наблюдается также повышенная активность производителей оборудования и программ для так называемого «цифрового дома» - новой инфраструктуры, призванной облегчить жизнь потребителя в современном электронном доме с десятками вычислительных единиц, применяющихся для управления разнообразными устройствами. Например, кроме традиционного производителя процессоров для подобных систем -фирмы Интел, недавно консорциум, в который входят компании IBM, Toshiba и Sony анонсировал специальный процессор Cell [62], предназначенный для нового поколения компьютерных систем и цифровых устройств бытовой электроники. Согласно утверждениям производителей, Процессор Cell является новым решением, в основе которого лежит гибкая параллельно-распределенная вычислительная архитектура, состоящая из независимых процессоров с плавающей запятой для выполнения интенсивных мультимедийных нагрузок. Само слово Cell обозначает программное обеспечение, предназначенное для изыскания свободных ресурсов на индивидуальной машине, в локальной или глобальной сети.

Таким образом, наблюдается экспоненциальный рост производительности процессоров и их номенклатуры, пропускной производительности сетей и емкости хранилищ данных, а так же численный рост количества установленных компьютеров и объектов сетевой инфраструктуры. Тем не менее, общепризнано, что рост потребностей потребителей обычно превышает предоставляемые инфраструктурой возможности -всегда есть новые заманчивые для потребителя сервисы, активное использование которых способно «убить» любую инфраструктуру. Сейчас примером такого сервиса является передача видео по сетям, особенно живых видеотрансляций.

Одним из наиболее существенных аспектов развития становится безопасность систем. Без соответствующей поддержки уровня безопасности серверов и коммуникаций использование их обычными потребителями уже не представляется возможным. Типичным примером является проблема спама при электронных коммуникациях - без борьбы с ним использование сервиса электронной почты уже совсем скоро становится лишенным всякого смысла, так как более 90% приходящих писем носят рекламный характер.

Экспоненциальный рост инфраструктуры, к сожалению, означает и близкий к нему рост сложности управления этой инфраструктурой. Увеличивается количество объектов, над поведением которых задумывается потребитель, растет количество средств управления ими, а разнообразие во всевозможных пультах управления, клавиатурах и графических интерфейсах может запутать и самого квалифицированного инженера.

Таким образом, стихийное эволюционное развитие системы Интернет и компьютерных технологий привело к ситуации, когда их использование в полезных целях даже квалифицированным пользователем проистекает с большими препятствиями и крайне непросто.

Более того, существующие технологии очень часто решают проблемы, возникшие из-за их собственного несовершенства. Причем успешность компаний, которые занимаются такой деятельностью, часто мешает увидеть другие способы их решения. К примерам такой деятельности можно отнести историю компании Google. Она имеет очень большие финансовые успехи, которые базируются на успешной реализации системы поиска данных в мировой сети. Основные доходы эта компания получает путем встраивания в результаты поиска для конечных пользователей релевантной рекламной информации, что дает возможность выхода на большой рекламный рынок даже маленьким компаниям. Но некоторые исследователи, исходя из очевидного для них тезиса, что правильность курса компании подтверждается ее текущими успехами, считают, что будущим Интернета является система в которой легко все искать, в которой возможность поиска встроена всюду. Проблема то в том, что на самом деле конечному пользователю сам поиск не нужен, он даже вреден - его тяжело инициировать, еще более тяжело понять что же тебе нашли по твоему запросу, найти в этом то что действительно нужно и т.д. По мнению автора работы, при текущем способе хранения информации и развития Интернета наличие такого поиска является печальной необходимостью и платой за рост.

Взгляд на такого рода проблемы «со стороны» для людей, которые активно «живут» в Интернете обычно очень сложен, так как привычка к текущему окружению влияет на наше представление об оптимальном решении окружающих нас проблем. Иногда прогнозы развития мировой сети напоминают известный прогноз основных проблем 20 века, сделанный в 19 веке - когда ученые экстраполируя окружающую действительность пришли к выводу, что основной проблемой городов 20 века будет гигантский слой навоза от лошадей, который надо будет куда-то убирать (для Нью Йорка он прогнозировался толщиной около 5 метров).

Итак, существует потребность в решениях, которые могли бы упорядочить использование компьютерных и сетевых ресурсов сети «Интернет».

Рассмотрим существующие в настоящий момент решения, части которых можно позаимствовать при создании «идеализированной системы».

В.8. Виртуализация

Одним из неочевидных способов решения проблемы организации компьютерной среды является использование подхода виртуализации вычислительных сервисов [34; 38; 39; 40; 42].

Под термином «виртуализация» очень часто объединяются сильно различные понятия. Рассмотрим их в применении к компьютерным технологиям на примере работы типовой операционной системы современной универсальной вычислительной машины (ОС) [34; 35; 40].

Одной из основных функций операционной системы всегда была унификация способа взаимодействия пользовательских программ с аппаратурой [63; 64], в частности, создание такого способа взаимодействия с устройством, при котором все специфические операции скрываются от пользователя. То есть ОС дает возможность прикладным программам возможность исполняться, предоставляя им некий набор API (application program interface - прикладных программных интерфейсов). При помощи этого набора программа прямо или опосредованно могла обращаться к внешним устройствам и файловой системе, посылать и получать сетевые пакеты данных, создавать и удалять другие процессы, обмениваться с ними информацией и т. п. А чтобы предоставлять такие возможности, ОС должны уметь работать с физическими устройствами.

Одной из основных функций ОС всегда была унификация способа взаимодействия пользовательских программ с аппаратной частью, и при этом обычно применялась какая-то реализация идеи виртуализации. Так, программа пользователя, работающая с файловой системой, размещенной на дисковом накопителе, видит его как некий обобщенный или виртуальный диск, не зная о технических деталях реализации того, что лежит "снизу", -скажем, SCSI это или IDE-диск, а, может быть, вообще USB флэш-устройство.

Другой смысл термина "виртуальный" - несуществующий физически. Например, виртуальная память процесса в некотором роде противопоставляется физической. Впрочем, и первый подход можно охарактеризовать как имеющий отношение к "несуществующему" виртуальному устройству, с которым работает сервис ОС, обеспечивающий возможности файловой системы поверх виртуального, обобщенного блочного хранилища данных с прямым доступом. Такое содержание термина "виртуальный" отражает один из доминирующих сейчас принципов организации ОС. Но и в этом плане существуют разные уровни виртуализации понятий.

До сих пор при реализации ОС виртуализация как подход наиболее активно использовалась на уровне именно устройств. Если рассмотреть традиционную иерархию понятий: нижний уровень - уровень прямого доступа к оборудованию, средний уровень -драйверов устройств, предоставляющих обобщенный интерфейс управления ими, и верхний уровень - набор сервисов ОС, предоставляемых уже приложениям пользователя, то можно отметить, что наиболее активно виртуализация применялась на среднем уровне. Когда появлялось новое устройство, то единственный способ его поддержки для приложений обычно сводился к тому, чтобы получить вместе с устройством некий "среднеуровневый" драйвер ОС, который непосредственно управлял самим устройством в "аппаратных" терминах (таких, как команды in/out и т. д.), предоставляя "наружу" возможность управления в терминах API (например, в виде графического драйвера, имеющего стандартный набор функций для рисования точек, линий, поверхностей и т. д.). Причем с точки зрения ОС этот интерфейс действительно был универсален для разных адаптеров устройств, т. е. в системе как бы было установлено одно или несколько "виртуальных" устройств, предоставляющих определенный сервис (в данном случае рисование изображения).

Тем не менее существовали и другие подходы, на других уровнях - верхнем и нижнем. Исторически сначала появился подход низкоуровневой виртуализации - когда ОС "подсовывалось" виртуальное, а не физическое устройство. Вообще, если рассматривать ОС как единый объект, обладающий некими "органами чувств", т. е. средствами общения с внешним миром, то для нее единственным способом определить наличие и состояние какого-либо объекта остаются стандартные действия, описываемые обычно производителем "железа" - начиная от детектирования подключения этого устройства (сейчас это обычно выполняется за счет специального протокола Plug-and-Play) до возможности "пощупать" оборудование путем выполнения каких-то конфигурационных действий (например, можно отправить на последовательный порт, к которому, как предполагается, подключен модем, текстовую строку "AT" и ожидать, что, если модем работает, обратно придет текстовая строка "ОК").

В таких условиях появляется возможность создать своего рода «виртуальную реальность» для «органов чувств» ОС. Если сымитировать ответы физических устройств программным способом, то как раз и получится "виртуальная реальность", состоящая из виртуальных моделей физических устройств, которые дают вполне осмысленные ответы на запросы ОС и поведение которых максимально приближено к оригиналу. Иными словами, получится некий эмулируемый компьютер - виртуальная среда - набор виртуального оборудования, которое практически полностью эквивалентно такому же набору физического оборудования - "ящику с компьютерным железом". Естественный следующий шаг - установка самой обычной ОС внутрь такого "виртуального ящика" и использование его для предоставления какого-либо сервиса.

В.8.1. Эмуляция компьютеров

Одной из первых по этому пути пошла компания IBM со своими мэйнфреймами, ОС OS/3xO (последняя из них - OS/390), ОС VM и системой LPAR (Logical partitioning). Пользователь получал в свое распоряжение полноразмерный и полнофункциональный виртуальный компьютер, на который он мог поставить собственную версию ОС и установить собственное прикладное ПО. В этом компьютере имелась оперативная память, возможность использования ресурсов процессора, собственные виртуальные периферийные устройства (диск или сетевая карта) - практически все то, чем обладает обычный компьютер, только в виртуальном виде. Число виртуальных компьютеров, обслуживаемых на одном аппаратном компьютере, зависело от многих факторов, в частности, от лицензии, доступных ресурсов памяти или диска, возможностей центрального процессора и т. д. На мощной физической машине можно было запустить множество виртуальных; например, IBM утверждает, что на S/390 реально запустить более десятка тысяч копий виртуальных компьютеров с ОС Linux.

Упрощенную версию такого подхода (а может быть, и усложненную, это зависит от точки зрения) представляют собой эмуляторы ПК, распространенные на обычных IBM PC-совместимых компьютерах, - системы виртуальных машин (virtual Machine, VM). Они реализуют аналогичный подход на традиционной архитектуре Intel х86 (хотя сейчас появляются и версии для 64-разрядной архитектуры Intel IA-64, но для простоты мы будем рассматривать системы для IA-32, включив туда и 64 битное расширение архитектуры х64).

Существует несколько проектов эмуляторов, использующих разные технологии и подходы и находящиеся на разных этапах своего жизненного цикла. Это и коммерческие реализации, такие, как предлагаемая компанией EMC VMware (http://www.vmware.com), решение, активно использующее аппаратную поддержку виртуализации компании SWsoft Parallels (www.parallels.com), Microsoft virtual PC/virtual Server (http://www.microsoft.com), и открытые - например, проекты системы паравиртуализации Хеп (http://www.cl.cam.ac.uk/Research/SRG/netos/xen), Р1ех86 (http://www.plex86.org) и UML (http://usermodelinux.org) для ОС Linux. Практически все они включают так называемый VMM - монитор виртуальных машин, который обслуживает запросы виртуальных машин, выполняет эмуляцию памяти, разделение доступа к ресурсам, изоляцию и т. д. Сам VMM обычно загружается через так называемую Host OS (основную ОС) - ту копию ОС, которая сама непосредственно работает с физическими устройствами. Другим способом реализации того же подхода является использование т.н. «гипервизора», который управляет доступом к ресурсам и обычно использует VMM на другом уровне привилегий, «депривилегируя» даже основную (host) ОС (проект Хеп, система ESX server компании EMC VMware и другие).

Эмулятор компьютера представляет собой некий процесс, внутри которого осуществляется моделирование набора стандартных устройств компьютера — памяти, сетевой платы, графической платы, клавиатуры, мыши и т.д. Особо стоит отметить, что кроме устройств эмулируется и BIOS, поэтому в этот процесс можно ставить полнофункциональную операционную систему, которая будет работать «не зная» о том, что она находится внутри эмулятора. Более того, на He-Intel платформах существовали и активно использовались до последнего момента системы, эмулирующие систему команд Intel — например, такой эмулятор входил в состав поставки Windows NT для процессора Alpha компании DEC (www.insignia.eom/about/default.asp#l).

Принцип использования ресурсов основной ОС близок к идее разделов: такие ресурсы, как оперативная память компьютера и дисковое пространство, делятся между экземплярами запущенных эмуляторов, практически исключая совместное использование. Копия ОС, вернее, набора ее файлов, необходимых для функционирования ОС, у каждого экземпляра виртуального компьютера будет своя. Особая сложность - эффективное использование собственной оперативной памяти виртуального компьютера, поскольку ее практически никак нельзя разделить между разными экземплярами VM эмуляторов. Отдельную проблему в такого рода решениях создает и тот факт, что ОС внутри эмулятора ничего не знает о существовании внешней ОС и, например, считает своим долгом в случае отсутствия активности своих процессов загрузить процессор выполнением процесса типа idle (в Unix). Еще одна проблема - двойное кэширование данных: обращение к данным пытаются кэшировать обе ОС, что явно не повышает производительность. Надо отметить, что другие ресурсы, например, сетевая плата или процессоры, честно делятся между всеми экземплярами эмуляторов.

В результате работа одного ядра ОС внутри другого приводит к существенной потере производительности системы в целом. Такая реализация системы не позволяет запускать достаточно большое число экземпляров виртуальных машин на одном компьютере; практически допустимое их число лежит в диапазоне от одной до четырех-пяти на типовую рабочую станцию.

Технически реализация подобных VM-систем в архитектуре х86 - весьма непростая задача, так как при проектировании Intel не предусматривала подобных задач. В результате часть команд, которые могут выполнять ОС, не должны быть разрешены для исполнения внутри VM. Самым простым способом решения этой проблемы была бы возможность получать так называемые прерывания или исключения при попытке выполнения этих команд внутри VM, с тем чтобы обрабатывать их внутри VMM. Но проблема в том, что простого способа вызвать это исключение для некоторого класса команд не существует. Они просто отработают внутри VM, дав при этом не тот результат, которого ожидали разработчики ОС, причем иногда выполнение такой небезопасной команды может вызвать сбой в основной ОС или даже зависание всего компьютера -например, команд ввода вывода in/out. Кроме собственно команд типа in/out, требующих особой обработки, требует особого внимания и команды, обращающиеся к заранее неизвестным областям памяти (скажем, возврата из функций по заранее неизвестному адресу в стеке или перехода по регистру), которые должны обрабатываться в процессе работы эмулятора. Существенную долю процессорного времени система в процессе исполнения т.н. «гостевого кода» (кода, находящегося внутри VM) тратит на разрешение подобного рода проблем. Они решаются разным образом - от бинарной трансляции исполняемого кода перед его реальным исполнением, как в технологии VMware, до обработки специальных отладочных прерываний или эмуляции команд, как в технологии компании Parallels, или путем модификации ОС, расположенной внутри VM (подход паравиртуализации Хеп).

Недавно компания Intel анонсировала поддержку виртуализации инструкций, вернее, возможность специального способа исполнения инструкций, удобного для реализации таких эмуляторов, во всех типах своих новых процессоров архитектур IA-32 и IA-64 - как для серверов, так и для рабочих станций (технология под названием Intel virtualization Technology VT [65]). Все новые процессоры Intel будут выходить с этой поддержкой, начиная с 2006 года. Аналогичные планы анонсировала и компания AMD (технология под кодовым словом Pacifica или SVM - secure virtual machine). Подобная поддержка теоретически упростит создание аналогичных программных продуктов и повысит их эффективность (хотя вопрос о реальной степени ускорения процедур эмуляции архитектуры остается пока открытым). Тем не менее, этот анонс ведущего производителя процессоров говорит о том, что в достаточно близком будущем использование технологий VM становится повсеместным, от ноутбуков до высокопроизводительных серверов. Большинство мировых аналитиков сходится в мнении что в той или иной степени виртуализация будет присутствовать абсолютно всюду, в любых вычислительных устройствах от самых простых до самых сложных.

В.8.2. Виртуализация на высоком уровне

Посмотрим теперь на другой уровень виртуализации - высокоуровневую виртуализацию, или виртуализацию API. Чтобы разобраться в ней, стоит выяснить, зачем вообще нужна виртуализация.

Если говорить о нижнем уровне, то цель виртуализации "физического ящика с оборудованием" может быть разной, но обычно такие VM используются для упрощения установки и развертывания машин (ведь все виртуальные эмуляторы обычно имеют одинаковую конфигурацию), например, при тестировании. Иногда VM также применяют для консолидации серверов или для поддержки старых приложений, которые не могут работать с новыми версиями ОС (именно для таких целей Microsoft предлагает использовать свой virtual Server). Виртуализация также удобна для отладки программ, опробования новых версий "заплаток" (не "сломают" ли они имеющиеся программы) и т. д.

Если взять средний уровень, там цель, казалось бы, очевидна - надо уметь использовать в рамках одной ОС максимальное разнообразие физических устройств, а следовательно, предоставлять пользовательским и системным процессам унифицированный интерфейс взаимодействия.

Но, если вдуматься, для пользовательских процессов ОС, - которые, собственно, и предоставляют сервисы пользователям, - наличие "виртуального оборудования", в общем-то, безразлично, их интересует только, чтобы те способы коммуникации, которые они применяют для связи с ОС, отрабатывались наиболее удобным и эффективным образом. Вот так и появляется "высокоуровневая виртуализация", которая обеспечивает для каждой среды исполнения (будем называть ее виртуальной средой - VE) свое собственное уникальное изолированное окружение - свои файлы и другие ресурсы (в том числе системные), свои сервисы, свои системные способы связи с внешним миром и т. д. [49].

Иными словами, с точки зрения приложения оно запускается в собственном компьютере с основной ОС, и пользователь может делать с этой средой (VE) все, что обычно может делать администратор машины, - запускать и останавливать приложения и системные сервисы, устанавливать обновления приложений, конфигурировать сеть и сетевой экран, перезапускать VE [32; 35; 37; 38; 40]. От оборудования, как видно из рис. 1, среда пользователя (VE) отделена специальным "уровнем виртуализации", вводящим понятие VE в корневую (или основную) ОС. Кроме того, появляются дополнительные возможности, которые не так просто реализовать на физическом компьютере или внутри VM - например, быстрая и эффективная установка приложений внутри множества VE, быстрая миграция [47; 53] (со временем недоступности сервера 1-3 с или даже вообще без остановки сервисов и прерывания сетевых сессий), динамическое управление ресурсами системы, выделяемыми конкретному VE и его процессам.

Автору диссертации принадлежат идея разработки подобной технологии виртуализации ядра операционной системы. Начиная с 1999 года он принимает активное участие в разработке технологии виртуализации под названием Virtuozzo® в компании SWsoft [66], которая была создана непосредственно для этой деятельности, и в рамках которой сейчас работает по всему миру более 600 инженеров. Приоритет автора в создании указанной технологии виртуализации, включая виртуализацию файловых систем, зафиксирован в полученных патентах США [49; 52; 54].

Для реализации подхода была выбрана идея разделения доступа путем изоляции пространства имен (namespace). Все объекты уровня ядра ОС имеют какие то идентификаторы, позволяющие их разделять. Обычно это или имя объекта в виде текстовой строки (пример - имя файла или ключа в Windows registry), специальные выделенные идентификаторы (типа pid - process identifier - идентификатор процесс, или fid - file identifier - идентификатор файла в файловой системе), просто какие то числа, являющиеся обычно номерами строк в специальных таблицах (пример - handle - «номер» графического объекта в программе ОС Windows), или просто адрес в виртуальном адресном пространстве процесса, возвращаемый при создании структуры данных для объекта. Существенным является тот факт, что в контексте вызова используемый идентификатор является уникальным, то есть отвечающим за один определенный объект, работу с которым и подразумевает тот, кто использует идентификатор. Таким образом, если ктото (например, процесс пользователя) хочет работать с объектом, то он использует для этого его идентификатор в качестве адреса.

Все объекты со своими адресами и связанными с ними идентификаторами объединяются в группы (обычно иерархические) - пространства имен (namespaces). Внутри пространства имя объекта обычно уникально, но, в разных пространствах, разные объекты могут иметь одно и тоже имя.

Современные операционные системы имеют развитую структуру именования объектов, на которую замкнуты практически все их возможности. Так, чтоб, например, послать сообщение процессу, завершить его или изменить приоритет необходимо знать его идентификатор pid, являющийся параметром вызова соответствующего системного сервиса.

Идея виртуализации и изоляции на уровне пространства имен состоит в том, что мы создаем более высокий уровень иерархии адресов объектов (чем имеющиеся уже уровни в ОС), объединяем пространство имен в группу (назовем ее VEn где п - порядковый номер создаваемой среды) и создаем группу процессов, для которых любые системные вызовы содержат параметры из группы VEn. Например, если раньше программа обращения к ключу регистра Windows в качестве параметра указывала имя ключа как «HKEYLOCALMACHINE\SOFTWAREVApple Inc.VApple Software Update» и получала к нему доступ, то, теперь, если она находится в контексте группы 101, то при использовании того же параметра она получит доступ (скрытым от нее образом, «она об этом знать не будет» к ключу «\\Machine\VE 101VHKE YLOC ALM ACHINE\S OFTWAREVApple Inc.YApple Software Update». Таким образом, две таких программы, запущенных в разных VE 101 и 102, обращаясь к одинаковому имени ключа «HKEYLOCALMACHINE\SOFTWARE\Apple Inc.VApple Software Update» получат доступ к разным экземплярам этого ключа

Machine\VE 101 \НКЕ YLOC ALM ACHINE\SOFTWARE\Apple Inc.VApple Software Update» и «\\MachineWE102\HKEYLOCALMACHINE\SOFTWARE\Apple Inc.VApple Software Update»), что и обеспечит их изоляцию на уровне имени. Более того, не будет никакого способа добраться до соответствующего ключа второго VE из контекста первого (скажем, если программа попытаяется явно открыть

Machine\VE 101 \НКЕ YLOC ALM ACHINEVS OFTWAREVApple Inc.VApple Software Update» из контекста VE 102, то в реальности она будет пытаться добраться до ключа «VVMachineVVE 102VMachineVVE 101\НКЕ YJLOC ALMACHINEVS OFTWAREVApple Inc.VApple Software Update»). Аналогичным образом осуществляется изоляция доступа и для других типов идентификаторов.

Предложенная модель виртуализации существенно отличается от существующих стандартных моделей низкоуровневой виртуализации оборудования (виртуальных машин - ВМ - VM) тем, что предоставляя практически такие же возможности, как и VM, позволяет добиться существенно более высокой «плотности» размещения виртуальных серверов на оборудовании (в сотни раз выше), не теряя в уровне безопасности и изоляции, и более эффективна для запуска и миграции вычислительных процессов.

Существенным отличием предложенной модели виртуализации является разделение всеми VE одного ядра ОС, что накладывает дополнительные требования на технологии управления ресурсами ОС. Как показал опыт, даже в высокоразвитых коммерческих ОС имеющихся средств управления ресурсами недостаточно для групповых гарантий и лимитов выделения ресурсов потребителям, и особенно для осуществления взаимной изоляции виртуальных серверов по производительности (в частности, для защиты от случайных или намеренных атак типа «отказа в обслуживании»). Особо следует отметить, что использованные в существующих ядрах ОС алгоритмы управления ресурсами предназначены для управления сотнями, максимум тысячами объектов, тогда как, например, для 25 тысяч виртуальных серверов, запущенных на одной машине (такой эксперимент проводился на стандартном сервере архитектуры Intel), общее количество процессов и потоков превысило 200 тысяч.

Кроме собственно участия в технической реализации системы, в разработке алгоритмов и методов, необходимых для ее функционирования, автор работы подал более 80 заявок на патенты США по теме виртуализации и организации распределенных хранилищ данных, 14 из которых к настоящему времени получены.

Шбшм ИИш

Уоочена V г 11 i < .'Mi

Рисунок 1. Virtuozzo - реализация технологии виртуального приватного сервера VE. Технология VE находится "выше" технологии VM, их различие по отношению к архитектуре иллюстрирует следующий рисунок.

Рисунок 2. Уровни реализации virtual Machine и virtual Private Server (на примере технологий VMware и Virtuozzo).

В.8.3. Цели и задачи виртуализации

Какие же задачи можно решать при помощи виртуальной среды (VE) или виртуальной машины (VM)? Ответ - самые разнообразные. Действительно, как-то их классифицировать или ранжировать довольно трудно. Технически VM и VE представляют собой практически полноценный компьютер, т. е. их можно использовать для всего того, для чего используют обычный компьютер. Наверное, проще будет описать для каждого способа те задачи, которые он решать не может или решает неэффективно.

Начнем с VM. Чем все же отличается VM и запущенная в ней программа от обычного «железного» компьютера-ящика? В первую очередь VM потребляет больше ресурсов, так как у нее есть накладные расходы (и немалые) на обслуживание собственно самой VM, VMM, Host OS и т. д. Это означает, что приложение, запущенное в VM, получит в свое распоряжение меньше ресурсов, чем такое же приложение, запущенное в такой же среде, установленной не внутри VM, а внутри обычного "железного" компьютера. Потери могут быть довольно велики - до 20-30% ресурсов процессора (в зависимости от нагрузки), минимум 20% физической памяти (обычно больше); может также быть ограничено число процессоров, видимых внутри VM, а при наличии сколько-нибудь экзотического оборудования - доступ к нему. Например, если на вашем компьютере оказалась карта со специальным видеоускорителем или современная сложная карта SAN, с большой вероятностью использовать их внутри VM так, как хотелось бы, вам не удастся.

Естественное следствие таких ограничений - невозможность массового использования множества VM на одном физическом компьютере. Обычно допустимое число VM составляет от 2-4 на обычной машине до 50 на высокопроизводительных серверах (и то только в одной определенной версии VM-системы, в типовом случае сервер может обслужить десяток машин).

Другим, достаточно неочевидным, ограничением может стать потребность в лицензиях. Многие приложения и системы сейчас лицензируются для определенного числа копий бинарных файлов, загруженных в память (такова, например, ситуация с Microsoft Windows Server 2003), и для каждой их копии в VM необходимо купить отдельную лицензию - а их общая цена может многократно превышать стоимость оборудования, использованного для данного физического сервера!

Ограничения на использование технологии VE - несколько другого рода и связаны обычно со способом ее реализации. Например, технология Virtuozzo подразумевает, что каждый запущенный на машине VE использует одно и то же ядро и изнутри VE нельзя менять существенные компоненты или версию ядра. Впрочем, это не означает, что нельзя применять, скажем, разные "заплатки" на разные VE, если они не затрагивают собственно ядра или модулей в Linux либо существенных библиотек или исполняемых файлов ядра Microsoft Windows. Других существенных ограничений, в общем-то, нет (за исключением прямого доступа к оборудованию, который опять-таки ограничен изнутри VE соображениями безопасности).

Есть еще некоторые ограничения, присущие той или другой реализации, - например, в VE в любой момент обычно возможен прямой административный доступ к файлам из основной ОС, тогда как в типовых VM-реализациях он возможен только по сети, если это сделал администратор соответствующей VM; и наоборот, в VM есть возможность сделать "снимок" состояния всей системы для дальнейшего возвращения к этому состоянию (snapshot), а в VE обычно это делается по-другому.

В.9. Необходимость в виртуализации сервисов, что она предоставляет конечному пользователю

На самом деле с точки зрения пользователя виртуализация сама по себе является чисто технической составляющей решения. Конечному пользователю (как корпоративному и бизнес, так и домашнему) от вычислительных систем нужно обслуживание, то есть набор сервисов, плодами работы которых он мог бы пользоваться. В реальности человека чаще всего интересует не возможность, например, пользоваться MS Word, а возможность получения текстового документа, который можно отправить по почте или напечатать, а адресат сможет его прочитать.

Виртуализация помогает решению такого рода задач, упрощая конфигурирование, развертывание и обслуживание реальных сервисов.

Используя виртуализационный подход можно отделить «суть» от «техники реализации», поместив сервисы, оказывающие услуги пользователям, внутри виртуализированного окружения, и отодвинув машинно- и коммуникационно- зависимые части вовнутрь средств поддержки функционирования виртуализации.

Именно это и является причиной появления и активного использования средств виртуализации - решающим здесь оказывается «экономический эффект», который можно получить от виртуализованных систем - дающий как некоторые новые возможности (например, по мобильности сервисов путем переноса их с одного физического компьютера на другой), так и уменьшение общей стоимости обладания (ТСО) системы.

Тем не менее, виртуализация, конечно, не является «панацеей» и полным решением задачи предоставления сервисов для конечных пользователей.

Для адаптации созданной на основе предложенной модели новой технологии виртуализации к промышленному использованию автор разработал систему математических моделей, предназначенных для эффективного группового наложенного управления ресурсами (более подробно рассмотренных ниже).

Промышленная реализация технологии для основных коммерческих ОС (технология Virtuozzo® компании Parallels - для Microsoft Windows, Linux, Unix) подтвердила, что уровень накладных расходов по сравнению с виртуальными машинами оказался в 3-10 раз ниже из за высокой эффективности разделения ресурсов ядром ОС и управления ресурсами.

В.10. Существующие решения, связанные с распределенными хранилищами

В.10.1 Хранение данных

Одна из главных задач, связанная с проектированием распределенной файловой системой связана с организацией файлового хранилища.

Рассмотрим возможные способы организации файловой системы на примере существующих систем.

VAX/VMS

Файловая система VMS [67] является частью операционной системы VAX/VMS, которая занимается хранением и обработкой файлов в памяти и на вспомогательном запоминающем устройстве. Файловая система VMS основывается на файловой системе, применяемой в VAX-кластерах [68].

Структура хранения данных не диску в файловой системе VMS называется Files-11. Базовым носителем структуры Files-11 является том - это упорядоченное множество логических блоков. Логический блок - это массив из 512 байт. Блоки, находящиеся в томе, имеют последовательные номера, которые называются LBN. Максимальный размер тома составляет 232 блоков. Том обеспечивает чтение и запись данных, размер которых не превышает 65536 байт и кратен 4.

Логические блоки в томе группируются в кластеры. Кластер - базовая единица распределения дискового пространства в томе. Каждый кластер содержит один или более блоков. Каждый том имеет home-блок, который обычно располагается в первом блоке. В этом блоке находится имя тома и указатель на индексный файл, в котором содержится информация обо всех остальных файлах.

Одной из основных идей этой файловой системы является надежность, или устойчивость к системным сбоям, особенно в VAX-кластере. Файловая система должна переносить сбой в узле VAX-кластера без потери файла или доступа к файлам из других узлов кластера. Другими словами, важным требованием надежной файловой системы является целостность тома. Это достигается путем хранения нескольких копий home-блока и индексного файла, а также порядком обновления специальных данных. Еще один способ обеспечения целостности - различие между структурой директорий и файловой структурой.

Файл - это упорядоченное множество виртуальных блоков, который соответствуют логическим блокам, выделенным в томе для этого файла. Каждый файл в томе имеет уникальный номер, называемый файловым идентификатором (Fro). FID - это 48-битная величина, которая присваивается файлу системой при его создании. Кроме FID'а каждый файл описывается заголовком. Заголовок не является частью файла, он хранится в индексном файле. Он содержит информацию о местоположении, владельце, защите, дате и времени создания файла. На рис.3 показана структура файлового хранилища и механизм записи изменений. home-block

Журналирование индексный файл

Кластер блок 1 блок п foo.txt; 1.0 foo.txt; 1.1 foo.txt; 1.2 rollback

Рисунок 3. Структура хранения данных в системе VAX/VMS.

Важным полем в заголовке файла является список контроля доступа (Access Control List). Этот список содержит список пользователей, которым разрешен доступ к файлу. При помощи ACL можно дать доступ определенным группам пользователей к определенному файлу, что нельзя обеспечить при помощи общих средств защиты доступа. В ACL хранятся записи контроля доступа (АСЕ). Поддерживаются АСЕ пяти типов:

• Alarm (сигналы)

• Application (приложение)

• Directory default protection (стандартная защита директории)

• Identifier (идентификатор)

• RMS (Record Management Services) journaling (журналирование)

Структура АСЕ содержит также и базовые поля: список идентификаторов пользователей, биты доступа. Бит доступа разрешает доступ, если установлено значение 1, иначе запрещает.

Alarm АСЕ дает возможность получать предупреждения, когда к объекту пытаются определенным образом (прочитать, записать или изменить) обратиться.

Application АСЕ применяется для хранения дополнительной информации о файле.

Directory default protection АСЕ определяет какую защиту надо применять к файлам и директориям, находящимся в этой директории.

Identifier АСЕ определяет тип доступа для определенного пользователя или группы пользователей.

RMS journaling АСЕ дает возможность хранить изменения, которые были сделаны в файле. Т.е. ведется журналирование изменений, и изменения файлов могут быть отменены.

LOCUS

LOCUS [69] - это распределенная операционная система, которая поддерживает высокую степень сетевой прозрачности, т.е. она представляет сеть компьютеров для пользователя и приложений в виде одного компьютера. Границы машины полностью спрятаны во время работы. И файлы, и программы могут динамически перемещаться без ущерба пространству имен и правильному функционированию системы. Доступ к удаленным ресурсам осуществляется так же как и к локальным.

LOCUS предоставляет множество возможностей, включая гибкое и автоматическое дублирование хранилища на файловом уровне, механизм транзакций и более надежное по сравнению с обычной системой Unix файловое хранилище.

Файловая система, особенно ее распределенный каталог имен, играет центральную роль в архитектуре системы. Во-первых, потому что операции файловой системы преобладают над другими операциями в большинстве операционных систем, и поэтому им нужна высокая производительность. Во-вторых, потому что сервис имен используется многими другими частями системы.

Файловая система LOCUS представляет собой дерево именной иерархии для пользователей и приложений. В этой системы расширяется функциональность системы Unix. Во-первых, одно дерево в системе LOCUS охватывает все файлы в файловых системах всех машин. Имена в системе LOCUS полностью прозрачны; невозможно по имени файла определить его местоположение в сети. Такая прозрачность местоположения дает возможность запуска программ, использующих данные из других хранилищ. Во-вторых, файлы могут дублироваться с разной степенью, и слежение за обновлением всех копий является обязанностью системы LOCUS, обеспечивающей запросы доступа к наиболее поздним версиям файлов.

Дерево имен состоит из совокупности групп файлов, как и в системе Unix. Каждая группа содержит в себе поддерево иерархии имен, включая хранилище для всех файлов и директорий, содержащихся в этом поддереве. Процесс связи друг с другом совокупностей групп файлов называется монтированием.

Дублирование хранилища в распределенной файловой системе делается с несколькими целями. Во-первых, большее число копий ресурсов данных дает возможность увеличить доступность к данным. Очевидно, что это дает выигрыш в случае чтения данных. Ситуация затрудняется, когда требуется обновление файлов, поскольку нужно следить за обновлением всех копий файла. Во-вторых, увеличение производительности. Если пользователь работает с файлом с другой машины, то доступ на чтение будет гораздо быстрее к копиям файла, которые находятся недалеко от пользователя. Это особенно проявляется в медленных сетях.

Некоторая степень дублирования файлов в системе LOCUS необходима для того, чтобы пользователь вообще смог работать. Некоторые файлы должны быть доступны даже тогда, когда не доступны различные машины (например, файлы, необходимые для загрузки). Также необходимо дублирование директорных записей для того, чтобы во время сбоев можно было иметь доступ к файлам. Кроме того, каждый файл содержит версию и информацию о его изменениях - это нужно для того, чтобы обеспечить доступ к самой последней версии файла при его модификации.

В системе LOCUS существует три типа узлов: узлы, пользующиеся файлам (US) узлы, хранящие файлы (SS) узлы синхронизации, следящие за предоставлением наиболее поздних версий файла на запросы (CSS).

После модификации файла его копии обновляются в фоновом режиме. Для устранения конфликтов между разными версиями файлов в системе LOCUS существует специальный механизм. На рис.4 показана последовательность запроса на открывание файла.

Рисунок 4. Диаграмма запроса.

Последовательность запроса на открывание файла:

US -> CSS - запрос на открытие файла

CSS -> SS - запрос к хранилищу

SS -> CSS - ответ на запрос

CSS -> US - ответ на первое сообщение

Аналогичная последовательность будет и при закрывании файла. В системе LOCUS применяется транзакционный механизм подтверждения изменений (commit), сделанных в файле. Для поддержки транзакций в системе LOCUS применяется механизм теневых страниц.

Благодаря механизму подтверждения изменений пользователь работает с исходным или с полностью измененным файлом. Никогда не возникнет такая ситуация, при которой пользователь получит частично измененный файл, даже в случае сбоя узлов системы. Такой возможности нет в стандартной системе Unix.

В системы LOCUS хорошо продумана система хранения данных, механизмы защиты целостности данных и прозрачность доступа к информации. Отрицательными свойствами являются отсутствие хранения изменений файлов (журналирование) и централизованность системы. Для реализации нашей системы мы можем взять механизмы защиты целостности данных (транзакции, синхронизация), а также способ организации именной иерархии для обеспечения прозрачности доступа к данным. xFS xFS [70] - это распределенная файловая система без выделенного сервера, все узлы этой системы равноправны. Каждая машина этой сети может хранить, кэшировать и контролировать любой блок данных. В этой системе организовано избыточное хранение данных для обеспечения надежного доступа к файлам.

Сетевое хранилище системы xFS использует высокую производительность и доступность данных RAID-массивов (Redundant Arrays of Inexpensive Disks) [71].

Для организации файлового хранилища используется система LFS (Log-structured File System) [72]. Эта система используется в xFS, потому что она обеспечивает быструю запись, простое восстановление и гибкий метод нахождения данных на диске. Ведется история изменений файлов и применяется метод подтверждения изменений (commit) для сохранения целостности данных. На рис. 5 показана схема хранения данных в системе xFS.

Клиент 1 Клиент 2 А В I т сеть

Блок четности Обычный блок

А В С т

1 2 3 т

Файловые хранилища Рисунок 5. Схема хранения данных в системе xFS.

В системе xFS хорошо организовано хранение данных (LFS). Положительными чертами являются быстрый поиск, механизм восстановления файлов и распределенность файловых хранилищ.

MojaveFS

MojaveFS [73] - это распределенная файловая система с поддержкой транзакций. Самыми главными свойствами системы являются прозрачность доступа, целостность данных и отказоустойчивость. MojaveFS разрабатывалась как составляющая часть проекта Mojave Compiler Collection (MCC).

MojaveFS является промежуточным уровнем между virtual File System (VFS) операционной системы Linux и обычными файловыми системами (ext2, vfat, reiserfs). Система состоит из трех модулей: модуль ввода/вывода (File I/O), модуль распределения (Distribution) и модуль журналирования (Journaling). Схема их взаимодействия показана на рис. 6.

Операции ввода/вывода

Пользователь т

Транзакции j

Г сеть

Иодуль журналирования Модуль ввода/вывода Модуль распреде,- ■ i

Рисунок 6. Схема взаимодействия компонент системы MojaveFS.

Обычно, только часть файла используется одним процессом в определенный момент времени. Поэтому для повышения эффективности использования файлов, они разбиваются на фрагменты (chunk) фиксированного размера. Каждому файлу, видимому пользователю, соответствует директория на обычной файловой системе (chunk directory). Каждый chunk представляется отдельным файлом в обычной файловой системе, но он невидим для пользователя.

Каждый файл системы MojaveFS имеет таблицу фрагментов (chunk table), которая находится в chunk-директории и содержит метаданные о файле. На рис. 7 показан один пользовательский файл с именем foo. Все фрагменты этого файла находятся в директории foochunkdir. Таблица chunk'ов для этого файла, называемая fooctable, находится внутри foochunkdir. На рис. 7 показана структура файла на обычной системе. Для пользователя видны только файл foo и директория, в которой он находится.

Рисунок 7. Структура файла.

Для обеспечения прозрачности доступа к файлам в системе MojaveFS используется глобальное пространство имен, и каждый файл и директория имеют уникальный идентификатор. Этот идентификатор 64-х битный (32-х битный идентификатор машины и 32-х битный идентификатор файла в локальной файловой системе). Директории в системе MojaveFS представляются в виде файлов в обычных файловых системах. Каждая директория имеет таблицу (directory table), содержащую записи обо всех содержащихся файлах.

Модуль распределения состоит из трех компонент: менеджер групп (Group Manager), модуль дублирования (Data Replicator) и сервис метаданных (Metadata Service). Менеджер групп следит за связью компьютеров в сети. Сервис метаданных следит за обновлением и целостностью метаданных в системе. Когда метаданные изменяются, то сообщение об этом рассылается всем компьютерам в сети, и они изменяют у себя свои метаданные. Метаданные каждого файла содержат список узлов, на которых этот файл открыт. Когда файл открывается, информация об этом рассылается всем узлам в сети, и узел добавляется в этот список. Когда файл закрывается, соответствующий узел удаляется из этого списка.

Модуль дублирования копирует данные для того, чтобы обеспечить более высокую степень доступности файлов. Для каждого файла модуль дублирования имеет список узлов, на которых хранятся фрагменты этого файла. Измененный фрагмент файла рассылается всем узлам из этого списка. В системе MojaveFS реализован метод транзакций и механизм подтверждения изменений (commit).

Способ организации хранения данных в системе MojaveFS устойчив к системным сбоям. Хорошо продумана система слежения за обновлениями данных в системе.

Intermemory

Система Intermemory [74; 75] разрабатывалась как надежное хранилище данных в сети Internet, способное противостоять сбоям в узлах сети. Также целями разработчиков было обеспечить самоорганизацию, самообслуживание и эффективное администрирование системы.

В системе Intermemory все файлы разбиваются на блоки размером 64 килобайта, затем эти блоки специальным образом кодируются. Закодированный блок становится в два раза больше, и он разбивается на 32 фрагмента размером 4 килобайта. Смысл кодирования заключается в том, что первоначальный блок данных может быть восстановлен по любым 16 фрагментам.

Полученные фрагменты распределяются по другим узлам, а полный закодированный блок сохраняется на отдельном узле (см рис. 8). При чтении пользователь пытается соединиться сначала с последним узлом, если ему это не удается, то он пытается собрать 16 фрагментов с других узлов.

Файловые хранилища

Рисунок 8. Схема хранения в системе Intermemory.

На каждом узле находятся базы данных, в которых хранятся все данные (полные блоки и фрагменты) и метаданные. Записи в базах данных выглядят следующим образом: (ключ, версия, данные, хэш). Ключ - это идентификатор, а хэш - это хэш-функция от всех трех полей, которая вычисляется для сохранения целостности данных.

В данной системе применяется очень интересный метод хранения данных, который делает систему очень надежной и отказоустойчивой. В нашей системе можно применить такой же метод.

Farsite

Farsite [76; 77; 78] - это масштабируемая, распределенная файловая система без выделенного сервера. Эта система обеспечивает высокую степень доступности, надежности и защищенности данных. Каждый узел является хранилищем для реплик replicas) зашифрованных файлов и ответственен за часть пространства имен файловой системы.

На рис. 9 показана часть системы Farsite с точки зрения одного клиента; части системы, которые не важны с этой точки зрения, нарисованы серым. Здесь показана одна клиентская машина, несколько машин, которые образуют директорный хост (directory host), и несколько машин-хранилищ (file host). directory host file host client h local file cache global Site sure file host global file store file host elobul file store

Рисунок 9. Архитектура системы Farsite.

Целостность группы машин, составляющих директорный хост, сохраняется даже при сбое Уз части машин. Каждый директорный хост управляет несколькими директориями в пространстве имен системы, обеспечивая доступ к иерархическому каталогу машин-хранилищ и другим метаданным файлов и поддиректорий.

Каждый файл в системе Farsite зашифрован, продублирован и хранится на многих машинах-хранилищах. Шифрование обеспечивает секретность данных, а криптографический хэш, хранимый в директорном хосте обеспечивает целостность данных. Дублирование обеспечивает сохранение файла даже в случае сбоя нескольких хранилищ или случайного удаления из хранилища. Дублирование также обеспечивает доступность файла, даже если некоторые машины-хранилища недоступны в момент запроса файла. Farsite непрерывно следит за присутствием машин и при необходимости переносит реплики для повышения доступности файлов.

Файлы, которые клиент недавно использовал, кэшируются локально, обеспечивая гарантированный и непосредственный доступ к ним. Файлы, которых нет в кэше, должны быть получены из одного из хранилищ, которые содержат реплику этого файла (это показано на рис. 9 пунктирной линией). В последнем случае клиент соединяется с директорным хостом для того, чтобы определить какие машины содержат реплики этого файла.

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

Выводы

Проанализировав данные системы, получаем следующие выводы.

В файловой системе VMS хорошо устроено файловое хранилище. Оно способно выдерживать системные сбои без потери данных, в нем хорошо контролируется доступ к файлам. Все модификации файлов сохраняются отдельными файлами, поэтому пользователь может отменить изменения, сделанные в файлах. Минусом системы является то, что все данные хранятся в незашифрованном виде.

Плюсами системы LOCUS являются способ организации именной иерархии, механизмы защиты целостности данных и прозрачность доступа к информации. Отрицательными свойствами являются отсутствие хранения изменений файлов (журналирование) и централизованность системы.

В системе xFS хорошо организовано хранение данных. Положительными чертами являются быстрый поиск, механизм восстановления файлов и распределенность файловых хранилищ. Минусом является то, что эта система ориентирована на компьютеры с одинаковой скоростью доступа к сети. Поэтому в реальной сети эта система начинает работать со сбоями.

Способ организации хранения данных в системе MojaveFS устойчив к системным сбоям. Хорошо продумана система слежения за обновлениями данных в системе. Плюсом является наличие механизма транзакций и журналирование. При разбиении файла на большое количество фрагментов затрудняется поиск нужного фрагмента, это является результатом не очень хорошей организации файлового хранилища.

В системе Intermemory применяется очень интересный метод хранения данных, который делает систему очень надежной и отказоустойчивой. Однако при выведении из строя основного хранилища файла требуется слишком много соединений, чтобы восстановить файл, это является недостатком системы.

В системе Farsite используется очень хороший, отказоустойчивый способ организации файлового хранилища и директорий. Для того чтобы нарушить целостность директории необходимо вывести из строя Уз часть группы машин, составляющих директорный хост. Минусами системы являются отсутствие поддержки журналирования, механизма транзакций и слишком большое дублирование данных.

В.10.2. Кэширование

Рассмотрим произвольную распределенную систему. Кэширование, в общем смысле, это процесс сохранения результатов различных запросов как можно ближе к источнику этих запросов. Целью процесса является уменьшение трафика в системе, при повторных запросах. Предполагается, конечно, что, запросив что-либо один раз, пользователь сделает это повторно. Без выполнения этого требования любое кэширование не даст никаких положительных эффектов.

Для распределенной файловой системы задачу можно сформулировать следующим образом:

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

Пользователь периодически запрашивает одни и же данные повторно.

Физические характеристики системы, такие, как объем локальных хранилищ, скорость передачи данных по каналам, конечны.

В идеале вообще вся информация, которая нужна клиенту, всегда хранится на его машине.

FreeNet

Главными функциями системы были провозглашены сохранение анонимности запросов (запрос не должен содержать информации ни о его генераторе, ни об адресате), неразличимость данных, хранящихся на узлах, для прямого доступа к ним, защита от вмешательства третьей стороны, эффективное динамическое хранение информации и маршрутизация и, наконец, децентрализованность всех сетевых функций.

Кэширование в FreeNet реализовано следующим образом:

Путь запроса на какие-нибудь данные выстраивает цепочку узлов от инициатора этого запроса до машины, на котором он удовлетворился. При возвращении этих данных к инициатору запроса они копируются в кэш каждого из узлов цепочки. При каждой новой попытке сохранить проходящий запрос в своем кэше, узел проверяет объем хранилища. Если места не хватает, из кэша стирается самые «древние», пока его не будет достаточно.

Кэширование запроса

Узел с данными

Рисунок 10. Запросы на операцию кэширования в FreeNet

Такой способ крайне прост и надежен. Он позволяет самым быстрым путем переместить данные к источнику запроса. Однако запрашиваемые данные при этом дублируются многократно - пропорционально длине цепочки. При работе с файлами большого размера эффективность подхода резко снижается: один файл может «очистить» весь кэш. Снижается она и при сильной загруженности системы: если кэш постоянно обновляется, серьезной помощи от него ждать не приходится.

Таким образом, рассматриваемый подход хорош в условиях, когда система нагружена не очень сильно, когда объем локальных хранилищ достаточно велик или размер запрашиваемых файлов достаточно мал.

NFS (Network File System)

NFS была разработана компанией Sun Microsystems в 1984-м году. С тех пор система была перенесена практически на все наиболее известные платформы. В большинстве UNIX - подобных систем NFS включена в стандартный установочный пакет.

Главной целью разработчиков было обеспечение прозрачного удаленного доступа к локальным файловым системам разных типов. Он был реализован в системе благодаря операции монтирования (операция сделана не транзитивной во избежание проблем с зацикливанием). NFS разделяет два типа узлов: сервер, предоставляющий свои файловые ресурсы, и клиент, пользующийся ими. Основная идея работы NFS заключается в том, что при выполнении удаленных файловых операций на клиенте все обращения к ядру операционной системы передаются по сети на сервер, где они собственно и выполняются, а результаты возвращаются клиенту.

На серверах NFS кэширования как такового практически нет. При запросах на чтение только просматривается кэш локальной файловой системы. Клиент же кэширует все поступающую на него информацию. По сравнению с FreeNet здесь уже появляется понятие актуальности кэшируемой информации, определяющее, устарела ли она (т.е. изменил ли кто-нибудь файл после его копирования в кэш). Вся ответственность за определение актуальности файлов в NFS возложена на клиента. Все следящие за кэшем механизмы выполняются на нем. Файл в кэше считается действительным (правильным, подходящим), если выполняется хотя бы одно из условий:

• С момента кэширования прошло не более заданного времени, т.е. не истек таймаут.

• Время последней модификации файла в кэше и на сервере совпадают.

Таким образом, по истечении таймаута, клиент перед использованием файла сверяет время его последней модификации с сервером. Величина таймаутов в NFS довольно четко определена: она составляет 3-30 секунд для файлов и 30 - 60 секунд для директорий.

Помимо этого, в NFS предусмотрены следующие кэширующие механизмы, ускоряющие ее работу:

• Предварительное считывание (read-ahead).

Файлы в NFS хранятся разбитыми на блоки определенного размера для стандартизации работы всех операций с ними. При выполнении запроса на чтение файла, считывается только первый блок - его начало. Результат предоставляется пользователю. При этом запускается механизм предварительного считывания: следующие N блоков докачиваются в асинхронном режиме. Параметр N задает сам пользователь.

• Запись с запаздыванием (delayed writes).

При выполнении запроса на запись, файл ставится в очередь «на отправку», и управление возвращается пользователю. Т.о. реально файл может быть отослан в сеть гораздо позже команды на запись. Впрочем, другой командой можно сразу поставить файл сразу «на первое место» в очередь отправки.

Andrew File System (AFS).

Распределенная файловая система AFS была создана в университете Carnegie Melon (США) также в 1984-м году. Основной задачей проектирования системы была абсолютная масштабируемость системы. Это было достигнуто за счет собственного разбиения имеющегося файлового пространства. Единицей такого разбиения в AFS служит так называемый «том» (volume). Это аналог «файла или директории». В томах AFS можно хранить файлы или другие тома. Их ценность в том, что они совершенно не зависят от места их расположения, их можно очень легко переносить с одной машины на другую (аналог, а может и предок, современных «агентных» систем). Расширение файловой системы сводится, таким образом, к подключению новых хранилищ и перегруппировке томов для разгрузки имеющихся. При этом файловое дерево AFS никак не изменяется.

Как и NFS, AFS спроектирована в рамках клиент - серверной модели. Реализация AFS включает две компоненты: vice и Venus. На серверах запускается vice, а на клиентах -VenusfxoTM Venus может в принципе запускаться и на отдельной машине).

Файлы в AFS кэшируются на клиенте при запросах на чтение, на его локальном диске. В отличие от NFS, здесь ответственность за определение актуальности кэша возлагается на серверы. Передавая файл клиенту в ответ на его запрос, сервер «обещает» ему следить за его актуальности, при этом на клиенте выставляется флажок - «годен». Когда какой - либо клиент модифицирует этот файл, он (Venus) сообщает об этом cepBepy(vice), а он, в свою очередь, уведомляет об этом нашего клиента, который изменяет значение флажка на противоположное. При каждом обращении к файлу из кэша клиент проверяет флажок и в неблагоприятном случае считывает его новую версию из сети.

Заметим, что для упрощения масштабируемости системы, файлы в ней хранятся целиком, не разбитыми на стандартные блоки, как во многих системах. Поэтому при работе с большими файлами возникают немалые проблемы. Кроме того, если адресат недоступен в момент, когда клиент должен сообщить серверу об изменении файла, или сервер разослать уведомления об устаревании их кэшей, клиент будет использовать и дальше прежнюю версию файла. При использовании AFS, считается, что запросы на чтение в системе встречаются значительно чаще, чем на запись (изменение). Предполагается также, что большинство файлов читаются и изменяются одним пользователем. Если эти условия не выполняются - система практически не работоспособна.

Файловая система Coda

Coda была спроектирована в том же университете Carnegie Melon в 1987 - м году. По сути, она является плодом дальнейшей разработки AFS. По крайней мере, Coda унаследовала от AFS все ее основные составляющие. Она также различает два вида машин: с запущенной компонентой Venus, отвечающие за клиентскую часть(обрабатывающую его запросы) и с запущенной компонентой vice, серверы. Файлы здесь снова хранятся в «volume»-ax, вложенных в другие. Целью создания системы было сохранение стабильной, постоянной доступности данных. Достигается это дублированием данных: любой «том» можно хранить в нескольких экземплярах, на нескольких серверах, называемых Volume Server Group (VSG). После модификации файл копируется на каждого из членов соответствующей VSG.

Базовая часть кэширования в Coda по логике не отличается от AFS, но репликация данных привела к некоторым модификациям. Так, Venus теперь при кэшировании какого-нибудь файла устанавливает и поддерживает связь со всеми членами VSG хранящего этот файл тома, с которыми это возможно. Эта группа доступных серверов из VSG называется Accessible Volume Storage Group (AVSG). Сервер из VSG удаляется из AVSG, если связь с ним прерывается (истекает соответствующий таймаут). Venus также периодически пытается подсоединиться к членам VSG. Если это удается - сервер добавляется в AVSG.

Venus также выбирает из AVSG один сервер, с которого он будет считывать файл вместо устаревшего в кэше (preferred server). Способ выбора может быть различным: случайным образом или по определенным критериям (надежность, скорость доступа.). Причем при считывании новой версии устаревшего файла с выбранного сервера Venus проверяет время последней модификации на остальных серверах из AVSG, убеждаясь, что считываема версия самая последняя.

Еще одним важным дополнением к AFS является новый, автономный режим работы клиента (Venus) - Disconnected Operation. Теперь, если группа доступных серверов AVSG пуста для какого-нибудь файла, никакой ошибки не происходит. Venus просто переходит в автономный режим работы с этим файлом. Пользователь уведомляется об этом. В этом режиме файл при запросе всегда считывается из кэша. При этом, вполне вероятно, что требуемого файла не будет в кэше. Создатели файловой системы посчитали, что такие случаи редки, и поэтому, допустимы. Здесь предполагается, что переход в автономный режим происходит после достаточно длительной работы пользователя, так что в кэше успевают сохранится большинство необходимых для работы файлов. В отключенный режим работы пользователь может перейти и добровольно. Например, заполнив кэш своего переносного компьютера (laptop) после длительной работы в Coda, он может отключить его и отправиться в путешествие и в пути спокойно работать с нужными файлами дальше.

В Coda были исправлены некоторые недостатки AFS и сохранены ее достоинства. Серьезно повышена устойчивость системы, уменьшена вероятность возникновения некорректных ситуаций. Однако остальные недостатки AFS перенесены и в Coda. Так, по-прежнему проблематична работа с файлами большого размера и хранилищами маленького объема. С дублированием данных эта проблема только усугубилась. Появились и новые проблемы. Основная - поддержка одинаковых версий файла на нескольких машинах. Например, если на две машины, хранящие копии одного файла одновременно с разных клиентов поступят разные новые версии этого файла - возникнет конфликт. То же самое произойдет, если новые версии поступят не одновременно, но связь между этими серверами временно прервется. По мнению автора, эти проблемы неразрешимы в подходе Coda.

В.10.3. Выбор оптимальной точки соединения.

Любой распределенной системе не обойтись без решения проблемы выбора способа подключения к ней. Путем подключения новых машин распределенная система расширяется. Кроме того, параметры сети постоянно меняются. Загруженность каналов, надежность того или иного узла, наконец, просто его существование - все это переменные величины, уже имеющиеся соединения могут перестать удовлетворять нас. Система должна находиться, поэтому в постоянной перестройке, и везде требуется уметь выбирать оптимальные по каким либо критериям соединения.

Рассмотрим следующую постановку задачи. Имеется множество узлов, соединенных между собой по некоторой схеме (связное множество). Кроме этого, есть отдельный узел, подключенный к совершенно произвольному узлу из множества. Введена некоторая метрика для сравнения соединений между собой. Необходимо найти в данном множестве узел, соединение отдельного узла с которым не будет нарушать логику схемы соединения узлов в множестве и будет квазиоптимальным по данной метрике. Квазиоптимальным мы будем называть выбранное соединение в связи с невозможностью абсолютно корректного выбора математически оптимального соединения (из-за не полноты нашего знания о работе системы, возможности ее эволюции во времени и т.д.).

Т.е. фактически нам необходимо заменить имеющееся («первое попавшееся клиенту») соединение на квазиоптимальное. Формулировка включает в себя и подключение новой машины к распределенной системе, ведь оно невозможно без первого соединения с кем - либо из «действующих членов», после чего и запускается основной алгоритм.

Рассмотрим несколько систем, решавших подобные или похожие задачи.

Система была создана относительно недавно, в 2000 - м году Ж. Франкелем и Томом Пеппером. Клиентская и серверная части в Gnutella практически соединены в одну, называемую «сервент». По сравнению с аналогичными распределенными хранилищами, файловыми системами, возможности Gnutella существенно урезаны: она была разработана под лозунгом «Ничего лишнего» - только средства подсоединения к «сервентам» системы и скачивания информации. Однако алгоритм подключения нового узла к системе оказался довольно интересным:

Рисунок 11. Алгоритм подключения нового узла к Gnutella

Первая часть алгоритма подключения заключается в поиске активного узла из имеющихся «сервентов» - того, который «готов общаться». Ведь принимающая сторона может отклонить попытку подключения по различным причинам: из-за ограничения на количество входящих соединений или из-за прямого приказа клиента. Первоначальный

Gnutella.

I | новый узел ЩЩ активный узел ИИ остальные сервенты список адресов узлов системы можно взять на официальном сайте Gnutella. Затем новоиспеченный «сервент» узнает адреса остальных узлов системы, посылая ping - запрос активному узлу. Тот генерирует в ответ pong - пакет, записывает туда свой адрес и отсылает его обратно, a ping рассылает по всем исходящим от него каналам. На каждом из них процесс повторяется итеративно. Причем при прохождении любого узла у ping -пакета уменьшается поле TTL(time-to-live) пакета на единицу. Когда оно достигает нуля, пакет возвращается обратно по тому же самому пути. Узнав о других «сервентах», новый узел начинает попытки искать среди них тех, с кем можно установить долгосрочное соединение. И так до тех пор, пока не постоянных партнеров не наберется достаточное количество.

Описанный алгоритм вполне естественен, трудно придумать что - либо более простое и надежное. Но у него есть один минус, который стать узким местом системы: один посланный пакет вызывает довольно большой поток трафика, так как он дублируется многократно на каждом сервере. Объем этого потока экспоненциально растет с значением TTL. По оценкам [79] в реальных системах объем трафика, приходящегося на ping/pong запросы составляет от % до % от полного.

Akamai.

Проект был основан Тимом Беренрсом - Ли из Массачусетского технологического института (МГГ) в начале 1995 года [80]. Его идея состояла в создании системы ускоренной доставки информации из Интернета пользователям. Идея ускорения доставки информации из интернета состоит в «расширении» его главных узких мест, например, соединений источника информации и ее получателя с интернетом (так называемые «первая миля» и «последняя миля»). «Расширение» достигается путем создания и использования сети специальных серверов: Edge Services. Они распределены по всему миру - везде, где есть пользователи Akamai. Качество соединения между ними достаточно высокое. Edge Services составляют прослойку между источником информации и получателем. Задача доставки информации сводится, таким образом, к ее пересылке от источника к прослойке и от прослойке к получателю. Различные узкие места на первом этапе должны обходиться, по замыслам разработчиков, за счет специальных алгоритмов маршрутизации. Второй этап пути, как предполагается, должен проходить по довольно разгруженной «окраине» интернета (это достигается расположением Edge Services). Таким образом, в системе стоит лишь задача выбора «ближайшего» сервера, которая описана подробнее ниже. Проблема «первой мили» решается за счет активного кэширования информации на серверах. Ну а задачу «последней мили» никому, кроме самого пользователя, не решить. Так, если клиент запросит какую - то информацию, то сначала проверится ее наличие на «ближайшем» сервере. Если желаемого там нет, запрос идет к источнику и по пути кэшируется на этом сервере. Проверка актуальности кэшируемых данных здесь не очень надежная: серверы надеются на использование источником информации стандарта, предусматривающего посылку специальных http - сообщений, если хранимая на них информация изменилась. Получив такое сообщение, сервер обновляет соответствующую информацию.

Рисунок 12. Архитектура системы Akamai

Основная идея алгоритма поиска «ближайшего» к клиенту сервера состоит в том, что специальные службы на серверах регулярно (каждые 10 секунд) составляют карты трафика локальной подсети, определяют степень загруженности соседних машин. Исходя из этой карты и выбирается «ближайший» сервер. К сожалению, более детального описания алгоритма (как и других, например, алгоритмов маршрутизации) получить из открытых источников нельзя.

Internet Relay Chat(IRC).

Первым предназначением IRC было средство общения сотрудников ВВС. Именно для этого он создавался в 1988-м году. Уже через несколько лет, исправленный и доработанный, он стал широко распространенным средством общения пользователей интернета. Основная часть архитектура IRC - дерево серверов. К любому из его узлов

48 могут подсоединяться клиентские программы. Впрочем, ими часто являются обыкновенные браузеры. Чтобы иметь возможность пользования IRC, клиент должен прежде зарегистрироваться, получить имя, под которым его будут знать другие. Пользователи IRC разбиваются на группы - «каналы». При подключении клиент может присоединиться к имеющемуся каналу или создать свой собственный. Если последний пользователь покидает канал, он уничтожается. Некоторые пользователи IRC обладают большими по сравнению с остальными правами. Их называют операторами. Их существование имеет целью поддержку целостности системы, логики ее работы в экстренных случаях, когда дает сбой «автоматика» (например, в ситуации так называемого «сплита» когда серверы теряют связь между собой и один и тот же канал оказывается имеющим разных участников для разных клиентов).

Каждый клиент IRC может посылать сообщения следующим адресатам:

• Всем пользователям.

• Всем членам своего канала.

• Выбранной им самим группе.

• Другому конкретному пользователю.

Сообщение, адресованное определенной группе пользователей, отсылается клиентом на сервер, который ретранслирует его в соответствующих направлениях. Отметим случай общения двух пользователей. В выполняющих те же функции системах мгновенного обмена сообщениями (Instant Messengers) два клиента общаются напрямую, через установленное между ними двоими соединение. Здесь же все общение проходит через дерево серверов. Сообщение, посланное, например, клиентом А клиенту В (см. рис. 13), проходит еще через серверы 1 и 2. Частный разговор в IRC легко может перестать им быть.

Сервер Пользователь

Рисунок 13. Архитектура системы IRC

Таким образом, IRC предлагает принципиально другой, централизованный способ обнаружения машин в сети: когда существует один или несколько серверов, ответственных за это. Серверы поддерживают постоянный контакт со всеми узлами системы. При подключении к сети, машина соединяется с одним из этих серверов и узнает обо всех остальных. При этом остальные мгновенно обнаруживают появление новичка. Такой способ, конечно прост и удобен. Его главным достоинством является скорость получения информации о пользователях системы и ее полнота. Однако единственной и очень серьезной слабостью такого способа является его централизованность. Она влечет множество проблем, связанных с надежностью, безопасностью, расширяемостью и другим. Соответственно, использовать его рекомендуется, когда достоинства имеют первостепенную важность над недостатками.

Рисунок 14. Обнаружение новых серверов в IRC. Веб-фермы

В последнее время структура систем, обрабатывающих пользовательские запросы все чаще становятся многосерверными. Такие группы серверов, обрабатывающих клиентские запросы как единое целое называют веб-фермами. Они имеющие одно управление, а чаще всего, помещение и обслуживающий персонал. Наиболее широко распространены веб-фермы, имеющие одно (распределенное) хранилище на все серверы. Их называют кластерами.

Основной принцип функционирования кластеров-ферм достаточно прост. Клиенты для возможности посылки запросов устанавливаю соединение с диспетчером. Диспетчер выбирает сервер - обработчика, устанавливает с ним другое соединение и «склеивает» его с клиентским (конкретные технологии «склеивания» различны, смысл - один). Нас как раз и интересуют принципы, согласно которым происходит это распределение. Здесь существует два основных подхода.

Ретрансляция по адресу. Диспетчер распределяет пакеты по ГР - адресу назначения. Сервер, которому посылается пакет, определяется только исходя из этого. Такой способ не требует глубокого проникновения в содержимое пакета, поэтому он достаточно быстр. Диспетчер в этом случае подобен обычному маршрутизатору (router).

Ретрансляция по содержимому. В этом случае работа диспетчера усложняется. Он должен проникать внутрь каждого приходящего запроса и, исходя из содержимого, определять сервер, которому послать пакет для обработки. Этот способ, конечно, медленнее предыдущего (особенно если размер клиентских запросов достаточно мал).

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

Диспетчер, по сути, решает нашу задачу, выбирает сервер для соединения из имеющегося множества. Однако принципы выбора (особенно второй) достаточно своеобразны и необычны. Причина - в особенностях упоминаемой в постановке задаче метрики, по которой оцениваются соединения. Здесь она зависит не от физических характеристик соединения (что, казалось бы, естественно), а от типа пришедшего запроса. Такой подход вполне оправдывает право на свое существование результатами его применения.

В.10.4. Проблемы безопасности

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

Таким образом, возникает задача создания полной анонимности пользователей, помещающих и запрашивающих информацию в системе. В общем случае, решение этой задачи крайне не просто, учитывая неприспособленность инфраструктуры Интернет к такой цели. Например, большинство запросов в сети снабжено информацией об источнике запроса как минимум в виде его ГР адреса, по которой можно раскрыть эту анонимность. Даже анализируя транзитную информацию маршрутизаторов, можно обнаружить большое количество информации, посылатели которой явно не рассчитывали на ее оглашение. Например, автор обнаружил интересный факт - после регистрации нового адреса на таких серверах бесплатной почты как mail.ru и отсылки на этот адрес любого сообщения адресату немедленно приходит как минимум одно письмо со «спамом». Это может быть сделано только двумя способами - или самим обладателем mail.ru (что достаточно маловероятно из-за соглашения с пользователем), или путем перехвата и анализа почтового трафика на маршрутизаторах.

Рассмотрим, как подходят к решению проблемы анонимности в других распределенных системах.

Freenet

Система Freenet разрабатывалась как адаптивная распределенная система, позволяющая осуществлять публикацию, размножение и получение информации, сохраняя анонимность авторов и читателей. Полное описание этой системы можно найти в [81]. Рассмотрим только часть этой системы, посвященную безопасности. Схема обычного запроса показана на рис. 15.

Рисунок 15. Обычный запрос в системе Freenet.

Основная цель безопасности системы Freenet - анонимность людей, запрашивающих и помещающих файлы. Также важно защищать подлинность хранителей файлов. Файлы должны быть защищены от злоумышленной модификации, и система должна быть устойчива к атакам denial-of-service.

Рейтер и Рубин в [82] предлагают удобную систематику свойств анонимности связи. Первая ось - тип анонимности: анонимность отправителя или получателя, что соответственно означает, что злоумышленник не сможет определить, кто послал сообщение и для кого оно послано. Вторая ось - данный злоумышленник: подслушивающий локально, один узел или несколько взаимодействующих узлов. Третья ось - степень анонимности: абсолютная секретность (существование связи не может быть определено), вне подозрений (равновероятно можно утверждать, что источником сообщения был один из потенциальных отправителей), вероятная невиновность (отправитель скорее был источником сообщения, чем не был), возможная невиновность, незащищенность, и доказуемая незащищенность (злоумышленник может доказать, кто был отправителем сообщения).

Так как коммуникации системы Freenet направлены не на определенный тип получателей, то анонимность получателя понимается, как анонимность ключа, т.е. скрывание ключа, который запрашивается или помещается. К сожалению, так как роутинг

Иници

Запрашиваемые данные

Запрос данных Пересылка данных

Неудачный запрос зависит от ключа, то анонимность ключа невозможна в базовой схеме Freenet. Использование хэш-функций как ключей обеспечивает некоторую защиту от обычных злоумышленников, но, конечно, не защищает от словарной атаки, поскольку их нехэшированные версии широко известны.

Анонимные свойства системы Freenet в соответствии с данной систематикой показаны в таблице 1.

Таблица 1. Анонимные свойства системы Freenet.

Система Злоумышленник Анонимность отправителя Анонимность ключа

Базовый Freenet подслушивающий локально незащищенность незащищенность взаимодействующие узлы вне подозрений незащищенность

Freenet pre-routing подслушивающий локально незащищенность вне подозрений взаимодействующие узлы вне подозрений незащищенность

Анонимность отправителя остается вне подозрений при взаимодействии злоумышленных узлов, так как узел на пути запроса не может сказать, был ли предыдущий узел источником запроса или просто отсылал его дальше. Рейтер описывает вероятностную атаку, которая может раскрыть анонимность отправителя, используя статистический анализ вероятности, что прибывший в узел А запрос отправляется дальше или сразу обрабатывается, и вероятности, что узел А выберет конкретный узел Б, которому оправит запрос. Этот анализ напрямую неприменим к системе Freenet, так как пути запросов строятся не вероятностно. Пересылка сообщения зависит от того, есть ли в хранилище узла А запрашиваемая информация или нет. Если запрос пересылается дальше, то таблицы роутинга определяют, куда его послать, и может получиться так, что узел А пересылает все запросы узлу Б, или никогда не посылает запросы узлу Б. Тем не менее, значение глубины может показать сколько шагов назад был источник, хотя это затрудняется случайным выбором начального значения глубины и вероятностным способом увеличения ее. Подобные рассуждения применяют к значению hops-to-live. Требуются дальнейшие исследования, чтобы разъяснить эти вопросы.

Против злоумышленника, подслушивающего локально, не существует защиты для сообщений между пользователем и первым узлом. Поскольку первый узел может действовать, как локальный подслушивающий злоумышленник, то пользователю рекомендуется использовать свою машину в качестве первого узла входа в сеть Freenet. Сообщения между узлами шифруются, чтобы защититься от локально подслушивающих злоумышленников, хотя анализ трафика может быть осуществлен (например, злоумышленник может наблюдать вышедшее сообщение, причем входящего сообщения не было, отсюда он может заключить, что узел - источник сообщения).

Анонимность ключей и более сильная анонимность отправителей может быть достигнута добавлением pre-routing'a сообщений (см. рис. 16). В этой схеме, сообщения базовой системы Freenet шифруются последовательностью публичных ключей, которая определяет маршрут, по которому пойдет зашифрованное сообщение (нормальный алгоритм роутинга не используется). Узлы на протяжении этого маршрута не могут определить ни источник сообщения, ни содержимое сообщения (включая запрашиваемый ключ). Когда сообщение доходит до конечной точки фазы pre-routing'a, оно возвращается в нормальную сеть Freenet и ведет себя дальше так, как будто это конечная точка была источником сообщения.

Рисунок 16. Система Freenet + pre-routing

Защита источников информации обеспечивается при помощи случайного установления поля с источником информации в ответном сообщении. То, что идентификатор узла находится в этом поле, не обязательно означает, что этот узел содержит эту информацию или был на пути следования запроса. Невозможно сказать содержит ли предыдущий узел файл или он просто переслал ответ, посланный кем-то другим. На самом деле, при успешном запросе файл кэшируется на предыдущем узле, если его там не было, поэтому при помощи последующих запросов нельзя определить был ли файл на этом узле или нет. Запрашивая определенный файл со значением hops-to-live равным 1, нельзя прямым образом определить, хранился ли он на этом узле. Но последовательность большого числа запросов на связанные файлы может дать основания полагать, что эти файлы уже хранились на этом узле.

Существенная угроза - модификация запрашиваемых файлов узлом злоумышленников, который находится в цепочке запроса, и не только из-за искажения самих данных. Поскольку таблицы роутинга основываются на ответах на запросы, то узел может попытаться направить трафик на себя, подменяя файлы фиктивными данными. Для данных хранимых с ключами, основанными на содержимом файлов или на подписях к файлам, это не возможно, поскольку ненастоящие данные могут быть определены в узах при конфликтах с хэшами или при вычислении криптографической подписи. Данные, хранимые с ключами, основанными на ключевых словах, подвержены словарным атакам, поскольку подписи могут быть сделаны всеми, кто знает исходную строку описания.

Существуют также атаки denial-of-service (отказ от обслуживания). Самая главная опасность заключатся в том, что злоумышленник попытается заполнить все хранилища в сети, добавляя большое количество файлов с "мусором". Существует интересный метод для противостояния этой атаке, который называется Hash Cash [83]. Суть метода заключается в том, что пользователь, который хочет поместить новый файл, должен осуществить довольно долгие вычисления в качестве "оплаты" перед тем, как поместить файл в систему, тем самым, снижая скорость атаки. Другая альтернатива - разделить хранилище на 2 части, одна для новых файлов, другая для "установившихся" (те файлы, на которые были получены, по крайней мере, несколько запросов). Новые файлы могут замещать файлы только из числа новых, а не из числа установившихся. В этом случае поток файлов с "мусором" временно парализует операцию добавления новых файлов, но не заменит существующие файлы. Злоумышленнику будет сложно искусственно подтвердить свои файлы, запрашивая их несколько раз, поскольку его запросы будут обрабатываться на первом же узле и не будут идти дальше. Напрямую дальше первого узла тоже нельзя отправить запрос, поскольку идентификаторы узлов неизвестны. Однако подобная схема может затруднить добавление нормальных новых файлов, которые могут быть удалены, прежде чем их запросят другие для того, чтобы они стали установившимися.

Злоумышленники могут попытаться заменить существующие файлы другими версиями с теми же ключами. Атака такого рода не возможна против ключей, основанных на содержимом файлов или на подписях к файлам. С другой стороны, атака против ключей, основанных на ключевых словах, может привести к тому, что обе версии файлов будут существовать в сети. Такие атаки затруднены способом обработки конфликтов при помещении нового файла. Успех такой атаки выражается соотношением поврежденной и исходной версий файла, оставшихся в сети. Тем не менее, чем больше поврежденных копий злоумышленник попытается распространить (установив большее значение hops-to-live), тем больше вероятность того, что произойдет конфликт, который приведет к увеличению числа исходных копий.

В системе Freenet очень хорошо реализована система защиты анонимности пользователей и защиты данных от атак злоумышленников. Для того чтобы раскрыть анонимность пользователей, злоумышленникам придется контролировать все узлы сети. Методы, примененные в этой системе, можно потенциально использовать и в нашей системе.

Onion Routing

Основная цель Onion Routing [84] - обеспечить защищенную от прослушивания трафика связь поверх общедоступной сети за разумную стоимость. Связь подразумевается защищенной, если локальный и находящийся в сети злоумышленники не могут определить содержимое сообщения от Алисы и Боба (эти имена используются в криптографии как символы коммуницирующих сторон), и не могут определить, что Алиса и Боб переговариваются друг с другом. Вторая цель - обеспечить анонимность отправителю и получателю, так что Алиса может получать сообщения, но не может определить того, кто ей его послал, даже тогда, когда она может отвечать на эти сообщения.

Onion Routing динамически создает анонимные соединения в сети onion роутеров. Это система состоит из набора работающих в режиме реального времени серверов -миксеров. Миксер - это устройство с промежуточным хранением данных, которое принимает некоторое количество сообщений фиксированной длины от многих источников, совершает над ними криптографические преобразования, и затем отсылает их дальше в порядке, не зависящем от порядка на входе. Один миксер затрудняет отслеживание конкретного сообщения по размеру или порядку относительно других сообщений. После прохождения через большое число миксеров становится еще труднее определить, кто с кем общается. Сеть Onion Routing состоит из onion роутеров (миксеров) и является распределенной, отказоустойчивой, и находится под контролем многих административных доменов, поэтому никакой одиночный роутер не сможет сломать сеть или скомпрометировать анонимность пользователя, и анализ взаимодействия между роутерами злоумышленниками ничего не даст. Onion роутеры, в отличие от обычных миксеров, передают информацию в реальном времени. Миксер может хранить сообщения довольно долго, пока не получит достаточное количество сообщений, которые можно перемешать друг с другом. Режим реального времени накладывает на Onion Routing ограничения на это перемешивание, и это является одним из главных отличий onion роутеров от миксеров. На рис. 17 показан принцип работы системы Onion Routing.

Пользовател

Пользователь 2

Рисунок 17. Принцип работы системы Onion Routing.

Onion Routing поддерживает протоколы HTTP, FTP, SMTP, rlogin, telnet и другие. Система имеет три логических уровня: дополнительный защитный фильтр, который обрабатывает поток данных; приложение, которое преобразовывает поток данных в формат, принимаемый сетью Onion Routing; onion агент, который создает анонимные соединения. Onion агент - самая доверенная в системе компонента. Эти агенты должны знать достаточно о топологии и состоянием каналов сети, публичные сертификаты узлов сети. Эта информация автоматически распространяется по сети по мере подключения новых узлов или по мере изменения этой информации.

Метод защиты анонимности, рассмотренный в этой системе, достаточно хороший. Для того чтобы сломать систему, т.е. раскрыть анонимность, требуется завладеть всеми узлами сети Onion Routing.

Основной задачей системы Rewebber [85] является анонимная World Wide Web (WWW) публикация статей. При этом сам автор может выбрать для себя нужный уровень анонимности.

По всему миру разбросаны узлы, которые называются rewebber'ами (все вместе эти узлы образуют сеть Rewebber). Каждый узел - это HTTP прокси, который может работать С "вложенными" URL (т.е. СО ссылками вида http://proxy.eom/http://realsite.com/). Основная идея заключается в том, чтобы потом опубликовать URL-ссылку такого вида, Которая будет указывать на proxy . com вместо realsite.com.

Очевидный недостаток - это то, что не прячется имя реального сервера. Эта проблема решается при помощи шифрования имени реального сервера открытым ключом так, что только rewebber может прочитать его. В этом случае URL-ссылка будет выглядеть как http://proxy.com/!RFkK4J.d4w/. Сервер rewebber на proxy.com, после принятия такой ссылки, сначала дешифрует ее (о том, что она зашифрована говорит ! вместо ожидаемого http://), затем продолжит работу с вложенным URL в обычном режиме. Такие зашифрованные URL-ссылки называются локаторами.

Этот механизм прячет от клиента реальное местоположение сервера, но имеет другие недостатки. Во-первых, после того как пользователь получит информацию, он может

TAZ и Rewebber попытаться установить, откуда эта информация пришла. Эта проблема решается путем шифрования хранимых документов. Таким образом, если к документу обратиться напрямую, то мы ничего не получим. Здесь должно использоваться шифрование с симметричным ключом.

В системе Rewebber используется алгоритм DESX, но также может использоваться любой стойкий алгоритм с симметричными ключами. Ключи DESX даются rewebber'у в зашифрованной части локатора; после дешифрования локатора, он получает не только URL-ссылку, но и DESX ключи, которыми он дешифрует получаемые документы. После этого документ отправляется пользователю.

Такой способ шифрования документов, хранимых на сервере, имеет преимущество: документ может быть заполнен до какого-то размера перед шифрованием, и rewebber откинет ненужную часть перед тем, как отправлять файл пользователю. Причина, по которой нужно это делать, похожа на ту, по которой нам надо шифровать документ: если размер полученного файла ровно 2834 байта, то при помощи поиска по размеру файла можно быстро найти зашифрованный документ. Чтобы помешать этому, в конец файла добавляются случайные данные так, что их итоговая длина принимает одно из фиксированных значений. Эти размеры равны 10000, 20000, 40000, 80000 и т.д., поскольку средний размер файла в сети WWW немного меньше 10000 байт.

В этой системе не используется метод миксеров, поскольку он дает задержку, которая не допустима для WWW. Но потеря надежности в связи с отсутствием этого метода уменьшается за счет других особенностей этой системы.

Если rewebber находится под управлением злоумышленника, то он может открыть связь между реальным сайтом и документом. Для того, чтобы избежать этого, используется метод формирования цепочки.

Для формирования цепочки достаточно заменить URL в зашифрованной части локатора другим локатором, который указывает на другой rewebber. Цепочку можно сделать такой длины, какой мы захотим. Схематическая диаграмма цепочки длины 3 показана на рис. 18.

При использовании цепочки документ, хранящийся на сервере, надо шифровать несколько раз. Чтобы сделать это, пользователь, публикующий документ, случайным образом выбирает DESX ключи для каждого rewebber'а в цепочке, зашифровывает их в локатор (см. рис. 18) и многократно зашифровывает документ. Таким образом, автор формирует локатор и показывает его всему миру. Все параметры безопасности, включая число узлов в цепочке, под контролем автора; каждый автор может выбрать уровень безопасности, какой он захочет.

Рисунок 18. Схематичная диаграмма цепочки.

Прямоугольники с нижним индексом означают шифрование с открытым ключом; К -DESX ключи, которые надо использовать для дешифрования возвращаемых данных. А, В и С - сайты-rewebber'bi.

Основное преимущество при использовании цепочек заключается в том, что только rewebber, ближайший к клиенту, видит незашифрованную информацию, и только rewebber, ближайший к серверу, знает, откуда он берет данные. Таким образом, один злоумышленный узел не сможет сломать всю систему.

Система Rewebber реализована на основе HTTP прокси. Эти прокси имеют кэш, для того чтобы улучшить производительность сети. Благодаря этому система получает еще одно преимущество. После кеширования данных на промежуточных rewebber'ах запросы будут достигать сервера с меньшей вероятностью. Это затрудняет использование анализа трафика, поскольку он основывается на анализе большого количества сетевых данных. Чем меньше трафик в сети, тем труднее его проанализировать. Еще одно преимущество в том, что кэшируются только зашифрованные данные, поэтому пользователь не будет нести ответственности за те материалы, которые будут у него кэшироваться.

Но главным недостатком является то, что локатор, содержащий простую цепочку rewebber'ов будет выглядеть следующим образом: http://rewebber.com/!Rj 2 OrawjGRT5 0ECKoUBa7Qv3FJlRbyejWhl0g9vpPAyeH mrYElQLlH2ifNh2Ma4UYt3laqeQRXXd7oxEvwR8wJ3cnrNbPF6rclUzr6mxIWUtlgW0uRlL0b GkAv3fX8WEcBdlJPWGT8V0YOFIjxgPL7OvuV0xtbMPsRbQg0iY=RKLBaUYedsCn0NUQ0m5JWT ElnuohJ5JyglCfkaN9j SGkdf51gdj 3RN4XHfYVyxfupgc8VPsSyFdEeR0dj 9kMHuPvLivE awqAwU3Af8mc44QBN0fMVJjpeyHSa79KdTQ5EGlPzLK7upFXtUFcNLSD7YLSclgKI3X8nkl 5s=RXbQaqm0Ax4VhKPwkLVKMMJaz9wchnpI48xhTzgndt5Hk0 9VToLyz7EF4wGH3XKPD7Yb KVyiDZytvasUBcdqpmPXTzApYLBnl4nDOylolPulRky8CxRfnC9BvQqof8 5 3n9 9vkuGKP9K4 p3H7pl6i8DOat-NrOIndpz5xgwZKc=/

Очевидно, что возникает проблема с именами, которую надо решать. Для ее решения создается виртуальное пространство имен .taz и создаются новые сервера, называемые TAZ серверами (Temporary Autonomous Zone [86]); идея в том, что .taz сайты могут быстро перемещаться.

TAZ сервер предоставляет авторам простой способ направить потенциальных читателей к их материалам, а также предоставляет читателям удобный способ доступа к этим материалам. TAZ сервер состоит из общедоступной базы данных, связывающей виртуальные имена, заканчивающиеся на .taz, с локаторами. Что важно, так это то, что оператор на TAZ сервере не может расшифровать локаторы, которые находятся в базе данных.

Общедоступность базы данных на TAZ серверах дает несколько преимуществ. Во-первых, операторов TAZ серверов нельзя обвинить в хранении запрещенных материалов, поскольку вся информация, к которой он имеет доступ, общедоступна. Во-вторых, можно изменять TAZ сервера без изменения rewebber'ов. В-третьих, TAZ серверы не могут понизить надежность всей системы.

В данной системе хорошо реализована защита анонимности авторов. Идея, используемая в этой системе, похожа на идею, используемую в системе Onion Routing. Минусом системы является то, что не защищается анонимность читателей.

Peek-a-booty

Система Peek-a-booty [87] создавалась для того, чтобы обходить систему государственного надзора за WWW, которая используется сейчас (в 1999 году) в 20 странах. Принцип работы очень простой: обходить firewall'ы при помощи альтернативного посредника к всемирной сети.

Система Peel-a-booty запускается на компьютерах пользователей в странах, которые не используют систему надзора за сетью Internet. Пользователь, находящийся в стране, которая использует цензуру, к сети компьютеров, на которых запущена система Peek-a-booty. Компьютеры этой сети получают web-странички и отсылают их пользователю.

Пользователь обходит защиту firewall'oB, поскольку он соединяется с компьютерами, которых нет в его запрещенном списке (см. рис. 19). Получаемые странички шифруются одним из распространенных стандартов для безопасной передачи и для того, чтобы защититься от просматривания содержимого firewall'aMH.

Пользователи, которые подключаются посредством системы Peek-a-booty, получают полный доступ ко всем ресурсам в сети Internet. Пользователи, которые запускают у себя эту систему, практически не замечают ее, поскольку она работает в фоновом режиме и тратит мало ресурсов.

Peek-a-booty - это распределенная система. Поскольку эта система распределенная, то правительству становится намного труднее вывести ее из строя. Если в ней будет достаточно много компьютеров, то становится практически невозможно заблокировать доступ ко всем компьютерам в этой системе. Каждый компьютер сети Peek-a-booty знает только о нескольких других компьютерах. Поэтому правительству становится еще труднее определить все адреса машин сети Peek-a-booty и внести их в список "запрещенных".

Данная система предоставляет возможность доступа к информации, которая может блокироваться при помощи firewall'oB, но она не предоставляет анонимности пользователям, читающим эту информацию. Минусом системы является то, что нет алгоритма выбора первого узла. Первый узел приходится задавать вручную, поэтому система становится сильно уязвимой.

Eternity project

Основная цель проекта Eternity - защита информации от цензуры и обеспечение анонимности при ее получении. Полное описание этой системы можно найти в [88].

Система состоит из серверов безопасности, которые контролируют несколько файловых серверов (см. рис. 20). Когда файл в первый раз загружается в систему через файловый сервер, он затем поступает на местный сервер безопасности, который потом пересылает этот файл на другие сервера безопасности. Эти сервера безопасности рассылают зашифрованную копию файла своим файловым серверам.

Рисунок 20. Система Eternity

При запросе пользователем файла, которого нет в хранилище, запрос поступает серверу безопасности. Затем этот сервер соединяется с другими случайно выбранными серверами до тех пор, пока не найдется тот, под контролем которого есть копия этого файла. Эта копия будет расшифрована, затем зашифрована публичным ключом пользователя и переслана ему.

Связь между серверами анонимная для того, чтобы защититься от анализа трафика, который может установить связь с зашифрованными и обычными файлами. Для обеспечения анонимности используются сеть миксеров и колец [89]. Первая используется для пересылки файлов пользователю, а вторая - для общения серверов безопасности. Поскольку даже при помощи анализа трафика злоумышленник не должен узнать информацию о том, где хранится определенный файл, то применяется метод заполнения трафика случайной информацией.

Наличие специальных шифровальных устройств позволяет уменьшить число копий каждого файла, которые надо хранить. Существенно то, что злоумышленник не может больше определить местоположение всех копий файла, который он хочет уничтожить.

Данная система дает довольно хорошую защиту информации. Для того, чтобы злоумышленник смог удалить определенный файл, ему придется завладеть всеми Сервер

Файловый сервер безопасности серверами безопасности этой системы. Но минусом является то, что на серверах безопасности используются специальные шифровальные устройства, поэтому для нашей системы подойдет только способ связи серверов безопасности и метод доставки файла пользователю.

Выводы

В результате анализа этих систем приходим к следующим выводам.

Плюсами системы Freenet являются хороший способ защиты анонимности пользователя и защита данных от стирания злоумышленников. Для того чтобы раскрыть анонимность пользователей, злоумышленникам придется контролировать все узлы сети. Минусом является то, что файлы хранятся в незашифрованном виде и любой пользователь имеет к ним доступ.

В системе Onion Routing хорошо реализована система защиты анонимности, но эта система предназначена только для пересылки данных. Для того чтобы сломать систему, т.е. раскрыть анонимность, требуется завладеть всеми узлами сети Onion Routing.

В системе Rewebber способ защиты анонимности авторов похож на идею системы Onion Routing. Но данная система создает статические маршруты доступа к данным, что является минусом системы. Также минусом системы является то, что не защищается анонимность читателей.

Система Peek-a-booty предоставляет возможность доступа к информации, которая может блокироваться при помощи firewall'ов, но она не предоставляет анонимности пользователям, читающим эту информацию. Минусом системы является то, что нет алгоритма выбора первого узла. Первый узел приходится задавать вручную, поэтому система становится сильно уязвимой.

Система Eternity дает довольно хорошую защиту информации. Для того чтобы злоумышленник смог удалить определенный файл, ему придется завладеть всеми серверами безопасности этой системы. Минусом является то, что система ориентирована на специальные шифровальные устройства.

Модель безопасности, которая используется в системе Freenet + pre-routing и в системе Onion Routing, наилучшим образом подходит для решения поставленных задач. Эта модель безопасности основывается на основе работающих в режиме реального времени миксеров, которые динамически будут создавать маршрут, по которому будут передаваться данные.

В. 11. Хранение с регулируемой избыточностью

Задача построения отказоустойчивой системы решается путем добавления в нее различных избыточных компонент. Существующие технологии, обеспечивающие отказоустойчивость можно разбить на три категории, в зависимости от уровня программно-аппаратного комплекса, в который вносятся избыточные компоненты:

• Аппаратные: Shared-Memory Multiprocessing, кластеры, RAID-массивы [71], Shared-Nothing Multiprocessing, Server Net Architecture [90]. В этих технологиях надежность системы обеспечивается путем добавления избыточных компонент в аппаратную платформу.

• Операционные: MS .Net, NonStop UX System Architecture [90]. Здесь надежность обеспечивается путем усложнения алгоритмов работы системных вызовов операционных систем.

• Прикладные: Microsoft Cluster [91], Error Detection/Correction Codes [92; 93], метод "зеркала" (mirrors), Server Load Balancing [94], Erasure codes [95] и др. В этих технологиях задача решается путем разработки специальных протоколов и механизмов взаимодействия прикладных программ с OS.

Естественно, так как исторически аппаратное обеспечение, операционные системы и прикладные программы развивались в тесной взаимосвязи друг с другом, то четкой грани между перечисленными категориями не существует и большинство промышленных систем, обеспечивающих отказоустойчивость обычно используют технологии всех трех категорий. Кроме этого очень часто аппаратные технологии строятся на основе прикладных, или просто одна технология может допускать как аппаратную реализацию, так и реализацию на уровне прикладных программ.

Рассмотрим, например технологию RAID, которая первоначально была создана для увеличения скорости чтения/записи на магнитные носители путем их распараллеливания. Основная идея заключается в том, что входной поток информации делится на блоки, которые, в свою очередь, записываются на диски. При считывании происходит обратный процесс - блоки собираются с накопителей и преобразовываются в единый поток. В зависимости от способа распределения блоков различают несколько уровней RAID, с нулевого по пятый (наиболее распространены 0,1 и 5 уровни).

RAID0 - алгоритм, при котором каждая порция информации входного потока делится на N фиксированных блоков (N - число дисков в матрице), а затем каждый блок записывается на свой диск. Его назначение - сделать максимально быструю дисковую систему, скорость которой в идеале в N раз превышает быстродействие одного диска (поскольку обычно скорость работы контроллера диска много выше чем самого диска).

RAID1 - или зеркалирование (mirroring) требует четного числа дисков и осуществляет попарное дублирование информации. Этот алгоритм уже обеспечивает отказоустойчивость, т.е. гарантию сохранности данных и теоретическое увеличение скорости в N/2 раз, но стоимость дискового пространства увеличивается вдвое.

RAID5 - этот алгоритм представляет собой что-то среднее между нулевым и первым. Порция информации из входного потока разделяется на N-1 блоков, а N-й блок вычисляется из N-1 первых и является контрольным. В случае потери одного из N блоков, информация однозначно восстанавливается из N-1 других. Контрольный блок каждый раз от цикла к циклу записываются на новый диск. Теоретическая скорость записи/чтения увеличивается в N/N-1 раз.

Таким образом для обеспечения аппаратной надежности в RAID-технологии также используется избыточность, однако к недостаткам подходов RAID по обеспечению отказоустойчивости следует отнести тот факт, что система предполагает наличие двух состояний - нормального и состояния восстановления. То есть в случае нарушения целостности данных система переходит в режим восстановления, и пока система не восстановит испорченные блоки обычно она не может функционировать нормальным образом. Производительность указанного режима восстановления обычно невелика.

Аналогичная проблема восстановления данных возникает при решении задачи обеспечения надежности передачи информации по каналам связи. Для этих целей используются алгоритмы исправления ошибок (Error Correction Codes, ЕСС) и обнаружения ошибок (Error Detection Codes, EDC) [92; 93]. Оба они заключаются в избыточности передачи информации путем внесения дополнительных битов в передаваемый блок данных. Первый формирует дополнительные биты так, чтобы, анализируя полученный блок, можно было бы указать где возникли искажения и исправить их. Это, так называемые, коды с исправлением ошибок. Второй алгоритм вносит избыточность лишь для того, чтобы, анализируя полученные данные, можно было сказать есть в переданном блоке ошибки или нет. Это, так называемые, коды с обнаружением ошибок. Выбор того или иного обычно зависит от требований к процессу передачи.

К недостаткам таких технологий относится их первоначальная ориентированность на вероятность ошибки канала, то есть они предполагают заранее, что количество ошибок в блоке не может превышать некоторого числа п. Это и определяет условия их применения.

Если же при передаче блока, количество возникших ошибок превышает п, то алгоритмы просто не работают.

Также следует отметить технологи erasure codes [95; 96; 97], которые наиболее близки к тому что необходимо, по мнению автора работы, для использования как основы распределенной системы хранения данных. В общем, erasure codes трансформируют сообщение, состоящее из п блоков в сообщение с количеством блоков больше чем п, так, что оригинальное сообщение может быть восстановлено из подмножества этих блоков. Обычно доля требуемых блоков называют отношением (rate) и обозначают г. Оптимальные erasure codes дают n/r блоков, где любые п достаточны для восстановления оригинального сообщения. К сожалению, оптимальные коды дороги (в терминах потребления памяти и CPU) для больших п, так что часто используются так называемые «почти оптимальные erasure codes». Они требуют (1+е)п блоков для восстановления сообщения. Уменьшение е может быть сделано за счет увеличения потребления CPU. Технология RAID является частным случаем оптимальных erasure codes.

Среди существующих технологий, обеспечивающих отказоустойчивость Internet-ресурсов, следует отметить технологию SLB (Server Load Balancing), задача которой обеспечить масштабируемость серверов, предоставляющих различные Internet-сервисы (Web,DNS,FTP). Суть его заключается в том, что несколько тесно связанных серверов объединяются в один виртуальный сервер и клиентские запросы распределяются между ними. Такой подход предполагает, что клиенты всегда обращаются к IP-адресу виртуального сервера, а функция SLB выбирает реальный сервер для обслуживания запроса клиента.

Такая технология, однако, имеет ряд недостатков. Во-первых, она предполагает зеркалирование данных каждого сервера, включенного в группу. Во-вторых, технология обеспечивает масштабируемость только по скорости обработки запросов и не обеспечивает масштабируемость по скорости передачи данных пользователю. Если каналы связи в связи с загруженностью сети не позволяют передавать объем данных, необходимый для удовлетворения всех клиентских запросов, то несмотря на то, что виртуальный сервер найдет все необходимые данные он не сможет в необходимое время передать их клиенту.

В. 12. Grid системы.

В настоящее время активно развивается концепция так называемых Grid - систем, которые иногда рассматриваются как решение проблем с запросами пользователей и основа для любых будущих сетевых сервисов. Рассмотрим такие системы более подробно.

В.12.1. Что такое Grid

Основной идеей Grid-технологии является централизованное и скоординированное распределение ресурсов, решение проблем создания виртуальных организаций. В данном случае под распределением ресурсов понимается не только обмен файлами, а прямой доступ к вычислительным мощностям, программному обеспечению, данным, периферийному оборудованию.

Технологические требования, предъявляемые к Grid, определены следующим образом:

• Гибкие отношения доступа (client-server, peer-to-peer).

• Чёткий высокоуровневый контроль над использованием ресурсов.

• Многоуровневый контроль прав доступа, локальные и глобальные политики доступа.

• Поддержка распределения различных ресурсов - программ, данных, устройств, вычислительных мощностей.

• Поддержка различных моделей пользования - многопользовательской, однопользовательской, режимов performance-sensitive и cost-sensitive.

• Контроль над качеством предоставляемых услуг, планирование, резервное предоставление услуг.

Согласно определению [98; 99], Grid системы позволяют виртуальным организациям разделять географически распределенные ресурсы таким образом, что подразумевается общие цели работы системы, подразумевается отсутствие центрального месторасположения, отсутствие централизированного управления, однотипность и отсутствие существующих доверительных отношений.

Здесь под виртуальными организациями понимается довольно широкий диапазон от небольших корпоративных отделов, находящихся в одном физическом месте, до большой группы людей из разных организаций, физически распределенных по всему миру.

Под ресурсом здесь понимается то, что может быть разделено между несколькими потребителями. Например, он может быть вычислительным - PDA, ноутбук, настольный компьютер или кластер мощных серверов, или может быть хранилищем данных, например, куском винчестера ноутбука, RAID - массива или гигантским хранилищем dataware house. Сенсор (упомянутый выше) является другим примером ресурса, так же как и кусок сетевой полосы пропускания, используемый в работе виртуальной организации.

Отсутствие центрального расположения и управления подразумевают, что работа с ресурсами не требуют выделенного центра управления. Кроме того, центральным местом в технологии является утверждение, что ресурсы не имеют предварительной информации о существовании друг друга, и не имеют никаких предварительно установленных отношений с точки зрения систем безопасности.

Существующие системы, использующие Grid технологию и инфраструктуру, не всегда полностью соответствуют этому определению и иногда имеют некоторые степени соответствия сформулированным критериям.

В общем, можно утверждать что вычисления в инфраструктуре Grid носят следующий характер: мы пытаемся запустить программу X используя ресурсы на сайте Y, являясь субъектом виртуальной политики Р, предоставляя доступ к данным в Z в соответствии с политикой Q.

В такой постановке задачи можно сформулировать 2 класса проблем. Первой проблемой является тот факт, что приложение X должно ИМЕТЬ ВОЗМОЖНОСТЬ работать в среде Y, которая может быть гетерогенной и географически распределенной (работая в парадигме параллельных вычислений).

Второй проблемой является вопрос того как координировать использование ресурсов на сайте Y и Z при действии разнообразных ограничений на их использование как определяется политиками Р и Q.

Таким образом, можно сказать что первичной целью системы Grid являлась возможность запуска ОДНОГО приложения на МНОЖЕСТВЕ узлов (распределенный «виртуальный суперкомпьютер», предназначенный для объединения ресурсов в единый комплекс), а так же поддержка «виртуальной организации», которая подразумевает собой единый иерархический механизм управления ресурсами организации.

Концепции и технологии GRID сначала разрабатывались для обеспечения возможности разделения ресурсов внутри распределенных по всему миру объединений научно-технических коллективов. При этом приложения включали совместную визуализацию больших наборов научных данных (объединение опыта), распределённый компьютинг для проведения вычислений, связанных с анализом данных (объединение компьютерных мощностей и систем хранения), и комплексацию научных измерительных устройств с удалёнными компьютерами и архивами (расширение функциональных возможностей, а также доступности).

Предполагается, что аналогичные приложения окажутся важны и в сфере коммерческой деятельности , сначала для научных и инженерных расчётов (где уже можно говорить об успешных результатах), а затем и для коммерческих распределённых прикладных систем, включая интегрированные корпоративные приложения и системы, поддерживающие бизнес партнёрство (В2В) через интернет. Приверженцами технологии ожидается, что Grid-технологии пройдут точно такой же путь, как Web, которая сначала использовалась в интересах научного сотрудничества, а затем стала применяться в электронных коммерческих системах, и станут решать проблемы обычных пользователей, а не только «суперзадачи» на «суперкомпьютере».

В.12.2. Проблемы, которые не решает Grid.

Очевидно, что в такой постановке существует набор задач, которые не могут быть решенными в рамках предложенного GRID- подхода.

Основная проблема, которая фактически не затрагивается GRID подходом - это работа ВНЕ рамок профессиональной виртуальной организации. Если хочется поддерживать систему, находящуюся, скажем, без должного административного контроля, который обычно имеется в любой организации, то оказывается что предоставляемых ею средств и возможностей недостаточно. Так, например, необходимость в конфигурировании каждого участника GRID может поставить барьер на подключении к системе таких домашних устройств, как домашний multimedia center или сотовый smartphone. Опыт развития сети Интернет и некоторых ее сервисов (например, файлобменных сетей) показал, что только децентрализованная система, для подключения к которой не требуется разрешение, может активно расти.

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

Так же можно отметить, что в классической постановке инфраструктура Grid является как бы новой, привнесенной извне поверх имеющейся вычислительно-сетевой инфраструктуры, не предназначенной для запуска старых приложений. В общем, можно сказать, что применимость Grid сроду применимости суперкомпьютеров - их мало, и так же мало задач которые их требуют и могут быть на них запущены, и особенно мало приложений, которые уже хоть как то используют возможности системы. А главное, что востребованность подхода на базе Grid в современных условиях невелика для некорпоративных потребителей и не видно предпосылок для изменения ситуации (скажем, для появления причин использования подобной технологии для домашних пользователей).

Сейчас ситуация с пониманием того что должен делать GRID меняется, но в работе автор апеллирует к классическому пониманию и определению GRED систем, тем более что даже сейчас, после почти 10 лет существования область применения GRID систем по прежнему ограничена несколькими коммерческими системами типа внутренних систем разводки микросхем компаниями Intel и Sun Microsystems, и несколькими большими академическими сетями (максимум достигнутый на 2005 год была распределенная система научных вычислений со 100 сайтами в 31 стране ).

В принципе, предложенный автором подход может быть рассмотрен как «расширение» или адаптация подхода, принятого в Grid. Но, считая что предложенные изменения идеологии системы слишком велики для рамок Grid технологий, автор будет придерживаться терминологии и представления о том, что разработанные в рамках диссертационной работы подходы являются самостоятельными, автономными и не входящими, как уже упоминалось, в рамки классического понимания Grid технологий.

В.12.3. Проблемы, которые порождает система на базе Grid.

Создавая систему на базе Grid технологии для обычных пользователей, можно столкнуться со множеством проблем, для решения которых требуется или привлечение новых, других, технологий, или изменение подхода. Кроме очевидной проблемы написания принципиально нового ПО (обычно на каких то специализированных языках или библиотеках типа MPI, НРС+ и т.п.) и проблемы начальной сложности развертывания систем такого типа для домашних пользователей, существует также некоторое количество «неочевидных» проблем, возникающих как следствие общего подхода к распределенным вычислениям. Примерами таких проблем могут считаться:

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

• Проблема с безопасностью и постоянными нарушениями privacy.

В работе предложена другая форма организации вычислительных сетей, исходя из требований конечных потребителей, которые обсуждаются в следующем разделе. Затем, на основании сформулированных требований предлагается система, которая может служить основой для решения упомянутых проблем, предлагаются технологические способы и модели организации системы, а также рассматриваются свойства полученного решения.

Заключение

В работе получены следующие основные результаты:

1. Предложены принципы функционирования качественно нового поколения средств размещения и управления ресурсами и данными как децентрализованной распределенной саморегулирующейся виртуализованной мобильной среды, являющейся совокупностью вычислительных ресурсов и хранилищ данных, объединенных коммуникационной инфраструктурой.

2. Поставлена и решена задача разработки нового подхода к виртуализации, который может быть использован как способ обеспечения мобильности приложений в виртуализованной среде.

3. Разработана система математических и имитационных моделей, а также алгоритмов и методов управления ресурсами, необходимых для функционирования предложенной виртуализованной распределенной среды, в том числе модель группового наложенного управления ресурсами и модель представления вычислительных ресурсов и способа их потребления.

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

5. Разработаны принципы функционирования распределенной среды с открытой коммуникационной инфраструктурой и возможностью переноса защиты с серверов и коммуникаций на клиентские узлы путем использования предложенной математической модели интегрированной системы контроля доступа, базирующейся на понятии «декларируемых» полномочий.

1. Тормасов А.Г., Нижник Е.И. Математическое моделирование производительностифайловой системы NTFS при нагрузке типа "запись дисковых данных" //Вестник НГУ. Серия: Информационные технологии.- 2007.- т.5, вып. 2- С. 67-77.

2. Тормасов А.Г. Модель потребления ресурсов вычислительной системы //Вестник НГУ.

3. Серия: Информационные технологии.- 2006.- т.4, вып.1- С. 63-72.

4. Тормасов А.Г., Обернихин В.А. Схема контроля доступа для распределенной одноранговой файловой системы (TorFS). //Безопасность информационных технологий,- 2005,- №3,- С. 68-74.

5. Тормасов А.Г., Хасин М.А., Пахомов ЮМ. Обеспечение отказоустойчивости в распределенных средах. //Программирование.- 2001.- №5,- С. 26-34.

6. Тормасов А.Г., Иванов В.Д., Петров И.Б., Пашутин Р.А., Холодов А.С. Сеточнохарактеристический метод расчета процессов динамического деформирования на нерегулярных расчетных сетках. //Мат. моделирование.- 1999.- т. 11. №7,- С. 118-127.

7. Тормасов А.Г., Петров И.Б. Численное исследование косого соударения жестко-гошарика с двухслойной упругопластической плитой. //Мат. моделирование.- 1992,- т.4. №3,- С. 20-27.

8. Тормасов А.Г., Петров И.Б. О численном исследовании трехмерных задач обте-канияволнами сжатия препятствия или полости в упругопластическом полупро-странстве. //Докл. АН СССР.- 1990.- т. 314. № 4,- С. 817-820.

9. Тормасов А.Г., Петров И.Б., Холодов А.С. О численном изучении нестационарныхпроцессов в деформируемых средах многослойной структуры. //Изв. АН СССР.- 1989. сер. МТТ. №4,- С. 89-95.

10. Тормасов А.Г., Петров И.Б. О численном решение пространственных задач соударения. //Изв. АН СССР.- 1990. сер. МТТ. №1,- С. 58-72.

11. Тормасов А.Г., Жуков Д.В., Петров И.Б. Численное и экспериментальное изучение разрушения твердых тел в жидкости. //Изв. АН СССР.- 1991.- сер. МТТ. №3.- С. 183190.

12. Tormasov A.G., Khasin М.А., Pakhomov Y.I. Ensuring Fault-Tolerance in Distributed Media. //Programming and Сотр. Software.- 2001.- № 27(5).- P. 245-251.

13. Тормасов А.Г. Классификация требований к сервисам по размещению, хранению и управлению ресурсами и данными. //Пробл. выч. математики, мат. моделирования и информатики: Сб. науч. тр.- М.: МЗ Пресс, 2006,- С. 282-293.

14. Тормасов А.Г., Петров В.А. Доставка информации пользователю в распределенных системах. //Пробл. выч. математики, мат. моделирования и информатики: Сб. науч. тр.- М. : МЗ Пресс, 2006.- С. 156-194.

15. Тормасов А.Г., И.В. Луковников, КС. Коротаев. Наложенное управление ресурсами ОС. //Пробл. выч. математики, мат. моделирования и информатики: Сб. науч. тр.- М. : МЗ Пресс, 2006,- С. 195-211.

16. Тормасов А.Г., Кобец А.Л., Луковников В.В. Модель управления группами потоков ввода/вывода с заданной точностью. //Модел. процессов обработки информа-ции: Сб. науч. тр. /Моск. физ.-тех. ин-т.- М., 2007.- С. 272-275.

17. Тормасов А.Г., Петров В.А. Расчет времени поиска в распределенной системе, использующей N-k схему при хранении. //Процессы и методы обработки информации: Сб. науч. тр. /Моск. физ.-тех. ин-т,- М., 2005.- С. 68-76.

18. Тормасов А.Г., Нижник Е.И. Обзор проблем тестирования производительности файловых систем. //Проблемы выч. математики, математического моделирования и информатики: Сб. науч. тр.- М. : МЗ Пресс, 2006.- С. 89-113.

19. Тормасов А.Г., Нижник Е.И. Тестирование производительности файловых систем на основе прогнозирующей модели. //Пробл. выч. матем., мат. моделирования и информатики: Сб. науч. тр.- М. : МЗ Пресс, 2006.- С. 114-135.

20. Тормасов А.Г., Нижник Е.И. Проблемы тестирования производительности Web-cepBcpaна основе прогнозирующей модели. Процессы и методы обработки инфор-мации: Сб. науч. тр. /Моск. физ.-тех. инст.- М., 2006. С. 249-257.

21. Тормасов А.Г., Хасин М.А., Пахомов Ю.И. Модель распределенного хранения данных с регулируемой избыточностью. //Электронный журнал "Исследовано в России",- 2001.-№035/010315,- С. 355-364.

22. Тормасов А.Г., Петров КБ. Численное изучение волновых процессов в слоистых средах. //Сб. Методы мат. модел. и обр. инф. М.: МФТИ, 1987.- С. 101-105.

23. Tormasov A. G., Ivanov V.D. Pashutin R.A. Petrov I.B. A new object-oriented package for scientific computation. //Int. Open Workshop «Actual Problems of Computational Mechanics Parallel Modeling» (IOW95).- 1995.- C. 23.

24. Тормасов А.Г., Иванов В.Д. Пашутин Р.А. Петров КБ. Объектно-ориентированный подход в создании сред поддержки сложных вычислений. //Юбилейная научная конференция.- Долгопрудный : МФТИ, 1996.- С. 106.

25. Тормасов А.Г., Жуков Д.В., Петров И.Б. Численное и экспериментальное изучение разрушения твердых тел в жидкости. //Информатика и медицина.- М.: Наука, 1997.-С. 156-167.

26. Tormasov A. G., Khasine М. Providing Availability of Internet Resources with Adjustable Redundancy. //Virtual Environment on a PC Cluster Workshop 2001 Protvino.- Protvino, 2001.- C. 127-137.

27. Тормасов А.Г., Обернихин В.А. Контроль доступа с протоколированием изменений в распределенной децентрализованной файловой системе (TorFS). //Электронный журнал "Исследовано в России".- 2004.- №203.- С. 2156-2165.

28. Тормасов А.Г., Протасов С. С. , Белоусов С. М. Архитектура и особенности функционирования современных операционных систем. //Объединенный научный журнал.- 2004,- 24(116).- С. 78-83.

29. Тормасов А.Г., Хасин М.А. Математическая модель хранения данных на слабосвязанных серверах. //Междунар. конференция "Математика, компьютер,образование", сборник научных трудов. Ч. 1.- Москва : Прогресс-традиция.- 2001.- С. 168-176.

30. Тормасов А.Г. Виртуализация ОС. //Открытые системы,- 2002,- №1.- С. 27-32.

31. Тормасов А.Г., Протасов С. С. , Белоусов С. М. Использование виртуальных сред для предоставления услуг по размещению ресурсов в глобальной сети. //Объединенный научный журнал,- 2004,- №24(116).- С. 74-78.

32. Тормасов А.Г. Среда для сборки многоплатформных программ. //Открытые системы,-2002,-№09.- С. 19-21.

33. Тормасов А.Г. Виртуализационные технологии и их возможности. //BYTE/Poc.- 2005.-№5.- С. 35-45.

34. Тормасов А.Г., Николаев А.Н. Технология виртуализации ОС на предприятиях. // BYTE/Poc.- 2006,- №5.- С. 37-51.

35. Тормасов А.Г., Протасов С. С., Белоусов С. М. Прошлое, настоящее и будущее: развитие архитектуры и принципов создания операционных систем. //Объединенный научный журнал,- 2004,- №24(116).- С. 83-86.

36. Тормасов А.Г., Николаев А.Н. Виртуализация сегодня: задачи, проблемы, технологии, решения. //PCWeek/RE.- 2006.- №27.- С. 12-14.

37. Tormasov A. G., Kuznetsov A.N. TCP/IP options for high-performance data transmission. //Builder Corporation Web site. http://builder.com.com/5100-637214-1050878.html.-2002.

38. Tormasov A.G., Kuznetsov A.N. Use sendfile() to optimize data transfer. //В Интернете.-http://builder.com.com/5100-637214-1044112.html.- 2002,- p. 4

39. Tormasov A. G., Kuznetsov A.N., Plant A. Take advantage of TCP/IP options to op-timize data transmission. //В Интернете.- http://builder.com.com/5100-637214-1050771.html. -2002.

40. Patent № 6,961,868 The USA. Fault tolerant storage system and method using a network ofservers. / Tormasov A., Khassine M., Beloussov S., Protassov S. ; 2005 r.

41. Patent № 7,076,633 The USA. System and method for using file system snapshots for onlinedata backup / Tormasov A., Beloussov S., Tsypliaev M., Lyadvinsky M. ; 2006 r.

42. Patent №7,076,633 The USA. Hosting service providing platform system and method. / Tormasov A., Beloussov S., Protassov S., Lunev D., Pudgorodsky Y. ; 2006 r.

43. Patent № 7,099,948 The USA. Virtual computing environment. / Tormasov A., Beloussov

44. S., Protassov S., Lunev D., Pudgorodsky Y.; 2006 r.

45. Patent № 7,209,973 The USA. Distributed network data storage system and method. / Tormasov A., Beloussov S., Protassov S., Pudgorodsky Y.; 2007 r.

46. Patent № 7,325,017 The USA. Method of implementation of data storage quota. / Tormasov

47. A., Beloussov S., Protassov S. ; 2008 r.

48. Patent № 7,328,225 The USA. System, method and computer program product for multilevel file-sharing by concurrent users. / Tormasov A., Beloussov S., Protassov S.; 2008 r.

49. Patent № 7,281,104 The USA. System and method for on-line data migration / Tormasov A.,

50. Beloussov S., Tsypliaev M., Lyadvinsky M.; 2007 r.

51. Patent № 7,222,132 The USA. Common template file system tree for virtual environments and virtual servers. / Tormasov A., Beloussov S., Protassov S., Pudgorodsky Y. ; 2007 r.

52. Moore, Gordon E. Cramming More Components Onto Integrated Circuits //Electronics.-April 1965,- T. 38 (8).- С. 114-117.

53. Ross, Philip E. Moore's Second Law.- Forbes, 1995 r.

54. Intel Corp. Gordon Moore: "An Update on Moore's Law". //В Интернете.-http://www.intel.com/pressroom/archive/speeches/gem93097.htm. 1997.

55. Shugart, A.l. //В Интернете.- http://www.alshugart.com/.

56. Gilder, George. The Gilder Paradigm. // В Интернете.-http://www.wired.eom/wired/archive//4.12/gilder.html?person=georgegilder&topicset=wi redpeople.- 1996.

57. Gilder, George. Gilder Technology Report.- 1993.

58. B. Briscoe, A. Odlyzko, and B. Tilly. Metcalfe's Law is Wrong //IEEE Spectrum.- July 2006.1. C. 26-31.

59. Wang, David Т., ред.. The CELL Microprocessor//IEEE INTERNATIONAL SOLID-STATE CIRCUITS CONFERENCE, 2005,- San Francisco: ISSCC 2005.

60. X. M. Дейтел, П. Дж. Дейтел, Д. Р. Чорнес. Операционные системы. Основы и принципы.- Москва : Бином-пресс, 2006.- С. 1204.

61. Таненбаум, Э. Современные операционные системы,- Санкт Петербург: Питер, 2002.-С. 1040.

62. Campbell, Sean и Jeronimo, Michael. Applied Virtualization Technology. Usage Models for IT Professionals and Software Developers.- Intel Press, 2006.

63. SWsoft, Inc. Virtuozzo: Server Virtualization, Virtual Server, Server Consolidation, Server Utilization, Disaster Recovery, High Availability. //В Интернете.-http://www.virtuozzo.com. 2007.

64. McCoy, Kirby. VMS File System Internals.- Digital Press, 1990.

65. Davis, Roy G. VAXcluster Principles.- Digital Press, 1993.

66. Popek, Gerald. The LOCUS Distributed System Architecture (Computer Systems Series) //The MIT Press , 1986.

67. Т.Е. Anderson, M.D. Dahlin, D.A. Patterson, R.Y. Wang. Serverless Network File System.-Computer Science Division University of California at Berkley, 1995.

68. D. Patterson, G. Gibson, R. Katz. A Case for Redundant Arrays of Inexpensive Disks (RAID).- Berkeley : University of California, 1987.

69. M. Rosenblum, J. Ousterhout. The Design and Implementation of a Log-Structured File System //Proceedings of the 13th Symposium on Operating System Principles.- 1999,- C.l-15.

70. J. Frantz, C. Tapus, J.D. Smith, J. Hickey. MojaveFS: A Transactional Distributed File System.- Caltech Computer Science at Pasadena, 2002.

71. A.V. Goldberg, P.N. Yianilos. Towards an Archival Intermemory //Proceedings of the IEEE1.ternational Forum on Research and Technology Advances in Digital Libraries, IEEE.-April 1998.- C. 147-156.

72. Y. Chen, J. Edler, A. Goldberg, A. Gottlieb, S. Sobti, P. Yianilos. A Prototype Implementationof Archival Intermemory.- Princeton : NEC Research Institute, 1999.

73. J.R. Douceur, R.P. Wattenhofer. Optimizing File Availability in a Secure Serverless Distributed File System //Proceedings of 20th IEEE SRDS.- 2001.- C. 4-13.

74. J.R. Douceur, R.P. Wattenhofer. Large-Scale Simulation of a Replica Placement Algorithms for a Serverless Distributed File System //Proceedings of 9th IEEE MASCOTS.- 2001,- C. 311-319.

75. Leuf, Bo. Peer to Peer: Collaboration and Sharing over the Internet.- Pearson Education, 2002.

76. В Интернете. Akamai, http://www.akamai.com.

77. Clarke, O. Sandberg, B. Wiley, T. Hong. Freenet: A Distributed Anonymous Information Storage and Retrieval System.- 2000 r.

78. Rubin, M.K. Reiter and A.D. Anonymous web transactions with Crowds. //Communications of the ACM.- 1999,- T. 42, 2.- стр. 32-38.

79. Hash Cash. //В Интернете.- http://www.cypherspace.org/~adam/hashcash/ . 2000.

80. D. Goldschlag, M. Reed, and P. Syverson. Onion routing for anonymous and private Internetconnections //Communications of the ACM.- 1999.- T. 42, 2.- C. 39-41.

81. Wagner, Ian Goldberg and David. TAZ servers and the rewebber network: Enabling anonymous publishing on the world wide web// First Monday.- August, 1998.- T. 3,4.

82. Bey, Hakim. T.A.Z.: The Temporary Autonomous Zone, Ontological Anarchy, Poetic Terrorism.- N. Y. : Autonomedia, 1991.

83. P. Baranowski, J. deVilla. Peekabooty Project. //В Интернете.-http://www.infoanarchy.org/en/Peekabooty.

84. Anderson, Ross J. The Eternity Service. //В Интернете.-http://www.cl.cam.ac.uk/ftp/users/rjal4/eternity.pdf. 1996.

85. Chaum, D. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability //Journal of Cryptology.- 1988 г.- Т. 1,- С. 65-75.

86. Hamann, V. Making Internet Servers Fault-Tolerant A Comprehensive Overview //Материалы конференции "Interner-Россия 96",- Москва, 1996.

87. D. Libertone, M. Brain. Windows NT Cluster Server Guidebook.- Prentice Hall, 1998.

88. Stallings, A. Data and Computer Communications. Fifth Edition.- Macmillan Publishing, 1997.

89. Adamek, J. Foundations of Coding.- Wiley, 1994.

90. H. Kameda, J. Li, C. Kim, Y. Zhang. Optimal Load Balancing in Distributed Computer Systems. (Telecommunication Networks and Computer Systems).- Springer Verlag, 1997.

91. James S. Plank, Michael G. Thomason. On the Practical Use of LDPC Erasure Codes for Distributed Storage Applications: Technical Report UT-CS-03-510.- Department of Computer Science, University of Tennessee, 2003.

92. Rizzo, Luigi. Effective erasure codes for reliable computer communication protocols //Computer Communication Review.- April 1997 r.

93. James S. Plank, Michael G. Thomason. A Practical Analysis of Low-Density Parity-Check Erasure Codes for Wide-Area Storage Applications IIThe International Conference on Dependable Systems and Networks. DSN-2004. - Florence, Italy, June 2004.

94. Ian Foster, Carl Kesselman , Steven Tuecke. The Anatomy of the Grid: Enabling Scalable Virtual Organizations. //International Journal of High Performance Computing Applications.- August 2001 г.- Т. 15 (3)- С. 200-222.

95. I. Foster, С. Kesselman, J. Nick, S. Tuecke. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration //Open Grid Service Infrastructure WG, Global Grid Forum.- 2002.

96. Schwan, Philip. Lustre: Building a File System for 1,000-node Clusters. //Linux Symposium.- Ottawa, Canada, 2003.

97. Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung. The Google File System //19th ACM Symposium on Operating Systems Principles.- Lake George, NY , 2003.

98. Stevens, W. Richard. TCP/IP Illustrated.- Wesley Pub Co, 1994. T. 1-3.

99. Варден, Б. Ван дер. Алгебра.- М. : Наука, 1979.

100. Курош, А. Курс высшей Алгебры,- М.: Наука, 1977.

101. Intel Corp. Intel® 64 and IA-32 Architectures Software Developer's Manual.- Intel Press, 2006.

102. В.М.Пименов, Е.В.Соколов. Анализ способов ускорения алгоритмов кодирования (декодирования) для отказоусточивых систем хранения данных,- Москва : б.н., 2006 г.

103. Wikipedia, the free encyclopedia. FastTrack (protocol). //В Интернете.-http://en.wikipedia.org/wiki/FastTrack. 2006.

104. Richard Rashid, Daniel Julin, Douglas Orr, Richard Sanzi, Robert Baron, Alessandro Forin, David Golub, Michael Jones. Mach: A System Software kernel. //Proceedings of the 34th Computer Society International Conference. COMPCON 89. 1989, COMPCON.

105. Tanenbaum, A.S. Distributed operating systems.- s.l. : Prentice-Hall, 1995,- P. 614.

106. M. Seltzer, K. Smith, H. Balakrishnan, J. Chang, S. McMains, V. Padmanabhan. File System Logging Versus Clustering: A Performance Comparison. //Proceedings of the Usenix Winter Conference.- 1995,- C. 249-264.

107. Schneier, В. Applied Cryptography. Second Edition. Section 18.7 Secure Hash Algorithm (SHA).- John Wiley & Sons, 1996.

108. M. Руссинович, Д. Соломон. Внутреннее устройство Microsoft Windows: Windows Server 2003, Windows XP, Windows 2000,- Санкт Петербург : Питер, Русская Редакция, 2005.

109. Intel Corp. Intel® Trusted Execution Technology. // В Интернете.-http://www.intel.com/technology/security/. 2006.

110. Ильин, P. Топологический сервер файловой системы TORFS: Дипломная работа. -Долгопрудный : МФТИ, 2001 г.

111. Ильин, Р. Сервер поддержки топологии распределенной файловой системы TorFS. // Труды 1-ой международной конференции по системам виртуального окружения на кластерах персональных компьютеров. 2001. - С. 138-159.

112. Хасин М.А. Модель распределенного хранилища в глобальной сети: Диссертация на соискание степени кандидата физико-математических наук.- 2001 г.

113. Rowstron, А. и Druschel, P. Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems // IFIP/ACM International Conference on Distributed Systems Platforms (Middleware). Heidelberg, 2001. - C. 329-350.

114. National Computer Security Center (NCSC). Department of Defense Trusted Computer System Evaluation Criteria.- United States Government Department of Defense (DoD), 1985.

115. Руководящий документ Гостехкомиссии России. Автоматизированные системы. Защита от несанкционированного доступа к информации. Классификация автоматизированных систем и требования по защите информации,- Москва : ГТК РФ, 1992,- С. 39.

116. Руководящий документ Гостехкомиссии России. Концепция защиты средств вычислительной техники и автоматизированных систем от несанкционированного доступа к информации.- Москва : ГТК РФ, 1992.- С. 12.

117. Zeichick, Alan. Processor-Based Virtualization, AMD64 Style. Advanced Micro Devices . //В Интернете.- Advanced Micro Devices, In c.-http://developer.amd.com/articles.jsp?id=14&num=l. 2006.

118. Обернихин В. А. Построение полностью децентрализованной системы контроля доступа на основе криптографических алгоритмов: Диссертация на соискание ученой степени кандидата физико-математических наук.- Москва : МФТИ., 2004.

119. Rowstron, А. и Druschel, P. Merkle, R. С. Protocols for public key cryptosystems // Symposium on Security and Privacy. 1980. - C. 122-134.

120. Merkle, R. "Secrecy, authentication, and public key systems": Ph.D. dissertation. Dept. of Electrical Engineering, Stanford Univ., 1979.

121. El Gamal, T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms // IEEE Trans. Inform. Theory. 1985 r. - T. 31 - C. 469-472.

122. Kholodov A. S., Kholodov Y.A. Computational models on graphs for the nonlinear hyperbolic system of equations. 2004 r. - T. 476 - C. 161-167.

123. А. С.Холодов, Я.А.Холодов, Н.В.Ковшов. Сетевые вычислительные модели для нелинейных систем уравнений гиперболического типа. //В Интернете. http://swsoft.mipt.ru/nkovshov/SVM.doc. 2006.

124. Захаров, В. А. Моделирование распределённых вычислительных систем непрерывными уравнениями: Выпускная квалификационная работа на степень бакалавра Москва : Московский Физико Технический Институт, 2007.

125. Aurema, Inc. Aurema: Application Performance and Server Consolidation Solutions, USA. //В Интернете. http://www.aurema.com.

126. Rabin, Michael O. Efficient dispersal of information for security, load balancing, and fault tolerance // Journal of the ACM (JACM) 2, New York : ACM Press. - April 1989 r. - T. 36,- C. 335-348.

127. Тормасов А.Г., Николаев A.H. Виртуализация сегодня: задачи, проблемы, технологии, решения // PCWeek/RE. №27. - 2006 г. - С. 12-14.