Felix021

备查。

一个日志问题，和一个沟通问题

一个“简单”的C++问题

踩坑记：一知半解protobuf

leetcode题解：秋叶收藏集

踩坑记：Goroutine泄漏

千万级广告定向

聊聊监控

简单记一下：




或者

最近老是想起陈芝麻烂谷子的事情，说明工龄所剩无几了。 

- 1 -

又是在那遥远的 2009 年，那个“杯具”已经不是杯具的年头，度厂办个算法比赛，办出了点儿杯具的味道。 

比赛的名字叫“百度之星”，那些年在校园里影响力还蛮大的（好像现在还是），大概赛制就是通过初赛、复赛、决赛这么几轮，选出几个社会主义四有青年瓜分奖金。值得一提的是，头两年（05、06）冠军都被楼教主承包了。

为什么说有点杯具的味道呢，因为那年的初赛结束以后，度厂搞了个骚操作，把所有参赛选手提交的代码导出来，打了个包，发在贴吧里。

于是贴吧突然就炸了。 




- 2 -

要知道初赛是网络赛，各个学校的 ACM（或OI） 集训队的队员们很可能都是凑在机房一起参与，毕竟毛主席教导我们人多力量大嘛。



所以这就有点意思了：如果同一个题，两份代码长得很像，说明互相抄袭概率就很大。

问题是参赛人数有点多，两两对比这 O(n^2) 的时间复杂度，靠人肉有点儿吃不消；但这么大一个瓜，光看不吃又有点可惜了。

那么这瓜到底该怎么吃呢？


- 3 -

还好，作为一个竞赛战五渣的我，通过初赛的能力没有，搞事情的能力还是有一点的。



为了对比两份代码的相似度，那我首先得找到一个指标。

作为一个善于 作弊 思考的社会主义三无青年，我估计作弊者在拿到弊友代码后不会直接提交，至少会做些更换变量名之类操作；但竞赛时间紧迫，大概率来不及修改整体框架。 

那么，只要我能算出修改的程度，就能判断相似度了：假设两份代码长度分别是 m、n，修改了 x 个字符， 我们大致可以把 `100% - x / ((m + n) / 2)` 当成相似度（没被修改的字符占比）。

但如何计算这修改的程度呢？毕竟修改前后代码长度很可能不同，不适合通过逐字比较来找到差别。 


- 4 -

既然直接处理两段代码有点棘手，那不妨先考虑一下简单的 case 。 

比如说要将字符串 "a" 改成 "b"，这个简单，只要改一个字符就行。

又比如说要将字符串 "a" 改成 "ab"，这个也简单，只要添加一个字符就行。

再比如说要将字符串 "ab" 改成 "b"，这个依然简单，只要删除一个字符就行。

如果我能算出将一段字符串通过添加、删除、修改三种操作修改成另一个字符串的最少操作次数，应该就能把这瓜给吃了。



好像是找到了方向，但是要怎么实现呢？ 


- 5 -

既然直接处理两段代码还是有点棘手，那不妨再考虑一下稍微复杂一点的 case ，比如把字符串 X = "baidu" 变成 Y = "bytedance"。

首先，因为 X[0] 和 Y[0] 相同，我们可以把问题简化成：将 "aidu" 变成 "ytedance"，即 X[1..4] => Y[1..8]（后面简记为 X[1:] => Y[1:]）。 

接着，X[1] = 'a', Y[1] = 'y'，如上一节所说，这时候我们有三种选择：

* 添加：给 X 添加 'y' ，当成 "byaidu"，于是问题简化为将 "aidu" 变成 "tedance"，即 X[1:] => Y[2:]；（注意，我们在这里把该操作当成一个思维实验就好，不需要真的修改 X ，所以这里 "aidu" 对应 X[1:] 而不是 X[2:]）
* 删除：从 X 中删掉 'a' ，当成 "bidu"，问题简化为将 "idu" 变成 ytedance"，即 X[2:] => Y[1:]；
* 修改：把 X 这个 'a' 改成 'y'，当成 '"byidu"，问题简化为将 "idu" 变成 "tedance"，即 X[2:] => Y[2:]；

这三种操作中，后续需要的修改次数最少的那个，再加上 1，就是我们把 X[1:] 改成 Y[1:] 所需的最少次数。

依此类推，如果我们将 X[i:] 变成 Y[j:] 需要 f(i, j) 次操作，由上可得到这样一个公式：



也就是说，我们可以用子问题的最优解来推导出问题的最优解，如果用不说人话的方式，就叫做该问题存在最优子结构。

这么一看，代码是不是呼之欲出了？ 


- 6 -

啰嗦了这么多，不能忘了大佬的教导： 



说干就干，把上面推导的公式落地成代码，so easy：



然后跑起来一看：






- 7 -

"index out of range"，越界了 —— 显然，这里漏掉了递归的终止条件。

不过这个简单：如果 X 越界了，说明这时 i == len(X)，那么 Y 还剩几个字符，我们都加上就行，即还需要 len(Y) - j 次操作；或者 Y 越界了，说明 j == len(Y)，我们把 X 剩下的几个字符删掉，即 len(X) - i 次操作。

于是代码变成了：



跑起来效果杠杠的，马上就得到了 7，算得没毛病。

只可惜这代码还没法用 —— 别说跑那些参赛代码，就连长度为 16 的两个字符串都跑不出结果…… 


- 8 -

稍微分析一下我们就会发现，它竟然是指数时间复杂度的：



不过仔细观察上图（不仔细也没关系，我给红色高亮了），我们可以发现，为了计算 f(i, j)，我们需要计算 f(i + 1, j + 1)；而且它也被用于计算 f(i, j + 1) 和 f(i + 1, j) 。

这意味着这个问题存在重复子问题，类似于我们用 f(i) = f(i - 1) + f(i - 2) 计算 飞波纳妾 fibonacci 数列。

因此我们完全可以将 f(i, j) 存下来、避免重复计算，就像这样：



注：实际上这里也可以直接用一个二维数组 f[i][j] 来保存 f(i, j)，对 C/C++ 来说实现会更容易，读写效率也更高。 

优化以后，因为每个 f(i, j) 只需要计算 1 次、并且可以在常数时间里完成（因为子问题已经计算好了），我们将时间复杂度降到了 O(m * n) ，从而可以在短时间内计算出结果了。


- 9 -

在这个问题里，还有一个很重要的特性是，我们在计算 f(i, j) 的时候，并不关心从 f(0, 0) 到 f(i, j) 的推导过程，或者说从 f(0, 0) 推导到 f(i, j) 的过程对后续计算 f(i, j) 没有任何影响。用不说人话的方式，这就叫做无后效性。

注意，无后效性并不是对所有问题都成立的。

比如在一个 N * N 的迷宫里寻找从坐标 (1, 1) 走到 (N, N) 的一条路径，我们在使用 BFS 或 DFS 搜索时需要将路过的坐标做好标记，避免再次走到，因此从 (1, 1) 到 (x, y) 的路径是会影响从 (x, y) 到 (N, N) 的路径，不满足无后效性。 

汇总一下前面提到的这个问题的几个特点： 

* 最优子结构
* 重复子问题
* 无后效性

—— 这不就是标准的 动态规划 问题嘛！对应的，第 5 节我们推导出的公式，就是这个动态规划问题的状态转移方程了！



由于满足这几个特性，我们实际上可用迭代的方式，从 f(m, n) 倒推出 f(0, 0)，这样可以使用循环而不是递归，进一步提高代码的运行效率。 

另外，对于同一个动态规划问题，状态转移方程也可以不止有一种写法，比如我们可以定义 g(i, j) 为将 X[1..i] 变为 Y[1..j] 的最小操作次数，于是： 



基于这一版状态转移方程，我们就可以从 f(0, 0) 开始逐步计算出 f(m, n)。 

具体代码就不在这里贴了，感兴趣的同学可以自己写写看，注意边界值的处理就好。

实际上，这个算法叫做编辑距离，英文名 Levenshtein distance，是一个和普京同名、姓 Levenshtein 的战斗民族大佬在 1965 年提出的算法；该算法经典到 php 的标准库里竟然包含了一个 levenshtein 函数（可见php的作者真是太闲了）。


- a -

还没完，在追求性能和效果的路上我们还能走得更远，根据代码本身的特性，我们还有一些优化可以做。

比如说代码的注释是可以先删掉再比较。

比如说代码里的字符串也可以删掉再比较。 

比如说代码里的空格，貌似也不影响我们的相似度对比。

通过这样的操作，我们可以大幅缩短了需要对比的代码长度，对于 O(m*n) 的算法而言，这个改善是很可观的。 

此外，当时下场切瓜的另一位瓜友将这个思路推到了极致：既然我们认为代码的整体框架不变、改变的只是变量名这些东西，那我们直接把所有字母、数字、空格等字符全删除，只留下标点符号来代表代码的框架，不是更香吗？ 

这样我们既提升了计算的效率，又进一步提升了计算的效果。 

值得一提的是，该瓜友用的不是编辑距离，而是另一个经典的动态规划算法“最长公共子序列（LCS）”。 


- b -

啰嗦了这么多，终于可以写总结了：


* 计算两个文本的相似度，可以使用编辑距离或者最长公共子序列算法；这两个都是典型的动态规划算法；
* 动态规划问题需要满足最优子结构、重复子问题、无后效性；
* 要解决动态规划问题，先定义状态，推导状态转义方程，再编码；可以用递归也可以用迭代，前者实现简单，后者运行更快；
* 搞事情要考虑后果，本不应该把参赛账号名也直接公开，结果是那次比赛有些人面子上有点不好看；不过年轻时谁没犯点错呢，除了自己谁又还记得呢？ 

最后，“编辑距离” 是个 LeetCode 的原题（No. 72，传送门），；“最长公共子序列” 也是个 LeetCode 的原题（No. 1143，传送门），感兴趣的同学也别错过。

都看到这儿了，帮忙点个 “赞” 或分享给你的小伙伴吧，感谢~

---

推荐阅读：

* 程序员面试指北：面试官视角
* 又是面试题？对，合并有序序列。
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* (译) Ｃ程序员该知道的内存知识 (1)

- 鹅厂 -

在遥远的2009年，那时候“呵呵”还没有奇怪的意思，我笑呵呵地去参加了鹅厂的实习招聘。 

面试被安排在面试官下榻酒店的房间里，校门口的**王朝大酒店，可能一晚上能顶我一个月生活费那种。



过程聊得应该还可以，不过大部分细节都忘了，只记得最后那道代码题，一张纸，一支笔。

题面很简单：写一个 C 函数，合并两个有序数组。

- “最好能通用一点”，面试官补充说。

- “可以用 C++ 模板吗？”

- “最好还是用 C 。”

好多年以后，当我开始面试别人了，发现这道题确实很好用。 


- 解 -

学过归并排序的同学应该都会觉得这个题目并不难，只不过是其中的一次归并环节。

其基本思路是，用两个指针，分别从数组的第一个元素开始，依次比较，每次找到最小的元素存入新数组，然后将指针移动到下一位。

需要注意的是当一个数组被取完以后，还得处理另一个数组的剩余元素。

而所谓“通用”，是指数组的元素可以是任意类型，因此需要把数组元素的大小、用于比较的函数也作为参数传进去。

大概就是要实现这样的一个函数：



其中 m、n 分别表示 A、B 这两个数组的长度，size 表示数组元素的大小。 

具体实现的 C 代码比较琐碎，就不在这里贴出来了，感兴趣的同学可以自己试着写一下。 

- WHY -

我在上一家公司，通常用这道题当笔试的压轴题，但不限制语言，以及去掉了对“通用”的要求。 

为什么选它呢？

首先，它很容易理解，不会产生歧义，不需要额外解释。

其次，在纸面上编码（至少是脱离IDE），程序员在编码前得想清楚；涂改较多也说明一些问题。

最重要的是，它有很好的区分度，因为真的有很多程序猿没认真学过归并排序。

但至少每个人都能想到将两个数组合并，然后进行排序。

有些特别直接的小伙伴，就用了 PHP 自带的 sort 函数，后来我们不得不加个说明：“避免使用库函数”。

至于排序算法，有人写冒泡，也有人写快排；快排的实现，又可以考察是不是在数组里做原地划分（大部分是拆到两个数组里再合并）。

并且，我们在题面上特地对 有序 两个字加粗、加下划线，引导候选人使用最优解法。

如果候选人最终仍然实现了排序解法，在面试中还可以再提示，是否能用上“有序”这个条件，进一步提高性能。 

这样层层递进，能够较好地帮助我们判断候选人的编码能力。 

不过机关算尽，还是遇到了比较挫败的case，比如一个候选人就反问：系统自带的函数效率最高啊，为什么要自己实现？ 




- 字节 -

到了字节跳动后，我发现这道题有点不够用了，撑死只能算 LeetCode Easy，对于有勇气来面试字节的候选人，通常都不在话下。

为了把它升级到 Medium，我想到了两个改动： 

1. 两个不够，m个来凑
2. 数组太简单，得换成链表

然后一看，诶，这 tm 不就是 LeetCode 23 原题吗？ 




话说回来，这题就变成了：请把 m 个有序链表合并成一个新的有序链表；平均每个链表有 k 个节点。


- 解² -

不用说，所有候选人都能想到每次遍历所有链表、找到最小值加入新的链表。 

对于选择这个思路的候选人，接下来的问题是：

Q1：这个方案的时间复杂度是多少呢？

有不少候选人回答 O(m * k)，大概是觉得两个链表合并是 O(2 * k)，m个链表合并自然是 O(m * k) 了。

实际上，使用这种思路，每次找到最小值需要逐个比较 m 个链表，这个操作需要执行 m * k 次（节点总数），因此总的时间复杂度应该是 O(m^2 * k)。

Q2：还有优化空间吗？

有些候选人确实想不到更优的解法，但只要能按这思路完成 bug free 的代码，综合面试中的其他表现，也可以通过我们的考查（详见 程序员面试指北：面试官视角）。

毕竟 LeetCode 23 原题可是 Hard 级别。


- 分治 -

对分治算法比较熟悉的候选人会想到，可以先两两合并，得到的 m / 2 个链表再两两合并，循环这个过程，直到只剩下一个链表。

然后又回到 Q1：这个方案的时间复杂度是多少呢？

这回答就千奇百怪了，O(m * log(k))，O(k * log(m)), O(m * k * log(k))……

这个计算其实不难：

* 第一轮需要 m/2 次两两合并，每次两两合并是 2k 次比较，合计 m*k
* 第二轮需要 m/4 次两两合并，每次两两合并是 4k 次比较（每个链表平均长度变成2k了），合计还是 m*k
* ……
* 对 m 个元素做二分，总共需要 log(m) 轮 

所以合理的答案应该是 O(m * k * log(m))。

具体实现又可以分成上下两部分。

下层应该实现一个合并俩链表的逻辑，比较常见的错误是没能正确处理链表的头结点（比如直接当成尾节点用，或者忘记初始化，以及 C++ 小伙伴用了 new 以后常常忘了 delete），还有前面说到的，一个链表摘空了后，需要处理另一个链表剩下的节点。

上层的实现其实和归并排序长得一毛一样，可以 bottom-up，也可以 top-down。bottom-up 的实现常见的错误是没处理好落单的那一个，而 top-down 则需要注意递归的终止条件。

另外有点意外的是，不少 Java 小伙伴被 List 这个 Interface 荼毒还挺深，在编码的时候顺手就用 List.get(i) ，完全不考虑这个 API 的开销。




- 最小堆 -

对常见数据结构比较熟悉的候选人则会提出使用最小堆，这样可以将每次查找最小值的时间复杂度降为 log(m) ，于是总的时间复杂度也可以降为 O(m * k * log(m))。

既然提到了堆，那就可以顺便问一下，最小元素从堆顶被摘掉以后，如何调整堆？

于是那些只知道可以用最小堆、不知道如何实现堆的候选人就暴露出来了。

不过也不打紧，大部分语言的库里都实现了 PriorityQueue 这个数据结构，让候选人直接用语言提供的版本来编码就好。

具体的代码主要有两个坑，一是循环中要注意对摘空链表的处理，二是对链表头结点的处理（前面提到了）。

- 没完 -

面试到上面的程度就足够了，不然 45 分钟实在是不够用。

但其实还有些值得思考的问题没讲完。

比如说，这两种算法，平均时间复杂度都是 O(m * k * log(m))，到底哪一个更好呢？

分治算法的优势是，两两合并时，当一个链表为空，可以直接将另一个链表的剩余节点串起来，相比于堆算法可以节约一些时间。 

另一方面，对于这样一个经典的多路归并问题，实际使用场景可能是要合并外存上的多个排好序的文件，这时候堆算法可以节约磁盘IO（只需要一次遍历），相比于分治算法就有了压倒性的优势。

所以具体还是要看场景。

再比如，在这个场景下，堆并不是最高效的数据结构。 

实际上，堆算法只是多路归并的早期实现，由于每一层的调整都需要两次比较（先取出两个子节点的较小者，然后再和当前节点比较），其效率还有优化空间。 



（堆的调整） 

如果我们将用于比较的节点作为叶子节点构建一棵完全二叉树，从叶子节点往上只保存获胜的节点：



这样每一层只需要和其兄弟节点做比较即可。这就是所谓“胜者树”，说起来还是空间换时间的套路(多一倍的节点数）。 

还没完 —— 这个方案对每一层的更新仍然需要访问3个节点（自己、兄弟节点，父节点），换个思路，如果我们在路径上只保存失败的值，再用一个额外的变量保存在根节点比较的获胜者：



于是我们对每一层的更新只需要访问当前节点和其父节点就好了。

由于每次保存的是失败者，这个方案又被称为“败者树”。


- 小结 -

这篇没有贴具体的代码，没试过的同学，正好可以用 LeetCode 23 来练手（传送门）。

照例小结一下：

* 笔试/面试题的区分度很重要；
* 归并排序是基础，bottom-up 和 top-down 都要熟；
* 多路归并可以用分治和堆来解决，时间复杂度最优；
* 通过败者树可以进一步优化堆的解法。

喜欢本文的小伙伴，别忘了分享给你的小伙伴，感谢~ 

---

推荐阅读：

* 程序员面试指北：面试官视角
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* (译) Ｃ程序员该知道的内存知识 (1)

在上一篇《踩坑记：Go服务灵异panic》里我们提到了 mutex 和 atomic ，感觉意犹未尽，这篇再展开一点。


- 锁 -

前面我们讲过好多面试题了，其实锁也很适合用来做套题，比如可以这么切入：sync.Mutex 是悲观锁还是乐观锁？

有些候选人不了解它们的区别，回答靠猜，缺乏逻辑以至于我都记不住。虽然这只是一个概念性的知识，但是却很能反映候选人的工作经验，比如读多写少的并发场景，乐观锁可以减少加锁冲突带来的开销。

当然大多数人还是知道的，于是可以继续问：你有了解过锁是怎么实现的吗？

很多人都能想到：维护一个初值为 false 的变量，当一个线程加锁成功的时候，将它置为 true ，就可以保证其他线程无法再获取。 

逻辑是没错，但真正的问题是：两个线程同时检查，发现它的值都是 false ，如何保证只有一个线程会把它置为 true 呢？ 

这样的提问让不少候选人意识到，自己其实并没有真正理解锁。


- 原子操作 -

学过操作系统原理的同学应该都知道，靠的是原子操作（atomic operations）。

那么具体是什么原子操作呢？

在早期只有单核的系统上只需要关闭中断就可以保证原子地执行一段代码 —— 但这通常效率较低，且还存在些问题，例如因为 bug 或恶意代码导致未能正常开启中断，系统就会锁死；而对于多核系统，通常也无法做到在多个核心上同时关闭中断。

因此 CPU 引入了硬件支持的原子操作，例如 x86 体系下的 LOCK 信号（在汇编里给指令加上 LOCK 前缀），通过锁定总线，禁止其他 CPU 对内存的操作来保证原子性。但这样的锁粒度太粗，其他无关的内存操作也会被阻塞，大幅降低系统性能，而随着核数逐渐增加该问题会愈发显著 —— 要知道现在连家用 CPU 都有16核了。

因此 Intel 在 Pentium 486 开始引入了用于保证缓存一致性的 MESI 协议，通过锁定对应的 cache line，使得其他 core 无法修改指定内存，从而实现了原子操作（缓存锁）。这里不展开了，对细节感兴趣的话，详见参考资料《原子操作是如何实现的》[1]。


- CAS -

针对前面问的“什么原子操作”，大多数候选人的回答是 CAS （compare-and-swap），也有人会提到 test-and-set 等其他操作，原理都一样，就是用前述机制实现的。

下面这段 Go 代码展示了 CAS 的逻辑：



请注意：这不是 CAS 的实现，如前所述，真正的 CAS 是硬件级别的指令支持的，最早出现在 1970 年 IBM 的 System 370 上，在 x86 上则是 80486 开始新增的 CMPXCHG 这个指令。

注：在多核系统上 CMPXCHG 也需要使用 LOCK 前缀，但是如果对应内存已经在 cache 里，就不用发出 LOCK 信号锁定总线，而是使用缓存锁。 

由于不用锁定总线，这样的原子操作指令不会限制其余 CPU core 操作非锁定内存，因此对系统整体的吞吐量影响不大。这一点对于当今核数越来越多的系统来说尤为重要。

由于原子操作指令仍然需要在 CPU 之间传递消息用于对 cache line 的锁定，其性能仍有一定损耗，具体来说大概就相当于一个未命中 cache 的 Load Memory 指令[2]。

基于 CAS 我们可以用实现很多实用的原子操作，例如原子加法：



看，这就是一个典型的使用乐观锁的实现了：先做加法，如果更新失败，就换个姿势再来一次。

注：Go 语言 atomic.AddInt32 的实现是直接使用汇编 LOCK XADDL 完成的，不是基于 CAS 和循环。


- 自旋锁 -

回到锁的问题上，基于 CAS 我们可以很容易实现一个锁：



这就是经典的自旋锁[3] —— 通过反复检测锁变量是否可用来完成加锁。在加锁过程中 CPU 是在忙等待，因此仅适用于阻塞较短时间的场合；其优势在于避免了线程切换的开销。 

注：spinlock 是 Linux 内核中主要的两种锁之一（另一种是Mutex），感兴趣的同学可以去看看内核源码里的实现，具体位于 include/asm/spinlock.h （吐槽：内核源码真是难读）。

在 Go 版的实现里还要注意：如果 GOMAXPROCS 被设置成 1 （Go Runtime只会给用户代码分配一个系统线程），会导致上述代码陷入死循环，因此更完善的实现是：



通过将当前系统线程的使用权暂时归还给 Go Runtime（相当于其他语言的 yield），可以避免前述情况，但这也在一定程度上破坏了自旋锁的语义、使其变得更重了。

值得一提的是，研究人员发现，如果锁冲突比较频繁，在 CAS 失败时使用指数退避算法（Exponential Backoff）往往能得到更好的整体性能[2]。


- Mutex -

实际上 Go 语言没有提供自带的自旋锁实现，我们在代码中用得更多的是 Mutex 。

对比于 Spinlock 的忙等待，如果 Mutex 未获得锁，会释放对 CPU 的占用。

上一篇 我们在说 Mutex 性能不够好的时候有提到“lock does not scale with the number of the processors”，这里的 lock 指的是用 CPU LOCK信号实现的锁；而通过阅读 Mutex 的源码，我发现实际上 Mutex 底层也是使用原子操作来实现的，所以前述说法不太准确。

Mutex 针对实际应用场景做了许多优化，是一个从轻量级锁逐渐升级到重量级锁的过程，从而平衡了各种场景下的需求和性能。

具体来说有这么几项：

* fastpath：在简单场景下直接使用 CAS 加锁和解锁，缩短执行路径
* spin：当自旋有意义时（多核、GOMAXPROCS > 1 、尝试不超过4次），优先使用自旋
* 饥饿 & 公平：当等待超过 1ms 时，进入饥饿模式，新竞争者需要排队

注：对具体实现感兴趣的同学，可以结合参考资料《golang中的锁源码实现：Mutex》[5] 阅读源码。 

这里提到的“公平”，指的是先到先得，这意味着每一个竞争者都需要进入等待队列，而这意味着CPU控制权的切换和对应的开销；而非公平锁，指的是在进入等待队列之前先尝试加锁，如果加锁成功，可以减少排队从而提高性能，但代价是队列中的竞争者可能会处于“饥饿”状态。


- sync  -

除了 Mutex，Go 在 sync 包里还实现了很多用于解决并发问题的工具，这里简单介绍下：

· RWMutex

读写锁，通过将资源的访问者分成读者和写者，允许多个读者同时访问资源，从而提高共享资源的并发度。适用于读远多于写的场景。

· WaitGroup

用于对 goroutine 的并发控制，在主 goroutine 里使用 Add(n) 指定并发数量，并使用 Wait() 等待所有任务都调用 Done() （配合 defer 使用效果更佳）。

· Pool

对象池，用于缓存后续会用到的对象，从而缓解 gc 压力。例如 fmt 包用它来缓存输出缓冲区。 

· Once

“单例”：once.Do(f) 保证 f 只会被执行一次。f 被执行后，通过原子操作保证了性能。 

· Cond

条件同步：当条件不满足时（通常是等待一个任务执行完成），goroutine调用 Wait() 等待通知；另一个 goroutine 完成任务后，调用 Signal() 或 Broadcast() 通知在等待的 goroutine。 

· Map

支持并发的 map：通过 Load、Store、LoadOrStore、Delete、Range 等方法提供线程安全的 map 数据结构。

· atomic

提供 Add、CAS、Load、Store、Swap 等对基础数据类型的原子操作，以及 atomic.Value 来支持其他类型的 Load、Store 原子操作。


- 收尾 -

哎呀，这篇写得干巴巴的，连一个表情包都没有（忍住）。

最后照例小结一下：

* 锁是基于原子操作实现的，而原子操作是需要硬件支持的
* 基于 MESI 协议的缓存锁可以提高锁的性能
* 比较常用的原子操作是 CAS
* Go 没有官方自旋锁，我们通常用 sync.Mutex
* sync 包里还有很多解决并发问题的实用工具

下次考虑结合一些具体案例来讲讲，可能更有意思一点儿~


---

推荐阅读：

* 程序员面试指北：面试官视角
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* (译) Ｃ程序员该知道的内存知识 (1)

---

参考资料：

1. 原子操作是如何实现的？
2. Compare-and-swap
3. 自旋锁
4. 聊聊CPU的LOCK指令
5. golang中的锁源码实现：Mutex

这个坑比较新鲜，周一刚填完，还冒着冷气。


- 1 -

在字节跳动，我们线上服务的所有 log 都通过统一的日志库采集到流式日志服务、落地 ES 集群，配上字节云超(sang)级(xin)强(bing)大(kuang)的监控能力，每一条 panic log 都可以触发一个打给值班同学的电话。 

所以我们常常不选电话，只选飞书 ↓↓↓



但毕竟是 panic，大部分 case 都会迅速被就地正法，除了少数排查费劲、又不对线上产生太大影响的，比如这一个：



注：为了方便阅读，略有简化。

你看，它可以被 recover 兜住（不会把服务搞挂），而且出现频率很低（每天几次甚至没有），考虑到在每天数百亿请求中的占比，解决它的 ROI 实在太低，所以就耽搁了一段时间 且不用担心背 P0 的锅。



- 2 -

其实之前 S 同学和我都关注过这个 panic ，从上面的 Error log 可以看到，错误发生在调用 json.Marshal 的时候，调用方的代码大概长这样：



注：实际map有更多key/value，这里略作简化。 

看这代码，第一反应是：这**也能 panic ？



找到对应的 json 库源码（encode.go第880行，对应下面第5行）：



—— 也只是从string里逐个读取字符，看着并没什么猫饼。 

由于 panic 发生在官方 json 库里，不适合修改并部署到全量机器；引入第三方 json 库又涉及很多依赖问题，所以当时没再跟进。

直到最近 panic 频率逐渐升高， H 和 L 同学实在看不下去了。

- 3 -

L 同学的思路是，既然这个 panic 能被 recover 兜住，那为什么不看看 panic 时这个 map 里装了什么呢？



于是代码就变成了这样：



然后 panic 顺利转移到了 log.Warnf 这一行[doge]


- 4 - 

不管怎么说成功地转移了问题，只要把 log.Warnf 这一行注释掉……



作为一个追求极致的 ByteDancer，L 同学抵制住了诱惑并尝试了新的思路，既然从 panic log 看到是跪在了一个 string 上，那至少先看看是哪一个string：



改起来倒是很简单，赶在这个 需要上班的 周日下午发了车，晚上就捉到了一个case。

通过线上 log，我们发现错误出现在 "step" 这个 key 上（log里有输出key、但没输出value），value 本应是 ctx.StepName 这个 string。

可是 string 这种看起来人畜无害的 immutable 的 type 为什么会导致 panic 呢？




- 5 -

通过走读代码得知，在遇到异常的时候，我们会往 ctx.StepName 写入这个异常点的名称，就像这样： 



一边读一边写，有那么点并发的味道了。

考虑到我们为了降低媒体感知的超时率，将整个广告的召回流程包装成一个带时间限制的任务：



因此在一个请求流程中，确实可能会出现并发读写 ctx.StepName 这个 string object 的情况。 

但如何实锤是这儿挖的坑呢？ 


- 6 -

在线上服务中直接验证这一点不太容易，但是 H 同学做了一个简单的 POC，大概像这样：



代码一跑起来就有点味道了：





虽然没看到 panic，但是确实看到了点奇怪的东西（严正声明：不是故意要吐槽GO的GC）。

再用 go 的 race detector 瞅瞅：



这下可算是实锤了。


- 7 -

那么为什么 string 的并发读写会出现这种现象呢？ 

这就得从 string 底层的数据结构说起了。在 go 的 reflect 包里有一个 type StringHeader ，对应的就是 string 在 go runtime的表示：



可以看到， string 由一个指针（指向字符串实际内容）和一个长度组成。 

比如说我们可以这么玩弄 StringHeader：



对于这样一个 struct ，golang 无法保证原子性地完成赋值，因此可能会出现goroutine 1 刚修改完指针（Data）、还没来得及修改长度（Len），goroutine 2 就读取了这个string 的情况。

因此我们看到了 "WHAT" 这个输出 —— 这就是将 s 从 "F*CK" 改成 "WHAT THE" 时，Data 改了、Len 还没来得及改的情况（仍然等于4）。

至于 "F*CKGOGC" 则正好相反，而且显然是出现了越界，只不过越界访问的地址仍然在进程可访问的地址空间里。 


- 8 - 

既然问题定位到了，解决起来就很简单了。 

最直接的方法是使用 sync.Mutex：



但 Mutex 性能不够好（lock does not scale with the number of the processors），对于这种读写冲突概率很小的场景，性能更好的方案是将 ctx.StepName 类型改成 atomic.Value，然后 



注：也可以改成 *string 然后使用 atomic.StorePointer

实际上，Golang 不保证任何单独的操作是原子性的，除非使用 atomic 包里提供的原语或加锁。


- 9 -

大结局：周一下午 H 同学提交了修复代码并完成发布，这个 panic 就再没出现了。

总结一下：
* string 没有看起来那么人畜无害
* 并发的坑可以找 -race 帮帮忙
* 记得使用 mutex 或 atomic

最后留下一个小问题供思考：

这说了半天并没有完全复现 panic，不过文中已经给了足够多的工具，你能想到怎么办吗？

---

推荐阅读:

* 程序员面试指北：面试官视角
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* [译] Ｃ程序员该知道的内存知识 (1)

Linux里养僵尸是怎么回事呢？Linux相信大家都很熟悉，但是Linux里养僵尸是怎么回事呢，下面就让小编带大家一起了解吧。


# - 1 -

上一篇挖了个 SIGHUP 的坑，这篇试着填一下。

之前在《程序员面试指北：面试官视角》里面说过，在结构化面试中，我们会从各个方向去考查候选人，其中之一是操作系统。

上篇介绍了一套题，我还有另一套，一般这么开场：

在终端下启动一个命令，如果在命令结束前关掉终端，它还能正常运行吗？




# - 2 -

这其实是一个很常见的case，但凡 Linux 或者 Mac 用得多一点，都会遇到。

在我还是一个穷酸学生的2009年，每个月都需要支付 20 元巨款（当时能买3根鸭脖），通过一个禁止分享网络的认证客户端接入校园网。

为了共建和谐宿舍 节省网费 ，我历经千辛万苦，交叉编译开源的Linux认证客户端，集成到固件里，并刷到了我的 NETGEAR 路由器上。

然后山水 BBS 的 Linux 版主把我的帖子置顶了 11 年。可见他有多痛恨禁止共享网络

这么一回忆，感觉自己的共享经济思维真是前卫，当时怎么就没想到去搞共享单车呢？



扯远了，在捣腾的过程中，我就踩了这么个坑：当我ssh到路由器上、刚启动认证时，能够正常联网；但是退出ssh后一会，网就断了。

经过一番捣腾后发现，只要一退出ssh，认证程序就凉了，而不是继续在后台保持和认证服务器的通信。


# - 3 -

所以前面那个问题，我以为大部分候选人应该会回答“否”，但没想到竟然还有不少人回答“是”。

其实回答“是”也没什么错，因为确实也有些命令不会随着终端关闭而结束。

问题是当我追问当时执行的是什么命令时，候选人往往又说不出个所以然来。


（借学长的表情一用）

然后我就感到很强的挫败感：这不按剧本来，没法问了啊……只好换题。

当然大部分候选人确实被坑过，于是我可以接着问：

如果确实需要在后台继续执行命令怎么办呢？

有些人只记得要在后面加个 & ；但也有不少人知道前面还得加个 nohup，就像这样：



注：其实我更喜欢 screen（或 tmux），偶尔也用 setsid 。

然后就可以放心地关闭终端 开始放羊 了。

但我的套题还没结束：为什么加上 nohup 就可以让进程在后台继续运行呢？


（这表情熟悉吗）


# - 4 -

铺垫了这么多，总算是可以开始填坑了。

答案其实很好找，man nohup 就能看到：



nohup工具在启动命令的同时会将 SIGHUP 信号设置为忽略。
而关于 SIGHUP，Wikipedia原文是这样介绍的：



对于 POSIX 兼容的平台（如Unix、Linux、BSD、Mac），当进程所在的控制终端关闭时，系统会给进程发送 SIGHUP 信号（Signal Hang Up，挂断信号）。

为什么叫 SIGHUP 呢？（严正申明：这一问不在套题里[doge])

我们知道，在上古时代，捉 bug 就已经是码农的必备技能（更准确地说是 moth）。


（我总觉得这个图是假的）

到了远古时代，他们不再需要去机房，通过基于 RS-232 协议的串行线路连接到大型机的终端上，就可以开始收福报。

收完福报，程序员通知自己的猫（modem）挂断（Hang Up）连接；大型机的 OS 检测到连接断开，就会给进程发送信号 —— 所以这信号被称为 SIGHUP 。

这果然是毫无卵用的知识啊。




# - 5 -

很多同学在操作系统的课程上学习了“进程间的通信方式有信号、管道、消息队列、共享内存……”，但是对信号到底是个什么东西，并没有现实的概念。

课堂教学的理论和实践往往是割裂的，在此特别推荐《Unix环境高级编程》（简称APUE）。

APUE在 1.9 - 信号 中写到：信号是通知进程已发生某种条件的一种技术。

而在 Linux/Unix 下，进程对信号的处理有三种选择：

* 按系统默认方式处理
* 提供一个回调函数
* 或忽略该信号（有些信号例外，不允许被忽略）

以 SIGHUP 信号为例，系统默认处理方式就是结束进程。

当然终端下打开的第一个进程通常都是shell（例如bash）。shell会给 SIGHUP 信号注册一个回调函数，用于给该 shell 下所有的子进程发送 SIGHUP 信号，然后再主动退出。

对于求生欲很强的程序（例如nohup），可以主动选择忽略该信号。

有一些进程本来就被设计成在后台运行，不需要控制终端，因此它们将 SIGHUP 挪作它用，一个常见的用法就是重新读取配置文件（例如Apache、Nginx），上篇提到的 logrotate 正是利用了这一点。

终于填完了坑。

# - 6 -

说了这么多都还是纸上谈兵，实操中如何主动忽略 SIGHUP 呢？

实际上也很简单，使用 Linux 的 signal 系统调用即可：



不妨试试看，编译运行起来，即使关闭终端，它也会在后台继续运行。

signal 也可以用于指定回调函数（或重置为系统默认处理方式），这里就不展开了，感兴趣的同学可以参考 APUE 里的代码，以及阅读 signal 的manual。

使用回调函数还需要注意一个坑：

由于回调函数可能在任意时刻被触发，因此要避免调用不可重入的函数（典型如printf）。常见的做法是 set 一个 flag，然后在程序的主循环中检测该 flag，再按需执行相应任务。

# - 7 -

SIGHUP 只是常见的一个信号，在 Linux 下，信号还有大量其他的场景和应用。

当你按下 Ctrl + C ，就是给进程发送了一个 SIGINT 信号。

当你执行 kill -TERM $PID，就是给进程发送了一个 SIGTERM 信号。可能和你期望有出入的是，SIGTERM 是可以被进程忽略的。所以有时候你得用 SIGKILL (kill -9) 。

你还可以使用可自定义的 SIGUSR1、SIGUSR2、SIGURG 来实现一些功能，比如《踩坑记#2：Go服务锁死》中提到 Golang 在其 goroutine 调度中使用了 SIGURG 。

# - 8 -

这次就不总结了，最后再用一个和信号有关的 case 收尾。

Linux 内核会为每一个进程分配一个 task_struct 结构体，用于保存进程的相关信息。

在进程死亡后，系统会发送一个 SIGCHLD 信号给它的父进程。

正确的父进程实现，通常应当使用 wait 系统调用来给子进程收尸 —— 父进程往往需要知道子进程结束这个事件，而且可能还需要得知其退出原因（exit code）。

然后内核才会将对应的 task_struct 释放。

如果父进程没有收尸，task_struct 里的 state 会一直保持为 EXIT_ZOMBIE，这时在 ps 或 top 等命令里，就可以看到该进程的状态为 Z ，而且无法被 kill 。

这就是所谓的僵尸进程，这时候你找九叔都没用。


（大半夜找这图还挺渗人的）

所以Linux里养僵尸，其实就是子进程死了父进程不收尸，大家可能会很惊讶Linux里怎么会养僵尸呢？但事实就是这样，小编也感到非常惊讶。

这就是关于Linux里养僵尸的事情了，大家有什么想法呢，欢迎在评论区告诉小编一起讨论哦！

---

推荐阅读

* 程序员面试指北：面试官视角
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* [译] Ｃ程序员该知道的内存知识 (1)