《设计数据密集型应用》
一～四章讲单机数据库。
五～九章讲分布式数据库，适合多看几遍。
十～十二讲数据如何被更高效地处理，即批处理、流处理。
一、可靠、弹性、可维护的应用
二、数据模型和查询语言
三、存储和检索
四、编码和演变
五、复制（Replication）
复制数据的原因：
- 放到离用户更近的地方，减少延迟；
- 即使系统的部分fail了，系统仍旧是可用的；
- 扩容系统提高吞吐量以应对查询。
复制的三种算法：
- 单主（single-leader）
- 多主（multi-leader）
- 无主（leaderless）
主从复制
可以通过主从复制来保证数据被保存到了所有的副本上：
leader和master、follower和slave这里是同义词
- 写请求均被发给leader；
- follower拷贝leader的replication log并重演到本地。
- 读请求被发给leader或follower都可以。
同步 OR 异步复制
同步复制的优点：
- 能确保数整体性能据被拷贝到了follower；
同步复制的缺点：
- leader被复制过程阻塞了，会影响性能；
- 如果复制失败——比如follower短暂的不可用，整个请求也会失败。
异步复制的优点：
- 不影响leader响应请求的性能；
异步复制的缺点：
- 如果数据还没被复制到任何follower的情况下leader挂掉了，且leader不可恢复（或者暂时不可恢复），则数据就3额丢失了；
一般会采用权衡的方案，即半同步（semi-synchronous）的模式。
复制的一般过程
- follower从leader下载一个全新的快照；
- follower从leader请求最新数据，也就是上面快照之后写入的新数据；
故障恢复 - Follower故障
Follower故障了只需要重启后从Leader下载log然后加载即可。
故障转移（Failover） - Leader故障
- 判断leader宕机
一般是大部分副本均PING leader超时就认为leader宕机了。 - 选择新leader
通过选举或一个controller node来选择下一个新leader。
一般优先选择数据最新的副本。 - 更新配置以选择新leader
客户端需要将请求发给新的leader
旧leader重启后，需要成为新leader的follower，以免发生脑裂。
Replication Log的实现
Replication Log的实现方式：
- 基于语句的
日志中记录的写入语句，比如SQL的INSERT、UPDATE、DELETE。
缺点是：一些每次执行结果都会变的语句，在leader和follower上执行结果不一致，比如now()、rand()，最好在写入日志时进行替换；一些语句的执行是有顺序要求的，复制指令的过程中不能乱序；一些语句有副作用，可能会导致不同副本上执行结果不一样。 - WAL（写前日志）
如MySQL里的redolog和undolog。 - 逻辑日志
如MySQL里的binlog
复制延迟（Replication Lag）
数据被拷贝到从服务器期间，主从是不一致的，一般情况下这个间隔时间是很短的，但是如果网络出现了问题就有可能会变得比较严重了。
TODO：我需要先研究下MySQL中是怎么处理这种延迟的。
多主复制（Multi-Leader Replication）
无主复制（Leaderless Replication）
六、分区
分区和复制
数据只存在于一个分区，而一个分区可以有多个复制，因此分区和复制是一对多的关系。
KV数据库的分区
倾斜（skew）指一些分区存储的数据比其他的多，或接受更多的查询请求。倾斜会导致大部分请求被打到了少数节点上，产生热点问题。
- 解决热点问题的一种最简单的方式是随机分配数据
但是这种方式的问题是不知道数据被分配到了哪个节点上，所以可能需要遍历所有节点才能获取到数据。 - 根据范围分区
根据范围边界我们可以快速得知一个key存在于哪个分区，如果已知分区和节点的映射关系，我们就可以直接将key定位到一个节点上。
优点除了找得快外，每个分区里的key也可以是有序的，这样顺序查找会快一些。
缺点是可能出现热点数据，比如按创建时间分区的话，最近产生的数据就会被扎堆访问。所以分区的key需要谨慎选择。
例子：Bigtable - 根据key的hash值进行分区
这种方式的好处是key在分区间能分布得比较均匀（和hash函数有关）。
缺点是范围查询非常不便。
Cassandra和MongoDB采用MD5作为hash函数；
Redis（Cluster）采用CRC16。
即使用hash的方式来分区，极端情况下仍有可能发生热点问题，比如大部分请求集中于少数的key上。
为了解决这种倾斜问题，应用可以通过设计数据分布方案来分散数据，比如给key加上一些随机数来帮助key分散得更均匀。
二级索引（关系数据库、文档数据库）的分区
- 根据文档分片
最常用的文档数据库比如Elasticsearch，如果将MySQL的每一行看作一个文档，二级索引实际上就是为文档建立索引。
二级索引服务于单个数据库实例（一个分片），因此又被称为本地索引，如果要查询数据库的多个分片，就需要从每个分片对应的二级索引上查询一次。
ShardingJDBC的分库分表方案就是采用这种每个库都建一个索引的方式。
MongoDB、Elasticsearch等均是采用的这种方案。 - 根据Term（词）分片
Term可以看作文档中的一个字段，根据Term索引即将一个范围内的Term索引到同一分片内，不考虑对应文档实际所处的分片，这种索引方式被称为全局索引（global term-partitioned）。
比如文档有一个颜色字段，我们可以将颜色首字母a-r的索引到第一个分片，s-z的索引到第二个分片，查询时如果判断要查询的颜色是红色（red）则可以直接定位到第一个分片上去查到所有的Term，然后再取到所有的文档。
好处是我们不需要遍历每个分片上的每个索引了。
缺点是写操作变得非常复杂，因为一次写入会影响多个分片，而且还需要分布式事务来保证这个过程的原子性。
这种方案比较少见，已知的有Riak、Oracle data warehouse。
分片再平衡（扩容）
Rebalancing：在集群中将一个节点的负载转移到另一个节点的过程称为Rebalancing。
- hash mod N
N变大的情况下将原来对其他节点的请求打到新节点上。
但是只要N变大原来key的定位就会发生变化，会发生很多不必要的Rebalancing，一个key第一次可能会被定位到节点0，第二次扩容可能会被定位到节点1，等等。 - 固定数量的分片
类似于Redis的做法，分片数量固定，且大于节点数，分片被平均分配到节点上，扩容也是针对分片进行的。
缺点是容易导致数据倾斜，比如大部分key被hash到了少数分片上。 - 动态分片
如果一个分片存储的数据过多，这个分片会被拆分成多个子分片，拆分后，两半中的一部分；
如果一个分片里的数据被删得过多了，也可以和相邻的分片合并。
动态分片的好处是分片数可以随着数据容量动态调整。
缺点是当刚开始数据集合为空（比如建了个新表）的情况下，只会有一个分区，这时所有请求都会被打到单个节点上，这时别的节点就都空着没事干了，在HBase上刚开始会创建固定数量的初始分片。 - 分片与节点数成比例
在Cassandra中，每个节点都会分配固定数量的分片，数据总量提升时每个分片容纳的数据量也会随着提升，除非增加节点数量。
当一个节点加入到集群后，它会随即选出固定数量个分片进行分裂，并带走其中的一半。
自动或手动再平衡（Rebalancing）
自动优势：方便；
自动劣势：容易损害网络请求的性能，因为rebalancing需要重定向请求并将大量数据从一个节点移动到另一个节点。
特别是结合故障检测后，比如一个节点因为过载暂时不能很快响应请求，其他节点判断它挂掉了，并开始执行故障迁移（包含数据的Rebalancing）。
请求路由
客户端如果将请求打到key真实存在的节点上。
- 允许客户端访问任意节点，如果该节点上存在key则响应，不存在的情况下重定向到该key真实存在的节点上；
- 有一个路由节点专门负责重定向，客户端都需要先访问该节点，由该节点将请求转发到目标节点上；
- 客户端需要感知每个分区所在的节点，然后直连到节点上。
后两种方式一般都需要有一个服务注册表（如ZooKeeper）存储服务的分片信息供查询。
七、事务
这一章蛮难的，前面的还好，到后面Weak Isolation的Write Skew和Serializability之前都没有深入了解过看得比较吃力，我打算等把MySQL的原理再深入一下后回来重读这一章。
八、分布式系统的故障排除
失败和部分失败
分布式系统的特征之一就是存在部分失败，哪些节点会挂掉是不可预测的。
不可信的网络
网络可能出现的问题：
- 请求可能丢失；
- 请求可能停留在一个队列中，并在之后投递；
- 远程节点可能挂掉；
- 远程节点可能会暂时停止响应；
- 远程节点可能处理了请求，但是响应被丢失了；
- 远程节点可能处理了请求，但是响应会比较慢。
错误检测：
- 如果网络请求得到错误响应，可以直接判断节点挂掉了；
- 很多时候根本没有响应，这时只能多试几次，等待超时。
但是现实中的大部分系统都是没有一个明确的超时时间可以断定它已经挂掉的，这意味着，如果等得太短会导致误判一个节点挂掉，等得太长又起不到及时检测出问题的作用。