海岛一隅

纠删码（erasure coding，EC）是一种数据保护方法，它将数据分割成片段，把冗余数据块扩展、编码，并将其存储在不同的位置，比如磁盘、存储节点或者其它地理位置（来自百度百科）。最早是在通信行业解决部分数据在传输中损耗的问题，它的基本原理是把传输的信号分段，加入一定的校验再让各段间发生一定的联系，即使在传输过程中丢失掉部分信号，接收端仍然能通过算法把完整的信息计算出来。 目前，纠删码技术在分布式存储系统中的应用主要有三类： 阵列纠删码（Array Code: RAID5、RAID6等） RS(Reed-Solomon)里德-所罗门类纠删码 LDPC(LowDensity Parity Check Code)低密度奇偶校验纠删码 磁盘阵列RAID RAID0 RAID0 是一种非常简单的的方式，它将多块磁盘组合在一起形成一个大容量的存储。当我们要写数据的时候，会将数据分为N份，以独立的方式实现N块磁盘的读写，那么这N份数据会同时并发的写到磁盘中，因此执行性能非常的高。 但RAID0的问题是，它并不提供数据校验或冗余备份，因此一旦某块磁盘损坏了，数据就直接丢失，无法恢复了。因此 ...

特别提醒，本文所涉及的源码是go1.22.4 darwin/amd64 文件位置：runtime/map.go Go早期的调度模型是GM的，M想要执行、放回G都必须访问全局G队列，并且M有多个，即多线程访问同一资源需要加锁进行保证互斥/同步，所以全局G队列是有互斥锁进行保护的。 老调度器有几个缺点： 创建、销毁、调度G都需要每个M获取锁，这就形成了激烈的锁竞争。 M转移G会造成延迟和额外的系统负载。比如当G中包含创建新协程的时候，M创建了G’，为了继续执行G，需要把G’交给M’执行，也造成了很差的局部性，因为G’和G是相关的，最好放在M上执行，而不是其他M’。 系统调用(CPU在M之间的切换)导致频繁的线程阻塞和取消阻塞操作增加了系统开销。 改进后的调度模型引入了P，因此就变成了GMP模型。Processor，它包含了运行 goroutine 的资源，如果线程想运行 goroutine，必须先获取 P，P 中还包含了可运行的 G 队列。 模型总览 调度策略 1.首先每60次，会先调度一下全局队列中的G以防止饿死，具体globrunqget运行下文会讲 1234567 ...

特别提醒，本文所涉及的源码是go1.22.4 darwin/amd64 gRPC使用protobuf作为接口定义语言(IDL)，包括定义服务的方法以及通过网络发送的消息。如下代码所示： 1234567891011service Greeter { rpc SayHello (HelloRequest) returns (HelloReply) {}}message HelloRequest { string name = 1;}message HelloReply { string message = 1;} 上面的proto文件中定义了一个服务叫做Greeter，其中包含一个方法名是SayHello，请求的参数为HelloRequest类型，返回的响应为HelloReply类型。 protobuf是如何将上面的消息编码为二进制的呢？ 请求参数和响应参数中都会包含若干个字段，这些字段被组成下图所示的样子： 如果是json编码的话，那其中的标签就是对应的字段名，比如上面的name和messag ...

引言Diego Ongaro在《In search of an understandable consensus algorithm》中提出的一种新的分布式共识算法。正如论文标题所说，Raft算法容易理解。 符号定义选举超时时间为：electionTimeout 所有的server的总数为：2k+1（其中k为正整数） 状态有三种：leader、follower、candidate 日志条目：log entry 领导选举 各server启动时都是follower状态 如果某个server在经过electionTimeout还没有收到来自leader的信息，那么该server由状态follower转变为candidate，并且首先给自己投上一票，然后向其他server发送请求投票的消息。 server保持candidate的状态直到出现下面三种情况： 该server收到了来自大于等于k+1的票数(包括它给自己投的一票)，该candidate转为leader 其他candidate成为了leader，也就是收到了任期不小于自己的leader发来的消息，该candidate转为follower ...

特别提醒，本文所涉及的源码是go1.22.2 darwin/amd64x/sync包的版本是v0.7.0 x目录下的包一般认为是go的官方拓展库 singleflight定义：Package singleflight provides a duplicate function call suppression mechanism 意思就是提供了一个重复的函数调用抑制机制 一般有如下两种应用场景，能减少缓存击穿的风险。 现在来看看具体的源码 3个结构体1234567891011121314151617181920212223type call struct { wg sync.WaitGroup // 存放fn函数调用的返回值 val interface{} err error // 合并的请求数 dups int // 调用DoChan的返回结果 chans []chan<- Result}type Group struct { mu sync.Mutex ...

1 树树是由n个节点构成的有限集，其中当n=0时，称为空树。并且树恰好有n-1条边。 其中A是树的根 2 二叉树顾名思义，二叉树就是一个节点只有两个子节点 左边的子节点称为左孩子，右边的节点称为右孩子。二叉树就有比较多的性质了： 节点数量为n，则边的数量为n-1 度为2的节点个数等于叶子节点个数-1，即$n_2=n_0 -1$ 第k层（k$\geq1$）有$2^k-1$个节点 节点i（i$\geq 1$）的左儿子编号为$2\times i$ ，由儿子编号为 $ 2\times i+1$ 有下面几种遍历顺序： 先序遍历 中序遍历 后序遍历 层序遍历 3 二叉搜素树二叉搜索树的左孩子节点的值小于父节点的值，右孩子节点的值大于父节点的值。 由于它具有这样的性质，因此查找一个在树上的值，可以使用到二分思想查找，时间复杂度为$O(log n)$，但是在极端情况下，即一条链的时候还是$O(n)$，因此有各种各样的平衡树来解决这个问题。 4 AVL树AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一 ...

特别提醒，本文所涉及的代码是redis3.0，由《Redis设计与实现》作者所注释的版本：地址 与字典相关的文件在dict.h和dict.c两个文件中 数据结构123456789101112typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next;} dictEntry; dictEntry是字典中的单个节点，即一个k-v对，注意到这里的值是一个union联合体，键值对中的值可以是一个指向实际值的指针即val，或者是一个无符号的 64 位整数u64或有符号的 64 位整数s64。 1234567891011typedef struct dictht { // 哈希表数组 dictEntry **table; // ...

Speed up systems calls 题目要求：为了加速某些系统调用，可以让用户空间和内核空间共享一片只读的物理内存空间，并放在TRAPFRAME下面 根据题目意思就是放在红框这里 首先需要在proc.h文件中的proc结构体添加一个成员： 1234567891011121314151617181920212223struct proc { struct spinlock lock; // p->lock must be held when using these: enum procstate state; // Process state void *chan; // If non-zero, sleeping on chan int killed; // If non-zero, have been killed int xstate; // Exit status to be returned to parent's wait in ...

一致性哈希的原理，可以直接看小林coding的什么是一致性哈希 Golang——groupcache在golang官方的仓库中有个名叫groupcache的仓库，里面提供了个简单的一致性哈希算法是实现，先简单分析一下这个的源码。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465package consistenthashimport ( "hash/crc32" "sort" "strconv")type Hash func(data []byte) uint32type Map struct { hash Hash // 哈希函数 replicas int // 每个节点对应的虚拟节点的数量 keys []int // Sorted hashMap map[int ...

Using gdb 如果不知道怎么运行gdb的，要先看提供的文档 1.首先在终端1中运行make qemu-gdb，结尾处会得到一个端口号，供终端2使用 2.新起一个终端，运行riscv64-unknown-elf-gdb，会进入如下所示的界面 3.输入target remote localhost: 25501，然后再输入file kernel/kernel，就可以跟着指示往下做了 问题1：Looking at the backtrace output, which function called syscall? usertrap() 问题2：What is the value of p->trapframe->a7 and what does that value represent? 从initcode.S文件中看到a7保存的是要执行的系统调用号，从syscall.h中看到7是SYS_exec 7和exec的系统调用号 问题3：What was the previous mode that the CPU was in? 通过输入p / ...