Неизменная карта - Что делать, если два потока вставляют один и тот же ключ?

Question

Вот мои знания о неизменных структурах данных, особенно неизменяемой карте, поправьте меня, если я ошибаюсь:

1. При обновлении они не изменяют внутреннюю структуру, но создают копию с обновленными данными.
2. Они обычно реализуются древовидными структурами данных, потому что копирование ветви дерева намного эффективнее, чем копирование линейного списка.
3. Когда их использует много потоков, их состояния среди этих потоков не синхронизируются. Некоторые потоки могут использовать старую версию, но поток чтения не должен ждать окончания потока обновления.
4. По крайней мере, требуется блокировка для синхронизации назначений общей переменной, ссылающейся на структуру данных (но в Java назначение является атомарным, так что это не проблема).

Если есть два потока t1 и t2, вставляющие в неизменяемую карту один и тот же ключ. Непосредственно перед тем, как t1 выполнит свою работу и обновит общую ссылку, t2 начнет свою работу и получит старую версию карты, ключ которой еще не вставлен, и продолжит вставлять тот же ключ. Теперь окончательная версия карты зависит от того, какой поток обновляет общую ссылку последним. В обоих случаях есть заброшенное значение ключа, которое вскоре будет очищено сборщиком мусора.

Мой вопрос заключается в том, как мне решить проблему, когда два потока вставляют один и тот же ключ в неизменяемую карту, ссылка на которую является общей для потока? Или использование общей ссылки в первую очередь неправильно?

Answer 1

Вопрос разбивается на две части. Первый вопрос

Что произойдет, если два потока пишут в одну общую ссылку?

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

Второй вопрос, который вам нужно задать, это

Всегда ли безопасно для двух потоков одновременно читать неизменный объект?

Ответ на этот вопрос - нет.

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

Answer 2

По терминологии: существует два вида коллекций, которые называются «неизменяемыми».

1. Коллекции, которые выдают исключение при попытке вызвать операцию мутатора (например, ImmutableMap в Guava).
2. Коллекции, которые при вызове мутатора создают и возвращают новую версию самого себя вместо изменения общего состояния (что-то вроде копирования при записи).

Вы, вероятно, спрашиваете о втором типе "неизменности".

Полагаю, у вас есть что-то вроде этого:

private CopyOnWriteTree tree;

void insertValue(Value value) {
    tree = tree.insert();
}

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

Если insertValue() вызывается более чем одним потоком с использованием одной и той же общей ссылки на объект, содержащий поле tree, то лучшее, что вы можете сделать, это сериализовать обновления этого поля, используя обычные методы, такие как synchronized, volatile или AtomicReference, но один из них будет потерян. (Обратите также внимание, что ссылочная атомарность обновлений здесь не проблема; проблема в том, что без такой синхронизации одному потоку даже не гарантируется, что он когда-либо увидит обновления, сделанные другими потоками).

Коллекции «Копировать при записи» хороши для случаев, когда каждый поток работает со своей собственной копией данных и выбрасывает ее после завершения работы.

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

PS. Я только что понял, что вопрос был о коллекциях Scala, и я отвечал так же, как и о Java. Тем не менее, логика остается той же, что и модель памяти, то же самое.