集算器:解决计算难题的利器

集算器

设计目标

集算器是一种程序设计语言,专注于(半)结构化数据计算。集算器采用了新的数据和计算模型,提供了丰富的基础计算方法,使计算更易于完成且性能更好。
集算器不是面向对象的程序设计语言,没有复杂的继承和重载概念,引入对象概念仅仅是为了更方便地描述与对象相关的方法,有BASIC这类初级程序设计水平的程序员都能很快掌握。集算器是基于Java解释执行的动态语言,可以在运行过程中拼出代码执行,这样可以获得更大的灵活性,进一步降低程序设计的复杂度。
集算器定位为(半)结构化数据计算,没有直接提供统计分析、数据挖掘和机器学习等算法,也不擅长处理媒体和地图类数据。

设计集算器的目标,主要试图解决的描述计算的效率和实施计算的效率这两个问题。
计算机听不懂我们说的语言,想让计算机实施计算,想清计算过程后,还需要将这个计算过程翻译成计算机可理解和执行的精确化的形式语言。如果用来描述计算过程的形式语言与我们自然思维相差太远,那就会出现“翻译问题解法的难度远远超过解决问题本身”的怪现象,不仅浪费时间而且很容易出错。
举个例子,我们想计算一支股票最长连续上涨了多少天,这个计算思路很简单,按交易日排序,然后发现比前一天上涨了则加1,下降了则清零,最后看这个计数的最大值。
作为数据库应用程序员,大家都会熟悉SQL,可以试着想想用SQL如何描述这个计算。
相当的困难!在SQL2003标准中有了窗口函数还可以写出来,但也很费劲。如果采用没有窗口函数的SQL92标准时,简直不知道怎么写了。
这是集算器希望解决的问题之一,即提供符合自然思维的形式语言语法,尽量不要让程序设计语言对程序员描述计算过程产生阻碍。

另一方面,集算器还希望提高实施计算的性能。
我们知道,软件不可能实质上提高硬件的计算性能。CPU执行一亿次基本运算、硬盘取出100G数据,这些时间总归要那么多,不可能减少。软件的作用是希望通过合适的算法,让CPU能少执行一些基本运算、硬盘能少读取一些数据,从而达到提高性能的目的。
但如果形式语言中采用的数据和算法模型不够好,有时我们明明知道有更高效的算法也可能无法实施。
仍然用SQL举例:我们要从几亿条交易记录中找出金额最大的前10条,SQL的做法是将数据全部排序后取前10条,但几亿行数据排序是相当慢的动作,特别是内存装不下的时候还要多次读写外存。然而,只要前10条最大记录时并不需要将所有数据全部排序,更没有必要用外存倒换,可以有高效的算法实现。
这是集算器希望解决的问题之二,在这个新的数据和算法模型支持下的形式语言中,可以灵活实现程序员所想到的算法,不会受制于模型而被迫采用低效算法。

相关技术

与Java等高级语言相比,集算器中提供了大量与结构化计算相关的基础对象和方法,这类运算在数据分析处理中很常见,因而完成同样功能的代码会比Java短得多,开发效率也自然会远高于用Java等高级语言。
举个例子, Java对一个数据集做过滤要写出几十行甚至上百行代码,如果想处理通用的数据类型和条件的话还会更长,而用集算器只要一句。
集算器对Java应用有非常好的集成性。集算器本身是用Java开发,与Java有天然的兼容性,而且集算器设计定位就是被集成,很容易被Java主应用程序调用。特别地,对于Java报表工具,用集算器为之提供数据源服务非常方便。

我们知道,用SQL实现很零碎的多步运算很不方便,特别是与次序相关的运算,程序员常常要把数据从数据库中取出来用Java等完成。我们后面会讲到,这是由于SQL的集合化不够彻底、缺乏游离记录等原因造成的。集算器在这些方面做了强化,实现非等值分组、分组重用、序运算及多步计算时思路更为直观。
不过,尽管集算器在大多数情况下的语法要比SQL更简单易写,但它并不能也不打算替代SQL。
数据从数据库读出的IO损耗较高,涉及数据量大的简单运算,数据读出的耗时远远超过运算本身,这种情况还是放在数据库中运算更合适;另外,SQL有元数据机制,其语法的透明度更好,程序员可以无须关心数据的物理存储方案,而集算器是个单纯的计算引擎,没有自成体系的存储机制和语义模型,不能提供透明的语法,需要程序员根据数据存储方案分区对待。
采用集算器不意味着放弃SQL,而是在协助SQL解决不方便完成的运算,比如复杂多步运算外、多个异构数据库的混合运算等场景。

除SQL外,业界并没有通行的专门用于结构化计算的程序语言,而SQL不仅有上述的计算困难,还由于封闭性导致了使用局限性,比如无法随意地用SQL计算本地文件。因此,常有人使用python(pandas)和R等脚本语言完成此类数据处理。
python(pandas)/R的定位是数学风格的统计分析,虽然提供了dataframe对象用于处理结构化数据,但并不专业,对于外存计算则没有提供直接支持。集算器则是专业的结构化数据处理语言,提供了内存的序表对象(功能相当于dataframe的超集)以及外存的游标对象,能方便编写多线程并行计算,涉及多样性数据源(xls,json,mongodb等)时也有更简单的配置和使用方法。
相反地,集算器不擅长数学风格的统计分析,目前还没有提供这类运算类库。
除独立分析外,结构化数据计算还经常在应用程序中发生,集算器还有良好的Java集成性,可以方便地被Java主程序调用;而python/R等则几乎没有任何集成性可言,程序员很难写一个python算法被Java调用。

应用结构

用开发环境IDE编写调试脚本(.dfx文件)后,由嵌入到应用程序中的JDBC驱动包解释执行,IDE和JDBC都可以调用集算服务器集群获得大数据计算能力。

独立应用
集算器的集成开发环境(IDE)具有很好的交互性,可以直接面向有程序设计基础的人员用于桌面交互分析工具。

与一般写成文本的脚本语言不同,集算器的脚本是写成格子里的,这样能有许多好处:无需为临时变量起名,直接像EXCEL一样使用A1、B2这种单元格名;循环和分支语句的作用域用缩进直观界定,不需要使用花括号或BEGIN/END,可以收缩显示节约屏幕,单元格中长代码可以只显示部分并使用漂起的tag式注释,同一行中书写多句代码而仍然清晰,方便阅读时能掌握代码的整体结构。还有完备的调试功能,单步执行,并在过程中随时查看中间变量的计算结果。

交互计算的关键是能够方便的显示和引用中间结果,由上一步决定下一步操作。集算器采用了网格式的代码编写风格。中间结果自然地保存单元格中,可以随时查看,且无须专门起名就可继续引用,这使得多步骤的交互计算非常方便。一般脚本语言用命令行方式实现交互计算,操作效率远远不及集算器。
集算器支持多样性数据源,不仅可以访问常见的数据库,还能够处理本地文件系统中的TXT、XLS等文件。计算结果除了查看外,也可以再写回数据库或文件。
除了能在IDE中执行外,集算器还提供命令行的方式被外部任务调度程序启动,利用其多样性数据源及强大的计算能力,可以用于定时数据清理(ETL)等任务。

Java类库
前面提过,被集成也是集算器的设计初衷。
集算器对外提供标准的JDBC接口,可以方便地嵌入Java开发的的宿主应用中,调用集算器脚本就相当于在数据库中调用存储过程,支持参数输入,其返回结果也是大家熟知的ResultSet,对于Java程序员而言,集成集算器的学习成本非常低。集算器的运行库以jar包形式提交,可以和应用程序一起部署发布,完全无缝集成。
我们知道,Java没有通行的结构化计算类库,碰到这类计算经常需要自己硬编码,非常繁琐。有了好的集成性和强大的计算能力,集算器可以看作是用于批量(半)结构化计算的Java类库。有时没有数据库可用(比如计算文本文件),也就没有SQL那么方便的计算能力可用,或者虽有数据库但运算用SQL很难写需要搬出数据库来实施。这些场合都可以用集算器来辅助Java实现计算。

集算器也像SQL一样支持单个语句调用。有时我们要写的代码较短,就可以不必编写集算器脚本文件而直接在集算器JDBC中写成较长的单语句执行,减少脚本文件降低管理复杂度也增加灵活性。
另外,集算器还是解释执行的动态语言,可以在运行过程中拼出代码执行,从而获得更大的灵活性。

报表数据源
报表工具作为Java应用的一种特例,当然也可以使用JDBC方式集成集算器为之提供数据源服务。
报表开发过程中有许多复杂而且临时的计算,放在报表工具环节由于其复杂性经常很难实现,而放在数据库环节又由于其临时性又会导致资源占用不划算,放在中间Java应用程序环节也会造成程序与代码耦合性高的问题。而使用集算器作为专业的报表数据源准备中间件,把这部分计算剥离出来,能有效降低开发难度;而且集算器脚本可以与报表模板一起管理,还能有效降低应用管理的复杂度。
后面还会详细解释集算器对报表应用的重复提升作用。

结构化数据计算

集合化

集合化是指程序设计语言提供有集合数据类型,能够直接支持集合运算。
结构化数据几乎总是批量的。如果程序语言只提供了针对单条数据的运算,理论上当然也是完备的,毕竟批量计算都能被单条计算组合出来,但是显然会很繁琐。比如像Java/C++这些高级语言都不是集合化的,写个简单的数组求和都要好几行代码,更不要说过滤、连接之类的复杂计算了。

那么,开发一套类库支持集合数据类型及相关运算,是否就可以了?
事情并没有这么简单,Java等高级语言的语法规则不支持表达式描述的函数。举个例子,我们想提供针对集合x的一些基础计算,比如求和,那可以做个x.sum()函数,但要想算平方和呢?是不是要再写个x.sum2()?这就没完没了了,光是求和就会有绝对值和、个位数和、…;类库很快会庞大到无法容忍的地步。
如果只用一个方法描述各种求和,这个sum就要能针对集合成员的函数进行运算,平方、取绝对值这些都是函数,能作为参数传递给sum方法。但是,Java/C++要实现这个机制需要使用函数指针概念,把平方、绝对值都先写成约定好参数形式的函数,这实在太麻烦了。
SQL就没有这个问题,可以简单地写sum(x),sum(x*x),sum(abs(x))。SQL允许用表达式定义一个临时函数,并作为参数传递给某个方法。这个概念在业界的术语叫做lambda语法,这是集合化程序设计语言必须有的机制。
对于Java,有个替代的方法是把这种表达式写进字符串作为参数传递,sum(x*x)要写成sum(“x*x”),这个方法理论上可行,但会导致书写和阅读的巨大困难,而且很可能造成字符串和表达式之间的理解歧义。

集合化语言还需要支持动态数据结构,有结构数据是一种基本数据类型,在程序执行过程中可能随时产生。解释执行的SQL可以较好地支持,而Java这类编译型语言就不行了。
SQL满足集合化语言的基本特征,也因此是目前最常用的结构化数据运算语言。

集算器也是一种集合化的程序语言,同样是解释执行,支持lambda语法,也支持动态数据结构,当然,还提供了丰富的结构化运算基础类库。
常规的结构化计算:

A
1 =file(“D.csv”).import@tc(name,sex,age)  
2 =A1.select(sex==”M”&&age>=25||sex==”F”&&age>=23) 过滤
3 =A2.sort(name) 排序
4 =A2.groups(sex;avg(age):age) 分组汇总,产生新数据结构
5 =A2.id(left(name,1)) 唯一值

???????? 直接集合运算:

A  
1 =file(“T1.txt”).import@ti(id)  
2 =file(“T2.txt”).import@ti(id)  
3 =A1^A2 交集,即T1和T2共有的值
4 =A1\A2 差集,即T1中有而T2中没有的值

离散性

离散性是指集合成员可以游离于集合之外存在,并独立地参与运算,对于结构化数据,离散性更特指记录能够游离于表之外和其它记录及表一起运算,包括再构成新的集合。
显然,Java这些高级语言都具有良好的离散性,对象的实例可以独立存在和运算。
但是,SQL的离散性却很差。SQL的记录必须依附于某个表并与这个表一起参与运算,从表中取出记录的动作实质上是复制数据后形成新临时表,和原表没有关系了。SQL没有表示记录的数据类型,记录只能被当作只有单条记录的临时表来处理。

我们知道,把一个复杂的运算拆成多个步骤后能够大大简化实施难度,而分步计算常常伴随着离散性,缺乏离散性会对分步计算的描述造成麻烦。
举个例子:要用人员表计算张三和李四的年龄差和收入差,思路很简单,分别取出张三和李四对应的记录,再做减法即可。这里涉及对单条记录的多次引用,如果用SQL描述,由于其对游离记录的表示方法很不自然,则要么查询多次分别取得两人的年龄和收入做减法,要么把两条记录连接成一条宽记录再做减法,写法都很繁琐。
而集算器继承了Java等语言的良好离散性,描述这种运算很自然:

A  
1 =employee.select@1(name=="张三")  
2 =employee.select@1(name=="李四")  
3 =A1.age-A2.age  
4 =A1.salary-A2.salary  

结构化数据大量出现之前,计算机处理的数据大都是数值。延用数学上的习惯,数值的运算结果是和原操作数不再相关的另一个数值,即每次运算的结果都会产生新数据。这对于简单数值没有太大问题,而对于记录、对象这类结构化数据则不合适。记录是个复杂的数据类型,它有自身的属性,如果每次运算都复制,不仅会造成空间时间上的多余,而且不能引用到原记录实施进一步访问。如果是只读的运算复杂还只是资源的浪费,如果要涉及对原记录的修改则无法进行了。
这种情况在实际应用中并不罕见,但一般都伴随着很复杂的业务,不适合做成简单的例子。这里用个业务上不很恰当的例子来说明。
取出销售额在前10%的代理商,再给予5%的销售额的奖励。前10%在SQL不能简单用地WHERE条件实现,就只能先用子查询取出这些代理商的主键,再用于针对原表的UPDATE语句,这破坏了语法的集合化。这里用前10%的例子,主要是为了说明实际业务中筛选条件常常很复杂,筛选过程可能有多个步骤,无法简单地写到WHERE子句中。
用集算器则可以按自然思路分步实现:

A  
1 =agent.sort(amount:-1).to(agent.len()*0.1) 取前10%
2 =A1.run(amount=amount*1.05) 奖励销售额

离散性更重要的应用在实现引用式外键。
SQL没有游离记录数据类型,字段的取值当然也不能是另一条记录。SQL采用外键来表示记录之间的引用,关联表较多的时候,JOIN语法写起来非常复杂、容易出错,可读性也很差。如果字段的取值可以是另一条记录,则可以简单地把外键对应的记录看成当前记录的字段,只是这个字段还有子字段。Java等高级语言的对象引用机制就是这样,无论有多少层关联,代码都会很清晰。
集算器有离散记录,允许字段取值为记录,则可以方便实现引用式外键计算:

A  
1 =file(“D.csv”).import@tc()  
2 =file(“P.txt”).import@t(id,area)  
3 =A1.switch(aid,A2:aid) 建立外键引用
4 =A3.select(aid.area==”Beijing”) 用外键引用记录的字段过滤

SQL缺乏离散性还有技术方面的的历史原因。在发明SQL的70年代,计算机的内存太小,而在外存实现指针式引用的成本很高,一定要实现,针对于当时还不算复杂的业务需求就不划算了。而40年后的今天,硬件能力的提升已经使离散性不再那么困难,而且业务需求的复杂度也完全不同了。
集算器是良好的离散性的集合化程序语言,集成了SQL与Java的共同优点,用于结构化数据计算更方便。

更彻底的集合化

SQL是集合化的语言,但集合化并不够彻底,彻底的集合化需要离散性来支持。

分组子集
除了数据表外,SQL没有显式的集合数据类型,在分组时会强迫计算出聚合值。但有时我们感兴趣的不只是聚合值,还有分组子集,这时SQL就很难处理,要用子查询反复计算。
集算器有集合数据,也提供了返回子集的分组函数。这样就能方便地处理分组后运算。
比如找出总分500分以上的学生的各科成绩记录。SQL需要先分组计算出各学生总分,从中过滤出500分以上的,再用这个名单与原成绩记录JOIN或用IN判断,较麻烦且要重复取数。而集算器则可以按自然思路写出来:

A  
1 =db.query("select * from R")  
2 =A1.group(student).select(~.sum(score)>=500).conj()  

这种分组后却要返回子集明细记录的情况很多,分组聚合是用来实现某种过滤的中间步骤而不是结果。后面要讲到的报表按分组汇总值排序的例子也是类似的运算。

有时即使是只要返回聚合值,但聚合计算较为特别,难以用简单聚合函数表示时,也需要保留分组子集用于再计算。
这类计算在现实中并不少见,但因为计算复杂,常常涉及较多的业务背景,不适合举例说明,这里改造了一个简化后的例子:
设有用户登录表L结构为:user(帐号),login(登录时刻);现要计算出每个帐号最后登录时刻以及该时刻前三天内的登录次数。
找出最后登录时刻很容易,但如果不保留分组子集时则很难计算出那个时间段登录次数。用SQL需要先分组计算出最后登录时间,与原表JOIN后过滤相应时间段的记录再次分组汇总,不仅麻烦而且记录效率很低。而使用集算器保留了分组子集则容易实现分步式计算:

A  
1 =db.query("select * from L")  
2 =A1.group(user;~.max(login):last,~.count(interval(login,last)<=3):num)  

其中~就是按user分组后的子集。
如果数据有序还可以用高效的方法计算:

A  
1 =db.query("select * from L order by login desc")  
2 =A1.group(user;~(1).login:last,~.pselect@n(interval(login,last)>3)-1:num)  

有序聚合
取出每组的前N条、最大值对应记录等也是较常见的运算。显然,这些都可以用保留分组子集的方法实现,但由于这类运算较常见,集算器将其理解成某种聚合而提供了专门的函数,这样就可以采用和普通的分组汇总基本一致的处理方式。
SQL没有集合数据类型,离散性也不好,无法提供返回结果是记录引用集合的聚合函数,这种运算就需要子查询等繁琐的方式,经常还会导致大排序而损失性能。

先看最简单的情况,用户登录表L结构为:user、login(登录时刻)、IP-address、…;列出每个用户首次登录的记录。
SQL可以用窗口函数生成组内排序序号,并取出所有序号为1的记录,但窗口函数是在结果集上再计算的,因而必须用子查询再过滤的形式,写法有些复杂。而不支持窗口函数的数据库写起来就会更困难了。
集算器提供了group@1方法可直接取出每个分组的第一个成员。

A  
1 =db.query("select * from L order by login")  
2 =A1.group@1(user)  

这类日志数据经常存在文件中,且已经对时刻有序,用集算器就可以直接取出第一条而不必再排序。数据量大到内存放不下时也可以基于游标实现类似的运算。

股价表S的结构为:code(股票代码)、date、cp(收盘价);计算每支股票最近的涨幅。
计算涨幅涉及到最后两个交易日的记录,使用SQL需要用两重窗口函数分别实施组内跨行计算再取出结果的第一行,写法繁琐。集算器提供了topN聚合函数,利用集合数据直接返回多条记录作为汇总值参与进一步计算。

A  
1 =db.query("select * from S")  
2 =A1.groups(code;top(2,-date)) 最后2个交易日的数据
3 =A2.new(code,#2(1).cp-#2(2).cp:price-rises) 计算涨幅

聚合函数并不会先计算出分组子集,而是直接在已有结果上累积,这样可获得更高的性能,而且在数据量大到内存放不下时还可以基于游标工作。
如果数据已有序,则可以更高效地用位置取出相应记录:

A  
1 =db.query("select * from S order by date desc")  
2 =A1.groups(code;top(2,0)) 直接取前2条
3 =A2.new(code,#2(1).cp-#2(2).cp:price-rises)  

取出最大值对应记录、第1条最后1条等类似计算都是topN聚合的特例了。

逆分组
与分组汇总相反,逆分组指将汇总数据拆分成多条明细数据。这种情况虽不多见,但碰到了用SQL很难处理,这里仅举一例。
分期付款表结构为:编号、总金额、起始日、总期数;要将每笔贷款拆分成多期记录,结构为:编号、期数、还款日、金额。总金额将简单地平均分配到每一期,一期为一个月。
SQL的集合化不彻底,从明细到汇总很容易,反过来就困难很多,要将记录数变多一般是和一个序号表JOIN或用递归查询,思路很不直接。而集算器则按常规思路写出来即可:

A
1 =db.query("select * from I")
2 =A1.news(periods;no,~:seq,after@m(start,~-1):date,sum/periods:amount)

有序计算

有序计算是结构化数据计算的重要内容,前面已经少量涉及过,这里专门提出来讲。
人们对序运算是天然有兴趣的,一个数据总是不变,那看一次就行了,变化的数据才更让人关心,比上期、同期比、移动平均等等,都是有序运算。
描述有序计算离不开集合化和离散性的良好配合。序是指成员在集合中的次序,只有在集合化的语言中,序才有意义;而用序访问又需要把成员单个取出来,以及取出其前一个后一个成员,这又需要良好的离散性。
集算器中的所有集合都是有序的,可以用序号访问,提供了很方便的语法。

跨行引用
早期SQL不直接支持跨行引用,要生成序号后再JOIN,极其繁琐困难。引入窗口函数后的SQL能够较方便地引用其它行数据,但写法仍不简洁,有多个跨行引用项时代码会很长。而且如前所述,窗口函数在其它运算结果集基础上再实施,对窗口函数计算值的再引用就要写成子查询的形式,仍然繁琐。
MySQL不支持窗口函数,但支持在SQL中使用变量,可以引用到前面的行,但无法引用到后面的行。
集算器提供了方便自然的跨行引用语法。

各产品月销售表S结构为:prod(产品)、month、sales;现要找出销量比上月多10%的记录。

A  
1 =db.query("select * from S order by prod,month")  
2 =A1.select(if(prod==prod[-1],sales/sales[-1])>1.1)  

排序后可以简单用[-1]就可以引用前一月的数据,且可以直接基于跨行计算值过滤。使用SQL窗口函数则要用子查询,MySQL则要定义两个临时变量。

再计算上表中各月前后一个月的销量移动平均值:

A  
1 =db.query("select * from S order by product,month")  
2 =A1.derive(if(prod==prod[-1]&&prod==prod[1],sales{-1:1}.avg()):moving-avg)  

计算移动平均涉及到向后引用和集合引用,用[1]可引用下一行数据,{-1:1}可引用从上一行到下一行的字段值集合。类似地,SQL窗口函数也需要子查询先把相应行计算出来再做移动平均;而MySQL的变量不能后向引用,就很难直接计算了。

再看一例,简化的事件表E结构为:seq(序号),time,…;时刻应当和序号同步递增,但可能有错误,需要找出时刻没有和序号同步递增的记录。

A  
1 =db.query("select * from E order by seq")  
2 =A1.select(time!=max(time{:0})||time!=min(time{0:})) 和前后所有记录对比

取集合时还可以从头取后或取到尾。SQL窗口函数也支持类似的写法,但两次比较要做两个不同方向的排序,当然了必须要用子查询。

有序分组
SQL只提供与次序无关的等值分组,但有时分组的键值并不能在每条记录中找到,而是和记录的次序有关,这种情况,用SQL又需要使用窗口函数(或其它更麻烦的手段)制造出序号才能实现。
集算器提供了与次序相关的分组机制,方便用于与连续区间相关的计算。

收支表B结构为:month、income、expense;找出连续亏损达三月或以上的那些月份的记录。

A  
1 =db.query("select * from B order by month")  
2 =A1.group@o(income>expense).select(~.income<~.expense && ~.len()>=3).conj()  

group@o表示在分组时只比较相邻记录,如果相邻值发生变化则会分出一个新组。这样就可以根据收入支出的比较把收支记录分成赢利、亏损、赢利、…这样的组,然后取出其中亏损且成员不少于3的组再合并起来。

还是这个表,希望计算收入最长连续增长了几个月。可以设计这样的分组机制:收入增长时和上月分作一个组,收入下降时则分出一个新组,最后统计组成员的最大值。

A  
1 =db.query("select * from B order by month")  
2 =A1.group@i(income<income[-1]).max(~.len())  

group@i将在条件变化时分出一个新组,即收入降低时。
在窗口函数的支持下,SQL也能实现本例和上例的思路,但写法非常难懂。

区间合并也是常见的有序分组运算。设有事件发生区间表T有字段:S(开始时刻)、E(结束时刻);现在要将这些区间中重叠部分去除后再计算该事件实际发生的总时长。

  A  
1

$select S,E from T order by S

 

2

=A1.select(E>max(E{:-1}))

去除被包含的条目
3

=A2.run(max(S,E[-1]):S)

去除重叠时间段

4

=A2.sum(interval@s(max(S,E[-1]),E))

计算总时长

5

=A2.run(if(S<E[-1],S[-1],S):S).group@o(S;~.m(-1).E:E)

合并有重叠的时间段

这里给了多种目标的处理方法,充分利用了跨行运算和有序分组的特点。SQL要实现这种运算简单用窗口函数已经做不到了,需要用到很难理解的递归查询。

位置利用
对于有序的集合,有时我们需要直接用序号访问成员。SQL延用了数学上的无序集合概念,要生成序号再用条件过滤才能访问指定位置的成员,这对许多运算造成很大的麻烦。
集算器采用了有序集合机制,允许直接用序号访问成员,这类运算要方便得多。
比如经济统计中常用到的在众多价格中找出中位数:

A  
1 =db.query@i("select price from T order by price")  
2 =A1([(A1.len()+1)\2,A1.len()\2+1]).avg()  

位置还可以用于分组。事件表E结构为:no(序号)、time、act,动作有开始、结束两种,现在要统计事件持续的总时长,即每一对开始和结束之间的时间之和。

A  
1 =db.query@i("select time from E order by time")  
2 =A1.group((#-1)\2).sum(interval@s(~(1),~(2))  

#表示记录序号,group((#-1)\2)即将数据每两个分成一组,然后针对每组计算时长再合计即可。

根据位置还能进行相邻跨行引用。设有股价表S结构为:date(交易日)、cp(收盘价);现列出计算出股价超过100元的交易日及当日涨幅。

A  
1 =db.query("select * from S order by date")  
2 =A1.pselect@a(cp>100).select(~>1)  
3 =A2.new(A1(~).date:date,A1(~).cp-A1(~-1).cp:price-rises)  

pselect函数将返回满足条件的成员位置,使用这些位置就可以方便地计算涨幅,而不必像使用窗口函数时事先计算出所有涨幅再过滤。

有时我们要求分组的结果是连续区间,要补齐中间缺省的空子集。SQL实现这个过程很麻烦,要手工先造出连续不断的分组区间再left join要统计的数据表,子查询将不可避免。集算器则可以直接利用位置来实现对位分组。
简化的交易记录表T结构为:no、date、amount。现需要按周统计累计的交易金额,没有交易记录的周也要列出。

A  
1 =db.query("select * from T order by date")  
2 >start=A1(1).date  
3 =interval(start,A1.m(-1).date)\7+1 计算总周数
4 =A1.align@a(A2,interval(start,date)\7) 按周分组,可能有空集
5 =A4.new(#:week,acc[-1]+~.sum(amount):acc) 汇总并计算累计

游标技术

当数据量太大而不能全部读入内存时,这时一般采用游标技术来处理。
游标的机理很简单,针对一个大数据源,按顺序每次读入一段数据进内存来处理,处理完毕后释放这些内存再读下一段,循环至所有数据全部读取完毕,处理也跟着完成。
游标的原则是只从前向后单向移动,所有数据只遍历一次。许多大数据运算都可以用游标完成,比如求和计数,结果集不大的分组汇总等,排序和大结果集分组汇总也可以用游标实现,不过需要使用中间结果的缓存机制。

多级游标
和其它的游标机制不同,集算器在游标上封装了计算功能,可以针对游标计算出结果,许多运算的返回结果仍然是个游标,可以连续操作。

  A  
1 =file(“Products.txt”).import().primary@i(id) 读入商品列表并建立索引
2 =file(“Sales.txt”).cursor() 建立游标,准备遍历
3 =A2.select(quantity<=10) 过滤,仍返回游标
4 =A3.switch(productid,A1:id) 建立连接指针,仍返回游标
5 =A4.groups(;sum(quantity*productid.price)) 求和汇总

A2建立原始游标,A3在A2基础上过滤,A4在A3基础上建立连接指针,A5最后针对A4计算出汇总结果。实质的数据遍历动作只在A5中的计算过程时才实施,A2,A3,A4仅仅是记录游标信息,并不实际运算。但这种多级游标的代码看起来像是一步步地处理游标,理解和编写都很简单。
SQL型的数据库都提供了游标,但只有简单的fetch数据功能,没有封装运算,更没有多级游标,要在这种游标基本的完成复杂运算会相当麻烦。

程序游标
多级游标非常方便,但每个环节的处理都要用一个函数写出来。有时某个环节的运算处理较为复杂,很难用一个函数拼出来,最好是写成一段代码才方便理解及将来维护。
集算器提供了程序游标方法,可以用一段代码定义一个游标。

  A B 游标处理程序sub.dfx
1 =file(“Sales.txt”).cursor()  
2 for A1,1000 每次取出1000条记录处理
   
  return … 处理后的结果返回

子程序分批读入数据进行复杂处理后分批返回,返回数据的记录数和读入数据的记录数没有关系。

  A 主程序
1 =cursor("sub.dfx") 使用子程序
2 =A1.fetch( 100 ) 当作普通游标使用

主程序将程序定义的游标当作普通游标使用,cursor函数将会缓存子程序返回的数据,主程序请求时即返回,缓存的数据不足时再去继续执行子程序进一步获取,获取后子程序暂停执行等待下一次数据获取请求,直到数据取完或主程序要求关闭游标时子程序才会彻底退出释放。这样就可以用程序代码实现多级游标中的某些环节。

有序游标
用户行为分析是常见的运算,其特点是:单用户内的运算很复杂,但跨用户的运算几乎没有,比如计算用户最近几周在线时长增长率,房贷帐户的利息及余额等;单用户数据量很小,可内存处理,全用户数据量很大,无法全读内存。这样最好是有一种机制使得每次读入一个用户的数据处理,算完后再读下一个。
前面讲过的有序分组对于游标也有效,集算器可以从有序游标中每次读入一组数据,这样就能方便地实现这类运算。

  A B  
1 =file(“userlogs.txt”).cursor() 按用户id排序的源文件
2 for A1;id 从游标中循环读入数据,每次读出一组id相同
3   处理计算该组数据

只要游标源数据有序就可以,无论来自数据库还是文件都可以。
后面讲到文本结构化时还可以看到更多类似的例子。

动态列能力

彻底的集合化,还包括在列上的集合运算。
SQL是解释执行的语言,可以临时生成动态的数据结构,这方面问题不大。不过,SQL认为列是数据的属性,是静态的,没有提供针对列上的集合运算。这样在我们事先不知道列的信息或列很多需要通用方式处理时就会显得很麻烦。

列间统计
体育测验表PE结构为:name、100m、1000m、long-jump、high-jump、…;成绩等级分为A、B、C、D四档,现在要统计各等级在所有项目上的人数合计。
思路很简单,把各项目成绩合并起来再分组汇总即可。SQL要用大长串的union合并各项目,写起来很繁琐。而且列数不确定时还要从数据库中动态获取列名拼接,更为复杂。
集算器支持列上的集合运算,全动态写法轻松简单:

A  
1 =db.query("select * from PE")  
2 =A1.conj(~.array().to(2,)) 从第2字段的各项目成绩合并起来
3 =A2.groups(~:grade;count(1):count) 分组汇总

通用转置
对于简单的静态转置,某些数据库提供了pivot和unpivot语句实现,不支持这些语句的数据库也可以用较繁琐的条件表达式和union语句写出来。但转置结果的列由行变换而来,经常是动态的,这时就需要用先算出目标列和行,然后动态拼出另一句SQL来执行,但SQL不提倡分步运算,实现这种运算即繁琐又难理解。

学生成绩表R结构为student、semester、maths、english、science、pe、art、…,需要双向转置为student、subject、semester1、semester2、…。
对于简单转置,集算器也提供了pivot函数:

A B C
1 =db.query("select * from R")
2 =A1.pivot@r(student,semester;subject,score)
3 =A2.pivot(student,subject;semester,score)

A2将列转成行,A3再将行转成列,从而实现双向转置。

还可以采用代码稍复杂但理解起来更简单的通用转置方案:

A B C
1 =db.query("select * from R order by student,semester")
2 =create(student,subject,${A1.id(semester).string()})
3 for A1.group(student) for 3,A1.fno() =A3.field(B3)
4     >A2.record(A1.student|A2.fname(B3)|C3)
5 return A2    

A2中先用宏生成目标结果集,再在A3-C4的循环中将数据变换后插入到结果集,这是集算器实现转置任务的标准流程,分步运算使代码更清晰易懂。这个方案也可用于静态或单向转置,代码更简单。集算器的列访问机制和动态语言的灵活性,使得各种转置,静态或动态、行转列还是列转行以及双向同时,都可以采用一致的方案实现。

转置计算
设有帐户状态变化表T:

seq acount state date
1 A over 2014-1-4
2 A OK 2014-1-8
3 A lost 2014-3-21
     

需要输出指定月份帐户每日的状态,若当日无记录,则延用前一日的状态:

account 1 2 3 4 5 6 7 8 9 3 1
A       over over over over OK OK OK
...                      

严格地说,这是个静态转置,但列数较多且有规律,完全静态写出很麻烦。而且转置过程中还涉及到列间有序计算,即使有pivot语句用SQL也难以写出。
而采用集算器则仍然按上述的流程即可简单实现:

A B
1 =db.query("select * from T where year(date)=? and month(date)=?",2014,1)
2 =create(account,${to(31).string()})
3 for A1.group(account) =31.(null)
4   >A3.run(B3(day(date))=state)
5   >B3.run(~=ifn(~,~[-1])
6   >A2.record(A3.account|B3)
7 return A2  

这里只涉及单向转置,比上例少一层循环,B3-B5中按规则计算插入数据的过程稍复杂些,但整体过程并无不同。

准结构化数据

我们常常会遇到在数据库外的文本、json/xml等数据,有许多原始数据就是这种形式,封闭的SQL只能计算数据库内的数据,而且这些还没有完全结构化的数据也不能直接用SQL计算。有时我们只能把这些数据导入数据库再计算,由于这类准结构化数据缺乏数据库要求的强数据类型特征,导入过程中常常伴随着繁琐的数据整理,其本身也是一种计算。
集算器作为开放的计算引擎,且由于数据类型的丰富性,对这类数据也能进行计算。

文本可以说是除了数据库外几乎最常见的数据存储形式,针对文本的计算非常重要。然而文本本身没有计算能力,这样对文本的计算就需要借助程序设计语言编码,而大多数用于文本处理的程序语言都没有集合化的,编写批量运算时很繁琐。perl,python,R等脚本语言在这些方面有所改善,但对批量结构化计算的支持仍然不足,而且集成性也较差。
还有一类json/xml等多层次结构化数据,采用缺乏离散性特征的集合化程序语言,会很难描述这类数据,计算就更难实施。
而集算器则没有这些问题。

文本解析
文本有时并不总是很规范的结构化数据,在计算前需要一定的解析动作,要求程序语言有集合化色彩的字符串处理能力。

文本T.txt的行内数据项由不确定数量的空格分隔开:
20010-8-13 991003 3166.63 3332.57? 3166.63? 3295.11
2010-8-10 991003 3116.31 3182.66? 3084.2?? 3140.2
……
现在要计算每行最后四项数据的平均值列表。用集算器只要一句:

A
1 =file("T.txt").read@n().(~.array@tp(“”).to(-4).avg())

read@n()将文本读入成字串集合,array@t(“”)将字串按不定数量的空白符拆成子串集合,@p将自动解析成合适的数据类型以便进一步计算(这里计算平均)。

将逗号分隔符文本T.csv中行内数据项数不少于8项的行的前8项写出成另一个文本R.txt,分隔符替换成|(某些银行系统采用的分隔符):

A
1 =file("T.csv").read@n().(~.array(“,”)).select(~.len()>=8)
2 >file(“R.txt”).write(A1.(~.to(8).string(“|”)))

string()函数可将集合按指定分隔符再拼成字串。

文本T.txt中都是形如下行的串,需要按字符US前的州名(LA)分组拆分成多个文件。
COOP:166657,'NEW IBERIA AIRPORT ACADIANA REGIONAL LA US',200001,177,553
……

A
1 =file("T.txt").read@n()
2 =A1.group(mid(~,pos(~," US'")-2,2):state;~:data)
3 >A2.run(file(state+".txt").export(data))

集算器也提供了对正则表达式的支持以应对复杂的拆解需求。不过由于正则表达式的使用难度较大且性能较差,一般建议仍然用常规方法实现。

结构化
把不太规范文本转换成规范的结构化数据,有时会写入数据库,是很常见的文本计算。对于一些特殊的格式文本,利用前述的有序计算机制,可以用集算器方便地实现结构化。

日志S.log中每3行构成一段完整信息,需要将其解析成结构化数据后再写进T.txt:

A B  
1 =file(“S.log”).read@n()    
2 =create(…)   建立目标结果集
3 for A1.group((#-1)\3) 按行号分组,每3行一个单位
  从A3(这3行)中解析出字段值
  >A2.insert(…) 插入到目标结果集
>file(“T.txt”).export(A2)   写出结果

有了按行号分组的机制,就可以用循环每次处理一组数据,简化难度。
显然,更简单的单行情况是其特例。

如果S.log大到不能读入内存,也可以使用游标逐步读入并写出:

A B  
1 =file(“S.log”).cursor@si() 创建游标用流式读入文件
2 =file(“T.txt”)   结果文件
3 for A1,3 每读入3行执行一轮循环
  从A3(这3行)中解析出字段值
  >A2.export@a(...) 追加写到文件中

熟悉的用户还可以优化代码,使得解析多条记录后一次写出,会有更好的性能。

日志S.log中每段完整信息均以”---start---“开头,包含行的数量不确定。这时只要将前面的A3格改成:

3 for A1.group@i(~==”---start---”) 出现---start---时会产生一个新分组

类似地,大文本时也可以用游标处理,也是将上面A3格改成:

3 for A1;~==”---start—“:0 出现---start---时另起一轮循环

不定行还有一种情况,同一段信息的每一行都有相同的前缀(比如该段日志所属的用户号等),当这个前缀发生变化时就表示开始另一段信息了,这时仍然只要简单地修改A3代码即可处理:

3 for A1.group@o(left(~,6)) 前6个字符变化时产生一个新组
3 for A1;left(~,6) 前6个字符变化时另起一轮循环

前一小节的运算也可以改造成使用游标支持大文本。

查找统计
在目录下所有文本中找出含有指定单词的文件,并列出所在行内容及行号:

A  
1 =directory@p(“*.txt”)  
2 =A1.conj(file(~).read@n().(if(pos(~,"xxx"),[A1.~,#,~].string())).select(~))  

grep是常用的unix命令,但有些操作系统下没有,且在程序中实现也不简单。集算器提供了文件系统的遍历功能,结合文本计算能力,只要两句代码就能完成。

列出文本T.txt中所有出现过的单词及次数,忽略大小写:

A  
1 =lower(file(“T.txt”).read()).words().groups(~:word;count(1):count)  

WordCount是著名的练习题,集算器提供了words()函数将串拆分成单词,只要一句就可以完成这个运算。

列出文本T.txt包括字母a,b,c的所有单词,忽略大小写:

A  
1 =lower(file(“T.txt”).read()).words().select(~.array(“”).pos([“a”,”b”,”c”]))  

由于次序问题,判断字母包含不能用子串查找,要用array(“”)将串拆成单字符集合,再用集合从属去判断。有集合运算支持的集算器也只要一句即可。
这些运算都可以用分段或游标的方式简单改造以支持大文本。

json/xml
Java有足够多的类库用于解析和生成json/xml,但缺乏后续计算能力。集算器支持多层结构数据,可以不丧失信息地将json/xml解析成可计算的内存数据表进一步处理。
设有如下格式的json数据:
{
“order”:[
{
“client”:”北京润乾软件”,
“date”:”2015-6-23”,
“item” : [

“product”:”HP笔记本”,
“number”:4,
“price”:3200
},
{
“product”:”DELL服务器”,
“number”:1,
“price”:22100
}]
},…]
}
要写入数据库中order表,结构为:orderid,client,date;和orderdetail表,结构为:orderid,seq,product,number,price的orderdetail表,orderid和seq按顺序生成即可。

A  
1 =file(“data.json”).read().import@j().order  
2 =A1.new(#:orderid,client,date)  
3 =A1.news(item;A1.#:orderid,#:seq,product,number,price)  
4 >db.update@i(A2,order)  
5 >db.update@i(A3,ordedetail)  

集算器可将多层json串解析成多层数据集,A2的item字段取值又是一个表。
除了解析外,也可用集算器将多层数据集生成多层json串。

大数据计算技术

大数据技术

SQL
结构化大数据计算的技术本质是高性能问题,也就是如何能计算得更快。要做的计算内容也就是过滤、分组、排序、连接这些,理解起来不需要太多的数学知识。
当前用来描述结构化数据计算的语法主要就是SQL了,除了数据库厂商外,很多大数据解决方案也在努力实现SQL。但是,如开始所举那个取前10条的例子,使用SQL,或者更明确地说是SQL采用的数学基础关系代数,有时会妨碍计算速度的提高。

对于一些简单的运算,比如常见的GROUP+SUM,因为过于简单,也就没有什么办法再优化以减少CPU和硬盘的动作量了,无论谁去做,都要做这个数量的基本动作,这个时间也没办法再减少了。
经常有些大数据解决方案号称比传统数据库快数十上百倍,但又不指明具体的运算内容以及环境场景,这就是忽悠了。比如用列存和Oracle的行存比,用内存和Hadoop的外存比,那要不快几十倍才不正常,谁都能做得到,没什么值得说的。如果都是同样的硬件环境和数据存储机制,对于这种简单运算,不可能存在什么方案比传统数据库有数量级的性能提高,提高两三倍已经不得了了。

但是,对于不那么简单的运算,SQL就常常有被优化的余地了。如前面的说的从上亿交易记录中取金额最大的前10条,集算器的做法是不同的。在前面讲集合化时说过,我们把top N这样的运算设计成一种和SUM、COUNT等同地位的聚合运算,不同的只是SUM、COUNT这些返回的是个单值,而top N返回的是一个集合,但聚合过程并没什么本质不同。这样,只需要遍历一次数据就可以了,而且排序范围也缩小很多,性能大幅度提高。
SQL,或者说关系代数,没有办法表达这种运算,只能寄希望于数据库厂商的优化工作了。SQL这种问题很多,下面会逐步碰到。

从这个例子大概能看到集算器做大数据计算的思路,我们设计了语法体系,提供了更丰富的数据对象及相关基本运算,让程序员可以根据计算任务和数据的特征设计合理的计算方案,充分利用硬件资源,达到最优的计算性能,不要像SQL这样由于语法和数学体系的限制导致我们不能采用更高效的计算方案。
需要说明的是,这样做并非全是好处,这种搞法会导致算法的透明化程度降低,程序员需要对数据的物理存储和运算过程的数据变换都有深入的了解。而SQL则有很好的透明性,程序员不必关心数据物理存储方案和执行路径。这是矛盾的两面,需要用户自己权衡了。

做SQL解决方案的厂商很多,甚至可以说已经做到极致了,能在SQL框架下顺利解决的大数据问题,已经有足够多成熟方案供选择,我们就不打算再闯进这个阵营中了。
但是,除了上面那类SQL语法无法描述出高性能计算的问题外,程序员们都知道,有许多运算用SQL很不好写,还需要自己写代码,而这些任务也常常涉及大数据高性能的问题,也就是集算器的定位所在了。
当然,集算器也可以连接SQL数据库取出数据继续计算,可以与SQL解决方案配合,共同解决大数据性能问题。

Hadoop
说到大数据技术,就不能不提Hadoop。集算器也提供了集群并行机制,但没有基于流行的Hadoop体系,完全是自己的并行和集群机制。
Hadoop的优点很多,但这里主要谈谈其缺点,也就是不采用Hadoop的原因。

Hadoop是个庞大的重型解决方案,虽然软件本身开源免费,但要配置用好它并不容易,维护支持成本不低。Hadoop其实是个高端产品,并不很适合中小用户。
Hadoop的设计目标是几百几千的大规模集群,这个规模下,在一个任务的执行周期,也就是几小时内,都有可能发生设备故障。所以,Hadoop投入了相当多资源用于提供超强的容错,这是非常必要的。而且,这种大规模的集群,显然不可能针对每个节点提供个性化的管理控制机制,否则工作量会大到累死人,Hadoop必须采用自动化的统一管理。
而集算器是个轻量级的东西,设计目标是几个到十几个最多几十个节点的中小规模集群,甚至单机也可以很好地工作。这种规模不需要太强的容错能力,集算器能做到有节点故障时整个集群仍能工作,但某个任务执行过程中有节点故障时就可能导致任务失败了,在几小时的任务周期内,这个规模的节点全能正常工作还是大概率事件。
小规模的集群也可以针对每个节点进行个性化配置,这样可以更有效地利用硬件资源,增加的管理工作量可以接受。

Hadoop有确定的框架体系,程序员只能去适应,这样会限制灵活性,难以写出适应业务和数据特征的代码。比如想控制HDFS的文件冗余方案,让不同文件的冗余数不同,我们后面会谈到特定的冗余方案能有效地减少网络传输量,也许能够通过修改Hadoop源码来实现,但并不轻松,而且随意修改底层源码会影响升级。还有,MapReduce为了容错把任务拆得太碎,难以直接控制执行次序,在编写有序和关联的运算就很困难,需要费劲去绕。
集算器的思路则不是这样。框架很重要,设计一个好框架也很耗时,但这不是工具能够帮得上忙的。框架实现的代码量很小,减少这部分工作量对提高开发效率作用不大。而无论用什么框架,总需要一些底层的基础方法,这是耗用开发时间最多的地方,那么我们就写出来让程序员调用,而整体流程管理由程序员用代码自行控制。
集算器几乎没有框架,程序员可以自由决定每个节点的计算任务和数据分布,这样能有更高的性能,但坏处是需要更细致的工作量,所以说集算器适合中小规模集群甚至单机,而不适合大规模集群,集算器是个轻量级大数据解决方案。

Hadoop还是个相对封闭完整的体系,要应用它的计算方案需要先把数据放地Hadoop之内,Hadoop不能计算关系数据库或其它网络文件系统中的数据;而集算器则是个单纯的计算引擎,相对来讲更为开放,它不挑数据源,来自关系数据库、NoSQL数据库、文件数据,包括HDFS文件都可以被集算器计算,计算结果也可以再写入这些数据源。数据在进入某个体系之前仍然都有计算需求,甚至可以说把数据送进体系本身也是一种计算,集算器可以在这个阶段发挥作用。

内存计算

所谓内存计算,是指把数据加载进内存再计算。内存计算常常用于即时报表和查询。现代计算机的内存已经可以做到几十几百G甚至上T,这个规模的数据量,用最快的硬盘遍历一次也需要数分钟甚至小时的时间。除了少量基于事先建好的索引的检索任务以外,当数据规模大到现代计算机内存装不下的时候,也不能指望用外存还能实现即时响应,这可以用于判断用户希望的即时响应需求是否可行。

我们知道,内存的速度比外存快得多,但内存的优势还不仅仅在于此,内存的关键优势还在于可以频繁随机小量访问。这里有三个定语,频繁、随机、小量。频繁是指可以访问很多次,随机是批每次访问的内容不同,小量是指访问读写的内容,也就是字节数,都很少。从内存中1万个不同地址取数,每次只取100字节,耗用的时间和连续取出100万字节是差不多的。
硬盘则完全不同,机械硬盘随机访问时会导致磁头跳动的动作,比读本身要慢得多了,固态硬盘会好一些;硬盘被操作系统分成了簇,每次读写单位都至少是一个簇,一般是4K,更小的访问量并不会耗时更少;而且要访问硬盘需要做许多IO准备工作,频繁访问会重复执行这些动作。也就是说,频繁、随机、小量这三个定语对于硬盘都不具备。

外键指针化
从外键指向的表(也就是我们平常所说的维表)获取字段与本表(也就是我们平常说的事实表)的字段一起运算,是SQL中很常见的JOIN动作。
对维表的外键式访问就是典型的频繁、随机、小量,维表。从事实表的次序看,它引用维表记录的次序是不定的,即随机;每次只要取得维表的一行记录的字段参与计算,这是小量;事实表记录数庞大,要频繁访问。

举个例子,这是简化过的超市商品列表和购买记录表的数据结构:
商品列表:编号、名称、厂商、类别、单价
销售记录:序号、时刻、商品编号、数量
销售记录中的商品编号是指向商品列表的外键。
现在我们要计算销售金额,用SQL的写法就是这两个表按商品编号JOIN起来后针对商品列表中的单价与销售记录中的数量乘积做合计。

那么怎么从销售记录的商品编号找到相应编号的商品的单价呢?
比较笨的办法就是遍历查找了,这个复杂度是两表记录数的乘积;优化一下,可以在维表上建立索引,相当于维表的查找次数做了个log,这确实大幅度提高性能了;再优化,使用HASH索引,维表查找次数可以降为常数,性能可以再提高。不过HASH索引有运气因素,如果HASH函数搞得不好,重复冲突太多,性能提高就不明显。
无论如何,这已经是已知的最快办法了。现代数据库也是用HASH JOIN的方案,关系数据库本身并没有维表的概念,它并不区分维表和事实表,HASH JOIN的办法是两个表的关联键值都做HASH计算,HASH值相同的记录再做遍历比较。一次运算时和在维表上做HASH索引的计算复杂度是一样的,多次运算时,如果事先知道谁是维表,那么维表上的HASH索引是可以复用的,先建索引的方案能减少一部分HASH计算时间。

但是,如果内存够大,能把数据都装下的时候,我们就有再提高性能的可能了。
熟悉Java和C语言的程序员都知道指针的概念,指针就是一种高速随机访问的机制。如果我们数据加载后将事实表的外键字段转换成指向维表记录的指针,引用维表记录时则可以完全没有任何HASH计算和比较动作了,直接就能用指针访问,查找时间几乎为0。转换成指针的过程当然仍需要做这些HASH计算和比较,但这是一次性的,一旦建立好指针,后续的计算都可以高速进行了。
集算器提供了指针化建立和访问的机制,简单起见以文件数据源为例,代码是这样:

  A  
1 =file(“Products.txt”).import() 读入商品列表
2 =file(“Sales.txt”).import() 读入销售记录
3 >A2.switch(productid,A1:id) 建立指针式连接,把商品编号转换成指针
4 =A2.sum(quantity*productid.price) 计算销售金额,用指针方式引用商品单价

实际场景中可能还有多任务共享这些加载数据的需求,代码会略有不同。

实际测试也支持了这个结论。我们做了两个分组汇总的测试,一个没有连接运算,另一个有五表多层外键连接,数据规模相当,且都小于机器物理内存。在同样硬件上用集算器和Oracle各执行几遍,结果是这样的:

  集算器 Oracle
单表无连接 0.57s 0.623s
五表外键连接 2 .3s 5.1s

Oracle没有纯内存的方案,多次运行后,Oracle会将数据缓存到内存中,但仍然可能会有些额外处理,所以横向绝对值比较意义不大,但数值的差异倍数有意义,在无外键连接时,集算器与Oracle性能相差不大,但有了连接运算后,集算器比Oracle快了一倍多。

指针是Java和C语言的基本概念,并不是很难想到的手段。不幸的是,SQL没有这种概念和相应的数据类型,因为SQL发明在机器内存很小的时代,对内存计算考虑很少。现代有些内存数据库仍然延用SQL体系,仅仅是简单地把数据读入从内存而不做指针化处理,也无法利用这个优势。

维表内存化
指针化要求全量数据都装入内存,要做指针转换的是事实表上的字段,而事实表数据常常在不断增长,时间长了就很可能无法全部装入内存了;而维表相对要稳定得多,总量一般就小一些,增长也不快,能全部装入内存的可能性要大得多。
而且,对事实表的计算操作一般都是按顺序遍历,这类运算没有随机、小量的特点,放在外存仅仅是读取性能本身比内存低一些,但不会引起由于随机、小量访问导致的近乎灾难性的后果。相反,维表访问由是频繁、随机、小量的,需要利用内存的优势。

在内存相对于数据量有限的情况下,我们可以考虑只把维表加载进内存,事实表仍然放在外存遍历。前面的运算在这种场景下将写成这样:

  A  
1 =file(“Products.txt”).import().primary@i(id) 读入商品列表并建立索引
2 =file(“Sales.txt”).cursor() 建立销售记录游标,准备遍历
3 =A2.switch(productid,A1:id) 在游标上建立连接指针,准备遍历
4 =A3.groups(;sum(quantity*productid.price)) 遍历计算销售金额,仍可用指针引用

这时候就不能事先建好的指针式连接,需要在遍历过程中临时建立。集算器也使用了高效的HASH索引,但显然仍然会比全内存方案的性能要差。

将维表和事实表区别对待,根据计算需求的特点,只将维表读入内存,能更有效地利用内存特点;同一个维表还常常被多个不同计算任务使用,读入内存中建立好的索引还可以复用。这种人为干预内存化的手段可以减少外存的访问量及访问性质,获得更优性能。
但是,如前所述,SQL在理论上没有区分维表和事实表,所有表是逻辑等同的。内存不足时做JOIN运算,数据一般会加载较小的表进内存,这在单次运算时和集算器效果差别并不大;但在多次运算时,维表就可能被反复加载并计算HASH值,内存的缓存能否被复用,基本上就是凭运气拼人品了。

外键序号化
如果我们把事实表中用于关联维表的外键字段值都改成维表中对应记录的次序号,而不是现在用的某种编码,就可以把上述外存事实表和内存维表的连接运算性能提高到和内存指针化差不多的地步。
针对上面的例子来讲,就是要把销售记录中的商品编号都改成整数,这个数就是该商品编号对应的商品在商品列表中的次序号。
显然,这个工作本身较为繁琐也很耗时,但它是一次性的。一旦准备完成,后续连接计算可以直接使用序号定位,不需要计算和比较HASH值。

  A  
1 =file(“Products.txt”).import() 读入商品列表
2 =file(“Sales.txt”).cursor() 根据已序号化的销售记录建立游标
3 =A2.switch(productid,A1:#) 用序号定位建立连接指针,准备遍历
4 =A3.groups(;sum(quantity*productid.price)) 计算结果

代码相差不大,但性能会提高很多。
SQL在理论上延用了数学上的无序集合概念,表中记录没有次序,即使人为地使用序号来表示外键了,数据库仍然会使用HASH JOIN算法,仍要计算和比较HASH值,事先费事准备数据也不能起到提高性能的作用。

需要注意的是,外键序号化以后,对维表的修改要比较小心。追加记录没有问题,但删除时一般只能做个记号而留下一个空洞,不能由后续记录补上,否则事实表记录的外键指向就会发生混乱。当删除数量较多时,产生的空洞太多也会浪费内存,这时可能就需要重新整理维表记录序号,同时要把引用到维表的事实表也做重整。
所以,外键序号化适合维表改变很少的场景,特别适合不再改变的历史数据,对于大数据计算还是比较常见的。而对于还在改变的当期数据搞外键序号化则会有较大的风险或面临较复杂的管理,这时一般就不建议实施了。

内存利用率
有用Java处理过较大数据经验的程序员都知道,Java数据对象占的内存很大。同样的数据,如果以文本存放形式占用的字节数为标准,读入内存后变成Java对象后占用的字节数会大上3到5倍,具体倍数和数据类型相关,整数实数稍好,字串差很多。
这导致的Java程序的内存利用率很低,100G内存的机器只能加载20G多点的数据,过于浪费了。而且,Java程序的性能对可用内存量非常敏感,内存不足时会引起频繁的垃圾收集动作,具体地就是内存搬家和硬盘之间的缓存倒换,性能常常会有数十倍的下降。

集算器提供了一种用时间换空间的手段。将数据以字节数组的方式紧致地存储,占用的内存空间就和外存相差不大,在引用到数据之前再临时将其对象化,计算完毕之后释放对象。这样能大幅提高内存利用率,代价是引用数据时需要增加对象化时间,但换来了可以充分利用内存允许频繁、随机、小量访问的特点。

集算器做了透明封装,使用字节表的代码和全内存对象时差别不大:

  A  
1 =file(“Products.dat”).create().primary@i(id) 根据文件创建字节表并建索引
2 =file(“Sales.dat”).cursor@b() 建立销售记录游标,准备遍历
3 =A2.switch(productid,A1) 和普通内存表一样使用
4 =A3.groups(;sum(quantity*productid.price)) 计算方案也一样

对字节方式的维表访问也可以使用HASH索引表,还可以实施外键序号化的技术。
实测表明,和全内存对象相比,大约会损失30%的性能,但内存不足时要和外存计算相比,优势就相当巨大了。

多线程并行
现代计算机的CPU多、核也多,而内存还有适合并发访问的特点,很适合实施多线程并行计算,充分发些这些CPU核的效能。
集算器提供了非常简便的多线程语法,配合内存游标,写并行计算很轻松:

  A B  
1 =file(“Sales.dat”).create() 源数据读入成字节表
2 fork 4 =A1.cursor(A2:4) 分作4段并行,分别建立内存游标
3   =B2.groups(;sum(amount):a) 遍历游标计算amount之和
4 =A2.conj().sum(a) 汇总每个线程的结果

这里fork语句用来启动多线程执行后续的代码块并收集每个线程的返回结果。这里也可以看出网络式编程的直观性,要并行执行的代码范围一目了然。

与Java和C++等更基础的程序设计语言不同,集算器没有提供多线程之间共享资源抢占与同步的机制。集算器认为各线程在执行过程中无关,只是同时启动并最后收集结果。显然这种机制不可能写出任意的并行算法,特别是实时逻辑,但对于数据计算类已基本够用。集算器牺牲了一些不太必要的能力换来更好的易用性。
并行数并非越多越好,原则上不能超过CPU的核数,否则再多的线程都只能是逻辑上的,不会真正并行执行。

集算器还提供了某些函数的内置并行选项,可以更简单地实施并行计算。

  A  
1 =file(“Sales.txt”).import() 取出数据
2 =A1.select@m(amount>1000) 并行过滤
3 =A2.sort@m(amount:-1) 并行排序

@m选项将自动根据系统配置决定并行的线程数量。不过,内置并行无法保证记录的取用次序,在涉及有序计算时就不能用了。
简单短小的并行代码,在获得高性能的同时,让程序员把注意力更多地放在计算的整体逻辑上,而不必纠缠于为了提高性能而采用的并行细节。

外存计算

数据量大过内存的情况还是更普遍的大数据计算场景,这时只能将数据存放在外存中。本质上外存是不能直接运算的,所谓外存运算是指将外存的大数据分批读入内存后处理,其中有大的中间结果还需要缓存到外存中。
和内存相比,外存(在物理上也就是硬盘了)不仅速度更慢,关键还在于缺乏频繁、小量、随机访问的能力;固态硬盘有了更强的随机访问能力,但仍不能做到频繁小量访问。对硬盘上计算的优化原则主要有这么三点:一是减少对硬盘的访问,因为它慢,要用CPU换硬盘时间;二是尽量顺序读取,特别是对于机械硬盘,同时还要权衡并行访问量;三是每次读入较多数据,避免频繁小量访问。

游标复用
有时我们需要针对同一批数据获得不同的统计值,如果是内存数据则无所谓,反复遍历也不会影响性能,但外存数据最好是一次遍历获得尽量多的结果,比如分组汇总时可以在一次遍历把每组的计数与合计都计算出来,SQL也是这么设计的,一个GROUP BY语句中可以SELECT多个汇总值。
情况再复杂一些就不是这样了,举个简单例子:计算一个大数据集的中位数。我们要将数据集排序,然后再数出位置在中间的成员,而这要事先知道总共有多少成员。但是,SQL的语法设计不能让我们在排序的同时把成员个数也数出来,需要事先取得计数,也就是要多多扫描一遍数据集,对于外存大数据集,这常常比运算本身的时间还要多了。
集算器提供了在游标上绑定延迟汇总计算的语法,可以在遍历游标时顺便计算其它统计值。这样就可以在为排序遍历时同时把个数计出来。

  A  
1 =file(“data.txt”).cursor()  
2 >A1.groups@x(;count(1);n) 绑定后计算的汇总,在遍历时再计算
3 =A1.sortx(key) 排序,遍历过程中处理A2的绑定计算
4 =A1.v(n).#1 取出绑定计算的结果,即总记录数
5 =A3.skip((A4-1)\2).fetch@x(2-A4%2).avg(key) 取出中位数记录并计算中位数

这段代码只在A3中将原始数据遍历了一次,A5中遍历的排序后的数据。

类似地,针对一个大数据集按不同分组口径统计的情况也很常见,SQL需要写成多句GROUP BY对数据遍历多次。而集算器则可以在游标上绑定多组计算,一次遍历完成。

分段并行
在计算总量不可减少的情况下,采用多线程并行可以让多CPU核分担计算量,对性能提高非常明显。
我们先看文本数据源的情况。文本是很常见的外存数据源,将文本读入内存时需要解析成相应的数据类型对象后才能运算,这个过程很慢,特别是碰到日期时间类型的数据,可以想像一下分析那个日期串会有多麻烦,经常会发生CPU时间会超过硬盘访问时间的现象。这时候如果能采用多线程就能有效地提高这个性能。

要并行处理需要将源文件分段,每个线程处理其中一段。文本文件一般是每一行对应一条记录,每一行长度不一定相同。按行数分段显然没有意义,这需要每次都从头遍历,完全起不到提高性能的目标。按字节分段不需要遍历,但有可能分段点正好落在行的中间,造成一行被拆进两段,数据就错误了。
借鉴Hadoop的搞法,集算器使用了自动去头补尾的字节分段机制,即分段开始点所在的行被舍弃,分段结束点所在的行会被补齐,这样将确保每一段都由完整的行构成,不会有数据错误。
结合前面说过的集算器并行代码,可以很方便地写出并行计算程序。

  A B  
1 =file(“data.txt”) 源文件
2 fork 4 =A1.cursor@t(amount;A2:4) 分作4段并行,分别建立游标
3   =B2.groups(;sum(amount):a) 遍历游标计算amount之和
4 =A2.conj().sum(a) 汇总每个线程的结果

上述代码把data.txt分作4段,产生4个线程分别用游标遍历每一分段并计算其中amount列的和,最后再汇总每段的返回值得到整个文件的amount列总和。

文本解析的时间经常比计算要长得多,有时候只要解析能够并行,计算本身是否并行并不重要。集算器对于读取数据提供了简单的内置并行选项,如果对数据读取次序不关心,比如求和运算就不在乎次序,可以更简单地写出代码。

  A  
1 =file(“data.txt”).cursor@tm(amount) 定义并行取数的游标
2 =A1.groups(;sum(amount))._1 遍历游标并汇总amount列

上面代码中,游标取数时会自动启动多线程并行,但计算amount合计时是串行的。

内存计算的并行数量基本只受CPU数量的限制,而外存运算还将受到硬盘的限制。单片硬盘在逻辑上就不能并发访问,多线程同时访问硬盘不同文件会造成磁头频繁移动,这消耗的时间比读取数据还要长,这时要为每个线程设置较大的数据缓冲区,但这又造成内存的占用。需要根据实际情况来权衡,集算器提供了相应的配置手段控制线程数量及缓冲区。

数据库表的分段就远没有文件自由了,不大适合进行分段计算,对于数据密集型的任务最好还是由数据库自行完成。有些计算密集型的任务,计算占用时间很多,而且复杂的计算在数据库内实现难度实在太大,需要读出到外部实现,这时候也可以采用分段并行机制。
一种办法是直接建立多个分表,每个线程分别处理若干个分表的数据,同一个分表不能再拆分给多个线程处理,这种方案下要拆分出较多分表才能让各线程负担相对均匀,而在数据库建立的表太多并不是个好设计,所以一般会让线程数和分表数基本相同,这会导致并行数被事先确定,较为死板。
还可以使用WHERE条件来分段,这样并行数可以很灵活,但最好事先建立索引并按这个索引去WHERE,否则每次WHERE都会导致全表遍历,浪费数据读取的时间。

我们测试发现,Oracle等数据库的JDBC很慢,读出计算时JDBC会成为一个瓶颈。如果数据库本身负担不重,这时也可以采用分段并行的方法取数,从而缓解JDBC的性能损失。

  A B  
1 fork 4 =connect(db) 分4线程,要分别建立连接
2   =B1.query@x(“select * from T where part=?”,A2) 分别取每一段
3 =A1.conj() 合并结果

实测表明,并行取数在数据库负担不重时能达到数倍的性能提升。

数据存储
除了文本文件外,集算器还提供了自有格式的二进制文件。
集算器的二进制文件中已经记录了数据类型,在读出时不需要再解析,这样会比文本好快得多。而且,集算器为二进制文件做了压缩,同样数据占用的硬盘空间一般能比文本要小三分之一到一半,读取性能也会更好。不过,压缩比并非越高越好,解压缩会占用CPU时间,压缩比越高的算法占用CPU时间越长,集算器的压缩算法非常简单,几乎不占用CPU时间,当然压缩比不是非常高。
整体算下来,二进制文件比文本能快出3到5倍的样子,比用JDBC从数据库中取数也快,特别是针对ORACLE这种JDBC很慢的情况更有巨大优势。所以,如果数据要反复使用时,以二进制格式存放会有更大的性能优势。
从文本或数据库到二进制文件的转换程序也非常简单:

  A  
1 =file(“data.txt”).cursor@t() 定义文本文件游标
2 =file(“data.bin”).export@z(A1) 写成可分段的二进制文件

集算器的二进制文件也支持分段并行,代码与文本文件几乎相同:

  A B  
1 =file(“data.bin”) 源文件
2 fork 4 =A1.cursor@b(amount;A2:4) @b表示二进制文件,其它参数相同
3   =B2.groups(;sum(amount):a) 后续计算语法完全相同
4 =A2.conj().sum(a)  

基于二进制文件,集算器还可以提供列式存储方案,即将每一列存储成一个文件。有些运算只涉及较少的列,这样只需要读取较少的数据就可以完成运算,硬盘访问时间将大大缩短,这也是列存的优势所在。
将文本转换成列存文件:

  A  
1 =file(“data.txt”).cursor@t() 原文本文件
2 =10.(file(“col”/~/”.bin”)) 产生10个列的对应存储文件
3 >A2.export@z(A1) 将原数据写成可分段的多个列存文件

使用列存计算:

  A  
1 =[1,3].(file(“col”/~/”.bin”)) 使用第1,3列
2 =A1.cursor() 定义列存游标
3 =A2.groups(;sum(col1+col3):all)._1 使用游标计算合计

集算器的列存文件还支持分段并行,和行存文件的相关代码写法一样。

  A B  
1 =[1,3].(file(“col”/~/”.bin”)) 定义列存文件组
2 fork 4 =A1.cursor(amount;A2:4) 并行和游标代码与行存相同
3   =B2.groups(;sum(amount):a) 后续计算语法完全相同
4 =A2.conj().sum(a)  

列存分段是个比较麻烦的问题,需要在分段时保证多个列同步,否则会发生记录值的错位。采用了压缩存储后,不同记录字段值存储长度不同,无法直接按序号定位。一般的办法是先把数据先按行分块,每块之内列存。分段以块为单位进行,不能把块再拆开了。这会产生一个矛盾,块太大则可分段的数量不够灵活;块太小则每个分段要涉及多个块,又会造成数据的不连续而弱化列存的优势。
集算器重新设计了列存分段机制,用很少的存储空间记录索引,在确保多列数据同步的前提下,可以支持很灵活的分段数量,而且每列的数据仍然是连续存放的,不再分成多块。不过其中的算法略有些复杂,有兴趣的同学可以再仔细交流。

需要指出的是,列存并不是总有效,如果读取的列较多时,对于机械硬盘又会产生寻道时间与缓冲区容量之间的严重矛盾。多线程并行计算时还会进一步恶化这个问题,列存方案不大适合普通机械硬盘,应当在有固态硬盘或可高并发磁盘阵列的场景下使用。

有序利用
数据库里经常许多逻辑上很宽的表,物理上被设计成多个主键相同的表,我们称为同维表;另外还有主子表的情况,比如订单和订单明细,也是用某一个主键关联起来。引用这些表时一般都会涉及到JOIN运算。
但是,这里的JOIN和前面所说的针对维表的外键式JOIN不同,对于维表的JOIN有随机性的特点,不一定会取到哪一条记录。而这种同维表和主子表则总是同步关联的,不会乱跳着取数,如果这些表都按关联主键排好序的话,可以使用归并算法一次遍历实现JOIN,复杂度要比外存分段HASH JOIN低得多得多。
集算器针对有序的游标提供了归并算法,可以更高效地执行JOIN以及集合的交并差等运算。

  A  
1 =file(“Order.txt”).cursor@t() 订单游标,按订单id排序
2 =file(“Detail.txt”).cursor@t() 订单明细游标,也按订单id排序
3 =join@x(A1:O,id;A2:D,id) 有序归并连接,仍返回游标
4 =A3.groups(O.area;sum(D.amount)) 按地区分组汇总金额,地区字段在主表中,金额字段在明细子表中

把JOIN分成外键式和对齐式两种,外键式JOIN因为维表相对较小可以采用内存方案,对齐式JOIN由于不需要随机访问可以事先排序。虽然排序也需要花费时间,但它也是一次性的,在后续反复使用这些数据运算时可以获得更高的性能。
关系代数没有有序集合的概念,无法利用这个特征。不过,许多数据库会自动为主键建索引,相当于做了排序,在运算时也会有一定程度的优化效果,但多少还是有点凭运气了。

事实上,准备数据本身的过程中也可以使用有序归并,已有数据是有序的,只要把新加入的数据排序后和已有数据一起做个归并就可以,而不必把所有历史数据重新排序。
而且也不必每次都和历史数据合并,只将一段时间内的新数据排序另存,在使用时再和有序的历史数据一起归并。归并算法的成本很低,只要归并段数不是非常多,使用时归并对总体性能并没有太大的影响。
除了事先准备的数据,我们有时也会明确知道某些数据已经有序,比如集算器返回的分组汇总结果缺省是按键值有序的,大分组结果本来也是针对有序小结果集归并出来的,这个结果仍然有序,可以继续使用归并算法。

前面提过到有序游标技术,采用集算器的二进制文件时,按组从游标取数也可以分段并行。在生成数据文件时添加分组标识,集算器会在将来分段时不把同一组内的数据拆分到两个分段中,从而确保每个线程都能处理若干完整的组。

  A  
1 =file(“userlog.txt”).cursor@t() 原始数据游标
2 =A1.sortx(id) 按id排序并返回游标
3 >file(“userlog.dat”).export@z(A2;id) 写成按id分段的二进制文件

利用有序的按组取数分段并行代码:

  A B C  
1 =file(“userlog.dat”) 对id有序的数据文件
2 fork 4 =A1.cursor@b(;A2:4) 分段时保证同一组id不会被拆开
3   for B2;id 后续计算语法相同
4      

源数据采用二进制文件存储时,有序归并也可以支持分段并行。在生成数据时按某个基准文件对齐,将来在分段时可以保证多个文件同步,不会发生记录错位。

  A  
1 =file(“Order.txt”).cursor@t()  
2 =A1.sortx(id) 按id排序
3 >file(“Order.dat”).export@z(A2;id) 写成按id分段的二进制文件
4 =file(“Detail.txt”).cursor@t()  
5 =A4.sortx(id) 按id排序
6 >file(“Detail.dat”).export@z(A2;id,file(“Order.dat”),id ) 和Order.dat同步按id分段

并行计算归并游标

  A B  
1 =file(“Order.dat”) 对id有序的数据文件
2 =file(“Detail.dat”) 同步分段的数据文件
3 fork 4 =A1.cursor@b(;A3:4) 分段时保证同一组id不会被拆开
4   =A2.cursor@b(;A3:4) 同步分段
5   =join@x(B3:O,id;B4:D,id) 归并
6   =B5.groups(O.area;sum(D.amount)) 汇总
7 =A3.conj().groups(#1;sum(#2)) 合并后再汇总

集群计算

数据量再大下去,单台机器无论如何也无法承受了,这时候就要使用集群技术了。当然,集群中每个节点都是独立的计算机,可以应用前面的内存和外存计算技术
集算器可以以独立的服务器进程形式运行,接受其它集算器程序的计算请求并返回结果。基本的任务模式很简单,就是由某个主控节点向其它节点发出计算指令,收到各节点的计算结果后再由主控节点汇总。一个复杂的任务可以由多个基本任务组合构成。
集群计算方案要求能够较方便地横向扩展,数据量再大时可以通过增加节点来解决。当然任何方案都会有节点数的上限,横向扩展也是在一定范围内。另外,与单机不同,设计集群方案时一定要考虑容错,即有个别节点失效时还能确保整个集群能工作,甚至计算任务也能继续执行完毕。

计算分布
先看较简单的共享数据源方案。
共享数据源是指各节点要处理的数据在同一个数据存储中,如同一个数据库或网络文件系统,节点本身不存储数据,只把计算分散到节点进行。显然,这会造成数据源有较大的并发访问压力,适合计算密集型而不是数据密集型的任务。

集算器实现共享数据源计算非常简单:

  A B  
1 =4.(“192.168.0.”/(10+~)/”:1234”) 节点机列表,4个
2 fork to(8);A1 到节点机上执行,分成8个任务
3   =hdfsfile(“hdfs:\\192.168.0.1\persons.txt”) HDFS上的文件
4   =B3.cursor@t(;A2:8) 分段游标
5   =B4.select(gender==’M’).groups(;count(1):C) 过滤并计数
7 =A2.conj().sum(C) 汇总结果

为简单起见,这里用了HDFS,用数据库是差不多的,集算器对这些数据源都能支持。
从主程序中可以看出,计算用到的节点是写在代码中的,也就是由程序员在计算任务中自行决定的,不同的计算任务可以使用不同的节点列表,当然也可以从某些配置文件中读出这些节点,但无论如何,集算器本身没有一个控制中心管理这些节点。
也就是说,集算器是个无中心的分布式结构,不像Hadoop那样有完善的框架体系,能把整个集群模拟成一个巨大的单机。集算器没有框架,也没有中心主控节点,需要程序员用代码控制参与计算的节点。

无中心结构中的好处是不会发生单点失效,任何某个节点故障时整个集群仍可以工作,但程序员会麻烦些,增加减少节点时都需要程序代码知道;相反,有中心结构的中心机如果发生故障会导致整个集群瘫痪,但是管理上要简单些,节点变化只要在中心上配置,代码可以透明地继承。
严格地说,集算器集群也不是完全无中心。集群本身没有中心,但每个计算任务仍有主控节点,在计算时由临时寻找其它节点参与计算。如果某个任务过程中主控节点失效,则这个任务将失败,但整个集群仍可以接受其它任务。

从上面代码还可以看出,总的子任务数是8,比可用节点数4要更多,这是集算器提供的负载均衡及容错能力。
集算器不是平均地向各个节点分配任务,而是采用动态均衡的方案。当主程序向节点下达子任务时,会计算每个节点大致的空闲程度(即节点当前正在运行的线程数量和该节点可执行的总线程数量对比),将任务分给最闲的节点。如果所有节点的任务数量已经达到饱和(节点的最大线程数),主程序就会暂停分配,等待到某个节点的子任务完成后有了空闲才继续分配,这样,速度快的节点可能会分配到更多的子任务,均衡各节点的负担。
如果过程中发现某个节点失效导致子任务失败,主程序还会再次将这个子任务分配给其它有效节点,整体运算时间会加长,但能实现一定程度的容错。
这种无结构方案允许性能不一致的机器构成集群,内存、CPU的配置乃至操作系统不同都可以,简单地说就是不挑机器,这样可以更大程度地保护用户的硬件投资。

数据分布
上面先通过简单的数据共享方案了解了集算器的集群机制。事实上,结构化大数据计算大多数还是数据密集型的,数据的IO成本非常高,共享数据方案会造成严重的吞吐瓶颈,导致的时间延迟经常远远超过计算本身。这时候,我们就要采用数据分布的方式,把数据IO成本也分摊给各个节点。
所谓数据分布,是把整体数据拆分后存储到各个节点上,目的在于使节点计算时用到的数据尽量都能在本地找到,这样避免网络传输以及共享冲突。但是,数据分布并不能简单地将所有数据(平均地)分成n段,分别部署到n个节点上,这种分布毫无容错能力,而且很可能由于关联运算而仍有较多的网络传输量。
与常见的网络文件系统不同,集算器的数据分布方案是不透明的,也就是说要由程序员控制数据如何分布,这样的好处是能更灵活地根据算法和数据特征决定分布方案。
数据的物理存储方式一般是文件,也可以是数据库,但实际上很少会在数量较多的集群节点上安装数据库,下面的代码都用文件存储来举例。

集算器把数据分成n个区,每个节点存放其中若干个不同的区。这样每个区都可能会多个节点上冗余,各分区的冗余数量以及所在节点均可以自由指定,没有提供在系统层面设置的统一冗余系数以及自动化的冗余方案。
冗余数据分布的首要目的是容错。某个节点失效时,在剩下的节点中还能找到完整的数据,这样虽然计算时间会变长,但仍然可以完成。
自由冗余方案还可以减少网络传输。比如,维表是几乎所有计算都要用到的,我们可以把维表放在同一分区,且让此分区在所有节点上冗余,只把大的事实表分段分别存放到多个节点上。维表一般较小,也不会增加太多容量负担,但引用维表时不需要跨机访问,可以有效地提高性能。
在各节点能力相当时,我们一般推荐简单的循环分区存放方案。

数据分成5个区并分到5个节点上,每个节点循环地放3个区,显然,这种分法下,任意有2个节点失效时仍能够获得完整的数据。所有任务都要用到的维表被分到X区在每个节点上冗余,减少网络传输量。

当然,灵活的冗余方案并不要求一定是这样分配,当机器能力不同时,可以在高性能节点多存放一些分区从而分摊到更多的计算任务,使整个集群的性能表现更为均匀。
集算器提供了节点间的同区数据同步的功能,有数据更新只要更新其中某些节点,然后可以用同步功能将数据同步到其它节点上。简单的办法是设计一个大容量数据节点存放所有分区用于更新,其它工作节点都从这个数据节点同步最新数据。

使用数据时,集算器提供了半透明的跨节点读取数据方案,读取文件时指定分区及节点列表,集算器将优先从本节点获取该区数据,如果找不到则会在列表中寻找共享程度最低的节点去读。
分配计算任务时,集算器仍然采用动态均衡方案,接收到任务的子节点先检查本节点是否本次任务需要的数据分区,有则计算并返回结果,没有则返回一个失败信息,主程序就会再寻找其它节点分配该任务,这样就可以确保子任务及其涉及数据在同一节点上。如果总也找不到一个节点能匹配相应的任务,说明失效节点过多,已经不能组合出全量数据了,就只能宣告整个任务失败了。

  A B C  
1 =4.(“192.168.0.”/(10+~)/”:1234”) 节点机列表,4个
2 fork to(8);A1   到节点机执行
3   =file(“person.txt”,A2) A2为数据区号
4   if !B3.exists() end “data not find” 找不到返回错误再分配
5   =B3.cursor()    
6   =B5. select(gender==’M’).groups(;count(1):C) 计算
7 =A2.conj().sum(C) 汇总

检测本节点是否存有相应数据分区的工作是由程序员用代码写出来的,因此是非常灵活的,比如可以要求高密集访问分区必须在本节点,而低密集访问分区则跨机获取。
用于实现动态分配的网络传输量非常小,即使多做几次反复,消耗的时间也只是毫秒级的,对于计算本身的时间相比可以忽略不计。

从上面的任务分配和数据分布的机制中还可以看出,集算器集群的设计目标是几到十几最多几十的中小规模集群,而不是成百上千甚至上万的大集群。人为控制每个节点的使用及其数据分布能获得更好的灵活性和性能,但会造成管理工作量上升,这对于中小规模集群还是可以接受的。但对于大规模集群,非自动化方案带来的管理工作量是无法容忍的,只能牺牲灵活性换取管理高效性,这进一步理解集算器与Hadoop集群的不同。

内存分布
集算器的数据分区是个逻辑概念,不一定是指文件系统中的数据,也可以是内存数据。这样,可以联合使用多台机器的内存执行集群式的高性能内存计算,针对较大的数据量也可以获得即时响应的速度。
同样地,内存集群方案时也要考虑容错问题。这和外存容错有很大的不同。

如前所述,外存数据容错采用的是冗余式的文件数据分区,整批数据被重复存放了许多份。如果容错指数是k,即允许最多k-1台机器失效时还可以找到全量数据,数据就需要被复制k份,这时候的存储空间的利用率相当于只有1/k。
这对于外存是无所谓的,因为硬盘非常便宜,经常可以被认为是无穷大的,重复倍数稍多点关系不大。但是内存就不行了,1/k的使用率对于昂贵的内存来说完全不能容忍。

对于内存,集算器采用了备胎式的容错方案。数据仍然分为n个区,分别存放在n个节点上,每个节点只保存一个分区。为了实现容错指数k,在旁边再摆上k台空闲的备用机,当这在用节点中有节点发生失效时,则从找出一台备用机来临时加载失效节点的数据然后再重新组成n个可用节点继续计算,原失效的节点机排除故障恢复后再用作备用机。整个过程就和汽车的备胎模式一样,所以叫了这个名字。
如果失效节点过多,把k个备用机都用完也不能再组合出n个可用节点,这时就只能报错宣告集群失效了。汽车开不了了。
这种方案的内存利用率可以达到n/(n+k),远远高于冗余式容错方案的1/k。由于内存数据量相对较小,有节点失效后临时加载的时间可以容忍,一般几分钟也就够了。对于外存,如果也采用这种备胎式方案,节点失效时要临时准备的数据量就可能会太大,会导致集群的不可用时间过长。
当然,共用的维表也仍然可以每个节点都加载,实利利用率会略小于n/(n+k)。

使用内存分布时会多一个临时加载的过程,代码比外存数据分布时稍显复杂。

  A 主程序
1 =8.(“192.168.0.”/(10+~)/”:1234”) 节点列表,共8个
2 =hosts(A1,to(4),”init.dfx”) 在其中寻找4个节点加载内存数据
3 =callx@a(“sub.dfx”,to(4);A2) 调用这些节点上程序计算
4 =A3.sum() 汇总结果
  A 节点初始化程序init.dfx
1 =file(“Product.txt”,z).import() 读入第z分区的数据
2 >env(T,A1) 将数据记入环境
3 >zone(z) 登记本节点的分区
  A 节点程序sub.dfx
1 =env(T) 从环境中取出数据
2 =A1.count(gender==’M’) 过滤并计数
3 return A2 返回结果

与外存分区的任务分配的动态机制相比,内存数据分区的任务分配采用的是静态机制,即在寻找完可用节点列表后主程序就知道每个子任务应当分配给哪个节点去执行。
理论上这两种分配机制和内外存并没有必然关系,外存也可以用静态分配,内存也可以用动态分配。但是,由于外存计算的稳定性较差,每次任务计算的时间不可控,使用静态分配就可能造成资源的浪费;而内存计算的稳定性很强,任务计算时间基本可控,就可以采取使用静态分配。相反地,按上面说的,我们一般不会在节点上保存冗余的内存分区,这样动态分配的结果就会和静态分配的结果是一样的,没有必要采用动态分配;而外存分区在节点上常常有较多的冗余,采取动态分配就能更充分地发挥硬件资源。

集群维表
前面说过,在集群计算时,我们一般会把维表冗余到每一个节点上。由于维表经常要被随机访问,不适合外存技术,加之维表相对较小,因而常常会被全部读入内存。
但有时维表也会很大,即使采用字节表技术仍然无法全部读入单个节点的内存,这时,基于内存数据分区的机制,集算器提供了集群维表,即将维表也分段读入各个节点的内存中,引用时再从节点中获取数据。

  A 主程序
1 =8.(“192.168.0.”/(10+~)/”:1234”) 节点机列表,共8个
2 =hosts(A1,to(4),”init.dfx”) 选择4个节点加载内存维表
3 =callx(“sub.dfx”,8*A2,to(8);A1) 调用节点程序计算,传入内存维表节点
4 =A3.sum() 汇总结果
  A 节点初始化程序init.dfx
1 =file(“Product.txt”,z).import() 读入第z分区的维表
2 >env(T,A1) 将数据记入环境
3 >zone(z) 登记本节点的分区
  A B 节点程序sub.dfx
1 =file(“Sales.txt”,z)   z区事实数据
2 if !A1.exists() end “data not find” 找不到返回错误
3 =createx(T,h) 基于节点组h上变量T建立集群维表
4 =A1.cursor()  
5 =A4.join(productid,A3,price) 与集群维表A3做连接计算
6 =A5.sum(quantity*price) 合计
7 return A6 返回结果

从上面代码可以看出,用于存储集群维表的节点和用于计算的节点可以是不同的。可以设定若干节点用作集群维表,其它节点用于计算。多个集群维表也可以分别用不同的节点存储。这一切都由程序员根据实际情况指定。
和硬盘类似,网络也不适合进行频繁小量访问,每次网络传输都需要做很多准备和收尾工作,而且网络协议还会自动加一些头尾数据。这样就不能把集群维表模拟成普通表一样可以随机访问单条记录,否则就会导致频繁小量访问而严重影响性能。所以,这里的代码不能用指针式的方案引用维表字段,而要针对游标数据批量引用集群维表,代码和前面内存计算时有所不同。

JOIN总结
结构化大数据计算中,JOIN可以说是最困难的任务之一了。SQL对此也一直很头疼,数据量超过内存时,一般是采用HASH分段JOIN的方案。大体原理是针对JOIN两表的键值计算HASH值,按HASH分成若干段,每段都可以内存放下了,然后再分别针对每段做内存JOIN;如果有一段还是太大,还需要做二次HASH分段。集群运算时也是类似,将数据根据HASH值分段后把分别送到各个节点机上做小数据量的JOIN。整个过程非常复杂繁琐,且有多次数据遍历和大量网络传输。
SQL对于JOIN的定义就是简单的笛卡尔积再过滤,定义简单的好处在于描述面非常广泛,很多关联运算可以看成是SQL的JOIN,针对这种JOIN研究的成果适应面非常广。但太简单的定义在实施运算时能够利用的特征太少,运算优化就不好做了。相反地,把定义复杂化,分各种情况讨论,虽然描述广泛度下降了,但可以根据情况的特征进行优化。
做个类比,所有的整数乘法其实都可以用加法表示,取消乘法而只用加法并不会导致某个运算做不出来,也就是说,只有加法的运算体系在某种意义下已经是完备的。但是,如果我们把多个相同数相加这种特殊的加法定义为乘法,研究它的特征后,就可能发明出九九表来实现更快捷的计算,而不必再用一个个硬加的手段了。
SQL的JOIN也是类似,在进一步细化分类后,可以针对各类任务的特征分别提出更优化的算法。

集算器中把JOIN分成外键式和对齐式两大类,外键式采用内存化以至集群维表的技术,对齐式则可以事先排序解决,过程简单许多,没有多次数据遍历,集群时网络传输量也小,整体性能可以大幅度提高。但是,由于SQL的理论体系对JOIN的理解过于简单,无法区分维表和事实表,另一方面SQL也没有有序集合和对象引用机制,这样导致SQL解决方案都有没办法很好地应用这些技术。
当然,就像不是所有加法都能表示为乘法一样,也不是所有的JOIN都可以纳入上述分类后采用这些技术,仍然存在一些不能事先排序且大到用集群维表也不能装入内存的情况,不过,现实场景中能用这些技术解决的情况也很多,可以说占到绝大多数。
对于这些技术不能解决的场景,为了计算的完备性,目前仍然需要采用HASH分段JOIN的算法,集算器提供了分组分批写出和远程文件读写的功能,也可以在集群下组合出这个算法。但确实过于复杂,这里就不详细说明了。我们今后会在集算器的基础上加上语义模式,形成大数据仓库产品,就可以提供更为透明化的语法体系,届时可以把这些算法进一步封装后提供。

报表型应用协助

引入计算引擎

“零编码开发报表”是许多报表工具厂商都喊过的口号,但现实并不是这么简单,虽然确实有不少简单报表可以拖拖拽拽完成,但仍然有相当数量的报表必须经过编码才能完成。
有报表开发经验程序员都知道,为报表编写复杂SQL是经常的事,存储过程以及事先准备的中间数据也是家常便饭,有时SQL和存储过程不好写的运算还需要采用自定义数据源即Java程序来处理。
虽然大部分报表相对简单,复杂报表总数上并不算多,但其占用的开发工作量却会是绝对的大头,开发10个用报表工具能拖拽完成的简单报表所用时间也做不了一个需要编码才能准备好数据的报表。

某些报表工具可以在呈现阶段直接实现多数据源关联计算和比上期同期比等层次格间引用计算,但即使这样,仍然大量碰到复杂数据准备的需求, 开发工作量很繁重。这时,引入计算中间层希望更便捷地实现数据准备就是个比较自然的想法。面对这类报表,我们不能再期望零编码,而是基于集算器简单编码。


这是引入了集算器后报表应用的体系结构图,从图中可以看到,比传统报表应用结构中多了一个计算层:数据源的数据先经过计算层的计算,再传给呈现层去展现。

降低报表开发难度

计算层之后对于报表开发带来的好处主要有三个方面:
首先是能降低报表开发难度,也就会提高开发效率,这是集算器的设计初衷;其次是能够优化报表的应用结构,使报表模块更为独立,减少不必要的冗余动作;然后还能够提高报表的运算性能,充分发挥硬件和系统的效能。
下面将分别详细讨论。

比Java和SQL更易写
当前复杂报表的数据准备工作一般是采用Java或SQL完成的,存储过程以及中间表也可以看作是SQL。集算器的语法比Java和SQL更为简单易懂,采用集算器能在很大程度上简化这些开发量。这在前面的讨论中已经多次说明。
集算器的代码比Java也要短小很多,这样不仅是写得更快,而且还能容易理解算法和排错,绝大多数报表的数据准备算法可以在一个屏幕内显示出来,可以更直观地理解代码的整体含义。而使用Java时,一个完整的业务逻辑常常需要几百行代码,翻看到后面时已经忘了前面的了。
前面已经在各方面将集算器与SQL的语法做了比较,除了那些模型上的优势外,集算器在日期和字串等运算,也比大部分SQL提供了更丰富的方法。
许多情况用SQL也不是写不出来,但不能直接按自然思维实现,很费脑筋,这种代码放时间长了程序员自己都会忘了是怎么写出来的,给将来的维护也造成麻烦。集算器代码则符合自然思维习惯,即使是与SQL相同的思路也能更清晰地表达,更容易理解和维护。
不过,需要说明的是,集算器虽然在大多数情况下的语法要比SQL更简单易写,但并不能完全取代SQL。数据从数据库读出的IO成本相当高,有些涉及数据量太大的简单运算,数据读出的耗时远远超过运算本身,这种情况还是放在数据库中运算更合适。

比报表中计算更广泛
报表工具都可以完成计算列、分组排序等运算,有些报表工具还提供了跨行组运算和相对格与集合的引用方案,可以完成相当复杂的运算。
但是,报表工具中的运算是一种状态式的计算,也就是把所有计算表达式写在报表布局上,由报表工具根据依赖关系决定计算次序。这种方法好处是很直观,在依赖关系不太复杂时能一目了然地了解各单元格的运算目标。
在依赖关系较为复杂,数据准备计算需要分成多步时,状态式计算就困难了,要实施过程式计算,经常需要借用隐藏格,隐藏格不仅将破坏状态式运算的直观性,由于状态式计算一般需要全内存处理依赖关系,还会占用更多不必要的内存。而且还有许多运算即使用隐藏格也难以完成。

比如要列出销售额占前一半的大客户,如果不借助数据准备环节,就要在报表中使用隐藏行列手段将不该列出来的条目隐藏,而不能直接过滤掉。再比如带明细的分组报表要按汇总值排序,需要先分组后排序,许多报表工具无法控制这个次序,报表就无法完成了。
还有个典型例子是舍位平衡,明细值四舍五入后再合计,可能会与合计值的四舍五入值不相等,会造成了报表上明细与合计数值不一致,这时需要根据合计的舍入值倒推明细的舍入值,这不是报表工具能搞定的事了。
这几个运算的逻辑都很简单,但在报表工具中却很难实现,单句的SQL也很难写,而为了这种简单且无复用价值的运算写一段Java程序或存储过程显得很无聊,况且也不是很轻松。但是,如果采用集算器就会容易得多,在数据准备阶段完成计算,报表只负责呈现及少量的直观计算,能有效地保持状态式计算的优势。过程多了一步,但结构更为清晰。

数据准备还能实现动态数据源和数据集。报表工具使用的数据源一般事先配置好了,不能根据参数动态选择,而使用集算器数据源时则可以用脚本控制连接不同的数据源。通用查询报表要求取数SQL不能简单地用参数控制条件,而要替换某个子句,支持宏的报表工具能够一定程度地解决这个问题,但面对要将宏计算后才能拼进SQL的复杂场景也会感觉困难,传统方案一般又要在外部编写Java程序事先将宏计算好再传入,增加开发工作量。而采用集算器则可以轻松使用脚本直接完成各种复杂宏计算了。

数据准备不仅能解决报表中的计算,还能协助处理格式。比如许多报表工具都支持纵向分栏,但很少有报表工具支持横向分栏。而用集算器可以将原数据集变换成横向拼接过的数据集,报表工作只要用普通的模板呈现列数更多的数据集即可。再比如许多报表工具不支持末页补足空行,也可以用集算器在返回数据集时补。

一致的多样性数据源支持
现代报表的数据源并不只是数据库,还可能是文本文件或json、XML等。这些非数据库数据源没有再计算能力,但生成报表时总还是需要再进行一些过滤分组甚至多表连接等运算,报表工具本身的计算能力不足,一般都不能很好地处理json和XML数据,即使针对能进行简单处理的结构化文本,由报表工具运算也也会造成容量负担过重的问题。因此,我们经常会有一个过程把这些非数据库数据导入到数据库再去生成报表,增加开发工作量。
如果采用集算器准备数据,则可以直接用这些非数据库数据作为数据源去生成报表,不需要导入数据库的过程,减少开发工作量。

数据库还包括NoSQL数据库、文件包括HDFS文件,对于集算器来讲都是数据源。集算器自有的计算能力可以使这些计算能力不一的多样性数据获得通用一致的计算能力。比如文件几乎没有计算能力,MongoDB对JOIN和GROUP运算支持不足,各家数据库对窗口函数的支持程度不同、日期与字串处理能力也普遍不足且风格迥异。采用集算器后可以用相对一致的方案来计算,而这将意味着更低的移植成本以及学习难度。

一般报表工具使用的数据集都是类似SQL返回的那种单层二维表,碰到像json或XML这类多层数据只能先转换成多个单层数据集,再在报表模板中关联运算拼接成多层报表。而集算器可以直接支持多层数据集计算,不需要做这个转换,减少工作量,报表也可以接受集算器返回的多层数据集直接按层次呈现,不需要在报表中再做关联。
类似地,MongoDB也支持多层数据,也可以用集算器直接计算并返回给报表。

优化报表应用结构

提高开发效率是集算器的设计初衷,但实际应用下来,优化报表业务的应用结构才是集算器能起到的最重要作用。可以说,集算器的出现是报表工具的二次革命。

解释执行降低应用耦合度
我们来比较使用Java和用集算器做报表数据准备时在应用结构上的差异。

我们知道,Java应用大多数情况是事先编译并静态加载的,也就是要把所有模块一起编译打包后部署,在运行过程中代码就不再改变了。其实Java也有动态编译和加载的技术,但难度和复杂度都高很多,一般应用程序员很少使用。而且即使采用了动态加载技术,也不能替换已经加载进内存的类,只能不断新增新的类。
这种机制下,用Java编写的报表数据准备算法就需要和主应用程序一起打包发布,这会导致报表模块与主应用之间的高耦合性。
一般来讲,报表的业务稳定性要比主应用差得多,报表变动的频率远远高于主应用,好的体系设计应当能把报表模板独立出来降低整个应用的耦合性。但是,一个完整的报表由报表工具开发的报表呈现模板和Java开发的数据准备算法构成,报表修改时需要同时改变这两部分,报表模块和主应用的耦合度就会很高。因为报表模板一般保存在文件系统中或有时在数据库中,而数据准备算法却要打入了主应用程序包,存放和管理机制都不一样,这样要保持两者一致就相当麻烦了,报表模块很难独立出来。
而且,如上所述,Java大多是静态加载的,报表数据准备算法有修改后会导致整个应用重新编译部署,很难做到热切换。

如果用集算器来实现数据准备算法,就能有效地降低主应用程序与报表功能的耦合度了。
集算器写出来的脚本也是类似报表模板的外置文件,不需要和主应用程序一起编译打包,而可以和报表模板一起放在文件系统中管理维护,报表模块可以独立出来。
集算器是解释执行的动态语言,在修改时不需要涉及主应用程序,只要把集算器脚本替换就可以,天然就支持热切换。
另外,Java编写的算法一旦加载后就会占据内存不再释放,即使相应报表不再被访问。而使用集算器没有这个问题,算法执行完后会立即释放,不再占用内存。

算法外置减少存储过程
在体系结构方面用存储过程准备报表数据和用Java程序是类似的,也会造成耦合度高的问题,只是从报表模块与主程序之间的耦合变成的报表模块与数据库之间的耦合。
存储过程存放在数据库中,报表模板放在文件系统中,保持两者同步修改依然很麻烦。
存储过程修改时需要申请一定级别的管理员权限做重编译,虽然不像Java那样难以做到热切换,但数据库高权限的频繁使用又会带来安全隐患。
比Java更糟糕的是,数据库及其中的存储过程可能被多个应用共享,如果管理不善,很容易造成多个应用之间的高耦合,时间长了会搞不清楚某个存储过程在被哪些应用调用,越来越混乱。
同样地,采用集算器也可以极大程度地减少数据库中的存储过程,算法外置后与报表模板一起存放管理,完全归属于报表模块,不仅降低与应用其它部分的耦合,更不会造成与其它应用的耦合。

实际上,存储过程本身编写难度并不小,遍历式计算代码的性能也不佳,而且可移植性很差,原则上在报表业务中应当尽量少用存储过程。
不过,集算器并不能完全替代存储过程,某些涉及数据量巨大难以移出库外计算的情况还是可能要用存储过程做些预先处理。

数据外置减少中间表
数据量巨大或计算过程太复杂时,我们经常会事先对原始数据做些处理后形成中间结果,再基于这些中间结果开发报表。这些中间结果一般是以数据库表的形式存在的,也就是这里所谓的中间表。
一个运行时间较长的系统中,中间表的数量往往会远远大于原始表。某些移动公司的数据库中有上万个表,即使很复杂的业务用五百个表也基本能描述了,这些上万的表中绝大多数都是为报表服务的中间表,这肯定是数据库厂商都没想到过的情况。

与存储过程类似,大量的中间表也会造成数据库管理的混乱。
数据库中的表是以线状方式存储的,相当于没有分类,而数据库被各个应用共享,中间表都混到一起,很难搞清楚。这需要项目组有很强的管理控制能力才能理清,比如规定中间表的命名规则并保证得到执行,但强化管理常常是以牺牲开发效率为代价的,项目时间一紧张就顾不得这些规矩了。
管理能力不够好其实是常态,这就会导致中间表越来越多,积累到上万可能是有点极端,但总归不是个小数目。这些中间表可能有相当多已经没有用了,但因为不清楚有哪些应用还在使用而只能先留着,相应的ETL过程也仍然要无意义地浪费计算资源继续更新数据。

那么为什么要把这些中间结果存到数据库中,而不能存放到文件系统中呢?
这是因为我们不可能为每个报表的每种参数组合事先计算中间结果,在生成报表时还需要根据参数进行计算,也就是要求这些中间结果仍有计算能力,而目前只有数据库有这种计算能力,文件是没有计算能力的,于是中间数据就只能变成中间表。

中间数据一般都是由不再改变的历史数据计算出来的,完全不需要数据库的事务一致性能力,因为都是导出的冗余数据,也不需要很高的稳定要求,数据坏了重算一次就行了,存放在数据库中仅仅为了获得计算能力,实在是划不来的。
有了集算器后,就可以将中间数据外置到文件系统中,由集算器提供针对文件的计算能力,可以有效地减少中间表,不必再让这些冗余数据继续占用昂贵并且低效的数据库空间。
外置的中间数据文件还可以使用文件系统的树形结构管理,与报表模板及数据准备算法统一存储。这不仅管理简单方便,而且,由于不考虑写入和一致性的需求,文件还会比数据库有更好的IO吞吐性能,整体提高报表的运算速度。

混合运算实现T+0报表
关系数据库的事务一致性能力目前尚没有有效的替代者,交易系统仍然有必要使用关系数据库来建设。
这种情况下,要实现T+0全数据量的实时报表,我们就得把历史数据继续存放在当期的交易数据库中一起计算,历史数据常常要庞大得多,这会要求我们建设更大容量的数据库,成本当然会很高。而且即使愿意支付成本,这个数据量也不可能一直增长,太大了会影响到交易业务的性能,这就不可容忍了。

通常的办法是把部分历史数据被移出来做个分数据库,这样可以保证交易系统的正常运转,但要实现T+0报表就麻烦得多,会涉及到跨库运算。
许多数据库都支持跨库运算,但一般都要求同类型的数据库,但历史数据和当期交易数据的要求不同,数据量更大但不要求事务一致性,很可能使用另一种数据仓库来存储。
而且,即使是同构的数据库,数据库的跨库运算的方法一般也是将另一个库中的数据表映射成本库数据表,实际运算还是一个数据库在做,而且还多出许多数据传递的通讯成本,性能和稳定性都不好。

使用集算器就可以很好地完成这个混合计算任务了。
集算器自己有计算引擎,不依赖于数据库,各个数据库内的数据计算仍由各库进行。集算器可以使用多线程向各数据库同时发出SQL语句,由这些数据库并行执行,将各自的运算结果返回到集算器再汇总处理后传给报表工具去呈现。
显然,这种机制还方便横向扩展,历史库可以有多个,是否同类型的也无所谓。
而且,集算器还有服务器方式的集群运行模式,在集算服务器的支持下,历史数据不必一定存放到数据库中,还可以存储在IO性能更好的文件系统中,配合集群计算,可以在更低的成本下获得更好的性能。

直接使用多样性数据源
像前面提到过的,集算器可以计算非关系型数据库和文件数据。直接使用多样性数据源制作报表,这不仅减少了将数据导入关系数据库的开发工作量,而且在应用体系上也更为简单,没必要为了获得更强的计算能力增加多余的关系数据库,成本降低还减少了数据导入过程中导致的不一致风险。
非关系数据库在某些方面比关系数据库更强,只是计算能力不足或不同,用集算器辅助计算后可以保留其原有的优势。比如MongoDB的对追加型日志数据的吞吐能力就远远超过普通关系数据库,但结构化计算能力较弱,用集算器来弥补后,数据可以继续留在MongoDB中,即获得其高吞吐性能也有了结构化计算能力。

提升报表运算性能

报表的性能问题主要会发生在三个环节:首先是数据源,大多数涉及数据量较大的报表,性能瓶颈几乎都是数据源造成的,最常见的表现就是发给数据库的SQL执行速度不够快;其次是取数环节,常见数据库中,Oracle和MySQL的JDBC性能很差,SQL执行得快,但数据取到报表工具却要很长时间;第三是报表本身的运算,有些关联或分组计算在报表工具中实现时会很慢。
碰到性能问题时,要根据报表生成的日志研究确定是哪个环节出的问题,然后才能对症下药地进行优化,当然也可能三个环节都有问题。
集算器对这几个环节都有一定程度的优化作用。

集算器替代报表计算
多源关联报表是很常见的形式,其具体形式是将多个数据集按某个关联字段,这在SQL中是典型的JOIN运算。然而,在报表模板中,对齐关系是用单元格内表达式各自定义的,无法描述数据集之间的整体关联关系,这样在运算时实际上是在遍历对齐,复杂度是平方级的。一般情况下这类表只有几十行,计算量虽大也感觉不到慢,但如果报表有数千行时,对齐的计算量就会有上千万次,性能问题就会很明显了。
用集算器则可以事先将多个数据集对齐后再提交给报表工具作为单数据集呈现,和SQL一样,集算器也使用了高效的HASH算法实现JOIN,复杂度是线性级的,对于上述有数千行的关联表性能也能提高数千倍。
类似地,集算器对于分组运算也采用了HASH方式,比一般报表工具用的排序方案要快得多。

报表工具采用的状态式计算方案要么无法利用中间结果,每次计算都只能从原始数据和单元格开始,有些涉及单元格集合的运算效率会很低;要么就采用隐藏格来保持中间结果,这又会占用太多内存,而Java程序的性能对内存非常敏感。报表计算时是带着单元格外观属性一起进行的,这会占用更多内存。
使用集算器事先准备数据则没有这些问题,过程式计算可以方便地复用中间结果,只进行纯粹的数据计算,不涉及隐藏格和外观属性,内存使用效率更高。

使用缓存能够有效地改善报表响应的用户体验,高端的报表工具一般都提供缓存功能。但报表工具的缓存机制比较死板,只能针对整个报表,不能只缓存报表的某个部分,两个报表有共同部分也无法复用缓存,也没法分别指定不同报表缓存在不同参数下的不同生存周期。因为报表工具采用可视化的配置方案,虽然使用简单,但很难设置过多复杂的参数。
用集算器准备数据时就可以实现可控缓存的效果,集算器是程序代码,可以由开发者灵活决定使用缓存的时刻及范围的策略,这样就可以实现报表的部分缓存、多个报表之间缓存复用、以及不同缓存的不同生存周期。

对于高并发报表,我们还可以利用集算器的内存共享机制,将报表用到的数据缓存在内存中,几个报表可以共享这份内存中数据。从内存中计算不仅能获得数倍于数据库或文件的访问性能,而且可以更方便地实施并行计算,充分利用现代CPU多核的优势,而集算器编写多线性并行计算代码也是非常简单的。
对于这种场景,还可以采用集算器的内存字节表的方式来提高Java内存利用率,数据加载成字节,在使用时才对象化。牺牲大约30%的性能,但可以将Java的内存利用率提高3至5倍,使用内存后,即使牺牲掉30%的性能也仍然远远比数据库和文件等外存更快。

集算器优化数据源计算
原则上讲,数据库本身的性能无法被报表工具以及其它数据库外部的技术手段优化,只能想办法优化SQL的写法。不过,还是有些场景可以使用集算器提高数据库相关的性能。
大多数情况下SQL的执行效率都较高,但如果SQL过于复杂,有许多子查询再与JOIN和GROUP等嵌套在一起时,数据库可能会表现出很糟糕的性能,原因是数据库不能正确地优化复杂SQL的执行路径,而SQL不提倡分步的语法让程序员实施干预也相当困难。
我们在实际应用过程中就碰到过几例,其中有一例是这样的:要针对若干子查询的结果再做JOIN+WHERE+GROUP,SQL执行的非常慢,接近7分钟。但把每个子查询单独执行并不慢,总和不到1分钟。于是我们用集算器作为主控程序,分别执行每一个子查询+WHERE,把结果集取出后在集算器中实现后续的JOIN+GROUP,结果性能从近7分钟降到了1分多一点,提高了5倍。
具体原因只能猜测了,估计是数据库在优化这句SQL时,把子查询拆开了和JOIN一起做,反而性能下降。如果有对数据库优化很精通的程序员,也许也能通过调整某些优化参数让数据库找到正确的优化路径,但这毕竟对人员要求过高了。而使用集算器就可以自由控制执行路径,部分运算移出数据库实施,总体上起到性能优化的效果。

前面曾提到过,Oracle等数据库的JDBC性能较差,而报表性能又严重依赖于取数环节,在数据库负担不重的时候,SQL可能很快地执行完,但取数却需要好几分钟,让用户无法忍受。这时候可以采用多线程并行的方式同时建立多个数据库连接从数据库分段取数,我们实际测试表明并行取数的性能提升基本上就是在做除法。但是,报表工具无法直接实现这个效果,而借助集算器就可以轻松实现。

还有些数据源计算是用Java编写的。理论上讲,集算器是用Java开发并解释执行的,多过了一道手,不可能比直接写Java代码有更好的性能!但在实际情况中,大多数应用程序员更擅长处理业务计算,而不是很精通编写这些底层算法。举个例子,很多应用程序员不会写HASH GROUP算法,或者是懒得写,代码毕竟复杂了太多,结果就用排序做GROUP,这时候Java直接编码的计算效率就会远远低于使用集算器了,因为集算器已经实现了许多高效算法可以直接使用。

报表的数据源有时是事先准备好的,就是前面说过的中间表。而计算这些中间表也是用SQL、存储过程或者Java来完成的,刚才这些分析对这类工作也是成立的,采用集算器经常也能提高中间数据准备的性能,减少ETL的窗口时间。而且还可以准备成库外文件,在报表生成时获得更好的IO性能的同时减少数据库负担,进一步优化整个报表应用的综合性能。

集算器协助大数据报表
集算器的多线程机制还可以用于操纵多个数据库以集群方式并行计算以获得更高性能,这个优势还可以横向扩展。

前面说过的T+0报表即是采用多数据库集群方案。多个数据库分段存储数据,每个数据库的数据量都不太大,保证运算性能够好。集算器以并行方式发出SQL给各个数据库分别计算,收到结果集后在集算器再汇总后提交给报表工具呈现。常见的过滤、分组汇总等运算都可以很方便地完成。数据量进一步增长时可以再增加更多的数据库分段以实现横向扩展。
使用数据库本身的集群方式,配置复杂度还是环境成本要求都远远高于这个方案。采用集算器实现多数据库集群还允许异构数据库集群,比如可以将小型机上的Oracle与PC服务器上的MySQL集群起来。

我们知道,文件系统的IO性能要远远好于数据库,原因可能是数据库要为写操作预留空隙,存储不够紧致了,而且为保证读一致性要更多地扫描回滚段也会消耗时间。不管怎么说,数据库的IO性能远低于文件是个不争的事实。
如果能够把数据外置出来,采用集算器的压缩数据格式存储,则可以获得比数据库更高的性能。实际测试表明,集算器对大数据的遍历性能在单线程时与Oracle基本相当,如果使用多线程并行时则会有明显优势,在数据量超过内存数倍时,Oracle的并行选项基本不起作用,而集算器并行时对性能的提升基本上和做除法一样。
集算器还支持列式存储,对于访问列数较少的查询和报表比行式数据库能有数量级的性能提升,而且这个列式存储也支持分段并行。
在脚本执行方面的测试,集算器代码解释执行性能也极大幅度地优于Oracle存储过程代码。这样,对于难以直接使用SQL写出的过程性复杂运算,如果将数据外置使用集算器运算,也将好于在库内使用存储过程运算。
前面提过,如果内存较大,还可以事先将数据读入内存获取更高性能。集算器支持内存记录的引用,用这种方式表达的连接运算与传统SQL的外键对应方式相比,不仅运算描述更为简单,运算性能也高得很多。实际测试表明,集算器的指针连接方式能比同容量的Oracle外键连接方式快出一倍以上。
另外,集算器本身也有可集群的服务器,在数据量更大时还可以使用集群进一步提速。

现金官网游戏下载