Storing namespace metadata in a key value store to facilitate space efficient point in time snapshots

Patent metadata

Field	Value
Publication number	US-12455791-B2
Application number	US-202217869507-A
Country	US
Kind code	B2
Filing date	Jul 20, 2022
Priority date	Jul 20, 2022
Publication date	Oct 28, 2025
Grant date	Oct 28, 2025

Abstract

Metadata of a file system is maintained in a key value store. The metadata includes a namespace represented as a B+ tree having pages written to the key value store. Identifiers to the pages include a snapshot identifier and a page number. The identifiers are stored as keys in the key value store. The snapshot identifiers are used to track pages that are shared between first and second snapshots. Upon a request to write to an existing page, a determination is made from the snapshot identifiers as to whether the existing page belongs to the first or second snapshot. If the existing page belongs to the second snapshot, the write to the existing page is allowed. If the existing page belongs to the first snapshot, a copy on write (COW) is performed to generate a new page for the write.

First claim

What is claimed is:

1. A method comprising:
maintaining metadata of a file system in a distributed key value store running on multiple nodes of a cluster hosting the file system, the metadata comprising multiple namespaces, each namespace represented as a B+ tree having pages written to the distributed key value store;
defining key names to the pages as a tuple, the tuple comprising an mtree identifier, a snapshot identifier and a page number, wherein the file system is divided into multiple logical partitions and the mtree identifier identifies a mountable directory hierarchy of a logical partition of the file system;
storing keys, having the key names, to the pages in the distributed key value store, each key name thereby comprising the mtree identifier, the snapshot identifier, and the page number;
tracking, using the mtree and the snapshot identifiers present in the key names, pages that are shared between first and second snapshots of a namespace corresponding to the mountable directory hierarchy of the file system, the first and the second snapshots not being immutable because the key value store in which the namespace is stored is not immutable, wherein the first snapshot comprises a first snapshot identifier, and the second snapshot comprises a second snapshot identifier,
wherein the distributed key value store comprises a plurality of keys including a first key and a second key,
the first key identifies a first page and a first key name of the first key comprises a first mtree identifier, the first snapshot identifier, and a first page number,
the first page comprises a child pointer to a second page, the child pointer comprising an entry having the first mtree identifier, the first snapshot identifier, and a second page number, and has a key name comprising the first mtree identifier, the first snapshot identifier, and the second page number,
the second key identifies a third page and a second key name of the second key comprises the first mtree identifier, the second snapshot identifier, and the first page number, and
the third page comprises the child pointer to the second page;

receiving a request to write to the second page;
comparing a key name of the child pointer comprising the first mtree identifier and the first snapshot identifier in the third page and a key name of the second key comprising the first mtree identifier and the second snapshot identifier identifying the third page;
determining that the key name of the child pointer comprising the first mtree identifier and the first snapshot identifier in the third page is different from the key name of the second key comprising the first mtree identifier and the second snapshot identifier identifying the third page;
conducting a copy-on-write for the second page to create a new page; and
modifying the child pointer of the third page with a new entry to point to the new page, the new entry comprising a new key having a new key name including the first mtree identifier, the second snapshot identifier, and the second page number.

2. The method of claim 1 wherein the tracking, using the mtree tree and the snapshot identifiers present in the key names, pages that are shared comprises with each snapshot that is taken of the namespace,
writing a page to the distributed key value store as a root page for the snapshot, and
updating a sequence of snapshot identifiers used in a key name of a key of the distributed key value store that identifies the snapshot.

3. The method of claim 1 further comprising:
incrementing the first snapshot identifier to obtain the second snapshot identifier;
dirtying a root page of the first snapshot; and
flushing the dirtied root page with a key having a key name comprising the first mtree identifier, the second snapshot identifier, and the first page number, wherein the dirtied and flushed root page in the distributed key value store is now a root page for the second snapshot and accessible from the distributed key value store using the key having the key name comprising the first mtree identifier, the second snapshot identifier, and the first page number, and
wherein the root page for the first snapshot is accessible from the distributed key value store using the key having the key name comprising the first mtree identifier, the first snapshot identifier, and the first page number;
creating a root page corresponding to a current state of the file system, the root page having the incremented snapshot identifier; and
flushing pages of the snapshot by writing keys of the pages to the key value store, each key comprising a snapshot identifier having a previous value of the incremented snapshot identifier, and an identifier of a logical partition of the file system.

4. The method of claim 1 wherein the pages of the B+ tree holding the namespace is kept in the distributed key value store with the keys identifying the pages and content of the pages stored as values for the keys.

5. The method of claim 1 wherein a form of the keys in the distributed key value store comprises a fixed string, followed by the mtree identifier, followed by the snapshot identifier, followed by the page number.

6. The method of claim 1 wherein the second snapshot is an active snapshot of the namespace and is exposed as a writable new namespace.

7. The method of claim 1 further comprising:
after the conducting the copy-on-write to create the new page, receiving a request to write to the new page;
comparing a key name of the new key comprising the first mtree identifier and the second snapshot identifier in the third page and the key name of the second key comprising the first mtree identifier and the second snapshot identifier identifying the third page;
determining that the key name of the new key comprising the first mtree identifier and the second snapshot identifier in the third page matches the key name of the second key comprising the first mtree identifier and the second snapshot identifier identifying the third page; and
allowing the write to the new page without performing a copy-on-write.

8. 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:
maintaining metadata of a file system in a distributed key value store running on multiple nodes of a cluster hosting the file system, the metadata comprising multiple namespaces, each namespace represented as a B+ tree having pages written to the distributed key value store;
defining key names to the pages as a tuple, the tuple comprising an mtree identifier, a snapshot identifier and a page number, wherein the file system is divided into multiple logical partitions and the mtree identifier identifies a mountable directory hierarchy of a logical partition of the file system;
storing keys, having the key names, to the pages in the distributed key value store, each key name thereby comprising the mtree identifier, the snapshot identifier, and the page number;
tracking, using the mtree and the snapshot identifiers present in the key names, pages that are shared between first and second snapshots of a namespace corresponding to the mountable directory hierarchy of the file system, the first and the second snapshots not being immutable because the key value store in which the namespace is stored is not immutable, wherein the first snapshot comprises a first snapshot identifier, and the second snapshot comprises a second snapshot identifier,
wherein the distributed key value store comprises a plurality of keys including a first key and a second key,
the first key identifies a first page and a first key name of the first key comprises a first mtree identifier, the first snapshot id

Assignees

• Dell Products Lp

Inventors

• Duggal Abhinav
• Mathew George
• Shilane Philip

Classifications

• G06F16/128 Primary

  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) · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F2201/84

  Using snapshots, i.e. a logical point-in-time copy of the data · CPC title

• G06F11/1453 Primary

  using de-duplication of the data · CPC title