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

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

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

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

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

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

Queueing theory for fun and practice (#1): square root staffing, Little's law

На 28-ом этаже центра разработки крупного инвестиционного банка есть 8 туалетных кабинок для людей, идентифицирующих себя с мужским гендером. Работающий в центре высокофункциональный аутист Иннокентий подсчитал, что когда он заходит в туалет, в среднем 5 из 8 кабинок уже заняты.

Сколько человеко-часов в день сотрудники офиса спускают в унитаз?

"Теория массового обслуживания для сантехников" (неизданное)

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

Материалы, которые мне попадались по теории массового обслуживания, распадаются на две категории: ТМО как раздел математики (теории вероятности), и ТМО как раздел бизнес-управления, менеджмента производства/обслуживания (operations research).

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

Мне же, как физику и инженеру, хотелось бы сфокусироваться на небольшом количестве простых но универсальных закономерностей. Чтобы про каждую закономерность было понятно, зачем она нужна и где ее можно применить, но и также откуда у нее ноги растут, и на каких приближениях она основана. Математическая строгость, как и точность полученных формул меня волнует меньше, потому что реальные системы все равно заметно отличаются от их абстрактных математических моделей, и результаты матмоделей всегда приходится корректировать под практику, особенно если модели очень базовые.

Design of everyday things

Недавно прочитал "Дизайн привычных вещей" Дональда Нормана. Норман – computer scientist, и когнитивный психолог, известный и авторитетный специалист по эргономике. Он популяризовал сам термин "user experience", и был, вероятно, первым User Experience Architect – в Apple, что совершенно не удивляет.

На его книгу я наткнулся совершенно случайно, и залип с первых страниц. Книга написана в 1986 году, и Норман в предисловии пишет, что сознательно не переписывал разделы про кнопочные телефоны и видеомагнитофоны – технику того времени, давно уже канувшую в лету. Я немного опасался, что читать про проблемы интерфейса вещей, которые уже 20 лет никем не используются, будет скучно – но нет, наоборот. Вещи из 80-х проще, и ошибки дизайна на их примере понятнее – и но совершенно очевидно, что современные дизайнеры, проектируя гораздо более сложные вещи, продолжают делать ровно такие же ошибки.

Charlie Gracie: Current state of JVM Escape Analysis and downstream optimizations

Я уже какое-то время отошел от темы скаляризации и escape-анализа, но тут случайно наткнулся на любопытное видео с JFokus: Чарли Грасье из Микрософта рассказывает, как они для своих целей сделали прототип stack allocation для java 11. И даже не для Graal (где нынче чаще всего делают что-то новое), а для старого-доброго C2. Чарли начинает с краткого обзора escape-анализа и скаляризации в целом, потом кратко рассказывает, как они модифицировали JVM C2, чтобы сделать аллокацию на стеке.

Что это дает: они заинтересованы прежде всего в scala, и для scala-бенчмарков аллокация на стеке дает 5-15% увеличения производительности. Чарли спекулирует, что это прежде всего из-за увеличения кэш-локальности, поскольку объекты, аллоцированные на стеке, всегда будут горячими в кэше, а объекты, аллоцированные в куче, не всегда. Звучит немного странно, потому что стандартная аллокация в джаве (bump the pointer) тоже должна давать довольно хорошо предсказуемый и дружественный для кэширования паттерн доступа — но результаты говорят за себя.

Еще они обещают привести код в порядок, и инициировать принятие их изменений в mainline. Если получится (если!), будет очень интересно: я уже и не ждал ничего подобного в JVM.

Waiting time paradox #4: aftermath

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

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

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

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-код тут, можно поиграться)

Waiting time paradox #2: почему успешный поиск в хэш-таблице дольше не успешного?

…Продолжение предыдущей статьи про waiting time paradox: на этот раз разберемся, почему успешный поиск в хэш-таблице обычно дольше, чем не-успешный

Возьмем классическую хэш-таблицу с разрешением коллизий цепочками: K пар ключ-значение, B корзинок со связными списками для разрешения коллизий, вот это все. Мы ищем в этой таблице разные ключи (а зачем еще нужна хэш-таблица?). Для каких-то ключей в таблице находится соответствие, для каких-то – нет.

Вопрос: что больше – среднее количество сравнений при успешном поиске, или среднее количество сравнений при неуспешном поиске?

Waiting time paradox #1: автобусы, очереди, и хэш-таблицы

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

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

Теория разбитых окон в применении к разработке

В социальной психологии есть такая "теория разбитых окон". Она утверждает, если упрощенно, что бардак который не исправляют — воспроизводит вокруг еще больший бардак. Точнее, утверждается, что человек смотрит на то, в каком состоянии находится его окружение, и интуитивно выводит отсюда неформальные социальные нормы (“как здесь можно себя вести”) — в противовес формальным социальным нормам ("как положено себя вести"). И если окружение показывает, что “здесь можно” бить окна, мусорить, другими способами нарушать формальные нормы, и это никого не волнует (окна не вставляют, мусор не убирают, нарушителей не штрафуют) — человеку психологически проще становится разбить еще одно окно, бросить жевачку на пол, припарковаться в неположенном месте.

Оценки квантилей распределений потока данных

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

Проблема тестирования конфигурации в том, что нет готовой инфраструктуры

Одна из проблем с тестированием конфигурации состоит в том, что нет готовой инфраструктуры

Я имею в виду, что когда вы собираетесь написать тест для кода — у вас уже многое есть. У вас есть какая-то доменная модель, у вас есть какие-то API, у вас есть какие-то builders/wizards/DSL. Да, поверх всего этого, обычно, все равно приходится дописать прослойку вспомогательного кода, предназначенного именно для тестирования (aka "test-harness"), но если основной код спроектирован и написан достаточно хорошо, то эта прослойка довольно тонкая. Условно, процентов 50-80 уже написано, и эти проценты очень облегчают начало.