Тема в Низкоуровневом Программировании про переполнение очереди меня сильно расстроила. Почему-то напомнила о всяких ЕГАИСах и прочих дико тормозных системах.
Потому начинаю серию постов о том, как оптимизировать архитектуры (не только низкоуровневые, хотя речь все боле о них) на производительность в условиях большого числа входящих извне реквестов, т.е. на scalability.
Пункт первый. "Ресурсный" подход.
Что такое массовое обслуживание — видели все в Ашанах, аэропортах и тому подобных местах. Изложу на пальцах некие азы теории оного массового обслуживания.
От чего зависит общее время, которое человек тратит на покупку в Ашане? выясним это. Сразу отметем для простоты субъективный фактор в виде "а я отдыхаю, гуляя по супермаркету, и мне это нравится".
Для начала, покупка состоит из _операций_:
а) въехать на парковку
б) найти место и запарковаться
в) найти пустую тележку
г) войти в зал
д) пройти по аллеям, собрав товар в тележку
е) пройти кассу и оплатить товар
ж) выйти из зала
з) доволочь тележку до машины
и) перегрузить покупку в багажник
к) выехать с парковки
Совокупность операций, каждая из которых обязана быть выполнена перед началом следующей, назовем _процессом_ (нет, это не Win32 process, это абстрактное понятие в моем изложении).
Теперь введем понятие _ресурс_. Ресурс — это та сущность, существующая в ограниченном количестве, временное обладание которой необходимо для успешного выполнения операции. Бывает, что для выполнения нужно более одного ресурса, в случае с Ашаном я такого не вижу, но в софте — сплошь и рядом.
Что у нас за ресурсы есть для операций процесса "покупка в гипермаркете"?
а) место на проезжей части
б) место на парковке
в) тележка
г) метр ширины входа в зал
д) метр ширины аллеи
е) время кассиршы, нужное для обслуживания одной покупки
ж) опять метр ширины входа
з) метр ширины проходов на парковке
и) время, нужное на эту тупую работу руками, т.е. "ручное время", по аналогии с процессорным
к) опять место на проезжей части.
Все эти сущности ограничены количеством, и временное обладание ими обязательно для исполнения операций. Т.е. это ресурсы, по определению выше.
Если ресурса не хватило — выполнение операции невозможно, и приходится ждать.
Теперь дальше. _Очереди_.
Очередь — это состояние, предназначенное для ожидания доступности ресурса для выполнения операции, и техсредства поддержки этого ожидания. В реале с "техсредствами" обычно проблем нет — очередь из людей вырастает везде и где угодно. В софте — нужно оную очередь действительно имплементировать, сама не вырастет.
Что происходит, если очередь забыли имплементировать? тогда нехватка ресурса для операции N тормозит операцию N-1, т.е. очередь вырастает даже перед N — 1, а не перед N. В худшем случае она вырастает вообще в начале процесса, состоящего из многих операций. Что не есть хорошо, почему — будет сказано ниже.
Теперь дальше. _Узкое место_ (bottleneck)
Узкое место процесса — это та операция, которая в реальном сценарии под большой нагрузкой дает максимальный вклад во время выполнения процесса. Такое происходит, либо когда ресурсом для этой операции является само по себе время в больших количествах (одна рука забинтована, долго перекладывать покупку в багажник), либо же когда ресурс не является временем, но в данном сценарии под нагрузкой находится в хроническом дефиците.
Под _производительностью_ понимается величина, обратная времени выполнения процесса на ненагруженной системе с только одним процессом.
Под _скалабильностью_ понимается характер зависимости времени выполнения процесса системой от количества одновременных процессов, т.е. от нагружки. В идеале это горизонтальная прямая — т.е. время выполнения не зависит от нагрузки. В плохом случае это прямая — т.е. время выполнения растет линейно с нагрузкой. В самом худшем случае, когда случается дефицит сразу многих ресурсов, да они еще и взаимозависимы оказались (скажем, нехватка памяти вызывает трешинг, который откушивает еще и disk bandwidth) — это кривая, растущая быстрее прямой — NlogN, квадрат и так далее.
Теперь практические рекомендации. То, что надо проанализировать, из каких операций состоит процесс — понятно. То, что надо найти узкое место — тоже понятно. Начинать оптимизацию надо с текущего узкого места, потом заниматься тем, которое второе по "узости" (особенно если оно после первого шага стало первым), и так далее.
Как оптимизировать конкретные операции? Оптимизация на одну лишь производительность — например, переписывание руками на "близком к ассемблеру Си" особо критичного вычислительного пути типа крипты или обработки картинки — это лишь один способ. Переход на более мощное "железо" — это он же.
Второй способ — _увеличить количество доступных ресурсов_ на эту операцию.
Скажем, если в Ашане растут очереди, они могут либо еще кассы поставить, либо выгнать кассирш и набрать более расторопных
Оптимизация кода в вычислительном смысле, а также замена процессора на более мощный — это второй путь. Но зачастую есть и первый.
Напоследок скажу о типичных бедах со скалабильностью.
Голодание (starvation) — это ситуация, когда операция не может быть выполнена, хотя для нее есть ресурсы, и причина невозможности — это проблемы в каких-то других частях системы.
Пример — операции A и B, перед A есть очередь, перед B она не предусмотрена совсем никак. В этом случае недостаток ресурсов на B приведет к тому, что процессы встанут в очереди перед A, т.е. A голодает, хотя для нее есть все ресурсы.
Особенно плохо, если очередь есть только в самом начале всего процесса. Тогда количество вообще выполняющихся процессов в системе строго определяется самым узким местом. Все остальное — голодает. Все остальные процессы ждут в очереди в самом начале.
Напомню, что лок — это очередь, как и эвент. Очередь ждущих нитей в кернеле.
Таким образом, использование "большого лока", под которым выполняются крупные и медленные пути кода — это плохо. Очень плохо. Правильно — разбить путь на операции, и выполнять под локом только некоторые из них, а еще лучше — еще и разобраться со своими данными и защитить их несколькими локами (каждый защищает свою часть данных) вместо одного. Это повышает скалабильность.
Скажем, выполнять запрос к удаленному серверу под локом — ужасно. Читать из сокета — тоже ужасно — лок удерживается, пока не поступят данные, и все ждут, даже те, кто ничего читать не хочет.
Здравствуйте, Maxim S. Shatskih, Вы писали:
MSS>Совокупность операций, каждая из которых обязана быть выполнена перед началом следующей, назовем _процессом_ (нет, это не Win32 process, это абстрактное понятие в моем изложении).
MSS>Теперь введем понятие _ресурс_. Ресурс — это та сущность, существующая в ограниченном количестве, временное обладание которой необходимо для успешного выполнения операции. Бывает, что для выполнения нужно более одного ресурса, в случае с Ашаном я такого не вижу, но в софте — сплошь и рядом.
В контексте этого стоит упомянуть GPSS — General Purpose Simulation System
GPSS — там же можно качнуть
GPSS позволяет моделировать именно такие модели — модели массового обслуживания.
Идея следующая. Рисуется граф системы из ресурсов, очередей и связей. Задаются параметры модели — времена обработки на каждом ресурсе, кол-во ресурсов и т.д. Задаются параметры рабочей нагрузки — частота и распределение входящих запросов.
Далее всё это запускается на моделирование — продвинутые системы даже визуализируют процесс.
На выходе имеем множество статистических параметров: среднее время обработки, отклонение времени, загрузка ресурсов, длины очередей перед ресурсами и т.д.
Эта информация достаточно легко читается и интерпретируется.
Далее можно пробовать модифицировать параметры система — "А что если мы увеличим в два раза кол-во памяти?", "А что если мы ускорим процесс шифрования в два раза?" и т.д. Далее опять запускается моделирование и смотрится какой результат дало изменение.
Первоначальное составление адекватной модели достаточно трудоёмко, зато потом пользоваться ей одно удовольствие.
Здравствуйте, Maxim S. Shatskih, Вы писали:
MSS>Напомню, что лок — это очередь, как и эвент. Очередь ждущих нитей в кернеле.
MSS>Таким образом, использование "большого лока", под которым выполняются крупные и медленные пути кода — это плохо. Очень плохо. Правильно — разбить путь на операции, и выполнять под локом только некоторые из них, а еще лучше — еще и разобраться со своими данными и защитить их несколькими локами (каждый защищает свою часть данных) вместо одного. Это повышает скалабильность.
MSS>Скажем, выполнять запрос к удаленному серверу под локом — ужасно. Читать из сокета — тоже ужасно — лок удерживается, пока не поступят данные, и все ждут, даже те, кто ничего читать не хочет.
Первое, что стоит советовать, это всё же, имхо, — надо постараться избавиться от локов (т.е. от разделения данных) вообще (если это возможно).
Методы:
— Патрицирование данных. Есть 4 потока. Каждый поток обрабатывает данные только для четверти пользователей. Соотв. разбиваем массив с сессиями на 4. К каждой части теперь вообще не нужна синхронизация, т.к. с ней работает только один поток. Это так же очень положительно сказывается на локальности данных. При таком подходе можно даже получать сверх-линейную скалабилити — т.е. на 4 ядрах производительность повышается в 5 раз.
— Использование TLS. Копируем данные каждому потоку в TLS. Синхронизация при работе с ними не нужна. Если необходима какая-то агрегация этих данных, то делаем её отдельно.
— Константные данные. Выделяем часть константных (редкоменяющихся данных). Синхронизация при доступе к ним не нужна.
И т.д.
Если избавиться от синхронизации не получается, то только тогда можно переходить в оптимизации синхронизации:
— Правильная гранулярность. Не слишком много и не слишком мало локов.
— Правильные примитивы синхронизации.
— Минимальное время в критической секции. О блокирующих операциях внутри критической секции не может быть и речи.
R> — Патрицирование данных. Есть 4 потока. Каждый поток обрабатывает данные только для четверти пользователей. Соотв. разбиваем массив с сессиями на 4. К каждой части теперь вообще не нужна синхронизация, т.к. с ней работает только один поток. Это так же очень положительно сказывается на локальности данных. При таком подходе можно даже получать сверх-линейную скалабилити — т.е. на 4 ядрах производительность повышается в 5 раз.
+1
Еще хорошо привязать каждую нить обработчика к своему CPU по affinity.
Но... дело в том, что локи часто охраняют не сами данные, а _структуры управления этим самым партицированием_
. Да, там будет очень короткий код под локом (к чему стоит стремиться). Но даже и туда может попасть priority inversion.
R> — Использование TLS. Копируем данные каждому потоку в TLS. Синхронизация при работе с ними не нужна.
Конечно. Можно даже без TLS — при создании треда ему передается параметр, параметр есть указатель, указатель на твою структуру, куда можно положить еще и указатели на данные. Так ИМХО красивее, чем с использованием лишних фич ОС.
TLS нужна все больше для случая, когда нить порождена _над тобой_, например — внутри OLE32 или RPCRT4.
R>Если необходима какая-то агрегация этих данных, то делаем её отдельно.
Угу, и там придется под локом пощупать некие управляющие структуры.
R> — Минимальное время в критической секции. О блокирующих операциях внутри критической секции не может быть и речи.
+1
Здравствуйте, Maxim S. Shatskih, Вы писали:
BZ>>очень полезная вещь, особенно в наши времена всепорникающих сетей и мультиядерности. надеюсь, потом ты сведёшь это в статью для rsdn?
MSS>Ну тут много критики, если сводить в статью — то с ней. Не знаю, когда руки дойдут.
верблюд — это лошадь, созданная комитетом
имхо, тебе надо сводить в статью свою точку зрения — то, что ты писал в заглавных статьях, плюс возможно дополнительные разъяснения/уточнения, которые ты давал позже. те, кто считает иначе, могут писать свои собственные статьи. речь идёт о том, чтобы документально оформить _твой_ подход
