谈笑风生间

对于分布式存储，在不同机器上存储不同对象的数据，我们通过使用哈希算法来建立从数据到服务器之间的映射关系。 为什么需要一致性哈希 使用简单哈希算法的例子就是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，所以数据也需要根据集群节点的变化而迁移。当集群中数据量较大时，使用这种简单哈希函数所导致的迁移带来的开销将是集群节点难以承担的，在分布式存储系统中，这意味着如果想要增加一台机器时，就要停下服务，等待所有文件重新分布一次才能对外重新提供服务，而一台机器掉线时，尽管只掉了一部分数据，但所有数据访问路由都会出现问题，导致整个服务无法平滑的扩缩 ...

写在前面 Go 语言是一门在语言层面支持用户级线程的高级语言，因此并发同步在 Go 程序编写中尤其重要，其中 channel 虽然作为并发控制的高级抽象，但它的底层就是依赖于 sync 标准库中的 mutex 来实现的，因此了解 sync 标准库是每一个 Gopher 的必备技能之一。 笔者使用的 Go 版本是 1.18.1 sync.WaitGroup sync.WaitGroup 使得多个并发执行的代码块在达到 WaitGroup 显式指定的同步条件后才得以继续执行Wait()调用后的代码，即达到并发 goroutine 执行屏障的效果。 在以下代码中，我们希望达到多个 goroutine 异步执行完输出任务后，main goroutine 才退出的效果，此时程序执行完毕。转换为实例，就是使得程序输出 110，此处我们并不关心main()中创建的两个 goroutine 之间的执行顺序。 12345678910111213package mainimport "fmt"func main() { go func() { fmt. ...

基于 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.R ...

简化容错，不惧失败 在实际的生产环境中，分布式数据系统面临着命运的裁决，诸多不幸随时可能发生： 系统侧：数据库软件和硬件系统在任何时间都有可能会发生故障 应用侧：应用程序在任意时刻都可能会崩溃 网络侧：数据库与应用、或与其他数据库节点的连接随时可能断开 并发：多个客户端并发写入时，可能会有竞态条件和相互覆盖 半读：一个客户端可能会读到部分更新的数据库 复杂度是不灭的，只能转移。为了实现可靠性，数据库必须处理这些故障，如果数据库对这些故障不做任何处理，应用层就需要处理上述所有相关问题，会极大的增加应用侧编程的复杂度。事务，就是为简化应用编程模型而生的，事务为应用程序提供了安全保证（safety guarantees），使得应用程序可以自由地忽略某些潜在的错误情况和并发问题。 简单来说，事务（transaction） 是将多个读写操作组合成一个逻辑单元进行执行，并提供一种保证，事务中的所有操作被视作单个操作来执行：整个事务要么成功（提交 commit），要么失败（被动终止 abort，或主动回滚 rollback）。如果事务执行失败，应用程序可以安全地重试，不用担心存在部分失败的情况， ...

技术 随手写写，希望以后内容会更丰富。 输出 纵观我的个人网站，发现基本都是今年发文的。= =这也怪我太懒了，之前出于好奇整了这个 butterfly 主题的博客，静态托管到 github pages 后就直接忘了，没有再管过，尽管学习笔记也有一直记着。今年发文后，我很明显的感觉到我的短板在总结这方面，在开启第一场面试之后感觉就更为明显，这也加快了我养成学习时同时输出的习惯。 笔记这方面，今年正式放弃了使用已久的语雀，转而使用飞书文档来作为笔记工具。语雀呢我觉得这个产品确实挺好的，但是有些时候用起来感觉确实挺不爽的。一方面是大文件的加载方面，我这有一个内容比较多的文档，图片很多，导致全文也显得很长，打开的时候就需要加载好几秒，而且阅读到一半发现个 typo，希望修改一下，点击编辑按钮进入编辑界面，又得加载好几秒，编辑完成后保存，又得好几秒。现在看了一下貌似快了很多，但是编辑和只读状态的切换还是太久了。飞书在这方面就做的很好，在我刚开始使用飞书的时候，还是没有阅读状态的，但是现在开始灰度阅读状态和宽度显示了，弥补了我对笔记工具一部分的需求。另一方面呢是语雀好像开始限制免费用户了，将免费版 ...

揭开操作系统内存的面纱 众所周知，每个程序都有属于它自己的源程序，通过翻译、链接阶段可以得到它的 ELF 可执行目标文件。ELF 可执行目标文件则是将这个程序的代码和数据按照一定的格式组织在这个文件中，其中包含了段头部表、ELF 头、节头部表和若干的节（section）。在 ELF 文件中，会为这个文件的每一条指令和数据分配一段虚拟地址，在加载 ELF 文件时，按照虚拟地址的大小来组织就能得到一个虚拟地址空间的布局。 当存在多个程序时，由于它们的ELF 可执行目标文件里的虚拟地址都是一样的，因此它们自己的虚拟地址空间的范围都是从 0 到虚拟内存的最大值，这便是虚拟内存的作用之一，隔离程序内存。不同的是它们的指令和代码都不一样，因此对于一模一样的虚拟地址空间而言，其使用情况不一样。当程序运行时，只需要将 ELF 可执行目标文件加载到物理内存中，此时只需要加载使用到的指令和数据（按需加载），因此尽管物理内存不大，操作系统却可以在内存中同时维护着多个程序。对于物理内存地址和虚拟内存地址的映射维护，则交由页表来管理。 总而言之，虚拟内存其实是不可见的，虚拟内存中的虚拟地址只是一个存在于物理内 ...

飞书文档思维笔记 - 走近 bolt

一步步认识中断 想要认识中断，我们必须要知道中断是什么，中断在操作系统中起到了什么作用，为什么中断是必不可少的。 我们先来看看操作系统与外部设备交互的过程，其中有两种交互方式，一种是直接通过汇编指令，另一种就是使用中断机制。 由于需要兼容多种底层设备，CPU 不方便直接去操作外部设备，因此需要加一个中间层——设备管理器（每一种外部设备都有一个设备控制器）来控制与外部设备的交互。设备管理器中包括了与 CPU 交互的三个主要的寄存器，状态寄存器、命令寄存器与数据寄存器以及与设备交互的控制电路，还有一个用于接收数据的缓冲区。其中状态寄存器存储了状态指示当前设备是否正在忙碌，或者处于就绪状态，命令寄存器存储了 CPU 需要执行的指令，数据寄存器存储了 CPU 传输给设备，或设备传入到设备控制器的数据。缓冲区用于接收和缓存数据，等待数据达到了缓冲区大小才将数据放入内存，避免了频繁占用总线开销大。 众所周知，CPU 的运算速度远远高于存储设备、外部硬件设备的操作速度（如网卡并不是一瞬间将所有数据都接收到，可能存在一个过程），CPU 需要去查看外部设备是否正在忙碌，此时使用的是轮询、忙等待的方式。 ...

GoFound 去发现，去探索全文检索的世界，一个小巧精悍的全文检索引擎，支持持久化和单机亿级数据毫秒级查找。 基础概念 全文检索 全文检索一般有两种方法。一是从头到尾扫描作为检索对象的文档，以此来搜索要检索的字符串，如 Unix 中的grep命令，但是文档数量越多，文档越大，检索的时间会越长，甚至超出预期上限。另一种是利用索引进行全文搜索，事先为文档建立索引，尽管建立索引可能需要不少时间，但是优点是即使文档的数量增加，检索的速度也不会大幅下降，GoFound 也是采取这种方式。 倒排索引 倒排索引与词典索引类似，用一本书的倒排索引作为示例，key 存储了单词，value 存储了一个组成页数的数组，当你需要查找I search keywords in Google.这句话时，你可以很直观的看到它的单词在哪一页。 倒排索引中，每个单词都有一个引用指向属于它的一个倒排列表，倒排列表中存储了众多的倒排项，倒排项即文档 ID。取出多个单词的倒排列表后，可以根据情况进行交集处理与评分，获取到更符合预想的搜索结果。 正排索引 正排索引存储了文档 id 和索引词组的映射，便于在修改索引时判断索引 ...

什么是 LSM-Tree SSTables 的结构 想要了解 LSM-Tree（Log Structured Merge Tree，日志结构合并树），我们得先了解 SSTables。SSTables 即排序字符串表（Sorted String Table），也是 LSM-Tree 里的核心数据结构。它的概念来自 Google 的 Bigtable 论文，大概的意思就是，SSTable 是一种可持久化，有序且不可变的键值存储结构，key 和 value 都可以是任意的字节数组，并且给提供了按照指定 key 查找和指定范围的 key 区间迭代遍历功能。 如下图所示，该图表示一个个日志结构存储数据段文件：为了避免最终用完磁盘空间，才将日志分为特定大小的段，对旧段文件进行压缩和合并，在新的日志文件中只保留每个键的最近更新。这种情况下，由于旧段的内容不会被修改，因此合并的段可以放入一个新的文件，旧段的合并和压缩都可以在后台线程完成，请求时仍然使用旧段处理，而完成合并后，就能直接删除旧段，使用新的合并段。 日志中稍后的值优先于日志中较早的相同键的值 怎么保证最近更新？ 每个段都包含在一段时间 ...