Cтрие

Не путать с C-trie .

Параллельная хеш-три или Ctrie — это параллельная поточно-безопасная без блокировки реализация хеш-массива, отображаемого trie, . Он используется для реализации абстракции параллельной карты. Он имеет особенно масштабируемые одновременные операции вставки и удаления и эффективно использует память. Это первая известная параллельная структура данных, которая поддерживает O(1) атомарные снимки без блокировки .

Операция

Структура данных Ctrie представляет собой неблокируемый параллельный хэш-массив, отображенный в виде дерева, основанный на однословных инструкциях сравнения и обмена в системе с общей памятью. Он поддерживает одновременные операции поиска, вставки и удаления. Так же, как и хэш-массив, отображаемый trie , он использует все 32-битное пространство для хеш-значений, что снижает риск коллизий хэш-кода. Каждый узел может иметь до 32 подузлов, но для экономии памяти список подузлов представлен 32-битной битовой картой, где каждый бит указывает на наличие ветви, за которой следует неразреженный массив (указателей). до подузлов), длина которых равна весу Хэмминга растрового изображения.

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

Операция вставки Ctrie

На рисунке выше показана операция вставки Ctrie. Trie A пуст — атомарная инструкция CAS используется для замены старого узла C1 на новую версию C1, которая имеет новый ключ k1 . Если CAS не удался, операция перезапускается. Если CAS успешен, мы получаем дерево B. Эта процедура повторяется при нового ключа k2 добавлении (дерево C). Если два хэш-кода ключей в Ctrie конфликтуют, как в случае с k2 и k3 , Ctrie должен быть расширен как минимум еще на один уровень - дерево D имеет новый узел косвенности I2 с новым узлом C2, который содержит оба конфликтующих ключа. Дальнейшие инструкции CAS выполняются над содержимым узлов косвенности I1 и I2 — такие инструкции CAS могут выполняться независимо друг от друга, что позволяет выполнять одновременные обновления с меньшим количеством конфликтов.

Ctrie определяется указателем на корневой узел косвенного обращения (или корневой I-узел). Для Ctrie определены следующие типы узлов:

структура INode {    основной: CNode} структура CNode {    bmp: целое число    массив: Ветка[2^W]} Ветка: INode | СНОд структура SNode {    k: Тип ключа    v: ТипЗначения} 

C-узел — это узел ветвления. Обычно он содержит до 32 ветвей, поэтому W выше равно 5. Каждая ветвь может быть либо парой ключ-значение (представленной S-узлом), либо другим I-узлом. Чтобы избежать потери 32 записей в массиве ветвления, когда некоторые ветви могут быть пустыми, используется целочисленная битовая карта для обозначения того, какие биты заполнены, а какие пусты. Вспомогательный метод flagpos используется для проверки соответствующих битов хэш-кода для данного уровня и извлечения значения бита в растровом изображении, чтобы увидеть, установлено оно или нет, что указывает на то, есть ли ветвь в этой позиции или нет. Если бит есть, он также вычисляет его позицию в массиве ветвей. Для этого используется формула:

бит = bmp & (1 << ((хэш-код >> уровень) & 0x1F))pos = счетчик бит((бит - 1) & bmp) 

Обратите внимание, что операции рассматривают только I-узлы как изменяемые узлы — все остальные узлы никогда не изменяются после создания и добавления в Ctrie.

Ниже приведена иллюстрация псевдокода операции вставки:

def   вставка  (  k  ,   v  )    r   =   ЧТЕНИЕ  (  корень  )    if   iinsert  (  r  ,   k  ,   v  ,   0  ,   null  )   =   RESTART   вставка  (  k  ,   v  )  def   iinsert  (  i  ,   k  ,   v  ,   lev  ,   родительский  )    cn   =   ЧТЕНИЕ  (  i.main ​ ​  )    флаг  ,   pos   =   flagpos  (  k.hc ​ ​  ,   lev  ,   cn.bmp ​  ,  )    если   cn  .  bmp   &   флаг знак   равно   0   {      ncn   =   cn  .  вставлено  (  pos  ,   flag  ,   SNode  (  k  ,   v  ))      если   CAS  (  т.е.  }  main  ,   cn  ,   ncn  )   возвращает   OK      иначе   возвращает   RESTART    ,    cn  .  массив  (  поз  .)   совпадение   {      case   sin  :   INode   =>   {        return   iinsert  (  sin  ,   k  ,   v  ,   lev   +   W  ,   i  )      case   sn  :   SNode   =>        if   sn  .  k   ≠   k   {          nsn знак   равно   SNode  (  k  ,   v  )          nin знак   равно   INode  (  CNode  (  sn  ,   nsn  ,   lev   +   W  ))          ncn   =   cn  .  обновлено  (  pos  ,   nin  )          если   CAS  (  i.main  ,  ncn  ,   cn  ,   ncn  )   возвращает   ОК          иначе   возвращает   RESTART        }   else   {          =   .   cn  ,  обновлено  (  pos  ,   SNode  (  k  ,   v  ))          если   CAS  (  i  .  main  ,   cn  ,   ncn  )   возвращает   ОК,          иначе   возвращает   RESTART        }    } 

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

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

Преимущества Ctries

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

Ctries имеют логарифмические границы сложности основных операций, хотя и с низким постоянным коэффициентом из-за высокого уровня ветвления (обычно 32).

Ctries поддерживают линеаризуемую операцию моментального снимка без блокировок с постоянным временем. на основе информации, полученной из постоянных структур данных . Это прорыв в разработке параллельных структур данных, поскольку существующие параллельные структуры данных не поддерживают моментальные снимки. Операция моментального снимка позволяет реализовать линеаризуемый итератор без блокировок, операции размера и очистки — существующие параллельные структуры данных имеют реализации, которые либо используют глобальные блокировки, либо являются правильными только при условии отсутствия одновременных изменений в структуре данных. В частности, Ctries имеет операцию создания итератора O(1), операцию очистки O(1), операцию дублирования O(1) и операцию извлечения амортизированного размера O(logn).

Проблемы с попытками

Большинство параллельных структур данных требуют динамического выделения памяти, а параллельные структуры данных без блокировки на большинстве платформ полагаются на сбор мусора. Текущая реализация Ctrie написан для JVM, где сбор мусора обеспечивается самой платформой. Хотя можно сохранить одновременный пул памяти для узлов, совместно используемый всеми экземплярами Ctries в приложении, или использовать подсчет ссылок для правильного освобождения узлов, единственной реализацией, которая на данный момент имеет дело с ручным управлением памятью узлов, используемых в Ctries, является общий реализация lisp cl-ctrie , которая реализует несколько методов сбора мусора с остановкой и копированием и маркировкой и очисткой для постоянного хранилища с отображением в памяти. Указатели опасностей — еще одно возможное решение для правильного ручного управления удаленными узлами. Подобный метод может оказаться целесообразным и для управляемых сред, поскольку он может снизить нагрузку на сборщик мусора. Реализация Ctrie в Rust для этой цели использует указатели опасностей.

Реализации

Реализация Ctrie для Scala 2.9.x доступен на GitHub. Это изменяемая потокобезопасная реализация, которая обеспечивает прогресс и поддерживает линеаризуемые снимки без блокировок, O(1).

• Структура данных, подобная Ctries, использовалась в ScalaSTM. программная библиотека транзакционной памяти для JVM.
• Стандартная библиотека Scala (начиная с версии 2.13.x) включает реализацию Ctries с февраля 2012 года.
• Реализация Haskell доступна в виде пакета. и на GitHub.
• Автономные реализации Java доступны на GitHub для Java 17, Java 11 и Java 8. также для Java 6.
• CL-CTRIE — это реализация Common Lisp, доступная на GitHub.
• Вариант Ctrie только для вставки использовался для табличного представления в программах на Прологе.
• Реализация Go доступна как отдельный пакет.
• Реализация на Rust в своей реализации использует указатели опасностей для достижения синхронизации без блокировок.
• Были реализованы как управляемая, так и неуправляемая версия Ctrie C++ . Managed Ctrie Unmanaged Ctrie .
• Также доступна реализация Clojure Clojure Ctrie .

История

Ctries были впервые описаны в 2011 году Александром Прокопцем . Цитирую автора:

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

В 2012 году была опубликована пересмотренная версия структуры данных Ctrie. упрощение структуры данных и введение дополнительной операции атомарного моментального снимка с постоянным временем и без блокировки.

В 2018 году была предложена тесно связанная структура данных Cache-Trie: который дополнил Ctries вспомогательной, стабильно согласованной структурой данных кэша. Этот «кэш» представляет собой объект, подобный хеш-таблице, который делает все возможное, чтобы «угадать» соответствующий узел на более глубоком уровне дерева, и поддерживается таким образом, чтобы он был как можно ближе к уровню, на котором находится большинство элементов дерева. Было показано, что попытки кэширования амортизируют ожидаемую сложность O (1) всех основных операций.