记录一下刷题过程中遇到的一些值得思考的点，以便之后复习用。 同时回顾一下每天遇到的问题，来重新整理自己的思路。 题目1 求数组中的波谷，但是波谷要满足一定的长度 分别求出来每一个位置上，最长的非递增序列和非递减序列的长度。最后遍历一遍就可以 题目2 对于每一个位置，求出数组中所有数除去当前数的乘积 这个最简单的方法就是求出前缀积和后缀积，然后单独计算就行 一个优化是可以只用一个变量来保存前缀积或后缀积，然后给对应的位置乘上贡献即可 题目3 投n个骰子，问每种点数出现的概率是多少 设dp[i, j]为当前投了i个骰子…
Raft-KV 这里写一下lab4 shardkv的思路吧，感觉如果不好好想一下设计细节的话写代码的时候就很容易乱套 目标就是完成所有的part，所以后面的选做部分也要实现（其实感觉不实现那我们的代码就太玩具了） 每个shard不能干扰其他的shard，比如一个shard正在等待数据，他是不能干扰其他shard完成正常操作的。所以我们分别维护每个shard的状态。每个shard有自己的map 去重表，可以放在shard外面也可以放在shard里面，我这里就选择放在shard里面 有一个定时向shardctrler去…
1 通过算法分解（leader选举，日志复制和安全）和减少状态机的状态来提升Raft的可理解性 Raft独特的特性 强leader： 日志只从leader发送给其他的服务器 leader选举： 使用随机计时器来选举领导人，在解决冲突的时候更加简单 成员关系调整： 使用共同一致(Joint Consensus)的方法来处理集群成员变化的问题，处于调整过程中的两种不同配置的集群中大多数会有重叠，让我们可以在集群变化的时候保证可用性 2 Replicated state machine 在一组服务器上的状态机具有相同状态…
通过functional model和用户指定的map和reduce操作，我们可以很容易的将这些计算并行化。 通过re-execution作为主要的fault tolerance的手段 2 programming model map接受input pair，并生成一组中间键值对。MapReduce Library会把相同key的键值对的所有value组合在一起，并把他们传给reduce reduce接受一个key以及对应的一组value，他将这一组值合并到一起，并返回给用户 一个计算每个document的单词数的例…
How to Read a Paper Just a note for convenience. First pass, get a bird's eye view of the paper Carefully read the title, abstract, and introduction Read the section and sub-section headings, but ignore everything else Read the conclusions Glance over the refe…
多核架构下的中断处理 来一句题外话，本以为我目前的体系结构相关的知识已经足够充分了，但没想到还是不够细节。在理解xv6的过程中，通过教授的一些assertion，我才找到了自己对于中断理解的一些错误，这里特此记录下来。 问题的起因是这样的，在xv6中，中断处理程序一般都需要用lock来防止race condition，所以我就理解成了lock是用来防止多核同时执行一个中断处理程序时，在操作共享数据结构的时候导致的race 但是xv6的net lab中，教授的solution在中断处理程序中没有用lock。同时在课上…
Daily Rust 有关所有权和生命周期的一些问题 首先看一段代码 use std::rc::Rc; #[derive(Debug)] struct Node { id: usize, downstream: Option<Rc<Node>>, } impl Node { pub fn new(id: usize) -> Self { Self { id, downstream: None, } } pub fn update_downstream(&mut self, do…
Lecture 16 run一个thread都涉及到了什么 比较常规的知识点，选择一个execution context，设置状态（pc， stack等），然后开始执行 对于同一个core上的multithread来说，os并不负责 os只负责粗粒度的调度，保证每个进程都能分享硬件资源 但是在硬件中利用多线程隐藏访存延迟的角度来说，用os调度代价太高了。所以在一个核上的若干个execution context，是由硬件来调度的 比如数据库中的latch，利用自旋锁实现就更好一些。因为这些都是轻量级的短时锁，不会等待…