Как организовать многопоточный доступ к графу?

Question

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

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

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

Мой текущий план - настроить что-то похожее на управление версиями строк в транзакционных БД, т.е. е. Поток чтения сначала получает текущий номер версии, а затем только посещает узлы и ребра графа, которые имеют этот номер версии или ранее. При написании потоков будет добавлен увеличенный номер версии для новых элементов (измененные элементы будут сначала клонированы), что сделает их невидимыми для запуска читателей. Затем поток записи может «зафиксировать» свою новую версию после успешного завершения, и читатели «выпустят» номер своей версии, что сделает удаленные элементы пригодными для удаления.

Эта стратегия все еще схематична и имеет ряд нерешенных проблем, таких как одновременный доступ к записи, но, как правило, она кажется жизнеспособной.

Answer 1

альтернатива будет использовать Постоянные структуры данных . Это структура данных, которая всегда сохраняет предыдущую версию самой себя, когда она модифицируется .

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

Answer 2

Ваш подход мне кажется правильным ...

Однако у вас могут возникнуть проблемы с обеспечением причинности между записями по отдельным подграфам.

Если писатель изменяет подграф A, а другой писатель изменяет отдельный подграф B, но другие операции чтения / записи выполняются на подграфе C, где A и B находятся в C, то вам нужно убедиться, что версия подграфа C совпадает с версиями из B и A.

Я бы предложил схему блокировки в группе обеспечения доступности баз данных, которая включает блокировку подграфа для множественного чтения / однократной записи из заданного корня. Тем не менее, вам необходимо выполнить диаграмму для циклических зависимостей, чтобы убедиться, что вы не попадете в состояние голодания / тупика внутри графика.

Если ваш график распределен или ваш параллельный доступ имеет латентность , то ваша система транзакций будет сложнее реализовать и, вероятно, потребует дополнительных мер безопасности.

Ваш подход к управлению версиями звучит нормально, если ваши положения о блокировке гарантируют, что во всех случаях набор ревизий для узлов в любое время T представляет интегральное состояние графика. Множество узлов и ревизий в T = {n0, n1, n2, n3} и одновременное столкновение ревизий подграфов создаст головную боль в сохранении всего набора ревизий и узлов в T.

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

Помните: время, целостность, причинность и параллелизм

Удачи!

Answer 3

Ну, я подумал, что я буду умен и найду несколько ключевых слов, чтобы найти литературу. Первый результат ... был этот вопрос.

Так что на эту тему не так уж много! Интересно. Просто думал, что поделюсь.

Эйден Белл и DFA дали очень подробные ответы, поэтому я не буду пытаться их опередить. :) Но я сделаю одно замечание, касающееся качества DAG графика и одновременного доступа для записи. Возможно, это уже произошло с вами, но эй. :)

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

Более сложный DAG (где у узла может быть несколько родителей, в частности) будет, по сути, иметь много перекрывающихся поддеревьев, и поэтому может быть не так много свободы, но правило все еще применяется: любой узел, который не заселен или является дочерним узлом, населенным потоком записи, может считаться разрешенным для записи.

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

Надеюсь, это поможет!

-Agor