今年年初寒假的时候，尝试做了一下CMU-15445的lab2，并发B+树的实现。可惜能力实在有限，如果不是西部小笼包大佬的博客，我都完全不知道从哪里开始。最后也是7分抄3分自己写，对着课件PPT的B+树分裂合并流程一点点啃完了。不过还有一个一直困扰我的问题，就是大佬使用了一个thread_local变量来记录根节点锁的上锁次数，我一直不明白为什么要这样做。然后我决定自己单步调试一下如果不使用thread_local变量记录根节点锁加锁次数会怎么样。

领导人选举

Raft 将所有节点分为三个身份：

• Leader：集群内最多只会有一个 leader，负责发起心跳，响应客户端，创建日志，同步日志。
• Candidate：leader 选举过程中的临时角色，由 follower 转化而来，发起投票参与竞选。
• Follower：接受 leader 的心跳和日志同步数据，投票给 candidate。

Raft使用心跳来维持leader身份。每个节点都以follower的身份启动。leader定期发送心跳给所有follower以维持自身的身份。每当follower收到了leader的合法心跳，就刷新自己的超时选举时间。每个节点在初始化时启动一个定时器协程节点选举超时后转变为candidate，提高任期，并发起这轮任期内的选举。

前言

lab1是实现一个MapReduce，markdown写了挺久了，一直没有上传到博客

    你用飘忽不定的眼神审视着周围世界，目光在无数个构成事物实体的点上游离，不曾停留。紧张、拘束、好动，你忍不住想将路障桩子一脚踢飞，可你不敢这么做，因为这会吸引市民朋友们的注视。你是一只狼，那种好奇的目光一旦被你的敏锐双眼所捕捉，你就忍不住起鸡皮疙瘩，因此你害怕哪怕是一瞬间的眼神对视。你低着头沿着街道在商店前快步前进着，扭头看见商店玻璃镜子里的你，他是那么的不安，仿佛极不情愿出门似的。你为什么要带他出来？

第一个用户进程

当xv6被加载到qemu后，执行的第一段代码如下所示，就是为每个cpu分配一个运行栈，即stack0，然后跳转到start函数

最小(大)值最大(小)化问题

875.爱吃香蕉的珂珂

其实我做过去年的lab，但没有写年轻人的第一棵B+树难免是一种遗憾，于是寒假决定写完B+树就收手！

Task #1 - Extendible Hash Table

这一部分是要实现一个可拓展哈希表，作为去年的Project-2，我已经接触过了，所以写起来没啥太难得地方，但还是有个bug卡了一会儿。

Bucket的插入删除查找很简单，不再赘述，主要介绍可拓展哈希的扩容原理。

可拓展哈希有一个目录，目录元素是指针，指针指向一个实际的Bucket

配置git账户名与邮箱

1
2

git config --global user.name "forgivehat"
git config --global user.email "87645****@qq.com"  #你的邮箱

lab-lock

Memory allocator

每个CPU都有一条对应的空闲内存链表，有利于分配时减少冲突。

1
2
3
4

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem[NCPU];

初始化空闲内存表锁。

1
2
3
4
5
6
7

void
kinit()
{
  for(int i =0; i < NCPU; i++)
    initlock(&kmem[i].lock, "kmem");
  freerange(end, (void*)PHYSTOP);
}

lab-fs

Large files

修改fs.h中关于直接块间接块的定义，前11块为直接快，第12块为一级间接块，第13块为二级间接块。

1
2
3
4

#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define NDUBINDIRECT (BSIZE / sizeof(uint)) * (BSIZE / sizeof(uint))
#define MAXFILE (NDIRECT + NINDIRECT + NDUBINDIRECT)

当要访问的bn(block number)大于NDIRECT + NINDIRECT时，访问二级间接块，仿照一级间接块的查询方式即可，注意需要查询两级地址。