mrdrivingduck / paper-outline

🔍 To record the papers I have read.
24 stars 0 forks source link

Are You Sure You Want to Use MMAP in Your Database Management System? #10

Open mrdrivingduck opened 2 years ago

mrdrivingduck commented 2 years ago

p13-crotty.pdf

mrdrivingduck commented 2 years ago

遵循对一个东西开喷就要讲清楚理由的原则,Andy Pavlo 把他在网课里随口说的 I hate mmap 变成了一篇完整的论文。甚至还在页眉上做了点文章: 🤣

image

Memory-mapped (mmap) 文件 I/O 是一个 OS 提供的特性,可以让用户空间的程序用指针像读写内存一样读写文件,即使文件无法在内存中装下。POSIX mmap 系统调用可以将一个文件映射到进程的虚拟地址空间中,并在进程读写文件时按需加载页面。由 OS 透明地管理页面的 load 和 evict,从进程的视角来看只有指针(内存)操作。

传统的 DBMS(这里特指 larger-than-memory 的 DBMS)使用 read/write 系统调用实现 buffer pool,将页面从外部存储中装入用户空间的 buffer 里。DBMS 对何时换出页面具有 100% 的控制权。

那么对于 DBMS 来说,有了 mmap 是否就可以无需实现复杂的 buffer pool 了呢?是否可以将页面的读取和换出的控制权交给 OS 呢?本文从 正确性性能 的角度详细说明了 DBMS 使用 mmap 所带来的代价和要额外解决的问题,并认为解决这些问题所带来的工程量违背了使用 mmap 减少工程量的初衷。因此本文将 mmap 和 DBMS 比作 coffee 和 spicy food——它俩结合在一起挺蛋疼。

mrdrivingduck commented 2 years ago

Background

MMAP Overview

使用 mmap 访问文件的步骤:

  1. 程序调用 mmap,获得一个指向映射文件内容的指针
  2. OS 在进程虚拟地址空间保留一部分用作映射,但不装载文件的任何部分进内存
  3. 程序使用指针访问文件内容
  4. OS 试图获取页面
  5. 映射缺失引发 page fault,OS 将页面调入物理内存
  6. OS 在页表中加入虚拟内存到物理内存的映射条目
  7. CPU 将这个页表条目缓存在本地 TLB 中

当程序访问其它页面并需要将当前页面换出时,OS 需要从内存页表和 每个 CPU 的 TLB 中移除映射项。对 CPU 本地的 TLB 进行刷新是很快的,但 OS 必须使用代价昂贵的跨处理器通信使其它 CPU core 的 TLB 失效。这个问题被称为 TLB shootdown,将会带来性能问题。

POSIX API

MMAP Gone Wrong

现实中的 DBMS 对 mmap 从使用到放弃的实例 😂...喷了一通

mrdrivingduck commented 2 years ago

Problems With MMAP

本章详细说明了 mmap 替换 DBMS buffer pool 之后会引发的问题,以及解决这些问题所需要付出的代价。

Problem 1: Transactional Safety

事务是 DBMS 对文件把控最重要最复杂的环节。由于 DBMS 通过 mmap 把页面在内存与磁盘间同步的权利下放给 OS,那么 OS 可以在任何时间将脏页刷进磁盘,而 DBMS 不会收到任何通知。那么 DBMS 就没法知道一个页面有没有真正进入磁盘。这对事务的回滚、提交来说是致命的。

因此,使用 mmap 的 DBMS 必须实现复杂的协议来保证透明的页面管理不会违反事务正确性。已有的处理方式有如下几种。

OS Copy-On-Write (MongoDB MMAPv1 storage engine)

使用 mmap 得到数据库文件的两个指针,初始状态下指向相同的物理页:

在页面更新时,DBMS 使用私人工作空间指针修改页面,将引发 OS 透明地将物理页拷贝、remap 私人工作空间到新页、在新页上应用更改。此时主拷贝上没有任何更新,因此更新不会被刷入磁盘。为保证持久性,OS 必须使用 WAL,保证事务提交后 WAL 记录被刷入磁盘。然后后台线程逐步将提交后的修改页面逐步应用到主拷贝上,从而最终被刷入文件。

如果事务提交后,主拷贝中的更改还没有被刷入磁盘,那么通过 WAL 记录还是可以恢复到事务提交后的状态。

存在的问题:

User Space Copy-On-Write (SQLite / MonetDB / RavenDB)

手动把要更新的页面从 mmap 的内存拷贝到一个独立维护的用户空间 buffer 中,然后 DBMS 只对这个副本做 apply,并确保 WAL 刷入磁盘。WAL 输入磁盘后,才可以安全地将用户空间 buffer 中的修改页复制回 mmap 的内存中,然后随便 OS 什么时候把脏页刷回磁盘了,反正有了 WAL 日志,可以把提交的事务恢复出来。

对页面中的小改动来说,直接拷贝整个页面比较浪费。所以一些 DBMS 也支持直接对 mmap 内存应用 WAL 记录中的更改。

Shadow Paging

DBMS 维护两个 mmap 后的文件:

DBMS 实现将要更改的页面从主文件复制到 shadow copy 文件中,然后 apply changes。事务提交的操作包含用 msync 强制把更改刷进磁盘,然后把主文件指针指向 shadow copy;原先的主文件成为了 shadow copy。

问题:DBMS 需要保证事务不会冲突或没有 部分更新 问题。

Problem 2: I/O Stalls

传统 buffer pool 通过异步 I/O 使查询执行的线程不会被阻塞,但 mmap 不支持异步读。

由于 OS 透明地调入和换出页面,只读查询可能会被随时暂停,因为 DBMS 不知道要访问的页面是否在内存中。为解决这个问题,开发者使用 mlock 来 pin 住内存中的页面,不让 OS 把它换出,但:

一种可行的解决方法是通过 madvise 向 OS 提供 I/O pattern 的提示。但是提示终究只是提示,OS 有忽视提示的自由;并且向 OS 提供了错误的提示将会极大影响性能(比如对随机访问提供了 MADV_SEQUENTIAL 的提示)。

Problem 3: Error Handling

从磁盘中读取页面时,DBMS 一般会对页面的 check 做验证。当使用 mmap 时,DBMS 需要在每一次访问页面时都验证页面的 checksum,因为 OS 可能已经将页面换出又调入了(DBMS 不知道)。

类似地,传统 buffer pool 在将页面刷进磁盘之前也会对页面中是否有错误进行检验,而 mmap 会将 corrupted 的页面默默刷回磁盘。

优雅处理 I/O 错误也会变得更加困难。

Problem 4: Performance Issues

除非 OS 级别能够重新设计,否则 mmap 对 DBMS 来说有严重瓶颈。理论上 mmap 避免了两方面的开销:

  1. 避免了调用 read/write 的系统调用开销,因为 OS 透明完成了所有工作
  2. mmap 直接返回了指向 OS page cache 的指针,避免了在用户空间中开辟一段 buffer 缓存页面,总体内存使用量降低

然而本文发现了 mmap 的三个致命瓶颈:

  1. 页表争抢
  2. OS 的页面淘汰机制无法在多线程场景下扩展
  3. TLB shootdowns:使其它 CPU core 的 TLB 失效需要大量 CPU 周期,暂时无法解决

前两点或许可以在 OS 层面部分解决。

mrdrivingduck commented 2 years ago

Experimental Analysis

对比:使用 fio 存储跑分工具,运行几个常见的 I/O pattern

Random Reads

Mmap 就算使用了符合 I/O pattern 的 hint,性能也较差。性能下降始于 page cache 被填满,OS 开始淘汰页面时。页面淘汰的三个开销在于:

  1. TLB shootdowns,跨 CPU core 通信
  2. OS 使用一个单进程进行页面淘汰
  3. OS 必须对 page table 进行同步,多线程场景下将会有大量碰撞

Sequential Scan

Mmap 在 page cache 被填满后性能下降,并且无法利用多 SSD RAID 的 I/O 带宽。