基于列存储的数据库存储系统研究
基于列存储的数据库，相对于传统的基于行的数据库，更适合在数据仓库存储方面发挥特长1简介
在项目中，将研究一个客户（常规）文件系统设计，以提高基于列存储数据库的查询性能。
该基于列存储数据库除了在磁盘上存储数据方式不同外，类似于典型的关系型数据库（基于行存储的数据库,如MySQL或Postgres）。
不同之处如图1所示：在一个基于行存储的数据库中，每一行的属性按顺序存储，并在每一行被存储在一个连续的文件中。
而在一个基于列存储的数据库中，每个属性列存储在一个单独的文件。
这个文件的配置有一个优势，主要是适合只读数据库（数据仓库）。
首先，任何查询涉及到的数据库属性的子集回归，只需要较少的磁盘带宽，因为只加载所需的属性。
随着装载属性增多，查询次数也就增加。
其次，每个列存储一个单一类型使文件比传统的数据库可压缩（整数，八进制，字节，等等）性更高。
压缩减少了磁盘上的数据读取量，可以进一步提高性能。
第三，CPU只处理为所需属性的数据列，只需要在内存中缓存，节省内存资源，提高CPU的性能。
基于行存储的数据库
Source IP Dest IP Source Port Dest Port
基于列存储的数据库
图1：基于行存储数据库和基于列存储数据库文件系统布局
面向列存储的缺点之一是：一个表中包含多个files。
推测由于基于列存储可以降低磁盘带宽要求，因此基于列存储的数据库可以提高查询性能。
但是它将增加磁盘查找时间，因为查询期间在一个磁盘上要定位更多的files。
因此希望文件系统可以定制，这样可以使基于列存储数据库的file寻求时间最小化，这样提高查询性能。
这个项目的目的是为了提高基于列存储数据库的操作性能，用于探讨如何捕获和储存大容量（数兆兆字节）网络流量（目前的数据包或网络流动数据NetFlow data）的高查询性能。
因此，这个项目的数据集来自劳伦斯伯克利国家实验室（LBNL）收集了几个月的包头数据。
该网络数据在基于列的环境中运行良好，因为数据一旦写入就很少修改，使其适合于只读型的数据存储，也就适合数据仓库类型的数据存储。
2背景
为了实现这个项目，使用一个基于列存储数据库——Fastbit，而劳伦斯伯克利国家实验室的包头数据作为测试数据集。
Fastbit支持一个SQL查询语言子集和可以进行快速数据检索的位图索引。
它支持索引压缩，但没有数据压缩。
劳伦斯伯克利国家实验室的数据集有2个月的包头数据相当于2/16个网络。
该网络包含7000主机总数（3000人及其他的4000）。
数据加载到数据库中,该数据库使用SiLK网络数据分析工具包，而数据可以根据自定义的数据加载工具加载。
数据被水平划分成10万个纪录块。
这样做，主要是因为网络数据是高度突发性的。
在一个典型的环境中，数据按时间被分割，但是，这就造成了在网络高流量时出现数据量大的捕获文件，而在低流量时出现小的捕获文件。
因此保持设置分区大小，有助于在进行某些类型查询时候可以减少和预测磁盘的读取量。
在进行数据库并行操作时候还可以发挥辅助作用，因为分区可以分发和复制一些节点，在查询时候每个节点可以负责处理大约相同数量的分区。
这将有助于每台计算机在一个相同的时间段内返回查询结果。
每个数据库分区由一个列文件及其对应的索引文件组成，如图1所示。
它还包含一个分区描述文件，描述分区中的文件。
每个分区有相同数量的文件（19）。
如上所述，每个分区包含高达10万条纪录，因此，一列的大小应是相同的，列并且横跨所有事先已知的分区。
由于有些分区没有完全充满，因此，列文件的大小可能要小些，但是在一个连续的网络数据集中分区最终有望被存满。
分区文件描述了分区中的所有列（见表1 part.txt）。
既然横跨所有分区的列的数量是不变的，那么文件的大小也应和横跨所有分区的类似。
不过，分区的文件是基于文本的，所以文件的大小在每一种情况下不会完全一样。
每个数据列都有一个对应的索引文件，索引文件保存了每一列的独特值和一个位图，描述了该行以及所具有的值。
判断索引文件的大小是非常困难的，因为他们依赖于列的基数，以及位图的压缩率。
在大多数情况下，索引要比其对应的列文件小。
在某些情况下，他们要小100倍左右。
不过，也有例外，索引文件的大小类似对应的列部分，但在少数情况下，其实更大。
有一个较高基数的列往往有一个大索引文件。
例如，字节计数列可以有较宽的值，因此一些索引文件的字节数要高于列。
3 方法
在这个项目中，打算修改现有的Linux文件系统模块，以便在磁盘上最佳地安排数据库文件，以提高阅读磁盘能力。
知道一个分区的文件数目和大概空间将提供一些磁盘上的分区安排优势，以减少某些特定查询的磁盘寻找时间。
在Linux中，文件系统建成独立的内核，形成可以从操作系统中加载和卸载的模块。
方法是利用自定义的一个简单的Linux文件系统为基础的系统模块，并修改它以直接支持数据库分区。
初步选定MINIX v2的文件系统作为基础平台。
MINIX开始建立时是作为学
习操作系统课程学生的学习工具。
在被Ext2取代之前，它适应并成为第一个Linux文件系统。
选择MINIX，是因为它简单。
与Ext2不同，MINIX只支持一个超级块、索引节点（inode）位图、和数据块位图。
这将使它更容易理解和修改模块。
除了修改MINIX的模块，还可能要修改虚拟文件系统的某些方面，尽管目前还不清楚这是否必要。
另一个应用程序可能需要修改的是“mkfs.minix“应用程序，该程序用于格式化硬盘驱动器和安排超级块以及和磁盘上的索引节点（inode）和数据位图。
表1 数据库分区中的文件
如何定位到分区展开。
块预分配将是这一发展的一个重要方面，因为希望确保特定文件与特定的分区块相当接近，以减少磁盘寻道时间。
此项努力的大部分预计将集中在对新系统的设计和评价方面。
4试验环境
为了实施这个项目，使用一个安装在VMware的虚拟机（VM）中的Fedora14。
将建立注册在MINIX操作系统中的一个最新的特殊调试版本内核和模块。
这将允许我们在开发中万一有错误时候启动这两个核心模块。
使用“mkfs.minix“在虚拟机中创建5GB的空间并格式化以创建MINIX版本2文件系统。
期望建立由自定义的文件系统模块管理的另外5 GB的磁盘空间。
然后，可以在两个磁盘上加载相同的数据库分区，以便进行系统评价。
5评价和预期成果
为了评估自定义文件系统，打算在通用的Minix文件系统和自定义文件系统中装载一个小规模的数据库分区（可能是5至10个）然后，将选择大约10个不同的数据库查询，其查询范围如下：
1.改变数据库分区的装载量。
将尝试查询只涉及一个分区和查询所有的分区情况。
2.改变列（属性）的返回量。
预期查询时间会因查询返回的列不同而改变——返回更多的列意味着更多的文件和更长的时间。
3.索引查询- 即只有查询索引文件，而不是查询列数据。
将在两个文件系统（刷新磁盘高速缓存之间）中执行5次以记录返回的时间和结果。
这样，可以计算出两个系统上查询的均值和标准差。
算法是在查询时，安排一个分区上的文件与磁盘密切结合，最大限度地减少磁盘寻道时间。
此外，按时间顺序写磁盘分区，以便降低分区寻找时间。
最后，希望利用这一算法可以减少磁盘文件碎片，进一步提高查询性能和使磁盘空间最大化。
一般来说，期望定制文件系统所显示的查询性能要比普通Minix文件系统明显改善。
六，结论
该项目研究一个定制的文件系统，以减少一般文件系统的寻找时间，最终用于提高基于列存储数据库性能。
该文件系统对基于列存储数据库有一个很大的影响，因为每一个关系表的属性是存储在一个单独的文件中，这意味着打开该文件时，必须寻找到文件在磁盘上的位置。
希望通过聚类分区，可以减少磁盘的寻找读取，
从而提高性能。
打算建立和评估的自定义文件系统用的是来自劳伦斯伯克利国家实验室的包头数据集和Fastbit的基于列存储数据库，并将其与MINIX的第2版（Linux）文件系统执行情况进行对比。
评价将包括执行对基于列存储的两种文件系统的查询和比较。
希望自定义文件系统能够显示对现有Minix文件系统性能的改善。