ZFS - 空间图 （Space Map）

翻译 Jeff Bonwick博客：https://blogs.oracle.com/bonwick/en/entry/space_maps

每个文件系统都必须做好的两个最基本的管理工作：管理数据的位置，管理空闲空间位置。

理论上说，管理空闲空间并不是必须的，因为每个block要么是被分配了，要么没有被分配，所以空闲空间可以通过假设所有的空间都是空闲的，然后扣除已经分配的空间来计算得到；已分配空间可以通过从文件系统的根来遍历整个文件系统得到，任何一个block只要在遍历过程中没有遍历到，就是空闲空间。

事实上，通过这种方式来查找空闲空间是令人无法忍受的，因为任何一个文件系统为了找到一点空闲空间都要耗费很长的时间。为了更快地分配和释放blocks，文件系统必须通过一个有效的方式来管理空闲空间。这篇文章中将讲述最常见的空间管理方式，以及它们的缺点，最后给出我们为ZFS设计的一种新的方法。

位图（Bitmaps）

最常用的管理空闲空间的方法是位图（bitmap）。位图是简单说就是位数组，数组的第N位用来表示第N个block是被分配的还是空闲的。使用位图方式消耗很少的资源：用一个位就可以表示一个block。对于一个4K大小的块来说，位图占用的空间是1/(4096*8) = 0.003%。（8代表每个字节有8位）。

对一个1GB的文件系统来说，它的Bitmap是32KB，很容易将这部分数据存储到内存中，也很方便对其进行扫描，找到空闲空间。对于一个1TB的文件系统来说，Bitmap是32MB，同样可以很方便地存放在内存中，但是扫描这32MB数据的每一位就不是那么容易的事情了。而对于1PB的文件系统来说，它的Bitmap是32GB,这对于大多数机器的内存来说都是不能接受的。这就意味着要从硬盘上将这32GB的数据读出，然后扫描每一位，这将会更慢了。

很显然，这种方式并不适合。

一个表面上的补救方法是将Bitmap分成许多小块，每次只管理一个小块中的位。比如，对于使用4KB块大小的1PB文件系统来说，空闲空间可以分策划那个一百万个小的bitmap，每个大小为32KB。同时将概要信息（使用一百万个整数来表示每个bitmap中的空间）存放在内存中，这样一来就可以很容易找到空闲空间，而且扫描小的bitmap要高效的多。

但是这里仍然有一个很严重的问题：Bitmap(s)不仅仅是在分配新block的时候需要被更新，在block被释放的时候也要被更新。文件系统控制这分配的位置（这决定数据将被写入哪些block），同时要控制释放的位置。一些很简单的操作，比如"rm -f"会造成整个设备上的block被释放。还拿1PB的文件系统为例，在最坏的情况下，删除一个4GB的数据（一百万个4K的block）将需要对这百万个bitmaps进行读、修改、写回操作。也就是说，删除一个4GB的文件可能将涉及到2百万次磁盘的I/O操作——这是很不合理的，甚至是最差劲的行为。

仅仅这一个因素就足以说明位图方式是不适合的：因为释放操作通常是随机的，但是位图并不适应内存中这种的随机访问的形式。

B-树（B-trees）

另外一个常用的管理空闲空间的方式是使用B-tree管理一个范围，范围是一个用两个整数（偏移和长度，offset and length）来表示的连续的空闲区域。B-tree是按照范围的偏移来排序的，所以说对于分配联系的空间很高效。很不幸的是，使用B-tree也有一个跟位图方式同样的问题，那就是难以对抗随机释放。

那应该怎么做？

延迟释放（Deferred freed）

一种减轻随机释放带来的问题的方法是采用延迟更新Bitmap或B-tree，增加一个最近释放的block链表。当这个延迟释放链表达到一定的大小时，它可以在内存中先排序，然后再释放到对应的位图或是B-tree中去。虽然不是很完美，但是很有帮助。

但是如果我们走的更深些呢？

空间图：日志结构的释放列表（Space maps: log-structured free lists）

回想一下很久以前日志结构文件系统提出的这个问题：如果我们不是周期性地将事务日志写回文件系统，而是将这些事务日志 作为 文件系统会怎么样呢？

对于延迟释放列表，我们可以提出同样的问题：如果我们不将延迟释放列表写回bitmap或是B-tree中去，而是将延迟释放列表本身用来表示空闲空间会怎么样呢？

这就是ZFS所做的。ZFS将每个虚拟设备（vdev）划分成几百个被称为metaslab的区域。每个metaslab都有一个关联的空间图（space map）用来描述这个metaslab的空闲空间。空间图实际上就是一个简单的按照时间排序的分配、释放的日志。空间图使得随机释放像顺序释放一样高效，因为无论哪个范围（译者注：前文所说的，用一对整数表示一段连续的空间）被释放，在磁盘上的表现形式就是将这个范围追加到空间图对象中。对于分配来说也是一样，在磁盘上的表现形式为在空间图的对象上追加这个范围（当然，需要用1bit来表示这个是分配而不是释放）。

当ZFS决定从一个特定的metaslab中分配block时，首先将这个metaslab的空间图从磁盘上读到内存中，在内存中重新构成一棵按偏移排序的AVL树，用来表示空闲空间。这样我们在内存中得到一个压缩的空闲空间表现形式，同时支持高效的连续空间分配。ZFS同时利用这个机会来压缩空间图，如果有很多的分配-释放可以抵消，ZFS将磁盘上的空间图替换成精简后的形式。

空间图有很多很高的属性：

• 不需要初始化，如果一个空间图是空的，那么说明它没有分配或释放过程，那么所有的空间都是空闲的。
• 适合大规模，由于空间图只追加，不管有多少空间图需要管理，只有最后一个空间图对象需要被存放在内存中来保持高性能。
• 没有病状，不论任何形式的释放或是分配，对空间图的更新都很高效。
• 无论pool是空的还是满的都可以很高效地找到空闲空间（不像位图，当快要填满时，需要耗费很长时间来扫描） 

最后，注意到当空间图满了的时候，它将会被一个单一的范围替代。因此空间图有一个很漂亮的属性：当你的存储池使用率接近100%时，空间图就开始蒸发，使得最后的磁盘空间可以得到充分的利用，用来存储有用的信息。