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

В работе построена объектная имитационная модель пула потоков, за
основу которой взята реализация, используемая в СУБД MySQL, MariaDB и Percona
Server. Описаны входные потоки модели и примеры их распределений. Приведены
результаты апробации модели, согласующиеся с известными паттернами зависимости
производительности от входных параметров. Практическое значение модель имеет как
инструмент статического и динамического выявления наиболее значимых для
производительности параметров и их оптимального выбора.

Ссылка на оригинал. http://simulation.su/uploads/files/default/2021-immod-412-420.pdf

Введение

Имитационное моделирование используется для эффективного принятия решений не
только в прикладных предметных областях, таких как различные отрасли народного
хозяйства и военное дело, но также и в проектах, связанных с разработкой
программного обеспечения и проектированием сложных IT-систем. Одной из таких
систем является пул потоков (трэдпул), активно применяемых в самых разнообразных
программных продуктах на протяжении последних примерно 25 лет. Данная технология
появилась как альтернатива концепции «одно соединение – один поток», т.к.
позволяет во многих случаях не только экономить ресурсы, но и повысить
производительность программного продукта в целом. Она заключается в
переиспользовании уже существующего потока для обработки следующей задачи.
Существует множество различных реализаций трэдпула, наиболее подробный обзор
которых приведен в ^[9]. По отдельным реализациям имеется большое количество
материалов. Так, один из первых трэдпулов для брокера объектных запросов CORBA
описан в ^[13], трэдпул для Android — в ^[1], для сервера приложений Oracle
GlassFish – в ^[10]. Поучительным примером эффективного использования модели
трэдпула в Python для решения сложной научной задачи является ^[23]. Трэдпул от
компании Microsoft для CLR описан в фундаментальном труде ^[16], а последняя
реализация доступна в ^[20]. Собственное расширение модели потоков Java в виде
трэдпула разработано в отечественном академическом исследовании ^[21]. Большое
внимание уделяют этому вопросу также разработчики известных СУБД, в частности,
MySQL ^[14], MariaDB^[18], Percona Server^[12]. Особенностями подхода, использованного в
этих реализациях, является разделение всего трэдпула на группы потоков, где
каждая группа имеет свои упорядоченные по приоритетам очереди запросов на
обслуживание и свои подгруппы активных, ожидающих и свободных потоков; отдельный
поток-таймер в таком трэдпуле отслеживает застрявшие потоки и запросы. Забегая
вперед, отметим, что модель именно такой разновидности трэдпула рассматривается
в данной работе.

Все трэдпулы характеризуются большим количеством параметров, которые назначаются
проектировщиком и оказывают влияние на итоговую эффективность трэдпула. Основным
из них является размер трэдпула, который задает ширину параллелизма
(concurrency level), в качестве которой, например, для упомянутых выше
СУБД-реализаций является количество групп. Этот выбор определяется множеством
факторов, такими как общая нагрузка на сервер и профиль этой нагрузки
(workload). Так, для CPU-ориентированной (CPU-bound) нагрузки и нагрузки,
ориентированной на ввод-вывод (IO-bound), даже при одном и том же количестве
одновременных соединений оптимальные значения размера трэдпула могут коренным
образом различаться. Именно поэтому большое число работ содержит в том или ином
виде рекомендации, как же выбирать этот параметр. Назначать его следует, подстраивая
под меняющуюся нагрузку. Делать это можно как из общих соображений, не отслеживая изменение
произвоидельности и не пытаясь ее оптимизировать, так и с учетом ее изменения. Первый подход
рассмотрен в работах ^{[1][7][8][10][11]}, где
приведены различные вариации формул, опирающихся на доступное число процессоров,
среднее время обслуживания запроса на CPU и среднее время простоя CPU из-за
ввода-вывода, а также на известный в теории очередей закон Литтла. Что же
касается алгоритмов с оптимизацией производительности, то здесь наибольших результатов
добилась Microsoft. В получивших широкую известность работах ^[5][6] рассмотрено
применение известного в теории метода HillClimbing для оптимизации размера
трэдпула, практические же результаты этого применения описаны в ^[19]. В ^[4]
описана, а в ^[20] реализована вариация HillClimbing-подхода, основанная не на
вычислении градиента, а на преобразованиях Фурье, как обладающая большей
устойчивостью к случайным воздействиям. Другие теоретические подходы к решению
задачи динамического выбора размера трэдпула предложены в ^[9] и ^[17]. Кроме
того, ^[17], опубликованная в 2021 году, содержит полную и актуальную
библиографию вопроса.

Вместе с тем, дать более полное и глубокое представление о том, как же работает
такая сложная система как трэдпул, может помочь имитационная модель. Итоговая
производительность (выраженная, например, в среднем числе обслуженных запросов в
единицу времени) зависит не только от размера трэдпула, но и от других
параметров. Чтобы установить значимость их влияния требуется большое количество
длительных и дорогих натурных экспериментов на рабочих серверах, а хорошо
спроектированная имитационная модель позволит сделать это гораздо быстрее,
собственно, это и есть ее основное достоинство для любых задач. Этот подход к
исследованию трэдпула на данный момент апробирован еще довольно слабо. Можно
отметить работу ^[2] (где использован специфический и малодоступный
инструментарий) и недавнюю работу украинских специалистов ^[15], где применены
стохастические сети Петри. Подход к моделированию и оптимизации трэдпула с
помощью сетей Петри используется также в ^[22]. В данной работе предлагается
имитационная модель трэдпула, где за основу моделируемой системы взята
реализация, описанная в ^[12]. Сама модель реализована на языке C++ с помощью
схемы, описанной в ^[24], позволяющей гибко учесть все алгоритмические нюансы
системы в полном объеме. В разделе II описан сам трэдпул, в разделе III –
архитектура предложенной модели, в разделе IV – некоторые результаты ее
валидации, в разделе V – выводы и рекомендации по ее применению.

Описание моделируемого трэдпула

Если опустить вторичные детали, граф вызовов функций трэдпула выглядит так (рис.
1):

Рис. 1. Граф вызовов функций трэдпула

где обозначения соответствуют следующим функциям (Таблица 1):

Таблица 1. Описание функций трэдпула.

Описание имитационной модели

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

• Входной поток соединений – распределение интервалов времени между вызовами
  функции add_connection.

  
  

• Длительность создания нового потока — тайминг для функции create_worker.

  
  

• Длительность одного раунда активности потока: от начала обработки запроса до
  первого вызова wait_begin, либо между вызовами wait_end и wait_begin,
  либо между wait_end и завершением обработки запроса.

  
  

• Длительность одного раунда простоя CPU: между вызовами wait_begin и
  wait_end.

  
  

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

  
  

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

  
  

Выходные значения модели – среднее число обслуженных запросов в секунду
(queries per second) и средняя длительность обслуживания запроса (latency).

Модель реализована на следующих предметных классах: Threadpool (синглетон),
Threadgroup, Connection, Thread, Timer(синглетон). Для экземпляров
класса Thread установлены состояния:

• creating – создание потока;

  
  

• active – обслуживание запроса;

  
  

• waiting – ожидание ввода-вывода;

  
  

• idle – простой потока, когда запрос обслужен, а новый еще не назначен;

  
  

• polling – в этом состоянии может находиться только поток, занятый
  поллингом (listener).

  
  

Для экземпляров класса Connection установлены состояния:

• in usual queue – соединение ожидает назначения потока в обычной очереди;

  
  

• in prio queue – соединение ожидает назначения потока в льготной очереди;

  
  

• threading – соединению назначен поток, запрос обслуживается;

  
  

• between – запрос обслужен, соединение ожидает выборки
  потоком-listener’ом.

  
  

Возможные переходы между состояниями показаны на рис. 2 и 3.

Параметрами, которыми исследователь может варьировать для их оптимизации, помимо
размера трэдпула (количества групп), являются следующие свойства класса
Threadgroup:

• oversubscribe – максимальное количество активных потоков в группе (по
  умолчанию – 3)

  
  

• queue_put_limit – создать новый поток внутри функции queue_put, если
  число активных потоков в группе меньше данного значения (по умолчанию – 0)

  
  

• create_thread_limit – не создавать поток в функции create_worker, если
  число активных потоков в группе превышает данное значение (по умолчанию – 1)

  
  

• listener_wake_limit – не будить idle-поток в потоке listener, если
  число активных потоков в группе превышает данное значение (по умолчанию – 0)

  
  

• listener_create_limit – не создавать новый поток в потоке listener, если
  число активных потоков в группе превышает данное значение (по умолчанию – 1).

  
  

Структура модели в виде графа взаимных вызовов методов классов приведена на
рис.4. Названия методов даны в таблице 2. Основной цикл модели выглядит так
(листинг 1).

Рис. 4. Структура имитационной модели

Таблица 2. Методы классов имитационной модели.

Листинг 1.

#define NUMBER_OF_TACTS 60000000 /*in mcs */ 
int main() {
  Threadpool *tpl = Threadpool::getInstance();
  Timer *tmr = Timer::getInstance();
   /*initialize random number generator*/
   srand((unsigned)time(0)); 
   for (long i = 0; i < NUMBER_OF_TACTS; i++) {
     Tpl->run();
     Tmr->run();
   }
   delete tpl;
   delete tmr;
   return 0;
}

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

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

Апробация модели и результаты

Валидность модели проверялась на контрольных примерах, где выходные результаты
модели (производительность и средняя длительность исполнения запроса)
сравнивались при той же моделируемой нагрузке с результатами, полученными на
реальном сервере с помощью известной утилиты тестирования производительности
MySQL sysbench. Модель показала расхождение с данными sysbench по обоим
выходным параметрам в пределах 2%. В этом разделе мы рассмотрим результаты
работы модели для двух принципиально различных профилей нагрузки – CPU-bound и
IO-bound. Вот примеры различия во входных данных.

На рис. 5 и 6 показаны гистограммы для собранных данных (около 1000 наблюдений)
для длительности одного раунда активности CPU в микросекундах. На рис. 7 и 8 показаны гистограммы
для длительности одного раунда ожидания CPU (иными словами, нахождения потока в
состоянии waiting). В первом случае (CPU-bound нагрузка) замеры производились для 1024
персистентных соединений с сервером при 32 ядрах, во втором случае (IO-bound нагрузка)
– 128 соединений с более трудоемкими запросами при 64 ядрах. Из рисунков видно,
что длительность ожидания ввиду гораздо более значительного удельного веса операций
ввода-вывода в запросах во втором случае значительно выше. Это означает бОльшее время
простоя процессора и, соответственно, возможность эффективной установки размера трэдпула
выше количества физических CPU.

На рис. 9 и 10 показаны зависимости производительности от размера трэдпула, построенные
с помощью имитационной модели. Продолжительность моделирования – 60 млн. тактов (микросекунд),
т.е. 1 минута, количество CPU 72. Эти графики хорошо соответствуют известным паттернам такой зависимости,
классифицированным, например, в ^[3]. Из графика видно, что при CPU-bound
нагрузке размер трэдпула выше числа CPU не дает эффекта – процессоры и так
постоянно загружены. Поэтому здесь основная цель модели – не столько
максимизировать выход, сколько минимизировать размер трэдпула. Для IO-bound
нагрузки картина иная – производительность продолжает расти и после значения 72,
достигая максимума при размере около 185, затем начинает снижаться из-за
конкуренции потоков на CPU и затрат на смену контекста процесса.

Заключение

Итак, где и каким образом можно применить построенную модель трэдпула – как для
описанной в этой работе реализации, так и для любой другой:

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

   
   

2. Выявление зависимости выходных величин от вида и параметров входных
   распределений.

   
   

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

   
   

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

   
   

5. Machine Learning: наполнение training data set, где представленному в количественном виде профилю нагрузки соответствует
   набор оптимальных параметров пула потоков. Этот data set далее можно будет использовать в реальной работе сервера СУБД для
   оптимизации пула потоков по собранному в run-time профилю.

   
   

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

Литература

1: Better performance through threading. — [developer.android.com/topic/performance/threads](https://developer.android.com/topic/performance/threads).

2: Boer F.S., Grabe I., Jaghoori M.M., Stam A., Yi W. Modeling and Analysis of
Thread-Pools in an Industrial Communication Platform. – ICFEM’09:
Proceedings of the 11-th International Conference on Formal Engineering
Methods, November 2009, pp.367-386.

3: Dongping X. Performance study and dynamic optimization design for threadpool
systems (2004). –
<https://digital.library.unt.edu/ark:/67531/metadc780878/m2/1/high_red_d/835380.pdf>

4: Fuentes E. Concurrency – Throttling Concurrency in the CLR 4.0 Threadpool
(September 2010). –
<https://docs.microsoft.com/en-us/archive/msdn-magazine/2010/September/concurrency-throttling-concurrency-in-the-clr-4-0-threadpool>

5: Hellerstein J.L., Morrison V., Eilebrecht E. Applying Control Theory in the
Real World. – ACM’SIGMETRICS Performance Evaluation Rev., Volume 37, Issue
3, 2009, pp. 38-42.

6: Hellerstein J.L., Morrison V., Eilebrecht E. Optimizing Concurrency Levels
in the .NET Threadpool. – FeBID Workshop 2008, Annapolis, MD USA.

7: Ilinchik A. How to set an ideal thread pool size (April 2019). –
<https://engineering.zalando.com/posts/2019/04/how-to-set-an-ideal-thread-pool-size.html>

8: Java Concurrency in lock optimization and optimization thread pool.
\-<https://programmersought.com/article/84012626442>

9: Nazeer S., Bahadur F. Prediction and Frequency Based Dynamic Thread Pool
System. – Int. J. of Comp. Sci. and Information Security, Vol. 14, No. 5,
May 2016, pp.299-308.

10: Oracle® GlassFish Server 3.1 Performance Tuning Guide. — <https://docs.oracle.com/cd/E18930_01/pdf/821-2431.pdf>

11: Pepperdine K. Tuning the Size of Your Thread Pool (May, 2013) –
<https://infoq.com/articles/Java-Thread-Pool-Performance-Tuning>

12: Percona Server for MySQL: Thread Pool. — <https://www.percona.com/doc/percona-server/5.7/performance/threadpool.html>

13: Pyarali I., Spivak M., Cytron R. Evaluating and Optimizing Thread Pool
Strategies for Real-Time CORBA. – ACM’SIGPLAN Notices, Volume 36, Issue 8,
August 2001, pp.214-222.

14: Ronstrom M. MySQL Thread Pool: Summary (October 2011). — <http://mikaelronstrom.blogspot.com/2011/10/mysql-thread-pool-summary.html>

15: Stetsenko I., Dyfuchyna O. Thread Pool Parameters Tuning Using Simulation. –
In book: Adv. in Comp. Sci. for Engineering and Education II (ed. Hu Z.),
Springer 2020, pp.78-89.

16: Terrell R. Concurrency in .NET: Modern patterns of concurrent and parallel
programming. – Simon and Schuster Publishing House, 2018, 568 pp.

17: Timm J. An OS-level adaptive thread pool scheme for I/O-heavy workloads. –
Master thesis, Delft University of Technology, 2021 (repository.tudelft.nl)

18: Thread Pool in MariaDB. – <https://mariadb.com/kb/en/thread-pool-in-mariadb>

19: Warren M. The CLR Thread Pool ‘Thread Injection’ Algorithm (April 2017). –
<https://codeproject.com/Articles/1182012/The-CLR-Thread-Pool-Thread-Injection-Algorithm>

20: <https://github.com/dotnet/coreclr/blob/master/src/vm/win32threadpool.cpp>

21: Акопян М.С. Расширение модели ParJava для случая кластеров с многоядерными
узлами. – Труды ИСП РАН, том 23, 2012.

22: Бабичев С.Л., Коньков К.А., Коньков А.К. Использование пула вычислительных
потоков со статическим планированием. – Труды МФТИ, т.4, № 3, 2012,
с.162-170.

23: Клячин В.А. Реализация параллельного алгоритма геометрического хеширования
на основе пакета NumPy и пула процессов. – Вестн. Волгогр. Гос. Ун-та, сер.
1, Мат.-Физ., 2015, выпуск 4 (29), с.13-23.

24: Труб И.И. Объектно-ориентированное моделирование на C++. –Питер, 2005. – 416
с.