关注公众号【高性能架构探索】,第一时间获取干货,回复【pdf】,免费获取计算机必备经典书籍
大家好,我是雨乐!
前段时间,某个同事找我倾诉,说是因为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<AdItem> &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值获取出来,在本地构建一个小范围测试,基本代码如下:
oid AdSort(std::vector<AdItem> &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<AdItem> v;
/*
给v进行赋值操作
*/
AdSort(v);
return 0;
}
执行下面命令进行编译,并运行:
g++ -g test.cc -o test
./test
运行报错,如下:
通过gdb查看堆栈信息
线上问题复现,基本能够确认coredump原因就是因为AdSort导致,但是在AdSort中,就一个简单的排序,sort不可能出现崩溃,唯一的原因,就是写的lambda函数有问题。
利用逐步定位排除法,重新修改lambda函数,执行,运行正常。
void AdSort(std::vector<AdItem> &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比较函数有问题,那么为什么这样就没问题了呢?
想起之前在<
那么为什么要遵循这个原则呢?打开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
的枚举常量值时,会使用快速排序
我们先看下sort的函数调用链(去掉了不会导致coredump的部分):
sort
-> __introsort_loop
--> __unguarded_partition
我们看下__unguarded_partition函数的定义:
template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
_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。
好了,截止到此,此次线上故障原因分析完毕。
结语
这个故障,说真的,无话可说,只能怪自己学艺不精,心服口服,也算是给自己一个教训,后面test case尽可能跟线上一致,把问题尽早暴露在测试阶段。
这次把这个故障原因分享出来,希望大家在后面的开发过程中,能避免采坑。
好了,本期的文章就到这,我们下期见。
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/191
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!