分布式理论

CAP 理论，为什么不能同时满⾜

CAP 理论是分布式系统设计中的三个基本属性，它们分别是⼀致性（Consistency）、可⽤性（Availability）、和 分区容错性（Partition Tolerance）。CAP 理论由计算机科学家 Eric Brewer 在2000年提出。

  • 一致性：一致性要求所有节点数据要一致。如果一个节点上修改了数据，那么其他节点也应该立即看到修改变更
  • 可用性：可用性要求系统能对用户的请求作出响应，即便出现节点故障的情况下仍然保持可用。
  • 分区容错性：系统面对网络分区的情况下仍然能工作，即节点之间出现网络故障无法通信时，仍然要保持一致性和可用性
  1. 一致性和分区容错性（牺牲可用性）CP: 分布式数据库\金融系统: 例如银行账户系统，需要确保每次交易都是一致的，即所有用户看到的账户余额必须是最新的。这种系统在网络分区时可能会选择暂时停止交易操作，以保持一致性。
  2. 可用性和分区容错性（牺牲一致性）AP: 社交网络和网络购物：例如微博或Facebook等社交媒体应用，需要确保用户始终能够发布帖子或查看内容，即使在网络分区的情况下。数据一致性可以在后台通过异步同步的方式来解决。 电商平台需要确保用户能够浏览商品和进行购买，即使在部分服务器不可用时。数据一致性的问题可以通过后台的补偿机制来处理。
  3. 一致性和可用性（牺牲分区容错性）CA: 内部企业系统和单节点数据库 （系统不具备分区容错性，网络或节点出现故障可能导致系统不可用。）

BASE 理论

BASE 理论，它是 CAP 理论的延伸。BASE 是 Basically Available（基本可用）、Soft State（软状态）和 Eventually Consistent（最终一致性）三个单词的简写，作用是保证系统的可用性，然后通过最终一致性来代替强一致性，它是目前分布式系统设计中最具指导意义的经验总结。

在做分库分表时，基于 Hash 取模和一致性 Hash 的数据分片是如何实现的？

基于 Hash 取模的数据分片

  1. 选择分片键。例如：用户ID，订单ID
  2. 计数分片键hash值。常用哈希算法MD5,SHA-1
  3. 取模运算。将 Hash 值对数据库或表的数量进行取模运算，结果即为数据存储的目标库或表的索引

一致性 Hash 的数据分片

  1. 构建一致性hash环。将整个hash空间构建成一个0-2的32次方-1大小的环。将数据库、表映射到环上的虚拟节点
  2. 计算分片的键hash值。对分片键hash计算，得到其在环上的位置
  3. 寻找最近的节点。从计算的分片hash值位置开始，沿顺时针方向查找最近的虚拟节点，该节点对应的数据存储库/表
  4. 数据存储 优点：当节点增加/减少是，仅需要重分布少量的数据。数据分布相对均匀，避免数据倾斜问题。 缺点：实现起来复杂。虚拟节点管理，数据迁移，平衡性等。

强一致性算法和最终一致性算法（共识算法）

强一致性保证了在任何时候，所有节点都能看到数据的最新状态。也就是说，写入操作成功后，任何读取操作都能返回最新的数据。这种一致性通常通过以下数据共识算法实现：

  1. Paxos：Paxos 是一种经典的分布式共识算法，它通过一系列的消息传递步骤来保证强一致性。在 Paxos 中，存在三个角色：提议者（Proposer）、接受者（Acceptor）和学习者（Learner）。提议者提出值，接受者决定是否接受值，学习者得到最终的决定值。Paxos 保证在大多数接受者同意的情况下，提议的值会被确定，从而保证强一致性。
  2. Raft：Raft 是一种更易理解的共识算法，也是 Paxos 的替代品。它通过选举一个领导者来简化共识过程。所有写操作都通过领导者处理，领导者将更改复制到其他节点上，并等待大多数节点确认。这种机制确保了系统中的每个节点都达成一致，从而实现强一致性。
  3. Zookeeper’s ZAB (Zookeeper Atomic Broadcast)：ZAB 是 Zookeeper 分布式协调服务使用的共识协议，它类似于 Paxos 和 Raft。ZAB 保证在领导者发生变更时，仍然能够保持数据的一致性和顺序性，从而提供强一致性。

最终一致性允许系统中的所有节点在没有立即同步的情况下，最终达到一致的状态。虽然在短时间内不同节点可能看到不同的数据，但随着时间的推移，所有节点都会收敛到一致的状态。这通常通过以下策略实现：

  1. Gossip Protocol：Gossip 协议是一种去中心化的传播方式，每个节点会周期性地与其他节点交换信息，从而逐渐将数据传播到整个系统中。随着时间的推移，所有节点最终会达到一致的状态。Cassandra 和 DynamoDB 等系统采用了这种协议来实现最终一致性。
  2. Vector Clocks：矢量时钟用于跟踪系统中不同节点的操作顺序，并帮助检测冲突。矢量时钟记录每个节点上数据的版本号，并在读取时将这些版本返回给客户端。如果存在冲突，系统可以通过应用某种冲突解决策略来实现一致性。
  3. Anti-Entropy Mechanisms：反熵机制通过定期同步数据来修复分布式系统中的数据不一致性。例如，节点之间可以定期交换哈希值来检测不一致，并修复差异。