历史题目复盘：设计一个每秒 5000 次查询的 DNS 缓存，数据结构怎么选

深蓝黑背景品牌封面：左侧大标题「每秒 5000 次查询的 DNS 缓存」，副标题「让 QPS 约束替你选数据结构」；右侧原创装饰——仪表盘指针指向高 QPS 区域，下方一排带 TTL 时钟标记的缓存条目格；顶部标注「历史题目复盘 · 系统设计」与「Day 05 · 09-23」图 1：本文封面，点明题目与「约束驱动选型」的主线。

先说明属性：这是一篇历史题目复盘，题目出自本地历史面试资料（见文末来源说明），与任何公司的当前招聘无关。设计题没有标准答案，但有标准打法——面试官想看的不是你背了哪个框架，而是你能不能把约束一条一条翻译成结构决策。

想象面试现场，面试官说：「设计一个 DNS 缓存，支持每秒 5000 次查询，插入要快，数据结构自己选。」

第一步，审题：先把约束列全。

别急着选结构，先把题面里没说出口的约束挖出来：一，查询 QPS 高且以读为主，查询延迟是第一指标；二，DNS 记录天然带 TTL，会过期，缓存必须处理失效；三，内存有限，不能无限存，要有淘汰策略；四，多线程环境下读写并发，要考虑竞争。约束列全的那一刻，设计其实已经完成了一半——每条约束都会替你否决一批方案、指向一个结构。

第二步，让每条约束替你选一个结构。

约束一指向哈希表。每秒 5000 次查询，平均每次只有 200 微秒预算，O(1) 查询的哈希表几乎是唯一选择；平衡树 O(log n) 的查询和再平衡开销在这里都是浪费。

约束二指向过期时间管理。每条记录带上过期时间戳，查询时先判过期（惰性删除）；如果记录量大、怕过期条目堆积，再加一个按过期时间组织的最小堆，定期集中清理堆顶。

约束三指向 LRU。容量满时淘汰「最久未使用」的记录最贴合 DNS 热点集中的访问特征；实现上用哈希表加双向链表（或在支持插入序的语言里用有序 Map）做到 O(1) 命中提队首、O(1) 淘汰队尾。

约束四指向分片锁。一把大锁会把 5000 QPS 串行化，按域名哈希把缓存拆成多个分片，每片一把锁，竞争降到原来的几十分之一。

设计推导图：左侧四条约束各自映射一个结构决策——每秒 5000 次查询以读为主，选哈希表做到 O(1) 查询；DNS 记录有 TTL 会过期，用按过期时间组织的最小堆集中清理；内存容量有限，用 LRU 双向链表淘汰最久未用的记录；多线程并发读写，用分片锁按域名分桶降低竞争。右侧查询路径：请求先查哈希表，命中且未过期则返回并把记录提到 LRU 队首，过期或缺失则回源 DNS 查询后写入缓存。底部方法论：设计题先把约束列全，让每条约束替你选一个结构；单机扛不住才谈分片与多级缓存图 2：四条约束到四个结构的映射，与完整的查询路径。

第三步，串起查询路径，并跑一遍代码。

完整路径：请求先查哈希表；命中且未过期，返回结果并把记录提到 LRU 队首；过期或缺失，回源 DNS 查询，写入缓存（必要时先淘汰）。下面这份实现把「哈希表 + TTL 惰性删除 + LRU 淘汰 + 分片」压缩进几十行，用 Node.js 22.15.0 直接运行（node dns-cache.js）即可：

'use strict';

// 单分片：Map 按插入序迭代，删了再插即「提到队首」，天然 O(1) LRU
class Shard {
  constructor(capacity) {
    this.capacity = capacity;
    this.store = new Map(); // name -> { ip, expireAt }
  }
  get(name, now) {
    const rec = this.store.get(name);
    if (rec === undefined) return null; // 未命中
    if (rec.expireAt <= now) {
      this.store.delete(name); // 已过期：惰性删除
      return null;
    }
    this.store.delete(name);
    this.store.set(name, rec); // 命中：提到 LRU 队首
    return rec.ip;
  }
  set(name, ip, ttlMs, now) {
    this.store.delete(name);
    this.store.set(name, { ip, expireAt: now + ttlMs });
    if (this.store.size > this.capacity) {
      const oldest = this.store.keys().next().value; // 队首 = 最久未使用
      this.store.delete(oldest); // 淘汰
    }
  }
}

// 多线程模型下每个分片配一把锁，域名哈希决定落哪片，降低锁竞争
class DnsCache {
  constructor(shardCount, capacityPerShard) {
    this.shards = Array.from({ length: shardCount }, () => new Shard(capacityPerShard));
  }
  shardOf(name) {
    let h = 0;
    for (const ch of name) h = (h * 31 + ch.charCodeAt(0)) >>> 0;
    return this.shards[h % this.shards.length];
  }
  get(name, now) {
    return this.shardOf(name).get(name, now);
  }
  set(name, ip, ttlMs, now) {
    this.shardOf(name).set(name, ip, ttlMs, now);
  }
}

// 模拟回源 DNS 查询（每次回源计数 +1）
let upstreamQueries = 0;
function resolveUpstream(name) {
  upstreamQueries += 1;
  return `93.184.0.${name.length}`;
}

const cache = new DnsCache(16, 100); // 16 分片，每片容量 100
let now = 1_000_000;

// 第一次查询：未命中，回源后写入缓存（TTL 60 秒）
let ip = cache.get('example.com', now);
if (ip === null) {
  ip = resolveUpstream('example.com');
  cache.set('example.com', ip, 60_000, now);
}
console.log(`第 1 次查 example.com -> ${ip}（回源 ${upstreamQueries} 次）`);

// 第二次查询：缓存命中，不回源
ip = cache.get('example.com', now);
console.log(`第 2 次查 example.com -> ${ip}（回源 ${upstreamQueries} 次）`);

// 同一分片内容量 2：写入 a、b 后访问 a，再写入 c——最久未用的 b 被淘汰
const shard = new Shard(2);
shard.set('a.dev', '10.0.0.1', 60_000, now);
shard.set('b.dev', '10.0.0.2', 60_000, now);
shard.get('a.dev', now); // 访问 a，把 b 挤到队首
shard.set('c.dev', '10.0.0.3', 60_000, now);
console.log(`容量 2：访问过 a.dev 再写入 c.dev，被淘汰的是 b.dev -> ${shard.get('b.dev', now) === null}`);

// 跨过 TTL 再查：记录过期，重新回源
now += 61_000;
ip = cache.get('example.com', now);
if (ip === null) {
  ip = resolveUpstream('example.com');
  cache.set('example.com', ip, 60_000, now);
}
console.log(`61 秒后再查 example.com -> ${ip}（回源 ${upstreamQueries} 次）`);

实测输出如下：

第 1 次查 example.com -> 93.184.0.11（回源 1 次）
第 2 次查 example.com -> 93.184.0.11（回源 1 次）
容量 2：访问过 a.dev 再写入 c.dev，被淘汰的是 b.dev -> true
61 秒后再查 example.com -> 93.184.0.11（回源 2 次）

四行输出分别验证了命中不回源、LRU 淘汰最久未用项、TTL 过期重新回源三件事。

易错点清单。

一，开口就报框架名——设计题先说约束再说结构，顺序反了就是背答案。二，忘记 TTL——DNS 缓存不处理过期，等于把错误答案缓存起来发。三，淘汰策略只说「LRU」三个字，讲不清命中后如何 O(1) 提到队首。四，用一把全局锁扛 5000 QPS——分片是并发设计的必答点。五，单机扛不住怎么办没预案：答「多实例 + 一致性哈希分片 + 上游递归缓存兜底」即可过关。

回到面试现场，建议的答题节奏：先复述并补全约束（读多写少、TTL、容量、并发），再逐条映射到结构（哈希表、过期堆、LRU、分片锁），然后讲一遍查询路径，最后主动谈单机之外的扩展。约束讲得越全，结构选得越稳。

高 QPS 低延迟的 KV 查询结构，与 AI 推理服务的特征缓存、向量粗排索引同构。如果题目改成「支持按域名前缀批量失效」，你会调整哪个结构？欢迎写出你的方案。

参考资料

Node.js v22.x 官方 API 文档（文中代码运行环境为 Node.js 22.15.0，Map 的插入序迭代等行为以此为准） — https://nodejs.org/docs/latest-v22.x/api/

历史题目复盘：设计一个每秒 5000 次查询的 DNS 缓存，数据结构怎么选

参考资料

相关阅读