批量随机键值的查询优化

一、 问题描述

键值查询是很常见的查询场景,在数据表上建有索引后,即使表中数据记录数巨大(几亿甚至几十亿行),用键值查询出单条记录也会很快,因为建立索引后的复杂度只有 O(log2N), 10 亿行数据大概只要比较 30 几次(10 亿约等于 2^30),在现代计算机上是个毫秒级别的事务。

不过,如果需要查询的键值很多,比如多达几千甚至几万的时候,如果每次都独立查找,那读取和比较也会累积到几万甚至几十万次,时间延迟由此也会涨到几十秒甚至几十分钟的级别,简单地使用数据库索引对于用户体验必然是难以容忍的了。

本文将讨论大批量键值查询的性能优化方法,示例代码将用集算器 SPL 完成。SPL 代码简洁易懂,且提供了丰富的算法支持,非常适合实现这种高性能计算。

二、 单一整数键值

我们先考虑最简单的单一整数键值情况,即用作键的字段只有一个,且为整数。

2.1 存储

与大多数分析场景不同,键值查找更适合使用行式存储而非列式存储。因为行存是按记录,一条条连续存储的。而列存是按列存储的,对整条记录来说并不连续,读取单条记录时,需要从更多的数据块中读取数据,访问量反而更多。

对于超大规模数据下的随机批量键值查找,不适合对数据进行压缩。因为命中的结果分布有可能很分散,大概率出现解压一个数据块仅能获取一条记录的情况,浪费很多解压缩时间,使得查询效率变低。

2.2 索引

通常我们会针对查找键建立索引,这样指定键值可以迅速定位,而不必遍历数据。我们知道,索引的本质也是排序,利用键值有序可以快速用二分法找到指定记录。那么,如果数据本身对键值就有序,是不是可以不建索引了?

键值有序的数据本身往往过大,不能放在内存中,即使利用二分法查找时,也多次读取外存用以对比。建立索引后,可以预加载索引到内存,在内存中对索引查找,相比多次读取外存效率高很多。所以,即使数据有序,再建立索引对于高速查找仍然有意义。

反过来,建立了索引后,还要求数据对键值有序吗?

对于键值无序并建有索引时,读取数据时需要再按物理位置排序, 因为外存数据是按块存储的, 在大批量查找时,同一块有可能涉及多条找到的记录,而如果按键值次序去读取时,物理次序如果键值次序不同,就可能发生同一块被读多次的情况,性能损失严重,所以一定要在读取前将欲读数据按物理位置排序。而取出的数据还要再按原顺序排序,来回就多两个排序步骤。读取的数据量大的时候会有些影响效率,若数据有序存放则可以省去这两次排序的开销。如果每次读取的数据量不大时,额外排序损失的性能也很少,可以不必按键值有序。

2.3 索引缓存

当数据量很大时,索引本身也会很大,无法全部放入内存,这样每一次的查找都需要从硬盘上读取索引。如果对索引再建立外层索引(可能有多级),再在进行批量查找之前,尽可能多地预先加载多级索引缓存,减少重复读取索引的次数,就可以提升查询效率。

2.4 查找

查找时,将待查找的键值集有序排序,当查完一个键值后,由于键值是有序(升序)的,下一个键值肯定不小于上一个键值,这样就不会重复读取比上一个索引区间更小的索引块,少走回头路。

2.5 举例

批量随机键值的查询优化_第1张图片

使用 SPL 创建一个满足以上数据结构的行存组表:

批量随机键值的查询优化_第2张图片

用键值 id,建立索引:

批量随机键值的查询优化_第3张图片

利用索引进行批量键值查找:

批量随机键值的查询优化_第4张图片

A1:这里待查找键值没有排序,因为 A4 的 T.icursor 中的 A.contain 会自动对 A 进行排序。

A3:其中 @3 的意思是将 id 键的多级索引的更多级缓存预先加载进内存。经过 index@3 预处理,第一遍查询时间就能达到索引被缓存后才能达到的极限值。另外,还有 index@2,相比 @3 缓存的索引层级更少,占用内存也更小。

三、 复杂键值

3.1 非整数键值

非整数键值,比如车牌号,通常是由字符与数字组合成的字符串。因为字符串比较要比整数的比较复杂得多,比较速度也更慢。所以可以把这种有规律或者可枚举的字符串转为简单的整数类型,提升性能。

3.2 多字段键值

多字段键值,可以直接利用多个字段键进行查找,但集合的存储和比较都要慢一些。为了获取高性能,更常用的办法是把多字段键拼成单字段键。对于有规律或者可枚举的串,可以将串数字化后,与其他数字化后的键值合并为一个新的整数键值。

3.3 举例

批量随机键值的查询优化_第5张图片

其中 pnum 和 pdate 两个字段作为联合主键确定一条记录。

3.3.1 多字段键直接查找

使用 SPL,按以上数据结构,创建组表(和单键值类似,多键值也需要确保键值有序,可以使用cs.sortx()函数排序,具体方法详见函数参考。):

批量随机键值的查询优化_第6张图片

多字段键组表建立索引时需要包含多个维。例如,以上数据结构中的 pnum 和 pdate 两个维:

批量随机键值的查询优化_第7张图片

多字段键组表查询时可以使用 n 元组。例如,以上数据结构中的 \[pnum,pdate\]:

批量随机键值的查询优化_第8张图片

3.3.2 数字化合并键值

用以上的数据结构做个例子,来说明如何进行数字化合并键值。

pnum是个串,一共 7 位,第一位是一个随机大写英文字母,后六位都是数字,可以将字母用 ACS 码值表示,与后六位数字拼接后转为整数。pdate 是一个日期类型字段,可以将 2007-01-01 定为起始日期,pdate 与起始日期间隔的天数可以作为该字段的数字化后的值。

pnum中大写英文字母的 ACS 码是两位数,与后面的 6 位数加起来是 8 位数,而日期 pdate 的跨度范围为 10 年,换算成天是个 4 位数,将数字化后的 pnum*10000+pdate,就得到了一个新的 12 位的数字化字段,pid。

批量随机键值的查询优化_第9张图片

这样就得到了一个单字段键的组表“conbi.ctx”,其数据结构如下:

10png

然后按照 "单一整数键值" 中的做法就可以处理了。

四、 并行技术

4.1 数据拆分

多线程并行,是把数据分成 N 份,用 N 个线程查询。但如果只是随意地将数据分成 N 份,很可能无法真正地提高性能。因为将要查询的键值集是未知的,所以理论上也无法确保希望查找的数据能够均匀分布在每一份中。比较好的处理方式是先观察键值集的特征,从而尽可能地进行数据的均匀拆分。

如果键值数据有比较明显的业务特征,我们可以考虑按照实际业务场景使用日期、部门之类的字段来对数据进行拆分。如:将属于部门 A 的 1000 条记录均分在 10 份数据中,每份数据就有 100 条记录。在利用多线程查询属于部门 A 的记录时,每个线程就会从各自对应的数据中取数相应的这 100 条记录了。

对于没有什么特征的数据,尤其是随机数,可以考虑按整数的尾数取余数来分成 N 份数据。这样可以尽可能地确保每份数据中数据量的均匀分配。

4.2 举例

11png

基于以上数据结构,数据拆分以及建立组表:

批量随机键值的查询优化_第10张图片

A2:使用循环函数,创建名为“键值名 _ 键值取 N 的余数.ctx”的组表文件,其结构同为 (#id,data)。

A3:用循环函数将游标数据分别追加到 N 个原组表上。此处 N 为参数,假设 N=4,当循环第一次时,拼出的 eval 函数参数为:channel(A1).select(id%4==0).attach(A2(1).append(~.cursor()))。意思是对游标 A1 创建管道,将管道中记录按键值 id 取 4 的余数,将余数值等于 0 的记录过滤出来。attach 是对当前管道的附加运算,表示取和当前余数值对应的原组表,将当前管道中筛选过滤出的记录,以游标记录的方式追加到 A2(1),即第 1 个组表。

多线程并行创建索引:

13png

A1:使用 fork 执行多线程时,需要注意环境中的并行限制数是否设置合理。

多线程并行查询:

批量随机键值的查询优化_第11张图片

需要注意的是,将待查找的批量键值用和拆分组表数据同样的规则拆分后,在各自对应的组表中进行查找。并且取数动作应当在多线程并行内完成,而不是将各自的游标返回后再取数。

五、 数据追加

对于大数据来说,新数据的追加是不可避免的。数据追加通常要考虑原数据与追加数据的关系,较简单的情况是连续有序的数据,直接在原数据尾部追加新数据,对追加后的数据,还需要更新索引。如果新数据与原数据,整体不是连续有序,就需要在追加数据时做归并运算,并随后更新索引。尤其是当原数据变得很大时,原数据与新数据的频繁归并、每次追加后更新索引,都会带来极高的时间成本和磁盘损耗问题。

这种情况可以建立一份临时数据区来存放每次追加的新数据,当这个临时数据区达到一定规模(在数据增量较为稳定的情况下也可以按时间来决定,比如每个月初),就将临时数据区(小数据)与原数据(大数据)进行一次归并,并更新索引。查找时可以将大小两份数据在逻辑上合并为一份数据后进行查找。

无序的数据追加时,因为索引就是排序的,要重建索引也会面临以上有序数据追加时的问题,还是需要大小两份数据的办法,等积累多了再重建索引。

5.1 举例

15png

SPL提供了补文件的功能,可以方便地应对复杂的数据追加场景。

单个文件时,利用补文件追加数据:

批量随机键值的查询优化_第12张图片

A1:add.txt 是新增数据(这里假设数据来自文本文件,实际也可能来自数据库等其他数据来源),与已有文件结构相同,均为 (#id,data),其中 id 有序。

A2:判断为当前系统时间是否为月初。

B2:若是月初,f.reset 函数将补文件有序归并到主文件,同时清空补文件,并更新索引。

A3:每天对补文件进行归并运算,append 的 @a 代表归并追加到补文件上,若没有补文件则自动创建,并更新索引。

多个文件时,利用补文件追加数据:

批量随机键值的查询优化_第13张图片

查找时,代码不变。open 函数,当存在补文件时,会连带补文件的数据一同查找。

六、 索引冗余

同一份数据不能在遍历运算(通常为列存)和随机取数(通常为行存)这两方面都达到最优性能。如果这份数据还想用于遍历运算,可以把数据冗余多份,以空间换时间。

6.1 举例

批量随机键值的查询优化_第14张图片

对需要遍历的数据,通常采用列存。SPL 中创建列存组表,只需要将 f.create@r 的 @r 去掉,就是以列存方式创建组表。

对于列存组表,在建立索引时,还可以建立带值索引,把需要获取的数据复制进索引,基于以上的数据结构:

批量随机键值的查询优化_第15张图片

对于多字段键的场景,组表建索引时,对应参数部分也有类似的写法:index(ids\_data\_idx;id1,id2,…,idN;data1,data2,…,dataN)。

SPL的带值索引的查询与不带值索引使用一样。需要注意的是,使用带值索引,读取数据时将不再访问原数据文件,取数速度会更快。但是另一方面,因为在索引中做了冗余,索引文件也会较大。

你可能感兴趣的