Тема в Низкоуровневом Программировании про переполнение очереди меня сильно расстроила. Почему-то напомнила о всяких ЕГАИСах и прочих дико тормозных системах.

Потому начинаю серию постов о том, как оптимизировать архитектуры (не только низкоуровневые, хотя речь все боле о них) на производительность в условиях большого числа входящих извне реквестов, т.е. на scalability.

Пункт первый. "Ресурсный" подход.

Что такое массовое обслуживание — видели все в Ашанах, аэропортах и тому подобных местах. Изложу на пальцах некие азы теории оного массового обслуживания.

От чего зависит общее время, которое человек тратит на покупку в Ашане? выясним это. Сразу отметем для простоты субъективный фактор в виде "а я отдыхаю, гуляя по супермаркету, и мне это нравится".

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

Совокупность операций, каждая из которых обязана быть выполнена перед началом следующей, назовем _процессом_ (нет, это не Win32 process, это абстрактное понятие в моем изложении).

Теперь введем понятие _ресурс_. Ресурс — это та сущность, существующая в ограниченном количестве, временное обладание которой необходимо для успешного выполнения операции. Бывает, что для выполнения нужно более одного ресурса, в случае с Ашаном я такого не вижу, но в софте — сплошь и рядом.

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

Все эти сущности ограничены количеством, и временное обладание ими обязательно для исполнения операций. Т.е. это ресурсы, по определению выше.

Если ресурса не хватило — выполнение операции невозможно, и приходится ждать.

Теперь дальше. _Очереди_.

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

Что происходит, если очередь забыли имплементировать? тогда нехватка ресурса для операции N тормозит операцию N-1, т.е. очередь вырастает даже перед N — 1, а не перед N. В худшем случае она вырастает вообще в начале процесса, состоящего из многих операций. Что не есть хорошо, почему — будет сказано ниже.

Теперь дальше. _Узкое место_ (bottleneck)

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

Под _производительностью_ понимается величина, обратная времени выполнения процесса на ненагруженной системе с только одним процессом.

Под _скалабильностью_ понимается характер зависимости времени выполнения процесса системой от количества одновременных процессов, т.е. от нагружки. В идеале это горизонтальная прямая — т.е. время выполнения не зависит от нагрузки. В плохом случае это прямая — т.е. время выполнения растет линейно с нагрузкой. В самом худшем случае, когда случается дефицит сразу многих ресурсов, да они еще и взаимозависимы оказались (скажем, нехватка памяти вызывает трешинг, который откушивает еще и disk bandwidth) — это кривая, растущая быстрее прямой — NlogN, квадрат и так далее.

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

Как оптимизировать конкретные операции? Оптимизация на одну лишь производительность — например, переписывание руками на "близком к ассемблеру Си" особо критичного вычислительного пути типа крипты или обработки картинки — это лишь один способ. Переход на более мощное "железо" — это он же.

Второй способ — _увеличить количество доступных ресурсов_ на эту операцию.

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

Напоследок скажу о типичных бедах со скалабильностью.

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

Пример — операции A и B, перед A есть очередь, перед B она не предусмотрена совсем никак. В этом случае недостаток ресурсов на B приведет к тому, что процессы встанут в очереди перед A, т.е. A голодает, хотя для нее есть все ресурсы.

Особенно плохо, если очередь есть только в самом начале всего процесса. Тогда количество вообще выполняющихся процессов в системе строго определяется самым узким местом. Все остальное — голодает. Все остальные процессы ждут в очереди в самом начале.

Напомню, что лок — это очередь, как и эвент. Очередь ждущих нитей в кернеле.

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

Скажем, выполнять запрос к удаленному серверу под локом — ужасно. Читать из сокета — тоже ужасно — лок удерживается, пока не поступят данные, и все ждут, даже те, кто ничего читать не хочет.