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

Question

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

我的应用程序有一个图形(如果重要，则为 DAG)，该图形同时被多个线程遍历。其中一些只是试图找到某些节点或检索子图，其他人可能会改变图的结构。

我想要实现的策略是读取线程将对图形的“快照”执行其整个操作，即。 e.查看某个时间点的结构。

我目前的计划是在事务数据库中设置类似于行版本控制的东西，即。 e.读取线程首先获取当前版本号，然后仅访问具有此版本号或更早版本的图节点和边。编写线程然后会在新元素上放置一个递增的版本号(更改的元素将首先被克隆)，使它们对于正在运行的阅读器不可见。写入线程可以在成功完成后“提交”其新版本，读者将“释放”他们的版本号，使已删除的元素有资格被删除。

这种策略仍然很粗略，并且有许多 Unresolved 问题，例如并发写入访问，但总的来说，它似乎是一条可行的道路。

Answer 1

另一种方法是使用 Persistent Data Structures .它们是一种数据结构，在修改时始终保留其先前版本。

它们就像一个日志文件，修改后的版本总是最后追加使它们不可变，因为它们的操作不会(明显地)就地更新结构，而是总是产生一个新的更新结构。编程语言，如 Clojure lately polularized this approach (至少对我而言)。