-
Algorithm-Graph(Basic)
NOTE: 内容来自于 算法4, 主要记录个人对其中算法的理解。有兴趣或者需要 Java 源码可以直接阅读 online website graph. Enjoy it:) 图 图结构是现实世界的一个重要抽象,表达的是实体间的关联关系,广泛存在于多种场景中,比如: 地图:非常直接的图关系,地点是顶点,道路是路径。 人际关系和社交网络:每个人有多个好友,好友又有好友,可能存在环状的相识链,好友关系一般是双向关系,而微博等平台的关注关系则是单向关系。 网站超链接:网站作为经典的分布式应用,网站内部通过维护其他网站超链接的方式组成一个超大规模图。 商品调度/贸易关系/软件设计:这些场景都涉及了多个模块之间的交互,自然存在顶点和连接的图抽象。 经典的图可以分成... Read More
-
Precision Loss of Float
Background 今天讲个轻松一点的话题,关于浮点型数的精度丢失问题,它源于我对3 个问题的疑问: 二进制表示十进制小数的天然精度丢失,比如十进制 0.1 对应的二进制是 0.00(1100)(1100)… 浮点数本身对小数点后可表示位数有限制,导致对小数点后数据本身就会截断,比如 1.123456789 可能就只能表示成 1.123457 这个比较诡异,float 最大可表示范围可以达到 $2^{127}$,但是实际上当一个整数大于 $2^{24}$ 的时候,还是出现了整数精度丢失问题,导致一些程序在用 float 解析一些大数时需要使用 decimal string 来表示 “100000123”。 在 online compiler 上运行以下测试程序: ... Read More
-
Simple-Paxos
Background 这篇博客主要讲下 Simple-Paxos 算法,它属于分布式系统多备份一致性(consistency)的领域, 这里的 consistency 说的是 recency requirement,即多备份场景下数据的 newest write 会被什么时候看到。 分布式系统多备份源于人们对于 fault-tolerant system 的需求。单份数据时代人们对 durability 的要求是数据能写入到 non-volatile 的介质中(HDD/SSD),后来人们发现如果出现了磁盘故障无法恢复,机房火灾,地震等不可抗自然因素下,数据还是无法恢复。 于是,对数据 durability 的要求自然变成了=> 同一份数据是否可以保持多备份,复制到不同的机房... Read More
-
Transaction(Basic)
Background Transaction 是数据并发读写操作的一种抽象。这种读写操作的特点是: 读写并发 可以涉及 single-object 或者 multi-objects 在没有 transaction 抽象之前,就需要考虑很多边界问题,比如: 操作 multi-objects 部分失败了,则成功的部分也会回滚,否则会出现数据不一致。 并发写同时读取到旧值后,然后执行自增操作,导致更新丢失。 并发读写导致读到了部分旧值,部分新值。 写操作给用户返回成功了,系统 crash 或者 power cutoff 导致数据丢失。 等等这些问题都可以称为数据异常 data anomaly。 事务一般和 RDMS(Related Database M... Read More
-
Linux Kernel-Schedule-Processes
进程调度是内核运行调度的核心章节,主要内容涉及 2 个方面: 进程切换,这是分时复用抽象的核心机制,涉及进程切换时机和切换机制。 进程优先级调度,动态调整进程优先级,满足进程公平调度需求,同时满足业务对不同形态进程的调度需求。 进程优先级调度 在设计任务调度问题时,有几个通用的问题: 任务是否有不同的重要程度?是否需要设置不同的优先级? 任务是否存在不同的类型?不同类型之间的优先级是否可以互相比较? 任务调度使用什么算法?是否能保证不同进程能合理获取 CPU 时间,不至于在一段长时间间隔内无法运行? 进程运行时类型 linux 内核根据任务对资源的使用方式将进程分成 3 类: 交互式进程:频繁等待外部输入,比如等待鼠标和键盘的输入,要求有响应外部事... Read More
-
Linux Kernel-From User Space To Kernel Space
在上一个博客中,我们介绍了进程管理相关的内核概念。进程管理是从内核角度看待问题,因为对于内核而言,所有的代码和数据,包括用户代码和数据,都属于动态内核的一部分,因为他们都维护在内核提供的进程描述符 task struct 中。 但是这部分视角是用户感知不到的,从编程人员的角度看,编程的时候内核其实完全不存在,或者说只存在一些编程规范而已,比如函数逻辑要从 main 开始,要区分堆栈,要区分进程和线程。所以这篇博客我们要再切换下视角, 观察下用户视角和内核视角下,用户代码和内核代码是如何切换运行。 用户态和内核态 这两个概念对于做后台开发的同学而言很熟悉,最常听见的说法是:要减少用户态到内核态的切换,避免不必要的开销。要说清楚这两个概念,我们也从几个问题开始: 用户态和内核态是... Read More
-
Linux Kernel-Manage Processes
在之前的博客中,我们一直在介绍内存相关的话题,因为我觉得内存是一切逻辑和数据的载体,先搞清楚事物的存在形式,再讨论事物的组织形式和运作形式,会更容易理解完整的流程。 所以我们从最核心的内核加载到物理内存出发,介绍到物理内存页的管理和小内存分配,再到最后内核给业务实体提供的抽象概念:进程线性地址空间。关于内存的一些核心概念我觉得大致上介绍完了, 注意实际实现还是很复杂的,需要考虑效率上的诸多细节。 这篇开始我们专注于 CPU 相关的概念,也就是事物是如何组织和运行的。 在开始之前,让我们再次在脑海中想象下操作系统这艘航母是如何轰鸣启动的。 在硬件通电,用户按下电源键的一瞬间,CPU 硬件单元如同蒸汽机被灌入第一缕蒸汽一般开始跃动。首先它会读取 ROM 内存特定位置存放的 BI... Read More
-
Linux Kernel-Process Address Space
进程线性地址空间 我们在之前的博客中尝试描述了内核加载进物理内存,物理内存划分和物理页框管理 buddy system 以及内核小对象内存管理器 slab system,这三部分内容 主要想要读者能以线性思维理解: 作为内核的代码和数据是在什么时机加载到物理内存的, 以及内核加载之后是如何管理和分配物理内存的, 至此内核的存在形式,不再神秘,但仍然复杂。 内核充分初始化后,具有了分配整个 page frame 和任意固定大小内存块的能力,充分满足了内核各个模块的内存分配需求,虽然其中的细节很复杂。接下来开始 我们的重头戏: 进程是什么? 进程在哪里? 进程中提及的堆、栈以及更宽泛概念的进程线性地址空间是什么? 这是几个看起来简单但是很有趣的问题,它是一... Read More
-
Linux Kernel-Slab System And Hardware Cache
slab 对象内存分配器 前面一篇博客我们从比较大的方面讲内核是如何管理和利用物理内存的,这篇博客我们讲在一个连续的内存区间中,内存是如何被管理的。 其实细想下就可以理解,实际用户和内核很少会按照页的模式申请内存,反而是按照 对象的大小 申请内存,而一般的对象可能都在 100 bytes 以内,所以如何将一个连续的内存块进行切分,提高内存利用率的同时减少内部碎片就成了一个研究课题。我们今天讲的 slab system 还会 涉及到 L1/L2/L3 高速缓存硬件。 连续内存区间的内存管理其实我们一直都在接触,比如我们平时调用 New/Delete 和 malloc/free 的时候其实底层就是一个 ptmalloc 的内存池,算法大体上是先分配一块大的连续内存,然后以某种方式切分成... Read More
-
Linux Kernel-Page Frame Managerment And Buddy System
物理页框维护 上一篇博客我们介绍了内核的内存管理,内核被加载到了物理内存的低位(1M)开始的位置,但是内核的线性地址被平移到了 [3G, 4G),通过内核页表维护 这种映射关系。所有进程的 [3G, 4G) 页表项都从内核页表中拷贝过来,从而实现将内核映射到进程线性地址空间的高 1G。 今天我们介绍内核是如何管理物理页框的,因为不管是内核还是进程,在解析线性地址时都可能需要分配对应的物理页框。内核维护物理页框 需要元数据,这些元数据空间需要实际的物理内存占用,所以为了避免鸡生蛋蛋生鸡的循环,物理页框的元数据直接在内核的数据段,不需要 通过内核分配器分配内存。 对于物理页框,我们需要描述物理页框的特权级、用途、引用计数、页框链接头等信息,所以实际每个物理页框需要 32bit 的页框... Read More
-
Linux Kernel-Memory Layout
内核镜像文件 前面我们介绍了内核中关于内存的分段和分页,介绍了 CPU 在处理指令地址和数据地址时经历的流程,从而得到真正的物理地址,访问内存中的 指令和数据。但是在末尾,还是提出了我们的疑问,虽然单个地址的操作可以理解,但是还是没搞清楚内核在这个流程中是如何交互的。内核到底在哪里。 今天我们开始从 Linux Kernel 加载开始讲内核的内存管理。前面我们说过,Linux Kernel 在静态上是数据和指令按特定规范组织在一起的文件, 大概就是文件头包含一些文件的元信息,比如有哪些段,每个段在文件中的偏移基址/长度,符号表等信息。这里的段是个抽象概念,是同属性事物 的集合,比如所有已经被初始化的全局变量放在数据段,没有被初始化的全局变量放在 BSS 段,指令放在代码段。所以我们... Read More
-
Linux Kernel-Memory Segment and Paging System
从今天开始我们会讲 Linux Kernel 内存管理相关的内容,因为这部分比较庞杂,有些设计上的考量没有完全搞清楚,所以会长期处于 WIP 状态。 奇怪的段寄存器 如果你之前看过一些 Linux Kernel 内存管理和内核源码,你会看到类似下面这种汇编指令片段: movl $(__KERNEL_DS),%eax movl %eax,%ds movl %eax,%es 这里的 ds 和 es 是两个段寄存器。这是我们不太熟悉的概念,可以说进程线性地址空间和分页管理还比较好理解,最终我们都能拿到一个整数的 地址值。CPU 直接将整数的物理地址放在通用寄存器中,然后通过内存总线对内存硬件进行寻址就行,为什么要搞出段寄存器的概念?讲述内存管理 是从我们最不熟悉的段概念开始。接下来我们... Read More
-
Mock
在一些系统设计方法论配合下,利用 Mock 可以很好得实现系统内多组件测试需求。具体而言就是: 在系统设计上,关注整体在时间和空间维度上的复杂度切分,明确定义和约束模块间交互的状态,控制模块间测试复杂度 单个模块内,利用 Base Class + Mock + Dependency Inject 实现模块功能,以便在单元测试中覆盖尽可能多的分支 最近想到一件事情,Tiflow 的单元测试好像变好了,主要是在单元测试中包含了更多的多组件 Mock 测试,可以覆盖更加丰富的多组件交互场景。 让我有这个想法的原因是,刚毕业的时候写代码主要还是写逻辑,工作了一段时间后虽然老的项目里也有单元测试,不过更多的是测试某个独立函 数在实现上是否符合预期,需要覆盖... Read More
-
What The Linux Kernel Is
Linux Kernel 是个超级复杂的状态机,而内核镜像本身只是包含内核数据和内核指令的文件,这种文件按照内核文件规范组织内核数据和指令 。 其中内核数据本身包含了维护内核状态的基础数据,动态申请的数据则通过内核数据中的地址引用来实现寻址访问。 内核指令则描述了不同场景下内核数据的变更流程 内核是什么 上一篇博客中我们简要介绍了在我们程序背后,Linux Kernel 做了什么样的抽象。在我尝试进一步描述 Linux Kernel 如何做资源抽象和管理之前, 需要先说清楚 Linux Kernel 是什么。 Linux Kernel 是用户程序和硬件的中间层 首先 Linux Kernel 肯定是用户程序和硬件的中间层,因为我们在写代码的时候几... Read More
-
What The Linux Kernel Does
为了更好得设计 Tiflow engine 的资源管控能力,我阅读了《Understanding The Linux Kernel》和思考了 Linux Kernel 关于资源管理的抽象, 越要提高资源利用率,越要将资源切小 越要提高资源管控能力,越要提供整体化视图 背景 最近团队在开发一个数据迁移的统一资源调度平台 Tiflow Engine,以便统一抽象 Data Platform 团队多个产品的资源调度能力和 Failover 能力。从 DP 产品能力上看,我们其实希望 Tiflow Engine 的最终形态是类似 Flink 这种流式计算框架,通过统一的流式算子抽象和 UDF 构建端到端的数据库同步流。至于为什么不直接使用 Flink 而... Read More
-
TiDB Online DDL In TiCDC
TiCDC 作为 TiDB 的数据同步组件,负责直接从 TiKV 感知数据变更同步到下游。其中比较核心的问题是数据解析正确性问题,具体而言就是如何使用正确的 schema 解析 TiKV 传递过来的 Key-Value 数据,从而还原成正确的 SQL 或者其他下游支持的形式。本文主要通过对 TiDB Online DDL 机制原理和实现的分析,引出对当前 TiCDC 数据解析实现的讨论。 背景和问题 数据同步组件是数据库生态中不可或缺的生态工具,比较知名的开源单机数据库 MySQL 就将数据同步作为 Server 能力的一部分,并基于 MySQL binlog 实现异步/半同步/同步的主从复制。 由于 MySQL 悲观事务模型和表元数据锁的存在,我们总是可以认为 MyS... Read More