第二部分：分布式数据系统
第五章、数据复制
通过网络在多台机器上保存相同的副本。
- 多副本的目的
- 使数据在地理位置上更接近用户，从而降低访问延迟。（CDN）
- 当部分组件出现故障，系统依然可以继续工作，从而提高可用性。（高可用，主从）
- 扩展至多台机器以同时提供数据访问服务，从而提高读吞量。（负载均衡，分布式）
主从复制
- 指定某一个副本为主副本 （或称为主节点）。当客户写数据库时，必须将写请求首先发送给主副本，主副本首先将新数据写入本地存储。
- 其他副本则全部称为从副本（或称为从节点）。主副本把新数据写入本地存 储后，然后将数据更改作为复制的日志或更改流发送给所有从副本。每个从副本 获得更改日志之后将其应用到本地，且严格保持与主副本相同的写入顺序。
- 客户端从数据库中读数据时，可以在主副本或者从副本上执行查询。再次强调， 只有主副本才可以接受写请求;从客户端的角度来看，从副本都是只读的。
同步和异步
同步和异步的区别在于主节点是否需要等待从节点返回成功后才算成功。
同步的优点：从节点的数据是完整的，从节点随时可以作为一个可靠的节点来读取数据或者替换主节点。
同步的缺点：虽然节点之间复制速度特别快，但只要从节点的一环出现错误，就会导致任务失败。如果同步的从节点过多，会让故障的概率指数级增加。
半同步：一个主节点，一个同步从节点，多个异步的从节点。如果同步的从节点出现问题，则将一个异步的从节点升级成为同步从节点。主节点出现问题，用同步从节点替换主节点。
配置新的从节点
当添加新的从节点后，如何保证新从节点和主节点之间数据的一致性。
- 如何在不停机的情况下，保证新节点的数据追平主节点（逻辑同样可以用来做数据库迁移）
- 在某个时间点，对主节点产出一个数据一致性快照，这样可以避免长时间锁定数据库。（MySQL的innobackupex）
- 将此快照拷贝到新的从节点。
- 从节点连接主节点并只请求快照点后所发生的数据修改日志（binlog）。
- 获取日之后，从节点追平主节点数据。
处理失效的节点
即使某个节点中断，也要保证系统总体的持续运行。高可用
- 从节点失效：追赶恢复数据
根据从节点数据日志情况，与主从复制日志情况，进行数据追赶。
- 主节点失效：节点切换
需要将某个从节点提升为主节点，同时客户端更新到新的主节点
- 确认主节点确实已失效。
- 确认新的主节点。可能需要多数节点达成共识，或者手动选择最接近主节点数据的从节点。让所有从节点同意新的主节点。
- 配置应用使用新的主节点。（写请求都到新的主节点）确保旧主节点已降级成从节点，且同意新的主节点。
主从切换时可能出现的一些问题：
- 异步复制，新的主节点可能没有收到所有旧主节点的数据；选举后，旧主节点又很快上线，出现旧主节点（现在的从节点）数据超过新主节点。
旧主节点未完成复制的数据丢弃掉。（会导致一部分数据丢失，违背数据持久化概念）所以应该尽量保证主节点提交的数据可以被全量同步。
如果程序依赖数据库的数据来生成主键，将直接导致业务系统出现问题。所以最好还是要保证有同步数据库。
- 超时时间设计的过短：可能导致不必要的主从切换。
应该尽量保持平衡，但其实也没有一个固定的解决方案。所以有些系统为了保证可靠，主从切换还是由运维手动操作。
复制日志的实现
- 基于语句的复制
主节点把所有写请求，都当做日志发送给从节点。（aof和增量binlog）
- 任何非确定性的函数调用（now，随机数等）
- 如何使用了自增id，必须保证所有库的自增键相同
可以把主节点执行后的结果当成转换成写语句同步给从库。
- 基于预写日志（WAL）传输
多数数据库都是基于WAL来做数据更新的，完全可以利用WAL，来向从库同步WAL，这样可以做到相同的写入操作。
- WAL受限于存储引擎，如果不同的存储引擎（和版本号），采用的WAL将完全不同。（无法实现热升级，如果需要升级数据库版本，需要停机）
- 基于行的逻辑日志复制
通过自定义的逻辑日志来进行复制
新增：日志包含所有相关的列新值
删除：通过唯一标识来生成删除日志。
更新：通过唯一标识和需要更新的新列值来生成更新日志。
- 基于触发器的复制
不使用数据库本身，通过第三方工具（触发器）来实现复制。（canel：思想相同，不过实现采用的伪装成数据库从库）
Oracle的Databus、Postgres的Bucardo
- 通常开销更高，也容易出错，但非常灵活。
复制滞后问题
主从复制要求所有写请求都经由主节点，而任何副本只能接受只读查询。如果一个应用正好从一个异步的从节点读取数据，而该副本落后于主节 点， 则应用可能会读到过期的信息。如果同时向主节点和从节点发起查询请求，可能会查到不同的值。
主要涉及讨论对于各种复制滞后的问题应该如何解决
读取自己写入的数据（读写请求一致性）
用户提交一些信息，然后查看自己刚刚提交的内容。由于主从复制滞后问题导致读取的内容不一致。
读写请求一致性：如果用户重新加载页面，总是能看到自己最近提交的更新。（其他用户读取此信息不保证最新）下面是几种实现方式
- 总是从主节点读取自己的配置信息，对于他人的配置信息从从节点读取。
- 跟踪用户的更新请求，如果最近一分钟提交了更新操作，则从主库读取，否则从库。
- 客户端本地记录最后一次更新的时间戳，保证查询的信息至少晚于或等于本地记录的时间戳。（这些请求不一定是从主库查询的，可以在多个从库之间轮询，直到查到满足条件的信息）可能由于不可靠的时钟出错
- 如果有多个数据中心，必须把用户请求路由到主节点所在的数据中心
单调读（读一致性）
第一次读取的数据与第二次读取的数据不同。比强一致性弱，比最终一致性强的保证
如果某个用户依次进行多 次读取，则他绝不会看到回滚现象，即在读取较新值之后又发生读旧值的情况。
- 确保同一个用户每次都从同一个副本查询，而不是每次请求都随机路由。（但如果被路由的节点失效，失效节点的所有用户都要重新分配）
前缀一致性读（happened-before）
对于存在因果关系的数据，必须要严格按照顺序复制。有点类似于jit需要保证乱序生成的代码，单线程结果一致性。（有序性）
微信聊天记录就存在这样的问题，产生这个情况的原因通常是：分布式写请求分片有多个，不能保证全集群写入顺序的一直。就会导致从分片读到完全乱序的情况。
- 所有具有因果关系的写请求都交给同一个分片来完成。（这样做效率会大打折扣）
- 可以用过一些happened-before算法来追踪因果关系。
多主节点复制
每个节点既扮演主节点，也同时扮演者其他主节点的从节点角色。
适用场景
多主模式逻辑复杂，在同一个数据中心内部使用没有意义，通过在多数据中心场景中使用。
- 多数据中心
为了容忍数据中心级别的故障，或者更接近用户，可以把数据库的副本横跨多个数据中心。
主从和多主之间的对比
| 场景 | 主从 | 多主 |
|---|---|---|
| 写性能 | 写请求必须传到主节点所在的数据中心。 写入延迟高 | 写请求可以在自己最近的数据中心完成。然后把数据复制给其他数据中心 |
| 数据中心故障 | 如果主节点所在的数据中心发成故障，必须把另一个数据中心提升为主数据中心 | 每个数据中心独立运行，即使某个数据中心挂了也不影响其他数据中心 |
| 网络问题 | 对于同步的主从模式，需等待同步节点写完才能写入成功，需依赖数据中心之间的网络 | 每个数据中心之间异步通讯，只需要依赖数据中心本地的网络。 |
多主模式同样也带来了许多问题：
- 不同的数据中心可能会同时修改相同的数据，因而必须解决潜在的写冲突。
- 自增id问题：可能由于同步的不及时导致每个数据中心之间，相同数据自增id不同。（多数据中心不建议使用自增id）
- 离线客户端操作
应用在与网络断开后还需要继续工作
每个设备都有一个充当主节点的本地数据库（用来接受写请求）。
- 协作编辑
实时协作编辑应用程序允许多个用户同时编辑文档。（在线文档）
当一个用户编辑文档时 ，所做的更改会立即应用到本地副本，然后异步复制到服务器以及编辑同一文档的其他用户。
处理写冲突
- 如何避免冲突
通过应用层来指定特定记录的写请求总是通过同一个主节点，这样就不会发生冲突。（有点违背多主模式的冲突，变成了主从模式的变种）
- 收敛于一致状态
数据更新符合顺序性原则，即如果同一个字段有多个更新，则最后一个写操作将决定该字段的最终值。（可能会导致最终值的不确定性）
如何实现收敛一致
- 最大id：所有写请求分配一个唯一的id（时间戳+uuid）所有数据同步时，只保留id最大的数据（最终一致）
- 合并一致：让需合并的结果按照一定规则排序，只取序列最靠后的。
- 同2，应用自定义合并规则。
一些常见的自动解决并发修改冲突算法
- 无冲突的复制数据类型（ CRDT）：多个用户同时编写map、list等。
- 可合并的持久数据结构（Mergeable persistent data) ：类似git跟踪变更历史，三向合并。
- 操作转换（0perationaI transformation）：Etherpad和Google Docs等协作编辑应用背后的冲突解决算法。
复制的拓扑结构
不同拓扑结构对于容错、是否有中心、复制成本各有优缺点，这里就不展开说明了。
无主节点复制
放弃主节点，允许任何副本直接接受来自客户端的写请求。
节点失效时写入数据库
当节点失效时，用户不关心自己写入的节点是否发生变化，更不需要进行节点提权等操作。
用户向多个节点同时发起写请求，只有超过半数的节点写入成功，则此请求成功。
- 读修复：用户读取时决定值（通过半数以上的节点返回来确认值）
- 反熵：后台进程自动查找节点之间的差异并修复。
但上面的例子，如果有多个用户同时写入则可能出现如下问题：
处理并发写入
- 最后写入胜利法（last write wins）
由于每个客户端在写入时都不会互相感知，且由于网络关系，无法区分那个写入一定在哪个写入之后。
可以强制对所有的写入进行排序：
为所有写请求附加一个时间戳，然后选择最新即最大的时间戳，丢弃较早时间戳的写入。
以上思想，在zookeeper，raft，各种分布式一致性问题中都有借鉴。
- happens-before关系和并发
happens-before：B的操作明确依赖A，具有先后关系
并发：A和B的操作“同时”，且完全独立的，互相不感知
为更好地定义并发性，我们并不依赖确切的发生时间，即不管物理的时机如何，如果两个操作并不需要意识到对方，我们即可声称它们是并发操作。
两个客户端同时多次向一个购物车中添加值，且相互不感知。
对于单个客户端，每次添加操作是有前后依赖关系的（happened-before），对于两个客户端之间，是“同时”发起的添加操作（并发）
服务器具体处理步骤如下：
- 服务器为每个主键维护一个版本号，当主键新值写入时，递增版本号，并将版本号和值一起保存。
- 当客户端读取主键时，服务器将返回所有（未被覆盖的）当前值以及最新的版本号。且要求写之前， 客户必须先发送读请求。（读取最新值）
- 客户端写主键，写请求必须包含之前读到的版本号、读到的值和新值合并后的集合。写请求的响应可以像读操作一样，会返回所有当前值，这样就可以像购物车例子那样一步步链接起多个写入的值。
- 当服务器收到带有特定版本号的写入时，覆盖该版本号或更低版本的所有值（因为知道这些值已经被合并到新传入的值集合中），但必须保存更高版本号的所有值（因为这些值与当前的写操作属于并发）。
整体逻辑有点像kafka集群的值是否写入成功逻辑，如果同步指针追上了的值，才算写入成功。这里只不过是相反的，每次写入都删除当前写入依赖版本号之前的所有版本。（算是MVCC的一种体现）
有依赖关系的值可以覆盖，并发的值需保存多份。可以保证并发写入的数据不会丢失
第六章、数据分区
分区通常与复制结合使用，即每个分区在多个节点都存有副本。这意味着某条记录属于特定的分区 ，而同样的内容会保存在不同的节点上以提高系统的容错性。
键-值数据的分区（常见的分区方式）
分区的主要目标是将数据和查询负载均匀分布在所有节点上。如果节点平均分担负载，那么理论上10个节点应该能够处理10倍的数据量10倍于单个节点的读写吞吐量。
基于关键字分区
为每个分区分配一段连续的关键字或者关键字区间范围。
每个分区可以按照关键字排序保存（LSM-Trees）。这样可以轻松的支持区间查询。
缺点：某些访问模式会导致热点。如果数据按照每天一个分区，每天所有的写入都会在同一哥分区，会导致单个分区负载过高，其他分区一直处于空闲状态。
基于关键字hash值进行分区
一个好的hash函数可以处理数据倾斜并使其均匀分布。
基于一致性hash的分区方式，可以进行高效的查询，但是却使数据丧失了有序性。
有些数据库采用hash分区的数据库直接禁用范围查询、或者把查询语句发送到所有的分区上。
- Cassandra的折中方案
声明一个由多列组成的符合主键。多列主键的第一部分用于hash分区，其他列用于对sstable的排序。（可以支持对于其他部分的区间查询）
负载倾斜和热点
基于hash的方法可以减轻热点，但无法做到完全避免热点。一个极端的情况是所有的读/写操作都针对同一个关键字，最终所有的请求都会被路由到同一个分区。
在社交媒体网站上，一个名人发布了热点事件，出现了大量相同关键字的写操作。此时hash起不到任何帮助，相同id的hash值相同。
- 一种无奈的解决方案
如果某个关键字被认定为热点，就在关键字的开头或者结尾添加一个随机数。只需一个两位数的十进制随机数就可以将关键字的写操作分布到 100 个不同的关键字上，从而分配到不同的分区上。
缺点：但之后所有的读操作都需要额外的工作，必须从所有100个关键字中读取数据然后进行合并。因此通常只对少量关键字做随机数才有意义。
分区和二级索引
二级索引通常不能唯一标记一条数据，而是用来加速特定值的查询。
二级索引不能规整的映射到分区中。
基于文档分区的二级索引
每个分区完全独立，各自维护自己的二级索引，且只负责自己分区内的文档而不关心其他分区中的数据。文档分区索引也被称为本地索引，而不是全局索引。
- 二级索引的查询
如果想要查询特定颜色的车使用二级索引，需要将查询发送的所有的分区，然后合并所有返回结果。（可以采用并行查询）
基于词条的二级索引分区
对所有的数据构建全局索引，而不是每个分区维护自己的本地索引。为了避免成为瓶颈，不能将全局索引存储在一个节点上，否则就破坏了设计分区均衡的目标。全局索引也必须进行分区，且可以使用与数据关键字不同的分区策略。
优点：查询足够高效，且不需要把查询分配给所有分区然后聚合，客户只需要向包含词条的分区发送读请求。
缺点：写入速度较慢且非常复杂，单个文档更新时，里面可能会涉及多个二级索引，二级索引的分区又可能完全不同甚至完全在不同的节点上，会引入显著的写放大。
由于二级索更新需要一个跨多个相关分区的分布式事务支持，写入速度极慢。因此大部分数据库都不支持同步更新二级索引。对全局二级索引的更新往往是异步的。
分区再平衡
当增加节点时，如何将之前的数据进行再平衡。
- 分区再平衡想要达到的效果
- 平衡之后，负载、数据存储、读写请求等应该在集群范围更均匀地分布。
- 再平衡执行过程中，数据库应该可 继续正常提供读写服务。
- 避免不必要的负载迁移，以加快动态再平衡，井尽量减少网络和磁盘IO影响。
动态再平衡策略
- 为什么不推荐使用取模
如果频繁的增加节点，会导致大量的数据频繁的迁移，大大增加了再平衡的成本。
- 固定数量的分区
- 创建远超实际节点数的分区数，然后为每个节点分配多个分区。
- 如果集群中增加了一个新节点，该新节点可以从每个分区上匀走几个分区，直到分区再次达到全局平衡。
- 被选中的整个分区会在映射节点之间迁移，但分区的总数量仍然维持不变，也不会改变关键字到分区的映射关系。（不需要像取模一样对每个key重新计算分区值）
- 唯一需要调整的是分区与节点的对应关系。调整可以逐步动态完成。在此期间，旧的分区仍然可以接收读取请求。
- 动态分区
当一个分区的数据量增长超过一个阈值，就会被拆分成两个分区，每个承担一半数据量。
如果大量数据被删除，且分区缩小到某个阈值，则将其相邻的分区合并。
HBase 通过HDFS分布式文件系统来实现分区文件的传输
- 按节点比例分区
使分区数与集群节点数量成正比，每个节点都有固定数量的分区。当节点数不变，每个分区的大小与数据集大小保持正比的增长关系；当节点数量增加，分区则会变小。大量的数据需要大量的节点来存储，这种方式可以使每个分区大小保持稳定。
请求路由
当客户端发送请求是，如何知道应该连接哪个节点？其实就是一个服务发现问题。
几种常见的路由策略
- 客户端连接任意节点，有节点把这个请求转发到正确的节点，再返回给客户端。（redis）
- 将所有客户端的请求都发送到一个路由层，路由层负责把请求转发到对应的分区节点上。路由层本身不处理请求，只负责负载均衡。（nginx）
- 客户端感知分区和节点关系。客户端可以直接连接到目标节点，而不需要其他中介。（springcloud注册中心的做法）
做出路由的组件，需要知道分区和节点的关系，以及变化情况。
大部分数据系统通过zookeeper来维护分区和节点的映射关系。一旦分区发生变化，zookeeper主动通知路由层来保持最新状态。
关于IP地址的变化，可以借助机器自己的DNS就可以了。
并行查询执行
查询优化器会把复杂的查询分解成许多执行阶段和分区，以便在集群的不同节点上并行执行。尤其是涉及全表扫描的查询操作，可以通过并行执行获益颇多。
第七章、事务
深入理解事务
ACID的含义
我之前多次记录过关于ACID的文章，对于ACID等详细说明推荐看我在凤凰架构里记录的文章。
不符合ACID的系统被称为BASE，基本可用（Basically Available），软状态（Soft state）和最终 一致性（Eventual consistency)。
原子性
多线程编程中，如果某线程执行了原子操作，这意味着其他线程是无法看到该操作的中间结果。只能处于操作前和操作后的状态，而不是两者之间。
在ACID中，多线程访问相同变量是由隔离性来保证的
ACID的原子性：在出错时中止事务，并将部分完成的写入全部丢弃。（可随意中止性，从而达到可重试的目的。）
一致性
ACID的一致性：对数据有特定的预期状态，任何数据更改必须满足这些状态约束（或者恒等条件）。（贷款系统中，贷款余额应和借款余额保持平衡。）
原子性，隔离性和持久性是数据库自身的属性，而ACID 中的一致性更多是应用层的属性。
应用程序可能借助数据库提供的原子性和隔离性，以达到一致性，但一致性本身并不拥于数据库。
字母 其实并不应该属于ACID
隔离性
ACID的隔离性：并发执行的多个事务相互隔离，它们不能互相交叉。
相互交叉其实有两个表现，下面是mysql对于两个场景的措施
- 读取：查询到其他事务可能在使用的变量。（通过MVCC快照读这种弱隔离性来实现）
- 修改：修改相同的变量（通过锁机制，保证一个变量无法被两个线程修改）
持久性
对于单机程序，持久性表示数据已经写入了非易失的存储设备（如硬盘）
对于支持远程复制的数据库，持久性意味着数据已成功复制到多个节点。
数据库必须等到这些写入或者复制完成之后才能报告事务成功提交。
弱隔离级别
关于mysql不同隔离级别的实现，已经不同级别的锁实现可以看我的这篇文章。
隔离是假装没有发生并发，可串行化隔离意味着数据库保证事务的最终执行结果与串行执行结果相同。
可串行化会严重影响性能，而许多数据库却不愿意牺牲性能，因此更多倾向于采用较弱的隔离级别。它可以防止某些但并非全部的并发问题。
读-提交
- 读数据库时，只能看到已成功提交的数据（防止脏读）
- 写数据库时，只会覆盖已成功提交的数据（防止脏写）
- 防止脏读
脏读：一个事务看到另一个事务尚未提交的内容。
如果事务需要更新多个对象，脏读意味着另一个事务可能会看到部分更新，而非全部。
如果事务发生中止，则所有写入操作都需要回滚。
- 防止脏写
脏写：两个事务同时修改相同的值，一个事务把另一个事务未提交的值修改了。
读已提交解决脏写的方式是一个事务等待另一个事务提交后，才能修改另一个事务已经修改了的值。（利用锁）
如果事务需要更新多个对象，脏写会带来非预期的错误结果。
多事务的不同写入顺序导致结果不一致。
- 实现读-提交
防止脏写：
数据库通常采用行级锁来防止脏写：当事务想修改某个对象（例如行或文档）时，它必须首先获得该对象的锁；然后一直持有锁直到事务提交（或中止）。如果有另一个事务尝试更新同一个对象，则必须等待。
防止脏读：
不能利用锁来解决脏读，因为长时间的写事务会导致许多只读的事务等待太长时间，任何局部的写入都会扩散进而影响整个应用。
对于每个待更新的对象，数据库都会维护其旧值和当前持锁事务将要设置的新值两个版本。在事务提交之前，所有其他读操作都读取旧值；仅当写事务提交之后，才会切换到读取新值。