如何组织对图形的多线程访问？

Question

我正在详细阐述一个对我来说难以解决的问题,我并不期待一个简单的解决方案,但也许有经过验证的实践或进一步阅读可能会使这更容易.我很确定许多应用程序中会弹出一般问题(例如垃圾收集或事务数据库).

我的应用程序有一个图表(如果重要的话DAG),它同时由多个线程遍历.其中一些只是试图找到某些节点或检索子图,其他可能会改变图的结构.

我想要实现的策略是读取线程将在图形的"快照"上执行其整个操作,即在某个时间点查看结构.

我目前的计划是在事务DB中设置类似于行版本控制的东西,即读取线程首先获取当前版本号,然后仅访问具有此版本号或更早版本的图节点和边.然后,编写线程会在新元素上添加增加的版本号(更改的元素将首先克隆),使其对于运行的读者不可见.然后,写入线程可以在成功完成后"提交"其新版本,并且读者将"释放"其版本号,使删除的元素有资格被删除.

这种策略仍然是粗略的,并且有许多未解决的问题,例如并发写访问,但通常它似乎是一条可行的道路.

Answer 1

另一种选择是使用持久数据结构。它们是在修改时始终保留其自身先前版本的数据结构。

它们就像一个日志文件，修改后的版本总是追加到最后，使它们不可变，因为它们的操作不会（明显）就地更新结构，而是总是产生一个新的更新结构。像 Clojure 这样的编程语言最近普及了这种方法（至少对我来说）。