Waiting time paradox #3: сервера и их очереди

Если происходит что-то странное, значит, где-то рядом автобусная остановка
(Народная мудрость)

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

Представьте себе сервер, на который приходят заявки, и очередь, где заявки могут чуток обождать, пока сервер занят с другими заявками. Не хочется тратить CPU на постоянный опрос очереди busy-loop-ом, поэтому сервер обрабатывает те заявки, которые уже накопились в очереди, а как только заявки в очереди заканчиваются – сервер переключается на какие-то фоновые задачи, а потом на sleep(5). Отоспавшись, сервер возвращается к очереди, и если там что-то накопилось – то все это разгребает, и опять уходит заниматься фоновыми делами + sleep(5), а если ничего не накопилось – так сразу уходит заниматься фоновыми делами и спать. Поддерживает разумный work-life balance:

while( true ){
    task = queue.poll()
    if( task != null ) {
        task.doTheNeedful()
    } else {
        doBackgroundJobs()
        sleep(5)
    }
}

(Полный java-код тут, можно поиграться)

...И так сервер жил-поживал, пока к нему не приставили девопса Василия. Василий первым делом замерил среднее время исполнения заявки, и решил, что 13 мс это многовато. Взглянул на код, подумал, и заменил sleep(5) на sleep(3).

Среднее время обработки заявки выросло с 14 до 15 мс.

Вася еще немного подумал, и решил, что это статистическая погрешность. И убрал sleep() вообще – от греха подальше.

Среднее время обработки выросло до 30мс.

Вася перекрестился, вернул все назад, и поклялся никогда больше не мешать компьютеру спать положенные по КЗоТу 5 миллисекунд.

Что за непотребство тут происходит?

Надо сказать, что Вася – довольно молодой девопс. Он ездит на работу на электросамокате, и давно уже не дожидался автобуса на автобусной остановке.

Но вы-то наверняка уже догадались, что тут как-то засветился парадокс времени ожидания. Таки да, в системах массового обслуживания (queueing systems) парадокс времени ожидания часто вылезает. Точнее, это в других местах он вылезает – а в системах массового обслуживания он живет, у него тут гнездо и птенцы.

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

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

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

$$\mathbb{E}[W]=\frac{\lambda \mathbb{E}[X]}{1-\lambda \mathbb{E}[X]}\frac{1}{2}\Big(\mathbb{E}[X]+\frac{\mathbb{D}[X]}{\mathbb{E}[X]}\Big)$$

(λ это частота прихода заявок, в штуках за единицу времени, а 𝔼[X], 𝔻[X] это среднее и дисперсия времени исполнения заявок)

Выражение это называется формулой Поллачека-Хинчина, и оно больше чем наполовину состоит из выражения для остаточного времени из парадокса времени ожидания!

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

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

Однако внешнее сходство формулы не так важно – множители в формуле можно перетасовать и так, что явной отсылки к парадоксу времен ожидания не будет. Что действительно важно, это что зависимость среднего времени ожидания от времени обработки в системе Поллачека-Хинчина имеет те же особенности, что и время ожидания на автобусной остановке. Ну, по крайней мере, 2 из 3-х:

• Время ожидания зависит от не только от среднего времени обслуживания, но и от дисперсии
• За счет вклада дисперсии время ожидания может быть сколь угодно большим даже при малом среднем времени обслуживания. А поскольку загрузка (утилизация) сервера прямо пропорциональна времени обслуживания заявки, то среднее время ожидания может быть сколь угодно большим даже если сервер бОльшую часть времени простаивает (а очередь, соответственно, бОльшую часть времени пуста)

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

Но самое любопытное свойство остаточного времени ожидания это немонотонность – что среднее остаточное время ожидания может уменьшаться, когда среднее время ожидания растет. Что-то подобное и наблюдал Василий. И вот немонотонность в системе Поллачека-Хинчина отсутствует! Это легко видно из формулы, если внести 𝔼[X] под скобки:

$$\mathbb{E}[W]=\frac{\lambda \mathbb{E}[X]}{1-\lambda \mathbb{E}[X]}\frac{1}{2}\Big(\mathbb{E}[X]+\frac{\mathbb{D}[X]}{\mathbb{E}[X]}\Big) =\frac{\lambda}{1-\lambda \mathbb{E}[X]}\frac{1}{2}\Big(\mathbb{E}[X]^2+\mathbb{D}[X]\Big)$$

...и первый и второй множители – монотонно возрастающие функции от 𝔼[X]. На графике это еще лучше видно:

Куда же пропала немонотонность – ведь в у остаточного времени она есть, а остаточное время здесь явно фигурирует?

Можно подумать, что дело в очереди – я поначалу так подумал. Но нет, очередь здесь ни при чем.

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

И если увеличивать длительность обработки заявки, то остаточное время сначала падает, а только потом растет – а вот вероятность наткнуться на занятый сервер однозначно растет, как минимум линейно. Больше времени на обработку одной заявки -> больше общий объем работы за то же время -> больше доля времени, когда сервер занят. И это увеличение вероятности ждать перебивает начальное уменьшение среднего остаточного времени ожидания.

Можно сформулировать это так: разница между двумя моделями в том, существует ли состояние "свободной кассы". Если бы автобус на пустой остановке оставался ждать пассажиров – то в такой системе эффект немонотонности времени ожидания уже не наблюдался бы (но остальные 2 свойства парадокса времен ожидания сохранились бы)

Я очень люблю немонотонность, можно ее вернуть? Ну, пожалуйста!

Раз в системе, где сервер опрашивает очередь постоянно, немонотонности нет, а в системе у Васи она наблюдается – значит, дело в перерывах. Система, которая досталась Васе, в литературе называется queue with vacation (and exhaustive service). Под vacation подразумевается то, что у меня "обработка фоновых задач" + "сон" – пауза-перерыв, когда сервер не обрабатывает заявки из очереди. (Позже будет понятно, зачем я поделил этот перерыв на две части).

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

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

$$\mathbb{E}[W_V]=\frac{\lambda \mathbb{E}[X]}{1-\lambda \mathbb{E}[X]}\frac{1}{2}\Big(\mathbb{E}[X]+\frac{\mathbb{D}[X]}{\mathbb{E}[X]}\Big)+\frac{1}{2}\Big(\mathbb{E}[X_V]+\frac{\mathbb{D}[X_V]}{\mathbb{E}[X_V]}\Big)$$

То есть время ожидания в системе "с перерывами" это время ожидания в аналогичной системе без перерывов, плюс среднее остаточное время от времени перерыва. (𝔼[X_V], 𝔻[X_V] это среднее и дисперсия длительности перерывов-vacations)

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

Вот мы и добрались до самого интересного: первое слагаемое в формуле от наличия перерывов не зависит вообще, а второе это чистое остаточное время от времени перерывов, со своим немонотонным поведением, и безо всякого компенсирующего множителя. Это второе слагаемое и описывает увеличение среднего времени ожидания при уменьшении среднего времени перерыва 𝔼[X_V], которое наблюдал Василий. В моем примере стандартное отклонение времени перерыва 7мс, то есть минимум времени ожидания будет если спать 6мс. В окрестности минимума функция меняется не очень быстро, так что в интервале 5..8 мс разница почти не видна.

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

(Продолжение последует. Ну, по-крайней мере, я на это надеюсь)

Ссылки

1. MAP6264 - Queueing Theory (видео-лекции, vacation model описывается в лекциях 27-29)
2. wiki:Pollaczek-Khinchine formula
3. Вывод формулы Поллачека-Хинчина (рус)
4. Queueing Theory in Practice: Performance Modeling for the Working Engineer (Вывод формулы Поллачека-Хинчина, eng)
5. Some reflections on the renewal-theory paradox in queueing theory (Cooper, Niu, Srinivasan, 1998)
6. When Does Forced Idle Time Improve Performance in Polling Models? (Cooper, Niu, Srinivasan, 1998)