Lock-free структуры данных. Итераторы: multi-level array

В предыдущих частях опуса (1, 2, 3) мы рассмотрели внутреннее строение lock-free map и убедились, что все основные операции — поиск, добавление и удаление ключа — могут быть выполнены без глобальных блокировок и даже в lock-free манере. Но стандартный std::map поддерживает ещё одну очень полезную абстракцию — итераторы. Возможно ли реализовать итерабельный lock-free map?
Ответ на этот вопрос — под катом.

Ещё год назад я был уверен, что итераторы в принципе нереализуемы для lock-free контейнеров. Судите сами: итератор позволяет обойти все элементы контейнера; но в мире lock-free содержимое контейнера постоянно меняется, что же считать под «обойти все элементы»?

Итерирование — обход элементов контейнера — занимает некоторое время, за которое одни элементы будут удалены из контейнера, другие — добавлены, но должно существовать некоторое подмножество stable (возможно, пустое) элементов, которые присутствуют в контейнере за все время обхода — от list.begin() до list.end(). Помимо них, мы можем посетить некоторые из добавленных элементов, как и некоторые из удаленных, — как карта ляжет. Очевидно, что задача посетить все элементы в lock-free map невыполнима, — мы не можем заморозить состояние нашего контейнера на все время обхода; такая заморозка фактически означает запрет другим потокам выполнять над контейнером модифицирующие операции, что равносильно блокировке.

Итак, будем считать обходом конкурентного контейнера гарантированное посещение всех узлов из подмножества stable.
Кроме вопроса «что считать обходом конкурентного контейнера», существует две проблемы:
Проблема 1. Итератор — это по сути специализированный указатель на элемент контейнера. Используя итератор, мы получаем доступ к самому элементу. Но в конкурентном контейнере элемент, на котором позиционирован итератор, может быть в любой момент удален. То есть итератор может в любой момент стать невалидным, — указывать на удаленный элемент, то есть на мусор:

Решением данной проблемы в схеме Hazard Pointer является собственно hazard pointer. Вспомним, что схема HP гарантирует, что пока указатель объявлен как hazard, он (указатель) не может быть физически удален, то есть он не может превратиться в тыкву мусор. Введем следующую полезную абстракцию — защищенный указатель guarded_ptr:

template <typename T>
struct guarded_ptr {
   hp_guard hp;    // защищает элемент
   T *      ptr;   // элемент контейнера
   guarded_ptr(std::atomic<T *>& p) 
   {
       ptr = hp.protect( p ); 
   }
   ~guarded_ptr() { hp.clear(); }
   T * operator ->() const { return ptr; }
   explicit operator bool() const 
             { return ptr != nullptr; }
};

Как видим, guarded_ptr – это просто указатель с hazard pointer'ом. Hazard pointer hp защищает указатель на элемент ptr, предотвращая его физическое удаление. Теперь если даже некий поток B удалит элемент, на который позиционирован итератор, этот элемент будет исключен из контейнера, но физически не будет удален, пока hazard pointer итератора содержит ссылку на данный элемент.
Таким образом, в схеме HP класс итератора будет выглядеть следующим образом:

template <typename T>
class iterator {
   guarded_ptr<T>  gp;
public:
   T* operator ->() { return gp.ptr; }
   T& operator *()  { return *gp.ptr; }
   iterator& operator++();
};

urcu.lock(); // вход в эпоху
for ( auto it = m.begin(); it != m.end(); ++it ) {
	// ...
}
urcu.unlock();  // выход из эпохи

Проблема 2: переход к следующему элементу.

Если некий поток B удалит элемент, следующий за тем, на который позиционирован итератор — в данном случае 42, — операция инкрементирования итератора приведет к обращению к удаленному элементу, то есть к мусору.
Эта проблема посложнее, чем первая, так как потоки ничего не знают о том, что мы обходим контейнер, и вольны удалять/добавлять любые элементы. Можно подумать о том, чтобы каким-то образом помечать элемент, на который указывает итератор, и при удалении элемента анализировать такой флаг, но это как минимум усложнит внутреннее строение контейнера (а как максимум — такие рассуждения ни к чему не приведут). Есть другой путь, который нам подскажет интересная структура данных — multi-level array.

Multi-level array

Эта структура данных предложена в 2013 году Стивом Фельдманом (Steve Feldman) и представляет собой ассоциативный контейнер, то есть hash map.

Представим, что хеш — это битовая строка постоянной длины. Будем рассматривать биты этой строки как индексы в многоуровневом массиве: первые M бит — это индекс в головном масиве head array (на рисунке M=4, то есть размер head array равен 2**4 = 16), следующие порции по N бит — это индексы в нижележащих массивах node array (на рисунке N = 2 и размерность node array равна 2**2 = 4). Элемент массива может быть

• пуст
• указателем на данные
• указателем на массив следующего уровня

Пустой multi-level array состоит только из head array, у которого все ячейки — пустые.

Добавление данных data с ключом key в multi-level array происходит по следующему алгоритму:

• 1. вычисляем хеш ключа h = hash( key )
• 2. Берем первые M бит хеша h – это индекс i ячейки в head array
• 3a. Если ячейка пуста (head_array[i] == nullptr), то помещаем данные в неё: head_array[i].CAS( nullptr, &data ) — и выходим. Так как у нас lock-free контейнер, мы используем атомарные операции, в данном случае — CAS (compare-and-swap, в терминах C++11 – это std::compare_exchange).
• 3b. Если ячейка содержит данные (head_array[i] = di), нужно её расщепить, то есть создать node array следующего уровня, поместить в него di и перейти к шагу 4.
• 3c. Если ячейка содержит указатель на нижележащий node array – перейти к шагу 4.
• 4. Текущий array – некий node array. Берем следующие N бит хеша ключа h, эти биты будут индексом i в текущем node array. Если все биты хеша исчерпаны — значит, в контейнере уже есть элемент с таким же хешем и вставка данных data заканчивается неудачей.
• 4a. Если ячейка пуста (current_node_array[i] == nullptr), то помещаем данные в неё: current_node_array[i].CAS( nullptr, &data ) — и выходим
• 4b. Если ячейка содержит данные (current_node_array[i] = di), нужно её расщепить, то есть создать node array следующего уровня, поместить в него di и перейти к шагу 4.
• 4c. Если ячейка содержит указатель на нижележащий node array – перейти к шагу 4.

Как видим, алгоритм вставки очень прост и интуитивно понятен — его легче нарисовать, чем описывать словами. Алгоритм удаления ещё проще: рассматривая хеш-значение удаляемого ключа как битовую строку, выделяя биты и интерпретируя их как индексы в массивах, мы спускаемся по ссылкам до массива, ячейка которого либо пуста, либо содержит данные. Если ячейка пуста, — значит, нашего ключа (точнее, его хеша) нет в контейнере и удалять нечего. Если ячейка содержит данные и ключ этих данных есть искомый ключ — меняем значение ячейки на nullptr с помощью атомарной операции CAS. Заметим, что при удалении мы просто обнуляем ячейку массива, сами node_array никогда не удаляются, — этот факт нам пригодится в дальнейшем.

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

struct array_slot  {
     union {
          T*   data;
           node_array*  array;
     };
     bool  is_array;  // признак, что содержит ячейка — data или array
};

Но у нас программирование необычное, и этот подход нам не подойдет. Необычность заключается в том, что мы должны оперировать атомарным примитивом CAS, который имеет ограничение на длину данных. То есть изменять значение ячейки и признака is_array мы должны уметь атомарно, одним CAS'ом.
Это не является проблемой, если вы читали предыдущую часть lock-free эпопеи и знаете, что есть такая вещь как marked pointer. Мы будем хранить признак is_array в младшем бите указателя ячейки массива:

template <typename T>
using array_slot = marked_ptr<T*, 3 >;

Таким образом, ячейка массива — это просто указатель, у которого мы используем последние 2 бита (маска 3 у marked_ptr) для внутренних флагов: один бит для признака «ячейка содержит указатель на массив следующего уровня», плюс ещё один бит для… а для чего?..
Посмотрим внимательно на алгоритм вставки. Шаги 3b и 4b говорят о расщеплении ячейки, то есть превращении её из ячейки, содержащей данные, в ячейку, содержащую указатель на нижележащий массив. Такое преобразование довольно длительно, так как требует:

• создания нового node_array;
• обнуления всех его элементов;
• поиска позиции в новом node_array для данных расщепляемой ячейки;
• записи в новый node_array в найденную позицию данных расщепляемой ячейки;
• и наконец, установки нового значения расщепляемой ячейки

Пока производятся все эти действия, расщепляемая ячейка находится в неопределенном состоянии. Именно это состояние мы и кодируем вторым младшим битом. Все операции над multi-level array, встретив флаг «ячейка расщепляется», ожидают окончания расщепления такой ячейки, используя активное ожидание (spinning) на этом флаге:

на рисунке черные данные — это добавляемый ключ Dn, синие — существующий D

Структура данных multi-level array проста и интересна, но её особенностями (хотел написать «недостатками», но это все же особенности) являются:

• она требует идеального хеширования. Идеальная хеш-функция — это такая хеш-функция h, которая для любых ключей k1 и k2 таких, что k1 != k2, дает разные хеш-значения: h(k1)!= h(k2). То есть multi-level array не допускает коллизий.
• ключи (или хеш-значения ключей) разного размера не поддерживаются. То есть ключ std::string переменной длины нельзя использовать как битовую строку.

Но если ваш ключ постоянного размера (или вы имеете идеальную хеш-функцию), multi-level array является очень хорошим lock-free контейнером, ИМХО.

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

Но для целей данной статьи важно одно свойство multi-level array: однажды созданный node array никогда не удаляется. А из этого вытекает мощное следствие: multi-level array поддерживает thread-safe итераторы, более того, это bidirectional-итераторы. В самом деле, раз node array не удаляются, итератор есть указатель на node array плюс индекс в node array, что есть «указатель» на ячейку:

class iterator {
    guarded_ptr<T> gp_;
    node_array*	 node_;
    int		 node_index_;
};

guarded_ptr здесь необходим, так как конкурентный поток может удалить данные, на которые позиционирован итератор; guarded_ptr препятствует физическому удалению. Получается, что итератор может указывать на элемент, который удален из контейнера — ещё одно неожиданное свойство lock-free структур данных. Но если хорошо подумать, такое свойство вполне объяснимо: в постоянно меняющемся мире, который представляют из себя конкурентные контейнеры, можно гарантировать только одно: на момент позиционирования итератора данная ячейка содержала валидные данные.
Указатель node_ на node_array и индекс в нем node_index_ необходимы в итераторе для перехода к следующему (или предыдущему) элементу контейнера, то есть они фактически определяют текущую позицию итератора в контейнере.
Интересно отметить, что если у нас ключи постоянного размера, а не хеш-значения, то обход multi-level array является упорядоченным.

Подводя итог, можно сказать: все же существуют конкурентные контейнеры, поддерживающие thread-safe итераторы, одним из таких контейнеров является multi-level array. Существуют ли другие?.. Можно ли создать итерируемый lock-free список, являющийся основой для многих интересных lock-free map?..
Ответ на этот вопрос — в следующей статье.

Автор: khizmax

Источник