In the 1.6.4 release, we introduced a re-implementation of the metadata cache. That release contained an incomplete version of the cache which could not be controlled via the API. The version in the 1.8 release is more mature, and includes new API calls that allow the user program to configure the metadata cache both on file open and at run time.
From the user perspective, the most striking effect of the new cache should be a large reduction in the cache memory requirements when working with complex HDF5 files.
Those working with such files may also notice a reduction in file close time.
Those working with HDF5 files with simple structure shouldn't notice any particular changes in most cases. In rare cases, there may be a significant improvement in performance.
The remainder of this document contains an architectural overview of the old and new metadata caches, a discussion of algorithms used to attempt to automatically adjust cache size to circumstances, and a high level discussion of the cache configuration controls. It can be safely skipped by anyone who works only with HDF5 files with relatively simple structure (i.e. no huge groups, datasets with large numbers of chunks, or objects with large numbers of attributes.)
On the other hand, it is mandatory reading if you want to use other than the default metadata cache configuration. The documentation on the metadata cache related API calls will not make much sense without this background.
The old metadata cache indexed the cache with a hash table with no provision for collisions. Instead, collisions were handled by evicting the existing entry to make room for the new entry. Aside from flushes, there was no other mechanism for evicting entries, so the replacement policy could best be described as "Evict on Collision".
As a result, if two frequently used entries hashed to the same location, they would evict each other regularly. To decrease the likelyhood of this situation, the default hash table size was slightly more than 10,000. However, since the size of metadata entries is not bounded, and since entries were only evicted on collision, this allowed the cache size to explode when working with HDF5 files with complex structure.
The "Evict on Collision" replacement policy also caused problems with the parallel version of the HDF5 library, as a collision with a dirty entry could force a write in response to a metadata read. Since all metadata writes must be collective in the parallel case, this caused the library to hang. Prior to the implementation of the new metadata cache, we dealt with this issue by maintaining a shadow cache for dirty entries evicted by a read.
The new metadata cache was designed to address the above issues. After implementation, it became evident that the working set size for HDF5 files varies widely depending on both structure and access pattern. Thus it was necessary to add support for cache size adjustment under either automatic or user program control.
Structurally, the new metadata cache can be thought of as a heavily modified version of the UNIX buffer cache as described in chapter three of M. J. Bach's "The Design of the UNIX Operating System" In essence the UNIX buffer cache uses a hash table with chaining to index a pool of fixed-size buffers. It uses the LRU replacement policy to select candidates for eviction.
Since HDF5 metadata entries are of no fixed size, and may grow arbitrarily large, the size of the new metadata cache cannot be controlled by setting a maximum number of entries. Instead the new cache keeps a running sum of the sizes of all entries, and will attempt to evict entries as necessary to stay within a user specified maximum size. At present, the LRU replacement policy is the only option for selecting candidates for eviction.
Per the buffer cache, dirty entries are given two passes through the LRU list before being evicted. The first time they reach the end of the LRU list, they are flushed, marked as clean, and moved to the head of the LRU list. When a clean entry reaches the end of the LRU list, it is simply evicted if space is needed.
The cache cannot evict entries that are locked, and thus it will temporarily grow beyond its maximum size if there are insufficient unlocked entries available for eviction.
When operating in parallel, only the cache running under process 0 of the file comunicator is allowed to write metadata to file. All the other caches must retain dirty metadata until the process 0 cache tells them that the metadata is clean.
Since all operations modifying metadata must be collective, all caches see the same stream of dirty metadata. This fact is used to allow them to synchronize every n bytes of dirty metadata, where n is a user configurable value that defaults to 256 KB.
To avoid sending the other caches messages from the future, process 0 must not write any dirty entries until it reaches the synchronization point. When it reaches this point, it writes entries as needed, and then broadcasts the list of flushed entries to the other caches. The caches on the other processes use this list to mark entries clean, allowing them to evict those entries as needed.
The caches will also synchronize on a user initiated flush.
To minimize overhead when running in parallel, the cache maintains a "clean" LRU list in addition to the regular LRU list. This list contains only clean entries, and is used as a source of candidates for eviction when flushing dirty entries is not allowed.
Since flushing entries is forbidden most of the time when running in parallel, the caches can be forced to exceed their maximum sizes if they run out of clean entries to evict.
To decrease the likelyhood of this event, the new cache allows the user to specify a minimum clean size -- which is a minimum total size of all the entries on the clean LRU plus all unused space in the cache. Note that the clean LRU list is only maintained in the parallel version of the HDF5 library, and thus that the minimum clean size is only relevant when running that version.
While the new metadata cache only supports the LRU replacement policy at present, that may change. Support for multiple replacement policies was very much in mind when the cache was designed, as was the ability to switch replacement policies at run time. The situation has been complicated by the late addition of the adaptive cache resizing requirement, as two of our resizing algorithms piggyback on the LRU list. However, if there is need for additional replacement policies, it shouldn't be too hard to implement them.
As mentioned earlier, the metadata working set size for a HDF5 file varies wildly depending on the structure of the file and the access pattern. For example, a 2MB limit on metadata cache size is excessive for an H5repack of almost all HDF5 files we have tested. However, I have a file submitted by one of our users that that will run a 13% hit rate with this cache size, and will lock up one of our linux boxes using the old metadata cache. Increase the new metadata cache size to 4 MB, and the hit rate exceeds 99%.
In this case the main culprit is a root group with more than 20,000 entries in it. As a result, the root group heap exceeds 1 MB, which tends to crowd out the rest of the metadata in a 2 MB cache
This case and a number of synthetic tests convinced us that we needed to modify the new metadata cache to expand and contract according to need within user specified bounds.
I was unable to find any previous work on this problem, so I invented solutions as I went along. If you are aware of prior work, please send me references. The closest I was able to come was a group of embedded CPU designers who were turning off sections of their cache to conserve power.
Perhaps the most obvious heuristic for identifying cases in which the cache is too small involves monitoring the hit rate. If the hit rate is low for a while, and the cache is at its maximum size, the cache is probably too small.
The hit rate threshold algorithm for increasing cache size applies this intuition directly.
Hit rate statistics are collected over a user specified number of cache accesses. This period is known as an epoch.
At the end of each epoch, the hit rate is computed, and the counters are reset. If the hit rate is below a user specified threshold and the cache is at its maximum size, the maximum size of the cache is increased by a user specified multiple. If required, the new cache maximum size is clipped to stay within the user specified upper bound, and optionally, within a user specified maximum increment.
My tests indicate that this algorithm works well in most cases. However, in a synthetic test in which hit rate increased slowly with cache size, and load remained steady for many epochs, I observed a case in which cache size increased until hit rate just exceeded the specified minimum and then stalled.
If this case occurs frequently in actual use, I will have to come up with an improved cache size increase algorithm. Please let me know if you see this behavior. However, I had to work rather hard to create it in my synthetic tests, so I would expect it to be uncommon.
Identifying cases in which the maximum cache size is larger than necessary turned out to be more difficult.
One obvious heuristic is to monitor the hit rate and guess that we can safely decrease cache size if hit rate exceeds some user supplied threshold (say .99995).
The hit rate threshold size decrement algorithm implemented in the new metadata cache implements this intuition as follows:
At the end of each epoch (this is the same epoch that is used in the cache size increment algorithm), the hit rate is compared with the user specified threshold. If the hit rate exceeds that threshold, the maximum cache size is decreased by a user specified factor. If required, the size of the reduction is clipped to stay within a user specified lower bound, and optionally, within a user specified maximum decrement.
In my synthetic tests, this algorithm works poorly. Even with a very high threshold and a small maximum reduction, it results in cache size oscillations. The size increment code typically increments cache size above the working set size. This results in a high hit rate, which causes the threshold size decrement code to reduce the cache size below the working set size, which causes hit rate to crash causing the cycle to repeat. The resulting average hit rate is poor.
It remains to be seen if this behavior will be seen in the field. The algorithm is available for use, but it wouldn't be my first choice.
Another heuristic for dealing with oversized cache conditions is to look for entries that haven't been accessed for a long time, evict them, and reduce the cache size accordingly.
The ageout cache size reduction applies this intuition as follows: At the end of each epoch (again the same epoch as used in the cache size increment algorithm), all entries that haven't been accessed for a user configurable number of epochs (1 - 10 at present) are evicted. The maximum cache size is then reduced to equal the sum of the sizes of the remaining entries. The size of the reduction is clipped to stay within a user specified lower bound, and optionally, within a user specified maximum decrement.
In addition, the user may specify a minimum fraction of the cache which must be empty before the cache size is reduced. Thus if an empty reserve of 0.1 was specified on a 10 MB cache, there would be no cache size reduction unless the eviction of aged out entries resulted in more than 1 MB of empty space. Further, even after the reduction, the cache would be one tenth empty.
In my synthetic tests, the ageout algorithm works rather well, although it is somewhat sensitive to the epoch length and ageout period selection.
To address these issues, I combined the hit rate threshold and ageout heuristics.
Ageout with threshold works just like ageout, save that the algorithm is not run unless the hit rate exceeded a user specified threshold in the previous epoch.
In my synthetic tests, ageout with threshold seems to work nicely, with no observed oscillation. Thus I have selected it as the default cache size reduction algorithm.
For those interested in such things, the ageout algorithm is implemented by inserting a marker entry at the head of the LRU list at the beginning of each epoch. Entries that haven't been accessed for at least n epochs are simply entries that appear in the LRU list after the n-th marker at the end of an epoch.
Due to lack of resources, the design work on the automatic cache size adjustment algorithms was done hastily, using primarily synthetic tests. I don't think I spent more than a couple weeks writing and running performance tests -- most time when into coding and functional testing.
As a result, while I think the algorithms provided for adaptive cache resizing will work well in actual use, I don't really know. Fortunately, the issue shouldn't arise for the vast majority of HDF5 users, and those for whom it may arise should be savy enough to recognize problems and deal with them.
For this latter class of users, I have implemented a number of new API calls allowing the user to select and configure the cache resize algorithms, or to turn them off and control cache size directly from the user program. There are also API calls that allow the user program to monitor hit rate and cache size.
From the user perspective, all the cache configuration data is
contained in an instance of the H5AC_cache_config_t
structure -- the definition of which is given below:
typedef struct H5AC_cache_config_t
{
/* general configuration fields: */
int version;
hbool_t rpt_fcn_enabled;
hbool_t set_initial_size;
size_t initial_size;
double min_clean_fraction;
size_t max_size;
size_t min_size;
long int epoch_length;
/* size increase control fields: */
enum H5C_cache_incr_mode incr_mode;
double lower_hr_threshold;
double increment;
hbool_t apply_max_increment;
size_t max_increment;
/* size decrease control fields: */
enum H5C_cache_decr_mode decr_mode;
double upper_hr_threshold;
double decrement;
hbool_t apply_max_decrement;
size_t max_decrement;
int epochs_before_eviction;
hbool_t apply_empty_reserve;
double empty_reserve;
/* parallel configuration fields: */
int dirty_bytes_threshold;
} H5AC_cache_config_t;
This structure is defined in H5ACpublic.h.
Each field is discussed in the associated header comment.
The C API allows you get and set this structure directly. Unfortunately the Fortran API has to do this with individual parameters for each of the fields (with the exception of version).
While the API calls are discussed individually in the reference manual, an overall discussion of what fields to change for different purposes should be useful.
The version field is intended to allow us to change the
H5AC_cache_config_t structure without breaking
old code. For now, this field should always be set to
H5AC__CURR_CACHE_CONFIG_VERSION, even when you are
getting the current configuration data from the cache. The library
needs the version number to know which fields are located where with
reference to the supplied base address.
The rpt_fcn_enabled field is a boolean flag that
allows you to turn on and off the resize reporting function that
reports the activities of the adaptive cache resize code at the end
of each epoch -- assuming that it is enabled.
The report function is unsupported, so you are on your own if you use it. Since it dumps status data to stdout, you should not attempt to use it with Windows unless you modify the source. You may find it useful if you want to experiment with different adaptive resize configurations. It is also a convenient way of diagnosing poor cache configuration. Finally, if you do lots of runs with identical behavior, you can use it to determine the metadata cache size needed in each phase of your program so you can set the required cache sizes manually.
As might be expected, the max_size and min_size
fields specify the range of maximum sizes that may be set for the cache.
min_size must be less than or equal to max_size,
and both must lie in the range [H5C__MIN_MAX_CACHE_SIZE,
H5C__MAX_MAX_CACHE_SIZE] -- currently [1 KB, 128 MB]. If you
routinely run a cache size in the top half of this range, you should increase
the hash table size.
The set_initial_size and initial_size fields
allow you to specify an initial cache size. If set_initial_size
is TRUE, initial_size must lie in the interval [min_size,
max_size]. If you disable the adaptive cache resizing code
(done by setting incr_mode to H5C_incr__off and
decr_mode to H5C_decr__off), you can use these fields
to control cache size manually.
The min_clean_fraction sets the current minimum
clean size as a fraction of the current max cache size. This
field is only used in the parallel version of the library, and must
lie in the range [0.0, 1.0]. 0.25 is a reasonable value.
The epoch_length is the number of cache accesses between runs
of the adaptive cache size control algorithms. It is ignored
if these algorithms are turned off. It must lie in the range
[H5C__MIN_AR_EPOCH_LENGTH,
H5C__MAX_AR_EPOCH_LENGTH] -- currently [100, 1000000].
The above constants are defined in H5Cprivate.h.
50000 is a reasonable value.
incr_mode specifies the cache size increment
algorithm used. Its value must be a member of the
H5C_cache_incr_mode enum type -- currently either
H5C_incr__off or H5C_incr__threshold.
This type is defined in H5Cpublic.h
If incr_mode is set to H5C_incr__off,
automatic cache size increases are disabled, and the remaining
fields in the cache size increase control section are ignored.
If incr_mode is H5C_incr__threshold,
the cache size is increased via the hit rate threshold algorithm.
The remaining fields in the section are then used as follows:
lower_hr_threshold is the threshold below which hit
rate must fall to trigger an increase. The value must lie in the
range [0.0 - 1.0]. In my tests, a relatively high value seems to
work best -- 0.9 for example.
increment is the factor by which the old maximum cache
size is multiplied to obtain an initial new maximum cache size when
an increment is needed. The actual change in size may be smaller
as required by max_size and max_increment
(discussed below). increment must be greater than or equal to 1.0.
If you set it to 1.0, you will effectively turn off the increment
code. 2.0 is a reasonable value.
apply_max_increment and max_increment allow
the user to specify a maximum increment. If apply_max_increment
is TRUE, the cache size will never be increased by more than the number of
bytes specified in max_increment in any single increase.
decr_mode specifies the cache size decrement algorithm used.
Its value must be a member of the H5C_cache_decr_mode enum
type -- currently either H5C_decr__off,
H5C_decr__threshold, H5C_decr__age_out, or
H5C_decr__age_out_with_threshold. This type is defined in
H5Cpublic.h
If decr_mode is set to H5C_decr__off, automatic
cache size decreases are disabled, and the remaining fields in the cache
size decrease control section are ignored.
if decr_mode is H5C_decr__threshold, the
cache size is decreased by the threshold algorithm, and the remaining
fields of decrement section are used as follows:
upper_hr_threshold is the threshold above which the hit
rate must fall to trigger cache size reduction. It must be in the
range [0.0, 1.0]. In my synthetic tests, very high values like .9995
or .99995 seemed to work best.
decrement is the factor by which the current maximum
cache size is multiplied to obtain a tentative new maximum cache
size. It must lie in the range [0.0, 1.0]. Relatively large values
like .9 seem to work best in my synthetic tests. Note that the actual
size reduction may be smaller as required by min_size and
max_decrement (discussed below).
apply_max_decrement and max_decrement
allow the user to specify a maximum decrement. If
apply_max_decrement is TRUE, cache size will never
be reduced by more than max_decrement bytes in any
single reduction.
With the hit rate threshold cache size decrement algorithm, the remaining fields in the section are ignored.
if decr_mode is H5C_decr__age_out
the cache size is decreased by the ageout algorithm, and the
remaining fields of decrement section are used as follows:
epochs_before_eviction is the number of epochs
an entry must reside unaccessed in the cache before it is
evicted. This value must lie in the range [1,
H5C__MAX_EPOCH_MARKERS].
H5C__MAX_EPOCH_MARKERS is defined in
H5Cprivate.h, and is currently set to 10.
apply_max_decrement and max_decrement
are used as above.
apply_empty_reserve and empty_reserve
allow the user to specify a minimum empty reserve as discussed
in section 4.2.2. An empty reserve of 0.05 or 0.1 seems to work
well.
The decrement and upper_hr_threshold
fields are ignored in this case.
If decr_mode is H5C_decr__age_out_with_threshold,
the cache size is decreased by the ageout with hit rate threshold
algorithm, and the fields of decrement section are used as per
the Ageout algorithm with the exception of upper_hr_threshold.
Here, upper_hr_threshold is the threshold above
which the hit rate must fall to trigger cache size reduction.
It must be in the range [0.0, 1.0]. In my synthetic tests, high
values like .999 seemed to work well.
This section is a catch-all for parallel specific
configuration data. At present, it has only one field
-- dirty_bytes_threshold.
In PHDF5, all operations that modify metadata must be executed collectively. We used to think that this was enough to ensure consistency across the metadata caches, but since we allow processes to read metadata individually, the order of dirty entries in the LRU list can vary across processes, which can result in inconsistencies between the caches.
To prevent this, only the metadata cache on process 0 of the file communicator is allowed to write to file, and then only after synchronizing with the other caches. After it writes entries to file, it sends the base addresses of the now clean entries to the other caches, so they can mark these entries clean as well.
The different caches know when to synchronize by counting
the number of bytes of dirty metadata created by the
collective operations modifying metadata. Whenever this count
exceeds the value specified in the dirty_bytes_threshold,
process 0 flushes down to its minimum clean size, and then
sends the list of newly cleaned entries to the other caches.
Needless to say, the value of the dirty_bytes_threshold
field must be consistant across all the caches operating on
a given file.
At present there is only one interaction between the increment and decrement sections of the configuration.
If incr_mode is H5C_incr__threshold,
and decr_mode is either H5C_decr__threshold
or H5C_decr__age_out_with_threshold, then
lower_hr_threshold must be strictly less than
upper_hr_threshold.
At present, the default configuration for the new metadata cache is as follows:
{
/* int version = */ H5C__CURR_AUTO_SIZE_CTL_VER,
/* hbool_t rpt_fcn_enabled = */ FALSE,
/* hbool_t set_initial_size = */ TRUE,
/* size_t initial_size = */ (1 * 1024 * 1024),
/* double min_clean_fraction = */ 0.5,
/* size_t max_size = */ (16 * 1024 * 1024),
/* size_t min_size = */ ( 1 * 1024 * 1024),
/* long int epoch_length = */ 50000,
/* enum H5C_cache_incr_mode incr_mode = */ H5C_incr__threshold,
/* double lower_hr_threshold = */ 0.9,
/* double increment = */ 2.0,
/* hbool_t apply_max_increment = */ TRUE,
/* size_t max_increment = */ (4 * 1024 * 1024),
/* enum H5C_cache_decr_mode decr_mode = */ H5C_decr__age_out_with_threshold,
/* double upper_hr_threshold = */ 0.999,
/* double decrement = */ 0.9,
/* hbool_t apply_max_decrement = */ TRUE,
/* size_t max_decrement = */ (1 * 1024 * 1024),
/* int epochs_before_eviction = */ 3,
/* hbool_t apply_empty_reserve = */ TRUE,
/* double empty_reserve = */ 0.1,
/* int dirty_bytes_threshold = */ (256 * 1024)
}
This configuration should be adequate for most HDF5 users. Outside of synthetic tests, I have only seen the cache increase beyond 1 MB on a few occasions, and never beyond 8 MB.
Should you need to change it, it can be found in
H5ACprivate.h. Look for the definition of
H5AC__DEFAULT_RESIZE_CONFIG.
The new metadata cache has a variety of debugging facilities that may be of use. I doubt that any other than the report function will ever be accessible via the API, but they are relatively easy to turn on in the source code.
Note that none of this should be viewed as supported -- it is described here on the off chance that you want to use it, but you are on your own if you do. Also, there are no promises as to consistency between versions.
As mentioned above, you can use the rpt_fcn_enabled
field of the configuration structure to enable the default reporting
function (H5C_def_auto_resize_rpt_fcn() in H5C.c).
If this function doesn't work for you, you will have to write your own.
In particular, remember that it uses stdout, so it will
probably be unhappy under Windows.
Again, remember that this facility is not supported. Further, it is likely to change every time I do any serious work on the cache.
There is also extensive stats collection code. Use
H5C_COLLECT_CACHE_STATS and
H5C_COLLECT_CACHE_ENTRY_STATS in H5Cprivate.h
to turn this on. If you also turn on H5AC_DUMP_STATS_ON_CLOSE
in H5ACprivate.h, stats will be dumped when you close a file.
Alternatively you can call H5C_stats() and
H5C_stats__reset() within the library to dump and reset stats.
Both of these functions are defined in H5C.c
Finally, the cache also contains extensive sanity checking
code. Much of this is turned on when you compile in debug mode,
but to enable the full suite, turn on H5C_DO_SANITY_CHECKS
in H5Cprivate.h
You have already seen how H5AC_cache_config_t
has facilities that allow you to control the metadata cache
size directly. Use H5Fget_mdc_config() and
H5Fset_mdc_config() to get and set the metadata
cache configuration on an open file. Use H5Pget_mdc_config()
and H5Pset_mdc_config() to get and set the initial
metadata cache configuration in a file access property list. Recall
that this list contains configuration data used when opening a file.
Use H5Fget_mdc_hit_rate() to get the average hit rate
since the last time the hit rate stats were reset. This happens
automatically at the beginning of each epoch if the adaptive cache
resize code is enabled. You can also do it manually with
H5Freset_mdc_hit_rate_stats(). Be careful about doing
this if the adaptive cache resize code is enabled, as you may
confuse it.
Use H5Fget_mdc_size() to get metadata cache size
data on an open file.
Finally, note that cache size and cache footprint are two different things -- in my tests, the cache footprint (as inferred from top) is typically about three times the maximum cache size. I haven't tracked it down yet, but I would guess that most of this is due to the very small typical cache entry size. This should be investigated further, but that will take time.
Absent major bugs in the cache, the only trouble shooting you should have to do is diagnosing and fixing problems with your cache configuration.
Assuming it runs on your platform (I've only used it under Linux),
the reporting function is probably the most convenient diagnosis tool.
However, since it is unsupported code, I will not discuss it further
beyond directing you to the source (H5C_def_auto_resize_rpt_fcn()
in H5C.c).
Absent the reporting function, regular calls to
H5Fget_mdc_hit_rate() should give you a good idea of
hit rate over time. Remember that the hit rate stats are reset at
the end of each epoch (when adaptive cache resizing is enabled),
so you should expect some jitter.
Similar calls to H5Fget_mdc_size() should
allow you to monitor cache size, and the fraction of the
cache that is actually in use.
If the hit rate is consistently low, and the cache it at its maximum size, increasing the maximum size is an obvious fix.
If you see hit rate and cache size oscillations, try disabling adaptive cache resizing and setting a fixed cache size a bit greater than the high end of the cache size oscillations you observed.
If the hit rate oscillations don't go away, you are probably looking at a feature of your application which can't be helped without major changes to the cache. Please send along a description of the situation.
If they do, you may be able to come up with a configuration that deals with the situation. If that fails, control cache size manually, and write me, so I can try to develop an adaptive resize algorithm that works in your case.
Needless to say, you should give the cache a few epochs to adapt to circumstances. If that is too slow for you, try manual cache size control.