Я надеюсь, что эта статья станет началом цикла заметок о lock-free структурах данных. Я хочу поделиться с хабрасообществом своим опытом, наблюдениям и размышлениями о том, что такое lock-free структуры данных, как их реализовывать, подходят ли концепции контейнеров стандартной библиотеки STL к lock-free контейнерам, и когда стоит (и стоит ли вообще) применять lock-free структуры данных.
Разговор о lock-free структурах данных бессмыслен без освещения таких тем, как атомарные операции, модель памяти, реализованные в том или ином языке программирования (если, конечно, язык достаточно взрослый, чтобы задуматься о своей модели памяти), безопасное освобождение памяти, компиляторы и используемые ими оптимизации, современные архитектуры процессоров, — все эти темы будут в той или иной степени затронуты в данном цикле. Я беру на себя смелость рассказать обо всех этих вещах, хотя не считаю себя абсолютным экспертом ни в одной из них. С другой стороны, не имея представления о них, я не смог бы написать и развивать библиотеку libcds, — open source C++ библиотеку lock-free контейнеров и алгоритмов безопасного освобождения памяти (safe memory reclamation). Cds – это аббревиатура Concurrent Data Structure, а префикс “lib” – это, как ни странно, “library”.
Начну я с истории появления библиотеки. Дело было в далеком 2006 году.
2006 год
Тогда я работал в довольно крупной компании, пишущей софт для одного телекоммуникационного оператора из Большой Тройки. Мы разрабатывали довольно сложные серверные приложения для зоопарка аппаратных платформ, в которых на первом месте стояла (и всегда будет стоять) проблема производительности. Она решалась, в числе прочего, методом распараллеливания обработки данных. Как водится, распараллеливание приводило к возникновению общих (shared) данных, доступ к которым требовалось синхронизировать. Как-то в одном из обсуждений мой коллега походя спросил: “а ты слышал что-нибудь о lock-free очередях?” В то время я не знал об этом ничего. Но, спросив у гугла, нашел несколько статей, в которых приводился псевдокод lock-free очереди. Прочитав их несколько раз, я ничего не понял. Точнее, я перешел в состояние “ничего не понял” после того, как, засучив рукава и сказав “щас!” всему миру (мол, все вы дураки, один я тут умный), я попытался “упростить” алгоритмы, приведя их в соответствие со здравым смыслом. Спустя месяц борьбы с segmentation fault, мой здравый смысл сдался. Вот тогда я и “ничего не понял”. Я не понял, как ЭТО вообще работает, и даже если ОНО как-то работает, как это можно реализовать на C++. Но ведь как-то оно должно работать, иначе умные люди не писали бы эти статьи, и другие умные люди на них бы не ссылались (статьи были научными, и в конце каждой, как водится в научном сообществе, приводились списки литературы). Следуя этим ссылкам, за год я прочитал несколько десятков мегабайт полезной и не очень информации, начиная от software developer guide по процессорным архитектурам и заканчивая обзорными статьями по общим подходам реализации lock-free алгоритмов. Попутно я что-то пописывал (на C++, разумеется) на эту тему, реализуя те или иные примитивы. Следует отметить, что в это время (год 2006-2007) стандарт C++11 ещё оптимистично назывался C++0x, в STL ещё не было атомарных примитивов, да и интерфейс ещё только намечался, а компиляторы иногда капризничали на моих атомарных примитивах и выдавали нерабочий код на особо критичных участках. К 2008 году у меня начали обрисовываться туманные контуры библиотеки libcds. Первые тесты на разных платформах дали обнадёживающие, иногда ошеломительные (“это стало быстрее в 50 раз!!!”), результаты, и я полностью погрузился в мир lock-free. В 2010 я выложил на SourceForge первую (0.5.0) версию библиотеки. На сегодня свежайшая версия библиотеки – 1.4.0, идет работа над версией 1.5.0.
Перейду к общему обзору lock-free структур данных. Итак, основная задача программиста при проектировании и разработке сложных программных проектов, особенно серверных, — наиболее эффективно задействовать все имеющиеся ресурсы целевой платформы. Современный компьютер, даже смартфон или планшет, – это многопроцессорное оборудование, поэтому одним из методов повышения производительности является распараллеливание программы. Параллельные потоки (threads) обрабатывают некие разделяемые данные (shared data); следовательно, нашей основной задачей является организация параллельного доступа к таким разделяемым данным.
В 80-х годах прошлого века было популярно так называемое структурное программирование, позиционировавшееся как метод написания хороших программ. Апологетом структурного программирования был Николас Вирт, автор языка Pascal, написавший бестселлер “Алгоритмы + структуры данных = программы”. Интересно, что эта старая формула указывает на слабое место современных API типа pthreads, Win32 API, предлагаемых операционными системами: API дают средство построения параллельных программ (это средство – потоки, threads), но не дают средств построения параллельных структур данных, обеспечивающих совместный доступ. Вместо этого API предоставляют средства ограничения доступа к данным в виде примитивов синхронизации. Однако синхронизация – это узкое место параллельных программ. По своей сути синхронизация – это антипод параллельности: распараллеливая алгоритмы, мы работаем с последовательными структурами данных, обеспечивая их работу примитивами синхронизации – критическими секциями, мьютексами (mutex), условными переменными (condvar); в результате мы выстраиваем все наши потоки в очередь на доступ к структуре данных, тем самым убивая параллельность. Примитивы синхронизации иногда являются объектами ядра ОС, поэтому обращение к такому объекту может быть очень дорогим: может потребоваться переключение контекста, переход на уровень ядра ОС, поддержка очередей ожидания доступа к защищаемым примитивом синхронизации данным и пр. И все это, быть может, только для того, чтобы поменять в данных значение одного единственного указателя, то есть выполнить одну-две ассемблерных инструкции. Накладные расходы могут быть (по факту и есть) очень велики. Кроме того, не стоит забывать, что объект ядра ОС – это ограниченный по количеству ресурс.
Ещё одним недостатком синхронизации является слабая масштабируемость. При возрастании числа потоков синхронизированный доступ к данным становится узким местом программы; зачастую при увеличении степени параллельности вместо пропорционального увеличения производительности мы получаем её ухудшение в условиях большой нагрузки (high contention).
Руководствуясь формулой Вирта “Алгоритмы + структуры данных = программы”, в своей работе над libcds я сосредоточился только на структурах данных: в библиотеке вы не найдете алгоритмов параллельной сортировки или параллельного for-each. Библиотека содержит только конкурентные структуры данных – очередь, список, map, set и т.п, — и необходимые алгоритмы поддержки lock-free данных, в первую очередь это алгоритмы безопасного освобождения памяти (safe memory reclamation). Зачастую та или иная структура данных представлена несколькими реализациями. Так задумывалось изначально: как правило, существует несколько интересных алгоритмов, реализующих очередь или map, и я не знаю в общем случае, какой из них “лучше”: во-первых, понятие “лучше” или “хуже” относительно и зависит от конкретного железа и конкретной задачи, во-вторых, пока не реализуешь алгоритм и не сравнишь его с другими, не поймешь, лучше он или нет. Ну а если алгоритм реализован и отлажен, то почему бы ему не занять своё место в библиотеке (и предоставить нелегкий выбор пользователю)?..
Лирическое отступление
Кстати, в этом плане у меня претензия к STL: почему, например, map во всех известных мне реализациях STL сделан как red-black tree? Есть много других структур данных, подходящих для реализации map, например, AVL tree, которое является таким же бинарным деревом, но с более сильным критерием сбалансированности (к тому же – наша разработка). Видимо, не только меня мучают такие вопросы: я встречал статьи, в которых сравнивались реализации red-black tree и AVL tree, и выводы в этих статьях были не однозначно в пользу red-black tree: во многих задачах (и на многих архитектурах) AVL tree оказывалось быстрее.
В академической среде изучение способов реализации конкурентных структур данных, обеспечивающих одновременный доступ к разделяемым данным, привело к созданию нескольких основных направлений:
- Lock-free структуры данных;
- Fine-grained algorithms;
- Транзакционная память (transactional memory)
В libcds нет реализаций, основанных на транзакционной памяти. Транзакционная память – это обширная область исследований, нацеленная в основном на будущее. Алгоритмы, основанные на транзакционной памяти, подразумевают, грубо говоря, что память поддерживает атомарные транзакции, которые можно атомарно принять (commit) или отклонить (rollback). Очевидно, что такая память должна быть реализована в железе; существующие софтверные реализации, по признанию самих исследователей, не обладают достаточной производительностью. Ради справедливости стоит отметить, что процессоры Intel архитектуры Haswell уже имеют поддержку транзакционности в своей системе команд, так что стоит ожидать, что расцвет алгоритмов, построенных на принципах транзакционной памяти, не за горами.
Fine-grained алгоритмы – это изощренные методы синхронизации, как правило, построенные не на применении примитивов синхронизации, предоставляемых OC, а на применении “легких” атомарных примитивов, например, на spin-lock. На основе таких примитивов строятся структуры данных, допускающие параллельное чтение или даже параллельную запись, в которых синхронизация производится на уровне узла (node) или страницы (page, bucket) структуры данных и встроена в сами алгоритмы операций над этой структурой. Часто fine-grained контейнеры показывают производительность, сравнимую с производительностью lock-free контейнеров при относительно небольшой нагрузке. Библиотека libcds не брезгует такими структурами данных.
Lock-free структурами данных я буду называть структуры данных, не требующие внешней синхронизации доступа. Это неформальное, чисто техническое определение, отражающее внутреннее строение контейнера и операций над ним. Слово “внешней” здесь выделено намеренно: надо понимать, что вовсе без применения специальной поддержки со стороны процессора lock-free структуры данных построить, скорее всего, не удастся. Но поддержка такого рода в lock-free контейнерах обеспечивается не синхронизацией доступа к последовательным методам контейнера, а механизмом атомарной модификации, зашитым внутрь методов контейнера, либо внутренней синхронизацией на уровне составных частей контейнера (узлов, buckets, страниц).
Формальное определение lock-free объекта звучит так [Her91]: разделяемый объект называется lock-free объектом (неблокируемым, non-blocking объектом), если он гарантирует, что некоторый поток закончит выполнение операции над объектом за конечное число шагов вне зависимости от результата работы других потоков (даже если эти другие потоки завершились крахом). Более строгое понятие wait-free объекта гласит: объект является wait-free, если каждый поток завершит операцию над объектом за конечное число шагов. Условие lock-free гарантирует продвижение как минимум какого-то одного потока, тогда как более сильное условие wait-free гарантирует успешное выполнение для всех потоков. В теории конкурентных структур данных существует также понятие linearizability [Her90], играющее важную роль в формальных доказательствах корректности lock-free алгоритмов. Грубо говоря, алгоритм является линеаризуемым (linearizable), если результат его работы виден по окончании алгоритма. Например, результат вставки в список виден по окончании функции вставки. Звучит по-идиотски, но возможно придумать алгоритм, который делает вставку в список и не является линеаризуемым. Например, всякого рода буферизация может привести к нарушению этого свойства: вместо вставки мы можем поместить новый элемент в некий буфер, дать команду другому потоку “вставь элемент из буфера в список” и не ждать, когда элемент будет вставлен; или же мы будем вставлять только тогда, когда в буфере накопится достаточное число элементов. Тогда по окончании функции вставки в список мы не можем гарантировать, что элемент находится в списке; всё, что мы можем гарантировать, это что элемент непременно будет (будущее время!) вставлен в список сейчас или позже.
Эти понятия широко используются в научно-исследовательских работах; моя статья не претендует на звание научно-исследовательской, поэтому я буду применять термин lock-free в “обывательском” смысле для обозначения класса конкурентных контейнеров, построенных без применения традиционных шаблонов синхронизации, либо не требующих внешней синхронизации.
Лирическое отступление 2 - О времени
Следует отметить, что понятие времени (причинно-следственных связей) как-то размыто в lock-free структурах данных. При традиционном подходе мы действуем так: блокируем доступ к контейнеру, что-то с ним делаем (например, добавляем элемент), разблокируем. В момент разблокировки мы знаем, что вставленный элемент находится в контейнере. В lock-free контейнере всё не так. Нам не нужно блокировать доступ, мы просто вызываем метод добавления. Если он возвратил true, значит, вставка прошла успешно. Но это не значит, что элемент находится в контейнере, — он уже может быть удален конкурирующим потоком. Это демонстрирует важное отличие lock-free контейнеров от традиционных a la STL, — мы не можем вытаскивать внутренности реализации контейнера наружу; например, концепция итераторов, широко используемая в STL, не применима к конкурентным структурам данных. Я надеюсь подробно обсудить построение интерфейсов классов конкурентных контейнеров в одной из следующих статей.
Чем же характеризуются lock-free алгоритмы? Пожалуй, первое, что бросается в глаза – это их сложность. Вы представляете, что из себя представляет обычная очередь, реализованная на односвязном списке? Очень простой код:
Показать очень простой код
struct Node {
Node * m_pNext ;
};
class queue {
Node * m_pHead = nullptr;
Node * m_pTail = nullptr;
public:
queue() {}
void enqueue( Node * p )
{
if ( m_pTail )
m_pTail->m_pNext = p;
p->m_pNext = nullptr ;
m_pTail = p ;
if ( !m_pHead )
m_pHead = p ;
}
Node * dequeue()
{
if ( !m_pHead ) return nullptr ;
Node * p = m_pHead ;
m_pHead = p->m_pNext ;
if ( !m_pHead )
m_pTail = nullptr ;
return p ;
}
};
Можно написать и ещё короче. А вот как выглядят методы enqueue/dequeue (синонимы push/pop) реализации классического алгоритма lock-free очереди Майкла & Скотта ([Mic96], код взят с минимальными сокращениями из класса
cds::intrusive::MSQueue библиотеки libcds):
Показать то же самое, но написанное очень громоздко
bool enqueue( value_type& val )
{
node_type * pNew = node_traits::to_node_ptr( val ) ;
typename gc::Guard guard ;
back_off bkoff ;
node_type * t ;
while ( true ) {
t = guard.protect( m_pTail, node_to_value() ) ;
node_type * pNext = t->m_pNext.load(memory_model::memory_order_acquire) ;
if ( pNext != null_ptr<node_type *>() ) {
// Tail is misplaced, advance it
m_pTail.compare_exchange_weak( t, pNext, memory_model::memory_order_release,
CDS_ATOMIC::memory_order_relaxed ) ;
continue ;
}
node_type * tmp = null_ptr<node_type *>() ;
if ( t->m_pNext.compare_exchange_strong( tmp, pNew, memory_model::memory_order_release,
CDS_ATOMIC::memory_order_relaxed ))
{
break ;
}
bkoff() ;
}
++m_ItemCounter ;
m_pTail.compare_exchange_strong( t, pNew, memory_model::memory_order_acq_rel,
CDS_ATOMIC::memory_order_relaxed );
return true ;
}
value_type * dequeue()
{
node_type * pNext ;
back_off bkoff ;
typename gc::template GuardArray<2> guards ;
node_type * h ;
while ( true ) {
h = guards.protect( 0, m_pHead, node_to_value() ) ;
pNext = guards.protect( 1, h->m_pNext, node_to_value() ) ;
if ( m_pHead.load(memory_model::memory_order_relaxed) != h )
continue ;
if ( pNext == null_ptr<node_type *>() )
return NULL ; // empty queue
node_type * t = m_pTail.load(memory_model::memory_order_acquire);
if ( h == t ) {
// It is needed to help enqueue
m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release,
CDS_ATOMIC::memory_order_relaxed ) ;
continue ;
}
if ( m_pHead.compare_exchange_strong( h, pNext,
memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
{
break ;
}
bkoff() ;
}
--m_ItemCounter ;
dispose_node( h ) ;
return pNext ;
}
Алгоритм сложный. Тот же односвязный список, но даже простое визуальное сравнение обычной и lock-free очереди уже кое о чём говорит. В lock-free очереди мы видим:
- бесконечный цикл – мы пытаемся выполнить операцию, пока не получится. Это типичный паттерн применения атомарной операции
compare_exchange; - защиту локальных переменных (
guards) с помощью одного из методов безопасной работы с памятью (указателями) в lock-free алгоритмах, в данном случае – это метод Hazard Pointers; - применение атомарных примитивов C++11 –
load, compare_exchange, барьеров памятиmemory_order_xxx; - helping — очень распространенный прием в lock-free алгоритмах, когда один поток помогает другому сделать его работу;
- применение back-off стратегий (функтор
bkoff), которые не являются обязательными, но позволяют в некоторых случаях существенно разгрузить процессор в условиях сильной нагрузки, когда много потоков обращаются к очереди одновременно
Сейчас я не буду ничего объяснять, так как все эти вещи весьма обширные и требуют отдельного разговора. Пусть сохранится интрига. Я надеюсь осветить эти темы в будущих статьях.
Следующая статья будет посвящена краеугольному понятию, на котором основаны все lock-free структуры данных, — атомарности и атомарным примитивам.
И напоследок – полезные книги (не статьи), в которых, с моей точки зрения, наиболее полно освещены вопросы конкурентного программирования.
На сегодняшний момент мне известны две хорошие работы:
1. Nir Shavit, Maurice Herlihy The Art of Multiprocessor programming. Перевода на русский язык, насколько я знаю, нет. Книга очень известных в мире lock-free авторов описывает множество параллельных алгоритмов и способов их построения. Все примеры на Java, поэтому авторам не пришлось заботиться об освобождении памяти, модели памяти C++ (в Java модель памяти более строгая) и прочих вещах, которые в Java внедрены в сам язык, а в C++ всё это приходится писать самому. Несмотря на это, книга очень полезная.
2. Anthony Williams C++ Concurrency in Action (есть русский перевод). Книга известного в мире C++ автора посвящена вопросам multithread programming именно в C++, доступно описывает новый стандарт C++11 и новые возможности, предоставляемые стандартом для реализации параллельных алгоритмов. Настоятельно рекомендуется к прочтению.
Ссылки:
[Her90] M. Herlihy, J. M. Wing Linearizability: A Correctness Condition for Concurrent Objects, ACM Transactions on Programming Languages and Systems, 1990
[Her91] M. Herlihy A Methodology for Implementing Highly Concurrent Data Object, 1991
[Mic96] M.Michael, M.Scott Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms
Lock-free структуры данных
