redis异地多活理论基础之CRDT-低调大师

redis异地多活理论基础之CRDT

2019-04-16 1387

随着服务规模的扩大, 为了提升系统的容灾能力以及性能的要求, 会将服务部署在多个地域, 如果服务是有状态的, 比如redis/mysql等, 就需要在多地域之间进行数据同步, 如何保证数据一致性, 就成为了实现"多活"的关键. 以redis为例, 业内已经有redislab和阿里云实现了多活, 并且都是使用的一种叫CRDT的解决方案, 所以, 本文以CRDT的论文为基础, 介绍一下CRDT的理解, 有问题欢迎指正.

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

微信关注我们

原文链接：https://my.oschina.net/watliu/blog/3037744

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道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的某个版本后才开始支持）：这样处理后，不管播放请求落在哪个进程上，都能获得推送...

2019-04-16

1216

今天小编就为大家分享一篇关于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...

2019-04-16

619

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。