Hierarchical allocation for file system storage device

摘要

Aspects of the subject matter described herein relate to storage allocation. In aspects, a hierarchical data structure is used to track allocation data for storage managed by a file system. The hierarchical data structure may have multiple levels with each level having data regarding a different granularity of storage. Portions of the hierarchical data structure may be locked independently of other portions of the hierarchical data structure. The hierarchical data structure may indicate that one or more portions of storage are for exclusive use by a directory. Extra space may be reserved in allocated space in anticipation of subsequent operations. Allocation requestors may obtain storage allocation from regions associated with different levels of the hierarchical data structure.

主权项

1. A method implemented at least in part by a computing device that includes at least one processor and memory, the method comprising:
receiving, by the computing device, a request to allocate storage managed by a file system; accessing, by the computing device in response to the request, a hierarchical data structure that includes data regarding allocated and non-allocated space on the storage, the data indicating a plurality of regions of the storage, the data further indicating relationships between pairs of nodes at different levels of the hierarchical data structure, and where two directly related nodes indicate allocation data for some of the storage at different levels of granularity; determining, by the computing device, a level of the hierarchical data structure for allocating space for the received request; searching, by the computing device, the hierarchical data structure for free space using one or more nodes of the determined level, where the searching comprises searching the hierarchical data structure for nodes of the determined level according to a proximity of regions of the nodes to a desired location on the storage for allocating space; allocating, by the computing device, the free space for the received request; allocating additional space to the level from a node in a higher level, where the allocating the free space comprises allocating at least some of the additional space; and updating, by the computing device, the hierarchical data structure to indicate that the free space has been allocated.