光与影的个人博客

基于Raft的Sharded KV 数据库实现

项目来自于MIT6.824分布式系统的结课大作业，实现代码已上传 github仓库，该博客为项目的总体框架总结，省略了大量的实现细节和代码，细节总结可参考 MIT6.824实验总结

该项目实现目标为一个分布式容错的简单KV数据库，系统主要的功能点可以总结为：

1. 提供包括put(key, value), append(key, value), get(key)的基本kv数据库功能
2. 基于Raft共识算法的多服务器备份，实现一致性备份存储，实现了系统容错功能
3. 基于Raft日志的WAL机制以及系统快照机制，允许系统在失效后通过日志重新执行、加载快照等，快速恢复数据
4. 通过数据分片和多复制服务器组存储方式，实现了系统的高并发访问性能
5. 支持存储服务器的动态配置，即可以动态的增加删除存储服务器

MIT6.824中共设计了四个实验，主要内容是一个分布式kv数据库。

1. mapreduce分布式实现
2. raft实现
3. 基于raft的kv数据库实现
4. Sharded KV数据库实现

Golang并发控制总结

写在开头：最近用go做MIT6.824课程作业时，涉及到大量基于golang的并发控制，但是由于不熟悉golang语言以及相关并发控制手段，导致出现了大量的bug，影响了实现进程，因此产生了总结学习golang并发控制的想法

目前大厂的后端开发大量的从java转向go，很大一部分原因是由于go所具备的高并发、高性能、容易开发等性质，可以说go并发控制是学习go内容中最为重要的一部分（java并发我都没学会，直接学go，看出我的诚意了吧），下面的总结学习主要基于golang官网的Effective Go的cocurrency章节。

分布式事务总结

要理解分布式事务首先要明白事务是什么，从单机事务的理解迁移到分布式事务，下面从两个角度总结单机和分布式事务

1. 单机事务 vs 分布式事务
2. 如何通过并发控制保证单机分布式事务的隔离性

单机/分布式事务

事务作为数据库系统读写操作的高层抽象，代表了数据库的基本操作。一个正常提供服务的数据库系统，其事务必须满足ACID四个性质，其中CI两个性质相互关联，是后续课程研究的重点。

1. Atomic（原子性）：每个事务被看作一个不可分割的单元，要么完全成功要么完全失败，不存在两者的中间状态。数据库系统必须保证任意时刻下事务的原子性
2. Consistency（一致性）：一致性是指数据库满足某种预先定义的约束，任何数据库的操作都必须满足一致性，即从一个满足一致性的状态转移到另一个满足一致性的状态（例如：转账事务要满足转出和转入账户总金额不变）
3. Isolation（隔离性）：一系列并发进程的执行导致数据库的状态改变和按照某种线性顺序执行的状态改变相同（实际上这是serializability的定义）
4. Durable（持久性）：事务一旦提交，其对数据状态的改变不会因为意外事件的发生而丢失

分布式事务可以看作事务+分布式环境，即一个执行范围跨越多个通过网络连接的不同主机的事务，分布式事务既然是事务，同样要满足ACID性质，但是由于分布式环境的复杂性，原有的事务性质保证手段在分布式环境下需要进行调整和新的设计。

Spark:分布式容错的内存计算框架

Resilient Distributed Datasets: A Fault-Tolerant Abstraction forIn-Memory Cluster Computing

Spark是目前大数据领域较为火热的批处理框架之一（也支持流处理），经过论文阅读，不难发现Spark的核心原理并不复杂，通过简单的抽象，有效的解决了内存计算问题，我想这就是Spark流行起来的原因之一，如果要理解Spark，最关键一步的是理解RDD这一抽象内存模型。

RDDs（Resilient Distributed Datasets）

Spark中将计算操作的基本内存数据单元抽象为一个只读、分区的数据集-弹性分布数据集（RDD），将一次Spark任务定义为RDD经过一系列操作不断变换状态的过程，如下图所示：

• 每一步操作将一个RDD转化为另一个逻辑上的RDD（例如map、filter、join等）
• 不同RDD之间通过操作链接起来，形成一个RDD转换父子关系链
• Spark通过记录RDD转化的父子关系以及操作类型，实现容错（在RDD丢失后，根据计算链重新计算）

系统中通过五个元信息定义一个RDD：一系列分区、一系列父RDD依赖、转化操作、元数据（分区放置、分区信息），依赖关系如下图，分为一对一（narrow）和多对一（wide）。

FaRM: 无妥协的强一致性分布式数据库

No compromises: distributed transactions with consistency, availability, and performance

从论文的名字就能看出微软对于自己这套分布式数据库系统的自信程度，强调自己在实现强一致性的同时，并不会妥协可用性和性能，然而深入论文就会发现，虽然确实实现了题目中的性质，但是很多机制局限于其实现条件，另外由于时间和能力有限，未能看懂论文中对于错误恢复部分的阐述，未来涉及到相关内容时再重新学习。

构建系统动机

FaRM的构建动机来自于目前数据中心内部硬件发展的两个趋势：

1. 基于RDMA（Remote Direct Memory Access）的快速网络通信技术：server之间进行通信时，不经过CPU，直接将数据写入到目标server存储区/拉取到本地存储区
2. 低成本非易失DRAM存储技术：直接将数据存储在DRAM中，通过单独供电，在断电时备份到SSD中实现非易失

在我看来，FaRM的高性能大部分原因来自于上部分阐述的硬件优势，除去优势以外，以上设计同样为FaRM带来了一定限制

• 无法实现跨数据中心分布
• 增加了分布式事务和消息传递实现的复杂性（这难道就是我看不懂错误恢复的原因？）

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的值

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