预支了所有运气 换一次概率拉低

我准备用“火箭酒”这个系列记录一些工作中真实的例子，具体技术细节将会故意隐藏或者篡改以防泄露不该泄露的信息。不仅是让读者思考，也找机会让我自己捋清楚。很多可能不是最近发生的，但是也用了现在时，增加可读性（

电话响起 又在期待的奇迹

周日早晨睡醒，其实更确切得说是被冻醒的。住在New Westminister冰冷地下室 ，在温哥华的初冬确实有点扛不住了。昨晚大约到家就12点了，记得是和阿文哥在公司喝光了16楼所有team的所有的酒才上路的。

掀开电脑，发现自己的team若干SDE已经在channel里整了好几个小时了。一个比较严重的问题，新oncall的大叔凌晨就被嗷起来了，然后他搞不定又嗷起来了escalation manager。大约就是主要的数据Object的一个UUID，从来没有出现过是Null的情况的，突然在两个小时内出现了十几个Object的这个UUID是Null。由于存储层根本不知道怎么handle这样的情况，就彻底卡死一些用户的数据。这个UUID是服务层生成发给存储层的，从代码上看不应该是Null的。怎么会这样呢？

一方面大家在mitigate它的影响，一方面就展开了对这个事情发生的解释权的争夺。这时候某老大发话了，因为他看见了同期同一个数据中心的网络有故障，所以认定应该是network bit flip，导致了这些UUID的值flip成了Null。

这天马行空的解释，当场就震住了所有七嘴八舌的人们。而我，那个在地下室里裹着棉被看戏的我，再也压不住胃里宿醉的填充物了，一口喷在了屏幕上。。。

你说你喜欢森女系，而我多了一个G

我们就事论事，这里就计算一下，这件事发生的几率。看看我这一口宿醉物喷得有没有道理。

首先读一下题是这样的，时间频率上我稍微简化了一点：在一小时之内，我们在通过http传输，有SigV4的情况下，由于bit flipping导致有10个message的UUID为Null的几率是多大？

这里面有五个点：

• 在Ethernet和TCP层传输时bit flip产生校验碰撞的几率
• 强制打开了http的Content-MD5校验
• SigV4，是用的是HMAC-SHA256算法，它的碰撞的几率
• 一个UUID，这里是一个byte array表示的UUID，flip成Null的几率
• 之前和之后从来没有发生过，在一小时内发生了10个的几率

我们一个一个来说。

我失了忆，每天都是星期七

Ethernet和TCP／IP传输层的校验其实是相对比较弱的一层校验。引入这个问题的时候，先说一下十年前S3曾经出过一个事情。当时认为的root cause是一个内部的用来做p2p healthcheck的service，对网络传输的状态信息不做任何其他的校验，直接拿来用。结果一个出问题的设备导致了出现了一些单个bit flip的包，导致down了IAD几个小时。那应该也是S3乃至AWS最大的事故之一了。你现在还可以看到这篇文章。我们后面还会提到这个。

Ethernet还好，它用的是CRC32；而TCP只是简单的16位的累加和校验。你可能会以为这样的话2^48的空间完全不用担心，然而实际情况并非如此。斯坦福教授Jonathan Stone写过一篇著名的文章详细统计过Ethernet层和TCP层累积的data corruption不被发现的几率大约在1/16m到1/10b之间。

为什么会这样呢？因为算法都是有缺陷的。比如TCP的checksum，它是invert了每一个byte之后累加得到的这个checksum值。你仔细想想就会发现，其实TCP的checksum对于一个bit flip的情况是天生免疫的。如果只是data有一个bit flip，它是无论如何不会出现碰撞的，因为invert之后累加的值肯定变了，并且根本也不够overflow checksum导致碰撞的。因此，它需要成立的场景是，在packet data flip一个bit的同时，在16个bit的checksum里要flip至少一个bit。一般来讲，TCP checksum比较怕的是对等位置的交换byte，这样累加算出来的checksum是一样的；而像我们上面说的这种一个bit flip的情况，绕过校验的几率将是非常非常的小。

而同时Ethernet的CRC32算法，对于这种间隔相对比较大的两个bit的flip，也是必然会detect的。所以这里还需要flip Ethernet的packet里的32 bit CRC值。。。而且这一flip，就通常需要flip这32 bit中的若干bit才能达到。

所以，我对于S3那次事件的root cause一直存疑。毕竟一个bit flip绕过校验的可能性将会远远小于Stone论文中给的碰撞几率。况且他们当时看到的所有的corrupt的data，呃，都是错一个bit的。这样的几率已经上天了，我后面会讲为什么上天了。就是这个事情，不管是在内部还是外部，都成了“面向传说编程”系统中的一个重要传说。我们今天讲的这故事，当事人也是由S3这个事情的解释来的“灵感之源”。

对我们现在这个case，1/16m到1/10b之间这个几率，我们还是可以用的。

你说爱喜欢随天意，我就爱上了锦鲤

这个web service的传输协议是HTTP，而且Content-MD5是打开的。但是128bit的碰撞的几率有多大呢？这就要讲到生日悖论（Birthday Paradox）了。这个原理你们自己估计都知道了。我这里就算一下你能看到MD5碰撞的几率。我们这里假设这个service是百万tps，然后这个service已经运行了10年了，这10年间你能看到一次碰撞的几率，呃，是7.19e-11。如果10万年以后还有这个service，碰撞的几率就有0.7%了；如果百万年之后，我们可以有50%的几率碰到一次！！！

这时候，如果考虑进去前面传输层的几率，我们即使是最可能的情况，也需要50万年可以有1%的几率。如果是传输层几率比较低的那种情况，呃，100亿年之后也不到1%。

床和游戏，我们每一个都要宠溺

虽然这时候已经很没有意义了，我还是要说一下这个AWS SigV4的SHA256的事情。按照现在这百万tps，就是你从宇宙出现第一天开始跑，跑到现在，仅仅SHA256碰撞的几率也在e-20这一档。我就不说再加上前面的了。。。

伪装的不在意，oh，假装很佛系

我们刚才都在讨论碰撞几率的事情，然而这件事情的deal breaker是一个UUID是不是能在传输过程中变null。答案是“滚粗”。

这个web framework是使用Json传data的。一个用byte array表示的UUID被Jackson序列化之后在Json里面长什么样子呢？呃，挺长的：

{
    "mimetype": "text/plain",
    "value": [
        81,
        109,
        ...
        ...
        87,
        48,
        61
    ]
}

而Java里的Null，根据Jackson的设置，它可以仅仅是null，或者根本不存在。你说这个能正好flip？呵呵。

然而这就引出了我对这个问题发生的根本原因的最大的怀疑：就是在序列化或者反序列化过程中出了问题，导致这个field消失了。因为在我们的codebase里，根本找不到其他这个field可以为null的可能。

就像LOVE，去掉一半变LOLI

更厉害的是，同样的情况在很短的时间内出现了很多个。这样的概率应该怎么计算呢？我这种概率论与随机过程66分的学渣已经无法解答了。于是我问了刘鑫老师。刘老师找了一位真（点）学数学的朋友。。。我们当时为了计算方便，假设了一千年出现一次的几率是100%。那么一小时内出现两次的几率是多少呢？

 l = 1 / (1000 * 365.25 * 24)
 p = l ^ 2 * exp(-l) / factorial(x)

得出的结果是6.51e-15。。。这还是一小时两次，把那个2换成10，你就又上天了。

我在默默等着你，哪怕中年危机

我当时喷那口宿醉物的时候，也没有想这么多。我只是知道SHA256你是碰撞不到的而已。当我们从头到位把所有的因素都考虑进去时候，已经有点伤人了。

我为什么把这些都写出来呢？就是想说三点：

• 凡事用数字说话，不要用传说
• 就是没有数字，心里也要有点B-Tree
• 妈妈说好好学概率不会被坏人骗