写在前面
与以磁盘存储为主的普通数据库相比，内存数据库的数据访问速度可以高出几个数量级，能大幅提高运算性能，更适合高并发、低延时的业务场景。
不过，当前大部分内存数据库仍然采用 SQL 模型，而 SQL 缺乏一些必要的数据类型和运算，不能充分利用内存的特征实现某些高性能算法。仅仅是把外存的数据和运算简单地搬进内存，固然也能获得比外存好得多的性能，但还没有充分利用内存特征，也就不能获得极致的性能。
下面我们来看看，有哪些适合内存特征的算法和存储机制，可以进一步提升内存数据库计算速度。
指针式复用
我们知道，内存可以通过地址（指针）来访问。但 SQL 没有用内存指针表示的数据对象，在返回结果集时，通常要把数据复制一份，形成一个新的数据表。这样不仅多消耗 CPU 时间（用于复制数据）而且还会占用更多昂贵的内存空间（用于存储复制的数据），降低内存使用率。
除了 SQL 型的内存数据库外，Spark 中的 RDD 也有这个问题，而且情况更严重。为了保持 RDD 的 immutable 特性，Spark 在每个计算步骤后都会复制出新的 RDD，造成内存和 CPU 的大量浪费。所以，即使耗用了巨大资源，Spark 也仍然做不到高性能。相比之下，SQL 型的内存数据库通常还会优化，在 SQL 语句中的计算会尽量使用内存地址，通常要比 Spark 的性能更好。
但是，受到理论限制，实现 SQL 的逻辑时，返回的结果集就必须复制了。如果涉及多步骤的过程运算，要多次在上一步的结果集（临时表）基础上进一步计算，SQL 的劣势就会很明显了。
事实上，如果没有改变数据结构，我们可以直接用原数据的地址形成结果集，不需要复制数据本身，仅仅多保存一个地址（指针），同时减少 CPU 和内存的消耗。
SPL 扩展了 SQL 的数据类型，支持这种指针式复用机制。
比如:
对订单表按照订单日期（odate）范围过滤后，分别求出订单金额（amount1）大于 1000 和运货费（amount2）大于 1000 的订单，再计算出两者的交集、并集和差集，最后将差集按照客户号（cid）排序。
SPL 代码大致是这样：
A |
B |
|
1 |
=orders.select(odate>=date(2000,1,1) && odate<=date(2022,1,1)) |
|
2 |
=A1.select(amount1>1000) |
=A1.select(amount2>1000) |
3 |
=A2^B2 |
=A2&B2 |
4 |
=A2\B2 |
=B2\A2 |
5 |
=A4.sort(cid) |
=B4.sort(cid) |
以上代码中有好几个步骤，有的中间结果也被用了多次，但由于使用的都是订单表记录的指针，所以内存占用增加的很少，也避免了记录复制的耗时。
外键预关联
外键关联是指用一个表（事实表）的非主键字段，去关联另一个表（维表）的主键。
比如订单表中的客户号和产品号分别关联客户表、产品表的主键。
现实运算中这种关联可能多达七八个甚至十几个表，还可能出现多层的关联。SQL 数据库通常使用 HASH JOIN 算法来做内存连接，需要计算和比对 HASH 值，过程中还会占用内存来存储中间结果，关联表很多时计算性能就会急剧下降。
其实，我们也可以利用内存指针引用机制事先做好关联。在系统初始化阶段，把事实表中的关联字段值转换为对应维表记录的指针。因为维表的关联字段是主键，所以关联记录唯一，将外键值转换成记录指针不会引起错误。在后续计算中，需要引用维表字段时，可以用指针直接引用，无需计算和比对 HASH 值，也不需要再存储中间结果，从而获得更优的性能。SQL 没有记录指针这种数据类型，也就无法实现预关联了。
SPL 则从原理上支持并实现了这种预关联机制。
例如，完成订单表和客户表、产品表预关联的代码大致是这样：
A |
|
1 |
=file("customer.btx").import@b().keys@i(cid) |
2 |
=file("product.btx").import@b().keys@i(pid) |
3 |
=file("orders.btx").import@b().switch(cid,A1;pid,A2) |
4 |
>env(orders,A3) |
A1、A2 加载客户表和产品表。
A3：加载订单表，将其中的客户号 cid、产品号 pid 转换为对应维表记录的指针。
A4：将完成预关联的订单表存入全局变量，供后续计算使用。
系统运行时，按照产品供应商过滤订单，再按客户所在城市分组汇总的代码大致是下面这样：
A |
|
1 |
=orders.select(pid.supplier=="raqsoft.com").groups(cid.city;sum(pid.price*quantity)) |
订单表中的 pid 已经转换为产品表记录的指针，所以可以直接用“.”操作符引用产品表记录。 不仅书写更简单，而且运算性能也快得多。
只是两、三个表关联时，预关联和 HASH JOIN 的差别还不是非常明显。这是因为关联并不是最终目的，之后还会有其它很多运算，关联本身运算消耗时间的占比相对不大。但如果关联情况比较复杂，涉及的表很多，以及有多层的时候（比如订单关联产品，产品关联供应商，供应商关联城市，城市关联国家等等），预关联的性能优势会更明显。
序号定位
与外存相比，内存的另一个重要特征是支持高速的随机访问，可以快速从内存表中按指定序号（也就是位置）取出数据。在做查找计算时，如果被查找的值正好是目标值在内存表中的序号，或者很容易通过被查找值计算出目标值的序号，我们就可以用序号直接取目标记录。这种方法不需要进行任何比对就能直接取出查找结果，性能不仅远远好于遍历查找，也好于使用索引的查找算法。
但是，SQL 以无序集合为基础，不能按序号取成员，只能用序号去查找。如果没有索引就只能遍历查找，会非常慢。即使有索引也要计算 HASH 值或用二分法查找，速度也比不上直接定位。而且，建立索引也会占用昂贵的内存。如果数据表中没有序号还要先排序再硬造个序号时，性能就会更差。
SPL 以有序集合为基础，提供序号定位功能。比如订单表中的订单号是从 1 开始的自然数。在查找订单号 i 时，直接取订单表中的第 i 条记录就行了。再比如数据表 T 从 2000 年到 2022 年每天存储一条数据，现在需要查询指定日期的记录。日期虽然不是目标值的序号，但是我们可以先算出指定日期距离起始日期的天数。这就是目标值的序号，然后再用序号取 T 表记录就可以了。对表 T 用序号定位查找 2022 年 4 月 20 日记录的代码，大致是下面这样：
A |
|
1 |
=date(2022,12,31)-date(1999,12,31) |
2 |
=T_orginal.align@b(to(A1),dt-date(1999,12,31)) |
3 |
=env(T,A5) |
4 |
=T(date(2021,4,20)-date(1999,12,31)) |
A1：计算出 2000 年到 2022 年总天数是 8401 天。
A2：用原始的 T 表记录计算出距离起始日期的天数，再和 to(A1)这个自然数集合 [1,2,3,…,8401] 对齐，空缺的日期会用 null 补齐。align 的 @b 选项表示对齐时将使用二分法来查找位置，这样完成对齐动作也会更快一点。
A3：计算好的结果，放到全局变量 T 中。
A4：要查找 2021 年 4 月 20 日记录，求出这个日期和起始日期距离 7781 天，直接取出 T 表中第 7781 条记录就可以了。
A1 到 A3 是对齐计算，用于处理空缺的日期，可以放在系统初始化阶段。在查找计算时，用 A4 中的序号定位代码就能得到查找结果，实际查找的日期可以作为参数传入。
集群维表
当数据量太大，超出单机内存时，就要使用集群来加载这些数据。许多内存数据库也支持分布式计算，通常是将数据分成多段，分别加载到集群不同分机的内存中。
JOIN 是分布式计算的一个麻烦任务，会涉及多个分机之间的数据传输。严重的时候，传输造成的延迟会抵消集群分摊计算量得到的好处，会出现集群变大反而性能并不能提升的现象。
SQL 体系下的分布式数据库，通常是将单机 HASH JOIN 方法扩展到集群上。每个分机根据 HASH 值将本机数据分发到其他分机，确保相关联的数据在同一分机上。然后再在各个分机上做单机连接。但是，HASH 方法在运气不好的时候，可能会造成数据分配的严重不均衡，需要借助外存来缓存这些分发到的数据，否则可能因为内存溢出而导致系统崩溃。但是，内存数据库的主要特征就是将数据加载到内存中计算，出现外存缓存会严重拖慢计算性能。
实际上，外键关联的事实表和维表有很大区别。事实表一般都比较大，要用各个分机内存分段加载才能装的下。正好事实表也比较适合分段，每个分段的数据都相互独立，分机之间不需要相互访问。而维表记录则会被随机访问，事实表的任何一个分段都可能关联全部维表记录。我们可以利用事实表和维表的区别，对集群的外键关联提速。
如果维表比较小，则将维表全量数据复制到所有分机内存中。这样，每个分机中的事实表分段和全量维表就可以继续完成预关联，完全避免了关联过程中的网络传输。
如果维表也很大，单机内存放不下，只能在各分机内存中分段加载。这时，没有一个分机上有全量的维表，外键关联计算就无法避免网络传输了。不过传输内容并不算很大，只涉及事实表的外键和维表关联记录的字段，事实表其它字段不需要传输，计算可以直接完成，过程中也不会产生缓存数据。
SPL 从原理上区分维表和事实表，针对维表较小和维表较大两种情况，分别提供了维表复制机制和分段维表机制，实现了上述算法，能显著提高集群情况下外键关联的计算性能。
备胎式容错
集群系统必须要考虑容错，内存数据的容错和外存是不同的。外存一般使用副本的方法，即同一份数据有多个副本，某个分机失效后仍然能在其它分机找到数据。这种机制的存储利用率很低，只有 1/k（k 是副本数量）。
但是，对于内存中的数据，却不能使用这种副本容错方法。这是因为硬盘足够便宜且几乎可以无限扩容，但是内存要昂贵的多而且扩容有上限。只有 1/k 的内存利用率是无法容忍的。
内存容错需要不同于外存的专门手段。SPL 提供了备胎式容错机制，将数据分成 n 段后分别加载到 n 个分机的内存中。然后准备 k 个空闲的分机作为备用机。当正在运行的某个分机失效时，则立即启用某个备用机，临时加载失效分机的数据，和其它分机重新组成拥有完整数据的集群继续提供服务。失效的分机排除故障后恢复使用，可以再充当备用机。整个过程和汽车更换备胎的模式很像。
备胎式容错机制的内存利用率可以高达 n/(n+k)，远远高于副本式容错的 1/k。能加载进内存的数据量通常不会非常大，分机失效后临时加载的时间并不多，集群服务就可以较快地恢复。
回顾与总结
内存数据库的计算体系，必须充分利用内存的特征才能获得极致性能。从数据计算的角度来看，内存主要优点有：支持指针引用、支持高速随机访问、并发读取能力强。内存的缺点是：成本高昂、扩容有上限。
而 SQL 计算体系中缺乏一些必要的数据类型和运算，比如：缺少记录指针类型，不支持有序运算，JOIN 定义过于笼统，不区分 JOIN 类型等，从原理上就不能充分利用内存的上述特征实现某些高速算法。基于 SQL 的内存数据库，通常只是简单的照搬外存数据结构和运算，会出现各种问题。比如：记录式复制过多消耗 CPU 和内存；查找和 JOIN 性能没有达到极致。再比如集群方面：内存利用率过低；大量网络传输导致分机数量增加但性能反而下降；多机 JOIN 出现外存缓存等等。
开源数据计算引擎 SPL 扩展了数据类型和运算定义，可以充分利用内存的特征，从而实现多种高性能算法，让性能达到极致。其中，指针式复用利用内存特有的指针引用机制，节省了内存空间，而且速度更快。预关联同样利用指针引用机制，在初始化阶段完成很耗时的外键关联，后续计算中直接使用关联好的结果，计算速度显著提高。序号定位利用有序性，充分发挥内存高速随机访问的优势，不用做任何计算和比对，直接用序号读取记录，性能好于 HASH 索引等查找算法。集群维表有效避免或减少了网络传输、避免了外存缓存，备胎式容错在保证高可用性的前提下，有效提高了集群内存利用率。
除此之外，SPL 还提供了排号键、序号索引、数据类型压缩等等其它方法。程序员可以根据具体的场景，有针对性的采用这些方法，就能充分发挥内存的优势，从而有效提升内存数据计算的性能。