分布式数据
背景
系统始于单节点，由于单节点的硬件限制(CPU，硬盘等资源)以及单点故障问题，系统走向分布式架构，如何分散存储数据？
分区
将一个大的数据集拆分成多个较小的数据集，通过增加节点来增大存储以及处理数据的规模。分区分为水平分区与垂直分区。
- 水平分区： 对表的行进行拆分，表的特性得以保留。例如把十年的订单记录按年划分到10个物理节点中存储。
- 垂直分区： 对表的列进行拆分，每个分区包含该列对应的所有行。
两种分区方法各有优势，水平分区可以方便对满足一定条件(与分区方式接近)的数据做处理，垂直分区可以方便对表中某些属性做分析。在某些情况可以同时采用两种分区方法，并根据请求的逻辑来选择分发给水平分区的数据库还是垂直分区的数据库。
水平分区算法
- 范围分区
- 哈希分区
两种分区方法各有优劣，范围分区实现简单，对小范围的数据处理性能好
| 优点 | 缺点 | |
|---|---|---|
| 范围分区 | 范围查询性能好，实现简单 | 数据流量不均，查询范围较大时性能下降 |
| 哈希分区 | 数据分布均匀，节点负载较为均衡 | 不支持范围查询，节点成员变更复杂 |
为了提高哈希分区的成员变更效率，可以引入虚拟节点，物理节点对应多个虚拟节点，数据在虚拟节点上均匀分配，物理节点根据自身硬件水平对应一个或多个虚拟节点。
分区的挑战
多节点联合查询较为低效。 分布式事务实现复杂
复制
同一份数据冗余地存在多个节点上，通过网络同步数据
优点：
- 增强安全性
- 提高响应速度，例如将请求发送到距离客户端更近地服务器中
- 增加吞吐量，多机可以处理更多地读写请求(主要是读，写需要考虑一致性)
缺点：
- 多个副本间同步、更新数据复杂
复制的策略
单主复制
一个主节点，多个副本，所有节点都可以处理读请求，仅主节点处理写请求
三种复制数据的方式
- 同步复制，主节点确定所有副本都接受了写请求再相应客户端写入成功
- 异步复制，主节点直接相应客户端，无需等待副本写入完成
- 半同步复制，至少有一个副本写入完成再相应客户端
| 优点 | 缺点 | |
|---|---|---|
| 同步复制 | 完全保证数据一致性 | 如果写请求多，或部分节点宕机，系统就会变慢甚至停滞 |
| 异步复制 | 写请求性能好 | 数据一致性无法保证，可能会读不到刚刚成功写入的数据，或者数据丢失(主节点返回写入成功后立马宕机) |
| 半同步复制 | 折中的设计 | 折中的设计 |
单主复制的问题
主节点宕机怎么办？
-
人工手动切换，安全但低效
-
系统自动切换，高效但危险，关键问题 如何保证只有一个主节点？ 也即领导者选举问题
多主复制
增加主节点分担写请求的负担
为了避免数据冲突，可以将写请求类型划分，特定节点处理特定类型的请求，或配合数据分区，特定行/列的数据由特定节点来写入。
由于复杂性远超于好处，单个数据中心一般不采用，用于跨地域的多个数据中心间，加快访问速度将请求转发至地理位置更近的数据中心。
无主复制
同时把写请求发送给多个节点，当部分节点确认后就认为写成功
优点：更能容忍节点故障
缺点：冲突更多
Quorum 数据冗余机制
在 N 个节点组成的系统中，要求 W 个节点写入成功， 并从 R 个节点读取数据，只要 $W+R>N$，那么返回的R条数据中必然包括最新的值。为了保证两个写请求不改变同一条数据，需要保证$W>\frac{N}{2}$，大多数的为真正写入的。
具体数值可以根据系统灵活调整，W 越大 R 越小，读的效率高，反之写入的效率高。
CAP 定理
在一个异步网络环境，只能满足三项中的两项：
- 一致性(Consistency)
- 可用性(Availability)
- 分区容错性(Partition Tolerance)
如果发生分区，那么可用性与一致性就无法同时保证。
一致性
一致性模型指的是如果开发者遵循一定的规则，那么执行读写操作的结果是可以预测的。
例如，我们认为每次读取的结果是”最近”写入的结果，因此需要定义”最近”的概念。
线性一致性
对于系统的所有读写操作都看起来像是一个节点，每个操作都是原子的
给出一段执行历史，可以把并发操作拓展为多个顺序历史，只要有一个合法的顺序历史，就是线性一致性的。
操作之间三种关系
- 一个操作在另一个操作开始前结束，顺序关系
- 两个操作之间有重叠，并发关系
- 一个操作包含另一个操作，并发关系
顺序关系必须满足，并发关系可以按照任意顺序排列。
在多线程中，通过加锁即可实现线性一致性。但是为了实现线性一致性，需要付出很多代价。想要更正确还是更快速？
分布式共识
什么是共识？
每个节点对一些状态或一些值达成共识，例如 大部分节点都认为某个节点是 leader，会把写请求转发给 leader。分布式共识主要研究分布式系统中节点达成共识的过程与算法。
倘若每个节点都对日志的值和顺序达成共识，那么每个节点都有着相同的日志副本，每个节点就都有一致的状态与输出，就是一个高可用的状态机。(给出相同的初始状态，相同的输入会得到相同的结果就是状态机)
Paxos 与 Raft
时间与事件顺序
时间是用来确定事件发生的顺序
NTP
单调时钟
分布式系统的单调时钟–逻辑时钟
todo: 分布式事务