Еще один сценарий для waiting time paradox

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

Сейчас по работе пишу небольшую странично-организованную структуру данных. Записи в ней случайного размера – т.е. не выровнены по границам страниц. Если очередная запись не влезает место, оставшееся на текущей странице, то надо либо разделить ее на две страницы, либо полностью перенести на новую страницу, а на старой оставлять padding-record.

Вариант "переносить полностью" – проще, но часть места непроизводительно теряется. Мне захотелось оценить: насколько большая эта потерянная часть? Если средний размер записи X, то сколько, в среднем, на страницу будет теряться на padding-record?

Интуитивно кажется, что в среднем будет теряться половина средней записи, X/2. Но первая же симуляция показала, что больше X/2.

И тут я вспомнил, где такое видел – это же waiting time paradox. Чтобы увидеть аналогию, пришлось немного переформулировать задачу: пусть случайные размеры записей отложены подряд на прямой. Мы тыкаем в случайную точку на этой прямой ("конец страницы"), и спрашиваем: какое, в среднем, расстояние до предыдущей границы записи?

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

(Еще в той задаче нас интересовало время до следующего автобуса, а здесь время от границы предыдущей записи – но это практически ничего не меняет в вычислениях)

Ответ получается тот же: в среднем теряется $$\frac{E[X]}{2}(1+\frac{D[X]}{E[X]^2})$$ – то есть всегда больше половины среднего размера записи. Если распределение размера записи Пуассоновское, то, в среднем, будет теряться ровно средний размер записи на страницу. Для распределений с бОльшей вариацией – и того больше.

Когда имеет смысл передавать IO в отдельный поток?

Допустим, у нас есть простая система, которая принимает запросы из сети, как-то их обрабатывает ("бизнес-логика"), и отправляет результат назад, в сеть. Мы заинтересованы в быстром отклике (=latency), а отправка – это IO, так что возникает идея ее снести в отдельный поток.

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

Стоит ли вообще игра свеч, и если стоит – то когда?

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

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

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

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

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

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

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

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

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

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

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

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

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

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