0x00 Everyday English preferable 更可取的 consequently 因此 inevitably 必然的 conventional 常规的、传统的 exacerbates 加剧 deteriorates 恶化 deterministic 确定性 0x01 Intro 本文主要提出了Pink，基于LSM tree的KV-SSD，主要通过避免使用布隆过滤器，而是使用少量DRAM来进行优化 传统的KV-SSD主要通过在控制器的DRAM中维护一个hash table来寻址，受到DRAM的容量限制，超出容量的部分会暂时存放在闪存中，因此在寻址时带来了访问闪存的额外开销，同时当发生哈希碰撞时，可能会操作多个闪存，造成了大量不可预测的开销 单纯使用LSM做为替换的话，可以减少DRAM的存储，但是存在一些性能问题： 尾延迟：很多LSM-tree使用布隆过滤器来快速检索，可靠性差，存在尾延迟问题 写放大：由于LSM对KV索引的排序和合并操作，带来了很多对闪存额外的访问，还增大了FTL进行GC的负担 布隆过滤器的重建和KV排序：消耗了大量的CPU资源，带来I/O性能的大幅下降 本文提出了一种基于LSM-tree的KV存储引擎-PinK，解决了上述三个问题。PinK使用了四种技术。 PinK的核心是level pinning，将固定在LSM-tree最顶层的KV索引固定到DRAM中 由于部分level固定在DRAM中，因此可以直接进行compaction，无需占用闪存的I/O，被固定的索引通过电容进行保护，因此也不需要定期进行刷新，这里要注意作者使用DRAM容量很小，使用电容足以保证持久化 GC的主要I/O开销来自对LSM-tree索引的更新，Pink通过延迟LSM-tree中索引更新到compaction阶段来减少GC的I/O开销 在SSD控制器和NAND芯片之间添加比较器，PinK在读取KV对象时执行KV排序，完全消除了compaction的CPU成本 0x02 Bg 了解一些有关NAND闪存SSD、KV-SSD、Hash-based KV-SSD、LSM-Tree-based KV-SSD的现状，并对Hash和LSM-tree进行比较 作者对LSM-tree的设计，L0位于DRAM中，并作为write buffer，其余各层存储在闪存中 0x03 Design Pink有四个主要的数据结构 位于DRAM中的level lists和Skiplist 位于闪存中的meta segments和data segments 在LSM-tree KV 文件系统方面，作者主要参考了WiscKey FAST'16，取代FTL进行GC、索引和磨损均衡 Skiplist Skiplist作为LSM-tree中的L0，起到类似write buffer的作用，暂时保存KV对象，Skiplist中的对象为：<key size, key, value size, value> 当Skiplist满时，会将缓存的对象以meta segment和data segment的形式刷新到L1中，在L1和更低的level中，Key和Value将被分离存储到meta/data segment中，data segment中存储value、key和key size用于GC Level list 用于跟踪闪存中每个level的meta segment

0x00 Everyday English LOC == line of code Guest OS == VM intricacies 错综复杂 drop-in replacement 通常表示直接替换，并且替换后不会产生影响，甚至会有一些新的功能 leverage 对…产生影响；一般也可以理解为 充分利用，比utilize语气强一些 0x01 Intro FEMU是用于软硬件全栈的SSD研究模拟平台，基于QEMU开发，相比于OpenChannel SSD实现了较高的准确率 此前的SSD研究模拟工具大多不开源，可扩展性差，研究成本高，并且已经过时。 FEMU首先开源免费，并且有较高的准确度，同时可伸缩性强，最大支持32 I/O 线程并模拟32个并行的SSD channels/chips，可扩展性高，得益于基于QEMU的优点，FEMU可以支持针对于SSD的研究，针对os 内核的研究，或者基于os内核和SSD的研究。 FEMU GitHub 仓库地址： https://github.com/vtess/FEMU 0x02 FEMU FEMU本身仅有3929行代码，基于QEMU v2.9，FEMU近些年的更新也主要为修复一些bug、合并QEMU的版本，将传统的App+宿主机+SSD的研究架构转变为了App+虚拟机+FEMU。 FEMU中的FTL模块、GC、I/O调度主要基于VSSIMVSSIM: Virtual machine based SSD simulator | IEEE Conference Publication | IEEE Xplore 可伸缩性 对于当前的高并行化的SSD，可伸缩性对模拟闪存至关重要。通过virtio和dataplane接口进行模拟，不能达到足够的可伸缩性，同时存在较高的延迟。 在QEMU中存在的两个主要问题是 QEMU使用传统的trap-and-emulate方法进行I/O模拟，虚拟机的NVMe驱动通过doorbell寄存器告知QEMU模拟的I/O设备。该doorbell将引起开销较大的VM-exit，同时在I/O完成阶段，也会产生该调用。 QEMU使用异步I/O来实现read/write，AIO的执行需要避免QEMU的I/O被阻塞，当在存储后端是基于RAM的镜像时，AIO产生的负载尤为明显 解决方案为： 使用基于轮询的方案，并且禁用了虚拟机的doorbell写操作，通过一个线程来轮询存储设备队列的状态，避免了VM-exit 不使用虚拟的镜像文件，使用自定义的以RAM为后端的存储模拟，定义在QEMU的堆空间中，将QEMU中DMA修改为从QEMU heap中读写数据，这个改变对VM来说是透明的 准确度 延迟模拟 当I/O请求到达后，FEMU发起DMA R/W，并用模拟的完成时间$(T_{endio})$对I/O请求进行标记，添加到endio queue中，队列按照I/O的完成时间进行排序。一旦I/O请求的预估完成时间大于当前时间，会由专门的end I/O 处理线程负责将其通过中断发送给虚拟机。 FEMU对每个I/O请求都设置了+50us的延迟。 延迟模型 对于$T_{endio}$的计算：

大四老狗为什么还写新生赛游记呢，怎么回事呢，怎么回事呢 Day 0 体测日，大三一年基本上是没怎么练跑步的，去年在女朋友监督下练了好久1000米摸到了及格线4'19，今年跑了5'00，还算能接受吧，以为能将将凑够50分毕业吧，结果50米垃了，9.7，明天早上再去润个50米，不然真毕不了业了。 Day 1 比赛日，早上七点半爬起来去体测，跑了个8.9，行了吧，也是可以及格了，遂赶紧带着装机u盘去了机房配环境。 不得不说，WHUT计算机学院的机房是一言难尽的，大二那年在管院办校赛，机器配置极其豪华，配环境的话可以直接分发系统，线路比较新分发也很快，计算机学院的机房如果搞分发估计要大半夜，而且主要是管实验室的老师不同意，只能拿着批处理一台一台的配。 配环境的中途发现很多机器突然开不起来了，预估坏了20台，抢救也没抢救过来，虽然机器也够用，但是1001机房背后就是轰鸣的服务器，很容易影响选手的发挥。上午又得知因为余家头校区出了小阳人，三十多个选手无法到场，虽然缓解了机房的压力，但是造成了分开参赛的情况，余区选手通过PTA线上参赛和监考，南湖这边还是线下，赶紧发了通知允许选手自带键盘，尽量保证体验一致吧然而线上没有零食吃。 志愿者人手感觉明显不太够，搞了一上午感觉就累的不行，好歹是准备工作都弄好了，比赛开始之后OJ也没出锅，这一点已经让我很高兴了。下午突然想解决一下PTA这边榜单的问题，有个学弟搞了一下domjudge的滚榜，赛后可以查看封榜后的实时提交和排名变化，来点区预赛的那种氛围。所以就是想把PTA那边的提交整合过来。目测了一下感觉可写，赶紧抓个包瞅瞅，写了大概一个多小时，直接导出了PTA里所有的提交，全部写SQL INSERT到OJ里面，榜单整合就成功了。然而没注意PTA那边给的接口LIMIT做了限制，请求的时候写了LIMIT=600，实际上response里上限就是100条，结果最后只导入成功了100条，这时候已经比赛结束30分钟了。于是打算赶紧搞一个榜单出来直接发奖了。 整体上还是有挺多遗憾的，榜单合并没及时搞好，滚榜没及时搞好，感觉还是自己没注意做好测试工作，所以说一定要做好测试。晚上回去顺便带了点零食，然后有把榜单整合了一下，微调了一下基本没问题了，学弟把滚榜也搞好了。然而一切还是来的太突然了，突入其来的yq防控打乱了很多事，不过最后的结果还是很不错的，又一年新生赛圆满结束了。 从大一参加新生赛，大二给新生赛出题，大三拉到老东家夜莺的赞助举办了一次线下新生赛（极其豪华的线下赛），再到大四举办的最后一次新生赛，前前后后忙了不少工作，从台前到幕后，一次次活动中也学到了不少东西，认识了很多优秀的同学，最后感谢所有志愿者同志们的付出吧。 Return 0

Questions 核心思想部分需要再思考和梳理下， 为什么采用 KV SSD 替代传统 block SSD 能够解决上述问题？ 其中，利用了 KV SSD 的什么特性？ 对文件系统哪些地方做了什么以优化？ 论文试图解决的问题： 随着存储设备的不断发展，存储设备的性能越来越高，但当前操作系统内核的文件系统在一些操作上并不能够充分利用如今存储设备的性能。 文件系统在执行数据写入时，需要执行大量操作维护元数据、进行硬盘的空间管理、维护文件系统的一致性，工作量大。 核心思想： 使用Key-Value存储接口取代传统的快设备接口。 具体实现： 提出Kevin，分为Kevin=KevinFS + KevinSSD KevinFS 维护文件和目录到KV对象的映射关系 将POSIX系统调用转译成KV操作指令 保证KV-SSD的一致性 KevinSSD 在存储设备中索引KV对象 对多个KV对象提供事务操作 0x00 Intro Kevin避免了大量元数据的维护带来的I/O放大 不需要日志即可完成崩溃一致性的维护 可以抵御文件分段后造成的性能下降 存储的文件块通过LSM进行分部排序和索引 0x01 BG && Related Work 传统块设备 提供块粒度（512B or 4KB）的访问 HDD通过维护一个间接表来处理坏块 基于闪存的SSD通过FTL来维护逻辑块到物理地址的映射索引表，以便在异地更新的NAND上模拟可重写介质并且排除坏块。 现有研究缓解了I/O调度、文件碎片化、日志相关问题，没能消除元数据的修改带来的I/O流量 DevFS实现了在存储设备内部的文件系统，直接将接口暴露给应用，调用时不用发生Trap，对于元数据的维护都在存储设备端执行，移除了I/O 栈减少了通信接口的开销。缺点是需要大量的DRAM和多核心的CPU、能提供的功能有限，还限制了快照、重复数据删除等文件系统高级功能的实现。 KV存储可以高效处理元数据和小文件的写入 LSM-Tree LSM Tree有多级，包括$L_1,L_2,…,L_{h-1},L_{h}$，h是树的高度，对于各级的大小有如下关系，$Size(L_{i+1})>=T*Size(L_i)$ 每层都有按Key排序的唯一KV对象。各层之间的Key范围可能会出现重叠。 KV对象首先写入DRAM中的Memtable，当Memtable不为空时，缓存的KV对象将刷新到L1中进行持久化，当L1不为空时，KV对象刷新到L2中，依此类推。在刷新过程中会执行压缩操作来对两层之间的KV对象进行合并和排序，在排序后写回磁盘中。 为了改善压缩操作的I/O开销，可以将所有的value存储在value log中，在LSM tree中只保存value指针，存储<key, value pointer>形式。对于失效的value要考虑垃圾回收问题。 在对KV对象进行检索时，可能需要在多级进行查找，当在Li不匹配时，查找Li+1。为了减少多级查找的读取，可以使用布隆过滤器进行优化，当检索到目标KV对象时，LSM tree将会返回相应的value，KV分离存储的情况下，将会额外去读一次value log。 0x02 Architecture KEVIN分为两个部分 KEVINFS：维护文件、目录到KV对象映射的文件系统 KEVINSSD：索引KV对象到闪存的LSM-tree KV Command 支持多种KV指令，同时支持事务

0x00 基本概念 文件的基本概念， 包含信息的比特流/块，计算机往往需要处理远高于主存容量的数据，需要使用文件来保存；文件的生命周期更长，不能存储在堆栈中；对文件的数据/信息对外进行分享的媒介。可以用于进程间的信息共享，自由性和容量上都优于共享内存的方式。 文件系统的功能 Namespace 命名空间 文件目录的建立、维护和检索（目录树） 存储管理 空间管理：存储空间的分配和管理（管理空闲的块） 文件块管理：逻辑地址与存储物理地址的映射（logical offset—Physical Block number） 数据保护 文件出现坏块 灾备 可靠性/一致性 0x01 用户视角 文件目录操作 文件操作： Create/Delete Open/Close 返回File Handle Read/Write Append 追加写入 Seek 移动文件指针 offset Getattr/Setattr 读取/修改inode中保存的文件信息 Rename 目录操作： Createdir/rmdir Link 软链接、硬链接 讲目录项目指向文件的inode Unlink Readdir 读取子目录以及目录项 Rename 文件目录的构成 文件的组成： 文件内容，字节序列 文件的元数据metadata，文件控制块，Unix系统中称为inode(index node) 目录的组成： 本质是一种特殊的文件，内容是子目录、文件等目录项目 目录也有inode File Handle 创建原文件的一个实例对象，对其进行读写，Offset可以共享给两个File Handle，也可以每个File Handle独有各自的Offset。 Linux VFS中为文件描述符fd，对应一个File Object，包含文件的信息，文件系统管理dentry、inode的缓存，用于查找文件在磁盘上的位置。关于Linux VFS的内容，计划再单独开个博客记录一下。 File Control Block (Inode) 每个文件唯一的id，包含以下结构 Block的信息，文件在磁盘上的位置 数据大小 Ctime创建时间，utime更新时间，access time最后一次访问时间 所有者信息，ACL(access control lists)访问控制 链接情况统计 Dirent - Directory Entry 目录项纪录子文件和子目录的名称

本文将从操作系统内核层面去介绍Linux I/O 栈 ==涉及Linux内核的部分主要为Linux 2.6== Linux I/O 栈概述 Linux I/O 栈的简图如下 下面分别简述各个层次的功能 应用程序层 应用程序层通过系统调用向VFS发起I/O请求 VFS层 VFS主要向用户空间提供文件系统层面的接口，同时向不同的文件系统实现提供抽象，使他们可以共存。VFS将文件系统在用户层面进行抽象，便于用户对文件进行操作。 来自应用程序的请求到达VFS后，VFS会创建包含I/O请求信息的结构体提交给块I/O层。 Linux在文件系统层提供三种IO访问的形式：Buffered IO、MMap 、Direct I/O。 Buffered I/O：这种访问情况下文件数据需要经过设备、Page Cache、用户态缓存，需要进行两次的拷贝动作。 MMap：内存映射技术，将内存中的一部分空间与设备进行映射，使得应用程序能够向访问普通内存一样对文件进行访问。使文件数据仅经过设备、Page Cache即可直接传递到应用程序。 Direct I/O：采用Direct IO的方式可以让用户态直接与块设备进行对接，跳过了Page Cache，从硬盘和用户态中拷贝数据，提高文件第一次读写的效率，若之后需要重复访问同一数据，需要消耗比利用Page Cache更多的时间，一般用于数据库系统。 块I/O层 系统能够随机访问固定大小的数据片的设备被称为块设备，最常见的块设备为硬盘（机械硬盘，固态盘），对块设备的访问通常是在其内部安装文件系统。操作系统为了对其访问和保证性能，需要一个子系统来对块设备和对块设备的请求进行管理。 SCSI底层 && 设备驱动层 块I/O层将请求发往SCSI层，SCSI就开始真实处理这些IO请求，但是SCSI层又对其内部按照功能划分了不同层次： SCSI高层：高层驱动负责管理disk，接收块I/O层发出的IO请求，打包成SCSI层可识别的命令格式，继续往下发 SCSI中层：中层负责通用功能，如错误处理，超时重试等 SCSI低层：底层负责识别物理设备，将其抽象提供给高层，同时接收高层派发的SCSI命令，交给物理设备处理 更正：对于传统的块设备而言，服务器通过SCSI协议、SAS接口连接，个人电脑通过AHCI协议/SATA接口连接，目前主流的发展方向为NVMe协议/M.2接口。 物理外设层 在I/O中一般为磁盘、固态硬盘等存储设备 VFS简介 Intro VFS主要向用户空间提供文件系统层面的接口，同时向不同的文件系统实现提供抽象，使他们可以共存。 VFS将文件系统在用户层面进行抽象，便于用户对文件进行操作。 VFS中有四个最重要的数据结构，分别是dentry、file、inode、superblock，下文对他们分别进行介绍。 Directory Entry Cache (dcache) VFS提供了open，stat，chmod等系统调用，需要向他们提供文件的路径名，VFS会在dcache中去查询。 dcache提供了非常快的查找机制将路径名转换到一个具体的dentry目录项，缓存的目录项存储在RAM中并且不会持久化到硬盘。 在没有命中缓存时，VFS会通过查找和加载inode来创建dentry缓存，最终实现可以通过path name查找到对应的dentry目录项。 The Inode Object 每个独立的dentry都有一个指向一个inode的指针，inode一般保存在disc（块设备文件系统）中或者内存中（虚拟文件系统）。disc中的inode在被请求或修改时会复制到内存中，并在修改后回写到disc。多个dentry可以指向同一个inode（硬链接） 对于查找inode的请求，VFS在父目录的inode调用lookup函数。 The File Object 在打开一个文件时，需要分配一个文件结构体（内核层面对file descriptor的实现），结构体内容的创建通过dentry指针来获取，文件结构体存储在进程的文件描述符表中。 对文件的读写、关闭通过用户空间的fd来操作正确的文件结构。 只要文件打开，它就会保持对dentry的使用状态，这同时意味着inode仍在使用。 The Dentry Object 目录项纪录子文件和子目录的名称