Chandy-Lamport 算法

Chandy-Lamport algorithm 是一种分布式快照算法,其名称以两个作者(K. Mani Chandy & Leslie Lamport)的名字命名。Chandy-Lamport 算法可以在没有全局时钟的情况下,记录异步分布式系统的一致性全局状态。Chandy-Lamport 算法对于解决分布式系统的一些问题如:分布式系统的死锁检测,分布式系统的终止检测等具有重要意义,也可以用于分布式系统的 checkpointing。并且 Chandy-Lamport 算法的执行可以和分布式系统的计算同时进行,不会影响和更改底层的运算状态。

阅读更多

Elasticsearch 新版选主流程

在 Elasticsearch 7.0 版本中,Elasticsearch 采用了一个新的集群协调模块(Coordinator)代替了旧版 Zen Discovery,对选主算法 Bully 也进行了更换。根据 ES 的说明,新协调模块提供了如下优势:1、免去了 Zen Discovery 的 discovery.zen.minimum_master_nodes 配置,es 会自己选择可以形成仲裁的节点,用户只需配置一个初始 master 节点列表即可。也即集群扩容或缩容的过程中,不要再担心遗漏或配错 discovery.zen.minimum_master_nodes 配置了;2、新版 Leader 选举速度极大快于旧版。在旧版 Zen Discovery 中,每个节点都需要先通过 3 轮的 ZenPing 才能完成节点发现和 Leader 选举,而新版的算法通常只需要在 100ms 以内;3、修复了 Zen Discovery 下的疑难问题,如“重复的网络分区可能导致群集状态更新丢失”问题。目前业界的分布式一致性算法的理论和工程实现都已经很成熟,出于 es 新旧版本之间平稳升级以及 es 实际应用中一些情况考虑,es 官方并没有直接采用现成开源的第三方一致性算法库,而是结合 es 实际情况自己进行了开发,但其实现的思想还是参考了 Raft 一致性算法,和其基本类似。比如角色一样分为 Leader、Candidate、Follower;将时间划分为一个个任意长度的 term(以连续整数编号)每个 term 起始于leader 选举,可以用于过期信息检测;选举 Leader 时为保证可进展性,各节点采用了随机超时启动选举等。es 社区对新协调模块实现的记录可以见 issue-32006(https://github.com/elastic/elasticsearch/issues/32006),下面对新版的 es 选主流程源码做一下分析。

阅读更多

Elasticsearch 选主流程

Elasticsearch 使用了一个类似 Bully 的算法进行 Leader 选举。Bully 算法在使用上有一些预设条件,比如系统需要是同步的(the system is synchronous)、有节点/进程故障监测机制(there is a failure detector which detects failed processes)、每个节点/进程都知晓自身及其他所有节点/进程的 id 和通信地址(each process knows its own process id and address, and that of every other process)等。Bully 算法总是选出进程中 id 最大的作为 Leader,其逻辑相较于其他分布式一致性算法而言较为简单。Elasticsearch 中,Discovery 模块用于节点发现和 Leader 选举,其默认内置的 ZenDiscovery 实现了 Bully 相关的内容。在具体实现上,又分为节点发现、选举 Leader、发布状态、失效监测等几个部分,下面按 es 启动时的实际执行流程介绍一下各部分内容。

阅读更多

Elasticsearch Clients 内部机制

本文试图通过源码分析阐释 Elasticsearch Clients 如下内部机制问题:

  • es 集群服务端异常,将如何影响客户端的请求?es 客户端能否自动重试?
  • es 客户端对多地址如何管理,新增地址或删除地址如何感知?
  • es 客户端负载均衡采用的是何种策略?
  • 对于 es 集群某个节点的掉线,es 客户端发送请求时如何感知,由会采用何种解决策略?
  • es 客户端请求是否用的是长连接,能否继续提升性能?
  • es sniff 机制作用?

阅读更多

PacificA 论文阅读笔记

PacificA,一个基于日志的分布式存储系统原型。PacificA 论文对其简单、实用且强一致性等特性做了详细介绍,为其他基于日志的分布式副本复制系统开发提供了良好的经验和建议。

阅读更多