Chinaunix首页 | 论坛 | 博客
  • 博客访问: 23420
  • 博文数量: 11
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 0
  • 用 户 组: 普通用户
  • 注册时间: 2016-08-27 19:11
文章分类

全部博文(11)

文章存档

2018年(2)

2017年(4)

2016年(5)

我的朋友

分类: 服务器与存储

2017-05-16 09:18:51

原文地址:ZFS - 空间图 (Space Map) 作者:nnusun

翻译 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%时,空间图就开始蒸发,使得最后的磁盘空间可以得到充分的利用,用来存储有用的信息。

阅读(771) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~