将一致性回退到最终一致性

论文地址：将一致性恢复到最终一致性-Balegas等人。2015年

今天的选择是最近一批欧洲系统2015年论文中的另一篇。Balegas等人。告诉我们，即使在地理复制环境中，我们也不必忍受最终一致性的弱形式。

在构建QuicksandHelland的过程中，我们认为需要在应用程序操作的层次上理解和推理分布式应用程序（而不是在某些数据存储中进行底层读写）。在数据库系统中的协调避免中，Bailis等人。向我们展示，通过在应用程序级别理解不变量（并仅使用实现这些不变量所需的最小协调），我们可以在提供比许多最终一致存储更强大保证的同时获得更好的可伸缩性。在今天的论文选择“将一致性还原为最终一致性”中，Balegas等人。在Bailis的不变驱动方法的基础上，在仍然需要协调的情况下，采用缓解策略。

弱一致性模型的缺点是应用程序必须处理并发操作，这会导致不直观和不需要的语义……在本文中，我们提出显式一致性作为替代一致性模型，其中应用程序指定系统必须维护的不变量或一致性规则。与根据执行顺序定义的模型不同，显式一致性是根据应用程序属性定义的：只要保持指定的不变量，系统就可以对不同副本上的操作执行重新排序。
在原型中，程序员使用简单的不变量规范语言在Java注释中表示全局和操作级不变量。然后，使用可满足性模块理论（SMT）求解器Z3对不变规范进行分析，以推断哪些组合的操作可以在没有协调的情况下安全执行。对于那些需要一些协调的剩余操作，程序员可以在不变修复机制和冲突避免机制之间进行选择。然后对应用程序代码进行检测，以插入对所提供的中间件库的必要调用。
结果表明，修改后的应用程序在执行大多数操作时具有与弱一致性相似的性能，同时能够强制应用程序不变量。
不变量必须始终为真，并且可以使用谓词和函数来表示。还必须定义操作后置条件。以下是显示批注的片段：

也许不是最漂亮的，但足以构成原型。我想起了Eiffel——Bertrand Meyer在90年代初首次引入的面向对象语言，它对语言中内置的契约式设计有着强大的支持。（因此，在我看来，它比现代注释式的方法优雅得多）。
不变修复策略允许冲突操作并发执行，然后在发生冲突后修复冲突。
Indigo[作者实现]对这种方法的支持有限，因为它只能处理在单个数据库对象上下文中定义的不变量（即使对象可能很复杂，如树或图）。为此，Indigo提供了一个对象库，可以使用文献中提出的技术自动修复不变量，例如具有不同冲突解决策略的集合、地图、图形、树。
Helland的（记忆）、判断和回退模型在更高层次上表达了同样的观点。
违规规避策略是我最感兴趣和最新颖的部分，它基于一个预约系统。
多级锁预留（或者简单地说多级锁）是我们限制能够破坏不变量的操作并发执行的基本机制。多级锁可以提供以下权限：（i）共享禁止，赋予共享权限禁止某些操作发生；（ii）共享允许，赋予共享权限允许某些操作发生；（iii）独占允许，赋予执行某些操作的独占权限。当副本拥有上述权限之一时，没有其他副本拥有其他类型的权限。例如，如果一个副本持有一个共享禁止，则没有其他副本具有任何形式的允许。

在多人锦标赛游戏的上下文中给出了使用这些锁的示例：
为了执行removePlayer（P），需要在removePlayer（P）的预订上获得正确的“共享允许”。在执行Enrollmoutament（P，T）时，需要获得removePlayer（P）预订的“共享禁止”权限。这保证了注册某个玩家不会与删除同一个玩家同时执行。但是，允许同时注册或同时删除。特别是，如果所有副本都拥有删除播放机的共享禁止权限，则最频繁的注册操作可以在任何副本中执行，而无需与其他副本进行协调。当一个操作与它本身不兼容时，也就是说，当同时执行同一个操作时，可能会导致不变量冲突，则排他允许权是必要的。
在多谓词（多于2个）析取的情况下，多级掩码保留充当多级锁的向量。托管保留用于数字不变量，例如x&geq；k或nrPlayers（T）对于x≥k形式的数值不变量，我们包含了一个托管保留，允许在不进行协调的情况下执行某些递减。给定x=x0的初始值，最初x0–k有权执行递减。这些权限可以在副本之间动态拆分。为了执行x.decrement（n），该操作必须获取并使用n个权限来减少它提交的副本中的x。如果副本中没有足够的权限，系统将尝试从其他副本获取其他权限。如果这不可能，操作将失败。
最后，分区锁保留允许保留部分资源…
对于某些不变量，希望能够保留部分可分区资源。例如，考虑禁止两个比赛在时间上重叠的不变量。

该系统是在SwiftCloud平台上实现的。
Indigo将保留的信息作为对象存储在底层因果一致的存储系统中。对于每种类型的保留，都存在一个特定的对象类。每个保留实例维护有关分配给每个副本的权限的信息；在Indigo中，每个数据中心都被视为单个副本…保留对象存储在底层存储系统中，并在所有数据中心中复制。保留权限是单独分配给数据中心的，这样可以保持信息较小。
在需要联系另一个数据中心以获得某些权限的情况下，这种方法显然容易受到高延迟的影响。因此靛蓝积极地获得和分配权利。托管锁权限在数据中心之间划分，并预先分配多级锁权限，以允许执行最常见的预期操作.

现在我的分区问题得到了回答：
如果一个数据中心（失败或）从其他数据中心进行分区，则无法从分区的数据中心向分区的数据中心传输权限。在每个分区中，只需要分区中可用权限的操作可以正常执行。要求分区中不可用权限的操作将失败。当分区被修复（或数据中心在其状态保持不变的情况下恢复）时，将恢复正常操作。
因此Indigo不能保证在发生分区时所有操作都可用。
总的来说，在单个应用程序访问数据的情况下，这个方向看起来很有希望。当多个应用程序在同一个底层数据存储上工作时（在升级过程中甚至可能是同一个应用程序的多个版本），会发生什么情况就不那么清楚了。从表面上看，我们需要对所有与数据交互的应用程序进行全局不变分析，并且在初始部署之后将新的应用程序引入到混合中将是一个问题。我怀着浓厚的兴趣等待未来的发展！