Tree Structured Writable Snapshots

Generally snapshots are read-only. We can have multiple snapshots taken at different instances. The snapshots at different instances and Original view of the data form a chain like structure, with original view(also called as primary) at the head(root) of the chain and the oldest snapshot at the tail. Assume a chain of snapshots exist named $C_{n}$...,$C_{1}$,$C_{0}$ such that $C_{0}$ is the oldest and $C_{n}$ the latest in the chain followed by the `root' that we will call $C_{n+1}$. This is shown in Figure 4. All the COPY-ON-WRITE pushes resulting from writes to root, will go to the recent snapshot which is next to the root node in the chain. For snapshot read on some snapshot $C_{k}$ proceeds as follows. First map of the snapshot $C_{k}$ will be checked. If that has an entry for the block to be read, then the read request will be serviced from snapshot $C_{k}$. Otherwise the maps of the snapshots $C_{k+1}$,$C_{k+2}$,.... taken after the snapshot $C_{k}$, will be checked in order and if any one of them have an entry for the block to be serviced then that block will be read from the corresponding snapshots. If no snapshot has that mapping, then the read request will be serviced from the root.

Figure 4: Snapshot Tree

Nothing prevents us from having a read-write snapshot. In this section, we present a design of tree structured writable snapshots, which we have implemented. The basic idea is to associate an additional snapshot to every snapshot that needs to be mounted writable. All actual writes are then made to this new snapshot and the snapshot chain is modified such that no downstream snapshot references this one.

The first time a snapshot $C_{k}$ is to be mounted writable, we create a child node($C_{k^{'}}$) rooted at the snapshot referenced $C_{k}$ and mount this child snapshot $C_{k^{'}}$ as writable. No (downstream) snapshot ($C_{j}$) with j $<$ k, will depend on snapshot $C_{k^{'}}$ because it doesn't occur in the path of root node(root node or primary will be the original view of data). With the tree structured snapshot instances, there will be additional dependencies. Snapshot removal cannot be permitted as long as writable children exist. Reading from the writable snapshot $C_{k^{'}}$ works just as reading from any standard read-only snapshot does. Writes to the snapshot $C_{k^{'}}$ will be directly written in $C_{k^{'}}$. Now pushes are never required to be made downstream to snapshot $C_{k-1}$. We can have again read-only snapshots from read-write snapshots and from these read-only snapshots we can again have read-write snapshots. Thus we will have a tree like structure as shown in Figure 4.