前半有序的大数据排序-欧洲杯在线开户
最近碰到这么一个案例,情况可以简化总结成这样:数据库中有表t,其中有两个重要的字段a和b,a是一个时间戳,精确到秒;b是用户号;其它字段用来表示用户b在时刻a发生的事件属性。
现在任务是:把数据按a,b排序导出。简单来讲,就是把select * from t order by a,b的结果集写出到文件。
但是,这个t表有几十亿条记录,这个sql发出去之后,数据库就象死了一样,一个多小时都没有任何反应。
这也难怪,几十亿记录的大排序确实非常慢,上t的数据量内存装不下,而外存排序需要分段读入数据,在内存将每段排序后再缓存到硬盘,然后将这些缓存数据一起再归并。这样,必须把所有数据都遍历过一遍且分段排序后才能开始输出。
还有什么别的办法么?
通用的大排序可以说已经被全世界研究到极致了,再想出一个更优的办法几乎没有可能性了。但是,如果我们能找到这些数据的一些可得特征,说不定就能有办法了。
了解到一些业务信息后,我们发现这批数据有这样一些特征:
1. 数据是按发生时刻(也就是a)为次序插入的,这样物理存储次序也就会接近于按a有序,而且数据库已经为字段a建好了索引;
2. 从某个起始时刻到终止时刻,几乎每一秒都会有数据插入;
3. 数据按时间分布比较平均,大概每秒数万条,没有某一秒的数据量特别多;
利用这些特征,我们可以设计这样的算法(用spl写成),其中start,end分别是数据的起止时刻。
a
|
b
|
|
1
|
for interval@s(start,end) 1
|
=elapse@s(start,a1-1)
|
2
|
=db.query(“select * from t where a=?”,b1)
|
|
3
|
=b2.sort(b)
|
|
4
|
>outputfile.export@a(b3)
|
基本逻辑是:循环所有的秒,从数据库取出某一秒的记录按b排序后再写出到文件。因为数据库为a建有索引,而数据也接近于按a有序存储,用索引取数就非常快。每一秒内的数据量并不大,可以在内存中排序,速度很快。容易证明这个算法返回的结果集就是按a,b有序的,这样就不需要缓存数据就可以完成这个大排序了。
这个算法执行后立即就有数据开始输出,数小时内就完成了按序导出数据的任务,之所以需要数小时,主要还是从数据库中取数以及写入文件的时间(几十亿行和上t的数据量),排序本身几乎没有占用时间。
针对这批数据,我们还有一个任务:想知道字段a,b是否可以用作t的主键,也就是说字段a,b的取值在t表是否是唯一的。
本来用sql做这个判断也很简单,只要看看
select count(*) from t
和
select count(*) from (select a,b from t group by a,b)
是否相等就可以了(有些数据库不支持count(distinct a,b)写法,这里写成子查询形式)。
count(*)容易算,但面对数十亿行的大数据做group by运算,其方法和外存排序是差不多的,成本也差不多,也是跑了一个多小时没动静。
但是,如果我们利用上述特征,就很容易计算出这个值:
a
|
b
|
|
1
|
for interval@s(start,end) 1
|
=elapse@s(start,a1-1)
|
2
|
=db.query@1(“select count(distinct b) from t where a=?”,b1)
|
|
3
|
=@ b2
|
类似地,循环每一秒,针对每一条记录一个count(distinct b),然后都加起来就是我们要的答案了(容易证明这个算法的正确性)。这段代码几分钟就完成了运算(和上例相比,这里不导出也就不需要取出明细数据了,也不必写文件,而且还能并行计算,不象上例中要有序写出就只能串行)。
细心的读者可能要问,这两个例子都是讲如何利用索引来快速计算,为什么本文标题要叫“前半有序”呢?
实际上我们就是利用了这批数据已经有的次序信息。这两个问题的关键点都是需要按a,b排序,而在索引的作用下,这批数据看起来已经对a有序了,也就是待排序字段中的前一部分字段已有序了。而如果前面字段相同时的记录数都没有大到内存放不下的地步,那么就可以不使用缓存实现大排序了。
如果数据已经存储在可以保持次序的文件中,则这个方法的适应面会更宽泛一些,不需要事先知道a的起止时刻并循环每一秒,代码也会更简单些。
假如数据文件t中按a的次序写入了t表的记录,则上面的两个问题的算法可以分别写出来是这样:
a
|
b
|
|
1
|
for file(t).cursor();a
|
=a1.sort(b)
|
2
|
>outputfile.export@a(b1)
|
a
|
b
|
|
1
|
for file(t).cursor(a,b);a
|
=@ a1.id(b).len()
|
spl中提供了针对游标的有序取出方法,上面两段代码中a1格的意思是针对文件t的数据游标循环,每次读到字段a的值发生变化时则进入循环体,然后再读下一批a相同的记录,…。
基于文件的运算比上述使用索引从数据库取数的效果又好了数倍。而且这几段代码对内存占用也非常少。本来大排序是个很耗用内存的动作,因为后一步归并的性能严重依赖于分段的数量,要减少分段,就要让每一段尽量大,所以内存越大的性能就越好。而利用前半有序的特征后,只要一点点内存(本例中只要能装入数万行记录)就可以高速完成运算了。
最后再温习一下我们的观点:性能优化要因地制宜,根据数据和运算的特征想办法。
我们不能解决通用的大排序问题,但在特定场合下却能设计出好算法提高性能。而数据库过于透明,看起来程序员不用操心了,但数据库并没有那么智能,经常不会利用数据特征来自动优化。而且,在sql体系下,即使人为想出好算法,也几乎无法实现。