用于文件系统存储设备的分层分配.pdf

(19)中华人民共和国国家知识产权局(12)发明专利(10)授权公告号(10)授权公告号CNCN102934094102934094B(45)授权公告日2014.12.03(21)申请号201180029558.7(51)Int.Cl.(22)申请日2011.06.03G06F12/02(2006.01)(30)优先权数据(56)对比文件12/816,4192010.06.16USCN1950802A,2007.04.18,说明书第8行-第26行、权利要求1-37、图1-4.(85)PCT国际申请进入国家阶段日CN101488919A,2009.07.22,全文.2012.12.14US6874062B1,2005.03.29,全文.(86)PCT国际申请的申请数据US2008208802A1,2008.08.28,全文.PCT/US2011/0390732011.06.03US2010125583A1,2010.05.20,全文.(87)PCT国际申请的公布数据审查员李强WO2011/159495EN2011.12.22(73)专利权人微软公司地址美国华盛顿州(72)发明人T.J.米勒J.M.卡吉尔W.R.蒂普顿S.费尔马(74)专利代理机构中国专利代理(香港)有限公司72001代理人刘红汪扬权权利要求书2页利要求书2页说明书11页说明书11页附图6页附图6页(54)发明名称用于文件系统存储设备的分层分配(57)摘要在此描述的主题的各方面涉及存储空间分配。在各方面，分层数据结构用于跟踪利用文件系统管理的存储空间的分配数据。分层数据结构可以具有多个级别，其中每个级别具有与不同的存储空间的粒度有关的数据。分层数据结构的各部分可以独立于分层数据结构的其他部分被锁定。分层数据结构可以指示：存储空间的一个或多个部分用于目录的独家使用。在预期后续操作中可以在分配的空间中预留额外空间。分配请求器可以从与分层数据结构的不同级别相关联的区域中获得存储空间分配。CN102934094BCN102934BCN102934094B权利要求书1/2页1.一种至少部分利用计算机实现的用于文件系统存储设备的分层分配的方法，所述方法包括：接收分配利用文件系统管理的存储空间的请求；响应于所述请求，访问包括与存储空间上的分配空间和未分配空间有关的数据的分层数据结构，所述数据指示存储空间的多个区域，所述数据进一步指示在分层数据结构的不同级别上的节点配对之间的关系，其中两个直接相关的节点指示在不同粒度级别上的存储空间中的一些的分配数据，所述数据进一步指示与相同级别的一个或多个节点中的一个相关联的未分配空间的大小以及与所述一个或多个节点中的一个相关联的未分配空间的最大邻近大小；确定用于为所述请求分配空间的分层数据结构的级别；使用所述级别的一个或多个节点来搜索分层数据结构，以查找空闲空间；为所述请求分配空闲空间；更新分层数据结构，以指示空闲空间已被分配，其中：使用所述级别的一个或多个节点来搜索分层数据结构，以查找空闲空间包括：访问与所述一个或多个节点中的一个相关联的未分配空间的大小以及与所述一个或多个节点中的一个相关联的未分配空间的最大邻近大小。2.权利要求1的方法，其中使用所述级别的一个或多个节点来搜索分层数据结构以查找空闲空间包括：访问分层数据结构中的标题和位图，所述标题与一个或多个节点之中的一个节点相关联，所述标题包括一个或多个节点中的所述一个节点的分配单元的分配大小、指示与一个或多个节点中的所述一个节点相对应的存储空间的物理位置的值以及所述位图中比特的数量，所述位图指示与一个或多个节点中的所述一个节点相对应的存储空间的分配状态。3.权利要求2的方法，其中访问标题包括访问所述标题中的附加数据，所述附加数据指示与一个或多个节点中的所述一个节点相关联的未分配空间的大小以及与一个或多个节点中的所述一个节点相关联的未分配空间的最大邻近大小。4.权利要求1的方法，进一步包括：接收指示在存储空间上用于分配空间的期望物理位置的提示，根据与期望物理位置的接近性来搜索分层数据结构以查找所述区域的空闲空间，以及提供与期望物理位置最靠近的空闲空间的指示。5.权利要求1的方法，其中接收分配利用文件系统管理的存储空间的请求包括接收在目录内创建或扩展文件的请求，以及其中为所述请求分配空闲空间包括分配所述目录专用的一个或多个区域中的空闲空间。6.权利要求1的方法，进一步包括：预留附加空闲空间，用于与被分配用于所述请求的空闲空间有关的后续操作。7.权利要求1的方法，其中为所述请求分配空闲空间包括：在分层数据结构的一部分上获取锁定，同时允许在分层数据结构的其他部分上获取其他锁定。8.一种至少部分利用计算机实现的用于文件系统存储设备的分层分配的方法，所述方法包括：接收格式化文件系统的存