Lock-free структуры данных. Concurrent maps: деревья

    Это последняя, на сегодняшний день, статья из цикла про внутреннее устройство конкурентных ассоциативных контейнеров. В предыдущих статьях рассматривались hash map, был построен алгоритм lock-free ordered list и контейнеры на его основе. За бортом остался один важный тип структур данных — деревья. Пришло время немного рассказать и о них.

    Исследования, посвященные алгоритмам конкурентных деревьев, не требующих внешней синхронизации доступа к ним, начались довольно давно — в 70-х годах прошлого века, — и были инициированы развитием СУБД, поэтому касались в основном оптимизации страничных деревьев (B-tree и его модификации).

    Развитие lock-free подхода в начале 2000-х не прошло мимо алгоритмов деревьев, но лишь недавно, в 2010-х годах, появилось множество действительно интересных работ по конкурентным деревьям. Алгоритмы деревьев довольно сложны, поэтому исследователям потребовалось время — порядка 10 лет — на их lock-free/non-blocking адаптацию. В данной статье мы рассмотрим самый простой случай — обычное бинарное дерево, даже не самобалансирующееся.

    В чем практический смысл обычного бинарного дерева, спросит читатель, ведь все мы знаем, что для упорядоченных данных такое дерево вырождается в линейный список со сложностью поиска O(N)? Основной смысл в том, чтобы апробировать подходы на простой структуре данных. Кроме того, для случайных данных бинарное дерево подходит довольно хорошо, обеспечивая сложность O(log N), а его внутренняя простота является залогом высокой эффективности. Так что тут все зависит от задачи, где такое дерево используется.

    Для начала — ретроспективный взгляд на проблему построения lock-free/non-blocking деревьев. После того, как были найдены довольно эффективные lock-free алгоритмы для очередей и списков, появились работы по lock-free самобалансирующимся деревьям — AVL tree, Red-Black tree. Псевдокод этих алгоритмов был сложен, — сложен настолько, что я бы не взялся его реализовывать, так как мне непонятно, например, как к ним применить схемы управления памятью (Hazard Pointer, RCU или что-то ещё), – алгоритмы полагались на garbage collector (GC) языка, обычно Java. Кроме того, я бы не стал воплощать алгоритм, использующий примитив CAS (compare-and-swap) для поиска ключа в дереве, — CAS слишком тяжел для этого. Да и вообще, несмотря на формальное доказательство корректности такого алгоритма (при наличии GC, — эта оговорка существенна, отсутствие GC может нарушить доказательство), его сложность, наличие множества граничных случаев, казались мне непреодолимыми в свете отладки.

    Видимо, не только меня пугала сложность и, по сообщениям разработчиков, неэффективность получающихся lock-free алгоритмов для деревьев. Поэтому в начале 2010-х годов акценты в разработке алгоритмов несколько сместились: вместо того, чтобы обеспечить lock-free любыми средствами, стало появляться много работ, где во главу угла ставилась эффективность операции поиска по дереву. Действительно, деревья применяются в основном в задачах поиска (считается, что поиск — это 70 — 90% операций), и именно поиск должен быть быстрым. Поэтому появились non-blocking алгоритмы, в которых поиск является lock-free, а вставка/удаление могут быть блокируемыми на уровне группы узлов (fine-grained locking) — либо явно с помощью мьютексов, либо неявно с использованием флажков и т.п., то есть по сути это spinning. Такой подход дал менее сложные и более понятные алгоритмы, один из которых мы и рассмотрим.

    Binary search tree


    Будем рассматривать дерево, в котором данные расположены в листьях, внутренние узлы являются маршрутными и содержат только ключи:



    Это так называемое leaf-oriented tree. Наличие искомого ключа во внутреннем узле не говорит о том, что ключ существует в дереве, — только листья содержат ключи и соответствующие им данные, внутренние узлы могут содержать удаленные ключи.

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

    Рассмотрим, какие неожиданности нас ждут при выполнении конкурирующих операций. Пусть имеется некое дерево и потоки A и B выполняют удаление ключей 15 и 27 соответственно:



    Поток A для удаления ключа 15 должен удалить лист с этим ключом и его родителя — внутренний узел с ключом 20. Для этого он изменяет правую ссылку у своего деда — узла 10 – с узла 20 на узел 30, который является братом удаляемого узла. Так как мы рассматриваем конкурентные деревья, данная операция должна быть выполнена атомарно, то есть с помощью CAS (compare-and-swap).

    В это же время поток B удаляет ключ 27. Аналогично вышеописанному, поток B перекидывает CAS'ом правую ссылку узла 20 (деда 27) с 30 на лист 45.

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

    При выполнении конкурирующих удаления и вставки ситуация похожа:



    Здесь поток A, удаляющий лист с ключом 27, конкурирует с потоком B, выполняющим вставку нового ключа 29. Для удаления 27 (и его родителя — внутреннего узла 30) поток A перекидывает указатель правого сына узла 20 с 30 на 45. В то же самое время ключ 29 и соответствующий ему внутренний узел 29 вставляются как левый сын узла 30, — в ту же самую позицию, откуда поток A удаляет ключ 27. В результате новый ключ становится недостижимым — утечка памяти.

    Очевидно, что примитив CAS сам по себе не может разрулить вышеописанные случаи. Необходимо перед выполнением вставки/удаления каким-то образом помечать узлы, участвующие в операции. В операции вставки участвуют узел-лист и его родитель — внутренний узел. Перед выполнением вставки узел-родитель следует пометить «выполняется вставка», чтобы конкурирующие вcтавки/удаления не смогли выполниться на этом узле. В операции удаления участвуют удаляемый лист, его родитель и родитель его родителя — дед удаляемого листа. Оба внутренних узла — родитель и дед — также должны быть помечены для исключения конкуренции на них.

    В этой работе предлагается использовать для каждого внутреннего узла поле состояния State:



    Внутренний узел может находиться в одном из следующих состояний:
    • Clean — на узле не выполняется вставок или удалений. Это состояние узла по умолчанию.
    • IFlag — в узел выполняется вставка. Таким флагом помечается внутренний узел, у которого хотя бы один сын является листом.
    • DFlag — выполняется удаление. Таким флагом помечается внутренний узел-дед удаляемого листа
    • Mark — внутренний узел будет удален. Таким флагом помечается родитель удаляемого листа (помним, что в нашем дереве при удалении листа всегда удаляется и его родитель).

    Эти состояния взаимоисключающие: каждый узел может находиться только в одном из них. Изменение состояния узла выполняется примитивом CAS.
    Вспомним, что нашей основной целью является как можно более эффективная реализация операции поиска ключа в дереве. Как эти состояния влияют на поиск? Очевидно, что операция вставки и соответствующий ей флаг IFlag может быть проигнорирована при поиске: при вставке нет удалений, значит, мы не сможем «зайти в запретную, удаленную зону». А вот флаги DFlag и Mark должны влиять на поиск: при достижении узла с одним из таких флагов поиск должен быть возобновлен с начала (здесь возможны вариации действий, но самое простое — начать поиск заново).

    Итак, рассмотрим, как работают эти состояния на примере вставки ключа 29:



    Мы находим узел вставки — это внутренний узел 30. Первым делом мы устанавливаем состояние IFlag узла 30 примитивом CAS. CAS здесь нам гарантирует, что мы перейдем в состояние IFlag только из состояния Clean, что исключает конкурирующие операции, то есть мы становимся эксклюзивными владельцами узла 30. Далее мы создаем внутренний узел 27, задаем ему сыновей — существующий лист 27 и новый 29, — и меняем указатель левого сына узла 30 на вновь созданный внутренний узел 27. Зачем здесь нужен CAS, нельзя ли обойтись обычным атомарным store? Ответ — в оригинальном алгоритме нельзя, в реализации libcds – можно применить атомарный store, об этом мы поговорим позже. И, наконец, третий шаг: снимаем флаг IFlag с узла 30. Здесь также применяется CAS в оригинальном алгоритме, который может быть заменен на атомарный store, если мы откажемся от кое-чего не очень нужного.

    Операция удаления с применением флагов State состоит из четырех шагов:


    • Помечаем деда удаляемого листа состоянием DFlag с помощью CAS
    • Маркируем родителя удаляемого листа состоянием Mark также CAS'ом
    • Перекидываем CAS'ом указатель потомка узла-деда
    • Снимаем метку DFlag с деда. Здесь используется CAS, но можно использовать и более простой атомарный store при некотором упрощении алгоритма

    Заметим, что метку Mark мы не снимаем с узла-родителя удаляемого листа, так как в нашем алгоритме родитель также удаляется и нет смысла в снятии метки с него.

    Посмотрим, как работают флаги в случае конкурентного удаления. Без флагов состояния конкурентное удаление ключей 15 и 27 приводило, как мы ранее видели, к достижимости удаленного листа:



    С флагами состояния будем иметь:



    Казалось бы, если поток A поставил флаг DFlag на узле 10, поток B не должен при поиске 27 пройти дальше узла 10. Но у нас операции выполняются параллельно, так что вполне возможно, что поток B успел прошмыгнуть узел 10 до того, как его пометили флагом DFlag. Далее на узле 20 возникает конкуренция: поток A хочет пометить его флагом Mark, поток B – флагом DFlag. Так как установка состояния узла производится атомарным CAS от состояния Clean, только один из потоков выиграет это сражение. Если выигрывает поток A, то есть если он успел пометить 20 флагом Mark, поток B начинает поиск удаляемого узла 27 с начала, а A удаляет 15 и затем снимает флаг DFlag с 10. Если же выигрывает B, пометив 20 флагом DFlag, поток A должен снять свою метку с 10 и повторить поиск узла 15. В обоих случаях удаление ключей выполняется в конце концов успешно и без нарушения структуры дерева.

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

    В оригинальном алгоритме используется прием взаимопомощи (helping) потоков при обнаружении конкуренции на узле. Для этого помимо флагов состояния внутренний узел может содержать дескриптор выполняемой операции — вставки или удаления. Конкурирующий поток, обнаружив состояние узла, отличное от Clean, может прочесть данный дескриптор и попытаться помочь своему собрату выполнить операцию. В этом случае переход в состояние Clean по окончании операции должен производиться только примитивом CAS, так как несколько потоков — инициатор операции и помощники — могут переводить состояние узла в Clean. Если мы будем делать это атомарным store, то возможна ситуация, когда узел, переведенный в состояние Clean и затем в некое другое последующей операцией вставки/удаления, будет переведен опять в Clean неким запоздавшим помощником.

    Прием взаимопомощи хорошо выглядит в псевдокоде, но на практике я не видел от него особого выигрыша. Более того, на C++, где нет сборщика мусора, данный прием реализовать эффективно довольно проблематично: сразу встает вопрос о том, как распределять дескрипторы (на стеке? alloc? пул?), а также ещё более серьезный — о времени жизни такого дескриптора (reference counting?). В реализации libcds helping отключен: несколько попыток его внедрения не увенчались успехом, — код получается нестабильным (эта красивая фраза из лексикона менеджеров означает, что программа падает). Так что алгоритм binary search tree в libcds содержит несколько артефактов, в том числе и CAS вместо атомарного store при переводе состояния узла в Clean, от которых в будущем я избавлюсь.

    Заключение


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

    Серию статей о concurrent map хотелось бы закончить результатами синтетических тестов для реализаций из libcds (Intel Dual Xeon X5670 2.93 GHz 12 cores 24 threads / 24 GB RAM, среднее число элементов — 1 миллион, ключи — int):



    Здесь:
    • MichaelMap — простейший hash map без rehasing'а, рассмотренный здесь
    • SplitListMap — алгоритм split-ordered list
    • SkipListMap — алгоритм skip list
    • BinTree — рассмотренное в данной статье бинарное дерево
    • std::map, std::unordered_map — STL-алгоритмы под std::mutex

    Результаты приведены для Hazard Pointer (HP) и user-space RCU (точнее, её буферизованной разновидности cds::urcu::general_buffered).

    Вы можете подтвердить или опровергнуть эти результаты, загрузив и скомпилировав libcds или применив структуры данных из libcds в своем приложении.

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

    Share post

    Comments 13

      +3
      Спасибо! Прочел весь цикл статей — многое почерпнул!
        +1
        Спасибо! Значит, цель достигнута :-)
        +1
        Попробовали ли вы ThreadSanitizer для отладки (вы когда-то упоминали, что собираетесь)? Как он вам?
          0
          К сожалению, в полной мере — нет, но вот уже собираюсь ;-)
          Почему до сих пор нет:
          Причина 1 — банальная: надо перестраивать билд-систему тестов, чтобы было удобно добавлять всякие инструменты (= флаги компиляции). Для этой задачи я уже созрел.
          Причина 2: очень большая работа. Собирал отзывы тех, кто пробовал tsan именно для проверки race/memory ordering. Боюсь погрязнуть в false positive (или false negative? в общем, в сообщениях об ошибках там, где их нет). На C++ 2015 Russia говорил с одним из разработчиков санитайзеров, Дмитрием Вьюковым. Он подтвердил, что tsan — инструмент более тупой (не в смысле «тупой», а в смысле особо не заточенный под memory ordering), чем его же relacy race detector, и может давать false positive. Применять relacy, — это перелопатить весь код libcds, над этим я думаю…
          Причина 3 — всепобеждающая: всегда находится более интересная задача
          +1
          Tsan более тупой, но он не дает false positive. Он может пропустить ошибки, это да.
          Если билд систему сложно менять, то можно сделать «compiler script»:
          $ cat /xxx/g++
          #!/usr/bin/env bash
          clang++ -fsanitize=thread $@
          $ export PATH=/xxx:$PATH
            +1
            Решил задействовать библиотеку в своем проекте. В моем случае очень неплохо показал себя CuckooMap — производительность при одном потоке по сравнению с unordered_map: 50%-100% для insert/erase и 30-40% для find. Скейлинг на разное количество потоков не пробовал. Зато хорошо скейлится при большом (~10^8) количестве элементов (в отличии от SplitListMap). Очень неплохая thread-safe stl-style unordered_map получается, по крайней мере если код не очень «состязательный», но без конкурентной структуры обойтись нельзя.
              0
              Для меня это несколько неожиданно.
              Хотя это подтверждает тезис о том, что не существует единого «хорошего для всех» map'а. Каждой задаче — свой map.
                +2
                И разобраться в том, для каких юз-кейсов какой map больше подходит — задача не из простых, похоже. Обзорная статья по сильным-слабым сторонам разных деревьев была очень полезна, но я такой ни на русском, ни на английском не нашел. Даже review articles в научных публикациях такой не отыскалось :(.
                Для себя пока выделил три hash-map структуры:
                MichaelMap — для данных, которые не требуется перестраивать.
                SplitListMap — для небольших (до 10^6) структур
                CuckooMap — для низкосостязательного (low-contention) кода, особенно если предполагается большое количество элементов в структуре.
                  +1
                  Нашел еще одну конкурентную реализацию CuckooMap — libcuckoo, вышел на нее через статью.
                    0
                    Спасибо за ссылки!
                      +1
                      Протестировал libcuckoo — супер круто. Привожу производительность при 6 потоках (в операциях/микросекунду). CH=CityHash. При одном потоке производительность libcuckoo и std::unordered_map примерно одинакова.

                      map_type			find		add/rem
                      cds::CuckooMap:			6.45		6.09672
                      cds::SplitListMap:		26.5		20.5555
                      libcuckoo::hashmap:		63.7		52.871
                      libcuckoo::hashmapCH:		55.5		47.0
                      


                      Хотя по функциональности, конечно, libcds несравнимо шире.
                        0
                        Прочитал вышеприведенную статьюотличнейший пример оптимизации известного алгоритма! В результате перформанс алгоритма преобразился до неузнаваемости.
                        Рекомендуется студентам старших курсов профильных вузов и инженерам/исследователям в области оптимизации структур данных, а также всем, кто не ленится применять что-то более чем std::unordered_map
                          0
                          Ну, принстон не зря такую репутацию имеет :)

                Only users with full accounts can post comments. Log in, please.