Lock-free структуры данных. Concurrent maps: rehash, no rebuild

Пройдем по следам C++ 2015 Russia ^[1] далее.
В предыдущей ^[2] статье мы рассмотрели алгоритм для lock-free ordered list и на его основе сделали простейший lock-free hash map. У этого hash map есть недостаток: размер хеш-таблицы постоянен и не может быть изменен в процессе роста числа элементов в контейнере. Это не представляет проблемы, если мы заранее примерно представляем требуемый объем контейнера. А если нет?

Процедура увеличения, равно как и уменьшения, размера хеш-таблицы (rehashing) довольно тяжелая

Как видно даже из этой простой картинки, при rehasing'е ключи перераспределяются по другим слотам новой хеш-таблицы, — происходит полная перестройка hash map. Это довольно трудно реализовать атомарно или хотя бы без блокировок.
Многократно мною упоминаемый Nir Shavit совместно с Ori Shalev посмотрел на проблему с другой стороны: хорошо, мы не можем атомарно перераспределить ключи по новым слотам (bucket'ам), но, быть может, мы можем просто вставить новый bucket в уже существующий, таким образом разбивая (splitting) его на две части? Эта идея легла в основу разработанного ими в 2003 году алгоритма split-ordered list ^[3].

Split-ordered list

Нельзя просто так взять ^[4] и вставить новый bucket, – см. рисунок выше: ключи при rehashing'е перераспределяются между bucket'ам, а нам требуется, чтобы их позиции не изменялись. Мы хотим чего-то странного такого:

В основе лежит уже рассмотренный нами lock-free ordered list. В нем появилось два типа узлов: регулярные узлы (овальные) и вспомогательные (sentinel) узлы (квадратные). Вспомогательные узлы играют роль меток начала bucket'ов и никогда не удаляются; в хеш-таблице находятся указатели на эти вспомогательные узлы.
Глядя на этот рисунок, вы можете спросить: список упорядоченный, но этого не видно, — ключи расположены хаотично, в чем дело? Ответ: список упорядоченный, но критерий порядка мы изобретем чуть позже.
Итак, мы имеем хеш-таблицу с двумя слотами, указывающими на вспомогательные узлы. Размер списка равен 4 (вспомогательные узлы не учитываются при подсчете количества элементов), load factor равен 2 (это мое волюнтаристское решение). Мы хотим вставить новый элемент с ключом 10:

При попытке вставки нового элементы мы выясняем, что наш список переполнен – число элементов становится 5, число bucket'ов равно 2, 5/2 > load factor, — надо расширять таблицу T[]. Предположим, мы каким-то образом её расширили — в ней стало 4 bucket'а, два первых инициализированы, два последних — нет. Новый элемент 10 должен попасть в bucket 2 ( 10 mod 4 = 2, здесь и далее я считаю для наглядности, что hash(key) == key), который ещё не инициализирован. Значит, сначала нужно вставить вспомогательный элемент 2, то есть сделать расщепление какого-то существующего bucket'а. Для начала надо найти этот существующий bucket, называемый родительским (parent):

Расщепление bucket'а, пожалуй, самый тонкий момент в алгоритме. Родительский bucket, пока нам не известный, должен находиться в первой половине хеш-таблицы, то есть в нашем случае это bucket 0 или 1.
Bucket – это hash(key) mod 2**(m+1), где 2**(m+1) — размер хеш-таблицы. Новый bucket расщепляет родительский, то есть разделяет элементы родительского bucket'а на два лагеря: одни входят в parent bucket, а вторые — в parent_bucket + 2**m. Отсюда следует, что для нового bucket 2 родительский — это bucket 0.
На C++ процедура вычисления родительского bucket'а выглядит очень просто:

        size_t parent_bucket( size_t nBucket )
        {
            assert( nBucket > 0 );
            return nBucket & ~( 1 << MSB( nBucket ) );
        } 

где MSB – most significant bit – номер старшего единичного бита.

Итак, для вставки элемента 10 прежде всего следует создать новый bucket 2 и вставить его в bucket 0. У нас есть готовый алгоритм упорядоченного списка, так что самое время определиться, как же должен быть упорядочен наш split-ordered list.
Заметим, что все операции, которые мы до сих пор делали, были основаны на арифметике по модулю степени двойки. Посмотрим на бинарное представление ключей:

А теперь — внимание: если прочесть бинарные значения ключей справа налево, мы получим отсортированный список:

Такие обращенные хеш-значения я называю shah.
Итак, критерий сортировки списка — по обращенным (прочитанным справа налево) хеш-значениям ключей.

        uint32_t reverse_bit_order( uint32_t x )
        {
            // swap odd and even bits
            x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1);
            // swap consecutive pairs
            x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2);
            // swap nibbles ...
            x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4);
            // swap bytes
            x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8);
            // swap 2-byte long pairs
            return ( x >> 16 ) | ( x << 16 );
        }

Получается интересно: bucket'ы вычисляются по хеш-значениям ключей, а сортировка — по обращенным хеш-значениям. Главное — не запутаться.
Но и это ещё не все. Взглянув на рисунок ещё раз, мы увидим, что узел с ключом 2 уже есть в списке, — это регулярный узел, а нам надо вставить вспомогательный с тем же самым ключом. Вспомогательные и регулярные узлы — совершенно разные объекты, даже по внутреннему строению: регулярные узлы содержат ключ и значение (value), а вспомогательные, служащие метками начала bucket'ов, — только хеш-значения. Регулярный узел может быть удален из списка, а вот вспомогательный — никогда. Следовательно, нам надо как-то различать эти два типа узлов. Авторы предлагают использовать для этого старший бит хеш-значения (в обращенном хеш-значении это будет младший бит): в хеш-значениях регулярных узлов старший бит выставляется в 1, а во вспомогательных — в 0:

Этот бит также играет роль ограничителя при поиске ключа в bucket'е, — мы никогда не вылезем за границы bucket'а.

Подведем итог всему вышесказанному. Вставка ключа 10 производится в два этапа: сначала добавляется новый вспомогательный узел 2 в родительский bucket 0:

Затем в bucket 2 вставляется элемент с ключом 10:

В основе split-ordered list лежит lock-free ordered list, который мы рассматривали в предыдущей статье ^[2], так что никаких трудностей со вставкой/удалением быть не должно. Кстати, про удаление, — никаких особенностей алгоритм удаления из split-ordered list не имеет, мы просто вычисляем по ключу bucket и вызываем функцию удаления из lock-free list с началом во вспомогательном узле этого bucket'а. Вспомогательные узлы не удаляются никогда, то есть хеш-таблица в split-ordered list может только динамически расти, но не сжиматься.

Алгоритм split-ordered list интересен тем, что он противоречит всем каноническим представлениям о хеш-таблицах. Вспомним, Кнут в своей монографии доказывает, что для построения хорошей хеш-таблицы её размер должен быть простым числом, следовательно, вся арифметика должна быть по модулю простых чисел. Для split-ordered list все наоборот: этот алгоритм существенно полагается на бинарное представление хеш-значений, вся арифметика ведется по модулю степени двойки. Такая заточенность под 2**N очень хорошо ложится на современные процессоры, которые, несмотря на значительный прогресс, всё ещё тупят на целочисленном делении, а вот замена деления на сдвиги им очень нравится.

Остался один невыясненный вопрос — динамическое расширение хеш-таблицы. Авторы предлагают сегментную организацию хеш-таблицы:

Вместо единого массива T[N] используется массив сегментов Segment[M], создаваемый при инициализации объекта split-ordered list. Здесь M — степень двойки. Номер сегмента — это старшие биты хеш-значения. Каждый сегмент указывает на таблицу T[N], эти таблицы создаются динамически по необходимости, кроме таблицы Segment[0], которая инициализируется при создании объекта split-ordered list (помните, я отмечал, что bucket 0 всегда должен быть).
При такой организации на момент создания объекта-списка все же нужно знать предполагаемое число элементов, чтобы вычислить размер таблицы сегментов M (никакого особого алгоритма этого вычисления нет — мною эмпирически подобраны некие границы, чтобы как Segment[], так и каждая T[] были соизмеримы по размеру). Но все же алгоритм допускает рост хеш-таблицы, пусть и в таком непривычном виде.

Итоги

В этой статье рассмотрен весьма оригинальный алгоритм lock-free split-ordered list, позволяющий делать rehash без rebuild, то есть без перестройки хеш-таблицы. Этот алгоритм также интересен тем, что в своей основе имеет обычный lock-free ordered list и может быть использован как полигон для отладки различных реализаций упорядоченных списков.
Реализация данного алгоритма в libcds ^[5] показывает очень неплохие результаты в тестах, но все же немного хуже, чем простейший hash map, описанный в предыдущей статье. Этому есть две причины:

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

С архитектурной точки зрения, очень увлекательно было этот алгоритм разрабатывать, чтобы выделить ordered list как стратегию для split-ordered list.

В следующей статье я расскажу об ещё одной реинкарнации lock-free ordered list. На сей раз будем строить не hash map, а упорядоченный map.

Автор: khizmax

Источник ^[16]