列式存储（Column-orientedStorage）并不是一项新技术，最早可以追溯到年的论文Cantor。然而，受限于早期的硬件条件和使用场景，主流的事务型数据库（OLTP）大多采用行式存储，直到近几年分析型数据库（OLAP）的兴起，列式存储这一概念又变得流行。
总的来说，列式存储的优势一方面体现在存储上能节约空间、减少IO，另一方面依靠列式数据结构做了计算上的优化。
一、什么是列式存储
传统OLTP数据库通常采用行式存储。以下图为例，所有的列依次排列构成一行，以行为单位存储，再配合以B+树或SS-Table作为索引，就能快速通过主键找到相应的行数据。
行式存储对于OLTP场景是很自然的：大多数操作都以实体（entity）为单位，即大多为增删改查一整行记录，显然把一行数据存在物理上相邻的位置是个很好的选择。
然而，对于OLAP场景，一个典型的查询需要遍历整个表，进行分组、排序、聚合等操作，这样一来按行存储的优势就不复存在了。更糟糕的是，分析型SQL常常不会用到所有的列，而仅仅对其中某些感兴趣的列做运算，那一行中那些无关的列也不得不参与扫描。
列式存储就是为这样的需求设计的。如下图所示，同一列的数据被一个接一个紧挨着存放在一起，表的每列构成一个长数组。
显然，列式存储对于OLTP不友好，一行数据的写入需要同时修改多个列。但对OLAP场景有着很大的优势：
当查询语句只涉及部分列时，只需要扫描相关的列
每一列的数据都是相同类型的，彼此间相关性更大，对列数据压缩的效率较高
BigTable（HBase）是列式存储吗？
很多文章将BigTable归为列式存储。但严格地说，BigTable并非列式存储，虽然论文中提到借鉴了C-Store等列式存储的某些设计，但BigTable本身按Key-ValuePair存储数据，和列式存储并无关系。
有一点迷惑的是BigTable的列簇（columnfamily）概念，列簇可以被指定给某个localitygroup，决定了该列簇数据的物理位置，从而可以让同一主键的各个列簇分别存放在最优的物理节点上。由于columnfamily内的数据通常具有相似性，对它做压缩要比对整个表压缩效果更好。
另外，值得强调的一点是：列式数据库可以是关系型、也可以是NoSQL，这和是否是列式并无关系。本文中讨论的C-Store就采用了关系模型。
二、起源：DSM分页模式
我们知道，由于机械磁盘受限于磁头寻址过程，读写通常都以一块（block）为单位，故在操作系统中被抽象为块设备，与流设备相对。这能帮助上层应用更好地管理储存空间、增加读写效率等。这一特性直接影响了数据库储存格式的设计：数据库的Page对应一个或几个物理扇区，让数据库的Page和扇区对齐，提升读写效率。
那如何将数据存放到页上呢？
大多数服务于在线查询的DBMS采用NSM(N-aryStorageModel)即按行存储的方式，将完整的行（即关系relation）从Header开始依次存放。页的最后有一个索引，存放了页内各行的起始偏移量。由于每行长度不一定是固定的，索引可以帮助我们快速找到需要的行，而无需逐个扫描。
NSM的缺点在于，如果每次查询只涉及很小的一部分列，那多余的列依然要占用掉宝贵的内存以及CPUCache，从而导致更多的IO；
如今，随着分布式文件系统的普及和磁盘性能的提高，很多先进的DBMS已经抛弃了按页存储的模式，但是其中的某些思想，例如数据分区、分区内索引、行列混合等，仍然处处可见于这些现代的系统中。
分布式储存系统虽然不再有页的概念，但是仍然会将文件切割成分块进行储存，但分块的粒度要远远大于一般扇区的大小（如HDFS的BlockSize一般是18MB）。
更大的读写粒度是为了适应网络IO更低的带宽以获得更大的吞吐量，但另一方面也牺牲了细粒度随机读写。
三、列数据的编码与压缩
无论对于磁盘还是内存数据库，IO相对于CPU通常都是系统的性能瓶颈，合理的压缩手段不仅能节省空间，也能减少IO提高读取性能。列式存储在数据编码和压缩上具有天然的优势。
以下介绍的是C-Store中的数据编码方式，具有一定的代表性。根据1)数据本身是否按顺序排列（self-order）)数据有多少不同的取值（distinctvalues），分成以下4种情况讨论：
有序且distict值不多。
无序且distict值不多。
有序且distict值多。
?无序且distict值多。
编码之后，还可以对数据进行压缩。由于一列的数据本身具有相似性，即使不做特殊编码，也能取得相对较好的压缩效果。通常采用Snappy等支持流式处理、吞吐量高的压缩算法。
最后，编码和压缩不仅是节约空间的手段，更多时候也是组织数据的手段。在PowerDrill、Dremel等系统中，我们会看到很多编码本身也兼具了索引的功能，例如在扫描中跳过不需要的分区，甚至完全改表查询执行的方式。
四、列式存储与分布式文件系统
在现代的大数据架构中，GFS、HDFS等分布式文件系统已经成为存放大规模数据集的主流方式。分布式文件系统相比单机上的磁盘，具备多副本高可用、容量大、成本低等诸多优势，但也带来了一些单机架构所没有的问题：
读写均要经过网络，吞吐量可以追平甚至超过硬盘，但是延迟要比硬盘大得多，且受网络环境影响很大。
可以进行大吞吐量的顺序读写，但随机访问性能很差，大多不支持随机写入。为了抵消网络的overhead，通常写入都以几十MB为单位。
上述缺点对于重度依赖随机读写的OLTP场景来说是致命的。所以我们看到，很多定位于OLAP的列式存储选择放弃OLTP能力，从而能构建在分布式文件系统之上。
要想将分布式文件系统的性能发挥到极致，无非有几种方法：按块（分片）读取数据、流式读取、追加写入等。我们在后面会看到一些开源界流行的列式存储模型，将这些优化方法体现在存储格式的设计中。
1.ApacheORC
ApacheORC最初是为支持Hive上的OLAP查询开发的一种文件格式，如今在Hadoop生态系统中有广泛的应用。ORC支持各种格式的字段，包括常见的int、string等，也包括struct、list、map等组合字段；字段的meta信息就放在ORC文件的尾部（这被称为自描述的）。
数据结构及索引
为分区构造索引是一种常见的优化方案，ORC的数据结构分成以下个层级，在每个层级上都有索引信息来加速查询。
FileLevel：即一个ORC文件，Footer中保存了数据的meta信息，还有文件数据的索引信息，例如各列数据的最大最小值（范围）、NULL值分布、布隆过滤器等，这些信息可用来快速确定该文件是否包含要查询的数据。每个ORC文件中包含多个Stripe。
StripeLevel对应原表的一个范围分区，里面包含该分区内各列的值。每个Stripe也有自己的一个索引放在footer里，和file-level索引类似。
Row-GroupLevel：一列中的每行数据构成一个row-group，每个row-group拥有自己的row-level索引，信息同上。
ORC里的Stripe就像传统数据库的页，它是ORC文件批量读写的基本单位。这是由于分布式储存系统的读写延迟较大，一次IO操作只有批量读取一定量的数据才划算。这和按页读写磁盘的思路也有共通之处。
像其他很多储存格式一样，ORC选择将统计数据和Metadata放在File和Stripe的尾部而不是头部。
但ORC在Stripe的读写上还有一点优化，那就是把分区粒度小于Stripe的结构（如Column和Row-Group）的索引统一抽取出来放到Stripe的头部。这是因为在批处理计算中一般是把整个Stripe读入批量处理的，将这些索引抽取出来可以减少在批处理场景下需要的IO（批处理读取可以跳过这一部分）。
ACID支持
ApacheORC提供有限的ACID事务支持。受限于分布式文件系统的特点，文件不能随机写，那如何把修改保存下来呢？
类似于LSM-Tree中的MVCC那样，writer并不是直接修改数据，而是为每个事务生成一个delta文件，文件中的修改被叠加在原始数据之上。当delta文件越来越多时，通过minor
