Lock-free структуры данных. Эволюция стека


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

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

    Lock-free стек


    Стек — это, пожалуй, первая из структур данных, для которой был создан lock-free алгоритм. Считается, что его первым опубликовал Treiber в своей статье 1986 года, хотя есть сведения, что впервые этот алгоритм был описан в системной документации IBM/360.
    Историческое отступление
    Вообще, статья Treiber'а — своего рода Ветхий Завет, пожалуй, первая статья о lock-free структуре данных. Во всяком случае, более ранних мне не известно. Она до сих пор очень часто упоминается в списках литературы (reference) современных работ, видимо, как дань уважения к родоначальнику lock-free подхода.

    Алгоритм настолько простой, что я приведу его адаптированный код из libcds (кому интересно — это интрузивный стек cds::intrusive::TreiberStack):
    // m_Top – вершина стека
    bool push( value_type& val )
    {
        back_off bkoff;
    
        value_type * t = m_Top.load(std::memory_order_relaxed);
        while ( true ) {
            val.m_pNext.store( t, std::memory_order_relaxed );
            if (m_Top.compare_exchange_weak(t, &val, 
                      std::memory_order_release, std::memory_order_relaxed))       
               return true;
            bkoff();
        }
    }
    value_type * pop()
    {
       back_off bkoff;
       typename gc::Guard guard; // Hazard pointer guard
       while ( true ) {
          value_type * t = guard.protect( m_Top );
          if ( t == nullptr )
             return nullptr ;  // stack is empty
    
          value_type * pNext = t->m_pNext.load(std::memory_order_relaxed);
          if ( m_Top.compare_exchange_weak( t, pNext, 
                      std::memory_order_acquire, std::memory_order_relaxed ))
               return t;
          bkoff();
       }
    }
    

    Этот алгоритм неоднократно разобран по косточкам (например, тут), так что я повторяться не буду. Краткое описание алгоритма сводится к тому, что мы долбимся с помощью атомарного примитива CAS в m_Top, пока не получим желаемый результат. Просто и довольно примитивно.
    Отмечу две интересных детали:
    • Safe memory reclamation (SMR) необходим только в методе pop, так как только там мы читаем поля m_Top. В push никакие поля m_Top не читаются (нет обращения по указателю m_Top), так что и защищать Hazard Pointer'ом ничего не нужно. Интересно это потому, что обычно SMR требуется во всех методах класса lock-free контейнера
    • Таинственный объект bkoff и его вызов bkoff(), если CAS неуспешен

    Вот на этом самом bkoff я хотел бы остановиться подробнее.

    Back-off стратегии



    Почему CAS неуспешен? Очевидно потому, что между прочтением текущего значения m_Top и попыткой применить CAS какой-то другой поток успел изменить значение m_Top. То есть мы имеем типичный пример конкуренции. В случае сильной нагрузки (high contention), когда N потоков выполняют push/pop, только один из них выиграет, остальные N – 1 будут впустую потреблять процессорное время и мешать друг другу на CAS (вспомним протокол MESI кеша).
    Как разгрузить процессор при обнаружении такой ситуации? Можно отступить (back off) от выполнения основной задачи и сделать что-либо полезное или просто подождать. Именно для этого предназначены back-off стратегии.
    Конечно, в общем случае «сделать что-либо полезное» у нас не получится, так как мы не имеем понятия о конкретной задаче, так что мы можем только подождать. Как ждать? Вариант со sleep() отметаем — немногие операционные системы могут обеспечить нам столь малые тайм-ауты ожидания, да и накладные расходы на переключение контекста слишком велики — больше, чем время выполнения CAS.
    В академической среде популярностью пользуется стратегия экспоненциального back-off. Идея очень проста:
    class exp_backoff {
        int const nInitial;
        int const nStep;
        int const nThreshold;
        int nCurrent;
    public:
        exp_backoff( int init=10, int step=2, int threshold=8000 )
             : nInitial(init), nStep(step), nThreshold(threshold), nCurrent(init)
        {}
        void operator()()
        {
              for ( int k = 0; k < nCurrent; ++k )
                  nop();
              nCurrent *= nStep;
              if ( nCurrent > nThreshold )
                   nCurrent = nThreshold;
        }
        void reset() { nCurrent = nInitial; }
    };
    

    То есть мы в цикле выполняем nop(), с каждым разом увеличивая длину цикла. Вместо nop() можно вызвать что-то более полезное, например, вычислить bitcoin hint-инструкцию (если таковая имеется), которая говорит процессору «у тебя есть время выполнить свои внутренние дела» (опять-таки, вспомним MESI – таких дел у процессора может быть море).
    Проблема с экспоненциальным back-off проста — трудно подобрать хорошие параметры nInitial, nStep, nThreshold. Эти константы зависят от архитектуры и от задачи. В коде выше значения для них по умолчанию взяты с потолка.
    Поэтому на практике довольно неплохим выбором для десктопных процессоров и серверов начального уровня будет yield() back-off — переключение на другой поток. Тем самым мы отдаем свое время другим, более удачливым потокам, в надежде, что они сделают то, что им требуется, и не будут нам мешать (а мы — им).
    Стоит ли вообще применять back-off стратегии? Эксперименты показывают, что стоит: примененная в нужном узком месте правильная back-off стратегия может дать выигрыш в производительности lock-free контейнера в разы.

    Рассмотренные back-off стратегии помогают решить проблему с неудачными CAS, но никак не способствуют выполнению основной задачи — операций со стеком. Можно ли каким-то образом объединить push/pop и back-off, чтобы back-off стратегия активно помогала выполнению операции?

    Elimination back-off


    Рассмотрим проблему неудачного CAS в push/pop с другой стороны. Почему CAS неудачен? Потому что другой поток изменил m_Top. А что делает этот другой поток? Выполняет push() или pop(). Теперь заметим, что операции push и pop для стека комплементарны: если один поток выполняет push(), а другой в это же время — pop(), то в принципе вообще не имеет смысла обращаться к вершине стека m_Top: push-поток мог бы просто передать свои данные pop-потоку, при этом основное свойство стека — LIFO – не нарушается. Остается придумать, как свести вместе оба эти потока, минуя вершину стека.


    В 2004 году Hendler, Shavit и Yerushalmi предложили модификацию алгоритма Treiber'а, в котором задача передачи данных между push- и pop-потоками без участия вершины стека решается с помощью специальной back-off стратегии, названной ими исключающей back-off стратегией (elimination back-off, я бы перевел ещё как поглощающая back-off стратегия).

    Имеется массив elimination array размером N (N — небольшое число). Этот массив является членом класса стека. При неуспехе CAS, уходя в back-off, поток создает дескриптор своей операции (push или pop) и случайным образом выбирает произвольную ячейку этого массива. Если ячейка пуста, он записывает в неё указатель на свой дескриптор и выполняет обычный back-off, например, экспоненциальный. В этом случае поток можно назвать пассивным.
    Если же выбранная ячейка уже содержит указатель на дескриптор P операции какого-то другого (пассивного) потока, то поток (назовем его активным) проверяет, что это за операция. Если операции комплементарны — push и pop, — то они взаимно поглощаются:
    • если активный поток выполняет push, то он записывает в дескриптор P свой аргумент, передавая таким образом его в операцию pop пассивного потока;
    • если активный поток выполняет pop, то он читает из дескриптора P аргумент комплементарной операции push.


    Затем активный поток помечает запись в ячейке elimination array как обработанную, чтобы пассивный поток при выходе из back-off увидел, что кто-то волшебным образом выполнил его работу. В результате активный и пассивный потоки выполнят свои операции без обращения к вершине стека.
    Если же в выбранной ячейке elimination array операция та же самая (ситуация push-push или pop-pop), — не повезло. В этом случае активный поток выполняет обычный back-off и далее пытается выполнить свой push/pop как обычно, — CAS вершины стека.
    Пассивный же поток, окончив back-off, проверяет свой дескриптор в elimination array. Если дескриптор имеет отметку, что операция выполнена, то есть нашелся другой поток с комплементарной операцией, то пассивный поток успешно завершает свой push/pop.
    Все вышеописанные действия выполняются в lock-free манере, без каких-либо блокировок, поэтому реальный алгоритм сложнее описанного, но смысл от этого не меняется.
    Дескриптор содержит код операции — push или pop, — и аргумент операции: в случае push — указатель на добавляемый элемент, в случае pop поле указателя остается пустым (nullptr), в случае успеха elimination в него записывается указатель на элемент поглощающей операции push.
    Elimination back-off позволяет значительно разгрузить стек при высокой нагрузке, а при малой, когда CAS вершины стека почти всегда успешен, такая схема не привносит вообще никакого оверхеда. Алгоритм требует тонкой настройки, заключающейся в выборе оптимального размера elimination array, что зависит от задачи и реальной нагрузки. Можно также предложить адаптивный вариант алгоритма, когда размер elimination array изменяется в небольших пределах в процессе работы, подстраиваясь под нагрузку.
    В случае несбалансированности, когда операции push и pop идут пачками — много push без pop, затем много pop без push, — алгоритм не даст какого-либо ощутимого выигрыша, хотя и особого проигрыша в производительности быть не должно по сравнению с классическим алгоритмом Treiber'а.

    Flat combining


    До сих пор мы говорили о lock-free стеке. Рассмотрим теперь обычный lock-based стек:
    template <class T> class LockStack {
        std::stack<T *> m_Stack;
        std::mutex      m_Mutex; 
    public:
        void push( T& v ) {
            m_Mutex.lock();
            m_Stack.push( &v );
            m_Mutex.unlock();
        }
        T * pop() {
            m_Mutex.lock();
            T * pv = m_Stack.top();
            m_Stack.pop()
            m_Mutex.unlock();
            return pv;
        }
    };
    

    Очевидно, что при конкурентом выполнении производительность его будет весьма низка — все обращения к стеку сериализуются на мьютексе, всё выполняется строго последовательно. Можно ли как-нибудь повысить performance?
    Если N потоков одновременно обращаются к стеку, только один из них захватит мьютекс, остальные будут дожидаться его освобождения. Но вместо того, чтобы пассивно ждать на мьютексе, ждущие потоки могли бы анонсировать свои операции, как в elimination back-off, а поток-победитель (владелец мьютекса) мог бы помимо своей работы выполнить и задания от своих собратьев. Эта идея легла в основу подхода flat combining, описанного в 2010 году и развивающегося и по сей день.

    Идею подхода flat combining можно описать следующим образом. С каждой структурой данных, в нашем случае со стеком, связан мьютекс и список анонсов (publication list) размером, пропорциональным количеству потоков, работающих со стеком. Каждый поток при первом обращении к стеку добавляет к списку анонсов свою запись, расположенную в thread local storage (TLS). При выполнении операции поток публикует в своей записи запрос — операцию (push или pop) и её аргументы — и пытается захватить мьютекс. Если мьютекс захвачен, поток становится комбайнером (combiner, не путать с комбайнёром): он просматривает список анонсов, собирает все запросы из него, выполняет их (в случае со стеком здесь может применяться поглощение (elimination), рассмотренное ранее), записывает результат в элементы списка анонсов и наконец освобождает мьютекс. Если же попытка захвата мьютекса не удалась, поток ожидает (spinning) на своем анонсе, когда комбайнер выполнит его запрос и поместит результат в запись анонса.
    Список анонсов построен таким образом, чтобы уменьшить накладные расходы на управление им. Ключевым моментом является то, что список анонсов редко изменяется, иначе мы получим ситуацию, когда к стеку прикручен сбоку lock-free publication list, что вряд ли как-то ускорит сам стек. Запросы на операцию вносятся в уже существующую запись списка анонсов, которая, напомню, является собственностью потоков и находится в TLS. Некоторые записи списка могут иметь статус «empty», означающий, что соответствующий поток не выполняет в настоящий момент никаких действий со структурой данных (стеком). Время от времени комбайнер прореживает список анонсов, исключая давно неактивные записи (поэтому записи списка должны иметь какой-то timestamp), тем самым уменьшая время просмотра списка.
    Вообще, flat combining является очень общим подходом, который с успехом распространяется на сложные lock-free структуры данных, позволяет комбинировать разные алгоритмы, — например, добавлять elimination back-off в реализацию flat combining-стека. Реализация flat combining на C++ в библиотеке общего пользования также является довольно интересной задачей: дело в том, что в исследовательских работах список анонсов является, как правило, атрибутом каждого объекта-контейнера, что может быть слишком накладно в реальной жизни, так как каждый контейнер должен иметь свою запись в TLS. Хотелось бы иметь более общую реализацию с единым publication list для всех объектов flat combining, но при этом важно не потерять в скорости.
    История развивается по спирали
    Интересно, что идея анонсирования своей операции перед её выполнением восходит к началу исследований lock-free алгоритмов: в начале 1990-х годов были предприняты попытки построения общих методов преобразования традиционных lock-based структур данных в lock-free. С точки зрения теории эти попытки успешны, но на практике получаются медленные тяжелые lock-free алгоритмы. Идея этих общих подходов как раз и была — анонсировать операцию перед выполнением, чтобы конкурирующие потоки увидели её и помогли её выполнить. На практике такая «помощь» была скорее помехой: потоки выполняли одну и ту же операцию одновременно, толкаясь и мешая друг другу.
    Стоило немного переставить акценты — с активной помощи до пассивного делегирования работы другому, более удачливому потоку — и получился быстрый метод flat combining.


    Заключение


    Удивительно, что такая простая структура данных, как стек, где и писать, казалось бы, не о чем, позволила продемонстрировать столько интересных подходов к разработке конкурентных структур данных!
    Back-off стратегии применимы повсеместно при конструировании lock-free алгоритмов: как правило, каждая операция заключена в бесконечный цикл по принципу «делаем пока не удастся», а в конце тела цикла, то есть именно тогда, когда итерация не удалась, не лишним будет поставить back-off, который может уменьшить давление на критические данные контейнера при большой нагрузке.
    Elimination back-off – менее общий подход, применимый для стека и, в меньшей степени, для очереди.
    Получивший развитие в последние годы flat combining является особым трендом при построении конкурентных контейнеров — как lock-free, так и fine grained lock-based.
    Надеюсь, мы ещё встретимся с этими техниками в дальнейшем.

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 14

      +1
      Спасибо за статью, LFS всегда интересовали.

      Хотя на самом деле увидев картинку, первым делом подумал, что это перевод старой статьи Эрика. Однако обознался.
        +1
        Упс… Картинку поменял, дабы не было путаницы, спасибо!
        +2
        Большое спасибо за очередную статью! Жаль, за карму можно только один раз голосовать.
          +1
          Спасибо за статью.
          Я правильно понимаю что упомянутый Hazard Pointer нужен для предотвращения ABA? Существует ли стандартная/оптимальная имплементация?
            0
            Да, Hazard Pointer нужен для предотвращения ABA-проблемы.
            Стандартная/оптимальная имплементация (видимо, имеется в виду стека?): о стандартной не слышал, о оптимальности можно говорить применительно к конкретной задаче. Приведенные алгоритмы — Treiber stack, back-off, elimination back-off, flat combining, — хороши каждый по своему при определенных нагрузках на конкурентный стек. Даже наличие нескольких алгоритмов намекает на то, что алгоритма на все случаи жизни пока (или вовсе) не существует.
              0
              Извиняюсь за невнятный вопрос. Я имел ввиду имплементацию Hazard Pointer и способы предотвращения ABA в целом. В будущем не собираетесь об этом написать подробнее?
                0
                Уже писал: Схемы управления памятью, RCU.
                Стандартной/общепринятой реализации Hazard Pointer я не знаю. Многих пугает то, что это патентованный IBM алгоритм.
                  0
                  Да правильно, и я даже читал, но забыл сам термин.
                  Напишите пожалуйста про lockfree queues, есть вопросы но не хочу забегать вперед.
                    0
                    В принципе, статья про очереди должна быть следующей. Очереди — самый популярный контейнер у исследователей, работ на эту тему много, трудно выбрать и как-то систематизировать. Вывод: про очереди напишу, но когда — не знаю…
                    0
                    del
              0
              Глупый вопрос, а почему в pop() мы пишем в top с std::memory_order_acquire, а не release?
                0
                На самом деле, вопрос далеко не глупый. На него есть два ответа.
                Первый — чисто технический: release/acquire всегда идут парами. Если в push() мы делаем release-CAS, то в pop — acquire-CAS.
                Второй — точнее. Memory order задают семантику атомарных RMW-операций. Метод push() — это метод записи данных в стек, а раз запись — значит, из пары «acquire или release» мы можем выбрать только release. Метод pop() — это чтение данных из стека, а для чтения подходящим memory order является acquire.
                  +1
                  Спасибо за быстрый ответ!
                  Я просто поясню, что взрывает мозг — то, что в обоих случаях мы _пишем_ (и читаем) в top. Аргумент про семантику более-менее понятен, но ведь процессор работает не в терминах чтения\записи в стек, а в терминах чтения\записи конкретных адресов (top). И как происходит этот переход, не очень ясно (ведь уровень команд синхронизации процессора весьма далек от семантики конкретного контейнера).
                  С точки зрения записи в top, парой к release мог бы быть guard.protect( m_Top ), если бы он использовал acquire семантику (но это, вероятно, не так, и он использует relaxed).
                  Верно я понимаю, что рассматривая семантику мы как бы говорим, что если происходит push/pop, то менять их местами нельзя (ведь стек может быть пуст), а pop/push — пожалуйста (ну вытолкнем мы 2й элемент, а не 1й, ну бывает).
                    0
                    Я просто поясню, что взрывает мозг — то, что в обоих случаях мы _пишем_ (и читаем) в top

                    Да, и не только у вас. RMW-операции могут обладать как acquire, так и release семантикой. К сожалению, стандарт довольно подробно описывает атомарные чтение/запись, и только вскользь — атомарные RMW, типа, «они могут обладать как acquire, так и release семантикой». А ведь это — самое главное, ИМХО: без RMW atomic'и довольно бесполезны. Мы сами наделяем RMW-операции нужной семантикой: одни становятся «операциями acquire-чтения», другие — «операциями release-записи», хотя на самом деле они операции и чтения, и записи.
                    С точки зрения записи в top, парой к release мог бы быть guard.protect( m_Top ), если бы он использовал acquire семантику (но это, вероятно, не так, и он использует relaxed).

                    Мог бы, но здесь как раз и проявляется семантика: операции с контейнером и с Hazard Pointer'ом — это разные семантические уровни (HP на уровень глубже и играет вспомогательную роль). На самом деле в глубине HP есть m_Top.load( acquire ). Но я не уверен, что этот acquire-load обеспечит нам синхронизацию push и pop.
                    Верно я понимаю, что рассматривая семантику мы как бы говорим, что если происходит push/pop, то менять их местами нельзя (ведь стек может быть пуст), а pop/push — пожалуйста (ну вытолкнем мы 2й элемент, а не 1й, ну бывает).

                    Да, можно сказать и так.

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

              Самое читаемое