Nothing is built on stone; all is built on sand, but we must build as if the sand were stone. —Jorge Luis Borges

What is Lock I’ve been pondering this topic for a long time and have written about it extensively. However, I was never quite satisfied. Recently, during some interviews, I found new inspiration. My first encounter with the concept of a “lock” was in multi-threaded programming. Locks are essential tools to ensure data integrity when multiple c... Read More

Background I haven’t updated my blog for a long time. Over the past year, I relocated and embarked on a job search journey. This experience was challenging but also enlightening, as it helped me understand the intricacies of the process. The language of this blog will be straightforward. It aims to review a notable system design experience that... Read More

NOTE: The content is derived from Algorithms, 4th Edition, mainly recording personal understanding of the algorithms. If you are interested or need the Java source code, you can directly read the online website graph. Enjoy it:) Graphs Graph structures are an important abstraction of the real world, representing relationships between entit... Read More

Background Today, let’s discuss a lighter topic about the precision loss of floating-point numbers. This stems from my curiosity about 3 questions: The inherent precision loss when representing decimal numbers in binary, such as the decimal 0.1 which corresponds to the binary 0.00(1100)(1100)… The limitation of floating-point numbers in re... Read More

Background This blog post mainly discusses the Simple-Paxos algorithm, which belongs to the field of distributed system multi-replica consistency. Here, consistency refers to the recency requirement, i.e., when the newest write in a multi-replica scenario will be seen. The need for multi-replica in distributed systems arises from the demand fo... Read More

Background Transaction is an abstraction of concurrent read and write operations on data. The characteristics of these operations are: Concurrent reads and writes Can involve single-object or multi-objects Before the abstraction of transactions, many boundary issues needed to be considered, such as: If part of the operations on multi-... Read More

进程调度是内核运行调度的核心章节，主要内容涉及 2 个方面： 进程切换，这是分时复用抽象的核心机制，涉及进程切换时机和切换机制。 进程优先级调度，动态调整进程优先级，满足进程公平调度需求，同时满足业务对不同形态进程的调度需求。 进程优先级调度 在设计任务调度问题时，有几个通用的问题： 任务是否有不同的重要程度？是否需要设置不同的优先级？ 任务是否存在不同的类型？不同类型之间的优先级是否可以互相比较？ 任务调度使用什么算法？是否能保证不同进程能合理获取 CPU 时间，不至于在一段长时间间隔内无法运行？ 进程运行时类型 linux 内核根据任务对资源的使用方式将进程分成 3 类： 交互式进程：频繁等待外部输入，比如等待鼠标和键盘的输入，要求有响应外部事... Read More

在上一个博客中，我们介绍了进程管理相关的内核概念。进程管理是从内核角度看待问题，因为对于内核而言，所有的代码和数据，包括用户代码和数据，都属于动态内核的一部分，因为他们都维护在内核提供的进程描述符 task struct 中。 但是这部分视角是用户感知不到的，从编程人员的角度看，编程的时候内核其实完全不存在，或者说只存在一些编程规范而已，比如函数逻辑要从 main 开始，要区分堆栈，要区分进程和线程。所以这篇博客我们要再切换下视角， 观察下用户视角和内核视角下，用户代码和内核代码是如何切换运行。 用户态和内核态 这两个概念对于做后台开发的同学而言很熟悉，最常听见的说法是：要减少用户态到内核态的切换，避免不必要的开销。要说清楚这两个概念，我们也从几个问题开始： 用户态和内核态是... Read More

在之前的博客中，我们一直在介绍内存相关的话题，因为我觉得内存是一切逻辑和数据的载体，先搞清楚事物的存在形式，再讨论事物的组织形式和运作形式，会更容易理解完整的流程。 所以我们从最核心的内核加载到物理内存出发，介绍到物理内存页的管理和小内存分配，再到最后内核给业务实体提供的抽象概念：进程线性地址空间。关于内存的一些核心概念我觉得大致上介绍完了， 注意实际实现还是很复杂的，需要考虑效率上的诸多细节。 这篇开始我们专注于 CPU 相关的概念，也就是事物是如何组织和运行的。 在开始之前，让我们再次在脑海中想象下操作系统这艘航母是如何轰鸣启动的。 在硬件通电，用户按下电源键的一瞬间，CPU 硬件单元如同蒸汽机被灌入第一缕蒸汽一般开始跃动。首先它会读取 ROM 内存特定位置存放的 BI... Read More

进程线性地址空间 我们在之前的博客中尝试描述了内核加载进物理内存，物理内存划分和物理页框管理 buddy system 以及内核小对象内存管理器 slab system，这三部分内容 主要想要读者能以线性思维理解： 作为内核的代码和数据是在什么时机加载到物理内存的， 以及内核加载之后是如何管理和分配物理内存的， 至此内核的存在形式，不再神秘，但仍然复杂。 内核充分初始化后，具有了分配整个 page frame 和任意固定大小内存块的能力，充分满足了内核各个模块的内存分配需求，虽然其中的细节很复杂。接下来开始 我们的重头戏： 进程是什么？ 进程在哪里？ 进程中提及的堆、栈以及更宽泛概念的进程线性地址空间是什么？ 这是几个看起来简单但是很有趣的问题，它是一... Read More

slab 对象内存分配器 前面一篇博客我们从比较大的方面讲内核是如何管理和利用物理内存的，这篇博客我们讲在一个连续的内存区间中，内存是如何被管理的。 其实细想下就可以理解，实际用户和内核很少会按照页的模式申请内存，反而是按照 对象的大小 申请内存，而一般的对象可能都在 100 bytes 以内，所以如何将一个连续的内存块进行切分，提高内存利用率的同时减少内部碎片就成了一个研究课题。我们今天讲的 slab system 还会 涉及到 L1/L2/L3 高速缓存硬件。 连续内存区间的内存管理其实我们一直都在接触，比如我们平时调用 New/Delete 和 malloc/free 的时候其实底层就是一个 ptmalloc 的内存池，算法大体上是先分配一块大的连续内存，然后以某种方式切分成... Read More

物理页框维护 上一篇博客我们介绍了内核的内存管理，内核被加载到了物理内存的低位(1M)开始的位置，但是内核的线性地址被平移到了 [3G, 4G)，通过内核页表维护 这种映射关系。所有进程的 [3G, 4G) 页表项都从内核页表中拷贝过来，从而实现将内核映射到进程线性地址空间的高 1G。 今天我们介绍内核是如何管理物理页框的，因为不管是内核还是进程，在解析线性地址时都可能需要分配对应的物理页框。内核维护物理页框 需要元数据，这些元数据空间需要实际的物理内存占用，所以为了避免鸡生蛋蛋生鸡的循环，物理页框的元数据直接在内核的数据段，不需要 通过内核分配器分配内存。 对于物理页框，我们需要描述物理页框的特权级、用途、引用计数、页框链接头等信息，所以实际每个物理页框需要 32bit 的页框... Read More

内核镜像文件 前面我们介绍了内核中关于内存的分段和分页，介绍了 CPU 在处理指令地址和数据地址时经历的流程，从而得到真正的物理地址，访问内存中的 指令和数据。但是在末尾，还是提出了我们的疑问，虽然单个地址的操作可以理解，但是还是没搞清楚内核在这个流程中是如何交互的。内核到底在哪里。 今天我们开始从 Linux Kernel 加载开始讲内核的内存管理。前面我们说过，Linux Kernel 在静态上是数据和指令按特定规范组织在一起的文件， 大概就是文件头包含一些文件的元信息，比如有哪些段，每个段在文件中的偏移基址/长度，符号表等信息。这里的段是个抽象概念，是同属性事物 的集合，比如所有已经被初始化的全局变量放在数据段，没有被初始化的全局变量放在 BSS 段，指令放在代码段。所以我们... Read More

从今天开始我们会讲 Linux Kernel 内存管理相关的内容，因为这部分比较庞杂，有些设计上的考量没有完全搞清楚，所以会长期处于 WIP 状态。 奇怪的段寄存器 如果你之前看过一些 Linux Kernel 内存管理和内核源码，你会看到类似下面这种汇编指令片段： movl $(__KERNEL_DS),%eax movl %eax,%ds movl %eax,%es 这里的 ds 和 es 是两个段寄存器。这是我们不太熟悉的概念，可以说进程线性地址空间和分页管理还比较好理解，最终我们都能拿到一个整数的 地址值。CPU 直接将整数的物理地址放在通用寄存器中，然后通过内存总线对内存硬件进行寻址就行，为什么要搞出段寄存器的概念？讲述内存管理 是从我们最不熟悉的段概念开始。接下来我们... Read More

With some system design methodologies, Mock can be used to effectively meet the testing needs of multiple components within a system. Specifically: In system design, focus on the complexity segmentation in time and space dimensions, clearly define and constrain the state of interactions between modules, and control the testing complexi... Read More

Linux Kernel 是个超级复杂的状态机，而内核镜像本身只是包含内核数据和内核指令的文件，这种文件按照内核文件规范组织内核数据和指令 。 其中内核数据本身包含了维护内核状态的基础数据，动态申请的数据则通过内核数据中的地址引用来实现寻址访问。 内核指令则描述了不同场景下内核数据的变更流程 内核是什么 上一篇博客中我们简要介绍了在我们程序背后，Linux Kernel 做了什么样的抽象。在我尝试进一步描述 Linux Kernel 如何做资源抽象和管理之前， 需要先说清楚 Linux Kernel 是什么。 Linux Kernel 是用户程序和硬件的中间层 首先 Linux Kernel 肯定是用户程序和硬件的中间层，因为我们在写代码的时候几... Read More

为了更好得设计 Tiflow engine 的资源管控能力，我阅读了《Understanding The Linux Kernel》和思考了 Linux Kernel 关于资源管理的抽象， 越要提高资源利用率，越要将资源切小 越要提高资源管控能力，越要提供整体化视图 背景 最近团队在开发一个数据迁移的统一资源调度平台 Tiflow Engine，以便统一抽象 Data Platform 团队多个产品的资源调度能力和 Failover 能力。从 DP 产品能力上看，我们其实希望 Tiflow Engine 的最终形态是类似 Flink 这种流式计算框架，通过统一的流式算子抽象和 UDF 构建端到端的数据库同步流。至于为什么不直接使用 Flink 而... Read More

TiCDC is a change data capture tool for TiDB, an open-source, distributed SQL database. TiCDC captures data changes from TiKV and synchronizes them downstream. This article discusses TiCDC’s data parsing implementation and the TiDB Online DDL mechanism. Background and Problem Data replication components are indispensable tools in the datab... Read More