23 мая 2019 г.

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)$$

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

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

Вот мы и добрались до самого интересного: первое слагаемое в формуле от наличия перерывов не зависит вообще, а второе это чистое остаточное время от времени перерывов, со своим немонотонным поведением, и безо всякого компенсирующего множителя. Это второе слагаемое и описывает увеличение среднего времени ожидания при уменьшении среднего времени перерыва 𝔼[XV], которое наблюдал Василий. В моем примере стандартное отклонение времени перерыва 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)

8 комментариев:

  1. А не связано ли это с тем, что при меньшем слипе и отсутствии заявок тред тупо чаще висит в обработке бэкграунд тасков? Если выпилить бэкграунд таски, то вроде исправления Васи не лишены смысла?

    И еще хотел у Вас уточнить, Вы писали на хабре в 2013 г что не volatile переменные в джава имеют relaxed семантику если по аналогии с c++11, это я что то недопонял или ...? Веди при релаксед гарантируется, что чтение увидит предыдущую запись, в то же время запись в джаве не в волатайл может быть не прочитано вообще. Интересно было бы получить ответ, спасибо!

    ОтветитьУдалить
    Ответы
    1. > Если выпилить бэкграунд таски, то вроде исправления Васи не лишены смысла?

      Если удастся избежать фоновых задач -- не лишены. Но вы не всегда можете их избежать -- роль фоновых задач могут выполнять GC, или page fault, или прерывания

      >Веди при релаксед гарантируется, что чтение увидит предыдущую запись, в то же время запись в джаве не в волатайл может быть не прочитано вообще

      Я не специалист в С++ memory model. Насколько я знаю, relaxed в CMM не дает никаких дополнительных гарантий порядка -- как и plain load/store в java. Что вы имеете в виду под "предыдущей записью" -- в какой последовательности она предыдущая?

      Удалить
    2. Спасибо вам за вашу статью! Несмотря на то, что выводы в 3ей части я нахожу вопиюще некорректными(что даже закрадывает подозрение, не шутка ли это), предыдущие части были очень познавательны.

      И вот почему выводы я нахожу некорректными. Все дело в коде вашей симуляции. Как верно было замечено выше, если мы убираем слип, то поток висит в фоновых тасках чаще. И в вашем коде(гист) почему реализация фоновых тасок - это бросание кубика с вероятностью уйти в длительный слип в 50мс. В отсутствие слипа кол-во бросков кубика значительно возрастает, поскольку окно до следующего реквеста позволяет бегать бесконечный цикл сколько хватит тактов процессора. Т.е. практически наверняка мы уйдем в 50мс слипа. Получается в среднем +25мс на реквест. +5мс на serviceTime. Вот и получаются те самые 30мс. И это никакая не симуляция background тасок. Кол-во background тасок в реальном мире не пропорционально кол-ву опросов на эти таски, как в случае с вашим бросанием.

      И действительно, если в этот doBackgroundJob() вместо кидания кубика поставить любой слип(пусть в 1мс, или тот же рандом использовать для выбора времени слипа), что гораздо ближе к реальности, то уже никаких этих эзотерических эффектов, о которых вы толкуете, не наблюдается.

      Спасибо за любопытную тему и за ваше трикстерство(впрочем, может вы и действительно запутались сами в том, о чем пишете, написали кривой код и подогнали под это математическое "объяснение", - что, впрочем, еще занятнее) :)

      Удалить
    3. Я раза 4 перечитал ваш комментарий, но так и не смог понять, что вас смущает. То, что я смог понять -- разобрано здесь, или в 4-й части. Кажется, вы просто не поняли (а то и не прочитали), о чем вообще речь.

      На всякий случай, вкратце повторю:
      1. Эффект не интуитивен, но весьма реален, и известен с полвека (хотя и в узких кругах)
      2. Он возникает даже на реальном производстве, а не только в симуляциях
      3. Эффект не частый, возникает при довольно узком спектре параметров. Если бы он не был редким -- он не был бы таким удивительным и контринтуитивным.
      4. Параметры в примере, конечно, подобраны, но сам пример вполне себе из реальной практики. В 4-й части я описываю, где такие системы естественно возникают.

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

      Удалить
    4. Этот комментарий был удален автором.

      Удалить
    5. Перечитал еще раз все внимательно. Понимаю, почему симуляция такая, какая есть. Не прав на счет ее некоректности в рамках вашего изложения. Интервал бэкграунд таски большой, слипа - маленький, все понятно.
      Однако это корректно для системы с пуассоновским распределением. Только автобусы в реальной жизни не распределяются по пуассону, там скорее нормальное распределение как раз.
      И в примере литературы[6] видно, что там тот же Пуассон. Т.е. речь идет о системах, где vacation содержит некоторую работу, носящую пуассоновый характер распределения. Только мы ведь имеем дело с детерменированными системами. И вы берете в качестве примера веб-сервер. Вам следовало бы приводить пример такой работы веб-сервера, которая могла бы действительно носить пуассоновый характер, т.е. недетерменированной работы. И если вы оговорите явно, что вот эти 5мс слипа помогли не вляпаться в недетерменированную работу(которую вообще говоря можно скипнуть, по всей видимости), тогда и Васе будет спаться спокойнее, и мне в том числе.

      Однако вы говорите:
      > "если в цикле обработки изначально присутствуют паузы, и их сложно или невозможно устранить – то иногда можно улучшить качество сервиса увеличив эти паузы"

      Речь то не про паузы сами по себе, и не в самих паузах причина такого эффекта. А в том, что есть какие-то мистические паузы, которые, во-первых, недетеменированы(потому что Пуассон), а во-вторых, не делают ничего полезного. Потому что если бы они делали полезную работу, то добавлением доп. пауз мы бы уменьшили это кол-во полезной недетерменированной работы. И уже нельзя говорить про "улучшение качества сервиса", потому что это уже некий trade-off. А ежели работа все-таки полезна, то ее возможно и необходимо описать.

      Что касается примера конвееров, то всякое переключение, связанное с физическим перемещением, вполне может укладываться в пуассона - т.к. это как раз вероятность поломки оборудования, возможность уронить ключ или сломать ногу, если очень быстро бегать от ленты к ленте. Это кажется правдоподобным.
      Что же до selector loop или, например, context switch в многопоточности - тоже да. Потому что всякое переключение не дается бесплатно. Лучше всего на примере сравнения производительности CAS, которые производительны при низком и умеренном contention, но уже уступают синхронизации при высоком спросе на ресурс. Здесь добавление sleep могло бы добавить производительности, но это же другая проблема. Там деградация ресурсов, но снова не Пуассон, т.к. мы знаем, что хотя бы одна операция CAS в момент времени будет успешна.
      Т.е. опять же детерменированные системы, и разные подходы в зависимости от нагрузки. Это не какой-то загадочно-мистический слип, это вполне исследованная и описанная область. И если бы речь в вашем примере с веб-сервисом шла именно о переключении контекстов или чем-то подобном, то можно было бы предложить вместо слипа задать разные стратегии блокировок.
      А вы мистифицируете и уходите в спекуляции 5минутными перерывами кассиров, в котором скрыто "такое нетривиальное поведение". Если уж проводить аналогию с кассирами, тогда надо бы назвать, в какую такую недетерменированную бесполезную(с точки зрения обслуживания клиентов) работу он бы мог вляпаться, не заполни он время, когда она могла бы случиться, спасительным перерывом.(прочтение статьи и размышления по поводу waiting time paradox не в счет :D )


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


      А еще спасибо за ваш ответ. Я честно пытаюсь разобраться, и это все действительно очень интересно. :)

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

      Удалить
    7. >Однако это корректно для системы с пуассоновским распределением.

      Наоборот: для систем с пуассоновским распределением времени vacation эффекта не будет. У пуассоновского распределения среднее всегда равно дисперсии, коэффициент вариации = 1. Т.е. оно лежит ровно на границе между распределениями с малой вариацией -- для которых аномального эффекта не будет, и распределениями с большой вариацией, для которых аномальный эффект проявляется.

      >А в том, что есть какие-то мистические паузы, которые, во-первых, недетеменированы(потому что Пуассон),

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

      Случайность пауз здесь так же не очень важна: если делать паузы не по ГСЧ, а детерминированно, каждый N-й раз -- ничего не изменится. Паузы должны иметь определенные статистические свойства -- это не означает, что они должны быть случайными.

      >а во-вторых, не делают ничего полезного.

      Вы никогда не встречали неоптимальный код -- который не делает ничего полезного, но этого просто никто не замечает/никому не важно? Я встречал его многократно. И особенно часто как раз в не-критических частях системы, типа выполнения фоновых задач очистки. В критических-то частях его быстро обнаруживают и оптимизируют, но кто полезет профилировать фоновые задачи?

      Например, та самая фоновая очистка может выглядеть как обход кэша, и сброс устаревших. И доминирующую роль играет обход всех элементов, которых там 100000 -- а вот количество устаревших действительно зависит от нагрузки/частоты очистки, но оно-то как раз является малой поправкой ко времени перебора. Вот вы и получаете большую константу, практически независящую от количества "полезной работы".

      Я подобный код видел не раз, да и сам писал.

      >А вы мистифицируете и уходите в спекуляции 5минутными перерывами кассиров, в котором скрыто "такое нетривиальное поведение".

      То есть для вас с самого начала было очевидно, что уменьшив время ожидания Вася ухудшит среднее время обслуживания? Вы могли это предсказать и подтвердить расчетами?

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

      Я возился с WTP около полутора месяцев, и вроде бы разобрался сверху донизу, но все равно ощущаю удивление. Это не так уж часто происходит: обычно если я в чем-то разбираюсь, то удивление пропадает. Так что этот эффект -- редкое исключение. Но вы, конечно, не обязаны разделять мои эмоции

      Удалить