Yuerer's Blog

剖析一下 CPython 的自动垃圾回收机制，并尝试提出改进的思路。

引用计数

相信有过计算机基础的人，哪怕对垃圾回收不那么熟悉，也肯定知道引用计数这个玩意。引用计数诞生于上个世纪，其主要思想是通过给每个对象增加计数，当计数为0时，则肯定没人使用该对象，可以放心将其删除。

虽然这个方法看起来有点糙，但在实际项目中，它的优点在于可以更实时的释放内存，释放内存的时机更精确，这也是为什么有的项目会尝试给 Lua 增添一个引用计数的垃圾回收，避免内存上涨过快。

凡事都有利弊，它的缺点也很明显，无法处理循环引用。

以下用 Python 举一个非常普遍的例子。

1
2
3
4
5
6
7
8
9
10
11
12

class A:  
    pass  
  
class B:  
    pass

a = A()
b = B()
a.b = b
b.a = a
del a
del b

在上面中，我们手动删除了 a 和 b ，理应进行释放，但由于 a 和 b 互相构成了循环引用，导致其引用计数总是不为0，进而造成内存泄漏，而 CPython 对其解决方法也极其简单，就是将所有可能造成循环引用的对象，构成一个双向链表进行扫描，从 root object 出发进行扫描 - 清除，无法到达的对象就是可释放的对象，普通的对象直接采用引用计数去释放，简单快捷。

怎么去验证以上结论呢？我们可以用反证法，当 del a 和 del b 后，再调用 gc.collect() 查看其是否能被回收到，如果能回收到，说明在此时引用计数已经失效。

1
2
3
4
5
6
7
8

# 设置 debug 标签，使得垃圾回收后的对象 存放至 gc.garbage 列表中
gc.set_debug(gc.DEBUG_SAVEALL)

# 回收第0代垃圾对象
gc.collect(0)

# 打印出回收的垃圾对象
print(gc.garbage)

可以看出引用计数确实失效了，因为通过 扫描-清除 回收能回收到这两个对象。

在上一篇关于 Python3 源码剖析中，剖析 float 的实现主要是阅读的 Python 3.10 的源码，但是在我看到 PEP-659 这篇关于指令特化(Specializing Adaptive Interpreter)的提案时，我就被它吸引了，因为这就是我之前想给 Lua 提速加的功能之一，冲着对它的热情，我决定将阅读的 CPython 版本提升到 3.11 ，这一篇就来剖析一下指令特化的实现，我们将通过两个对象做加法进行分析。

对象相加

首先通过 Python 自带的 dis 工具进行分析，分析两个对象相加的流程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

from dis import *
def test():  
    a = 1.5  
    c = a + 1.3
print(dis(test))

  3           0 RESUME                   0

  4           2 LOAD_CONST               1 (1.5)
              4 STORE_FAST               0 (a)

  5           6 LOAD_FAST                0 (a)
              8 LOAD_CONST               2 (1.3)
             10 BINARY_OP                5 (*)
             14 POP_TOP
             16 LOAD_CONST               0 (None)
             18 RETURN_VALUE

可以看到两个对象相乘的指令码为 BINARY_OP ，我们跟踪到 CPython 中，可以确定会调用到 PyNumber_Add 函数中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

static const binaryfunc binary_ops[] = {
    [NB_ADD] = PyNumber_Add,
    [NB_AND] = PyNumber_And,
    .....
};
TARGET(BINARY_OP) {
    PREDICTED(BINARY_OP);
    PyObject *rhs = POP();
    PyObject *lhs = TOP();
    PyObject *res = binary_ops[oparg](lhs, rhs);
    Py_DECREF(lhs);
    Py_DECREF(rhs);
    SET_TOP(res);
    if (res == NULL) {
        goto error;
    }
    JUMPBY(INLINE_CACHE_ENTRIES_BINARY_OP);
    DISPATCH();
}

PyNumber_Add 实现也很简单，先看看这两个对象支不支持该二元运算符，不支持，则看看支不支持 concat 操作。

去年 2021 年的时候，我的工作主要集中在改进 Lua虚拟机 ，后来由于工作变动，现在主要的工作语言已经切换为了 Python ，因此打算阅读下 Python 3.10 的源码，学习一下它的设计，对比 Lua 的优势。

希望在接下来的阅读过程中，能够体会到一种 回家 的畅快感。

本篇将以 float 作为起点，了解如何创建出一个浮点对象，深入剖析 float 其内部实现。

一切皆对象

一切皆对象 这句话都要被讲烂了，但是还要讲多一次。

Python 是一门面向对象的强类型动态语言，里面的任何东西都是对象，以浮点数为例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# a 是一个浮点实例对象，类型是 float
>>> a = 3.14159
>>> type(a)
<class 'float'>

# float 也是个对象，但它是 类型对象
>>> float
<class 'float'>
>>> float()
0.0

# float这个类型对象的类型是 type
>>> type(float)
<class 'type'>

以上我们可以确定，Python 中类型也是对象。

此外所有对象的类型都是 type ，可以称其为元类。而所有对象都继承自 object 。

截止至上一次发博文已经过了接近三个月时间，这么长的一段时间我主要是去做了以下几件事情，一个是实现 Lua 多线程的垃圾回收 方案，另一个则是 LuaJIT 5.3.6 实现。其实也没用到三个月，实现代码加上测试一共花了一个月。

Lua 多线程垃圾回收

这一块的思路主要是从 Redis 通过子线程释放内存这块学来的，通过这个小优化，使得我们游戏服务器在大量玩家下线时，不再出现大规模的掉帧，效果还是非常显著的。

LuaJIT 5.3.6

之所以实现这个 Lua 5.3.6 JIT，其实是因为 LuaJIT 2.0 不支持 5.3的新扩展，而项目已经进行到了中后期，没有时间去调整代码了，最后花了半个月的时间去实现了一个小版本，通过了 Lua 的官方测试用例，也在项目用上了。性能方面提高了2-5倍，接入成本为0，不需要修改任何逻辑代码。

至于解释器部分，借鉴了 Lua 5.4 的一个小优化点，将 switch case 修改为了 computed goto ，提升了约 5% 的性能，之后可能会学习 Lua 5.4 扩展字节码。如果这个项目还做下去的话(我有时间的话)，我会想尝试解释器执行脚本时记录各个操作数的类型，实现动态替换字节码，减少不必要的类型判断，从而提升一定的解释器速度。不过这个方案风险太大，暂时先搁置。

在实现 LuaJIT 5.3.6 的过程中，顺带复习了一下编译原理的前端部分，实现了一些官方不支持的语法，比如 ‘+=’，自增表达式(当然没有提交)，还是非常有趣的。

结语

以上的代码实现已经开源，合并之前的 NOGC 优化思路，LuaJIT-5.3.6，欢迎 Star ，这对我很重要。

本篇是 Redis 6 剖析的第二篇，主要探讨 Redis 是怎么做主从同步的，对代码会有所删减。

SLAVE

通常启用主从同步，只要在从服务器执行 SLAVEOF HOST PORT 即可，这个时候就会执行到 replicaofCommand 。由于主从同步是从服务器发起的，因此我们先从 Slave 开始进行剖析。

一直觉得关系型数据库非常难用，在使用之前要先定好表的结构，中途修改存储结构，改动就会非常繁杂，特别是 外键 这玩意离开了学校就再也没见过。好在在 游戏领域 中，用的最多的都是 NoSQL 。

熟悉我风格的人，可以看出这个系列的标题，不再是 源码剖析，而是只有 剖析 两字，主要是考虑到 Redis 6.0 的代码量已经挺大了，同时网络中又有大量关于 Redis 数据结构的源码剖析，没必要再炒冷饭了。

出于以上的原因，我将 Redis 分为几个部分进行剖析和讨论。

1. 异步机制
2. 主从同步
3. 集群
4. 数据结构

本篇主要是来剖析 Redis 为了避免 阻塞 ，是如何运用 多进程 与 多线程，这两种异步机制的。

阻塞点

Redis 一般有以下几种阻塞的点。

从网络交互来看有

• 网络 I/O (多线程)
• 客户端交互 (部分删除用多线程 BIO)
• 传输 RDB 快照 (多进程)

从磁盘交互又分

• 关闭文件 (多线程 BIO)
• 记录 AOF 日志 (多线程 BIO)
• AOF 日志重写 (多进程)
• RDB 快照生成 (多进程)

前篇解析了 Gossip 协议，这篇主要看看 Raft 是如何实现的。

本文主要分为两个部分，首先是粗略讲解一遍 Raft 的设计思想，在这一部分不会将 RPC 的各种字段（因为没有意义，只会徒增心智负担），而在第二部分则是通过解析一份优质的 Raft 源码实现，在这个部分再深入到 RPC 各个字段。

如果看了一遍看不懂也没关系，建议多去看看 Raft 的论文，笔者也是反复看了两周才大致理解其指导思想。

Raft

一提到共识算法，相信大部分人都能马上想到 Paxos，但是我认为它不是算法，它的论文里面顶多算是一个指导思想，很少有人能够读完它就实现出一个可靠的共识算法（关键是要验证其的正确性），但是 Raft 不一样，它的一些设计非常巧妙，能够令人非常好的理解其指导思想，同时比较容易的实现（因为 Raft 从诞生那一刻就是为了弥补 Paxos 的可理解性，看看人家的论文名字 In Search of an Understandable Consensus Algorithm 可理解的分布式共识算法）。

用过 Zookeeper 的可能知道其内部的协议就是根据 Paxos 的指导实现的一个 Zab 算法，之所以不用 Raft 是因为 Raft 那时候还没出世呢。

一直都对分布式协议比较感兴趣，选择了 Gossip 和 Raft 作为起点，之所以这么选择有两个原因。

1. 它们足够简单。
2. 一个基于 AP ，一个基于 CP ，分别是可用性优先和一致性优先的代表。

Gossip

Gossip 协议主要通过谣言传播的形式，传播给其他节点。

我这里称 Gossip 为 协议 而不是算法是因为这只是个思想，基于这个思想有很多的变种。

Gossip 能够正常运作需要以下三种实现组合。

1. 广播
2. 反熵(Anti-entropy)
3. 谣言传播

近期在压测服务器的过程中发现内存随着用户数增加而暴涨，用户数减少内存却没有释放回内核，一开始怀疑是内存泄漏，后面上了工具排查，最终定位到是 glibc 的内存管理并没有将内存释放给OS，为了解决这个问题，对 ptmalloc2 进行了剖析。

本篇中，不谈论 brk 和 mmap 系统调用的使用方法，默认环境为 Linux-x86-64，讨论的 ptmalloc2 的版本为 glibc 2.17 的版本。

chunk

ptmalloc2 分配给用户的内存都以 chunk 来表示，可以理解为 chunk 为分配释放内存的载体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#ifndef INTERNAL_SIZE_T
#define INTERNAL_SIZE_T size_t
#endif

/* The corresponding word size */
#define SIZE_SZ                (sizeof(INTERNAL_SIZE_T))

struct malloc_chunk {
  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
// -----------------------------------------------------------------------
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

chunk 由以上几部分组成， INTERNAL_SIZE_T 为 size_t 为了屏蔽平台之间的差异，这里只谈论64位平台，为8字节。

1. prev_size 代表着上一个 chunk 的大小，是否有效取决于 size 的属性位 P。
2. size 代表当前 chunk 的大小和属性，其中低3位为属性位 [A|M|P]。
3. 当这个 chunk 为空闲时，则会使用 fd, bk 将其加入链表中管理。
4. 同上， fd_nextsize bk_nextsize 只用在 large bin 中，表示 上/下一个大小的指针，加快链表遍历。

最近接手的一个游戏项目是重 Lua 的结构（网络模块在 C++，其余逻辑全在 Lua）。和许多用 Lua 的游戏项目一样，遇到了 Lua 的垃圾回收的性能问题，经常跑着跑着就会掉帧，因此花了一周的时间，给 Lua 虚拟机写了个模块，把 Lua 垃圾回收的速度提高了一个量级。

思路

这个思路其实在之前的一篇博客中也有提到，想要 垃圾回收快，无非就那么几种思路。

1. 使用内存池
2. 减少对象生成
3. 垃圾回收提速

使用内存池

第一种思路，我觉得不合理，因为现代的内存分配器早就有内存池的设计了，手写一个内存池的收益并不大。

减少对象生成

第二种思路，是比较合理的。因为我在项目的代码中发现很多处地方有动态生成 Closure 的情况。

1
2
3
4
5
6
7

function test()
  local fn = function()
    print("test")
  end
  fn()
  fn()
end

上面那个例子，每次调用到 test 函数的时候，都会动态根据 fn 的 函数原型，生成一个 Closure

可能有人会问，Proto 不是有一个 cache 指向 Closure 吗？按道理这里 没有 UpValue（即代表UpValue 完全相同），应该会复用啊，但是很可惜，执行完这个函数以后，因为没有对象指向 Closure 用完再不久的将来又会被回收。

因此，少写这种代码就可以减少对象的生成。

垃圾回收提速

第三种思路，我的想法是，让垃圾回收所要遍历的对象大幅减少，就可以为垃圾回收提速了，由于我们是重 Lua 的框架，因此我们的所有配置都存在于 Lua 的 table中，而这一部分肯定是不需要被回收的，但是每次垃圾回收的时候，又会不停的扫描递归遍历，不合理。同时代码中的很多全局函数，也是根本不需要被回收的，也会被扫描到，于是就想到一个想法，给这些对象打上标记，让他们不被遍历不被清理，就可以大幅度的提速了。

原理简单，但是做起来确实挺难受的，要注意要手动关闭 UpValue 将其保留下来。

目前已经开源，LuaJIT-5.3.6源码。