1.概览
1.1 主要创新点
企业上云的大趋势不断促进云原生数据库的发展，用户对云原生数据库，大概如下要求：持久性、高可用、随着workload和数据量弹性扩展、高性能低成本、按需付费等。华为Taurus作为云数据库市场后起之秀，采用Aurora存储计算分离的方式，吸收Socrates availability与durability分离的思想，支持与前两者相同的云数据库特性：多个读节点、快速recovery、共享存储节点、支持扩展到128T等等。虽然功能都差不多，但是Taurus在如下方向做出了进一步创新。
他们分析了log与pages读写区别：
- Log：主要作用是durability，多副本间需要强一致保障，顺序读写。高频写，因此写性能很关键；低频读（恢复时），读性能不用过多关注。
- Pages：随机读写。读性能很关键，写性能次要。
鉴于以上特征，Taurus 将 Log 与 Page 的存储分开（Log Stores 和 Page Stores），依据它们各自的特点，做针对性的读写、复制与数据分布的优化。由于 log 读请求不频繁、log 与 log 之间无依赖，某条 log 不需要写到特定的 Log Store Server，写到任意可用 Log Store 即可。而 Page 的更新依赖于前一个版本的 Page ，因此 Page 需要存储在特定已知的 Page Store 方便访问。
在不影响性能和强一致性的前提下，分别针对Log Stores 和 Page Stores，设计了一套低成本的复制与同步算法来保证高可用，这里的低成本是指使用更少的replication（不超过durability的要求，一般3副本足矣）。
Taurus这里宣称：
With only 3-way data duplication required for durability, Taurus achieves availability comparable to the 6-way quorum replication used by Aurora and better than the 3-way quorum replication used by POLARDB.
个人理解：Aurora 6 副本是考虑跨 region 高可用，Taurus 没提这个能力。
Taurus 将 Log 与 Page 分开存储，依据其特点，应用不同的 replication 和 recovery 算法，带来如下优势：
（1）高可用，基于Quorum的写，需要在固定个数个存储节点上持久化 log 后方能返回，为保证搞可用，副本数需要较大（例如 Aurora 6 个），而 Taurus 写高可用的保证，不依赖Quorum，只要有三个可用的 Log Store 就能写，如果写三个副本失败，则立即重新选三个副本写，只要系统中有超过3个 Log Stores，写可用性就能保证。Taurus集群中往往存在成千上百个 Log Stores，因此可达接近 100% 的可用性，且每份 Log 只存三份（高可用、低成本）。
（2）性能优化。Log 和 Page 分离能提升性能，相互之间没有 IO 资源之间的竞争；异常情况下写请求也很快，只要一个 Log Store 比较慢或者网络丢包了，写请求会寻找新的 Log Store 写；相较于与 Socrates 读和写的关键路径，最多只需要一次网络请求（写 log 或 读 Page）；Page Store 也采用 append-only write（论文中说性能提升2-5倍）。
1.2 与现有系统的对比
The Taurus replication algorithm provides higher availability for writes than the quorum replication used by POLARDB and Aurora, and uses only three data replicas to minimize storage costs。
Taurus separates the database system into two physical tiers compared to Socrates’four-tier architecture. This results in lower network load and latency.
In order to reduce read latency, Socrates caches all pages on local storage at the Page Server tier. In contrast,
Taurus does not have intermediate tiers. It does not require caching as data can be quickly retrieved from storage devices with a single network hop.
2.系统总览
2.1 云上使用传统数据库的面临的问题
以 MySQL 为例，redo+undo, binlog, pages 所有的数据都需要通过网络传输到存储层，浪费网络带宽。存储层本身有三副本保证高可用，MySQL再部署三副本，九副本浪费存储资源。主备 binlog 同步，replica 需要再次执行一遍所有 update，浪费计算资源。增加读节点需要拷贝一遍全量数据，慢且代价大。
2.2 Taurus总体架构
4个逻辑组件（DB front end，Log Stores，Page Stores，Storage Abstraction Layer），2个物理部分（计算与存储层）。作者宣称2个物理组件与Socrates相比，减少了网络数据传输的总量与响应延迟（Socrates在大部分情况下，也只用一次网络通信吧？）。
DB front end：MySQL计算实例，负责与用户建立连接、优化执行查询、事务处理、生成Log等，也分为读写与只读实例。
Log Stores：负责（1）持久化日志，一个事务的日志持久化后即可返回用户；（2）供 replica 读取 log。master周期性地向 replicas 发送最新 log 的位置，提示 replica 读取相应日志。master还要负责向 Page Stores 发送 log。
日志在存储层的存储单位是Plog（定长，3 Log Stores 同步）。24 bytes长的 id 标识一个 Plog，当需要新建一个Plog 时，系统会选择3个 Log Stores 来保证可用性。log 在3个 Log Stores 都写成功了，才返回成功，如果有一个没响应，则标识写入失败，此 Plog 不再接受新的写请求，原有写请求将新建新的 Plog（在3个 Log Stores replicaction）。因此只要系统中含有超过3个健康的 Log Stores，写请求总会成功。实践中，集群往往包含成千上百个 Log Stores。写请求也因此非常快，一旦写失败，不会再原有的 Log Stores上重试，而是写到新的 Log Stores。
Log Stores 为只读实例提供读服务，为加速读取，新写入的 log 被缓存在内存（规则：FIFO），此外 recovery 时也需要读取 log 发送到 Page Stores。
Plog 分为两类：数据 Plog 与元数据 Plog。元数据 Plog 存储数据 Plog 元信息，并缓存在数据库实例内存中。
Page Stores：相应读写与只读实例的 Page reads 请求，其具备生成任何一个 Page 版本的能力，以响应数据库实例某个 snapshot 读请求。单个 Page Store Server 存储了特定的 Page，与 Log Store 相比，其面临的可用性挑战更高。
数据库每更改一个 Page，其版本会发生变化，一个 Page 的版本由 PageID 和一个 LSN 唯一标识。一个Page Server 存储管理了来自不同数据库的多个 Slice （10G），它不断地接收 log records 生成新版本的 Pages。
数据库实例通过 SAL （Storage Abstraction Layer）与Page Stores 交互，提供如下4个主要接口：
- WriteLogs is used to ship a buffer with log records
- ReadPage is used to read a specific version of a page
- SetRecycleLSN is used to specify the oldest LSN of pages belonging to the same database that the front end might request (recycle LSN)
- GetPersistentLSN returns the highest LSN that the Page Store can serve（返回的 所有 slices 的么？还是 所有 slices 中最小的？）
Storage Abstraction Layer： 为数据库实例读写 Log Stores 和 Page Stores提供接口。它还负责创建、管理、销毁 slices，并将 Pages 映射到相依的 Slices。有新 Page 生成，SAL会选择合适的 Page Stores 并创建新的 slice。
写 log 的过程，SAL会 group 一批 log （database log buffer），当 log 在三个 log stores 都持久化成功后，即可返回用户提交成功。SAL还需将 database log buffer 中的 log records 按照 slice 划分，缓存到多个 per-slice buffers，buffer满或超时后，这些 log 需要被发送到相应的 Page Stores。
SAL 维护了一个重要的全局变量 C(luster) V(isible) LSN，该 LSN 代表当前全局一致的最大 LSN，CV-LSN推进的两个条件：（1） database log buffer 里的 log records 持久化成功。（2）这些 log 对应的所有 pages（database log buffer 对应的多个 per-slice buffer flush成功），其三副本至少有一个已经 apply 成功。 CV-LSN的意义在于，SAL 保证 CV-LSN 及其之前的版本都是一致可读的。为了判断 CV-LSN 是否能推进的条件，SAL 需要维护database log buffers 和 per-slice buffers 之间的多对多关系。
3. Replication
3.1 写路径
1.事务执行产生 redo log。
2.通过 SAL 写到 PLog （64M，fixed），3个副本都写成功，则返回用户写成功。当一个 PLog 写满后，会依据 Log Stores 的存储和负责情况，选择3个，并产生新的 PLog，接受写请求。
3.返回写成功给用户。只要有3个以上可用的 Log Stores，写就一定会成功，鉴于实践中有成败上千的 Log Stores，可用性可在实践中达到100%。
4.持久化成功后，SAL将持久化的 log 分发到不同的 per-slice buffers，并发送到相应的 Page Stores（三副本）。发向 Page Store 的 buffer 包含 sliceID 和 sequence number， Page 可依据此检测空洞。
5.只要一个 Page Stores 返回成功，SAL 即可回收相应的 per-slice buffer 了。
6.Page Stores 副本之间通过 Gossip 协议交互检测并补全丢失的 log。
高可用的创新：
log可以存储在任意 Log Stores，只要三副本没有写成功，立即换三个 Log Stores。可用性几乎100%。相较于其他云数据库，Log也是写到特定的多个副本，如果超过一半跪了，Quorum就失效了。
Page 存储在固定的 Page Stores，只要有一个 Page Stores 收到 per-slice buffer 即可返回，三副本后台同步信息，这提高可用性，降低了延迟，SAL也因此减少了保存 buffer 的时长和重试发送的次数（相较于3副本都要 apply 成功）。
3.2 读路径
刷脏策略的改动：buffer pool 中某个脏页只有在所有相应的 log records 被写到至少一个 Page Store 后才能被evicted。否则需要再去 load 这个 page 时，没有 Page Store 能提供最新版本。
SAL 维护了每个 slice 对应的 latest log record LSN。读请求会携带上述 LSN，被路由到记录的响应延时最小的 Page Stores，如果该 Page Store 不可用或者缺少部分小于读请求携带 LSN 的日志，报错返回给SAL，SAL会重试另一个 Page Store，直到找到可以满足要求的 Page Store。
3.3 Log truncation
Log record 可以被清理的条件：log record 都已经写到 slice 三副本。Page Store 维护了每个slice persistent LSN，该 LSN 之前的 log 都已经收到了。
如果 track 每个 log 是否已经写到 slice 三副本，成本太高了。因此 Taurus 还是依赖 LSN 做 Log 回收。SAL 维护了每个 slice 的每个副本的 persistent LSN。所有 slices 的 persistent LSNs 里，没有被相应的 slice 三副本都持久化的，最小的 LSN 就是全局的 database persistent LSN（小于这个 LSN 的 log records 在相应 Slice 三副本上都已经持久化了），SAL 定期更新这个LSN（定期调用GetPersistentLSN ）。 SAL 还记录了所有 PLog 的 LSN 范围，如过 PLog 的 LSN 都小于 database persistent LSN，这个 PLog 就可以被清理了。该方式保证log records 总是持久化在至少3个节点（3个 Log Stores 或 3个 Page Stores）。
4. Recovery
4.1 Log Stores Recovery
Log Store 一旦不可用，其上的PLog 立即停止写服务，等待恢复。新写入选择新的 Log Stores 和 PLog。如果某 Log Store 长时间不能提供服务，将其剔除，并依据其上 Plog 的其他两个副本，选择 Log Store 重建新的PLog。
问题：写入的时候，是PLog写完一个再新建一个，还是同时起好几个 Plog 同时写？
4.2 Page Stores Recovery
1.一图胜千言，短期的宕机恢复，依据gossip协议补全日志。
2.如果探测到一个长期失败的实例，需要新建一个新 slice ，如果其它副本也不包含某个 log records，需要去 log stores 拿。
开始恢复的 slice 可以接受WriteLogs请求，但不能提供读服务。
新建的这个slice replica 1 通过 gossip 协议拿到了部分 log records，此时 persistent LSN 变成了1，SAL 检测到 Persistent LSN 回退，会从 Log Stores 拿相应的 Log records，根据前文描述的 Log records truncate 策略，这条日志肯定没有被删除。
3.仅仅检测 Persistent LSN 回退与否不够的，例如下例 。检测回退可以说是 fast path，SAL 还需定期检查 Flush LSN 与三副本的 Persistent LSN 的大小，如果Flush LSN > Persistent LSN，说明出现了空洞，此时需要借助 Log Store 来修补。
Taurus 支持成千上百个 Page Stores，由于 gossip 协议比较开销比较大，因此只让其在每30分钟执行一次。为减小对可用性的影响， SAL 会随时监控 Page Stores 的状况，如果某个 slice replica 的 persistent LSN 一直不推进（会影响 Log truncation），或者某个宕机恢复的实例 persistent LSN 短时间不推进，会触发 gossip 协议执行一次。如果 SAL 检测到某个 log record 三个副本上都没有，则从 Log Store 读取发送给 Page Stores。
4.3 SAL and database recovery
SAL 恢复的关键：所有的Page Stores 必须已经持久化了已经在 Log Stores 持久化的log records。SAL 从 database persistent LSN 开始扫 log，发现 Page Stores 有缺失发送一记，以上恢复过程是为了保证在接受新的请求之前，保证 Page Stores 上都是最新的数据，这样 load 到实例本地 buffer pool 的 pages 才是正确的。SAL 恢复完毕，实例就可以开始提供服务了，于此同时实例还可以后台处理一些 undo 的工作。
5. 只读实例
1.Master更新数据库本地 buffer pool，向 Log Stores 和 Page Stores 发送日志。
2.只读实例主动从 master 来取以下信息：（1）log 的位置信息；（2）更改了哪些 Slices。（3）最新更改的LSN（已持久化）。
3.依据上述信息从 Log Stores 读取 log records，更新本地 buffer pool。Log Stores 本地维护了 FIFO 缓存，几乎不需要磁盘I/O。
4.需要时，只读实例也需要从 Page Stores 读取 Pages。
An alternative design would be to stream all log records directly from the master to every read replica. However, this approach would result in the master becoming a bottleneck。Not only would the master need to spend CPU and memory transmitting log records, but its network interface may become a bottleneck。尤其是replica 很多的时候。
只读实例如何保证一致性：
1.内部结构一致性（physical consistency），单机数据库通过锁来保证 Page 分裂合并的原子性。如果 master 在分裂 B-tree 节点时，只读实例正在遍历这个节点，如何处理？显然维护分布式锁的代价太大。 Taurus的解决方案是：master 将 log records batch为一个个 groups，让 group 的边界为一个一致性点（一组 log records 作为整体回放完成后再一起可见？），只读实例以 group 为单位读取回放日志。只读实例回放完的最后一个 LSN 被称为replica visible LSN，它总是一个 group 的边界。 注意：只读实例不能让自己的replica visible LSN 超过 slice persistent LSN，这有可能导致只读实例回放了 LSN 为 10 的 log records，但其相应的 Page 所在的 slice persistent LSN 均是 8。当读请求另一个 Page，需要去 Page Store 的 Slice 拿时，由于Slice 上可能没有 LSN 为9 （或10）的 log records，导致读请求失败。（或者得等一段时间，slice persistent LSN 推进，这个延时就太大了）。
读请求首先会获取replica visible LSN，作为自己的 Transaction visible LSN（TV-LSN），只读实例需要 Track 最小的 TV-LSN，定期向Master 汇报，Master选取最小的发送到 Page Stores 作为 Recycle LSN，小于 Recycle LSN 的 Page 可以被 purge 掉了。
2.逻辑一致性（Logical consistency），即行级别的读写冲突处理，由于只读实例只有读服务，因此与Master只有读写冲突，因此需要保证只读实例的 MVCC 机制。日志里记录了事务的开始与提交，只读实例维护了 Active/Commited Transaction list，可以帮助做可见性判断，当一个事务的写不可见时，查上一版本的 Page。
6. Page Store
关键点：
1.Log Directory 记录Page Store上收到的所有 Pages 及相应的 log records ，是一个 lock-free 的hashtable，key是 Page ID，因此如果回放不及时，这个内存结构会撑爆内存。每个Slice都有自己单独的 Log Directory。会为写压力更大的slice，分配更大的内存。
2.选择回放的Page的策略：
（1）"the longest chain first"，选择 log records 链最长的 Pages 回放。这种方式频繁更新的 Page 回放优先级更高。但是可能导致 cold pages 长期得不到回放，它们的 log records 都被挤出 Log Buffer 了。这样的页面太多，Log Directory 占用内存过多，也会增加很多读 IO，重新捞回 log records。
（2）"log cache-centric"，只回放 Log Cache中 的log records，Log Cache 是 FIFO 规则的cache，回放顺序也是 FIFO，如果 Log Buffer 满了，会将新来的 log records 持久化到磁盘，等 Log Buffer 有空闲了再load进去。这就基本保证了 所有的 Log read 都是内存读。该方法的劣势是，buffer pool 命中率会降低。
