解读

面试官把“小程序本地缓存上限 2 MB”当成一个硬性资源约束，要求候选人在如此小的容量里实现 LRU（最近最少使用）淘汰，并给出“命中率 ≥90%”的量化指标。
这不仅是算法题，更是性能测试视角的容量规划题：

1. 2 MB 是“总预算”，必须先把“字节”作为度量单位，而不是“条数”。
2. 90% 命中率是 SLA，需要可验证的测试方法，而不是拍脑袋。
3. 小程序运行环境无 C++ STL、无 Java LinkedHashMap，只能依赖 JS 基础 API，还要考虑 setStorageSync 的同步阻塞代价。
4. 性能测试工程师要给出“如何压测、如何采样、如何报告”的完整闭环，否则方案不可落地。

知识点

1. 小程序存储模型
   • wx.setStorageSync 最大单键 1 MB，总配额 10 MB，但业务线通常只给 2 MB，防止用户侧爆涨。
   • 同步接口会阻塞渲染线程，连续写入 >5 ms 就可能掉帧，必须批量合并。
2. 字节级 LRU 实现
   • 需要双向链表 + HashMap 的经典结构，但节点里存的是“字节长度”而不是“个数”。
   • 每次写入前做“预算预扣”，如果超限，从尾节点向前累加字节，直到释放足够空间，再整体写入，保证事务性。
3. 命中率定义
   • 命中率 = 字节命中 / 总字节请求。
   • 测试阶段用“真实用户 trace 回放”或“泊松+Zipf 合成流量”灌入，跑 30 min，置信区间 95%。
4. 容量规划公式
   • 根据 Zipf 偏斜系数 α≈0.9 估算：欲使命中率 ≥90%，热数据累积体积 Vh 需 ≥ 总数据体积 Vt 的 18%。
   • 2 MB 对应 Vt ≤ 11 MB 即可达标；若 Vt 更大，需前置过滤或分层缓存（内存+本地+网络）。
5. 性能测试脚本设计
   • 用 miniprogram-automator 起 20 个并发小程序实例，循环回放 1 万条请求，打点每次缓存命中/缺失、耗时、CPU。
   • 输出两条曲线：命中率-时间、卡顿-时间，验证 90% 线是否平稳，且掉帧率 <1%。

答案

1. 数据结构
   维护一个双向链表，节点结构：{key, value, size, prev, next}；同时用 Map<key, node> 做 O(1) 查找。
2. 写入流程
   a. 计算新条目字节数：size = new Blob([value]).size + key.length2。
   b. 如果 Map 已存在该 key，先删除旧节点并扣减 usedSize。
   c. 检查 usedSize + size > 21024*1024，循环删除 tail 节点，直到预算足够。
   d. 头部插入新节点，Map 更新，usedSize += size。
   e. 延迟刷盘：每 50 ms 或 16 个变更批量 wx.setStorageSync({‘lru_meta’: JSON.stringify(serializedList)})，降低掉帧。
3. 读取流程
   Map 命中则把节点移到链表头，返回 value；未命中返回 null，并上报埋点。
4. 命中率测试
   步骤 A：线上采样 7 天，得到 100 万条真实请求序列，按用户 session 分组。
   步骤 B：本地用 Node 版小程序容器回放，把本地缓存设成 2 MB，跑 10 轮，每轮 30 min。
   步骤 C：统计字节命中率 = servedFromCache / totalBytes；若均值 ≥90%，且 95% 置信区间半宽 <0.5%，则通过。
   步骤 D：同时监控 setStorageSync 单次耗时，P99 < 4 ms，掉帧率 <1%，否则回退批量策略。
5. 结果示例
   在 Vt=10 MB、α=0.9 的 trace 下，实测命中率 91.3%，P99 读耗时 0.8 ms，写入抖动 2.1 ms，满足 SLA。

拓展思考

1. 分层降级
   当业务数据总量持续增长，2 MB 本地缓存已无法覆盖 18% 热数据时，可把 LRU 拆成两级：
   L1 内存 200 KB（页面存活期有效），L2 本地 2 MB，L3 网络。性能测试需给出“降级阈值”——命中率连续 3 min 低于 88% 即自动扩容到 4 MB 并触发告警。
2. 压缩与序列化
   对 JSON 值先进行 JSONB+gzip 压缩，平均节省 45% 体积，但压缩耗时 1~2 ms。性能测试需做“时间-空间”权衡曲线，找到收益拐点。
3. 预加载与热启动
   利用小程序“周期性更新”能力，在闲时把次日 95% 概率访问的 key 预拉取到本地，命中率可再提 3~5 个百分点。测试阶段需模拟 4G/5G 弱网，验证预加载对首屏启动时间影响 <50 ms。
4. 自动化回归
   把“命中率 ≥90%”写进 CI：每次 MR 触发 5 min 压测，若命中率下跌 >1%，即阻塞合并，并输出火焰图定位是哪条新增请求把热数据挤出。