一、试题背景与考察重点

东北大学2009年春季博士入学考试中，分布式数据库作为计算机科学与技术领域的重要方向，成为考察考生理论深度与实践能力的关键科目。分布式数据库系统通过将数据分散存储于多个节点，实现高可用性、可扩展性与容错性，是现代大规模数据处理的核心技术之一。本试题旨在考察考生对分布式数据库基本原理、设计方法及关键技术的掌握程度，具体涵盖数据分片、事务处理、并发控制、故障恢复等核心模块。

二、试题核心内容解析

（一）分布式数据库基本概念

1. 定义与特征
分布式数据库（Distributed Database, DDB）是物理上分散、逻辑上统一的数据库系统，其核心特征包括：

• 数据分布性：数据存储于多个物理节点，节点间通过网络通信。
• 逻辑统一性：用户视角下，系统表现为单一数据库，支持全局查询与事务。
• 自治性与协作性：节点具有局部自治能力，同时需协调全局操作。

2. 优势与挑战

• 优势：提高系统可用性（单节点故障不影响全局）、扩展性（通过增加节点提升性能）、就近访问（减少网络延迟）。
• 挑战：数据一致性维护、分布式事务处理复杂度、网络通信开销。

（二）数据分片与分配策略

1. 数据分片方法

• 水平分片：按行划分数据，例如将用户表按地域分片（如东北、华北）。
• 垂直分片：按列划分数据，例如将用户信息表拆分为基本信息分片和订单信息分片。
• 混合分片：结合水平与垂直分片，适用于复杂场景。

2. 分配策略

• 轮转分配：循环将分片分配至节点，适用于负载均衡场景。
• 哈希分配：通过哈希函数确定分片位置，例如node_id = hash(key) % N，可减少热点问题。
• 范围分配：按数据范围分配，如按时间范围分片日志数据。

示例：
假设某电商系统需按用户ID分片，可采用哈希分配：

def get_node(user_id, num_nodes):
    return hash(str(user_id)) % num_nodes

（三）分布式事务处理

1. 事务ACID特性

• 原子性（Atomicity）：事务操作全部成功或全部回滚。
• 一致性（Consistency）：事务执行前后数据状态一致。
• 隔离性（Isolation）：并发事务互不干扰。
• 持久性（Durability）：事务提交后结果永久保存。

2. 两阶段提交协议（2PC）

• 阶段1（准备阶段）：协调者向所有参与者发送准备请求，参与者锁定资源并返回“就绪”或“中止”。
• 阶段2（提交阶段）：若所有参与者就绪，协调者发送提交命令；否则发送回滚命令。
• 缺点：单点故障（协调者崩溃）、阻塞问题（参与者等待超时）。

3. 三阶段提交协议（3PC）
通过增加“预提交”阶段，减少阻塞风险，但无法完全解决单点问题。

（四）并发控制机制

1. 封锁协议

• 共享锁（S锁）：允许读操作，阻塞写操作。
• 排他锁（X锁）：阻塞读写操作。
• 两阶段锁（2PL）：事务分为增长阶段（获取锁）与收缩阶段（释放锁），可能引发死锁。

2. 时间戳排序
为每个事务分配时间戳，按时间顺序执行，避免死锁但可能引发饥饿。

3. 多版本并发控制（MVCC）
通过维护数据多个版本，允许读写操作并行，例如PostgreSQL的实现。

（五）分布式查询优化

1. 查询代价模型
优化目标为最小化总代价，包括I/O代价、CPU代价及网络通信代价。

2. 半连接优化
通过半连接操作减少数据传输量，例如：

-- 全连接
SELECT * FROM R JOIN S ON R.a = S.a;
-- 半连接优化
SELECT * FROM R WHERE a IN (SELECT a FROM S);

3. 并行查询执行
将查询分解为子任务，并行执行于不同节点，例如MapReduce框架。

（六）故障恢复与容错

1. 日志恢复
通过预写日志（WAL）确保事务持久性，例如：

• UNDO日志：回滚未提交事务。
• REDO日志：重做已提交事务。

2. 复制与一致性

• 主从复制：主节点处理写操作，从节点同步数据。
• 多主复制：多个节点可处理写操作，需解决冲突（如最后写入优先）。

3. 拜占庭容错
在存在恶意节点的场景下，通过PBFT等协议保证一致性，但开销较大。

三、备考建议与拓展思考

1. 理论深化：重点掌握CAP理论（一致性、可用性、分区容忍性）及其在分布式系统中的权衡。
2. 实践结合：通过模拟实验（如使用MySQL Cluster或Cassandra）验证理论，例如设计分片策略并测试性能。
3. 前沿跟踪：关注分布式数据库新趋势，如NewSQL（如Google Spanner）、边缘计算中的分布式数据管理。

东北大学2009年春季博士入学试题中分布式数据库部分，不仅考察基础理论，更强调对系统设计复杂性的理解。考生需通过案例分析、算法推导及实验验证，构建完整的知识体系，为后续研究奠定坚实基础。