工程学习台

主题

主要章节

并发综合：访问序 LRU、令牌桶与接纳控制 ​

基线：OpenJDK 17u jdk-17.0.12+7，本机实验运行 Oracle JDK 17.0.12。本页保留并发推导与可检查实验；可运行的纯编码题单由 #33 承接，不在这里复制第二份讲解。

目标与不变量 ​

本单元把集合、锁、时间与线程池组合成一个可以检查的协议。高级必会是实现并解释线性化点；架构师进阶是说明单机正确实现放入多实例服务后，哪些保证不再成立。

LRU 的不变量不是“用了 Map 和链表”：每个键恰好对应一个节点；Map 的键集合等于链表节点集合；相邻节点双向指针相互对应；头到尾按最近访问时间排序；对外可观察时容量不超过上限。必须先定义成功读取、更新已有键、未命中、删除是否改变顺序。实验选择成功 get 和 put 更新热度，未命中不改变，禁止 null 键值，容量必须大于零。

限流器的不变量要写成可验证的时间命题：在任意区间内最多接纳多少请求、桶容量允许多大的突发、时钟回退或实例扩缩容时保证是否仍成立。只写“用了令牌桶”不是协议。

LinkedHashMap 源码解析：一次读取也可能写链表 ​

固定版本的 LinkedHashMap.java 保留 HashMap 桶结构，并让 Entry 增加 before / after。查找仍走哈希桶；accessOrder 开启时，命中后的 get 会调用 afterNodeAccess，把非尾节点移到尾部。put 的创建与更新路径分别通过 afterNodeInsertion、afterNodeAccess 维护淘汰和访问顺序。

下面是教学调用链，不是原样源码：

教学伪代码text
get(key) → HashMap.getNode → 未命中：返回 null
                          → 命中且 accessOrder：afterNodeAccess → 移至 tail
put(key,value) → putVal → 已存在：更新值并 afterNodeAccess
                      → 新建：加入桶和链表 → afterNodeInsertion
afterNodeInsertion → removeEldestEntry 为 true 时删除 head

关键分支：当前命中已经在 tail 时无需搬移；否则同时修改前驱、后继、head/tail，属于结构变化。因此“get 是读操作，可以只加读锁”对 access-order LRU 是错误答案。该实现本身不提供并发保护，迭代器 fail-fast 也不是安全性协议。源码注释及 afterNodeAccess 的 modCount 更新可用于验证这个边界。

手写 Map + 双向链表时，若两个线程先后读到相同旧前驱，再分别移动节点，即使 Map 是 ConcurrentHashMap，链表仍可能断裂。把两个组件各自做成线程安全容器，不能得到整体原子性。

原码：读命中为什么也要同步 ​

原码连续摘录（仅统一公共缩进，截取方法）：LinkedHashMap.java，jdk-17.0.12+7，L439–L446。

原码java
public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

未命中直接返回；命中且 accessOrder 开启时先 afterNodeAccess 再返回值。结构修改发生在 get 内，所以不能用读锁并发执行这些命中。后面的实验实现再以同一监视器保护查找、移动与淘汰，原容器不会替组合协议自动加锁。

最小正确实现与扩展边界 ​

实验用同一监视器保护 get、put 和 keys 快照。put 在一个临界区内更新 Map、调整顺序、必要时删除最老项，其他线程不能观察中间的超容量状态。可以把线性化点选在临界区内完成该操作最终状态变更的位置；get 命中需要将读取值和热度变化看成同一个操作。

教学伪代码java
// 教学简化；完整校验、快照方法见 AlgorithmProbe.java。
synchronized void put(K key, V value) {
    entries.put(key, value);       // entries 使用 accessOrder=true
    if (entries.size() > capacity) {
        var it = entries.entrySet().iterator();
        it.next();
        it.remove();              // 删除最久未访问项
    }
}

全局锁便于证明，却使热点命中也串行。分段 LRU 降低争用，但只能保证段内顺序，不能宣称精确全局 LRU；异步批量更新热度也是近似策略。选择时要比较命中率、锁等待、分配、淘汰吞吐，而不只报单线程 O(1)。按条数限容还不能控制字节数，value 大小不均时需要权重、对象保留图和内存上限。

缓存装载不可把慢 IO 无限制放进全局锁。先解锁装载又会发生同键击穿，需单键合并、失败清理与并发额度；无界保存每个 key 的 Future 会把缓存问题转成内存问题。返回可变 value 后，对象内容也不自动受 LRU 的锁保护。

限流算法先问语义 ​

固定窗口在窗口内累加，跨边界重置；若每秒允许 100 次，前一秒最后 1ms 和后一秒最初 1ms 各 100 次，可以短时间通过 200 次。它满足固定桶计数，不满足“任意连续一秒最多 100 次”。

滑动日志保存时间戳并移除窗口外请求，语义精确但状态和删除成本随请求量增长。滑动窗口分桶节省空间，需要明确离散近似误差。令牌桶则约束持续速率并允许有限突发：桶容量 B、补充速率 r，在任意长度 Δt 的区间内，可接纳量至多约为 B+rΔt（离散计数再取整数界）。它不保证输出等间隔，也不保证“任意一秒最多 r 次”。漏桶若指固定速率排出，还必须说明缓冲长度与队满处理，不能用名称替代协议。

令牌桶实现：时间与余额是一笔事务 ​

实验模型状态为 tokens、last，使用注入的单调时钟。一次 acquire 必须原子完成：

教学伪代码text
elapsed = now - last
tokens = min(capacity, tokens + elapsed * ratePerNano)
last = now
if tokens < 1: reject
else: tokens -= 1; accept

“补充”和“消费”分开用原子变量仍会重复消费；两个线程可能同时看到 tokens=1 并都成功。可以锁住整段，也可 CAS 更新不可变的“余额＋时间戳”状态对，失败时重新计算，不能只重试减法。实验选择 synchronized，获得一个清晰的线性化顺序。

不能每次用整数截断补充量再把 last 更新到 now：速率每秒 2 个、每 0.25 秒请求一次时，每次补充 0.5 被丢弃，桶会长期不恢复。实验保留小数余额；严格计费可改成定点整数并保留余数，同时检查乘法溢出。浮点教学实现不适合任意巨大容量、极小速率或财务精度要求。

使用 wall clock 会受校时影响。nanoTime 适合计算经过时间，不适合跨进程比较或持久化绝对时刻；实验假设时间差在 long 可表达范围内且不倒退。时钟回退在模型中显式报错。进程重启时满桶意味着额外突发，要把初始化策略写入限流契约。

从限流器到资源接纳 ​

令牌桶控制入口速率，不直接控制在途数量。若接纳 1000/s、平均处理时间从 20ms 增至 2s，稳定近似下在途量会从 20 增至 2000；继续按原速率放行仍会耗尽线程和连接。应同时设计并发上限、有界队列、deadline、拒绝反馈与恢复放量。超时已返回不代表后台任务停止，取消必须配合可中断 IO 或明确的副作用确认协议。

假设 10 个实例各设 100/s，均匀负载下总上限约 1000/s；扩容到 20 个却不改配置，上限会翻倍。集中原子配额利于全局控制，但依赖远端存储延迟与故障策略；分配本地配额降低每请求协调成本，却引入配额闲置、租约回收和短期超发边界。要求硬上限时，应证明所有实例可用配额之和以及配额转移协议，不以“Redis 原子”掩盖复制、故障转移和超时未知结果。

图：访问序与令牌状态 ​

访问序 LRU 的链表搬移与令牌桶的原子状态转换

左图强调一次命中 get 也会写链表；两个线程同时搬移不同节点时，旧的 prev/next 关系会让链表断裂。右图强调 tokens 与 last 属于同一个状态转换，拆成两个原子变量会让两个请求同时消费最后一个令牌。

实验：LRU 顺序与令牌并发 ​

从仓库根目录运行：

实验代码bash
JAVA_HOME=/Library/Java/JavaVirtualMachines/jdk-17.jdk/Contents/Home \
  bash labs/java-senior/run.sh algorithms

本轮实际输出：

text
PASS LRU get/update order, bounded capacity, eviction
PASS token bucket: atomic burst=3, fractional refill retained, idle cap

实验覆盖两组断言：容量 2，put A/B、get A、put C 后 B 被淘汰；更新 A 后顺序为 C/A。满桶容量 3、速率 2/s，冻结时钟让 64 个并发请求争抢，只成功 3 个；0.25s 时不能通过，0.5s 时补足一个并通过；长时间空闲也只能再通过 3 个。

LRU 断言是受控顺序测试；令牌桶包含并发接纳测试。它们不等价于对所有线程交错的形式化证明，也没有测量生产吞吐。扩展练习是用屏障强制两个线程同时消费最后一个令牌，先展示错误版本的超发，再验证修正；压测要同时记录拒绝率、排队年龄、P99 和有效完成量。

竞争时间线：断链与双花 ​

时间线程 T1线程 T2链表状态
t1get(A)，记住旧前驱 B—B ↔ A ↔ C
t2—get(C)，记住旧前驱 A两者都持有旧视图
t3移动 A 到 tail—B ↔ C ↔ A
t4—按旧前驱 A移动 C指针互相覆盖，可能断链或丢节点
时间线程 T1线程 T2tokens / last
t1读 tokens=1—1，last=t0
t2—读 tokens=1两个线程都认为可消费
t3扣减并写 0—0
t4—扣减并写 0两个请求通过，只应通过一个

正确实现把每一步的读取、补充、扣减与 last 更新放进同一临界区，或 CAS 一个包含两者快照的不可变状态；失败方必须重新读取，而不是重试旧减法。

闭卷验收 ​

本页 10 道闭卷题收进了下方自测面板：先回忆，再展开参考答案与评分点，最后给三档自评。

架构师追问 ​

将流量改为大租户占 80%、昂贵请求耗时为普通请求 20 倍、配额中心不可用 30 秒。分别给出按租户公平、按成本加权、资源隔离与故障策略。参考方向是全局保护＋租户额度＋昂贵请求并发隔离；fail-open 保可用但可能压垮下游，fail-closed 保资源却扩大拒绝，预分配应限制失联期间可消费额度。要求写出最大暴露量和恢复时避免同步突发的方法。Google SRE 的过载处理 说明了按资源成本而非仅按 QPS 判断负载的必要性。

来源与版本 ​

来源版本用途
Java SE 17 LinkedHashMap APIJava SE 17访问序、removeEldestEntry 与 fail-fast 边界
OpenJDK 17u LinkedHashMapjdk-17.0.12+7get 命中后的 afterNodeAccess（L439–L446）
Java SE 17 ConcurrentHashMap APIJava SE 17单键原子边界，不覆盖跨结构不变量
Java SE 17 System.nanoTimeJava SE 17单调时间差的适用范围
Google SRE：Handling OverloadSRE Book按资源成本判断过载与接纳
本地 AlgorithmProbeOracle JDK 17.0.12LRU 顺序/淘汰与令牌桶并发突发实测

访问日期：2026-10-23。限流模型是教学实现，不宣称生产吞吐或跨实例硬上限；集群配额仍需单独的故障与失联验证。

工程学习台　阅读讲解，学后自主自测。记录保存在本机浏览器。