Database paper part 6

发表于 |

本部分开始为最新的学习笔记。包含 PolarDB Serverless、Monkey: Optimal Navigable Key-Value Store
。

PolarDB Serverless: A Cloud Native Database for Disaggregated Data Centers

https://users.cs.utah.edu/~lifeifei/papers/polardbserverless-sigmod21.pdf

INTRODUCTION

大概有三种 cloud 数据库的架构：

  1. monolithic
  2. virtual machine with remote disk
  3. shared storage

后两种也被统称为存算分离的架构。

存算一体的架构缺点：

  • 将 db 分配到对应的机器类似于解决 bin-packing 问题
  • 难以满足客户的灵活的资源需要
  • 资源之间没法独立地进行恢复

下面两种存算分离的架构：CPU 和内存同样存在 bin-packing 的问题，内存开销大。

因此 PolarDB Serverless 共享了内存。

和 Aurora、HyperScale 以及 PolarDB 一样，它有一个 RW 的主节点，以及多个 read only replica。它也可以通过提出的 disaggregation 架构支持多个 RW 主节点，但不在这个论文中讨论。

一些挑战：

  • 引入共享内存后，事务的正确性。
    • read after write 不会在节点间丢失修改 -> cache invalidation
    • RW 节点在 split 或者 merge 一个 B+Tree 的时候，其他的 RO 节点不能看到一个不一致的 B 树 -> global page latch
    • 不能脏读 -> 在不同的 database node 间同步 read view
  • 网络延迟
    • 使用 RDMA CAS 技术提优化 global latch 的获取
    • page materialization offloading 技术将 dirty page 从 remote memory 中驱逐，而不是将它们 flush 到存储中

BACKGROUND

PolarDB

介绍了 PolarFS。

RW 和 RO 节点通过 redo log 同步内存状态。通过 LSN 实现一致性，其执行流程是：

  1. 将所有的 redo log flush 到 PolarFS 中
  2. 提交事务
  3. RW 异步广播消息：read log 以及最新的 LSN 即 LSN_rw。
  4. 当 ROi 收到 RW 的消息后，从 PolarFS 上拉取所有的 redo log，将它们 apply 到 buffer pool 中的 buffered page 里面
  5. ROi 此时就和 RW 完成了已同步
  6. ROi 将自己的 LSN_ro 发送给 RW
  7. RW 可以在后台将 read log 去 truncate 到所有的 LSN_roi 的最小值
  8. ROi可以处理 LSN_roi 之前的读取，提供 SI 隔离级别

假设某个 ROk 落后了，比方说落后超过 1M，这样的节点会被发现，并且被踢出集群。

Disaggregated Data Centers

在 disaggregation 架构下，一个数据库实例所需要的计算、内存和存储资源将被分配到同一个 PoD 下面。不同的 db instance 则看见恶意分配到不同的 PoD 下面。计算和内存资源会被尽可能分配到同一个 ToR 下面。

一台机器有两个 RDMA NIC，他们会被连接到两个 ToR 交换机上面，从而避免网络连接失效。一个 leaf switch group 由多个 leaf switch 组成。ToR switch 连接到 leaf switch 上。

Serverless Databases

pay-as-you-go model。

一个 ACU 包含了 2GiB 的内存以及对应的虚拟处理器。这个设定 fixes the resource ratio。比如，分析数据库可能需要更多的内存，而不是 CPU，因为它们可能要 cache 大量的数据。对应的，事务数据库需要大量的 CPU 去处理业务的尖峰。而一个小内存，只要能满足 cache hit，那也是足够的了。

DESIGN

Disaggregated Memory

Remote Memory Access Interface

这里内存也是按照 Page 来组织的。一个 PageID 可以表示为 (space, page_no)。使用 page_register 和 page_unregister 去做类似 RC 一样的内存管理。page_read 从 remote memory pool 拉数据到 local cache。page_write 将 page 从 local cache 写到 remote memory pool。page_invalidate 被 RW 调用，用来将所有 RO 的 local cache 上的 page 设置为无效。

Remote Memory Management

内存分配的单位是 slab，一个 slab 是 1Gb。

Page Array(PA)

一个 slab 被一个 PA 结构实现。一个 PA 是一个连续的内存，包含 16KB page 的 array。PA 中的 page 可以被 remote node 通过 RDMA 直接访问，因为他们在启动的时候就已经被注册到 RDMA NIC 上了。

一个 memory node 也被称为一个 slab node。一个 slab node 管理多个 slab。一个实例可以对应到多个 slab node 上，其中第一个 slab node 称为 home node。home node 中有一些 instance 级别的元数据。

Page Address Table (PAT)

PAT is a hash table that records the location (slab node id and physical memory address) and reference count of each page. 也就是前面 page_register 和 page_unregister 所操作的东西。

【Q】这个结构保存在哪里？

Page Invalidation Bitmap (PIB)

PIB is a bitmap. For each entry in the PAT table, there is an invalidation bit in PIB. Value 0 indicates that the copy of the page in the memory pool is of the latest version, while value 1 means that the RW node has updated the page in its local cache and haven’t written it back to the remote memory pool yet. There is also a local PIB on each RO node, indicating whether each page in the RO node’s local cache is outdated.

Page Materialization Offloading

Aurora 提出 log is database 的理论。将 redo log 看做是增量的 page 修改。Socrates 进一步地，将 log 从 storage 分离。Log 被存在 XLOG 服务中，然后被异步地发送到一系列 page server 中，每一个 page server 负责一个 database partition，独立地重放日志，生成 page 并处理 GetPage@LSN 请求。

PolarDB 类似于 Socrates，将 PolarFS 设计为分别存放 log 和 page 到两个 chunck 中。redo log 首先被持久化到 log chunkc 中，然后被异步地发送到 page chunck 中。在 page chunck 中，logs 被 apply，从而更新 page。不同于 Socrates，为了重用 PolarFS，log 只会被发送到 page chunk 的 leader 节点，这个节点会物化 page，然后将 update 通过 ParallelRaft 通知给其他的 replica。This method adds additional latency to the ApplyLog operation due to the replication cost. However, it is not a critical issue because ApplyLog is an asynchronous operation not in the critical path. Moreover, since the replicated state machine guarantees data consistency between page chunks, there is no need for an extra gossip protocol among storage nodes like in Aurora.

Monkey: Optimal Navigable Key-Value Store

https://nivdayan.github.io/monkeykeyvaluestore.pdf

个人觉得一篇很好的文章，介绍了 LSM 的 design space。

Abstract

Bloom filter 的 FP 率，和最坏情况下的查询开销成正比。

The insight is that worst-case lookup cost is proportional to the sum of the false positive rates of the Bloom filters across all levels of the LSM-tree.

对于不同的层，引入不同的 bloomfilter 的大小。

Monkey allocates memory to filters across different levels so as to minimize this sum.

设计了一个调优工具。感觉类似 《Fast Scans on Key-Value Stores》里面的思路。

Furthermore, we map the LSM-tree design space onto a closed-form model that enables co-tuning the merge policy, the buffer size and the filters’ false positive rates to trade among lookup cost, update cost and/or main memory, depending on the workload (proportion oflookups and updates), the dataset (number and size of entries), and the underlying hardware (main memory available, disk vs. flash). We show how to use this model to answer what-if design questions about how changes in environmental parameters impact performance and how to adapt the various LSM-tree design elements accordingly.

INTRODUCTION

The intuition is that any given amount of main memory allocated to Bloom filters of larger runs brings only a relatively minor benefit in terms of how much it can decrease their false positive rates (to save I/Os). On the contrary, the same amount of memory can have a higher impact in reducing the false positive rate for smaller runs.

调研 Pareto curve 基于内存容量和工作负载，去寻找到查询和更新开销的平衡点。

The second key point in Monkey is navigating the Pareto curve to find the optimal balance between lookup cost and update cost under a given main memory budget and application workload (lookup over update ratio).

BACKGROUND

Buffering Updates

首先是下面这张图。

$M_{buffer}$ 等于 $ P \times B \ times E$。E 是 entry 的大小，B 是一个 disk page 中有多少个 entry，P 是内存中有多少个 disk page 用于 buffer。

$ N \times \frac{T-1}{T} $ 是怎么来的呢？其实是个等比数列求和

1
1 + T + T^2 + ... + T^(L-1) + T^L = N

套一下公式，然后取 T^L-1 直接约等于 T^L，即可得到结果。

然后，得到另一个 L 关于 T 的公式。

其中，T 是有一个上限的取值，即 $ \frac{N \times E}{M_{buffer}} $。取这个上限时，L 会退化到 1。因为整个数据库才 $ N \times E $ 这么大，挨个按照 tiered 逻辑 dump 下来就是公式这么多个，然后 T 等于它，那么这一层永远将将好填满。

Merge Operations

The essential difference is that a leveled LSM-tree merges runs more greedily and therefore gives a tighter bound on the overall number of runs that a lookup has to probe, but this comes at the expense of a higher amortized update cost.

Lookups

查询从 buffer 开始，从低层往高层走。一旦找到第一个满足要求的就可以立即返回，因为层数越往下，数据是越旧的。

A point lookup starts from the buffer and traverses the levels from lowest to highest (and the runs within those levels from youngest to oldest in the case of tiering). When it finds the first matching entry it terminates. There is no need to look further because entries with the same key at older runs are superseded.

  • 查找一个不存在的值代价可能很高，因为会检查所有 level 中的所有 run
  • 范围查询需要 sort merge 一系列 run，然后丢掉被 override 掉的数据

Probing a Run

在 1996 年最老的 LSM 设计中，每个 run 是被存储为压缩的 B 树的。

Over the past two decades, however, main memory has become cheaper, so modern designs simply store an array of fence pointers in main memory with min/max information for every disk page of every run.
Maintaining a flat array structure is much simpler and leads to good search performance in memory (binary search as each run is sorted).

查询的时候，

  • 如果是点查，那么就先二分 fencing pointers，然后找到对应的 page
  • 如果是扫表，也还是二分到对应的 page，然后从这个 page 往后读取

所以，如果只需要 O(1) 的 disk IO，那么 pointers 的内存大概是 O(N / B)。

For example, with 16 KB disk pages and 4 byte pointers, the fence pointers are smaller by ≈ 4 orders of magnitude than the raw data size. Stated formally, we denote the amount of main memory occupied by the fence pointers as $M_{pointers}$, and we assume throughout this work that $M_{pointers}$ is O(N / B) thereby guaranteeing that probing a run takes O(1) disk I/O for point lookups.

Bloom Filters

FPR 即假阳性率，和 entry 的数量正相关，和 bloom filter 的内存占用负相关。如下面公式所示

因为如果出现假阳性，则需要去下一个 sst 文件（tiered）或者下一层（leveled）中去找下一个 run。因此假阳性率实际上就关系到找一个 key 要有多少次 disk IO，从而直接影响到性能。

Rocksdb 中普遍使用 10 bits 给 Bloomfilter，则假阳性率在 1%。

Cost Analysis

如何度量最坏情况呢？

  • 对于 update，度量 amortized worst-case I/O cost，主要和 update 之后的 merge 操作有关
  • 对于 lookup，度量 zero-result average worst-case I/O cost。原因是它很常见，并且它的 IO overhead 确实很大

对于最坏情况：

  • Tierd
    • Lookup 的 IO 正比于 L、T、FPR 三者乘积
    • Update 的 IO 正比于 L / B
  • Leveled
    • Lookup 的 IO 正比于 L、FPR 二者乘积
    • Update 的 IO 正比于 T * L / B

LSM-TREE DESIGN SPACE

The design space of LSM trees spans everything between a write-optimized log to a read-optimized sorted array.

Design space contentions

Figure 4

  1. 如何将总共 $M_{filters}$ 这么多内存分配给所有的 Bloomfilter？
  2. 如何在 buffer 和 filter 之间分配内存？
    例如，根据 Figure 4，如果分配在 buffer 上的内存变多，那么 lookup 和 update 的 cost 就会变低，但是会同时提高 Bloomfilter 的 FP 率，从而又实际上提高了 lookup 的 cost。
  3. 如何调节 size ratio 也就是 T 和 merge policy？

MONKEY