花了三周时间把拖了很久的Lab 4给做了，相比于前面3个lab，难度明显提高了很多。难点在于官方没有提供任何参考资料，但是给了很多hint。我认为这就是这个lab设计得最好的一点，不直接告诉你如何去解决这个问题，但是会给出一些可能有价值的hint，描绘出一个模糊的轮廓，启发学生的思考。 不得不说，这是个很难得的锻炼自己系统设计能力的机会，如果去网上搜解决方案那就太浪费了。所以我还是和往常一样，坚持独立思考。采用的方法论还是那一套：问自己问题，然后自己回。不论问题大小，都记录下来，当问题大概都能解决了，整个思路就慢慢浮出水面了，觉得差不多了就可以开始动手了，边动手边和自己Q&A。从结果来看，这个方法论是适合我的。 接下来简单记录一下这个思考、实现、debug的过程，其中涉及到一些早期的废案（有标识），但我还是记下来了。 Part A: The Shard Master 和lab3的key/value service基本一致，要改的地方就是server应用raft层传上来的cmd时的处理逻辑。一共要实现Join、Leave、Move、Query共四种功能，shard master 的作用就是将总数固定的shard平均分配到各个server group中。注意，join/leave都是可以一次上线/下线多个server group的。 我的实现算法很朴素，Join时每次把shard数最多的group分一个shard分给shard数最少的group，直到shard数的极差<=1时，迭代结束。Leave的逻辑也是类似。实现上要注意，golang的map是reference，所以拷贝config时，其中的的Group字段需要手动深拷贝。 2024.3.9 发现shardmaster有问题，同一个Num，能Get出Num相同而Shard不同的Config值，跑TestUnreliable2时偶尔能复现；后来发现这是因为go的map是hash map，for loop遍历的时候go会故意打乱顺序，导致leader和follower运行同一个join或者leave指令，结果可能会不一样（破坏了确定性状态机状态唯一的性质），导致之后Get的结果可能不同。关于go map for loop的随机性详见stack overflow的这个问题。在查找解决方案时，我还知道了ordered map和sorted map原来不是一种东西，ordered map只要求有序就行，不要求按大小顺序，一般是按键的插入顺序；而sorted map就是按key大小排序的map，比如C++里的map。golang里这两种map都是由第三方库提供的。我最终的解决方法还是采用的标准库的map，按官方推荐的方法，将它的key（gid）拿出来，先sort一下，然后按照这个sort的序去遍历，这样在不同实例上的遍历顺序就是确定的了（按gid大小顺序）。 Part B: Sharded Key/Value Server config 配置更新的设计 为每个shardkv实例维护一个newest_config。 Q: follower需要去shardmaster拉取最新配置吗？ A:两种方法，一种是follower自己去shardmaster拉取最新配置，第二种是leader发现config发生变化后通过raft log告知follower，应该都是可行的。我选的是前者。 shard transfer过程的设计 由于我的目标是实现全异步的configure update的过程，所以一个group不会等自己要传输的shard都集齐了，再一起transfer出去。这要求我们将newest_config的更新逻辑和shard transfer的逻辑分离开来。 func (kv *ShardKV) updateConfig() { for { if atomic.LoadInt32(&kv.dead) == 1 { return } kv.mu.Lock() if !kv.inited { // first-time started (...) } else { kv.

MIT XV6 2023笔记 记录一下MIT 6.1810 2023 fall公开课（以前叫6.828）的lab，以及自己看xv6-book觉得有意思的点。一方面方便自己回顾，另外希望能帮上一些后来的朋友。 Lab: Xv6 and Unix utilities sleep 没什么好说的 pingpong 主要熟悉一下pipe系统调用，fd[2]第一个是rfd，第二个是wfd。思路就是创建两个pipe，父子进程通过管道进行同步，依次打印所需内容即可。 primes 实现质数筛。handout里的这篇文章值得一读，主要的思想就是“多进程模型不仅仅是一种利用多处理器的手段，它本身也是一种解决一些问题的一种自然的模型”，比如这个质数筛，就是以“每个进程作为一层筛子”的思路来实现的，具体实现上面的文章里有伪代码，进程间通信还是用pipe。值得注意的是记得对于不需要的pipe fd要及时关掉（比如邻居与邻居的邻居之间的管道显然是不需要的，可以关闭），要不然递归创建pipe，fd会爆。xv6里一个进程默认的最大的打开的文件数是16。 find unix里常用的一个命令，主要是用来熟悉文件系统调用，思路就是递归遍历指定的path下所有的目录以及文件，逐个判断是否与pattern match。文件的类型通过stat系统调用来获取。这里值得注意的是directory文件并不是按照来其中的entry数来确定大小的，它永远是固定大小的，inum=0的entry大概就表示是空entry吧？我这里通过判定ent.name == ‘\0’来判定是否为空entry也能过测例。 xargs 开个buffer数组用来存新argv参数，最好作为全局变量，放栈上可能爆栈。然后就是从标准输入中一个一个字节读，并以\n为分割，解析出新的参数，再fork+exec就好了。 另外，我发现vscode自带的ClangFormat导致include的头文件顺序乱了，最终导致过不了编译，这是因为xv6里头文件的编码风格都是手动管理include顺序来保证不会miss definition，而不是用在每个头文件里定义宏来防止重复include。 解决办法有两种，一种是加上// clang-format off 这一行就好了，另一种办法就是不用clang-format。 Lab: system calls Using gdb 用gdb源码编译并安装好gdb，如果gdb时发现layout指令用不了，需要加–enable-tui=yes参数重新编译并安装一遍gdb，我按照这个博客重新装了一遍。 这里涉及到了一些寄存器，risc-v硬件方面的前置知识可以看rcore的介绍 sstatus:寄存器，其中有SPP位表示进入supervisor mode之前是什么特权级，0表示user mode，1表示supervisor mode。其中的SIE位是Supervisor Interupt Enable，PSIE位是Prior Supervisor Interupt Enable 见The RISC-V Instruction Set Manual, Volume II: Privileged Architecture | Five EmbedDev (five-embeddev.com) epc: exeption program counter,发生异常时，在进入trap前，硬件自动将pc存到epc中，用于异常处理的返回。 satp: 页表首地址 从scause可以看出这是个page fault，sepc是发生缺页中断的指令地址，stval中保存的是导致page fault的非法地址。通过sepc去kernel.asm文件中找就能发发现page fault的位置。

多核环境下in-memory database的挑战 多核下，从数据库系统（特别是内存数据库）等访存密集的应用，可能会因为访存行为而产生一些新的性能瓶颈，我将其分为两个方面，一个是共享内存时的缓存行所有权争用，这一点再OLTP的工作负载下尤为明显；另一个是NUMA架构带来的潜在的远程节点内存访问的问题，这一点是面向OLAP的数据库需要重点考虑的。 服务器级CPU的架构 这一部分主要从硬件设计的角度看看现在服务器级CPU的宏观架构，这是一个很大的话题，不同厂商不同代的架构都不一样，不过当今总体的发展方向是比较稳定的，即堆核（没错，不仅RISC厂商在堆，CISC厂商也在堆）。 先从主板说起，一个服务器一般是一个主板，一个主板上有多个socket，即物理插槽，一个插槽上可以插一个cpu package（可以理解为将多个die打包成为一个整体），即市面上买到的一个个CPU，一个CPU内可以有一个或者多个die，一个die由多个core组成。 die是个很重要的概念，die就是一个“片”，一个die中的每个core是独享L1和L2 cache的，所有core共享LLC，LLC通过hash的方式将物理地址空间分为一个个slice，用Ring Bus或者Mesh网络的方式连接起来，这两种连接链路都属于片内总线。 ring bus架构的缺点是，核越多，延迟越大。Mesh网络的方式除了制作难度更大，由于其大大减少了总体的访问距离（双向ring bus的情况下，每个核最远的访问都是半个圈）,所以总体访问延迟更低，并且不再需要跨ring访问。 至于FSB的淘汰，是因为FSB（CPU与NorthBridge的连接线）瓶颈有限，在CPU多时容易成为性能瓶颈，所以在很早的时候，Intel等厂商就把North Bridge集成到了die中，自然也就不需要FSB了。 为了提升算力，除了提升制程（很难），另一种方式就是堆核。堆核也有很多方式，一个die里堆核是有上限的，片内堆核虽然性能很好，但是堆多了良品率太低，要进一步扩展的话就得扩展为多个die(多个die合成一个package)，die与die之间的连接方式AMD和Intel的选择也不一样，这里不做更细的展开;另外需要注意的是，这里的连接方式和Intel的QPI和UPI没有任何关系，QPI和UPI是实现跨Socket的通信的，类似网络路由，进行点对点的通信。 缓存一致性协议 要保证缓存一致性，硬件是需要支付开销的，在多核下开销会变大，表现为缓存访问延迟变高，所以不可忽略。 延迟变高的主要原因来自于写缓存时产生的RFO请求（RFO：Request For Ownership，指处在S状态的缓存行要升级为E状态，需要向所有核广播一个RFO请求，将其余S状态的缓存行设置为Invalid)。RFO本身就是有延迟的，因为需要等待其余所有核的Invalidate的回应。而总线也是有带宽限制的，所以热点数据竞争修改越多，RFO请求越多，修改请求的延迟就会越高。 缓存一致性，是对于LLC之上的缓存，即每个core独有的缓存来说的，在如今普遍使用的3级缓存架构下，一般是L1d,L1i,L2缓存。 缓存一致性协议可以分为基于Snooping-Based和Directory-Based两种，主流的还是采用基于Snooping的方法，主要是MESI协议及其变种，简单介绍一下MESI及其变种。 MESI MESI协议资料很多，这里不赘述。这里的一个例子我认为比较有代表性，表述也比较准确。 A simple example, a 2 vCPU VM consuming on core 1 and 2 runs SQL server. The VM runs on a 4 core ESXi host. 1: A SQL query requests memory at address X. The query runs on vCPU1 and core 1 detects it does not have this data in it’s L1 and L2 cache.

MIT 6.824 2020 (3) Fault-tolerant Key/Value Service实现笔记 该博客主要关注功能实现，Read Lease等优化之后有时间填坑：） Basic Q&A 首先需要问自己这些问题，想清楚后后就能理解server层和raft层之间的交互逻辑了。 Q:对于client来说，在进行read请求时，是向leader发送（保证得到最新的数据），还是向任意一个节点发送呢？ A:client的读写请求都向leader发送，如果不知道leader是谁，就随机向一个server进行询问。raft通过这种方式保证了线性语义（强一致性），但是损失了读性能（这与zookeeper是相反的）。 Q:raft在进行写请求的时候，如果随机选中了一个旧的leader（比如在一个非majority的parition中的旧leader)，那写请求的拒绝执行是通过什么机制实现的？ A:请求的回复应该是阻塞的，得等到leader确认该log被复制到大多数replica时，才能给出一个promise；所以，作为leader的server需要有处理请求超时的逻辑，防止自己是minority的旧leader，无法commit客户端的请求却久久不释放客户端连接。 Q:为什么每个leader的term期开始时都要追加一个no-op log？ A:因为leader只能提交当前term期的log, 通过no-op log日志的提交能够间接提交之前的term期的未提交日志，这样能够保证leader在自己拿到任期后能尽快地进入可读状态。（原文中说的是leader可以尽快知道commit index,本质上说的是一样的事）。 Q:server需要维护每个client的最后请求的序列号一防止重复执行，那这个信息是由leader在AP rpc里同步到followers吗？ A:对，所以ClientId和Seq这两个信息都要作为log entry的一部分，followers commit的时候，server层可以可以根据根据这个进行去重。防止一个请求被apply多次。 开始编码前的建议 个人感觉这部分比lab2要难调试一些，回顾起来，主要有两方面：遇到了很多死锁的问题；加上server和client后，log更多了，看起来比较吃力。所以，有以下推荐： 跑测试的时候，把-race打开 用logrus库来代替std log，支持多日志级别 调试时借助死锁检测工具，如go-deadlock Part A: Key/value service without log compaction 线性一致性 要满足线性一致性，可以理解为对于同一个数据对象，一个Read请求，一定要读到“在时间上最新的”已经返回Success的write请求的数据。考虑这么一个场景，网络分区发生了，一个follower被选举为了新的leader，他的commit index其实可能是小于旧leader的，所以他的数据其实是旧的，那么如果这时候来了一个Read请求，他该如何操作，才能保证这个Read请求读到的是最新的数据呢？ 最自然的想法就是将read也作为一个cmd，放在log里进行replica，这个log commit后，再返回read的结果，这样就能保证读到的是最新的数据了。这个线性顺序也就是log提交的顺序。 当然，这不是必须的，有Read Lease/ follower read等优化。 请求超时 做partition3A时遇到了问题处于minority的leader旧久久不释放客户端请求的情况，这里我为server端增加了一个处理请求超时时间为1s，过了1s如果leader没有收到raft层的consensus，直接返回timeout Err。然后为client端增加超时换target server重试的逻辑。 添加NO-OP log的位置 2023.11.17 要在两个地方加NO-OP日志, 一个是选举成功成为新leader后，另外一种作为leader，收到其他节点的RV rpc请求，发现Term比自己高，但是其log日志落后所以拒绝时，要更新自己的CurrentTerm，然后这里还要添加NO-OP! 我的设计中，希望重复的log不要放到raft的log中，所以我是在kv.rf.Start前就做了去重操作；清华佬的想法相反，在log commit并且apply时再进行去重操作。 记录结果 关于是否需要记录最后一次session的结果的问题，我之前没有想过，因为我认为记录的是旧的结果，这会违反线性一致性。举个例子，比如一个Get操作，第一次超时了，但是leader成功commit并记录了结果，那Get操作重试时，如果直接返回这个结果，那这就是旧数据，因为client重试的这段时间可能这个数据又发生改变了。但是后来偶然看到这位大佬认为需要记录结果。论点如下： 为什么要记录应用的结果？因为通过这种方式同一个命令的多次 apply 最终只会实际应用到状态机上一次，之后相同命令 apply 的时候实际上是不应用到状态机上的而是直接返回的，那么这时候应该返回什么呢？直接返回成功吗？不行，如果第一次应用时状态机报了什么例如 key not exist 等业务上的错而没有被记录，之后就很难捕捉到这个执行结果了，所以也需要将应用结果保存下来。

miniob 2023 初赛记录 写在前面 第一次参加miniob，记录一下初赛。总体来说没有什么技术难度，大部分是体力活，但也让我复习了不少数据库细节上的东西，比如MVCC、SQL解析与查询计划构建等等。记录是为了以后再参加时可以给自己或者其他同学做参考。 各题思路 Drop table 这个sql解析语法已经写好了，需要做的是添加一个drop_table_executor，然后为Db类（管理数据库的元数据的类）添加一个drop_table函数，函数内需要删除一个table的元数据文件、index文件、data文件，然后还需要回收bufferpool中该文件对应的页，成功的话再将该table的tableMeta从Db类中删除即可，此时就完成了一个table的完全清理。 update 这个虽然分值不高，但是涵盖了从sql层解析到底层table分页存储的内容。具体来说，包括： 增加update语句的sql解析 增加updateStatement\updateLogicalOperator\updatePhyicalOperator，并在各个stage中添加构建这些对象的链路，至于这些对象需要哪些字段以及如何构建，可以参考select和delete的链路。 增加tablehandler->update_record()、pagehandler->update_record函数，为updatePhyicalOperator提供存储上的支持。tablehandler->update_record()除了修改data文件，还需要修改对应的索引（现在只支持b+tree索引，需要先delete再insert)。 Null 增加建表的时候的语法，为table增加元信息nullable； 增加Value的null字段，标识该字段是否为null。在insert value时，如果是NULL，则将 null 赋值为true； 为where增加 is null 和 is not null 语法； 在insert和update时，在executor或者resolver阶段检查插入的数据是否允许null，如果允许，则插入为一个特殊的值，对于INT来说，插入INT_MIN, FLOAT:FLOAT_MIN, CHAR(N): ‘/0’，这里在从record中存储数据以及读取数据为value时，提供一下判NULL支持。 新增compareType IS和IS_NOT，在表达式进行比较时，如果两边value有任意一个为null，则判断比较运算符是否为IS或者IS_NOT，如果不是，直接判false；如果是，则返回 (left.is_null() == left.is_null()) == (cmptype==IS) 可能需要在别的地方加上对NULL特判的支持，比如聚合函数。 以下是mysql的做法，每个coloumn一个bit表示是否是null(https://cloud.tencent.com/developer/article/1469056) 这是关于mysql 与null有关的index上走没走索引的讨论 aggregation-func 除了sql层添加的语法，主要增加了一个aggregation的逻辑和物理算子，在select查询计划中，放在查询计划的顶端（和projection 平级），即predicate以上的位置。agg算子的逻辑可以认为是bustub中group by算子的子集，功能还很弱，只能输出一行数据。 另外，这里还涉及到schema的问题，miniob中的schema表示的是数据的输出字段显示格式，具体在RC ExecuteStage::handle_request_with_physical_operator(SQLStageEvent *sql_event)。在agg这个题目中，由于需要为聚合字段添加名字，所以需要在这个函数中添加命名方式。比如“MIN(字段名)”等。 所有权的设计挺有意思的，可以详细写一下, 包括swap和move（生成phyical operator时从sqlnode move过来而不是采用指针引用，可以使之后的执行减少一次访存的开销） 过测例的时候发现，恶心的是强制要求把很多能在parse阶段解决的错误延后到resolve阶段，使得需要重新设计sql部分。 sub-query 采用物化的方法，优先进行子查询，然后将子查询的结果作为Value(或者vector)放在predicate_operator中。具体来说，这是通过给predicate_operator加child做到的。predicate_operator在open时，会检查自己有几个children，如果有两个children，说明第二个children是一个子查询，则优先进行子查询，利用得到的结果构造出最终的predicate expression。本质上是将expression的构造时间延后了。 为了支持IN/NOT算子，设计了一个新的ExprType，称为ExistExpr，继承自Expresion，其内部维护一个Value集合。get_value时根据查询值是否在这个Value集合返回一个bool值。 过测例时发现update的set value字段也可以是一个subquery, 我采用的还是加child的方式，不过这次是加到update_operator后面，逻辑也是一样的，open时发现有两个children则优先进行子查询。本质上是将value的构造时间延后了。 multi-index 修改存储在index文件中第一页的元数据 实现最左匹配：在生成物理执行计划时判断table get能不能走索引，用最左匹配原则。如果有，则需要构造出left key和right key，剩下的无法走索引的字段左右分别设置为最小值和最大值即可。注意，由于这里我的NULL值是比MIN（MIN设计的是NULL+1)还小的值，所以左边界是NULL。 另：logical_operator重写阶段实现了谓词下推（predicate pushdown)，所以在table_get_logical operator构建物理执行计划时，如果有谓词，再尝试使用索引即可，如果有索引，构建index_scan的物理执行计划。 **text ** 弄个新的TextPage, header存char_num, char_num表示这个page中存的实际数据有多少， next_page指示下一个TextPage的page_num。读取时，当char_num == FULL_CHAR_NUM && next_page !

MIT 6.824 2020 (2) lab2 Raft 实现笔记 这个lab我是边看论文、边看课边做的，前前后后花了快2周，非常有挑战性。做完后感触颇深，特别是后来再去了解了一下Paxos后，更感慨raft的大道至简，也钦佩这篇论文的作者——来自Stanford的Diego Ongaro，一是钦佩他的严谨的思维，二是钦佩他的文字表达能力，我虽然从没接触过共识算法，但也能较轻松地看懂论文（唯一理解上比较吃力的是 figure 8，看了我一个下午我都没看懂，后来上网查才发现好多人也没看懂这个），并根据figure 2来实现一个这样的系统，真可谓是深入浅出。 基础设施 labrpc是模拟了一个网络，网络除了模拟正常的网络延迟，还模拟了异常的情况，比如可能出现丢包（返回ReplyMsg{false, nil}), 长时间延迟等。 config.go里相当于构建了一个raft集群环境，可以通过connect,、disconnect等模拟这个环境可能出现的状况。并通过checkOneLeader等接口可以查看这个环境当前的运行状况。另外还有one函数，会尝试start一个log，并检测集群内是否达到了共识，是主要的test手段。 lab2A 领导人选举 首先，每个raft服务启动时，会开启一个electionTimeOut的计时器，如果计时结束前收到了RequestVote请求。 RequestVote RPC 代码如下，注意，后面关于有关与log的判断是lab2B加上去的。 func (rf *Raft) RequestVote(args *RequestVoteArgs, reply *RequestVoteReply) { // Your code here (2A, 2B). rf.mu.Lock() fmt.Printf("RV from %d to %d received: %+v with curTerm:%d votedFor:%d\n", args.CandidateId, rf.me, args, rf.currentTerm, rf.votedFor) defer rf.mu.Unlock() reply.Term = rf.currentTerm if args.Term < rf.currentTerm { reply.VoteGranted = false rf.persist() return } if args.