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

Question

我读到this问题但并没有真正帮助。

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

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

1. 阅读 D 中的内容
2. 最终在 D 上写点东西
3. 最终删除 D 上的某些内容

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

1. 读取操作不能绝对等待:它们必须立即处理
2. 写入和删除可能需要等待一段时间，但越早越好。

从上面的描述来看，任何锁定机制都是 Not Acceptable :这意味着读取操作可能会等待，这是不可接受的(抱歉，如果我强调太多，但这确实是一个至关重要的问题)点)。

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

解决方案应该独立于数据结构，因此我们是否在矢量、列表、 map 或唐纳德·特朗普的脸上书写都没有关系。

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

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

我们使用两台服务器:第一台服务器(称为 f )有 Df ，第二台服务器(称为 s )有 Ds更新。

f使用 Df 回答客户请求并将写/删除操作发送到 s 。然后s应用写入/删除操作 Ds依次。

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

现在，f和s角色交换:s将使用 Ds 回答客户请求和f将保留Ds的更新版本。交换过程会定期重复。<​​/p>

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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