Conclusions and future work

[TOC]

天上冷飕飕，地上滚绣球；有陷是包子，没陷是窝头 — 郭儿

• 目标1：ATC‘ 22，1月6/13日
• 目标2：FAST’ 23，7月24日

工作总结

1. 问题总结

• 文档总结 《IO瓶颈分析》

• 出发点：Ceph并不能发挥NVMe SSD的性能

  

• 性能分析

  • iostat：主要差距在于平均队列长度，最好的结果也只有4左右，这说明对下层I/O压力还是不足

  

  • 火焰图，主要占用CPU时间有以下两部分:

    • find_object_context ：获取对象上下文，主要是对象的元数据，会从Cache获取RocksDB中读取
    • execute_ctx：从BlueStore中读取数据
    • 整个处理流程中，上下文切换主要发生在从磁盘中读数据，PG锁竞争，一些cond_wait

  • Ceph-Blk+lttng分析io时间

    • 对读过程所有io进行时间统计，总运行时间平均耗时2.54ms，其中osd部分1.08ms (占总的42%)，msg部分占29%
    • 进出队列时间0.4ms (占osd37%，占总的16%)
    • find_object_context有0.31ms （28.7%，12%）
    • decode有0.01ms、complete_read_ctx有0.06ms、execute_ctx平均耗时0.32ms （30%，12.5%）
    • 从trace分析，主要耗时在网络模块、osd中进出队列部分、获取对象上下文和从bluestore中读取数据等

  • 分段测试：网络、Bluestore、RocksDB

    • 网络：足够的压力可以是3个Worker线程满载，并且有1949.3MB/s，暂时应该不会成为主要瓶颈
    • Bluestore：不同对象大小和线程下测试，读性能上限大概是1.1G/s

  • RocksDB分析

    • 读流程分成8个过程，通过db_bench+perf分析每个过程的延迟
    • 两个大头：1. 高读盘延迟 DBLoad 50.58%；2. 内存查找中文件索引 IBSeek & DBSeek 15.31%

    

• 数据分布-CRUSH问题

  • 参考文档《数据分布优化总结》

  

  • 问题1：不可控迁移，迁移量是理论下限的h倍（h为分层结构的层数）

  • 问题2：不够均衡，CRUSH 输入的样本容量不够、副本机制的缺陷

  • 问题3：选择存储节点时，仅以节点存储容量为唯一选择条件，并没有考虑其他因素（到网络和节点 的负载状况等等）

2. 工作总结

• Ceph优化：Bluefs+RocksDB+异步读+索引优化+数据分布…

  

• RocksDB优化—TridentKV

  • 异步优化（+SPDK）降低读盘延迟；Learned Index加速文件索引

  • 分区优化删除问题

    

• 数据分布优化

  • 结合表可控分布；结合强化学习 RLRP

    

论文总结

• key-value store 2021年就有 4,490 条记录

• 以上图为基础，补充最新的论文

主题1：元数据优化—高性能KV

• 索引结构

  • 结合场景和介质特性等等，优化索引
  • LSM-tree（L）, B+tree（B）, Tire-tree（T）, Bε-tree（E）, Bw-Tree（W），Hash（H），SkipList（S）
  • SLM-DB：LB；LSM-trie ：LT；SplinterDB：LE；ArkDB：LW；UniKV：LH；Skiptree：LS
  • 参考文档《KV索引综述》(doing)

• 结合新介质 && 混合设备：SpanDB（Fast‘21），KVIMR（ATC’21），Facebook（ATC‘21）

  • 参考文档《NVMKV综述》

• Far memory && DSM：DrTM+R（EuroSys’16），DrTM+H（OSDI’18），DrTM+N（ACT‘21），Xstore（OSDI’20）

  • 参考文档《分布式存储》

• LSM-tree & RocksDB

  • LSM-based storage techniques: a survey （VLDP 20）

  

  

  • 参考文档《键值存储优化论文综述》
  • 读写放大
    • KV分离：Wisckey，HashKV，UniKV，DiffKV（ATC‘21）
    • 允许部分键值覆盖：PebblesDB，LSM-tire，SifrDB
    • 增大内存：Skiptree，VT-Tree，FloDB
  • Compaction：TRIAD，LDC，LSbM，SILK，X-Engine（FPGA），
    • Constructing and Analyzing the LSM Compaction Design Space，VLDB’21
    • 把compaction问题抽象建模（设计空间），为如何和何时compaction提供指导
  • 尾延迟（compaction导致写停顿）：SILK，bLSM，KVell，MatrixKV，CruiseDB，RocksDB（写节流算法）
  • 空间优化：SuRF，SlimDB，RocksDB
  • 读优化
    • 参考文档《RocksDB读优化总结》
    • 索引优化
      • X-Engine，SLM-DB，Kvell，Bourbon&&Google
    • cache
      • Ac-key：多种cache自适性选择
      • LSbM-Tree，Leaper（VLDP’21）：compaction之后读cache命中率下降严重
    • filter
      • BLSM：第一次使用bloom过滤器
      • ElasticBF，monkey：动态调整filter大小
      • SuRF：支持范围查询；
      • Rosetta，Chucky（Sigmod’21）
  • 删除优化
    • 参考文档《RocksDB删除问题总结》
    • Lethe：定期 && 分区
    • RocksDB / MyRocks：SingleDelete和定期触发compaction
  • 范围查询
    • RocksDB：前缀filter
    • REMIX（Fast’21）：分析LSM基于迭代器范围查询过程，通过记录键值映射和游标加速范围查询
  • CPU
    • Kvell：share-nothing；
    • Kreon：系统调用开销大，优化内核
    • uDepot：异步架构
  • 自动调优：Monkey，Dosteovsky，ElasticBF
  • 性能测试、自动调参、特定负载和场景等等
    • Toward a Beter Understanding and Evaluation of Tree Structures on Flash SSDs，VLDB’21

• 最新论文分析：ATC’21，OSDI‘21，VLDB’21，SIGMOD‘21

论文1-1（索引）：ArkDB: a Key-Value Engine for Scalable Cloud Storage Services

• sigmod 2021, 阿里盘古，Bw-Tree + LSM-tree 结合

• 背景：LSM-tree 和 Bw-tree

  • 传统的基于b+tree的存储引擎，例如BerkeleyDB和MySQL的innodb，读的性能很高，随机读和范围读都挺高，但是写性能比较低，因为写的时候，虽然只需要把redo log写入磁盘即可完成，但是为了缩短失效恢复时候的恢复时间，一般都需要频繁的做checkpoint。checkpoint是随机的写，随机写无论是在传统的机械硬盘还是SSD，或者PCID SSD上性能都较低，在实际测试MySQL的过程中使用TPCC，通常能把磁盘写满，导致刷redo log性能降低，从而影响系统整体的吞吐量
  • 而基于LSM-tree典型的例如leveldb／rocksdb，写入性能较高，但是读性能，特别是范围读能力性能较差，例如读一条数据首先要看memtable中有没有，然后再扫描1级sstable和2级sstable，则需要多次磁盘io才能读到这条数据，特别是1级sstable每个分块的range还可能交叉，需要扫描多个1级sstable文件。另外一个就是在compact的时候会有一个性能的剧烈波动。

• The Bw-Tree: A B-tree for New Hardware Platforms，ICDE’13，微软研究院

  • 通过无锁的方式来操作b+tree，提升随机读和范围读的性能。核心的思想是把b+tree的page通过page id（PID）映射map，map的[key, value]变成[PID, page value]，把直接对page的修改，变成一个修改的操作记录，加入到“page value”，所以“page value”可能是一个“base page”即page原始的内容，和一串对page修改形成的记录的链表，而在修改记录链表中加入一个修改记录节点可以很容易变成一个无锁的方式来实现。另外就是对btree的split和merge操作也通过类似的原理，把具体的操作细化成好几个原子操作，避免传统的加锁方式

    

  • 把传统checkpoint刷page的变成通过log struct storage方式刷盘，把随机写变成顺序写，提高写的性能

• ArkDB

  • 用户事务的数据更改记录在 UserTransactionLog 中，并在提交时应用于Active的 MemoryBuffer (❶)。 MemoryBuffer 支持point查找和有序范围扫描。 一旦Active MemoryBuffer 中的数据量达到阈值，例如 64 MB，这个 MemoryBuffer 就会被sealed，并打开一个新的 MemoryBuffer 以接受新的修改。 Sealed MemoryBuffer 被刷新到存储中 (❷)。 此刷新操作称为获取用户checkpoint。 存储的主干结构是一棵 B+ 树。 对于用户checkpoint，同一叶子page的数据更改形成了Host page的Delta Page。 Delta Page被写入 DeltaPageStream。 通过从Host Page到添加到 PageMappingTable 的这个 delta page的页面映射，一个 delta page被间接地挂接到 B+ 树中
  • 当Leaf Page的Delta Page数达到阈值时，该Leaf Page及其更改被压缩到单个连续Page中。稍后，该页面的存储位置将更新到父页面，导致父页面被重写。同样地，从旧的父页面映射到重写的父页面的页面被添加到PageMappingTable中。这个映射意味着父节点的实际内容现在位于重写的父节点页面中。更新了父页面后，可以删除压缩页的页面映射项。通过这种方式，ArkDB有效地收缩了PageMappingTable。当一个Host Page被压缩时，它可能被重写为多个页面，在这种情况下，它表示一个 Page Split。紧凑的叶页和重写的父页都被称为钩在B+树中的基页，并被写入BasePageStream中
  • 页面映射更改作为系统事务执行，并记录在SystemTransactionLog中。只有在系统事务日志记录被持久化之后，对PageMappingTable的更改才会被应用（❹）。从概念上讲，DeltaPageStream、BasePageStream和PageMappingTable一起形成了一个存储上的Bw-tree，在只追加的存储上有Delta Page。通过合并来自MemoryBuffers和存储上的Bw-tree的结果来回答查询
  • 随着用户检查点、页面压缩和页面拆分或合并，DeltaPageStream和BasePageStream中的extent也会被消耗掉。当一个页面被重写时，该页面先前写入的部分将失效。每个extent的确切有效用法在ExtentUsageTable中被跟踪，在DeltaPageStream和BasePageStream的垃圾收集期间会参考这个表。当ExtentUsageTable占用的内存达到一个阈值时，历史使用数据会被压缩，并溢出到存储(实际上是BasePageStream)，以控制表内存占用低于一个阈值
  • 当系统事务日志大小达到阈值时，PageMappingTable和ExtentUsageTable都会被刷新到系统检查点。在获取系统检查点之后 (❺) ，它的元数据(包括时间戳和位置)被记录到MetadataLog中。恢复从MetadataLog指示的最近的系统检查点开始。分区拆分或合并操作也记录在MetadataLog中，以指导恢复
  • 具体优化：略

论文1-2（索引、测试）Toward a Beter Understanding and Evaluation of Tree Structures on Flash SSDs

• VLDB’21，IBM Research，测试陷阱和建议，听了如同听的一席话的一席话
• Persistent tree data structures (PTSes)
  • log structured merge (LSM) tree , used, e.g., by RocksDB and BigTable;
  • the B+Tree , used, e.g., by Db2 and WiredTiger (the default storage engine in MongoDB );
  • the Bw-tree,used, e.g., by Hekaton and Peloton;
  • the B-e tree,used, e.g., by Tucana and TokuMX.
• 由于树结构的内部行为对性能的影响，以及 SSD 底层逻辑的特殊性，SSD 上对数结构进行基准测试是一个复杂的过程，容易出现不准确的评估。本文通过 RocksDB 和 WiredTiger 确定了 7 个 SSD 基准测试陷阱，该陷阱会导致对关键性能指标的错误测量，导致生产环境中无法实现最优部署。本文还提供了避坑指南来获得更可靠的性能测量结果
  • Running short tests （测试周期短）
    • Flash SSDs have time-evolving performance dynamics. Short tests lead to results that are not representative of the long-term application performance
    • 闪存 SSD 具有随时间变化的性能动态性，短期测试导致的结果不能代表长期应用程序性能
    • 建议1：研究人员应该区分稳态（steady-state ）和突发性能，并优先报告前者。为了检测稳态行为，应该实施一种包含应用程序级吞吐量、WA-A 和 WA-D 的整体方法。 CUSUM 等技术可用于检测这些指标在足够长的时间内没有显着变化
      • CUSUM：Continuous Inspection schemes
  • Ignoring the device write amplifcation (WA-D) （设备写放大）
    • SSDs perform internal garbage collection that leads to write amplifcation. Ignoring this metric leads to inaccurate measurements of the I/O efciency of a PTS
    • SSD 执行内部垃圾回收导致写入放大，忽略此指标会导致对 PTS 的 I/O 效率的测量不准确
    • 建议2：WA-D 的分析应该是任何 PTS 性能研究的标准步骤，这种分析是正确衡量替代系统的闪存友好性和 I/O 效率的基础
  • Ignoring the internal state of the SSD （SSD的内部状态）
    • Experimental results may signifcantly vary depending on the initial state of the drive. This pitfall leads to unfair and non-reproducible performance measurements
    • 实验结果可能会因SSD的初始状态而显着不同，这个陷阱会导致不公平和不可重现的性能测量
    • 建议3：在每次测试之前控制和报告 SSD 的初始状态，此状态取决于 PTS 的目标部署。 对于性能工程师来说，这种状态应该尽可能类似于在生产环境中观察到的状态，这也取决于可能与 PTS 并置的其他应用程序。 应该对SSD 进行预处理（略）
  • Ignoring the dataset size （数据量大小）
    • SSDs exhibit different performance depending on the amount of data stored. This pitfall leads to biased evaluations
    • SSD 不同存储的数据量下表现出不同的性能，这个陷阱导致有偏见的评价
    • 建议4：建议使用生产中预期大小的数据集对替代 PTS 进行基准测试，并且为了时间的缘故不要使用缩小的数据集进行测试。 建议尝试不同的数据集大小，首先，它允许研究人员研究其 PTS 设计对不同设备利用率值的敏感性。 其次，它不允许有意或无意地偏向于一种设计而不是另一种设计的评估
  • Ignoring the extra storage capacity a PTS needs to manage data and store additional meta-data （额外容量）
    • This pitfall leads to ignoring the storage allocation versus performance tradeoff of a PTS, which is methodologically wrong and can result in sub-optimal deployments in production systems
    • 这个陷阱导致忽略 PTS 的存储分配与性能权衡，这在方法上是错误的，可能导致生产系统中的部署不理想
    • 建议5：PTS 的实验评估不应只关注性能，还应包括空间放大。 对于研究工作，分析空间放大提供了关于 PTS 设计选择的性能动态和权衡的额外见解，并允许设计之间的多维比较。 对于生产工程师来说，分析空间放大是计算为生产中的 PTS 配置存储的货币成本的关键，这通常比最大性能更重要
  • Ignoring SSD over-provisioning （超额配置）
    • Over-provisioning an SSD (i.e., reserving part of its capacity for internal operations) can improve the performance of a PTS, at the cost of reducing the amount of data that the PTS can index. This pitfall leads to the capacity versus performance trade-off achievable by a PTS being ignored
    • 超额配置 SSD（即保留部分容量用于内部操作）可以提高 PTS 的性能，但代价是减少 PTS 可以索引的数据量。 这个陷阱导致 PTS 可实现的容量与性能权衡被忽略
    • 建议6：众所周知，PTS 有许多影响性能的调参旋钮，建议考虑将 SSD 超额配置作为 PTS 的附加但第一类调整旋钮。SSD 额外的预留空间以容量换取性能，并且在某些用例中可以降低 PTS 部署的存储成本
  • Ignoring the effect of the underlying storage technology on performance （底层存储技术对性能的影响）
    • This pitfall leads to drawing quantitative and qualitative conclusions that do not hold across different SSD types
    • 这个陷阱导致得出的定量和定性结论不适用于不同的 SSD 类型
    • 建议7：建议在多个 SSD 类别上测试 PTS，最好使用来自多个供应商的设备，并使用多种闪存技术。 这使研究人员能够就 PTS 设计的性能得出更广泛、更重要的结论，并评估此类设计的“内在”有效性，而无需将其与测试该设计的介质的特定特性联系起来。 对于性能工程师来说，使用多个驱动器进行测试对于确定哪个驱动器能够根据目标工作负载产生最佳的存储容量、性能和成本组合至关重要
• 参考文档《RocksDB测试方法》(doing)
  • Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook（Fast’20）：负载相关

论文3-1（KV分离）Differentiated Key-Value Storage Management for Balanced I/O Performance

• ATC’21，李永坤团队，把KV分离玩出花了
• KV分离问题
  • GC低效：HashKV
  • Scan性能差：DiffKV，把value也用类树结构管理

论文3-2 (读优化-cache)： Leaper: a learned prefetcher for cache invalidation in LSM-tree based storage engines

• 北京大学，VLDB’20，采用机器学习方法解决X-Engine中cache miss问题

• 在X-Engine实际运行中，由于后台异步数据合并任务造成的大面积缓存失效问题 LSbM-Tree提出这种问题，具体解决是多增一个buffer cache，空间换效率。

• Leaper采用机器学习算法，预测一个 compaction 任务在执行过程中和刚刚结束执行时，数据库上层 SQL 负载可能会访问到数据记录并提前将其加载进 cache 中，从而实现降低 cache miss，提高 QPS 稳定性的目的

  

• Leaper分成三个部分：Collector、Prefetcher和Learner

  • Collector：收集数据和分key range
  • Prefetcher：预测Hot key
  • Learner：学习模型/训练

论文3-2 (读优化-filter)： Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores && Chucky: A Succinct Cuckoo Filter for LSM-Tree

• 哈佛大学Stratos Idreos团队，Monkey，Dosteovsky，，，
• bloom filter的问题
  • Chucky（sigmod’21）：性能低，开销大。之前的SSD或者HDD等访问延迟较大，Bloom filter引起的开销比重较小，可以忽略不计NVMe SSD性能提升，与DRAM性能差距进一步缩小，由于在每层都要维护Bloom filter，会引起比较大的查询延迟，引起LSM-Tree中Bloom filter成为新的瓶颈之一
  • SuRF，Rosetta（sigmod’20）：不支持范围查询
• Rosetta：优化SuRF的范围查询能力
  • 问题1：Short and Medium Range Queries are Significantly Sub-Optimal
  • 问题2：Lack of Support for Workloads With Key Query Correlation or Skew

• Chucky
  • 关注点：高性能介质的使用，Bloom filter引起的开销不容忽视
  • Chucky提出用单个Succinct Cuckoo Filter替代LSM-Tree中的多个Bloom filter，可以有效减少查找引起的开销

主题2：OSD架构优化

• 参考文档《Ceph优化总结》

• Messenger优化
  • 问题：当连接过载时，它将导致工作线程之间出现负载不平衡的问题
  • Optimizing communication performance in scale-out storage system，平衡算法&双工作线程
  • Async-LCAM：缓解锁争用开销
• Ceph-osd流程优化
  • Performance Optimization for All Flash Scale-Out Storage：主要针对写过程，细化PG锁流程，无阻塞日志和轻量级事务处理
  • Design of Global Data Deduplication for a Scale-Out Distributed Storage System：重复数据删除
  • Re-architecting Distributed Block Storage System for Improving Random Write Performance，ICDCS‘21
  • Crimson: A New Ceph OSD for the Age of Persistent Memory and Fast NVMe Storage：社区方向 Seastore
  • Ceph Optimizations for NVMe：RocksDB去重 + spdk、dpdk与ceph messenger RDMA
• 后端存储 Bluestore & Bluefs
  • File systems unfit as distributed storage backends: lessons from 10 years of Ceph evolution
  • Reconciling LSM-Trees with Modern Hard Drives using BlueFS
• 其他
  • Towards Cluster-wide Deduplication Based on Ceph
  • SAPPHIRE

论文1：Re-architecting Distributed Block Storage System for Improving Random Write Performance

• ICDCS‘21，Myoungwon Oh 团队，三星&国立首尔大学，通过重新架构Ceph来构建一个具有高随机写性能的分布式块存储系统

• 主要思想和设计原则参考KVell：使用分片分区（share-nothing），随机IO不排序

• 基于NVMe SSD的Ceph性能瓶颈

  • roofline-based 的方法对带有NVMe固态硬盘的传统分布式数据块存储系统（Ceph）进行性能分析，发现瓶颈不在于某个特定的软件模块，而在于整个软件堆栈
    • Roofline: an insightful visual performance model for multicore architectures.
  • (1) tightly coupled I/O processing
  • (2) inefficient threading architecture
  • and (3) local backend data store causing excessive CPU usage

• 背景以及问题

  • OSD守护进程由三个模块组成: Messenger、OSD core，后端存储

    • Messenger：有messenger 线程池，负责消息处理(MP)的，收到IO请求，它会将请求插入到相应的PG工作队列中
    • OSD core：有PG线程池，负责PG工作队列中传入请求的复制处理(RP)、事务处理(TP)
    • Bluestore：后端对象存储(OS)，负责数据持久化。使用RocksDB存储Ceph的元数据，同时将用户数据存储在原始磁盘中。由于数据是以 out-of-place 的方式更新的，因此需要维护工作(MT)，例如compaction
    • 大致分成五个过程消息处理(MP)、复制处理(RP)、事务处理(TP)、对象存储(OS)和维护任务(MT)

  • 性能测试：baseline Ceph (Original) 和三个修改版本

    • RTC-v1：实现了一个run-to-completion (RTC) 模型，一个线程执行客户端请求的完整处理，它包括MP，RP，TP，OS，MT
    • RTC-v2：不存在对象存储开销时RTC模型的性能，对后端对象存储的写请求立即返回成功，只包括MP、RP和TP
    • RTC-v3：当事务处理和对象存储相关工作不产生开销时的性能，只包括MP和RP

    

    • NP：用于Network Processing 的CPU时间，包括MP和RP的；latency-critical jobs
    • SP：代表 Storage Processing 的CPU时间， 包括TP和OS。
    • 当使用RTC模型时，RTC代表网络处理和存储处理的CPU时间部分，即RTC = NP + SP
    • MT：表示后端对象存储所需的维护任务的CPU时间，例如 compaction 和 sync 等等
    • 总结一下
      • RTC-v1执行MP+RP+TP+OS+MT，RTC-v2执行MP+RP+TP，RTC-v3执行MP+RP
      • NP = MP + RP；SP = TP + OS；RTC = NP + SP

  • 性能分析

    • fio，4KB随机写入
    • Original配置：两个messenger线程和两个PG线程，同时将Ceph process 设置为仅在4个内核上运行；为了公平比较，将Ceph使用的线程总数保持为每个节点四个线程，不包括后端对象存储使用的线程数
    • 在原始版本中，每个节点的CPU使用率为346%，而性能为29K IOPS
    • 假设其性能随系统内核数量线性扩展，最理想的性能约为369K IOPS(每个节点有44个逻辑内核，29*11)，非常低
    • 每个节点使用8个NVMe SSD（4K随机写 330KIOPS）

  • 问题分析 和 解决方法

    

    • Tightly Coupled I/O Processing
      • 1.主节点从客户端接收请求；2. 主节点将数据保存在存储器中；3. 主节点向副本服务器发送复制请求；4. 辅助节点在收到复制请求后将数据保存在存储中；5. 主节点等待来自副本的输入/输出完成确认；6. 主节点将结果发送给客户端
      • RTC-v3 其平均延迟(0.8毫秒)也高于的NVMe SSD的4KB随机写入延迟(0.4毫秒)，且CPU使用率为200%。这意味着除了网络处理或延迟复制处理之外，提交写入的额外写入过程会导致高延迟，并且IO路径已经使用了大量的CPU
      • 问题在于 latency-critical tasks 和 the best-effort batch tasks 紧耦合
      • 优化措施：2、4过程 和 其他过程 需要解耦，异步flush

    

    • Inefficient Threading Architecture

      • 大多数分布式存储系统使用线程池模型，它为不同的目的管理不同的线程池

      • 在Ceph中，有两个线程池: 用于网络处理的messenger线程池和用于存储处理的PG线程池

      • 然而，这种体系结构导致线程之间频繁的上下文切换，因为IO请求是在一条长路径上处理的，其中messenger和PG线程都多次涉及，从而导致上下文切换开销，这在快速设备中变得不可忽略

      • 为了解决快速设备的性能问题，RTC model被应用，通过最小化上下文切换开销和提高缓存效率

        • IX: A protected dataplane operating system for high throughput and low latency, 应用到网络解决方案中，其中每个数据包在处理任何其他数据包之前都被完全处理
        • Seastore

      • 简单的RTC模型 RTC-v1

        • 用一个RTC模型替换Ceph中的传统线程池模型，其中每个RTC线程都被固定在一个专用的内核上。请注意，为了防止来自单个客户端的请求重新排序，来自同一客户端的所有请求都由同一messenger线程处理。因此，在正在进行的IO操作完成之前，RTC 线程无法处理其他IO请求，它会导致响应时间延迟
        • 与Original相比，简单的RTC模型(RTC-v1)通过减轻上下文切换开销，在较低的CPU使用率下实现了稍好的性能。此外，没有对象存储和维护任务的简单RTC模型(RTC-v2)实现了较高性能
        • 但是，它的延迟仍然比NVMe慢(1.45毫秒)，并且性能提升很小，因为RTC线程在等待副本的写完成确认时被阻塞

      • 优化措施：Prioritized Thread Control

        • 为不同的线程类型维护单独的CPU池，涉及线程调度策略，以提高CPU利用率

        • 有两种线程类型：latency-critical tasks的优先级线程 和 其他任务的非优先级线程，前者负责消息交换和复制处理，而后者负责存储处理

          

        • 每个优先级线程都被固定在一个专用的核心上，因为来自其他线程的干扰会影响客户端感知的性能。相比之下，非优先级线程共享剩余的内核，每个内核负责PG的存储处理

        • 这种线程架构背后的一个关键概念是为延迟关键任务赋予高优先级，以便写操作可以以低延迟(通过优先级线程)完成，同时通过以批处理方式(通过非优先级线程)刷新写操作来减少CPU消耗

        • 具体线程设计和调度 略

    • Local Backend Object Store causing High CPU Usage

      • Ceph的默认后端对象存储 BlueStore 直接管理存储设备，而不使用本地文件系统来解决问题，例如日志异常的日志记录，以及分布式存储系统中的对象和文件系统中的文件之间不必要的转换开销。但是，在使用NVMe固态硬盘时，在随机IO工作负载下，BlueStore 可能会受到CPU的限制
      • 这主要有两个原因。第一，主机端写放大。BlueStore使用基于LSM-tree的RocksDB进行元数据和小数据写入。然而，所有LSM-tree需要compaction；此外，虽然它是在后台执行的，但它不仅干扰前台I/o，而且需要很高的CPU时间来运行它。后端数据存储的后台作业(MT)占总CPU使用量中不可忽略的一部分
      • 第二，单一data domain。现代后端数据存储使用的一致性机制可能是可伸缩性的性能瓶颈。例如，BlueStore需要同步原语来处理单个分区内的事务。为了克服这些问题，一些研究提出了一种用于本地文件系统的分区域方法，然而，由于本地文件系统不向应用程序公开这种分区域信息，分布式存储系统很难实现位置感知处理
      • 优化措施：CPU-efficient object store
        • 旨在最大限度地减少执行客户端发出的操作所需的IO数量，并在存储处理过程中最大限度地提高并行性
        • 避免写入放大，它为每个分区使用就地更新磁盘布局，例如日志文件系统；它由元数据、块图和数据区组成。因为它允许覆盖，所以不需要清理过程（compaction），它不仅降低了主机端的写入放大，还降低了主机端的CPU消耗
        • 使用了预分配技术，用于避免不必要的元数据更新，减少IO数量
          • WALDIO: Eliminating the filesystem journaling in resolving the journaling of journal anomaly
          • 覆盖预先分配的对象不需要对其元数据(如块位图、索引节点表等)进行任何更改，不需要元数据更新，这只有在对象大小固定的情况下才可行。在典型的数据块存储服务中，数据块设备映像被分条到固定大小的对象上。例如，在Ceph RBD，默认对象大小为4MB。因此，可以在创建时预先分配所有对象
        • 为了获得高性能，对象存储使用NVM作为元数据缓存。它还将整个磁盘空间划分为多个分区，这样就可以将一个非优先级线程分配给一个分区。因此，可以并行处理IO操作，而不会发生锁争用

主题3：新介质和新场景的

其他

• 自动调参：参数对系统使用影响非常大，Ceph相关研究很少
• 可靠性：数据分布，故障处理
• SCM、RDMA

论文（NVM）：Improving Performance of Flash Based Key-Value Stores Using Storage Class Memory as a Volatile Memory Extension

• Optane PMem 100系列SCMs (DCPMM) 做 RocksDB 混合缓存

• 应用场景（doing）

思考1 （10/16）

• 之前的想法
  • 高性能KV，针对场景和设备
  • 混合存储中，性能的提升、数据交换
  • 混合存储中，从延迟上保证前端io的情况下，尽可能给后台任务分配更多的资源

目标要小，想法要大 — 冉·阿万

• 以RocksDB为基准，LSM-tree的读性能优化为目标

  • 思考1：LSM-tree的读性能是否是个问题？

    • 传统的读性能问题指的是要一层层找，导致多次IO和读放大
    • RocksDB很多优化，参数调控和Cache设置，可以保证一次找到
    • RocksDB关注的优化点（Fast‘21）：
      • How can we use SSD/HDD hybrid storage to improve efficiency? （混合存储）
      • How can we mitigate the performance impact on readers when there are many consecutive deletion markers? （标记删除对读性能的影响）
      • How should we improve our write throttling algorithms? （节流算法，写操作和compaction导致的性能停顿）
      • Can we develop an efficient way of comparing two replicas to ensure they contain the same data? （一致性算法）
      • How can we best exploit SCM? Should we still use LSM tree and how to organize storage hierarchy? （新介质）
      • Can there be a generic integrity API to handle data handoff between RocksDB and the file system layer? （RocksDB和文件系统之间的数据转换，提供通用API）

  • 思考2：索引、cache、filter等等，应该从何下手？

    • 分析RocksDB火焰图，seek和读盘 -> 思考索引的优化

    • 有些细节可以扣，比如序列化、系统调用开销等等 -> 内存组织 / spdk / by pass kernel

      

    • cache的影响？和负载有关，随机读cache? -> Scan操作的cache优化？

    • RocksDB Filter的误报率比较低，可能的问题是内存消耗和Scan -> Learned index也有做filter的研究

  • 思考3：继续之前的研究，更加深入？

    • learned index训练和模型的优化

    • google的方式可以使得性能与模型精度无关，但是sstable创建时训练模型，占用过多CPU，严重影响写性能和compaction

    • delete问题：分区的方法治标不治本，同一分区内的删除也会有问题；另外分区后需要额外维护索引来加速Get和Scan，导致写性能下降

      

  • 思考4：另辟蹊径？

    • 从CPU占用入手？Scan性能？NVM能干嘛？
    • bluefs？索引结构能不能结合一下？
    • 新问题？新场景？

思考2（10/23）

为什么不问问神奇海螺呢 — 维穆里·宝

最近会议，SOSP：10月26日；SC：11月16日；SoCC（B）：11月1日

【老师的意见】

• KV读优化，根据之前分析，可以基于几个方向出发

  • Cache：提高缓存命中率。由于在 LSM-tree 中数据从内存写入磁盘和磁盘中不同层间的数据合并操作，造成缓存失效问题，降低了缓存命中率。可以考虑设计相关算法（相关索引、机器学习等）根据工作负载和 LSM-tree 内部的操作特点，预测未来可能访问的数据并将其预取到缓存中，从而降低缓存失效问题
    • ML/RL：Leaper + Cacheus
    • 结合负载：Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook
      • UDB：a MySQL storage layer for social graph data
      • ZippyDB：a distributed key-value store
      • UP2X：a distributed key-value store for AI/ML services
  • LSM-tree 范围查询优化。目前, 大多数查询优化方法主要是针对 LSM-tree 点查询进行优化，对范围查询的优化较少，而 LSM-tree 对范围查询更不友好。使用filter来LSM优化范围查询无法避免对数据的探查与探查结果的合并开销，并且不适合长范围查询场景。REMIX 对数据建立全局索引能够避免这些开销，但是插入新数据时索引重构开销较大。能否考虑将两者优势结合在一起?
    • Partitioned Learned Bloom Filter，Tim Kraska
    • Hash Adaptive Bloom Filter，ICDE‘21
    • Learned FBF: Learning-Based Functional Bloom Filter for Key–Value Storage，TOC
  • LSM-tree大规模删除问题，新的解决思路
    • 是否可以考虑建立删除窗口，超过一定值设定compaction高优先级
    • 分区方案能否优化
    • 像REMIX一样建立一个全局索引，空间换效率

• 优势：有基础，博士论文好组织；劣势：很难有什么创新

【伟哥的意见】

• 和强化学习业务结合？

  • Ray: A Distributed Framework for Emerging AI Applications

  • DI-engine / DI-store

    

  • 强化学习训练特点：数据分布是动态生成、时序制约的，已有的训练模型会影响后续经验缓存池样本的分布

  • 存储优化点：Prefetching？节点选择&任务分配？性能优化？（调度、网络、训练并行等）

  • Clairvoyant Prefetching for Distributed Machine Learning I/O，SC‘21

  • 优势：没人搞过，做好应该能出文章；劣势：没基础（不了解训练和存储过程），没相应问题，没出发点

【易老师的意见】：可以和公司业务相结合

• 先参与项目中，从项目中入手由浅入深，找到问题和研究方向
  • 大集群项目
  • Ceph性能优化
  • Lunule: An Agile and Judicious Metadata Load Balancer for CephFS，SC‘21
• 收集一定的trace，分析负载
  • Characterization and Prediction of Deep Learning Workloads in Large-Scale GPU Datacenters，SC’21
  • CHRONUS: A Novel Deadline-aware Scheduler for Deep Learning Training Jobs，SoCC’21
• 结合AI应用和算法特点，针对性优化存储
  • Clairvoyant Prefetching for Distributed Machine Learning I/O，SC‘21
  • ZeRO-Infinity: Breaking the GPU Memory Wall for Extreme Scale Deep Learning

论文1（filter）Partitioned Learned Bloom Filters

论文2（训练IO优化）Clairvoyant Prefetching for Distributed Machine Learning I/O

• 问题：I/O正在成为机器学习训练的主要瓶颈，特别是在分布式环境中。事实上，在大规模情况下，I/O需要85%的训练时间

• 训练一个DNN涉及三个方面：执行DNN的计算；通信：跨节点同步更新；和I/O：为每个节点提供训练数据和标签

  • 绝大多数优化训练的工作都集中在计算和通信上
  • 训练中的性能瓶颈正在转移到I/O。当在ImageNet 上大规模训练ResNet-50 时，高达85%的运行时间是I/O开销，在其他数据集上观察到了类似的趋势。随着计算能力趋势的不断改善，机器学习加速器和数据集达到数亿至数十亿[57]个样本和万亿至千兆个大小，这种I/O瓶颈只会加剧

• “I/O”：从存储中读取样本（Reads），对其进行预处理（Preprocess），其Collate中预处理本身可能需要多个阶段，例如解码图像、标记文本、标准化或数据扩充，最后将它们整理成小批量（Collate）进行训练。 这个过程中的任何一点停顿都会影响训练时间

  

• 挑战性&难点

  • 随机梯度下降(SGD)随机访问(通常是小的)数据样本
  • 对于分布式训练来说，因为 shared flesystem contention（共享文件系统争用）会对性能造成损害
  • 传统优化：现有框架经常将I/O与计算重叠，以减少其开销
    • 有限前瞻和双缓冲[1，23，68]、数据分片[30，50]、前置和内存缓存[40，67]或修改后的访问模式[78，79]。这些都有很大的局限性，包括可扩展性差、需要额外的硬件、忽略部分存储层次或偏离完整数据集随机化。所有这些方法都无法充分利用机器的输入/输出子系统

• 优化（主要思想）：具体分析/建模太复杂，略

  • 预取：DNN训练过程，深度神经网络几乎总是用mini-batch SGD或者变体来训练
    • 训练由许多epoch 组成，每个epoch 都是以不同的随机顺序在训练数据集上的完整传递
    • 组成给定小批量的样本是随机选择的，而不是从整个训练数据集中替换。这通常是通过为每个样本分配一个索引，在每个时期随机地对索引进行混洗，然后将混洗（shuffle）的索引划分为小批量来实现的。因此，一个给定的样本在每个epoch 中只被访问一次
    • 给定用于混洗索引的种子，无论混洗算法如何，我们都可以精确地复制混洗的结果，并因此预测访问模式。这些访问模式几乎适用于所有用小批量SGD训练的神经网络
  • 对于分布式训练，将上述访问模式分析和性能模型相结合，以提供适应不同数据集和存储层次结构的分布式缓存策略

• 优化：通过建模结合训练过程预取训练数据；NoPFS 系统：IO中间件

  

• 相关

  • tf.data: A Machine Learning Data Processing Framework
  • Scalable Deep Learning via I/O Analysis and Optimization
  • Tuning HDF5 for Lustre fle systems
  • Efcient memory disaggregation with Infniswap

论文3（内存墙）ZeRO-Infinity: Breaking the GPU Memory Wall for Extreme Scale Deep Learning

论文4（负载分析）Characterization and Prediction of Deep Learning Workloads in Large-Scale GPU Datacenters

• SC 2021，孙鹏，颜深根
• 开源 SenseTime 的GPU 数据中心的真实工作trace， DL 作业和资源管理的特征进行了全面的研究
• Implication #1: Both the cluster utilization and the job submission rate exhibit obvious daily patterns. This provides us opportunities to predict those behaviors in advance and then perform the optimal resource management and job scheduling
  • 集群利用率和作业提交率都呈现出明显的日常模式（有规律可循）， 这为我们提前预测这些行为提供了机会，然后执行最优的资源管理和作业调度
• Implication #2: For monthly trends, it is infeasible and unnecessary to predict the submissions of single-GPU jobs due to their weak impact on the cluster usage. In contrast, multi-GPU jobs exhibit more stable monthly patterns, and are critical to cluster utilization, which we can predict for better scheduling efciency
  • 从月度趋势来看，单个GPU作业提交量对集群使用影响较小，因此预测单个GPU作业提交量不可行，也没有必要。 相比之下，多GPU作业表现出更稳定的月模式，并且对集群利用率至关重要，我们可以预测集群利用率，以获得更好的调度效率
• Implication #3: Different groups submit DL jobs to their VCs with distinct GPU demands and duration. Hence, the imbalanced resource allocation across VCs can lead to low resource utilization and severe job queuing delay. It is critical to consider fairness when designing schedulers for shared clusters
  • 不同的组将DL作业提交给他们的VC（Virtual Clusters 虚拟集群），并具有不同的GPU需求和持续时间。 因此，VCs之间资源分配的不平衡会导致资源利用率低，作业排队延迟严重。 在为共享集群设计调度程序时，考虑公平性是至关重要的
• Implication #4: Despite the number of single-GPU jobs is predominant, GPU resources are mainly consumed by multi-GPU jobs. Hence, optimization of multi-GPU jobs is more important to improve cluster efciency. This characteristic resembles traditional HPC workloads and implies some optimization techniques in HPC can also be applied to GPU clusters
  • 虽然单GPU作业数量占主导地位，但GPU资源主要被多GPU作业占用。 因此，多GPU作业的优化对于提高集群效率尤为重要。 这种特性类似于传统的HPC工作负载，意味着HPC中的一些优化技术也可以应用于GPU集群
• Implication #5: Since many DL training jobs can reach the convergence earlier than expected, the scheduler can automatically detect this condition and stop the jobs for resource efciency. Users can use different metrics (e.g., loss, accuracy) and authorize the scheduler to monitor and manage their jobs
  • 由于许多DL训练作业能够比预期更早地达到收敛，调度程序可以自动检测这种情况并停止作业以提高资源效率。 用户可以使用不同的度量标准(例如，损失、准确性)，并授权调度程序监视和管理他们的作业
• Implication #6: A lot of failed jobs are for debugging purposes, and last for a very short time. However, they are mixed with the long-term production jobs in the queue and possibly suffer from much longer waiting time than execution. A possible solution is to allocate a special VC for debugging jobs and enforce a short-term limit (e.g., 2 minutes). This can help users obtain error messages timely and flter most failed jobs for normal clusters
  • 许多失败的作业都是出于调试目的，并且持续的时间很短。 但是，它们与队列中的长期生产作业混合在一起，因此等待时间可能比执行时间长得多。 一个可能的解决方案是为调试工作分配一个特殊的VC，并强制一个短期限制(例如，2分钟)。 这可以帮助用户及时获取错误消息，并为正常集群筛选大多数失败的作业
• Implication #7: To alleviate the problem of unfair cluster queuing, it is recommended that the scheduler should consider our user-level analysis to perform the corresponding optimization. For instance, the scheduler can dynamically adjust temporary priorities to users, especially to the marquee ones, based on their current job queuing statuses. The VC confguration can also be regulated appropriately according to users’ behaviors
  • 为了缓解集群排队不公平的问题，建议调度程序考虑我们的用户级分析来执行相应的优化。 例如，调度器可以根据用户当前的作业队列状态动态地调整临时优先级，特别是针对字幕用户。 VC的配置也可以根据用户的行为进行适当的调整

思考3（10/29）

• 厚积薄发 × 只为毕业 √

从毕设论文组织：

主题1：面向深度学习平台的存储系统性能优化研究

• 读性能优化：TridentKV: A Read-Optimized LSM-tree Based KV Store via Adaptive Indexing and Space-Efficient Partitioning
• 强化学习平台：？— 需要问题
• 问题？— 需要学习
  • 密歇根大学EECS 598: Systems for AI (W’21)

主题2：基于LSM-tree的键值存储性能优化研究

• 索引优化：TridentKV: A Read-Optimized LSM-tree Based KV Store via Adaptive Indexing and Space-Efficient Partitioning
• cache/filter优化：进行一些测试，寻找不同场景/负载下的瓶颈 —> 尝试阶段
  • 方向1：高效Cache for LSM-tree-based KV store
    • 拟定优化方向：1. cache效率低； 2. cache失效问题； 3. 多线程cache优化
    • Kangaroo，sosp’21
  • 方向2：高效范围查询 for LSM-tree-based KV store
    • 拟定优化方向：1. 支持范围查询的 learned index filter ；2. 大range范围：索引优化&异步I/O与预取；3. 结合负载
• 结合项目？— 需要思考

主题3：基于深度强化学习的分布式存储系统关键技术优化研究

• 学习索引：TridentKV: A Read-Optimized LSM-tree Based KV Store via Adaptive Indexing and Space-Efficient Partitioning
• 分布算法：RLRP: High-Efficient Data Placement with Reinforcement Learning for Modern Distributed Storage Systems
• 自动调参：ADSST: Automatic Distributed Storage System Tuning using Reinforcement Learning
  • https://github.com/tikv/auto-tikv and https://pingcap.com/zh/blog/autotikv
  • 分布式存储的自动调参？SAPPHIRE + RLRP
  • 难点：参数多（state空间）；很多参数非离散取值（action空间）
    • all_knob: 1384；rados_knobs: 933
  • 可做：SAPPHIRE 参数选择 + 测试环境及代码 + RLRP 算法框架

论文1：SAPPHIRE: Automatic Configuration Recommendation for Distributed Storage Systems

SOSP 2021

• 本年度SOSP有效投稿论文348篇，共接收论文54篇，涵盖BFT、找Bug、一致性、数据库、数据中心、Flash存储、图计算、机器学习、NVM、调度、安全、验证等18个议题。会议共持续四天，分为欧美和亚太两个镜像

• Flash存储

  • Kangaroo: Caching Billions of Tiny Objects on Flash Sara McAllister (Carnegie Mellon University), Benjamin Berg (Carnegie Mellon University), Julian Tutuncu-Macias (Carnegie Mellon University), Juncheng Yang (Carnegie Mellon University), Sathya Gunasekar (Facebook), Jimmy Lu (Facebook), Daniel Berger (University of Washington/ Microsoft Research), Nathan Beckmann (Carnegie Mellon University), Gregory R. Ganger (Carnegie Mellon University)

  • IODA: A Host/Device Co-Design for Strong Predictability Contract on Modern Flash Storage Huaicheng Li (University of Chicago and Carnegie Mellon University), Martin L. Putra (University of Chicago), Ronald Shi (University of Chicago), Xing Lin (NetApp), Gregory R. Ganger (Carnegie Mellon University), Haryadi S. Gunawi (University of Chicago)

  • FragPicker: A New Defragmentation Tool for Modern Storage Devices Jonggyu Park (Sungkyunkwan University), Young Ik Eom (Dept. of Electrical and Computer Engineering/College of Computing and Informatics, Sungkyunkwan University)

论文2（Flash Cache）：Kangaroo: Caching Billions of Tiny Objects on Flash

https://www.youtube.com/watch?v=bJ4rqSrcVqs

• 闪存芯片上缓存大量小文件的问题

• 背景

  • 小文件：许多主流的网络服务都需要快速、廉价地访问大量的小文件
  • 闪存：DRAM和NVM虽然速度很快，但其价格高昂，而相比之下闪存更为廉价，且其容量可扩展
  • Flash问题：写入次数存在限制，缓存系统需要关注写放大的问题以提升闪存寿命

• 针对闪存的缓存设计主要分为两类

  • 第一类为log-structured cache，通过顺序地将数据写到闪存上，可以减少写放大的发生，然而为了对数据建立索引，log-structured cache需要占用大量的DRAM
  • 第二类为set-associative cache，类似于CPU的高速缓存，数据存储的位置由其哈希决定，因此不需要占用大量的DRAM，然而这一设计的写放大问题比较明显。本文期望能同时减少DRAM的使用和对闪存的写入

• Kangaroo

  • 其采用了层级化的架构，将log-structured cache与set-associative cache结合。为了减少索引的DRAM开销，Kangaroo将缓存的绝大部分用于set-associative cache（称为KSet），同时，为了减少对闪存的写入，其在KSet前加入了一个较小的log-structured cache（称为KLog）。KLog暂存了许多对象，当出现大量会被映射到KSet中同一个set的对象时，这些对象会一次性地写入到KSet中，这极大地减少了所需的闪存写入次数。

  

  • 基于上述设计，Kangaroo提出了三个措施来减少DRAM使用和闪存写入并提升缓存命中率
    • 第一，KLog采用了partitioned index，其可以快速地寻找到KLog中所有映射到KSet中同一个集合的对象
    • 第二，数据从KLog向KSet移动时，其采用threshold admission策略，数据或是直接被丢弃，或是将大量属于同一KSet的元素同时从KLog移到KSet
    • 第三，KSet中采用的名为RRIParoo的数据驱逐策略可以通过使用极少的元信息来智能选择需要驱逐的数据，提升了缓存的命中率

####

论文2（SOSP）：Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3

https://www.youtube.com/watch?v=YdxvOPenjWI

论文3（SC）：Lunule: An Agile and Judicious Metadata Load Balancer for CephFS

• 先收集大量负载，测试

• 发现问题： Load imbalance phenomenon
• 解决方法：。。。

思考4（11/19）

• 学习

• 等IPDPS（175），DAC（885）的回复；两篇中一篇，就主题三毕业

• 主题二：ceph/kv 测试，读性能优化

  • 方向1：负载+NVMe
    • COSBench、UDB、ZippyDB、UP2X
    • 负载测试 ——费长红，没什么进展

  • 方向2：高效Cache for LSM-tree-based KV store

    • 主要问题：compaction导致cache失效，cache命中率，多线程cache低效
    • 拟定优化方向：1. cache效率低； 2. cache失效问题； 3. 多线程cache优化
    • 负载测试 ing

  • 方向3：高效范围查询 for LSM-tree-based KV store

    • 主要问题：范围查询低效，删除问题，filter和索引各存在问题
    • 拟定优化方向：1. 支持范围查询的 learned index filter ；2. 大range范围：索引优化&异步I/O与预取；3. 结合负载
    • 思考优化 ing

读优化

• 新trace，Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook（Fast’20）
• RocksDB Trace, Replay, Analyzer, and Workload Generation
  • Tracing：收集RocksDB的操作，主要记录操作类型，CF，key，value，时间戳
  • Trace Replaying：通过db_bench回放trace file
  • Trace Analyzing：分析workload，但是因为生产环境的workload涉及隐私不能公布，所以最终输出内容是一些描述，主要包括：1）每个CF（column family）内KV的操作次数，操作类型；2）KV size的统计数据；3）KV数据热度（Popularity）；4）key空间的局部性；5）QPS统计
  • Modeling and Benchmarking：对workload进行建模
• 负载
  • Get在UDB与ZippyDB中占比最多，UP2X最多的操作是Merge
    • UP2X大量服务于Read-Modify-Write（读后写）类型的请求，这种请求一般用于实现increment，checkAndSet等语义。典型的场景是做持久化的计数器，比如视频文章点赞数，银行卡余额等
    • UP2X: Facebook uses various AI/ML services to support social networks, and a huge number of dynamically changing data sets (e.g., the statistic counters of user activities) are used for AI/ML prediction and inferencing. UP2X is a distributed KV-store that was developed specifically to store this type of data as KV-pairs. As users use Facebook services, the KV- pairs in UP2X are frequently updated, such as when counters increase. If UP2X called Get before each Put to achieve a read- modify-write operation, it would have a high overhead due to the relatively slow speed of random Gets. UP2X leverages the RocksDB Merge interface to avoid Gets during the updates. KV-pairs in UP2X are divided into shards supported by RocksDB instances. Note that the KV-pairs inserted by Merge are cleaned during compaction via Compaction Filter, which uses custom logic to delete or modify KV-pairs in the background during compaction. Therefore, a large number of KV-pairs are removed from UP2X even though the delete operations (e.g., Delete, DeleteRange, and SingleDelete) are not used.
    • UP2X：Facebook 使用各种 AI/ML 服务来支持社交网络，大量动态变化的数据集（例如，用户活动的统计计数器）用于 AI/ML 预测和推理。随着用户使用 Facebook 服务，UP2X 中的 KV 对会经常更新，例如当计数器增加时。如果 UP2X 在每次 Put 之前调用 Get 来实现读-修改-写操作，由于随机 Get 的速度相对较慢，它会产生很高的开销。 UP2X 利用 RocksDB Merge 接口来避免更新期间的 Gets。UP2X 中的 KV-pairs 被划分为 RocksDB 实例支持的分片。Merge 插入的 KV 对在压缩期间通过 Compaction Filter 进行清理，该过滤器在压缩期间使用自定义逻辑在后台删除或修改 KV 对。因此，即使不使用删除操作（例如，Delete、DeleteRange 和 SingleDelete），也会从 UP2X 中删除大量 KV 对
  • UDB和ZippyDB中大部分KV数据是冷数据
  • UDB的部分CF表现出较强的昼夜模式，这跟社交网络用户习惯相关，ZippyDB和UP2X没有表现出这样的特征
  • key size通常比较小，value size的大小与具体数据类型有关，key size的标准差较小但是value size较大，UDB平均的value size比其他两个例子要大
• “mixgraph”的基准测试，它可以使用四组参数来生成合成工作负载，可自行生成想要的负载

./db_bench --benchmarks="mixgraph" \
  -use_direct_io_for_flush_and_compaction=true \
  -use_direct_reads=true \
  -cache_size=268435456 \
  -keyrange_dist_a=14.18 \
  -keyrange_dist_b=-2.917 \
  -keyrange_dist_c=0.0164 \
  -keyrange_dist_d=-0.08082 \
  -keyrange_num=30 \
  -value_k=0.2615 \
  -value_sigma=25.45 \
  -iter_k=2.517 \
  -iter_sigma=14.236 \
  -mix_get_ratio=0.85 \
  -mix_put_ratio=0.14 \
  -mix_seek_ratio=0.01 \
  -sine_mix_rate_interval_milliseconds=5000 \
  -sine_a=1000 \
  -sine_b=0.000073 \
  -sine_d=4500 \
  -perf_level=2 \
  -reads=420000000 \
  -num=50000000 \
  -key_size=48 \
  -db=/mnt/ssd \
  -compression_type=none

• 火焰图

perf record -p `pidof db_bench` -F 9999 -g -- sleep 60
perf script > out.perf 
./FlameGraph/stackcollapse-perf.pl out.perf > out.folded
./FlameGraph/flamegraph.pl out.folded > out.svg

范围查询

• 背景&&问题
  • 范围查询不友好—测试
  • 删除问题—测试
• 优化
  • 过滤器方法：不适合长范围查询场景 （Surf）— 学习
  • 索引方法：插入新数据时索引重构开销较大 （REMIX ）—学习

参考文献

1. 无锁B-tree：http://mysql.taobao.org/monthly/2018/11/01/
2. Bw-tree：https://15721.courses.cs.cmu.edu/spring2017/papers/08-oltpindexes2/bwtree-icde2013.pdf
3. Roofline: an insightful visual performance model for multicore architectures.
4. RocksDB Merge. https://zhuanlan.zhihu.com/p/235745224

基本战略：稳中求险

• 稳：以 KV读优化 和 自动调优 为当前主要目标 —> 测试阶段
  • 结合负载 + KV性能测试
    • RocksDB Trace, Replay, Analyzer, and Workload Generation
    • Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook
      • UDB：用于MySQL中用来存储社交图数据，使用RocksDB作为底层存储
      • ZippyDB：用于存储分布式对象存储的元数据的分布式KV
      • UP2X：用于存储AI/ML数据的分布式KV
  • ACSTS: Automatic Cloud Storage Tuning System using Reinforcement Learning
• 险1：Ceph测试，性能优化，寻找新瓶颈 —> 看项目发展
• 险2：了解强化学习和DI-engine，寻找问题和场景 —> 学习阶段
• 未知因素：trace收集？后续项目？
• NEXT：“稳“中出1~2篇文章；“险1”和“险2”出0~1篇文章