9 августа 2020 г.

Queueing theory for fun and practice #3: системы с потерями

Начальник отдела челобитных Апполинарий Матвеевич любит порядок, поэтому просители могут ожидать его внимания только смиренно сидя в приемной, а не толкаясь возле дверей присутственного места – оттуда их гоняет казак Семен.

Какова должна быть посадочная вместимость приемной, чтобы не более 1 просителя в день ушло не солоно хлебавши, если пропускная способность Апполинария Матвеевича не более дюжины челобитных в день, а входящий поток около 10 челобитных в день?

TL;DR: реальные системы обрабатывают не все задачи – часть задач теряется или отбрасывается за счет ограниченности буферов и/или таймаутов. Потери делают систему устойчивой к перегрузке, и улучшают качество обслуживания тех задач, что дожидаются обработки – теряются более вероятно именно те задачи, которым пришлось бы ждать дольше всех. Системы с потерями – добро, делайте его больше.

(часть 3, предыдущая часть: нагрузка и время отклика)

Я уже упоминал, что система с бесконечной очередью, загруженная на 100%, будет давать неограниченное время ожидания. Однако на практике этого не происходит: есть немало систем, пропускная способность которых планировалась по максимуму, без запаса емкости – и которые, при этом, вполне приемлемо работают.

Почему? Конечно, может быть в оценку трафика затесалась ошибка, и система на самом деле имеет запас емкости. Другое возможное объяснение: в системе есть потери – она обрабатывает не всех клиентов. Часть клиентов не добирается до кассира, часть задач не добирается до сервера.

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

27 июля 2020 г.

Queueing theory for fun and practice #2: нагрузка и время отклика

Во храме Божьей Матери Поклонской батюшка Иннокентий принимает исповедь у раба божьего обыкновенно минут за 10, а утешения жаждут около 5-и рабов божьих в час. Много ли стульев надобно поставить во храме, дабы исповеди ожидающие не толпились в праздности пред святым алтарем?

"Массовое окормление паствы: пособие для начинающих" (редакция 3-я, неизданная)

(Часть 2, начало: ТМО, square root staffing, Little)

Как зависит время отклика от нагрузки на систему (утилизации)? Для многих систем измерения дадут что-то вроде такой картинки:

Такую кривую зависимости среднего времени отклика от нагрузки за характерную форму часто называют J-curve. Конечно, не обязательно кривая в конкретной системе будет выглядеть точно так – например, могут присутствовать ступеньки, соответствующие разным механизмам, которые ответственны за время отклика – но в среднем такая кривая свойственна многим системам, и приводит к ней как раз наличие внутренних очередей/буферов.