代码之家 › 专栏 › 技术社区 › James McMahon

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

graph computer-science concurrency

James McMahon · 技术社区 · 15 年前

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

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

我要实现的策略是,一个读取线程将在图形的“快照”上执行其整个操作,也就是说,在某个时间点查看结构。

我目前的计划是在事务数据库中设置类似于行版本控制的内容,即读取线程首先获取当前版本号,然后只访问具有此版本号或更早版本号的图形节点和边。然后,编写线程会在新元素上添加一个递增的版本号(更改后的元素将首先被克隆),使它们对运行的读卡器不可见。当一个写线程成功完成后,它就可以“提交”它的新版本,读卡器会“释放”它们的版本号,使被删除的元素符合删除的条件。

这个策略仍然是粗略的,有许多未解决的问题,如并发写访问,但一般来说,这似乎是一条可行的道路。

3 回复 | 直到 15 年前

James McMahon 15 年前

另一种选择是 Persistent Data Structures . 它们是始终保持不变的数据结构 修改时的早期版本 .

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

Community CDub 7 年前

我觉得你的方法很合理…

但是,你可能会遇到的问题是确保 因果关系 在不同子图上的写入之间。

如果一个编写器更改了子图A,另一个编写器更改了不同的子图B,但其他读/写操作发生在子图C上,其中A和B在C中,则需要确保子图C的版本与B和A的版本正确对齐。

我建议在DAG中使用一种锁定方案,该方案将子图锁定与给定根目录的多读/单写结合在一起。但是,您需要对循环依赖关系图进行grep,以确保您不会在图中进入饥饿/死锁状态。

如果你的图表是 分布式的 或者同时访问 等待时间 那么,您的交易系统将更加难以实现,并且可能需要额外的保护措施。

您的版本控制方法听起来不错,只要您的锁定规定确保在所有情况下,节点的一组修订在任何时候都代表 积分状态 图中的t=n0、n1、n2、n3处的一组节点和修订,以及子图的并发修订碰撞,将使整个修订集和节点保持t积分,这是一个难题。

AS dfa suggests above ,节点和修订集在某一点上表示整个结构的变更集。如果它具有完整性,那么它在某个时间点上表示整个结构。

记住:时间、完整性、因果关系和并发性

祝你好运!

agorenst 15 年前

嗯,我想我会很聪明,搜索几个关键词,找到一些文学作品。第一个结果…是这个问题吗?

所以这个话题没有太多!有趣。只是想和你分享。

艾登·贝尔和德国足协都给出了非常彻底的答案,所以我不会试图超越它们。:)但我将对图形的DAG质量和并发写入访问进行一次观察。这可能已经发生在你身上了,但是嘿。:)

您可以允许并发线程,而不必担心一个线程重写另一个线程的更改,只需假设在任何时候 由写入线程驻留的节点以及该节点的所有子节点都被该特定写入线程“锁定”。 .我发现用一棵树(很明显,它也是一把匕首)来形象化是最容易的。任何写线程基本上都锁定了一个子树,但同样地,我们现在可以说任何兄弟树或任何祖先节点都是愉快的可写的。

一个更复杂的DAG(尤其是一个节点可以有多个父节点)实际上会有很多重叠的子树,因此可能没有那么多的自由,但规则仍然适用:任何不受驻留的节点或受写入线程驻留的节点的子节点都可以被视为启用了写。

显然,有很多因素可能会导致上述想法无济于事,但如果多个写线程经常朝着“不同”的方向发展,那么它可能会减轻一些使其线程安全所需的要求。

希望这有帮助!

-阿格尔