О графике из книги «Проект Феникс»

ponomarev@corchestra.ru

@inponomarev

Иван Пономарёв, КУРС/МФТИ

Кто читал эту книжку?

phoenix

А кто знает, про что эта картинка?

graph

WTF?

  • Как так вышло, что чем «оптимальнее» загружен процессор, тем медленнее идёт процесс?

  • И почему всё настолько плохо возле точки 100% загрузки процессора?

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

  • Очередь из сообщений в топике Kafka,

  • очередь задач в вашей Жире,

  • очередь на кассу в магазин,

вообще любая очередь.

london queue

Параметры модели

  • Cредняя частота возникновения событий — λ,

  • Средняя пропускная способность обработчика — μ

  • Загруженность обработчика — \(\rho=\frac{\lambda}{\mu}\)

Получаем такую картинку

othergraph

Но почему не такую??

whynot

Наливаем себе пивко, начинается матан

beers

Модель (самая простая)

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

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

  • Система может находиться в счётном количестве состояний:

markov.png

Вероятность нахождения в состоянии n в момент времени t

markov.png
\[\huge \begin{array}{rcl} p_0(t+\Delta t) & = & (1 - \lambda \Delta t) p_0(t) + \mu \Delta t p_1(t) + o(\Delta t), \\ p_n(t+\Delta t) & = & \lambda \Delta t p_{n-1}(t) + (1 - (\lambda +\mu)\Delta t) p_n(t) \\ & & + \mu \Delta t p_{n+1}(t) + o(\Delta t). \end{array}\]
kitten 1

При Δt → 0

markov.png
\[\huge \begin{array}{rcl} p'_0(t) & = & - \lambda p_0(t) + \mu p_1(t),\\ p'_n(t) & = & \lambda p_{n-1}(t) - (\lambda +\mu) p_n(t) + \mu p_{n+1}(t) \end{array}\]
kitten 2

При стационарном поведении системы

markov.png
\[\huge \begin{array}{rcl} 0 & = & - \lambda p_0 + \mu p_1,\\ 0 & = & \lambda p_{n-1} - (\lambda +\mu) p_n + \mu p_{n+1},\\ 1 & = & \sum\limits_{n=0}^{\infty}p_n \end{array}\]
kitten 4

Решение всей системы

\[\Huge \begin{array} &p_n=(1-\rho)\rho^n,\\ n = 0,1,2\ldots, \quad \rho = \frac{\lambda}{\mu} \end{array}\]
kitten 5

Средняя длина очереди?

\[\Huge \begin{array} &E(L) = \sum\limits_{n=0}^{\infty}n p_n = \rho(1-\rho)\sum\limits_{n=0}^{\infty}n \rho^{n-1}=\\ = \frac{\rho}{1- \rho}. \end{array}\]
kitten 3

Итак…​

\[\Huge E(L) = \frac{\rho}{1- \rho}.\]

Но ведь это…​

graph

На пальцах это можно объяснить как-то так

gates
othergraph

Выводы

Любая система с очередью может находиться в одном из трёх режимов

Нестабильный режим

μ < λ или μ = λ (нам конец)

othergraph 1

Режим с малым ожиданием в очереди (и малой загрузкой процессора)

μ >> λ (очереди нет, но и процессор часто простаивает)

othergraph 2

Возле точки насыщения

  • μ > λ, но ненамного!

othergraph 3

Главный вывод

Оптимизация процессора и оптимизация потока — это «качели»: оптимизируя поток, мы должны лимитировать загрузку процессора.

seesaw

У меня всё!

seesaw