# US 12,182,066 B2 · Namespace salvage in logging-based filesystems

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,182,066 B2
- Document ID: US12182066B2
- Status: Granted
- Kind: B2
- Application number: 18/322,518
- Filed: 2023-05-23
- Published: 2024-11-28
- Granted: 2024-12-31
- Earliest claimed: 2023-05-23
- Assignees: Dell Products L.P.
- Applicants: Dell Products L.P.
- Inventors: Geetha Shendge; Charles Hickey; Dhawal Bhagwat; Ramesh Kannan K
- Web page: https://patentgrep.com/patent/US12182066B2

## CPC

- G06F 16/122: {using management policies (point-in-time backing up or restoration of persistent data G06F11/1446; file migration policies for HSM systems G06F16/185)}
- G06F 11/1435: {using file system or storage system metadata}
- G06F 11/1458: {Management of the backup or restore process}
- G06F 16/128: {Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16)}
- G06F 16/13: File access structures, e.g. distributed indices (arrangements of input from, or output to, record carriers G06F3/06)
- G06F 16/1805: {Append-only file systems, e.g. using logs or journals to store data}
- G06F 2201/84: Using snapshots, i.e. a logical point-in-time copy of the data
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Recovering a namespace held in a tree structure that has been corrupted includes scanning a linear representation of pages belonging to the tree structure to copy out keys from uncorrupted leaf pages into a new tree structure. The scan is repeated over snapshots that have been taken of the tree to find keys that are missing from the new tree structure. Upon finding a missing key in an uncorrupted leaf page of a snapshot, the missing key is copied out into the new tree structure unless the missing key has already been found and copied out from an uncorrupted leaf page of a more recent snapshot taken of the tree structure.

## Claims

### Claim 1

A method comprising:
scanning a linear representation of pages belonging to a tree structure that has been corrupted, the tree structure storing metadata of files managed by a logging-based filesystem, and comprising leaf pages having keys indexing the metadata;
during the scanning, salvaging keys from leaf pages that are not corrupted by copying out the keys from uncorrupted leaf pages into a new tree structure;
retrieving a plurality of snapshots that have been taken of the tree structure;
repeating the scanning using the plurality of snapshots that have been taken of the tree structure to find keys that are missing from the new tree structure;
upon finding a missing key in an uncorrupted leaf page of a snapshot taken of the tree structure, copying out the missing key into the new tree structure unless the missing key has already been found and copied out from an uncorrupted leaf page of a more recent snapshot taken of the tree structure;
wherein the keys comprise a plurality of first keys and a plurality of second keys, each first key indexes an inode of a file, and each second key indexes a name of the file, and the method further comprises: when a first key indexing an inode of a particular file has been found, but a second key indexing a name of the particular file has not been found, generating a new name for the particular file that includes an inode number of the particular file, and a placeholder name;
assigning the new name to the particular file;
reviewing the new tree structure to identify a directory within which the particular file resided at a previous point-in-time; and
placing the particular file having the new name in the identified directory.

### Claim 2 (depends on 1)

The method of claim 1 wherein the new tree structure comprises keys indexing most recent versions of the metadata and keys indexing older versions of the metadata, the keys indexing older versions of the metadata including keys salvaged from different snapshots taken of the tree structure at different points-in-time.

### Claim 3 (depends on 1)

The method of claim 1 wherein the repeating the scanning using the plurality of snapshots that have been taken of the tree structure comprises selecting the snapshots in reverse chronological order.

### Claim 4 (depends on 1)

The method of claim 1 wherein the tree structure comprises intermediate pages referencing the leaf pages and the scanning the linear representation comprises:
skipping the intermediate pages; and
skipping leaf pages that are corrupt.

### Claim 5

A system comprising: a processor; and memory configured to store one or more sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of:
scanning a linear representation of pages belonging to a tree structure that has been corrupted, the tree structure storing metadata of files managed by a logging-based filesystem, and comprising leaf pages having keys indexing the metadata;
during the scanning, salvaging keys from leaf pages that are not corrupted by copying out the keys from uncorrupted leaf pages into a new tree structure;
retrieving a plurality of snapshots that have been taken of the tree structure;
repeating the scanning using the plurality of snapshots that have been taken of the tree structure to find keys that are missing from the new tree structure;
upon finding a missing key in an uncorrupted leaf page of a snapshot taken of the tree structure, copying out the missing key into the new tree structure unless the missing key has already been found and copied out from an uncorrupted leaf page of a more recent snapshot taken of the tree structure;
wherein the keys comprise a plurality of first keys and a plurality of second keys, each first key indexes an inode of a file, and each second key indexes a name of the file, and the processor further carries out the steps of:
when a first key indexing an inode of a particular file has been found, but a second key indexing a name of the particular file has not been found, generating a new name for the particular file that includes an inode number of the particular file, and a placeholder name;
assigning the new name to the particular file;
reviewing the new tree structure to identify a directory within which the particular file resided at a previous point-in-time; and
placing the particular file having the new name in the identified directory.

### Claim 6 (depends on 5)

The system of claim 5 wherein the new tree structure comprises keys indexing most recent versions of the metadata and keys indexing older versions of the metadata, the keys indexing older versions of the metadata including keys salvaged from different snapshots taken of the tree structure at different points-in-time.

### Claim 7 (depends on 5)

The system of claim 5 wherein the repeating the scanning using the plurality of snapshots that have been taken of the tree structure comprises selecting the snapshots in reverse chronological order.

### Claim 8 (depends on 5)

The system of claim 5 wherein the tree structure comprises intermediate pages referencing the leaf pages and the scanning the linear representation comprises:
skipping the intermediate pages; and
skipping leaf pages that are corrupt.

### Claim 9

A computer program product, comprising a non-transitory computer-readable medium having a computer-readable program code embodied therein, the computer-readable program code adapted to be executed by one or more processors to implement a method comprising:
scanning a linear representation of pages belonging to a tree structure that has been corrupted, the tree structure storing metadata of files managed by a logging-based filesystem, and comprising leaf pages having keys indexing the metadata;
during the scanning, salvaging keys from leaf pages that are not corrupted by copying out the keys from uncorrupted leaf pages into a new tree structure;
retrieving a plurality of snapshots that have been taken of the tree structure;
repeating the scanning using the plurality of snapshots that have been taken of the tree structure to find keys that are missing from the new tree structure;
upon finding a missing key in an uncorrupted leaf page of a snapshot taken of the tree structure, copying out the missing key into the new tree structure unless the missing key has already been found and copied out from an uncorrupted leaf page of a more recent snapshot taken of the tree structure;
wherein the keys comprise a plurality of first keys and a plurality of second keys, each first key indexes an inode of a file, and each second key indexes a name of the file, and the method further comprises:
when a first key indexing an inode of a particular file has been found, but a second key indexing a name of the particular file has not been found, generating a new name for the particular file that includes an inode number of the particular file, and a placeholder name;
assigning the new name to the particular file;
reviewing the new tree structure to identify a directory within which the particular file resided at a previous point-in-time; and
placing the particular file having the new name in the identified directory.

### Claim 10 (depends on 9)

The computer program product of claim 9 wherein the new tree structure comprises keys indexing most recent versions of the metadata and keys indexing older versions of the metadata, the keys indexing older versions of the metadata including keys salvaged from different snapshots taken of the tree structure at different points-in-time.

### Claim 11 (depends on 9)

The computer program product of claim 9 wherein the repeating the scanning using the plurality of snapshots that have been taken of the tree structure comprises selecting the snapshots in reverse chronological order.

### Claim 12 (depends on 9)

The computer program product of claim 9 wherein the tree structure comprises intermediate pages referencing the leaf pages and the scanning the linear representation comprises:
skipping the intermediate pages; and
skipping leaf pages that are corrupt.