Lab2和Lab3构成基础分布式数据库的框架,实现多节点间的数据一致性,支持增删查改,数据同步和快照保存。然而,在实际应用中,当数据增长到一定程度时,若仍然使用单一集群服务所有数据,将会造成大量访问挤压到leader上,增加集群压力,延长请求响应时间。这是由于lab2和lab3所构成的分布式数据库的核心在于分布式缓存数据,确保在leader宕机后,集群仍然可用,并没有考虑集群负载问题,每时每刻,所有数据请求都集中在一台机器上,显而易见的,在数据访问高峰期,请求队列将会无比漫长,客户等待时间也会变长。一个非常直接的解决方法,就是将数据按照某种方式分开存储到不同的集群上,将不同的请求引流到不同的集群,降低单一集群的压力,提供更为高效、更为健壮的服务。Lab4就是要实现分库分表,将不同的数据划分到不同的集群上,保证相应数据请求引流到对应的集群。这里,将互不相交并且合力组成完整数据库的每一个数据库子集称为shard。在同一阶段中,shard与集群的对应关系称为配置,随着时间的推移,新集群的加入或者现有集群的离去,shard需要在不同集群之中进行迁移,如何处理好配置更新时shard的移动,是lab4的主要挑战。
MIT6.824-LEC07-Spinnaker
在lab3中我们实现了一个分布式键值数据库,提供容错机制,但是并未实现真正的分布式机制,因为在lab3键值数据库的架构中,所有与client交互的操作都放在leader这台服务器上,在实际应用中这会导致热点问题。所谓热点问题,就是有成千上万的请求并发的访问同一台服务器,使得这台服务器的等待队列非常长,导致响应时间延长。一个非常直接的解决方法,就是将访问分流到其他服务器上,减缓leader服务器的压力,但这有一个很严重的问题,如何保证其他服务器上的内容是最新的?而且这种划分方式,仅仅只能将读请求划分到其他服务器上,写请求仍然是必须放到leader服务器上保证写操作的顺序性,因此,如果有成千上万的写操作并发到来,还是会造成热点问题。
而这篇论文,就是提出了一个解决上述热点问题的方法(我看的论文少,不确定是不是本文第一个提出的,不过本文的内容的确是解决热点问题)。简单来说,假设键值数据库的键是一个集合,那么将这个集合根据某种方式(范围或者哈希算法)划分成互不重叠的几个部分,且这几个部分加起来等于集合本身(我记得有个专业术语,不过一时间想不起来),论文里将这些被划分的部分称为shrd。将这几个部分分别放到不同的集群上进行同步,每个leader/follower集群负责同步缓存处理分配到的shard,如此一来,可以将读写压力分流到不同的服务器上,提高集群的响应能力和容错能力。比如,假设键值范围是26个字母,spinnaker的做法,就是将这26个字母分配到26个的集群上,由这26个集群分别维护对应字母的读写请求。其实就是一致性哈希的想法。
CSAPP-lab5-Cache
本实验是CSAPP第三版配套实验中的第五个实验,对应书本第六章《存储器层次结构》,准确来说,是其中有关于缓存部分的知识。本实验共分为两部分:第一部分要求实验一个简易的缓存架构,接收一系列指令,模拟指令hit和miss的过程,如果指令miss,需要根据LRU策略来替换缓存项;第二部分是编写缓存友好的矩阵转置算法,要求矩阵转置尽可能多的hit缓存,减少内存访问的次数,这一部分很有意思,一共只测试3个矩阵,题目暗示可以针对每个矩阵做特别的优化。完成这一实验可以加深对缓存的认识,以及理解为什么同样是计算一个矩阵转置/乘积,有些算法就是比其他算法快,或者说,可以体会到矩阵加速运算的精髓所在。这里是我的完整实现。
MIT6-824-lab3-kvservice
在Lab2,我们完成了底层raft框架的建立,包括Leader选举、日志复制、状态持久化,在网络分区、不可靠网络等各种不稳定条件中保证多机环境下的日志一致性;并确保在节点宕机后,能从磁盘中读取持久化的日志重新执行,快速同步到集群中。Lab3A的任务,是在lab2的raft之上,多加一层收发指令的逻辑,构建kvservice层。kvservice分两部分,一部分是发起指令的client,另一部分是负责处理、同步和执行指令的server,server将收到的client指令作为新日志传递给底层raft,然后由raft同步日志并让对应的kvservice执行指令,实现简易的分布式键值数据库,保证在大多数不良环境下,多机数据库的内容保持一致。此外,随着日志的增加,持久化的数据也在不断扩张,规模较大的持久化数据将会使得日志宕机后恢复的过程较为漫长,拖慢节点回到集群的速度。Lab3B的任务,是实现论文中的快照系统,当日志增长到一定程度时,保存现阶段的数据库快照,并且截断底层raft的日志,当节点宕机后恢复时,首先加载快照,然后执行未执行的指令(一般会非常少),如此一来,节点能快速同步到集群的最新状态。
MIT6.824-lab2-raft
MIT6.824第二个实验,实现著名的分布式一致性算法Raft,包括leader选举、日志复制和状态持久化,不包括成员变更。下面仔细分析一下实验要求,顺便分享一下我的解题思路。
CSAPP-lab3-Attack
本次实验是CSAPP第三个lab:Attack,在实验2的基础上更进一步,不但需要分析汇编代码,还需要分析栈帧内容,通过栈溢出来注入攻击代码。通过本次实验,我们可以更加清晰的认识到缓冲区溢出的危害,了解如何利用栈帧漏洞更改程序跳转地址,以执行恶意代码,修改程序功能。
MIT6.824-LEC04-VMWARE-ft
本文介绍用于虚拟机的容错机制。通过建立backup备份机同步primary虚拟机的状态,使得当primary宕机时,备份机可以立刻补上,并且在整个恢复的过程中,用户并没有感受到太大的差异。从用户视角出发,他们自始至终都在访问同一台虚拟机,备份机的存在对他们而言是透明的。这一种容错机制,个人认为适用于计算节点的容错恢复,比如MapReduce中Master,Map和Reduce节点的状态保存和数据备份。
MIT6.824-LEC3-GFS
GFS是谷歌在03年发布的关于构建分布式文件系统的论文,全文高屋建瓴的概括了建立分布式文件系统的方向和各种性能之间的权衡,提出了设计分布式文件系统的初衷,描述了相关背景意义,详尽的解释了GFS的设计理念和构筑流程,描绘了许多难点和挑战,具有非常高的启发意义。然而本文干货太多了,读每一段的时候都感觉大有收获,但是读完下一段上一段的内容就忘的差不多了,及至读完全文,大脑因为接受信息太多而一片混沌。本文参考网上一些博客和导读,旨在梳理整篇文章的思路,以及做一些总结。
MIT6.824-lab1-MapReduce
MIT6.824是一门非常出名的分布式课程,在这门课里,我们能了解到分布式系统的前生今世,领略一种种令人拍案叫绝的算法,顺便学一下人际管理,有人戏称,分布式系统是一门在你有多个女朋友并且她们都相互认识的情况下,将她们妥善安置的学问,细细一想,觉得很有道理,然而真学完这门课估计就找不到女朋友了,因为那时候已经秃头了… 言归正传,我刚上完前两节课程(其实就是看了一篇mapreduce论文和go语言入门),就来做lab1了,收获良多,下面分享一下我做lab1时的一些认识和想法。 lab1要求使用Go语言实现mapreduce,包括任务安排、节点调度以及map和reduce的操作和相互之间的配合。事实上,大部分代码已经写好了,我们只需要完成核心的代码就可以了。但是我还是建议大家看看其他的代码,从中可以学到许多东西。包括但不限于如何将问题拆分为几个小问题,如何构建一个微型服务器,如何去在客户和服务之间交互,如何设计相关的数据结构和服务,这些都能在6.824/src/mapreduce/*.go文件里找到。