Revising Links in HDF5 Groups

Document's Audience:

• Current H5 library designers and knowledgable external developers.

Background Reading:

The HDF5 file format description:

B-Tree Nodes

Group Nodes

Group Node Entries

Local Heaps

Introduction:

What is this document about?

This document describes some enhancements to the information stored for each link in an HDF5 group.

How do links in HDF5 groups currently operate?

Links in HDF5 groups are the method that indicates an object's inclusion in a group. Objects in HDF5 files don't have names themselves (due to being able to be included in multiple groups with different names), so the link to the object has a name for that particular reference to the object.

Fundamentally, links store certain required information, such as the name of the link and either the object header address in the file (for hard links) or the target name (for soft links). Additionally, hard links can cache certain additional information about the target object (such as it's B-tree root and local heap addresses, for group objects) in an attempt to speed up operations on that object.

Currently, the information for each link in a group is split into two pieces. A fixed size portion is stored in the group node entry, and the name is stored in the local heap for the group.

Links in a group are indexed by a B-Tree, where the B-tree keys are the names of the objects (using the offset of the name in the local heap) and leaf nodes of the B-tree point to group nodes, which contain lists of group node entries.

What are limitations of the current design?

Over time, we've learned more about how HDF5 groups are used and have determined a few limitations in the current design. One difficulty is the way the B-tree and local heap addresses are cached for groups. Because the empty B-tree and local heap are allocated for each new group (in order to put them into the cached information for the new link to that group), if the group remains empty, the space used by the B-tree and local heap is wasted. It would be better to allocate the B-tree and local heap on demand, when links are created in an empty group.

Additionally, the information about each link is split into two locations (the group node entry and the local heap) in a way which wastes space for linking to common objects, like datasets. The information about each link also includes "cached" information about the object linked to, which breaks the modularity of the design.

Also, each time the B-tree is traversed, the local heap must be mapped into memory, in order to compare the names of the links. It would be possible to avoid this penalty by creating a hash-value of each name to store in the B-tree keys and avoid touching the local heap at all during B-tree traversals.

How are object references and group links related?

Object references in datasets point to other objects in an HDF5 file. Object references are stored in datasets as an address of the object referenced. They are similar in this respect to the way hard links are stored (hard links also directly store the address of the object linked to). However creating an object reference to an object doesn't increment the reference count of the target object, which allows an object reference to "dangle" like a soft link.

New Requirements:

There are several new requirements listed here, in order of decreasing importance:

• Support a "creation ordering" in a group. Multiple applications, including netCDF-3/4 require a mechanism for accessing linked objects in the order they were created. netCDF in particular requires a way to get the n^th object in a group, according to the order the links were created, ideally as fast as locating a link by its name. Supporting this fast lookup would require adding a B-tree to the group which was indexed according to the creation order. (Note that this is about the creation order, not the creation time.)
• Reduce the amount of space taken by an empty group. Several HDF5 customers, including Boeing, are using empty groups as "place holders" to attach attributes to. Having these groups allocate space for empty B-trees and local heaps can waste enormous amounts of space. (This may belong better in the "suggested changes" section, since we don't have explicit funding for this effort)

Additional Suggested Changes:

Since we are planning to revise the format of the links, there are several other changes that would be beneficial to make at this time. Suggested changes are listed here:

• Unify the information about a link. Since we need to access the local heap in order to retrieve the name on a link, all the information for a link should be stored in the local heap. This will allow the information stored for each link to be smaller and more flexible as well as possibly vary in size.
• Allow more information to be stored about a link. We need to allow creation order information to be added to links, for netCDF-3/4 support. How about certain other predefined information about each link, such as the creation time, etc?
• We should allow link names to be stored with non-ASCII character sets, such as Unicode. Probably all the links in a group should be stored with the same character set though, so the actual character set chosen should probably be stored at a higher level.
• If links are more of a "real" object, we can change object references to use links instead of the current format. Links as object references in a dataset would be stored in a local heap for the dataset. We would have to decide whether to keep object references the way they are now (pointing to an object like a hard link, but not incrementing the target's reference count like a soft link), or change them to be closer to the way hard or soft links in groups operate.
• If links are particular objects that can be referenced from anywhere in the file (as offsets in a local heap at a particular address), we can add back-pointers to HDF5 files. This would be done by adding a list of "back-pointers" to each HDF5 object, each of which referred to the link that pointed to the object. This would allow file compaction to be performed much more easily than without back-pointers. It may also allow browsers to more easily traverse and present objects in a file.
• If links are closer to a "real" object, we can allow attributes to be added to them. The attributes on links would allow the links to be colored or weighted by graph traversal routines that used HDF5 links and groups to describe a graph. Possibly, the attributes on a link could be treated as additions to the attributes on the target object by an application, allowing different sets of attributes to be seen on an object, depending on the path taken to arrive there.
• Change the default format for B-tree keys to a hash-value, to speed up name lookups in the B-tree. This would also have the advantage of avoiding comparing names encoded with different character sets during B-tree traversal. Of course, the downside is that the order of the objects iterated with this B-tree would appear in random alphabetical name order. This could be addressed by adding an additional B-tree to track the alphabetical ordering, if a user desired.