《经由位图的树表示分配文件存储的方法和设备的制作方法》由会员分享，可在线阅读，更多相关《经由位图的树表示分配文件存储的方法和设备的制作方法（7页珍藏版）》请在金锄头文库上搜索。
1、经由位图的树表示分配文件存储的方法和设备的制作方法专利名称：经由位图的树表示分配文件存储的方法和设备的制作方法技术领域：本发明一般涉及文件系统。更具体地，本发明涉及基于位图为文件分配存储装置中的区块。背景技术：文件系统的一个主要要求是以 区块为单位保持对存储装置的可用空闲空间的跟踪。传统上，文件系统可使用位图来表示空闲空间。位图简单地是位的阵列，其中，第N个位指示第N个区块是已分配的还是空闲的。因此，位图的开销(overhead)可以相对低，诸如，对于每4K大小的区块I位的情况，约为0. 003%。对于IGB的文件系统，对应的位图的大小约32KB，这可以容易地适应存储器，以进行快速扫描来识别空
2、闲空间。然而，当文件系统的大小继续比存储器大小的增长更快地增长时，加载在文件系统中用于扫描的位图在大小或时间方面可能变得重要。例如，用于IPB文件系统的32GB大小位图可能不适应大多数数据处理系统或处理机上的存储器。结果，扫描位图可能需要每次从盘中读取位图(例如，盘的页入和页出)，这样会显著降低文件系统的速度。此外，将大尺寸位图加载到存储器中会直接与其它内核任务竞争数据处理系统中可用的有限资源。例如，如果位图不能被完全缓存，则可能需要用多个缓冲区来管理分页操作。因为每个缓冲区都需要分配系统中的有限数量的缓冲区头中的一个，所以加载大尺寸位图会进一步劣化系统性能。因此，使用位图在存储装置中分配空闲
3、空间的传统文件系统与现代文件系统的增长不协调。发明内容本发明的实施例可包括搜索位图的树表示(例如，红黑树)来找到存储装置中待分配的可用区块的方法和设备。可以接收针对文件的分配请求，以开始搜索。在一个实施例中，位图可包括与存储装置中的区块对应的位的阵列。每个位可指示区块之一是否可用。树表示可包括具有节点的至少一个红黑树(red-black tree),所述节点对应于位图中指示可用区块范围(例如，包括偏移和长度)的一个或多个连续位。可以基于针对给定文件的分配请求的本质(例如，分配大小请求、是否存在该文件等)，选择一个树表示。当位图随着存储装置中的区块分配的改变而被更新时，树表示可以被同步。在替代实
4、施例中，可在存储器(例如，RAM)中维护位置树和范围树，以表示存储装置(例如，硬盘)中的位图，从而指示存储装置中区块的分配状态。位置树可以是根据可用区块范围的位置而设置键值的红黑树。范围树可以是根据可用区块范围的大小而设置键值的红黑树。可以基于如下搜索来识别位置树和/或范围树的一个或多个节点搜索指定的树来找到与基于针对文件的分配请求的标准匹配的未分配空间范围。如果位置树和/或范围树不包括满足搜索标准的匹配节点，则可以遍历位图。可以通过遍历位图并且插入表示盘空间的未分配区域的节点来构建位置树和范围树。根据附图和下面的具体实施方式，本发明的其它特征将显而易见。在附图的图中，以举例的方式而非限制的方
5、式示出本发明，在附图中，类似的附图标记指示类似的元件，并且其中图I是示出用于搜索位图的树表示以分配区块的系统的一个实施例的框图；图2是示出用于表示位图的示例性红黑树的样品图；图3是示出在不搜索位图的情况下识别供分配的可用区块的处理的一个实施例的流程图； 图4是示出搜索位图的树表示以进行区块分配的处理的一个实施例的流程图；图5示出可与本文描述的实施例结合使用的诸如计算机系统之类的数据处理系统的一个示例。具体实施例方式本文描述了用于基于位图的树表示来分配区块的方法和设备。在下面的描述中，阐述了众多具体细节，以提供对本发明实施例的透彻说明。然而，对于本领域技术人员显而易见的是，可以在没有这些具体细节
6、的情况下实践本发明的实施例。在其它情形下，为了不模糊对本说明书的理解，没有详细示出熟知的组件、结构和技术。在说明书中提及“ 一个实施例”或“实施例”意指结合该实施例描述的特定特征、结构或特性可以包括在本发明的至少一个实施例中。说明书各处出现的短语“在一个实施例中”不一定都指同一个实施例。以下附图中示出的那些处理是由包括硬件(例如，电路、专用逻辑等)、软件(诸如，在通用计算机系统或专用机器上运行的软件)或这两者的组合的处理逻辑执行的。虽然这些处理在以下是依据一些顺序的操作来描述的，但应该理解，所描述的操作中的一些可以按不同的次序执行。此外,一些操作可以并行而非顺序地执行。在一个实施例中，存储器(
7、例如，诸如DRAM之类的主存储器)中的至少两个红黑树被用于表示盘(或诸如闪存、硬驱等的其它大容量存储装置)中的位图，位图在文件系统中映射区块分配状态。在位图的树表示(或树结构)中可以明确地描述位图中各个位之间的高层结构。例如，在包括偏移参数10和大小参数200的树节点中可以容易地识别从位图中的第10个块开始的200个未使用区块的片段。因此，基于有效的红黑树搜索能够在有界的时间框架内找到用于分配200个区块(例如，用于巨大的电影文件)的完美匹配。在一个实施例中，表示位图的分别的红黑树可以使能用不同的搜索标准来搜索最佳分配。例如，为了定位用于追加(append)到文件的连续区块的片段，可以搜索位图
8、的基于位置的树表示来找到最靠近指定位置的未分配区块。可替代地，为了定位用于新文件的大块空间，可以搜索位图的基于大小的树表示来找到用于该大块空间的连续区块范围。倘若搜索不能识别到完美匹配，在一个实施例中，可以对相同的树或不同的树执行使用不同搜索标准的第二搜索。例如，如果针对大块空间搜索基于位置的树并不能得到匹配，则可以基于所需大小(例如，有能力容纳所需大小的最小区块数量)来执行后续搜索以识别一个或多个区块片段。在一个实施例中，可以根据基于相对于文件的现有的分配区块位置在配置阈值(例如，4个区块)以内的附近位置的搜索标准来执行另一个搜索。搜索标准可以包括用于识别位于文件附近并且对于所需大小来说足够
9、大的可用区块范围的最少区块数量。多次搜索的结果可以被组合到一起来得到使盘碎片最少的最佳区块分配。在一些实施例中,可以按照需要根据惰性机制(lazy mechanism)来构建存储器中所维护的用于表示盘中所保持的位图的一个或多个红黑树，以节省存储和/或提供更快的分配响应。因此，当文件系统执行分配/释放存储空间的操作时，每个树可以随之递增地增长。当树被完全填充时，该树可完整地表示盘中的位图。在一个实施例中，可以在系统启动期间构建红黑树，而不会导致额外成本，使得当系统启动时，位图表不可以被加载到存储器中。通常，位图的树表不可被保持在存储器中，而并非被存储在盘中。在盘中的位图改变之前或之后，可以在文件
10、系统中执行对位图的树 表示的更新。图I是示出用于搜索位图的树表示以分配区块的系统的一个实施例的框图。在一个实施例中，系统100可以包括具有在操作系统中的文件系统107的计算机操作环境105。存储设备101可以是本地或远程耦接至系统101的一个或多个存储装置，诸如硬盘、闪存或其它大容量存储介质。在一个实施例中，系统100中的文件可以被存储在存储设备101中所分配的一个或多个区块中。存储设备101可以包括位图103，该位图使用位来表示每个所分配区块的可用性(例如，使用0/1作为状态值来指示区块是空闲的/已分配的)。在一个实施例中，文件系统107可以包括接口模块119，该接口模块用于例如经由API
11、(应用程序编程接口)从运行时程序121接收文件访问(读/写)请求。文件管理模块117可以针对接收到的文件访问请求，确定文件访问操作，诸如文件读取、文件写入、文件创建、文件删除等。例如，文件管理模块117可以向盘区块分配模块115发送存储分配请求，以创建新文件和/或存储/更新文件的数据。在一个实施例中，文件系统107可以包括针对位图103的存储表示(如位置树111或范围树(extent tree) 113)中的一个或多个存储表示的位图表示109。存储表示中的每个可对应于位图103的至少一部分。例如，位置树111和/或范围树113中的每个节点可以包括与在位图103中示作可用的一个或多个连续区块(或
12、范围)对应的位置和/或大小信肩、O在一个实施例中，位图表示管理模块123可以与存储设备101中的位图103同步地构建和/或维护存储器中的位图表示109。例如，当直接在位图103上执行搜索时，位图表示管理模块123可以访问加载在存储器中的位图103的一部分。可替代地，当位图103被更新时，位图表示管理模块123可以接收更新通知。文件系统107可以包括盘区块分配模块115，用于在不访问存储设备101中的位图103的情况下，根据位图表示109来分配存储设备101中的区块以供存储文件内容。盘区块分配模块115可以判定存储设备103中哪些块是可用的，并且例如响应于针对文件的分配请求，选择大得足以容纳待存
13、储数据量的一个或多个可用区块。在一个实施例中，盘区块分配模块115可以访问存储器中的位图表不109中的一个或多个树和/或存储设备101中的位图103，以识别待分配的可用区块。例如，响应于分配请求，根据例如所述请求的一个或多个特性，诸如是否存在与请求相关联的文件，盘区块分配模块115可以动态地确定搜索位图表示109中的各个树以识别供分配的可用区块的次序(例如，对于将数据写入现有文件，从位置树111开始)。盘区块分配模块115可在必要时(例如，如果经由位图表示109并没有找到期望区块)，直接搜索位图 103。在一个实施例中，位图表示管理模块123可以在盘区块分配模块115访问位图103的同时构建位
14、图表不109。例如,盘区块分配模块115可以将位图103的一部分加载到存储器中，以更新位图103进行区块分配或者搜索待分配的可用区块。位图表示管理模块123可以构建在位图表示109中，其中，来自位图103的一部分的区块分配状态已加载在存储器中。在一个实施例中，盘区块分配模块115可以判定位图表示管理模块123何时访问位图103以更新和/或构建位图表示109。图2是示出用于表示位图的示例性红黑树的样品图。示例200可以基于如在图I的系统100中那样的文件系统，该文件系统维护一个或多个树来表示用 于分配文件存储空间的区块的位图。在一个实施例中，位图201可包括用于指示存储装置中区块的分配状态的位阵
15、列，如图I的存储设备101中那样的位图103。每个位都可以指示对应的区块是否可用。例如，对于已被占用的区块，位207可以具有值O。在一个实施例中，位置树203和范围树205可以存储在存储器中，如图I的位图表示109中那样，用于表示位图201的部分。树203、205可以基于作为底层数据结构的自平衡二叉搜索树，以允许对树进行有效的更新操作，如，搜索、删除、插入等。例如，树203、205可以是使用红黑树更新操作来确保树达到适度平衡的红黑树。位置树203可以基于红黑树结构(或树表示)而由表示位图201中所指示的可用区块的节点构成，其中红黑树结构(或树表示)包括节点的键值(key)。在一个实施例中，可以
16、根据连续可用区块或可用区块范围的起始位置，来设置位置树203的键值。例如，节点209可以包括位置键值3，位置键值3对应于5个可用连续区块(例如由位207和位213之间的5个位表示)的起始块(例如由位207表示)的位置。节点209可以包括指示连续区块大小的大小键值。在一个实施例中，范围树205可以基于红黑树结构由表示位图201中指示的可用区块的节点构成，其中使用连续可用区块的大小作为键值。例如，节点211可以包括大小键值5，其对应于5个连续可用区块(例如，用位207和位213之间的5个位表示)。节点211可包括位置键值(例如，3)，用于表示与位图201的位207 (第三个位)对应的起始块。图3是示出在不搜索位图的情况下识别供分配的可用区块的处理的一个实施例的流程图。示例性处理300可以由可包括硬件(电路、专用逻辑等)、软件(诸如在专用机上运行的软件)或这两者的组合的处理逻辑来执行。例如，可由图I的系统100的一些组件执行处理300。在方框301中，处理300的处理逻辑可以在存储器中构建一个或多个树表不，如图I的树111、113，以表示维
