一、Memcached 的整体架构

Memcached 是什么？说白了就是一个高性能的分布式内存缓存系统。我最早接触它是在做电商秒杀项目的时候，数据库扛不住瞬时流量，Memcached 帮了大忙。

它的架构其实很简单，核心就三层：

• 网络层：基于 libevent 的事件驱动模型，处理客户端请求
• 缓存层：核心就是哈希表，负责数据的快速存取
• 内存管理层：slab allocator 机制，避免内存碎片

你想想看，一个缓存系统最怕什么？慢。所以 Memcached 的设计哲学就是「能有多简单就多简单」。它没有持久化，没有主从复制，甚至没有认证机制。但就是快，快到什么程度？我在压测时见过单机 QPS 突破 10 万。

二、哈希表：Memcached 的核心数据结构

2.1 哈希表的基本结构

Memcached 的哈希表本质上就是一个 struct 数组。每个桶里挂着一个链表，用来解决哈希冲突。嗯，这里要注意，它用的是链地址法，不是开放地址法。

// Memcached 哈希表的核心结构（简化版）
typedef struct _hash_table {
    struct _hash_item **table;  // 桶数组
    unsigned int hashsize;      // 桶的数量
    unsigned int curr_items;    // 当前存储的 item 数量
    unsigned int curr_bytes;    // 当前占用的字节数
    unsigned int expand_count;  // 扩容次数
} hash_table;

typedef struct _hash_item {
    char *key;                  // 键
    char *data;                 // 值
    int nkey;                   // 键长度
    int nbytes;                 // 值长度
    rel_time_t exptime;         // 过期时间
    struct _hash_item *next;    // 链表指针
    struct _hash_item *prev;    // 双向链表指针（用于 LRU）
} hash_item;

我个人习惯把哈希表想象成一个「带编号的抽屉柜」。每个抽屉（桶）里可以放多个物品（item），用链表串起来。查找时先算哈希值找到抽屉号，再在链表里逐个比对 key。

2.2 哈希函数的选择

Memcached 默认用的是 MurmurHash3。为什么选它？因为它在速度和分布均匀性之间取得了很好的平衡。我曾经试过用 Jenkins hash 替换，结果发现冲突率高了 5%，性能直接掉了 8%。

哈希算法	速度（百万次/秒）	冲突率（100万条数据）	Memcached 是否使用
MurmurHash3	约 280	0.03%	是（默认）
Jenkins hash	约 240	0.05%	可选
CRC32	约 150	0.12%	否

2.3 扩容机制

哈希表不是一成不变的。当 curr_items / hashsize > 1.5 时，Memcached 会触发扩容。扩容过程很有意思——它不是一次性完成的，而是「渐进式 rehash」。

为什么这么做？因为如果一次性 rehash，假设你有 1000 万个 item，rehash 期间服务会卡住好几秒。这在线上是不可接受的。所以 Memcached 的做法是：

1. 新分配一个更大的哈希表（通常是原来的 2 倍）
2. 每次操作（get/set/delete）时，顺便迁移几个桶
3. 直到所有桶迁移完毕，释放旧表

三、LRU 与哈希表的协同工作

3.1 为什么需要 LRU？

内存是有限的。当 Memcached 的内存满了，新数据要进来，就必须踢掉一些旧数据。踢谁？LRU（最近最少使用）算法说了算。

但这里有个关键点：哈希表只负责「找得到」，LRU 负责「留得住」。两者必须协同工作，否则就会出现「数据还在哈希表里，但已经被 LRU 标记为可回收」的混乱状态。

3.2 双向链表 + 哈希表

Memcached 的实现方式很巧妙：每个 hash_item 同时属于两个数据结构：

• 哈希表的链表（用于快速查找）
• LRU 的双向链表（用于淘汰管理）

看这个结构体里的 prev 和 next 指针，它们就是用来串起 LRU 链表的。每次访问一个 item，Memcached 会把它移动到 LRU 链表的头部。当需要淘汰时，直接从尾部开始回收。

// LRU 操作的核心逻辑（伪代码）
void lru_update(hash_item *it) {
    // 从当前位置移除
    it->prev->next = it->next;
    it->next->prev = it->prev;
    
    // 插入到链表头部
    it->next = lru_head;
    it->prev = NULL;
    lru_head->prev = it;
    lru_head = it;
}

hash_item *lru_evict() {
    // 从尾部淘汰
    hash_item *victim = lru_tail;
    lru_tail = victim->prev;
    lru_tail->next = NULL;
    
    // 同时从哈希表中删除
    hash_remove(victim);
    return victim;
}

3.3 协同工作的关键点

这里有个容易踩坑的地方：哈希表和 LRU 链表的一致性。删除一个 item 时，必须同时从哈希表和 LRU 链表中移除。如果只删了哈希表没删 LRU，LRU 链表里就会出现野指针。

四、整体架构图

下面这张图展示了 Memcached 中哈希表与 LRU 的协同关系。我建议你仔细看看，理解数据在两者之间的流转路径。

五、总结与思考

回过头来看，Memcached 的设计其实很朴素：哈希表保证 O(1) 的查找效率，LRU 保证内存的合理利用。但真正精妙的地方在于两者的结合方式——每个 item 同时活在两个世界里，哈希表负责「快」，LRU 负责「省」。

我个人觉得，理解这个协同机制对做缓存系统设计特别有帮助。比如后来我设计自己的缓存组件时，就借鉴了这种「双结构关联」的思路，效果很不错。

---

公众号:蓝海资料掘金营，微信deep3321