编辑“︁分布式系统理论”︁

= 分布式系统理论 =

分布式系统理论是计算机科学中研究多台计算机协同工作以完成共同任务的基础框架。本专题将系统性地介绍核心概念、设计原则及实际应用场景。

== 基本定义 ==
'''分布式系统'''由一组通过网络连接的独立计算机节点组成，这些节点通过消息传递进行通信和协调，对外表现为一个统一的计算资源。其核心特征包括：
* '''并发性'''：多个节点并行执行任务
* '''缺乏全局时钟'''：节点间的时间同步存在挑战
* '''独立故障'''：单个节点故障不影响整体系统
* '''消息传递延迟'''：网络通信存在不可预测的延迟

数学表示为：<math>DS = \{N_1, N_2, ..., N_n\} \times \{C_{ij}\}</math>，其中<math>N_i</math>表示节点，<math>C_{ij}</math>表示通信通道。

== 核心理论 ==

=== CAP定理 ===
分布式系统最多只能同时满足以下三个特性中的两个：
* '''一致性'''（Consistency）：所有节点看到相同数据
* '''可用性'''（Availability）：每个请求都能获得响应
* '''分区容错性'''（Partition tolerance）：网络分区时系统仍能运行

<mermaid>
pie title CAP特性选择
    "AP系统" : 45
    "CP系统" : 35
    "CA系统" : 20
</mermaid>

=== BASE理论 ===
作为ACID特性的补充，包含：
* '''基本可用'''（Basically Available）
* '''软状态'''（Soft state）
* '''最终一致性'''（Eventually consistent）

=== FLP不可能定理 ===
在异步网络模型中，即使只有一个节点可能故障，也不存在总能达成共识的确定性算法。

== 共识算法 ==

=== Paxos算法 ===
经典分布式共识算法示例（Python伪代码）：

<syntaxhighlight lang="python">
class Acceptor:
    def __init__(self):
        self.promised_id = 0
        self.accepted_value = None

    def prepare(self, proposal_id):
        if proposal_id > self.promised_id:
            self.promised_id = proposal_id
            return (True, self.accepted_value)
        return (False, None)

    def accept(self, proposal_id, value):
        if proposal_id >= self.promised_id:
            self.promised_id = proposal_id
            self.accepted_value = value
            return True
        return False
</syntaxhighlight>

输入输出示例：
1. 提案者发送prepare(5)
   → 返回(True, None)
2. 提案者发送accept(5, "X")
   → 返回True
3. 新提案者发送prepare(4)
   → 返回(False, None)

=== Raft算法 ===
通过选举leader节点简化共识过程，包含：
* Leader选举
* 日志复制
* 安全性约束

<mermaid>
stateDiagram-v2
    [*] --> Follower
    Follower --> Candidate: 选举超时
    Candidate --> Leader: 获得多数票
    Leader --> Follower: 发现更高任期
</mermaid>

== 实际应用案例 ==

=== 分布式数据库 ===
'''Cassandra'''采用最终一致性模型，配置策略示例：
<syntaxhighlight lang="sql">
CREATE KEYSPACE ecommerce 
WITH replication = {
  'class': 'NetworkTopologyStrategy',
  'DC1': 3,  // 数据中心1部署3个副本
  'DC2': 2   // 数据中心2部署2个副本
};
</syntaxhighlight>

=== 微服务架构 ===
服务发现模式的工作流程：
1. 服务启动时向注册中心注册
2. 客户端通过注册中心获取服务实例列表
3. 采用负载均衡策略调用服务

== 挑战与解决方案 ==

{| class="wikitable"
|+ 常见问题及应对策略
! 问题类型 !! 典型表现 !! 解决方案

| 网络分区 || 节点间通信中断 || 设置超时机制、断路器模式

| 时钟漂移 || 事件顺序混乱 || 使用逻辑时钟（Lamport时间戳）

| 脑裂问题 || 多个主节点并存 || 法定人数投票、fencing机制
|}

=== 向量时钟示例 ===
解决事件排序问题的数据结构：
<math>
VC_i = [c_1, c_2, ..., c_n] \quad \text{其中} \quad c_j \text{表示节点j已知的事件计数}
</math>

比较规则：
* <math>VC_a > VC_b</math> 当且仅当 <math>\forall i, VC_a[i] \geq VC_b[i]</math>
* 否则事件为并发关系

== 进阶话题 ==
* 拜占庭容错系统
* 分布式事务的Saga模式
* 一致性哈希算法
* 分布式锁的实现方式（Redlock等）

本内容持续更新，建议读者通过实际搭建简单的分布式系统（如使用Docker Swarm或Kubernetes）来加深理解。

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:分布式系统]]