US Patent 8996797 Dense tree volume metadata update logging and checkpointing

The embodiments described herein are directed to efficient logging and checkpointing of metadata managed by a volume layer of a storage input/output (I/O) stack executing on one or more nodes of a cluster. The metadata managed by the volume layer, i.e., the volume metadata, is illustratively organized as a multi-level dense tree metadata structure, wherein each level of the dense tree metadata structure (dense tree) includes volume metadata entries for storing the volume metadata. Each volume metadata entry may be a descriptor that embodies one of a plurality of types, including a data entry and an index entry, and a hole (i.e., absence of data) entry.