L1nxy's Blog

This is a simple blog about tech and life

0%

raft基础

一个raft集群一般来说有5个服务器结点,能让系统承受其中任意两台的down掉。每个服务器一共有三个状态,leader,follower,candidate,follower被动的接受来自candidate与leader的消息并作出回应。leader handle了所有了所有的客户端的请求,如果follower接收到了请求,会重定向到leader那去。

status

raft把时间分成任意长的阶段,从选举开始,每个阶段都是一个连续增长的整数,至少有一个或者多个candidate会尝试成为leader。如果有一个candidate成为了leader,则接下来的term,它将是leader。在一些情况下,选举会出现,平分票数的情况,这种情况,term将会维持没有leader的状态到结束,到下一次的新的选举。

不同的服务器 可能感知不到不同的term之间的转换,或者根本不知道有选举这回事,在这其中,term充当了一个逻辑时钟的作用,能让服务器能检测过时的信息,比如落后的leader。每一个服务器有一个current term number,随着时间增长,当服务器之间通信时,current term 会被 交换,如果有一个服务器的term小于别的,就会更新自己的,如果一个canditate或者leader发现它自己的term过时了,就会马上转变成follower,如果服务器收到了一个过时的请求,则会直接拒绝这个请求。

raft的服务器之间用rpc请行通信,其中RequestVote用于canditate 来进行选举,AppendEntries 用于分发log与当心跳包(事实上是无论收到一个请求,都应该重置time out chekcer)。另外 还有一个转移快照的rpc。之后 再说。

Read more »

前言

这篇文章来自于Github的一篇关于Rust size的一些介绍,本文内容基本上是这文章的总结。可以话尽量看原文。

Read more »

i3 与 gnome 配置

记录一下i3与gnome配合使用的配置方法。

前言

i3 作为一个很调教好了之后就很好用的平铺式的桌面管理器,其中由于过简法的桌面环境使得日常使用也多少有些不方便,一些常用的功能需要仔细配置与研究,比如音频设置的选择,电源管理,多显示器的配置。我选择的方法是让i3wm去调用gnome的setting center。

配置

首先安装i3-gnomegome flashback ,这个在arch的仓库里就有,装完之后,按照它的wiki配置好即可。

~/.i3/config 里面加入以下几条:

  • GNOME setting daemon:exec --no-startup-id /usr/lib/gsd-xsettings

  • GNOME power manager:exec_always --no-startup-id gnome-power-manager

  • polkit-gnome:exec --no-startup-id /usr/lib/polkit-gnome/polkit-gnome-authentication-agent-1

  • GNOME Flashback:exec --no-startup-id gnome-flashback

其中 gnome flashback集成了更多的gnome的一些特性,装完之后才能打开完整的gnome setting center;

然后 加入一条gsettings set org.gnome.gnome-flashback desktop false;使桌面重启不产生gnome桌面。gnome falshback能配置更多选项,比如使用gnome桌面的壁纸。

锁屏

  • exec --no-startup-id /usr/bin/gnome-screensaver
  • dbus-send --type=method_call --dest=org.gnome.ScreenSaver /org/gnome/ScreenSaver org.gnome.ScreenSaver.Lock

MIT 6.828 Lab3

前言

本Lab比较简单,重在理解代码,并且作业描述中都给出了解决方式,只要理解了代码,按着描述中的思路去解决即可。

解决

第一部分

第一部分主要是把buddy malloc应用到files.c里面去,很简单,把filealloc函数里的代码换成bd_malloc的实现即可,注意把bd_free里面要把各种使用的资源释放掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
// Allocate a file structure.
struct file *filealloc(void) {
acquire(&ftable.lock);
struct file *f = bd_malloc(sizeof(struct file));
if (f){
memset(f,0,sizeof(struct file));
f->ref = 1;
release(&ftable.lock);
return f;
}
release(&ftable.lock);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Close file f.  (Decrement ref count, close when reaches 0.)
void fileclose(struct file *f) {
acquire(&ftable.lock);
if (f->ref < 1)
panic("fileclose");
if (--f->ref > 0) {
release(&ftable.lock);
return;
}
struct file ff = *f;
f->ref = 0;
f->type = FD_NONE;
release(&ftable.lock);

if (ff.type == FD_PIPE) {
pipeclose(ff.pipe, ff.writable);
} else if (ff.type == FD_INODE || ff.type == FD_DEVICE) {
begin_op(ff.ip->dev);
iput(ff.ip);
end_op(ff.ip->dev);
}

bd_free(f);
}

第二部分

这部分主要是说把伙伴内存分配器给优化一下,按hint说的是每两个block的分配状态来共享同一个记录位,用异或来做状态转换。这里我们只要把有bit_setbit_isset换成我们自己写的bit_xorbit_get就行了。

特别要注意的是要在xv6有记录meta信息在内存中,然后我们要把除低位与高位之外的没有分配过的block加到free list里去。

实现:

具体实现

前言

MIT 6.824是著名的分布式课程,课程包含了视频,讲义,与作业。而本篇博文将阐述6.824课程的第一个作业的一些思考与解法,记录一些关于Map Reduce系统的思考。

Map Reduce

Map Reduce作为“谷三篇”的第一篇,出名不是没有原因的,jeff dean的超前思想构建了谷歌搜索的基石,使得谷歌在超大应用系统的构建上得心应手。而Map Reduce则是一个基石中的基石。

Map Reduce的思想就是分布式的,系统中包含一个Master和许多个Worker,Master负责调度Worker与任务分发,容灾等等,Worker则与Master通信,请求任务。

而Map Reduce则把一个任务拆分成Map与Reduce部分,简单来说,Map部分是把输入通过用户定义的Map Function输出成中间文件,再把中间文件作为输入给Reduce,Reduce把中间文件调用Reduce Function,然后合并并输出。

整个系统如图所示。如论文所说,这些文件可以是在本地机器上,也可以在分布式文件系统中,这并不影响整个系统框架。

具体Map Reduce的思想可以读一下Google的论文。

MIT 6.824 Lab1

现代的6.824比以前的要难许多,我做过之前的lab1,当时就把Map Reduce的框架都搭好了,只要写两个函数就算通过了。而这个2020的6.824要求对Go熟悉且要把MapReduce整个实现一个大概出来,前后花了不少时间去思考要怎么来做这个实验。

思考

当我们拿到Lab的时候需要做什么?需要思考我们要实现哪些东西。MIT的代码里只给了几个RPC的函数,然后在这个基础去实现Map Reduce。

而我们要做的有:

  1. 实现Master管理,这其中需要管理任务的状态,Worker请求任务的处理,Worker任务完成报告的处理,Worker失败超时的处理。
  2. 实现Worker请求任务,对Map部分任务的处理,对Reduce部分任务的处理,还有任务完成的上报。
  3. 还要实现一个文件锁,不能让Goroutine之间产生Race。

实现

我的一些方案是在Master的结构体里管理两个Channel,当Master启动之后,把任务发给MapChannel,然后在另一个Goroutine里面对这个MapChannel进行读取,Channel如果不设置的话,一方没有读,写方会阻塞住,所以只有Worker进行请求任务之后才会继续生产任务。当Map部分完成后,再启动Reduce部分,生产Reduce任务到ReduceChannel。

我们在每个请求任务的RPC返回之前再开启一个Goroutine来等待Worker的任务完成报告,这里我们用到了Go的select语法,并使用一个timer,如果超时就把这个任务再次Push进TaskChannel,即使任务失败了,也能再次把任务分发下去。

对于Worker部分的代码来说,完全就是苦力活,可以看看官方代码里那个非分布式的Worker里代码,可以直接复制过来。Worker如果联系不上Master了,马上退出进程,这样就不用实现一个退出语义了。(其实是我不知道怎么让Master去通知Worker退出)

代码

这里只给出一些结构体的定义:

Master:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type Master struct {
MapTaskList []*MapTask
ReduceTaskList []*ReduceTask

MapTaskChan chan *MapTask
ReduceTaskChan chan *ReduceTask

CompleteMapTaskNum int
CompleteReduceTaskNum int

mu sync.Mutex
files []string
nReduce int
}

Task Def

1
2
3
4
5
6
7
8
9
10
11
12
type MapTask struct {
TaskNum int
TaskStatus TASK_STATUS
FileName string
NReduce int
}
type ReduceTask struct {
TaskNum int
TaskStatus TASK_STATUS
FileName []string
NReduce int
}

一些吐槽

这次写了蛮久了,因为不是很熟悉Go,学了一会才知道有select这种语法,然后官方的hint里让人把中间文件命名为mr-x-y.txt,这样其实挺坑的,因为testmr.sh里面没有把这个中间文件删除掉,而在文件读写的时候因为hash的缘故,不会把所有的文件清空,这样导致前一个test的中间文件会影响到后一个test。所以我加一个函数,把所有的中间文件清空的,这样也算是TDD吧。

接下来就是要做Lab2了,完成一个Raft。

MIT 6.828 Lab2

前言

课程仓库地址:https://github.com/l1nxy/mit-6.828
本Lab是实现一个sh,即读取用户的输入并执行命令然后输出执行结果,对于本Lab来说,难点在于Lab中不能使用malloc的要求,不能使用malloc即不能申请动态内存,只能大量使用全局变量。下面将说一说我的做法与注意点。

注意事项

我的做法是用一个全局变量来存一份用户输入的cmd,然后用指针去指向这份cmd,然后写一个parser来解析命令,然后把命令分发到系统调用。
Lab的hint中提到可以不用实现全部的feature,那我们可以采用TDD的思想,去testsh.c中看有多少个test case,然后去实现sh并通过test case即可。
要注意到可能会fork失败,fork失败之后要注意exit,然后会重新fork,不然最后一个test:lots of cmd会失败。

代码

Read more »

MIT 6.828 Lab1

Environment Configuration

Arch

1
sudo pacman -S riscv64-linux-gnu-binutils riscv64-linux-gnu-gcc riscv64-linux-gnu-gdb qemu-arch-extra

Mac

1
2
$ brew tap riscv/riscv
$ brew install riscv-tools

WSL

I DO NOT recommend you use WSL to write lab,because wsl have many bugs,and hard to use. when bug come, i must reboot my win10 and reset network.

If you still want to use wsl, try to Arch WSL.

Read more »

主要还是Typecho要主机费,现在拿着一个VPS也没啥用,就迁移到Hexo好了。
之后慢慢写博客吧,还是要点产出的。