- 正确答案：LRU和LFU缓存的分片（Sharding）通常采用一致性哈希（Consistent Hashing）或模运算（Modulo Sharding）将缓存键映射到多个独立的缓存分片（Shard）上，每个分片内部维护自身的LRU链表或LFU计数器；分片本身不共享状态，读写操作先路由到对应分片，再由该分片执行本地淘汰策略。常见工业实践如Redis Cluster、Caffeine多段分片（Segmented LRU/LFU）、Guava Cache的concurrent level分片均基于此思想。 - 解答思路：首先明确“缓存分片”的目标是解决单机缓存容量/并发瓶颈，提升水平扩展性与线程安全性。LRU/LFU是单分片内的淘汰策略，而分片是数据分布策略——二者正交。因此设计分片需回答三个问题：（1）如何把key分配到分片？（2）分片间是否共享元数据（如访问频次、时序）？（3）如何保证高并发下的线程安全与局部性？答案是：不共享（否则丧失分片意义），每个分片自治；分配采用无状态哈希（如 key.hashCode() % N 或一致性哈希）；线程安全通过分片粒度加锁或使用无锁数据结构（如ConcurrentLinkedQueue + CAS更新LRU头尾）实现。 - 深度知识讲解：【底层数据结构】 • LRU分片：每个Shard内部典型实现为“双向链表 + 哈希表”组合（Java中常用LinkedHashMap或手写Node链表+ConcurrentHashMap）。插入/访问时：O(1)定位节点 → 移至链表头部（最新）→ 若超容量则淘汰尾部节点。分片后，总LRU全局序被打破，变为N个局部LRU序列，这是牺牲全局最优换取可扩展性的本质代价。 • LFU分片：更复杂。基础LFU需记录每个key的访问频次+最近访问时间（解决频次相同下的新旧区分，即LFU-Aging或TinyLFU优化）。单机LFU常用“频次桶（Frequency Bucket）+ 多级链表”（如Redis 6.0+的evict.c中dictEntry->lru字段复用为lfu_log + lfu_freq），或“最小堆+哈希表”（但堆不支持O(1)更新频次）。分片LFU中，每个Shard维护独立的频次映射（ConcurrentHashMap）和一个按频次分组的双向链表（类似Redis的“freq bucket list”），淘汰时扫描最低频次桶内最久未访问项。注意：分片LFU无法感知跨分片的全局频次分布，故对倾斜访问（hot key跨分片）无鲁棒性，需额外热点探测机制（如布隆过滤器+采样统计）。【分片算法对比】 • Modulo Sharding（key % shardCount）：简单高效，但扩容缩容时大量key重哈希（rehash），缓存击穿严重。 • Consistent Hashing：虚拟节点+哈希环，增删分片仅影响邻近key，缓存命中率更平稳；但实现复杂，且仍无法解决数据倾斜（需结合key预处理如加盐）。 • Jump Hash（Google提出的单向跳跃哈希）：O(1)计算、无状态、天然均衡，适合无中心协调的分布式缓存分片，被Caffeine 3.x用于SegmentedCache的shard选择。【并发控制深度】单分片内LRU链表操作（move-to-head、evict-tail）必须原子。常见方案： – 细粒度锁：每个Shard一把ReentrantLock，吞吐受限于锁竞争； – 无锁化：使用AtomicReferenceFieldUpdater更新Node.prev/next，配合CAS循环（如JDK ConcurrentLinkedQueue），但LRU需双向更新，需双CAS或引入版本号； – 分段锁升级：Caffeine采用“WriteBuffer + Drain on read/write”，将链表更新暂存为不可变buffer，定期批量drain到主链表，降低锁持有时间。【关键陷阱与优化】 • LRU分片的“伪热点放大”：某分片因哈希倾斜承载过多热key，导致其LRU频繁淘汰，而其他分片冷数据滞留——需在分片层引入动态负载感知（如监控各shard miss rate，自动迁移key）。 • LFU分片的“频次漂移”：各分片独立计数，初始频次为0，新key写入后频次从1开始，但全局视角下可能已是高频；解决方案包括：① 启动时预热频次（从持久化存储加载历史频次）；② 跨分片轻量同步（如Gossip协议广播top-K hot key频次，仅作参考不强一致）；③ 替代方案TinyLFU：每个分片维护一个微型LFU sketch（Count-Min Sketch），空间O(1)，支持近似频次查询与合并，Caffeine默认启用。 - 代码示例（简化版分片LRU伪代码，Java风格）： ``` public class ShardedLRUCache { private final int shardCount; private final LRUShard[] shards; public ShardedLRUCache(int shardCount, int capacityPerShard) { this.shardCount = shardCount; this.shards = new LRUShard[shardCount]; for (int i = 0; i < shardCount; i++) { shards[i] = new LRUShard<>(capacityPerShard); } } private int getShardIndex(K key) { // 使用MurmurHash3避免低质量hashCode导致倾斜 return Math.abs(MurmurHash3.hashBytes(String.valueOf(key).getBytes()).hashCode()) % shardCount; } public V get(K key) { int idx = getShardIndex(key); return shards[idx].get(key); // 内部：查hash表 → 移至链头 → 返回 } public void put(K key, V value) { int idx = getShardIndex(key); shards[idx].put(key, value); // 内部：插入hash表+链头；若超容则移除链尾节点 } } // 单分片LRU实现（简化） static class LRUShard { private final int capacity; private final ConcurrentHashMap> map; private final AtomicReference> head; // head → most recently used private final AtomicReference> tail; // tail → least recently used static class Node { final K key; V value; final AtomicReference> prev = new AtomicReference<>(); final AtomicReference> next = new AtomicReference<>(); } LRUShard(int capacity) { this.capacity = capacity; this.map = new ConcurrentHashMap<>(); this.head = new AtomicReference<>(); this.tail = new AtomicReference<>(); } V get(K key) { Node node = map.get(key); if (node == null) return null; moveToHead(node); // CAS更新prev/next，需循环重试 return node.value; } void put(K key, V value) { Node node = map.get(key); if (node != null) { node.value = value; moveToHead(node); } else { node = new Node<>(key, value); map.put(key, node); addToHead(node); if (map.size() > capacity) { Node last = tail.get(); removeNode(last); map.remove(last.key); } } } void moveToHead(Node node) { // 双向链表CAS移动：断开原连接 → 插入head后 Node prev = node.prev.get(); Node next = node.next.get(); if (prev != null) prev.next.compareAndSet(node, next); if (next != null) next.prev.compareAndSet(node, prev); if (head.get() != null) { node.next.set(head.get()); head.get().prev.set(node); } node.prev.set(null); head.set(node); if (tail.get() == null) tail.set(node); } void addToHead(Node node) { node.next.set(head.get()); if (head.get() != null) head.get().prev.set(node); node.prev.set(null); head.set(node); if (tail.get() == null) tail.set(node); } void removeNode(Node node) { Node prev = node.prev.get(); Node next = node.next.get(); if (prev != null) prev.next.set(next); if (next != null) next.prev.set(prev); if (head.get() == node) head.set(next); if (tail.get() == node) tail.set(prev); } } ``` 注：上述伪代码展示核心逻辑，真实生产环境会使用更健壮的无锁原语（如VarHandle代替AtomicReferenceFieldUpdater）、内存布局优化（@Contended避免false sharing）、以及驱逐回调（eviction listener）等。对于LFU分片，只需将Node扩展为含freq字段，并在get/put时原子递增freq，淘汰时遍历最低freq桶内tail节点即可。

腾讯提前批软开-侧开一面面经

全站热榜

创作者周榜