Доброго времени суток, хабражители!
Этот пост есть краткий конспект многих часов раздумий, каляк на бумаге, набросков кода и, в конце-концов, реально работающего кода в продакшене.
Наш сайт (и далее — просто сайт) активно использует мемкеш для горячих данных. Код, заполняющий мемкеш, может работать очень долго (0,5 секунд — это долго) и при этом пользовательские запросы успевают запустить ещё сотню процедур обновления. Последстия понятны, однако долго мы просто не могли их заметить на уровне общей нагрузки. Только когда мы увидели всплески времени на обслуживание некоторых запросов (от возросшей нагрузки они ещё и попадали в SLOW_QUERIES_LOG MySQL) — тогда и закипела работа.

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

Мне по работе часто приходится сталкиваться с высоконагруженными многопоточными или многопроцессными сервисами (application-, web-, index-server).
Достаточно интересная, но иногда неблагодарная работа — оптимизировать все это хозяйство.
Растущие потребности клиентов часто упираются в невозможность просто заменить железную составляющую системы на более современную, т.к. производительность компьютеров, скорость чтения-записи жестких дисков и сети растут много медленнее запросов клиентов.
Редко помогает увеличение количества нодов кластера (система как правило распределенная).
Чаще приходится запустив профайлер, искать узкие места, лезть в source code и править ляпы, которые оставили коллеги, а иногда и сам, чего греха таить, много лет назад.
Некоторые из проблем, связаных с синхронизацией, я попытаюсь изложить здесь. Это не будет вводный курс по многопоточному программированию — предпологается, что читатель знаком с понятием thread и context switch, и знает для чего нужны mutex, semaphore и т.д.

Джефф Прешинг (Jeff Preshing) опубликовал отличную демонстрацию, как нормальный код C++ возвращает непредсказуемый результат на многоядерных процессорах со слабо упорядоченной обработкой очереди запросов (Weakly-Ordered CPU), то есть на ARM-процессорах. Например, на iPhone или каком-нибудь современном Android-устройстве.

Простая программа C++ с двумя потоками 20.000.000 раз прибавляет единичку к значению, защищённому мьютексом, — и каждый раз на выходе получается разный результат, который меньше 20.000.000!



Как говорится, наш враг — CPU.

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

В результате стандартный консервативный аллокатор выстраивает все запросы в очередь на pthread_mutex / critical section. И наш многоядерный процессор медленно и печально едет на первой передаче.

И что с этим делать? Познакомимся поближе с деталями реализации метода Scalable Lock-Free Dynamic Memory Allocation. Maged M. Michael. IBM Thomas J. Watson Research Center.

Самый простой код что я сумел найти — написан под LGPL камрадами Scott Schneider и Christos Antonopoulos. Его и рассмотрим.

На хабре уже было несколько статей про lock-free алгоритмы. Этот пост — это перевод статьи моего коллеги, которую мы планируем публиковать в нашем корпоративном блоге. По роду деятельности мы пишем огромное количество lock-free алгоритмов и структур данных, и этой статьей хочется показать, насколько это интересно и сложно одновременно.



Эта статья во многом похожа на эту статью, но в той статье рассматриваются не все проблемы, с которыми можно столкнуться, разрабатывая lock-free структуры данных, и уделяется очень мало внимания решению этих проблем. В этой статье хочется детально остановиться на некоторых решениях, которые мы используем в реальной реализации lock-free структур данных в нашем продукте, и больше внимания уделить оценке производительности.

Постановка задачи

Один из алгоритмов, который я реализовывал, имел интересные особенности при работе с памятью:

• Могло выделяться огромное количество, до десятков и сотен миллионов небольших объектов одного типа.
• Объекты представляли собой POD- типы.
  
  POD

  A Plain Old Data Structure in C++ is an aggregate class that contains only PODS as members, has no user-defined destructor, no user-defined copy assignment operator, and no nonstatic members of pointer-to-member type.
• Заранее было неизвестно какое количество объектов понадобится, могло так случится, что потребуется сотня, а может и сто миллионов.
• Объекты никогда не удаляются по одному, в какой-то момент они становятся не нужны все сразу.
• Алгоритм хорошо распараллеливается, по этому выделением объектов занимается одновременно несколько потоков, по количеству ядер процессора(ов).

Использование в таких условиях стандартного new – delete приводит к очень большим потерям времени на удаление объектов. Если без отладчика удаление происходило хотя бы за несколько секунд, то в присутствии отладчика освобождение памяти замедляется примерно в 100(!) раз, и отладка проекта становится просто невозможной. Кроме того из-за большого количества выделенных объектов достаточно ощутимым становился перерасход памяти на внутренние данные распределителя памяти.
Для решения задачи выделения огромного количества объектов одного типа, и их пакетного удаления, был сделан lock-free контейнер MassAllocator. Код компилируется Visual Studio 2012. Полный код проекта выложен на github.

Я надеюсь, что эта статья станет началом цикла заметок о lock-free структурах данных. Я хочу поделиться с хабрасообществом своим опытом, наблюдениям и размышлениями о том, что такое lock-free структуры данных, как их реализовывать, подходят ли концепции контейнеров стандартной библиотеки STL к lock-free контейнерам, и когда стоит (и стоит ли вообще) применять lock-free структуры данных.

Построение lock-free структур данных зиждется на двух китах – атомарных операциях и способах упорядочения доступа к памяти. В этой статье речь пойдет об атомарности и атомарных примитивах.

Анонс. Спасибо за теплый прием Начал! Вижу, что тема lock-free интересна хабрасообществу, это меня радует. Я планировал построить цикл по академическому принципу, плавно переходя от основ к алгоритмам, попутно иллюстрируя текст кодом из libcds. Но часть читателей требует зрелищ не мешкая показать, как пользоваться библиотекой, особо не рассусоливая. Я согласен, в этом есть свой резон. В конечном счете, и мне не так интересно, что там внутри boost, — опишите, как его применять! Поэтому свой эпический цикл я разделю на три части: Основы, Внутри и Извне. Каждая статья эпопеи будет относится к одной из частей. В Основах будет рассказываться о низкоуровневых вещах, вплоть до строения современных процессоров; это часть для почемучек вроде меня. Внутри будет освещать интересные алгоритмы и подходы в мире lock-free, — это скорее теория о том, как реализовать lock-free структуру данных, libcds будет неисчерпаемым источником C++ кода. В Извне будут статьи о практике применения libcds, — программные решения, советы и FAQ. Извне будет питаться вашими вопросами/замечаниями/предложениями, дорогие хабражители.

А пока я судорожно готовлю начало Извне, — первая часть Основ. Статья во многом не о C++ (хотя и о нем тоже) и даже не о lock-free (хотя без atomic lock-free алгоритмы неработоспособны), а о реализации атомарных примитивов в современных процессорах и о базовых проблемах, возникающих при использовании таких примитивов.
Атомарность — это первый круг ада низкий уровень из двух.

Как только я заинтересовался lock-free алгоритмами, меня стал мучить вопрос – а откуда взялась необходимость в барьерах памяти, в «наведении порядка» в коде?
Конечно, прочитав несколько тысяч страниц руководств по конкретной архитектуре, мы найдем ответ. Но этот ответ будет годен для этой конкретной архитектуры. Есть ли общий? В конце концов, мы же хотим, чтобы наш код был портабелен. Да и модель памяти C++11 не заточена под конкретный процессор.
Наиболее приемлемый общий ответ дал мне мистер Paul McKenney в своей статье 2010 года Memory Barriers: a Hardware View of Software Hackers. Ценность его статьи – в общности: он построил некоторую упрощенную абстрактную архитектуру, на примере которой и разбирает, что такое барьер памяти и зачем он был введен.
Вообще, Paul McKenney – известная личность. Он является разработчиком и активным пропагандистом технологии RCU, которая активно используется в ядре Linux, а также реализована в последней версии libcds в качестве ещё одного подхода к безопасному освобождению памяти (вообще, о RCU я хотел бы рассказать отдельно). Также принимал участие в работе над моделью памяти C++11.
Статья большая, я даю перевод только первой половины. Я позволил себе добавить некоторые комментарии, [которые выделены в тексте так].

В этой статье я даю краткий обзор того, как применять библиотеку lock-free структур данных libcds. В реализацию я углубляться здесь не буду, — это просто взгляд извне, взгляд со стороны пользователя библиотеки.

Библиотека libcds имеет свою точку зрения на многие известные структуры данных. Отчасти это объясняется целевой областью – lock-free структуры данных довольно минималистичны по набору предоставляемых методов, — отчасти желанием выйти за ограничения и решения стандартной библиотеки STL. Что из этого получилось – решать пользователям libcds.

Кому интересно – добро пожаловать под кат

В предыдущей статье мы заглянули внутрь процессора, пусть и гипотетического. Мы выяснили, что для корректного выполнения параллельного кода процессору необходимо подсказывать, до каких пределов ему разрешено проводить свои внутренние оптимизации чтения/записи. Эти подсказки – барьеры памяти. Барьеры памяти позволяют в той или иной мере упорядочить обращения к памяти (точнее, кэшу, — процессор взаимодействует с внешним миром только через кэш). “Тяжесть” такого упорядочения может быть разной, — каждая архитектура может предоставлять целый набор барьеров “на выбор”. Используя те или иные барьеры памяти, мы можем построить разные модели памяти — набор гарантий, которые будут выполняться для наших программ.

В этой статье мы рассмотрим модель памяти C++11.

Как я упоминал в своих предыдущих заметках, основными трудностями при реализации lock-free структур данных являются ABA-проблема и удаление памяти. Я разделяю эти две проблемы, хоть они и связаны: дело в том, что существуют алгоритмы, решающие только одну из них.
В этой статье я дам обзор известных мне методов безопасного удаления памяти (safe memory reclamation) для lock-free контейнеров. Демонстрировать применение того или иного метода я буду на классической lock-free очереди Майкла-Скотта [MS98].

В этой статье я продолжу знакомить хабрасообщество с техниками, обеспечивающими написание lock-free контейнеров, попутно рекламируя (надеюсь, не слишком навязчиво) свою библиотеку libcds.

Речь пойдет об ещё одной технике безопасного освобождения памяти для lock-free контейнеров — RCU. Эта техника существенно отличается от рассмотренных ранее алгоритмов a la Hazard Pointer.

Read – Copy Update (RCU) – техника синхронизации, предназначенная для «почти read-only», то есть редко изменяемых, структур данных. Типичными примерами такой структуры являются map и set – в них большинство операций является поиском, то есть чтением данных. Считается, что для типичного map'а более 90% вызываемых операций — это поиск по ключу, поэтому важно, чтобы операция поиска была наиболее быстрой; синхронизация поиска в принципе не нужна — читатели при отсутствии писателей могут работать параллельно. RCU обеспечивает наименьшие накладные расходы как раз для read-операций.

Откуда взялось название Read – Copy Update? Первоначально идея была очень проста: есть некоторая редко изменяемая структура данных. Если нам требуется изменить её, то мы делаем её копию и производим изменение — добавление или удаление данных — именно в копии. При этом параллельные читатели работают с первоначальной, не измененной структурой. В некоторый безопасный момент времени, когда нет читателей, мы можем подменить структуру данных на измененную копию. В результате все последующие читатели будут видеть изменения, произведенные писателем.

Не так давно в boost-1.53 появился целый новый раздел — lockfree реализующий неблокирующие очереди и стек.
Я последние несколько лет работал с так называемыми неблокируюшими алгоритмами (lock-free data structures), мы их сами писали, сами тестировали, сами использовали и втайне ими гордились. Естественно, у нас немедленно встал вопрос, переходить ли с самодельных библиотек на boost, и если переходить, то когда?
Вот тогда у меня и возникла в первый раз идея применить к boost::lockfree кое-какие из методик которыми мы испытывали собственный код. К счастью, сам алгоритм нам тестировать не придется и можно сосредоточиться на измерении производительности.
Я постараюсь сделать статью интересной для всех. Тем кто еще не сталкивался с подобными задачами будет полезно посмотреть на то что такие алгоритмы способны, а главное, где и как их стоит или не стоит использовать. Для тех кто имеет опыт разработки неблокирующих очередей возможно будет интересно сравнить данные количественных измерений. Я сам по крайней мере таких публикаций еще не видел.

В предыдущих своих заметках я описал основу, на которой строятся lock-free структуры данных, и базовые алгоритмы управления временем жизни элементов lock-free структур данных. Это была прелюдия к описанию собственно lock-free контейнеров. Но далее я столкнулся с проблемой: как построить дальнейший рассказ? Просто описывать известные мне алгоритмы? Это довольно скучно: много [псевдо-]кода, обилие деталей, важных, конечно, но весьма специфических. В конце концов, это есть в опубликованных работах, на которые я даю ссылки, и в гораздо более подробном и строгом изложении. Мне же хотелось рассказать интересно об интересных вещах, показать пути развития подходов к конструированию конкурентных контейнеров.
Хорошо, — подумал я, — тогда метод изложения должен быть такой: берем какой-то тип контейнера — очередь, map, hash map, — и делаем обзор известных на сегодняшний день оригинальных алгоритмов для этого типа контейнера. С чего начать? И тут я вспомнил о самой простой структуре данных — о стеке.

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

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

Все примеры приведены на Java, но содержат комментарии и я надеюсь будут понятны программистам не знакомым c Java. Данная статья носит обзорный характер и не претендует на полноту. В то же время она наполнена ссылками, которые дают более подробное объяснение терминам и утверждениям.

Как вы, наверное, догадались, эта статья посвящена lock-free очередям.

Очереди бывают разные. Они могут различаться по числу писателей (producer) и читателей (consumer) – single/multi producer — single/multi consumer, 4 варианта, — они могут быть ограниченными (bounded, на основе предраспределенного буфера) и неограниченными, на основе списка (unbounded), с поддержкой приоритетов или без, lock-free, wait-free или lock-based, со строгим соблюдением FIFO (fair) и не очень (unfair) и т.д. Подробно типы очередей описаны в этой и этой статьях Дмитрия Вьюкова. Чем более специализированы требования к очереди, тем, как правило, более эффективным оказывается её алгоритм. В данной статье я рассмотрю самый общий вариант очередей — multi-producer/multi-consumer unbounded concurrent queue без поддержки приоритетов.

Windows принято не любить. Однако, зачастую, фраза: «Книгу писателя не читал, но осуждаю» очень хорошо описывает эту ситуацию. Несмотря на укоренившееся презрение к «Винде», отдельные вещи в ней реализованы весьма удачно, и именно об одной из них мы хотели бы написать. Отдельные фрагменты WinAPI, хотя и были реализованы достаточно давно, по разным причинам, и часто незаслуженно, выпали из поля зрения широкой аудитории.
В этой статье речь пойдёт о встроенной в ОС реализации lock-free стека и сравнении его производительности с кросс-платформенными аналогами.

Со времени предыдущего поста из жизни lock-free контейнеров прошло немало времени. Я рассчитывал быстро написать продолжение трактата об очередях, но вышла заминка: о чем писать, я знал, но реализации на C++ этих подходов у меня не было. «Не годится писать о том, что сам не попробовал», — подумал я, и в результате я попытался реализовать в libcds новые алгоритмы очередей.
Сейчас настал момент, когда я могу аргументированно продолжить свой цикл. В данной статье закончим с очередями.

Кратко напомню, на чем я остановился. Были рассмотрены несколько интересных алгоритмов lock-free очередей, а под занавес приведены результаты их работы на некоторых синтетических тестах. Главный вывод — всё плохо! Надежды на то, что lock-free подход на магическом compare-and-swap (CAS) даст нам пусть не линейный, но хотя бы какой-то рост производительности с увеличением числа потоков, не оправдались. Очереди не масштабируются. В чем причина?..