Как синхронизировать вставку / удаление элементов в / из структуры данных Функциональным способом?

Question

У меня есть структура данных, скажем MinHeap. У него есть такие методы, как peek (), removeElement () и addElement (). removeElement() и addElement() могут создавать несогласованные состояния, если они не сделаны поточно-ориентированными (потому что они включают в себя увеличение / уменьшение currentHeapSize).
Теперь я хочу реализовать эту структуру данных функциональным способом. Я читал, что в функциональном программировании неизменность является ключом к безопасности потоков. Как мне реализовать это здесь? Должен ли я избежать увеличения / уменьшения currentHeapSize? Если так, то как? Я хотел бы получить направление в этом направлении.

Редактировать # 1

@YuvalItzchakov и @Dima указали, что мне нужно возвращать новую коллекцию каждый раз, когда я делаю вставку / удаление, что имеет смысл. Но разве это не помешает производительности? Мой вариант использования заключается в том, что я получу поток данных и продолжаю добавлять его в кучу. Когда кто-либо запрашивает данные, возвращается корень минимальной кучи. Так что здесь вставка происходит очень быстро. Разве создание новой кучи для каждой вставки не будет дорогостоящим? Я думаю, что будет. Если да, то как реально помогает функциональное программирование? Это просто теоретическая концепция или она имеет практические последствия?

Answer 1

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

Answer 2

Вы можете использовать кошек Ref тип класса https://typelevel.org/cats-effect/concurrency/ref.html Но это реализация AtomicReference или написать какую-нибудь java.util.concurent.ConcurentHashMap оболочку

Answer 3

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

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

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

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