Я пытаюсь найти лучшую структуру данных для использования на сервере C ++ с высокой пропускной способностью. Структура данных будет использоваться для хранения от нескольких до нескольких миллионов объектов, и сортировка не требуется (хотя уникальный ключ сортировки может быть предоставлен очень дешево).
Требования заключаются в том, что он может поддерживать эффективную вставку, в идеале O (1), умеренно эффективное удаление и эффективный обход. Не требуется поддержка операции поиска (кроме той, которая может потребоваться для удаления).
Суть в том, что он должен быть потокобезопасным в отношении изменений, в то время как другие потоки перечисляют структуру данных. Это означает, что простое красно-черное дерево не работает, так как один поток не может вставить элемент (и выполнить необходимые повороты дерева), не испортив курсоры других потоков.
не допустимо использовать блокировку чтения / записи и отложить операции записи до завершения всех считывателей, поскольку операции чтения могут быть долгоживущими. Неважно, видны ли вставки, которые происходят, когда есть читатель, этому читателю или нет.
Объем памяти также очень важен, а маленький, очевидно, лучше!
Какие есть предложения?
Ответ на комментарий:
Спасибо за ответы.
Нет, вставки не могут сделать недействительными существующие итераторы. Итераторы могут видеть или не видеть новую вставку, но они должны видеть все, что увидели бы, если вставка не произошла.
Требуется удаление, однако из-за правил более высокого уровня я могу гарантировать, что итератор никогда не будет остановлен для элемента, доступного для удаления.
Блокировка на узел для курсора слишком сильно повлияет на производительность. Может быть несколько потоков, читающих одновременно, и любая горячая точка памяти, которую несколько потоков используют в блокировке, убивает пропускную способность памяти (как мы обнаружили трудным путем!). Даже простое число читателей с несколькими потоками, вызывающими InterlockedIncrement, не может быть правильно масштабировано.
Я согласен, что связанный список, вероятно, лучший подход. Удаление происходит редко, поэтому уплата штрафа памяти за обратные указатели для поддержки удаления O (1) обходится дорого, и мы можем вычислять их отдельно по требованию, поскольку удаление, как правило, представляет собой пакетные операции.
К счастью, вставка в связанный список не требует какой-либо блокировки для считывателей, если указатели обновляются во вставленном узле до изменения указателя заголовка.
Интересна идея блокировки-копирования-разблокировки. Объем данных слишком велик для того, чтобы он работал по умолчанию для читателей, но его можно использовать для писателей, когда они сталкиваются с читателями. Блокировка чтения / записи защищает всю структуру, а запись клонирует структуру данных, если она сталкивается с читателем. Пишет гораздо реже, чем читает.