HDF5: Disk Format Implementation

1. Disk Format Level 0 - File Signature and Boot Block
2. Disk Format Level 1 - File Infrastructure
   1. Disk Format Level 1A - B-link Trees
   2. Disk Format Level 1B - Symbol Table
   3. Disk Format Level 1C - Symbol Table Entry
   4. Disk Format Level 1D - Local Heaps
   5. Disk Format Level 1E - Global Heap
   6. Disk Format Level 1F - Free-Space Index
3. Disk Format Level 2 - Data Objects
   1. Disk Format Level 2a - Data Object Headers
      1. Name: NIL
      2. Name: Simple Data Space
      3. Name: Data-Space
      4. Name: Data-Type
      5. Name: Reserved - not assigned yet
      6. Name: Reserved - not assigned yet
      7. Name: Data Storage - Compact
      8. Name: Data Storage - External Data Files
      9. Name: Data Storage - Layout
      10. Name: Reserved - not assigned yet
      11. Name: Reserved - not assigned yet
      12. Name: Data Storage - Compressed
      13. Name: Attribute List
      14. Name: Object Name
      15. Name: Object Modification Date & Time
      16. Name: Shared Object Message
      17. Name: Object Header Continuation
      18. Name: Symbol Table Message
   2. Disk Format: Level 2b - Shared Data Object Headers
   3. Disk Format: Level 2c - Data Object Data Storage

Disk Format Implementation

The format of a HDF5 file on disk encompasses several key ideas of the current HDF4 & AIO file formats as well as addressing some short-comings therein. The new format will be more self-describing than the HDF4 format and will be more uniformly applied to data objects in the file.

Three levels of information compose the file format. The level 0 contains basic information for identifying and "boot-strapping" the file. Level 1 information is composed of the object directory (stored as a B-tree) and is used as the index for all the objects in the file. The rest of the file is composed of data-objects at level 2, with each object partitioned into header (or "meta") information and data information.

The sizes of various fields in the following layout tables are determined by looking at the number of columns the field spans in the table. There are three exceptions: (1) The size may be overridden by specifying a size in parentheses, (2) the size of addresses is determined by the Size of Addresses field in the boot block, and (3) the size of size fields is determined by the Size of Sizes field in the boot block.

Disk Format: Level 0 - File Signature and Boot Block

The boot block may begin at certain predefined offsets within the HDF5 file, allowing a block of unspecified content for users to place additional information at the beginning (and end) of the HDF5 file without limiting the HDF5 library's ability to manage the objects within the file itself. This feature was designed to accommodate wrapping an HDF5 file in another file format or adding descriptive information to the file without requiring the modification of the actual file's information. The boot-block is located by searching for the HDF5 file signature at byte offset 0, byte offset 512 and at successive locations in the file, each a multiple of two of the previous location, i.e. 0, 512, 1024, 2048, etc.

The boot-block is composed of a file signature, followed by boot block and object directory version numbers, information about the sizes of offset and length values used to describe items within the file, the size of each object directory page, and a symbol table entry for the root object in the file.

Disk Format: Level 1A - B-link Trees

B-link trees allow flexible storage for objects which tend to grow in ways that cause the object to be stored discontiguously. B-trees are described in various algorithms books including "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. The B-link tree, in which the sibling nodes at a particular level in the tree are stored in a doubly-linked list, is described in the "Efficient Locking for Concurrent Operations on B-trees" paper by Phillip Lehman and S. Bing Yao as published in the ACM Transactions on Database Systems, Vol. 6, No. 4, December 1981.

The B-link trees implemented by the file format contain one more key than the number of children. In other words, each child pointer out of a B-tree node has a left key and a right key. The pointers out of internal nodes point to sub-trees while the pointers out of leaf nodes point to other file data types. Notwithstanding that difference, internal nodes and leaf nodes are identical.

Disk Format: Level 1B - Symbol Table

A symbol table is a group internal to the file that allows arbitrary nesting of objects (including other symbol tables). A symbol table maps a set of names to a set of file address relative to the file boot block. Certain meta data for an object to which the symbol table points can be cached in the symbol table in addition to (or in place of?) the object header.

An HDF5 object name space can be stored hierarchically by partitioning the name into components and storing each component in a symbol table. The symbol table entry for a non-ultimate component points to the symbol table containing the next component. The symbol table entry for the last component points to the object being named.

A symbol table is a collection of symbol table nodes pointed to by a B-link tree. Each symbol table node contains entries for one or more symbols. If an attempt is made to add a symbol to an already full symbol table node containing 2K entries, then the node is split and one node contains K symbols and the other contains K+1 symbols.

Disk Format: Level 1C - Symbol-Table Entry

Each symbol table entry in a symbol table node is designed to allow for very fast browsing of commonly stored scientific objects. Toward that design goal, the format of the symbol-table entries includes space for caching certain constant meta data from the object header.

The symbol table entry scratch-pad space is formatted according to the value of the Symbol Type field. If the Symbol Type field has the value zero then no information is stored in the scratch pad space.

If the Symbol Type field is one, then the scratch pad space contains cached meta data for another symbol table with the format:

Disk Format: Level 1D - Local Heaps

A heap is a collection of small heap objects. Objects can be inserted and removed from the heap at any time and the address of a heap doesn't change once the heap is created. Note: this is the "local" version of the heap mostly intended for the storage of names in a symbol table. The storage of small objects in a global heap is described below.

Objects within the heap should be aligned on an 8-byte boundary.

Disk Format: Level 1E - Global Heap

Each HDF5 file has a global heap which stores various types of information which is typically shared between datasets. The global heap was designed to satisfy these goals:

1. Repeated access to a heap object must be efficient without resulting in repeated file I/O requests. Since global heap objects will typically be shared among several datasets it's probable that the object will be accessed repeatedly.
   
   
2. Collections of related global heap objects should result in fewer and larger I/O requests. For instance, a dataset of void pointers will have a global heap object for each pointer. Reading the entire set of void pointer objects should result in a few large I/O requests instead of one small I/O request for each object.
   
   
3. It should be possible to remove objects from the global heap and the resulting file hole should be eligible to be reclaimed for other uses.
   
   

The implementation of the heap makes use of the memory management already available at the file level and combines that with a new top-level object called a collection to achieve Goal B. The global heap is the set of all collections. Each global heap object belongs to exactly one collection and each collection contains one or more global heap objects. For the purposes of disk I/O and caching, a collection is treated as an atomic object.

Disk Format: Level 1F - Free-Space Index (NOT FULLY DEFINED)

The Free-Space Index is a collection of blocks of data, dispersed throughout the file, which are currently not used by any file objects. The blocks of data are indexed by a B-tree of their length within the file.

Each B-Tree page is composed of the following entries and B-tree management information, organized as follows:

The elements of the free-space heap page are described below:

Free-Space Heap Signature: (4 bytes)

The value ASCII: 'FREE' is used to indicate the beginning of a free-space heap B-Tree page. This gives file consistency checking utilities a better chance of reconstructing a damaged file.

B-Tree Left-Link Offset: (<offset> bytes)

This value is used to indicate the offset of all offsets in the B-link-tree which are smaller than the value of the offset in entry #1. This value is also used to indicate a leaf node in the B-link-tree by being set to all ones.

Length of Free-Block #n: (<length> bytes)

This value indicates the length of an un-used block in the file.

Offset of Free-Block #n: (<offset> bytes)

This value indicates the offset in the file of an un-used block in the file.

"High" Offset: (4-bytes)

This offset is used as the upper bound on offsets contained within a page when the page has been split.

Right-link Offset: (<offset> bytes)

This value is used to indicate the offset of the next child to the right of the parent of this object directory page. When there is no node to the right, this value is all zeros.

The algorithms for searching and inserting objects in the B-tree pages are described fully in the Lehman & Yao paper, which should be read to provide a full description of the B-Tree's usage.

Disk Format: Level 2 - Data Objects

Data objects contain the real information in the file. These objects compose the scientific data and other information which are generally thought of as "data" by the end-user. All the other information in the file is provided as a framework for these data objects.

A data object is composed of header information and data information. The header information contains the information needed to interpret the data information for the data object as well as additional "meta-data" or pointers to additional "meta-data" used to describe or annotate each data object.

Disk Format: Level 2a - Data Object Headers

The header information of an object is designed to encompass all the information about an object which would be desired to be known, except for the data itself. This information includes the dimensionality, number-type, information about how the data is stored on disk (in external files, compressed, broken up in blocks, etc.), as well as other information used by the library to speed up access to the data objects or maintain a file's integrity. The header of each object is not necessarily located immediately prior to the object's data in the file and in fact may be located in any position in the file.

The header message types and the message data associated with them compose the critical "meta-data" about each object. Some header messages are required for each object while others are optional. Some optional header messages may also be repeated several times in the header itself, the requirements and number of times allowed in the header will be noted in each header message description below.

The following is a list of currently defined header messages:

Name: NIL

Name: Simple Data Space/a>

Name: Data-Space (Fiber Bundle?)

The elements of the dimensionality message are described below:

Mesh Type: (unsigned 32-bit integer)

This value indicates whether the grid is polar/spherical/cartesion, structured/unstructured and regular/irregular.
The mesh type value is broken up as follows:

HDF5 Mesh-Type Layout

byte	byte	byte	byte
Mesh Embedding	Coordinate System	Structure	Regularity

The following are the definitions of mesh-type bytes:

Mesh Embedding

This value indicates whether the dataset data-space is located within another dataspace or not:

<STANDALONE>

The dataset mesh is self-contained and is not embedded in another mesh.

<EMBEDDED>

The dataset's data-space is located within another data-space, as described in information below.

Coordinate System

This value defines the type of coordinate system used for the mesh:

<POLAR>

The last two dimensions are in polar coordinates, higher dimensions are cartesian.

<SPHERICAL>

The last three dimensions are in spherical coordinates, higher dimensions are cartesian.

<CARTESIAN>

All dimensions are in cartesian coordinates.

Structure

This value defines the locations of the grid-points on the axes:

<STRUCTURED>

All grid-points are on integral, sequential locations, starting from 0.

<UNSTRUCTURED>

Grid-points locations in each dimension are explicitly defined and may be of any numeric data-type.

Regularity

This value defines the locations of the dataset points on the grid:

<REGULAR>

All dataset elements are located at the grid-points defined.

<IRREGULAR>

Each dataset element has a particular grid-location defined.

The following grid combinations are currently allowed:

<POLAR-STRUCTURED-REGULAR>

<SPHERICAL-STRUCTURED-REGULAR>

<CARTESIAN-STRUCTURED-REGULAR>

<POLAR-UNSTRUCTURED-REGULAR>

<SPHERICAL-UNSTRUCTURED-REGULAR>

<CARTESIAN-UNSTRUCTURED-REGULAR>

<CARTESIAN-UNSTRUCTURED-IRREGULAR>

All of the above grid types can be embedded within another data-space.

Logical Dimensionality: (unsigned 32-bit integer)

This value is the number of dimensions that the dataset occupies.

HDF5 Data-Space Embedded Dimensionality Information

byte	byte	byte	byte
Embedded Dimensionality
Embedded Dimension Size #1
. . .
Embedded Dimension Size #n
Embedded Origin Location #1
. . .
Embedded Origin Location #n

Embedded Dimensionality: (unsigned 32-bit integer)

This value is the number of dimensions of the space the dataset is located within. i.e. a planar dataset located within a 3-D space, or a 3-D dataset which is a subset of another 3-D space, etc.

Embedded Dimension Size: (unsigned 32-bit integer)

These values are the sizes of the dimensions of the embedded data-space that the dataset is located within.

Embedded Origin Location: (unsigned 32-bit integer)

These values comprise the location of the dataset's origin within the embedded data-space.

The elements of the dimensionality message are described below:

Logical Dimension Size #n: (unsigned 32-bit integer)

This value is the current size of the dimension of the data as stored in the file. The first dimension stored in the list of dimensions is the slowest changing dimension and the last dimension stored is the fastest changing dimension.

Logical Dimension Maximum #n: (unsigned 32-bit integer)

This value is the maximum size of the dimension of the data as stored in the file. This value may be the special value <UNLIMITED> which indicates that the data may expand along this dimension indefinitely.

Examples:

Name: Data Type

The data type message defines the data type for each data point of a dataset. A data type can describe an atomic type like a fixed- or floating-point type or a compound type like a C struct. A data type does not, however, describe how data points are combined to produce a dataset. Data types are stored on disk as a data type message, which is a list of data type classes and their associated properties.

The Class Bit Field and Properties fields vary depending on the Type Class. The type class is one of: 0 (fixed-point number), 1 (floating-point number), 2 (date and time), 3 (text string), 4 (bit field), 5 (opaque), 6 (compound). The Class Bit Field is zero and the size of the Properties field is zero except for the cases noted here.

The Properties field of a compound data type is a list of the member definitions of the compound data type. The member definitions appear one after another with no intervening bytes. The member types are described with a recursive data type message.

Data type examples are here.

Name: Reserved - Not Assigned Yet

Name: Reserved - Not Assigned Yet

Name: Data Storage - Compact

This message indicates that the data for the data object is stored within the current HDF file by including the actual data within the header data for this message. The data is stored internally in the "normal" format, i.e. in one chunk, un-compressed, etc.

Note that one and only one of the "Data Storage" headers can be stored for each data object.

Format of Data: The message data is actually composed of dataset data, so the format will be determined by the dataset format.

Examples:

Name: Data Storage - External Data Files

Purpose and Description: The external object message indicates that the data for an object is stored outside the HDF5 file. The filename of the object is stored as a Universal Resource Location (URL) of the actual filename containing the data. An external file list record also contains the byte offset of the start of the data within the file and the amount of space reserved in the file for that data.

Name: Data Storage - Layout

Purpose and Description: Data layout describes how the elements of a multi-dimensional array are arranged in the linear address space of the file. Two types of data layout are supported:

1. The array can be stored in one contiguous area of the file. The layout requires that the size of the array be constant and does not permit chunking or compression. The message stores the total size of the array and the offset of an element from the beginning of the storage area is computed as in C.
2. The array domain can be regularly decomposed into chunks and each chunk is allocated separately. This layout supports arbitrary element traversals and compression and the chunks can be distributed across external raw data files (these features are described in other messages). The message stores the size of a chunk instead of the size of the entire array; the size of the entire array can be calculated by traversing the B-tree that stores the chunk addresses.

Name: Reserved - Not Assigned Yet

Name: Reserved - Not Assigned Yet

Name: Data Storage - Compressed

Purpose and Description: Compressed objects are datasets which are stored in an HDF file after they have been compressed. The encoding algorithm and its parameters are stored in a Compression Message in the object header of the dataset.

Sometimes additional redundancy can be added to the data before it's compressed to result in a better compression ratio. The library doesn't specifically support modeling methods to add redundancy, but the effect can be achieved through the use of user-defined data types.

The library uses the following compression methods.

The compression is applied independently to each chunk of storage (after data space and data type conversions). If the compression is unable to make the chunk smaller than it would normally be, the chunk is stored without compression. At the library's discretion, chunks which fail the compression can also be stored in their raw format.

Name: Attribute List

Purpose and Description: The Attribute List message is used to list objects in the HDF file which are used as attributes, or "meta-data" about the current object. Other objects can be used as attributes for either the entire object or portions of the current object. The attribute list is composed of two lists of objects, the first being simple attributes about the entire dataset, and the second being pointers attribute objects about the entire dataset. Partial dataset pointers are currently unspecified and unimplemented.

Format of Data:

The elements of the attribute list message are described below:

Attribute List Flags: (unsigned 32-bit integer)

These flags indicate the presence of simple and complex lists of attributes for this dataset. Bit 0 indicates the presence of a list of simple attributes and Bit 1 indicates the presence of a list of complex attributes.

# of Simple Attributes: (unsigned 32-bit integer)

This indicates the number of simple attributes for this dataset.

Simple Attribute #n Name Offset: (unsigned 32-bit integer)

This is the offset of the simple attribute's name in the global small-data heap.

Simple Attribute #n Data-type: (unsigned 32-bit integer)

This is a simple data-type, which indicates the type of data used for the attribute.

Simple Attribute #n Rank: (unsigned 32-bit integer)

This is the number of dimensions of the attribute, limited to four or less.

Simple Attribute #n Dim #n Size: (unsigned 32-bit integer)

This is the size of the attribute's n'th dimension, which is stored in the canonical order for dimensions (i.e. no permutations of the indices are allowed).

Simple Attribute #n Data Offset: (unsigned 32-bit integer)

This is the offset of the simple attribute's data in the global small-data.

# of Complex Attributes: (unsigned 32-bit integer)

This indicates the number of complex attributes for this dataset.

Pointer to Complex Attribute #n: (unsigned 32-bit integer)

This is the small-data heap offset of the name of the attribute object in the file.

[Note: It has been suggested that each attribute have an additional "units" field, so this is being considered.]

Examples:

Name: Object Name

Name: Object Modification Date & Time

Examples:

Name: Shared Object Message

A constant message can be shared among several object headers by writing that message in the global heap and having the object headers all point to it. The pointing is accomplished with a Shared Object message which is understood directly by the object header layer of the library and never actually appears as a message in the file. It is also possible to have a message of one object header point to a message in some other object header, but care must be exercised to prevent cycles.

If a message is shared, then the message appears in the global heap and its message ID appears in the Header Message Type field of the object header. Also, the Flags field in the object header for that message will have bit two set (the H5O_FLAG_SHARED bit). The message body in the object header will be that of a Shared Object message defined here and not that of the pointed-to message.

Name: Object Header Continuation

The object header continuation is formatted as follows (assuming a 4-byte length & offset are being used in the current file):

The elements of the Header Continuation Message are described below:

Header Continuation Offset: (<offset> bytes)

This value is the offset in bytes from the beginning of the file where the header continuation information is located.

Header Continuation Length: (<length> bytes)

This value is the length in bytes of the header continuation information in the file.

Examples:

Name: Symbol Table Message

The symbol table message is formatted as follows:

The elements of the Symbol Table Message are described below:

B-tree Address (<offset> bytes)

This value is the offset in bytes from the beginning of the file where the B-tree is located.

Heap Address (<offset> bytes)

This value is the offset in bytes from the beginning of the file where the symbol table name heap is located.

Disk Format: Level 2b - Shared Data Object Headers

In order to share header messages between several dataset objects, object header messages may be placed into the global small-data heap. Since these messages require additional information beyond the basic object header message information, the format of the shared message is detailed below.

The elements of the shared object header message are described below:

Reference Count of Shared Header Message: (32-bit unsigned integer)

This value is used to keep a count of the number of dataset objects which refer to this message from their dataset headers. When this count reaches zero, the shared message header may be removed from the global small-data heap.

Shared Object Header Message: (various lengths)

The data stored for the shared object header message is formatted in the same way as the private object header messages described in the object header description earlier in this document and begins with the header message Type.

Disk Format: Level 2c - Data Object Data Storage

The data information for an object is stored separately from the header information in the file and may not actually be located in the HDF5 file itself if the header indicates that the data is stored externally. The information for each record in the object is stored according to the dimensionality of the object (indicated in the dimensionality header message). Multi-dimensional data is stored in C order [same as current scheme], i.e. the "last" dimension changes fastest.

Data whose elements are composed of simple number-types are stored in native-endian IEEE format, unless they are specifically defined as being stored in a different machine format with the architecture-type information from the number-type header message. This means that each architecture will need to [potentially] byte-swap data values into the internal representation for that particular machine.

Data with a "variable" sized number-type is stored in an data heap internal to the HDF file [which should not be user-modifiable].

Data whose elements are composed of pointer number-types are stored in several different ways depending on the particular pointer type involved. Simple pointers are just stored as the dataset offset of the object being pointed to with the size of the pointer being the same number of bytes as offsets in the file. Partial-object pointers are stored as a heap-ID which points to the following information within the file-heap: an offset of the object pointed to, number-type information (same format as header message), dimensionality information (same format as header message), sub-set start and end information (i.e. a coordinate location for each), and field start and end names (i.e. a [pointer to the] string indicating the first field included and a [pointer to the] string name for the last field). Browse pointers are stored as an heap-ID (for the name in the file-heap) followed by a offset of the data object being referenced.

Data of a compound data-type is stored as a contiguous stream of the items in the structure, with each item formatted according to it's data-type.