SPL 的有序存储

有序存储是将数据按照某些字段(通常是主键或部分主键)排序后,连续写入外存(主要是硬盘)。有序存储能实现低成本的数据压缩,能够避免频繁跳跃的读取硬盘。而且,计算时从硬盘中连续读出的就是排好序的数据,能够实施专为有序设计的高性能算法,如:二分法查找、快速过滤、有序分组、有序关联等等。这里我们详细介绍 SPL 有序存储的原理。

存储结构

SPL 组表支持行存和列存两种方式,程序员要按照场景来选择。来源数据通常是分批写入组表的,每一批包含若干条记录。而行存组表也是按照记录连续存储数据的,SPL 只要将每一批源数据按记录依次写入组表文件即可。计算时,顺序读取记录就可以了。生成行存组表的代码大致是这样的:

file("T-r.ctx").create@r(#f1,#f2,f3...).append(cs)

      // 建立行存组表,并将来自游标 cs 的数据写入组表。f1 和 f2 前面有 #,代表这两个字段有序。这里显式指定有序字段,便于编写计算代码时利用有序的特征。

 

和行存不同,列存本质上是将各个记录的相同字段存储在一起,不同字段存储在不同区域。如果计算中用到两个或以上字段,要分别找到这些字段值,组合起来再使用。生成列存组表时,SPL 先划分出一定大小的数据块,每个数据块只存储同一个字段的数据。再将每一批源数据的字段值分别写入对应字段的数据块。当某字段写满一个数据块后,要跳过已经存储了其他字段的数据块,产生新数据块,继续写入该字段的数据。这些数据块的起止位置和大小不会随着数据的追加而改变。

 

假设数据表共有 m 个字段 F1 到 Fm,这时候形成的列存组表大致是下面这样:

..

上图中,block#k 代表第 k 个数据块。一个字段在同一个数据块中是连续存储的,但这个字段占用的多个数据块却常常是不连续的。例如上图中的字段 F1 在数据块 block#1 中是连续的,但存储 F1 的下一个数据块并不是 block#2 而是 block#x。虽然 F1 的两个数据块不连续,但是只要每个数据块足够大,就可以避免硬盘的频繁随机读取。对于主流硬盘来说,数据块超过 1M 后,跳动成本占比就非常小,可以认为每一个字段都是逻辑上连续的。

将列存组表有序字段连续存储后,相邻字段值相同的可能性很大。这种情况下,SPL 只存入一个值和重复的数量,不必把同样的值存储多遍,有效的压缩了数据,可以节省大量存储空间。

生成列存组表的 SPL 是这样的:

file("T-c.ctx").create(#f1,#f2,f3...).append(cs)

      // 建立列存组表,并将来自游标 cs 的数据写入组表。同样的,# 表示字段有序。代码很简单,但是封装了上述分块、列存有序压缩等算法。

SPL 组表在追加数据时并不检查字段的有序性,需要程序员自己保证写入数据确实是有序的。

 

数据有序存储之后,可以利用这个特征来实施高性能算法。比如常见的二分法查找。SPL 二分法查找的代码也很简单:

= file("data.ctx").open().find(123456)

       // 打开组表,用二分法查找主键值为 123456 的记录。

再比如区间条件过滤。组表文件头部记录了分块的起始位置。对有序字段过滤时,可以按照起始位置直接取得记录,对比记录中有序字段的值和过滤条件,再加上有序性来判断本块中有没有查找目标,如果没有则直接跳过。这样,能减少数据读取量,节省计算时间。

= file("data.ctx").open().cursor(f1,f2,f4;f1>=123456 && f1<234567)

       // 打开组表,按照有序字段 f1 做区间式查找。

少量修改

存储的数据生成之后,可能会有数据变动操作,包括插入、删除和修改。为保证高性能,组表上不能直接进行这些操作:修改的新值不一定和原值一样长,无法在原位上直接替换;组表也没有预留空白来插入数据,而删除则会造成数据的不连续。我们也可以重写组表来实现数据变动,但是,这需要重新排序以保持有序存储,再加上要重新生成组表,耗时会非常长。

对于有主键的组表,SPL 提供补区机制实现少量的数据变动。也就是在组表文件中划分出单独的补区(如下图),用于存储变动的数据。

..

读取这个组表时,补区的数据(黄色部分)和正常数据(蓝色部分)一起归并计算。

数据变动操作的代码大致是这样的:


A

B

1

=file("data.ctx").open()


2

=10.new(rand(1000):ID,…)

>A1.update(A2)

3

=10.new(rand(10000):ID,…)

>A1.delete(A3)

4

//A2、A3 用随机的排列模拟等待修改和删除的数据。

 

补区机制可以用很短的时间完成数据变动操作,同时还可以保证读取数据的有序性。而且,补区对于 SPL 程序员来说是透明的,语法不变。

 

只有少量变动时,补区对性能的影响很小。但经过多次修改后,补区会越来越大,对性能的影响也会变大。因此,需要定期对补区进行清理,将其合并进原数据区,并清除补区。


A

B

1

=file("data.ctx").open()


2

if (day(now())==1

>A1.reset@q()

3

//每月 1 日清理补区。


下图简单描述了使用 reset@q 清理补区的方法:

..

假设数据按照主键升序存储。图中,SPL 先确定补区最小的主键值,再在正常数据内找到这个值,即黄色箭头位置。在这之前的正常数据(蓝色部分)不动,从黄色箭头位置开始重写组表。这样,既可以保证主键有序,又可以减少重写的数据量,节省时间。

 

定期追加

有些有序数据不会发生插入、删除或者修改,但是会不断有新数据追加进来,新数据不一定能在原数据最后直接追加。比如为了方便进行用户相关统计,订单组表按照用户 ID 有序存储。而新订单数据通常是以时间为序,时间比组表中数据晚,但用户 ID 还是同样的一批值,直接追加会破坏用户 ID 的顺序。如果用新旧数据一起做大排序,再重新生成组表,则耗时会非常长。

SPL 提供补表机制,能在追加新数据时快速得到逻辑上有序的新组表。具体方法大致可以用下面的示意图表示:

..

SPL 在组表主文件之外,增加了一个补表文件。将新数据按照主文件的有序字段排序后,和补表文件有序归并。这样,每次只需要新数据和补表文件做归并排序,涉及数据量就少了很多。读取组表时,分别从两个文件中读取数据,归并后得到结果集。结果集仍然有序,即逻辑上看起来还是一个组表。这会比访问单个文件时性能下降一些,但仍然能够利用到有序。

 

补表和补区不同,即使随着时间逐渐变的很大,也不大影响访问性能。但太大了会导致每次追加数据时变慢,所以也需要定期合并,形成一个更大的主文件,再把补文件清空,这个过程封装在 reset 函数中。比如,每天新增的数据都归并到补文件中,每月 1 日执行 reset 函数。SPL 代码是这样的:


A

B

1

=file("data.ctx").open()


2

=file("data_new.btx").cursor@b()


3

if (day(now())==1

>A1.reset()

4

>A1.append@a(A2)


A3 判断当前日期是否为 1 号,如果是,就在 B3 中对组表执行 reset。A4 中用 append@a 将新增数据归并到补文件中。这样,补文件最多只存储一个月数据,一般都会比主文件小很多。因此,每天的归并量都不会很大,能够较快地完成数据追加。每隔一个月,才需要做一次耗时较多的全量数据整理工作。

 

批量删除

按照日期有序的组表,会出现大量数据过期的情况。比如:历史表 data 对日期等字段有序,存储 2010 年后 10 年的数据。到第 2014 年时,2010 年的数据过期了,需要删掉。而数据是按日期有序的,删除前面的数据会导致整个组表重写一遍,非常耗时。

SPL 提供了复组表,可以快速、便捷的删除过期数据。复组表是用多个文件构成一个组表,这些文件称为复组表的分区。用不同的分区存储不同日期段的数据,当某一个分区存储的数据过期,直接删除对应文件即可。复组表机制可以用下图来示意:

..

1 号分区数据过期了,直接删除文件 1。再打开组表的时候不加入 1 号分区就可以了,不需要重写其他分区中的数据。对应的代码大致是这样:


A

1

=file("data.ctx":to(10)).create(#dt,…;year(dt)-2009)

2

=file("data.ctx":to(2,10)).open()

A1创建组表,设置了10个分区,每个分区有分区号1、2、…、10。year(dt)-2009是分区号表达式,是指按照年份把数据分到不同分区。使用选项 append@x 追加数据时,SPL 会针对每条追加记录计算year(dt)-2009,根据结果把数据追加到相应分区号的文件中。如果删除了1号分区,A2中打开组表的时候,只打开2到10号分区即可。

利用复组表删除过期数据,实际上是在删除文件,速度非常快。如果不用复组表,就要把剩余数据全部重写一遍。即使数据已经按日期有序,不必重新排序,但全部重写还是非常耗时。当然,也可以人为多建几个组表文件,每个装一个时间段的数据,计算时把众多文件再连起来,这就是复组表的思路。只是人为实现时代码会比较复杂,复组表将这些过程封装起来,代码更为简化。

 


以下是广告时间

对润乾产品感兴趣的小伙伴,一定要知道软件还能这样卖哟性价比还不过瘾? 欢迎加入好多乾计划。
这里可以低价购买软件产品,让已经亲民的价格更加便宜!
这里可以销售产品获取佣金,赚满钱包成为土豪不再是梦!
这里还可以推荐分享抢红包,每次都是好几块钱的巨款哟!
来吧,现在就加入,拿起手机扫码,开始乾包之旅



嗯,还不太了解好多乾?
猛戳这里
玩转好多乾