Войти
A concurrent hash-trie или Ctrie - это параллельная thread-safe lock-free реализация сопоставленного хэш-массива Три. Он используется для реализации параллельной абстракции карты. Он имеет особенно масштабируемые параллельные операции вставки и удаления и эффективно использует память. Это первая известная параллельная структура данных, которая поддерживает O (1), атомарные, безблокирующие моментальные снимки.
Структура данных Ctrie представляет собой неблокирующий параллельный хэш-массив , отображаемый trie на основе однословных инструкций сравнения и замены в системе с общей памятью. Он поддерживает одновременные операции поиска, вставки и удаления. Как и хэш-массив , сопоставленный с trie, он использует все 32-битное пространство для хеш-значений, что снижает риск коллизий хэш-кода. Каждый узел может выполнять до 32 подопытных попыток. Для экономии памяти каждый узел содержит 32-битное битовое отображение, где каждый бит указывает на наличие ветви, за которой следует массив длины, равный весу Хэмминга битовой карты.
Ключи вставляются путем выполнения атомарной операции сравнения и замены на узле, который необходимо изменить. Чтобы гарантировать, что обновления выполняются независимо и в правильном порядке, между каждым обычным узлом и его подгруппами вставляется специальный косвенный узел (I-узел).
Операция вставки Ctrie На рисунке выше показана операция вставки Ctrie. Trie A пусто - атомарная инструкция CAS используется для замены старого узла C1 на новую версию C1, которая имеет новый ключ k1. Если CAS не работает, операция перезапускается. Если CAS успешен, мы получаем дерево B. Эта процедура повторяется при добавлении нового ключа k2 (дерево C). Если два хэш-кода ключей в Ctrie сталкиваются, как в случае с k2 и k3, Ctrie должен быть расширен, по крайней мере, еще на один уровень - trie D имеет новый косвенный узел I2 с новым узлом C2, который содержит оба конфликтующих ключа. Дальнейшие инструкции CAS выполняются для содержимого узлов косвенного обращения I1 и I2 - такие инструкции CAS могут выполняться независимо друг от друга, что позволяет выполнять одновременные обновления с меньшим количеством конфликтов.
Ctrie определяется указателем на корневой косвенный узел (или корневой I-узел). Для структуры Ctrie определены следующие типы узлов:
структура INode {main: CNode} структура CNode {bmp: integer array: Branch [2 ^ W]} Branch: INode | Структура SNode SNode {k: KeyType v: ValueType}C-узел - это узел ветвления. Обычно он содержит до 32 ветвей, поэтому W выше 5. Каждая ветвь может быть парой ключ-значение (представленной S-узлом) или другим I-узлом. Чтобы избежать потери 32 записей в массиве ветвлений, когда некоторые ветви могут быть пустыми, используется целочисленное растровое изображение, чтобы обозначить, какие биты полны, а какие пусты. Вспомогательный метод flagpos используется для проверки соответствующих битов хэш-кода для заданного уровня и извлечения значения бита в битовой карте, чтобы увидеть, установлен ли он или нет, - указывая, есть ли ветвь в этой позиции или нет. Если есть бит, он также вычисляет свою позицию в массиве ветвей. Для этого используется формула:
bit = bmp (1 << ((hashcode>>level) 0x1F)) pos = bitcount ((bit - 1) bmp)
Обратите внимание, что операции обрабатывают только I-узлы как изменяемые узлы - все остальные узлы никогда не изменяются после создания и добавления в Ctrie.
Ниже показан псевдокод операции вставки:
def insert (k, v) r = READ (root) if iinsert (r, k, v, 0, null) = RESTART insert (k, v) def iinsert (i, k, v, lev, parent) cn = READ (i.main) flag, pos = flagpos (k.hc, lev, cn.bmp) if cn.bmp flag = 0 {ncn = cn.inserted (pos, flag, SNode (k, v)) if CAS (i.main, cn, ncn) return OK else return RESTART} cn.array (pos) match {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.updated (pos, nin) if CAS (i.main, cn, ncn) return OK else return RESTART} else {ncn = cn.updated (pos, SNode (k, v)) if CAS (i.main, cn, ncn) вернет OK else return RESTART}}Методы вставленного и обновленного узла возвращают новые версии C-узла со значением, вставленным или обновленным в указанной позиции, соответственно. Обратите внимание, что приведенная выше операция вставки является хвостовой рекурсией, поэтому ее можно переписать как while loop. Другие операции описаны более подробно в исходной статье о Ctries.
Структура данных оказалась верной - операции Ctrie обладают свойствами атомарности, линеаризуемости и свободы от блокировок. Операция поиска может быть изменена, чтобы гарантировать свободу ожидания.
Было показано, что Ctries сравнимы по производительности с параллельными списками пропуска, параллельными хэш-таблицы и аналогичные структуры данных с точки зрения операции поиска, немного медленнее, чем хеш-таблицы, и быстрее, чем списки пропуска, из-за более низкого уровня косвенных обращений. Однако они гораздо более масштабируемы, чем большинство параллельных хеш-таблиц, когда речь идет о вставках. Большинство параллельных хэш-таблиц плохо экономят память - когда ключи удаляются из хэш-таблицы, базовый массив не уменьшается. Ctries обладают тем свойством, что выделенная память всегда является функцией только текущего числа ключей в структуре данных.
Ctries имеют логарифмические границы сложности основных операций, хотя и с низким постоянным коэффициентом из-за высокий уровень ветвления (обычно 32).
Ctries поддерживают безблокировочную линеаризуемую операцию моментального снимка с постоянным временем, основанную на информации, полученной из постоянных структур данных. Это прорыв в проектировании параллельных структур данных, поскольку существующие параллельные структуры данных не поддерживают моментальные снимки. Операция моментального снимка позволяет реализовать свободные от блокировки, линеаризуемые операции итератора, размера и очистки - существующие параллельные структуры данных имеют реализации, которые либо используют глобальные блокировки, либо являются правильными только при условии отсутствия одновременных модификаций структуры данных. В частности, Ctries имеют операцию создания итератора O (1), операцию очистки O (1), операцию дублирования O (1) и операцию извлечения размера с амортизированным размером O (logn).
Большинство параллельных структур данных требует динамического выделения памяти, а lock-free параллельные структуры данных полагаются на сборку мусора на большинстве платформ. Текущая реализация Ctrie написана для JVM, где сборка мусора обеспечивается самой платформой. Хотя можно сохранить параллельный пул памяти для узлов, совместно используемых всеми экземплярами Ctries в приложении, или использовать подсчет ссылок для правильного освобождения узлов, пока что единственной реализацией для ручного управления памятью узлов, используемых в Ctries, является обычная Реализация lisp cl-ctrie, которая реализует несколько методов сборки мусора с остановкой и копированием и меткой и очисткой для постоянного хранилища с отображением в память. Указатели опасности - еще одно возможное решение для правильного ручного управления удаленными узлами. Такой метод может быть применим и для управляемых сред, поскольку он может снизить нагрузку на сборщик мусора. Реализация Ctrie в Rust использует для этой цели указатели опасности.
Реализация Ctrie для Scala 2.9.x доступна на GitHub. Это изменяемая потокобезопасная реализация, обеспечивающая прогресс и поддерживающая безблокирующие линеаризуемые снимки O (1).
Cтрины были впервые описаны в 2011 году. Процитируем автора:
Ctrie - это неблокирующее параллельное хэш-дерево с общей памятью, основанное на однословных инструкциях по сравнению и замене. Операции вставки, поиска и удаления, изменяющие различные части хэш-дерева, могут выполняться независимо друг от друга и не конкурировать. Операции удаления гарантируют, что ненужная память будет освобождена, а дерево останется компактным.
В 2012 году была опубликована пересмотренная версия структуры данных Ctrie, упрощающая структуру данных и вводящая необязательную операцию атомарного моментального снимка с постоянным временем, без блокировок.
