В современном многопоточном программировании одним из фундаментальных вызовов является эффективная синхронизация доступа к общим данным, когда существует один поток записи и множество потоков чтения. За последние годы появилось несколько популярных методов решения этой задачи, среди которых выделяются техники Left-Right и Seq-Lock. Каждая из них имеет свои сильные и слабые стороны, и объединение их преимуществ позволяет создать более совершенный алгоритм, который усиливает как производительность, так и надежность в условиях высокой конкуренции потоков. Начнем с разбора того, что такое Left-Right алгоритм. Этот подход использует две копии данных, между которыми переключаются читатели и писатель.
Идея в том, что пока один экземпляр структуры данных находится в состоянии модификации, читатели работают с другим, что исключает блокировки читателей со стороны писателя. Недостатком Left-Right является необходимость хранить и обновлять две копии данных, что увеличивает затраты по памяти и иногда время обновления, так как приходится делать две записи данных по очереди. С другой стороны, Seq-Lock — это метод, который основан на использовании счетчика последовательности, который писатель увеличивает до и после изменений. Читатели во время чтения смотрят на этот счетчик до чтения данных и после, чтобы убедиться, что данные не изменялись во время их чтения. Преимущество Seq-Lock в том, что писатель никогда не блокируется, а читатели не требуют пометки своего присутствия в памяти, что снижает накладные расходы и повышает производительность.
Однако читатели иногда могут задерживаться из-за состояний, когда писатель был прерван посреди изменений, и читатель получает неконсистентные данные. Что произойдет, если объединить Left-Right и Seq-Lock? Такой гибридный подход позволяет добиться того, чтобы ни писатель, ни читатели не блокировались взаимно ни в каком состоянии. В основе метода лежит использование двух копий данных, как в Left-Right, и счетчика изменений, как в Seq-Lock. Писатель меняет данные в одной из копий, увеличивая счетчик после каждого обновления. Читатель читает счетчик, чтобы определить, с какой копией работать, и может легко понять, не было ли изменение во время чтения данных.
В результате такой метод сохраняет преимущества обеих техник. Писатель не блокируется ожиданием окончаний чтения, а читатели могут работать без значительных ожиданий, что существенно повышает общую производительность системы при высокой конкуренции потоков. Кроме того, поскольку сохраняется семантика Seq-Lock, читатели не записывают данные в память своего присутствия, что снижает конфликты записи, особенно на процессорах семейства x64, где используется оптимистичный подход к синхронизации через операции memory_order_acquire и memory_order_release. Важный аспект — семантика и гарантии согласованности данных. Гибридный алгоритм, как и Seq-Lock, не гарантирует жёсткий глобальный порядок всех операций, но обеспечивает упорядоченность всех операций записи, поскольку в системе только один писатель.
Для читателей гарантируется, что они прочитают только валидные данные, записанные писателем. При необходимости можно использовать дополнительные барьеры памяти (atomic_thread_fence с memory_order_seq_cst) для усиления последовательной согласованности, что помогает разработчикам создавать более строгие модели синхронизации при необходимости. На практике такой подход представлен в виде легковесной C++ библиотеки, которая реализует шаблон left_right_seq. Она позволяет защитить сложные структуры данных с атомарными полями, сохраняя инварианты и обеспечивая эффективные операции чтения и записи. Примером может служить структура, содержащая несколько атомарных числовых полей с некоторой внутренней зависимостью, например сумма из двух чисел.
Использование библиотечного интерфейса достаточно интуитивно: для записи вызывается метод write, которому передается функция обновления данных. Записи выполняются с relaxed memory order операциями, поскольку дополнительные барьеры и защита обеспечиваются библиотекой. Для чтения используется метод read, который принимает функцию обработки данных в безопасном и консистентном состоянии. В случае обнаружения несовпадений данных или изменений между проверками, функция может быть повторена для получения валидного снимка. Такой способ синхронизации подходит для множества сценариев, где сильная конкуренция потоков обращается к одним и тем же данным, а важно минимизировать задержки со стороны читателей и писателя.
