Resizable cache sensitive hash table

[0001] The present invention is directed to an improvement in computing system data structures and in particular to improvements in defining dynamically resizable cache sensitive hash tables.

[0002] Computer systems often make use of hash tables to optimize data searches. Hash tables are widely used in computer program products as this construct can be used to provide fast access to many different kinds of data structures.

[0003] Data items referenced by a hash table are characterized uniquely using some properties of the data (the use of multiple properties to uniquely identify such data is common). For a hash table referencing a given data set “S”, the design and logic used to access the hash table will permit a computer program product to either locate target data (“D”) or determine that it does not exist in “S”. For a set “S” containing N data items, if a linear search is performed (comparing each item individually to “D”), such a search could in the worst case scenario (where “D” is not present in the data set), require accessing all N items in the set “S”.

[0004] A hash table is a table of a size which is typically much smaller than N. Hash tables are typically rounded to a size X which is either a prime number or the next power of 2 (still typically much smaller than N).

[0005] To implement a particular hash table, a hash function is selected based on properties identifying each data item “D”. The hash function may be applied to any data item “D” to generate a hash value. The properties used as an input to the hash function can be a subset of the total properties necessary to uniquely identify each data item. In typical applications, the hash value is the size of a word (often 32 or 64 bits). A hash index can then be generated from the hash value using modulo arithmetic carried out on the hash values of the elements in “S”. This is expressed as HASHVALUE % X=HASHINDEX (X is the size of chosen for the hash table).

[0006] Any data item “D”, being defined by a unique set of properties, some or all which are used in generating its hash value (and then ultimately through the hash value in its hash index), can thus only map to one entry in the hash table. Each entry in a hash table, and the associated data items, is called a hash bucket or bucket.

[0007] Multiple threads (or processes), may access a hash table and the associated data items at any given time. In a typical application, such as a database system main memory buffer system, the set of database pages (or their header or directory information) that are present in main memory may be hashed. Typically in such an application the hash bucket contains a pointer to a first data item. Data items themselves include pointers that permit them to be arranged in a linked list. Adding an item to a hash table is accomplished by placing the item in the appropriate linked list pointed to by the appropriate bucket in the hash table.

[0008] A thread looking for a particular page “D” in the buffer system would calculate the hash index of that page and perform a lookup in the hash table to determine if the page is in the database's main memory buffer. If it is not present in the hash table buckets (the pointer in the hash table bucket points to a linked list and the linked list does not contain the page) then the thread will cause the required page to be read from disk to the main memory buffer. The page will be added to the linked list pointed to by the appropriate hash bucket so that the next thread that is looking for the same page will be able to use the hash table to locate the page in the memory buffer.

[0009] Hash tables are typically kept consistent by the use of concurrency primitives called latches, with one latch for each hash bucket. This latch is often called the bucket latch. Threads wishing to parse contents (the data items in the associated linked list) of a particular hash bucket will take the bucket latch to ensure that the contents of the bucket remain consistent while the threads access items in the bucket. A thread inserting a new item into a linked list pointed to by a bucket will obtain the bucket latch to ensure that no other threads are parsing through the linked list of the bucket while the thread modifies the content of the bucket or the linked list. The bucket latch is often implemented as a full function latch where threads that are parsing through the contents of the bucket take the latch in share mode (so that multiple threads can look at the contents of a bucket concurrently), while those that are inserting or removing data items into a bucket take the latch in exclusive mode. As the above indicates a hash table bucket may include a latch and a pointer to the first data item in the linked list of data items that is related to that bucket.

[0010] The ability to handle concurrency in a hash table implementation becomes important when a hash table is resized. Resizing is desirable when the number of data items in the table becomes large relative to the number of buckets (causing the number of data items in the linked list for each bucket to grow). The most straightforward way to carry out a resizing operation is to first lock out all threads accessing the hash table and then to redistribute the data in the table. This can be done by creating one new latch (in addition to the existing bucket latches) for the entire hash table (or alternatively, by latching all buckets). Threads wishing to use the hash table would have to take the entire hash table latch (in share mode) before proceeding to access the bucket of interest. This is not a desirable approach because it locks out all users of the hash table during the resize.

[0011] Another approach avoids having to latch the whole hash table. Following this approach, each bucket is individually split (typically a binary split). In this approach, each bucket data structure includes a bit indicating whether the bucket is split or not, as well as data that pointing to the new buckets, if any. This approach is also limited. For example, the granularity of the split is limited in this case. In addition, it is typical for a thread or process accessing a particular hash table to store a copy of a calculated hash index value in a local variable or a register (this is referred to as maintaining a cached copy of the index value). Keeping the hash index value in a local variable or register in this way permits the thread or process to access the data item using the hash table without having to recalculate the hash index for the data item. Where a bucket is split as described above, any stored index values must be discarded, as they will no longer be reliable.

[0012] A hash table is itself typically implemented as a contiguous piece of computer memory (an array of 0 to X−1 hash bucket elements). The structure of each hash bucket in the generic hash table has two contents, i) the bucket latch and ii) a pointer to the start of the linked list of data items present in the bucket. Two adjacent buckets (e.g. 0 and 1), are thus separated by sizeof (Latch)+sizeof (FirstDataItemPtr). On a typical 32-bit computer system, a simple Latch is 4 bytes and a pointer in memory is also 4 bytes. The size of a hash bucket is therefore typically 8 bytes. Thus the starting points of two adjacent buckets (and hence two adjacent latches) would only be separated by 8 bytes of memory.

[0013] Since a typical data cache line on modem computer systems is 128 bytes (dependant on the processor architecture), the end result is that multiple buckets (and hence multiple bucket latches) will exist on the same cache line. On Symmetric Multi Processor (SMP) computer systems, multiple processors share the same main memory resources and have physically separate data caches (each processor typically has a data cache on the processor chip itself). As a result, on such systems there is a concept of cache line ownership. Since the data in the cache line is really shared data, expensive cache synchronization must occur across the processors to ensure that any cache lines that exist in more than one processor's cache are consistent.

[0014] Since any thread T0, running on processor P0 accessing bucket 0 must take that bucket's latch, the processor P0 will take ownership of the cache line that the latch exists in (since the latch is marked as “Taken”, the cache line has been “Dirtied” by processor P0). Thread T1, running on processor P1 accessing bucket 1 (a completely separate bucket) must “take” that bucket's latch, causing the processor to dirty the same cache line that P0 owns. This results in expensive cache synchronization across P0 and P1 (in some schemes, P0 will have to provide the updated cache line to P1 by snooping the bus to see when P1 requests the cache line). The net result is that even though the two threads T0 and T1 are accessing separate buckets, which are protected by separate latches, because the latches are on the same cache line, a false sharing of the latches occurs as a result of the cache line effects. The caching of the hash table is therefore less efficient than could otherwise be the case. The common approach to address this issue is to pad each bucket with unused bytes so that each bucket is on its own cache line. If there is an 8 byte bucket size and a 128 byte cache line, there will be 120 unused bytes for each bucket.

[0015] Another aspect of hash table operation that affects the efficiency of a hash table is the frequency of cache misses. A cache miss occurs when a thread or process seeks to access a bucket or the data items in the linked lists pointed to by the hash table but the item is not present in the cache. This is typically the case when a process or thread “walks” the linked list of data items. Accessing each item in the linked list will typically result in a CPU stall as a result of the cache line being accessed not being present in the data cache. This is inefficient as CPU cycles are wasted in waiting for the data items in the linked list (not cached) to be read from main memory.

[0016] It is therefore desirable to have a method and system for hash table creation and maintenance that permits hash tables to be dynamically resized and that provides improved performance of hash tables by minimizing cache line misses.

[0017] According to one aspect of the present invention there is provided an improved method and system for providing dynamically resizable, cache sensitive hash tables.

[0018] In another aspect, a method for providing a hash table for a collection of data items includes providing a set of hash buckets in the hash table, each hash bucket being associated with a subset of the collection of data items, and providing a set of properties entries in each of the hash buckets. Each properties entry includes a pointer to an associated data item in the subset associated with the hash bucket and a set of representative values for the associated data item, where the set of representative values identifies the data item. A system includes means for providing the above features.

[0019] In another aspect, a method for generating a hash table for a collection of data items includes defining a set of hash buckets, generating, for each data item, a properties entry associated with the data item, and storing each properties entry in a selected one of the hash buckets in a linked list of properties entries. The properties entry includes representative values for the data item and a pointer to the data item, and the selected one of the hash buckets is determined by a hash value of the data item associated with the properties entry.

[0020] In another aspect, a computer readable medium includes program instructions to be implemented by a computer for generating and maintaining a hash table for a collection of data items, the hash table comprising a set of bucket groups and hash buckets, each bucket group including a latch for the bucket group, a set of inline hash buckets, and a group header comprising a pointer definable to point to an array of overflow hash buckets.

[0021] In another aspect, a method for generating a hash table for a collection of data items, where the hash table includes a set of bucket groups and hash buckets, includes defining each of the bucket groups to include a latch for the bucket group, a set of inline hash buckets, and a group header comprising a pointer definable to point to an array of overflow hash buckets, and defining each hash bucket to comprise a set of properties entries. Each properties entry comprising a pointer to an associated data item in the subset associated with the hash bucket and a set of representative values for the associated data item, where the set of representative values identifies the data item.

[0022] In another aspect, a method for generating and maintaining a collection of data items includes providing a hash table, and defining hash buckets in the hash table, the hash buckets storable in alignment with cache line boundaries in a specified data cache.

[0023] In another aspect, a system for providing a hash table for a collection of data items, includes means for providing a set of hash buckets in the hash table, each hash bucket being associated with a subset of the collection of data items; and

• • [0024] means for providing a set of properties entries in each of the hash buckets, wherein each properties entry includes a pointer to an associated data item in the subset associated with the hash bucket, and a set of representative values for the associated data item, wherein the set of representative values identifies the data item.

[0025] In another aspect, a computer readable medium includes program instructions to be implemented by a computer for providing a hash table for a collection of data items, the program instructions performing steps including providing a set of hash buckets in the hash table, each hash bucket being associated with a subset of the collection of data items, and providing a set of properties entries in each of the hash buckets. Each properties entry includes a pointer to an associated data item in the subset associated with the hash bucket and a set of representative values for the associated data item, wherein the set of representative values identifies the data item.

[0026] Advantages of the present invention include, but are not limited to, hash table definition and use to reduce cache misses and to permit flexible resizing of the hash table buckets without requiring exclusive control of the entire hash table.

[0029] The present invention provides an improved method and system for providing dynamically resizable, cache sensitive hash tables. The following description is presented to enable one of ordinary skill in the art to make and use the invention and is provided in the context of a patent application and its requirements. Various modifications to the preferred embodiment and the generic principles and features described herein will be readily apparent to those skilled in the art. Thus, the present invention is not intended to be limited to the embodiment shown but is to be accorded the widest scope consistent with the principles and features described herein.

[0030] The structure of the cache sensitive hash table of the preferred embodiment is shown with reference to the example of the block diagram of FIG. 1. As will be apparent from the following description, FIG. 1 relates to the cache sensitive aspect of the hash table of the preferred embodiment. The aspect of the preferred embodiment relating to the resizability of the hash table is illustrated with respect to FIG. 2. Those skilled in the art will appreciate that the hash table of the preferred embodiment includes both cache sensitive and resizable characteristics, although a different embodiment according to aspects of the present invention need not include both these features.

[0031] FIG. 1 shows hash table 10 having hash buckets 12, 14, 16 (detailed illustration of the structure of hash bucket entries 14, 16 is omitted in FIG. 1). According to the preferred embodiment, each data item “D” that is referenced by the hash table is represented in two parts: a data properties item and a data contents item. A data properties item contains some or all of the properties necessary to uniquely identify the original data item “D” (these properties form a set of representative values for the associated data item “D”). A data contents item contains the remainder of the contents of the original data item “D” (in the preferred embodiment this includes a second copy the data properties, so that the data contents item is the same as the original data item “D”). Data properties items are optimized for size (smaller is preferred), by selectively picking the minimum set of properties that will, in most cases, be sufficient to identify “D”.

[0032] It should be noted that the identification of “D” through data properties items does not necessarily have to be unique. A non-unique identification can be used to keep the size of the data properties items to within a fraction of the total cache line size. In the case that the identification is non-unique, failing to find a match when seeking a given set of data properties values will mean that there is no corresponding data item pointed to by the hash table bucket. However, finding a match with one of the data properties items does not indicate that the data item is necessarily pointed to by the hash table bucket. The consequences of this non-unique correspondence are that in those cases, additional accesses to data items (and likely cache misses) will be required to access the data contents items to confirm the existence of the data item in the hash table set. As will be apparent to those skilled in the art, the selection of the properties used to identify the data items will depend on the data being accessed using the hash table. For economy of cache resources, the smaller the set of properties used, the better. However, in the preferred embodiment, the set of properties is larger than the set of properties used to generate the hash values for the hash table (where these sets of properties are the same, the additional properties items provide no functional advantage).

[0033] As indicated above, the preferred embodiment includes data properties items and data contents items. In the preferred embodiment, the hash table itself points to the data contents items and keeps the corresponding set of properties in the hash table itself (in the preferred embodiment the data contents items are complete data items, from which a subset of properties are copied to the data properties items in the buckets of the hash table). As shown in the example of FIG. 1, hash bucket 12 contains a linked list of items storing the properties of corresponding data items referenced by the bucket. The link list of properties is anchored by first data property pointer 20 in hash bucket 12. In the example of FIG. 1 the first data property pointer 20 points to properties entry 22 containing the property values (“Properties”), a pointer to the next item in the linked list (“NextInBkt”) and a pointer to the contents portion of the entry in the hash bucket (“ContentsPtr”). In the example of FIG. 1, entry 22 points to properties entry 24 and to data item 32. Properties entry 24 points to data item 34.

[0034] As may be seen in the example of FIG. 1, the data items themselves are not directly within the buckets in the hash table in the preferred embodiment. Rather, the buckets contain pointers to the data items (properties entry 22 points to data item 32, for example). Although the data items are not maintained within the data structure of the hash table, the terminology of the art refers to data items as being “in a hash table” or “in a bucket” where the data item is within a linked list pointed to by the bucket in the hash table. In this description, it will be understood that when a data item is described as being in a bucket, or the number of data items in a bucket is referred to, the data items are, in fact, pointed to by the data structure the implements the buckets, rather than being within the data structure of the bucket. In the preferred embodiment, it is the properties entries that are stored within the buckets. This distinction is significant for the caching that is done with hash table entries as the properties entries are, by definition, intended to be smaller than the data items to which they relate.

[0035] A pool of unused data properties entries is kept on a per bucket basis, within the bucket data structure. This is shown in FIG. 1 where hash bucket 12 maintains a list of free entries in the properties table. Free data properties pointer 26 anchors this linked list and in the example of FIG. 1 points to entry 28. Entry 28 has a next free pointer (NextFree) shown in FIG. 1 pointing to entry 30. In the preferred embodiment, the linked lists in the buckets are implemented to minimize the space in the cache line required to store the items in the linked lists and the pointers between items in the lists. The implementation used will depend on the available space on the cache line and other system details. Options include defining the linked list to be an array allocated within the cache line and pointers to be indexes into the array (of a byte or less in length). Another option is to allow for an overflow area to which the pointers of the linked list may point. A defined set of (upper order) bits in the pointer can be used to indicate whether the data item is in the main cache line or in one or more overflow spaces (and if so, in which one).

[0036] In the preferred embodiment, each hash bucket is defined to commence on a cache line boundary and to be less than one cache line in size. Requiring buckets to be arranged in this manner avoids the problem of false latch sharing that can occur when multiple buckets are stored on the same cache line.

[0037] By defining buckets to be aligned with cache line boundaries the effective minimum size of a bucket becomes the size of a cache line. As many cache lines are 128 bytes in length, the pool of unused properties entries (and its control structures) can be allocated from the bucket in most systems without extending the size of the bucket. The space occupied by the properties entries (both used and unused) is in many cases part of the bucket that would have otherwise been unused.

[0038] When a new item “D” is to be added to the data items in the hash table (added to the data items pointed to by the bucket), a data properties entry from the free pool is located, the properties of “D” are copied into it, and the entry is added to the properties entries linked list. A pointer to the contents data item is also added to the properties entry.

[0039] The number of data properties entries in the free pool for each bucket is calculated with reference to the average load factor of a bucket, assuming uniform distribution of hash values. In the event that a given bucket ends up not having uniform distribution of hash values, an additional pool of unused data properties entries can be maintained to be used as an overflow pool. The additional pool can be further optimized by not allocating it until necessary (until a bucket is identified that requires an overflow properties entry). Another optimization involves allocating an entire additional cache line of free data properties for the bucket in question as the overflow pool. The requirement for such optimization steps for the overflow pool of data properties entries is dependant on the uniformity of distribution of hash values.

[0040] In most applications, a search for a data item “D” in a hash table is effectively bottlenecked by processor stalls that result from cache misses. In the worst-case scenario (when item “D” is not present in the data set), even after missing in all the individual data items in the given bucket, item “D” will still not be found and will have to be inserted into the linked list.

[0041] The result of the preferred embodiment design of hash table is that the number of cache misses is reduced. On most systems, where the distribution of hash values is uniform (or predictable), and enough data properties entries can be accommodated within the hash bucket memory (the extra memory which results from the padding to avoid false sharing of latches), only one cache line miss is encountered (the bucket itself will be loaded to the cache) when searching for any data item “D” in the hash table. The preferred embodiment has the potential to eliminate any additional cache misses (and the resulting processor stalls) that are incurred by a processor when a thread searches for a data item which is not currently in the hash table. In this sense the preferred embodiment is said to be “cache sensitive”. The design of hash table in the preferred embodiment is able to support redistribution of data items in the buckets of the table. If the size of the underlying data set (size N) increases, and the hash table is not resized, the average load factor (N/X—where X is the size of the hash table) will increase, resulting, on average, in more time being required for searching through a hash bucket.

[0042] The design of the preferred embodiment relies on the fact that there will likely be unused bytes available in each hash bucket, given the requirement that each bucket be aligned with cache line boundaries. The available data space in the bucket is used to create a two-level hash table which facilitates resizing of the hash table.

[0043] FIG. 2 shows the structure of the hash table of the preferred embodiment, at a level illustrating the two-level structure of the hash table. The hash table of the preferred embodiment is comprised of a fixed set of X hash bucket groups (rather than a fixed set of X hash buckets). FIG. 2 shows the groups by example as bucket groups 60, 62, 64 (the contents of bucket group 60 are shown, contents for bucket groups 62, 64 are omitted). Each hash bucket group contains one latch which controls access to all the hash buckets within the group. The number of hash bucket groups—X—(and hence the number of latches) is related to the maximum number of threads that can exist in the system at any given time. Each hash bucket group is cache line aligned and some of the available bytes left as a result of the padding are used for a fixed number of inline hash buckets that will fit in to the hash bucket group. FIG. 2 shows bucket group 60 with an inline bucket array of three buckets (0, 1, 2). It will be appreciated that, although not illustrated in the simplified presentation of FIG. 2, the arrangement of the inline array of buckets in the preferred embodiment conforms to the structure shown in FIG. 1.

[0044] As indicated in FIG. 2, a number of bytes in each hash bucket group are used for a hash bucket group header which is used for the management of each hash bucket group, as is described below. The header points to an overflow bucket array, when required (overflow bucket array 66 in FIG. 2). When a hash table of the preferred embodiment is initially created, there is no overflow bucket array for each hash bucket group.

[0045] In the preferred embodiment, the initial number of bucket groups in the hash table (X) is based on two things:

• • [0046] 1. The number of threads that can co-exist in the system, and
  • [0047] 2. The product of X and the number of inline buckets per bucket group should be large enough to achieve the desired LOAD FACTOR.
    In the preferred embodiment, the number of inline buckets is dependent on how many bytes are left for cache line padding in the hash bucket group.

[0048] In operation, the hash table of the preferred embodiment is accessed by a thread seeking to locate, add or remove a data item D in the following manner:

[0049] The thread determines which hash bucket group the data item D maps to using modulo arithmetic based on the number of hash bucket groups X (this is similar to the calculation carried out for a single-level hash table described above).

[0050] The thread obtains the latch for the hash bucket group (in SHARE mode if the thread is searching for a data item and in EXCLUSIVE mode if the thread inserting or removing data item D). If the thread is inserting or removing a data item D then it updates the numDataItemsChainedInGroup accounting variable.

[0051] Within each hash bucket group is a small sized hash table (the second level of the two-level hash table). The number of buckets in this hash table is “numInlineBucket+numOverFlowBucket” (the total number of buckets in the group). To determine the appropriate bucket to access to determine the presence of D or where D should be added, a second hash function is applied and modulo arithmetic is performed based on the size of this second level hash table to map to the appropriate bucket.

[0052] When the hash table is initially allocated, it is sized appropriately (the appropriate X is selected), so that no overflow buckets are required. Overflow buckets are part of a separate cache line and therefore accessing the overflow bucket array causes a cache miss. Overflow buckets are used in the design of the preferred embodiment when a hash bucket group is resized. This takes place by allocating an overflow bucket array (such as overflow bucket array 66 in FIG. 2). Data items within the hash bucket group may then be redistributed over the new buckets using the new hash function resulting from increasing the size of the second level hash table within the hash bucket group.

[0053] In the design of the preferred embodiment, each hash bucket group is separately resizable.

[0054] In a simple case requiring a resize (as a result, for example, of the size of the underlying data set changing), one thread can be assigned to resize all the buckets. This thread starts with a first hash bucket group and selects all the bucket groups in turn. As the thread processes each hash bucket group it obtains the latch for the bucket group in EXCLUSIVE mode. Thus locking out other threads from accessing the bucket group being processed, but no other bucket group. The thread allocates (or reallocates in the event there is already an overflow array) a new overflow array, updates the bucket group header data that records the number of overflow buckets (numOverflowBucket) and re-distributes the buckets in the bucket group.

[0055] The design of the preferred embodiment can be used for bucket group resizing such that the resizing occurs asynchronously based on running conditions. Using this approach, a special worker thread periodically scans each the hash bucket group and calculates its load factor using the numDataItemsChainedInGroup accounting variable referred to above. If the load factor is too high or too low (in comparison with a defined threshold) for a given bucket group then the worker thread latches the bucket group and resizes only that group.

[0056] In an alternative approach, special worker thread is not needed. In this implementation of the preferred embodiment, any thread using a bucket group that obtains an EXCLUSIVE mode latch on a bucket group will determine if the group needs resizing (a good Samaritan approach). Since threads that are adding or removing an item in a bucket group need to obtain a latch in EXCLUSIVE mode, the additional cost to perform the resizing check is not high.

[0057] This technique of resizing is useful where the distribution of data is not uniform. Each bucket group can be a different size.

[0058] In the preferred embodiment, only the hash bucket group indexes (the first level of the hash table) are cached. Since the first level hash table is not resized, then there is no need to invalidate any copies of index values made by accessing threads or processes (in local variables or registers, for example), when the table is resized. As the copy of the index value stored in a local variable or register is referred to as a cached copy of the hash index value, this aspect of the preferred embodiment may be considered to be “cache sensitive” feature.

[0059] In summary, according to one aspect of the present invention, there is provided a hash table for data items that has two levels, the levels being made up of hash buckets and bucket groups. The hash buckets in the hash table are both inline in the bucket groups and in overflow arrays pointed to by the bucket groups. The hash buckets have properties entries arranged in a linked list in each bucket. Each property entry contains a pointer to a data item and representative values for the data item to which it points. Other aspects are detailed above.

[0060] Although a preferred embodiment of the present invention has been described herein in detail, it will be appreciated by those skilled in the art that other variations may be made. Such variations may be made without departing from the spirit of the invention or the scope of the appended claims.

[0061] Although the present invention has been described in accordance with the embodiments shown, one of ordinary skill in the art will readily recognize that there could be variations to the embodiments and those variations would be within the spirit and scope of the present invention. Accordingly, many modifications may be made by one of ordinary skill in the art without departing from the spirit and scope of the appended claims.