概述

本篇是《从零构建分布式索引系统 OriginDB》系列的番外篇，是 OriginDB 最底层“基础层”涉及线程安全技术的理论铺垫，OriginDB“基础层”用于为“内核层”各个功能提供数据结构和线程安全支持。

本篇主要内容涉及：CPU 缓存机制、Java 内存模型、Java 线程安全工具、常用数据结构线程安全方案。

整体架构

理论铺垫

线程安全定义

多线程并行执行，通过同步手段，保障运行正确

线程安全原则

CPU 缓存机制

多级缓存架构

- 功能

缓解 CPU 计算和读写速度不匹配问题，引入多级高速缓存（SRAM），各级缓存之间及同主内存之间均以 CacheLine（缓存行，一般 64 字节）为最小单位交换数据。

- 架构

- 性能

注：主内存访问速度：约 100ns，多 CPU 只能通过主内存共享数据，多 cpu 之间可见性成本高

- 影响

数据在多个 Cache 中存在副本，读写需要通过“缓存一致性”解决数据“可见性”问题。

MESI：缓存一致性协议

- 功能

最常见的解决“缓存一致性”的协议，通过“CacheLine 状态跟踪、写传播、事务串行化”，维护一致性。

- 状态定义

- 状态转移

MESI状态转换

核心转换流程：Shared 到 Modified 流程

• 普通场景：

• 特殊场景：

• 两个核同时写“相同的 CacheLine”，MESI 基于总线事务仲裁，保证顺序生效，对其他和顺序可见，但基于“旧数据”后写的 CacheLine 覆盖先写的“新数据”无法解决，需要通过业务手段干预，如原子操作，内存屏障等。

-协议优化

• 背景：

• CPU 写操作前消息广播等待 Acknowledge 以及其他核收到 Invalidate 设置 CacheLine 失效响应 Acknowledge，两个过程“等待”影响 CPU 效率，影响性能。

• 
  

• 方案：异步化

• 写方增加 Store Buffer（写缓冲）： 位于 L1Cache 和 L2Cache 之间，用于写 Acknowledge 过程临时缓存，cpu 继续执行其他指令，收到 Acknowledge 后，由 StoreBuffer 写入 L2Cache

• 失效方增加 Invalidate Queue（失效队列）: 收到 Invalidate 信息后，加入 队列立刻 Acknowledge，排队设置 Invalid 状态

• 影响：

• 有序性： “指令重排”，写仅放入 StoreBuffer 未完成本地 Cache 更新，CPU 继续执行后面的命令，后面命令没有冲突，先执行完。

• 可见性： Invalid 状态未及时淘汰刷新。

内存屏障命令

-作用:

解决“缓存一致性协议”，引入 Store Buffer，Invalidate Queue 引起的有序性，可见性问题。

1. 有序性： 写异步，CPU 继续执行后面命令，后面明天先于内存更新完成，即 CPU 流水线指令重排

2. 可见性： Invalid 失效异步化，造成使用旧数据

-方案：

内存屏障命令，通过强制“等待缓存刷新完成”，保证有序性和可见性，代价性能延迟 20-50 ns。

-分类：

Java 内存模型（JMM）

作用

抽象线程访问“主内存”共享变量方案，屏蔽硬件差异

分类

- 原子操作抽象

功能：

线程共享变量访问的底层原子方法和互斥方法

操作：

应用：

• 读取流程：read → load → use（主内存 → 工作内存 → CPU 寄存器）

• 写入流程：assign → store → write（CPU 寄存器 → 工作内存 → 主内存）

• 同步流程：lock → (读写操作) → unlock（确保原子性和可见性）

- 内存屏障抽象

功能：

保证有序性，可见性

分类：

Java 线程安全支持

内存屏障

- Unsafe

- VarHandle

安全工具

- 机制

- 工具

1）volatile：

机制： 打桩添加内存屏障

性能影响：

volatile 写操作（StoreLoad 屏障），等待刷新，比普通变量写慢 20-30 倍（纳秒级差异）。

2）AtomicXXX：

机制： volatile 成员变量 + Unsafe 的 cas 原子操作

AtomicInteger：

private volatile int value;
public final int getAndIncrement() {        return U.getAndAddInt(this, VALUE, 1);}

Unsafe：

public final int getAndAddInt(Object o, long offset, int delta) {    int v;    do {    //以volatile 方式获取对象 。在内存偏移量 offset 处的整数值    v = getIntVolatile(o, offset);                //CAS    } while (!weakCompareAndSetInt(o, offset, v, v + delta));    return v;}

3）Synchronized：

机制： 对象锁（对象 markword 状态）+ 内存屏障

锁升级：

注：

非 Synchronized 块读取 Synchronized 修改的共享变量，没有锁和内存屏障的保护，读取数据不确定，可能读到中间状态

4）Lock：

机制： AQS（AbstractQueuedSynchronizer）：CLH 锁的优化版本

1. CLH 锁：基于链表的自旋锁，带获取锁的线程加入链表，自旋检查前驱状态，避免检查相同对象锁缓存一致性，提高性能

2. 优化：

3. 自旋+阻塞：降低 cpu 消耗

4. 双向链表：向前自旋检查状态，向后唤醒等待线程（因为除自旋还有阻塞）

- 总结

数据结构线程安全方案

数组

- 队列

• 特点： 两端插入读取，除扩容不涉及元素移动

• 案例： Disruptor

• 方案： 无锁：CAS 读写索引 + 伪共享

- 集合

• 特点： 可中间插入删除，涉及数组元素移动，依赖 size，capacity，数组移动过程读到中间状态导致错误。

• 案例： CopyOnWriteArrayList

• 方案： 读写锁 或 CopyOnWrite

链表

• 特点： 插入删除仅影响 Previous 节点的 Next 指针

• 案例： ConcurrentLinkedQueue

• 方案： 保障可见性，volatile Node<K,V> next

树

- 二叉树

• 特点：

• 固定两个子节点指针：left，right

• 插入删除可能涉及树平衡

• 案例： ConcurrentHashMap 使用红黑树

• 解析： ConcurrentHashMap 红黑树实现：红黑树 +链表

• 插入过程：

• 红黑树插入： 仅涉及 Parent 节点的 left 或 right 指针可见性

• 链表插入： 仅涉及 Previous 节点的 next 指针的可见性

• 平衡过程： 读写互斥，此时链表已经可用

• 写锁： cas 非阻塞写锁竞争（不存在其他写线程和读线程），树平衡，读改为链表读

• 读锁： cas 非阻塞锁竞争

• 未获取读锁： 链表读，遍历每个节点，cas 尝试获取读锁，一旦获取到读锁，回根，红黑树加速读，理论 O(logN) 远远小于 O(N)，依然高效。

• 获取堵锁： 阻塞平衡，红黑树读

- B+树（n 叉树）

• 特点：

• 子节点： 插入或删除涉及节点分裂或合并

• 父节点： 子节点分裂合并，父节点需修改多个子节点指针

• 案例： B+Tree

• 方案： 锁耦合（Lock Coupling）

• 过程： 锁爬行

• 爬行策略：

• 悲观（Pessimistic Crabbing）： 写锁根，尤其树长高的过程

• 乐观（Optimistic Crabbing）： 无锁下潜，版本号对比 发现不安全时（版本更新） 写：回退并加锁重试 读：回根重来

总结