Многопоточное удаление из BST только с локальными блокировками

Question

При написании многопоточной реализации BST в Java я пришел к следующей проблеме. Этот BST не должен использовать глобальную блокировку, а должен блокировать как можно меньше, в частности, только те узлы, которые меняются (команда добавления и удаления). Таким образом, другие потоки могут быть активны в дереве, если они не пытаются изменить те же узлы, что и вы. Я не могу найти способ реализовать удаление узла, который имеет 2 дочерних элементов. Обычный алгоритм говорит, что нужно найти преемника по порядку удаляемого узла, поместить его вместо удаленного узла, а затем удалить скопированный узел. Но это может создать проблему для потока, который находится между этими двумя узлами и нуждается в скопированном узле, после передачи поток не найдет запрошенный узел, даже если он находится в дереве. Посмотрите на следующий пример: шаг 1 выполняет remove(5). Он находит и копирует следующий ключ (6) в узел, а затем удаляет узел из копии. Но в то же время другой поток, выполняющий команду contains(6) и ожидающий на узле 8, после того, как исполняющий узел номер 6 больше не будет находиться на своем пути, и он вернет ложный результат, даже если узел 6 все еще находится в дереве .

Иллюстрация состояния перед командой удаления (синяя стрелка указывает, где находится поток 2 ^nd .

Иллюстрация состояния после команды удаления (синяя стрелка указывает, где находится поток 2 ^nd .

Как я могу преодолеть эту проблему, не блокируя все дерево?

Answer 1

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

Answer 2

Решение, которое я использовал, заключалось в том, чтобы иметь номер версии для BST, и каждый раз, когда remove требуется для узла с двумя дочерними элементами, я увеличиваю номер версии перед удалением дублированного узла.

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

Это означает:

• Для remove и contains - если действие не удалось (это означает, что ключ не был найден) и версия была изменена, попробуйте еще раз.
• Для insert - я проверяю номер версии не в конце действия, а когда я нахожусь на листе и перед созданием и добавлением нового узла. Если я собираюсь добавить новый узел, это означает, что я не нашел узел с этим ключом, я хочу убедиться, что ключ действительно не находится в дереве, прежде чем изменять его и создавать новый лист, чтобы предотвратить ситуацию, когда двойной ключ будет добавлен к дереву, а затем мне нужно будет повторить это, удалив узлы.

Answer 3

Синхронизируйте узлы независимо от BST. Это означает, что если вы удаляете узел, вам необходимо заблокировать самый верхний узел, на который это влияет, и все узлы под ним, чтобы другие потоки не могли прочитать или изменить эти узлы. К сожалению, для BST это может означать блокировку корневого узла в зависимости от операции, что эффективно предотвратит любое чтение.

Я считаю, что это будет самая быстрая реализация того, что вы пытаетесь сделать.

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