-
浅谈分布式存储之raft
前言分布式一致性是分布式系统中最基本的问题，用来保证分布式系统的高可靠。业界也有很多分布式一致性复制协议：Paxos、Zab、Viewstamped Replication、Raft等。Raft相比于其他共识算法简化了协议中的状态以及交互，更加清晰也更加容易理解实现。这篇文章作为Raft的学习、思考、整理，各种查资料前前后后花了3天时间，包含以下内容，老铁手动点个👍吧。:)Leader Election、Log Replication、Log Recovery、Log Compaction...…
-
浅谈分布式存储之单机对象存储引擎
前言构建大规模分布式存储系统通常需要一个高性能、低延迟、稳定可靠的单机存储引擎。对于不同的分布式存储系统其需要的单机存储引擎也不相同。分布式KV存储通常使用RocksDB等单机KV存储引擎，其特点是value通常很小且不可变；分布式数据库通常也是使用RocksDB作为单机存储引擎；分布式对象存储使用Haystack、Bitcask等作为单机对象存储引擎，本质上也是kv存储，其特点是value可以是1B–5GB且对象不可变；分布式块存储也需要高性能的单机对象存储引擎，其特点是对象是可变的，需...…
-
浅谈Linux内核IO体系之磁盘IO
前言Linux I/O体系是Linux内核的重要组成部分，主要包含网络IO、磁盘IO等。基本所有的技术栈都需要与IO打交道，分布式存储系统更是如此。本文主要简单分析一下磁盘IO，看看一个IO请求从发起到完成到底经历了哪些流程。目录 名词解释 IO体系 VFS层 PageCache层 映射层 通用块层 IO调度层 设备驱动层 物理设备层 FAQ名词解释 Buffered I/O：缓存IO又叫标准IO，是大多数文件系统的默认IO操作，经过PageCache。 Direc...…
-
BlueStore源码分析之事物状态机
前言BlueStore可以理解为一个支持ACID的本地日志型文件系统。所有的读写都是以Transaction进行，又因为支持覆盖写，所以写流程设计的相对复杂一些，涉及到一系列的状态转换。我们着重分析一下状态机、延迟指标以及如何保证IO的顺序性和并发性。目录 状态机 延迟分析 IO保序 线程队列 IO状态 最后YY状态机queue_transactionsqueue_transactions是ObjectStore层的统一入口，KVStore、MemStore、FileStore...…
-
BlueStore源码分析之对象IO
前言BlueStore中的对象非常类似于文件系统中的文件，每个对象在BlueStore中拥有唯一的ID、大小、从0开始逻辑编址、支持扩展属性等，因此对象的组织形式，类似于文件也是基于Extent。目录 稀疏写 名词解释 onode结构 big-write small-write simple-write deferred-write IO流程稀疏写我们知道一个文件的逻辑空间上是连续的，但是真正在磁盘上的物理空间分布并不一定是连续的。同时我们也会使用lseek系统调用，使得文...…
-
BlueStore源码分析之Cache
前言BlueStore使用DIO + Libaio跳过文件系统直接操作裸设备，那么便使用不了PageCache，为了提升读的性能，需要自行管理Cache。BlueStore主要涉及元数据、数据的Cache，同时也实现了LRU、2Q两种Cache算法，默认使用2Q算法。目录 数据结构 初始化 元数据 数据 Trim数据结构// a cache (shard) of onodes and buffersstruct Cache { // 统计缓存命中率等 PerfCounters *...…
-
浅谈分布式存储之sync详解
前言由于内存比磁盘读写速度快了好几个数量级，为了弥补磁盘IO性能低，Linux内核引入了页面高速缓存(PageCache)。我们通过Linux系统调用(open—>write)写文件时，内核会先将数据从用户态缓冲区拷贝到PageCache便直接返回成功，然后由内核按照一定的策略把脏页Flush到磁盘上，我们称之为write back。write写入的数据是在内存的PageCache中的，一旦内核发生Crash或者机器Down掉，就会发生数据丢失，对于分布式存储来说，数据的可靠性是至关...…
-
BlueStore源码分析之Stupid分配器
前言前面介绍了BlueStore的BitMap分配器，我们知道新版本的Bitmap分配器的优势在于使用连续的内存空间从而尽可能更多的命中CPU Cache以提高分配器性能。在这里我们了解一下基于区间树的Stupid分配器（类似于Linux Buddy内存管理算法），并对比分析一下其优劣。目录 伙伴算法 数据结构 初始化 插入删除 空间分配 空间回收 优劣分析伙伴算法Linux内存管理算法为了能够快速响应请求，尽可能的提高内存利用率同时减少外部内存碎片，引入了伙伴系统算法Bud...…
-
浅谈分布式存储之数据冗余
前言为了保证分布式存储系统的高可靠和高可用，数据在存储系统中一般会冗余存储。当某个冗余数据所在的节点出现故障时(磁盘坏掉、静默错误、进程挂掉、机器宕机等)，分布式存储系统能够返回其他冗余数据，从而实现自动容错。分布式存储系统的数据冗余一般有两种方式：副本冗余和纠删冗余，其中副本冗余是最常用的冗余方式，通常为3副本；纠删冗余是为了节省副本冗余的成本，多用于冷数据的存储。目录 副本冗余 纠删冗余 总结副本冗余副本冗余是指同一份数据在存储系统中拥有相同的多个副本，一般为三副本。其中一个副本...…
-
浅谈分布式存储之数据分布
前言分布式系统区别于单机系统是在于能够将数据分布到多个节点，并且在多个节点之间实现负载均衡。所以分布式系统面临两个问题：一是如何将海量数据分散到多个节点；二是多个节点之间如何实现负载均衡。无论是KV存储、对象存储、块存储、文件存储还是数据库，所有的分布式存储在数据分布方面都面临相同的问题，本文将试着分析数据分布以及负载均衡可选的方案并权衡其利弊。目录 衡量指标 分布算法 Hash分布 Range分布衡量指标我们假设数据分布的目标数据是以key标识的value即k-v数据，数据分布算...…
-
BlueStore源码分析之FreelistManager
前言BlueStore直接管理裸设备，需要自行管理空间的分配和释放。Stupid和Bitmap分配器的结果是保存在内存中的，分配结果的持久化是通过FreelistManager来做的。一个block的状态可以为占用和空闲两种状态，持久化时只需要记录一种状态即可，便可以推导出另一种状态，BlueStore记录的是空闲block。主要有两个原因：一是回收空间的时候，方便空闲空间的合并；二是已分配的空间在Object中已有记录。FreelistManager最开始有extent和bitmap两种...…
-
BlueStore源码分析之架构设计
前言Ceph早期的单机对象存储引擎是FileStore，为了维护数据的一致性，写入之前数据会先写Journal，然后再写到文件系统，会有一倍的写放大，而同时现在的文件系统一般都是日志型文件系统(ext系列、xfs)，文件系统本身为了数据的一致性，也会写Journal，此时便相当于维护了两份Journal；另外FileStore是针对HDD的，并没有对SSD作优化，随着SSD的普及，针对SSD优化的单机对象存储也被提上了日程，BlueStore便由此应运而出。BlueStore最早在Jewe...…
-
BlueStore源码分析之BlockDevice
前言Ceph新的存储引擎BlueStore已成为默认的存储引擎，抛弃了对传统文件系统的依赖，直接管理裸设备，通过Libaio的方式进行读写。抽象出了BlockDevice基类，提供统一的操作接口，后端对应不同的设备类型的实现(Kernel、NVME、NVRAM)等。除此之外，还引入了支持NVME的spdk，完全通过用户态操作NVME磁盘，提升IOPS缩短延迟。目前Ceph进一步的工作计划是基于SeaStore(基于seastar的框架)来重构OSD，相信性能会有质的飞跃。目录 数据结构 ...…
-
BlueStore源码分析之BitMap分配器
前言块是磁盘进行数据操作的最小单位。任意时刻磁盘中的每个块只能是占用或空闲两种状态之一，如果将磁盘空间按照块进行切分、编号，然后每个块使用唯一的一个Bit表示其状态，那么所有的Bit最终会形成一个有序的Bit流，通过这个Bit流我们可以索引磁盘中任意空间的状态，这种磁盘空间管理方式我们称为位图。BlueStore直接管理裸设备，那么必然面临着如何高效分配磁盘中的块。BlueStore支持基于Extent和基于BitMap的两种磁盘分配策略，刚开始使用的是BitMap分配器，由于性能问题又切...…
-
BadgerDB源码分析之vlog优化
前言回顾一下VLog的格式，这种由一个个record(即BadgerDB的entry)组成的WAL称为recordio，可以有效的防止磁盘静默错误。但是recordio也有一些缺点，比如要读取部分数据开销太大等。同时VLog只有一个可写的vlog文件，对于HDD尚还可以，毕竟HDD的并发度基本为0，但是对于SSD来说，由于只有一个goroutine在append写入，并没有充分利用SSD的并行性，而且写WAL通常使用Libaio更高效。所以VLog中value的写入可以使用Libaio直接...…
-
BadgerDB源码分析之VLog详解
前言VLog里面记录了key-value的完整数据，发生故障时可以通过读取VLog里面的数据来恢复，此时便不需要LSM-Tree里面的WAL了，也就减少了一次写放大。目录 目录结构 IO模式 Entry格式 Reply日志 GC机制目录结构BadgerDB可以为LSM-Tree以及VLog配置不同的目录，而LSM-Tree的数据量相比VLog要小很多，如果有SSD磁盘，那么便可以把LSM-Tree的目录配置在SSD上，VLog配置在HDD上，加快读取LSM-Tree的速度。VLo...…
-
BadgerDB源码分析之架构设计
前言学习一个开源项目应该先从其架构设计入手，尤其是存储类的开源项目，在了解其整体设计之后，应该沿着IO路径去阅读代码，再由表及里去分析每个模块的具体功能。目录 架构设计 功能特性 写流程 读流程 VLog Manifest架构设计BadgerDB是基于Wisckey论文实现的，而Wisckey论文新颖的地方便在于把LevelDB和RocksDB做key-value分离，所以大体架构遵循LevelDB，区别就在于去掉了LSM-Tree里面的WAL，用VLog代替。在实现上，去掉了...…
-
BadgerDB源码分析之Wisckey论文
前言LSM-Tree的优势在于将随机写转换为顺序写，将大块的内存连续的写入到磁盘，减少磁盘Seek(磁头移动)的时间，同时又是按照key有序组织的，查找起来也比较快，但同时也带来了写放大和读放大。这些优化很适用于HDD，但是对SSD是极其不友好的，所以Wisckey提出了一种面向SSD的，将key-value分离存储的方法。BadgerDB便是基于该论文实现的。目录 LSM读写放大 Wisckey设计目标 并行Range查询 Crash一致性 GC机制 改进点LSM读写放大LS...…
-
BadgerDB源码分析之kv杂谈
前言随着分布式关系型数据库TiDB和CockroachDB以及分布式图数据库Dgraph的流行，我们认识到传统单机数据库也可以基于分布式KVS来实现分布式存储，几乎任何的分布式存储都可以基于分布式KVS来做A KVS For Any Scale。而分布式KVS便是基于单机的KV引擎来实现的。众所周知，单机KV引擎里面应用的最广泛的莫过于LevelDB的变种RocksDB了，关于LevelDB以及RocksDB的源码分析文章网上已经很多了，在这里不在赘述。然而任何事物都有其两面性，已经很优秀...…
-
浅谈分布式存储之SSD基本原理
前言随着制造工艺的不断进步，SSD(Solid State Drive)性能和容量不断突破，价格不断降低，迎来了快速的发展，目前已经是商用服务器、高性能存储服务中非常流行的存储介质。作为开发人员，需要了解SSD的基本原理，以便开发时能更好地发挥其优势，规避其劣势。本文章基于末尾所列参考文献整理而来。目录 SSD简介 闪存基础 存储原理 读写流程 GC机制 Trim机制 Bit-Error Read-Disturb Program-Disturb Wear-Levelin...…
