[ASPLOS2020] Hailstorm: Disaggregated Compute and Storage for Distributed LSM-based Databases 笔记

最近专攻存算分离和DB On K8s方向，因此读一些相关的论文，做一些笔记

shared-nothing架构下的LSM-based 数据库在吞吐量和延迟之间的瓶颈主要在：

1. 不同分片数据不均衡，某些热点数据处理压力大
2. 后台进行flush/compaction或者数据迁移时产生的抖动

Hailstorm通过存算分离，存储层使用分布式文件系统实现存储的池化和compaction offloading(任务调度迁移）

存算分离意味着不再需要进行分片的resharding，并且通过把compaction等io-intensive的任务从高负载机器分发到低负载机器，而不是只能在计算存储耦合的节点上进行，可以大大舒缓吞吐量/响应时间的压力。

Introduction

工业界很多分布式的数据库都以RocksDB这种LSM-based的KV store作为底层存储，在MPP架构下会造成许多不确定的性能抖动和资源利用率的浪费，主要有以下两个原因：

1. 数据倾斜导致CPU和IO的不均衡。MPP数据库解决数据倾斜的方法就是定期做resharding；问题是resharding涉及到批量数据迁移，同样会带来巨大的CPU和IO开销，迁移过程中还会影响读写过程，影响用户线上功能；

2.flushing/compaction造成IO和CPU的抖动；尤其是在涉及到多个node的range query中抖动影响更严重。

在shared-nothing的mpp数据库下，由于存储计算资源不共享，各个节点无法得知各自的资源利用情况和后台任务执行情况，因此在CPU/IO/和存储利用率经常会遇到不均衡的情况。

本文提出了Hailstorm这一轻量级的分布式文件系统，部署在每一个节点的存储层下；致力于解决一上提出的问题。

核心思想是通过存储的池化，在rack（理解为disk的机架，存储资源池化的基本单元）内，各个分片的下的数据以small block（1MB）统一组织在HailStorm中。换句话说就是做了一层shared-storage，来消除数据倾斜和单机disk的瓶颈。SnowFlake的做法就是直接把文件丢到Object Storage中，同样划分为small block来做池化。而本文使用文件存储而非对象存储进行池化，有什么好处呢？

这里粒度大小的选择很关键，本系统是1MB，而Snowflake貌似是平均在16MB，粒度大小对network 传输的性能会有比较大的影响，文件越大，io的latency也会越大。

和Snowflake相似，为了舒缓单机cpu的压力，会有类似work-stealing机制把部分compaction task迁移到cpu利用率比较低的机子上，从而实现更加balance的整体cpu利用率。

HailStorm Design

我理解Hailstorm有点像FUSE，对计算节点的storage engine提供FS client接口，对storage device提供server接口进行所有devices的池化；而且client和server独立部署通过network传输数据；这样一来本在storage engine层进行的compaction/flushing外包到Hailstorm进行；同时所有shard下的storage devices统一池化在hailstorm层，消除了数据倾斜。

HailStorm Agent类似于一个compaction/flush任务的scheduler，把io/cpu intensive的task分发到利用率比较低的节点上。

总结一下Hailstorm的设计理念：

1.资源解耦合

计算/存储资源的解耦合，使得独立的扩缩容和负载均衡成为可能。

2.存储池化

在各shard下的storage engine引入一层shared-storage的存储层进行池化，分摊了io开销和消除io热点。

3.合适粒度的数据分布

把数据划分为small block并且均匀分布在所有的storage device；消除了io热点和单个shard上disk容量瓶颈；

4.Compaction/flush任务的均衡调度

Hailstorm提供task调度功能，将compaction/flush任务根据io/cpu负载在不同分片中进行调度

文件系统架构

HailStorm提供POSIX接口，属于经典的CS架构；单点的client能够访问rack内全局数据，意味着单个shard的数据能够分布在所有的storage device。

为什么用文件系统？

1. 主要原因是：storage engine中对compaction/flushing是对文件进行操作的，使用文件系统保留文件语义，能够最少地修改相关的代码；例如在进行compaction任务调度的时候，我们需要感知到sstables文件信息
2. 同时文件系统也提供如mmap()等存储引擎常用的内存映射方法

为什么不用现有的分布式文件系统？

1. Hailstorm是专门用于LSM KV优化的文件系统，消除了许多不必要的功能，如消除了中心化的metadata management；并且block size比一般的分布式文件系统更小，以降低IO latency;而且LSM KV本身有保持一致性的journaling机制（wal）;所以文件系统层就不需要实现
2. Hailstorm对顺序查询做了读取优化；对compaction进行pre-fetch优化；page-cache 缓存数据；wal保存在本地盘而不是hailstorm来加速崩溃的恢复

存储层架构&细节

元数据存储

每个文件通过全局唯一的uuid来识别；

每个文件的block顺序存储，方便定位

每个hailstorm client存储着文件路径和uuid的映射；

同时如size，timestamp，permission等metadata也是存储在本地。

存算分离架构性能瓶颈主要在network的开销；

读取比写入时，block的粒度会更小，来减少传输的latency和读放大；而写入时compaction/flush操作则使用默认的block粒度来保证写入性能。

分布式数据库通过跨机器/跨机架/跨AZ/跨数据中心的备份来保持高可用；

LSM用WAL实现崩溃恢复保证数据一致性；

rack内部，为了避免单点disk故障导致rack内所有shard不可用，磁盘级别则使用RAID保证冗余；

文件的metadata存储在本地；需要额外做复制保证高可用

计算层架构&细节

存储的池化用于舒缓单机存储压力；而计算层的compaction offloading用于减缓cpu load;

Compaction Mechanism

Hailstorm会在每个client和DB instance部署一个轻量级的agent，用于检测资源的使用情况；如果agent认为某个db instance上cpu/io过载；会暂停当前task的线程并且尝试把task交给负载更低的机器运行；

agent会把compaction的一些细节信息如对哪些sstable文件进行compaction告知给将要执行task的节点；因为compaction不涉及对文件的原地修改，因此交互不需要涉及同步；代理节点完成compaction操作后，代理节点的agent把新生成的sstable信息/metadata告知会原来节点的agent；原来节点会重新得到这些新合并生成文件的ownership。

整个系统的cpu和memory的瓶颈从各个db instance转移到hailstorm上。

果不其然，Hailstorm是用FUSE来实现的；但是FUSE涉及到用户态内核态的复杂交互；意味着读取性能肯定会受到一定影响。替代方案有Parallel NFS；为了方便用ext4文件系统存储本地的block数据。

至于IO粒度的选择，论文发现100KB-4MB的block-size性能相近；采用1MB是在性能和远程访问延迟上做了平衡。太小了的话影响随机写性能，并且会增加FUSE中内核态用户态切换次数；太大了会影响网络传输延迟；而在client read时候的block大小选择了64KB。

略；看论文

HailStorm借助FUSE实现了一个文件系统接口；通过统一存储设备进行资源池化和后台compaction任务的动态调度进行存储计算分离，来消除数据分布不均衡和IO/CPU抖动的影响。

但是论文只实现了单rack内的池化；没有实现rack之间的池化；并且FUSE频繁的内核台用户态切换必定会造成性能不佳。并且没有实现计算资源的弹性伸缩，只是通过调度来解决workload imbalance问题。