理解 Cache Line 缓存行
理解缓存行是进行高性能编程（例如数据库内核）的基石。如果你忽略了它，即使算法复杂度最优，程序性能也可能因为频繁的缓存未命中（Cache Miss）而下降 10 倍甚至 100 倍。
为什么需要缓存行
CPU 访问内存的速度远慢于访问缓存的速度。为了弥补这个差距，CPU 不会一次只从内存读取 1 个字节，而是一次性读取一整块连续的数据到缓存中。这个一次性读取的最小单位就是 cache line 缓存行。其大小一般为 64 字节。
可通过以下命令查看缓存行大小。
postgres@slpc:~$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64可通过代码获取缓存行大小。
#include<unistd.h>
long cache_line_size = sysconf(_SC_LEVEL1_DCACHE_LINESIZE);当你访问内存地址 0x1000 的一个整数（4 字节）时，CPU 会把 0x1000 到 0x103F（共 64 字节）的数据全部加载到 L1 缓存中。如果你接下来访问 0x1004, 0x1008… 这些数据已经在缓存里了（缓存命中），速度极快。这就是空间局部性 (Spatial Locality) 的硬件实现。
如果 L1 缓存没命中，则需要等待从下一级缓存（L2/L3）或主内存（DRAM）加载整个 64 字节的缓存行。
如何查看 CPU 缓存大小
可通过 lscpu 命令查看。
postgres@slpc:~$ lscpu | grep -i cache
L1d cache: 384 KiB (8 instances) # L1 数据缓存大小
L1i cache: 256 KiB (8 instances) # L1 指令缓存大小
L2 cache: 10 MiB (8 instances) # L2 缓存大小
L3 cache: 36 MiB (2 instances) # L3 缓存大小
# 查看 CPU0 的 L1 缓存大小
postgres@slpc:~$ cat /sys/devices/system/cpu/cpu0/cache/index0/size
48K缓存未命中的代价
这里我们编写一个数组和链表在遍历时的性能对比，整体上，数组的缓存命中率更高，虽然它们的算法复杂度相同，都是 O(N)，但是因为数组的缓存命中率更高，所以性能更好。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdint.h>
#define ARRAY_SIZE 1000000
#define CACHE_LINE_SIZE 64
// 数组结构
typedef struct {
int* data;
size_t size;
} Array;
// 创建并初始化数组
Array* create_array(size_t size) {
Array* arr = (Array*)malloc(sizeof(Array));
arr->size = size;
arr->data = (int*)malloc(size * sizeof(int));
// 初始化数据
for (size_t i = 0; i < size; i++) {
arr->data[i] = i % 1000;
}
return arr;
}
// 释放数组
void free_array(Array* arr) {
free(arr->data);
free(arr);
}
// 遍历数组并求和
long long traverse_array(Array* arr) {
long long sum = 0;
for (size_t i = 0; i < arr->size; i++) {
sum += arr->data[i];
}
return sum;
}
// 链表节点定义
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建普通链表
Node* create_linked_list(size_t size) {
if (size == 0) return NULL;
Node* head = (Node*)malloc(sizeof(Node));
head->data = 0;
head->next = NULL;
Node* current = head;
for (size_t i = 1; i < size; i++) {
current->next = (Node*)malloc(sizeof(Node));
current = current->next;
current->data = i % 1000;
current->next = NULL;
}
return head;
}
// 释放普通链表
void free_linked_list(Node* head) {
while (head != NULL) {
Node* temp = head;
head = head->next;
free(temp);
}
}
// 遍历普通链表并求和
long long traverse_linked_list(Node* head) {
long long sum = 0;
Node* current = head;
while (current != NULL) {
sum += current->data;
current = current->next;
}
return sum;
}
// 性能测试函数
typedef long long (*TraverseFunc)(void*);
void benchmark(const char* name, TraverseFunc func, void* data, int iterations) {
clock_t start = clock();
long long result = 0;
for (int i = 0; i < iterations; i++) {
result += func(data);
}
clock_t end = clock();
double time_ms = (double)(end - start) / CLOCKS_PER_SEC * 1000;
printf("%-30s: %8.3f ms (总和=%lld)\n", name, time_ms, result);
}
int main() {
printf("╔════════════════════════════════════════════════════════╗\n");
printf("║ 数组 vs 链表：缓存性能对比测试 ║\n");
printf("╚════════════════════════════════════════════════════════╝\n\n");
// 设置随机种子
srand(time(NULL));
printf("测试规模：%d 个元素\n\n", ARRAY_SIZE);
// 创建数据结构
printf("正在创建数据结构...\n");
Array* array = create_array(ARRAY_SIZE);
Node* linked_list = create_linked_list(ARRAY_SIZE);
printf("✓ 数据结构创建完成\n\n");
// 测试次数
int iterations = 100;
printf("=== 顺序遍历性能测试 ===\n");
benchmark("数组 (连续内存)", (TraverseFunc)traverse_array, array, iterations);
benchmark("链表 (普通分配)", (TraverseFunc)traverse_linked_list, linked_list, iterations);
printf("\n");
// 清理内存
printf("正在清理内存...\n");
free_array(array);
free_linked_list(linked_list);
printf("✓ 清理完成\n\n");
return 0;
}
执行结果：
╔════════════════════════════════════════════════════════╗
║ 数组 vs 链表：缓存性能对比测试 ║
╚════════════════════════════════════════════════════════╝
测试规模：1000000 个元素
正在创建数据结构...
✓ 数据结构创建完成
=== 顺序遍历性能测试 ===
数组 (连续内存) : 28.274 ms (总和=49950000000)
链表 (普通分配) : 340.064 ms (总和=49950000000)
正在清理内存...
✓ 清理完成对比它们的性能，发现相差十倍还多，核心原因就是链表的指针跳转导致大量缓存未命中，而数组是连续内存，所以缓存命中率更高。
具体的可通过 perf 工具来查看缓存的引用和未命中次数，比如：
# 统计程序运行时的缓存引用和未命中次数
perf stat -e cache-references,cache-misses ./your_program因为虚拟机无法访问物理 CPU 的硬件性能计数器，所以我们通过软件模拟的方式来观察，可通过 valgrind（cachegrind）工具来模拟程序在 CPU 缓存中的行为。
root@slpc:/home/postgres/works/my-github/dbnotes/cpu# valgrind --tool=cachegrind --cache-sim=yes ./array
==10443== Cachegrind, a high-precision tracing profiler
==10443== Copyright (C) 2002-2017, and GNU GPL'd, by Nicholas Nethercote et al.
==10443== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==10443== Command: ./array
==10443==
--10443-- Warning: Cannot auto-detect cache config, using defaults.
--10443-- Run with -v to see.
╔════════════════════════════════════════════════════════╗
║ 数组 vs 链表：缓存性能对比测试 ║
╚════════════════════════════════════════════════════════╝
测试规模：1000000 个元素
正在创建数据结构...
✓ 数据结构创建完成
=== 顺序遍历性能测试 ===
数组 (连续内存) : 905.899 ms (总和=49950000000)
正在清理内存...
✓ 清理完成
==10443==
==10443== I refs: 512,166,121
==10443== I1 misses: 1,542
==10443== LLi misses: 1,525
==10443== I1 miss rate: 0.00%
==10443== LLi miss rate: 0.00%
==10443==
==10443== D refs: 101,055,817 (100,040,083 rd + 1,015,734 wr)
==10443== D1 misses: 6,314,563 ( 6,251,637 rd + 62,926 wr)
==10443== LLd misses: 6,314,402 ( 6,251,492 rd + 62,910 wr)
==10443== D1 miss rate: 6.2% ( 6.2% + 6.2% )
==10443== LLd miss rate: 6.2% ( 6.2% + 6.2% )
==10443==
==10443== LL refs: 6,316,105 ( 6,253,179 rd + 62,926 wr)
==10443== LL misses: 6,315,927 ( 6,253,017 rd + 62,910 wr)
==10443== LL miss rate: 1.0% ( 1.0% + 6.2% )
root@slpc:/home/postgres/works/my-github/dbnotes/cpu# valgrind --tool=cachegrind --cache-sim=yes ./list
==11420== Cachegrind, a high-precision tracing profiler
==11420== Copyright (C) 2002-2017, and GNU GPL'd, by Nicholas Nethercote et al.
==11420== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==11420== Command: ./list
==11420==
--11420-- Warning: Cannot auto-detect cache config, using defaults.
--11420-- Run with -v to see.
╔════════════════════════════════════════════════════════╗
║ 数组 vs 链表：缓存性能对比测试 ║
╚════════════════════════════════════════════════════════╝
测试规模：1000000 个元素
正在创建数据结构...
==11420== brk segment overflow in thread #1: can't grow to 0x4859000
==11420== (see section Limitations in user manual)
==11420== NOTE: further instances of this message will not be shown
✓ 数据结构创建完成
=== 顺序遍历性能测试 ===
链表 (普通分配) : 1486.941 ms (总和=49950000000)
正在清理内存...
✓ 清理完成
==11420==
==11420== I refs: 823,180,518
==11420== I1 misses: 1,541
==11420== LLi misses: 1,525
==11420== I1 miss rate: 0.00%
==11420== LLi miss rate: 0.00%
==11420==
==11420== D refs: 306,061,821 (270,043,788 rd + 36,018,033 wr)
==11420== D1 misses: 51,016,462 ( 50,515,889 rd + 500,573 wr)
==11420== LLd misses: 51,003,183 ( 50,502,690 rd + 500,493 wr)
==11420== D1 miss rate: 16.7% ( 18.7% + 1.4% )
==11420== LLd miss rate: 16.7% ( 18.7% + 1.4% )
==11420==
==11420== LL refs: 51,018,003 ( 50,517,430 rd + 500,573 wr)
==11420== LL misses: 51,004,708 ( 50,504,215 rd + 500,493 wr)
==11420== LL miss rate: 4.5% ( 4.6% + 1.4% )两者对比，显然，数组相比链表缓存命中率高。
==10443== D1 miss rate: 6.2% ( 6.2% + 6.2% ) # 数组缓存未命中率
==11420== D1 miss rate: 16.7% ( 18.7% + 1.4% ) # 链表缓存未命中率MESI 协议
MESI 协议是现代多核 CPU 中用于维护缓存一致性的最核心机制。在多核 CPU 中，每个核都有自己的私有 L1/L2 缓存，而 L3 缓存是多个核共享的。这就会产生缓存一致性问题，为了解决这个问题，引入 MESI 协议，MESI 协议给每个缓存行标记了四种状态：
| 状态 | 名称 | 含义 (通俗解释) | 数据一致性 |
|---|---|---|---|
| M | Modified (已修改) | “脏数据，我独有” 数据已被修改，与主存不一致。只有当前核心有这份数据，其他核心必须来问我拿。 | 与主存不一致 |
| E | Exclusive (独占) | “干净数据，我独有” 数据与主存一致，且只有当前核心拥有。我可以随意修改它，不需要通知别人。 | 与主存一致 |
| S | Shared (共享) | “干净数据，大家都有” 数据与主存一致，且可能有其他核心也缓存了这份数据。修改前必须先通知大家作废。 | 与主存一致 |
| I | Invalid (无效) | “垃圾数据” 这份数据已经过时了（被别人改了），我不能用，必须重新去读。 | 无效 |
MESI 协议依赖总线嗅探技术。你可以把系统总线想象成一个广播频道。
- 动作：当核心 A 想要读写内存时，它会在总线上发出信号。
- 嗅探：核心 B、C、D 都在”监听”这个频道。
- 响应：如果发现核心 A 要修改的数据，自己手里也有一份（处于 S 状态），核心 B 就会把自己的那份标记为 I (无效)。
假设有一个变量 x = 10 存储在内存中，核心 A 和核心 B 都要操作它。
阶段一：初始读取 (E 状态)
- 动作：核心 A 读取 x。
- 结果：总线发现没有其他核心缓存 x。
- 状态：核心 A 的缓存行标记为 E (独占)。
- 含义：A 拥有最新数据，且是唯一的，数据是干净的。
阶段二：共享读取 (S 状态)
- 动作：核心 B 也读取 x。
- 过程：核心 B 发出读请求。核心 A 嗅探到这个请求，发现”哎，我也有这个数据”。核心 A 告诉总线：“我也有，给你一份”。
- 状态：核心 A 和核心 B 的缓存行都变为 S (共享)。
- 含义：大家都有这份数据，谁都不能随便改。
阶段三：写入操作 (S → M 状态)
- 动作：核心 A 想要执行 x = 20。
- 过程：核心 A 向总线发送无效化请求：“我要改 x 了，你们手里的都作废！” 核心 B 嗅探到请求，立即将自己的 x 标记为 I (无效)。核心 A 收到确认后，修改自己的缓存数据。
- 状态：核心 A 变为 M (修改)，核心 B 变为 I (无效)。
- 含义：此时核心 A 的数据是最新的（20），但主内存里还是旧的（10）。只有当核心 A 把这个数据换出时，才会写回内存。
伪共享
伪共享是因为 MESI 协议而造成的，是多核编程中的性能杀手。
现象：
- 变量 a 和变量 b 是两个完全不同的变量，互不相关。
- 但它们靠得很近，刚好落在同一个缓存行（通常 64 字节）里。
- 核心 1 频繁修改 a，核心 2 频繁修改 b。
MESI 的视角：
- 缓存一致性协议是以缓存行为单位的，它不知道 a 和 b 是独立的。
- 核心 1 修改 a → 整个缓存行失效 → 核心 2 的缓存行变 I。
- 核心 2 修改 b → 整个缓存行失效 → 核心 1 的缓存行变 I。
后果：
- 两个核心虽然操作不同变量，却在疯狂地互相”踢”对方的缓存行。
- 缓存行在核心间来回 bouncing（乒乓效应），导致性能急剧下降。
解决方案：缓存行填充 (Padding)。在变量间插入无用的字节，强制让它们位于不同的缓存行。
// ❌ 错误示范：伪共享
struct Counter {
long long val1; // 线程 1 写
long long val2; // 线程 2 写
// 如果 val1 和 val2 地址相邻，它们很可能在同一个 64 字节行里
};
// ✅ 正确示范：使用 padding 隔离
struct Counter {
long long val1;
char pad[64 - sizeof(long long)]; // 填充，确保下一个变量在下一行
long long val2;
};
// C++ 标准写法 (alignas)
struct AlignedCounter {
alignas(64) long long val1;
alignas(64) long long val2;
};缓存行对齐
如果一个数据结构（如锁、热点计数器）跨越了两个缓存行，访问它可能需要加载两次缓存，或者引发额外的缓存一致性流量。
最佳实践：将高频访问的小对象（如自旋锁、原子计数器）对齐到 64 字节边界。
struct SpinLock {
std::atomic<int> flag;
// 确保整个结构体占满一行并对齐，避免与其他数据共享
} __attribute__((aligned(64))); 如何观测缓存的状态
我们是无法直接读取 CPU 中 L1/L2/L3 缓存中的内容的，但可以借助工具间接了解缓存是否命中等信息。
现代 CPU 内部有专门的硬件计数器，可以统计缓存的行为（如命中率、未命中数）。
# 统计程序运行时的缓存引用和未命中次数
perf stat -e cache-references,cache-misses ./your_programPostgreSQL 数据库中缓存行优化
在数据库这类基础软件中，对性能要求极高，缓存行优化是在内核设计中必须要考虑的点。
如下，解释了 PG 中缓存行 cache line 的大小设置为了 128，而不是 64，这是为了 PG 能够适配不同的硬件平台，虽然当前 x86 缓存行是 64 字节，但已有部分 ARM 架构（例如鲲鹏 920 处理器的 CacheLine 为 128 字节）等缓存行已经是 128 位，以及为了后续能够适应硬件架构的演进，这里 PG 将缓存行大小保守性的设置为了 128 位。
/*
* Assumed cache line size. This doesn't affect correctness, but can be used
* for low-level optimizations. Currently, this is used to pad some data
* structures in xlog.c, to ensure that highly-contended fields are on
* different cache lines. Too small a value can hurt performance due to false
* sharing, while the only downside of too large a value is a few bytes of
* wasted memory. The default is 128, which should be large enough for all
* supported platforms.
*/
#define PG_CACHE_LINE_SIZE 128锁非常影响性能，对此 PG 进行了优化，以 PG 中的轻量锁 LWLock 为例，轻量锁的主要作用是保护共享内存中的变量，由于 PG 是多进程结构，因此轻量锁的使用特别频繁，它的实现在 PG 中有着非常重要的地位。C 语言中联合体的大小由最大的成员决定，而将 LWLockPadded 定义为联合体，无论 LWLock 内部多么紧凑，一旦放入 LWLockPadded，它就被填充到了 128 字节。
typedef struct LWLock
{
uint16 tranche; /* tranche ID */
// 原子变量，保存轻量锁的状态
pg_atomic_uint32 state; /* state of exclusive/nonexclusive lockers */
// 轻量锁的等待者链表
proclist_head waiters; /* list of waiting PGPROCs */
} LWLock;
/*
在大多数情况下，将每一批（tranche）轻量级锁（LWLock）按缓存行边界对齐，并让数组步长（stride）为 2 的幂次，是理想的做法。
这不仅能节省索引寻址时的几个 CPU 周期，更重要的是能确保单个轻量级锁不会跨缓存行边界。这有助于减少缓存争用问题，尤其是在 AMD Opteron 处理器上。
在某些场景下，添加更多填充（padding）以使每个 LWLock 占据整个缓存行也是有用的；
例如，在主 LWLock 数组中，当锁的总数较少但某些锁的争用非常激烈时，这种做法就很有价值。
*/
#define LWLOCK_PADDED_SIZE PG_CACHE_LINE_SIZE
/* LWLock, padded to a full cache line size */
typedef union LWLockPadded
{
LWLock lock;
char pad[LWLOCK_PADDED_SIZE];
} LWLockPadded;WAL 插入锁也是通过缓存行对齐，确保锁本身不发生伪共享。
typedef struct
{
LWLock lock;
XLogRecPtr insertingAt;
XLogRecPtr lastImportantAt;
} WALInsertLock;
typedef union WALInsertLockPadded
{
WALInsertLock l;
char pad[PG_CACHE_LINE_SIZE];
} WALInsertLockPadded;