Из доклада старшего разработчика Сергея Мурылёва можно узнать о многопоточном ассоциативном контейнере для стандартной библиотеки, который разрабатывают в рамках WG21. Сергей рассказал о плюсах и минусах популярных решений этой задачи и о пути, выбранном разработчиками.


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

Во многих языках программирования — Java, C#, Python — такое уже есть и довольно широко используется. А в нашем горячо любимом, самом быстром и производительном C++ такого не оказалось. Но мы посовещались и решили такую штуку сделать.



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

Самый известный и широко используемый вариант — кеширование больших тяжелых вычислений. Есть достаточно известный сервис Memcached, который просто кеширует ответы веб-серверов в памяти. Понятно, что сделать примерно то же самое можно на стороне своего приложения, если у тебя есть конкурентный ассоциативный контейнер. У того и другого подхода есть свои плюсы и минусы. Но если такого контейнера у тебя нет, придется либо делать свой велосипед, либо использовать какой-нибудь Memcached.

Следующим популярным случаем использования является дедупликация событий. Я думаю, многие в этой комнате пишут всякие распределенные системы и знают, что часто для связи между компонентами используются распределенные очереди, типа Apache Kafka и Amazon Kinesis. Они отличаются такой особенностью, что у них одно сообщение одному консьюмеру может приходить по несколько раз. Это называется у них at least once delivery, что означает гарантию доставки как минимум один раз: больше можно, меньше нельзя.

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

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

Последний вариант на этом слайде — подсчет статистики. Из реальных применений в жизни можно привести пример использования в виртуальной машине от Facebook. Они сделали целую виртуальную машину, чтобы оптимизировать PHP и у себя в этой виртуальной машине они для всех встроенных функций стараются записывать в многопоточную хэш-таблицу аргументы, с которыми они назывались. И если у них в кэше есть результат, то они его пытаются просто сразу отдать и ничего не считать.

^{_{Ссылка со слайда}}

Добавить что-то большое и сложное в стандарт — не простая и не быстрая работа. Как правило, если происходит добавление чего-то большого, оно проходит через техническую спецификацию. В данный момент в стандарте идет большое движение по расширению поддержки многопоточности в стандартной библиотеке. И конкретно сейчас туда едет proposal P0260R3 про многопоточные очереди. Этот proposal — про очень похожую на нас структуру данных, и решения в дизайне у нас во многом похожи.

Собственно говоря, одним из основных концепций их дизайна является то, что у них интерфейс отличается от стандартного std::queue. В чем суть? Если посмотреть на стандартную очередь, то, чтобы из нее извлечь элемент, надо сделать две операции. Надо сделать операцию front, чтобы считать, и операцию pop, чтобы удалить. Если мы работаем в условиях многопоточности, то у нас может произойти какая-то операция над очередью между этими двумя вызовами, и может получиться так, что мы считаем один элемент, а удалим уже другой, что кажется концептуально неверным. Поэтому эти два вызова там заменили на один, и добавили еще немного вызовов из разряда try push и try pop. Но общая идея такова, что многопоточный контейнер не будет таким же, как обычный по интерфейсу.

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

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

Также в этом proposal’e описано, что у нас есть отдельно сделанный интерфейс, который позволяет различить, какая у нас имплементация внутри блокирующая, или lock free. То, что тут везде в proposal пишется lock free, на самом деле в книжках это пишется, как wait free. Это означает, что у нас алгоритм отрабатывает за фиксированное количество операций. Lock free там означает немного другое, но это не суть.



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

На данной картинке у нас нарисована хэш-таблица, которая сделана на списках. На самом деле, в нашей референсной имплементации мы написали хэш-таблицу с открытой адресацией из соображений производительности. Соображения производительности, в принципе, такие же, почему std::vector быстрее, чем std::list, потому что vector, условно говоря, хранится последовательно в памяти. Когда мы по нему идем, у нас происходит последовательный доступ, который хорошо кешируется. Если мы используем какие-то листы, то у нас будет много всяких прыжков между разными участками памяти. И все это дело, как правило, заканчивается тем, что мы теряем производительность.

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

^{_{Ссылка со слайда}}

Основные идеи нашего дизайна. Конечно же, мы тоже сделали интерфейс, который не совпадает с std::unordered_map. Причина такая. У нас, например, в обычном std::unordered_map есть такая замечательная штука, как итераторы. Во-первых, не все имплементации могут их нормально поддержать. А те, которые могут поддержать, как правило, это какие-то lock free имплементации, которые требуют наличия либо garbage collection, либо каких-нибудь умных указателей, которые подчищают за ней память.

Помимо этого там есть еще несколько других типов операций, которые мы выкинули. На самом деле, итераторы, они во многих местах есть. Например, они есть на Java. Но, как правило, как это ни странно, они там никак не синхронизуются. И если вы попытаетесь что-то с ними сделать из разных потоков, то они могут легко перейти в невалидное состояние, и можно в Java получить exception, а если написать такое на плюсах, то это, скорее всего, будет undefined behavior, что еще хуже. И кстати, на тему undefined behavior: по-моему, товарищи из Facebook в своей библиотеке folly, которая выложена в опенсорс на GitHub, именно так и сделали. Просто скопировали интерфейс с Java и получили такие замечательные итераторы.

Еще у нас нет рекламации памяти, то есть если мы что то добавили в контейнер и заняли под это память, то обратно ее мы не отдадим, даже если удалить все. Еще одной предпосылкой к этому решению было то, что у нас внутри хеш таблица с открытой адресацией. Она работает на линейной структуре данных, которая как и vector не отдает обратно память.

Следующий концептуальный момент, это мы никогда ни при каких условиях никому наружу не отдаем ссылки и указатели на внутренние объекты. Это как раз таки было сделано с целью того, чтобы предотвратить необходимость наличия garbage collection, и чтобы не энфорсить умные указатели. Понятно, что если мы храним какие-то достаточно большие объекты, хранить их по значению внутри будет невыгодно. Но, в этом случае, мы их всегда можем обернуть их в какие-то умные указатели по своему выбору. И, если мы хотим, например, делать какую-то синхронизацию на значениях, мы можем их обернуть в какой-нибудь boost::synchronised_value.

Мы посмотрели на то, что какое-то время назад у класса shared_ptr убрали метод, который возвращал количество активных ссылок на этот объект. И пришли к выводу, что нам тоже надо выкинуть несколько функций, а именно, size, count, empty, buckets_count, потому что, как только мы возвращаем это значение из функции, оно сразу перестает быть валидным, потому что его кто-то может в этот же момент поменять.

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

^{_{Ссылка со слайда}}

На этом заседании на Гавайях против нас написали целый proposal. :) Нам сказали, что таким вещам не место в стандарте, потому что способов сделать свой многопоточный ассоциативный контейнер существует очень много.

У каждого есть свои плюсы и минусы — и непонятно, как использовать то, что у нас в итоге у нас получится. Как правило, оно используется, когда тебе нужен какой-то экстремальный перформанс. И вроде как наше коробочное решение не подходит, надо оптимизироваться под каждый конкретный случай.

Второй поинт этого proposal был в том, что наш интерфейс не совместим с тем, что запостил Facebook на GitHub из своей стандартной библиотеки.

На самом деле там каких-то особых проблем не было. Там просто был вопрос из разряда «Я не читал, но осуждаю». Просто они посмотрели — интерфейс разный, значит, не совместимый.

Идея proposal была еще и в том, что подобные задачи надо решать при помощи так называемого policy based design, когда необходимо сделать дополнительный шаблонный параметр, в котором можно передавать битовую маску с тем, какие фичи мы хотим включить, а какие выключить. Действительно, это звучит немного диковато и приводит к тому, что у нас получается порядка 2^n имплементаций, где n — количество различных фич.



В коде это выглядит примерно так. У нас есть какой-то параметр и какое-то количество предопределенных констант, которые туда можно передавать. Как ни странно, этот proposal отклонили.



Потому что, на самом деле, комитет уже занял позицию, что таким вещам быть, когда многопоточная очередь прошла через SG1. По этому вопросу даже не было голосования. Но на голосование были выставлены два вопроса.

Первый. Много людей захотели, чтобы мы на стороне нашей референсной имплементации поддержали чтение без взятия любых блокировок. Чтобы у нас было полностью не блокирующее чтение. Это, действительно, имеет смысл: как правило, самый популярный юзкейс — кеширование. И нам очень выгодно иметь быстрое чтение.

Второй момент. Все наслушались предыдущего товарища, который говорил про policy based design. У всех возникла идея — а что, давай я свою идею тоже потолкаю! И все проголосовали за то, чтобы policy based design был. Хотя надо сказать, вся эта история длится достаточно давно, и перед нами этим занимались коллеги из Intel, Арч Робинсон и Антон Малахов. И у них уже было несколько proposals на эту тему. Они как раз таки предлагали добавить lock free-имплементацию на основе алгоритма SeepOrderedList. И у них тоже был policy based design как раз таки с рекламацией памяти.

И этот proposal не понравился Library Evolution Working Group. Его завернули с тем основанием, что у нас просто будет неограниченно расти количество слов в стандарте. Это будет просто невозможно адекватно проревьюить и просто реализовать в коде.

У нас замечаний к самим идеям нет. У нас есть замечания, по большей части, к референсной имплементации. И конечно, у нас есть пара идей, которые можно внести, чтобы было понятнее. Но по сути, мы в следующий раз пойдем примерно с тем же самым proposal. Мы искренне надеемся, что у нас не будет, как с модулями, пять заходов с одним и тем же proposal. Мы искренне верим в себя, и что в следующий заход нас пропустят дальше, и что Library Evolution Working Group все-таки настоит на своем мнении, не даст пропихивать policy based design. Потому что наш оппонент не останавливается. Он решил доказывать всем, что это надо. Но, как говорится, время покажет. У меня все, спасибо за внимание.