1.4 数据存储
随着云计算、大数据、人工智能等新兴技术的发展，以及互联网业务复杂度和需求的提升，数据的核心价值不仅是简单存储，而是在于对海量数据进行处理、信息挖掘和分析预测等方面。传统的存储技术面临着数据量大、高并发和低延迟等诸多挑战，为满足现代应用对高性能、高可用性、可扩展性以及经济性等需求，分布式数据库已成为业界普遍采用的有效解决方案。分布式数据存储采用可扩展的结构，将数据分散存储在多个设备中，并将数据的分片、容错、负载均衡等功能透明化，以解决传统数据库在存储容量、高并发、高可用等方面的不足。此外，随着系统中数据量和并发量的不断增加，分布式数据库中的一致性、性能和容错等问题也需要我们去着手解决。
一般来说，计算机系统中存在多种数据存储介质。如图1-8所示，根据不同的速度、容量和成本，将它们按层次结构组织起来。主存和缓存是最昂贵和最快的存储介质，称为主存储器；二级存储器（或在线存储器）位于层次结构的下一级，例如磁盘；层次结构的最底层为三级存储器（或离线存储器），例如光盘等。
除了速度、容量和成本的不同之外，还有易失性的问题。在图1-8中，主存以上为易失性存储，即保存数据的环境如果不能满足某种条件，数据就会丢失，例如保存在DRAM中的数据是易失的，因为只要DRAM的电源被切断，其中所保存的数据就会丢失；闪存以下为非易失性存储，为了保证数据的安全，必须把数据写入非易失性存储中。
图1-8 存储设备的层次结构
为提高可靠性和可用性，使用独立磁盘冗余阵列（RAID），同时在几块硬盘上进行并发读写以提升程序运行效率。由于数据在多张磁盘上冗余存储，因此一张磁盘的损坏并不会丢失所有数据，这种组织方式也提高了数据的可靠性。
为了在成本和性能之间权衡，RAID 分为不同级别。RAID 0表示对数据进行块级拆分，但无冗余；RAID 1表示对数据进行块级拆分，并使用镜像进行冗余数据的保存；RAID 5表示对数据进行块级拆分，数据块和奇偶校验块交叉分布在磁盘中。RAID 5支持当一台磁盘发生故障时，还能够正常读取数据。在由4块磁盘构成的RAID 5存储中，奇偶校验块pk保存在第k mod 4块磁盘中，其余三块磁盘存储第3k、第3k+1、第3k+2个数据块。表1-3展示了部分数据块的存储细节，之后的数据块的存储按照规律重复。
表1-3 RAID 5磁盘阵列存储方式
我们在选择RAID级别时应该考虑的因素有经济成本、系统读写所需的性能要求、磁盘故障对系统的影响等。RAID的概念不仅在磁盘中适用，在包括SSD内的闪存设备和无线设备中的数据广播中都有应用。以下总结几种不同RAID级别的特性以及选择的参考。
●RAID 0组合两个或更多硬盘以提高性能和容量，但不提供容错功能。单个硬盘出现故障将导致阵列中的所有数据丢失。RAID 0对于需要高价格/性能平衡的非关键系统非常有用。
●RAID 1通常由两个硬盘来执行，硬盘中的数据会进行镜像，在硬盘出现故障时提供容错保护功能。读取性能得到提高，而写入性能与单个硬盘相似，可承受单个硬盘出现故障而不会丢失数据。在容错保护非常关键而空间和性能不那么重要时，往往使用 RAID 1。
●RAID 5提供容错保护功能并可提高读取性能。至少需要三个硬盘才能组成。RAID 5可承受单个硬盘丢失。硬盘发生故障时，故障硬盘上的数据将从其余硬盘上延展的奇偶校验进行重建。因此，当 RAID 5阵列处于降级状态时，读写性能会受到严重影响。当存储空间和成本的重要性高于性能时，RAID 5较为理想。
●RAID 6与RAID 5相似，但其提供了另一层区块延展功能，可承受两个硬盘出现故障。至少需要四个硬盘才能组成。RAID 6的性能因其额外的容错保护功能而低于RAID 5。在存储空间和成本较为重要且需要承受多个硬盘出现故障的情况下，RAID 6较为理想。
●RAID 10集合了RAID 1与 RAID 0的优势。读写性能有所提高，但用于存储数据的空间仅为总空间的一半。需要四个或更多硬盘，因此成本相对较高，但在提供容错保护功能时性能较高。只要故障不是发生在同一子群组，RAID 10可承受多个硬盘出现故障的情况。RAID 10对于需要高I/O的应用程序而言是理想的解决方案，例如数据库服务器。
1.4.1 数据库内部的数据结构
数据库的底层存储使用了各种树形结构。在树形结构中，二叉树的查找效率最高（比较次数少），但是数据库的文件索引是存放在磁盘上的，所以我们不仅要考虑查找效率，还要考虑磁盘的寻址加载次数，因此传统的关系型数据将数据以B树的形式存储在磁盘上。它们会在RAM上使用B树维护这些数据的索引，来保证更快的访问速度。相比于从磁盘中加载数据，在内存中的数据运算效率更高，而我们进行数值比较的时候是在内存中进行的，虽然B树的比较次数可能比二叉查找树多，但是磁盘操作次数少。实际上磁盘的加载次数基本上是和树的高度相关联的，高度越高，加载次数越多，高度越低，加载次数越少。所以对于这种文件索引的存储，我们一般会选择矮胖的树形结构。
当今信息时代，在消息、聊天、实时通信和物联网等以客户为中心的服务和大量无结构化数据的分布式系统中，每小时都会进行数百万计的写入操作。因此，这些系统是以写为主的系统，为了满足这些系统的需要，数据库需要拥有快速插入数据的能力。典型的数据库并不能很好地满足类似的场景，因为它们无法应付高可用性、尽可能的最终一致性、无格式数据的灵活性和低延迟等要求。
因此LSM树应运而生。日志结构的合并树（LSM-tree）是一种基于磁盘的数据结构，旨在为在较长时间内经历高记录插入（和删除）率的文件提供低成本索引。LSM-tree使用一种算法来降低延迟和执行批量索引更改，以类似于归并排序的有效方式将来自基于内存的组件的更改级联到一个或多个磁盘组件。在此过程中，所有索引值都可以通过内存组件或磁盘组件之一连续访问（除了非常短的锁定期）。与传统的访问方法（例如B树）相比，该算法大大减少了磁盘臂的移动次数，并且将在传统访问方法的插入磁盘臂成本超过存储介质成本的领域中提高性价比。
LSM Tree这个概念就是结构化合并树的意思，它的核心思路其实非常简单，就是假定内存足够大，因此不需要每次有数据更新就必须将数据写入磁盘中，而可以先将最新的数据驻留在内存中，等到积累到足够多之后，再使用归并排序的方式将内存中的数据合并追加到磁盘队尾（因为所有待排序的树都是有序的，所以可以通过合并排序的方式将数据快速合并到一起）。
LSM树的索引结构图1-9所示。内存部分导出形成一个有序数据文件的过程称为flush。为了避免flush影响写入性能，会先把当前写入的MemStore设为Snapshot，不再容许新的写入操作写入这个Snapshot的MemStore。另开一个内存空间作为MemStore，让后面的数据写入。一旦Snapshot的MemStore写入完毕，对应内存空间就可以被释放。这样，就可以通过两个MemStore来实现稳定的写入性能。
图1-9 LSM树索引结构
在操作系统中，数据库以文件的形式保存在磁盘中，数据库可映射为多个文件。每个文件中存储记录的序列，记录大小不会超过文件块（block）的大小，并且每条记录保存在同一个块中。在文件块中删除一条记录时，需要向前移动所有的块以释放空间，这会造成大量的资源浪费。在文件头中保存一个指针，指向被删除的地址，形成一个释放链表（free list）。若释放链表指向一个地址，则将新加入的数据插入该地址，当释放链表为空时，将新增记录插入到尾端。
变长记录即每条记录的长度是可变的，比如字符串等数据类型。对于变长属性使用2字节记录偏移量和长度，使用空位图来记录哪些属性为空值。使用分槽的页结构来保存变长记录，分槽的页结构一般用于在块中组织记录，如图1-10所示。
图1-10 分槽的页结构
分布式存储架构是分布式文件系统（包括对象存储和块存储）、分布式数据库的有效组成部分。分布式存储架构通常由3个部分组成：客户端、元数据服务器和数据服务器。
●客户端：负责发送读写请求给一个自动路由服务器或一个中心化的服务器。
●元数据服务器：元数据从数据管理中分离，庞大的元数据需要独立管理，因此元数据服务器负责管理元数据和处理客户端对元数据的请求。
●数据服务器：负责存放用户文件等数据，保证数据的可用性、完整性和一致性。
以元数据和用户数据分离的方式设计架构有两个好处：性能和容量可同时扩展，系统规模具有很强的伸缩性。
分布式存储的比较
为了满足海量数据的存储需求，市场上出现了分布式存储技术。分布式存储的兴起与互联网的发展密不可分，互联网公司由于其大数据、轻资产的特点，通常使用大规模分布式存储系统。我们对比了主流的分布式存储架构，它们各有各的优势和使用场景。
HDFS主要用于大数据的存储场景，是Hadoop大数据架构中的存储组件。HDFS在开始设计的时候，就已经明确它的应用场景就是大数据服务。主要的应用场景有大文件存储，例如几百兆、几个G的大文件。因为HDFS采用元数据的方式进行文件管理，而元数据的相关目录和块等信息保存在NameNode的内存中，文件数量的增加会占用大量的NameNode内存。
如果存在大量的小文件，会占用大量内存空间，引起整个分布式存储性能下降，所以使用HDFS存储大文件比较合适；HDFS适合低写入、多次读取的业务。就大数据分析业务而言，其处理模式就是一次写入、多次读取，然后进行数据分析工作，HDFS的数据传输吞吐量比较高，但是数据读取延时比较差，不适合频繁的数据写入；存储数据的DataNode依赖于廉价的现成硬件，从而降低了存储成本。此外，由于HDFS是开源的，因此没有许可费；HDFS旨在检测故障并自行自动恢复，可从硬件故障中快速恢复；HDFS可在所有硬件平台上移植，并且兼容多种操作系统，包括Windows、Linux和macOS，具有可移植性；HDFS专为高数据吞吐量而构建，最适合访问流数据。
Ceph是一个可扩展的分布式存储系统，是目前应用最广泛的开源分布式存储系统，已得到众多厂商的支持，许多超融合系统的分布式存储都是基于Ceph深度定制的。而且Ceph已经成为Linux系统和OpenStack的“标配”，用于支持各自的存储系统。Ceph可以提供对象存储、块设备存储和文件系统存储服务，同时支持三种不同类型的存储服务的特性，这在分布式存储系统中是很少见的。
Ceph没有采用HDFS的元数据寻址的方案，而是采用CRUSH算法，数据分布均衡，并行度高。而且在支持块存储特性上，数据可以具有强一致性，可以获得传统集中式存储的使用体验；在对象存储服务方面，Ceph支持Swift和S3的API接口；在块存储方面，Ceph支持精简配置、快照、克隆；在文件系统存储服务方面，Ceph支持POSIX接口，支持快照。但是目前Ceph支持文件的性能与其他分布式存储系统相比，部署稍显复杂，性能也稍弱，一般都将Ceph应用于块和对象存储；Ceph是去中心化的分布式解决方案，需要提前做好规划设计，对技术团队的能力要求比较高。特别是在Ceph扩容时，其数据分布均衡的特性会导致整个存储系统性能的下降。
Swift是一个高度可用、分布式、最终一致的对象存储。组织可以使用Swift高效、安全且廉价地存储大量数据。Swift主要面向对象存储，与Ceph提供的对象存储服务类似，主要用于解决非结构化数据存储问题。
它和Ceph的对象存储服务的主要区别是，Swift的特性客户端在访问对象存储系统服务时，Swift要求客户端必须访问Swift网关才能获得数据，而Ceph使用一个运行在每个存储节点上的OSD（对象存储设备）获取数据信息，没有一个单独的入口点，比Swift更灵活一些；在数据一致性方面，Swift的数据是最终一致，对海量数据的处理效率要高一些，但是主要面向对数据一致性要求不高但是对数据处理效率要求比较高的对象存储业务，而Ceph是始终跨集群强一致性。在OpenStack中，对象存储服务使用的是Swift，而不是Ceph。
1.4.2 列式存储
组织关系数据库有两种方法：面向行和面向列。面向行的数据库是按记录组织数据的数据库，将与记录相关联的所有数据彼此相邻地保存在内存中。面向行的数据库是组织数据的传统方式，并且仍然为快速存储数据提供了一些关键优势。它们针对有效的读取和写入行进行了优化。常见的面向行的数据库有MySQL和PostgreSQL面向列的数据库是按字段组织数据的数据库，将与字段相关联的所有数据彼此相邻地保存在内存中。列式数据库越来越受欢迎，并为查询数据提供了性能优势。它们针对有效的读取和计算列进行了优化，常见的面向列的数据库有Redshift、BigQuery和Snowflake等。
列式存储（column-oriented storage）并不是一项新技术，最早可以追溯到1983年的论文Cantor。然而，受限于早期的硬件条件和使用场景，主流的事务型数据库（OLTP）大多采用行式存储，直到近几年分析型数据库（OLAP）的兴起，列式存储这一概念又变得流行起来。
面向行的数据库创建了传统的数据库管理系统来存储数据。它们经过优化以读取和写入单行数据，这导致了一系列设计选择，包括具有行存储架构。在行存储或面向行的数据库中，数据是逐行存储的，即一行的第一列将紧挨前一行的最后一列，如表1-4所示。
表1-4 面向行的数据示例
这些数据将按行存储在面向行的数据库中的磁盘上，如图1-11所示。
图1-11 面向行的数据存储底层示意图
这允许数据库快速写入一行，因为写入一行所需要做的就是将另一行附加到数据的末尾。如图1-12所示，如果我们要添加一条新记录：
图1-12 新增一条行数据
我们可以将它附加到当前数据的末尾，如图1-13所示。
图1-13 添加行数据后的变化
面向行的数据库通常用于在线事务处理（OLTP）风格的应用程序，因为它们可以很好地管理对数据库的写入。但是，数据库的另一个用例是分析其中的数据。这些在线分析处理（OLAP）用例需要一个能够支持数据的即席查询的数据库。
在进行临时查询时，有许多不同的数据排序顺序可以提高性能。例如，我们可能希望按日期列出数据，包括升序和降序，我们可能正在寻找有关单个客户的大量数据。
在面向行的数据库中可以创建索引，但很少以多个排序顺序存储数据。但是，在面向列的数据库中，你可以以任意方式存储数据。事实上，除了提高查询性能之外，面向列的数据库还有其他好处。这些不同的排序列被称为投影，它们提高系统容错性，因为数据被存储多次。
面向行的数据库在检索一行或一组行时速度很快，但是在执行聚合时，它会将额外的数据（列）带入内存，这比仅选择要执行聚合的列要慢。此外，面向行的数据库可能需要访问的磁盘数量通常更多。
假设我们想从上表数据中获取年龄总和，为此，我们需要将所有9个数据块加载到内存中，然后提取相关数据进行聚合，这将浪费计算时间。
让我们假设一个磁盘只能容纳足够的数据字节，以便在每个磁盘上存储三列。在面向行的数据库中，表1-4将存储为表1-5。
表1-5 在每个磁盘上存储三列示例
为了得到所有人年龄的总和，计算机需要查看所有三个磁盘以及每个磁盘中的所有三列才能进行此查询。因此我们可以看到，虽然向面向行的数据库中添加数据既快速又容易，但从中获取数据可能需要使用额外的内存和访问多个磁盘。
面向列的DBMS或列式DBMS是一种数据库管理系统（DBMS），它按列而不是按行存储数据表。面向列的DBMS好处包括仅在查询列子集时更有效地访问数据（通过消除读取不相关列的需要），以及更多数据压缩选项。但是，它们插入新数据的效率通常较低。关系数据库管理系统提供表示列和行的二维表的数据。创建数据仓库是为了支持分析数据。这些类型的数据库是读取优化的。在列式或面向列的数据库中，数据的存储方式是使列的每一行与同一列中的其他行相邻。让我们再次查看相同的数据集，看看如何将存储它在面向列的数据库中，如表1-6所示。
表1-6 面向列的数据存储示例
如图1-14所示，一个表一次按行存储一列：
图1-14 列存储示意图
如图1-15所示，如果要添加一条新记录：
图1-15 添加一条新记录
我们必须在数据中导航以便将每一列插入到它应该在的位置，如图1-16所示。
图1-16 列式存储的插入
如果数据存储在单个磁盘上，它将与面向行的数据库存在相同的额外内存问题，因为它需要将所有内容都放入内存。但是，当存储在单独的磁盘上时，面向列的数据库将具有显著优势。
如图1-17所示，如果我们将上面的表格放入同样受限的三列数据磁盘中，它们将像这样存储：
图1-17 列式存储底层示意图
要获得年龄的总和，计算机只需转到一个磁盘（Disk 3）并将其中的所有值相加，不需要拉入额外的内存，它访问的磁盘数量最少。虽然这有点过于简化，但说明通过按列组织数据，需要访问的磁盘数量将减少，并且必须使在内存中保存的额外数据量最小化，这大大提高了计算的整体速度。还有其他方法可以让面向列的数据库获得更高的性能。
涉及硬盘的最昂贵的操作是查找。为了提高整体性能，相关数据的存储方式应尽量减少搜索次数。这被称为参考位置，基本概念出现在许多不同的上下文中。硬盘被组织成一系列固定大小的块，通常足以存储表格的几行。通过组织表的数据使行适合这些块，并将相关的行分组到连续的块中，在许多情况下，需要读取或查找的块的数量以及查找的次数都会被最小化。
面向列的数据库将一列的所有值序列化在一起，然后是下一列的值，以此类推。在这种布局中，任何一列都更紧密地匹配面向行的系统中的索引结构。这可能会导致混淆，从而导致人们错误地认为面向列的存储“实际上只是”在每一列上都有索引的行存储。但是，数据的映射有很大的不同。在面向行的系统中，索引将列值映射到 rowid，而在面向列的系统中，列将 rowid 映射到列值。
面向列的系统是否会更有效地运行在很大程度上取决于自动化的工作负载。检索给定对象（整行）的所有数据的操作速度较慢。面向行的系统可以在单个磁盘读取中检索行，而列式数据库中需要从多个列收集数据的大量磁盘操作。但是，这些整行操作通常很少见。在大多数情况下，只检索有限的数据子集。将数据写入数据库时更是如此，尤其是当数据趋于“稀疏”且包含许多可选列时。为此分区、索引、缓存、视图、OLAP多维数据集和事务系统（例如预写日志记录或多版本并发控制）都极大地影响了任一系统的物理组织。也就是说，以在线事务处理（OLTP） 为重点的 RDBMS 系统更加面向行，而以在线分析处理（OLAP） 为重点的系统是面向行和面向列的平衡。
传统OLTP数据库通常采用行式存储。所有的列依次排列构成一行，以行为单位存储，再配合以B+树或SS-Table作为索引，就能快速通过主键找到相应的行数据。
行式存储对于OLTP场景是很合适的。大多数操作都以实体（entity）为单位，即大多为增删改查一整行记录，显然把一行数据存在物理上相邻的位置是很好的选择。
然而，对于OLAP场景，一个典型的查询需要遍历整个表，进行分组、排序、聚合等操作，这样一来按行存储的优势就不复存在了。更糟糕的是，分析型SQL常常不会用到所有的列，而仅仅对其中某些列做运算，因此一行中那些无关的列也不得不参与扫描。
面向行和面向列的数据库之间的比较通常与给定工作负载的硬盘访问效率有关，因为与计算机中的其他瓶颈相比，查找时间非常长。例如，典型的串行ATA（SATA）硬盘驱动器的平均寻道时间为16～22ms，而英特尔酷睿i7处理器上的DRAM访问平均需要60ns，两者相差近400 000倍。显然，磁盘访问速度是处理大数据的主要瓶颈。列式数据库通过减少需要从磁盘读取的数据量来提高性能，既可以有效地压缩相似的列式数据，也可以只读取查询所需的数据。
在实践中，列式数据库非常适合OLAP类工作负载（例如，数据仓库），这些工作负载通常涉及对所有数据（可能是PB级）的高度复杂的查询。但是，必须做一些工作才能将数据写入列式数据库。事务（INSERT）必须分成列并在存储时进行压缩，使其不太适合OLTP工作负载。面向行的数据库非常适合OLTP这种负载更重的交互式事务的工作负载。例如，当数据位于单个位置（最小化磁盘寻道）时，从单行检索所有数据效率更高，如在面向行的体系结构中。然而，面向列的系统已被开发为能够同时进行OLTP和OLAP操作的混合体。这种面向列的系统所面临的一些OLTP约束是使用（以及其他质量）内存数据存储来调节的。
显然，列式存储对于OLTP不友好，一行数据的写入需要同时修改多个列，但对 OLAP场景有着很大的优势：当查询语句只涉及部分列时，只需要扫描相关的列即可，每一列的数据都是相同类型的，彼此间相关性更大，对列数据压缩的效率较高。
列数据是统一类型的，因此，在面向列的数据中存在一些在面向行的数据中不可用的存储大小优化的机会。例如，许多流行的现代压缩方案，如LZW或游程编码，利用相邻数据的相似性进行压缩。临床数据中常见的缺失值和重复值可以用两位标记表示。
为了改进压缩，对行进行排序也有帮助。例如，使用位图索引，排序可以将压缩提高一个数量级。列压缩以降低检索效率为代价来减少磁盘空间。实现的相邻压缩越大，随机访问可能变得越困难，因为数据可能需要解压缩才能读取。因此，有时会通过最小化对压缩数据的访问需求来完善面向列的体系结构设计。
传统关系数据库主要面向在线事务处理应用，这些应用需要在频繁的小规模更新时仍可以保证很好的性能，因此行式存储成为主流的记录组织格式。而对于在线分析处理和数据挖掘类查询密集型应用，访问模式完全不同，这类应用通常只访问记录中少量属性，通过对大量数据进行计算后得到汇总结果集。如果使用行式存储组织数据，即使只访问少数几列，也需要读取记录中的所有数据，大量的I/O只能产生少量有效数据。因此对于在线分析处理类应用，产生了两种应对的方法，即预计算和垂直分区方法。预计算方法将预先计算的结果存放于立方体或物化视图中，这种方法可以对汇总的结果进行切片、下钻和上卷等操作。但这种方法的缺点在于只能加速模式已知的查询，而对灵活的即席查询并不适用，另外，还需要考虑事实表和预计算结果集之间的同步问题。而垂直分区方法则是将数据按列组织，由于需要查询的属性值集中存放在连续的数据块中，因此对于合计、分组、排序、映射等操作，通过较少的访问即可获取更多的有效数据，这极大提高了数据分析类应用的效率。列式存储提高了I/O效率，通过将列式存储完全加载到内存则进一步避免了磁盘I/O访问，并且可以充分发挥多处理器多核的并行处理优势，对于即席查询也可以获得很好的性能。
总的来说，列式存储的优势一方面体现在存储上能节约空间、减少I/O，另一方面依靠列式数据结构做了计算上的优化。