Высокопроизводительный неблокирующий дизайн сервера: альтернативы занятому ожиданию

Question

Я создавал высокопроизводительное серверное приложение для обмена мультимедийными сообщениями, язык реализации - C++. Каждый сервер может использоваться в автономном режиме или многие серверы могут быть объединены для создания оверлейной сети на основе DHT; серверы действуют как супер-пэры, как в случае Skype.

Работа в процессе. В настоящее время сервер может обрабатывать около 200000 сообщений в секунду (256-байтовые сообщения) и имеет максимальную пропускную способность около 256 МБ / с на моей машине (Intel i3 Mobile 2 ГГц, Fedora Core 18 (64-разрядная), 4 ГБ ОЗУ) для сообщения длиной 4096 байт. На сервере есть два потока: один поток для обработки всех операций ввода-вывода (на основе epoll, инициируемый ребром), другой - для обработки входящих сообщений. Существует еще один поток для управления оверлеями, но он не имеет значения в текущем обсуждении.

Обсуждаемые два потока совместно используют данные, используя два кольцевых буфера. Поток № 1 ставит в очередь свежие сообщения для потока № 2, используя один циклический буфер, а поток № 2 возвращает обратно обработанные сообщения через другой циклический буфер. Сервер полностью заблокирован. Я не использую какие-либо примитивы синхронизации, даже атомарные операции.

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

Теперь мой вопрос: поток № 1 ставит в очередь сериализованные сообщения по одному сообщению за раз (фактически, указатели на объекты сообщений), в то время как поток № 2 извлекает сообщения из очереди порциями (куски 32/64/128) и возвращает обратно. обработанные сообщения порциями через второй кольцевой буфер. В случае отсутствия новых сообщений поток #2 продолжает занят, ожидая, следовательно, постоянно удерживая одно из ядер ЦП. Как я могу улучшить дизайн дальше? Каковы альтернативы стратегии занятого ожидания? Я хочу сделать это элегантно и качественно. Я подумал об использовании семафоров, но боюсь, что это не лучшее решение по простой причине, что мне приходится вызывать "sem_post" каждый раз, когда я помещаю сообщение в очередь в потоке #1, что может значительно снизить пропускную способность, второй поток должен Вызовите "sem_post" равное количество раз, чтобы предотвратить переполнение семафора. Также я боюсь, что реализация семафора может использовать мьютекс внутри.

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

О. При выполнении системных вызовов сервер должен тратить минимум циклов ЦП, а системные вызовы должны использоваться минимальное количество раз.

B. Должны быть очень низкие накладные расходы, и алгоритм должен быть эффективным.

C. Никаких блокировок.

Я хочу, чтобы все варианты были представлены на столе.

Вот ссылка на сайт, где я поделился информацией о моем сервере, чтобы лучше понять функциональность и цель: www.wanhive.com

Answer 1

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

Есть некоторые улучшения, которые могут быть сделаны.

1. Если поток № 2 в общем связан с процессором и занят ожиданием - он может быть оштрафован планировщиком (по крайней мере, в Windows и Linux). Планировщик ОС динамически настраивает приоритеты потоков для повышения общей производительности системы. Это уменьшает приоритеты связанных с процессором потоков, которые потребляют большое количество процессорного времени для предотвращения истощения потоков. Вам нужно вручную увеличить приоритет потока #2, чтобы предотвратить это.
2. Если у вас многоядерная или многопроцессорная машина, у вас будет недостаточная подписка на процессоры, и ваше приложение не сможет использовать аппаратный параллелизм. Вы можете смягчить это, используя несколько потоков процессора (поток № 2).

Распараллеливание шага обработки. Есть два варианта.

1. Ваши сообщения полностью упорядочены и должны обрабатываться в том же порядке, в котором они поступили.
2. Сообщения могут быть переупорядочены. Обработка может быть выполнена в любом порядке.

Вам понадобится N циклических буферов и N потоков обработки и N выходных буферов и один потребительский поток в первом случае. Поток #1 помещает в очередь сообщения в циклическом порядке в буферах этого цикла.

// Thread #1 pseudocode
auto message = recv()
auto buffer_index = atomic_increment(&message_counter);
buffer_index = buffer_index % N;  // N is the number of threads
// buffers is an array of cyclic buffers - Buffer* buffers[N];
Buffer* current_buffer = buffers[buffer_index];
current_buffer->euqueue(message);

Каждый поток потребляет сообщения из одного из буферов и помещает результат в свой выделенный буфер вывода.

// Thread #i pseudocode
auto message = my_buffer->dequeue();
auto result = process(message);
my_output_buffer->enqueue(result);

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

// Consumer thread pseudocode
// out_message_counter is equal to message_counter at start
auto out_buffer_index = atomic_increment(&out_message_counter);
out_buffer_index = out_buffer_index % N;
// out_buffers is array of output buffers that is used by processing
// threads
auto out_buffer = out_buffers[out_buffer_index];
auto result = out_buffer->dequeue();
send(result);  // or whatever you need to do with result

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

N должно быть равно num CPU's - 3 в первом случае ("- 3" - один поток ввода-вывода + один потребительский поток + один поток DHT) и num CPU's - 2 во втором случае ("- 2" - один поток ввода-вывода + один поток DHT). Это связано с тем, что ожидание занятости не может быть эффективным, если у вас переподписка процессоров.

Answer 2

Похоже, вы хотите скоординировать продюсера и потребителя, связанных каким-то общим состоянием По крайней мере, в Java для таких шаблонов одним из способов избежать ожидания ожидания является использование wait и notify. При таком подходе поток № 2 может перейти в заблокированное состояние, если обнаружит, что очередь пуста, вызвав функцию wait и избегая вращения ЦП. Как только поток #1 помещает некоторые вещи в очередь, он может сделать уведомление. Быстрый поиск таких механизмов в C++ дает следующее:

ждать и уведомлять в общей памяти C/C++

Answer 3

Вы можете сделать так, чтобы поток № 2 перешел в спящий режим на X миллисекунд, когда очередь пуста.

X можно определить по длине очередей, которые вы хотите + какой-нибудь защитный диапазон.

Кстати, в пользовательском режиме (ring3) вы не можете использовать инструкции MONITOR/MWAIT, которые идеально подойдут для вашего вопроса.

редактировать

Вы обязательно должны попробовать RWlock TBB (есть бесплатная версия). Похоже, что вы ищете.

Edit2

Другой вариант - использовать условные переменные. Они включают мьютекс и состояние. В основном вы ждете при условии, чтобы стать "правдой". Здесь можно найти низкоуровневый материал.