Java的LongAdder实现原理

<think>我们正在讨论Java中的LongAdder类，这是一个用于高并发场景下计数的工具。根据引用，LongAdder通过分散竞争来提升性能。接下来，我将详细解释其工作原理和实现机制。 首先，LongAdder的设计目标是减少线程竞争。它采用了一个基础值（base）和一个单元格数组（cells），当没有竞争时，操作直接作用于base；当出现竞争时，会使用cells数组来分散更新。 核心思想：将单个值的更新压力分散到多个值上，最后在需要总和时进行汇总。 具体实现步骤： 1. 初始时，LongAdder内部有一个base值，所有更新操作都直接尝试更新base（通过CAS操作）。 2. 当多个线程竞争更新base时（即CAS失败），它会初始化一个cells数组（每个元素是一个Cell对象，内部是一个volatile long值），并将更新操作分散到数组的不同元素上。 3. 每个线程根据哈希算法映射到cells数组的一个位置，然后更新该位置的Cell值。这样，多个线程就可以同时更新不同的Cell，从而减少竞争。 4. 当需要获取当前总和时，将base和所有cells数组中的值相加即可。 注意：Cell数组是惰性初始化的，只有在发生竞争时才创建。此外，数组的大小会根据竞争情况动态扩展（比如从2扩容到4、8等），但不会无限扩容，有一个上限（通常是CPU核心数的一个倍数，因为超过核心数的线程数并不能真正并行）。 源码关键点（基于Java 17，具体实现可能因版本而异）： - LongAdder继承自Striped64类，Striped64中实现了核心的分段累加逻辑。 - Cell类使用@Contended注解避免伪共享（缓存行共享问题）。 - 核心方法： increment() -> 调用add(1L) add(long x) -> 尝试更新base，失败则进入cell更新逻辑 sum() -> 返回base与所有cell值的总和（注意：没有加锁，所以是一个近似值，但在没有并发更新时是准确的） 下面是一个简化的代码逻辑（非完整源码，仅展示关键步骤）： public void add(long x) { Cell[] cs; long b, v; int m; Cell c; // 首先尝试更新base if ((cs = cells) != null || !casBase(b = base, b + x)) { // 如果cells数组不为空（已经初始化过）或者更新base失败（说明有竞争），则进入 boolean uncontended = true; if (cs == null || (m = cs.length - 1) < 0 || (c = cs[getProbe() & m]) == null || !(uncontended = c.cas(v = c.value, v + x))) // 如果cells数组未初始化，或者当前线程对应的cell为空，或者更新cell失败，则调用longAccumulate方法 longAccumulate(x, null, uncontended); } } final boolean casBase(long cmp, long val) { return BASE.compareAndSet(this, cmp, val); } longAccumulate方法负责初始化cells数组，扩容，以及为线程分配cell等。 性能优势：在高并发下，多个线程可以同时更新不同的cell，从而大大减少竞争，提高吞吐量。但获取总和（sum）时，需要遍历整个cells数组，所以sum操作的开销相对较大，不适合频繁调用。 与AtomicLong比较：AtomicLong使用一个volatile变量，每次更新都需要CAS操作，高并发下CAS失败重试的开销大。而LongAdder通过分散热点，使得每个线程大部分时间操作自己独立的cell，竞争减少。 缺点：LongAdder在统计时可能会有精度损失（因为并发更新时，sum操作没有加锁，所以是某一时刻的快照，但最终一致）。另外，它占用更多的内存（cells数组）。 应用场景：适合高并发的计数，如统计请求次数、点击量等，但不适合需要精确实时获取值的场景（如控制流程）。 根据引用[4]中的例子，LongAdder常与ConcurrentHashMap结合使用，用于维护频率映射。 相关问题： §§相关问题§§ 1. LongAdder在哪些场景下比AtomicLong更有优势？ 2. LongAdder的sum()方法为什么在并发更新时不是精确的？ 3. 如何避免LongAdder中Cell数组的伪共享问题？ 4. LongAdder的初始化和扩容机制是怎样的？</think>### Java LongAdder 类的工作原理及实现机制 `LongAdder` 是 Java 并发库（`java.util.concurrent.atomic`）中用于高效处理高并发计数场景的类。其核心设计目标是通过**分散竞争**来提升性能，避免 `AtomicLong` 在高并发下的性能瓶颈[^1][^2]。以下是详细实现机制： --- #### **1. 核心设计思想** - **分散热点**：将单一共享变量的更新压力分散到多个变量（称为 `Cell`）上，减少线程竞争[^1][^5]。 - **空间换时间**：通过额外内存开销换取更高吞吐量，适用于统计场景（如计数、直方图）而非精确同步控制[^3]。 - **最终一致性**：结果不保证实时精确，但调用 `sum()` 时可获得最终一致的总和[^1]。 --- #### **2. 关键数据结构** ```java // 简化版源码（基于 OpenJDK） public class LongAdder extends Striped64 { // 基础值（无竞争时直接更新） transient volatile long base; // 动态扩容的 Cell 数组（处理竞争） transient volatile Cell[] cells; // Cell 内部类（避免伪共享） @sun.misc.Contended static final class Cell { volatile long value; Cell(long x) { value = x; } } } ``` - **`base`**：无竞争时的主计数器，通过 CAS 更新。 - **`cells` 数组**：当线程竞争 `base` 失败时，初始化数组并将更新分散到不同 `Cell` 元素[^5]。 - **`@Contended` 注解**：填充 `Cell` 的内存布局，防止 CPU 缓存行伪共享（False Sharing）[^5]。 --- #### **3. 工作流程** 以 `increment()` 为例： 1. **尝试更新 `base`** 使用 CAS 直接更新 `base`（低竞争时高效）。 ```java if (CAS(base, current, current + 1)) return; // 成功则退出 ``` 2. **竞争时转向 `cells` 数组** - 若 `cells` 未初始化，则创建大小为 2 的数组（惰性初始化）。 - 根据线程哈希值定位到某个 `Cell` 槽位： ```java int index = Thread.currentThread().hashCode() & (cells.length - 1); ``` - 对该 `Cell` 执行 CAS 更新（每个线程优先更新独立槽位）[^1][^5]。 3. **动态扩容** 若特定 `Cell` 槽位竞争仍激烈（CAS 失败），则扩容 `cells` 数组（通常翻倍），直到达到 CPU 核心数上限[^5]。 4. **求和（`sum()`）** 遍历所有 `Cell` 的值并累加到 `base`： ```java public long sum() { long sum = base; Cell[] cs = cells; if (cs != null) { for (Cell c : cs) if (c != null) sum += c.value; } return sum; // 注意：非原子快照 } ``` --- #### **4. 性能优势与代价** | **维度** | **LongAdder** | **AtomicLong** | |----------------|----------------------------------------|------------------------------| | **高并发吞吐量** | 极高（分散竞争）[^2][^5] | 低（CAS 竞争激烈时自旋开销大）| | **内存开销** | 较高（`Cell` 数组 + 填充）[^3][^5] | 低（单一变量） | | **结果精确性** | 最终一致（`sum()` 非原子）[^1] | 实时精确 | | **适用场景** | 统计计数（如 QPS 监控）[^4] | 细粒度同步控制 | --- #### **5. 典型应用场景** - **服务监控**：统计心跳请求次数（如引用[^4]的 `ServiceRegistry`）。 ```java Map<String, LongAdder> heartbeatCounters = new ConcurrentHashMap<>(); heartbeatCounters.computeIfAbsent(serviceId, k -> new LongAdder()).increment(); ``` - **频率统计**：与 `ConcurrentHashMap` 结合实现直方图（如引用[^3]）。 - **高并发计数器**：替代 `AtomicLong` 用于访问量统计等[^2][^5]。 --- #### **6. 局限性** - **非实时精确**：`sum()` 遍历时可能遗漏正在更新的值[^1]。 - **内存敏感场景慎用**：`Cell` 数组可能占用较多内存[^3]。 - **不适用于原子操作**：如比较交换（`compareAndSet`）需用 `AtomicLong`[^3]。 --- ### 相关问题