infobright: 系统结构

上次初步介绍了基于mysql的数据仓库实现：infobright，这里深入介绍其结构及工作原理。下图是infobright白皮书中展示的系统架构，灰色部分是mysql原有的模块，白色与蓝色部分则是infobright自身的。下面说说它的几个主要概念及其相互协作原理。

infobright架构图

系统结构分析：

1. 跟mysql一样的两层结构，上面的逻辑层处理查询逻辑，下面的是存储引擎。
2. 逻辑层右端的loader与unloader是infobright的数据导入导出模块，也即处理SQL语句里LOAD DATA INFILE … 与SELECT … INTO FILE任务，由于infobright面向的是海量数据环境，所以这个数据导入导出模块是一个独立的服务，并非直接使用mysql的模块。
3. 逻辑层的infobright优化器包在mysql查询优化器的外面，如下面将会提到的，因为它的存储层有一些特殊结构，所以查询优化方式也跟mysql有很大差异。
4. 存储层最底层是一个个的Data Pack（数据块）。每一个Pack装着某一列的64K个元素，所有数据按照这样的形式打包存储，每一个数据块进行类型相关的压缩（即根据不同数据类型采用不同的压缩算法），压缩比很高。它上层的压缩器与解压缩器就做了这个事情。
5. 压缩层再向上就是infobright最重要的概念：Knowledge Grid（知识网格），这也是infobright放弃索引却能应用于大量数据查询的基础。它包含两类结点：每个Data Pack Node（知识节点）对应于一个Data Pack，存储该Data Pack的一些统计信息，如min, max, avg, null的个数，甚至不同值的量等等；Knowledge Node则存储了一些更高级的统计信息，以及与其它表的连接信息，这里面的信息有些是数据载入时已经算好的，有些是随着查询进行而计算的，所以说是具备一定的“智能”的。

查询原理（为什么infobright能处理大量数据的查询）：

1. 例如一个infobright表T，按列存储了两列A与B。A包含A1，A2，A3，A4；B包含B1，B2，B3，B4几个Data Pack。
2. 输入一条查询语句：SELECT MAX(B) FROM T WHERE A>3。
3. 根据查询infobright会先把A的知识网格数据取出来，因为A1-4都有相应的知识节点存储其范围，所以仅根据知识网络就能知道哪些数据块符合A>3这个查询要求。这里假设A1，A2，A3全部符合或半符合（半符合是指根据知识网格无法准确判断）要求。
4. 然后取出B1，B2，B3的知识网格，仅凭知识网格中的max信息即可判断哪个数据块是全部符合或半符合要求的，这里假设是B2。
5. 把B2取出来，解压缩，获取B2中的最大值。
6. 返回结果。

下次再介绍一下这些天我使用infobright的一些实践经验。

如上图所示，Infobright采用了和MySQL一致的构架，分为两层。上层是服务及应用管理，下层是存储引擎。Infobright的默认存储引擎是brighthouse，但是Infobright还可以支持其他的存储引擎，比如MyISAM、MRG_MyISAM、Memory、CSV。Infobright通过三层来组织数据，分别是DP(Data Pack)、DPN（Data Pack Node）、KN（Knowledge Node）。而在这三层之上就是无比强大的知识网络（Knowledge Grid）。

数据块（DP）是存储的最低层，列中每64K个单元组成一个DP。DP比列更小，具有更好的压缩比率；又比单个数据单元更大，具有更好的查询性能。

数据块节点（DPN），DPN和DP之间是一对一的关系。DPN记录着每一个DP里面存储和压缩的一些统计数据，包括最大值、最小值、null的个数、单元总数count、sum等等。

KN里面存储着指向DP之间或者列之间关系的一些元数据集合，比如值发生的范围（MIin_Max）、列数据之间的关联。大部分的KN数据是装载数据的时候产生的，另外一些事是查询的时候产生。

在这三层之上是知识网络（Knowledge Grid），Knowledge Grid构架是Infobright高性能的重要原因。

Knowledge Grid可分为四部分，DPN、Histogram、CMAP、P-2-P。

DPN如上所述。Histogram用来提高数字类型（比如date，time，decimal）的查询的性能。Histogram是装载数据的时候就产生的。DPN中有mix、max，Histogram中把Min-Max分成1024段，如果Mix_Max范围小于1024的话，每一段就是就是一个单独的值。这个时候KN就是一个数值是否在当前段的二进制表示。

Histogram的作用就是快速判断当前DP是否满足查询条件。如上图所示，比如select id from customerInfo where id>50 and id<70。那么很容易就可以得到当前DP不满足条件。所以Histogram对于那种数字限定的查询能够很有效地减少查询DP的数量。

CMAP是针对于文本类型的查询，也是装载数据的时候就产生的。CMAP是统计当前DP内，ASCII在1-64位置出现的情况。如下图所示

比如上面的图说明了A在文本的第二个、第三个、第四个位置从来没有出现过。0表示没有出现，1表示出现过。查询中文本的比较归根究底还是按照字节进行比较，所以根据CMAP能够很好地提高文本查询的性能。

Pack-To-Pack是Join操作的时候产生的，它是表示join的两个DP中操作的两个列之间关系的位图，也就是二进制表示的矩阵。

Knowledge Grid还是比较复杂的，里面还有很多细节的东西，可以参考官方的白皮书和Brighthouse: an analytic data warehouse for ad-hoc queries这篇论文。