【技术干货分享】银联分布式缓存的异地多活实践

avatar
Administrator

2024-09-10

39
0

分享嘉宾：中国银联 云计算中心UPRedis 赵仕荣

主要内容有:

1. 异地多活的必要性:多中心、就近访问、高可用性等需求。

2. 异地多活的实现方案:主从复制、主动复制、双向同步。双向同步需要解决循环复制和断点续传问题,引入了AOF Binlog算法。

3. 处理异地多写冲突:使用CRDT算法,如LWW-Element-Set ,确保数据最终一致性。

4. AOF Binlog和LWW-Element-Set算法的具体实现方式。

5. 异地多活部署的应用场景:单元化和多中心共享数据。提出单元化场景更适合银行体系。

6. 异地数据同步的全量+增量方案:先用复制协议完成全量数据同步,然后同步增量的AF Blog进行同步。

7. 异地多活部署存在的一些限制。

异地多活的必要性

实时架构异地多活（Multi-Live）的设计是一种高级的系统架构方案，旨在通过在不同地理位置部署相同的服务实例来提高系统的可用性和可靠性。这种架构不仅有助于应对自然灾害、硬件故障等突发事件，还能优化用户的访问体验。以下是实施异地多活架构的一些必要性：

1. 提高系统可用性

  • 灾难恢复：在某个数据中心发生灾难性事件（如地震、火灾、洪水等）时，其他地理区域的数据中心可以无缝接管服务，确保业务连续性。

  • 故障转移：当某个数据中心出现故障时，流量可以自动切换到健康的节点，减少宕机时间。

2. 优化用户体验

  • 减少延迟：通过就近原则将请求路由到最近的数据中心，减少网络延迟，提高用户体验。

  • 负载均衡：可以更好地分散全球范围内的负载，防止单一数据中心过载。

3. 数据一致性和完整性

  • 数据冗余：在多个地点保存数据副本，可以有效防止数据丢失。

  • 数据同步：通过实时数据同步技术，确保各个数据中心之间的数据一致性。

4. 法规遵从

  • 数据主权：许多国家和地区有数据驻留要求，即用户数据必须存储在本地，以遵守当地法律。异地多活架构可以帮助企业满足这些规定。

  • 合规性：对于金融、医疗等行业，数据保护和隐私法规可能要求数据在不同地区有备份。

5. 扩展能力

  • 灵活扩展：可以根据业务需求动态调整资源，无需担心单点限制。

  • 全球化布局：便于企业在全球范围内拓展业务，支持国际化战略。

实施挑战

尽管异地多活架构带来了诸多好处，但也面临着一些技术和运营上的挑战：

  • 数据同步：确保数据在不同数据中心之间的一致性是一项技术难题。

  • 网络复杂性：跨地域的网络连接需要高度可靠且低延迟。

  • 成本问题：部署和维护多个数据中心的成本较高。

  • 管理难度：多个数据中心的运维管理更加复杂，需要先进的自动化工具和流程。

技术方案

为了克服这些挑战，通常会采用以下技术手段：

  • 分布式数据库：使用支持多活架构的分布式数据库，如TiDB、CockroachDB等。

  • 分布式缓存：使用如Redis Cluster等分布式缓存系统来提高数据访问速度。

  • 数据复制与同步：利用成熟的复制技术（如MySQL主从复制、Kafka MirrorMaker等）来同步数据。

  • 负载均衡与路由：使用DNS负载均衡、智能DNS解析等技术来实现流量的智能调度。

  • 故障切换与恢复：设计自动化的故障检测与切换机制，确保在故障发生时能够快速恢复服务。

总的来说，异地多活架构虽然增加了系统的复杂性和成本，但它对于那些追求高可用性和全球覆盖的企业来说是必不可少的。通过精心规划和利用现代技术，企业可以构建出既稳定又高效的实时架构。如果您有具体的场景或技术细节需要探讨，欢迎继续提问。

lww element

"LWW Element" 是一种常用于分布式系统中的数据结构，其全称是 "Last Write Wins Element"。这种数据结构主要用于解决分布式环境中的冲突解决和数据一致性问题，特别是在弱一致性和最终一致性模型中。

LWW Element 的概念

LWW Element 是一种特殊的数据结构，它记录了每个元素最后一次写入的时间戳以及对应的值。当多个节点尝试更新同一个元素时，最终保留的是最新写入的那个值。这种方式特别适合于分布式系统中，因为在这些系统中，由于网络延迟、分区等问题，可能无法立即得知哪个写操作是最新的。

工作原理

  1. 版本控制：每个元素都有一个版本号（通常是时间戳），表示最后一次更新的时间。

  2. 写操作：当一个元素被更新时，它的版本号也会更新为当前的时间戳。

  3. 读操作：读取元素时，返回带有最高版本号（即最新时间戳）的值。

  4. 冲突解决：如果两个节点同时尝试更新同一个元素，并且网络延迟导致这两个更新未能同步，那么在后续的同步过程中，系统会选择版本号较高的那个更新作为最终的值。

特点

  • 简单性：LWW Element 的实现相对简单，只需要记录每个元素的版本号即可。

  • 性能：由于不需要复杂的共识算法来确保所有节点的一致性，LWW Element 在高并发环境下表现良好。

  • 最终一致性：LWW Element 保证了最终一致性，即随着时间推移，所有节点最终会收敛到相同的值。

  • 可扩展性：适用于大规模分布式系统，因为它允许多个节点并行写入而不必等待全局一致性。

使用场景

LWW Element 适用于那些对数据一致性要求不是非常严格的应用场景，例如：

  • 日志系统：在日志系统中，最新的日志条目覆盖旧的日志条目是合理的。

  • 缓存系统：在缓存系统中，当数据更新时，最新的值覆盖旧的值。

  • 分布式数据库：在分布式数据库中，特别是那些需要高可用性和分区容忍性的系统中，LWW Element 可以用来处理数据冲突。

实例

一个简单的 LWW Element 可能包含以下几个部分：

{
    "value": "some_value",
    "timestamp": 1631313600,  // UNIX 时间戳，例如 2021-09-10T12:00:00Z
}

在这个例子中，value 是元素的当前值，timestamp 是最后一次写入的时间戳。如果两个节点同时更新这个元素，那么拥有较新时间戳的更新将会覆盖之前的值。

优点与缺点

优点:

  • 实现简单。

  • 高性能，适合高并发场景。

  • 良好的可扩展性。

缺点:

  • 可能会导致数据丢失，因为较早的更新会被覆盖。

  • 不适合需要强一致性的场景。

总结

LWW Element 是一种实用的机制，用于解决分布式系统中的数据冲突问题。它通过记录最后一次写入的时间戳来确定哪个版本的数据应该是有效的。这种机制非常适合那些对性能和可扩展性有高要求，但可以接受一定程度数据丢失的应用场景。然而，在需要强一致性的系统中，LWW Element 可能不是最佳选择，这时可能需要考虑其他更复杂的解决方案，如 Raft 或 Paxos 协议。

LWW Element（Last Write Wins Element）作为一种解决分布式系统中数据冲突的机制，虽然在很多场景下非常有用，但也存在一些难点，并且有许多潜在的优化点。下面我们详细探讨一下这些方面。

难点

  1. 数据丢失风险：

    • 当多个写操作并发发生时，非最新的写操作会被丢弃，这可能导致有价值的数据被覆盖。

    • 在某些情况下，数据的丢失可能对业务产生不利影响。

  2. 时间戳的管理：

    • 时间戳需要在整个分布式系统中保持一致，否则可能会导致错误的结果。

    • 需要考虑到时钟偏移和网络延迟等因素，确保时间戳的准确性。

  3. 全局时间戳的同步：

    • 在大规模分布式的环境中，保持所有节点的时间戳同步是一个挑战。

    • 如果节点之间的时间戳不同步，可能导致不正确的数据覆盖。

  4. 并发冲突：

    • 在高并发的场景下，LWW Element 可能会频繁地发生冲突，导致大量的写操作实际上没有改变数据，只是更新了时间戳。

  5. 事务支持：

    • LWW Element 本身并不支持原子性的事务操作，这在需要保证一组操作要么全部成功要么全部失败的场景中是个问题。

优化点

  1. 时间戳的改进：

    • 逻辑时钟：使用矢量时钟（Vector Clocks）或因果时钟（Causal Clocks）来替代单一的时间戳，可以更好地处理并发写操作。

    • 混合逻辑时钟（Hybrid Logical Clocks）：结合物理时钟和逻辑时钟的优点，提供更为精确的并发控制。

  2. 冲突检测与解决：

    • 多版本并发控制（MVCC）：允许保留多个版本的数据，并在读取时选择最新版本。这种方法可以减少数据丢失的风险。

    • 冲突解决策略：除了简单的“最后写入者胜利”外，还可以根据业务逻辑定义更复杂的冲突解决规则。

  3. 减少不必要的写操作：

    • 乐观锁：通过乐观锁机制来减少不必要的写操作，只有当数据确实被修改时才更新时间戳。

    • 写前检查：在写入之前检查数据是否已被更新，如果是，则跳过本次写操作。

  4. 时间戳同步：

    • NTP（Network Time Protocol）：使用 NTP 来同步分布式系统中的时间，减少时钟偏移的影响。

    • 分布式时钟服务：部署专门的分布式时钟服务来提供全局一致的时间戳。

  5. 事务支持：

    • 分布式事务协议：实现如两阶段提交（2PC）或三阶段提交（3PC）等分布式事务协议，以支持原子性的事务操作。

    • 分布式锁：使用分布式锁机制来确保一组操作的原子性。

  6. 数据版本管理：

    • 版本控制：引入版本控制机制，允许追踪数据的历史版本，这对于审计和回滚非常重要。

    • 增量更新：仅更新数据的变动部分，而不是每次都更新整个数据项。

实践建议

  • 评估业务需求：在使用 LWW Element 之前，首先要评估业务的具体需求，了解是否可以接受数据丢失的情况。

  • 监控与调试：实施监控机制来跟踪时间戳的变化，以及冲突发生的频率，以便及时发现问题并进行调试。

  • 持续优化：随着系统的发展，不断地评估和优化时间戳管理机制，确保系统的性能和可靠性。

通过上述的优化措施，可以在一定程度上缓解 LWW Element 的局限性，使其更适合于更广泛的分布式应用场景。如果您的系统有特定的需求或遇到具体的问题，请提供更多细节，以便给出更具针对性的建议。

针对 LWW Element（Last Write Wins Element）在分布式系统中遇到的难点及其优化点，可以采取多种解决方法来缓解这些问题。下面详细探讨具体的解决方案：

1. 数据丢失风险

解决方法：

  • 多版本并发控制（MVCC）：通过保存多个版本的数据，可以避免重要数据的丢失。在读取时可以选择最新的版本，而在需要时也可以访问历史版本。

  • 业务逻辑中的冲突解决策略：定义业务逻辑中的冲突解决规则，当发生冲突时，可以根据业务需求决定如何处理，而不是简单地覆盖旧数据。

2. 时间戳的管理

解决方法：

  • 逻辑时钟：

    • 矢量时钟（Vector Clocks）：每个节点都有一个独立的时钟计数器，每次写操作都会增加该计数器。矢量时钟可以用来检测并发写操作，并解决冲突。

    • 因果时钟（Causal Clocks）：类似于矢量时钟，但只记录实际发生因果关系的操作，从而减少了时钟的维度。

  • 混合逻辑时钟（Hybrid Logical Clocks）：结合物理时钟和逻辑时钟的优点，既能保证时间戳的单调递增，又能检测并发操作。

3. 全局时间戳的同步

解决方法：

  • NTP（Network Time Protocol）：使用 NTP 来同步分布式系统中的时钟，减少时钟偏移的影响。

  • 分布式时钟服务：部署专门的分布式时钟服务，如 ZooKeeper 或 Etcd，来提供全局一致的时间戳。

4. 并发冲突

解决方法：

  • 乐观锁：通过乐观锁机制减少不必要的写操作，只有当数据确实被修改时才更新时间戳。

  • 写前检查：在写入之前检查数据是否已被更新，如果是，则跳过本次写操作，从而减少不必要的冲突。

  • 冲突检测与解决：实现更复杂的冲突检测机制，比如在发生冲突时，通过比较数据的版本号或其他元数据来决定如何处理。

5. 事务支持

解决方法：

  • 分布式事务协议：

    • 两阶段提交（2PC）：通过协调者和参与者之间的两次投票来确保事务的一致性。

    • 三阶段提交（3PC）：通过增加一个准备阶段来减少锁定时间，提高系统性能。

  • 分布式锁：使用分布式锁机制来确保一组操作的原子性，比如通过 Redis 的 SETNX 命令或者分布式锁服务如 Redlock。

6. 数据版本管理

解决方法：

  • 版本控制：引入版本控制机制，允许追踪数据的历史版本，这对于审计和回滚非常重要。

  • 增量更新：仅更新数据的变动部分，而不是每次都更新整个数据项，减少不必要的数据复制和同步。

实践建议

  1. 评估业务需求：首先明确业务需求，了解哪些数据是可以接受丢失的，哪些数据必须保留。根据这些需求来设计数据结构和冲突解决策略。

  2. 监控与调试：实施监控机制来跟踪时间戳的变化，以及冲突发生的频率，以便及时发现问题并进行调试。

  3. 持续优化：随着系统的发展，不断地评估和优化时间戳管理机制，确保系统的性能和可靠性。

示例实现

1. 使用矢量时钟解决冲突

{
    "value": "some_value",
    "vector_clock": {
        "node1": 2,
        "node2": 1,
        "node3": 0
    }
}

在这个例子中，每个节点都有一个独立的计数器。当发生冲突时，比较各个节点的计数器值来决定哪个版本的数据应该胜出。

2. 使用乐观锁

{
    "value": "some_value",
    "version": 3
}

客户端在读取数据时获取当前版本号，更新数据时带上版本号，如果版本号不匹配，则重试。

3. 使用分布式锁

使用分布式锁服务（如 Redis 或 ZooKeeper）来保证在并发操作时只有一个节点能够修改数据。

// Redis 锁的伪代码
lock = redis.setnx("mylock", "locked")
if lock:
    # 执行写操作
    ...
    redis.del("mylock")  # 释放锁
else:
    # 锁已被占用，等待或重试

通过上述方法，可以有效地解决 LWW Element 在分布式系统中面临的难点，并对其进行优化。如果您的系统有特定的需求或遇到了具体的技术挑战，请提供更多细节，以便提供更具体的建议和支持。

CRDT

CAP理论证明三者之间不可能同时完全满足,如果分布式数据库必须满足P-分区容忍性,CA只能占其一.A是可用性,C是一致性.
CRDT(Conflict-Free Replicated Data Type)能根据一定的规则自动合并,解决冲突,达到最终一致的状态.即可以满足AP,但会保证最终是一致的.
参考链接1有详细的CRDT介绍,链接2是Redis lab基于CRDT实现的分布式数据库系统,链接3介绍Roshi,也是一个基于CRDT的开源分布式数据库,本文重点关注Roshi

Roshi起源

SoundCloud公司(类似于喜马拉雅),会有大V和粉丝人群,如果一个大V发布一条音频,那么有如下两种方式发布给粉丝:

  • Fan out on write:每个粉丝有一个收件箱,将该信息放入所有粉丝的收件箱.很明显,这样有利于粉丝的读取,但是会有大量的写和冗余数据.

  • Fan in on read:将信息放入大V的发件箱,当粉丝查看的时候从所有该用户关注的大V信箱拉取信息并且合并展示.这种方法不利于读取,如果有大量的关注,那么得从大量的发件箱去拉取数据.但是由于数据冗余很小,可以考虑将数据放入内存,例如Redis.那么Redis如何实现为一个分布式数据库就提上了日程

Roshi实现

Roshi,一个分布式时间序列的数据库.底层使用Redis ZSET存储数据(模拟每个人的发件箱).整体架构如下:

  • Pool:基于key的sharding

  • cluster:实现Insert/Select/Delete API

  • farm:Writes发往所有的clusters,可以配置quorum,大于等于该quorum返回成功.Read有不同的策略,生产上使用的读策略最好允许read-repair(下文介绍)

  • roshi-server:给farm提供rest http 接口.无状态并且兼容12-factor

  • roshi-walker:扫键以便触发read repairs

API

  • Insert(key, timestamp, value)

  • Delete(key, timestamp, value)

  • Select(key, offset, limit) []TimestampValue

select的offset,limit用于分页获取

数据结构

CRDT需要满足交换律、结合律以及幂等性,Roshi实现的是LWW-element-set,即 Last Writer Wins element set.满足以下两个条件:

  • 如果一个元素最近一次操作是add,那么它肯定在集合中

  • 如果一个元素最近一次操作是remove,那么它肯定不在集合中

具体实现原理为:集合痛殴两个集合A和R表示,A为add set,R为remove set,增加元素时增加一个tuple例如(e,timestamp)到A中,删除一个元素时增加一个tuple例如(e,timestamp2)到R中.那么检查一个元素e是否在集合S中,即需要查看e是否在A中,并且在R中没有大于A中时间戳的e存在

Roshi中操作如下,三列分别代表原始状态,操作,最终状态

Original state

Operation

Resulting state

A(a,1) R()

add(a,0)

A(a,1) R()

A(a,1) R()

add(a,1)

A(a,1) R()

A(a,1) R()

add(a,2)

A(a,2) R()

A(a,1) R()

remove(a,0)

A(a,1) R()

A(a,1) R()

remove(a,1)

A(a,1) R()

A(a,1) R()

remove(a,2)

A() R(a,2)

A() R(a,1)

add(a,0)

A() R(a,1)

A() R(a,1)

add(a,1)

A() R(a,1)

A() R(a,1)

add(a,2)

A(a,2) R()

A() R(a,1)

remove(a,0)

A() R(a,1)

A() R(a,1)

remove(a,1)

A() R(a,1)

A() R(a,1)

remove(a,2)

A() R(a,2)

其他实现

Redis lab的商业版实现包括了更多的类型,包括register(string),counter等等.并且实现CRDT的方式也略有不同.详情可参考后文链接.

如果update操作无法满足条件，则可以考虑同步副本数据，同时附带额外元信息，通过元信息让update和merge操作具备以上三律，这种形式称为state-based CRDT。让元信息满足条件的方式是让其更新保持__单调__，这个关系一般被称为__偏序关系__。举一个简单例子，每次update操作都带上时间戳，在merge时对本地副本时间戳及同步副本时间戳进行比对，取更新的结果，这样总能保证结果最新并且最终一致，这种方式称为Last Write Wins：

有两点值得注意的地方：

  • update操作无法满足三律，如果能将元信息附加在操作或者增量上，会是一个相对state-based方案更优化的选择

  • 如果同步过程能确保exactly once的语义，幂等律条件是可以被放宽掉，比如说加法本身满足交换律结合律但不幂等，如果能保证加法操作只回放一次，其结果还是最终一致的。

有了以上的理论基础后，我们可以看看各种数据结构如何设计，才能满足CRDT，达到最终一致。

CRDTs一览

以下展示一些典型的CRDT数据结构的例子，每一种数据类型都会给出示意图，必要时给出伪代码说明，证明略过，有兴趣可参见[2]。

Counter

counter是最简单的例子，为了说明state-based和op-based的差异，在此分别给出两种形式的描述。

Op-based counter

counter的op-based形式支持两种写操作：increment和decrement，由于加法天然满足交换律和结合律，所以非常容易实现，直接转发操作即可：

但要注意的是加法不幂等，所以同步过程中需要保证不丢不重。

G-Counter (Grow-only Counter)

counter的state-based形式并非那么的显而易见，为了简化问题，我们先从一个只有increment的counter开始看起。
由于同步的是全量，如果每个副本单独进行累加，在进行merge的时候无法知道每个副本具体累加了多少，更不能简单的取一个max作为最终结果，比如A做一次INCR 1同时B做一次INCR 2，副本全量同步之后，A和B都取max以2做为结果并最终一致，但正确的结果应该是3。
所以一种可行的方式是在每个副本上都使用一个数组保留其它所有副本的值，update时只操作当前副本在数组中对应项即可，merge时对数组每一项求max进行合并，query时返回数组的和，即为counter的当前结果。

update increment()
    let g = myID()
    P[g] := P[g] + 1
query value(): integer v
    let v = sum(P)
merge (X, Y): Z
    let Z.P[i] = max(X.P[i], Y.P[i]) (i in [0, n - 1])

易见update和merge均能保证单调的递增，所以G-Counter是state-based CRDT。

PN-Counter

带有decrement的state-based CRDT也并非像G-Counter那样显而易见，带有减法之后，不能满足update时单调的偏序关系。 所以正确的方式是构造两个G-Counter，一个存放increment的累加值，一个存放decrement的累加值。

Register

register本质是一个string，仅支持一种写操作assign。并发assign是不存在交换律的，所以需要考虑附加上偏序关系。

Last-Writer-Wins Register (LWW Register)

一种简单的做法是后assign的覆盖先assign的(last write wins)，方式是每次修改都附带时间戳，update时通过时间戳生成偏序关系，merge时只取较大时间戳附带的结果。示意图前文已经给出。

Set

Set一共有两种写操作，add和remove，多节点并发进行add和remove操作是无法满足交换律的, 会产生冲突：

所以必须附加一些额外信息，可以从一个只做添加的set开始看起。

Grow-Only Set (G-Set)

set的add操作本质上是求并，天然满足交换律、结合律和幂等律, 满足Op-based CRDT：

交换律: X U Y = Y U X
结合律: (X U Y) U Z = X U (Y U Z)

幂等律: X U X = X

2P-Set

考虑删除操作，思路和PN-Counter一致，使用两个G-Set, set A只负责添加，对于从set A中remove的元素不做实际删除，只是复制到set R中，如下：

query时如果元素在set A且不在set R中，则表示该元素存在。

query lookup(e): bool b 
    let b = (e in A && e not in R)

由于只同步操作，且两个set只添加不减少，易证其为op-based CRDT。但2P-Set十分不实用，一方面已经被删除的元素不能再次被添加，一方面删除的元素还会保留在原set中，占用大量空间。

LWW-element-Set

为了解决删除元素不能再次添加的问题，可以考虑给2P-Set中A和R的每个元素加一个更新时间戳，其它操作保持不变，只要在查询的时候做如下处理

query lookup(e): bool b
    let b = (t1 < t2): (e, t1) in A && (e, t2) not in R

一个更优化的实现是不要R集合，而A集合中每一个元素除了维护一个更新时间戳之外，还有一个删除标志位。

Observed-Remove Set (OR-Set)

还有一种想法不太相同的设计，核心思想是每次add(e)的时候都为元素e加一个唯一的tag，remove(e)将当前节点上的所有e和对应的tag都删除，这样在remove(e)同时其它节点又有并发add(e)的情况下e是能够最终保证添加成功，此种语义称为add wins。如图，A上做remove e时仅有A一个tag，所以在C收到A同步过来的remove时，只删除tag A，tag B保留e在C上仍然存在，最终ABC三个节点是一致的，都有e及tag B。

虽然在remove时看似存在并不能保证交换律的删除操作出现，但删除的元素是全局唯一的，所以并不破坏语义，故仍然是为CRDT。
ORSet相对来说是一种比较实用的结构，但实现上仍然有几个问题要解决：

  • 重复add和remove的场景下会产生大量的tag，空间需要优化

  • 在考虑空间优化的前提下如何生成全局唯一的tag

  • 需要考虑如何进行垃圾回收

学术界有多篇论文都是在探讨对此种算法的优化。但OR-Set在实践中最严重的问题是一旦同步通道出现延迟或者中断，很可能出现用户认为早已删除掉的字段在同步恢复之后再次出现。从工程实践角度讲，更优化的方案是使用时间戳作为unique tag，好处是易保证唯一性，同时自带单调递增属性，重复删除添加时不会生成大量tag。

基于CRDT的数据最终一致性

对于分布式系统的架构师来说，CAP 定理所描述的一致性和可用性是一个较大的挑战。网络远程跨机房是不可避免的，数据中心之间的高延迟总是导致数据中心之间在短时间内出现某种断开。因此，传统的分布式应用体系结构被设计成要么放弃数据一致性，要么降低可用性。

不幸的是，我们不能牺牲应用可用性。尝试保持一致性，业界接受了最终一致性模型。在这个模型中，应用依赖于数据库管理系统来合并数据的所有本地副本，以使它们最终保持一致。除非出现数据冲突，最终一致性模型看起来很好。一些最终一致性模型承诺尽最大努力解决冲突，但不能保证强一致性。

1. 什么是CRDT？

一个新趋势是，围绕CRDT构建的模型提供了强最终一致性。那么，什么是CRDT 呢？

CRDT是无冲突复制数据类型的缩写。CRDT通过预先确定的一套解决冲突规则和语义来实现了最终一致性，它引入一组特殊的基础数据类型， CRDT是一种特殊的数据类型，可以从所有数据库副本汇聚数据。常用的 CRDTs包括 G-counters (grow-only counters)、 PN-counters (positive-negative counters)、寄存器、 G-sets (grow-only sets)、2P-sets (two-phase sets)、 or- sets (observed-remove sets)等等。

在背后，CRDT依靠以下数学特性来处理数据:

  1. 交换律：a ☆ b = b ☆ a

  2. 结合律：a ☆ ( b ☆ c ) = ( a ☆ b ) ☆ c

  3. 等幂: a ☆ a = a

G 计数器是一个完美的例子，操作 CRDT合并的业务。这里，a + b = b + a 和 a + (b + c) = (a + b) + c。副本之间只交换更新(增加的内容)。CRDT 通过添加更新来合并更新。例如，g 集合应用幂等({ a，b，c } u { c } = { a，b，c })来合并所有元素。幂等可以避免在元素通过不同路径传递和汇聚时重复添加到数据结构中的元素。

一个典型的多主系统的副本同步方式如下：

CRDT能够自己解决合并冲突，更一般的情况是处理在多leader分布式系统中的副本同步。

那么， 有哪些典型的副本同步模式呢？

2. 副本同步模式

2.1 基于状态的同步

基于状态的同步， 也称为被动同步，形式为聚合复制数据类型（Convergent Replicated Data Type，CvRDT）， 用于 NFS、 AFS、 Coda 等文件系统，以及 Riak、 Dynamo 等 KV存储。

在这种情况下，副本通过发送对象的完整状态来传播更改，必须定义 merge ()函数，以将传入的更改与当前状态合并。

基于状态的同步必须满足以下要求，以确保复制的一致性:

  • 数据类型(或复制上的状态)形成一个具有最小上界的偏序集

  • Merge ()函数产生一个最小上界

  • 副本构成一个连通图

例子:

数据类型: 自然数集是N，极小元到正负无穷大，则Merge (x，y) = max (x，y)

这样的要求给出了一个用于交换的幂等merge()函数，它也是给定数据类型上的一个单调递增函数。

这保证了所有的副本最终都会聚合收敛，并且让我们不用担心传输协议ーー可以丢失传播更新，也可以多次发送它们，甚至可以按任何顺序发送它们。

2.2 基于操作的同步

基于操作的同步，也称为主动同步，形式为交换复制数据类型（Commutative Replicated Data Type ，CmRDT），用于 Bayou, Rover, IceCube, Telex这样的系统。

在这种情况下，副本通过向所有副本发送操作来传播更改。当对副本进行更改时:

  1. 执行 generate ()方法，该方法返回一个要在其他副本上调用的 effector ()函数。换句话说，effector ()是一个用于修改其他副本状态的闭包。

  2. 将effector ()应用于本地状态

  3. 向所有其他副本传播effector ()

  1. 基于操作的同步必须满足以下要求，以确保复制的一致性:

  • 可靠的传输协议

  • 如果effector()以因果顺序交付，那么并发 effector ()就必须转换为OR

  • 如果effector()在没有遵守因果顺序的情况下交付，那么所有effector()都必须转换

  • 如果能够多次传递，则 effector ()必须是幂等的. 在现实中，一般会依赖于可靠的发布-订阅系统(例如，Kafka)作为交付的一部分。

2.3 基于增量的同步

考虑到基于状态/操作的同步，如果一个更改只影响对象的一部分，那么传输整个对象的状态是没有意义的。此外，如果更新修改了相同的状态(如计数器) ，我们可以周期性地只发送一个聚合状态。

增量同步结合了状态和操作这两种方法，并传播所谓的 Delta 变异，这些变异相应地将状态更新到最后的同步日期。所以，需要发送一个完整的状态进行第一次同步，然而，一些实现实际上考虑了远程副本的状态以降低所需的数据量。

如果允许延迟，那么基于操作的日志压缩可能是下一个优化:

2.4 基于纯操作的同步

在基于操作的同步中有一个延迟，以创建一个effector()。在某些系统中，这样的延迟是不可接受的，必须立即传播更新，需要更复杂的组织协议以及更多的元数据空间

典型用法：

  1. 如果在系统中必须立即传播更新，基于状态的同步是一个糟糕的选择，因为它会增加整个状态的成本。然而，在这种特殊情况下，基于增量的同步是更好的选择，与基于状态更新的差别不会太大。

  2. 如果你需要在失败后同步副本，基于状态/基于 delta 是正确的选择。如果必须使用基于操作的同步，则必须:

  • 回复所有失败后遗漏的更改

  • 获取其中一个副本的完整副本并应用于所有错过的操作

3.基于操作的同步只需要将 effector ()传递给每个副本一次。通过要求effector ()具有幂等性，可以放松这一要求。实际上，前者比后者更容易实现。

基于操作和基于状态的同步之间的关系是:基于操作和基于状态的同步可以在保持 CRDT 要求的前提下相互仿真。

3. 数据一致性模型

一致性模型数据协议是分布式数据库和应用程序之间的一个协议，它定义了在写操作和读操作之间数据的清洁程度。

例如，在一个强一致性模型中，数据库保证应用程序总是读取最后一次写入的数据。使用循序一致性数据库的时候，数据库保证你读取的数据的顺序与数据写入数据库的顺序一致。在最终一致性模型中，分布式数据库承诺在幕后同步和整合数据库副本之间的数据。因此，如果将数据写入一个数据库副本并从另一个数据库副本读取数据，则可能不会读取数据的最新副本。

关于最终一致性的研究已经有了许多的研究成果。当前的趋势是从强一致性转向其他可能的一致性变化，研究什么样的数据一致性模型最适合特定的系统/场景，并需要重新考虑当前的定义。这就导致了一些矛盾，例如，当一些人考虑一个具有特殊属性的最终一致性时，同时，其他作者已经为这个特殊情况创建了一个定义。

简单地，可以从效果来重新定义最终一致性，即如果所有请求都没问题，那么它最终是一致的。

3.1 数据一致性的分类

强一致性(SC)

所有的写操作都严格按顺序执行，对任何副本的读请求都返回相同的、最后的写结果，需要实时的共识(及其所有后果) 。为了解决冲突，允许 n/2-1节点关闭。

最终一致性（EC）

在本地进行更新，然后传播更新。读取一些副本可能会返回过时的状态。回滚或以某种方式决定在发生冲突时应该做什么。也就是说，我们还需要共识，不是实时的。

强最终一致性（SEC）

EC + 复制有一个自动解决冲突的方法。因此，我们不要求达成共识，允许关闭 n-1节点。

如果放松 CAP 定理中的 SC 要求，那么 SEC 就解决了那些恼人的问题。

3.2 强一致性

两阶段提交是实现强一致性的常用技术。这里，对于本地数据库节点上的每个写操作(添加、更新、删除) ，数据库节点将更改传播到所有数据库节点，并等待所有节点确认。然后，本地节点向所有节点发送一个提交，并等待另一个确认。应用程序只能在第二次提交之后才能读取数据。当网络断开数据库之间的连接时，分布式数据库将不能进行写操作。

3.3 最终一致性的实现方法

最终一致性模型的主要优点是，即使在分布式数据库副本之间的网络连接中断的情况下，数据库也可以执行写操作。一般来说，这个模型避免了两阶段提交产生的往返时间，因此支持的每秒写操作比其他模型多得多。最终一致性必须解决的一个问题是冲突，即在不同的地方同时写同一个条目。根据如何避免或解决冲突，最终一致性可以进一步分为以下几类:

最后写入的最终一致性（Last writer wins ，LWW)

在这种策略中，分布式数据库依赖于服务器之间的时间戳同步。数据库交换每个写操作的时间戳和数据本身。如果发生冲突，使用最新时间戳的写操作获胜。

这种技术的缺点是假设所有系统时钟都是同步的。实际上，同步所有的系统时钟是困难和昂贵的。

法定人数的最终一致性（Quorum-based eventual consistency）

此技术类似于两阶段提交。然而，本地数据库并不等待所有数据库的确认; 它只是等待大多数数据库的确认。多数人的确认确定了法定人数。如果发生冲突，建立仲裁的“写”操作获胜。

另一方面，这种技术增加了写操作的网络延迟，从而降低了应用程序的可伸缩性。此外，如果本地数据库与拓扑中的其他数据库副本隔离，那么它将不能进行写操作。

合并复制（Merge replication）

在这种关系数据库中常见的传统方法中，一个集中的合并代理将所有数据合并。这种方法还提供了一些灵活性，可以实现自己解决冲突的规则。

合并复制速度太慢，无法支持实时使用的应用程序，还存在一个单点故障。由于此方法不支持冲突解决的预设规则，因此常常导致冲突解决的错误实现。

无冲突复制数据类型（Conflict-free replicated data type，CRDT)

简而言之，基于 CRDT的数据库提供无冲突的最终一致性。基于 CRDT的数据库是可用的，即使分布式数据库副本不能交换数据。它们总是将本地延迟交付给读写操作。

因此，我们希望为不稳定且经常分区的分布式系统提供一组基础数据类型。此外，希望这些数据类型为我们解决冲突，这样就不需要与用户交互或查询仲裁节点。

然而，并非所有数据库用例都受益于CRDT，而且，基于 CRDT数据库的冲突解决语义是预定义的，不能被重写。

4. CRDT 分析

4.1 CRDT 之 Counter

一个带有两个操作的整数值: inc ()和 dec ()，让我们考虑一些基于操作和状态同步的实现:

4.1.1 基于操作的计数器

很明显，我们只需要传播更新。

例如，Inc () : generator (){ return function (counter){ counter + = 1}}。

4.1.2 基于状态的计数器

这是一个棘手的问题，因为我们还不清楚如何实现 merge ()函数。

增量计数器，g 计数器:

让我们使用一个具有副本数量大小的向量(又叫版本向量) ，每个副本在 inc ()操作中增加它的向量元素。Merge ()函数取相应向量项的最大值，即计数器值中所有向量元素的和。

此外，G-Set 也可以使用。

例如，社交媒体中点击/喜欢 的计数器。

加减计数器

使用两个 g 计数器，一个用于增量，另一个用于减量。

例如，P2P网络(Skype)中登录的用户数量。

非负数计数器:

不幸的是，到目前为止还没有一个现实中的应用。

4.2 CRDT之 Register

具有两个操作的存储单元：assign()和value()。问题在于assign()操作，它们不进行交换。有两种方法可以解决这个问题:

4.2.1 LWW-Register

通过在每个操作上生成惟一的 id (时间戳)来引入总顺序。

例如，基于状态的，通过元组(value，id)的更新:

现实中，cassandra 中的列和 NFS中整个文件或其中的一部分都是具体的应用场景。

4.2.2 Multi-Value Register

该方法类似于每个节点的 G-Counter+ store 的集合。Multi-Value Register的值是所有值，merge ()函数对所有向量元素应用 LWW 方法。

例如，网上商城中的购物篮。

4.3 CRDT之 Set

一个集合有两个非交换操作: add ()和 rmv () ，它是容器、映射、图等的基础类型。

考虑一个原生的集合实现，其中 add ()和 rmv ()在到达时顺序执行。首先，在第1和第2个副本上有并发的 add () ，然后 rmv ()在第1个副本上到达。

果然，在同步之后副本发生了偏移。

4.3.1 Grow-Only Set

一个非常简单的解决方案是根本不允许 rmv ()操作。Add ()操作转换，merge ()函数只是一个集合。

4.3.2 2P-Set

允许 rmv ()操作，但不能在删除元素后重新添加元素。一个附加的 g-set可以用来跟踪删除的元素(也称为墓碑集)。

4.3.3 LWW-element Set

思路是在一个集合中引入一个总顺序。例如，生成时间戳。我们需要两个集合: 添加集和删除集。Add ()将(element，unique _ id ())添加到 add-set，rmv ()将添加到 remove-set。Lookup ()检查 id 在 add-set 或 rmv-set 中的大小。

4.3.4 PN-Set

对集合进行排序的另一种方法ーー为每个元素添加一个计数器。在 add ()操作上增加它，在 rmv ()上减少它。当且仅当其计数器为正时，集合中要考虑相应的元素。

4.3.5 Observe-Remove Set, OR-Set, Add-Win Set:

在此数据类型中，add ()优先于 rmv ()。可能实现的一个例子是: 向每个新添加的元素添加唯一的标记(每个元素)。然后 rmv ()将元素的所有可见标记发送给其他副本，副本保留其他标记。

4.3.6 Remove-win Set

同上，但是 rmv ()优先于 add ().

4.4 CRDT之Graph

图类型基于集合类型。这里有以下问题: 如果有两个并发 addEdge (u，v)和 removeVertex (u)操作ー我们应该怎么做？有三种可能的策略:

  1. removeVertex ()具有优先级，所有关联的边都将被删除

  2. addEdge ()具有优先级，所有移除的顶点将被重新添加

  3. 延迟 removeVertex ()的执行，直到所有并发 removeVertex ()都执行为止

第一个是最容易实现的，因为可以只使用两个2p 集，得到的数据类型称为2p2p 图.

4.5 CRDT之 Map

对于map，有两个问题需要解决:

  • 如何处理并发 put ()操作? 可以类比计数器，使用 LWW 或 MV 语义吗？

  • 如何处理并发的 put ()/rmv ()操作？我们可以通过类比设置和使用 put-wins 或 rmv-wins 或 last-put-wins 语义么？

Map允许嵌套其他 CRDT 类型。需要注意的是，Map不处理其值的并发更改，必须由嵌套的 CRDT 本身来处理。

4.5.1 Remove-as-recursive-reset map

在此数据类型中，rmv (k)操作“重置”给定 k 下 CRDT 对象的值，例如，对于值为零的计数器。

例如，一个共享的购物车。一个用户添加更多的面粉，另一个同时做一个检查(这导致删除所有元素)。同步之后，有一个“单元”的面粉，这似乎是合理的。


4.5.2 Remove-wins map

在这种情况下，rmv ()优先于 add ()。

例如，玩家张三在一个网络游戏中有10个硬币和一个锤子。接下来发生了两个并发操作: 在副本 a 上她发现了一个钉子，在副本 b 上 Alice 被删除(删除所有项目)。

4.5.3 Update-wins map

Add ()优先于 rmv () ，更准确地说，add ()取消了以前所有的并发 rmv ()。

例如，玩家李四在一个在线游戏中在副本 a 上被删除，同时她在副本 b 上做了一些活动。很明显，rmv ()操作必须被取消。

需要注意的是， 假设我们有两个副本 a 和 b，它们以 k 为单位存储一组复制品。如果 a 删除了密钥 k，b 删除了集合中的所有元素，那么最终，两个副本的密钥 k 下都会有一个空集。

然而，有时不能取消以前所有的 rmv ()操作。考虑下面的例子，如果用这种方法，同步状态将与初始状态相同，这是一个不正确的结果。

4.6 CRDT之List

这种类型的问题在于，在本地更新操作之后，不同的副本上的元素索引将会不同。为了解决这个问题，可以使用操作转换索引的方法，在应用接收到的更新操作时，必须考虑原始索引。

5 构建基于CRDT的应用

将应用程序连接到基于CRDT的数据库与将应用程序连接到任何其他数据库没有什么不同。然而，由于最终一致性的策略，应用程序需要遵循一定的规则来提供一致的用户体验，其中的三个关键点是:

1. 应用程序无状态

无状态应用程序通常是 api 驱动的。对 API 的每次调用都会导致从头重新构建完整的消息。这可以确保在任何时候获得一个干净的数据副本。基于CRDT的数据库提供的低本地延迟使得重构消息更快更容易 。

2. 选择适合场景的正确 CRDT

计数器是 crt 中最简单的。它可以应用于诸如全局投票、跟踪活动会话、计量等用例。但是，如果要合并分布式对象的状态，那么还必须考虑其他数据结构。例如，对于允许用户编辑共享文档的应用程序，您可能不仅希望保留编辑，还希望保留执行编辑的顺序。在这种情况下，将编辑保存在基于 crdt 的列表或队列数据结构中将是比将编辑保存在寄存器中更好的解决方案。了解由 crt 强制执行的冲突解决语义，以及您的解决方案符合规则也很重要

3. CRDT 不是一个万能的解决方案 !

为了实现更快的上线应用，建议拥有一致的开发、测试、阶段化和生产设置。除此之外，这意味着开发和测试设置必须有一个小型化的模型。检查基于CRDT的数据库是可用的 Docker 容器还是可用的虚拟设备。将数据库副本部署到不同的子网上，这样就可以模拟已连接和断开连接的集群设置。

使用分布式多leader数据库测试应用程序可能听起来很复杂。但是在大多数情况下，需要测试的是数据一致性和应用程序可用性，这两种情况分别是: 连接分布式数据库时，以及数据库之间存在网络划分时。

通常，可以在开发环境中设置一个三节点的测试用分布式数据库，就可以覆盖单元测试中的大多数测试场景。以下是测试应用的基本准则:

（1）网络连接和节点间延迟低的测试用例

测试用例必须更加强调模拟冲突。通常，可以通过多次跨不同节点更新相同的数据来实现这一点，在所有节点上合并暂停并验证数据的步骤。即使数据库副本是连续同步的，测试最终一致性数据库也需要暂停测试并检查数据。

对于验证，要验证两件事: 所有数据库副本具有相同的数据，以及每当发生冲突时，冲突解决将按照设计进行。

（2）分区网络的测试用例

这里，通常执行与前面相同的测试用例，但是分为两个步骤。在第一步中，使用分区网络测试应用程序，也就是说，数据库无法彼此同步的情况。当网络被拆分时，数据库不会合并所有数据。因此，测试用例必须假设只读取数据的本地副本。在第二步中，重新连接所有网络以测试合并是如何发生的。如果遵循与前一节相同的测试用例，那么最终的数据必须与前一组步骤中的数据相同。

6. CRDT的应用示例

6.1 CRDT 用例: 投票，喜欢，爱心，表情符号等的计数

计数器有许多应用程序。作为一个分布式的应用程序，它可以收集选票，衡量一篇文章中“赞”的数量，或者跟踪一条信息的表情符号反应数量。例如，每个地理位置的本地应用程序连接到最近的数据库集群，更新计数器并用本地延迟读取计数器。

可以使用 PN-Counter 的CRDT，示意代码如下：


void countVote(String pollId){
     // CRDT Command: COUNTER_INCREMENT poll:[pollId]:counter
}

long getVoteCount(String pollId){
// CRDT Command: COUNTER_GET poll:[pollId]:counter
}

6.2 CRDT 用例: 分布式缓存

分布式缓存的缓存机制与本地缓存中使用的机制相同: 应用程序尝试从缓存中获取对象。如果对象不存在，则应用程序从主存储区检索并将其保存在缓存中，并设置适当的过期时间。如果将缓存对象存储在基于CRDT的数据库中，该数据库将自动在所有区域中提供缓存。例如，将每个电影的海报缓存到本地环境。

采用register的CRDT，示意代码如下


void cacheString(String objectId, String cacheData, int ttl){
     // CRDT command: REGISTER_SET object:[objectId] [cacheData] ex [ttl]
}

String getFromCache(String objectId){
     // CRDT command: REGISTER_GET object:[objectId]
}

6.3 CRDT 用例: 使用共享会话数据进行协作

CRDT最初是为支持多用户文档编辑而开发的。共享会话用于游戏、电子商务、社交网络、聊天、协作、应急响应和许多其他应用程序。例如，一个简单的婚礼祝福应用，在这个应用中，新婚夫妇的所有祝福者都将他们的礼物添加到购物车中，该购物车作为共享会话进行管理。

婚礼祝福的应用程序是一个分布式应用，每个实例都连接到本地数据库。在开始一个会话时，应用的所有者邀请他们来自世界各地的朋友。一旦被邀请者接受邀请，他们就可以访问会话对象。然后，他们购物并将商品添加到购物车中。

2P-Set 和一个 PN-counter 用于存放购物车中的物品，另外还有一个2P-Set 用于存储活动会话，示意代码如下：

void joinSession(String sharedSessionID, sessionID){
     // CRDT command: SET_ADD sharedSession:[sharedSessionId] [sessionID]
}

void addToCart(String sharedSessionId, String productId, int count){
     // CRDT command:
     //          ZSET_ADD sharedSession:[sharedSessionId] productId count  
}

getCartItems(String sharedSessionId){
     // CRDT command:
     //          ZSET_RANGE sharedSession:sessionSessionId 0 -1
}

6.4 CRDT 应用: 多区域数据摄取

List或队列在许多应用程序中使用。例如，订单处理系统在基于 CRDT的 List 数据结构中维护活动作业。这个解决方案在不同的地点收集任务。每个位置的分布式应用程序连接到最近的数据库副本。这减少了写操作的网络延迟，从而允许应用程序支持大量作业提交。这些作业是从一个集群的 List 数据结构中弹出的。这保证了作业只被处理一次。

基于 CRDT的List，列表数据结构用作 FIFO 队列的示意代码如下：

pushJob(String jobQueueId, String job){
     // CRDT command: LIST_LEFT_PUSH job:[jobQueueId] [job]    
}

popJob(String jobQueueId){
     // CRDT command: LIST_RIGHT_POP job:[jobQueueId]
}

小结

CRDT 对于许多用例来说确实是一个很好的工具，通过在这些场景和其他场景中利用基于 crdt 的数据库，您可以专注于业务逻辑，而不用担心区域之间的数据同步。最重要的是，基于 crdt 的数据库可以提供本地的应用延迟，同时承诺即使在数据中心之间出现网络故障时也可以提供强大的最终一致性。

但是，它可能不是所有用例(例如 ACID 事务)的最佳工具。基于 CRDT的数据库通常非常适合微服务体系结构，其中每个微服务都有一个专门的数据库。当然，区块链或许是使用CRDT 的又一主要场景。

基于CRDT的一种文档冲突算法