从抽象层次上详细讲述各种数据存储，包括关系型数据库、NoSQL、大数据存储、流处理系统等等，由浅入深、拨丝抽茧

内部机制、各种数据存储的利弊、如何取舍，读下来有一种豁然开朗的感受

现在的互联网应用，本质上就是一个数据系统：一个浅应用层包裹着的复杂的数据系统，理解数据系统的运作非常必要

作者是少有的从工业界干到学术界的牛人，知识面广得惊人，也善于举一反三，知识之间互相关联

提出问题 -> 解决方案 -> 这个方案的长处短处 -> 发散到其它方案

一、可靠、可扩展、可维护的数据系统

多数应用程序都是数据密集型的，非计算密集型(瓶颈不在CPU)，极待解决的问题是海量的数据、数据结构之间的复杂性，应用的性能

经常打交道的数据系统：

存储数据，以便它们或其他应用程序稍后再找到它（数据库）
记住昂贵操作的结果，以加快读取速度（缓存）
允许用户按关键字搜索数据或通过各种方式过滤数据（搜索索引）
将消息发送到另一个进程，异步处理（流处理）
周期性地压缩大量的累积数据（批处理）

应用程序的绝大工作就是将这些数据系统进行组合，然后添加我们的运行逻辑，但是如何更加合理的整合这些数据系统，对我们来说仍然是一个值得学习和思考的问题

缓存系统 Redis、数据队列 Kafka 都可以支持数据落地来存储消息，很多应用场合可以替代传统的RDBMS

更加深刻的理解这些数据系统，来更好的权衡架构设计，是一门很精深的课题

多种数据系统构成的应用程序，随着数据量和数据逻辑的复杂，就成为了一个数据密集型的应用

三原则

可靠性

具有容错性（硬件或软件故障，甚至是人为错误），仍正常工作（期望的性能水平上执行正确的功能）
可扩展性

系统增长（在数据量、流量或复杂度），有合理的方法来处理这种增长
可维护性

随着时间的推移，许多不同的人将致力改善数据系统（既保持当前的行为，并使系统适应新的环境），他们都应该能够卓有成效地工作

可靠性

硬件故障 硬盘，内存，停电，拔网线 …

解决方案：

软件与硬件冗余，来确保硬件的故障不会演变为系统的故障
人为错误

人不可靠，经常犯错。从驾驶技术的演变就可以看出来，人为疏失会带来巨大的灾难

解决方案：

最小化错误机会的方式设计系统。例如，精心设计的抽象，API和管理界面可以很容易地做“正确的事情”，阻止“错误的事情”

人们犯最多错误的地方和那些可能导致失败的地方解耦

全面测试，单元、集成、手动测试

快速和容易地从人为错误中恢复，尽量减少失败影响。如，快速配置回滚，逐步上线新代码（错误只影响一小部分用户），提供工具重新计算数据（如果原来旧的计算是不正确的）

可扩展性

系统未来工作不可靠，常见原因是负载增加：并发或用户量增加

“系统以特定的方式增长，应对增长的选择是什么？” “怎样才能增加计算资源来处理额外的负载？”

描述负载

参数选择取决于系统体系结构，如：

Web server qps
db 读写比
活跃用户量
缓存命中率

描述性能

描述完系统负载，讨论负载增加时发生的情况，两方面：

加负载并保持资源（CPU、内存、网络带宽等）不变时，系统性能如何受影响？
增加负载时，如果希望保持性能不变，需要增加多少资源？

描述性能的尺子：

平均响应时间：所有请求时间/请求数 n,的平均值，然而这不是很好的指标，不告诉你有多少用户真正体验了延迟
百分比响应时间：所有响应时间从最快到最慢排序，中间值是中间点：平均200毫秒，意味着一半请求少于200毫秒，另一半请求比200毫秒要长
高百分比的响应时间：P95，P99，和p999来参考响应时间的阈值

负载与性能情况很重要，有时系统瓶颈由少数极端情况引起

Twitter例子(2012年11月16日数据)

两个主要操作：

发Tweet 用户可以发布一个Tweet给他们的订阅者（平均4.6k请求/秒，峰值超过1.2万请求/秒）
获取Tweet 用户可以查看他们关注者发布Tweet（300K请求/秒）

Twitter扩展性挑战主要在Tweet数量，在每个用户都有很多订阅者，每个用户也有很多关注者

执行这两种操作大致是两种方法：

1、发推只插到推文集合

请求关注者Tweet时，查找关注的所有人，找到每个用户的所有Tweet，按时间合并排序

SELECT tweets.*, users.* FROM tweets 
	JOIN users ON tweets.sender_id = users.id
    JOIN follows ON follows.followee_id = users.id 
    WHERE follows.follower_id = current_user

2、每用户订阅的Tweet一个缓存

发推时，查找所有关注该用户的人，将新的Tweet推送到他们的缓存中

读取Tweet列表是很划算的，因为它的结果提前计算好了

更合适Tweet的发布，发Tweet的写比读低两个数量级，最好在写时做更多的工作，而不是在读时

但方法2 不适用于有大量关注者的账号，3000W粉丝，一次发Tweet产生的写操作可能是巨大的

所以要将这两种方法混合。多数用户的推文发布时推到缓存中

（这例子很精炼的描述了架构设计的妥协与精妙，依据业务特点，最大优化数据系统的性能）

怎么扩展

放大（垂直缩放，移动到更强大的机器）和缩放（横向缩放，在多台更小的机器上分配负载）之间的二选一

好的架构通常涉及到一种实用的混合方法：例如，使用几个功能强大的机器仍然比大量的小型虚拟机更简单、更便宜

无节制的分布式会给系统混入复杂度，这是软件工程中危险的地方，虽然在多台机器上分发无状态服务相当简单，但将有状态数据系统从单个节点转移到分布式安装程序会带来许多额外的复杂性

没有这样的东西，一个通用的，适合所有的应用的可伸缩的架构

可维护性

（维护别人留下的烂摊子真的是很痛苦的事情，文档，注释真的是重中之重！！！）

二、数据模型和查询语言

数据模型的分层

每一层提供一个干净的数据模型，隐藏底层的复杂性。这样抽象来允许不同的人群有效地协同工作

每个数据模型都包含了如何使用它的假设。用法是否容易，不支持什么操作；操作性能；数据转换自然还是笨拙

数据模型对上层的应用程序能做什么和不能做什么有着深刻的影响，选择适合于应用程序的数据模型十分重要

数据模型

关系型、nosql

某些场景nosql提供了

更大数据容量、更高的读写吞吐
专有查询
数据模型更灵活

多数程序是面向对象编程语言，导致对SQL数据模型灵活性的批评：

数据存储在关系表中，代码在对象与表、行和列的数据库模型之间需要一个笨拙的转换层（ORM）

LinkedIn，使用不同数据模型的差异

传统SQL模型最常见的规范化表示是将位置、教育和联系人放单独表，外键表引用到用户表

多表间的依赖关系复杂了应用程序的编写

JSON模型减少了代码和存储层间匹配问题，更加灵活。相比多表模式具有更好的局部性。如教育或职业信息，多表模型之中要执行多次查询（通过user_id查询每个表）或执行一个多表连接的操作

JSON数据模型一次查询就足够完成

region_id和industry_id 用ID 优点

可以统一更新，减少写开销，不一致性的风险
可以本地化来适应不同的语言
区域和行业的列表可能很小，而且变化缓慢，可以缓存在内存

文档型数据模型的灵活性

应用希望改数据格式情况，**灵活性显得至关重要

db 用户全名存在一个字段，现在想要分别存储名称和姓氏

文档数据库中，只需要开始使用新字段编写新文档，并在应用程序中有代码处理旧文档读取时的情况
```
if (user && user.name && !user.first_name) {
   user.first_name = user.name.split(" ")[0];
}
```
- 关系型数据库模式中，通常修改模型：

    ALTER TABLE users ADD COLUMN first_name text;
    UPDATE users SET first_name = split_part(name, ' ', 1); 
    UPDATE users SET first_name = substring_index(name, ' ', 1);

大表每一行都要重写，性能慢

小结

文档型数据模型主要优点是模式灵活性，局部性更好的性能

程序经常访问整个文档时具有更好的性能优势。特定应用程序，更接近应用程序所使用的数据结构

关系型数据库（mysql 5.7）也开始引入JSON支持,mongo 4 也引入事务,混合型的数据模型或许会是数据库发展的方向

数据查询语言

用SQL表达的逻辑同样可以用程序设计语言去表达，为何还需要多此一举的使用另一种方式去表达数据模型？

当然可以直接使用程序设计语言来和数据交互。（如：Mongo用Js作为原生的交互语言）

但多数直接使用的程序设计语言是命令式语言，而SQL这种代数关系声明式的查询语言会有一些更贴合数据模型的优点

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

select * from animals where family='sharks';

命令式语言告一行一行单步执行，评估条件，更新变量，并决定是否再循环一次

SQL关系代数声明式查询语言中，只需指定想要的数据的模式，结果必须满足什么条件，以及如何转换数据（排序、分组和聚合），而不是具体的实现流程

dbms的查询优化器决定哪些索引以及哪些连接方法可以使用，以及执行查询的各个部分的顺序

声明式查询语言通常比命令式语言的API更简洁，更易于使用，隐藏了数据库引擎的实现细节，使dbms可以在不需要对查询进行任何更改的情况下引入性能改进

但SQL功能有限，灵活性受限制

声明式语言只指定结果的模式，而不是用于确定结果的算法

总结

不同数据模型都被广泛使用，各自的领域都很好

一个模型可以用另一个模型来模拟，但结果往往很笨拙

三、存储与索引

kv

#!/bin/bash                                                                                                                           

# storage functions
db_set () {
  echo "$1,$2" >> db
}

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

# main flow
db_set name dd
db_set age 30
db_set name zzj
db_set age 27
db_get name
db_get age

更新 kv ，不会覆盖旧版本，但 tail -n 1 读取最新键值对

真正的 dbms 需要处理更多的问题（并发控制、回收磁盘空间、日志不能永久增长、处理错误和部分写），但基本设计思路和原则是相同的

db_get 算法定义中，查找时间复杂度是O（n）

有效查，需要不同的数据结构：索引

索引

从原始数据派生出来的附加结构

添加和删除索引时，不影响数据存储的内容，只影响查询性能。但维护额外的结构会导致开销(每次写入数据时也需要更新索引)

哈希索引

比如内存哈希映射，每一个键映射到数据文件中偏移量

插入和更新都向文件append，避免耗尽磁盘空间

后台线程压缩，扔掉重复的键，只保键的最新更新，合并

操作进行时用旧文件提供读写，操作完用新合并完的文件，删旧文件

缺点

内存有限
范围查询性能

SSTable(Sorted String Table)

要求按键来排序。似乎破坏了顺序写的性能，但大大提高维护数据以及索引结构的效率

合并既简单又高效，用简单的归并排序算法
利用键有序特点,不需内存索引所有键，只要部分
分组压缩，省存储与减少I/O

写入的键值对有序在内存中如红黑树或AVL树

使用SSTable时，内存维护一个MemTable数据结构，到阀值时，MemTable作新的SSTable序列化到磁盘

后台线程不断压缩删除旧的SSTable，两次写一次是在内存，一次顺序的磁盘写，可以支持非常高的写入吞吐量

Cassandra**，HBase，**LevelDB

B Tree

MySQL，Oracle，MongoDB大量应用

哈希索引结构将数据分解成可变大小的段

树型索引将数据分成固定大小的块或页，每次读写基于页的大小。更接近于底层硬件

B树键值也排序，既允许高效值查询也允许高效范围查询

保证 N 个键总是有深度的O（log n）树，大多数数据都可以放入到一个三或四层的B树之中，（4页的四级树，分支系数500，可存256TB）

基本写操作覆盖旧数据，不改变页的位置

B树索引并发控制相对复杂，多线程访问要用锁保护树的数据结构（也可Copy on Write来快照隔离）而哈希索引结构的压缩，合并则不会影响查询，写入等操作

小结

树型索引对于很多的工作负载提供始终如一的良好性能

用什么索引需要对业务逻辑有更深层次的理解

OLTP、OLAP

从OLTP提取（周期性或持续不断的更新），将提取的数据的结构转为易于分析的结构，然后加载到数据仓库（Extract-Transform-Load）

OLAP 存储索引结构

列式存储

四、编码

Apache Avro，Facebook Thrift Google Protocolbuf

文本编码

1、内存中数据保存在对象、结构、列表、数组、哈希表、树、等。这些数据结构在内存之中被优化为CPU可以高效访问和操作的结构

2、写入文件或者网络发送时，要编码成某种形式的字节序列（如 JSON）

Java的java.io.Serializable , Ruby的Marshal, Python的pickle

编程语言内置的库存在一些深层次的问题

异构语言交互性、java commons collections/jackson等序列化bug,内置序列化糟糕的性能和臃肿的编码

XML描述十分精准（xsd schema），但过于冗长

JSON流行主要归功于 Web浏览器内置支持和相对于XML的简单性

CSV与语言无关，功能不强

XML/CSV不能区分恰好由数字组成的数字和字符串

JSON区分字符串和数字，但不区分整数和浮点数，也不能确认精度

JSON与XML为不支持二进制字符串（字节序列没有字符编码)

二进制编码

{
	"username":"Martin",
	"favoriteNumber:1337,
	"interests":["daydreaming","hacking"]
}

MessagePack

81> 66 字节，丧失可读性的保障

Thrift

需要 IDL
```
struct Person {
1: required string userName,
2: optional i64 favoriteNumber,
3:optional list<string> interests
}
```
两种二进制编码格式，Binary和Compact

比MessagePack省去字段名等信息，用字段标记（1,2和3）

Compact 字段类型和标记号打成一个字节，较大的数字使用更多字节
Protocolbuf

只有一个二进制编码格式，与Thrift的Compact格式大同小异

Avro

发源于Hadoop，作为Thrift的替换方案存在

没有标识字段或数据类型。

读取与写入数据的代码使用完全相同的模式，二进制数据才能被正确地解码

五、副本

如何去管理和副本，会遇到的各种问题

副本使用场景

位置接近用户，减少延迟（Cache，CDN）
提高可用性（GFS三副本）
通过扩展性增加读取吞吐量（ZooKeeper的Observer）

副本管理困难在于对副本数据的修改琐碎的问题

副本复制时要考虑许多权衡，使用同步还是异步复制，如何处理失效的副本？

Leader-Follower机制

PG、MySQL、Oracle Data Guard 、SQL Server

MongoDB，Kafka，RabbitMQ

同/异步复制

同步复制有延迟

异步复制响应快（mysql只是主写了binlog就返回），但会延迟，或Leader失败且不可恢复，尚未复制到Follower的任何写操作都将丢失

同步复制保证副本一致性，但网络或节点故障，无法写入，如果所有的Follower都是同步复制，任何一个节点中断，整个系统瘫痪

实际数据库运维时，通常一个副本同步复制，另一个异步复制

添加新的Follower

增加副本的数量，或者替换失败的节点

新Follower要有正确的副本数据，仅拷贝数据通常不够：客户端不停向系统写入数据

锁定系统，拒绝客户写入，大大降低可用性，需要不停机加新Follower

Leader**快照，复制到新Follower
Follower连Leader，请求快照之后所有的数据更改。通常是Leader日志序列号

节点故障

Follower故障

和加新差不多
- Leader故障更棘手：

一个Follower要提升为新的Leader

客户端要识别且后续请求发给新的Leader

其他Follower要开始在新Leader之下工作

1、确认Leader失效

多数用超时机制，中心化系统可用Lease机制

心跳无法确定是慢还是宕机，心跳检测可与结果分离(目标机3秒没心跳，应用A解读为宕机，等待重试，应用B解读为超时，转移至其他目标机)

2、选取新的Leader

中心化架构如HDFS，新的Leader可以用中心化节点指定

非中心化架构之可通过选举完成：2PC，3PC，Paxos，Raft等

3、调整系统配置以使用新的Leader

如果旧的Leader回归到集群，它可能仍然认为自己是Leader，这时需要确保旧的Leader成为Follower并承认新的Leader

异步复制，新leader可能还没收到旧leader的信息，如果丢弃旧leader之前的写入，违反一致性

两个都认为是leader,脑裂，可能数据破坏

故障切换时间，超时长，意味leader失效情况下，恢复时间更长，超时短，有不必要的故障转移(如临时峰值，导致节点响应时间增加至超时，不必要的故障转移使情况更坏)

日志复制

Statement-Based 坑

非确定函数now()、更新依赖现有数据，如异步转发，乱序到达、有副作用的语句，如主库有触发器等

造成副本不一致

Write-ahead log

数据拷贝与存储引擎紧密耦合

Row-based

与Write-ahead类似，但它允许复制日志与存储引擎内部分离

这种日志称为逻辑日志，通常是描述在一个行的粒度上记录写入操作：

插入，日志包含所有列的新值。删除，日志包含足够的信息以唯一地标识删除的行。（主键）更新，日志包含足够的信息以唯一地标识更新的行，以及所有列的新值

由于逻辑日志与存储引擎内部分离，可更容易地保持向后兼容，允许Leader与Follower运行不同版本的数据系统，甚至是不同的存储引擎

逻辑日志格式对外部应用程序也更容易解析

可以将逻辑日志的内容发送到外部系统（如用于离线分析的数据仓库），或者用于构建自定义索引和缓存

可用性与一致性之间的折中一致性等级：最终一致性