In-kernel memory compression 翻译:内核内实现的内存压缩
http://blog.jcix.top/2016-12-09/inkernel_memory_compression/
2016年12月9日 BY JAYCEEZ·0评论
ToC [折叠]
（发布于 April 3, 2013， 意译于12/9/2016）
- 原文链接 ：https://lwn.net/Articles/545244/
- 另一个版本的翻译(有些句子没有翻): http://kernel.taobao.org/index.php?title=%E5%86%85%E6%A0%B8%E6%9C%88%E6%8A%A52013-04#In-kernel_memory_compression
- 吐槽 : 我的天呐！！翻译完我才发现有人翻译过了，早知道我就不自己翻译了，痛苦死我了。。
- PS :内容我还没有完全理解，仅供参考，以原文为准。
阿姆达尔定律告诉我们一个计算机系统肯定存在一个瓶颈。历史上，对于很多工作负载这个瓶颈都是cpu，所以人们在不断提升cpu性能。所以现在，渐渐地，ram成为了瓶颈。有时当数据在ram和disk之间来回传递时，cpu就在一边干瞪眼呢。增大ram有时并不是一个好的或者经济的做法，更快的I/O或者ssd可以缓解问题，但是不能消除这个瓶颈。
如果可以增大ram中数据的有效容量，不是很好吗？既然cpu闲置，也许我们可以拿闲置的cpu周期来专注这件事。这就是内核内压缩的目标：用闲置的cpu周期来做ram中的压缩和解压缩。
算上刚刚发布的zswap，现在有3个内核内实现的压缩方法在被建议merge到内核的内存管理(memory management, MM) 子系统：zram, zcache和zswap。乍一看可能会让人觉得一个就够了吧，但是他们三个却有很大的不同，可能面向着不同的用户群。所以就像现在内核中存在很多文件系统一样，有一天内核中也会存在多种压缩方案吧，不过这还得李纳斯大神和主要的内核开发者说了算。。。为了方便说明，本文把这些方案统称“zproject”，并对比了这些方案。我们先说明一些关键原则和压缩遇到的挑战。然后我们会从三个层次说明并详细地阐释这些zprojects设计上的不同选择，之后我们还讨论zprojects怎么和内核其他部分交互，最后给出结论。
压缩基础
要让压缩在内核中工作，内核必须把字节序列放入内存中再压缩，之后内存中也应保有压缩后的版本，以备这些数据被再次使用。压缩状态下的数据不能被读写，所以对压缩版本的数据再进行解压缩后才能继续读写这些数据。
字节序列压缩多少都可以，但还是以一个固定大小的单元压缩较方便。贯穿整个内核的一种基本的存储单元是page，一个page由PAGE_SIZE个字节组成，通常的linux支持的架构中，page的大小是4KB。如果这个page对准了PIGE_SIZE的地址分界，那么它就被称为page frame。对于每个page frame，内核在ram中都有相应的struct page结构。所有这三个zprojects都用page作为压缩的单元，并且通过开辟和管理page frames来存储压缩页。
有很多可用的压缩算法，但总的来说，高压缩比意味着高cpu周期，运行的快的算法一般压缩比较低。在时间效率和压缩率之间做出权衡很重要。这三种zprojects，默认都使用内核lib/文件夹中的LZO(1X)算法，这种算法做出了很好的权衡。然而，算法的选择还是很灵活的，也许cpu运行的算法还会被一些特殊架构的硬件压缩引擎取代呢。
一般，存在一些数据一会儿压缩一会儿解压缩的循环，数据序列大概和序列中的字节数成正比。因为页比较大，页压缩和解压缩都是很昂贵的操作，所以我们希望限制这些操作的数量。因此我们必须谨慎的选择哪些页要被压缩，尽可能找到那些可能会被再次用到同时最近不会用的页，以免把cpu时间浪费在重复的压缩然后立刻又解压缩上。因为压缩页不能直接访存某个字节，我们必须要保证内核清楚地辨识出哪个是压缩页，避免对压缩页中的字节尝试cpu的线性地址操作，同时保证压缩页可以被找到并可以在被访问时解压缩。
页被压缩时，它被执行了压缩算法，并且结果是一个我们可以称为zpage的字节序列，zpage的大小我们称为zsize。zsize的大小和被压缩数据相关，所以我们很难预测它的大小。事实上，zsize的大小驱动了很多zproject的设计决策，所以还是很有要深入了解的。一个页的压缩率等于zsize除以PAGE_SIZE。尽管对于几乎所有页，zsize都应比PAGE_SIZE小（压缩率小于1），但是也有zsize大于PAGE_SIZE的偶然情况，好的压缩方案应该有一个应急方式去处理这种例外。对于另一种极端，一个数据页包含大多0和1时压缩比可能达到100倍或更多，比如用LZO算法压缩全0的页，得到的zpage的zsize大小等于28，压缩率是0.0068。
掰手指头算一算，平均来说，压缩率都差不多在0.5左右，对于那么多种工作负载，可以把分布想象成一个均值为PAGE_SIZE/2的钟形曲线，我们把zsize小于PAGE_SIZE/2的zpage称为thin zpage，大于PAGE_SIZE/2的称为fat zpage。对于任一给定的工作负载，分布可能偏向thin或者fat，这取决于被压缩的数据是否有利于压缩（比如可以考虑大部分为0的页和已经压缩的JPEG图片的情况）。一个好的压缩方案应该能处理各种zsize分布的情况。
有了这些概述，我们现在可以比较三种zproject了。从上层看，每种方案都有一个“数据源层”（data source layer）来提供要压缩的页和一个“数据管理层”（data management layer）来组织和存储zpage。对于数据管理层，有两个子层，一个是数据管理，我们成为元数据层（metadata layer），还有第二个我们称为zpage分配器层（zpage allocator layer）的层，来决定如何利用好已有的内核内存和内核分配代码（比如alloc_page()）来合理地存储这些zpages。
数据源层
如前所属，压缩的特性限制了其可以被应用到的页的种类和数量。压缩一个马上会被再次使用的页没有什么意义，压缩一个也许永远也不会用到的页也没有意义。所有三个zproject都设定了一个或多个数据源来提供预认证（”pre-qualified” ）的数据页序列。在其中一个zproject中，一个存在的内核子系统是数据源，在另两个zproject中，一些内核hooks被作为transcendent memory项目的一部分被提前添加到了内核，被称为cleancache和frontswap机制，用于获取数据页流。
每个数据源还必须为每个数据页提供一个特殊的描述符，或者说“键”，来保证对于每个页，一旦被存储和关联这个特殊的“键”，以后可以被通过“键”值来检索到。还有很重要的一点需要注意，就是不同的数据源可能会导致完全不同页流内容，所以压缩时，或出现不同的zsize分布。
Swap/匿名页作为数据源
linux 的swap子系统提供了一个很好的压缩机会，因为当系统内存紧张时，swap扮演了一个在频繁使用的匿名页和很少使用的匿名页间的看门人角色，后者会被从ram换出到慢得多disk。我们可以压缩要被换出的页，不让它们全部被换出。进一步说，swap子系统还已经为每个页提供了一个特殊的“键”，来保证页可以从disk swap区被取回。不出所料地，三种zproject都将swap页作为一个理想的压缩数据源。
其中一个zproject zram用了已有的swap设备模型，一个zram swap设备被明确创建出来并在用户空间可用（用mkswap和swapon实现），这个zram swap设备在所有已经配置的swap设备优先级最高，当swap子系统把数据页发送到zram设备中时，页直接穿过块IO子系统被送到zram”驱动”中。所有的swap页被送到zram后都被压缩，并且关联到swap设备号和页偏移量连接得到的“键”上。稍后当swap子系统决定页必须被换入时，zram设备会被通知，zram会解压匹配swap设备号和页偏移量的zpage到目标页框中。
另外两个zproject，zcache和zswap，用到了内核中swap子系统的frontswap hooks（linux 3.5开始可用）。frontswap作为前端的存储，它是已存在swap设备的一种cache。被交换的页会直接进入zcache或者zswap并被压缩，它完全避开了块io。发生缺页时，块IO依然会被绕过，然后页像在zram中一样，被解压并直接放入到缺页页框。
对于这些不同的实现方式，有一些细微但是重要的副作用：
- 块IO子系统被设计成工作于固定大小的块设备，如果块写操作导致错误时，不是很高兴（？）。所以当遇到压缩效果不是很好的页时，所有PAGE_SIZE的未压缩页都会被直接存入ram中的zram，并没有节省内存。基于frontswap的zproject有更大的灵活性，当一个比较大的zpage出现时，zcache和zswap会简单地拒绝它，让对应的未压缩页直接进入真实的位于磁盘上的swap分区。
-
由于zram声称自己是一个磁盘swap，需要用户空间的配置，但是这也意味着没有物理swap设备时zram也可以工作，而恰好在嵌入式linux系统中，一般是没有物理swap设备的。另一方面，zcache和zswap完全倚靠已配置好的swap设备，所以需要至少一个设置好的且足够大小的物理swap才能工作。所以，对于嵌入式环境，zram更为友好，而对于传统的服务器/数据中心环境中，其他两种zproject更为合适。
-
还有值得注意的一点是：三种方案都永远不会丢弃任何数据页除非明确指出，否则用户空间的程序就可能出现数据丢失。由于三种方案都有有限的容量，设置一个“减压阀”是很有必要的。zcache和zswap都有把数据“writeback”到swapdisk中数据原本目标地的能力，但是zram却没有这个机制。
干净page cache页作为数据源
对于一个运行的系统来说，大多数页框的都包含很多磁盘文件系统上已有的相同页面。在Linux中，这些页被存储到page cache中，这些页中的数据被存储到RAM中来等待未来被再次访问。当内存紧张时，内核开始寻求释放RAM空间，内核会快速丢弃一些重复“干净”页，这些也如果被再次用到还可以从文件系统中读到。内核从linux 3.0开始出现的“cleancache”hook可以转换这些页框中的数据，把页送到zcache中进行压缩并保存在RAM中，缺页也会被另一个cleancache hook中断来解压这些数据。
因为现代文件系统可以很庞大，保证页标识(unique identification)的唯一性对于page cache页来说可能要比swap页更容易遇到困难。事实上，cleancache提供的键必须唯一地标识出页属于：哪个文件系统、文件系统中的哪个文件（一个“可输出的”inode值）和文件中的页偏量。
Zcache设计了掌控cleancache的页的功能，包括全范围所需要的键。随之而来的结果是，数据管理层更为复杂，由不同的数据结构组合而成，下边将会说到。进一步来说，在内核VFS部分的一些cleancache hooks导致了数据管理层的一些调用，这些调用不能被中断，应该被的恰当地控制。
甚至相较于swap数据，压缩过的文件系统数据（page cache数据）也可以更急速地增长，更快地填满RAM。所以，就像面对swap数据那样，对于page cache数据增加一个“减压阀”也是很有必要的。我们知道，和swap数据不同的是，page cache数据可以在必要时被简单丢弃。因为zcache从一开始就是被设计为管理page cache页的，它的数据管理层也被设计了高效管理page cache的zpages丢弃的方法。
zram可以在RAM中包含整个被压缩后的固定大小文件系统，但是并不是一个“无RAM文件系统“的cache。本质上来说，部分RAM可以被预分配作为文件系统的”快盘（fast disk）“，即使文件系统元数据也被压缩并储存在zram中了。对于小到可以放置入RAM的文件系统，zram是有用的，zcache的cleancache结合压缩提供的缓存容量即使对于大型文件系统也是很有用的。
zswap是特别关注的是swap，所以从不会用page cache或者文件系统数据作为数据源。结果它的设计也更简单，因为它略过了管理page cache数据源的复杂性。
元数据层
一旦zproject收到要被压缩的数据页，它建立并维护一些数据结构来保证zpage可以被存储并关联一个相应的键，进而保证可以在以后被找到和解压缩。并发性页必须被考虑，来保证不必要的串行瓶颈不会发生。三种zproject采用了非常不同的数据结构，这是因为数据源的需求不一样。
因为系统swap设备的数量比较少，而且每个设备中页的数量是预先决定和固定的，用一个小的非负整数表示的swap设备和页偏移量相结合来表示一个特定的页就足够了。所以zram干脆直接用表（每个配置好的zram swap设备都有一个表）查找的方法来寻找和管理它的数据。比如，对于每个存储的页，zram表包含一个zsize（因为zsize对于解压缩的验证很有用），还有一些存储数据需要获取的信息。每个设备的并发性用一个读写引号量被限制。
zswap必须管理相同的swap驱动（swap-driven）的地址空间，但是它对于每个swap设备用一个动态的红黑树来管理它的数据。在进入树的时候，必须保持一个树的自旋锁，这不是一个瓶颈，因为对任一swap设备的同步访问都被其他swap子系统的因素很大程度地限制了。zswap的元数据层是被有意地保持简洁（intentionally minimalist？）。
zcache必须同时管理swap数据和page cache数据，因为后者有一个更加大范围的键空间，这导致了zcache的元数据数据结构大小和复杂性提高。对于每个文件系统，zcache都创建了一个”池子“（pool），里面是包含有红黑树根指针的hash表。红黑树中的每个节点表示一个文件系统inode（inode空间在一个可输出的文件系统（exportable filesystem？）经常非常稀疏地，这样会把自己提供给红黑树做管理）。然后每个红黑树节点包含一个基数树(整个内核中用于页偏移量的数据结构)的头结点，这个基数树被用来查找某一个特定的页偏移量的。基数树的叶子节点指向一个zpage引用的描述符。每个hash表的入口都有一个自旋锁来进行并发管理。与swap和frontswap不同，通过cleancache进行文件系统访问非常可能会同时发生，所以要积极地避免竞争。
元数据层回写(writeback)的影响
前边说过zcache和zswap支持回写，这为他们中的数据结构增加了重要转机，理想情况下，我们一般会喜欢以一定的有根据的顺序来回写，比如LRU算法等。为了达到这个目的，zcache和zswap维护了一个队列来把存储的数据排序，zswap将每个独立的zpage加入队列，zcache将用于存储zpage的页框加入队列。由于查找需要键，并且搜索是从根向下来搜索的，所以回写要从数据结构的叶子节点中选取一个或多个zpages，然后不但要输出的解压缩数据，还要从叶子向上层删除它的元数据。这个需求有两个后果：1.数据结构的叶子节点必须包含key和其他别要的心理来删除元数据；2.如果回写被允许于其他数据结构的访问（搜索、插入、删除）一起并发执行，必须理解和避免竞争条件的发生。
zswap当前实现的writeback仅是存储数据的一个副作用（仅当内核页分配 失败时发生），它会限制可能的竞争条件。zcache实现writeback作为收缩机制来完全独立地运行，因此也必须处理更多的潜在竞争条件，zcache当进行page cache页消除时必须处理同样多的竞争条件。
其他元数据层的话题
一个聪明的数据管理技术值得提一下：zram删除重复的”零页（zero pages）“（页中只含有0）使之不会占用额外的存储空间。在一些zsize分布中，这样的页可以代表很大一部分被存储的zpages。由于整个页的数据可能都需要被扫描来看是不是零页，这个操作的开销要远小于数据的压缩。在任何情况下，这种扫描也会预先占据cache的空间，这正是压缩算法所需要的。zcache和zswap未来应该加入这个特性。更精确的数据重复删除也许更有用，欢迎这些patches。
Zpage分配器层
zpage的内存分配可能会出现一些独特的挑战。首先，对于给定数量的内核页框，我们希望最大化zpage可以存储的数量，这个比率我们称为”密度（density）“。将这个密度最大化是有挑战性的，因为我们不能预测要被存储的zpage的数量和这些zpage的zsize大小分布，所以碎片化将是一个挑战。第二，分配内存给存储的zpages经常发生在有很严重内存压力的环境中，一个高效的分配器必须掌控频繁的失败而且应该最小化大的(比如多相邻页)分配。第三，如果可能，我们希望分配器支持一些按顺序的回写或者如上所述的丢弃机制。
一个明显的选择是用内核中已经存在和广泛使用的分配器：kmalloc()，它对于 2^N 大小的默认块是最优化的。对于分配 2^N+x 的大小，最少50%被分配的内存会被浪费。kmalloc()对于奇数大小提供一个选项，但它需要预先分配caches，一般是相邻的一些页（“高阶”(“higher order”)页），他们在内存压力下很难被分配。早期的研究证明kmalloc()的失败很频繁，是不能被接受的，而且密度也不高，所以kmalloc()被抛弃了，其他的选择都是基于alloc_page()的，它总是一次只分配一个页框。
为了提高密度，基于TLSF算法的xvmalloc分配器被写了出来。Xvmalloc对于一些工作负载提供高密度，它是zram初始默认的分配器，也是最初zcache的frontswap-driven部分。高密度导致了糟糕的碎片化(poor fragmentation)的特性，特别是对zsize分布偏向于fat（压缩率偏向于>50%）的情况。Xvmalloc现在已经被linux内核抛弃了。
一个新的分配器zbud被写出来用于zcache的cleancache-driven部分。最初的zbud版本没有关注密度，二是专注于丢弃cleancache提供的zpages。对于zbud，一个页框不能有多于两个zpages，有一对zpages，一个fat一个thin。页框而不是zpages会进入LRU队列，这样整个页框可以更容易地被系统释放。对于zsize偏向于thin的工作负载，很大一部分的空间都被浪费了，但是碎片化被控制了，释放也很简单。
Zsmalloc，是一个想统一切的分配器。zsmalloc有kmalloc的所有优点，而且还有分配全范围匹配存储zpage大小的能力，zsmalloc也永远不会需要高次分配。所有有同一级别zsize的zpages都会聚在一起存储在同一大小的zspage中。一个聪明的特性（特备对于zpages很有用）允许不连续的页框“缝”到一起，所以第一个页框最后的字节包含zpage前一部分，第二个页框前边的字节包含zpage的后一部分。N个不连续页被按需要分配了各自的大小级别，N的值是zsmalloc选取的最有利于高密度的值。
纵观这些创新，zsmalloc达到了高密度的同事保证了大范围的zsize分布：balanced，fat或是thin。可是，它有一个致命弱点：高密度和页的横跨页框导致了丢弃页和同时回写到空闲页较难，导致不同程度的碎片化，并导致低密度，使得它对于zcache的clean。所以zbud被修改，使用了一些zsmalloc所开创的技术。zbud还是被限制在最多两个页一个页框，但是当丢弃或者回写任务繁重时，它的密度就可以和zsmalloc相比了。zcache决定使用zbud来用于zswap导致了zcache的fork。首先是“老zcache”（也就是zcache1），然后是“新zcache”（也就是zcache2），然后是zproject的完全分裂，zswap，因为作者喜欢zsmalloc的密度胜过zbud的对cleancache页的支持、预测能力和页框回收能力。
所以现在，有两个zpage分配器，它们也都在发展中。好的zpage分配器的选择决定于使用的模型和不可预测的工作服在。有可能两种分配器的混合版本会出现，或者以后出现的分配器会统一它们。
与内存管理(MM)子系统交互
一定程度上，一个zproject就像一个对于暂时移除出MM子系统的页的cache。但是它是一个不同寻常的cache，因为它会存储他自己的数据，它从它的后端存储（MM子系统）偷走了容量（page frames）。从MM子系统的角度来看，RAM只是消失了，就好像页面帧被吃RAM的设备驱动生吞一样。这有些不幸，由于zproject和MM子系统都是各自独立的，但是分开来，管理压缩和未压缩的匿名页（也可能是压缩和未压缩的page cache页）。所以考虑一个zproject可以怎么”负载均衡“它和MM子系统及剩余内核部分的内存需求是很有意义的。
现在，所有三个zproject都包含使用标准内核alloc_page()调用的页框，用“GFP标识”参数来保证内核的紧急预留的页不会被用到。所以每个zproject都必须地具备了应对相当频繁的alloc_page()调用失败情况的能力。
Zram没有尝试其他的方法来限制其页框的使用，我们发现，它只是被管理员配置为一个swap设备，swap的参数的确限制了swap页的数量，所以对于zpage，这是可以被接受的。这间接地但是无法预测地限制了使用页框的数量。而且配置是独立的，并且不会认识到系统安装RAM的总量，所以配置上的错误很有可能发生。
Zswap用一个轻微改动过的zsmalloc版本来追踪page frame分配的总数，它保证这个数不会超过系统RAM的某个特定百分比，并且这个限制可用通过sysfs调节。
Zcache和zbud从开始被设计就对页框的使用就有动态限制的特性，最终旨在灵活地于MM子系统使用的显著时变的存储器平衡算法相结合。由于确切的交互模型和最好的未来预测控制策略还没被定下来，所以zcache和zbud的基于页框的回写和丢弃机制支持类似收缩的接口，这个接口可以做到例如减少用于存储匿名zpage页或者page cache zpage页的页框数量等功能。由于zbud可以更好的被预测（每个页框两个zpage），MM子系统可以估计和管理系统中的匿名和pagecache页（包括压缩和未压缩的）和用于管理它们的页框数量。
现状和结论
Zram，zcache和zswap都以不同的方式推进了内核实现压缩的概念。 Zram和zcache都是in-tree状态，但仍然在staging tree中。 虽然分段树已经将内核压缩的概念曝光给一大群内核开发人员，甚至向几个前沿发行版的用户公开，但是staging tree是”代码将会被最终忽略的地方”。 staging tree的维护者Greg Kroah-Hartman已经不愿意接受将任何新的zproject添加到staging tree中。 这为这些zproject创造了一个难题：在staging tree中的演进已经导致zproject的设计和实现被快速改进，但是由于这种演进，它达不到足以合并到核心内核中的稳定程度，现在进一步演进处于停滞状态。
Zswap正在提出通过使用简化的zcache分支（仅有frontswap的分支、使用zsmalloc而不使用zbud），来寻求直接合并到MM子系统中。由于它也比zcache简单得多，它已经获得更多的审阅者，这是待合并代码的一个有价值的优势。但由于它依赖于还在staging中的zsmalloc，不支持page cache页面，也不支持基于页框的回写，所以它的简单性是有代价的。 如果zswap被合并，以后它是否会被充分地扩展还需拭目以待。
所以，内核中实现的压缩有明显的优势和明确的用户群。我们还不清楚它会不会或者什么时候会被合并入核心内核中，也不清楚它会怎么和核心内核交互。如果你很好奇，众多的zproject开发者会鼓励你提出想法和做出贡献。
致谢
Nitin Gupta是compcache的原作者，我是transcendent memory的原作者。虽然这两个项目最初的目标是提高多租户虚拟化环境中的内存利用率，但是它们在单个内核系统中的应用也很快地凸显。 Nitin设计并编写了zram，xvmalloc和zsmalloc的Linux代码，并写了一个zcache的早期原型。我写了frontswap和cleancache（cleancache hook最初是由Chris Mason写的），以及zcache，zbud和ramster的Linux代码。 Seth Jennings对zcache提供了许多改进，并且他也是zswap的作者。 Kernel mm开发者Minchan Kim对所有zprojects都提供了帮助，没有作为staging drivers tree的维护者的Greg Kroah-Hartman的支持和偶尔的批评，没有一个zprojects是可能发展下去的。
与其他任何开源项目一样，还有很多人提出过想法、修复了bug或改进着代码，我们对所有人的努力表示感谢。