一个自制简易数据库 KxDB

背景 启发自一位富裕女同事推荐的 CMU:15-445 与 15-721 数据库课程,但大部分都已经学过了,于是改头换面,顺便记录一下 Google 基于 BigTable 实现的 Percolator 事务算法。 设计初衷: 存储层框架 LSM 树 在写入时,LSM 树假设了磁盘文件数据的写入是有序的,如果输入数据无序,则会使用内存的有序数据结构,如跳表、红黑树(本设计采用红黑树),在一定量后溢…

数据仓库维度建模笔记

维度建模模型本质是对关系模型的修补,提出缓慢变化维度的处理方案,使其更适用于记录历史数据,同时提出一致性理论,使得新的业务也可以从数仓总线中复用原有的数据。 数据仓库的建模第一步与关系建模过程一样,从业务过程开始分析,关系模型关注业务过程所需的字段,而服务于分析系统的维度建模,在此基础上还需要关心分析需求的指标(推动埋点的设计);然后构建总线矩阵梳理出原子粒度的维度表与事实表,生成 DWD 层明细…

探究 HBase Cluster Replication

Cluster Replication 在 HBase 中不是一件容易的事情(但似乎 HBase 中就没有容易的事情 🙃)。 在阅读本文之前,首先需要了解 Sequence ID(以下简称 SeqId),在 HBase 中,一个 Region 的 SeqId 相当于代表该 Region 的“年龄”,新的 Region(比如新表刚创建,或者刚由父 Region Split 出来的两个子 Region…

从 HDFS 到 HBase 的 RPC 设计思路

两者虽然都依赖了 ProtoBuf,但都暗藏玄机。 总的来说,HDFS 的 RPC 分为两个大类:普通与流式 RPC,普通 RPC 全程传递的都是 ProtoBuf 编码对象,流式 RPC 则分为两段数据,一段 ProtoBuf 编码对象,一段一系列的 Packet 数据包。HBase 的 RPC 主要应用是批量传递 Cell[] 数据单元组,因此 HBase 使用未经 ProtoBuf 编码的 …

HDFS 基于 Unix Socket 的短路读与中心化缓存的实现演进

在 SSD 集群的 HBase 中, 硬盘 I/O 可能可以已经可以支撑很高的 QPS,但基于 HDFS 短路读的 HBase 在实际测试中可能并不如预期,这是因为短路读在共享内存的分配与回收上,其 QPS 也是非常高且消耗资源的 。所以 —— 短路读为什么依赖共享内存?直接传递文件描述符不可以吗? 在展开后文之前,需要说明,基于 UNIX Socket 在多进程间传递文件描述符,传递行为需要使用…

简易算法原理与实现手册

排序算法 快速排序 快速排序定义了 Pivot 中枢值,每次排序的目标是(下文均以升序为例),希望排序后的 Pivot 值位置的左区间都比 Pivot 值小,右区间都比 Pivot 值大,也就是希望排序后,Pivot 值位置是正确的,且左右区间都对 Pivot 值偏序。 因此在递归树中,每层能绕过扫描的数据是树上层确定位置的 Pivots 集合。当 Pivot 每次都选择在中位数上,每层分别确定出…

Raft 分布式一致性协议笔记

Raft 是一种用来管理日志复制一致性算法。 基本概念 算法限定每个 Server 只能为以下三种状态之一:Leader、Follower 和 Candidate。 算法通过强化 Leader 地位简化日志副本的管理,比如日志项只允许从 Leader 流向 Follower。 因此 Raft 把算法分解为三个子问题: 选主(Leader Election) 日志复制(Log Replication…