database – 有关复制方案/算法的文章？

>将密钥K更新为值V.
>查找关键K的近似值.

你提到你需要最终的一致性.因此,如果您进行单个更新,它最终将在任何地方复制.如果你做了两个几乎同时发生的更新,你关心哪一个获胜？如果一个副本报告已成功完成更新,您是否关心如果该副本在之后不久暂时崩溃,该值是否会丢失？或者,如果该副本被永久销毁？

最近有多精确？如果有netsplit或其他东西,查找可能会返回一个非常陈旧的结果或只是失败.你关心哪个？

你是否需要支持像…这样的更高级的运营？

>获取密钥K的绝对最新值？
>如果最新值为V,则将密钥K的值更新为值V’？

您是否具有严格的可靠性,延迟和/或带宽要求？您的副本/网络之间的距离有多远？如果您可以在每次更新甚至每次查找时进行跨副本通信,则会产生这种影响;或者即使您可以/应该将操作故障转移到远程副本,如果本地的副本似乎已关闭.

根据您在这里的答案,我已经使用了几个可能符合您要求的不同方案.它们有几种可能的变化.

>最简单的方法是让应用程序始终与本地副本通信.副本时间戳值(使用NTP同步时钟)并且仅相互通信以进行异步复制.最高时间戳在复制中获胜.当然,如果两个不同副本上的应用程序各自同时进行读取/修改/写入,则其中一个修改很容易丢失. (实际上,如果没有条件更新方案,对同一副本上的近同步更改也是如此.)如果副本永久失败,则可能会丢失最近的更新.这或多或少是Bigtable的内置复制所做的.在您链接的论文中,它是“乐观 – 多主管”分支,但不会过多关注丢失一些更新使其比他们建议的更简单.
>有些数据库使用Paxos算法(例如参见“Internet规模单点登录的数据管理”here)可以让更好的东西成为可能.每个副本都可以知道它可能有多远,所以你可以说“给我一个价值”这不超过1分钟“或”给我绝对的最新值“.在法定数量的复制品接受它之前,更新不被认为是完整的,因此”给我绝对的最新值“肯定会一直返回该值,直到发生了另一次更新.您可以执行我提到的条件更新操作,以防止同时写入者相互踩踏.这似乎不适合该作者定义的乐观或悲观类别,因为更新同步复制到仲裁但是在最近的Paxos轮中没有投票的复制品仍然可以回答一些问题.这个方案可能非常复杂,但……