事件溯源的复制:CloudState是如何支持分布式一致性CRDT的?

19-09-11 banq
                   

无冲突复制数据类型(CRDT)是可用于支持分布式系统中高可用性和可伸缩状态共享的数据结构。CRDT状态被复制到系统中的每个节点。每个节点都可以读取和更新CRDT,而无需与其他节点进行任何协调。如果两个或多个节点同时修改CRDT,则修改可以合并在一起,并且CRDT保证最终所有节点将就该CRDT的当前状态达成一致。

CRDT强项是它的合并功能,如果对于给定的数据类型,您可以定义一个函数,该函数接受它所拥有的数据的多个版本,并使用该函数将这些版本合并为单个版本,这样版本合并的顺序无关紧要在,你仍然会得到相同的结果,然后该数据类型可以用作CRDT。

要使用CRDT,应用程序必须找到一种方法来使用可用的CRDT来表示其数据(满足可交换 可联合等条件 banq注:事件溯源的事件日志是其中一种)。重要的是要记住,CRDT不是一种神奇的技术辣酱,可以倾注在任意数据模式上,使其具有高可用性和可扩展性。必须仔细设计应用程序表示其数据的方式,以便在可用CRDT的约束下工作。

何时使用CRDT

CRDT在不需要强一致性的情况下非常有用,只需要最终的一致性。CRDT不保证在一个节点上进行的更新将立即在所有节点上可见,而是保证这样的更新最终将在所有节点上可见。

它们在需要极低延迟读写的情况下非常有用。读取CRDT不需要网络通信,因为只需从节点本地副本读取该值。修改CRDT也不需要网络通信,因为修改CRDT只需要更新节点本地副本。CRDT的更新稍后会复制到其他节点。

CRDT在需要高可用性的情况下也很有用。如果一个或多个节点在群集中无响应,则这决不会影响其他节点读取和更新它们所持有的CRD的能力。对于网络分区造成的脑裂,一旦消除了网络分区,在CRDT上执行的任何更新都将复制到曾经无法访问的节点。

最后,在需要非常高吞吐量写入的某些情况下,CRDT可能很有用。具体取决于所使用的特定CRDT,例如计数器和投票可以支持非常高的吞吐量写入,因为它们不需要将每个更新复制到每个节点,只需偶尔复制它们的更新就足够了。

CloudState中提供CRDT

  • GCounter:仅增长计数器或GCounter是一个只能递增的计数器。它的工作原理是跟踪每个节点的单独计数器值,并获取所有节点的值之和以获取当前计数器值。由于每个节点仅更新其自己的计数器值,因此每个节点可以协调这些更新以确保它们是一致的。然后合并函数,如果它看到同一节点的两个不同的值,则只取最高值,因为它必须是节点发布的最新值。
  • PNCounter:正负计数器或PNCounter是一个可以递增和递减的计数器。它的工作原理是两个GCounters,一个跟踪增量的正数,一个跟踪减量的负数。通过从正GCounter中减去负GCounter来计算最终计数器值。
  • GSET:仅增长集(GSet)是一个只能添加项目的集合。GSet是一个非常简单的CRDT,它的合并函数是通过合并两个GSets的并集来定义的。(类似事件日志)
  • ORSet:Observed-Removed Set或ORSet是一个可以添加和删除项目的集合。它是通过为每个元素维护一组唯一标记来实现的,这些标记是在添加到集合中时生成的。删除元素时,该节点当前观察的所有标记都将添加到删除集中,因此只要节点在删除元素时没有看到任何新添加,该元素将是除去。一个天真的实现将在删除元素时累积逻辑删除,但是CloudState参考实现提供了清理逻辑删除的实现。
  • Flag:Flag是一个以false开头的布尔值,可以设置为true。设置为true后,无法将其设置为false。标志是一个非常简单的CRDT,合并函数只是一个布尔值或合并的两个标志值。
  • LWWRegister:Last-Write-Wins寄存器或LWWRegister是一个CRDT,它可以保存任何值,以及时钟值和节点ID,以指示何时由哪个节点更新。如果两个节点具有两个不同版本的值,则具有最高时钟值的节点获胜。如果时钟值相等,则使用节点上的稳定函数来确定它(例如,具有最低地址的节点)。请注意,LWWRegisters不支持对其值进行部分更新。如果寄存器包含person对象,并且一个节点更新age属性,而另一个节点同时更新name属性,则这些更新中只有一个最终会获胜。默认情况下,LWWRegister容易受到节点之间时钟偏差的影响。如果可以获得更可靠的更新排序,CloudState支持可选地提供自定义时钟值。
  • ORMap:Observed-Removed Map或ORMap类似于ORSet,另外该集合的值用作Map的键,Map的值本身就是CRDT。当在两个不同节点上同时修改ORMap中相同键的值时,将两个节点中的值合并在一起。
  • 投票:投票是CRDT,允许节点对条件进行投票。它类似于GCounter,每个节点都有自己的计数器,奇数值被认为是对条件的投票,而偶数值被认为是投票。投票的结果是通过获取当前集群成员的所有节点的投票来决定的(当节点离开时,其投票被丢弃)。可以使用多种决策策略来决定投票结果,例如至少一个,多数和所有。

在CloudState中使用CRDT的方法

有状态服务可以管理多个CRDT,每个CRDT由CloudState实体密钥标识。

CloudState代理负责实现CRDT机制。这包括合并功能,复制状态变化的机制以及确保所有节点最终就每个CRDT状态达成共识。代理将告诉用户函数CRDT的状态是什么,并且具有用于推送更新和从用户功能接收更新的协议。代理和用户功能通过轮流允许进行更新来保持其本地表示同步 - 允许用户功能在从代理接收命令时进行更新,并允许代理进行更新(当用户功能上没有未完成的命令时,从其他节点接收)。这种方法使CRDT实现在用户功能中非常简单,

流式CRDT呼叫

CloudState CRDT支持处理服务器流式调用,也就是说,当CRRT的gRPC服务调用将返回类型标记为streamed。当用户功能接收到流式消息时,允许更新CRDT,有两种情况 - 首次接收呼叫时,以及客户端取消流时。如果它希望在其他时间进行更新,则可以通过向流向下发送的流式消息发出效果来实现。

用户功能可以响应任何内容向下发送消息,但是CloudState提供的支持库仅允许发送消息以响应CRDT的变化。通过这种方式,可以实现需要监视CRDT状态的用例。

写一致性

默认情况下,更新在本地节点上执行,并异步复制到其他节点。更新也可以在其他写入一致性上执行,CloudState支持多数和所有。请注意,当使用非本地写入一致性时,CRDT的许多优点不再可用,写入将需要网络通信,并且可能受到其他节点上的故障的影响。因此,应谨慎使用非本地写入一致性,它们主要适用于在将节点复制到另一个节点之前由于节点崩溃而丢失写入的罕见情况是不可接受的。

虽然CRDT可以持久,但CloudState Reference Implementation还不支持持久CRDT。将来可能会提供此功能。

由于CloudState CRDT不持久,这意味着扩展到零,完整的集群崩溃将导致所有数据丢失。