Distributed Caching and Data Partitioning

Distributed Caching and Data Partitioning (分布式缓存与数据分片)

在大规模分布式系统架构中，缓存（Caching）与数据分片（Data Partitioning / Sharding）是突破单机 I/O 吞吐瓶颈、降低数据库压力的两大核心基础设施支柱。两者的核心设计哲学在于通过空间换时间平抑读延迟，以及通过水平切分打破单一节点的容量物理天花板。

Source: 2026-10-07-book-grokking-the-system-design-interview.md（来源未公开）

---

一、缓存更新与失效策略 (Cache Invalidation Schemes)

缓存与持久化数据库（Source of Truth）的数据一致性维护是架构设计的经典难点，主流写入模式包括以下三种：

flowchart LR
    subgraph WT["Write-Through (同步写穿)"]
        C1[Client] -->|Write| CA1[Cache]
        CA1 -->|Sync Write| DB1[(Database)]
    end
    subgraph WA["Write-Around (绕写)"]
        C2[Client] -->|Direct Write| DB2[(Database)]
        C2 -.->|Read Miss| CA2[Cache]
    end
    subgraph WB["Write-Back (异步写回)"]
        C3[Client] -->|Fast Write| CA3[Cache]
        CA3 -.->|Async Batch| DB3[(Database)]
    end

写入模式	工作流机制	优势	劣势与适用场景
Write-Through (同步写穿)	数据同时写入缓存和数据库，双写成功后向客户端返回确认。	强一致性保障，缓存永不落后；宕机不丢数据。	写入延迟叠加（两次 I/O）；适合读多写少、一致性要求高的核心数据。
Write-Around (绕写)	写入时直接落库，彻底绕过缓存；后续由读请求触发 Cache Miss 后被动加载。	防止低频访问或只写不读的大量数据污染缓存池。	最新写入的数据首次读取必发生 Cache Miss，读延迟抖动明显。
Write-Back (异步写回)	数据仅极速写入缓存即向客户端确认；由后台批处理或定时任务异步刷盘进 DB。	极致的低写入延迟与超高写入吞吐量。	缓存节点宕机或断电存在数据丢失风险；适合写密集、可容忍微量丢失场景。

---

二、缓存淘汰算法 (Cache Eviction Policies)

当缓存容量耗尽时，系统需借助淘汰算法驱逐特定数据以腾出空间：

1. LRU (Least Recently Used)：淘汰最长时间未被访问的项。通常以哈希表加双向链表（LinkedHashMap）实现 $O(1)$ 查找与移动，工业界应用最广。
2. LFU (Least Frequently Used)：基于访问频次计数，优先淘汰累计使用频率最低的项。适合长周期热点明确场景，但对突发临时流量敏感度滞后。
3. FIFO (First In First Out)：先进先出队列，不考虑访问频次与热度，实现简单但命中率较低。
4. MRU (Most Recently Used)：淘汰最近刚刚访问过的项。适合“访问过一次近期极大概率不再访问”的特定扫描模式。
5. Random Replacement (RR)：伪随机选择淘汰项，在超大规模分布式缓存中能有效降低锁竞争。

---

三、数据分片维度 (Partitioning Criteria)

1. 哈希/键值分片 (Key or Hash-based Partitioning)：
   • 采用 $Hash(Key)(\mathrm{mod}N)$ 确定存储节点。实现简单且分布均匀，但致命缺陷在于节点扩缩容导致全局哈希失效，必须通过 consistent-hashing（一致性哈希环与虚拟节点）解决。
2. 列表分片 (List Partitioning)：
   • 根据业务属性预定义枚举映射（如按国家、地理区域分配 Shard）。业务亲和性强，但容易因单一地区人口/业务爆发导致数据倾斜。
3. 轮询分片 (Round-Robin Partitioning)：
   • 依次分配至第 $i(\mathrm{mod}N)$ 个分片，保证写入绝对平摊，但无法基于业务属性建立单节点索引检索。
4. 复合分片 (Composite Partitioning)：
   • 结合多种策略，例如先按业务范围做列表分片，内部再做哈希散列。

---

四、分布式分片三大核心痛点与攻防

1. 跨分片关联查询 (Cross-Partition Joins & Denormalization)：
   • 在单机关系型数据库中 Join 操作极其便捷，但分片后跨机器 Join 会引发网络通信风暴。
   • 破局解法：对数据库进行反范式化（Denormalization），通过冗余宽表以单表查询取代跨库关联，由应用层处理并发写时的弱一致性。
2. 分布式外键参照完整性 (Referential Integrity)：
   • 分片架构下数据库级 Foreign Key 约束彻底失效。
   • 破局解法：必须在应用业务服务层（Application Logic）实现约束检查与级联校验，并配合定时异步离线 SQL 清理孤儿记录（Dangling References）。
3. 数据重平衡 (Rebalancing & Hotspots)：
   • 局部业务爆炸或节点容量告警时需迁移分片。
   • 破局解法：采用基于目录的路由寻址服务（Directory-Based Partitioning），支持平滑迁移数据，但需防止配置路由中心成为系统单点故障（SPOF）。

---

关联概念与知识网络

• consistent-hashing — 一致性哈希环设计与热点解决
• grokking-the-system-design — 系统设计经典业务架构全景
• cap-theorem-and-nosql-taxonomy — 分布式数据存储与 CAP 权衡
• system-design-interview-framework — 系统容量估算与高并发设计流程