UStore：面向新型硬件的统一存储系统

屠要峰 韩银俊 金 浩 陈正华 陈 兵

1（南京航空航天大学计算机科学与技术学院 南京 211106）2（中兴通讯股份有限公司 南京 210012）

近年来，随着云计算、移动互联和物联网技术的快速发展，数据规模呈爆发式增长，传统的存储系统已经无法满足不断增长的海量数据存储需要，大容量高性能分布式存储已经成为数据中心的必备.长期以来，大多数分布式存储直接使用本地文件系统如XFS（extents file system），EXT4（fourth extended file system）等访问本地存储资源.比如GlusterFS，HDFS直接使用本地文件系统作为其后端存储，早期分布式文件系统Ceph 的FileStore 也是基于本地文件系统XFS 进行本地存储的访问.本地文件系统成熟稳定，充分利用了文件和对象天然的映射关系，利用操作系统页缓存机制缓存数据，利用inode 节点缓存机制缓存元数据，同时从操作系统层面保证了磁盘的隔离性.但这种架构也有明显的局限性[1]，主要是事务一致性难以保证，元数据管理低效，以及缺乏对新型硬件的支持.由于这些弊端，Ceph 在Jewel 版本引入了BlueStore 作为后端存储.BlueStore 将对象数据的存放方式改为直接对裸设备进行指定地址和长度的读写操作，不再依赖本地文件系统提供的POSIX接口.同时，BlueStore 引入了RocksDB 数据库保存元数据和属性信息，包括对象的集合、对象、存储池的omap 信息和磁盘空间分配记录等.BlueStore 有效避免了数据和日志的双写，提升了元数据的操作效率，使得本地I/O 性能得到了较大的提升.但BlueStore 在小I/O 的处理上依然需要写日志到RocksDB 中，同时RocksDB 的使用引入了序列化和反序列化以及compaction 带来的开销.

持久内存（persistent memory，PMEM）、硬件加速的KVS（key-value store）等新型存储形态的出现为本地存储带来了新的机遇.PMEM 具有低时延、非易失、字节寻址等特性，但是目前商用的PMEM 也存在着读写不对称等不足，PMEM 比固态硬盘（solid state drive，SSD）容量小且单位存储成本更高，在大容量高性能存储场景下，存储的数据规模和扩展性受限，因此PMEM 适合用来存储元数据和小数据.KVS 规范为存储设备定义了标准APIs，基于FPGA 硬件的KVS 在实现CPU-offload 的同时，利用超级电容保证崩溃一致性，可以有效减少类似RocksDB 在处理事务过程中带来的写放大和compaction 的开销，具有较好的性能表现，同样适合于元数据的存储.基于Flash 的SSD由于存在着磨损不均衡、垃圾回收（garbage collection，GC）开销及长尾延时等问题，不适合海量小文件频繁读写的元数据管理，而更适合存储大块的数据对象.研究者针对新型硬件的存储系统做了大量的研究和优化.然而，现有基于新型硬件的存储系统大多是对某种硬件单一场景的优化，其优化机制和应用场景存在较大差异，普遍存在兼容性和扩展性差的问题，无法灵活适配多种硬件配置的不同组合，例如基于SSD 优化的存储系统无法很好地适配PMEM 的读写特性.

针对上述问题，本文提出并实现了一种适配多种新型硬件的统一存储UStore，通过不同存储介质特性的组合优化设计，灵活构建性价比更优的本地存储系统.本文的主要贡献有3 个方面：

1）实现了一个兼容PMEM、KVS 加速卡、NVMe SSD 等多种存储介质的统一存储系统UStore，并可根据业务场景灵活选择存储介质；针对PMEM+NVMeSSD，KVS+NVMeSSD，NVMe SSD 这3 种常用场景，结合PMEM 和NVMe SSD 硬件特性进行组合设计优化，满足多层次的业务需求.

2）提出一种高效的数据布局和管理方法，利用易失的空闲空间管理和写时重定向（redirect on write，ROW）技术，实现了无日志的数据更新方法，减少写放大和管理开销，提升了数据的访问性能.

3）提出一种与物理存储介质形态解耦的元数据管理机制，能够高效地适配不同存储硬件介质和接口；设计了一种面向数据原子写优化的元数据结构，利用PMEM，NVMe SSD 等新型硬件的写入原子性实现高效的元数据原子更新.

1 相关工作

现有研究在本地存储优化设计、基于PMEM 的存储优化、基于SSD 的存储优化等方面做了很多有益尝试，以充分发挥新型存储器件的特性和性能优势，提升存储系统性能.

1）基于PMEM 的存储优化.传统的存储栈冗长的I/O 路径和诸如页缓存等机制严重影响PMEM 的特性和性能.PMFS[2]是英特尔公司提出的持久内存文件系统，采用8B 原地更新和细粒度日志机制保证元数据更新的原子性，采用undo 日志和写时复制混合的方式保证数据的一致性.NOVA[3]是一个基于混合易失/非易失主内存的日志结构文件系统，充分利用PMEM 的优势提供更强的一致性和原子性保证，支持元数据、数据和mmap 三种操作的原子性保证.NOVA 保存日志和文件数据到PMEM 中，并且通过在DRAM 中构建radix 树保存索引以便加速查找操作.NoveLSM[4]是基于PMEM 的LSM-Tree（log-structure merge tree）的键值存储系统，旨在利用PMEM，为应用提供低延迟和高吞吐键值存储，但是没有引入SSD进行组合优化.KucoFS[5]重新审视了基于非易失性存储器的文件系统体系结构，提出一个内核和用户级协作文件系统，它充分利用了用户级直接访问和内核空间数据保护各自的优点.KucoFS 将文件系统解耦为内核线程（称为master）和用户空间库（称为Ulib），客户端能够通过Ulib 直接在用户级别读取/写入文件数据，而master 专用于更新元数据并保证文件数据的完整性，通过以只读模式将PMEM 空间导出到用户级别来防止错误的程序破坏文件系统.KucoFS通过索引卸载技术重新平衡内核和用户空间之间的路径名解析开销，通过协调内核和用户空间之间的数据分配，并使用范围锁定写入和无锁定读取来支持高并发，提升了数据访问效率和多核扩展性.

2）基于SSD 的存储优化.业界主要研究和解决基于Flash 的SSD 所存在的GC 长尾延时、垃圾回收开销、容量利用率低以及主机软件复杂等问题.Stream SSD[6]通过SSD 主控来对写入的请求进行标记，请求进入到流式SSD 内部的时候根据预定义好的流式SSD 标记来将带有不同标记的输入命令分配存储到不同的擦除块之内，可以减少因为内存转换层（flash translation layer，FTL）调度GC 导致的性能和SSD 寿命的损失.但是流式SSD 对主控要求比较高，需要消耗更多的内存（保存未区分的状态）以及性能更好的主控芯片.Open-channel SSD[7]允许SSD 主机和SSD 共同管理一个连续的LBA（logical block address）块集合，并且对外暴露的操作指令是擦除块对齐的.这种按照擦除块对齐的访问模型能够消除 SSD 内部GC 的代价，并且降低对OP（over provisioning）空间的消耗.但是，Open-channel SSD 需要主机软件来做LBA管理、擦除块的回收以及坏块的管理，还需要兼容不同的SSD 内部实现机制，开发维护成本过于高昂.NVMe 分区命名空间命令集规范（zoned namespaces command set specification，ZNS）代表主机软件和基于闪存的SSD 之间的新功能划分，它有望成为解决SSD 现有问题的主流方案.文献[8]采用ZNS 接口，通过将管理擦除块内数据组织的功能从FTL 层转移到主机软件，消除了设备内LBA 到页的映射、GC 和OP 空间.ZNS 使得基于闪存的SSD 具有更高的性能和更低的每字节成本.ZNS 的架构契合LSM-Tree 的追加顺序写特性，SSD 的GC 过程也能和LSM-Tree的compaction 操作相结合，因此软件层面上的需求和发展趋势也促进了ZNS SSD 的发展.

在软件层面上，LSM-Tree 把离散的随机I/O 通过compaction 操作转变成连续的顺序I/O，相对于传统的B+树，对于机械硬盘（hard disk drive，HDD）的写入性能有很好的优化，对于SSD 则能够减少GC.WiscKey[9]提出一种基于SSD 优化的键值存储，核心思想是把键Key和值Value分离，只有Key被保存在LSM-Tree中，而Value单独存储在日志中.这样就显著减小了LSM-Tree 的大小，使得查找期间数据读取量变少，并减轻了由于索引树合并时不必要的数据移动而引起的写放大.WiscKey 保留了LSM-Tree 的优势，减少了写放大，但数据访问时需要进行多次MAP 映射，且依然存在LSM-Tree 固有的compaction 过程.KVell[10]是基于NVMe SSD 设计的高效键值存储，核心设计思想是简化CPU 的使用，数据在SSD 上不排序，每个分区的索引在内存中是有序的.这种设计在每次启动时需要进行索引的重构，无法满足快速重启动的需求.KVell 使用页缓存和最近最少使用（least recently used，LRU）算法负责磁盘上的空闲空间申请和释放，省去了磁盘上空闲空间回收和整理的过程.但是当磁盘容量快被用完时，大概率触发SSD 的擦除→拷贝→修改→写入过程，实际I/O 性能会大幅下降.

3）基于PMEM/SSD 混合存储的优化.Strata[11]是针对持久性内存、SSD 和HDD 设计的混合存储系统.Strata 将PMEM 空间划分为日志区和共享数据区2个部分，日志区对每个进程是私有的，共享数据区对所有进程可见，SSD 和HDD 均为共享数据区.在进行文件系统更新操作时，将更新在用户态直接以日志的形式写入到PMEM 的私有日志区，以绕过内核中的页缓存.后台线程异步地将私有日志区中的数据写入到共享数据区中，即digest 操作，过程中先对日志进行合并后再写入，从而减少写入量.在DRAM中维护LRU 列表，供内核进行数据迁移，将最近访问的数据保存在快速设备中，迁移的粒度分别使用SSD 擦除块的大小或者HDD 写入块大小，优化SSD和HDD 的写入.SLM-DB[12]基 于PMEM 和SSD 对LSM-Tree 进行改进，通过把多层SSTable 结构减少为一层，避免了多层SSTable 带来的写放大问题，同时在PMEM 上用B+树给所有的SSTable 建立了全局索引，加速对磁盘数据的访问，具有低写入放大和近乎最优的读取放大特性.但是，当数据量变多时维护PMEM 上B+树的代价会很大.

Table 1 Experimental Environment Configuration表1 实验环境配置

肖仁智等人[13]从持久索引、文件系统和持久性事务等方面对基于PMEM 的相关工作进行了综述和总结，并指出在开发新的一致性持久内存索引方面，未来更多的工作将集中在LSM-Tree[14]和SkipList[15]上.在基于异构硬件加速的优化方面，PolarDB 的后端存储引擎X-Engine[16]基于LSM-Tree 改进，将写操作实现为多核并行流水化模式，使用FPGA 加速compaction 过程，将L0 层文件保存到PMEM 介质，一定程度上避免抖动.PolarDB 所做的优化对电商业务场景的数据访问有显著改进，对普通的存储场景的数据读写效果未知.

上述3 种改进和优化[11-13]，都是针对SSD 或者PMEM 的硬件特性在软件层面进行优化，以提升系统性能和器件寿命.各种优化方案相互差异大，存在彼此不兼容、扩展性差、缺乏对硬件环境的灵活适应等问题，未见从兼容性和扩展性角度出发，构建PMEM+SSD 混合存储系统，灵活适配多种硬件配置的工作和研究.本文提出并实现了一种适配多种新型硬件的统一存储UStore，通过不同存储介质特性的组合优化设计，灵活构建性价比更优的本地存储系统.

2 UStore 架构设计

传统的存储系统通常是面向内存+外存2 层存储架构设计.内存是高性能、易失的，容量较小；外存（例如HDD，SSD）则是低速、非易失的，容量较大.新型存储硬件的出现打破了内存、外存之间的界限，对上层软件系统的设计产生重大影响.针对高性能的NVMe SSD，PMEM，KVS 存储等硬件，虽然都是非易失存储器，但相互之间在容量、成本、性能以及硬件特性方面差异较大.为了充分利用不同存储设备各自的性能、容量和成本优势，有必要将性能、容量、易失性作为独立的维度进行考虑，设计全新的系统架构，灵活适配多种硬件特性和业务场景.

原子写是存储系统需要解决的关键问题之一.原子写是指写入的数据是原子的，要不全部写入成功，要不写入失败，保留原先数据，而不能是一个中间的不确定状态.XFS 等文件系统通过日志机制保证了自身元数据的崩溃一致性，但不提供针对文件内容的原子写保证.NVMe 规范定义了原子写相关特性AWUN（atomic write unit normal）和AWUPF（atomic write unit power fail），但当前主流的NVMe SSD 仅实现了4KB 数据的写入原子性，如果要更新4KB 以上的数据则仍然需要在软件层面通过额外的手段进行保证.比如MySQL 通过DWB（double write buffer）机制保证数据库8KB 页面的原子写入，PostgreSQL 通过FPW（full page writes）机制保证了16KB 数据页面的原子写入，RocksDB[17]通过预写式日志（write ahead log，WAL）机制确保了数据写入的原子性.这些系统有一个共性，就是通过重复的数据写入机制来实现原子更新，但是数据的多次写入带来了额外的系统开销，对SSD 来说同时也增加了闪存介质的磨损，减少了硬件寿命.

UStore 将介质的容量、性能、易失性分开考虑，从系统架构层面进行重新组合，通过数据和元数据分离、元数据设计和存储介质解耦，实现了性能与容量的平衡，数据和元数据的存储可以分别使用特定硬件或硬件组合完成，充分发挥各自的优势，具有很好的通用性.同时，利用硬件的写入原子性实现元数据的原子更新，并进一步结合ROW 机制完成数据的原子更新，使得上层软件不再需要关注该问题.

UStore 的系统架构如图1 所示.UStore 对上层提供块接口，内部则主要包括元数据管理、数据管理和空闲空间管理3 个模块，其中元数据管理模块负责管理系统的元数据，数据管理模块负责SSD 盘的管理和数据的读写，空闲空间管理模块则记录了数据存储空间的空闲情况，用于空间的分配和回收.

Fig.1 UStore system architecture图1 UStore 系统架构

数据管理模块提供可变容量存储空间分区（Blob）的抽象.Blob 与传统的LVM（logical volume manager）逻辑卷类似，提供一段连续的逻辑存储空间，并支持动态扩容.Blob 分区可用于支持数据和性能的隔离，有利于实现更高效、更稳定的数据访问.用户数据被切分为较小粒度的数据块（Chunk）进行管理和存储，用户的块接口读写请求被转换为基于ChunkID 的Chunk 内数据读写.数据管理模块中的数据是非易失的，且提供特定粒度数据的原子更新特性，以帮助UStore 对外提供任意粒度的原子写接口.数据管理模块底层可以选用NVMe SSD，ZNS SSD 等大容量设备作为其物理存储设备.

空闲空间管理模块负责空闲空间管理.一段存储空间在任意时刻只可能是“空闲”或“占用”2 种状态之一，占用空间信息由元数据管理模块持久化，空闲空间信息则可不必持久化.因此，空闲空间管理被设计为易失性的，以避免持久化开销，同时降低数据更新的复杂度，提高空闲空间管理的性能.空闲空间被描述为若干个[offset，length]的结构并在内存中进行索引，在空间分配、回收或Blob 容量调整时更新.在系统启动阶段，通过加载和遍历元数据管理中的已占用空间信息，在内存中反向构建出每个Blob 的空闲空间信息.配合Blob 的动态调整，空闲空间管理模块的索引数据总量可以维持在较小的规模，可以全部驻留在内存中，并由此获得较高的性能.

元数据管理模块负责维护Chunk 和Blob 中数据的映射关系，即元数据，该信息描述为Chunk 在Blob内的偏移地址，以缩减元数据总量.该信息是非易失的，支持原子更新，并且需要提供高效读写能力.元数据管理模块设计了与物理存储介质形态解耦的元数据管理方案，可根据业务场景选择不同的存储介质保存元数据，满足同一存储系统灵活适配不同存储硬件形态的组合.对于容量和性能要求较高、存储成本不敏感的业务场景选择PMEM+NVMe SSD 方式，将元数据保存到性能较好的PMEM.对于需要控制成本、无法添加PMEM 等硬件的传统业务，则可以选择全NVMe SSD 方式构建存储系统，将数据、元数据都保存到NVMe SSD.对于CPU 资源敏感的场景选择硬件KVS+NVMe SSD 方式，可以将元数据读写卸载到硬件KVS 系统.

UStore 充分利用新型存储硬件的写入原子性，实现了Chunk 粒度的原子写，根据写操作是否超出了硬件提供的原子写能力，系统通过2 种不同的方式进行处理.当写操作满足硬件原子写对齐和粒度要求时，例如NVMe SSD 的4KB 更新，使用直接I/O的方式进行覆盖写，不需要对索引进行更新，硬件的原子写直接保证了数据的原子写.当写操作粒度超出硬件能力时，例如大于4KB 的数据写入，则通过ROW 方式写入，UStore 首先分配新的空闲空间进行数据的写入，在写入成功以后再更新元数据信息，此时原子写问题被转换为元数据的一致性问题.进一步地，UStore 通过优化的元数据设计将一致性问题简化为单次、小粒度的元数据更新问题，然后通过硬件原子写完成元数据更新.具体来说，空闲空间管理是易失性的，空闲空间的分配不涉及持久化操作；数据写入完成后，仅由元数据管理模块执行一次元数据原子更新，并在成功后进行旧数据所占用空间的回收过程；同样，空间回收过程不涉及持久化操作.由于元数据更新的原子性和空闲空间管理的易失性，此过程在任意阶段崩溃都不会造成用户数据的错误和Blob 空闲空间的泄漏.

此外，系统中的数据及其维护操作被按照Blob进行了水平分割，每个Blob 由特定的工作线程处理，这样可减少资源争用和锁冲突，使得数据隔离等特性容易实现，NUMA（non-uniform memory access）亲和性等技术也可以方便地应用到系统中，以便从多方面提升系统性能.

UStore 通过数据和元数据的分离、与存储硬件形态解耦的元数据管理、基于存储硬件特性的原子写等优化设计，充分利用不同存储器件的容量、成本、性能以及硬件特性优势，实现了针对多种存储硬件和场景优化的统一存储，在提升性能的同时，具有较好的通用性和灵活性.

3 关键技术

3.1 高效的数据管理机制

数据管理包括物理空间的分配与回收、数据的读写等功能.出于优化硬件兼容性和管理效率的考虑，空间分配和回收被划分为Blob 和Block 两个级别，Blob 的管理由数据管理模块负责，Block 的管理则由空闲空间管理模块负责，并借助元数据管理模块进行持久化.

3.1.1 高性能的空间分区

数据管理模块主要负责Blob 管理和读写，Blob空间随着用户数据的写入动态扩容.Block 是Blob 的基本读写单元，但不是空间分配单元，这样做的目的是减少地址转换条目的数量.

如图2（a）所示，为了实现动态扩容，Blob 实际由NVMe 盘上的多个物理区段组成，每个物理区段的容量是Block 的整数倍，并远大于Block 大小.数据管理模块仅需要维护极少量Blob 到物理区段的地址转换条目信息，对Blob 内特定偏移地址的访问可以很容易地通过计算转换为NVMe SSD 的物理地址.Blob的另一个作用是性能的聚合或隔离，例如，对于ZNS SSD，可以将Blob 映射到不同zone，以避免高负载用户挤占其他用户的资源，或者将Blob 交错排布到不同硬件上，以提供更高的读写性能.

Fig.2 Data management mechanism图2 数据管理机制

数据管理模块的设计要求Blob 边界满足硬件原子写的对齐要求，以便利用存储硬件的原子写特性实现高效的Chunk 粒度原子写接口.对于NVMe SSD，由于硬件支持Block 级别的原子写，Blob 划分总是满足对齐要求，无需额外的处理.当后续适配其他新型存储硬件时，可以根据新硬件的特性扩展Blob 的实现，并对UStore 的其他模块屏蔽这种变化.

实现Blob 的高性能读写，还需要降低或避免系统调用、内存拷贝等操作的开销.UStore 选择基于SPDK[18]库实现数据管理模块.SPDK 是Intel 提供的存储平面开发套件，其BlobStore 接口实现了UStore所需的Blob 语义，并能够支持NVMe，ZNS 等多种存储设备，SPDK 通过用户态NVMe 驱动访问NVMe SSD，以绕过操作系统内核，获得更高的I/O 性能.Blob 的创建、删除、扩容都是原子的，异常崩溃不会导致一致性问题.同时，SPDK 提供了直接内存访问（direct memory access，DMA）内存管理机制，UStore 利用这种机制管理Blob 读写时的内存申请和释放，以减少数据的来回拷贝.

3.1.2 轻量级空闲空间索引

数据空间分配、空闲空间回收的实现方式不仅关系到整个存储系统的性能，而且直接影响存储空间利用率.Blob 内的空间按Block 进行管理，对用户提供的块接口也是Block 对齐的，不会出现不规则的空间碎片，因此物理空间的分配回收算法能够做到简洁而高效.

如图2（b）所示，空闲空间管理模块使用链表和B+树来存储空闲块信息，空闲块[offset，length]信息保存在链表中，并按空闲块长度length升序排列，方便按长度查找空闲块.B+树的Key为空闲块的offset值，底层叶子节点则直接指向链表中的节点，用于实现相邻空闲块的归并.除此之外，为链表增加多个Pointer指针，分别指向不同长度的空闲空间的起始节点，以避免空间分配时遍历整个链表.同一个Blob 的I/O 请求由相同的工作线程处理，因此避免了多线程并发访问和更新上述结构时的锁开销.

空间分配操作从链表中找到符合要求的最小空闲块，首先将空闲块从链表、B+树中删除，从空闲块尾部分配指定大小空间，然后更新空闲块的length信息，最后将更新后的空闲块重新插入到B+树及链表，当空闲块剩余长度为0 时，则不需要重新插入.

空间释放操作根据待释放空间的offset在B+树查找插入位置，并尝试与相邻节点的空闲块合并.若与前驱节点合并成功，则更新前驱节点的length为二者之和；若与后继节点合并成功，则删除后继节点，并使用待释放空间的offset作为Key插入新节点，其length为二者之和；若与前、后节点都合并成功，则更新前驱节点length为三者之和，并删除后继节点；若无法合并，则直接插入新节点.

初始化时，空闲空间管理模块将整个Blob 初始化为一个连续的空闲块，然后通过遍历元数据找到所有已占用的空间信息，按照空间分配过程将所有已占用的空间从空闲空间管理中删除，最终恢复出Blob 的空闲空间信息，元数据管理的高性能使得这一过程能够很快地完成.

得益于Block 对齐和最佳匹配长度的数据分配策略，经过长时间频繁的空间分配和回收，系统空闲空间仍然比较规整，不会出现大量碎片空间，避免了传统空间管理中复杂的碎片整理流程，也使空闲空间管理的索引数据总量得到控制.相对于传统的空闲空间管理，UStore 空闲空间管理更简洁而高效.

3.2 与存储介质形态解耦的元数据管理

元数据管理模块负责维护元数据信息，元数据索引的本质是逻辑地址与数据存储位置的对应关系，读写操作根据逻辑地址查询索引，找到数据保存的Blob 及offset信息.UStore 设计了一种与物理存储介质形态解耦的元数据管理方案，能够适配不同存储硬件介质和接口，元数据采用2 级索引结构，第1 级索引是Chunk 索引，记录Chunk 的物理地址信息，第2 级索引是Chunk 内子数据块的地址信息，用于实现数据原子写能力.同时，2 级索引的引入使得多个子数据块可以并发写入，提高系统的并发更新能力.

当Chunk 首次写入数据时，按照Chunk 大小分配一段连续的初始空间，此时逻辑空间的Block 块与物理空间Block 块一一对应.如图3（a）所示，元数据中只需要保存逻辑ChunkID、物理空间偏移地址offset.

Fig.3 Metadata management图3 元数据管理

当使用ROW 模式完成数据更新时，需要将数据写入新分配的物理空间，因此每次写入超过Block 长度的数据会产生一段随机物理地址，如图3（b）所示，一个Chunk 的数据由一段初始空间和多段增量空间存储.为了管理这些不连续的物理空间，UStore 采用2 级索引记录子数据块逻辑地址与物理地址的映射关系.

索引条目采用键值接口的数据容器存储，Key为ChunkID，Value为索引条目.KV 数据容器的类型根据实际采用的存储介质不同而有所差异.一个Chunk索引条目具体包括ChunkID，offset，head，tail，以及用于保存二级索引的entry数组.其中ChunkID长度为8B，offset（长度为4B）为Blob 内地址偏移，tail（长度为2B）指向entry数组的下一个空闲位置，head（长度为2B）指向entry数组的最早写入位置，entry数组每个成员保存一段子数据块的索引信息，包括：数据在Chunk 内的偏移地址entry_off（长度为2B）、数据在Blob 中的偏移地址data_off（长度为4B）、以Block 为单位的数据长度len（长度为2B）.数组长度决定了单个Chunk 更新的最大并发度以及读操作时的最大读盘次数，为了适配不同业务场景需求，2 级索引条目数组长度支持灵活配置，可以根据实际情况指定.

经过测试验证，深度为16 的4KB 原子写能够接近主流NVMe SSD 的吞吐率上限，因此，UStore 设定默认值为16.此时，一个完整的Chunk 索引条目长度为8+4+2+2+（4+2+2）×16=144B.为了优化索引的读写性能，将head，tail都定义为2B，同时将索引结构声明为cacheline 对齐的.此时，单个entry也满足8B 对齐要求，硬件仅需提供8B 的原子写保证即可用于元数据的原子更新，而无需日志机制.

第2 级索引基于数组entry实现循环队列算法，head，tail分别指向循环队列的头位置和尾位置，队列采用尾部插入、头部删除的规则，插入时前移tail指针，删除前移head指针，指针到达边界后从0 重新开始.

基于这样的2 级索引，数据读取操作在查询到Chunk 索引条目后，需要遍历循环队列head和tail之间的所有条目，确定对应的数据块是否存在更新.如果不存在，则直接从1 级索引对应偏移位置读取；否则，根据实际情况不同，可能需要读取多个更新并进行合并，得到所需的用户数据.考虑到上层系统通常以相同的粒度更新和读取数据，涉及合并的情况并不会太多.

为了避免2 级索引耗尽导致写操作产生性能抖动，UStore 启动后台归并线程，在循环队列届满时进行子数据块的合并.归并线程首先将所有子数据块合并到原始Chunk 中，然后更新第2 级索引的head指针.子数据块迁移完成前，索引、子数据块都不变，因此不影响数据的读流程，迁移过程中系统崩溃也不会产生一致性问题.对于写操作，工作线程、归并线程分别更新第2 级索引的head，tail指针，可以并行执行，而无需使用锁或其他互斥机制.

综上，UStore 的元数据结构是面向数据原子写而优化的，任意情况下对索引条目的更新仅需8B 原子性保证，降低了对底层硬件的要求.对于元数据条目本身的创建和删除操作，其原子性则通过KV 容器来保证.当元数据存储到不同硬件时，可以灵活地根据其特性设计高性能的KV 容器方案，最大限度地保证2 级索引的访问性能.通过与物理存储介质形态解耦的元数据管理机制，UStore 实现了对多层次存储需求的兼容，可以根据业务场景灵活地选择存储介质的组合.

3.2.1 基于NVMe SSD 的索引

NVMe SSD 支持4KB 的Block 原子写能力，可以用于实现2 级索引的原子更新.当仅使用NVMe SSD存储元数据时，每次读写数据都需要至少2 次访问SSD盘，如果元数据访问涉及不止1 次I/O，则性能损耗更为明显.为了提高读写效率，使用DRAM 作为缓存，即组合使用DRAM+NVMe SSD 完成元数据存储.此时，读操作可以从内存中读取元数据.数据更新时先写数据，再更新内存中的元数据，最后将元数据所在的Block 写入SSD 盘，依靠Block 原子写保证整个写流程的原子性.[19]

如图4 所示，元数据、数据分别由索引Blob，数据Blob 存储.系统启动后，初始化阶段将所有索引Blob 内容加载到连续的内存空间，这样可以通过内存数组方式直接访问元数据的一级索引.根据前文定义，单个Chunk 的索引条目长度为144 B，那么1 个Block可以容纳4 096/144=28 个索引，以Intel P4610 SSD 盘（1.6 TB）为例，当Chunk 大小为默认值1MB 时，1 个SSD 盘的索引空间大约为（1.6 TB/1 MB）/28×4 096=236 MB，DRAM 中索引缓冲空间则最多为236 MB.运行过程通过查找内存线性表完成Chunk 索引查询，第1 级索引查询的时间复杂度O（1），其算法为ptr=（ChunkID/28）×4 KB+ChunkIDmod 28.第2 级索引需要从尾部遍历子数据块，因此，查询效率与子数据块的数量相关.

Fig.4 NVMe SSD-based index图4 基于NVMe SSD 的索引

单个Chunk 的索引条目保存在1 个Block 块，因此，1 个Chunk 的索引更新可以通过1 次原子写完成持久化，依靠SSD 的原子写能力实现用户数据的原子更新.一次完整的索引更新步骤为：

1）分配新的SSD 盘物理空间并写入数据，构造新的索引条目；2）将索引条目写入内存中静态数组的对应位置；3）将索引所在Block 整体写入SSD 盘对应的索引Blob 中.

元数据的原子性和一致性机制确保了系统崩溃一致性.系统发生宕机等异常时，内存缓存数据全部丢失，系统重新加载SSD 盘索引分区中的元数据，并根据元数据重新计算磁盘空闲空间信息，由于元数据信息的原子写入特性，不会出现数据不一致和空间泄漏的情况，同时保证元数据和数据保持一致.

基于NVMe SSD 的元数据存储，充分利用了NVMe SSD 硬件Block 原子写特性，实现了元数据的原子更新，有效提升了写性能，保证数据、元数据一致性；利用DRAM 缓存索引条目，显著提高系统读性能.

3.2.2 基于PMEM 的索引

PMEM 是介于内存、外存之间的新型存储介质，一方面PMEM 具有非易失、字节寻址、低读写延迟等特性，另一方面，PMEM 具有比DRAM 更大的存储空间和比NVMe SSD 更小的存储容量.因此，PMEM更适合存储元数据，这样可以充分发挥其延迟低、字节寻址的特性，同时节省内存资源开销.另外，借助PMDK[20]框架，不仅能够实现任意大小元数据原子写，而且支持多个元数据原子更新的事务.目前业界常用的PMEM 索引管理方式有B+树、SkipList 跳表，如DAOS[21]项目中使用B+树存储数据，MixStore[22]实现了一种PMEM 的无锁跳表，支持多线程并发，大大提高了PMEM 内存的访问效率.与NVMe SSD 采用静态表的方式不同，UStore 利用持久内存的硬件特性，设计了基于PMEM 的索引，整个数据空间划分为相互隔离的Blob 分区，每个Blob 的元数据保存到半持久化的SkipList 中，跳表叶子节点存储在PMEM 中，索引节点则存储在DRAM 中.一方面，PMEM 索引基于PMEM 的字节寻址能力实现了指针寻址，通过索引节点的地址信息可以直接访问持久存储中的叶子节点，每个叶子节点保存了下一个叶子节点地址信息，进而实现基于持久内存的链表结构.另一方面，利用PMEM 持久化特性解决索引节点掉电丢失问题，借助PMDK 接口中的布局（layout）结构体保存叶子节点链表头节点的地址信息，系统初始化时定位到头节点并遍历叶子节点链表，可以在DRAM 内存中构造整个跳表索引结构.UStore 采用半持久化的跳表索引，既能发挥DRAM 读写性能高的优势和提高元数据查找性能，又能发挥PMEM 的持久化、字节寻址特性，实现元数据的崩溃一致性.

如图5 所示，第1 级索引实现为半持久化的SkipList 跳表，第2 级索引为叶子节点中entry数组.与NVMe SSD 方式不同，不需要将索引内容映射到内存空间，而是直接访问持久内存中的索引，因此，第1 级索引查询的时间复杂度为O（logn）.

Fig.5 PMEM-based index图5 基于PMEM 的索引

第1 级索引的更新表现为跳表的插入、删除操作，涉及PMEM 中空间分配、回收、地址更新等，UStore 使用PMDK 开发库提供的持久内存事务实现索引的原子更新，事务接口需要记录事务日志，开销较大，但第1 级索引更新只发生在首次写Chunk、删除逻辑分区流程中，对存储系统读写性能影响有限.第2 级索引中entry长度为8B，而且设计为cacheline对齐，因此，第2 级索引直接由PMEM 硬件特性实现原子更新，entry数据更新后调用clflush 操作确保持久化完成，无需额外的原子性保证机制.

基于PMEM 的元数据存储，充分利用PMEM 的字节寻址、持久化特性以及8B 写入原子性，实现了接近内存的元数据访问性能.

3.2.3 基于硬件KVS 的索引

为了提高本地存储引擎的性能，业界尝试对存储软件栈进行卸载，以释放CPU 资源，硬件KVS 就是一种重要的卸载方式.一方面，KVS 内部集成掉电保护的高速存储芯片，能够像PMEM 一样持久化保存索引元数据；另一方面KVS 硬件设备对外提供标准的键值接口，软件栈通过get，put 接口方便地完成任意大小键值读写，并保证插入数据的原子性、一致性，极大地简化读写流程的设计.但是，KVS 采用PCIe 总线与主机CPU 通信，会带来较大延迟开销.

为了降低KVS 硬件访问频率，UStore 在DRAM空间中实现一个cache 层来缓存热数据索引，采用LRU算法对cache 中索引进行替换更新，索引查询时先从cache 中查找元数据，未命中则从KVS 硬件中读取元数据，并将读取的元数据信息插入到cache 中，当缓存中元数据数量超过阈值时则根据上次访问时间淘汰最近最少访问的元数据.cache 实现为DRAM 内存中的一个无锁SkipList 跳表，支持多个线程并发访问，只缓冲最近访问的热数据，跳表能够保持较低的深度，确保cache 能够实现非常高的查询效率.与NVMe SSD 索引缓冲类似，更新索引都需要调用put 接口将新的键值写入KVS 硬件，写入成功后同步更新cache，由硬件保证元数据更新的原子性，进而确保元数据、数据的一致性.

基于硬件KVS 的元数据存储，充分利用硬件KVS 的加速能力和原子读写特性，通过键值接口将元数据管理卸载到FPGA 硬件，主机软件不需要维护元数据信息，降低了软件栈的复杂度，有效减少了CPU 资源的开销.

4 实验及分析

4.1 实验环境

本实验采用的环境配置信息如表1 所示，PMEM配置为App-Direct 模式，作为持久化的内存来使用.主机操作系统均安装Fedora34，内核版本升级到5.16.11-100，以提供对PMEM 的支持，服务端分别安装UStore，Ceph octopus 15.2.16 提供底层存储服务，安装PostgreSQL 数据库软件.客户端选择压力测试工具FIO 完成I/O 性能测试，选择benchmarkSQL 完成数据库TPC-C 性能测试.进行BlueStore 和UStore对比测试时所采用的硬件环境和相关软件相同.

测试BlueStore 时，使用NVMe SSD 设备存储数据，PMEM 配置为fsdax 模式，用于存储BlueStore 的WAL 和DB 文件；测试UStore 时，使用NVMe SSD 存储数据，并分别使用PMEM，NVMe SSD，KVS 设备存储元数据，对应UStore-PM，UStore-NVMe，UStore-KVS 这3 种测试场景.客户端使用FIO 3.10 进行负载模拟，吞吐率测试配置深度为32，延迟测试配置深度为1，分别测试4KB，8KB，16KB，64KB 这4 种数据块大小的读写场景.FIO 工具使用自研bdevUstore ioengin 插件访问UStore 逻辑卷，使用FIO 自带的ioengine 插件访问BlueStore 存储，完成单节点块存储设备的性能测试.

4.2 写性能测试

写操作性能测试包括单深度的写延迟、32 深度的吞吐率，主要测试几种不同I/O 大小数据在UStore，BlueStore 这2 种存储系统的写流程.UStore 采用数据索引分离的设计方案，首次写入数据时需要为Chunk 块分配初始空间，并创建Chunk 索引，首次写开销大于覆盖写，为了验证设计方案，本实验还对首次顺序写的延迟做测试分析.

首先测试UStore-PM，UStore-NVMe，UStore-KVS，BlueStore 这 4 种系统在4 KB，8 KB，16 KB，64 KB 四种I/O 数据大小场景下的写延迟，图6～8 是首次顺序写、顺序覆盖写、随机覆盖写3 种场景下的延迟测试结果.在这3 种测试场景中，BlueStore 的写延迟都远大于UStore，以顺序覆盖写场景为例，BlueStore 的4KB 写延迟是UStore 的13 倍，8 KB 写延迟是UStore的4 倍，16 KB 写延迟是UStore 的3 倍.UStore 在这3种场景下的写延迟表现出相同的变化规律，随着I/O数据块的增大，写延迟显著增加，说明UStore 软件栈开销在整个写流程中占比较小，存储设备的写开销对整个写延迟影响较大.I/O 数据小于64 KB 时，BlueStore 的写延迟随写入数据大小的变化不大，说明此时BlueStore 软件栈开销远远大于硬件读写开销，存储硬件写延迟的变化对整个写延迟影响较小.4 种存储系统的64 KB 写延迟都出现较大幅度增长，说明此时硬件延迟成为写延迟开销的主要部分.可见，随着I/O 数据块变大，存储硬件的写延迟在整个写延迟中占比变大，UStore 软件栈的优势逐渐变小，存储系统的写延迟都趋向于硬件设备延迟.

Fig.6 First sequential write latency图6 首次顺序写延迟

Fig.7 Sequential override write latency图7 顺序覆盖写延迟

Fig.8 Random override write latency图8 随机覆盖写延迟

通过图6～8 纵向比较可以发现，相同数据大小场景下UStore 随机覆盖写、顺序覆盖写的延迟差距很小，首次写的延迟大于覆盖写延迟，例如UStore-PM的4 KB 首次写延迟比覆盖写多1.8 μs，16 KB 首次写比覆盖写多4.2 μs.这是因为首次写时需要创建索引、更新索引、持久化索引，覆盖写只需要更新索引、持久化索引，创建索引的操作主要在内存中完成，因此多了几个微秒的开销.BlueStore 写延迟整体较大，首次写、顺序覆盖写采用同样的实现机制，首次写、顺序覆盖写延迟基本持平.

通过纵向比较还发现，UStore 的16 KB 写延迟较8 KB 写延迟增长较小，8 KB 写延迟较4 KB 写延迟增长显著.如图8 所示，UStore-PM 的16KB 随机写延迟是8KB 随机写延迟的1.27 倍，8 KB 随机写延迟是4 KB 随机写延迟的3.4 倍.这是因为4 KB 数据采用直写方式更新Chunk 的初始空间，8 KB，16 KB，64 KB 采用ROW 方式写入数据，执行路径增加较多步骤，包括：分配新空间、遍历2 级索引、更新索引条目、释放旧空间等，因而UStore 的8 KB 写延迟较4 KB写延迟出现跳跃式增长，16 KB 写延迟较8 KB 写延迟则表现出缓慢增长趋势，64 KB 写延迟再次出现大幅增加则是由硬件延迟变大导致.

写满盘后分别测试顺序写、随机写的性能变化，测试结果如图9 和图10 所示.UStore 顺序写、随机写的性能都高于BlueStore，其中4 KB 场景下的性能优势最大，UStore-PM 的4 KB 顺序写吞吐率是BlueStore的3.2 倍，4 KB 随机写吞吐率是BlueStore 的9.2 倍.测试结果符合UStore 的设计预期，4 KB 支持原子写，数据直接写入SSD 空间，因此4 KB 写性能是UStore的最佳性能，与BlueStore 相比优势明显.随着数据块的增大，UStore 领先的优势逐渐减小，UStore-PM 的8 KB顺序写的吞吐率是BlueStore 的2.8 倍，16 KB 顺序写性的吞吐率是BlueStore 的1.7 倍.随机写性能表现出同样的规律，UStore-PM 的8KB 随机写吞吐率是BlueStore 的7.3 倍，16 KB 随机写吞吐率是BlueStore的2.7 倍.这是由于UStore 采用的ROW 方式实现超过4 KB 大小的数据原子写，数据从ROW 空间迁移到Chunk 初始空间占用了大量的磁盘带宽，导致UStore 的有效吞吐下降，相比BlueStore 的性能优势显著下降.当数据大小增加到64 KB 时，存储硬件所占开销比重更大，UStore 的性能优势进一步缩小，如图9 所示，UStore-PM 的64 KB 顺序写吞吐率是BlueStore 的1.55 倍.

Fig.9 Sequential write performance图9 顺序写性能

UStore 的3 种实现方式中，在顺序写场景下，UStore-PM 性能最高，UStore-NVMe 性能最低.根据硬件特性，PMEM 介质访问延迟最低，支持多线程并发写，写操作吞吐率最高；基于FPGA 的KVS 系统支持多深度异步写入，访问延迟介于PMEM 和NVMe SSD 之间，吞吐率基本介于二者之间；UStore-NVMe的元数据、数据都需要写SSD 盘，而且空间相邻数据的索引可能出现重复持久化，写操作的吞吐率最低.在随机写场景下，UStore-PM 性能最高，但随着数据大小的变化，UStore-KVS 与UStore-NVMe 的性能对比互有高低。这是由UStore-KVS 的元数据缓存机制导致的，在随机写时UStore-KVS 缓存命中率较低，而且变化比较大.

4.3 读性能测试

本次实验在盘写满前提下，分别对4 KB，8 KB，16 KB，64 KB 大小的数据在顺序读和随机读2 种场景下做性能对比测试.由图11、图12 可见，所有测试场景中UStore 的读操作性能都明显高于BlueStore.以UStore-PM 为例，4 KB 顺序读吞吐率是BlueStore的4.4 倍，4 KB 随机读吞吐率是BlueStore 的4.2 倍，UStore-KVS 和UStore-NVMe 的性能优势更加明显.这是因为UStore 读流程先查找索引，再经过用户态驱动读取NVMe SSD 中的数据，绕过了内核软件栈，避免了操作系统中断开销.与写性能测试不同，相同场景下，UStore-KVS 和UStore-NVMe 的读性能要高于UStore-PM，因为它们的索引全部缓冲在DRAM 中，读流程直接从DRAM 中读取索引元数据，性能高于从PMEM 中读取元数据.

Fig.12 Random read performanc图12 随机读性能

随着数据块的增大，存储设备的读开销逐渐增大，UStore 读吞吐率随之下降，与BlueStore 相比，读性能优势显著缩小.以UStore-NVMe 随机读场景为例，8 KB 的吞吐率比4 KB 下降39%，16 KB 的吞吐率比8 KB 下降43%.数据大小为64 KB 时，UStore 顺序读、随机读的吞吐率下降到50KIOPS 以下，与BlueStore 的吞吐率差距缩写到10～30KIOPS.

UStore 的3 种实现方式中，UStore-PM 的顺序读、随机读性能都低于另外2 种实现方式，UStore-PM 的元数据存储在PMEM 的叶子节点中，读操作需要从PMEM 读取索 引，UStore-KVS 和UStore-NVMe 的 热数据索引缓冲在DRAM 中，读操作从内存中读取索引，但是DRAM 空间有限，只能存放部分热数据的索引，缓存未命中时需要从SSD 盘读取索引信息，最差情况读性能会下降50%.因此，大规模存储场景下，UStore-PM 的整体读性能仍然高于UStore-KVS 和UStore-NVMe.

4.4 数据库负载测试

为了对比UStore 和BlueStore 在业务负载场景下的性能表现，本实验采用TPC-C 基准测试，将UStore-PM 和BlueStore 这2 种块设备格式化为EXT4 类型，挂载为PostgreSQL 数据库的数据盘，设置仓库数量为100，向PostgreSQL 导入10GB 业务数据，使用benchmarkSQL-5.0 测试工具，通过修改并发线程数模拟数据库的负载压力，测试不同负载场景下事务流量和数据盘延迟.

测试结果如图13 所示，基于UStore-PM 数据盘的数据库性能表现优异.UStore-PM 的事务流量是BlueStore 事务流量的2.8 倍，UStore-PM 的90%尾延迟不足BlueStore 90%尾延迟的50%.随着并发线程数量的增加，这2 种数据盘的事务性能都呈线性增长，UStore-PM 增长的斜率越大，并发度越高，性能优势越明显.主要原因是UStore 存储系统基于无锁并发的框架[23]实现，从根本上避免系统中断、互斥锁的开销，UStore 软件栈的并发能力远远优于基于内核实现的BlueStore，可以更好地发挥PostgreSQL 数据库事务并行处理能力.

Fig.13 TPC-C performance comparison图13 TPC-C 性能对比

本实验中，数据库服务通过NVMe over RDMA访问UStore-PM 设备，BlueStore 的rbd 客户端只能使用以太网访问远端存储设备.为了避免网络传输的差异，数据库服务使用rbd 内核驱动直接访问本地BlueStore 存储，因此，数据库服务访问UStore-PM 设备增加了网络传输的时间开销.本实验使用了新型高性能RDMA 网卡，收发延迟在10 μs 以内，根据4.2 节实验结果，UStore-PM 的4 KB 写延迟比BlueStore小50～80 μs，虽然增加了网络传输的延迟开销，访问UStore-PM 数据盘的延迟仍然小于访问BlueStore 数据盘，因此，数据库事务访问数据盘次数越多，UStore事务延迟的优势越明显.图13 中访问BlueStore 数据盘延迟比UStore-PM 数据盘多4～5 ms，这部分延迟差距包括多次访问数据盘增加的延迟和BlueStore 驱动层增加的延迟.随着并发量增加，事务访问2 种数据盘的延迟都出现增大，由于每个数据库事务访问数据盘的次数不变，总的延迟差变化不大.

综上，实验结果表明UStore 的吞吐率、单深度延迟都优于BlueStore，在4KB 块大小的场景下存在量级的优势.在3 种场景中，UStore-PM 的写性能优势突出，但读性能低于UStore-KVS，UStore-NVMe 的内存缓冲模式，因此UStore-PM 更适合数据规模大、写多读少的业务场景；UStore-NVMe 方式在元数据缓冲全部命中的前提下，能够取得非常好的性能，适合读写数据比较集中的业务场景；UStore-KVS 总体性能接近UStore-PM，CPU 资源占用最小，更适合计算密集的业务场景.在数据库负载测试中，相比于BlueStore，UStore-PM 在TPC-C 场景表现出较大优势.因此，UStore 能够灵活适配多种存储硬件配置和应用场景，在提升性能的同时，具有较好的通用性.

5 结论

持久内存、高性能KVS 加速卡、NVMe SSD 等新型存储硬件的出现，对存储软件栈提出了新的要求.本文实现了一种兼容PMEM、KVS 加速卡、NVMe SSD 等多种存储介质的统一存储系统UStore，满足多层次的业务需求；提出了一种高效的数据布局和管理方法，优化数据的存储和访问性能，利用硬件原子性实现了数据一致性，提升性能的同时增强了系统的稳定性；提出一种与物理存储介质形态解耦的元数据设计方案，能够高效地适配不同存储硬件介质和接口，并可根据硬件特性实现高效的数据块索引.实验表明，UStore 显著提升了读写性能，相比BlueStore，UStore-PM 的4 KB 随机写性能提升了8.2 倍，4 KB随机读性能提升了3.2 倍，UStore-KVS 和UStore-NVMe在不同测试场景中均表现出显著的性能改善.

展望未来，随着新型器件发展和持久内存产业化水平的提升，计算、存储和网络能力都将显著提升，可能会出现基于持久内存等新型器件构筑的全新存储环境.我们需要重新审视现有的设计和优化机制，并设计新的算法来适配新的硬件环境.

作者贡献声明：屠要峰提出了文章思路和方案设计，撰写论文；韩银俊、金浩参与方案实施和论文修改；陈正华协助设计实验方案；陈兵指导方案设计和论文写作.