第二部分 分布式数据系统
使用分布式的原因：
- 扩展性
- 数据量或读写负载大，单机顶不住；
- 容错和高可用性
- 单个机器宕机后，为保证服务正常提供，需要多台机器做冗余；
- 延迟考虑
- 如CDN的使用，客户端分布在全球时，需要多数据中心提供数据访问的能力，避免请求长途跋涉；
- 资源弹性
- 在云上部署时，可按照需求动态扩缩容服务；
有状态：
- 服务自身需要保存数据，因为请求间有关联；
- 需要维护状态的一致性；
无状态：
- 请求间是独立的（读数据库等依赖下游服务等操作，不视为请求间的关联）；
- 服务不需要维护请求有关的状态，容易扩展，如计算框架 MapReduce；
系统架构
共享内存架构：
一个操作系统管理多CPU、内存、磁盘，可视为一台强大的机器；
缺点：性价比不高，且硬件性能翻倍，往往不代表处理能力翻倍；
共享磁盘架构：
多服务器拥有各自独立的CPU、内存，数据存储在共享的磁盘阵列上，采用高速网络连接（NAS，SAN）；
一般用于数仓；
缺点：资源容易发生竞争，锁开销也限制了进一步扩展的能力；
无共享架构：
如 mysql，每个 mysql 实例都有自己的存储、内存和计算资源；
数据是分布式存储的，各实例之间不共享物理存储；
复制：多节点保存相同副本；
分区：将单个数据库表或索引的数据根据某种逻辑规则（如范围、列表、哈希等）划分成多个部分，这些部分仍然存储在同一个数据库实例中，每个分区包含表或索引的一部分数据；
分片：业务的数据按照某种逻辑规则划分成片，分布在多个数据库实例上，水平扩展；
第五章 数据复制
主要目的：
降低访问延迟：数据在地理位置上更接近用户；
提高可用性：当部分组件出现故障，系统依然可以利用备份数据继续工作；
提高读吞吐量：多台机器可同时提供数据访问服务；
主从间同步/异步复制
以主返回响应为完成操作，同步复制也可以视为实现了强一致性，客户端不可能在从节点读到过期的数据，而异步复制实现了最终一致性，由于从节点在主节点返回响应的时刻，还没更新（复制）到新数据，此时客户端在从节点更新前，可以读到过期数据；
显而易见，一主多从时，从节点均采用异步复制时，性能是最好的，但是存在数据不一致的可能，即主挂掉时，异步复制不保证最新数据一定能被复制到从节点（复制滞后问题）；
一种常见用法（半同步），为防止传输数据丢失，至少一个从节点为同步复制，保证当主挂掉后，不会发生数据丢失的情况；当然也需要监控该从节点的状态，如果发生挂了等异常情况，需要更换一个从节点同步复制；
同步复制的一种实现：6.824L11链式复制；
添加新从节点
类似于数据迁移过程；
- 先确定时间点T，主节点生成快照（redis生成RDB文件）；
- 将快照传给从节点；
- 从节点应用快照后，连上主节点，追赶剩余新数据的变更；（如发送偏移量，说明需要哪些新数据）
注意：适用主从架构，如果类似raft需要选主的，在添加多个新节点时，需要额外考虑脑裂的问题，集群成员变更；
节点失效处理
从节点失效
根据落后情况，从节点直接追赶日志，或者快照+追赶；应该由主节点判断（redis根据偏移量是否还存在主节点的缓存中判断）；
故障原因倒不用再区分，结果上看就是日志落后了；
主节点失效
相比从节点的恢复较复杂，简单来说需要：
- 将从节点提升为主节点；
- 通知客户端/从节点，新主节点地址； 提升的过程可以由人工、自动（哨兵机制）处理；
自动切换时，一般的流程：
- 确定主节点挂了；判断方式如：哨兵模式
- 选举新主节点；
- 重新配置系统元信息；
切换过程中的问题：
（1）如果只使用异步复制，当新主节点没有最新数据，且原主节点重新上线加入集群，此时就会发生冲突；
此时的矛盾点在于按照正常逻辑，旧主节点应该降级为从节点，但此时就会丢失已持久化的数据；如果不降级，此时集群有两个主节点，scheduler需要重新降级新主节点，但在这个时间差内可能发生新的写入，变成两个主节点都有各不相同的最新数据，无法合并；
故如果单纯的主从异步复制下，个人认为最优解就是丢掉未复制的写请求；不能承诺全数据持久化；
（2）注意，可以直接丢的重要前提是，该写请求修改的数据一定是独立的，因为丢的这个操作代表不会对这个数据进行额外的逻辑处理，例如：当数据写入数据库后，建立了外键关系、被其他系统（如原文提及的redis）引用，此时就会发生严重的数据不一致情况，如果使用自增主键，那么：外部引用的数据被硬覆盖，如果使用UUID等不会重复的主键，外部最后也会发现自己引用的数据莫名消失；
（3）如果主从没有类似哨兵的 scheduler，那么在（1）的情况下，同一时刻有两个主节点，需要具体场景具体分析了，但可预计发生的错误，如：脑裂等；
（4）需要考虑如何判断主节点挂了，在没有 scheduler 的情况下，通常使用超时时间判断，当然需要动态根据 trace 确定超时时间的值；显而易见，过长 -> 服务可用性下降、过短 -> 误判的可能性增加，服务性能下降；
复制日志的实现
基于语句的复制
如 binlog 的 STATEMENT 模式，主节点执行的每个写（操作语句）请求，都会作为日志传送给从节点；
但明显有缺点：
- 非确定性的语句，如RAND()等，在不同节点会生成不同结果；
- 如果有自增键、或者依赖于数据库的现有数据，在高并发的情况下，原则上就需要所有副本严格按照相同的顺序执行；
注：此处原文应该默认前提是自增锁使用交叉模式，也就是模式2，在并发的情况下，自增键虽然不会出现遗漏或者重复，但是不一定按照单增的顺序执行语句，主从间的顺序不一定一致；
- 产生副作用（执行后）的语句（触发器、存储过程、用户定义的函数等），可能在不同副本产生不同的副作用，简单来说就是缺失上下文；
基于预写日志（WAL）传输
即 将wal传输给从节点； wal主要记录：
- 物理数据变更：记录的是数据库页、块的物理变化；
- 事务开始和结束；
缺点就在于依赖于存储格式或者说存储引擎，无法跨版本；
基于行的逻辑日志复制
如 binlog 的 ROW 模式，简单来说就是将存储的逻辑和实现剥离，日志记录以行为单位的修改：
也称为变更数据捕获(CDC)；
- 行插入，记录所有相关列的新值；
- 行删除，记录被删除行的唯一标识，一般记主键，如果没有主键，就需要记录所有列的旧值；
- 行更新，记录被更新行的唯一标识，及所有列的最新值；
在一个事务中若同一行多次更改，则会产生多条日志，并且最后有记录标识该事务已提交；
复制滞后问题
读自己的写
即用户写入数据后，第二次读从节点时，从节点尚未复制到这份新数据，从用户角度看就是刚写入的数据“丢失”了；
问题：需要保证写后读一致性；
解决方案：
- 业务逻辑，即用户可更改的内容，会锁定在主节点上读，用户不可更改的内容则倾向从节点上读；
- 如果不符合第一点的前提，则可以选择判断上次更新时间，即大于主从同步的最大延迟时，读从节点，小于则读主节点；
- 由客户端记录自身最后一次更新的时间戳，并且在读请求中附带该信息，由节点判断自己是否已经同步该时间戳以前的数据，如果没有则需要转发到其他节点；
额外问题：跨设备的写后读一致性:
多设备相互是隔离的，故更新时间戳无法统一，需要将多设备的元数据做到全局共享；
需要注意:多客户端请求需要路由到同一个数据中心；
单调读
即客户端多次读取时，被路由到不同的同步进度节点，读到数据出现又消失；
简单的解决方法，如通过哈希分配节点，换句话说用户仅访问固定的节点，当然如果节点挂了就需要重新路由；
前缀一致性读
即第三方观察双方的对话顺序可能因为不同主从节点（不同分片）同步速度而发生顺序混乱；
简单方法就是将强调顺序的数据发送给一个分区内处理，避免不同分片同步速度的差异问题；(性能差，需要额外处理数据的导向)
多主节点复制
单纯在多个数据中心分别部署主节点，之间采用异步复制；
相比单主节点:
性能提升，异步复制下，多主节点提供服务，响应更快，地理上平均距离更近；
数据中心宕机时，不会停止服务；
场景:
离线客户端操作，协作编辑
即将各种终端都作为主节点，都有自己的db，上线或者实时各自再进行同步；
明显有写冲突；
问题: 写冲突:
一种可能的解决方法:将同操作路由到同一数据中心，但明显一方面有潜在的性能问题，即负载不均衡，另一方面，或者服务宕机等涉及重新分配的情况下，问题容易重新出现；
收敛一致性
简单来说，利用时间戳等标识，确定所有操作的全局顺序，(容易数据丢失？)
自动冲突解决: crdt：无冲突复制数据类型，是一种数学结构，它允许多个节点在不需要通信的情况下独立地对数据进行修改，最终所有副本会自动达成一致。CRDT 的设计保证了操作是可交换的，也就是即使多个节点进行不同的更新，最终所有节点的状态都会一致。CRDT 适用于不需要强一致性的系统，如协作编辑工具；
三向合并的持久数据结构：将当前版本、本地修改版本和远程修改版本三个版本进行比较，自动合并两者的修改。如果两个版本的修改不冲突，它们会自动合并；如果冲突，系统会提示用户手动解决；
操作转换（OT）：通过转换操作的顺序来保持一致性。每次当两个用户对同一数据进行不同的操作时，系统会调整操作顺序，确保两次操作在最终的结果中都被应用；
无主节点复制
个人认为其实类似实现一致性共识算法，强一致性下，读写都需要满足大多数节点同意，此处客户端一定程度上负担了leader的作用；
有n个副本，写入需要w个节点确定，则读取至少需要查询r个结果，即需要满足 Quorum；
w + r > n
w 和 r 越大，系统的一致性越强，可用性会下降（因为需要需要更多在线的节点）；
w 和 r 越小，一致性变弱，但提升可用性；
happens-before关系和并发
操作a和b存在三种可能，a先b，b先a，ab并发；
确定并发关系算法:(p178~180)
版本号绑定主键，新值写入后递增版本号；
写前需先读，即获取当前值和各自最新的版本号；
写请求必须包含 当前最新的版本号，读取到的所有值及新值 合并后的集合，写响应也会返回版本号和所有值；
服务器收到写请求后，将请求的版本号与数据版本号对比，覆盖小于等于该版本号的数据(请求一定包含版本号前的数据集合，故可直接覆盖)，不可修改大于该版本号的数据；