[VLDB-2022] SA-LSM: Optimize Data Layout for LSM-tree Based Storage using Survival Analysis

概要

生存分析(Survival Analysis) 是一种生物统计学中常用的模型,SA-LSM 基于这一模型,用历史 Workload 预测数据的冷热程度,进而指导 LSM-tree compaction 策略。

文章主要有三个贡献点:

  • 针对多类型存储设备共存的存储环境下的 LSM-tree,在数据粒度和 compaction 算法上进行了重新设计。
  • 基于生存分析算法设计了 SA-LSM,将数据访问看作一个 ‘time-to-event’ 的预测问题。
  • 设计了一个轻量级通信协议,让 SA-LSM 服务和数据库内核通信,以 External Service 的形式指导数据库内核识别冷热数据并进行主动式 compaction(Proactive Compaction)。

传统 LSM-tree 冷热数据识别算法的问题

LSM-tree 可以认为是一种分层存储的结构,数据在 memtable 中写满后刷入磁盘的 L0 层中。传统的 compaction 算法为每一层数据量设置了一个阈值,L0 层达到阈值后将其中的数据进行多路归并排序后写入 L1 层,依此类推。

冷热数据识别是个历久弥新的话题。比如缓存替换策略就需要识别出冷数据进行替换,最经典的 LRU 算法认为距今最久的访问数据是冷数据。这在缓存替换中固然是一种有效的方法,但它不能有效利用 LSM-tree 海量 Workload 中的各类信息对数据冷热进行推断,因此将 LRU 一类的替换算法应用在 LSM-tree 冷热分层上不是个很好的想法。

AWPI Workload

archival write and point read intensive (AWPI) 是 LSM-tree 非常常用的一类 workload,简而言之就是越早 insert 的数据一般来说被访问到的概率越低,并且查询主要以 OLTP 的点查为主。如图,logistics 负载中差不多 15% 的访问数据都是当日被插入的数据。

Survival Analysis 与 LSM-tree 的结合

本文工作是在 X-Engine(RocksDB 4 的一个 fork 版本) 上做的。

生存分析是医学上常用的一种统计学方法。打个比方,医生想了解某种手术对于不同特征的人的风险,那么医生就每隔一段时间对术后患者进行回访,绘制不同特征患者的生存率折线图(K-M 图表),并用一些统计学模型(Cox Model, Random Survival Forest 等)对采集的数据进行拟合,得到不同特征人群的术后生存时间期望。

关于生存分析的详细信息可以参考:生存分析 简明教程

特征提取

首先需要采集数据特征和标签来训练我们的生存模型。本文针对每条数据将 AWPI workload 拆分为了两个阶段:

  1. Feature Selection Phase
  2. Labeling Phase

第一阶段用于采集数据特征,第二阶段用于给数据打标签。

SA-LSM 首先通过随机选取 pivot 分割这两个阶段。由于不同操作之间的时间间隔不一样,因此简单地在 workload 选取任意时间点作为 pivot 不是很公平。SA-LSM 提出了一种简单的两阶段 pivot 选取办法,它把两个操作之间的间隔看作一个窗口,随机选取任意窗口后再在窗口上随机选取一个时间点。

Feature Selection 阶段主要提取两类 feature。第一类是时序上的访问特征,比如插入时间和 pivot 的时间间隔等;第二类主要是语义特征,比如该数据对应的列在过去 20 天有多少次 Select 和 Update 操作等。

Label Generation 主要标记下一次访问和 pivot 的时间间隔。由于简单地把下一次访问的时间间隔作为标签会引入大量噪声,因此本文定义了 \(\tau\) event 的 access time interval 作为真正的数据标签。\(\tau\) event 设置了一个阈值 \(\tau\),排除了 access time interval 小于该阈值的访问。

生存模型实现

关于它怎么实现的用机器学习模型来预测这部分我看得很费力,后来发现它其实就是基本照搬了 Random Survival Forest 这篇文章对它自己模型的描述,并且缺少了 RSF 文章里一些介绍公式由来之类的上下文。。

相比特征提取这块,模型实现上感觉本文基本没什么贡献。

工程实现

SA-LSM 非侵入式的设计也是本文一大贡献点。在 PolarDB 中,用户通过 DDL 开启 SA-LSM 的开关。开启后,Enternal Service 不断获取 DB 中的 metadata,并判定当前的 Workload 是否属于 AWPI Workload,如果是的话则使用使用特征工程和生存模型识别 Cold Keys,告知 DB 并进行主动式的 Compaction,将 Cold Key 合并入冷存设备中。

实验结果

主要是两方面的评估,一方面是生存模型的离线评估;一方面是数据库线上吞吐量和尾延时的评估。从模型精度来说,RSF 相对 GBDT 和传统的 Cox 生存模型都有一定优势。而在冷热数据判定的召回率上,RSF 相对传统算法的优势就非常大了。

整体来说 SA-LSM 对降低尾延迟有很大帮助。但部分 workload 下整体吞吐变化不是很大,可能是这些 workload 中很多数据不符合 AWPI Workload 的判定。由于文末比较的 Workload 数量比较多,因此这里只放一张图,有兴趣可以去原文中看。

标签:

更新时间: