大数据生态圈里的一致性算法

发表于 2016-10-11 更新于 2023-12-30 分类于大数据阅读次数：本文字数： 1.4k 阅读时长 ≈ 1 分钟

大数据生态圈中，保证一致性的方式举不胜举

Hadoop 用 ZooKeeper（Zab，即支持事务顺序的 Paxos）
Elasticsearch 用 Hash 路由算法（而非一致性 Hash）
Cassandra 用 Gossip 闲话算法
Redis 用 Raft 选举算法

他们各有什么区别，为什么会如此选型？

Paxos 选举算法

　Paxos 是最先解决拜占庭将军问题的算法，利用过半选举的机制，保证了集群数据副本的一致性（微服务中服务注册与发现的场景，其实已经不再适用了）

Raft 选举算法

　Redis 使用 Raft 实现了自己的分布式一致性。Raft 本身和 Paxos 并没有场景上的区别。更多的是，协议上的简化、Term 概念的强化、Log 只会从 Leader 到 Follower 单向同步，使得实现起来会很方便

Zab 原子广播协议

　Hadoop 偏向于离线的海量数据处理，利用 ZooKeeper 来保证数据副本的一致性，是最为合适的

Hash 路由算法

　Elasticsearch 集群接收到为文档创建索引的请求时，需要选择在哪一个 shard（完整且独立的 Lucene 索引实例）上对文档进行索引。Elasticsearch 采用的是 djb2 哈希算法（俗称 times33），对要索引文档默认或指定的 key 进行哈希 hash(key)，然后再对 Elasticsearch 集群中 shard 的数量 n 进行取模，即 $hash(key) \, mod \, n$

一致性 Hash

　用于对数据存储进行负载均衡的算法。最新的进展，是在去年 Google 发表的一篇有界负载的一致性 Hash 算法的论文。该算法保证了负载均衡一致性和稳定性的同时，在均匀性方面做出了实质性地改进。同时，Consistent Hashing with Bounded Loads 算法也在 HaProxy 开源项目中得以应用，有效减少了其 8 倍的缓存带宽