Содержание к диссертации
Введение
I. Обзоры существующих систем 10
1. Системы хранения данных 10
Google File System (GFS) 10
Pastry 12
Beehive 14
2. Системы доставки информации 16
Akamai 16
Border Gateway Protocol (BGP) 18
Выбор ближайшего веб-сервера 22
3. Методики моделирования 25
Моделирование распределенных систем управления с помощью
марковских процессов 25
Моделирование распределенных систем с помощью сетей Петри 27
II. Модели распределенной системы 32
1. Круг рассматриваемых систем 32
Предпосылки 32
Схема хранения файлов 32
2. Имитационная модель 33
Обозначения 34
Передача данных 35
Усеченное нормальное распределение 37
3. Теоретическая модель 38
III. Прогнозирование длительности поиска 40
1. Процедура получения файла 40
Обоснование выбора 40
Описание процедуры 41
2. Постановка задачи 42
3. Вывод времени поиска 42
1. Обозначения 42
2. Время поиска 43
4. Особенности практического использования выведенного 47
1. Метод расчета -. 47
2. Выбор начальных параметров 48
5. Пример использования 49
1. Условия расчета 49
2. Представление результатов 50
3. Результаты 51
IV. Длительность поиска в распределенной системе с регулярной структурой в условиях точечной загруженности 57
1. Базовые понятия 58
a) Регулярность структуры 58
b) Точечная загруженность 59
2. Математическая постановка 59
3. Имитационное моделирование 60
4. Теоретическая оценка 62
5. Результаты 66
V. Длительность миграции 68
1. Задача о миграции 68
Базовые термины 68
Два этапа миграции 69
Математическая постановка 69
2. Оценка длительности миграции 70
Имитационная 70
Теоретическая 72
3. Сложность алгоритмов 73
Имитационного 73
Теоретического 76
4. Пример 76
Выбор распределений 76
Распределенная система 77
Результаты 78
VI. Перенос задания в вычислительной системе 81
1. Задачао переносе 81
Актуальность задачи 81
Модель вычислительной распределенной системы 82
Модель компьютера 82
Предположения и допущения 83
Постановка задачи 84
2. Решение 84
Общая схема 84
Сетевые расходы 85
Вычисление задержки 85
Функции потребления ресурсов. Вычисление постоянного члена 92
Заключение 97
Список использованных источников
- Системы доставки информации
- Имитационная модель
- Особенности практического использования выведенного
- Точечная загруженность
Введение к работе
1. Актуальность темы.
Бурное развитие сетевых технологий последних десятилетий требует
постоянного повышения уровня организации коммуникации. Привнести упорядоченность в коммуникационные структуры призваны распределенные системы, управляющие множеством объединенных в сеть компьютеров, представляя их единым целым. Причем предназначение распределенных систем может широко варьироваться: от манипулирования информационными потоками между отдаленными уголками планеты, до контроля кластеров относительно недалеко разнесенных машин.
Главное преимущество децентрализованных распределенных систем перед имеющими ярко выраженный центральный узел - отказоустойчивость. Причем с развитием сетевой инфраструктуры возрастает важность этого свойства, побуждая активное расширение этого класса распределенных систем.
N-k-cxQMa. хранения данных позволяет собирать разбитый на N порций файл из любых к из них. Это компромисс между избыточностью хранения и экономией свободного места, позволяющий гибко регулировать границу между ними. Схема начинает применяться в распределенных системах, получая все большее распространение.
Виртуальный сервер имитирует реальный: обрабатывает сетевые запросы от клиентов. Одной из самых существенных характеристик реального сервера является его доступность. В любой момент времени он должен быть готовым обработать поступивший запрос. Длительность миграции виртуального сервера - это то время, в течение которого он будет недоступным для клиентов. Поэтому крайне важно знать оценку этой величины. На основе этой оценки может приниматься решение о том, производить миграцию или нет.
Особое внимание уделено в работе возможности определения зависимости длительности миграции от характеристик распределенной системы. Она позволяет выделить степень влияния на длительность отдельных факторов, а также оценить, насколько сократится время миграции при их улучшении.
2. Цель работы, задачи исследования.
Цель диссертационной работы - разработка математических моделей сетевых процессов в децентрализованных распределенных системах, использующих N-k-схему хранения файлов, на примере поиска файла и миграции виртуальных серверов.
В работе ставятся следующие задачи исследования:
• Оценка длительности поиска файла в децентрализованной распределенной системе, использующей N-к-схєму хранения файлов.
• Оценка длительности миграции виртуальных серверов в децентрализованной распределенной системе, использующей N-k-схему хранения файлов.
• Построение зависимостей длительностей поиска и миграции от входных параметров соответствующих алгоритмов.
• Оценка длительности выполнения виртуальным сервером задания в децентрализованной распределенной системе, использующей N-к-схему хранения файлов.
3. Научная новизна.
Научная новизна работы заключается в предложенных математических и имитационных моделях процедур поиска файла и миграции виртуального сервера. Имитационная модель отличается от существующих аналогов гибкостью - возможностью учесть широкий спектр внешних факторов, универсальностью - она может быть использована для моделирования и других сетевых процессов, точностью - результаты были подтверждены теоретическими оценками. В работе также была предложена новая методика моделирования процесса выполнения задания виртуальным сервером. Полученная оценка длительности выполнения задания может служить критерием сравнения целевых узлов миграции.
4. Практическая ценность.
Имитационная модель поиска файла и миграции виртуального сервера достаточно универсальна: она может быть использована для моделирования широкого спектра сетевых процессов, таких как балансировка хранения данных, доставка информации и др.
С помощью комплекса программ были получены распределения длительности поиска файла и миграции виртуальных серверов, а также прослежены зависимости их средних значений от различных входных параметров. Распределения дают возможность прогнозировать значения соответствующих величин с определенной вероятностью. Зависимости величин от входных параметров позволяют оптимизировать эти параметры исходя из минимизации длительностей.
Важное практическое значение имеют математические модели поиска файла и миграции виртуального сервера. Они позволяют сравнить теоретические оценки с имитационными, проверяя точность последних.
Модель процесса выполнения задания позволяет оценить время его выполнения на выбранном узле распределенной системы. Эта оценка важна в задаче балансировки нагрузки на вычислительную сеть. Она может использоваться для выбора целевого узла миграции виртуального сервера.
5. Краткое содержание работы.
В первой главе дается обзор существующих распределенных систем, схем поиска и доставки информации в них, а также методов их моделирования. В этой главе обсуждаются работы, подобные данной, демонстрируются пути решения поставленных в диссертации задач, методы моделирования распределенных систем.
Для обзора выбирались типичные представители систем передачи данных и распределенных хранилищ. Также представлены другие методики моделирования распределенных систем.
Ни одно из рассмотренных решений напрямую не применимо к децентрализованным распределенным системам с N-k-схемой хранения данных. Хотя некоторые их элементы были включены (или оказались общими) в предлагаемые решения поставленных в работе задач.
Вторая глава посвящена моделям, с помощью которых будут решаться поставленные задачи: имитационная и математическая. Для них вводятся основные обозначения, описываются как реальные величины представляются в моделях.
В третьей главе на основании описанных выше моделей решается задача о прогнозировании длительности поиска в децентрализованной распределенной системе, использующей N-k-cxQMy при хранении. Она заключается в нахождении распределения длительности поиска Т как случайной величины. Для этого сначала выводится выражение для длительности поиска в зависимости от случайных параметров и объясняется сложность получения функции распределения аналитически. Затем предлагается имитационный метод для получения выборки длительности поиска и эмпирической функции распределения по ней. В конце главы работа предложенного алгоритма демонстрируется на конкретном примере, показаны распределения длительности для различных узлов системы, а также зависимость среднего значения длительности от глубины поиска.
В четвертой главе решается задача о влиянии загруженности соединений децентрализованной распределенной системы на длительность поиска. Предполагается, что повышение загруженности происходит в результате роста количества запросов к определенным узлам распределенной системы. После пояснения базовых понятий (регулярность структуры распределенной системы и точечная загруженность) в главе описываются пути решения поставленной задачи в рамках двух моделей из второй главы. Завершает главу демонстрация работы алгоритма на конкретном примере.
Пятая глава посвящена миграции виртуальных серверов в децентрализованной распределенной системе, начале в ней описываются новые термины и двухэтапная схема миграции, ставится математическая задача. Решение также осуществляется на базе двух моделей из второй главы. Причем в нем используются некоторые результаты четвертой главы. В главе вычисляются сложности двух алгоритмов решения в зависимости от основных влияющих на нее факторов. В конце главы снова демонстрируется конкретный пример работы представленных алгоритмов, приводятся графики функций плотности и распределения длительности миграции для двух моделей, объясняются их отличия и условия сводимости одних результатов к другим.
В последней шестой главе решается задача о переносе выполняемого виртуальным сервером задания в децентрализованной распределенной системе. Для этого предлагается новая модель процесса выполнения задания (условно разделена на модель вычислительной сети и модель компьютера). Главной слолшостью в решении задачи является вычисление задержки выполнения задания на узле распределенной системы за счет одновременного выполнения других заданий. Поскольку функции потребления заданием вычислительных ресурсов считаются известными для всех компьютеров сети, отдельным пунктом вынесен способ их определения: функции измеряются на одном «модельном» компьютере и пересчитываются для любого другого узла исходя из его характеристик.
В заключении описываются основные результаты и выводы работы.
Системы доставки информации
Проект Akamai ([10, 11]), как системы ускоренной доставки информации из интернета пользователям, был основан Тимом Беренрс-Ли из Массачусетского технологического института (MIT) в начале 1995-го года. Сейчас это основной продукт одноименной успешно развивающейся компании.
Идея ускорения доставки информации из интернета состоит в «расширении» его главных узких мест, например, соединений источника информации и ее получателя с интернетом (так называемые «первая миля» и «последняя миля»). «Расширение» достигается сети специальных серверов:
Edge Services. Они распределены по всему миру - везде, где есть пользователи Akamai. Качество соединения между ними достаточно высокое. Edge Services составляют прослойку между источником информации и получателем (рис. 1.3). Задача доставки информации сводится, таким образом, к ее пересылке от источника к прослойке и от прослойке к получателю. Различные узкие места на первом этапе должны обходиться, по замыслам разработчиков, за счет специальных алгоритмов маршрутизации. Второй этап пути, как предполагается, должен проходить по довольно разгруженной «окраине» интернета (это достигается расположением Edge Services). Поэтому там стоит лишь задача выбора «ближайшего» сервера. Вся информация активно кэшируется на серверах. Кэш обновляется, при получении сервером специального сообщения. Так, если клиент запросит какую - то информацию, то сначала проверится ее наличие на «ближайшем» Edge services Клиенты . Структура системы Akamai сервере. Если желаемого там нет, запрос идет к источнику. Основная идея алгоритма поиска «ближайшего» к клиенту сервера состоит в том, что специальные службы на серверах регулярно (каждые 10 секунд) составляют карты трафика локальной подсети, определяют степень загруженности соседних машин. Исходя из этой карты и выбирается «ближайший» сервер. К сожалению, более детального описания алгоритма (как и других, например, алгоритмов маршрутизации) закрыт для общественности.
С точки зрения пользователя система выглядит значительно проще. Он не видит ее распределенной структуры. Посылая запрос, он указывает имя источника информации в интернете (например, www.site.com). Перенаправление запроса осуществляется (как и в случае с Google) ДНС сервером, принадлежащим Akamai и обслуживающим этот источник.
Выделим существенные для нас особенности Akamai: Иерархичность распределенной структуры: один источник и множество кэш-серверов (Edge Services). Метрика, по которой осуществляется выбор «ближайшего» кэш-сервера, основана на картах текущей загруженности сети. Border Gateway Protocol (BGP).
Протокол BGP ([12, 13, 14]) определяет общение маршрутизаторов в интернете. Именно он ответственен за распространение появляющихся, новых маршрутов, за выбор сервером основного маршрута доставки пакетов к какому-нибудь пункту назначения, фактически, за связность глобальной сети интернет.
Последняя версия протокола (BGP-4) вышла в 1995 году. Таким образом, он уже 10 лет справляется со своей задачей. Причем, если учесть количество участников общения и, самое главное, их рост за эти 10 лет, справляется довольно успешно.
Все множество компьютеров, подключенных к интернету, разбито на непересекающиеся подмножества, имеющие схожие предпочтения при маршрутизации - автономные системы (АС). Логика протокола BGP несколько различается в зависимости от того, находятся ли общающиеся маршрутизаторы внутри одной автономной системы (тогда протокол называют IBGP - Internal BGP) или в разных (EBGP - External BGP).
Стандартный «жизненный путь» маршрутизатора, использующего BGP таков: 1. Появившись в сети он устанавливает BGP-соединение с соседями -маршрутизаторами. 2. Получает от соседа всю его таблицу маршрутизации. Это происходит единственный раз при «рождении» нового маршрутизатора. 3. До «конца своих дней» маршрутизаторы уведомляют друг друга о появляющихся маршрутах или возникающих ошибках.
Причем, протокол BGP отличается тем, что сравнение маршрутов, выбор одного из нескольких, осуществляется сразу при их появлении, не при доставке пакета. Получив пакет, маршрутизатор сразу отправляет его по заранее выбранному пути
Имитационная модель
Распределенную систему в данной модели будем понимать как граф, узлы которого есть компьютеры, хранящие некоторые данные, а ребра -физические каналы передачи информации. Каждый элемент графа, узел или ребро - характеризуется определенным набором параметров, например, производительность машины, или пропускная способность узла.
Обозначения.
Многие факторы в модели носят случайный характер, поэтому при описании происходящего п п у т т была выбрана вероятностная модель. В ней n \) щ \)m О пт О параметры узлов и соединении системы n т , Рис. 2.2. Обозначения представляются случайными величинами (см. рис. 2.2): \ - время пересылки сетевого пакета узлом п, п - время обработки запроса (на сборку файла) на узле п, -пропускная способность соединения между узлами лит. Оп— количество требуемых порций на машине и, 1, если посылка пакета от п до т была У. = пт успешной, О, если при посылке пакета от п до т произошла ошибка (пакет не дошел до т). Заметим, что Р{ пт = 1} = 0 означает, что узлы п и т просто не соединены.
Сама длительность миграции также представляется в модели случайной величиной, зависящей от вышеописанных.
Для величин \ и I выбрано усеченное нормальное распределение. Vnm считается равномерно распределенным на отрезке [l,J ax] чтобы подчеркнуть неустойчивость сети. Максимальная пропускная способность V" здесь - это физическая характеристика самого пропускного канала.
Остальные параметры при оценке длительности миграции считаются заданными постоянными величинами: Структура распределенной системы: множество узлов и схема связей между ними, Ту- сетевая задержка (latency) при передаче данных между узлами / и j. Эта задержка фактически определяется физическим расстоянием между узлами, поэтому меняться не может, d - глубина поиска (максимальное количество узлов, которое может пройти запрос с поиском), М— общее количество узлов в сети. Хотя такое разделение довольно условно. Постоянные параметры можно перевести в разряд случайных, если потребуется определить характер зависимости искомой величины от них. Передача данных. Между соседями. Для представления в модели времени передачи данных между соседними узлами мы будем использовать два подхода: стандартный и упрощенный. Стандартный подход. Стандартное представление времени передачи данных объема V по соединению между узлами і и j (обозначим его за 0tj (V)) с пропускной способностью Vy и задержкой т{. таково: ) = , (2-1) у То есть длительность передачи данных между соседними узлами - это случайная функция, зависящая от случайной величины Vy и неслучайного параметра V. После введения &у(У) следует уточнить роль Vy - она моделирует среднюю пропускную способность соединения между / и j за период передачи данных. Упрощенный подход.
В ряде задач, например для оценки длительности поиска файла в распределенной системе (будет описана ниже), нет смысла вводить зависимость времени передачи данных между соседними узлами от объема V. Потому что при поиске рассылаются только пакеты запроса одинакового размера. В этом случае логично представить 0y(V) нормальной случайной V величиной. Математическое ожидание при этом берется равным Е{— + т ) V с объемом запроса Vпорядка 1 МБ.
Особенности практического использования выведенного
Любая реальная система имеет свои ограничения, пределы, за которыми ее использование перестает быть целесообразным. Данная глава посвящена изучению характера поведения длительности поиска в распределенной системе в условиях повышения загруженности сети ([35-38, 41]). В частности - научиться находить предельно допустимую загруженность. В работе предполагается, что повышение загруженности происходит в результате роста количества запросов к определенным узлам распределенной системы. Такая схема не случайна, она взята из реальной ситуации: сайт, посвященный олимпийским играм в Сиднее, во время их проведения одновременно посещали несколько миллионов пользователей, что сильно сказывалось на скорости получения данных каждым из пользователей. Во время некоторых соревнований сервер был недоступен из-за перегрузки.
Задача решается в рамках двух описанных во второй главе моделей. Процедура поиска файла описана в разделе 1. Процедура получения файла. Разъясним используемые понятия, саму задачу и путь решения. 1. Базовые понятия. а) Регулярность структуры. Регулярной назовем распределенную систему, каждый узел которой соединен ровно с / соседями. В данной главе все примеры были выполнены для 1 = 4, т.е. для графов в виде решеток (рис. 4.1).
Регулярность не является Рис. 4.1. Регулярная распределенная система необходимым для решения задачи ограничением. Оно было выбрано для упрощения расчетов как один из вариантов.
При такой структуре, например, нетрудно посчитать количество узлов, достигаемых из центрального ровно за / шагов Д: Д = 4/, а таюке количество узлов, вовлеченных в процедуру поиска через / шагов Bt (считая, что ни один запрос не потерялся при передаче): Д=1 + ц =1 + 2/-(/ + 1) 7=1 Заметим, что общее число узлов в окрестности поиска глубины d равно B,=l + 2d-(d + l), b) Точечная загруженность.
В данном разделе изучается влияние загруженности соединений распределенной системы на длительность поиска. Предполагается следующий сценарий: на выбранных заранее компьютерах появляется актуальная информация, которая «притягивает» произвольно расположенных пользователей, повышая загруженность прилежащих соединений. Степень актуальности хранящейся на выбранном компьютере информации определяет количество поступающих запросов, а следовательно и величину прироста загруженности. Каждая порция актуальной информации увеличивает загруженность всех соединений системы на величину, убывающую в геометрической прогрессии в зависимости от их удаленности от выбранного компьютера.
Увеличение загруженности соединения выражается в пропорциональном росте длительности передачи данных по нему. Приращения загруженности, вызванные двумя различными узлами с актуальной информацией, суммируются.
На рис. 4.2 показано, как прирост загруженности снижается с расстоянием. Максимум R соответствует количеству запросов, приходящих на узел с актуальной информацией. На каждого из ближайших соседей будет приходиться в среднем в /(=4) раз меньше запросов и т.д. Полная картина загруженности сети будет представлять собой несколько таких «горок» для каждого узла с актуальной информацией.
В главе ставится задача изучить поведение длительности поиска в регулярной распределенной системе в стрессовой ситуации: при возрастании количества запросов к актуальной информации. В введенных обозначениях это будет выглядеть следующим образом: Перенумеруем все узлы распределенной системы: 1,2,...,М. Пусть дан набор узлов с актуальной информацией: i:,i2,..Jr где У/»О -М Каждому Требуется найти зависимость среднего значения длительности поиска, как случайной величины, от времени T(t). 3. Имитационное моделирование. Для передачи запроса на поиск между соседями использовался упрощенный подход (см. раздел Передача данных.). Размер пакета с запросом составлял Vq - 1МБ.
Для решения поставленной задачи в рамках имитационной модели необходимо уметь получать длительность поиска Г по входных параметрам: Структура распределенной системы: ее узлы и схема связей. Величины &1, I и 0„ для всех узлов, @lm{Vq) и „„, для всех соединений. Параметры N и к схемы хранения файлов в распределенной системе. Глубина поиска d.
Точечная загруженность
При решении задачи будем предполагать следующее: 1. Функции потребления ресурсов заданий считаем кусочно непрерывными. Это естественное предположение: потребление ресурсов заданием может изменяться скачком при их выделении или освобождении, но количество таких моментов конечное (о кусочной непрерывности см [90]). 2. Не учитывается взаимодействие задачи с внешними устройствами, кроме диска, памяти и процессора. Учет всех возможных устройств просто невозможен. Хотя бы потому, что постоянно появляются новые. Поэтому мы выделили основные. 3. Постоянство скорости обработки запросов устройствами, (линейная зависимость количества обрабатываемых данных от объема входных). В реальности это не совсем верно. Обычно запросы к устройству буферизуются и отсылаются пакетами фиксированного размера. Для диска в ОС Windows 2003, например, этот размер составляет 64 КБ. Однако учет этих особенностей требует доскональных знаний о размере каждого посылаемого заданием запроса. Сложность их получения и учета практически исключает этот путь. К тому же непостоянство скорости обработки будет нивелироваться при больших объемах запрашиваемых данных. 4. Объем диска не ограничен. Современное развитие устройств долгосрочного хранения данных сильно ограничивает число задач, которые могут упереться в границу дискового пространства. 5. Выполняющиеся на машинах задания считаем равноприоритетными. Предположение сделано для удобства расчетов. Оно позволяет упростить модель: общая очередь запросов к устройствам согласуется с реальностью только при этом допущении. В общем случае это была бы очередь с приоритетами. 6. Задания конечные по времени выполнения.
Допущение также не ограничивает общности, поскольку любое бесконечное задание рассматривать в виде последовательности конечных.
Постановка задачи. На машине / выбрано задание. Необходимо определить, ускорит ли ее выполнение перенос на машину /. 2. Решение. Общая схема. Перенос задания на другую машину ускорит его выполнение, если Т (І0) Т ) + Т!(І0+Т )),ГДЄ: Г!(70) - длительность выполнения у-го задания на машине /, если оно начнется в момент времени t0, Tjf (У) - длительность переноса данных объема V по сетевому каналу между компьютерами / и /. Длительность выполнения T (t0) разобьем на постоянную и переменную составляющие: 7"(0 = Го+АГ(/0) (6.1)
Здесь TQ - время выполнения нашего задания на «пустой» г -й машине, без других выполняющихся заданий, a AT (t0) - задерлска выполнения у -го задания, связанная с одновременным выполнением других. Последняя часть определяется количеством и типами выполняющихся заданий. Только она зависит от начального момента запуска у -го задания. Сетевые расходы. Длительность передачи данных объемом F между узлами / и / T (Vj) будем вычислять в рамках стандартной модели, где каждое сетевое соединение характеризуется двумя параметрами - пропускной способностью Vй и физической задержкой (латентностью) т 1:
Если узлы / и / не являются непосредственными соседями, и путь от / к / содерлсит несколько физических каналов с различными параметрами F/, то V !=minVll. Вычисление задержки. Дисковая задержка ATD.
Диск обрабатывает запросы с некоторой скоростью (пропорциональна скорости вращения диска). За один запрос молено получить ограниченный объем данных. В предположении малости этого объема по сравнению с общей нагрузкой на диск, молшо считать, что длительность обработки запросов диском линейно зависит от объема считываемых/записываемых данных.
