Хэш-таблицы чрезвычайно активно используются в ядре Linux, чтобы увеличить скорость доступа к различным объектам. Хэш-таблицы намного увеличивают скорость доступа по сравнению с обычным линейным поиском. Но всегда остаётся возможность для оптимизации. В последние годы немало сделано для этого. В частности, реализован метод read-copy-update (RCU), позволяющий добавлять и удалять ячейки из хэш-таблицы без блокировки доступа к ней.
Ещё один метод улучшения производительности — изменение размера хэш-таблицы. Скорость поиска объекта напрямую зависит от размера таблицы. Поэтому, если у нас есть большая таблица с малым количеством элементов, то мы впустую расходуем память и жертвуем производительностью. Но ничего не поделаешь: ядро Linux до сих пор не позволяло изменить размер таблицы после её первоначального создания.
Ещё три года назад академический исследователь Джош Триплетт (Josh Triplett) из университета штата Портленд опубликовал научную работу, а затем и защитил диссертацию о релятивистских хэш-таблицах, размер которых можно менять в процессе работы. Триплетт даже опубликовал код для ядра Linux.
Уникальная особенность релятивистских хэш-таблиц — изменение размера без блокировки доступа к ним. В процессе многоступенчатого перестроения таблицы (сжатия или расширения) сохраняется совместный доступ ко всем ячейкам. Название «релятивистский» объясняется тем, что при совместном доступе разные CPU «видят» разное состояние хэш-таблицы, которая в этот момент осуществляет своё перестроение.
Прошло три года, и в ядре Linux 3.17 наконец-то появятся релятивистские хэш-таблицы. Разработчик Томас Граф (Thomas Graf) предложил патч для сетевой подсистемы управления сокетами netlink. Это только начало. Поскольку соответствующий алгоритм уже проник в ядро Linux, то в будущем его можно использовать для управления и другими хэш-таблицами. Всё это позволит высвободить память и увеличить производительность ядра Linux.
Что ж, лучше поздно, чем никогда.
Алгоритм сжатия таблицы
Алгоритм расширения таблицы
