光与影的个人博客

Spanner：“真”分布式数据库

Spanner: Google’s Globally Distributed Database

Spanner作为Google开发的全球分布式数据系统，具备外部一致性、支持分布式事务、多副本容错等特性，相较于Aurora，更具“分布式”特征。

从何而来？

论文的intro介绍Spanner是从类似于MegaStore的基于BigTable的kv存储系统演化而来的，MegaStore虽然能够很好得解决大部分客户的数据存储需求，但还存在一部分问题

1. 对于关系模型的支持较差，难以支持复杂的、经常变化的模型
2. 无法在使用大范围副本的同时保证强一致性，并且支持分布式事务

针对以上问题，一个支持更强关系模式的多时间版本的数据库-Spanner诞生了。

Frangipani 分布式文件系统

Frangipani: A Scalable Distributed File System

Frangipani是20多年前发表论文中描述的一个分布式文件系统，之所以现在还要深度了解一篇这个“古老”的论文，是因为其中的一些设计思路值得我们学习和研究（不还是因为MIT6.824里要讲吗），Frangipani的设计出发点是要实现一个简单、方便扩展和管理的共享文件系统，在读论文时主要关注的点如下：

1. 如何在分布式环境下实现缓存一致性？
2. 如何实现分布式事务？
3. 如何在经常出错的分布式环境中，通过错误恢复实现容错？、

Amazon Aurora 云端分布式数据库

论文: Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Database

Amazon Aurora是亚马逊从2014年开始提供的一种云上关系型数据库架构，基于mysql的基础上改进而来，在实现传统关系型数据库特性的基础上，实现了事务吞吐量、错误恢复等性能巨大提升。

Amazon Aurora到来之前

要理解Amazon Aurora的设计原理，首先要了解一般数据库的事务执行流程；传统单机事务型数据库数据一般以B-Tree形式组织存储在硬盘上，并在内存中存储数据的缓存以加速访问/修改过程。以写事务流程为例，一般的事务执行过程如下：

1. 首先锁定要想修改的数据，防止其他事务修改
2. 在WAL（Write-ahead-log）中写入当前事务日志项
3. 根据操作修改缓存中的数据项
   • 修改前镜像+修改日志+修改后进行
4. 提交事务，等待特定的时机(缓存区满等)，再将缓存持久化到磁盘中

链式复制及其改进

写在前面：CRAQ还涉及到了服务器放置策略等内容，我目前阶段学习并不关心，所以没有深入了解

论文：Object Storage on CRAQ High-throughput chain replication for read-mostly workloads

本文主要提出了一种区别于主从备份容错方式的链式复制容错方式，通过将备份服务器组织链结构，实现数据的冗余备份。本文中的CRAQ(Chain Replication with Apportioned Queries) 是在链式复制（Chain Replication）的基础上改进而来的，两者针对对象存储系统设计实现（object-based storage system），对象存储系统主要包括一下两个操作原语：

1. write(objID, V)：更新某个obj关联的值
2. read(objID): 获取某个obj的值

对象存储只需要考虑修改读取特定对象的请求顺序，而并不需要考虑整个数据库，降低了保证一致性的成本

分布式消息中间件-ZooKeeper

线性一致性（linearizability）

线性一致性是指分布式系统面对网络延迟和系统故障保证不同分布之间的数据一致性，使分布式系统在客户端看起来就像一个没有副本的单机系统。

• 也成为 原子一致性（atomic consistency），强一致性（strong consistency），立即一致性（immediate consistency） 或 外部一致性（external consistency ）。

• 换一个角度：一旦新的值被写入或读取，所有后续的读都会看到写入的值，直到它被再次覆盖

线段树总结

学完树状数组，很难控制住自己不学线段树，线段树是一种可以在$O(logN)$ 时间复杂度内实现区间和单点操作的数据结构：

1. 单点修改/查询
2. 区间修改/查询

与树状数组的区别在于：树状数组只能执行 单点修改+区间查询 或 区间修改+单点查询 。线段树能够均能支持，但是复杂度的常数系数显著大于树状数组（ps:能用树状数组就用树状数组）

第二部分 提问题，找答案

这一部分主要提供如何从兴趣、专业领域中寻找研究问题，并寻找问题答案过程的建议和方法论。

从话题到问题

从感兴趣的话题领域到具体的研究问题是一个从大到小的过程

• 话题是广泛的，往往涵盖大量的信息和资料，沉浸在一个话题中搜索查找相关信息，虽然能够搜集大量的信息，然而这些信息大部分往往是没有任何用途的，因为缺乏重点，在读者眼里可能仅仅是堆放在一起的事实。
• 问题是从话题中产生的，根植于话题的。一个好的问题的好的答案答案能够在一定程度上推进整个领域往前发展

然而疑问（question）并不等于问题（problem）

• 一个好的问题是具有实际价值的”疑问“，解答这个问题能给我们带来一些东西（eg：解决某个工程难题，提升程序运行效率等等）
• 通过问我们自己:”不解决这个问题会怎样’’来区分区分疑问和问题的方式，如果答案是”不会怎么样 so what?”，那么这个问题就不应该成为我们的研究问题

写在开头

开头废话：终于摆脱了没有前途的项目开始写论文了，虽然写论文不一定比做项目更有前途，但是可以预计的是只要我认真干，达到毕业标准是没问题的，而我目前对于实验室工作的目标就是满足毕业要求，所以说捋起袖子，加油干吧。正好李沐出了这个如何搞研究的视频，我也跟着学一学，不止为了写论文，更多的是从写论文这个经历里，为未来工作中各种报告文档的书写留下一点可用的经验。

跟着李沐的课程学习搞研究的基本概念，主要的学习资料有

1. 李沐的研究的艺术B站视频
2. 研究的艺术中文版第四版

计划是先自己读一遍中文书的对应章节，再去看李沐的视频，加深印象，下面是第一部分内容。

研究、研究人员、读者

什么是研究

什么是研究？

• 为了回答/解决某个问题搜集信息就是研究

• 日常生活中我们经常有类似的场景（例如百度小米的CEO是谁），只是我们并不会把这个过程规范化，结论文档化

为什么要把研究内容写下来？

• 为了方便记忆（俗话说得好：好记性不如烂笔头）
• 为了增进对于研究内容的理解。在梳理论据，描述论点的过程中，会加深自己对于相关内容的理解
• 为了检验自己的思想。只说是无法证明自己思想的正确性，写在纸上，通过论据论述，数学公式的证明，为自己的思想进行强有力的证明

分布式共识算法-Raft

Raft是基于Paxos改进的共识算法，其最开始的设计目标即为容易理解且容易实行，所以相较于Paxos学起来更容易（确实比Paxos容易，但我还是看不懂啊）。

Raft中定义了三种角色：

1. Leader：唯一的leader，负责与Client交互，在其他follower上备份log日志。
2. Follower: 多个Follower，接收Leader的日志备份请求，当Leader出现问题时，选举成为新的leader。
3. Candidate: 当Follower认为Leader失效时，Follower状态转换为Candidate，进行Leader的竞选。

Raft中只包括两种类型的RPC消息

1. RequestVote RPC：参与选举的Candidate发送的选举消息
2. AppendEntries RPC: Leader向Follower发送的添加日志信息

分布式共识算法-Paxos

共识算法目的是通过一系列通信约束，使得依靠不可靠通信网络上的不同结点之间能够通过算法得到一致的结论（区别于分布式一致性这一概念）,共识算法是实现state machine replication 的基础，后者是分布式系统中较为重要的备份容错算法策略

分布式CAP

一个分布式系统只能满足一下三条性质中的两条

1. Consistency(一致性)：每个客户端的读操作均能读取到最近的写入内容或者返回错误
2. Availability(可用性): 客户端的每个请求均能收到非报错响应（回复不一定正确即不一定保证C）
3. Partition Tolerance(分区容错性)：不同结点或分区之间的网络故障不会影响系统的正常运行

为什么说分布式系统只能保证其中两条？

1. 分布式系统由于系统结点/分区分布于不同的网络环境，通过网络进行通信，不可避免地会出现结点由于网络故障下线问题，为了系统的可用性，必须保证Partition Tolerance
2. 当部分结点出现网络故障时，面对客户端请求，系统有两种处理方式
   • 回退操作，相当于保证了C但舍弃了A
   • 继续执行操作，由于部分结点下线，此时执行操作无法保证C，但是保证了A

单机系统由于不会出现分布网络失效，所以也就不需要P，可以同时保证CA