Linux笔记
数据结构链表相比普遍的链表实现方式,Linux内核的实现比较独树一帜。普通的实现是数据通过在内部添加一个指向数据的next或prev节点指针,才能串联在链表中,存储这个结构到链表里的通常方法是在数据结构中嵌入一个链表指针,如next或prev。而Linux内核中,是将链表节点塞入数据结构。
1234567891011struct list_head{ struct list_head *next; struct list_head *prev;};struct fox { unsigned long tail_length; unsigned long weight; bool is_fantastic; struct list_head list; // 所有fox结构体形成链表}
内核还提供了一组链表操作接口,比如list_add()加入一个新节点到链表中,他们都有一个统一的特点,就是只接受list_head结构作为参数。通过使用宏container_of()我们可以很方便地从链表指针找到父结构包含的任何 ...
Raft论文研读笔记
摘要Raft是用于管理复制日志的一致性协议,与Multi-Paxos作用相同,效率相当,但是架构更简单,更容易实现。Raft将共识算法的关键因素分为几个部分:
Leader election 领导者选举
Log replication 日志复制
Safety 安全性
且Raft用了一种更强的共识性来减少要考虑的状态state的数量。
Raft对比于现有的共识算法有几个新特性:
Strong leader(强领导性):相比于其他算法,Raft 使用了更强的领导形式。比如,日志条目只能从 leader 流向 follower(集群中除 leader 外其他的服务器)。这在使 Raft 更易懂的同时简化了日志复制的管理流程。
Leader election(领导选举):Raft 使用随机计时器来进行领导选举。任何共识算法都需要心跳机制(heartbeats),Raft 只需要在这个基础上,添加少量机制,就可以简单快速地解决冲突。
Membership changes(成员变更):Raft 在更改集群中服务器集的机制中使用了一个 联合共识(joint consensus) 的方法。在联合 ...
一文了解一致性哈希
对于分布式存储,在不同机器上存储不同对象的数据,我们通过使用哈希算法来建立从数据到服务器之间的映射关系。
为什么需要一致性哈希使用简单哈希算法的例子就是m = hash(o) mod n,其中o为对象,n为机器数量,得到的m为机器编号,hash()为选用的哈希函数。
考虑以下场景:
3个机器节点,有10个数据哈希值为1,2,3…10。使用的哈希算法为m = hash(o) mod 3,其中机器0上保存的数据有3,6,9,机器1上保存的数据有1,4,7,10,机器2上的数据保存的是2,5,8。
当增加一台机器后,n=4,此时通过哈希算法索引数据所在节点编号时会发生变化,如数据4会保存的机器是编号0而不再是1,所以数据也需要根据集群节点的变化而迁移。当集群中数据量较大时,使用这种简单哈希函数所导致的迁移带来的开销将是集群节点难以承担的,在分布式存储系统中,这意味着如果想要增加一台机器时,就要停下服务,等待所有文件重新分布一次才能对外重新提供服务,而一台机器掉线时,尽管只掉了一部分数据,但所有数据访问路由都会出现问题,导致整个服务无法平滑的扩缩容,成为了有状态的服务,这种问题又被称为reha ...
一文了解Go语言Sync标准库
写在前面Go语言是一门在语言层面支持用户级线程的高级语言,因此并发同步在Go程序编写中尤其重要,其中channel虽然作为并发控制的高级抽象,但它的底层就是依赖于sync标准库中的mutex来实现的,因此了解sync标准库是每一个Gopher的必备技能之一。
笔者使用的Go版本是1.18.1
sync.WaitGroupsync.WaitGroup使得多个并发执行的代码块在达到WaitGroup显式指定的同步条件后才得以继续执行Wait()调用后的代码,即达到并发goroutine执行屏障的效果。
在以下代码中,我们希望达到多个goroutine异步执行完输出任务后,main goroutine才退出的效果,此时程序执行完毕。转换为实例,就是使得程序输出110,此处我们并不关心main()中创建的两个goroutine之间的执行顺序。
12345678910111213package mainimport "fmt"func main() { go func() { fmt.Print(1) }() go func ...
一文了解Go语言HTTP标准库
基于HTTP构建的服务标准模型包括客户端Client和服务端Server。HTTP请求从客户端发出,服务端接收到请求后进行处理,然后响应返回给客户端。因此HTTP服务器的工作就在于如何接受来自客户端的请求,并向客户端返回响应。典型的HTTP服务如下图:
Client以下是一个简单示例,在例子中,我们通过http标准库向给定的url:http://httpbin.org/get发送了一个Get请求,请求参数为name=makonike。
1234567891011121314151617package mainimport ( "fmt" "io" "net/http")func main() { resp, err := http.Get("http://httpbin.org/get?name=makonike") if err != nil { return } defer resp.Body.Close() body, _ := io.ReadAll(resp.Bod ...
一文了解事务
简化容错,不惧失败在实际的生产环境中,分布式数据系统面临着命运的裁决,诸多不幸随时可能发生:
系统侧:数据库软件和硬件系统在任何时间都有可能会发生故障
应用侧:应用程序在任意时刻都可能会崩溃
网络侧:数据库与应用、或与其他数据库节点的连接随时可能断开
并发:多个客户端并发写入时,可能会有竞态条件和相互覆盖
半读:一个客户端可能会读到部分更新的数据库
复杂度是不灭的,只能转移。为了实现可靠性,数据库必须处理这些故障,如果数据库对这些故障不做任何处理,应用层就需要处理上述所有相关问题,会极大的增加应用侧编程的复杂度。事务,就是为简化应用编程模型而生的,事务为应用程序提供了安全保证(safety guarantees),使得应用程序可以自由地忽略某些潜在的错误情况和并发问题。
简单来说,事务(transaction) 是将多个读写操作组合成一个逻辑单元进行执行,并提供一种保证,事务中的所有操作被视作单个操作来执行:整个事务要么成功(提交commit),要么失败(被动终止abort,或主动回滚rollback)。如果事务执行失败,应用程序可以安全地重试,不用担心存在部分失败的情况,即某些操 ...
2022年总结:勇敢迈进,开拓自我
技术随手写写,希望以后内容会更丰富。
输出纵观我的个人网站,发现基本都是今年发文的。= =这也怪我太懒了,之前出于好奇整了这个butterfly主题的博客,静态托管到github pages后就直接忘了,没有再管过,尽管学习笔记也有一直记着。今年发文后,我很明显的感觉到我的短板在总结这方面,在开启第一场面试之后感觉就更为明显,这也加快了我养成学习时同时输出的习惯。
笔记这方面,今年正式放弃了使用已久的语雀,转而使用飞书文档来作为笔记工具。语雀呢我觉得这个产品确实挺好的,但是有些时候用起来感觉确实挺不爽的。一方面是大文件的加载方面,我这有一个内容比较多的文档,图片很多,导致全文也显得很长,打开的时候就需要加载好几秒,而且阅读到一半发现个typo,希望修改一下,点击编辑按钮进入编辑界面,又得加载好几秒,编辑完成后保存,又得好几秒。现在看了一下貌似快了很多,但是编辑和只读状态的切换还是太久了。飞书在这方面就做的很好,在我刚开始使用飞书的时候,还是没有阅读状态的,但是现在开始灰度阅读状态和宽度显示了,弥补了我对笔记工具一部分的需求。另一方面呢是语雀好像开始限制免费用户了,将免费版降级为了体验版 ...
一文了解OS-内存布局
揭开操作系统内存的面纱众所周知,每个程序都有属于它自己的源程序,通过翻译、链接阶段可以得到它的ELF可执行目标文件。ELF可执行目标文件则是将这个程序的代码和数据按照一定的格式组织在这个文件中,其中包含了段头部表、ELF头、节头部表和若干的节(section)。在ELF文件中,会为这个文件的每一条指令和数据分配一段虚拟地址,在加载ELF文件时,按照虚拟地址的大小来组织就能得到一个虚拟地址空间的布局。
当存在多个程序时,由于它们的ELF可执行目标文件里的虚拟地址都是一样的,因此它们自己的虚拟地址空间的范围都是从0到虚拟内存的最大值,这便是虚拟内存的作用之一,隔离程序内存。不同的是它们的指令和代码都不一样,因此对于一模一样的虚拟地址空间而言,其使用情况不一样。当程序运行时,只需要将ELF可执行目标文件加载到物理内存中,此时只需要加载使用到的指令和数据(按需加载),因此尽管物理内存不大,操作系统却可以在内存中同时维护着多个程序。对于物理内存地址和虚拟内存地址的映射维护,则交由页表来管理。
总而言之,虚拟内存其实是不可见的,虚拟内存中的虚拟地址只是一个存在于物理内存上的值,通过页表映射到实际 ...
走近bolt
飞书文档思维笔记-走近bolt
一文了解OS-中断
一步步认识中断想要认识中断,我们必须要知道中断是什么,中断在操作系统中起到了什么作用,为什么中断是必不可少的。
我们先来看看操作系统与外部设备交互的过程,其中有两种交互方式,一种是直接通过汇编指令,另一种就是使用中断机制。
由于需要兼容多种底层设备,CPU不方便直接去操作外部设备,因此需要加一个中间层–设备管理器来控制与外部设备的交互。(每一种外部设备都有一个设备控制器)设备管理器中包括了与CPU交互的三个主要的寄存器,状态寄存器、命令寄存器与数据寄存器,以及与设备交互的控制电路,还有一个用于接收数据的缓冲区。其中状态寄存器存储了状态指示当前设备是否正在忙碌,又或者说是否处于就绪状态,命令寄存器存储了CPU需要执行的指令,而数据寄存器则存储了CPU传输给设备,或者设备传入到设备控制器的数据。缓冲区用于接受和缓存数据,等待数据达到了缓冲区大小才将数据放入内存,避免了频繁占用总线开销大。
众所周知,CPU的运算速度远远高于存储设备、外部硬件设备的操作速度(比如说网卡有时不是一时间将所有数据都接收到,可能会有延时)CPU需要去查看外部设备是否正在忙碌,此时使用的是轮询、忙等待的方式。
那 ...