Waiting time paradox #4: aftermath

(продолжение серии про парадокс времени ожидания)

…Мне кажется, это поразительный эффект: добавка sleep(5) в цикл обработки задач может уменьшать среднее время обработки. Даже после того, как я уже разобрался с этим эффектом на примере автобусной остановки, я все еще не мог поверить, что такой же эффект будет и в системе с очередью. И, несмотря на все формулы, разобранные примеры и симуляции, на интуитивном уровне я все еще ощущаю это как какой-то трюк. Это и поразительно: хотя логически я все понимаю, могу объяснить, и симуляцию написать, и картинку нарисовать – но моя интуиция все равно отказывается воспринимать это как очевидное.

И ведь происходит все в очень обыденной системе, с которой мы регулярно сталкиваемся в жизни. В математике есть множество выносящих мозг результатов, но многие из них выносят мозг просто потому, что относятся к системам, для которых в повседневной жизни нет аналогов. Парадокс Банаха-Тарского гораздо круче парадокса времен ожидания – но кто из нас в жизни сталкивается с разрезанием сферы на не-измеримые куски? Сама постановка задачи уже далеко выходит за рамки повседневного опыта и бытовой интуиции – не удивительно, что результат получается не интуитивный. Но очередь в Сбербанк, и кассир, который делает между клиентами минутную паузу, а иногда выбегает перекурить на 5 минут, а иногда попить чай на 15 – это обыденная ситуация. И оказывается, что в этой обыденной ситуации скрыто такое нетривиальное поведение!

Чуток подробностей

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

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

Дальше: зачем в примере из предыдущего поста я разделил vacation на "обработку фоновых задач" и sleep(5)? Потому что парадокс возникает, когда среднее время "отдыха" меньше его же стандартного отклонения, и это среднее меняется, не затрагивая стандартного отклонения. Сумма из случайной паузы с большим разбросом, и детерминированной паузы – этим условиям удовлетворяет. И (судя по литературе) именно в таких условиях парадокс чаще всего проявляется в реальной жизни: есть какие-то "внешние условия" обеспечивающие случайную задержку с большим разбросом, и есть детерминированные накладные расходы внутри системы. Менять "внешние условия" может быть довольно непросто, поэтому инженеры сначала берутся за оптимизацию того, что ближе и понятнее – накладных расходов внутри системы. Ну и получается (если повезет) неожиданный результат.

Следующий вопрос (который мне задали в твиттере): среднее время ожидания – это хорошо, но как ведут себя высшие квантили распределения времени ожидания? Сейчас уже мало кто измеряет только среднее время обслуживания, почти все уже меряют какие-нибудь 90%/95%/99%…

С квантилями такой простой формулы, как со средним, не получится. Можно получить распределение времени ожидания, а из него и квантили. Но какого-то простого соотношения между, скажем, квантилями распределения времени задержки и квантилями распределения времени ожидания – похоже, нет. На простых вырожденных примерах понятно, что чем выше квантиль, тем меньше он подвержен парадоксу времен ожидания. То есть высшие квантили скорее всего ведут себя интуитивным образом: увеличивается задержка – почти наверняка увеличивается и 99%. А вот более низкие квантили могут вести себя нормально или аномально – зависит от конкретного распределения времен задержек. Если постараться, можно подобрать такое распределение, чтобы и 99% вел себя аномально, но встретить такое распределение в реальной жизни кажется маловероятным

Где еще может происходить такое непотребство?

Еще одна система, где такое парадоксальное поведение времени ожидания может наблюдаться – это мультиплексор: один сервер, обрабатывающий несколько очередей, по кругу. Как в selector loop, или в паттерне Reactor. (В теории очередей эта модель называется polling model или cycling queueing system)

C точки зрения каждой конкретной очереди время, пока сервер обрабатывает другие очереди, выглядит как "перерыв" в работе. То есть для каждой конкретной очереди все выглядит как в системе из предыдущего поста (vacation model), но только время "перерывов" теперь складывается из задержек на переключение между очередями, и еще и из времени обработки заявок из других очередей.

Насколько я понял, впервые эффект увеличения среднего времени ожидания при уменьшении задержек был замечен как раз в системе мультиплексора (Sarkar, Zangwill, 1991). Речь шла не о компьютерных системах, а о промышленных конвейерах. В промышленной установке естественным образом возникают задержки при переключении с одного конвейера на другой – что-то должно физически куда-то переместиться. Такие задержки руки тянутся соптимизировать (а тогда как раз на взлете были идеи "бережливого производства" Тайоты – непрерывное устранение потерь на каждом этапе). И обнаружилось, что иногда такая оптимизация может не улучшить, а ухудшить результат.

У мультиплексора гораздо больше свободных параметров, чем у системы с одной очередью, поэтому и анализ его тоже сильно сложнее. Но результат (когда его удается получить) получается очень знакомым: выражение для среднего времени ожидания заявки так же распадается на слагаемые, описывающие сервер без задержек и слагаемые, зависящие от остаточного времени времен задержек при переключении между очередями. И благодаря вторым слагаемым, среднее время ожидания для заявки оказывается выпуклой вниз функцией от среднего времени задержки на переключение от очереди к очереди. Минимум у этой функции уже не будет точно в точке $$\mathbb{E}[V]=\sqrt{\mathbb{D}[V]}$$, но где-то около того: под корнем будет стоять какая-то взвешенная сумма дисперсий времен переключения между разными очередями

Например, для симметричного мультиплексора – когда очереди полностью идентичны по всем параметрам – удается получить явную формулу для среднего времени задержки, которое минимизирует время ожидания заявок:
$$\mathbb{E}[V]=\sqrt{\frac{1-\rho_T}{1-\rho_T/N}\mathbb{D}[V]}$$
($$\rho_T$$ это общая утилизация сервера, со всех N очередей, а $$\mathbb{E}[V],\mathbb{D}[V]$$ это среднее и дисперсия суммы всех задержек на всех очередях). Если средняя суммарная задержка в системе сейчас меньше этого (оптимального) значения – то среднее время ожидания можно улучшить, добавив в цикл опроса очередей постоянную задержку так, чтобы общая задержка увеличилась до оптимального значения.

И для автобусной остановки, и для сервера с одной очередью минимум достигался когда среднее равно корню из дисперсии. Здесь же перед корнем из дисперсии появляется еще коэффициент, зависящий от загруженности сервера. Коэффициент этот чуть меньше 1 при малой загрузке, и стремится к 0 при высокой – то есть чем больше загрузка, тем уже область, где проявляется аномальное поведение. Это вполне интуитивно: чем больше загружен сервер заявками, тем меньшую роль в общем раскладе играют задержки на переключение между очередями

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

$$\mathbb{E}[V] = \sqrt{\sum_{i=0}^{N}\alpha_iD[V_i]}$$
коэффициенты этой взвешенной суммы уже не имеют явного выражения, есть только итеративный алгоритм их вычисления

Похоже, что соотношение между средним и дисперсией это неплохое эвристическое правило, чтобы оценить, может ли что-то подобное происходить в системе, на которую я сейчас смотрю: если среднее время пауз меньше его же стандартного отклонения, $$\mathbb{E}[X_V] < \sqrt{\mathbb{D}[X_V]}$$, то может быть (но не обязательно) в системе проявляется аномальная зависимость времени ожидания от величины пауз, а если среднее заметно больше стандартного отклонения, то это маловероятно.

Ссылки

1. MAP6264 - Queueing Theory (видео-лекции, vacation/polling model описывается в лекциях 27-29)
2. When Does Forced Idle Time Improve Performance in Polling Models? (Cooper, Niu, Srinivasan, 1998)
3. Variance Effects in Cyclic Production Systems (Sarkar, Zangwill, 1991, http://dx.doi.org/10.1287/mnsc.37.4.444)

P.S. В своих старых статьях я неожиданно обнаружил еще один пример, когда оптимизация задержек ухудшает какую-то метрику производительности. Несколько лет назад была любопытная история: после оптимизации атомарных инструкций при переходе с архитектуры Nehalem на Sandy Bridge, примитивные бенчмарки atomic increment начали показывать существенно худшие результаты. Как мне кажется, тамошний сценарий все же отличается от парадокса времени ожидания. Но что-то общее между ними есть: там тоже суть в том, что у атомарных инструкций есть быстрый (локальный) и медленный (глобальный) сценарии исполнения. И после оптимизации медленного режима увеличилась доля инструкций, исполняющихся в этом бенчмарке по медленному сценарию, и это перевесило эффект от оптимизации.