Microsoft Technology Licensing, LLC

Omar Carey

Rajsekhar Das

Aaron William Ogus

Scott Chao-Chueh Lee

Garret Buban

Vadim Makhervaks

Laura Marie Caulfield

Lee Edward Prewitt

Bryan Stephen Matthew

Ioan Oltean

Madhav Himanshubhai Pandya

Karel Danihelka

A file system volume's space is internally allocated as a set of containers, with each container corresponding to a different subset of storage clusters. The set of containers includes a first container corresponding to a first subset of storage clusters storing first data that is compressed according to a first set of compression attributes, a second container corresponding to a second subset of storage clusters storing second data that is uncompressed, and a third container corresponding to a third subset of storage clusters that are free. Based on determining that the second data of the second container is to be compressed, compressed second data is created based on a second set of compression attributes. The second set of compression attributes is different than the first set of compression attributes. The compressed second data is written to the third subset of storage clusters of the third container.

Container-level management of compressed file system data

A processing system dynamically adjusts the size of root nodes in hierarchical data structures, such as B+ trees. Upon creation, a root node has a predefined initial size. When a request is received to insert a new record, a determination is made as to whether the size of the root node has reached a predefined maximum size. If the root node has not reached the predefined maximum size, the size of the root node is increased to accommodate the new record and the new record is added to the root node. If the root node has reached the predefined maximum size, one or more new child nodes are created, and records are moved from the root node to the new child nodes. The size of the root node is then reduced to a predefined minimum size.

Dynamically resizing root nodes of hierarchical data structures

A dataset is represented by an ordered set of B+ trees, with each snapshot of the dataset being represented by an immutable B+ tree. An ordering of B+ trees in the ordered set logically arranges those B+ trees into layers, with the mutable B+ tree representing the current state of the dataset being logically arranged as an upper layer, and with immutable B+ trees representing snapshots of the dataset being progressively arranged as lower layers with the oldest snapshot being a lowest layer. A snapshot deletion includes merging the snapshot's corresponding B+ tree with its highest neighbor B+ tree.

Managing snapshotting of a dataset using an ordered set of B+ trees

Methods, systems, and computer storage media for providing reduced-latency data operations for data or storage in file systems. The file system implements a set of policies that indicate how data operations are performed. In operation, a request for access to storage of a file system to perform a data operation is received. The file system supports both a bitmap representation and a range-only representation of the storage. A bitmap representation of a region for performing the data operation is communicated because, for certain data operations, the file system operates based on communicating only bitmap representations while restricting access to range-only representations. The range-only representations are a compacted representation of storage of the file system. Based on the bitmap representation of the region, the storage of the file system is accessed. The bitmap representation of the region further includes a bitmap lock that restricts access to storage corresponding to the bitmap representation.

Reduced-latency data operations for files in a file system

Methods, systems, and computer storage media for providing self-healing operations for root corruptions in a file system are provided. While performing file system operations, the root may be inaccessible by the file system engine for executing file system operations. A root becomes inaccessible for performing file system operations when corrupted. A determination is made that the root having a root data region is corrupted and a self-healing operation should be performed. A root-corruption self-healing operation is executed to re-allocate (or recycle) the root data region to the root. The self-healing operation circumvents a copy-on-write policy of the file system to re-allocate the root data region of the root in-place and transform the root from a corrupted root to a recycled root. A file system data operation, such as a data recovery operation or file system management operation (e.g., a file or directory operation) can be performed using the recycled root.

Self-healing operations for root corruption in a file system

A current state of a dataset is represented by a mutable B+ tree, while each snapshot of the dataset is represented by an immutable B+ tree. An ordering of B+ trees in the ordered set logically arranges those B+ trees into layers, with the mutable B+ tree representing the current state of the dataset being logically arranged as an upper layer, and with immutable B+ trees representing snapshots of the dataset being progressively arranged as lower layers with the oldest snapshot being a lowest layer. Each B+ tree stores dataset records with a strong or a weak reference state; strong records are independent of any lower-layer record, while weak records are dependent on at least one lower-layer record. A snapshot deletion includes merging the snapshot's corresponding B+ tree with its highest neighbor B+ tree, including merging overlapping records based on their weak vs. strong reference state.

Methods, systems, and computer storage media for providing data operations using hard links (hard link operations) for files in a file system are provided. Accessing files using hard link operations is based on File_Name-to-File_ID mappings and File_ID-to-File_Object mappings stored in hard link data structures. In operation, a file name for file content is received to perform a data operation. The file content is accessed using the file name. The file name is associated with a hard link data structure having a File_Name-to-File_ID mapping and a File_ID-to-File_Object mapping. The file name is also associated with an alternate file name for the file content. The alternate file name is associated with an alternate hard link data structure having an alternate File_Name-to-File mapping and the File_ID-to-File_Object mapping. The alternate file name is received. The file content is accessed using the alternate file name to perform an alternate data operation on the file content.

Hard link operations for files in a file system

Methods, systems, and computer storage media for providing reduced-latency data operations in a file system. In operation, a request to perform a data operation associated with a B+ table storage of a file system is received. The file system supports the B+ table storage that is accessible using a B+ tree lookup logic for accessing B+ table data and supports a cache storage that is accessible using a cache table lookup logic for accessing cache data in the cache storage. A number of references to the location in the B+ table storage is determined. The location in the B+ table storage is associated with the request to perform the data operation. Based on determining the number of references to the location, a cache storage location to perform the data operation is accessed. The cache storage location is mapped (using the cache table) to the location in the B+ table storage.

Data operations using a cache table in a file system

An append-only streams capability may be implemented that allows the host (e.g., the file system) to determine an optimal stream size based on the data to be stored in that stream. The storage device may expose to the host one or more characteristics of the available streams on the device, including but not limited to the maximum number of inactive and active streams on the device, the erase block size, the maximum number of erase blocks that can be written in parallel, and an optimal write size of the data. Using this information, the host may determine which particular stream offered by the device is best suited for the data to be stored.

Append only streams for storing data on a solid state device

In a hybrid storage device comprising a fast tier and a slow tier, utilization of the fast tier is improved by dividing the fast tier into zones, including a zone for filesystem metadata, a zone for fast data, and a spillover zone for metadata, fast data or a combination thereof. By reducing the size of zones used exclusively for one type of data, while allowing both metadata and fast data to be stored in the spillover zone when necessary, better use of the fast tier is achieved. In another embodiment, a filesystem allocator is passed a policy object from which bands of storage are enumerated. The filesystem allocator iterates over the enumerated bands, searching for space to satisfy the allocation request.

Policy based tiered allocation for hybrid storage devices

A cluster allocation bitmap determines which clusters in a band of storage remain unallocated. However, concurrent access to a cluster allocation bitmap can cause CPU stalls as copies of the cluster allocation bitmap in a CPU's level 1 (L1) cache are invalidated by another CPU allocating from the same bitmap. In one embodiment, cluster allocation bitmaps are divided into L1 cache line sized and aligned chunks. Each core of a multicore CPU is directed at random to allocate space out of a chunk. Because the chunks are L1 cache line aligned, the odds of the same portion of the cluster allocation bitmap being loaded into multiple L1 caches by multiple CPU cores is reduced, reducing the odds of an L1 cache invalidation. The number of CPU cores performing allocations on a given cluster allocation bitmap is limited based on the number of chunks with unallocated space that remain.

Growing community of inventors

Redmond, WA, United States of America

Omar Carey