Hash Table Size

Fortunately, analyzing the size of the hash table is a fairly simple issue on the surface. The dominant factor is the size of the hash table relative to the number of entries expected in the hash table. The challenge is that sometimes it is difficult to predict the exact size of the data set. The original question posted on the NTFSD forum asking about hashing file handles becomes, "How many file handles will there be in the target system?" If this is a single process, then it is likely there will be a few dozen handles for the process and thus a modestly sized hash table should yield good results. On the other hand, if this is a hash of file objects on the entire system of a large server, such as a high end 64-processor IA64 box with 1TB of physical memory, then we'll need to use a much larger table that has perhaps 50,000 or more entries.

If your hashing may span both extremes, you may need to construct an extensible scheme. In the past, when constructing general purpose hash tables, one approach we used was to maintain a pre-computed list chosen from the first few hundred prime numbers. We would start with a number of hash buckets from the lowest entry in the table. When the size of the hash table exceeded the number of hash buckets by a significant percentage (e.g., 2x), then we'd rebuild the hash table using a bigger prime number. Thus, if the number of entries was very small, the table would be small. As the number of entries grew, the size of the table grew ‑ the size of the table grew logarithmically in size versus the number of entries. Think of this as mimicking the scatter of prime numbers as one wanders off to infinity. The hash value was actually computed in two parts. The first part computed a fixed size value (e.g., 32 bit) based upon the data itself and was normally a function pointer provided when the hash table was first initialized. The second part of the computation took this fixed size value and performed modulo arithmetic on it to find the actual hash bucket. Once the correct bucket was identified we would walk a doubly-linked list of entries to do full matching.

Prime numbers are popular for hash table sizes because modulo arithmetic over prime numbers has good characteristics since they form a field and thus have the same behavior as the integers (see http://en.wikibooks.org/wiki/Abstract_algebra:Fields for a description of this property of prime integer fields). If your collision management system is tied to doing a search of a sequence of locations, using prime numbers works extremely well.

However, developers don't traditionally like to use modulo arithmetic because it is so computationally expensive, even though this should be only one instruction in potentially many instructions.  Thus, in many environments, this issue is not nearly as important now as it once was. However, the level of importance will depend on the usage pattern for your particular hash package.

Often it may be "good enough" to choose a fixed size table, which usually effectively shifts the complexity into handling collisions. For example, in one project we recently chose to go with a fixed size (256 entries) table because our goal was to minimize the lock contention on the table, not to minimize collisions. We'll discuss collisions later in the article.

Hashing Functions

Having chosen your table size, it is equally important to choose a good hash function. Ideally, you want the chosen hash function to "scatter" the values so similar input values yield different hash values. Choosing a good hash function is not immediately obvious because it requires some insight into the actual data set. For example, when hashing file object addresses, we noted that the low order two bits and the upper bit have essentially no information value due to the way memory is allocated on the system. Thus, we decided that a "good enough" algorithm was to take the middle two bytes from a 4 byte address and XOR them together. While not perfect, we concluded it was not only sufficient for our purposes, but also because it was very cheap to compute.

A search of the Internet seems to suggest there are numerous algorithms for hash functions. Much of the analysis relates to the cost of computing the hash and how good of a job it does at "scattering" similar input values. For example, cryptographic hash functions do an excellent job of scattering the value, but are computationally expensive. The article at http://burtleburtle.net/bob/hash/doobs.html does a good job of describing a broad variety of hash functions and also provides a model for analyzing them.

Collisions

Having chosen a hash function and deciding how to handle table sizing, the only remaining issue is how to handle collisions. There are several techniques that can be used, but we'll talk about the technique OSR normally uses - linked list or table.

The simplest technique is to use a linked list of entries. Thus, once we have identified the right hash "bucket," we use a linked list of some sort to look through each of the values in the bucket, performing a comparison until we find the right entry or run out of entries.

Linked lists work well for small lists of a dozen or so entries. If you have a 256 entry hash table, with each hash table containing a list of 10 entries, you have 2560 entries.  This technique also works well with an extensible hash table scheme, which shows that generally a linked list is sufficient.

However, beyond that, it often makes sense to use a table lookup scheme. For example, Windows includes both an AVLhash bucket.

Note: There are other collision techniques available that are not mentioned in this article.

Locking

One of the interesting motivators for some of our hash table work has been the need to parallelize locking. For example, we had a handle lookup table that was originally protected with a single lock around the entire table. During some performance analysis, we found that this lock was the source of considerable contention. To parallelize this we tied the locks to the individual buckets of the table itself. While most discussions of hashing ignore the need for parallel access, this may be an important consideration in the kernel environment, particularly if you expect to handle parallel activity such as would be seen in a storage level driver.

Thus, to protect our hash tables we used two ERESOURCE locks. One was a lock on the entire table, which allows one thread to traverse the entire table without worrying it will change. The second was a lock on the individual hash bucket. Therefore, we had the following three table lock options:

• Acquiring the "whole hash table" lock in exclusive mode, which allows access to anything in the table. This lock, which is used sparingly (e.g., volume dismount or shutdown cases), is for walking the whole table lock.
• Locking an individual hash table "bucket" for lookup. This requires holding the "whole hash table" lock in shared mode and the "bucket lock" in shared mode. In this mode, entries can be searched, but cannot be not inserted or removed. This lock allows concurrent lookups, which were our most common case.
• Locking an individual hash table "bucket" for insert/remove. This requires holding the "whole hash table" lock in shared mode and the "bucket lock" in exclusive mode. Entries can be searched, inserted, or removed, but only within a single thread at a time.

By tying our locking into the structure of our hash table package, we were able to optimize our performance within our specific environment.

Conclusions

Conceptually hashing seems simple, but it is often difficult to balance between common cases (small hash tables) and uncommon cases (large hash tables). Our experience is that uncommon cases are often the more performance sensitive. The more you know about the size and layout of your data set and your performance needs, the better your implementation will perform.

All but the most complex hashing implementation should take no more than a few hours to put together since there are dozens of samples to use when constructing your own.