【线上问题】P1级公司故障，年终奖不保

大家好，我是雨乐！

前段时间，某个同事找我倾诉，说是因为strict weak ordering导致程序coredump，给公司造成数百万损失，最终评级故障为P0级，年终奖都有点不保了，听完不禁一阵唏嘘。

在之前的文章中，我们分析了std::sort的源码实现，在数据量大时候，采用快排，分段递归排序。一旦分段后的数据量小于某个阈值，为了避免快排的递归调用引起的额外开销，此时就采用插入排序。如果递归层次过深，还会采用堆排序。

今天，借助本文，我们分析下这次故障的原因，避免后面的开发过程中出现类似的问题。

背景

流量经过召回、过滤等一系列操作后，得到最终的广告候选集，需要根据相应的策略，进行排序，最终返回首位最优广告。

struct AdItem {
  std::string ad_id;
  int priority;
  int score;
};

现在有一个AdItem类型的verctor，要求对其排序，排序规则如下:

• 按照priority升序排列

• 如果priority一样大，则按照score降序排列

需求还是比较简单吧，当时线上代码如下：

void AdSort(std::vector &ad_items) {
 std::sort(ad_items.begin(), ad_items.end(), [](const AdItem &item1, const AdItem &item2) {
   if (item1.priority < item2.priority) {
      return true;
    } else if (item1.priority > item2.priority) {
      return false;
    }

    return item1.score >= item2.score;
 } );
}

测试环境构造测试case，符合预期，上线。

恐怖的事情来了，上线不久后，程序直接coredump，然后自动重启，接着有coredump，当时心情是这样的。

定位

第一件事，登录线上服务器，通过gdb查看堆栈信息

由于线上是release版的，看不了堆栈信息，将其编译成debug版，在某台线上进行灰度，不出意料，仍然崩溃，查看堆栈信息。

通过堆栈信息，这块的崩溃恰好是在AdSort函数执行完，析构std::vector的时候发生，看来就是因为此次上线导致，于是代码回滚，重新分析原因。

原因

为了尽快定位原因，将这块代码和线上的vector值获取出来，在本地构建一个小范围测试，基本代码如下：

void AdSort(std::vector &ad_items) {
std::sort(ad_items.begin(), ad_items.end(), [](const AdItem &item1, const AdItem &item2) {
  if (item1.priority < item2.priority) {
      return true;
    } else if (item1.priority > item2.priority) {
      return false;
    }

    return item1.score >= item2.score;
} );
}

int main() {
  std::vector v;
  /*
  给v进行赋值操作
  */

  AdSort(v);

  return 0;
}

执行下面命令进行编译，并运行：

g++ -g test.cc -o test
./test

运行报错，如下：

通过gdb查看堆栈信息

线上问题复现，基本能够确认coredump原因就是因为AdSort导致，但是在AdSort中，就一个简单的排序，sort不可能出现崩溃，唯一的原因，就是lambda函数实现有问题。

利用逐步定位排除法，重新修改lambda函数，执行，运行正常。

void AdSort(std::vector &ad_items) {
 std::sort(ad_items.begin(), ad_items.end(), [](const AdItem &item1, const AdItem &item2) {
   if (item1.priority < item2.priority) {
      return true;
    } else if (item1.priority > item2.priority) {
      return false;
    }
    
    if (item1.score > item2.score) {
      return true;
    }

    return false;
 } );
}

运行正常，那么就是因为lambda比较函数有问题，那么为什么这样就没问题了呢？

想起之前在>中看到一句话第21条：总是让比较函数在等值情况下返回false。应该就是没有遵循这个原则，才导致的coredump。

那么为什么要遵循这个原则呢？打开Google，输入std::sort coredump，看到了一句话

❝

Having a non-circular relationship is called non-transitivity for the < operator. It’s not too hard to realise that if your relationships are circular then you won’t be getting reasonable results. In fact there is a very strict set of rules that a data type and its comparators must abide by in order to get correct results from C++ STL algorithms, that is 「strict weak ordering」.

❞

从上面的意思看，在STL中，对于sort函数中的排序算法，需要遵循严格弱序(strict weak ordering)的原则。

严格弱序

什么是严格弱序呢？摘抄下来自wikipedia的定义：

❝

A 「strict weak ordering」 is a binary relation < on a set S that is a strict partial order (a transitive relation that is irreflexive, or equivalently,[5] that is asymmetric) in which the relation "neither a < b nor b < a" is transitive.[1] Therefore, a strict weak ordering has the following properties:

• For all x in S, it is not the case that x < x (irreflexivity).
• For all x, y in S, if x < y then it is not the case that y < x (asymmetry).
• For all x, y, z in S, if x < y and y < z then x < z (transitivity).
• For all x, y, z in S, if x is incomparable with y (neither x < y nor y < x hold), and y is incomparable with z, then x is incomparable with z (transitivity of incomparability).

❞

上面概念，总结下就是，存在两个变量x和y：

• x > y 等同于  y < x
• x == y 等同于 !(x < y) && !(x > y)

要想严格弱序，就需要遵循如下规则：

• 对于所有的x：x < x永远不能为true，每个变量值必须等于其本身
• 如果x < y，那么y < x就不能为true
• 如果x < y 并且y < z，那么x < z,也就是说有序性必须可传递性
• 如果x == y并且y == z，那么x == z，也就是说值相同也必须具有可传递性

那么，为什么不遵循严格弱序的规则，就会导致coredump呢？

❝

对于std::sort()，当容器里面元素的个数大于_S_threshold的枚举常量值时，会使用快速排序，在STL中这个值的默认值是16

❞

我们先看下sort的函数调用链(去掉了不会导致coredump的部分)：

sort
-> __introsort_loop
--> __unguarded_partition

我们看下__unguarded_partition函数的定义：

template
     _RandomAccessIterator
     __unguarded_partition(_RandomAccessIterator __first,
               _RandomAccessIterator __last,
               _Tp __pivot, _Compare __comp)
     {
       while (true)
     {
       while (__comp(*__first, __pivot))
         ++__first;
       --__last;
       while (__comp(__pivot, *__last))
         --__last;
       if (!(__first < __last))
         return __first;
       std::iter_swap(__first, __last);
       ++__first;
     }
     }

在上面代码中，有下面一段：

while (__comp(*__first, __pivot))
         ++__first;

其中，__first为迭代器，__pivot为中间值，__comp为传入的比较函数。

如果传入的vector中，后面的元素完全相等，那么__comp比较函数一直是true，那么后面++__first，最终就会使得迭代器失效，从而导致coredump。

好了，截止到此，此次线上故障原因分析完毕。

此次故障，由于牵扯到算法、工程等部门，由于一开始的时候，不确定问题出在哪(一方面线上是release版本，一方面涉及到多个模块的改动)，几个部门联合分析，最终才定位到bug原因，期间曲折过程略去不表。

结语

这个故障，说真的，无话可说，只能怪自己学艺不精，心服口服，也算是给自己一个教训，后面test case尽可能跟线上一致，把问题尽早暴露在测试阶段。

这次把这个故障原因分享出来，希望大家在后面的开发过程中，能够避免遇到同样的问题。