redis异地多活理论基础之CRDT
随着服务规模的扩大, 为了提升系统的容灾能力以及性能的要求, 会将服务部署在多个地域, 如果服务是有状态的, 比如redis/mysql等, 就需要在多地域之间进行数据同步, 如何保证数据一致性, 就成为了实现"多活"的关键. 以redis为例, 业内已经有redislab和阿里云实现了多活, 并且都是使用的一种叫CRDT的解决方案, 所以, 本文以CRDT的论文为基础, 介绍一下CRDT的理解, 有问题欢迎指正.
-
CRDT: 无冲突复制数据类型
-
解决多主架构中, 数据复制时的最终一致性问题
-
使用这类数据结构, 需要满足以下三个条件(比如: INCR命令满足交换律, 结合律, 但是不满足幂等)
-
交换律: x⊔y=y⊔x
-
幂等律: x⊔x=x
-
结合律: (x⊔y)⊔z=x⊔(y⊔z)
-
-
-
分类
-
基于操作的(CmRT), 比如incr decr等
-
基于状态的(CvRT), 就是传输的是最终值, 比如restore
-
-
数据类型
-
Op-based counter
- 解释: 基于操作实现, 每个下游需要同步相同的操作, 查询时直接查询本地即可
- 说明: 适合类似INCR/DECR等命令, 但是需要确保幂等性
-
G-Counter
-
-
解释: 基于状态进行复制, 合并的时候: 取两个时间点中值更大的, 查询的时候: 取各地域求和的值
-
说明: 只能增加, 因为如果有删除操作, 在max的运算下, 会被认为数据是老数据而丢弃
-
-
PN-Counter
-
-
解释: 基于状态进行复制, 聚合时取两个时间点中最大的, 查询的时候: 取各地域求INCR和的值 - 各地域求DECR和的值
-
说明: 支持增加和减少, 而且由于是基于状态的, 幂等性也有保证
-
-
Non-negative Counter
- 解释: 非负数的counter, 很遗憾, 没有给出实现
-
LWW-Register
-
-
-
解释: 基于状态进行复制, 每个元素在生成时同时添加一个时间戳, 之后按取时间戳大的为标准进行聚合, 查询时取当前本地域的值
-
说明: 有两点限制, 一个是需要保障时间戳全局唯一,有序,一致, 另外需要保证状态不太大, 否则网络传输成本较高
-
-
解释: 基于操作进行复制, 每个地域执行update的时候, 会记录时间戳, 之后同步给其他地域, 其他地域判断时间戳是否大于本地的, 如果是的话, 就进行更新
-
说明: 可以用于SET,HSET这类幂等类型的操作, 同时需要保证时间戳的全局一致
-
-
MV-Register
-
-
解释: 基于状态的, 带版本的更新, 元素变更, 就增加版本号, 实际的合并交给业务完成
-
-
G-SET
-
- 解释: 一种只增加元素的set集合
- 点评: 只支持增加
-
-
2P-SET
-
- 解释: 基于状态, 由一个增加元素的set和一个删除元素的set组成, 查询时, 通过判断e是否属于A同时也不属于R来确认
- 说明: 删除的数据, 后续无法再次添加
-
-
U-SET
- 解释: 基于操作的, 元素唯一的set类型, 如果保证add一定会在remove之前触发, 这样remove-set就可以不用了
- 说明: 元素必须唯一, 和基于状态的2P-SET类似, 但是更加严格
-
LWW-Element-Set
-
-
解释: 一个元素会认为存在, 如果它在add set, 但是不在remove set, 或者它在add set的时间戳大于remove set中所有的时间戳
- 说明: 相比2P-SET的好处是可以添加已经删除的元素, 但是问题在于如何保证时间戳的全局有序性
-
-
PN-Set(PositiveNegative-Set)
-
- 解释: 在Set中使用一个计数器, 每次添加就计数加1, 删除就计数减1, 如果计数大于0, 说明数据存在
- 说明: 这个的问题是如果删除了多次, add可能失效
-
-
OR-Set (Observed-Remove Set)
-
-
-
解释: 基于操作, 2P-Set的变种, 把唯一性做到Set里了, 每次add 元素产生一个唯一tag, 每个地域rmv的时候, 只rmv本地所有的与元素相关的tag集合, 传播时会带上元素及对应tag, 下游接收到之后, 需要确认每个remove(e, u) 都已经add过了.
-
说明: 元素带上唯一tag, 这样数据是不冲突了, 但是会导致和实际的操作不符合, 如图中所示, 期望应该是a查询不到的.
-
-
-
其他说明:
-
由于文中有说到很多数据类型都依赖全局的时间戳, 感兴趣的可以了解一下谷歌的原子钟
-
-
参考文档:
- CRDT tech report: https://hal.inria.fr/file/index/docid/555588/filename/techreport.pdf
- CRDT: https://hal.inria.fr/inria-00609399/document
- redislabs, Developing Applications with Geo-replicated CRDBs on Redis Enterprise Software(RS): https://redislabs.com/redis-enterprise-documentation/developing/crdbs/
- CRDT——解决最终一致问题的利器: https://yq.aliyun.com/articles/635632?utm_content=m_1000015503
- 谷歌利用GPS和原子钟使数据库全球范围信息同步: https://m.ithome.com/html/25938.htm

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
nginx-rtmp-module的缺陷分析
Arut最初在开发nginx-rtmp-module的时候只实现了单进程模式,好处是架构简单,推送和播放,数据统计,流媒体控制等都在一个进程上完成。但是这显然浪费了Nginx多进程(在Linux和FreeBSD平台上每个进程都可以绑定一个CPU核心,以减少进程切换带来的开销)的处理能力。但是,如果开启多进程模式,推送和播放如果不在同一个进程上,会造成播放失败的问题: 另外,请求数据统计信息也是个问题,因为采取HTTP方式请求数据统计信息时,在多进程模式下,请求被Nginx随机分配给了worker进程,可能造成我想看worker 1上的数据统计信息,但是Nginx返回的是worker 3上的数据统计信息。流媒体控制也采取了HTTP请求的方式,所以也存在着同样的问题: 针对推送和播放不在同一个进程上的问题,Arut后来加入了auto push的功能,即把原始的推流数据再relay到其他进程上去。这个功能需要Unix domain socket的支持(所以类Unix系统都支持,Windows在Windows 10的某个版本后才开始支持): 这样处理后,不管播放请求落在哪个进程上,都能获得推送...
- 下一篇
JavaScript"模拟事件"的注意要点
今天小编就为大家分享一篇关于JavaScript"模拟事件"的注意要点详解,写的十分的全面细致,具有一定的参考价值,对此有需要的朋友可以参考学习下。如有不足之处,欢迎批评指正。 DOM中的事件模拟 三个步骤: 首先通过document.createEvent()方法创建event对象,接收一个参数,即表示要创建的事件类型的字符串: UIEvents(DOM3中的UIEvent)鼠标和键盘事件; MouseEvents(DOM3中的MouseEvent)鼠标事件; MutationEvents(DOM3中的MutationEvent)变动事件; HTMLEvents(没有DOM3中对应的事件)HTML事件; 其次在创建了event对象之后,还需要使用与事件有关的信息对其进行初始化。每种类型的event对象都有一个特殊的方法,为它传入适当的数据就可以初始化该event对象。用event.init......()此类行的方法。 最后就是触发事件。这需要使用dispatchEvent()方法,接收一个参数,即表示要触发的event对象。 模拟鼠标事件 首先创建鼠标事件对象的方法createEv...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- CentOS7安装Docker,走上虚拟化容器引擎之路
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- Red5直播服务器,属于Java语言的直播服务器
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- 2048小游戏-低调大师作品
- CentOS6,7,8上安装Nginx,支持https2.0的开启