DDIA Chapter 5-Replication（1）

再不发不行了，先发为敬，明天在继续读后面的

总的来说还是上课讲的一套东西,主要是工业界的案例比上课多一些吧

一个奇怪的栏目，每日水题。就是出一份题解描述思路，提升文字能力

每日水题Leetcode - 862. Shortest Subarray with Sum at Least K

先做前缀和,显然一段的和sum(l,r) = sum(r)-sum(l-1)

- 对于每个右端点r,找到最大的满足sum[l]

因为要找最大的,所以如果sum[r]

遍历右端点r,通过查找找到最大的l使得sum[r]-sum[l]>=K(如果存在),更新答案(找最小的),加入单调队列.

时间复杂度: O(nlogn)

感想: 二分真难写,早知道用bisect了

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/description/

前言

书名: Designing Data-Intensive Application

做为本时代数据库操作系统分布式系统导论，这书很有含金量。

前段时间由leader发起的读书会活动，志在找回天生骄傲(大误~) 。

虽然质量层次不齐，但是每次leader分享的东西都有含金量(且好玩)的。

这种终于轮到我讲第五/六章，先来提炼一下内容与问题。

很可能是计算机工程实践中的终极问题，这一章也不例外。

基本概念

主从复制

主从复制，是基于leader的复制：

主库， 又称为领导者，是特殊的。只有主库接受写操作。

从库， 又称为追随者，热备份等。从库只接受读操作。

主库与从库间通过变更日志来通信，从库将自己更新到主库的状态。

主从复制有leader，相应的就有这个怎么制定leader的问题。

同步与异步

不论复制是同步发生还是异步发生，在基础设施≈网络+读写出现故障时，都会面临一致性问题与可用性的：

同步: 单点不可用时，面临整体可用性风险

异步: 写入失败时，一致性风险

半同步

在两者之外，还有一个半同步，指一个从库为同步，其余从库为异步的配置方式。

这个从库是可替换的，原来的挂了就换一个。这可以保证你至少有两份最新的数据。

我们认为这个从库是平凡的。

所以正常情况下，这个从库完成意味着半数以上的从库更新完成。

问题来自何方

故障

大数定理保证巨大的系统总是always在面临各种单点故障。

面临故障时，如何应对故障与如何在故障后恢复是绕不过去的问题。

网络

网络不会永远稳定，总会有出现延迟的情况。

延迟是客观存在的标量，我们这里的延迟指的是超过期望延迟的事件

而延迟导致的两个典型问题是：

丢包: 一条信息完全丢失了，需要重传机制与容错机制。

乱序: 信息没有丢失，但是顺序乱了，需要对校验机制与对因果律的容错机制。

异地延迟

很明显，当异地状态下，网络信号不可能是瞬时到达的。

光一秒绕地球七圈半，有0~66ms的基于光速的延迟是躲不掉的。

重要指标

复制与分区是分布式的入口，由此引入了所有的分布式问题。

一致性Consistency

各个节点上的数据应该是一致的，满足约束的。

一致性有许多具体的要求：

强一致性Strong一致性: 数据更新后，所有节点的读操作立刻**获得最新的数据。

弱一致性Weak: 其他节点能读到某一操作对系统特定数据的更新需要一段时间，我们称这段时间为不一致性窗口。

最终一致性Eventually一致性：我认为最终一致性是一个魔法概念， 其实就是在某种case下保证数据最终弱一致。

这里的case有:

因果关系: 写后读一致，一致前缀读，对会话一致性。

时序关系: 单调读一致，单调写一致。

因为我们的时间轴是单向的，所以因果关系以时序关系来体现。

可用性Availability

操作可以在一定时间内返回结果成功或失败。

更强的可用性要求更短的响应时间和更普遍的成功响应操作。

分区容忍性Partition Tolerance

对数据分区的容忍性。越能容忍数据分区，就越能分区，相应的可伸缩性，性能等指标也会自然而然的上升。

单主复制

场景

单主复制是最简单常见的主从复制场景。

基于主库的复制要求所有写入都由单个节点处理，但只读查询可以由任何副本处理。对于读多写少的场景，会创建许多从库：将读请求分散到从库上，减少主库的负载。并能向最近的副本发送读请求

复制的实现

如何添加从库

假如有了新的节点加入，需要拷贝数据。

我们显然不能通过锁定数据库的方式来，这会导致写服务的停机。

这就需要提供一致性快照，一个能描述数据库现在状态的集合。

基于语句复制

主库记录下每个执行的写入语句，并将该语句日志发送给其他从库。

风险在于，如果语句是有外部依赖或副作用的，这种方式往往会失效：

非确定性函数，每次调用生成不同的值

自增列与其他依赖顺序或依赖外部的行为

基于传输

预写式日志Write Ahead Log

第三章存储与检索中讨论了存储引擎如何在磁盘上表示数据，我们发现通常往往是追加到日志中。

对于日志结构存储引擎SSTables与LSM-tree，日志是主要的存储位置。

对于B树，在复写单个磁盘块之前，会先写入预写式日志Write Ahead Log。

在这两种情况下，日志都是包含全部数据库写入的仅追加数据，可以使用完全相同的日志在另一个节点上构建副本与同步数据。

基于WAL的复制协议往往需要数据库的版本匹配，因为不同的版本意味着不同的存储格式细节。

基于逻辑日志复制

复制与存储引擎使用不同的日志格式，使得复制日志从存储引擎内部分离出来.提供更好的的兼容性，可以应用在不同的版本甚至存储引擎上。

这种复制日志被称为逻辑日志，与存储引擎的物理数据表示区分开来。

逻辑日志通常是以行粒度描述对数据库的写入记录：

对于插入的行，日志包含全部数据。

对于删除的行，日志包含足够的信息来唯一表示已删除的行(通常是主键，没有主键时则记录全部列的值)。

对于修改，类似与删除，但是还要记录更新列的新值。

修改多行的日志会产生多个这样的日志记录，最后跟着一条事务已提交的记录。

基于触发器复制

之前的复制方法都是基于数据库系统实现的，不涉及应用层。但是如果你需要更高的灵活性，则需要在应用程序层解决复制问题。

处理节点宕机

处理从库失效: 追赶恢复

通过日志机制，我们需要知道从库执行到哪一条日志，在服务恢复后补上中间的数据变更。

处理主库失效:

故障转移failover

提升一个从库为新的主库，然后让所有节点知情就可以了。

自动与手动

一般来说，可用性需求越高，手动转移就越难实现。

可用性需求在99.9%以上时(年宕机时间小于8小时)，手动切换就已经需要专业运维团队24小时oncall，成本非常高。

可用性需求在99.99%以上时(年宕机时间小于1小时)，就不可能手动切换。

处理的基本流程

确认宕机

如何确认是真的宕机是非常复杂的问题。

一般而言，我们抽象的使用超时Timeout来确认服务不可用，这一定会有误差。

选择新主库

我们可以通过控制器节点来指定新的主库。

让机器自行选举一个新的主库是一个共识问题，将在第九章一致性与共识中讨论。

启用新主库

客户端需要将写请求发送给新主库，这可以通过第六章分区的请求路由来做到。

引发的问题

没有完全同步的写入操作怎么处理？

一般是直接丢弃，但是这显然打破了对数据持久性的期望

外部依赖怎么同步?

外部依赖的量一定要被同步过去，不然会导致一致性问题

作者举了一个的例子：

自增ID被外部的缓存Redis依赖，在替换了主库后，自增ID却没有同步更新。

导致数据不一致， 用户从缓存Redis中拿到了不该拿到的数据。

脑裂问题怎么处理？

脑裂: 多个节点都认为自己是主库的情况，这会导致两者都接受写操作，却没有冲突解决机制，导致数据丢失或损坏等一致性问题。

冲突解决机制参考下文多主复制。

屏蔽fencing机制：检测到两个主库节点时，关闭其中一个。一般需要第三方仲裁，引入了复杂性。

爆彼之头: 屏蔽机制设计出现问题，导致两个节点互相关闭了对方。

一个设计是，由一个主库向另一个发送关闭的指令，两者同时向对方发导致两者最终都乖乖关闭了。

超时时间Timeout如何配置？

超时时间太短，意味着更频繁的故障转移failover。

在高负载或网络波动时，不必要的故障转移failover导致系统整体可用性进一步下降。

超时时间太长，意味着不可用时间更长，恢复时间更长。

这些问题没有简单的解决方案，所以运维团队往往更愿意手动执行故障转移failover。

第八章分布式系统的麻烦和第九章一致性与共识会更深入的讨论这些问题。

复制延迟问题

在大的系统中，随时都会有单点故障，完全同步的配置是非常不可靠的。

而异步复制到从库时，因为延迟的存在，可能会看到过时的信息，导致出现明显的不一致。

这种不一致只是一个暂时的状态 - 如果停止写入数据库并等待一段时间，从库最终会赶上并与主库保持一致， 这种效应被称为最终一致性Eventually Consistency。

最终一词故意含糊不清，从库落后的程度是没有限制的。在实践中，我们通过具体场景来描述最终一致性。

写后读

场景: 用户向主库写入了新数据，立刻从从库去读数据，因为还没有复制到从库上，所以用户发现刚写入的数据没了。

写后读一致性: 写后读一致提供的保证是，用户总可以看到自己提交的更新.而不保证别人的更新。

实现手段

读用户可能修改过的内容时，从主库读.。

例如: 社交网络，从主库读自己的档案，从从库读别人的更新。

客户端记录最近写入的时间戳。

系统确保从库为用户提供查询时， 该时间戳前的变更都已经被更新。

如果当前从库不够新，则可以从另一个从库读，或者等待从库追赶上来。

时间戳可以是逻辑时间戳或实际时间戳(这时时间同步就是问题)

单调读

场景: 主库写入一条信息，用户向两个从库查询两次，第一次查询的从库更新了这条信息，第二次查询的从库没有更新这条信息.看上去就像时间倒流了一样

单调读一致性: 比最终一致性更强的保证，保证了读取数据时，不会看到时间后退.

实现手段

确保每个用户总是从同一个副本进行读取(一致性哈希)

副本失效时的转移就更复杂了

因果律因果関係

场景: 两个写入间有明显的因果关系时序

一致前缀读consistent prefix reads：如果一系列写入按某个顺序发生，那么任何人读取这些写入时，也会看见它们以同样的顺序出现

实现手段

如果从库总是以相同的顺序应用复制来的写入，则读取总是会看到一致的前缀，所以这种异常不会发生。

在分区Partitioning的情况下，不同的分区独立运行. 这时不存在全局写入顺序。

一个解决方案是，保证因果相关的写入写入相同的分区（一致性哈希）

显式的跟踪因果依赖的关系，将在下文的检测并发写入中讨论。

分布式事务

事务: 数据库通过事务提供强大的一致性保证

单点事务存在了很长时间，在走向分布式数据库复制与分区时，因为在性能与可用性上的代价太高，很多系统都放弃了事务.

DDIA的第七章事务与第九章一致性与共识讨论了事务的话题，并讨论了一些代替机制

未完待续...