Package org.apache.hadoop.hdfs.server.namenode.snapshot

Class DiffListBySkipList

java.lang.Object
org.apache.hadoop.hdfs.server.namenode.snapshot.DiffListBySkipList
All Implemented Interfaces:
Iterable<DirectoryWithSnapshotFeature.DirectoryDiff>, DiffList<DirectoryWithSnapshotFeature.DirectoryDiff>
public class DiffListBySkipList extends Object implements DiffList<DirectoryWithSnapshotFeature.DirectoryDiff>
SkipList is an implementation of a data structure for storing a sorted list of Directory Diff elements, using a hierarchy of linked lists that connect increasingly sparse subsequences(defined by skip interval here) of the diffs. The elements contained in the tree must be mutually comparable.

Consider a case where we have 10 snapshots for a directory starting from s0 to s9 each associated with certain change records in terms of inodes deleted and created after a particular snapshot and before the next snapshot. The sequence will look like this:

s0->s1->s2->s3->s4->s5->s6->s7->s8->s9.

Assuming a skip interval of 3, which means a new diff will be added at a level higher than the current level after we have ore than 3 snapshots. Next level promotion happens after 9 snapshots and so on.

level 2: s08------------------------------->s9 level 1: S02------->s35-------->s68-------->s9 level 0: s0->s1->s2->s3->s4->s5->s6->s7->s8->s9

s02 will be created by combining diffs for s0, s1, s2 once s3 gets created. Similarly, s08 will be created by combining s02, s35 and s68 once s9 gets created.So, for constructing the children list fot s0, we have to combine s08, s9 and reverse apply to the live fs.

Similarly, for constructing the children list for s2, s2, s35, s68 and s9 need to get combined(or added) and reverse applied to current fs.

This approach will improve the snapshot deletion and snapshot diff calculation.

Once a snapshot gets deleted, the list needs to be balanced.