《NoSQL权威指南》——2.1 列式数据库的历史

本节书摘来自异步社区出版社《NoSQL权威指南》一书中的第2章，第2.1节，作者：【美】Joe Celko（乔•塞科） ，更多章节内容可以访问云栖社区“异步社区”公众号查看。

2.1 数据库" title="列式数据库">列式数据库的历史

列式存储以及倒排或不按顺序存储文件的方式并不是最新提出的。TAXIR是1969年为生物学建立的第一个列式数据库存储系统。加拿大统计局于1976年实现了RAPID系统，并将其用于加拿大人口和住房普查数据的处理和检索，以及其他与统计相关的一些应用。RAPID被拿来与世界各地的其他统计机构共享，并在20世纪80年代被广泛使用。直到20世纪90年代，它一直被加拿大统计局使用。

多年来，Sybase IQ是市面上唯一一个可以商用的列式DBMS。然而，当OLAP（online analytical processing，联机分析处理）越来越流行后，其他产品厂商看到，可以将某些用于多维数据集和汇总的技术应用到更通用的数据库上。

由于一个列只有一种简单的数据类型，可以做很大程度的压缩。如果需要重建行，必须打破单一数据集模型并且为行进行编号，就像在一个顺序文件中所做的一样。每一行是通过检查该行行号进行重构的。具有相同的数据值的连续行号可以按范围建模：{start_position, end_position,data_value}。这是最简单的压缩格式，但也是非常强大的。很多数据以离散值进行编码，因此在同一列中常常会有大量相同的值。

然后，我们可以针对特定领域和所用的数据类型，使用内置的专门例程对数据值进行压缩。如果有某个域占用与数据值相同或者比数据值更大的空间，这就是很愚蠢的做法，而成本也随之（数据列更大）而来（占用了更多的空间，同时也降低了效率）。使用短记号为较长值构建查找表是很容易的，参考{domain_token, data_value}，现在模型变为{start_position, end_position, domain_token}。

例如，美国的电话号码中区号使用的正则表达式是[2-9][0-9][0-9]，这意味着我们至多可以有800个区号。代替这3个ASCII字符，可以用SMALLINT或BCD[1]来生成记号，并得到一个小的查找表。这个例子并没有获得很大的节省，但就是这样的小数据逐渐增加，形成了TB级数据库。另一个更有力的例子是美国城市和城镇的名字，截至2012年，美国大约有超过30 000个城市和城镇。2字节的整数可以存储65 535个记号。很少有名字只有两个字母的城市，其中还有不少名字是重复的，如美伊利诺斯州首府斯普林菲尔德是最常见的小镇的名字，这也是这个名字常常用在电视节目（如《辛普森一家》）中的原因。同样，一个2字节的整数大概可以表示180年内的日期[2]。

这也为我们提供了能够加入一定的完整性约束的独立环节。例如，666和777是有效的区号，但截至2012年还被没有被分配使用。同样，在电影中看到的555是不存在的电话区号。拨号前的Klondike 5[3]是用来保证（表示）的电话号码不能被呼叫的。在美国老电影、动画片以及现代美国电视节目中都回听到这个区号。我们可以在查找表中简单地将这些无效的值去掉！

各种形式的文本压缩方式是众所周知的。对于数据库的数据来讲，我们希望压缩是无损的，这也就意味着，当我们解压的时候，得到的内容与压缩前的内容是完全一致的。在音乐和视频中，为了速度和空间，在不伤及内容的情况下可以牺牲一些质量。Lempel-Ziv（LZ）压缩方式是无损存储中最流行的算法。DEFLATE[4]是针对解压缩速度和压缩率而优化的LZ的变体，但压缩速度可能会很慢。DEFLATE用于PKZIP、gzip和PNG等。LZW（Lempel-Ziv-Welch）用于GIF图片。另外，值得注意的是LZR（LZ-Renau）方法，它是Zip方法的基础。

LZ方法使用重复字符串的替换表，表本身往往是霍夫曼编码的（如SHRI、LZX）。这种方法非常适用于人类语言的压缩，因为语法词缀和结构词（介词、连词、冠词、小标记等）构成了大量的文本。但编码方案也倾向于遵循模式（pattern）。在美国，银行账号以美国银行家协会银行编号的代码开始的，产品序列号中会包括产品线等内容。分层和矢量编码方案采用了这种压缩方式。

近几年，已经用最小完美散列算法[5]做了大量的工作（如果还不太了解这一技术，请参见“散列快速入门”）。当列是一组相对静态的字符串时，这种方式是最理想的。任何值的集合，甚至那些没有共同子串的值，被散列成短的、固定长度的、能够被更快地进行计算的数据记号。

对这种模型比较幼稚的看法是，它是复杂的、大的、缓慢的。这只说对了一半。与简单的顺序字段读取相比，它的确是复杂的，但是它并不慢，而且也不大。

有一个观点是计算机处理单元（CPU）是瓶颈，但随后的SMP（对称多处理）、群集和MPP（大规模并行处理）技术让我们获得了数百或数千倍的CPU，可以比以往任何时候的运行速度都快。有点儿IT民俗意味的摩尔定律[6]（Moore’s law）认为每18个月计算机处理速度就会提升一倍，成本会降为之前的一半。但与此同时，数据量也越来越大。10年前，20 GB就被认为是无法控制的了，现在小型互联网创业公司已经开始管理TB级的数据。

MPP使用许多独立的CPU并行地运行同一个程序。MPP与SMP类似，但在SMP中，所有CPU共享相同的内存，而在MPP系统中，每个CPU都有自己的内存。

需要权衡考虑的是，MPP系统中更难编程，因为处理器必须相互通信并相互协调。另一方面，SMP系统在所有CPU试图在同时访问相同的内存位置时会发生阻塞。然而，这些CPU常常会发生闲置。这是由于CPU的L1、L2（尤其是L2）缓存当前缺少快速支撑大吞吐量数据的能力。在基于行的数据模型中，我们依然需要在CPU和存储间移动整条记录。

打一个比方，如个人电子产品，如果你只想从专辑购买几首曲目，在iTunes中只购买这几首曲目会很便宜。当你最想要专辑中大多数曲目，购买整张专辑会更加省钱和省时间，尽管你只播放其中的一些曲目。而“查询”与“搜索并检索”是不一样的问题。一条查询要么需要某个列要么不需要，并且在做查询编译时就可以知道需要哪些列，不需要哪些列。得益于现代处理器的速度和大型存储设备，把数据组装成行的方式在速度上远远快于从转动的磁盘中读单个字节的速度。2012年，IBM已经能够将DB2中的表的大小减为原始表的1/3或更小。由于{domain_token, data_value}这样的数据就是全部要读的数据，这种空间的节省带来很多回报，现在可以把数据放在更快的存储器上，如固态硬盘（SSD）。

列式存储和基于行的存储（数据库）之间的显著不同的是，一个表中所有的列都不会存储在数据页中。这避免了存储在数据页上的大量的元数据。这些元数据因产品不同而各异，但是最常见的元数据是每个数据页中的行（记录）相对起始位置的位移以及可能一些其他关于数据页的元数据。在这些元数据中还有每一行中的每一列相较起始位置的位移，以及这一列的值是否是null。这就是SQL数据管理系统获知在磁盘何处放置读写磁头并返回哪些数据的方式。

特别是，在早期的SQL产品中向行中加入一个VARCHAR(n)列时，它们将按CREATE TABLE语句中列的顺序分配。不过，这也意味着这些列（这里特指VARCHAR(n)的列）将为全部n个字符分配存储，即便实际存储的数据很短（例如，实际的数据长度小于n的情况）。我们曾经使用的方案是手动地将所有的VARCHAR(n)列放到DDL语句中的尾部。目前，DB2和Oracle已经在产品内部实现—在输出时对列进行重新排列，并且对用户隐藏这些细节。

列式数据库模型可以就地（或在适当的位置）压缩数据，或者对指向字符串列表的指针进行存储。例如，first_name与查找表{1 = Aaron, 2 = Abe,3 = Albert, …, 9999 = Zebadiah, …}对应。但是现在可以做一个折中，我们仍然可以将VARCHAR(n)存储为固定长度，以加快搜索，但却并不会受到太大影响，这是因为查找表很小，查找表中的每个值只出现一次，因此我们还是会有相对较小的存储量。

显然，随着在数据页上插入记录或删除记录，这些元数据映射必须被更新。删除是很容易的，被删除的行可以立即被打上标记并在列被读取时被忽略。插入的新数据可以被添加到列结构的末端。尽管这种方式运行起来没问题，但最好仍然是将相关的数据做成集群[7]，以保持数据规模很小，并使数据值更容易搜索。有实用程序来恢复（还原）存储—其他内存管理系统的垃圾收集程序的列式数据库版本。

列式数据库也可以有索引，但实际上大多数没有。事实上，列式存储本身就是索引。位移也必须通过索引来处理。

散列快速浏览

索引和指针链涉及本地数据的物理搜索、查找。给定一个需要搜索的键，可以从指针链中的一个节点遍历到另一个节点，直到找到与搜索值对应的节点，或发现这个节点不存在。

散列是以数学为基础的磁盘访问技术。先定义好搜索键，然后把它放入公式中，公式会返回一个数组或查找表的位置。该位置包含物理存储地址，可以直接去访问它通过一次磁盘访问来找到该数据。

对于量较大的数据，散列比索引快得多。随着数据量的增加树形结构的索引会变得更深。在树中查找数据需要遍历，直至最终找到一个叶子结点满足查询条件。这可能意味着数据量大的情况下需要更多的磁盘访问。

两个或多个不同的搜索键会产生相同的散列键的情况是可能的，这就是所谓的冲突或（更文雅地说）散列碰撞。这种情况下，搜索键可以使用另一个函数重新进行散列，第二个函数常常是与第一个散列函数同族的函数，但是与第一个函数相比，会在一些常量上有所变化。有证据证明，某些散列函数最多5次重新进行散列计算，就会产生独一无二的结果。

没有冲突的散列函数称为完美的散列函数。如果散列函数在数组中没有空插槽，那么它就是最小的。一个最小完美散列函数需要满足：搜索值的集合是固定的，以便散列函数可以作用于编译器和类似的数据集中的关键字。

大多数散列算法的基本工具如下。

数字化挑选。给定一个搜索键，从数中提取一些数字，也许会对这些数字重

新排列。如果能够做到随机分布，就是一项很好的技术。事实上，这种方法被百货公司用在订货窗口上，使用姓氏的第一个字母对某些字母进行分类（S代表史密斯，J代表琼斯、约翰逊等，但几乎没有人会用到X、Y和Z）。但是，客户的电话号码的最后两位数字是随机地均匀分布。

除法。配有一个素数（m）的mod（<键>，m）函数应该是非常好的散列函数（Lum et al.，1971）。它会给出(0, (m − 1))区间内的结果。TOTAL和IMAGE/3000数据库[8]中会内置一系列大素数用来分配散列表。

**乘法。**这种技术是对一个键做平方，然后取出中间的数字。5位数的键将产生一个10位数字的平方，使用中间3位会具有良好的效果。例如，54 3212=2 950 771 041，中间的数字是077作为散列。散列必须来自中间的数字，否则可能会得到太多的聚类（即重复的结果）。

折叠。这种技术取出n个数字的连续子集，并简单地将它们进行相加。例如，给定一个5位数的键，可以将所有5个数字相加，就获得了在范围（0≤散列值≤45）的结果。如果使用双数[9]，那么得到的范围将是（0≤散列值≤207）。这是一个很弱的技术，所以往往不会使用，或是被用来代替某些算法并且一般与另一种技术结合使用。

冲突解决技术也是多种多样的，最常见的一种是使用桶（bucket）。一个桶代表可容纳多个值的散列表的位置。下面是两种基本的方法。

开放寻址。这种方法试图在散列表中找到仍处于打开状态的桶。最简单的方式是从冲突的位置开始，并且将此点作为起点对开放空间进行地址递增式的线性搜索。其他类似的技术使用了比地址递增方式更加复杂的函数。常用的函数是使用二次方程式和伪随机数生成器。

外部链。可以将新的值添加到一个链表中，这个链表可能是存储在主存中或部分存储在磁盘上。但是在正确选择主存表的大小的情况下，溢出到磁盘的数据可以控制在主存中散列表大小的15%以下。这种方法是非常有效的。