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

• Соколов Александр Михайлович
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Соколов Александр Михайлович

Введение

Глава 1. Исследование системы вида MMAP/PH/N/R с приоритетным обслуживанием методами теории

очередей

1.1 Введение

1.2 MMAP-поток и РЫ-распределение

1.3 Постановка задачи

1.4 Система ММАР/РЫ/К/И, с двумя классами приоритетов

1.4.1 Цепь Маркова, описывающая состояние системы

1.4.2 Стационарное распределение цепи Маркова

1.4.3 Характеристики производительности системы

1.4.4 Вычисление матриц Р^), А^^,•), и Ь^^, •)

1.4.5 Время нахождения стационарного распределения системы

1.5 Заключение

Глава 2. Исследование характеристик производительности многолинейной СМО большой размерности с

приоритетным обслуживанием

2.1 Введение

2.2 Получение оценок характеристик производительности с

помощью имитационного моделирования

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

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

2.3.2 Методы машинного обучения

2.3.3 Генерация входных данных

2.4 Численные результаты

2.4.1 Получение оценок характеристик производительности с помощью имитационного моделирования

2.4.2 Получение быстрых оценок характеристик производительности с помощью комбинированного метода

2.4.3 Анализ времени расчетов

2.5 Заключение

Глава 3. Разработка распределенной системы для потоковых

вычислений

3.1 Введение

3.2 Архитектура системы

3.2.1 Задачи: определение, жизненный цикл, приоритизация

3.2.2 Пользовательский интерфейс и серверная часть приложения

3.2.3 Супервизор

3.2.4 Обработчик подзадач

3.2.5 Время выполнения задачи

3.3 Аналитическая модель системы для потоковых вычислений

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

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

3.3.3 Составление системы уравнений баланса для случая,

когда в системе есть заявки, ожидающие выполнения

3.3.4 Нахождение стационарного состояния системы

3.3.5 Характеристики производительности системы

3.4 Численные результаты

3.4.1 Исследование стационарных характеристик производительности аналитическим методом

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

3.4.3 Пример задачи

3.4.4 Оценка влияния контейнеризации на время получения результата

3.4.5 Зависимость времени выполнения задачи от числа обработчиков

3.5 Заключение

Глава 4. Исследование вычислительных систем с

приоритетным трафиком

4.1 Сетевая балансировка нагрузки

4.1.1 Виды балансировки сетевой нагрузки

4.1.2 Методы балансировки сетевой нагрузки

4.1.3 Балансировщик сетевой нагрузки HaProxy

4.1.4 Реализация очередей и приоритетов в HaProxy

4.1.5 Численные результаты

4.2 Асинхронная очередь задач

4.2.1 Система для распределенных вычислений Celery

4.2.2 Численные результаты

4.3 Заключение

Заключение

Список сокращений и условных обозначений

Словарь терминов

Список литературы

Список рисунков

Список таблиц

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

ЭВМ

Приложение Б. Акты о внедрении

Введение диссертации (часть автореферата) на тему «Аналитические и программные методы оценки характеристик производительности вычислительных систем с приоритетным обслуживанием»

Введение

Одной из важных задач при проектировании и анализе вычислительных систем является исследование характеристик производительности. Во многих вычислительных системах и сетях связи данная задача усложняется использованием приоритетного доступа пользователей к приложениям и услугам. Примерами систем с приоритетным трафиком являются системы IoT (Internet of Things), системы для распределенных вычислений, сетевые балансировщики нагрузки и др. При проектировании систем важным аспектом являются характеристики производительности: время отклика, время до начала обслуживания заявки, среднее число заявок в системе, среднее число заявок в очереди и др. Учитывая стохастический характер поступления и обработки задач, в рассматриваемых системах основной интерес представляют стационарные характеристики производительности. В качестве математического аппарата для отыскания и исследования стационарных характеристик производительности приоритетных стохастических систем эффективно применяются методы теории очередей (теории массового обслуживания).

В качестве входных потоков рассматриваемых систем массового обслуживания (СМО) используются коррелированные MAP-потоки, описывающие трафик в компьютерных системах и сетях. Естественным обобщением MAP-потоков на случай приоритетного неоднородного трафика является MMAP (Marked Markov Arrival Process) - маркированный Марковский входной поток, который позволяет описывать коррелированное поступление заявок для произвольного предусмотренного в системе числа приоритетов К ^ 2. Для моделирования обработки заявки в теории очередей используется PH-распреде-ление (Phase type, распределение фазового типа). PH - распределение является обобщением ряда распределений, таких как: распределение Эрланга к-го порядка, гиперэкспоненциальное распределение и др. Более того, для любого неотрицательного распределения случайной величины A(t) можно подобрать PH-распределение сколь угодно близкое к распределению A(t) в условиях слабой сходимости.

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

буфером памяти. Например, в системе балансировки сетевой нагрузки есть ограничения на число одновременных сетевых запросов, часть из которых находится в ожидании (в буфере) до тех пор, пока не освободится сервер для обработки. Аналогично в системах для распределенных вычислений, где для обработки задач предусмотрено несколько серверов и буфер ограниченной памяти для задач. В общем виде приоритетные системы в терминах Кендалла обозначаются как MMAP/PH/N/R, где MMAP - входной поток заявок с приоритетами, в котором предусмотрено K классов приоритетов, PH - распределение времени обслуживания, N - число обслуживающих приборов, а R - размер буфера в системе .

Исследованиям вычислительных приоритетных систем на базе математических моделей теории очередей посвящен ряд работ, среди которых следует особо отметить работы отечественных и зарубежных учёных: В.М. Вишневский, В.И. Клименок, А.Н. Дудин, В.В. Рыков, К.Е. Самуйлов, С.Н. Степанов, Ю.В. Гайдамака, С.П. Моисеева, А.А. Назаров, Е.В. Морозов, Р.Л. Смелянский, В.Г. Карташевский, Р.В. Разумчик, D. Lucantoni, M.F. Neuts, G. Horvath, B. Sun, V. Ramaswami, A. Joohnson, G. Horvath, A. Krishnamoorthy и др.

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

Объектом исследования являются вычислительные системы с приоритетным обслуживанием.

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

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

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

1. Разработка и реализация алгоритма вычисления стационарных характеристик производительности системы массового обслуживания вида ММАР/РЫ/К/Я с приоритетным обслуживанием.

2. Разработка имитационной модели для получения оценок стационарных характеристик производительности системы ММАР/РЫ/К/Я большой размерности с приоритетным обслуживанием.

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

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

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

1. Разработана математическая модель и программный комплекс для получения точного аналитического решения и стационарных характеристик производительности системы с распределенной обработкой данных и приоритетным обслуживанием. (п.9 паспорта специальности 2.3.5)

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

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

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

систем с приоритетным обслуживанием. (п.3 паспорта специальности 2.3.5)

Область исследования. Диссертационная работа соответствует паспорту специальности 2.3.5 «Математическое и программное обеспечение вычислительных систем, комплексов и компьютерных сетей», а именно следующим пунктам:

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

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

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

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

Теоретическая и практическая значимость. Аналитические и имитационные модели и методы, разработанные в диссертации, могут эффективно использоваться для оценки характеристик производительности многолинейных приоритетных вычислительных систем. Разработанный программный комплекс в рамках диссертационного исследования может применяться для улучшения эффективности получения результатов научных расчетов. Практическая значимость диссертационной работы подтверждается актами о внедрении, полученными от НИИ «Центрпрограммсистем» и МФТИ ГУ. Результаты работы также были представлены в исследованиях, проводимых по грантам Российского фонда фундаментальных исследований №19-07-00919, №20-37-70059 и Российского научного фонда №22-49-02023.

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

Основные положения, выносимые на защиту:

1. Математическая модель двухприоритетной системы массового обслуживания вида MMAP/PH/N/R и программный комплекс для вычисления стационарных характеристик производительности вычислительных систем с приоритетным обслуживанием.

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались на конференциях: «Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems» (Москва, 13-17 апреля 2020); «Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems» (Москва, 19-23 апреля 2021); «5th International Scientific Conference on Information, Control, and Communication Technologies» (Астрахань, 4-7 октября 2021); «6th International Scientific Conference on Information, Control, and Communication Technologies» (Астрахань, 2-7 октября 2022); «International Conference named after A. F. Terpugov Information Technologies and Mathematical Modelling» (онлайн, 1-5 декабря, 2021); «International Conference on Distributed Computer and Communication Networks: Control, Computation, Communications» (Москва, 25-29 сентября 2023); «XVIII Всероссийская школа-

конференция молодых ученых Управление Большими Системами» (Воронеж, 5-8 сентября 2023).

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

Публикации. Основные результаты по теме диссертации изложены в 15 печатных изданиях, 3 из которых изданы в журналах, рекомендованных ВАК, 7 —в периодических научных журналах, индексируемых Web of Science и Scopus, 5 —в тезисах докладов. Зарегистрирована 1 программа для ЭВМ.

Объем и структура работы. Диссертация состоит из введения, 4 глав, заключения и 2 приложений. Полный объём диссертации составляет 150 страниц, включая 54 рисунка и 12 таблиц. Список литературы содержит 132 наименования.

Глава 1. Исследование системы вида MMAP/PH/N/R с приоритетным обслуживанием методами теории очередей

1.1 Введение

Системы массового обслуживания с приоритетами, являющиеся важным разделом теории очередей [1], эффективно используются при анализе технических и социальных систем [2—8]. Примерами систем с приоритетным трафиком являются цифровое телевидение [9], в котором передача синхронизирующих сигналов имеет более высокий приоритет, чем передача видео, оптические сети нового поколения с поддержкой приоритетных классов обслуживания (QoS), в частности - системы Интернета вещей (IoT) [3; 4; 7; 8], информационные сервисы с различными категориями пользователей [6], а также любые социальные системы с клиентами разного типа, например, больницы [10—13]. В качестве примера последних можно привести исследования [2; 5], в которых изучается эффективность алгоритмов распределения мест в очереди на пересадку органов для пациентов в зависимости от тяжести их заболевания. Кроме того, приоритетные системы используются для предоставления пользователям приоритетного входа в систему при работе с различными сервисами. Так, в статье [6] приведён анализ влияния приоритетов на загруженность веб-сервисов, время проведения транзакции и другие характеристики. Кроме того, теория массового обслуживания активно применяется при исследовании различных распределенных систем, например, для исследования характеристик производительности систем для распределенных вычислений, а также для исследования характеристик производительности интернет-сервисов [14].

Как известно, трафик в современных компьютерных сетях является коррелированным [15; 16], и для его моделирования необходимо использовать марковские входные потоки MAP (Markovian Arrival Process) [17—22]. Естественным обобщением MAP-потоков на случай приоритетного неоднородного трафика являются маркированные марковские входные потоки (Marked MAP, MMAP) [17—19; 21; 22], которые позволяют описывать коррелированные поступления заявок для произвольного числа классов приоритетов.

Исследование характеристик производительности приоритетных систем массового обслуживания является темой многих работ. В статье [23] исследуется двухприоритетная система массового обслуживания вида MAP/PH/1 с дискретным временем. Получено стационарное распределение числа приоритетных и неприоритетных заявок в системе. Похожее исследование было проведено в работе [24]. В работе [5] рассматривается приоритетная система с произвольным числом приоритетов, входным MMAP-потоком и PH-распре-делением времени обслуживания. Отличительной особенностью данной статьи является то, что заявки могут изменять свой приоритет, находясь в очереди. В данной статье получены условия эргодичности системы, а также оценки характеристик производительности системы. Из-за общности и большой сложности системы стационарное распределение и точные формулы для вычисления характеристик производительности получить не удалось. В исследовании [25] получено условие существования стационарного режима для двухприоритет-ной системы вида MAP/PH/1. В статье [26] рассматривается двухприоритетная система MMAP/PH/N. Приоритетные заявки в этой работе обладают абсолютным приоритетом: в случае, когда все обслуживающие приборы заняты неприоритетными заявками, и поступает приоритетная заявка, одна из неприоритетных заявок прекращает обслуживание, и ее место на обслуживающем приборе занимает поступившая приоритетная заявка. Кроме того, в случае выбивания заявки или прихода неприоритетной заявки в момент, когда все приборы заняты, она попадает в ожидающие обслуживания заявки и попробует через экспоненциально распределенное время попасть на обслуживание (retrail customer). В работе найдено стационарное распределение, получены формулы для характеристик производительности системы. В статье [27] рассматривается система MAP + MAP/M2/N/to. Здесь также приоритетные заявки обладают абсолютным приоритетом, а неприоритетные заявки могут возвращаться на обслуживание через экспоненциально распределенное время. Найдено стационарное распределение и формулы для характеристик производительности системы. В работе [28] получено стационарное распределение и формулы для характеристик производительности системы, являющейся обобщением системы, описанной в статье [26]. Здесь рассматривается система MMAP/PH/N в предположении, что PH-распределения для неприоритетных заявок могут быть разными. Статья [29] отличается от [26] тем, что рассматривается случайное воздействие, из-за которого обслуживающие приборы становятся временно

недоступными. Система с двумя классами приоритетов была исследована в статье [30]. Двухприоритетная система состоит из двух подсистем, в каждую из которых заявки поступают в МАР-потоке, причем для приоритетных заявок предусмотрен буфер для хранения в случае, когда все приборы заняты, а для неприоритетных нет. В работе приведен алгоритм построения генератора цепи Маркова, получены формулы для различных характеристик производительности системы. Двухприоритетная система была описана в [31], получено стационарное распределение и формулы для вычисления стационарных характеристик производительности системы.

В статье [32] анализируется размер очереди приоритетной системы ММАР/МАР/1. Исследование условий стационарного режима многолинейной СМО с входящим ММАР-потоком представлено в статье [5]. Однако в ней отсутствует описание алгоритма расчёта стационарных вероятностей состояний и характеристик производительности. В недавних работах [31; 33] была исследована проблема поиска стационарного решения для приоритетных систем с входным ММАР-потоком для случая одного обслуживающего прибора. В статье [31] исследуется очередь с относительной приоритизацией, в статье [33] - с абсолютной.

В статье [34] рассмотрена сложная многолинейная СМО с входящим ММАР-потоком с двумя классами приоритетов и отсутствием буфера. Настоящая глава является развитием и обобщением этой статьи. Принципиальным отличием данного исследования от [34] является наличие буфера конечного размера и произвольного числа классов заявок. Такое обобщение, с одной стороны, значительно усложняет математический анализ даже для двух классов приоритетов, но, с другой стороны, расширяет область практического применения рассматриваемой модели. В данной главе приведена постановка задачи исследования, описана СМО вида ММАР/РЫ/К/Я. В процессе исследования СМО показано, что размерность состояний цепи Маркова, описывающей состояние системы, экспоненциально зависит от ее параметров. В связи с этим поиск стационарного состояния системы в общем виде - сложная задача. В разделе приводится алгоритм нахождения стационарного состояния и вычисления стационарных характеристик производительности СМО для случая двухпри-оритетной системы.

1.2 MMAP-поток и PH-распределение

Для задания и исследования коррелированного трафика в теории очередей используется MAP-поток. MAP-поток описывает трафик, в котором все поступающие заявки одинакового типа. MMAP является обобщением MAP-потока. В MMAP-потоке заявки различаются, в отличие от MAP. MAP-поток является частным случаем MMAP, когда в потоке предусмотрены заявки только одного приоритета. Рассмотрим подробнее, как определяется MMAP-поток.

Заявки разных приоритетов поступают в MMAP-потоке под управлением неприводимой цепи Маркова с непрерывным временем Vt, t ^ 0, которая принимает значения на множестве {0,1,2,..., W}. Процесс V пребывает в состоянии v в течение экспоненциально распределенного времени с параметром AV,

у = 0,W, после чего с вероятностью рк(у,у1) переходит в состояние у', и генерируется заявка к-го типа, к € {1,2,... ,К}, или, с вероятностью р0(у,у'), цепь переходит в состояние у' без генерации заявки, причем р0(у,у) = 0. Процесс у^

называется управляющим процессом ММАР-потока. Для указанных вероятно-

к ш _

стей выполняются естественные ограничения: ^ р^(у,у') = 1, у,у' = 0,Ж.

к= 1 у'=0

Таким образом, ММАР-поток задается:

— размерностью пространства состояний управляющего процесса W + 1;

— числом приоритетов К;

— интенсивностями времен пребывания управляющего процесса в соответствующих состояниях Ау, V = 0,W;

- вероятностями переходов р(у,у'), к = 1,К, у,у' = 0, W. Всю информацию о ММАР-потоке удобно хранить в виде набора матриц Иь, к = 1,К, порядка (Ж + 1) х (Ж + 1), элементы которых определяются как:

(Dk)vy = \vPk(V,V), v,V = 0,W,k = 1,K, (1.1)

{

(A,)v v = { -av, v =v' = 0,^_ (1.2)

AVp0(v,v'), v = v',v,v' = 0, W.

Элементами матриц Д^, к = 1,К, являются интенсивности переходов процесса у^, сопровождающиеся генерацией заявки к-го типа. Аналогичный смысл имеют недиагональные элементы матрицы И0, а диагональные элементы этой

матрицы - взятые с противоположным знаком интенсивности выхода процесса ■у^ из соответствующих состояний.

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

Матрицы В к, к = 1,К можно задавать их матричной производящей к

функцией В(х) = Е Вкхк, < 1. Отметим, что значение этой функции

к=0

в точке ^ = 1 — матрица ^(1) является инфинитезимальным генератором управляющего процесса ^, Ь ^ 0. Стационарное распределение этого процесса, представленное в виде вектора-строки 0, определяется как решение системы линейных алгебраических уравнений 0^(1) = 0, 0е = 1. Здесь и далее е -вектор-столбец, состоящий из единиц.

Интенсивность Лк поступления заявок к-го типа в ММАР-потоке задается формулой

Лк = 0Рке, к = 1,К, (1.3)

а суммарная интенсивность поступления заявок, Л, по формуле

к

Л = 0 ^ Вке. (1.4)

к=1

Дисперсия Ук длин интервалов между моментами поступления групп заявок к-го типа вычисляется по формуле

20(-Д> - Е В/ )-1е „

у{к) =---Л ,к = т;к. (1.5)

Л к Л к

Коэффициент корреляции €¿>1 длин двух соседних интервалов между моментами поступления групп заявок к-го типа вычисляется по формуле

к

Л к) =

г0(До + Е А)

/=1,1=к

Л к

1

е

Вк (Во +

к

£ а)

=1,/=к

1

е

(лк)

V

1

(1.6)

к = 1.К.

Более подробное описание ММАР можно найти в [5]. Отметим, что стационарный пуассоновский поток является частным случаем ММАР-потока при ЦТ = 0, К = 1, ^0 = -А, А = А.

В качестве примера рассмотрим переходы в ММАР-потоке, где число состояний управляющего процесса равно }¥ = 4, число классов приоритетов К=2, матрицы заданы следующим образом:

=

( -1 0.3 0 0 ^ 0 -2 0 1 0 0-30

V

00

4

/

=

0 0.2 0 0

0 0 0.3 0

1 0 0 1

V

0 2 0 0

Г>2 =

^ 0 0 0 0.5 ^

0 0 0.7 0

0 0 1 0

0 0 0 0

V

/

/

Рисунок 1.1 — Схема переходов в ММАР-потоке с генерацией заявки разных

типов

Для задания процесса обслуживания в теории массового обслуживания, как правило, используют РН-распределение. РН-распределение задается парой (в к ). Здесь в к-вектор-строка порядка М^, а -квадратная матрица порядка М^. Заданное время обслуживания интерпретируется как время, за которое некоторая управляющая цепь Маркова I ^ 0, с пространством

состояний {1,..., М^, М^ + 1} достигнет единственного поглощающего состо-

(к)

яния Мк + 1. Переходы цепи т\ , I ^ 0 в пространстве несущественных

состояний {1,... ,Мк} задаются субгенератором Зк, а интенсивности переходов в поглощающее состояние задаются вектором #0к) = —Зке. В момент начала обслуживания состояние процесса к), £ ^ 0 выбирается из пространства состояний {1,... ,Мк} на основании вероятностного вектора-строки вк. Интенсивности обслуживания задаются как (к = — (вк^к-1 е)—1.

Для примера рассмотрим пример РН-распределения размерности М = 3, где вектор начального распределения в = (2,3,6) и матрица £ равны:

S =

( -2 1 0 \

1

V 1

-3 2 0 4/

; в

'О i

3

UZ

Рисунок 1.2 — Схема переходов в PH-процессе

1.3 Постановка задачи

Рассматривается N -линейная система массового обслуживания с буфером размера R (рис. 1.3).

В общем случае заявки разных типов отличаются приоритетами и параметрами PH-распределения времени обслуживания. Более подробно эти отличия будут описаны ниже. Полагаем, что все обслуживающие приборы одинаковы и независимы друг от друга. Время обслуживания любым прибором заявки к-го (к = 1,..,^) типа имеет фазовое распределение (P^-Phase type distribution).

N обслуживающих приборов

( щ ~РЯ(5Ь)81) V

О

£ ~ мм ар

К классов приоритетов

2 2 2 1 1

1._

Емкость буфера R

('щ ~ РЯ(52,/32) >

Завершение обслуживания

Рисунок 1.3 — Система массового обслуживания вида MMAP/PH/N/R с приоритетным обслуживанием

Предполагаем, что заявки типа к' < к, к,к' = 1,К обладают относительным приоритетом. Это означает, что более приоритетные заявки стоят в буфере впереди всех менее приоритетных заявок. Поступающая заявка ти-

па к', заставшая все приборы занятыми и в очереди г, г = 0,Я — 1, заявок,

(к')

с вероятностью qi становится впереди всех неприоритетных заявок типов (к = к' + 1, к' + 2,..., К) и в конце очереди приоритетных заявок типов к = 1, 2,... ,к'. С вероятностью 1 — ) новая заявка решает не присоединяться к очереди и уходит из системы навсегда. Если заявка любого типа, поступающая в систему, застает систему полностью занятой, то она покидает систему навсегда. Для упрощения записи, в случае К = 2 типов заявок, будем обозначать вероятности присоединения к очереди длины % приоритетных заявок класса к = 1 как qi = д(1), а неприоритетных заявок класса к = 2 как = д(2). Целью является расчет стационарных вероятностей системы и характеристик производительности, включая вероятность потери заявки и время отклика системы.

1.4 Система ММАР/РН/МуК с двумя классами приоритетов

1.4.1 Цепь Маркова, описывающая состояние системы

Пусть в момент времени Ь:

— ц - число заявок в буфере, ц = 0,Я;

— кг - число приоритетных заявок в буфере, кг = 0,^;

— щ - число занятых приборов, щ = 0,А;

— - число приборов, занятых обслуживанием приоритетных заявок, =

0,щ;

— ) - число приборов, обслуживающих приоритетные заявки на фазе

(1) (т[1]) й- (!) ТТТ

т\ , щ ' = 0,гг, ту = 1,м1;

— п) - число приборов, обслуживающих неприоритетные заявки на

1 (2) ~(т[2)) - (2) Т1\Т

фазе пц , щ ' = 0, щ — гг, ту = 1,м2;

— V - состояние управляющего процесса ММ АР, V = 0^. Процесс изменения состояний системы описывается регулярной неприводимой цепью Маркова с непрерывным временем:

ь = {(чМ,п ,щ, vt ,п!1),п12),...,п1М1),п !!),п 12),...,п Г2) },* ^ 0, (1.7)

и пространством состояний:

^ = {(¿,п,г,У,П(1),п(2),. . . , п(М1),п (1),п (2),...,п(М)),

г = 0, п = 0 Д, г = 0,п, V = 0,Ж г(т) = 0Д, т = 1Ж, п(т) = 0, п — г, т = 1^} У (1.8)

{(¿,^,П,Г,У,П(1),П(2), . . . , п(М1),п (1),п(2),... ,п( 2)), (1.9)

г = 1,Д,£ = 0,г, п = А, г = 0,п, V = 0№,п(т( 1)) = 0,г,

Список литературы диссертационного исследования кандидат наук Соколов Александр Михайлович, 2024 год

А // »

Y

/д ш'

V Г л 1

л-' У

V t—* J_3

/А V Jj

. У/ -X-»г-^Т Л

< и4=< м г-<

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Число обработчиков

3.00 2.75 2.50 2.25 2.00

I 1.75

CD

£1-50 1.25 1.00 0.75 0.50 0.25

1 3 5 7 9 11 13 15 Число обработчиков

« Selectel • Yandex Cloud ▼ VK Cloud Сервер

Выполнение docker-контейнера

Выполнение подзадачи без контейнера

Разность

Рисунок 3.21 — Среднее время выполнения подзадачи от числа обработчиков в

системе

Интересный эффект при проведении эксперимента наблюдался при проведении эксперимента на серверах Yandex Cloud. На рис. 3.22 показано среднее время выполнения подзадачи в зависимости от числа обработчиков в системе. Без привязки обработчиков к ядрам время выполнения подзадачи начинает расти линейно, начиная с 4 рабочих, хотя число виртуальных ядер в систе-

ме равно 8, и рост должен начаться, когда число обработчиков равно числу ядер в системе.

60 55

о50

гг-45

140

0)

I-35

30 25 20 15

Рисунок 3.22 — Среднее время выполнения подзадачи на серверах Yandex Cloud в зависимости от числа обработчиков с привязкой и без привязки обработчиков

к ядрам

Распределение процессорного времени между обработчиками на

разных платформах

В предыдущем подразделе было показано, что время выполнения задачи и подзадачи зависит от выбранной платформы для выполнения задачи. Время выполнения задачи зависит от числа ядер. Временные затраты на накладные расходы зависят от архитектуры виртуализации и работы гипервизора в системе. Чтобы показать различие работы гипервизора на различных платформах, мы провели эксперимент, в котором на платформе запускалось 4 параллельных процесса. В каждом процессе происходил численный расчет - вычисление числа Фибоначчи на С++. В процессе выполнения задач отслеживалось, какое ядро занимает каждый процесс. Для этого была написана простая программа, запускающая набор процессов, в каждом из которых выполняется расчет числа Фибоначчи, а в отдельном процессе параллельно, каждые 200 мс, считываются данные из файлов /proc/cpuinfo, /proc/stat и /ргос/<pid>/stat.

Ha, рис. 3.23 показаны временные диаграммы и гистограммы занятости каждого из ядер для различных платформ: Yandex Cloud, VK Cloud, Selectel

Yandex Cloud

UCO 1 l\ л^р Yandex Cloud с привязкой к ядра aivi

М

____

i t л |___

/

/

6 7 8 9 10 11 12 13 14 15 16 Число обработчиков

и рабочая станция. Из графиков видно, что на платформе Yandex Cloud происходило больше всего переключений для процессов между ядрами. Причем для одного процесса происходило переключение только между соседними виртуальными ядрами. В результате все ядра были заняты примерно одинаковое время. Платформы VK Cloud и Selectel переключали процессы реже, здесь более выражены ядра, на которых происходили вычисления. На рабочей станции были задействованы 4 ядра, на временной диаграмме для процессов наблюдается четыре прямых линии. Стоит отметить, что при привязке процессов к ядрам скачков процессов между ядрами не наблюдалось, каждый процесс выполнялся на отдельном ядре без скачков

Рисунок 3.23 — Распределение процессов по ядрам при параллельном выполнении 4 задач на различных платформах

Приоритизация задач

Для исследования применения приоритетов мы провели численный эксперимент, в котором в систему приходили задачи двух видов: приоритетные (HP - High Priority) и неприоритетные (LP - Low Priority). В эксперименте изучалась эффективность применения разных стратегий приоритизации. Каждая задача содержит 100 подзадач. В эксперименте мы использовали рабочую станцию с процессором Intel Core i7-9700K, имеющим 8 ядер и не поддерживающим hyper-threading. В качестве подзадачи использовалось вычисление числа Фибоначчи, число итераций и вычисляемое число подобраны так, чтобы вычисление занимало порядка 10 секунд (реализация на C++). Можно посчитать, что время выполнения 50 задач на 8 рабочих будет равно [50] =7 - число итераций запуска обработчиков. Общее время равно произведению числа итераций запуска обработчиков на время выполнения одной подзадачи: 7 х 10 = 70 секунд. Приоритетные задачи поступают с интенсивностью одна в две минуты, а неприоритетные задачи поступают с интенсивностью одна в полторы минуты.

Таблица 11 — Среднее время вычисления подзадач для разных стратегий при-оритизации

Тип приоритизации Время выполнения задачи, с Время до начала выполнения первой подзадачи, с

HP LP HP LP

FIFO 526 589 446 501

PRIORITY FIFO 98 844 12 752

UNIFORM 1166 1159 8 12

PRIORITY UNIFORM 182 1542 5 84

В табл. 11 приведены метрики для случая, когда каждая задача имеет постоянное время выполнения. Наиболее эффективной стратегией для выполнения приоритетных задач является PRIORITY FIFO, нахождение задачи в системе при таком режиме приоритизации минимально — 98 секунд. Стратегия PRIORITY UNIFORM немного уступает PRIORITY FIFO во времени нахождения в системе задачи - 182 секунды, но показывает лучшее время до начала

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

3.5 Заключение

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

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

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

3. Получены теоретические и экспериментальные оценки эффективности применения системы для потоковых вычислений.

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

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

Результаты исследования, представленные в этой главе, были опубликованы в работах [84; 111—118]

Глава 4. Исследование вычислительных систем с приоритетным

трафиком

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

Существует множество технологий и алгоритмов балансировки нагрузки. В статье [119] исследуется эффективность различных алгоритмов балансировки при использовании технологии HaProxy. Авторы статьи [120] исследуют эффективность применения системы балансировки HaProxy при DoS атаках. Эксперименты проводились на различных платформах с различными операционными системами, включая Linux и Windows. В статье [14] предлагается динамический алгоритм балансировки для оценки загрузки сервера на основе загрузки CPU, пропускной способности канала связи между балансировщиком и сервером и др. Показана эффективность алгоритма по сравнению с классическим алгоритмом Weighted Round-robin. В статьях [121—123] исследуются эффективность различных алгоритмов балансировки: Round-robin, Least Connections и др.

Множество исследований посвящено сравнению характеристик производительности различных балансировщиков нагрузки. Авторы статьи [121] сравнивают производительность технологий HaProxy и Nginx. Сравнивается пропускная способность балансировщиков, время отклика и другие характеристики производительности. Также в данной работе исследуется эффективность использования системы балансировки по сравнению с системой без балансировщика нагрузки. В статье [124] авторы исследовали эффективность балансировки нагрузки в SDN-сетях.

Для исследования эффективности балансировщиков нагрузки и реализации алгоритмов для динамического распределения нагрузки между серверами [125—127] применяется теория очередей. Например, в статье [125] предложен алгоритм балансировки, в котором для каждого сервера задается средняя интенсивность обслуживания интенсивность поступления запросов Л, а также максимальный размер очереди запросов на каждом сервере. Исходя из этих параметров, предложена формула для вычисления весов для каждого сервера при применении алгоритма балансировки Weighted Round-robin. Аналитическая модель для исследования балансировки нагрузки приведена в статье [127]. В статье предложено, что балансировщик нагрузки имеет бесконечную очередь. Балансировщик перенаправляет запросы на сервер, где они попадает на обслуживание или в очередь. Сервер в терминах Кендалла обозначается М/М/1/К. В систему поступает Пуассоновский поток заявок, время обслуживания распределено экспоненциально, а максимальное число заявок в очереди равно K. В статье представлены различные схемы балансировки и соответствующие им цепи Маркова, приведены формулы для вычисления стационарных характеристик производительности системы.

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

ма. В статье [129] показано применение алгоритмов машинного обучения для организации асинхронной очереди задач Celery и распределения задач между обработчиками. Показана эффективность применения алгоритмов по сравнению с традиционными методами. Показано, что применение данного алгоритма улучшает производительность и эффективность применения системы на 70%. В работе [130] с помощью методов теории очередей и методов имитационного моделирования подбирается оптимальное число приборов обслуживания для асинхронной очереди с произвольным входным потоком. В терминах Кендалла СМО обозначается как G/G/k. Стационарные характеристики производительности системы с асинхронной очередью задач с использованием технологии Celery были исследованы в статье [131]. Получена зависимость времени нахождения задачи в очереди от числа обработчиков задач в системе.

В данной главе исследуется применимость СМО вида MMAP/PH/N/R и разработанной имитационной модели для получения оценок стационарных характеристик производительности системы с балансировкой сетевой нагрузки и приоритизацией трафика, а также для систем с распределенной очередью задач. В данной главе проведены численные эксперименты, показывающие возможность применения разработанных моделей для оценки стационарных характеристик производительности систем балансировки сетевой нагрузки HaProxy и технологии для организации распределенной очереди задач Celery.

4.1 Сетевая балансировка нагрузки

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

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

— уменьшение времени отклика системы - времени от отправления запроса пользователем до получения им ответа;

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

— эффективное распределение ресурсов, при котором серверы получают примерно одинаковую нагрузку.

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

4.1.1 Виды балансировки сетевой нагрузки

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

Ь4 балансировка является наиболее простым методом для балансировки сетевой нагрузки. Данный вид балансировки называется Ь4, потому что балансировка происходит на транспортном уровне стека протоколов модели 081. В данном случае установка соединения и передача данных происходит следующим образом. Клиент устанавливает ТСР-соединение с балансировщиком, после чего балансировщик устанавливает ТСР-соединение с одним из серверов и проксирует данные от клиента к серверу. После завершения

Рисунок 4.1 — Система без балансировки нагрузки

TCP-сессии балансировщик-сервер балансировщик отправляет ответ в TCP-сессию клиент-балансировщик. Проксирование является легким и быстрым, поскольку осуществляется на транспортном уровне. Данный метод балансировки поддерживает множество функций, таких как: health checking (проверка работоспособности сервера), сокрытие внутренней сети, в которой осуществляется соединение балансировщик-сервер, организация очереди соединений для предотвращения перегрузки серверов, а также ограничение скорости соединений. Данный вид балансировки подходит для веб-приложений, работы с СУБД, например, Postgres, Redis и др.

Рисунок 4.2 — Схема системы с L4 балансировщиком

При использовании L7 метода балансировка происходит на 7 уровне OSI - уровне приложений. При таком способе балансировщик может принимать решение о маршрутизации на основе данных подключения. Например, ip адреса и порта источника, метаданных HTTP: заголовки, cookie, url и др. По сути

этот метод является надстройкой над Ь4 балансировкой. Решение о перенаправлении принимается не только на основе пары ¡р адрес - порт, а еще и НТТР-метаданных.

Рисунок 4.3 — Схема вычислительной системы с Ь7 балансировщиком сетевой

нагрузки

4.1.2 Методы балансировки сетевой нагрузки

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

простаивают. Алгоритм Round Robin это не учитывает и все равно отправляет запрос на первый сервер. Таким образом, алгоритм выбирает неоптимальный способ с точки зрения производительности и минимизации времени отклика системы. Существует несколько оптимизаций алгоритма: Weighted Round Robin и Dynamic Round Robin.

В алгоритме Weighted Round Robin каждому серверу в соответствие ставится некоторое число - весовой коэффициент. Чем больше пропускная способность сервера, тем больше должен быть его весовой коэффициент. В зависимости от величин весовых коэффициентов на сервер поступает соответствующее число запросов. Например, если веса для трех серверов равны 3,1,1, то на первый сервер в среднем поступает в три раза больше запросов, чем на второй и третий. В модификации алгоритма Dynamic Round Robin веса рассчитываются из текущей загрузки серверов.

Метод Least Connections учитывает число подключений на конкретный сервер и передает новое подключение серверу с наименьшим числом подключений в данный момент времени. Есть также улучшенная версия данного алгоритма Weighted Least Connections, которая учитывает не только число активных подключений, но и весовые коэффициенты серверов.

В алгоритме Sticky Sessions пользовательская сессия закрепляется за одним сервером. Перенаправление запроса на другой сервер возможно только в случае отказа закрепленного.

4.1.3 Балансировщик сетевой нагрузки HaProxy

Технологии HaProxy является одной из популярных технологий, использующихся для балансировки сетевой нагрузки. HaProxy используется во многих популярных крупных интернет-сервисах, например: Github, Stack Overflow, Reddit, Amazon Web Services и др. Помимо балансировки сетевой нагрузки технология HaProxy может выполнять многие функции, среди которых:

— обратный прокси-сервер: принимает HTTP-запросы из внешней сети и проксирует (ретранслирует) запросы серверам, как правило, расположенным во внутренней сети. Доступны режимы HTTP/l.x или HTTP/2;

— TCP прокси-сервер: принимает TCP-подключения и ретранслирует их на другой указанный адрес;

— защита от DDOS-атак;

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

Технология HaProxy построена на основе архитектуры с неблокирующим I/O операциями с многопоточным планировщиком. Архитектура оптимизирована для максимально быстрого перемещения данных с наименьшим возможным числом операций. HaProxy оптимизирует работу с кешем процессора, работая с одним подключением на одном ядре, без переключения. В основном вся нагрузка ложится на операционную систему. Так, например, при TCP-проксировании данных 15% времени тратится на работу HaProxy и 85% уходит на работу операционной системы: открытие / закрытие соединения, пересылка данных.

Для работы с HaProxy в качестве балансировщика нужен только конфигурационный файл. После запуска HaProxy непосредственно выполняет функции:

— принимает входящие подключения;

— периодически проверяет состояние серверов (health checks);

— обменивается информацией с другими балансировщиками, если они предусмотрены в системе.

1

2

3

4

5

6

7

8 9

10 11 12

13

14

Листинг 4.1: Пример конфигурационного файла HaProxy

def ault s

mode http

timeout client 10s timeout server 20s timeout http-request 10s log global

frontend frontend bind :80

default_backend webservers

backend webservers

server si 192.168. 110 . 100 : 80 check

server s2 192.168. 110 . 110 : 80 check

server s3 192.168. 110 . 120 : 80 check

Конфигурационный файл состоит из нескольких основных секций. Секция defaults - конфигурация по умолчанию, применяемая ко всем остальным секциям, объявленным в конфигурационном файле. Опция mode отвечает в каком режиме работает сервер, доступные значения: http и tcp. Опция timeout [объект] определяет тайм-аут для конкретного объекта, в данном примере для подключения клиента тайм-аут равен 10 секунд, для сервера тайм-аут равен 20 секунд, а для http-запроса равен 10 секунд. Тайм-аут для http-запроса -максимальное время, в течение которого сервер сохраняет соединение с клиентом. По истечении данного времени соединение обрывается. В секции frontend описывается конфигурация балансировщика. В примере указано, что балансировщик занял 80-ый порт, также указывается, к какой группе серверов будет осуществляться балансировка (будут перенаправляться запросы по мере освобождения ресурсов) и другие параметры. В примере в секции backend указаны серверы, между которыми осуществляется балансировка: указано три сервера и соответствующие им ip-адреса и порты.

4.1.4 Реализация очередей и приоритетов в HaProxy

Для защиты от переполнения памяти и, как следствие, падения системы в HaProxy предусмотрено ограничение на число подключений. Задать максимальное число подключений можно с помощью директивы maxconn.

1 defaults

2 maxconn 50000

Листинг 4.2: Пример настройки числа активных подключений в конфигурационном файле HaProxy

В приведенном примере максимальное число активных подключений равно 50000. При задании максимального числа подключений нужно учитывать вычислительные характеристики серверов, входящих в состав системы. Число активных подключений можно настраивать также в секциях frontend (балансировщик) и backend (серверы) в конфигурации HaProxy. Рассмотрим следующий листинг конфигурации:

1 defaults

2 maxconn 50000

4

5

6

7

8 9

10 11 12

Листинг 4.3: Пример настройки числа активных подключений балансировщика в конфигурационном файле HaProxy

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

backend web_servers

balance roundrobin timeout queue 30s

server si 192.168.110.10:80 maxconn 100 server s2 192.168.110.11:80 maxconn 30 server s3 192.168.110.12:80 maxconn 50

Листинг 4.4: Пример ограничения числа активных подключений к серверам

Помимо указания максимального числа одновременных подключений в конфигурации HaProxy можно указать максимальное время нахождения подключения в очереди при отказе/занятости серверов. Этот параметр задается директивой timeout queue, где указывается время в секундах. Подключение находится в очереди определенное время, после чего, в случае, когда все серверы заняты или отказали, клиенту возвращается ответ с кодом 503 (Service Unavailable).

# Конфигурация backend серверов backend web_servers

# Балансировка Round Robin balance roundrobin

acl is_checkout path_beg /checkout/

http-request set-priority-class int(1) if is_checkout

7 http- request set-priority -class int (2) if !is_checkout

8 timeout queue 30s

9 server si 192 .168.110.10: 80 maxconn 100

10 server s2 192 .168.110.11: 80 maxconn 30

11 server s3 192 .168.110.12: 80 maxconn 50

Листинг 4.5: Настройка приоритетного доступа в HaProxy

Начиная с HaProxy 1.9 появилась поддержка приоритизации трафика. Чтобы приоритизировать трафик в конфигурационном файле нужно прописать определенные правила, которые носят аббревиатуру ACL (Access Control Lists). ACL позволяют устанавливать правила для различных клиентов. Например, определять серверы, куда возможен доступ или переадресация трафика, определять приоритет клиента и другие. На примере листинга 4.5 видно, что здесь задается правило is_checkout: если путь начинается с /checkout/, то переменной присваивается значение true, иначе false. После этого запросу присваивается соответствующий приоритет. Стоит отметить, что приоритетные запросы находятся в очереди впереди неприоритетных запросов (относительная приори-тизация). Приоритетные запросы (клиенты) обслуживаются в первую очередь.

Из описания технологии видно, что схема балансировки сетевой нагрузки с использованием технологии HaProxy сложнее рассматриваемой в работе модели с приоритетными заявками из-за наличия большого числа конфигураций различных тайм-аутов: максимального времени установки соединения между клиентом и фронтендом, максимального времени ответа сервера, максимального времени нахождения запроса в очереди и др. Не учитывая данные конфигурации, система работает следующим образом. Фронтенд организует очередь соединений, упорядочивает их по времени создания или по приоритету. Число активных соединений задается директивой maxconn в части frontend конфигурационного файла. При описании бекенд серверов каждому серверу так же с помощью директивы maxconn можно указать число активных одновременных подключений.

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

Число параллельно

обрабатываемых запросов задается в конфигурации НаРгоху

Рисунок 4.4 — Схема балансировщика HaPгoxy

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

4.1.5 Численные результаты

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

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

1

2

3

4

5

6

7

8 9

10 11 12

13

14

15

16

17

18

19

20 21 22

23

24

25

26

27

28

29

30

31

32

Листинг 4.6: Конфигурационный файл HaProxy при проведении численного результата по исследованию применимости модели СМО с приоритетным обслуживанием заявок для исследования характеристик производительности системы с балансировкой нагрузки

Виртуальные машины для серверов и для балансировщика были арендованы в одном облаке (Yandex Cloud) для минимизации сетевых задержек

Рисунок 4.5 — Схема проведения эксперимента для исследования характеристик производительности балансировщика сетевой нагрузки HaPгoxy

(рис. 4.5). Для проведения эксперимента были арендованы четыре виртуальные машины с характеристиками: Intel Ice Lake, процессор Intel Xeon Gold 6338, тактовая частота процессора 2.00 Ггц, 2 Гб оперативной памяти. На каждой виртуальной машине запущен http-сервер, написанный на Python, принимающий GET-запросы для неприоритетных и приоритетных пользователей. Для всех запросов предполагалось, что время обработки запроса на сервере распределено экспоненциально. Для имитации обработки запроса на сервере выполнялась функция sleep(n), где п - число секунд, на которое останавливалась обработка запроса. Для генерации клиентского трафика использовался скрипт, написанный на Python с использованием библиотек asyncio, requests_async (для организации асинхронных запросов), а также библиотеки pyqumo (https://github.com/ipu69/pyqumo) для генерации временных интервалов между последовательными запросами. HaProxy «из коробки» осуществляет сбор Prometheus-метрик. Для агрегации и отображения статистики использовался сервис Grafana.

В эксперименте для балансировщика использовалась конфигурация 4.6, среднее время обработки приоритетного и неприоритетного запросов были распределены экспоненциально, среднее время обработки запросов на серве-

ре равнялось трем секундам (|ХрГ = \1ЩУГ = ц,). Каждый сервер максимально мог одновременно обрабатывать 30 запросов. На вход поступал ММАР-поток, интенсивность поступления приоритетных и неприоритетных запросов была одинакова \рг = \прг = Л. В рамках эксперимента мы исследовали зависимость стационарных характеристик производительности: время отклика для приоритетных и неприоритетных запросов, время нахождения запроса в очереди, а также число активных подключений в системе от коэффициента загрузки системы. Результаты сравнивались с характеристиками, полученными с помощью имитационной модели, описанной в главе 2.

0

^ о 2.995

2 О

н о.

2 л 2.990

1 "

О) О.

с 2.985

\

3.1

о а

г о с; о 5 о. н с о со к »

| о. 3.05 ££

100 200 300 400 Число сгенерированных запросов (тыс.)

дУ ►ч

/ *

1( )0 Ю 3( Ю 400

Число сгенерированных запросов (тыс.)

Рисунок 4.6 — Значение времени отклика для приоритетных и неприоритетных запросов в зависимости от числа сгенерированных запросов

8 3

о. т

05

00

0.2 0.4 0.6 0.8

тЙ

I . . ■ 4 ■ г

[ 1 [ I т.

0.2 0.4 0.6 0.8

Коэфф. загрузки

1.0

X

я ,

3! I

к

г

0> о.

СП

о 1.4

■1.0

(О

" 0.6 о.

аЗ 0.2

X

1

ту

3 г т т 1 Г 1 _ ТГ

^ 1 1 Г1

0 2 0 4 0 6 0 8 1.

I

у

Е I I ] Е-4— -чг*

0.2 0.4 0.6 0.8 1.0

Коэфф. загрузки

Моделирование ■ НаРгоху

Рисунок 4.7 — Сравнение характеристик производительности балансировщика НаРгоху с результатами вычисления с помощью имитационного моделирования для приоритетных и неприоритетных запросов

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

сгенерированных запросов. На рис. 4.6 показана зависимость времени отклика системы для приоритетных и неприоритетных запросов при коэффициенте загрузки равном р = 0.9. Как видно из графиков, необходимое минимальное число сгенерированных запросов для получения стационарных характеристик производительности равно 200 тысяч.

На рис. 4.7 показаны результаты эксперимента. Для получения значений характеристик производительности для каждого значения коэффициента загрузки число сгенерированных запросов равнялось 200 тыс. Для устранения систематических ошибок измерение для каждого значения производилось 5 раз с последующим усреднением результатов и вычислением погрешностей. Из рис. 4.7 видно, что результаты моделирования совпали с метриками, полученными из системы НаРгоху в пределах погрешности. Погрешность получения оценок характеристик производительности возрастает при возрастании значения коэффициента загрузки. Так, при р ^ 0.9 для времени отклика погрешность составляет примерно 10%, а для времени ожидания неприоритетных пакетов запросов около 15%). Для остальных характеристик погрешность составила не более 10%). На рис. 4.8 показано сравнение числа активных подключений балансировщика к серверам. Результаты, полученные с помощью имитационного моделирования, в пределах погрешности совпадают с метриками, полученными из тестового стенда системы.

Коэффициент загрузки Моделирование ■ $ ■ НаРгоху

Рисунок 4.8 — Сравнение числа подключений балансировщика НаРгоху с результатами вычисления с помощью имитационной модели для приоритетных и

неприоритетных запросов

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

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

Таблица 12 — Среднее время получения стационарных характеристик производительности для системы HaPгoxy

Метод р = 0.2 р = 0.4 р = 0.6 р = 0.8 р = 0.9

HaProxy сервер Имитационное моделирование 20 ч 10 с 12 ч 15 с 8 ч 24 с 6 ч 32 с 4 ч 38 с

4.2 Асинхронная очередь задач

Асинхронная очередь задач используется в вычислительных системах для обработки отложенных ресурсоемких задач, которые не предполагают мгновенного выполнения. Примерами таких задач являются: отправка электронной почты и push-уведомлений (все письма и уведомления поступают в очередь, где по мере освобождения серверов осуществляется отправка), вычисление фоновых задач, например, формирование отчетов за большой промежуток времени, периодическое обновление данных и другие задачи. К системам с асинхронной очередью задач можно отнести, в том числе, системы для потоковых вычислений, описанные в предыдущей главе. Как правило, в рамках вычислительной системы отводится один или несколько серверов, предполагающих выполнение некоторой программы. Кроме того, нередко задачи упорядочиваются по приоритету, например, отправка push-уведомления может быть менее приоритетна, чем отправка email-уведомления. Или в вычислительных системах одни задачи приоритетнее других. Для организации распределенных вычислительных систем существует множество библиотек и фреймворков, одним из которых является фреймворк Celery (https://docs.celeryq.dev/en/stable/ index.html).

4.2.1 Система для распределенных вычислений Celery

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

— брокер - очередь задач, в качестве которого чаще всего используются Redis или RabbitMQ;

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

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

Обработчики задач

Клиенты

Рисунок 4.9 — Схема асинхронной очереди задач

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

на NodeJS. Celery инициализируется экземпляром приложения, который предоставляет API для создания и управления задачами. Ниже приведен простой пример создания экземпляра приложения Celery. Все возможные для выполнения задачи помечаются декоратором @app.task. В примере ниже в качестве задач используются вычисление числа Фибоначчи рекурсивным методом без кэширования, а также вычисление факториала числа.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

В конструктор создания приложения app передается имя 'tasks', оно же назначается в качестве имени модуля, где находятся задачи для выполнения. Также в конструктор передается адрес брокера сообщений 'redis://localhost:6379/' (в данном примере в качестве брокера используется Redis, запущенный локально). Помимо Redis возможна интеграция с RabbitMQ, SQS и др. Все задачи выполняются на выделенных виртуальных машинах, на которых запущен обработчик. Чтобы запустить отдельный экземпляр обработчика задач, нужно выполнить команду в консоли:

1 celery -A tasks worker --concurrency = 1 --prefetch-multiplier = 1

Листинг 4.8: Запуск обработчика задач в Celery в консоли

В аргументах передается название модуля, где объявлены задачи для выполнения. Значение -concurrency=1 означает, что в рамках данного процесса

from celery import Celery

app = Celery('tasks', broker='redis://localhost:6379')

Листинг 4.7: Пример инициализации приложения Celery

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

1

2 3

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

Для мониторинга состояния системы в Celery используется open-source решение Flower (документация доступна по ссылке: https://flower. readthedocs.io/en/latest/index.html). Flower предоставляет информацию о состоянии системы, включая метрики: статус обработчика, статусы задач, число сообщений в брокере и др. Для удобства использования предусмотрен пользовательский интерфейс и REST API. Устанавливается Flower с помощью pip командой:

1 pip install flower

Для запуска из консоли используется команда:

1 celery -A tasks flower --port=5555

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

from tasks import fib f ib.apply_async(args = [10])

Листинг 4.9: Пример запуска задачи в Celery

Задачи и результаты выполнения передаются через очередь

1. from tasks import fib

2. fib.apply_async(args=[i7me_to_s/eep])

vm1

Генератор задач

f* PyQumo

m

Redis

£ ~ MM АР

Ш. Flower

> PromQL

Grafana Сбор статистики

port 6379

vm2

Ш iCJ

обработчики vm3

lù LCJ

обработчики

vm4

С LC

обработчики

vm5

lCJ

обработчики

На каждой виртуальной машине запускается несколько обработчиков

celery -A tasks worker -c $workers_count --prefetch-count=1

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

7/1 ~ PH(Si,Pi)

m ~ PH(S2,/32)

Рисунок 4.10 — Схема стенда для исследования характеристик производительности системы Celery

4.2.2 Численные результаты

В работе проведен численный эксперимент по исследованию применимости модели приоритетной системы для расчета характеристик производительности Celery. С этой целью был собран стенд, показанный на рис. 4.10. Стенд состоял из четырех виртуальных машин, на каждой из которых запускалось до двух обработчиков включительно. Отдельная виртуальная машина отводилась для организации очереди задач. В качестве брокера сообщений использовался Redis. На этой же виртуальной машине был запущен генератор задач. Задачи поступают в MMAP-потоке, где предусмотрены приоритетные и неприоритетные задачи. Для приоритетных и неприоритетных задач заданы интенсивности поступления \рг и \прг соответственно. При этом интенсивность поступления приоритетных и неприоритетных заявок была одинакова. Время выполнения всех задач распределено экспоненциально с интенсивностью ц. Также для сбора и обработки статистики состояния системы использовались Flower и Prometheus/Grafana Для имитации выполнения сложной задачи использовалось обычное засыпание программы:

@app.task

def sleep(n, creation_date ) :

time.sleep(n)

return { sleep': n, 'creation_date ' : creation_date}

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

Характеристики производительности системы в ходе эксперимента были получены при следующих параметрах системы: интенсивность поступления приоритетных и неприоритетных задач: \рг = \прг = 3с-1; интенсивность обслуживания приоритетных и неприоритетных задач = 1с-1. Число обработчиков менялось в интервале от 3 до 8. Для каждого значения числа обработчиков для измерения характеристик производительности было сгенерировано порядка 150 тыс. задач. Результаты эксперимента приведены на рис. 4.11.

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

особенностями работы системы Celery и Redis. Также погрешность может быть связана с методом измерения и слишком низкой частотой запроса метрик из системы Flower.

5 6

Число обработчиков

5 6

Число обработчиков

- Монте-Карло —»- Celery

Рисунок 4.11 — Сравнение характеристик производительности системы Celery с результатами вычисления с помощью имитационного моделирования для приоритетных и неприоритетных задач

100 200 300 400 500 Число сгенерированных задач (тыс.)

А ч Л i \ .А.

V 0 1С W у Ю 20 D 3( Ю 4( VV Ю 500

Число сгенерированных задач (тыс.)

Рисунок 4.12 — Значение времени отклика для приоритетных и неприоритетных задач в зависимости от числа сгенерированных задач