一种元数据存储管理的方法——多级位图

    元数据是描述数据的数据，在文件系统、卷管理系统、快照系统中经常会用到元数据，利用元数据信息来描述数据的特征。元数据信息的格式是多样的，不同的系统中元数据具有不同的格式。在快照系统中，元数据的信息量是比较大的，并且会随着管理数据块粒度的减小而增大。但是快照数据的元数据信息语义简单，只有一种语义，所以，诸如快照这样的元数据可以采用位图（bitmap）的方式进行存储。位图存储具有如下两大优点：

1、  位图存储能够节省存储空间。位图中的一位就能描述一个数据块粒度的信息；

2、  位图访问速度快。位图的访问同数组访问方式保持一致，无须任何遍历操作，可以直接通过计算的方法进行定位。

当被管理的数据较少时，可以采用一级位图很轻松的实现对数据空间的管理，但是当被管理的数据空间很大时，直接采用一级位图就会存在如下两大问题：

1、              存储空间的浪费。当数据空间很大时，无效数据空间的比例就会大大增加，如果为这些无效数据也分配位图信息，那么将会大大浪费宝贵的内存资源。实际上，这种思想在Linux内存管理的页表管理部分早就得以采用了。

2、              位图的访问效率偏低。在访问位图信息时，每次都需要获取该位的真实值，当被管理的数据空间很大时，位图信息往往霸占较大的内存空间，所以也需要换入换出技术的支持。在这种情况下，如果只采用一级位图，那么就会做很多无效的换入换出操作，访问效率偏低。

<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

基于上述问题的考虑，针对海量数据管理时，可以采用多级位图实现大量元数据信息的高效管理。一种多级位图的设计思想描述如下图所示：

上图给出了一个三级bitmap的框架图，其中一级bitmap的容量最小，逐层往下容量越大。一级Bitmap容量较小，所以可以常驻内存，二级和三级bitmap可以被换出换出至磁盘设备。一级bitmap中的一位描述二级bitmap中的一个数据块，依此类推，上一级bitmap中的一位表示下一级bitmap中的一个数据块信息。先假设一个数据块的大小为4K，那么上级bitmap中的一位可以表示下级4K的数据情况，如果下级bitmap中的一个数据块中存在有效的位，那么上级对应的bit将会被设置为有效。反过来，如果上级bitmap信息中的bit位无效，那么被描述的下级数据块可以不存在。通过这种方式可以很容易的避免无效数据的存在，节省了大量的元数据内存空间。

此外，多级bitmap可以管理海量数据空间。如上图所示的三级bitmap，如果每级bitmap都能管理4K的数据块，第一级bitmap也为4k容量，那么三级bitmap可以管理的数据块数量为：32T个，所以多级bitmap能够管理的数据空间非常庞大。

另外，多级bitmap可以多位图的访问进行优化。当需要读一个位图信息时，首先需要读第一级bitmap，如果第一级中的bit位有效，那么继续读下一级bitmap，如果第一级bit无效，那么无须访问下一级bit信息了，这种方式可以对大量bitmap元数据访问进行优化。

阅读到这个地方，可能有些读者会产生疑问：二级、三级bitmap信息在内存中该如何组织呢？因为上一级bitmap没有给出下一级bitmap的内存地址，像Linux内存页表的管理都会给出下级页表的地址。实际上这里可以采用B+树之类的结构对二级、三级bitmap数据块进行管理。查询这些数据块可以采用通过bitmap的索引信息，B+树在搜索效率上有一定优势，并且实现简单，所以可以在这个地方进行使用。

多级位图是一种管理bitmap元数据比较高效的方法，其可以节省内存空间，管理大量元数据信息，加速bitmap的访问效率。其基本思想和内存管理中的页表管理有着本质上的相似性。