分布式数据系统里的复制和分区方案
为什么要进行数据复制？
- 让数据在地理位置上距离用户更近，从而带来更低的延迟
- 当部分组件出现故障时仍然保持可用状态，实现高可用
- 扩展到多台机器上提供数据访问，提高吞吐量
- 复制线上数据进行分析、测试等操作
思维导图
数据复制（简书log_gol）.png
数据复制的方案大概分为三种：
主从复制、多主复制、无主复制
主从节点
一主多从的方式，所有写操作均发生在主库上，所有读操作发生在从库上。
主库与从库的数据一致性通过复制完成，所有从库从主库中复制最新的数据。
同步复制
主库需要等到从库复制操作的确认后才会向用户报告完成
同步复制的优点是能够确保数据处于最新状态，一旦主库发生异常，可以将从库提升为主库，且保证数据为最新；但从库发生状况时可能会对主库造成阻塞，特别是存在多个同步从库时，会对主库的吞吐量造成很大影响；
异步复制
主库向从库发送完复制消息后立即向用户报告完成，从库可能会经过很长时间才会收到复制日志
异步复制的吞吐量更优，但存在数据滞后问题。当主库发生故障时，从库升级为主库，但由于滞后此时从库数据并非最新，可能会造成数据丢失现象
通常会配置一台同步复制从库，多台异步复制从库，一旦同步从库发生异常，将某个异步从库提升为同步从库
节点失效
为什么主从复制能够起到高可用的作用？
- 当某个从库发生崩溃重启，该库可以通过本地磁盘上的复制日志定位到故障前最后处理的一笔事物，然后连接到主节点请求之后所有错过的数据变更，进行追赶式恢复
- 当主库失效时，从库之间进行选举，被选举出的从库会作为新的主库，并通知客户端。但可能会存在一些变数，如两个库均认为自己是主库的脑裂现象
- 心跳检测。各库之间通过心跳检测判断是否正常工作。
复制的实现
语句复制
从库重新执行主库上所有的写操作语句，但对于非确定性的函数语句如Now()、RAND()等无法试用，且该方法需要严格按照相同顺序执行
预写日志（WAL）传输
对于Btree结构，每次数据修改前都会预先写入日志，将该日志传输给其他从库进行复制，建立相同的数据副本，但该方案与存储引擎紧密耦合
行逻辑日志
与存储引擎解耦，也称为变更数据捕获
- 对于行插入，日志中包含所有相关列的新值
- 对于行删除，日志里有足够的信息来唯一标识已删除的行（通常靠主键，若无主键则记录所有列的旧值）
- 对于行更新，日志包含足够的信息来唯一标识更新的行，以及所有列的新值（或至少包含所有已更新列的新值）
- 对于多行事物，后面紧跟记录事物提交
触发器和存储过程
非数据库实现，由程序层实现，更灵活，如部分复制、复制到其他数据库中等操作
复制滞后问题
由于写在主库，读在从库，从而造成数据的延时带来的问题
读自己的写
用户写完最新数据后，从某个从库上读，由于数据暂时未同步到从库，导致无法获取到最新的数据
对于该情况，需要提供读写一致性
方案介绍：
- 对于用户可能会修改的内容，从主库读。如社交网站个人首页通常只有用户自己才能编辑，因此可以总是从主节点读取用户自己的首页配置文件。
- 若上面的页面太多，则不适用；此时可以跟踪最近更新时间，更新后的一分钟内从主库读。
- 记录更新时间戳，但在分布式系统中存在的时钟同步问题，可能会导致其他情况发生。
同时对于多个设备、不同网络类型、不同数据中心等也会产生更复杂的问题
单调读
用户多次访问时可能访问到不同的从节点，而不同从节点间的数据可能不同步
对于该情况需要提供单调读一致性
方案介绍：
可以设定规则让每个用户从固定的副本进行读取
前缀一致读
A操作和B操作具备前后因果性，在主库上先A再B，但由于各种原因（网络波动等）导致到达从库的顺序为先B再A
多主节点复制
单主节点可能存在瓶颈问题，多主节点结构存在多个主节点接受写操作，且所有主节点同时也是其他主节点的从节点
多主节点适用于以下几个场景：
- 多数据中心：不同地理位置设置多个数据中心，每个数据中心都有一主多从，不同数据中心的主节点之间进行多主复制
- 离线客户端：离线后仍需工作，本地数据库
写冲突
多主复制的最大问题就是写冲突，如A在库a上修改了数据X，同时B在库b上也修改了X，从而造成了冲突。
解决方案：
- 最好的方法就是避免冲突，目前没有太成熟的解决冲突方案，最好避免。如特定的数据的写对应的特定的数据中心
- 收敛于一致状态，保证副本最终状态一致。如分配唯一ID，以最高ID为胜利者，但可能造成数据丢失；或将多个值进行合并保存；或靠应用层解决
无主节点复制
上面两种的写入都是依靠主节点的，无主节点方案是所有副本均可以接受写请求。当客户端写入数据或读取数据时，不是发往一个节点，而是对所有节点请求。
如三个库，客户端写入会发往这三个库，只要有两个以上回应写入成功即代表写入成功。当某个节点失效后重新上线时，Dynamo风格数据库采用以下方式进行数据恢复：
- 读修复
客户端向三个库请求某个值，库1和库2该值的版本为9，库3该值的版本为7，则认为库3的数据是旧值，客户端会拿到版本9的数据，同时更新库3的值到版本9。该方法适用于会被频发读的场景，若某个值很少被读，可能会是很古老的版本。 - 反熵
后台进行不断扫描数据差异并进行修复，不保证顺序复制写入，会引入明显的同步滞后
Quorum
选举数为多少的时候合适？即总库n时，多少个库返回ok才代表成功？
设总n，写入需要w个确认，读取需要r个读取，则有：
w+r>n
即可，即保证读和写节点集中有至少一个重复的节点，即可保证至少有一个最新值。
常见设置为n为奇数，w=r=(n+1)/2 向上取整
即使在w+r>n也有可能返回旧值
局限：
- 并发写时如果挑选胜利者，某些写入可能被误丢弃
- 部分写成功，部分写失败，且总的成功数少于w，此时认为写失败，但写成功的库无法回滚数据
- 一个集群可能有远远大于n的节点数，使用仲裁节点来计算w和r的值；若因网络中断，客户端只能连接部分节点，但这部分节点不全是仲裁节点，无法达到w或r要求。在高可用容忍旧值的情况下，可以放宽仲裁，将新数据临时写入非仲裁节点（网络恢复后需要回传给仲裁节点），只要满足w或r即算成功。但此时其他客户端可能无法拿到这个新值，因为新值在临时非仲裁节点且由于网络中断还未进行回传过来
并发
对于并发，由于分布式系统中的时钟同步问题，其实是无法严格确定时间的先后顺序的，因此只要两个操作不需要意识到对方，即不存在依赖、因果关系，即可称之为并发
分区
何为分区？复制是将相同的数据复制保存在多个节点上，从而达到备份容灾的目的；而分区是为了扩展系统能力，当面临海量的数据集成和查询压力时，将一个大数据集分散在更多的磁盘上或机器上，从而也将查询负载分摊在更多的处理器上
分区的方法
随机分配
最简单的方法就是将记录随机分配到所有节点上
优点：能够避免热点（频繁访问的数据全放在一个节点上了，造成倾斜）
缺点：当试图读取特定数据时无法知道数据保持在哪个节点，需求并行查询所有节点
基于关键字区间分区
为每个区间分配一段连续的关键字或范围，区间不一定均匀分布，根据数据分布特征进行划分。
优点：可以按照关键字排序保存，轻松支持区间查询（时间戳为关键字，某段时间的数据轻松查询）
缺点：可能导致热点（时间戳为关键字，某段时间的写入全集中在一个节点上）
基于关键字哈希值分区
找到一个合适的关键字哈希函数（能够处理数据倾斜并使数据均匀分布），为每个分区分配一个哈希范围，关键字根据哈希值对应不同的哈希范围划分到不同分区
优点：均匀分配，分界边界也可以是均匀分布
缺点：丧失区间查询特性
针对负载倾斜与热点
如微博名人八卦信息，会造成对某个分区的访问风暴，目前这种情况只能在应用层解决（热点关键字前加随机前缀分散成多个不同关键字进行操作，代价是读取会造成很多额外操作），数据系统暂无能力自动解决
二级索引分区
基于文档分区
也称为本地索引，不同分区各自维护自己分区的二级索引。
优点：简单
缺点：查询需要在所有分区并行查找（A区和B区有相同的索引键）
基于词条分区
也称为全局索引，为了避免瓶颈，全局索引会切片（如关键字或哈希）分布在多个分区内
优点：读取更高效
缺点：写入慢且复杂，因为单个文档更新可能牵扯多个二级索引，而不同二级索引可能分布在不同分区甚至节点上，造成明显的写放大
分区再平衡
- 压力增加，需要更多CPU处理
- 数据规模增加，需要更多磁盘和内存存储
- 节点故障需要其他机器接管失效节点
不使用取模
使用取模映射时，当节点数量发生改变，会导致以前的映射结果同样发生改变，从而造成数据迁移，因此一般不适用取模的方式。
固定数量分区
创建远超实际节点数量的分区，然后为每个节点分配多个分区；当增加节点时，从原来的节点中剥离一部分分区给新节点即可。Redis的槽就是基于这种思想实现的。
优点：动态平衡，不会产生大规模的数据迁移，可以根据节点能力分配不同数量的分区等
缺点：分区数量需要提前确定好，每个分区包含数据量有限；分区数量需要设置合理
动态分区
适用于关键字分区和哈希值分区
当一个分区的数据量达到设定的阈值后，该分区分裂为两个分区；
当大量数据被删除后，多个分区合并成一个分区
每个节点可以承载多个分区，分裂后的分区可以转移至其他节点进行负载均衡
优点：分区数量自适应
按节点比例分区
前两者分区数量都是与数据规模有关的，与节点数无关
该方法每个节点拥有固定数量的分区，节点数量不变时分区大小与数据集大小正比，节点增加时分区会变小因为分区数量增加。
优点：每个分区大小保持稳定
缺点：新节点加入会随机选择现有节点拿走其一半数据，随机选择法可能带来不公平分裂
请求路由
分区后客户端连接的时候选哪个？可以使用类似zookeeper等服务注册发现服务辅助进行
