CRDT——解决最终一致问题的利器

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
简介: ## 概述 跨数据中心的数据同步是企业提升容灾能力的必备手段,对于社交、视频直播、电商以及游戏等访问规模大、业务分布广的行业,跨区域全球部署也愈发重要。 然而面对大型分布式系统, 不免要讨论CAP理论,在跨区域多活的场景下如何取舍?显然P(网络分区)是首要考虑因素。其次,跨区域部署就是为了提高可用性,而且对于常见的一致性协议,不管是2PC、Paxos还是raft,在此场景下都要做跨区域同步更新

概述

跨数据中心的数据同步是企业提升容灾能力的必备手段,对于社交、视频直播、电商以及游戏等访问规模大、业务分布广的行业,跨区域全球部署也愈发重要。
然而面对大型分布式系统, 不免要讨论CAP理论,在跨区域多活的场景下如何取舍?显然P(网络分区)是首要考虑因素。其次,跨区域部署就是为了提高可用性,而且对于常见的一致性协议,不管是2PC、Paxos还是raft,在此场景下都要做跨区域同步更新,不仅会降低用户体验,在网络分区的时候还会影响可用性,因此C必定被排在最后。那是不是C无法被满足了呢?事实并非如此,退而求其次,最终一致也是一种选择。CRDT(Conflict-Free Replicated Data Type)1是各种基础数据结构最终一致算法的理论总结,能根据一定的规则自动合并,解决冲突,达到强最终一致的效果。2012年CAP理论提出者Eric Brewer撰文回顾CAP[3]时也提到,C和A并不是完全互斥,建议大家使用CRDT来保障一致性。自从被大神打了广告,各种分布式系统和应用均开始尝试CRDT,redislabs[4]和riak[5]已经实现多种数据结构,微软的CosmosDB[6]也在azure上使用CRDT作为多活一致性的解决方案。
阿里云redis现配套推出了全球多活产品[7],助力企业在云上部署跨区域服务,并且依据CRDT确保在全球多活的场景下,所有redis实例中数据最终一致。本篇文章我们会对CRDT进行简要介绍,下一篇文章将说明我们是如何实现CRDT的。

CRDT简介

先简单统一一下概念和名词:

  • object: 可以理解为“副本”
  • operation: 操作接口,由客户端调用,分为两种,读操作query和写操作update
  • query: 查询操作,仅查询本地副本
  • update: 更新操作,先尝试进行本地副本更新,若更新成功则将本地更新同步至远端副本
  • merge: update在远端副本的合并操作

一个数据结构符合CRDT的条件是update操作和merge操作需满足交换律、结合律和幂等律,具体证明见[1],在此不做赘述。如果update操作本身满足以上三律,merge操作仅需要对update操作进行回放即可,这种形式称为op-based CRDT,最简单的例子是集合求并集。

image.png | center | 281x339

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

image.png | center | 555x274

有两点值得注意的地方:

  • update操作无法满足三律,如果能将元信息附加在操作或者增量上,会是一个相对state-based方案更优化的选择
  • 如果同步过程能确保exactly once的语义,幂等律条件是可以被放宽掉,比如说加法本身满足交换律结合律但不幂等,如果能保证加法操作只回放一次,其结果还是最终一致的。

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

CRDTs一览

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

Counter

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

Op-based counter

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

image.png | center | 278x340

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

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])

image.png | center | 278x340

易见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操作是无法满足交换律的, 会产生冲突:

image.png | center | 278x338

所以必须附加一些额外信息,可以从一个只做添加的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中,如下:

image.png | center | 276x363

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    

image.png | center | 277x365

一个更优化的实现是不要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。

image.png | left | 827x342

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

  • 重复add和remove的场景下会产生大量的tag,空间需要优化
  • 在考虑空间优化的前提下如何生成全局唯一的tag
  • 需要考虑如何进行垃圾回收

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

附录

  1. CRDT: https://hal.inria.fr/inria-00609399/document
  2. CRDT tech report: https://hal.inria.fr/file/index/docid/555588/filename/techreport.pdf
  3. Eric Brewer: https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed
  4. redislabs, Developing Applications with Geo-replicated CRDBs on Redis Enterprise Software(RS): https://redislabs.com/redis-enterprise-documentation/developing/crdbs/
  5. riak: https://docs.basho.com/riak/kv/2.0.0/developing/data-types/
  6. cosmosDB: https://docs.microsoft.com/en-us/azure/cosmos-db/multi-region-writers
相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
目录
相关文章
|
6月前
|
编译器 API 容器
Compose:从重组谈谈页面性能优化思路,狠狠优化一笔
Compose:从重组谈谈页面性能优化思路,狠狠优化一笔
199 0
|
5月前
|
数据采集 存储 监控
构建高效爬虫系统:设计思路与案例分析
构建高效爬虫系统涉及关键模块如爬虫引擎、链接存储、内容处理器等,以及用户代理池、IP代理池等反反爬策略。评估项目复杂性考虑数据规模、网站结构、反爬虫机制等因素。案例分析展示了电子商务价格比较爬虫的设计,强调了系统模块化、错误处理和合规性的重要性。爬虫技术需要不断进化以应对复杂网络环境的挑战。
116 1
|
6月前
|
缓存 C语言 C++
【项目日记(九)】项目整体测试,优化以及缺陷分析
【项目日记(九)】项目整体测试,优化以及缺陷分析
|
消息中间件 缓存 NoSQL
程序员快来学习缓存层场景实战数据收集—技术选型思路及整体方案
根据以上业务场景,项目组提炼出了6点业务需求,并针对业务需求梳理了技术选型相关思路。 1)原始数据海量:对于这一点,初步考虑使用HBase进行持久化。 2)对于埋点记录的请求响应要快:埋点记录服务会把原始埋点记录存放在一个缓存层,以此保证响应快速。关于这一点有多个缓存方案,稍后展开讨论。 3)可通过后台查询原始数据:如果直接使用HBase作为查询引擎,查询速度太慢,所以还需要使用Elasticsearch来保存查询页面上作为查询条件的字段和活动ID。
|
存储 NoSQL 算法
线上真实排队系统重构案例分享——实战篇
线上真实排队系统重构案例分享——实战篇
527 0
|
设计模式 程序员 开发者
重构·改善既有代码的设计.01之入门基础
近期在看Martin Fowler著作的《重构.改善既有代码的设计》这本书,这是一本经典著作。书本封面誉为软件开发的不朽经典。书中从一个简单的案例揭示了重构的过程以及最佳实践。同时给出了重构原则,何时重构,以及重构的手法。用来改善既有代码的设计,提升软件的可维护性。
625 1
重构·改善既有代码的设计.01之入门基础
|
安全 数据可视化 Java
Jmix - 业务系统高效开发的少代码平台
少代码具有低代码产品的所有优点,但是又没有任何低代码产品的缺点。[Jmix.cn ](https://www.jmix.cn/)从定位、产品设计方面把低代码平台的缺陷都抹平并且提升为优点。我们称它为 “少代码”。
490 2
Jmix - 业务系统高效开发的少代码平台
“从幼稚到成熟,是从不负责任到承担责任的过程” | 技术人金句系列
技术人做事情,判断力和分寸感很重要。有时候你遇到的困难和问题,可能别人早就经历过、克服过,并沉淀了与之匹配的“判断力”和“分寸感”。 今天,我们想分享来自大淘宝技术工程师们的《人间清醒语录》,这些金句里凝结了他们多年实践经验的智慧,希望可以给你带来启发和思考。
204 0
“从幼稚到成熟,是从不负责任到承担责任的过程” | 技术人金句系列
|
测试技术
谈谈我理解的测试的核心价值
测试人员的核心价值      随着公司组织架构的调整,战略调整,产品的实现技术不断变化,现在的测试人员可以说是什么都可以干。       有些人做产品,有些人做平台,有些人做工具......     有些人有点象专职开发,有些人有点象专职运营......      Facebook,google的一些敏捷测试理念中,测试人员应该致力于提出测试解决方案,研究各种测试工具为主,具体的测试执行工作,由coding的开发同学去做。
1330 0
|
JavaScript 前端开发 定位技术
如何做产物优化(下)
如何做产物优化(下)
273 0
如何做产物优化(下)