Memory effective RCU B+ дерево

Помимо сложности в проектировании и реализации RCU-safe структуры данных, есть существенные накладные расходы, связанные с большим количеством аллокаций памяти при вставке и удалении. Несмотря на то, что в большинстве случаев такие решения направлены на увеличение производительности на стороне чтения, существуют случаи, когда производительность вставки и удаления ключей не менее важна. Например, для Maple tree, которое использует Linux kernel для управления VMA, можно выделить два типа нагрузки:

• чтение — speculative page faults;
• вставка/удаление — mmap()/munmap().

В докладе поделимся нашим опытом разработки memory effective RCU-safe B+ дерева и его интеграцией в Linux kernel для управления VMA.