9 августа 2020 г.

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

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

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

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

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

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

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

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