USTCReadingGroup——How-to-Copy-Files

Step 1

题目摘要引言

Copy-on-Write写时拷贝技术，查阅资料发现，有两个应用运用CoW较为成功

  1. 进程的写时拷贝技术（Linux）

    进行fork()时，操作系统不会拷贝父进程的“正文段”、“数据段”、“堆”、“栈”并分配物理块给子进程，而是为新生成的子进程创建虚拟空间结构，它们来复制于父进程的虚拟究竟结构，但是不为这些段分配物理内存，它们共享父进程的物理空间。当父进程有更改段的行为发生时（“Write”发生），再为子进程相应段分配物理空间。原文博主援引 LKD《Linux Kernel Development》：

    传统的 fork()系统调用直接把所有的资源复制给新创建的进程。这种实现过于简单并且效率低下，因为它拷贝的数据也许并不共享，更糟的情况是，如果新进程打算立即执行一个新的映像，那么所有的拷贝都将前功尽弃。Linux 的 fork()使用写时拷贝（copy-on-write）页实现。写时拷贝是一种可以推迟甚至免除拷贝数据的技术。内核此时并不复制整个进程地址空间，而是让父进程和子进程共享同一个拷贝。只有在需要写入的时候，数据才会被复制，从而使各个进程拥有各自的拷贝。也就是说，资源的复制只有在需要写入的时候才进行，在此之前，只是以只读方式共享。这种技术使地址空间上的页的拷贝被推迟到实际发生写入的时候。在页根本不会被写入的情况下—举例来说，fork()后立即调用 exec()—它们就无需复制了。fork()的实际开销就是复制父进程的页表以及给子进程创建惟一的进程描述符。在一般情况下，进程创建后都会马上运行一个可执行的文件，这种优化可以避免拷贝大量根本就不会被使用的数据（地址空间里常常包含数十兆的数据）。由于 Unix 强调进程快速执行的能力，所以这个优化是很重要的。这里补充一点：Linux COW 与 exec 没有必然联系

  2. 文件系统的写时拷贝技术

    Copy-on-write 在对数据进行修改的时候，不会直接在原来的数据位置上进行操作，而是重新找个位置修改，这样的好处其一是一旦系统突然断电，重启之后不需要做 Fsck。好处就是能保证数据的完整性，掉电的话容易恢复。再者就是和本文内容相关，Cow 常常也作为减少文件物理复制的优化手段。比如很多逻辑卷 manager 支持 block-level 的 Cow 快照。一些文件系统直接支持 Cow 文件或目录。

基本理论概况

write-optimization 来实现 Copy（复制）与 Write（写）的分离。

没有出现数学公式，图示过程后是复杂度分析。

结论部分

文章展示了如何利用写优化来实现Decouple writes from copies，并实现nimble performance的性质。且这种优化不干扰非相关操作的性能。如在 LXC container 体现出 3-4 倍的拷贝性能提升。

推广：数据结构批量更新。不仅能够应用于文件系统，还可用在数据库等，比如（在 B-DAG 的实现可用于 KV store）。

回答基本问题

  1. 类别

    对现有系统的优化，提出一种新模式。

  2. 内容

    暂无，文章中提到的 COW 技术没有学习过。

  3. 正确性

  1. 创新点

    不同于传统的 COW 技术，通过写优化将 C 与 W 分开达到性能上的进一步提升。

  2. 清晰度

阅读选择

继续阅读

Step 2

细读笔记

Introduction

Cow 技术的核心调节参数是 Copy 的粒度：

  • 粒度大
    • 比如文件级
    • 小改动的代价会被放大
    • 会增大更新延时
    • 相关的 Copy 会丧失 share 能力，可能造成大的空间浪费（如只有很小修改）
  • 粒度小
    • 更新很快但是碎片花
    • 按序读代价变大

Nible clones:

  • be fast to create
  • have excellent read locality, so that logically related files can be read at near disk bandwidth, even after modifination.
  • have fast writes, both the original and the clone
  • conserve space（节省空间）, the write amplification and disk footprint are as small as possible, even after updates to the original or to the clone.

现有的 CoW 技术实现都不是 Nible 复制。

文章 Contribution（详细见第二页右下）:

  • 提出一个逻辑复制 specifiction（说明？）
  • nimble clone 必须满足的一组（性能）条件
  • 实现了一个符合上述要求的文件系统设计

CAW（Copy-on-Abundant-Write）：应用于 BetrFS 0.5's clone 实现，buffer 累计小的修改，直至衡量其维持 delta 的代价超过 copy，如此则重新复制。

BetrFS Background

B\(^\epsilon\)-tree

BetrFS 由 KV-store 的数据结构（B\(^{\epsilon}\)-tree）来命名，同 B 树变体，B\(^\epsilon\)-tree 将 kv 对储存在叶子结点中，

关键特征：B\(^\epsilon\)-tree 的内部结点（interior nodes）缓冲了叶子内容将要发生的改变，名为 message。逐曾 flush message 直到达到叶子结点。

B\(^\epsilon\)-tree 在每个结点 log 更改，而向下的更新是按批次的，所以 IO 的节省空间遂批次增多而增大。

Range Operation

BetrFS 对连续键值范围操作的优化，设计用来优化文件系统 namespace 的子树操作。

full-path keys 带来的遍历，读文件、搜索都是一个 range 操作（相同 prefix）

问题记录

未读（且值得读）文献记录

[25][the log-structured merge-tree (lsm-tree)]() （太多相关内容都是基于 LSM-tree 的了，一定要补一下）。

Step 3

思路复现

证明与推理复现

实验验证复现

会议内容记录

What is logical Copy?

  • cp -r "Not changed"
  • ln "will change"
  • ln -s "will change" 硬软连接
  • cp --reflink 本文内容，逻辑拷贝

过程描述

改变之前两个文件指向相同的 Data Block 组，假设对 1 位进行改变，会使 Copy 一个新的 Data Block，产生两大问题：

  1. 一点修改就要改 Data Block
  2. 碎片化，把排排坐有序的 Data Block，变为无序访问了。

测试过程描述（图示）

写放大：每个 block（4KB）都做个小修改，

碎片导致时间开销：越碎片，时间越长？

当前存在的问题

物理 Copy、逻辑 Copy 的三个问题，其中还包含一个 Trade Off。

Contribution

Implementation

什么是 BetrFS？

  • BetrFSL

    • an in-kernel， local file system
    • built on a KV-store substrate(B\(^\epsilon\)-tree)

    特征：1. 更小的关键字 fewer pivots. 2. buffer

B\(^\epsilon\)-tree

左边 piviot b 树中的关键字，右边是 buffer

Cloning Operation Semantics

write amplification

对于 Trade Off，根据已知的 B\(^\epsilon\)-tree 数据结构的特征，在保证块很大的情况下，写也不慢（减小写放大影响）。

Postpone：树到 DAG，树的叶子节点是要保证唯一性的。

GOTO messages

GOTO messages： Prefix /b/0, goto /a。举例子，Docker 逻辑复制，通过 GOTO message 就可以占据一个名称空间，还用原来的物理空间，不扩。

A GOTO message maps: keyrange(a,b)->a node 把一个范围的 key 映射到一个 node。(The target node should be the Lowest-Common Ancestor(LCA)). 为什么是公共祖先，我个人理解，再下一层就不饿能保证下次对应相同的 data block。

由于加了边（Goto 指向边），变成了个有向无环图。

有向无环图带来的问题，直接指向的位置如果不是最新的（上一层有 buffer），则有过去更改没有刷下来。解决方案，加 Ref 标记，并强制上层路径 flush

Handling Fringe Nodes

Implementation and Optimization

Preferential splitting

  • 分割 leafnodes 的选择
  • 11

Background cleaning

BetrFS 的影响

写放大和碎片控制都有效，克隆的 Latency 最低的。

结论：相比于剩下三个文件系统，达到的效果：Low space amplification, Low fragmentation, Low clone latency

通常的文件系统

顺序 IO 和随机 IO

Li 老师点评

Slides 比文章更好，可以再关注下。

Research，小而美的问题，比如这个，How to copy files。

大的 Scope