Patent Description:
Computers are used to store and organize data. Stored data may be structured and managed with many objectives, some conflicting. For example, data may be structured and managed for reliability and integrity, efficient reading and writing, efficient searching, minimal waste of the underlying storage, ease of management, minimal computational overhead, and so forth. The particular algorithms and strategies that may be used to structure and manage any particular data often depend on which of these objectives are most important for the use of that data. As discussed below, algorithms and techniques that can improve any of these objectives without significantly undermining other objectives are desirable. Before discussing some shortcomings and improvements in the field of structured data storage, some terminology will be established.

A common data storage scenario involves a storage system layering structured data on an underlying block-based storage unit. There are many kinds of block-based storage units. For instance, disk drives, logical and physical file system volumes, memory, virtualized storage devices, database page files, block-based cloud storage systems, and so forth. Block-based storage units are referred to herein as "storage units", with the understanding that the term refers to any type of discrete unit of storage, physical or virtual, that is able to store structured data within its discrete blocks, pages, clusters, or other generally segmented into uniform sub-units of storage, which will be referred to herein as "blocks". Usually, the blocks of a storage unit are contiguous, their size is aligned with the size of their storage unit, and they are discretely written to and read from their storage unit. Note that a block can also be a byte of a byte-addressable storage (DAX).

The term "storage system" is used herein to refer to any computer-executable system that organizes and manages structured data ("data") within the blocks of a storage unit, where the data is structured for retrieval, updating, deletion, etc., by the storage system. "Structured data" will refer to the data abstraction provided by a storage system and layered on top of a storage unit. Typically, structured data is stored in objects (data types, items, sub-structures, etc.) defined and implemented by the storage system. Objects typically store data that is passed into the storage system (e.g., "user data" or "client data") as well as management metadata generated and used by the storage system. A storage system usually maintains "storage metadata" on a storage unit to logically arrange the storage unit's objects and perhaps track properties of the objects (i.e., object metadata). Storage systems also store and manage global metadata for a storage unit. A storage unit's global metadata may include data about the storage unit itself, for instance its size (or location and extent), layout, block size, properties, access credentials or keys, global information about the structured data per se, and so forth. For efficiency, global and storage metadata (collectively, "metadata") are often stored in trees. Often, a root piece of global metadata points to other units of global metadata.

File systems are one type of structured data. In terms of file systems, a file system manager is an example of a storage manager. A volume, whether physical or logical, is an example of a storage unit consisting of blocks (i.e., nodes, clusters, etc.). A file system is an example of structured data managed by a file system manager, which is usually included as part of the storage stack of an operating system. Objects of a file system typically include files, directories, links, access control lists, and others. Storage metadata provides the hierarchical structure of a file system. Global metadata of a file system or volume may include information about which blocks are allocated, counts of references to objects in the file system, the number of blocks and their size, properties of the volume, etc. All of this file system information is overlaid on the blocks of the volume and is managed by the file system manager.

Databases are another type of structured data. In terms of databases, a database engine is an example of storage system. A page file consisting of pages (i.e., blocks) is an example of a storage unit managed by a database engine. A database is an example of structured data overlaid on the pages of the page file, and the objects of a database typically consist of tables, records, indexes, schemas, security information. Global metadata may include information about which pages are allocated, which objects are stored at which locations of which pages, and so forth.

With this terminology in mind, consider that most storage systems allow updating of their structured data; they enable objects to be added, removed, and modified. Therefore, most storage systems have some mechanism for, for a given storage unit, tracking which blocks of the storage unit are currently allocated, i.e., which blocks are in use to store global metadata, storage metadata, objects, object metadata, or any other information. Because allocating blocks, deallocating blocks, and querying for block allocation states are frequent operations of storage systems, a storage system's performance may be limited by how quickly these allocation operations can be performed. For speed, storage systems generally use some form of index (a type of global metadata) to track block allocation states. Recently, trees such as B-trees and B+ trees have been favored due in part to their fast search times and other advantages. In any case, often, the more efficient an index, the more vulnerable the index may be to corruption. For some types of indexes, one erroneous bit might cause a storage system to consider an entire corresponding storage unit to be corrupt and unusable. Described below are techniques for detecting corruption in allocation indexes and repairing corrupt allocation indexes while the related structured data and storage unit remain online and continues to be made available by the corresponding storage system.

Many storage systems also track how many references are currently active for the objects in a storage unit. For instance, a file system may have a tree of reference counts maintained by a file system manager to track how many references are active for objects in the file system. Described below are techniques for monitoring the integrity of global reference counts while corresponding structured data remains online, and, while the structured data remains online, repairing the reference counts in a way that allows the structured data to remain online.

Other techniques for improving the availability and robustness of structured data, in particular storage metadata and global metadata are also described below. <CIT> teaches a hierarchical compression tester and associated method stored in a computer readable medium that employs a grid-based storage capacity wherein a storage unit is defined by a grouping of data blocks.

<CIT> teaches data storage techniques. One example can buffer write commands and cause the write commands to be committed to storage in flush epoch order. Another example can maintain a persistent log of write commands that are arranged in the persistent log in flush epoch order. Both examples may provide a prefix consistent state in the event of a crash.

<CIT> teaches that a file system that enables the real-time correction of detected corruptions to on-disk data. An enhancement to a file system responds in real time to file system corruptions detected on a running volume, and repairs the corruptions at the point where the file system detects them.

<CIT> teaches pruning previously-allocated free blocks from a synthetic backup. In one example embodiment, a method of pruning previously-allocated free blocks from a synthetic backup includes identifying multiple sequential backups to be included in a synthetic backup, accessing a copy of a file system block allocation map (FSBAM) of the most recent of the multiple sequential backups that was stored with the most recent backup, identifying a set of blocks that includes the most recent block for each unique block position contained within the multiple sequential backups, pruning the set of blocks to exclude all blocks that are identified as being free in the FSBAM, storing the pruned set of blocks in the synthetic backup, and storing a copy of the FSBAM with the synthetic backup.

<CIT> teaches a mechanism that allows a file system to handle corrupted file system metadata in a way that provides high availability. When corrupted metadata is detected, the corrupted metadata may be deleted while the file system remains online and available to service file input/output operations that involve non-corrupted metadata.

The following summary is included only to introduce some concepts discussed in the Detailed Description below. This summary is not comprehensive and is not intended to delineate the scope of the claimed subject matter, which is set forth by the claims presented at the end.

Examples described herein relate to testing the integrity of a storage system's metadata while corresponding structured data remains online. Examples also relate to enabling corrupt storage system metadata to be repaired while the metadata remains in use and while its structured data remains online. Corruption detection and repair is described with respect to allocation metadata and reference count metadata. The examples are applicable to many types of storage systems, including file systems and databases, for example.

Many of the attendant features will be explained below with reference to the following detailed description considered in connection with the accompanying drawings.

The present description will be better understood from the following detailed description read in light of the accompanying drawings, wherein like reference numerals are used to designate like parts in the accompanying description. <FIG> is not according to the invention and is present for illustration purposes only.

<FIG> shows an example storage system <NUM>. The storage system <NUM> controls and accesses a block-based storage unit <NUM>, which is segmented into blocks <NUM>. Generally, the storage system <NUM> communicates with the storage unit <NUM> by passing in entire blocks <NUM> to be written and by requesting and receiving entire blocks <NUM> read from the storage unit <NUM>. Blocks may be tracked by identifiers, offsets, etc. For discussion, blocks will be considered to have unique identifiers in a range or namespace (or key space) that fully describes the blocks of the storage unit <NUM>. However, any scheme for block identification can be used.

The storage system <NUM> uses the blocks <NUM> as a coarse unit of storage, and manages storage of more granular independently structured data <NUM> within the blocks <NUM>. Typically, the overlay of structured data <NUM> starts with global metadata <NUM> that the storage manager <NUM> is configured to read and interpret. As noted above, the global metadata <NUM> might include information about the structured data <NUM> as a whole, information about the storage unit <NUM> such as sizes of blocks, overall size or number of blocks, layout, amounts of free and used space, sub-units of global metadata (or pointers thereto) such as an allocation tree/index or reference count tree. Global metadata <NUM> might also point to storage metadata <NUM> that organizes the structured data <NUM>, for instance, by indicating locations of objects <NUM> managed by the storage system <NUM>, relationships between the objects <NUM>, perhaps locations of properties of the objects, and so forth. In short, the structured data <NUM> including objects <NUM> and storage metadata <NUM> are used by the storage manager <NUM> to manage the "user" data (content) stored in the storage unit <NUM>, and the global metadata <NUM> is used to maintain related global information. As will be seen, there are usually some functional relationships between the global metadata and the structured data.

The storage system <NUM> may include a storage allocator <NUM> and a structured data manager <NUM>. The structured data manager <NUM> ("data manager") is the primary logic of the storage system <NUM> and provides a level of data abstraction atop the blocks <NUM> of the storage unit. The data manager <NUM> is configured with logic to interpret the storage metadata <NUM> and objects <NUM> and structure the structured data while handling requests from clients, applications or other entities <NUM> that interface with the storage system <NUM>. Typically, clients issue, via a corresponding application programming interface (API) of the storage system <NUM>, requests <NUM> directed to one or more of the objects <NUM>. Requests <NUM> might be for updating the content of obj ects, deleting obj ects, reading the content of an object, reading or modifying the properties of an object, querying object metadata and global metadata (e.g., how much space is free on the storage unit <NUM>), moving objects, creating new objects, and so forth. The data manager <NUM> translates between the high level requests <NUM> and the lower-level data stored in the blocks <NUM>, and updates the objects <NUM>, storage metadata <NUM>, and global metadata <NUM> by reading and updating blocks <NUM>. The data manager <NUM> returns responses <NUM> such as indications of success or failure, requested data such as objects <NUM> or properties thereof, etc..

The allocator <NUM> performs block allocation functions for the storage system <NUM>, and in particular for the data manager <NUM>. The allocator <NUM> accesses and maintains a unit of global metadata that will be referred to as an allocation map <NUM> (or, "allocation index"). The allocation map <NUM> can be accessed either by finding the location of its root in the global metadata <NUM>, or by accessing a pre-defined location of the storage unit <NUM>. The allocation map <NUM>, is used to store the global allocation state, that is, information indicating which of the blocks <NUM> are logically considered to be in use (allocated) which and which blocks are logically considered to be available for use (not allocated).

It should be noted that implementation of the allocator <NUM> and data manager <NUM> as distinct components of the storage system <NUM> is a design convenience and is not significant for operation of the storage system <NUM>, whose functions can be organized in many ways. Moreover, as noted above, the storage system <NUM> can be a file system manager, a database engine, or any other of type of data abstraction layer. The objects <NUM> might be files, directories, records, tables, etc..

<FIG> shows how an allocation map or index can be implemented as a sparse data structure. In <FIG>, the keys <NUM> are generic elements in an address space or namespace. For example, the keys could be block numbers or identifiers, page numbers, offsets (in bytes) from the start of the corresponding storage unit (i.e., byte addresses), block extents, or any other type of information that can be used to represent and identify all of the blocks in the relevant storage unit. A sparse map is one in which keys that are not explicitly stored in the map or index are logically treated as present in the map. In the example of <FIG>, blocks <NUM>, <NUM>, and <NUM> do not have keys in the allocation map <NUM> and are therefore considered to be implicitly indicated (through their absence) as "allocated". If the map is searched for a key and the key is not found, key is treated by the storage system as being "present" in the map.

<FIG> shows a process for searching a sparse allocation map. If at step <NUM> the allocator <NUM> receives a query for keyN for example, at step <NUM> the allocator <NUM> searches the allocation map <NUM> for keyN, perhaps traversing a search tree or other type of data structure until the search algorithm determines whether keyN is present in the allocation map <NUM>. If the search key keyN was found, then at step <NUM> the allocator <NUM> returns an indication that the corresponding block is not allocated (or alternatively, the allocation state of the block may depend on a value associated with keyN, such as a bit in a bitmap). If the search key keyN was not found, then at step <NUM> the allocator <NUM> returns an indication that the corresponding block is already allocated. In sum, the idea of a sparse search index is that keys not explicitly represented in the index are considered to be present in the index, which, among other benefits discussed below, results in a more compact index.

<FIG> shows an example sparse B+ tree 124A for implementing an allocation map or index. The namespace (or key space) of the example in <FIG> is represented as a combination of keys and bit numbers. Each key/leaf represents a chunk of blocks and stores a bitmap whose bits respectively represent the allocation states of the respective blocks in the chunk. In the example of <FIG>, each chunk is <NUM> blocks/bits. Each key-bit combination is a unique entry (block number) in the namespace of all of the blocks in the corresponding storage unit. In the example of <FIG>, assuming zero-based indexing, the 4th bit (bit #<NUM>) in the bitmap of key <NUM> represents block number <NUM>; ((<NUM>-<NUM>)*<NUM>)+(<NUM>).

B+ trees are well-known data structures, and algorithms for constructing and maintaining non-sparse B+ trees are known and, as described herein, can be adapted to implement sparse B+ trees. The sparse B+ tree 124A is searched in the same way other B+ trees are searched. Assuming that the presence of block number <NUM> is being queried, the bitmap for block number <NUM> would be stored at a leaf having key <NUM>. Starting at the root node (possibly found by reading a piece of global metadata <NUM>), key <NUM> is compared with the key values <NUM> and <NUM> in the root node to select which child node to search. Since <NUM> is less than key value <NUM> in the root node, the child to the "left" <NUM> in the root node is followed and node A is then searched. Since the search key <NUM> is between key values <NUM> and <NUM> in node A, the middle child - node E - is then searched and key <NUM> is found. The bitmap of key <NUM> is read and the 4th bit is found to be " <NUM>", indicating that block number <NUM> is currently allocated. If block number <NUM> had been searched, the 3rd bit in key <NUM>'s bitmap is "<NUM>", and block number <NUM> would be treated as not currently allocated. If a leaf key or node's bitmap reaches a state indicating that all corresponding blocks are allocated, then the key or node is deleted, as indicated by node F.

Other addressing schemes can be used in conjunction with a search tree. For example, as shown in <FIG>, leafs can store extents rather than bitmaps. Node D in <FIG> has the same information as node D in <FIG>, but the bits set to "<NUM>" are described by extents rather than bitmaps. Each extent represents a run of allocated blocks. Linked lists might also be used to represent blocks. For ease of discussion, repair techniques will be described with reference to generic "keys" with the understanding that keys map to individual blocks. Extents, bit numbers, or other fine-grained block-identifying information may be assumed. In another example, each block number is represented as a complete key in a B+ tree leaf.

<FIG> shows how integrity values of an allocation map can be calculated and used to detect data corruption. As shown in <FIG>, integrity values can be stored for each element of an allocation map/index, or for any arbitrary portions of an allocation map. For discussion, checksums, in particular cyclic redundancy checks (CRCs) will be used as exemplary integrity values. However, other types of integrity code can be used, for example error correction codes, hash functions, and others.

Each integrity value, denoted as CRCN in <FIG>, corresponds to a different portion of the allocation map. In the case of a B+ tree, each tree node has a CRC that is computed over the node and is stored in its parent node. Each node stores the CRCs of its children nodes in association therewith. For other types of allocation maps or indexes, different sub-units thereof may be checksummed in any way that covers the structural and substantive content of the allocation map. The CRC of a node may be computed for the entire content of the node, including at least its child pointers, keys, and in the case of leaf nodes, its substantive content (items). The integrity values are kept current as the B+ tree is updated. For instance, if a bit is changed in the bitmap of key <NUM>, then the CRC for node E (CRCE) is recomputed and is stored in parent node A. Because node A has changed (new value of CRCE), CRCA must also be recomputed, and so on up to the root node. CRCs must similarly be recomputed when nodes are added, removed, updated, merged, split, etc.; any change to the content of a node results in recomputation of the affected CRCs.

Returning to <FIG>, when the allocation map is to be searched for some key K, at step <NUM> the root node's integrity is tested. The CRC of the root node may be stored in a separate item of global metadata (CRCN in <FIG>). The current CRC of the root node is computed and compared to the stored root CRCN, and if they are equal the search proceeds as normal by, at step <NUM>, selecting the appropriate child node for the key K (e.g., node A). At step <NUM> the integrity of the selected child/intermediate node is checked by computing the CRC of the child node and comparing it to the CRC stored in the parent/root node (e.g., CRCA). This checking continues recursively until at step <NUM> a leaf node is determined to not exist for key K, in which case the search returns an indication that key K is present. If a leaf node does contain Key K, then the integrity of the leaf node is similarly checked.

In another example, an additional global structure is maintained to track which blocks in a storage unit have integrity values (e.g., checksums) and which do not. Such a checksum structure has similar sparse-representation behavior as the sparse allocation maps described herein, in that a missing range implies that all of the blocks in the missing range have checksums. Although the data represented/indexed differs, the same techniques described herein for implementing a sparse allocation map may be used to implement a sparse checksum map or index. In one example, blocks can be allocated but have no checksums, though if a block has checksums it must also be allocated.

<FIG> shows how an allocation map <NUM>/124B of a storage unit can be repaired while remaining in use for servicing an online storage unit. The process of <FIG> may be performed by a storage system. The allocation functions discussed with reference to <FIG> may be related to allocations for any type of data to be stored or queried, including global metadata, user data, structured data objects, storage metadata, or any other allocation request by the storage system.

At step <NUM> there is a determination that a portion of the allocation map is corrupt (bold portion of the allocation map <NUM>). The portion may be identified by any information, such as inconsistent or erroneous structure of the allocation map, failure of the backing media, failure of an integrity value, etc. In the case of a search tree, a corrupt sub-tree might be detected, as explained above. Any indication that a sub-space of the index/name space is corrupt is sufficient.

At step <NUM>, the allocation map <NUM> is modified or supplemented (allocation map 124B) to indicate that the corrupt portion is allocated. That is, in any way suitable for the type of allocation map being used, the blocks represented by the corrupt portion of the allocation map are taken out of the pool of blocks considered to be unallocated. For a sparse type of allocation map, where keys that are not present in the map are logically treated as allocated, step <NUM> can involve merely logically deleting any keys (or key range/extent) in the corrupt portion. If a B+ tree is used, then the corrupt node may be deleted or flagged. If the node is an intermediary node, then the sub-tree of which it is the root is naturally deleted and the corresponding part of the namespace associated with the corrupt node becomes effectively allocated. In the example of <FIG>, the portion of the allocation map from key1 to key3 would be deleted. Or, for the example shown in <FIG>, if node A were found to be corrupt, it would be deleted, and then all of the keys for node A's key space - <NUM> to <NUM> per the root node - would be considered to be allocated. All of the blocks represented by the bitmaps in nodes D and E, including those previously set to "<NUM>" (free) would all become implicitly allocated. Because a portion of the allocation map is corrupt, it may not be possible to know exactly which keys are affected, so in practice, all keys potentially present in the corrupt portion are to be considered as allocated. A corrupt portion may be a range of all keys from the lowest possible corrupt key to the highest possible corrupt key (e.g., the range of the keys in a B+ tree node).

To track the corrupt portion of the allocation map for later off-line reconstruction, the parent node of the deleted node may be updated with a marker to indicate that the child node was deleted. For example, in <FIG>, the child pointer for node A could be changed from pointing to node A (a location of node A) to having a pre-defined value such as null, -<NUM>, etc., which by convention indicates a corrupt child. Such a marker can be detected when an off-line repair process walks the allocation tree, which in turn can trigger an off-line re-build of the allocation map. Alternatively, a flag in the relevant global metadata can be set to indicate that the allocation map is in need of repair, and when the storage unit is offline a repair can be undertaken.

If a non-sparse allocation map is being used and explicit allocations are tracked (non-allocated blocks are not described in the map), other modifications can be used. For instance, the corrupt range can be marked as reserved (no new allocations can be granted), or, as another form of reservation, the state can be overwritten in-place to make it consistent. These operations can be performed either directly, on top of the structure, or stored in other structures which would are used as indirection layers. However, because the allocation map is known to be corrupt, any technique to repair the allocation map should avoid a need to allocate blocks, since a block storing data might be erroneously allocated for the repair; actual data in the block could be over-written. For example, a portion of the relevant storage unit can be reserved (pre-allocated) for the purpose of tracking allocation map corruptions. This technique can also be used for sparse allocation maps, and can allow a record of the corrupt portion of the allocation map to be stored and later used for off-line repair of the allocation map by using metadata to reconstruct the underlying data and identify the blocks that it is stored on. For instance, if the storage system is a file system manager, then the file system can be reconstructed in a read-only mode to identify all of the allocated blocks and capture that into a new allocation map.

At step <NUM>, while the relevant storage unit and its structured data remains online, the modified or supplemented allocation map 124B continues to be used. At step <NUM>, if the allocator <NUM> receives a request for a block allocation, a key/block from the non-corrupt portion of the modified/supplemented allocation map 124B is selected and then marked as allocated (e.g., key0). If the allocator receives a query about key5, the allocator answers that key5 is allocated. If the allocator receives a query about key6, the allocator indicates that key6 is not allocated. Thus, even though the modified/supplemented allocation map 124B is corrupt, it continues to be fully functional. At step <NUM>, if allocation of key3 is requested, the allocator denies the request, even though, prior to the corruption, key3 had been unallocated. As can be seen, treating a portion of the allocation map <NUM>/124B as being allocated due to its having been corrupted may take some empty blocks out of circulation but it also allows an online repair to keep the allocation map in service.

Moreover, any type of allocation map may be used. Sparse indexes will be convenient to use. When an allocation map is implemented in a way in which portions of the allocation map are considered to be implicitly allocated, then it becomes possible to prune part of the allocation map. In short, when a portion of the allocation map is found to be corrupt, the corrupt portion is updated or supplemented so that the affected portion of the allocation map effectively becomes protected from being newly allocated.

<FIG> shows another allocation map repair process. The processes in <FIG> may be performed while the relevant storage unit remains online. For instance, a file system or database may be online throughout all of the steps shown in <FIG>. When the allocator <NUM> receives a request to update a given key, at step <NUM> a checksum mismatch is detected while searching the allocation map. A repair process <NUM> is invoked, and, depending on the result and the type of update, at step <NUM> success or failure is returned. The repair process <NUM> may include an initial step <NUM> of seeking a copy of the corrupt portion of the allocation map. For instance, a mirror or RAID drive, a backup, a checkpoint, or any other source storing a copy of the corrupt portion can be accessed and used to overwrite the corrupt portion of the allocation map. If this is successful, then the update operation is allowed to proceed as normal and success is returned. However, if no backup data is available, then at step <NUM> any of the previously described techniques for isolating the corrupt portion of the allocation map are used. At step <NUM> the integrity values are updated, if needed. If the update was to set a key to "allocated" (" <NUM>"), then the update request can be answered at step <NUM> as true/successful.

Similarly, if the allocator <NUM> receives a request at step <NUM> to query a key, and corruption is detected, then the same repair process <NUM> is invoked. At step <NUM>, if the copy-based repair at step <NUM> was successful, then the return value depends on the key's value in the copy. If the copy-based repair at step <NUM> was not successful, then in accordance with the repair step of causing the corrupt portion of the allocation map to be all "allocated", the query is answered as "true", i.e., the queried key/block is treated as allocated, regardless of the pre-corruption ground-truth state of the key/block.

<FIG> also shows a monitor process <NUM>. Although it is possible to check the integrity of the allocation map during ordinary allocation-related operations directed to the allocation map, alternatively or additionally, integrity-checking scans can be performed independent of allocation-related activity by scanning the allocation map (e.g., walking a B+ tree). At step <NUM> the allocation map is traversed. At step <NUM>, if a corruption is found, the repair process <NUM> is invoked.

In one example, it might be useful to use some of the global metadata to help update a sparse allocation map. The global metadata might indicate the size of the relevant storage unit or volume. As such, when the allocation map is found to be corrupt, the global metadata can be used to understand what the complete namespace is for the allocation map. That is, the range of the allocation namespace can be derived from the global metadata. Thus, if there is corruption near the upper bound of the allocation namespace, the allocation map can be updated to indicate that blocks from the lowest point of the corruption up to the maximum block name or key is in an allocated state.

In general, any data that a storage system can use that contains partial or complete (redundant) information about another global structure can be used to fix identified corruption. The type of data (or partial information) used will depend on the particular storage system. In the case of an allocator, there may be another table, such as a container table, that stores how many blocks are allocated in a given region of the relevant storage unit. If the container table states that all clusters are free within a given region, then there is no need to "leak" the space in that region of the allocator, everything in the corrupt range can be essentially marked as allocated, except for the range described as entirely free in the container table.

For counting to blocks (reference counting in general is discussed next), if a region is corrupt, the entire region can be described as having a maximum reference count. However, it may be known that individual subranges within the corrupt range are marked as free in the allocator, in which case a reference count of zero can be stored for the ranges and the maximum reference count can be set only for the ones that are marked as allocated in the allocator structure.

In some cases the entire structure can be rebuilt with minimal or no additional information, if the end state of the system remains consistent. For example, if a table which stores the last mount time and a few additional volume-specific parameters (e.g. enable/disable certain features), if the structure becomes corrupt, it can be recreated and populated with default values, potentially losing the original semantic, but keeping the volume online.

These are just a few examples of how the efficiency/quality of a repair can be improved when additional information can be derived from other structures.

<FIG> shows a repair technique for handling a corrupt reference count tree <NUM>. Many storage systems keep track of how many references are currently open for stored objects. For example, for a file system, the number of references to respective files may be tracked. If the storage system is a database, the reference counts may be tracked for references to tables, records, or other objects. Reference counts may be stored in a separate tree or data structure, or in the storage metadata that organizes the referenced objects (e.g., a file system tree). Any of the corruption detection techniques described above may be used. At step <NUM> a corruption in the reference count data is detected. At step <NUM> the reference counts in the affected portion are all set to a maximum reference count value, and at step <NUM> the reference count data is flagged for later offline repair.

If a non-sparse reference count data structure is used, for instance a B+ tree, where only the blocks, objects, files, etc. that have active references are represented, repair may require that the entire potentially corrupted portion of the reference count namespace be updated. That is, if a node is found to be corrupt, because the entire node's sub-tree must be considered corrupt, it may not be sufficient to merely update existing nodes. Rather, the maximal range of potential corruption is determined, and the reference count tree <NUM> is updated to explicitly add representation for the relevant range of key space corruption. New nodes may need to be inserted with values that fill out the corrupt range such that each key in the corrupt range has a maximum reference count.

Returning to <FIG>, once the reference count tree <NUM> is repaired, some reference-count related operations may proceed normally or with results that are helpful for requestors. For example, if at step <NUM> a client requests a new reference, then at step <NUM> the storage system determines that the maximum references have been reached and denies the request for a new reference. Although some functionality may be lost, the relevant storage unit continues to be available. If, at step <NUM>, a client requests that a particular key's reference count be decremented, for instance when closing a file descriptor, then the system is able to safely decrement the reference count and at step <NUM> inform the client that the request was completed.

Although reference counts to file system objects have been described above, the same techniques can readily be extended to counting references to blocks of a file system.

<FIG> shows details of a computing device <NUM> on which embodiments described above may be implemented. The technical disclosures herein constitute sufficient information for programmers to write software, and/or configure reconfigurable processing hardware (e.g., FPGAs), and/or design application-specific integrated circuits (ASICs), etc., to run on one or more of the computing devices <NUM> to implement any of features or embodiments described in the technical disclosures herein.

The computing device <NUM> may have a display <NUM>, a network interface <NUM>, as well as storage hardware <NUM> and processing hardware <NUM>, which may be a combination of any one or more: central processing units, graphics processing units, analog-to-digital converters, bus chips, FPGAs, ASICs, Application-specific Standard Products (ASSPs), or Complex Programmable Logic Devices (CPLDs), etc. The storage hardware <NUM> may be any combination of magnetic storage, static memory, volatile memory, non-volatile memory, optically or magnetically readable matter, etc. The meaning of the term "storage", as used herein does not refer to signals or energy per se, but rather refers to physical apparatuses and states of matter. The hardware elements of the computing device <NUM> may cooperate in ways well understood in the art of computing. In addition, input devices may be integrated with or in communication with the computing device <NUM>. The computing device <NUM> may have any form factor or may be used in any type of encompassing device. The computing device <NUM> may be in the form of a handheld device such as a smartphone, a tablet computer, a gaming device, a server, a rack-mounted or backplaned computer-on-a-board, a system-on-a-chip, or others.

Claim 1:
A method performed by processing hardware (<NUM>) and storage hardware (<NUM>), the method comprising:
executing a storage system (<NUM>) that manages structured data (<NUM>) layered on a block-based storage unit (<NUM>), the structured data stored in blocks (<NUM>) of the storage unit, the managing including maintaining a map (<NUM>) in one or more of the blocks of the storage unit to track which of the blocks currently have an allocated state for the structured data;
while the storage unit is online and while the structured data is online and accessible via the storage system, determining (<NUM>, <NUM>, <NUM>, <NUM>) that a portion of the map representing blocks considered to be unallocated is corrupt, and based on the determination that the portion of the map representing blocks considered to be unallocated is corrupt, while the storage unit and structured data remain accessible via the storage system, updating (<NUM>) the map to indicate that blocks corresponding to the corrupt portion of the map currently have the allocated state, such that they are taken out of a pool of blocks considered to be unallocated; and
while the storage unit and structured data continue to be online and accessible via the storage system, in response to receiving a request for a block allocation, using (<NUM>) the map to deny (<NUM>) the request for block allocation of blocks of the storage unit which have the allocated state and to grant (<NUM>) the request for block allocation of blocks of the storage unit which do not have the allocated state and updating the map to indicate that the blocks of the storage unit which have been allocated in response to the request have the allocated state while the storage unit and structured data remain online to reflect the allocations.