Efficient Memory-Mapped I/O on Fast Storage Device

0x00 引言

这篇Paper是关于Memory-Mapped I/O 即使用mmap来实现IO操作的早快速存储设备上面的优化。mmio的一些特别的地方就是虚拟地址空间和io之间的关系。mmio中在需要的时候需要进行释放一些memory page的操作，or 将dirty page写入磁盘。这个和Database的Buffer Pool有一些类似。这篇Paper主要设计到这两个的操作的优化，

 Experimental results show that our optimized mmio has up to 7x better performance than the original mmio. We also compare our system to a system that has enough memory to keep all data in the main memory. The system with insufficient memory and our mmio achieves 92% performance of the resource-rich system.

0x01 基本思路

mmio中，在系统分配free page失败 or到达其它的一些出发条件下，需要进行page reclamation的操作。如果对应的Page是Dirty的，则需要将这个Page写入磁盘对应的位置。另外这里需要将对应的进行置于等待的状态，会有上下文切换的操作。在HDD的环境中，由于磁盘操作很高的延迟，这里带来的开销都是可以忽略的。但是在高速的存储介质下面，这些操作的开销也显得比较明显，需要进行优化。

• 在需要回收进行的一些Memory Page的时候，有这样的一些策略，Clean-Only Recycling (COR)，即只会回收Clean的Page，这些就不需要进行写回操作了。直接讲回收的Page重新映射到虚拟地址空间对应的位置就可以了。缺点是在一些写负载比较高的workload中，Dirty Page比较多，Clean Page少。性能比较差。Full Recycling (FR)，为了优化COR策略在写负载高的Workload中的问题，这里会回收Dirty Page，进行写回操作。这里没有什么特别的？区别在与而是这里直接写回？

• 这里写回的话带来另外一个问题，就是可能的多个写操作的请求，可能是由于这些Page对应的位置处于不同的地方。这里的优化方式是使用vectored I/O (or scatter/gather I/O)。实际上估计类似于readv/writev的操作。这里另外一个优化是对Block层请求对象bio的一个优化，基本的思路如下图，

  

  这里另外的一个优化是多核环境下的一个优化，回收之后的Pag会被添加到一个全局的Free List中。但是在多核的环境下吗可能会带来比较大的竞争。这里的思路就是使用每个核心一个list的方式。也没有特别的，在内核中也是一种非常常见的优化思路。

0x02 评估

这里的具体信息可以参看[1].

Failure-Atomic msync(): A Simple and Efficient Mechanism for Preserving the Integrity of Durable Data

0x10 引言

这篇paper描述的是如何实现一个 Failure-Atomic的msync()操作。目前msync()的系统调用不是原子的，也就是说如何msync()设计到多个Page写回到磁盘的时候，可能在发生故障的情况下，系统会处于中中间的状态。这篇Paper就使用JDB2实现一个Failure-Atomic的msync()。

0x11 基本思路

为了表明一个mmio需要Failure-Atomic的msync()。这里为mmap添加了一个MAP_ATOMIC的flag。在调用msync的时候，使用msync(MS_SYNC)的方式。整体上还是兼容了之前的mmap相关的接口。这里的主要改动涉及到这样的一些，1. 只有在用户主动调用msync的时候，才会进行dirty page刷盘的操作。避免之前的刷盘机制刷一部分导致不满足这里的语义。2. 必须满足msync的时候，满足原子性的语义。满足第一点思路上没有什么特别的。不过要对内核中的相关机制进行修改，会导致一个什么样的结果，会不会导致系统其它的一些异常的行为不是很清楚。对于第二点，使用的是基于journaling的机制。ext4文件系统就依赖于一个日志组件JBD2。这里的实现也利用了JDB2。内容被写入到日志中后，实际更新文件可以在后面操作，

  In our implementation, failure-atomic msync() collects the set of dirty pages at an msync() call and encapsulates them into a single handle — the unit of failure-atomic I/O guaranteed by the journaling JBD2 layer. JBD2 is capable of providing atomic transaction guarantees via a checksummed journal entry, so failures during an atomic msync() will merely result in an incomplete journal entry which will be discarded.

• 在ext4中已经存在的相关函数中，ext4 writepages()和ext4 writepage()，前者可以一次写入多个Page，但是需要这些Page是连续了。所以对于不连续的情况，需要使用ext4 writepage。但是这里的原子性保证只能在一个调用之内，所以这样的会有一部分写入而另外的一部分没有写入的情况，所以需要另外的方式处理。
• 这里将已经写入Redo Log的Dirty Page称之为journaled dirty page。没有写入的称之为file system-layer diry page。现在的系统设计中是没有考虑到这里的不同的，写入到时候也就没有考虑到这个。这样可能导致一些性能的问题，特别是在频繁调用msync的时候。而这里使用的思路是将file system-layer diry page优先处理，而journaled dirty page可以延迟处理。
• 这里还讨论了这样的方式给系统内存带来更大的压力的问题，以及可能的在被映射的memory page被交换出去的处理方式。另外还在此基础之上实现了一个Key Value Store[2].

0x12 评估

这里的具体信息可以参看[2].

Unified Address Translation for Memory-Mapped SSDs with FlashMap

0x20 引言

这篇paper讨论的是Memory-Mapped File在SSD上面的优化。Memory-Mapped File在现在的系统上面，映射到最终的SSD上面的存储空间会经过进程的Page Table，之后再经过文件系统层，最终是SSD的FTL层。多层的间接会对性能有诸多的不利影响。这里的思路就是去掉这些间接层，Memory-Mapped File直接映射到SSD的NAND Flash上面，基本思路如下图所示，

By combining these layers, FlashMap reduces critical-path latency and improves DRAM caching efficiency. We find that this increases performance for applications by up to 3.32x compared to state-of-the-art SSD file-mapping mechanisms. Additionally, latency of SSD accesses reduces by up to 53.2%.

0x21 基本思路

这里的思路就是将Memory-Mapped File当作是进程地址空间中的一个连续的区域。实际上mmap也是可以当作这么来使用的。但是一般mmap的实现知识逻辑上面的一个区域，实际上会经过上图中的Page Table、File Index以及FTL的多层的间接映射来实现。而这里的思路是直接把这些间接映射都放到进场的Page Table中，实现一个更加真正意义上的地址空间中的一个连续的区域。

• 这里是将文件系统中Block索引的方式改成了类似于现在Linux/amd64上面的四级Page Table的方式，这个“Page Table属于一个文件的一部分。在改动的同时可以兼容原来的POSIX的接口，

  

• 这里有有个问题要处理，由于这个Page Table 属于一个文件，如果不同的进程使用不同的permissions映射同个文件的时候，比如READ_ONLY 和 READ_WRITE，共享的Page Table可以导致违反permission的情况。这里的解决方式是使用Semi-Virtual Memory，即只会共享leaf-level page table pages (LL-PTP)。Page Table其它的部分为在map和unmap的时候创建和销毁。下面这幅图来自Paper上面，另外一个从网上着的Slide[5]中和这幅图存在一些差别，[5]中的右边的Page Directory为一个而不是两个，

  

• FlashMap中，mmaped file的一个page在内存中的时候，对应的LL-PTP中的PTE会有相应的标记。保存在内存中的时候会记录在内存中的地址，在SSD中的时候会记录在SSD中的位置。当保存在内存中的时候，使用另外的一个索引结构来记录这个Page原来的在SSD中的位置，这个index实际占用的空间也很小，

  The auxiliary index is implemented using a simple one-to-one correspondence between DRAM pages and the SSD-Location of the block that the DRAM page may hold – a simple array of 8 byte values. It must be noted that the size of this array is the same as the number of pages in DRAM and therefore is not significant.
  

• mmap相关的系统调用中，mmap、munmap之外，mprotect也是很常用的一个(另外还有msync)。这里为了保持mprotect的语义。对于使用mproect特殊处理permission的内存区域，这里的处理方式是通过禁用Semi-Virtual Memory机制的方式。使用另外的一个Private的LL-PTP来处理。基本的思路如下图。其它的部分还是使用Shared的方式处理，

  

• 前面讲的是文件系统和进程内存管理上面的一些修改。在系统和SSD交互的借口上面，这里就有一个特殊的要求：即没有使用这里的这种机制的SSD部分，使用原来的机制处理，而使用了这里这种机制的部分，使用不同于原来的机制处理。为了处理这种要求，这里使用的是一种虚拟化的机制。对于每个mmaped file，FlashMap创建一个48bit地址空间的虚拟的SSD，这些虚拟化的信息会被FlashMap保存到一个地方。当虚拟的SSD使用48bit的地址空间，而实际的SSD使用64bit的地址空间的时候，可以创建的虚拟SSD数量是一个比较大的数字。

• FTL也是SSD中一个非常重要基本的组件。这里的思路是讲FTL和Page Table结合起来，

  The SSD driver is designed to use the x86_64 style four-level page table of the file as the data structure for storing the indirections. The indirections for the proto-SSD are implemented and managed by the SSD driver, while the indirections for every virtual SSD are stored inside the shared LL-PTPs of FlashMap. 
  

  SSD Driver也可以使用这里提供的接口来查询和修改映射信息，

  • update_mapping allows the SSD driver to change the log- ical to physical mapping of a particular virtual block of a particular virtual SSD.
  • read_mapping is used by the SSD to obtain the physical page address of a virtual page of a virtual SSD.
  • lock_mapping is used by the SSD to lock access to the virtual page. Any accesses will lead to a fault. Faults are not processed until the SSD releases the lock.
  • unlock_mapping is used by the SSD to unlock access to the virtual page. Fault that occurred since locking are processed.
  

0x23 评估

这里的具体信息可以参看[3].

参考

1. Efficient Memory-Mapped I/O on Fast Storage Device, TOS ‘16.
2. Failure-Atomic msync(): A Simple and Efficient Mechanism for Preserving the Integrity of Durable Data, Eurosys’13.
3. Unified Address Translation for Memory-Mapped SSDs with FlashMap, ISCA ‘15.
4. https://www.cc.gatech.edu/grads/j/jhuang95/papers/ISCA-FlashMap-Jian.pdf