Параллельное проектирование структуры данных

Question

Я пытаюсь найти лучшую структуру данных для использования на сервере C ++ с высокой пропускной способностью. Структура данных будет использоваться для хранения от нескольких до нескольких миллионов объектов, и сортировка не требуется (хотя уникальный ключ сортировки может быть предоставлен очень дешево).

Требования заключаются в том, что он может поддерживать эффективную вставку, в идеале O (1), умеренно эффективное удаление и эффективный обход. Не требуется поддержка операции поиска (кроме той, которая может потребоваться для удаления).

Суть в том, что он должен быть потокобезопасным в отношении изменений, в то время как другие потоки перечисляют структуру данных. Это означает, что простое красно-черное дерево не работает, так как один поток не может вставить элемент (и выполнить необходимые повороты дерева), не испортив курсоры других потоков.

не допустимо использовать блокировку чтения / записи и отложить операции записи до завершения всех считывателей, поскольку операции чтения могут быть долгоживущими. Неважно, видны ли вставки, которые происходят, когда есть читатель, этому читателю или нет.

Объем памяти также очень важен, а маленький, очевидно, лучше!

Какие есть предложения?

Ответ на комментарий:

Спасибо за ответы.

Нет, вставки не могут сделать недействительными существующие итераторы. Итераторы могут видеть или не видеть новую вставку, но они должны видеть все, что увидели бы, если вставка не произошла.

Требуется удаление, однако из-за правил более высокого уровня я могу гарантировать, что итератор никогда не будет остановлен для элемента, доступного для удаления.

Блокировка на узел для курсора слишком сильно повлияет на производительность. Может быть несколько потоков, читающих одновременно, и любая горячая точка памяти, которую несколько потоков используют в блокировке, убивает пропускную способность памяти (как мы обнаружили трудным путем!). Даже простое число читателей с несколькими потоками, вызывающими InterlockedIncrement, не может быть правильно масштабировано.

Я согласен, что связанный список, вероятно, лучший подход. Удаление происходит редко, поэтому уплата штрафа памяти за обратные указатели для поддержки удаления O (1) обходится дорого, и мы можем вычислять их отдельно по требованию, поскольку удаление, как правило, представляет собой пакетные операции.

К счастью, вставка в связанный список не требует какой-либо блокировки для считывателей, если указатели обновляются во вставленном узле до изменения указателя заголовка.

Интересна идея блокировки-копирования-разблокировки. Объем данных слишком велик для того, чтобы он работал по умолчанию для читателей, но его можно использовать для писателей, когда они сталкиваются с читателями. Блокировка чтения / записи защищает всю структуру, а запись клонирует структуру данных, если она сталкивается с читателем. Пишет гораздо реже, чем читает.

Answer 1

Лично мне очень нравятся постоянные неизменяемые структуры данных в ситуациях с высокой степенью параллелизма. Я не знаю ничего конкретно для C ++, но Rich Hickey создал несколько превосходных (и невероятно быстрых) неизменяемых структур данных в Java для Clojure . В частности: vector, hashtable и hashset. Их не слишком сложно портировать, поэтому вы можете рассмотреть один из них.

Чтобы разработать немного больше, постоянные неизменяемые структуры данных действительно решают много проблем, связанных с параллелизмом. Поскольку сама структура данных является неизменной, нет проблем с одновременным чтением / повторением нескольких потоков (при условии, что это постоянный итератор). «Запись» также может быть асинхронной, потому что она на самом деле не записывает в существующую структуру, а создает новую версию этой структуры, которая включает в себя новый элемент. Эта операция становится эффективной ( O (1) во всех структурах Хикки) благодаря тому, что вы на самом деле не копируете все. Каждая новая версия разделяет большую часть своей структуры со старой версией. Это повышает эффективность использования памяти и значительно повышает производительность по сравнению с простой техникой копирования при записи.

При неизменных структурах данных единственное время, когда вам действительно нужно синхронизироваться, - это фактически записывать данные в ячейку ссылки. Поскольку доступ к памяти является атомарным, даже это обычно может быть без блокировки. Единственное предостережение: вы можете потерять данные между потоками (условия гонки). Структура данных никогда не будет повреждена из-за параллелизма, но это не означает, что противоречивые результаты невозможны в ситуациях, когда два потока создают новую версию структуры на основе одного старого и пытаются записать свои результаты (один из них будет «победа» и другие изменения будут потеряны). Чтобы решить эту проблему, вам нужно либо иметь блокировку для «операций записи», либо использовать что-то вроде STM . Мне нравится второй подход для простоты использования и пропускной способности в системах с низким уровнем коллизий (записи в идеале не блокируют и читают никогда блок), но любой из них будет работать.

Вы задали сложный вопрос, на который не очень хороший ответ. Безопасные для параллелизма структуры данных сложно написать, особенно когда они должны быть изменяемыми. Полностью свободные от блокировок архитектуры доказуемо невозможны при наличии общего состояния, поэтому вы можете отказаться от этого требования. Лучшее, что вы можете сделать, - это минимизировать требуемую блокировку, следовательно, неизменяемые структуры данных.

Answer 2

Связанные списки, безусловно, ответ здесь. Вставка и удаление в O (1), итерация от одного узла к следующему в O (1) и стабильность между операциями. std::list гарантирует все это, включая то, что все итераторы действительны, если элемент не удален из списка (это включает указатели и ссылки на элементы). Для блокировки вы можете просто обернуть список в класс блокировки или написать собственный класс списка (в этом случае вы не сможете использовать std::list, который поддерживает блокировку на основе узлов - например, вы можете заблокировать определенные области списка для использования, в то время как другие потоки выполняют операции над различными областями. То, что вы используете, во многом зависит от ожидаемого типа одновременного доступа - если несколько операций над различными частями списка будут действительно обычными, напишите свои собственные, но помните вы будете помещать объект взаимного исключения в каждый узел, что неэффективно при использовании пространства.

Answer 3

Извинения за двойной ответ ...

Поскольку записи выполняются довольно редко, действительно следует рассмотреть возможность использования STM вместо блокировки. STM - это форма оптимистической блокировки, которая означает, что она сильно смещена в производительности по отношению к системам без столкновений (например, меньше записей). В отличие от этого, пессимистическая блокировка (блокировка-запись-разблокировка) оптимизирована для систем с интенсивным столкновением (например, много записей). Единственный недостаток STM в том, что он практически требует использования неизменяемых структур данных в ячейках TVar, в противном случае вся система выходит из строя. Лично я не думаю, что это проблема, поскольку приличная неизменяемая структура данных будет такой же быстрой, как и изменяемая (см. Мой другой ответ), но это стоит рассмотреть.

Answer 4

Я не уверен, упоминал ли кто-нибудь об этом, но я бы черпал вдохновение из Java ConcurrentHashMap. Он предлагает обход, поиск и вставку без блокировки или ожидания. Единственная блокировка происходит, когда вы нашли группу данных, соответствующую хеш-ключу, и вы просматриваете эту корзину (то есть вы ТОЛЬКО блокируете корзину, а не фактическую карту хеша). «Вместо единой блокировки коллекции ConcurrentHashMap использует фиксированный пул блокировок, которые образуют разделение по коллекции блоков».

Более подробную информацию о фактической реализации можно найти здесь . Я считаю, что все, что показано в реализации, может быть так же легко сделано с C ++.

Итак, давайте рассмотрим ваш список требований:

1. High throughput. CHECK
2. Thread safe. CHECK
3. Efficient inserts happen in O(1). CHECK
4. Efficient removal (with no data races or locks). CHECK
5. VERY efficient traversal. CHECK
6. Does not lock or wait. CHECK
7. Easy on the memory. CHECK
8. It is scalable (just increase the lock pool). CHECK

Вот пример карты. Запись:

protected static class Entry implements Map.Entry {
    protected final Object key;
    protected volatile Object value;
    protected final int hash;
    protected final Entry next;
    ...
}

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

Answer 5

Единственный способ, которым я думаю, что это достижимо, - это использовать нечто похожее на протокол многоверсионного параллелизма, используемый в базах данных, таких как oracle / postgresql и т. Д. Это гарантирует, что читатели не блокируют читателей, писатели не блокируют читателей, а писатели блокируют только те писатели, которые обновляют один и тот же кусок данных. Это свойство писателей, блокирующих писателей, которые обновляют один и тот же фрагмент данных, важно в параллельном мире программирования, в противном случае возможны несоответствия данных / системы. Для каждой операции записи в структуру данных вы делаете снимок структуры данных или, по крайней мере, часть узлов структуры данных, затронутых операцией записи, в другое место в памяти перед выполнением записи. Поэтому, когда выполняется запись, поток считывателя запрашивает чтение части данных из части записи, вы всегда обращаетесь к последнему снимку и выполняете итерацию по этому снимку, предоставляя согласованное представление данных всем читателям. Снимки являются дорогостоящими, так как они потребляют больше памяти, но да, для ваших конкретных требований эта методика является правильной. И да, используйте блокировки (мьютекс / семафор / спин-блокировка) для защиты операции записи от других потоков / процессов записи, которым необходимо обновить тот же фрагмент данных.

Answer 6

У вас есть 3 типа задач:

1. итерация (медленная)
2. вставка (быстрая)
3. удаление (быстрое)

Если близкая согласованность достаточно хороша, следите за количеством активных итерационных задач.

Если итерационные задачи активны, и новые задачи вставки или удаления поступают в очередь для этих задач для последующей обработки (но вы можете сразу же вернуть их вызывающей стороне)

Как только последняя итерация, если завершенный процесс поставлен в очередь, вставляется и удаляется.

Если запрос на итерацию поступает во время ожидания вставки или удаления, поставьте его в очередь.

Если запрос на итерацию поступает, когда выполняются только итерации, просто отправьте его и выполните итерацию.

Вы все равно должны написать итерацию как можно быстрее, сделав копию данных, для которых вы выполняете итерацию, и затем обработать эти данные в клиенте, если фактическая обработка данных занимает намного больше времени, чем сама итерация.

Я бы реализовал основную коллекцию с помощью хеш-таблицы или stl: карта могла бы быть достаточно быстрой. Запросы на вставку / удаление могут быть поставлены в очередь в виде списка.

Answer 7

Если вам не нужен порядок сортировки, не используйте красное / черное дерево или что-либо еще, что по своей природе сортирует.

Ваш вопрос недостаточно точно задан в отношении взаимодействия между операциями чтения и записи. Было бы хорошо, если бы "чтение" было реализовано с помощью блокировки + копирования + разблокировки, а затем использовать новую копию?

Возможно, вы захотите прочитать о seqlocks в http://en.wikipedia.org/wiki/Seqlock, и о процессах «без блокировки» в целом - хотя, возможно, вы захотите максимально ослабить ваши требования - реализация хеш-таблицы без блокировок является крупным предприятием.

Answer 8

Я думаю, что связанный список должен отвечать вашим требованиям. Обратите внимание, что вы можете заблокировать только те узлы, которые были изменены (т.е. удалены / добавлены), поэтому читатели большую часть времени смогут работать в полном параллелизме с авторами. Этот подход требует блокировки на узел связанного списка, однако это не обязательно. Вы можете иметь ограниченное количество блокировок, и тогда несколько узлов будут сопоставлены одной и той же блокировке. То есть, имея массив из N блокировок и узлов с номерами 0..M, вы можете использовать блокировку (NodeId% N) для блокировки этого узла. Это могут быть блокировки чтения-записи, и, контролируя количество блокировок, вы можете контролировать степень параллелизма.

Answer 9

Я немного опоздал на вечеринку. Но если кто-то все еще ищет практическое решение этой проблемы и еще не определился с сервером, позвольте мне предложить Google App Engine . Их хранилище данных оптимизировано для таких требований.

Answer 10

FWIW, это тривиально решить, если у вас есть сборщик мусора. Например, в F # вы можете просто использовать изменяемую ссылку на связанный список или чисто функциональную карту (сбалансированное двоичное дерево) без каких-либо блокировок. Это работает, потому что структуры данных являются неизменными, и запись ссылки (для обновления после записи) является атомарной, поэтому одновременные читатели гарантированно увидят либо старую, либо новую структуру данных, но никогда не будут повреждены. Если у вас есть несколько писателей, вы можете их сериализовать.

Однако, это гораздо сложнее решить в C ++ ...