Параллельная хеш-таблица - Concurrent hash table

Одновременный доступ к одной и той же хеш-таблице.

А одновременный хеш-таблица (параллельная хеш-карта) - это реализация хеш-таблиц, позволяющая одновременный доступ к несколько потоки используя хэш-функция.[1][2]

Таким образом, параллельные хеш-таблицы представляют собой ключ параллельная структура данных для использования в параллельные вычисления которые позволяют нескольким потокам более эффективно взаимодействовать для вычислений между общими данными.[1]

Из-за естественных проблем, связанных с одновременным доступом, а именно раздор - способ и область одновременного доступа к таблице различаются в зависимости от реализации. Кроме того, результирующее ускорение может не зависеть от количества используемых потоков, так как необходимо разрешить конфликт, что приведет к обработке накладные расходы.[1] Существует несколько решений для смягчения последствий разногласий, каждое из которых сохраняет правильность операций на столе.[1][2][3][4]

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

Параллельное хеширование

При создании параллельных хэш-таблиц функции, обращающиеся к таблице с выбранным алгоритмом хеширования, должны быть адаптированы для параллелизма путем добавления стратегии разрешения конфликтов. Такая стратегия требует управления доступом таким образом, чтобы конфликты, вызываемые ими, не приводили к повреждению данных, в идеале повышая их эффективность при параллельном использовании. Херлихи и Шавит[5] описать, как доступ к хеш-таблице без такой стратегии - в своем примере, основанном на базовой реализации Кукушка хеширования алгоритм - может быть адаптирован для одновременного использования. Fan et al.[6]дополнительно описать схему доступа к таблице, основанную на хешировании с кукушкой, которое не только является параллельным, но также сохраняет эффективность использования пространства для своей функции хеширования, а также улучшает локальность кеша, а также пропускную способность вставок.

Если размер хеш-таблиц не ограничен и, таким образом, разрешено увеличиваться / уменьшаться при необходимости, алгоритм хеширования необходимо адаптировать для выполнения этой операции. Это влечет за собой изменение используемой хэш-функции для отражения нового ключевого пространства таблицы с измененным размером. Алгоритм параллельного выращивания описан Maier et al.[1]

Мега-КВ[7] это высокопроизводительная система хранения ключей и значений, в которой кукушка используется, а индексирование KV массово распараллеливается в пакетном режиме с помощью GPU. При дальнейшей оптимизации ускорения графического процессора на NVIDIA и Национальная лаборатория Ок-Ридж, «Мега-КВ» поставила новый рекорд по пропускной способности в 2018 году (до 888 миллионов операций «ключ-значение» в секунду).[8]

Обработка разногласий

Одновременные обращения, вызывающие конкуренцию (отмечены красным).

Как и любая параллельная структура данных, параллельные хеш-таблицы страдают от множества проблем, известных в области параллельных вычислений, в результате конкуренции.[3] Примеры таких Проблема ABA, условия гонки, и тупиковые ситуации. Степень, в которой эти проблемы проявляются или даже возникают вообще, зависит от реализации параллельной хеш-таблицы; в частности, какие операции таблица позволяет выполнять одновременно, а также ее стратегии для смягчения проблем, связанных с конкуренцией. При обработке конфликтов основная цель такая же, как и для любой другой параллельной структуры данных, а именно обеспечение правильности каждой операции с таблицей. В то же время это, естественно, должно быть сделано таким образом, чтобы при одновременном использовании было более эффективным, чем последовательное решение. Это также известно как контроль параллелизма.

Атомарные инструкции

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

Использование так называемого оборудования Транзакционная память (HTM), операции с таблицами можно представить как транзакции базы данных,[3] обеспечение атомарности. Примером HTM на практике являются Расширения транзакционной синхронизации.

Блокировка

С помощью замки операции, пытающиеся одновременно получить доступ к таблице или значениям в ней, могут обрабатываться способом, обеспечивающим правильное поведение. Однако это может привести к снижению производительности,[1][6] в частности, когда используемые блокировки слишком строгие, таким образом блокируя доступ, который в противном случае не конкурировал бы и мог бы выполняться без каких-либо проблем. Необходимо принять дополнительные меры, чтобы избежать еще более серьезных проблем, угрожающих корректности, таких как блокировки, взаимоблокировки или голодание.[3]

Параллелизм фаз

Параллельные доступы сгруппированы в отдельные фазы.

Фазовая параллельная хэш-таблица группирует доступ, создавая фазы, на которых разрешен только один тип операции (то есть чистая фаза записи), за которой следует синхронизация состояния таблицы во всех потоках. Формально проверенный алгоритм для этого предложен Шуном и Блеллохом.[2]

Чтение-Копирование-Обновление

Широко используется в Ядро Linux,[3] читать-копировать-обновлять (RCU) особенно полезен в случаях, когда количество операций чтения намного превышает количество операций записи.[4]

Приложения

Естественно, параллельные хэш-таблицы находят применение везде, где используются последовательные хеш-таблицы. Преимущество параллелизма заключается в потенциальном ускорении этих сценариев использования, а также в повышенной масштабируемости.[1] Учитывая оборудование, такое как многоядерные процессоры которые становятся все более способными к параллельным вычислениям, важность параллельных структур данных в этих приложениях неуклонно растет.[3]

Анализ производительности

Maier et al.[1] провести тщательный анализ множества параллельных реализаций хэш-таблиц, чтобы получить представление об эффективности каждой из них в различных ситуациях, которые могут возникнуть в реальных случаях использования. Наиболее важные выводы можно резюмировать следующим образом:

ОперацияСпорПримечания
НизкийВысоко
найтиОчень высокое ускорение как при удачных, так и при неудачных уникальных находках, даже при очень высокой конкуренции
вставлятьДостигнуто высокое ускорение, высокая конкуренция становится проблематичной, когда ключи могут содержать более одного значения (в противном случае вставки просто отбрасываются, если ключ уже существует)
ОбновитьКак перезапись, так и изменение существующих значений достигают высокого ускорения, когда конкуренция остается низкой, в противном случае производительность хуже, чем при последовательной
УдалитьФазовый параллелизм достиг максимальной масштабируемости; Полностью параллельные реализации, где Удалить использует Обновить с фиктивные элементы были близко позади

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

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

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

Реализации

  • libcuckoo предоставляет параллельные хеш-таблицы для C /C ++ разрешая одновременное чтение и запись. Библиотека доступна на GitHub.[10]
  • Заправка строительных блоков предоставлять параллельные неупорядоченные карты для C ++ которые позволяют одновременную вставку и обход и хранятся в том же стиле, что и C ++ 11 std :: unordered_map интерфейс. Включены параллельные неупорядоченные мультиотображения, которые позволяют нескольким значениям существовать для одного и того же ключа в параллельной неупорядоченной карте.[11] Кроме того, предоставляются параллельные хэш-карты, которые основываются на параллельной неупорядоченной карте и дополнительно допускают одновременное стирание и содержат встроенную блокировку.[12]
  • Growt предоставляет одновременно растущие хеш-таблицы для C ++ на основе так называемого фольклор выполнение. На основе этой нерастущей реализации дается множество различных растущих хеш-таблиц. Эти реализации допускают одновременные чтения, вставки, обновления (в частности, обновление значений на основе текущего значения в ключе) и удаления (на основе обновления с использованием надгробия ). Кроме того, варианты на основе Intel TSX предоставлены. Библиотека доступна на GitHub.[1][13]
  • глупость предоставляет параллельные хеш-таблицы[14] за C ++ 14 и позже обеспечение чтения без ожидания и блокировки, сегментированный писатели. Как указано на странице GitHub, эта библиотека предоставляет полезные функции для Facebook.[15]
  • Junction предоставляет несколько реализаций параллельных хэш-таблиц для C ++ на основе атомарных операций, чтобы обеспечить безопасность потоков для любой заданной функции-члена таблицы. Библиотека доступна на GitHub.[16]

Смотрите также

Рекомендации

  1. ^ а б c d е ж грамм час я j k Майер, Тобиас; Сандерс, Питер; Дементьев, Роман (март 2019). «Параллельные хеш-таблицы: быстрые и общие (?)!». ACM-транзакции на параллельных вычислениях. Нью-Йорк, Нью-Йорк, США: ACM. 5 (4). СТАТЬЯ 16. Дои:10.1145/3309206. ISSN  2329-4949.
  2. ^ а б c Шун, Джулиан; Блеллох, Гай Э. (2014). «Фазо-параллельные хеш-таблицы для детерминизма». SPAA '14: Материалы 26-го симпозиума ACM по параллелизму в алгоритмах и архитектурах. Нью-Йорк: ACM. С. 96–107. Дои:10.1145/2612669.2612687. ISBN  978-1-4503-2821-0.
  3. ^ а б c d е ж Ли, Сяочжоу; Андерсен, Дэвид Дж .; Каминский, Михаил; Фридман, Майкл Дж. (2014). «Алгоритмические улучшения для быстрого одновременного хеширования кукушки». Труды Девятой Европейской конференции по компьютерным системам. EuroSys '14. Нью-Йорк: ACM. Статья № 27. Дои:10.1145/2592798.2592820. ISBN  978-1-4503-2704-6.
  4. ^ а б Триплет, Джош; Маккенни, Пол Э .; Уолпол, Джонатан (2011). «Масштабируемые параллельные хеш-таблицы с изменяемым размером с помощью релятивистского программирования». USENIXATC'11: Материалы конференции USENIX 2011 г. по ежегодной технической конференции USENIX. Беркли, Калифорния: Ассоциация USENIX. п. 11.
  5. ^ Херлихи, Морис; Шавит, Нир (2008). «Глава 13: Параллельное хеширование и естественный параллелизм». Искусство многопроцессорного программирования. Сан-Франциско, Калифорния, США: Морган Кауфманн Паблишерс Инк., Стр. 316–325. ISBN  978-0-12-370591-4.
  6. ^ а б Вентилятор, Бин; Андерсен, Дэвид Дж .; Каминский, Михаил (2013). «MemC3: компактный и параллельный кэш MemCache с более простым и более интеллектуальным хешированием». nsdi'13: Материалы 10-й конференции USENIX по проектированию и внедрению сетевых систем. Беркли, Калифорния: Ассоциация USENIX. С. 371–384.
  7. ^ Чжан, Кай; Ван, Кайбо; Юань, юань; Го, Лэй; Ли, Рубао; и Чжан, Сяодун (2015). "Mega-KV: возможность для графических процессоров максимизировать пропускную способность хранилищ ключей и значений в памяти ". Труды VLDB Endowment, Vol. 8, №11, 2015.
  8. ^ Чу, Цзин-Син; Потлури, Шрирам; Госвами, Аншуман; Венката, Манджунатх Горентла; Имам, Нинаанд; и Ньюберн, Крис Дж. (2018) "Разработка высокопроизводительных операций «ключ-значение» в памяти с использованием постоянных ядер графического процессора и OPENSHMEM »..
  9. ^ Документация Java ConcurrentHashMap
  10. ^ Репозиторий GitHub для libcuckoo
  11. ^ Блоки потоковой передачи concurrent_unordered_map и concurrent_unordered_multimap документация
  12. ^ Блоки потоковой передачи concurrent_hash_map документация
  13. ^ Репозиторий GitHub для Growt
  14. ^ Страница GitHub для реализации параллельных хэш-карт в безумии
  15. ^ Репозиторий GitHub для безумия
  16. ^ Репозиторий GitHub для Junction

дальнейшее чтение

  • Херлихи, Морис; Шавит, Нир (2008). «Глава 13: Параллельное хеширование и естественный параллелизм». Искусство многопроцессорного программирования. Сан-Франциско, Калифорния, США: Морган Кауфманн Паблишерс Инк., Стр. 299–328. ISBN  978-0-12-370591-4.