Конкурентная хэш-таблица или конкурентная хэш-карта — это реализация хэш-таблиц, позволяющая осуществлять одновременный доступ нескольким потокам с использованием хэш-функции . [ 1 ] [2]
Параллельные хэш-таблицы представляют собой ключевую параллельную структуру данных для использования в параллельных вычислениях , которая позволяет нескольким потокам более эффективно взаимодействовать для вычислений среди общих данных. [1]
Из-за естественных проблем, связанных с параллельным доступом, а именно с конкуренцией , способ и область, в которой таблица может быть доступна одновременно, различаются в зависимости от реализации. Более того, результирующее ускорение может быть нелинейным с количеством используемых потоков, поскольку необходимо разрешить конкуренцию, что приводит к накладным расходам на обработку . [1] Существует несколько решений для смягчения последствий конкуренции, каждое из которых сохраняет корректность операций с таблицей. [1] [2] [3] [4]
Как и их последовательный аналог, параллельные хэш-таблицы могут быть обобщены и расширены для соответствия более широким приложениям, например, позволяя использовать более сложные типы данных для ключей и значений. Однако эти обобщения могут негативно влиять на производительность и поэтому должны выбираться в соответствии с требованиями приложения. [1]
При создании параллельных хэш-таблиц функции, обращающиеся к таблице с выбранным алгоритмом хэширования, должны быть адаптированы для параллелизма путем добавления стратегии разрешения конфликтов. Такая стратегия требует управления доступом таким образом, чтобы конфликты, вызванные ими, не приводили к повреждению данных, в идеале увеличивая их эффективность при параллельном использовании. Херлихи и Шавит [5] описывают, как доступ к хэш-таблице без такой стратегии — в ее примере, основанном на базовой реализации алгоритма хэширования Cuckoo — может быть адаптирован для параллельного использования. Фан и др. [6] далее описывают схему доступа к таблице, основанную на хэшировании Cuckoo, которая не только является параллельной, но и сохраняет эффективность пространства ее хэш-функции, а также улучшает локальность кэша, а также пропускную способность вставок.
Когда хэш-таблицы не ограничены по размеру и, таким образом, могут увеличиваться/уменьшаться при необходимости, алгоритм хэширования должен быть адаптирован для обеспечения этой операции. Это влечет за собой изменение используемой хэш-функции для отражения нового ключевого пространства измененной таблицы. Параллельный алгоритм роста описан Майером и др. [1]
Mega-KV [7] — это высокопроизводительная система хранения ключей и значений, в которой используется хеширование кукушки , а индексация KV массово распараллеливается в пакетном режиме с помощью GPU. С дальнейшей оптимизацией ускорения GPU от Nvidia и Oak Ridge National Lab , Mega-KV достигла еще одного рекорда пропускной способности в 2018 году (до 888 миллионов операций «ключ-значение» в секунду). [8]
Как и любая структура параллельных данных, параллельные хэш-таблицы страдают от множества проблем, известных в области параллельных вычислений в результате конкуренции. [3] Примерами таких проблем являются проблема ABA , состояния гонки и взаимоблокировки . Степень, в которой эти проблемы проявляются или даже возникают вообще, зависит от реализации параллельной хэш-таблицы; в частности, какие операции таблица позволяет выполнять одновременно, а также ее стратегии смягчения проблем, связанных с конкуренцией. При обработке конкуренции главная цель та же, что и для любой другой параллельной структуры данных, а именно обеспечение корректности для каждой операции в таблице. В то же время, это, естественно, должно быть сделано таким образом, чтобы быть более эффективным, чем последовательное решение при использовании одновременно. Это также известно как управление параллелизмом .
Используя атомарные инструкции, такие как compare-and-swap или fetch-and-add , можно уменьшить проблемы, вызванные конкуренцией, гарантируя, что доступ будет завершен до того, как другой доступ получит возможность вмешаться. Такие операции, как compare-and-swap, часто накладывают ограничения на размер данных, которые они могут обрабатывать, что означает, что типы ключей и значений таблицы должны быть выбраны или преобразованы соответствующим образом. [1]
Используя так называемую аппаратную транзакционную память (Hardware Transactional Memory, HTM), табличные операции можно рассматривать как транзакции базы данных , [3] обеспечивая атомарность. Примером HTM на практике являются расширения транзакционной синхронизации .
С помощью блокировок операции, пытающиеся одновременно получить доступ к таблице или значениям в ней, могут быть обработаны таким образом, чтобы гарантировать правильное поведение. Однако это может привести к негативным последствиям для производительности, [1] [6] в частности, когда используемые блокировки слишком ограничительны, тем самым блокируя доступы, которые в противном случае не конкурировали бы и могли бы выполняться без возникновения каких-либо проблем. Необходимо принять дополнительные меры, чтобы избежать еще более критических проблем, которые угрожают корректности, таких как лайвлокинги, взаимоблокировки или голодание . [3]
Фазовая параллельная хэш-таблица группирует доступы, создавая фазы, в которых разрешен только один тип операции (т. е. чистая фаза записи), за которой следует синхронизация состояния таблицы по всем потокам. Формально доказанный алгоритм для этого предоставлен Шуном и Блеллоком. [2]
Широко используемый в ядре Linux [3] метод чтения-копирования-обновления (RCU) особенно полезен в случаях, когда количество чтений значительно превышает количество записей. [4]
Естественно, параллельные хеш-таблицы находят применение везде, где полезны последовательные хеш-таблицы. Преимущество, которое обеспечивает параллелизм, заключается в потенциальном ускорении этих вариантов использования, а также в увеличении масштабируемости. [1] Учитывая аппаратное обеспечение, такое как многоядерные процессоры , которые становятся все более способными к параллельным вычислениям, важность параллельных структур данных в этих приложениях неуклонно растет. [3]
Майер и др. [1] провели тщательный анализ различных реализаций параллельных хэш-таблиц, давая представление об эффективности каждой из них в различных ситуациях, которые могут возникнуть в реальных вариантах использования. Наиболее важные выводы можно суммировать следующим образом:
Как и ожидалось, низкая конкуренция приводит к положительному поведению в каждой операции, тогда как высокая конкуренция становится проблематичной, когда дело доходит до записи. Последнее, однако, является проблемой высокой конкуренции в целом, где преимущество параллельных вычислений сводится на нет из-за естественного требования к управлению параллелизмом, ограничивающего конкурирующий доступ. Результирующие накладные расходы приводят к худшей производительности, чем у идеальной последовательной версии. Несмотря на это, параллельные хэш-таблицы по-прежнему оказываются бесценными даже в таких сценариях с высокой конкуренцией, когда мы наблюдаем, что хорошо спроектированная реализация все еще может достигать очень высокого ускорения, используя преимущества параллелизма для одновременного чтения данных.
Однако реальные варианты использования параллельных хэш-таблиц часто представляют собой не просто последовательности одной и той же операции, а скорее смесь нескольких типов. Таким образом, когда используется смесь insertи findопераций, ускорение и вытекающая из этого полезность параллельных хэш-таблиц становятся более очевидными, особенно при наблюдении за findбольшими рабочими нагрузками.
В конечном итоге, конечная производительность параллельной хэш-таблицы зависит от множества факторов, основанных на ее желаемом применении. При выборе реализации важно определить необходимый уровень общности, стратегии обработки конфликтов и некоторые соображения о том, можно ли заранее определить размер желаемой таблицы или вместо этого следует использовать подход с увеличением.
std::unordered_map . Включены параллельные неупорядоченные мультикарты, которые позволяют нескольким значениям существовать для одного и того же ключа в параллельной неупорядоченной карте. [11] Кроме того, предоставляются параллельные хэш-карты, которые строятся на параллельной неупорядоченной карте и дополнительно позволяют выполнять параллельное стирание и содержат встроенную блокировку. [12]