multithreading - 通过克隆数据结构进行并发读写？

Question

我读了this问题，但它并没有真正帮助。

首先也是最重要的事情:时间性能是我正在开发的应用程序的重点

我们有一个客户端/服务器模型(如果我们愿意，甚至是分布式或云)和一个数据结构 D托管在服务器上。每个客户端请求包括:

阅读 D 的内容

最终在 D 上写点东西

最终删除 D 上的某些内容

我们可以说，在这个应用程序中，接收到的操作数之间的关系可以描述为 delete<<write<<read .此外:

读取操作不能绝对等待:他们 必须立即处理

写入和删除可以等待一段时间，但越快越好。

从上面的描述来看，任何锁机制都是 Not Acceptable :这意味着读取操作可以等待，即 不是 可以接受(对不起，如果我这么强调它，但这确实是一个关键点)。

一致性不是必需的:如果执行了写入/删除操作，然后读取操作看不到写入/删除效果，这没什么大不了的。这会更好，但这不是必需的。

解决方案应该是数据结构独立的，所以我们是否在矢量、列表、 map 或唐纳德特朗普的脸上书写都无关紧要。

数据结构可能会占用大量内存。

到目前为止我的解决方案:

我们使用两台服务器:第一台服务器(称为 f )有 Df ，第二个服务器(称为 s)有 Ds更新。
f使用 Df 回答客户请求并将写入/删除操作发送到 s .然后 s应用写入/删除操作 Ds依次。

在某个时刻，所有 future 的客户端请求都被重定向到 s .同时， f副本 s更新 Ds进入其 Df .

现在， f和 s角色互换: s将使用 Ds 回答客户请求和 f将保持 Ds 的更新版本.交换过程定期重复。

请注意，为了简单起见，我故意省略了很多细节(例如，一旦交换完成， f 必须在应用同时从 s 收到的写入/删除操作之前完成所有待处理的客户端请求) .

为什么我们需要两台服务器？因为数据结构可能太大而无法放入一个内存中。

现在，我的问题是:文学中有一些类似的方法吗？我在 10 分钟内想出了这个协议(protocol)，我觉得奇怪的是，没有(更好的)与这个类似的解决方案已经被提出!

PS:我可能忘记了一些应用程序规范，请随时要求澄清!

Answer 1

您拥有的方案有效。我看不出它有什么特别的问题。这基本上就像许多数据库运行其 HA 解决方案一样。他们将写入日志应用到副本。该模型在如何形成、访问和维护副本方面提供了很大的灵 active 。故障转移也很容易。

另一种技术是使用持久数据结构。每次写入都会为您返回一个新的独立版本的数据。所有版本都可以以稳定且无锁的方式读取。版本可以随意保留或丢弃。版本尽可能多地共享底层状态。

通常，树是这种持久数据结构的基础，因为很容易更新树的一小部分并重用大部分旧树。

您可能没有找到更复杂的方法的一个原因是您的问题非常普遍:您希望它完全适用于任何数据结构并且数据可能很大。

SQL Server Hekaton 使用非常复杂的数据结构来实现任何数据库内容的无锁、可读、时间点快照。也许值得看看他们是如何做到的(他们发布了一篇描述系统每个细节的论文)。它们还允许 ACID 事务、可串行化和并发写入。全部无锁。

At the same time, f copies s updated Ds into its Df.

这个副本需要很长时间，因为数据很大。它会阻止读者。更好的方法是在接受新的写入之前将写入日志应用到可写副本。这样就可以连续接受读取。

切换也是一个短暂的时期，其中读取的延迟可能比正常情况稍高。