通过克隆的数据结构并发读取和写入？
Concurrent read and writers through cloned data structures?
我阅读了 this 问题，但它并没有真正帮助。
首先也是最重要的事情：时间性能是我正在开发的应用程序的重点
我们有一个 client/server 模型（如果我们愿意，甚至可以是分布式或云）和一个托管在服务器上的数据结构 D。每个客户端请求包括：
- 从
D 读一些东西
- 最终在
D 上写点东西
- 最终 删除
D 上的内容
可以说，在这个应用中，接收到的操作数之间的关系可以描述为delete<<write<<read。另外：
- 读取操作不能绝对等待：它们必须立即处理
- 写入和删除可以等一段时间，但越早越好。
从上面的描述来看，任何锁机制都是不可接受的：这意味着读操作可以等待，这是不可以接受的（抱歉，如果我这么强调它，但这确实是一个关键点）。
一致性不是必需的：如果执行了 write/delete 操作，然后读取操作没有看到 write/delete 效果，这没什么大不了的。会更好，但不是必需的。
解决方案应该是独立于数据结构的，所以无论我们写在向量、列表、地图还是唐纳德特朗普的脸上都没有关系。
数据结构可能会占用大量内存。
我目前的解决方案：
我们使用两台服务器：第一台服务器（名为 f）已更新 Df，第二台服务器（名为 s）已更新 Ds。
f 使用 Df 响应客户端请求并将 write/delete 操作发送到 s。然后 s 依次应用 write/delete 操作 Ds。
在某个时刻，所有未来的客户端请求都被重定向到 s。同时，f 将 s 更新的 Ds 复制到它的 Df 中。
现在，f 和 s 角色互换：s 将使用 Ds 回答客户请求，而 f 将保留更新版本的 Ds。交换过程会定期重复。
请注意，为了简单起见，我故意省略了很多细节（例如，完成交换后，f 必须在应用 write/delete 操作之前完成所有待处理的客户端请求同时从 s 收到）。
为什么我们需要两台服务器？因为数据结构可能太大而无法放入一个内存。
现在，我的问题是：文献中有类似的方法吗？我在 10 分钟内想出了这个协议，我发现奇怪的是没有（更好的）类似的解决方案已经被提出！
PS：我可能忘记了一些应用程序规范，不要犹豫，要求任何澄清！
你的方案有效。我看不出有什么特别的问题。这基本上就像许多数据库 运行 他们的 HA 解决方案。他们将写入日志应用于副本。该模型在如何形成、访问和维护副本方面提供了很大的灵活性。故障转移也很容易。
另一种技术是使用持久数据结构。每写returns你一个新的独立版本的数据。所有版本均可稳定无锁读取。版本可以随意保留或丢弃。版本尽可能多地共享底层状态。
通常，树是这种持久数据结构的基础，因为很容易更新树的一小部分并重用旧树的大部分。
您可能没有找到更复杂的方法的一个原因是您的问题非常普遍：您希望它适用于任何数据结构并且数据可能很大。
SQL Server Hekaton 使用相当复杂的数据结构来实现任何数据库内容的无锁、可读、时间点快照。也许值得看看他们是如何做的（他们发布了一篇描述系统每个细节的论文）。它们还允许 ACID 事务、可串行化和并发写入。全部无锁。
At the same time, f copies s updated Ds into its Df.
因为数据量大，所以复制的时间会比较长。它会阻止读者。更好的方法是在可写副本接受新写入之前将写入日志应用到可写副本。这样可以连续接受读取。
切换也是一个很短的时间，读取的延迟可能会比正常情况稍高。
我阅读了 this 问题，但它并没有真正帮助。
首先也是最重要的事情：时间性能是我正在开发的应用程序的重点
我们有一个 client/server 模型（如果我们愿意，甚至可以是分布式或云）和一个托管在服务器上的数据结构 D。每个客户端请求包括：
- 从
D 读一些东西
- 最终在
D上写点东西
- 最终 删除
D 上的内容
可以说，在这个应用中，接收到的操作数之间的关系可以描述为delete<<write<<read。另外：
- 读取操作不能绝对等待：它们必须立即处理
- 写入和删除可以等一段时间，但越早越好。
从上面的描述来看，任何锁机制都是不可接受的：这意味着读操作可以等待，这是不可以接受的（抱歉，如果我这么强调它，但这确实是一个关键点）。
一致性不是必需的：如果执行了 write/delete 操作，然后读取操作没有看到 write/delete 效果，这没什么大不了的。会更好，但不是必需的。
解决方案应该是独立于数据结构的，所以无论我们写在向量、列表、地图还是唐纳德特朗普的脸上都没有关系。
数据结构可能会占用大量内存。
我目前的解决方案：
我们使用两台服务器：第一台服务器（名为 f）已更新 Df，第二台服务器（名为 s）已更新 Ds。
f 使用 Df 响应客户端请求并将 write/delete 操作发送到 s。然后 s 依次应用 write/delete 操作 Ds。
在某个时刻，所有未来的客户端请求都被重定向到 s。同时，f 将 s 更新的 Ds 复制到它的 Df 中。
现在，f 和 s 角色互换：s 将使用 Ds 回答客户请求，而 f 将保留更新版本的 Ds。交换过程会定期重复。
请注意，为了简单起见，我故意省略了很多细节（例如，完成交换后，f 必须在应用 write/delete 操作之前完成所有待处理的客户端请求同时从 s 收到）。
为什么我们需要两台服务器？因为数据结构可能太大而无法放入一个内存。
现在，我的问题是：文献中有类似的方法吗？我在 10 分钟内想出了这个协议，我发现奇怪的是没有（更好的）类似的解决方案已经被提出！
PS：我可能忘记了一些应用程序规范，不要犹豫，要求任何澄清！
你的方案有效。我看不出有什么特别的问题。这基本上就像许多数据库 运行 他们的 HA 解决方案。他们将写入日志应用于副本。该模型在如何形成、访问和维护副本方面提供了很大的灵活性。故障转移也很容易。
另一种技术是使用持久数据结构。每写returns你一个新的独立版本的数据。所有版本均可稳定无锁读取。版本可以随意保留或丢弃。版本尽可能多地共享底层状态。
通常，树是这种持久数据结构的基础，因为很容易更新树的一小部分并重用旧树的大部分。
您可能没有找到更复杂的方法的一个原因是您的问题非常普遍：您希望它适用于任何数据结构并且数据可能很大。
SQL Server Hekaton 使用相当复杂的数据结构来实现任何数据库内容的无锁、可读、时间点快照。也许值得看看他们是如何做的（他们发布了一篇描述系统每个细节的论文）。它们还允许 ACID 事务、可串行化和并发写入。全部无锁。
At the same time, f copies s updated Ds into its Df.
因为数据量大，所以复制的时间会比较长。它会阻止读者。更好的方法是在可写副本接受新写入之前将写入日志应用到可写副本。这样可以连续接受读取。
切换也是一个很短的时间，读取的延迟可能会比正常情况稍高。