The core of MST: Unlocking scalable data and index layout

Introduction

Our previous blog, Introduction to Multicloud Snapshot Technology, provides an introductory view of Multicloud Snapshot Technology (MST), its value proposition and high level architecture. As part of that blog, we mentioned how the usage of copy-on-write B+Trees as index structure is the key to the MST’s ability to support deep snapshot chains.

In this blog, we delve a bit deeper into the index structure and data layout of MST.

Data Organization

The MST architecture differentiates between logical and physical layouts in its data organization. The objective of the logical layout of MST is to provide quick retrieval of snapshot data with long chains. Whereas the objective of the physical layout is space efficiency and data integrity.

At the logical level, a virtual disk address space is divided into variable sized ranges called segments, such that a segment completely falls in a single data object. These segments facilitate the B+Tree index management, where we can translate a logical offset into a virtual disk to the underlying object containing that data.

While storing a segment into an object, we divide it into 32 KB slices, which we compress before storing into the object. The way we store these slices define the physical layout of data.

Metadata for logical layout

The cornerstone of MST’s design is its B+tree index. This index is what enables bounded retrieval complexity of any block of any snapshot in a deep snapshot chain. This index enables quick delta computation between any two snapshots in a snapshot chain, thus enabling clients to perform incremental restores. This delta computation mechanism is also leveraged by our garbage collection algorithm, which completes in bounded time.

The figure depicts the B+Tree indices of two snapshots of a disk d0, which share their data as well as index metadata.  

The internal nodes contain disk offsets and pointers to child nodes. The disk offset is the index key used by the B+Tree to get to the actual object containing data.

A leaf node contains a set of segments and pointers to a set of data objects. As described earlier, a segment represents a contiguous address range of a disk that resides on the same object. Segments are variable sized and created based on the ranges replicated by the client of MST. 

Multiple snapshots of a disk share data and index objects. In the figure above, snapshots S0 and S1 of the same disk (d0) share certain index nodes, both internal and leaf. A shared internal node means that the complete subtree underneath that node is shared between the snapshots. A shared leaf means that all the segments contained in that leaf, and hence all the data objects referred to by that leaf, are shared between the snapshots.

The MST solution allows a client to send incremental (delta) changes with respect to a base snapshot. The copy-on-write B+Tree structure enables space efficient management of the delta changes by sharing the unchanged data with the base snapshot. In the figure above, the snapshot d0s1 contains delta changes into 0-1TB range, which results in copying and overwriting d0s0:11 to create a new node d0s1:11. On the other hand, there are no delta changes to the 1TB-2TB range, allowing continued sharing of the entire subtree underneath d0s0:12.

Each snapshot has its own B+Tree index, resulting in bounded (logarithmic) complexity in getting to its data objects. The disk configuration of a snapshot keeps a reference to its B+Tree root node.

Index construction

The AOS client replicates snapshot data ranges to MST. Once all the ranges have been replicated it finalizes the snapshot, which acts as a commit point for the snapshot. The MST service constructs the B+Tree index at this point in time in a bottom up fashion. This delayed construction of the index not only keeps the algorithm simple, but also significantly reduces write amplification that is typically observed with an inline B+Tree construction approach. MST leverages the distributed KV store as a staging area to facilitate this delayed construction of the B+Tree.

Physical data layout

When segments of a virtual disk are stored in a data object, they are divided into 32 KB slices. On each slice we perform transformations before storing it in the data object. Transformations include compression (e.g. lz4), encryption, etc. As shown in the figure, the object contains metadata associated with each slice before storing the transformed data of the slices. Note that the physical size of the transformed slice would not be equal to 32 KB (due to the transformations). The slice metadata keeps information about where in the object the actual slice data is located. Additionally, we maintain a checksum of each slice as part of the slice metadata, something we rely on to maintain integrity of the data.

Key takeaways

The key takeaways of this metadata scheme are as follows:

First, the use of a copy-on-write B+Tree as an index of the logical disk address space enables MST to support long snapshot chains while still  providing bounded (logarithmic) time retrieval latency. 

Second, the copy-on-write B+Tree also enables garbage collection of snapshots with bounded complexity. Garbage associated with an expired snapshot can be computed by performing just two B+Tree comparisons. We need to compare the B+Tree of the expired snapshot with the B+Trees of its two adjacent snapshots (the parent and the child) in the snapshot chain.

Lastly, keeping the physical layout of the data distinct from the index enables flexibility around choice of compression algorithms, checksum maintenance for data integrity etc. In short, different data objects can potentially have different algorithms to compress their data slices, while being referred to by the same B+Tree index.

©2026 Nutanix, Inc. All rights reserved. Nutanix, the Nutanix logo and all Nutanix product and service names mentioned are registered trademarks or trademarks of Nutanix, Inc. in the United States and other countries. All other brand names mentioned are for identification purposes only and may be the trademarks of their respective holder(s).