分布式存储

1. 分布式存储基础

1.1 数据分片（Sharding）

哈希分片

• 对 key 计算哈希值，取模得到分片

• 优点：分布均匀

• 缺点：扩缩容需要数据迁移

/**
 * 简单哈希分片
 */
public class HashSharding {
    private int shardCount;

    public HashSharding(int shardCount) {
        this.shardCount = shardCount;
    }

    public int getShard(String key) {
        int hash = key.hashCode();
        // 处理负数哈希值
        return Math.abs(hash % shardCount);
    }
}

// 问题：扩容时几乎所有数据需要迁移
// 3 节点 -> 4 节点：约 75% 数据需要迁移

范围分片

• 按 key 的范围分片

• 优点：支持范围查询

• 缺点：可能数据倾斜

范围分片示例：

分片1: [A-F]  -> 用户 A-F
分片2: [G-L]  -> 用户 G-L
分片3: [M-R]  -> 用户 M-R
分片4: [S-Z]  -> 用户 S-Z

问题：如果姓 Wang 的用户特别多，分片4 会成为热点

1.2 一致性哈希详解 ⭐⭐⭐⭐⭐

基本原理

传统哈希：hash(key) % N
问题：N 变化时，几乎所有 key 的映射都会改变

一致性哈希：
1. 将哈希空间组织成环形（0 ~ 2^32-1）
2. 节点和数据都映射到环上
3. 数据存储在顺时针方向第一个遇到的节点

优势：
- 增减节点只影响相邻节点
- 平均只需迁移 K/N 的数据（K=数据量，N=节点数）

一致性哈希实现

/**
 * 一致性哈希实现
 */
public class ConsistentHash<T> {
    // 哈希环，使用 TreeMap 实现有序映射
    private final TreeMap<Long, T> ring = new TreeMap<>();
    // 每个物理节点的虚拟节点数
    private final int virtualNodes;
    // 哈希函数
    private final HashFunction hashFunction;

    public ConsistentHash(int virtualNodes) {
        this.virtualNodes = virtualNodes;
        this.hashFunction = Hashing.murmur3_128();
    }

    /**
     * 添加节点
     */
    public void addNode(T node) {
        for (int i = 0; i < virtualNodes; i++) {
            // 为每个虚拟节点计算哈希值
            long hash = hash(node.toString() + "#" + i);
            ring.put(hash, node);
        }
    }

    /**
     * 移除节点
     */
    public void removeNode(T node) {
        for (int i = 0; i < virtualNodes; i++) {
            long hash = hash(node.toString() + "#" + i);
            ring.remove(hash);
        }
    }

    /**
     * 获取 key 对应的节点
     */
    public T getNode(String key) {
        if (ring.isEmpty()) {
            return null;
        }

        long hash = hash(key);
        // 找到第一个大于等于 hash 的节点
        Map.Entry<Long, T> entry = ring.ceilingEntry(hash);
        if (entry == null) {
            // 环形：回到第一个节点
            entry = ring.firstEntry();
        }
        return entry.getValue();
    }

    /**
     * 获取 key 对应的多个副本节点
     */
    public List<T> getNodes(String key, int replicaCount) {
        if (ring.isEmpty()) {
            return Collections.emptyList();
        }

        List<T> nodes = new ArrayList<>();
        Set<T> seen = new HashSet<>();
        long hash = hash(key);

        // 从 key 的位置开始顺时针查找
        SortedMap<Long, T> tailMap = ring.tailMap(hash);
        Iterator<T> iterator = Iterators.concat(
            tailMap.values().iterator(),
            ring.values().iterator()
        );

        while (nodes.size() < replicaCount && iterator.hasNext()) {
            T node = iterator.next();
            // 跳过同一物理节点的虚拟节点
            if (!seen.contains(node)) {
                seen.add(node);
                nodes.add(node);
            }
        }

        return nodes;
    }

    private long hash(String key) {
        return hashFunction.hashString(key, StandardCharsets.UTF_8).asLong();
    }
}

虚拟节点

为什么需要虚拟节点？

问题：节点少时，数据分布不均匀
      Node1         Node2         Node3
        │             │             │
   ─────┼─────────────┼─────────────┼─────
        ↑             ↑             ↑
      分布不均匀，Node2 负责的范围过大

解决：每个物理节点映射多个虚拟节点
      V1-1  V2-1  V1-2  V3-1  V2-2  V3-2  V1-3  V2-3  V3-3
        │     │     │     │     │     │     │     │     │
   ─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────
        ↑     ↑     ↑     ↑     ↑     ↑     ↑     ↑     ↑
      虚拟节点分散，数据分布更均匀

虚拟节点数量建议：
- 100-200 个虚拟节点可以使数据分布较均匀
- 太多会增加内存开销

带权重的一致性哈希

/**
 * 带权重的一致性哈希
 * 权重大的节点分配更多虚拟节点
 */
public class WeightedConsistentHash<T> {
    private final TreeMap<Long, T> ring = new TreeMap<>();
    private final int baseVirtualNodes;

    public void addNode(T node, int weight) {
        // 权重决定虚拟节点数量
        int virtualNodes = baseVirtualNodes * weight;
        for (int i = 0; i < virtualNodes; i++) {
            long hash = hash(node.toString() + "#" + i);
            ring.put(hash, node);
        }
    }
}

// 应用场景：
// - 不同配置的服务器（内存大的权重高）
// - 跨机房部署（本机房权重高）

1.3 数据副本

副本策略

副本放置策略（以 Cassandra 为例）：

1. SimpleStrategy
   - 顺时针放置副本
   - 适用于单数据中心

2. NetworkTopologyStrategy
   - 跨机架、跨数据中心放置
   - 每个数据中心可配置不同副本数

副本数量选择：
- 3 副本：常见配置，容忍 1 节点故障
- 5 副本：高可用要求，容忍 2 节点故障

副本一致性

模式	特点	应用
主从复制	写主节点，读从节点	MySQL, Redis
多主复制	多个节点可写	Cassandra
无主复制	Quorum 机制	DynamoDB

1.4 Quorum 机制 ⭐⭐⭐⭐

Quorum 参数：
- N：副本数
- W：写成功需要的确认数
- R：读需要的副本数

一致性保证：
- 强一致性：W + R > N
- 最终一致性：W + R <= N

常见配置：
N=3, W=2, R=2：强一致性，写入需要 2 节点确认
N=3, W=1, R=1：最终一致性，高可用低延迟
N=3, W=3, R=1：写入强一致，读取快速

示例：N=3, W=2, R=2
写入：
  Client -> Node1, Node2, Node3
  Node1: ACK
  Node2: ACK (W=2 满足，返回成功)
  Node3: 后续同步

读取：
  Client <- Node1, Node2
  比较版本，返回最新值

2. LSM Tree 深入分析 ⭐⭐⭐⭐⭐

2.1 LSM Tree 原理

LSM Tree（Log-Structured Merge Tree）

核心思想：
- 牺牲部分读性能换取写性能
- 将随机写转换为顺序写
- 适合写多读少的场景

结构：
┌─────────────────────────────────────────┐
│              内存（MemTable）             │
│         红黑树/跳表，有序存储              │
└─────────────────────────────────────────┘
                    │ Flush
                    ▼
┌─────────────────────────────────────────┐
│         Level 0 (SSTable)               │
│    可能有重叠，直接从内存刷下来            │
└─────────────────────────────────────────┘
                    │ Compaction
                    ▼
┌─────────────────────────────────────────┐
│         Level 1 (SSTable)               │
│    不重叠，有序，大小约为 Level0 的 10 倍  │
└─────────────────────────────────────────┘
                    │ Compaction
                    ▼
┌─────────────────────────────────────────┐
│         Level 2 (SSTable)               │
│    不重叠，有序，大小约为 Level1 的 10 倍  │
└─────────────────────────────────────────┘
                    │
                    ▼
                  ......

2.2 写入流程

/**
 * LSM Tree 写入流程
 */
public class LSMTree {
    private MemTable memTable;
    private MemTable immutableMemTable;  // 正在刷盘的 MemTable
    private WriteAheadLog wal;
    private List<Level> levels;
    private static final int MEMTABLE_SIZE_THRESHOLD = 64 * 1024 * 1024; // 64MB

    public void put(String key, String value) {
        // 1. 先写 WAL（预写日志）
        wal.append(key, value);

        // 2. 写入内存表
        memTable.put(key, value);

        // 3. 检查是否需要刷盘
        if (memTable.size() >= MEMTABLE_SIZE_THRESHOLD) {
            // 将当前 MemTable 转为不可变
            immutableMemTable = memTable;
            memTable = new MemTable();

            // 异步刷盘
            flushMemTable(immutableMemTable);
        }
    }

    private void flushMemTable(MemTable table) {
        // 将 MemTable 写入 Level 0 的 SSTable
        SSTable sst = table.toSSTable();
        levels.get(0).add(sst);

        // 清理 WAL
        wal.truncate();

        // 触发 Compaction
        maybeCompact();
    }
}

2.3 读取流程

/**
 * LSM Tree 读取流程
 */
public String get(String key) {
    // 1. 先查 MemTable（最新数据）
    String value = memTable.get(key);
    if (value != null) {
        return value.equals(TOMBSTONE) ? null : value;
    }

    // 2. 查不可变 MemTable
    if (immutableMemTable != null) {
        value = immutableMemTable.get(key);
        if (value != null) {
            return value.equals(TOMBSTONE) ? null : value;
        }
    }

    // 3. 从 Level 0 到 Level N 依次查找
    for (Level level : levels) {
        // Level 0 需要查所有 SSTable（可能重叠）
        // Level 1+ 使用二分查找定位 SSTable
        value = level.get(key);
        if (value != null) {
            return value.equals(TOMBSTONE) ? null : value;
        }
    }

    return null;
}

2.4 Compaction 策略

Compaction 的作用：
1. 合并多个 SSTable，减少文件数量
2. 删除过期数据和墓碑标记
3. 将数据下推到更低层级

策略对比：

┌─────────────────────────────────────────────────────────────┐
│ Size-Tiered Compaction (STCS)                               │
├─────────────────────────────────────────────────────────────┤
│ 原理：相似大小的 SSTable 合并                                │
│ 优点：写放大小                                               │
│ 缺点：空间放大大（同一 key 可能存在多个 SSTable）             │
│ 适用：写密集型                                               │
│ 应用：Cassandra 默认                                        │
└─────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────┐
│ Leveled Compaction (LCS)                                    │
├─────────────────────────────────────────────────────────────┤
│ 原理：按层级合并，每层 SSTable 不重叠                         │
│ 优点：空间放大小，读性能好                                   │
│ 缺点：写放大大                                               │
│ 适用：读密集型                                               │
│ 应用：LevelDB, RocksDB 默认                                 │
└─────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────┐
│ FIFO Compaction                                             │
├─────────────────────────────────────────────────────────────┤
│ 原理：按时间删除最老的 SSTable                               │
│ 优点：写放大极小                                             │
│ 缺点：不适合更新操作                                         │
│ 适用：时序数据                                               │
└─────────────────────────────────────────────────────────────┘

2.5 LSM Tree 优化

1. Bloom Filter
   - 快速判断 key 是否可能存在
   - 避免无效的磁盘读取
   - 假阳性率通常设置 1%

2. Block Cache
   - 缓存热点数据块
   - LRU 或 ARC 替换策略

3. 压缩
   - SSTable 支持压缩（Snappy, LZ4, ZSTD）
   - 减少磁盘占用和 IO

4. 索引
   - 稀疏索引：每 N 条记录一个索引
   - Block 索引：定位数据块

3. Cassandra 详解 ⭐⭐⭐⭐

3.1 架构特点

• 完全去中心化，无单点故障

• P2P 架构，节点对等

• AP 系统：最终一致性

3.2 数据模型

Cassandra 数据模型：

Keyspace（类似数据库）
└── Table（类似表）
    └── Partition（分区，基本存储单元）
        └── Row（行）
            └── Column（列）

主键设计：
PRIMARY KEY ((partition_key), clustering_column1, clustering_column2)

- partition_key：决定数据存储在哪个节点
- clustering_column：决定分区内数据的排序

示例：
CREATE TABLE user_activities (
    user_id UUID,
    activity_time TIMESTAMP,
    activity_type TEXT,
    details TEXT,
    PRIMARY KEY ((user_id), activity_time)
) WITH CLUSTERING ORDER BY (activity_time DESC);

-- user_id 是分区键：同一用户的数据在同一分区
-- activity_time 是聚集列：按时间倒序排列

3.3 写入路径详解

Cassandra 写入流程：

Client
   │
   ▼
Coordinator Node（任意节点）
   │
   ├──────────────────────────────────────┐
   │                                      │
   ▼                                      ▼
Replica Node 1                      Replica Node 2
   │                                      │
   ▼                                      ▼
┌─────────────────┐              ┌─────────────────┐
│  Commit Log     │              │  Commit Log     │
│  (顺序写磁盘)    │              │  (顺序写磁盘)    │
└─────────────────┘              └─────────────────┘
   │                                      │
   ▼                                      ▼
┌─────────────────┐              ┌─────────────────┐
│   MemTable      │              │   MemTable      │
│  (内存写入)      │              │  (内存写入)      │
└─────────────────┘              └─────────────────┘
   │                                      │
   ▼ (异步刷盘)                           ▼
┌─────────────────┐              ┌─────────────────┐
│    SSTable      │              │    SSTable      │
│   (磁盘文件)     │              │   (磁盘文件)     │
└─────────────────┘              └─────────────────┘

写入特点：
1. 无需读取旧数据（append-only）
2. Commit Log 保证持久性
3. MemTable 提供高速写入
4. 最终一致性：W 个副本确认即返回

3.4 读取路径详解

Cassandra 读取流程：

                    Client
                       │
                       ▼
            Coordinator Node
                       │
      ┌────────────────┼────────────────┐
      ▼                ▼                ▼
  Replica 1        Replica 2        Replica 3
      │                │                │
      ▼                ▼                ▼
┌──────────────────────────────────────────────┐
│ 1. 检查 Row Cache（行缓存）                   │
│    命中 → 直接返回                            │
└──────────────────────────────────────────────┘
      │
      ▼
┌──────────────────────────────────────────────┐
│ 2. 检查 MemTable                             │
│    可能找到最新写入的数据                     │
└──────────────────────────────────────────────┘
      │
      ▼
┌──────────────────────────────────────────────┐
│ 3. 检查 Bloom Filter                         │
│    快速排除不包含该 key 的 SSTable           │
└──────────────────────────────────────────────┘
      │
      ▼
┌──────────────────────────────────────────────┐
│ 4. 检查 Partition Key Cache                  │
│    缓存分区索引位置                           │
└──────────────────────────────────────────────┘
      │
      ▼
┌──────────────────────────────────────────────┐
│ 5. 读取 SSTable                              │
│    - Partition Summary → Partition Index     │
│    - Compression Offset → 数据位置           │
│    - 读取数据块                               │
└──────────────────────────────────────────────┘
      │
      ▼
┌──────────────────────────────────────────────┐
│ 6. 合并结果                                   │
│    - 合并 MemTable 和多个 SSTable            │
│    - 按时间戳选择最新版本                     │
└──────────────────────────────────────────────┘
      │
      ▼
  Coordinator 汇总结果
      │
      ▼
  返回给 Client

3.5 核心机制

1. Gossip 协议
   - 节点间状态交换
   - 每秒随机选择节点通信
   - 传播节点状态（UP/DOWN）

2. Hinted Handoff
   - 目标节点不可用时，暂存数据
   - 节点恢复后发送
   - 解决临时故障

3. Read Repair
   - 读取时检测不一致
   - 自动修复过期副本
   - 分为同步和异步模式

4. Anti-Entropy Repair
   - Merkle Tree 比较数据
   - 定期运行 nodetool repair
   - 修复长时间不一致

4. HBase 详解 ⭐⭐⭐⭐

4.1 架构设计

HBase 架构：

┌─────────────────────────────────────────────────────────┐
│                        Client                           │
└─────────────────────────────────────────────────────────┘
                            │
                            ▼
┌─────────────────────────────────────────────────────────┐
│                      ZooKeeper                          │
│     - HMaster 选举                                       │
│     - RegionServer 注册                                  │
│     - META 表位置                                        │
└─────────────────────────────────────────────────────────┘
           │                              │
           ▼                              ▼
┌─────────────────────┐      ┌─────────────────────────────┐
│      HMaster        │      │      RegionServer           │
│  - Region 分配       │      │  - 管理多个 Region          │
│  - 负载均衡          │      │  - 处理读写请求             │
│  - Schema 管理       │      │  - MemStore + HFile        │
│  - 故障恢复          │      │  - Compaction              │
└─────────────────────┘      └─────────────────────────────┘
                                          │
                                          ▼
                             ┌─────────────────────────────┐
                             │          HDFS               │
                             │   - HFile 存储              │
                             │   - WAL 存储                │
                             └─────────────────────────────┘

4.2 Region 管理

Region 概念：
- 表的水平分片
- 包含连续的 Row Key 范围
- 由单个 RegionServer 管理

Region 分裂（Split）：
┌─────────────────────────────────────┐
│         Region (A-Z)                │
│      大小达到阈值（默认10GB）         │
└─────────────────────────────────────┘
                 │ Split
                 ▼
┌─────────────────┐  ┌─────────────────┐
│  Region (A-M)   │  │  Region (N-Z)   │
└─────────────────┘  └─────────────────┘

分裂策略：
1. ConstantSizeRegionSplitPolicy
   - 固定大小阈值
   - 简单但可能导致热点

2. IncreasingToUpperBoundRegionSplitPolicy（默认）
   - 动态阈值：min(maxRegionFileSize, 初始大小 * region数量^3)
   - 早期分裂更积极

3. SteppingSplitPolicy
   - 大表固定阈值
   - 小表快速分裂

4.3 Region 负载均衡

/**
 * HBase 负载均衡策略
 */
public class LoadBalancer {

    /**
     * 计算每个 RegionServer 应该有多少 Region
     */
    public int getTargetRegionCount(int totalRegions, int serverCount) {
        return (int) Math.ceil((double) totalRegions / serverCount);
    }

    /**
     * 简单负载均衡：Region 数量均衡
     */
    public List<RegionMove> balanceByRegionCount(
            Map<String, List<Region>> serverRegions) {

        List<RegionMove> moves = new ArrayList<>();
        int totalRegions = serverRegions.values().stream()
                .mapToInt(List::size).sum();
        int avgRegions = totalRegions / serverRegions.size();

        // 找出过载和空闲的 RegionServer
        List<String> overloaded = new ArrayList<>();
        List<String> underloaded = new ArrayList<>();

        for (Map.Entry<String, List<Region>> entry : serverRegions.entrySet()) {
            int count = entry.getValue().size();
            if (count > avgRegions + 1) {
                overloaded.add(entry.getKey());
            } else if (count < avgRegions) {
                underloaded.add(entry.getKey());
            }
        }

        // 从过载节点迁移 Region 到空闲节点
        for (String from : overloaded) {
            List<Region> regions = serverRegions.get(from);
            while (regions.size() > avgRegions && !underloaded.isEmpty()) {
                String to = underloaded.get(0);
                Region region = regions.remove(regions.size() - 1);
                moves.add(new RegionMove(region, from, to));

                if (serverRegions.get(to).size() >= avgRegions) {
                    underloaded.remove(0);
                }
            }
        }

        return moves;
    }
}

4.4 热点问题与 Row Key 设计

热点问题：
- 连续的 Row Key 导致请求集中在少数 Region
- 写入/读取都可能产生热点

解决方案：

1. 加盐（Salting）
   原始：user_001, user_002, user_003
   加盐：0_user_001, 1_user_002, 2_user_003
   优点：数据分散
   缺点：范围扫描需要合并多个分区

2. 哈希前缀
   原始：2024-01-01_user_001
   哈希：hash(user_001)_2024-01-01_user_001
   优点：同一用户的数据分散
   缺点：无法按用户范围查询

3. 反转
   原始：www.example.com
   反转：com.example.www
   适用：URL、域名等天然热点数据

4. 预分区
   建表时预先创建多个 Region
   避免初期所有写入集中在一个 Region

CREATE 'user_table', 'cf',
  {SPLITS => ['10', '20', '30', '40', '50', '60', '70', '80', '90']}

5. Dynamo 设计原理 ⭐⭐⭐⭐

5.1 Dynamo 概述

Amazon Dynamo（2007）：
- 高可用 Key-Value 存储
- 启发了 Cassandra、Riak、Voldemort
- 核心目标：永远可写（Always Writable）

设计原则：
1. 增量可扩展性
2. 对称性（节点对等）
3. 去中心化
4. 异构性（支持不同配置的节点）

5.2 核心技术

Dynamo 使用的技术：

┌────────────────────┬───────────────────────────────────┐
│ 问题               │ 解决方案                           │
├────────────────────┼───────────────────────────────────┤
│ 数据分区           │ 一致性哈希 + 虚拟节点               │
├────────────────────┼───────────────────────────────────┤
│ 高可用写入         │ Vector Clock + 读时修复            │
├────────────────────┼───────────────────────────────────┤
│ 临时故障           │ Sloppy Quorum + Hinted Handoff    │
├────────────────────┼───────────────────────────────────┤
│ 永久故障恢复       │ Merkle Tree 反熵                   │
├────────────────────┼───────────────────────────────────┤
│ 成员检测           │ Gossip 协议                        │
└────────────────────┴───────────────────────────────────┘

5.3 版本控制与冲突解决

Vector Clock（向量时钟）：

场景：多个节点可能同时写入同一 key

写入流程：
T1: Client1 写入 key1=v1 到 Node1
    版本：[(Node1, 1)]

T2: Client2 写入 key1=v2 到 Node2（未同步 T1）
    版本：[(Node2, 1)]

T3: 读取时发现两个版本
    [(Node1, 1)] 和 [(Node2, 1)]
    这是冲突！无法判断哪个更新

冲突解决：
1. 客户端解决（Dynamo 方式）
   - 返回所有冲突版本给客户端
   - 客户端合并后写回

2. LWW（Last Write Wins）
   - 使用时间戳选择最新
   - 可能丢失数据

3. CRDT（Conflict-free Replicated Data Type）
   - 设计可自动合并的数据类型
   - 如：计数器、集合、LWW-Register

5.4 Sloppy Quorum

传统 Quorum：
- 必须从 N 个固定副本中获得 W/R 个响应
- 如果副本不可用，操作失败

Sloppy Quorum：
- 优先使用 N 个首选节点
- 首选节点不可用时，使用后续节点
- 保证操作成功，但可能写到非首选节点

示例：
Preference List: [A, B, C, D, E]
N=3, 正常副本：A, B, C

场景：A 宕机
- 传统 Quorum：等待 A 恢复或失败
- Sloppy Quorum：使用 B, C, D
  - D 存储数据并标记 "hinted for A"
  - A 恢复后，D 将数据发送给 A（Hinted Handoff）

6. 面试要点总结

6.1 分布式存储核心

知识点	重要程度	考察频率
一致性哈希	⭐⭐⭐⭐⭐	非常高
LSM Tree	⭐⭐⭐⭐⭐	高
Quorum 机制	⭐⭐⭐⭐	高
数据分片	⭐⭐⭐⭐	高
副本策略	⭐⭐⭐⭐	中

6.2 关键记忆点

一致性哈希：
- 虚拟节点解决数据倾斜
- 只迁移 1/N 的数据
- 带权重支持异构节点

LSM Tree：
- 写入：WAL → MemTable → SSTable
- 读取：MemTable → Level0 → Level1 → ...
- Compaction：合并、删除、下推

Quorum：
- W + R > N：强一致性
- 读写权衡：高 W 保证写入一致，高 R 保证读取一致

7. 常见面试题

7.1 一致性哈希

Q1：一致性哈希如何解决数据倾斜？

答：使用虚拟节点。

1. 每个物理节点映射多个虚拟节点到哈希环
2. 虚拟节点分散分布，使数据更均匀
3. 通常使用 100-200 个虚拟节点
4. 支持带权重的虚拟节点分配

Q2：一致性哈希节点下线时如何处理？

答：
1. 移除该节点的所有虚拟节点
2. 原本存储在该节点的数据自动归属于
   顺时针方向的下一个节点
3. 只影响相邻的一个节点
4. 副本机制保证数据不丢失

7.2 LSM Tree

Q3：LSM Tree 为什么写性能好？

答：
1. 写入只需追加到内存（MemTable）
2. WAL 是顺序写磁盘（比随机写快 100 倍）
3. MemTable 满了才刷盘
4. 刷盘也是顺序写（生成新 SSTable）
5. 不需要读取-修改-写入循环

Q4：LSM Tree 读取为什么可能慢？

答：
1. 可能需要查找多个 SSTable
2. Level 0 的 SSTable 可能重叠
3. 需要合并多个版本
4. 空间放大导致更多磁盘读取

优化方案：
1. Bloom Filter：快速判断 key 不存在
2. Block Cache：缓存热点数据
3. Compaction：减少 SSTable 数量
4. 索引优化：稀疏索引定位数据块

Q5：比较 B+ Tree 和 LSM Tree？

答：
B+ Tree：
- 写入：随机 IO，需要更新原地
- 读取：O(log N)，一次定位
- 空间放大：小（数据只存一份）
- 写放大：小（只更新变化的页）
- 适用：读多写少，如 MySQL

LSM Tree：
- 写入：顺序 IO，追加写入
- 读取：可能需要查多个文件
- 空间放大：大（同一 key 可能存多份）
- 写放大：大（Compaction 重复写）
- 适用：写多读少，如 日志、时序数据

7.3 存储系统

Q6：Cassandra 和 HBase 的区别？

答：
Cassandra：
- AP 系统，最终一致性
- P2P 架构，无中心节点
- 适合跨数据中心部署
- CQL 查询语言

HBase：
- CP 系统，强一致性
- Master-Slave 架构
- 依赖 HDFS 和 ZooKeeper
- 适合大数据生态集成

选择建议：
- 需要强一致性 → HBase
- 需要高可用、跨机房 → Cassandra
- Hadoop 生态 → HBase
- 简单运维 → Cassandra

Q7：如何设计一个支持高并发写入的 KV 存储？

答：
1. 数据分片
   - 一致性哈希分散数据
   - 虚拟节点均衡负载

2. 写入优化
   - WAL 保证持久性
   - 内存缓冲批量写入
   - LSM Tree 顺序写磁盘

3. 副本机制
   - 多副本高可用
   - Quorum 读写平衡一致性和性能

4. 热点处理
   - 加盐/哈希分散热点 key
   - 本地缓存吸收读热点

5. 故障处理
   - Gossip 检测故障
   - Hinted Handoff 临时存储
   - 反熵修复数据