「书籍阅读」数据密集型应用系统设计

可靠、可拓展与可维护的应用系统

应用系统的组成模块：

数据库：存储数据
高速缓存：缓存复杂或操作代价昂贵的结果
索引：用户可以按关键字搜索并支持各种过滤
流式处理：持续发送消息至另一进程(异步)
批处理：定期处理大量的累积数据

数据软件系统重视的三个问题：

可靠性(Reliability)：硬件、软件故障、人为失误等，系统仍然可以正常运转。
可拓展性(Scalability)：数据量和复杂度是可变的
可维护性(Maintainability)：新人员可以参与到系统开发和运维，维护现有功能或适配新的场景，系统都能够高效运作。

可靠性

可能出错的事情称为错误(faults)或故障，系统可应对错误称为容错(fault-tolerant)。与失效(failure)不完全一致，前者表示与预期目的偏离，后者表示整个系统完全停止工作。

硬件故障: 硬盘崩溃、内存崩溃、电网停电、误拔网线。

软件错误：软件错误导致当输入特定值时应用服务器崩溃；应用程序使用某些共享资源时不行失控跑飞；依赖的服务变慢甚至无响应；小组件故障触发相关组件故障。设计时需要考虑很多细节，认真检查依赖的假设条件与系统之间的交互，进行全面测试，进程隔离，允许进程崩溃并自动重启。

人为失误：以最小出错的方式来设计系统；想办法分离出最容易出错的地方；充分测试；设置详细而清晰的监控子系统，包括性能指标和错误率。

可拓展性

这更多的讨论的是：如果系统以某种方式增长，应对增长的方式有哪些

负载：负载可以用称为负载参数的若干数字来描述，比如Web服务器的每秒请求处理次数，数据库中写入的比例，缓存命中率等等。

性能：在批处理系统中，通常用吞吐量(throughput)，在在线系统更看重服务响应时间(response time)。服务响应时间通常使用百分位数表示(对收集到的响应时间进行排序，然后取第百分位的位置，作为结果，表示有前百分之多少低于这个时间。)通常使用p50(中位数)，p95，p99以及p999来表示。

延迟与响应时间：

延迟：请求花费在处理上的时间

相应时间：除了处理时间外，还包括来回网络延迟和各种排队延迟。

可维护性

这要求我们关注软件系统的三个设计原则：

可运维性：方便运营团队来保持系统平稳运行
简单性：简化系统复杂性，使新工程师能够轻松理解系统
可演化性：后续工程师能够轻松对系统进行改进，并根据需求变化将其是被到非典型场景中

可运维性：监视系统的健康状况，并在异常时快速恢复；追踪问题的原因；保持软件和平台至最新状态；了解不同系统如何相互影响；建立用于部署、配置管理等良好的时间规范和工具包；执行复杂的维护任务；当配置更改时，维护系统的安全稳健；指定流程来规范操作行为；保持相关知识的传承；

简化性：消除意外复杂性(比如状态空间膨胀，模块耦合，令人纠结的相互依赖关系，不一致的命名和术语等)的最好手段之一就是抽象。好的抽象设计可以隐藏大量的实现细节，并对外提供干净易懂的接口。

数据模型与查询语言

关系模型与文档模型

关系数据库的核心在于商业数据处理，主要包括事物处理和批处理。

NoSQL

NoSQL的含义是：不仅仅是SQL

其驱动因素包括：

比关系数据库更好的拓展性，包括支持超大数据集或超高写入吞吐量
普通偏爱免费和开源软件
关系模型不能很好得支持一些特定的查询操作
渴望更具有动态和表达能里的数据模型。

混合持久化：将关系数据库与各种非关系数据库存储一起使用

网络模型

网络模型由一个称为数据系统语言会议(Conference on Data System Languages，CODASYL)的委员会进行标准化的，并由多个不同的数据库厂商实施，它也被称为CODASYL模型。

在层次模型的树结构中，每个记录只有一个父节点，而在网络模型中，一个记录可以有多个父节点。在网络模型中，访问记录的唯一方法是选择一条始于根记录的路径，并沿着相关链接一次访问，这条链接链条被称为访问路径。

网络模型的最大问题在于它们使查询和更新数据库变得异常复杂而没有灵活性。

关系模型

关系模型定义了所有数据的格式：关系(表)只是元组(行)的集合。

在关系数据库中，查询优化器自动决定以何种顺序执行查询，以及使用哪些索引。其与访问路径的最大区别在于，关系数据库中的查询选择是查询优化自动生成的。关系模型的核心思想是：只需要构建一次查询优化器，然后使用该数据库的所有应用程序都可以从中受益。

文档数据库的比较

文档数据库是某种方式的层次结构：即在其父记录中保存了嵌套记录，而不是存储在单独的表中。

在表示多对一和多对多的关系时，关系数据库和文档数据库并没有根本的不同：在两种情况下，相关项都由唯一的标识符引用，该表示在关系模型中称为外键，在文档模型中称为文档引用。

数据库查询语言

很多常用的编程语言都是命令式的，比如在动物列表中找到鲨鱼

function getSharks(){
    var sharks = [];
    for (var i = 0;i<animal.length;i++)
        if(animals[i].family==="Sharks")
            sharks.push(animals[i]);
}

而SQL则可以表示为

1	SELECT * FROM animals WHERE family = 'Sharks';

命令式语言(javascript的代码)会告诉计算机待定顺序执行的某些操作。声明式语言(SQL)则只需指定所需的数据模式，结果满足什么条件，以及如何转换数据。

声明式查询语言很有吸引力，它比命令式API更加简介和容易使用，此外，声明式语言通常适合于并行执行。

Web上的声明式查询：举个例子就是在CSS中针对特定的类别写上相应的样式，然后在HTML语言的标签中加上对应的类别的类名，从而实现样式映射。但如果不是使用CSS而是使用XSL的话，也是使用XPath表达式来选中HTML中的对应标签，然后加上对应的样式。如果非得使用命令式的方法的话，可以直接使用JavaScrpit中的对象模型(Document Object Module, DOM)API，具体流程就是使用DOM的选择器API选出对应的标签，再手动加入对应的样式。

MapReduce查询：MapReduce既不是声明式查询语言，也不是一个完全命令式的查询API，而是介于两者之间：查询的逻辑用代码片段来表示，这些代码片段可以被处理框架重复地调用。主要基于map和reduce函数。map函数主要是将数据处理成键值对的形式，然后reduce函数主要是对同一个键的不同值进行相应的处理。但map和reduce函数对于可执行的操作有所限制，他们必须是纯函数，这意味着只能用传递进去的数据作为输入，而不能执行额外的数据库查询，也不能有任何副作用。

图状数据库模型

图由顶点和边构成。常见的图结构有：社交网络，Web图，公路或铁路网等。图提供了单个数据存储区中保存完全不同类型对象的一致性方式。常见的三种声明式图查询语言：Cypher，SPARQL和Datalog。

属性图

$图\begin{cases} 顶点\begin{cases} 唯一标识符\\ 出边的集合\\ 入边的集合\\ 属性的集合(键值对) \end{cases} \\ 边\begin{cases} 唯一标识符\\ 边开始的顶点(尾部顶点)\\ 边结束的顶点(头部顶点)\\ 描述两个顶点之间关系类型的标签\\ 属性的集合(键值对) \end{cases} \end{cases}$

举个例子：

任何顶点都可以连接到其他任何顶点。
给定某个顶点，可以高效地得到它的所有入边和出边，从而遍历图。
通过对不同类型的关系使用不同的标签，可以在单个图中存储多钟不同类型的信息，同时仍然保持正解的数据模型。

Cypher查询语言

Cypther是一种用于属性图的声明式查询语言。

举个例子：

(Idaho)-[:WITHIN]->(USA)创建了一个类别为WITHIN的边，其中节点Idaho为尾节点，USA为头节点。

首先是根据出生边(BORN_IN)和地区具体信息边(WITHIN)搜索出出生在美国的人，然后根据居住边(LIVES_IN)和地区具体信息边(WITHIN)搜索出现在居住在欧洲的人。

三元组存储

三元组的主体相当于图中的顶点，客体则是下面两种情况之一：

原始数据类型中的值，比如字符串或数字
图的另一个顶点

举个例子：

_:表示节点对应的名称，:name通常表示其属性值，:Person指的是节点的类型。

SPARQL查询语言

举个例子：

从personName中进行筛选(SELECT所在为第一行)，不管叫什么名字(第二行)；出生在任意节点，但这些节点所属地的name属性必须是没过(第三行)；居住在任意节点，但这些节点的所属地的name属性必须是欧洲(第四行)，满足上面三个约束的交集就是查询的结果。

其和Cypher很像，下面两个表达式是等价的

(person)-[:BORN_IN]->()-[:WITHIN*o..]->(location) # Cypher

?person :bornIn / :within* ?location. # SPARQL

数据存储与检索

数据库核心：数据结构

数据库最简单的实现方式如下：

#!/bin/bash

db_set(){
	echo "$1,$2" >> database
}

db_get(){
	grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

上面实现了一个key-value的存储方式，db_set key1 value1的操作就是向database文件中追加一个键值对key1,value1，然后db_get key的操作就是输入对应的键，然后在database文件中进行匹配，然后为了使用最新的结果，通常使用tail -n 1来取出文件中的最后一个匹配项。

许多数据库内部都使用日志(log)，日志是一个仅支持追加式更新的数据文件。

日志通常指的是应用程序的运行输出日志，记录发生了什么事情。书本中的日志表示一个仅能追加的记录序列集合，他可能是人类不可读的，可能是二进制格式而只能被其他程序来读取。

我们可以假设如果database内容很多，那么使用db_get来搜索对应的内容时，要搜索全部的文件，这样时间开销就很大，于是需要新的数据结构——索引，通过它来高效地查找数据库中特定的值。索引是基于原始数据派生而来的额外数据结构，其不影响数据库中的内容，只会影响查询性能。而通常维护额外的数据结构，在数据发生变动时，相应的索引结构也会跟着修改，这就意味着索引的存在可能会对数据的写入存在一定的影响。因此，适当的索引可以加速读取查询，但每个索引都会减慢写速度。

哈希索引

假设数据存储全部采用追加式文件组成，那么最简单的索引策略就是：保存内存中的hash map，把每一个键一一映射到数据文件中特定的字节偏移量，这样就可以找到每一个值的位置了。同样的，在插入时，也要更新插入数据的hash值和对应的偏移量。

如何避免存值可能造成的最终用尽磁盘空间？将日志分解成一定大小的段，当文件到达一定大小时就关闭它，并将后续写入到新的段文件中。然后就可以在这些段中执行压缩(丢掉重复的键，只保留最新的结果)，如下图：

当然，也可以在执行压缩的时候将多个段合并在一起，如下图：

端在写入后不会再进行修改，所以合并的段会被写入一个新的文件中，在合并和压缩运行时，仍然可以使用旧的段文件继续正常的读取和写请求，当合并过程完成后，将读取请求切换到新的合并端上，而旧的段文件可以安全删除。每个段现在都有自己的内存哈希表，将键映射到文件的偏移量。为了找到键的值，首先检查最新的段hash map，如果键不存在，检查第二最新的段，以此类推。

但是上面的想法在实际使用过程中仍然存在一定的问题：

文件格式：CSV显然不是最好的选择，最好的选择应该是使用二进制格式。
删除记录：如果要删除键和相关的值，必须在数据文件中追加一个特殊的删除记录，当合并日志时，一旦发现这个标记，则会丢弃这个已经删除键的所有值
崩溃恢复：数据库重启后，内存中的hash map就会丢失。这需要从头到尾读取整个段文件，然后记录每个键最新值的偏移量，来回复每个段的hash map。但如果分段文件很大，重新恢复的时间就会比较长。
部分写入记录：数据库随时可能崩溃，包括将记录助教到日志的过程中。
并发控制：由于写入以严格的先后顺序追加到日志中，通常的实现选择是只有一个写线程。

哈希索引存在的局限性：

当哈希表很大时，内存里装不下，只能在磁盘上进行管理，这就会引入IO时间，性能下降。
区间查询效率不高，当给定范围查询时，只能按照逐个键遍历，然后筛选的方式进行。

SSTables

与之前的简单想法相比，排序字符串表(SSTable)就是添加了一个规则：要求key-value对的顺序按键排序。其要求每个键在合并的段文件中只能出现一次，其具有以下优点：

合并段更加简单高校，即使文件大于可用内存。比较每个文件的第一个键，把最小的键拷贝到输出文件中，从而产生新的按键排序的合并文件，即使遇到键相同的情况，也能够根据哪一个是最新的进行写入。
在文件中查找特定键时，不在需要在内存中保存所有键的索引。根据有序性，可以根据偏移量进一步确定搜索键的位置。
读请求往往需要扫描请求范围内的多个key-value对，可以考虑将这些记录保存到一个块中并在写磁盘之前将其压缩。稀疏内存索引的每个条目指向压缩块的开头。

内存排序的实现主要还是使用红黑树或AVL树，基本工作流程如下：

写入时，将其添加到内存中的平衡树数据结构中，其被称为内存表。
当内存大于某个阈值时，将其作为SSTable文件写入磁盘中。新的SSTable文件成为数据的最新部分。当SSTable写磁盘的同时，写入可以继续添加到一个新的内存表实例中。
为了处理读请求，首先尝试在内存表中找键，然后是最新的磁盘段文件，接下来是次新的磁盘段文件，以此类推。
后台进程周期性地执行段合并与压缩过程，以合并多个段文件，并丢弃那些已经被覆盖或删除的值。

LSM-Tree

基于合并和压缩排序文件原理的存储引擎通常被称为LSM存储引擎。在确定键不存在之前，会检查内存表，一直检查到最久的文件，这使得LSM-Tree算法很慢。为了避免这种情况，会使用额外的布隆过滤器(内存高效的数据结构，用于近似计算集合的内容。如果数据库中不存在某个键，就会很快告诉你结果)。

SSTable压缩和合并的方式——大小分级和分层压缩。在大小分级的压缩中，新而小的SSTable被连续合并到旧而大的SSTable中。在分层压缩中，键的方位分裂成更多的SSTable，旧的会移动到对应的层级中。

B-tree

B-tree仍然是几乎所有关系数据库中的标准索引实现，其保留键值排序树，这样可以实现高效的键值查找和区间查询。其会将数据库分解成固定大小的块或页，传统大小为4KB(有时更大)。每一页都会有对应的标识，指向磁盘的地址。下图就是一个简单的B-tree索引：

B-tree的优化

在恢复时，不采用覆写的方案，而是采用复制的方案维护预写日志(在修改磁盘文件时，要先写入预写日志中再进行，WAL)，然后写好对应的文件后直接修改树的索引位置即可
保存键的缩略信息，节省页空间
尝试对树进行布局，以便相邻叶子可以按顺序保存在磁盘上
添加额外的指针到树中，比如向左向右的指针引用其兄弟页
使用B-tree的变体，比如分形树

B-tree与LSM-tree对比

根据经验：LSM-tree通常对于写入更快，而B-tree被认为对于读取更快。

LSM-tree的优点：B-tree索引必须先写入预写日志，再写入树的页本身，即使该页中只有几个字节更改，也必须承受整个页面的开销。LSM-tree能够承受比B-tree更高的写入吞吐量，一方面其具有较低的写放大，另一方面其以顺序方式写入紧凑的SSTable文件，而不是重写树中的多个页(磁盘顺序写比随机写要快得多)。LSM-tree可以支持更好地压缩。

LSM-tree的缺点：

压缩过程有时会干扰正在进行的读写操作。
高写入吞吐量时，压缩还存在一个问题：磁盘的有限写入带宽需要在初始写入(记录并刷新内存表到磁盘)和后台运行的压缩线程之间所共享。
当吞吐量和压缩没有仔细配置，高吞吐量的情况机会导致压缩的带宽减小，并且未完成的压缩会产生更多的段，使得压缩过程要查看的段更多，读取速度降低。

B-tree的优点：每个键都恰好唯一对应于索引中的某个位置，在许多关系型数据库中，事务隔离是通过键范围上的锁来实现的，并且在B-tree索引中，这些锁可以直接定义到树中。

其他索引结构

在索引中存储值：

聚集索引：索引行直接存储在索引中
非聚集索引：仅存储索引中的数据的引用

多列索引（级联索引）：将一列追加到另一列，将几个字段简单地组合成一个键。

全文搜索与模糊索引：支持对一个单词的所有同义词进行查询，并忽略单词语法上的变体。

事务处理与分析处理

交互式的数据存储事务（博客评论，游戏动作，通讯录像）被统称为在线事务处理(OLTP)。

由业务分析师编写的查询事务以形成有助于公司管理层更好决策的报告的处理，称为在线分析处理(OLAP)。

属性	事务处理系统(OLTP)	分析系统(OLAP)
主要读特征	基于键，每次查询返回少量的记录	对大量记录进行汇总
主要写特征	随机访问，低延迟写入用户的输入	批量导入(ETL)或事件流
典型使用场景	终端用户，通过网络应用程序	内部分析师，为决策提供支持
数据表征	最新的数据状态（当前时间点）	随着时间而变化的所有事件历史
数据规模	GB到TB	TB到PB

数据仓库

公司放弃使用OLTP系统分析目的，而是在单独的数据库上进行分析(避免分析师的查询影响正常业务)，这个单独的数据库被称为数据仓库。数据仓库包含公司所有的OLTP系统的只读副本。数据导入数据仓库的过程称为提取-转化-加载(ETL)，如下图所示：

星型模式：模式的中心是事实表，记录了每一个具体的动作。然后其他具体信息，由不同的表(维度表)进行拓展。（具体就是，以一个事件作为item，其他细节通过外键进行详细连接）举个购物的例子(如下图)：

雪花模式：就是在星型模式的维度表进一步细分成多个子空间。一般在使用过程中更多地使用星型模式。

列式存储

面向列存储的想法很简单：将每列中的所有值存储在一起。

列压缩

我们都知道一列中不同元素的数量m通常是小于等于行的数量n的。然后对于某一列如果有m个不同的值，将其作为行标号，然后原始行数据作为列的标号，构建一个mxn的零矩阵。这时候如果原始数据中第i行的列值是j，那么在mxn矩阵中的(j,i)位置被记录为1。然后构建好矩阵后，对于每一个列值，用值:0的个数，1的个数，0的个数，1的个数...表示。然后有m个值就有m个这样的格式，将其存储在列中，从而实现数据压缩，举个例子：

列存储中的排序

单独对每一列排序是没有意义的，因为列存储中每一行的元素都是对应的，如果对每一列都进行排序，会导致列存储无法还原出行的原始结构。列存储中的排序实际上是先对行的结构进行排序(先按第一列排序，如果第一列相同就按照第二列排序，以此类推)，然后再将其转化成列存储的形式。这样从某种程度上还是有益于列压缩的，因为经过排序之后，前几列中相同数字彼此接近，使得用于表示0和1个数使用的数字变少，但是到后面几列，几乎是呈随机分布，但是由于前面已经经过了压缩，总体上来讲压缩性能还是有所提高的。当然，还有一种列排序存储的说法，就是在对数据进行冗余备份时，采用按照不同列进行排序的方式进行多个备份，就是说，多个不同列排序的结果作为冗余备份。

列存储的写操作

列压缩可以使得列存储占用空间更小，但是这也就意味着写操作更加困难，如果要插入一行，就不得不重新写如这些东西。现在的解决方案是，先将排序的原始数据存放在内存缓存中，当达到一个阈值后就写入磁盘，这时候如果没有达到阈值，写入时直接添加到内存缓存中即可，当达到阈值后，就将他们与磁盘上的列文件合并，并批量写入新文件中。