Month: 七月 2018

蛤?什么是 raft 协议?

Raft 协议是一个分布式的一致性协议,主要通过 Leader Election 和 Log Replication 两个步骤来实现高可用的一致性状态存储。

这篇文章并不是 Raft 协议的一个完整介绍,只是其中核心概念的一个总结概括,要完全理解所有细节还是得看论文。

Leader 选举

  1. 每个节点有三种状态:follower、candidate、leader。
  2. 作为 leader 有任期(term)的概念,根据基本法必须选举上台。Term 是一个自增的数字。
  3. 作为 leader 要不断发送心跳给 follower,告诉他们一律不得经商。
  4. 所有节点都有一个随机的定时器(150ms~300ms),当 follower 没有收到日志后就会升级为 candidate,term + 1,给自己投一票,并且发送 Request Vote RPC 给所有节点,也就是 apply for professor 啦。
  5. 节点收到 Request Vote 后,如果自己还没有投票,而且比自己在的任期大,那就说明水平比自己高到不知道哪里去了,就投票出去,否则拒绝。
  6. 如果节点发现自己的票超过了一半,就吟两句诗,钦点自己是 leader 了
  7. 新的 leader 上台后,继续发送日志昭告天下,其他的 candidate 自动灰溜溜的变为 follower 了。

日志复制(Log Replication)

  1. 所有的请求都发送给 leader,一律由中央负责。
  2. leader 把收到的请求首先添加到自己的日志当中
  3. 然后发送 Append Entries RPC 给所有的 follower,要求他们也添加这条日志
  4. 当大多数的节点都添加这条日志之后,leader 上这条日志就变为了 commited
  5. leader 再发送给所有的节点,告诉他们这条日志 commited
  6. leader 返回给客户端,告诉他请求成功

分区容忍

如果网络发生了分区,也就是另立中央了,那么 raft 的日志复制机制也可以保证一致性。

比如下图中,由于中间的网络分区,出现了两个 leader,这之后如果给下面的 leader(Node B)中发送请求,因为它向一个节点中同步日志,所以只能获得两个节点的确认,因此提交失败。而如果向上面的leader 中发送请求,可以向两个节点中同步日志,也就是说一共三个节点都是同步的,那么就提交成功。不会出现两个 leader 分叉的情况。

参考资料:

  1. Raft 动画演示
  2. Raft 论文

LSM 和 sstable

核心要点

lsm 是 bigtable、leveldb、rocksdb 等数据库采用的算法。

硬盘,尤其是机械硬盘,顺序写入性能远大于随机写入性能,所以 lsm 把大量的随机写入抓换成了顺序写入,从而极大地又花了写入能力。同时查找效率收到了损伤。

适用于顺序写入多,随机读取少的场景。

之所以要使用 Immutable Memtable,就是为了避免将 MemTable 中的内容序列化到磁盘中时会阻塞写操作。

操作

  1. 插入

    写入 WAL,然后操作 memtable。WAL 是顺序读写,而 memtable 是跳表,操作都很迅速

  2. 更新

    和插入其实是一样的操作

  3. 删除

    插入一条特殊的删除日志,在 memtable 中标记删除

  4. compaction(压缩)

    当 memtable 达到设定的阈值的时候,会写入到 immutable memtable,然后写入到硬盘上的 sstable。当 sstable 的数量达到某个阈值的时候,就合并到下一级的 memtable。需要注意的是只有第一级的 memtable 可能有重复的键值,其他层都不会有重复的,所以可以多线程 compact。

  5. 读取

    最原始的算法:首先从 memtable 读,然后从 sstable 中往高层读取。

    可以采取的优化方法:

    1. 把 sstable 的一些原始信息放到 manifest 中,放在内存中,快速查找
    2. 使用 bloom filter 先过滤一遍,看 key 是否在 LSM 中,然后再查找。

一图胜千言:

参考:

  1. http://blog.fatedier.com/2016/06/15/learn-lsm-tree/

MySQL 性能小技巧和在 Django 中的应用

对于 delete update insert 等语句一定要使用 limit 子句限制影响的行数,避免一次更改特别多的行,造成数据库假死

while (1) {
    // 每次只做 1000 条
    mysql_query("DELETE FROM logs WHERE log_date <= "2009-11-01" LIMIT 1000");
    if (mysql_affected_rows() == 0) {
        // 没得可删了,退出!
        break;
    }
    // 每次都要休息一会儿
    usleep(50000);
}

2. 垂直分割

把不会用作索引的,或者是过长的字段可以考虑使用其他存储引擎,比如 rocksdb 等。

3. IPv4 地址可以存为 uint32

使用 uint32 存储 IP 地址不光可以节省空间,而且可以按区间查询。

4. 避免 select *

从数据库里读出越多的数据,那么查询就会变得越慢。并且,如果你的数据库服务器和应用服务器是两台独立的服务器的话,这还会增加网络传输的负载。

所以,你应该养成一个需要什么就取什么的好的习惯。

不要使用:

SELECT * FROM user WHERE user_id = 1

使用:

SELECT username FROM user WHERE user_id = 1

在 django 中,可以使用 only

books = Book.objects.filter(author="Jim").only("book_name")

5. 当只要一行数据时使用 LIMIT 1

当你查询表的有些时候,你已经知道结果只会有一条结果,但因为你可能需要去 fetch 游标,或是你也许会去检查返回的记录数。

在这种情况下,加上 LIMIT 1 可以增加性能。这样一样,MySQL 数据库引擎会在找到一条数据后停止搜索,而不是继续往后查少下一条符合记录的数据。

下面的示例,只是为了找一下是否有“中国”的用户,很明显,后面的会比前面的更有效率。(请注意,第一条中是 Select *,第二条是 Select 1)

SELECT * FROM user WHERE country = "China"
SELECT 1 FROM user WHERE country = "China" LIMIT 1

在 Django 中可以使用 [:1] 来添加 limit 1

6. EXPLAIN 你的 SELECT 查询

使用 EXPLAIN 关键字可以让你知道 MySQL 是如何处理你的 SQL 语句的。这可以帮你分析你的查询语句或是表结构的性能瓶颈。

7. 尽量让查询能 fit 进内存中

参考:

  1. https://coolshell.cn/articles/1846.html

每个程序员都应该知道的延迟数字

动作 | 时间 | 换算
—————————-|—————-| —
L1 缓存访问 | 0.5 ns | 0.5ns
分支预测错误 | 5 ns | 5ns
L2 缓存访问 | 7 ns | 7ns
互斥锁/解锁 | 25 ns | 25ns
内存访问 | 100 ns | 100ns
使用 Zippy压缩 1KiB | 3,000 ns | 3 µs
通过 1 Gbps 网络发送 2KiB | 20,000 ns | 20 µs
SSD 随机读取 | 150,000 ns | 150 µs
内存中连续读取 1 MB | 250,000 ns | 250 µs
同一个数据中心的来回 | 500,000 ns | 0.5 ms
从 SSD 上连续读取 1 MB* | 1,000,000 ns | 1 ms
机械磁盘寻道 | 10,000,000 ns | 10 ms
机械磁盘连续读取 1 MB | 20,000,000 ns | 20 ms
发送数据包 加州->荷兰->加州 | 150,000,000 ns | 150 ms

  • 假设 ~1GB/sec SSD

如果把这些时长都乘以 10 亿的话:

动作 | 时长 | 相当于
—————————-| ———–| —-
L1 缓存访问 | 0.5 s | 一次心跳 (0.5 s)
分支预测错误 | 5 s | 打个哈欠
L2 缓存访问 | 7 s | 打个长哈欠
互斥锁/解锁 | 25 s | 冲一杯咖啡
内存访问 | 100 s | 刷牙
使用 Zippy压缩 1KiB | 50 min | 一集电视剧(包括广告)
通过 1 Gbps 网络发送 2KiB | 5.5 hr | 从午餐到下午工作结束
SSD 随机读取 | 1.7 days | 一个普通的周末
内存中连续读取 1 MB | 2.9 days | 一个长周末
同一个数据中心的来回 | 5.8 days | 一个普通假期
从 SSD 上连续读取 1 MB* | 11.6 days | 等快递等了两周
机械磁盘寻道 | 16.5 weeks | 大学里的一个学期
机械磁盘连续读取 1 MB | 7.8 months | 几乎能造个人了
上面两个加起来 | 1 year | 整整一年
发送数据包 加州->荷兰->加州 | 4.8 years | 快能读个博士了

可视化网页:
https://people.eecs.berkeley.edu/~rcs/research/interactive_latency.html

这些数字的作用是什么?

了解这些时间的量级有助于比较不同的解决方案。通过这些数字,你可以看出来从远程服务器的内存中读一些数据时比直接从硬盘上读取快的。在一般的程序中,这也就意味着使用磁盘存储比使用数据库服务器要慢,因为数据库通常把所有东西都放在内存里了。而且这也说明了为什么在服务全球客户的时候 CDN 至关重要。从北美到欧洲的一个 ping 就要花上 100+ ms,所以从地理上来说,内容应该是分布式部署的。

The idea is more about knowing the scale of time it takes to help compare different solution. With those number you can see that it’s faster to get data in memory from a distant server than to read the same data from disk. In common application that means using disk storage is less efficient that storing it in a database on an other server, since it usually keeps almost everything in memory. It also tells a lot about why CDN are needed if you are serving client worldwide. A ping from North America to Europe will always takes 100+ ms, so having geographically distributed content is a good idea.

对于互斥锁的开启锁定时间
mutex lock/unlock time is important for anyone writing code that depends on code that is accessing the same data structures at the same time. If you don’t know that there is a considerable cost to writing such code, now you do; and this number can quantify it.

还需要注意顺序读写和批量读写带来的提速

常见问题

随着摩尔定律的发展,这些数字会不会不太准确了?

首先摩尔定律基本上经失效了。其次,这些数字的重点是他们之间的比例,而不是具体数字。

延迟, 带宽和吞吐之间的区别和联系?

Tube

  • 延迟表示通过管道需要花费的时间
  • 带宽表示管道的宽度
  • 每秒钟流过的水的数量就是吞吐

吞吐 = 延迟 x 带宽

然而不幸的是, 吞吐这个词经常被用作两个意思. 有时候吞吐的意思是指的系统总荷载, 有时候又指
的是每秒吞吐量, 也就是带宽(当然单位不同).

参考:

  1. https://gist.github.com/hellerbarde/2843375
  2. https://softwareengineering.stackexchange.com/questions/312485/how-can-jeff-deans-latency-numbers-every-programmer-should-know-be-accurate-i
  3. https://stackoverflow.com/questions/36949735/what-is-the-difference-between-latency-bandwidth-and-throughput

MySQL 中的 wait_timeout 是做什么的?

Mysql 中默认的 waittimeout 和 interactivetimeout 的值是八小时,也就是一个连接(交互式和非交互式的)只有在 8 小时没有活动之后才会被关闭掉。对于互联网公司来说,这个值实在太大了,一个库可能被很多脚本和服务访问,可能只是一个简短的查询就不需要数据库了,如果每个查询都占据了 8 小时的时间,那么 mysql 很快连接数就会满了,报出 too many connections 错误。

mysql 默认的连接数可以修改 max_connections 参数,但是一个服务器能支撑的连接数显然是由硬件决定的。

设置 waittimeout 过短可能会造成一些问题,如果在 django 中两次查询的之间时间大于 waittimeout,就会报 (2006, ‘MySQL server has gone away’)。django 官方给的建议是:

  1. 当你的脚本不需要使用数据库的时候,主动关闭连接,比如在 django 中使用 from django.db import connection; connection.close()
  2. 增大 wait_timeout 的值

不过 django 默认 CONNMAXAGE 是 0,也就是在查询数据库之后会立即关闭链接,理论上应该不会报这个错误。但是这样不能复用链接,会造成对数据压力很大。

CONNMAXAGE 应该小于数据库本身的最大连接时间 wait_timeout,否则应用程序可能会获取到连接超时的数据库连接,这时会出现 MySQL server has gone away 的报错。

可以在 settings.py 中动态地获取并填充这个值,然后写到 CONNMAXAGE 中

理论上这样就不会再报错了,但是难免数据库重启或者什么时候会报错,总是使用 closeoldconnections 还是很烦。

有一种思路是在检测到和数据库链接断开的时候,自动重连,但是这样会破坏 django.db.atomic,但是可以实现一种不同的 backend。可以参考这两个:

  1. https://github.com/django/django/pull/2740/commits/38f58aa4d751ad83f1dc76d5b945a1036239584f

  2. https://github.com/django/django/pull/2454/commits/36b8bf870cab183b7ad63c0d8e7e8c02e314a053#diff-f8a587a973ef4c3a94d7550a5b85342c

还有一种解决思路是使用 connection pooling,我们可以使用 sqlalchemy 的 连接池作为 django 连接数据库的工具。参考这里, 不过这种方法比较 hack。

参考

  1. https://code.djangoproject.com/ticket/21597#no2
  2. https://github.com/django/django/commit/2ee21d9f0d9eaed0494f3b9cd4b5bc9beffffae5
  3. https://stackoverflow.com/questions/1125504/django-persistent-database-connection
  4. django 优化
  5. https://docs.djangoproject.com/en/2.1/ref/databases/#persistent-connections
  6. 如何设置 max_age

动态规划(LeetCode 413. Arithmetic Slices)

LeetCode 413. Arithmetic Slice

是一道可以用动态规划解的问题

题目

给定一个数组,找出其中等差数列的个数。等差数列的定义:3 各元素以上,每个元素之间差相等。

比如:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

下面的就不是:

1, 1, 2, 5, 7

例子:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

解法

观察发现,当我们遍历数组的时候,如果能和前一个元素构成等差数列,那么在这个位置可以构成的等差数列的个数就是上一个位置加一,所以的到递推公式:

dp[i] = dp[i-1] + 1

借用官方答案里的图片:

所以我们就得到了答案:

class Solution:
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        dp = [0] * len(A)
        for i in range(2, len(A)):
            if A[i] - A[i-1] == A[i-1] - A[i-2]:
                dp[i] = dp[i-1] + 1

        return sum(dp)

彭博到底是做什么生意的?

一句话:卖彭博终端机

为什么大家要买彭博终端机呢?界面那么老土

I think most of your questions can be answered by realizing that Bloomberg was founded in 1981, and they basically got a monopoly in financial data provision because there were no other options in 1981. That is why they have a custom monitor & keyboard: in the days before the IBM PC, everyone had a custom monitor & keyboard, because these things were not standardized. Bloomberg was a technologist & businessman before he was a politician; his business success gave him the money to run for office, his office doesn’t force people to pay for Bloomberg.

The reason they’re still a monopoly is because knowing how to navigate a Bloomberg is a critical skill for most finance professionals, and now that they have that skillset, they can be very productive moving around in it. A different (better?) UI would require they re-learn everything, which is not going to happen. And when financial professionals are making half a million a year, paying $24k/year for a terminal so that they can be productive isn’t a bad investment.
(Source: have a couple friends at Bloomberg. One is in their UI department, and keeps having his proposals for better UIs shot down for business reasons. Also married a financial professional who had to use a Bloomberg in her days as a bond trader.)

The best way to think about the Bloomberg terminal is a web browser that connects you to a private network. (Bloomberg actually is the largest known private network.) Once connected, you have access to thousands of “web apps” – which Bloomberg users call “functions”. Instead of a URL, you use a short 2 to 5 letter mnemonic code for each function, such as “MSG” for email, or “TOP” for top news. These different functions provide all sorts of various functionality – most of them are of course related to financial information. Functions like “CDSW” are for analyzing credit default swaps, “SDLC” gives you supply chain data for different companies, other functions analyze or curate Twitter, others correlate news events with historical stock data, etc. There are also many non-financial functions as well that reflect the “social network” aspect of the Bloomberg terminal, such as “POSH” which is basically a high-end Craigs list, or “DINE” which is a high-end Yelp.
All-in-all, the Bloomberg Terminal is like a private Internet for financial professionals.

核心的依赖可能是 bloomberg chat,相当于金融圈的社交网络。

“I think Facebook is the best comparison,” Ayzerov says. “If Facebook had only one fourth of your friends, you wouldn’t use it. The advantage of Bloomberg is that every financial person has it.””

Wow, great comments about Bloomberg. It makes me wonder, is there similar system for Cryptocoins traders?

Bloomberg would be very hard to dethrone. It’s key selling point is all of the data they have access to, which takes forever to setup integration with all of those providers. They continually expand data sources as well so it’s not like they are asleep at the wheel.
Finally, Bloomberg chat has strong network effects so even if you had all of the same data, many traders still wouldn’t switch to you because they can’t communicate with others still on Bloomberg.

  1. It is a all-in-one news source. There are a lot of features that allow you to monitor the news from many different sources in real time.
  2. It is a social network. The built-in chat and email service is really basic. But, just about every one working in Finance is on it, with their contact details and resumes. As a trader, you can legally close financial transactions on the Bloomberg chat, as one would over the phone.
  3. It is a data sharing platform. Banks and other market participants contribute to Bloomberg data by sending information that is normally not visible in the market. For instance FX volatilities are quoted by banks on bloomberg in real time. This information is only available in few places.
  4. It is an API that allows its users to use its data for custom analytics.
  5. It is an execution platform, where you can book trades, follow their values and risk when the market moves, etc.
  6. It is open to 3rd parties: some banks and other data vendors have their own pages on bloomberg (which I never had access to).
  7. It has many many other stuffs. There is a restaurant review system. There is a classified section. There are things to monitor the weather. It has videos, maps, it’s just huge.

redis 常见问题

主要参考这篇文章:https://mp.weixin.qq.com/s/vS8IMgBIrfGpZYNUwtXrPQ

1. 集合操作避免范围过大

使用 sortedset、set、list、hash 等集合类的 O(N) 操作时要评估当前元素个数的规模以及将来的增长规模,对于短期就可能变为大集合的 key,要预估 O(N) 操作的元素数量,避免全量操作,可以使用 HSCAN、SSCAN、ZSCAN 进行渐进操作。集合元素数量过大在使用过程中会影响 redis 的实际性能,元素个数建议尽量不要超过 5000,元素数量过大可考虑拆分成多个 key 进行处理。

2. 合理使用过期时间

如果 key 没有设置超时时间,会导致一直占用内存。对于可以预估使用生命周期的 key 应当设置合理的过期时间或在最后一次操作时进行清理,避免垃圾数据残留 redis。redis 不是垃圾桶。

3. 利用批量操作命令

假设要给一个集合导入 5000 个元素:

方案 1:直接使用 redis 的 HSET 逐个设置

for _ in 0..5000
    HSET hash, k,v

结果:失败。redis ops 飙升,同时接口响应超时

方案 2:改用 redis 的 HMSET 一次将所有元素设置到 hash 中

map<k, v> = 50000 个元素
HMSET hash map

结果:失败。出现 redis 慢日志

方案 3:依然使用 HMSET,只是每次设置 500 个,循环 100 次

map_chunk<k, v> = 500 个元素
for i in 0..100
    HMSET hash map_chunk[i]

结果:成功

MSET/HMSET 等都支持一次输入多个 key,LPUSH/RPUSH/SADD 等命令都支持一次输入多个 value, 也要注意每次操作数量不要过多,建议控制在 500 个以内

4. 合理设置值的大小

String 类型尽量控制在 10KB 以内。虽然 redis 对单个 key 可以缓存的对象长度能够支持的很大,但是实际使用场合一定要合理拆分过大的缓存项,1k 基本是 redis 性能的一个拐点。当缓存项超过 10k、100k、1m 性能下降会特别明显。关于吞吐量与数据大小的关系可见下面官方网站提供的示意图。

在局域网环境下只要传输的包不超过一个 MTU(以太网下大约 1500 bytes),那么对于 10、100、1000 bytes 不同包大小的处理吞吐能力实际结果差不多。

5. 禁用一些命令

keys、monitor、flushall、flushdb 应当通过 redis 的 rename 机制禁掉命令,若没有禁用,开发人员要谨慎使用。其中 flushall、flushdb 会清空 redis 数据;keys 命令可能会引起慢日志;monitor 命令在开启的情况下会降低 redis 的吞吐量,根据压测结果大概会降低 redis50% 的吞吐量,越多客户端开启该命令,吞吐量下降会越多。

keys 和 monitor 在一些必要的情况下还是有助于排查线上问题的,建议可在重命名后在必要情况下由 redis 相关负责人员在 redis 备机使用,monitor 命令可借助 redis-faina 等脚本工具进行辅助分析,能更快排查线上 ops 飙升等问题。

6. 避免大量 key 同时过期

如果大量的 key 过期时间设置得过于集中,到过期的时间点,redis 可能会出现短暂的卡顿现象。一般需要在时间上加一个随机值,使得过期时间分散一些。

7. Redis 如何做持久化

bgsave 做镜像全量持久化,aof 做增量持久化。因为 bgsave 会耗费较长时间,不够实时,在停机的时候回导致大量丢失数据,所以需要 aof 来配合使用。在 redis 实例重启时,优先使用 aof 来回复内存状态,如果没有 aof 日志,就会使用 rdb 来恢复。

如果 aof 文件过大会导致恢复时间过长,不过 redis 会定期做 aof 重写,压缩 aof 文件日志大小。在 redis 4.0 之后还有了混合持久化的功能,将 bgsave 的全量和 aof 的增量做了融合处理,这样既保证了回复的效率有兼容了数据的安全性。

为了避免断电时后丢失数据,还可以设置 aof 日志的 sync 属性,极端情况下,可以每次写入都执行,不过会对性能有影响,一般每秒一次就可以。

8. 保存失败

redis 报错:Can’t save in background: fork: Cannot allocate memory。

原因是 redis 在后台保存的时候会直接 fork 一下,然后保存。由于数据库过大,就会 fork 失败,但是实际上由于 copy-on-write 机制的存在,并不会产生问题。所以可以直接更改系统的配置,允许 fork。

/etc/sysctl.conf 文件修改如下:

vm.overcommit_memory=1

然后重新加载:

sysctl -p /etc/sysctl.conf

参考资料:

  1. https://stackoverflow.com/questions/11752544/redis-bgsave-failed-because-fork-cannot-allocate-memory

大规模字符串的匹配

问题:假设我们有一组比较长的文本,每一个文本都有几十 k 左右,还有一些敏感关键词需要删除,大概有几千,然后需要在这些文本中把关键词找出来。

方法 1:暴力搜索

import re

compiled_words = [re.compile(r"\b" + word + r"\b") for word in my20000words]

for sentence in sentences:
  for word in compiled_words:
    print(re.sub(word, "***", sentence))

改进 1:把正则组合起来

pattern = "\b(word1|word2|word3)\b"

for sentence in sentences:
  print(re.sub(pattern, "***", sentence))

改进 2:使用 Trie 优化正则

对于数组:[‘foobar’, ‘foobah’, ‘fooxar’, ‘foozap’, ‘fooza’],使用上面的方法,我们可能会写出正则:

"\b(foobar|foobah|fooxar|foozap|fooza)\b"

但是这并不是最优的正则,应该使用前缀树的思想来合并单词,形成下面的正则:

r"\bfoo(?:ba[hr]|xar|zap?)\b"

具体的方法可以看这里:https://stackoverflow.com/a/42789508/1061155

改进 3:基于集合的搜索

import re

def delete_banned_words(matchobj):
    word = matchobj.group(0)
    if word.lower() in banned_words:
        return ""
    else:
        return word

word_pattern = re.compile("\w+")

for sentence in sentences:
    sentence = word_pattern.sub(delete_banned_words, sentence)

参考:

https://stackoverflow.com/questions/42742810/speed-up-millions-of-regex-replacements-in-python-3/42789508

https://medium.freecodecamp.org/regex-was-taking-5-days-flashtext-does-it-in-15-minutes-55f04411025f

Python 中的 GC(垃圾回收)

一般来说,垃圾回收有两种算法:引用计数和标记删除。

引用计数(reference counting)

CPython 中默认使用的垃圾回收算法是 Reference Counting。也就是对每个元素标记有多少个其他元素引用了它,当引用数降到零的时候就删除。

  1. 当对象增加一个引用,比如赋值给变量,属性或者传入一个方法,引用计数执行加1运算。
  2. 当对象减少一个引用,比如变量离开作用域,属性被赋值为另一个对象引用,属性所在的对象被回收或者之前传入参数的方法返回,引用计数执行减1操作。
  3. 当引用计数变为0,代表该对象不被引用,可以标记成垃圾进行回收。

为了解决循环引用的问题,CPython 使用了 Cyclic GC,遍历所有的环,并且把每一个元素的引用减一,来检测每一个引用环是不是循环应用。

标记删除(Mark and Sweep)

  1. 从某一个已知的还活着的对象开始,便利对象,如果经过了某个对象就认为是活着的
  2. 如果没有被标记的就删除

避免了循环引用的问题

实际的处理过程

Pluggable
Generational
Incremental

引用计数(reference counting)

CPython 中默认使用的垃圾回收算法是 Reference Counting。也就是对每个元素标记有多少个其他元素引用了它,当引用数降到零的时候就删除。

  1. 当对象增加一个引用,比如赋值给变量,属性或者传入一个方法,引用计数执行加 1 运算。
  2. 当对象减少一个引用,比如变量离开作用域,属性被赋值为另一个对象引用,属性所在的对象被回收或者之前传入参数的方法返回,引用计数执行减 1 操作。
  3. 当引用计数变为 0,代表该对象不被引用,可以标记成垃圾进行回收。

为了解决循环引用的问题,CPython 使用了 Cyclic GC,遍历所有的环,并且把每一个元素的引用减一,来检测每一个引用环是不是循环应用。

标记删除(Mark and Sweep)

  1. 从某一个已知的还活着的对象开始,便利对象,如果经过了某个对象就认为是活着的
  2. 如果没有被标记的就删除

避免了循环引用的问题

实际的处理过程

Pluggable
Generational
Incremental

参考资料

  1. https://www.youtube.com/watch?v=iHVs_HkjdmI
  2. https://droidyue.com/blog/2015/06/05/how-garbage-collector-handles-circular-references/
  3. https://www.cnblogs.com/Xjng/p/5128269.html
  4. https://foofish.net/python-gc.html