坠星书阁

核心机制#

将内存划分为大小均为 2 的幂 的块，通过分裂与合并管理空闲块。

分配流程#

1. 请求大小向上取整到 2 的幂
2. 从对应空闲链表取块
3. 若无则分裂更大块，将伙伴插入低一级链表

释放流程#

1. 将块放回链表
2. 检查伙伴是否空闲
3. 若是则合并并继续向上合并

优缺点#

定位#

构建于伙伴系统之上的对象缓存管理器。

核心结构#

Cache（管理器）

• 为特定大小/类型对象创建的管理器
• 维护三个链表：
  • slabs_full：完全使用的 slab
  • slabs_partial：部分使用的 slab
  • slabs_free：完全空闲的 slab

Slab（内存块）

• 连续内存块（通常一个或多个页）
• 划分为等大小对象
• 包含空闲链表等元数据

工作流程#

分配

1. 优先从 slabs_partial 取 slab
2. 再从 slab 空闲链表取对象
3. 若无则从 slabs_free 取或向伙伴系统申请新 slab

释放

1. 对象放回 slab 空闲链表
2. 根据空闲数量调整 slab 所在链表
3. 若 slab 完全空闲可能归还伙伴系统

优势#

• 减少伙伴系统调用
• 降低内部碎片
• 显著提升内核对象分配性能

Slab 分配器 ≠ Redis 缓存#

• Slab：内核内存管理组件，缓存内核对象
• Redis：用户态数据库，其内部可能借鉴 Slab 思想，但层次与目的不同

Cache 与 Slab 的关系#

• Cache（如 kmem_cache）：是管理器，管理多个 slab
• Slab：是被管理的实际内存块

核心要求#

• get 和 put 操作均达到 O(1) 时间复杂度
• 准确维护数据的访问顺序

数据结构设计#

采用双向链表 + 哈希表的组合：

1
┌────────────────────────────────────────┐
2
│  双向链表（存储数据）                   │
3
│  ┌──────┐    ┌──────┐    ┌──────┐     │
4
│  │ Head │◄──►│ Node │◄──►│ Tail │     │
5
│  └──────┘    └──────┘    └──────┘     │
6
│     ▲                                    │
7
│     │ 索引                               │
8
│     ▼                                    │
9
│  哈希表（快速定位）                      │
10
│  key ──► node 指针                       │
11
└────────────────────────────────────────┘

• 双向链表：每个节点存储键值对，prev 和 next 指针串联
  • 头部：最近使用的节点
  • 尾部：最久未使用的节点
• 哈希表：数组 + 链地址法，快速定位键对应的链表节点

核心操作流程#

get(key)

1. 通过哈希表定位节点
2. 若存在：将节点移动到链表头部，返回值
3. 若不存在：返回 -1

put(key, value)

1. 检查键是否已存在
   • 存在：更新值，移动到头部
   • 不存在：创建新节点插入头部，存入哈希表
2. 若超过容量：移除尾部节点，从哈希表删除

关键代码逻辑#

常见误区澄清#

数据结构本质#

跳表是一种概率平衡的多层有序链表：

• 底层（第 0 层）包含所有节点
• 向上每一层是下一层的随机子集
• 节点层数由几何分布随机决定（常用概率 p=0.5）

1
Level 3:     ┌─────┐
2
             │  4  │
3
Level 2:     ├─────┤────────┐
4
             │  4  │   7    │
5
Level 1:     ├─────┤───┐    ├─────┐
6
             │  4  │ 6 │    │  9  │
7
Level 0: ┌───┼─────┼───┼────┼─────┼─────┐
8
         │ 1 │  4  │ 6 │ 7  │  9  │ 10  │
9
         └───┴─────┴───┴────┴─────┴─────┘

核心操作#

查找

1. 从最高层开始
2. 在当前层向右移动直到下一节点 key ≥ 目标
3. 下降一层，重复至底层
4. 路径确定，无回溯

插入

1. 查找确定每层的前驱节点（update 数组）
2. 随机生成新节点层数 k
3. 将新节点插入第 0 到第 k 层
4. 若 k 超过当前层数，提升跳表层数

删除

1. 类似查找定位节点
2. 在各层将其从链表中移除
3. 可能降低跳表层数

随机性作用#

• 仅用于插入时决定节点层数，保证高层节点稀少，形成”快速通道”
• 查找过程完全确定，依靠高层稀疏性实现跳跃
• 平均时间复杂度 O(log n)
• 随机化替代了平衡树复杂的旋转操作

关键设计细节#

性能与特点#

核心原理#

数据结构

• 长度为 m 的位数组（初始全 0）
• k 个独立的哈希函数

添加元素

• 对元素计算 k 个哈希值
• 将位数组对应位置设为 1

查询元素

• 计算同样的 k 个哈希位置：
  • 若所有位均为 1 → 可能存在（存在假阳性）
  • 若任意一位为 0 → 一定不存在（无假阴性）

实现关键点#

哈希函数设计

• 通常用双哈希法（如 FNV-1a + DJB2）生成 k 个独立哈希值

参数优化

1
m = -n·ln(p) / (ln2)²    # 位数组大小
2
k = (m/n)·ln2            # 哈希函数个数

其中 n 为预期元素数，p 为可接受的误判率

位操作

• 使用 []byte 存储位
• 通过 idx/8 定位字节，1 << (idx%8) 定位位掩码

本质作用#

• 极简布尔判断：返回”可能存在”或”一定不存在”
• 用极小的空间（每个元素仅占数比特）实现海量数据的存在性过滤
• 允许假阳性，但杜绝假阴性

优缺点#

典型应用场景#

• 缓存穿透防护
• 数据库查询优化
• 网络爬虫 URL 去重
• 垃圾邮件/恶意 URL 过滤
• 分布式系统（HBase、Cassandra、Redis）

核心思想#

先写日志，后写数据

• 所有修改操作必须先在日志文件中记录完整信息
• 强制落盘（fsync）后才能应用到内存/数据存储

崩溃恢复

• 系统重启后，通过重放日志文件中的操作
• 使数据恢复到崩溃前的一致状态

原子性与持久性

• 保证事务的持久性（已提交的操作不会丢失）
• 保证原子性（部分写入的日志在恢复时会被丢弃）

设计要点#

日志记录格式

• 序列号、操作类型（SET/DELETE）、键、值（仅 SET）、校验和
• 采用固定长度结构，方便直接读写

校验和

• 使用简单的 XOR 对记录关键字段计算
• 用于检测日志是否完整（防止部分写入）

写入流程

1. wal_append：追加记录到文件缓冲区
2. wal_sync：调用 fflush + fsync 强制落盘
3. 日志落盘成功后，更新实际存储

恢复流程

1. 顺序读取日志文件
2. 对每条记录重新计算校验和
3. 校验通过的记录通过回调函数应用到存储（重放操作）
4. 遇到校验失败则停止恢复

SSTable 基础设计#

文件结构

1
┌─────────────┬─────────────┬─────────────┐
2
│   数据区    │   索引区    │  尾部元数据  │
3
└─────────────┴─────────────┴─────────────┘

• 数据区：键长度(4B) + 键数据 + 值长度(4B) + 值数据
• 索引区：键长度(4B) + 键数据 + 偏移量(4B)
• 尾部元数据：index_offset（索引区起始偏移）、num_entries（记录数）

查找流程

1. 读取尾部元数据
2. 将索引区全部加载到内存
3. 二分查找定位键
4. 根据偏移量读取键值对

写入流程（两阶段）

1. sstable_writer_add：顺序追加数据区
2. sstable_writer_finish：构建索引并写入索引区和元数据

结合跳表与 WAL：LSM 树引擎#

写入路径

1
写入请求 → WAL（保证持久性） → 跳表（MemTable）
2
                ↓
3
         Flush（后台写入 SSTable）

读取路径

1
查询请求 → MemTable → Immutable MemTable → SSTable 文件（多层）
2
                ↓
3
         合并结果返回最新版本

持久化与恢复

• 系统启动时，重放 WAL 中的日志
• 重建内存中的 MemTable
• 使用 fsync 控制持久化时机

后台合并 (Compaction)

• 定期将多个 SSTable 文件合并
• 清除过期数据，降低读放大和空间放大

核心思想#

读写不对称

• 读者不阻塞写者
• 写者通过原子替换将新数据”发布”
• 旧数据被隔离，等待所有可能仍在访问旧数据的读者完成（宽限期）
• 最后安全释放旧数据

宽限期 (Grace Period)#

C 语言实现

• 全局 epoch 计数器与每线程的活跃标志
• 写者递增 epoch，遍历所有线程
• 等待旧 epoch 内进入临界区的读者全部退出

Go 语言实现

• 两个原子计数器分别记录两个 epoch 的活跃读者数
• 写者等待对应 epoch 的计数器归零

核心约束

• 读者在临界区内不能阻塞或睡眠
• 否则会导致宽限期无限延长

内存模型与内存屏障#

C11 标准

• 显式使用 atomic_thread_fence 或带有内存顺序的原子操作（acquire/release）
• rcu_read_lock：acquire 屏障确保临界区内读操作不会提前到锁之前
• rcu_read_unlock：release 屏障防止读操作延迟到锁之后
• rcu_assign_pointer：全屏障保证新数据初始化完成后再发布指针

Go 语言

• sync/atomic 包自动插入必要的内存屏障
• 开发者仍需理解语义，正确编排逻辑顺序

C vs Go 实现差异#

公平性本质#

CFS 摒弃传统优先级队列，引入虚拟运行时间 (vruntime) 作为唯一调度依据。

nice → 权重映射#

vruntime 更新公式#

1
inc = delta_ms × BASE_WEIGHT / weight

• 高权重进程的 inc 小，vruntime 增长缓慢
• 低权重进程增长快

最小堆实现调度队列#

• 所有就绪进程按 vruntime 组织成最小堆
• 堆顶始终是 vruntime 最小的进程
• 调度时直接取出堆顶运行
• 运行后重新计算 vruntime 并插入堆中

优先级隐式体现#

代码中没有显式的优先级比较，而是通过：

1. 权重影响 vruntime 增长速率
2. 堆选择 vruntime 最小的进程
3. 最终实现高权重进程被频繁调度

核心机制#

epoll 是 Linux 下高效的 I/O 多路复用技术，通过三个系统调用实现：

可以同时管理成千上万个连接，只在事件发生时通知应用程序，避免了轮询开销。

C 语言实现要点#

• 将监听 socket 和客户端 socket 设为非阻塞
• 选择边缘触发 (ET) 模式以获得更高效率
• 事件循环中，epoll_wait 返回后遍历就绪事件
• 对监听 socket 调用 accept 接受新连接
• 对客户端 socket 循环读写直到返回 EAGAIN
• 处理 EPOLLERR 和 EPOLLHUP 事件，及时关闭异常连接

Go 语言实现路径#

直接使用 syscall

• 使用 syscall 或 golang.org/x/sys/unix 包
• 代码结构与 C 版本类似，语法更简洁
• 借助 defer 方便资源释放

推荐使用标准库 net 包

• 在 Linux 底层同样基于 epoll
• 封装成同步阻塞风格的 goroutine-per-connection 模型
• 每个连接启动一个 goroutine
• 调用 conn.Read/Write 时，Go 运行时自动挂起 goroutine
• 开发者无需手动处理非阻塞、事件循环和 EAGAIN

手动 epoll vs net 包#

事件触发与处理流程#

1
网卡数据到达
2
    ↓
3
协议栈处理 → socket 接收缓冲区
4
    ↓
5
内核检查 socket 是否被 epoll 监控
6
    ↓
7
满足注册事件 → 加入就绪队列 → 唤醒等待线程
8
    ↓
9
epoll_wait 返回 → 遍历就绪事件数组
10
    ↓
11
根据 fd 类型分发：监听 socket / 客户端 socket

核心思想#

把哈希空间想象成一个数轴（0 ~ 2³²-1）：

• 所有真实节点通过虚拟节点在数轴上各自占据一些位置
• 把这些位置按数值从小到大排序，得到一个有序的数组

查找 key 的归属#

1. 给定 key，算出哈希值 h
2. 在有序数组里，找到第一个哈希值 ≥ h 的虚拟节点
3. 若 h 比所有哈希值都大，则回到数组的第一个元素（数轴首尾相连）

偏移量描述

• 计算 h 与每个虚拟节点哈希值的差值（偏移量）
• 找到差值最小且 ≥0 的节点
• 若所有差值 <0，则取绝对值最小的差值（对应第一个节点）

节点增减的影响#

加入新节点

• 生成一批虚拟节点，在数轴上插入新的哈希位置
• 原来落在这些新位置附近的 key，会”偏移”到新节点上
• 其他 key 的归属保持不变

移除节点

• 原本指向该节点虚拟位置的 key 会偏移到顺时针方向的下一个节点

虚拟节点的作用#

• 让每个真实节点在数轴上拥有多个”锚点”（多个哈希值）
• 就像给每个真实节点分配一组均匀分布的偏移位置
• 使整个数轴被划分成更小的区间
• 每个真实节点管理的区间总长度大致相等，实现负载均衡

核心思想#

基于概率传播的去中心化信息扩散机制：

• 每个节点周期性随机选择少量其他节点交换自身状态
• 通过冗余通信实现最终一致性

与全广播的对比#

Gossip vs Raft#

反熵机制#

• 每次通信交换完整或增量状态
• 接收方将新信息合并到本地成员表
• 信息在节点间单向增长，直至所有节点掌握全集
• 超时机制剔除故障节点，使信息量有界且自适应

C 语言实现难点#

状态机与并发

• Raft 节点有 Follower、Candidate、Leader 三种角色
• 状态转换需要严格保护
• 采用单线程事件驱动模型，通过 epoll 统一管理网络、定时器和用户输入

网络通信

• 使用 UDP 作为传输层
• 自行处理消息的序列化、粘包与拆包
• 消息格式采用简单的二进制结构
• 使用 htonl/ntohl 保证字节序一致

持久化

• 日志、任期、投票信息必须持久化
• 使用 open + write + fsync 保证数据落盘
• 通过临时文件 + rename 实现原子更新
• 快照机制用于压缩日志

定时器与选举

• 选举超时和心跳定时器通过 Linux timerfd 实现
• 与 epoll 集成，实现高精度、非阻塞的计时
• 每个节点独立随机生成选举超时时间

C vs Go 实现对比#

核心设计#

线程本地缓存

• 每个线程独立拥有一组空闲对象链表
• 分别对应不同的大小类
• 绝大多数分配和释放操作仅在本地缓存进行，完全无需加锁
• 只有本地缓存为空或过满时，才与中央缓存交互

分层缓存结构

1
┌─────────────────────────────────────┐
2
│         线程本地缓存                 │  ← 无锁，单链表存储空闲对象
3
├─────────────────────────────────────┤
4
│         中央缓存                     │  ← 全局互斥锁保护，Span 为单位
5
├─────────────────────────────────────┤
6
│         页堆                         │  ← 向操作系统申请/释放虚拟内存
7
└─────────────────────────────────────┘

大小类与对齐策略

• 小对象尺寸划分为一系列大小类（8, 16, 32, 64, 128, …）
• 请求分配时向上取整到最近的大小类
• 减少内部碎片

Span 与对象管理

• Span：一组连续的物理页
• 一个 Span 可被切分为多个相同大小的小对象
• 中央缓存以 Span 为单位存储空闲对象
• 当 Span 内所有对象都空闲时，可归还给页堆

地址映射 (PageMap)

• 从内存地址到所属 Span 的快速查找结构
• 通过任意指针可以常数时间定位到 Span
• 实现高效释放的关键

性能特点#

• 多核可伸缩性：数百线程场景下依然保持低锁争用
• 吞吐量随核心数线性扩展
• 支持将空闲内存主动归还给操作系统

核心思想#

利用数据中的重复模式，将重复出现的字符串替换为一个匹配对：

• 偏移量 (offset)：指向历史窗口中相同字符串的距离
• 长度 (length)：重复字符串的长度

滑动窗口与哈希表加速#

• 维护固定大小的滑动窗口（历史缓冲区）
• 使用环形缓冲区避免数据移动
• 引入哈希表：将窗口中每个可能匹配位置的三字节哈希值记录在表中
• 压缩时对当前位置计算哈希，直接在表中查找可能匹配的位置

偏移量的关键角色#

与文法压缩的联系#

• “八个1”的表达方式与形式语言中的重复规则相似
• LZ77 实际上是基于有限上下文的引用
• 文法压缩（如 Sequitur）能够提取更复杂的重复模式
• 揭示了数据压缩与计算理论（形式语言）之间的内在关联

MVCC vs xv6 COW 的异同#

MVCC vs Git 的类比#

本质区别

• Git：有向无环图（DAG），支持分支、合并、人工冲突解决，适用于离线协作
• MVCC：单调递增的全局提交时间戳，版本历史呈线性，通过写冲突检测自动回滚事务

线性历史 vs DAG#