Patent Description:
Hashing algorithms are commonly used to store data objects in a memory of a computer system. The process of identifying a location in the memory for a data object based on a hashing algorithm can be resource intensive affecting the performance of a data storage and/or retrieval processes. It is therefore desirable to provide efficient data object storage and retrieval.

In <CIT> techniques for storing key-value pairs in a hash table are described.

The present disclosure relates to methods and systems for the storage of objects in a memory of a computer system. Specifically, objects are stored in an object store having a plurality of locations and a location for an object is determined using a hashing algorithm such as any suitable hashing algorithm as known to those skilled in the art. Furthermore, in the event that a location in the object store identified by a hashing algorithm for the storage of an object is already occupied, a linear probing technique is employed, as is well known in the art. Briefly, the linear probing technique involves storing a data object at a sequentially most proximate unoccupied location in the object store traversing the store in a predetermined direction (typically at locations of increasing address). Notably, in some examples, the linear probing technique can include wrapping or wrap-around in which a traversal for identifying an unoccupied location loops to a starting location in the object store when a final, last or end location of the object store has been found to be occupied.

Examples of the present disclosure provide performance benefits in the object storage process. These benefits are realised by the provision of: a map of binary flags, each flag corresponding to a storage location in the object store, and each flag indicating a state of occupation of the storage location as either occupied or unoccupied; and a set of truncated hash keys, the set including one truncated hash key entry for each location in the object store, whereby unoccupied or not yet occupied locations may have a null, zero or non-entry in the set. The flags and hash key set provide considerable performance advantages in the determination of identity of an object to be stored at a determined location in the object store and an object already stored in the determined location. This includes determining identity at locations sequentially subsequent to the determined location, where non-identity is determined. Where identity can be determined then the object is already stored in the object store and further storage is not required. Where identity is not determined then continued traversing for a free location is occasioned. In existing techniques, a comparison process to check for identity as part of a linear probing process undertakes a direct reference to the object store to determine occupation of a location and a full object comparison to determine identity. Examples of the present disclosure do not require direct reference to the object store to determine occupation which is instead determined more efficiently by the bitwise storage of occupation information in the map of binary flags. Furthermore, examples of the present disclosure do not require a comparison of all data objects to determine identity - such comparison being resource intensive especially for large multi-byte data objects. Rather, examples of the present disclosure compare a hash key of an object for insertion with a partial hash key stored at a determined location in the hash key set. This comparison of a partial hash key involves fewer resources than a direct object comparison and provides performance gains where non-identity can be determined on this basis alone (so avoiding direct object comparison in such cases). In accordance with examples of the present disclosure, direct comparison of objects is reserved only for those cases where there is observed to be identity of that part of a partial hash key stored for a location with a corresponding part of a hash key for the data object to be stored.

Thus, in this way, examples of the present disclosure provide considerable performance advantages over known techniques, especially for larger data objects. In particular, implementations of data object storage in accordance with examples of the present disclosure have exhibited performance exceeding those of the prevailing existing techniques. The performance benefit is especially realised for larger sized data objects. In principle, the performance improvement should be observable for data objects exceeding the size of the truncated hash - such as data objects exceeding 32bits. In practice, the performance benefit is particularly notable for the storage of data objects over <NUM> bytes in size. The performance improvement is particularly beneficial for the storage of data objects over <NUM> bytes in size. The performance improvement is acutely beneficial for the storage of data objects over <NUM> bytes in size.

<FIG> is a block diagram of a computer system suitable for the operation of examples of the present disclosure. A central processor unit (CPU) <NUM> is communicatively connected to a storage <NUM> and an input/output (I/O) interface <NUM> via a data bus <NUM>. The storage <NUM> can be any read/write storage device such as a random access memory (RAM) or a non-volatile storage device. An example of a non-volatile storage device includes a disk or tape storage device. The I/O interface <NUM> is an interface to devices for the input or output of data, or for both input and output of data. Examples of I/O devices connectable to I/O interface <NUM> include a keyboard, a mouse, a display (such as a monitor) and a network connection.

<FIG> is a component diagram of an arrangement for storing a data object <NUM> in a memory <NUM> of a computer system in accordance with examples of the present disclosure. The memory <NUM> includes an object store <NUM>, a set of occupancy flags <NUM> and a set of truncated hash keys <NUM>. The data object <NUM> is stored at a location in the object store <NUM> determined by a hashing process <NUM>.

The hashing process <NUM> determines a location for the data object <NUM> based on a hashing algorithm that generates a hash value for the data object, as will be apparent to those skilled in the art. The hash value for the data object <NUM> serves to indicate a location in the object store <NUM> for the storage of the data object <NUM>. The occupancy flags <NUM> are binary flags each indicating a state of occupancy of a location in the object store <NUM>. For example, a binary flag having a value of zero can indicate occupation of a corresponding location in the object store <NUM>, and a binary flag having a value of one can indicate non-occupation. Occupation of a location refers to the storage of a data object at the location in the data store. Notably, the state of a flag is authoritative with respect to the storage or not of a data object at a location in the object store <NUM>. That is to say that a location in the object store <NUM> may contain data and a determination of whether that data constitutes a data object stored in the location is determined with reference to an occupancy flag corresponding to that location. In this way, an object can be deleted from the object store <NUM> by merely indicating the location of the object as unoccupied in the occupancy flags <NUM>.

The truncated hashes <NUM> has an entry for each location in the object store <NUM>. When an object is stored at a location in the object store <NUM> a partial hash key value for the object is stored in a corresponding entry in the set of truncated hashes <NUM>. The partial hash key value constitutes a portion of the hash key for the data object suitable for comparison with hash keys for other data objects to determine a likelihood of identity of data objects. The partial hash key is a truncation of the hash key for a data object, such as portion of the hash key. In preferred examples, the truncated hash key is one of: a set of least significant bits of the hash key; a set of most significant bits of the hash key; or a set of bits taken from predetermined range of bit positions within the hash key. Truncated hash keys are stored in the set <NUM> when data objects are stored in the object store <NUM>.

<FIG> is a flowchart of a method of storing the data object <NUM> in the object store of <FIG> in accordance with examples of the present disclosure. Initially, at step <NUM>, the method employs the hashing process <NUM> to determine a location in the object store <NUM> for the storage of the data object <NUM>. At step <NUM> the method determines if the determined location in the object store <NUM> is already occupied. This determination can be made efficiently with reference to the occupancy flags <NUM>. Where the location is not occupied, the method stores the data object <NUM> in the object store <NUM> at the determined location at step <NUM> and returns the location of the stored item at step <NUM>.

Where the location is determined to be occupied the method proceeds to step <NUM> where a truncated hash for the determined location is compared with the hash of the data object <NUM> to determine if the data object may be identical to an object already stored at the location in the object store <NUM>. Where the truncated hash matches a corresponding portion of the hash key for the data object <NUM> at step <NUM>, the method proceeds to step <NUM> where an object stored at the determined location is compared with the data object <NUM> to confirm identity. If identity of the objects is confirmed at step <NUM>, the data object is determined to be already stored in the object store at step <NUM> and the location of the existing stored object is returned at step <NUM>.

Where the truncated hash did not match the hash key of the data object <NUM> at step <NUM>, or the objects were not found to be identical at step <NUM>, the method determines if there are more locations in the object store <NUM> to be checked at step <NUM>. If there are no more locations then the object store <NUM> is determined to be full at step <NUM>. Otherwise, a next location in the object store is considered from step <NUM> and the method iterates to step <NUM> for the new location. Notably, the operation of <FIG> can involve looping or wrapping to a first, start or lowest location following traversal of a last, end or highest location.

In some examples, the method of <FIG> further provides a direct pointer to the location of the stored data object in the object store <NUM>, such as a memory pointer or the like. Such a pointer can be provided at, for example, step <NUM>.

<FIG> is a flowchart of a method of removing a data object in the object store of <FIG> in accordance with examples of the present disclosure. Initially, at step <NUM>, the method deletes the data object at an identified location in the object store <NUM>, such deletion can be made by merely updating the occupancy flag for the location and, optionally, by actually deleting or overwriting the data stored at the location in the object store <NUM>. Thus, the deletion renders the location newly unoccupied. For example, the method of <FIG> may operate on the basis of a pointer or address of a particular location in the object store <NUM> in which case a data object stored therein is deleted. Alternatively, the method of <FIG> may operate on the basis of a hash key or a data object from which a hash key is generated, a location for such hash key or data object being identified in the object store <NUM> as part of the process of step <NUM>.

Subsequently, at step <NUM>, the method identifies a sequentially next location in the object store <NUM> and determines if the next location is occupied. Notably, the operation of the method of <FIG> can involve looping or wrapping to a first, start or lowest location following traversal of a last, end or highest location. If the next location is not occupied the method ends, otherwise the method traverses to the next location at step <NUM>. At step <NUM> the method examines a data object stored in the location and determines a preferred location for the data object based on the hashing algorithm. Notably, the location at which the data object is stored may not be the location indicated by a hash key for the data object since the data object may have been stored at a different location in the object store <NUM> due to occupancy of the proper location according to the insertion method of <FIG>. Accordingly, there can be considered to be an actual location of the data object (the current location) and a preferred location of the data object (that location in the object store <NUM> indicated by the hashing algorithm).

At step <NUM> the method undertakes a determination whether the data object stored at the current location should be moved to the newly unoccupied location. This determination can be made by comparing the preferred location for the data object determined at step <NUM> with the newly unoccupied location. If the newly unoccupied location is closer to, or the same as, the preferred location determined at step <NUM> then the data object at the current location should be moved to the newly unoccupied location. This move takes place at step <NUM>. As part of this move, the data object is copied to the newly unoccupied location and is deleted from the current location (such as by marking the current location as unoccupied). Thus, the current location becomes newly unoccupied and, thus, the newly unoccupied location.

The method iterates through all occupied locations via step <NUM> until either, at step <NUM>, all locations in the object store <NUM> have been traversed or, at step <NUM>, an unoccupied location is encountered. Thus, in this way, object deletion from the object store <NUM> is supplemented by moving objects to be more proximate to their preferred location according to the hashing algorithm.

Notably, in examples where a direct pointer or reference to a location of a stored object in the object store <NUM> is provided by a data object insertion method such as that of <FIG>, such direct pointers will cease to be valid following the deletion method of <FIG> since the deletion method can involve the moving of data objects in the object store <NUM>. Accordingly, it is necessary to indicate that such direct pointers or references cease to be valid following a deletion by, for example, marking such references as expired. In one example, direct pointers or references have associated an identifier of an age, generation, or other indicator corresponding to their validity and their invalidity is indicated by a global change to an age, generation or such indicator such that all pointers or references having old, expired, outdated or non-current indications are treated as expired.

One exemple of the present disclosure will now be described. The exemple is known as PHashSet and can be provided as, for example, a C++ template which can be used with most data types that provide an implementation of std::hash to create a hash value, and an implementation of std::equal_to to check hash key equality. Functional methods known as reserve, find, insert and erase methods will be described and a linear probing strategy is adopted. Hereinbelow, the term "hash set" is used to refer to the combination of the object store <NUM>, the occupancy flags <NUM> and the truncated hashes <NUM> as previously described.

PHashSet provides a stable hash set on insertion, i.e. elements do not to move on insertion. This is not the case when data objects are erased as erasure may cause objects to be moved. Such movement could cause unexpected behaviour, so a smart-pointer can be provided. The smart-pointer is returned by an insert method and can be passed to an erase method. According to this example, when a smart-pointer is populated it stores the number of erases that have taken place in the hash set at that time. When a smart-pointer is used, the number of erasures associated with the pointer is checked to see if a global count of erasures differs from that number. If there is a mismatch between erasure counts then a system fault (e.g. segfault, reference fault, or similar) can be generated to indicate that the smart-pointer is outdated. In such an event, the find method can be employed to generate a new smart-pointer for a data object.

PHashSet creates, at initialisation, a set of <NUM>-bit words to use as flags to indicate the presence or absence of a valid data object in a particular location (i.e. occupancy flags <NUM>). One bit is used per location. For example, a binary <NUM> indicates that the location is unoccupied, and a binary <NUM> indicates that the location is occupied.

A reserve method can be provided to generate a fixed size hash set having a suitably sized object store <NUM> and suitably configured data structures for the occupancy flags <NUM> and the truncated hashes <NUM>. Required memory is preferably pre-allocated for a given size of the object store <NUM> allowing for reduced per-item timing deviation during execution.

Only hash set sizes which are a power of <NUM> (e.g. <NUM>, <NUM>, etc) are used, with a minimum of <NUM> locations. PHashSet stores the set of flag words as occupancy flags <NUM>, a <NUM>-bit truncation of a hash for every stored data object as truncated hashes <NUM>, and a copy of the items being stored as object store <NUM>.

In the exemple, an insertion/find method is provided. This method will preferably insert a given data object into the hash set, returning an indicator to it, or, for an object already present in the hash set, it will return the object, it's hash key, location and/or smart-pointer.

On insertion PHashSet computes a hash for a given data obejct and masks it against the hash set size (minus one, to account for the 0th element). A flag word is located for the intended location which is then checked to see if the preferred location is in use. If it is, then the hash value for the item stored at the preferred location is compared against the <NUM>-bit truncated hash for the new data object. If the truncated hash matches the corresponding portion of the hash value then the new and stored data objects are compared using std::equal_to. If the data objects are equal (i.e. identity), then the data object is determined to be already stored in the hash set and a reference to it is returned, such as a smart-pointer as previously described. Checking the hash equality initially with the truncated hash improves performance significantly because comparing <NUM>-bit integers is significantly quicker than comparing larger data objects. If the location is in use but fails either the hash similarity or data object equality checks, then a next location is selected in the object store <NUM>, advancing to the next flag word if necessary. This is known as linear probing and is well suited to PHashSet because it could involve checking the next bit along in the empty flag words, which is very cache friendly. The occupancy check, truncated hash check and data object identity check are then repeated as necessary until the data object is located in the hash set or an empty location is encountered, at which point the data item is inserted and a pointer to it returned within a smart-pointer.

PHashSet detects if the set is full and returns an indicator to state that this is the case.

An exemplary data object erase method is provided accepting either a data object being stored or a smart-pointer previously returned by the insert/find method. In the former case the procedure starts by finding the element within the hash set, resulting in a smart-pointer being produced. Subsequently, the hash set locates the flag word for the location being cleared (erased) and sets it to indicate that the location is newly unoccupied. The next location (in the next flag word if appropriate) is then checked, and if that is empty the function completes. If the next location is not empty then PHashSet obtains the hash for the data object in that next location to see if it would be closer to its preferred location if it were in the location that was just erased (the newly unoccupied location). If so, then the object is moved to the newly unoccupied location. This procedure repeats until an empty location is found (or the entire hash set is traversed).

It is important to note that data objects that would not be made closer to their preferred location by being moved are not moved, and other objects might leapfrog them to be closer to their ideal slot. This process is illustrated in <FIG> which illustrates an exemplary object store for the storage of objects in accordance with examples of the present disclosure. In the example of <FIG>, data object "A" hashes to location <NUM> in an exemplary object store <NUM>. On insertion, object "A" is thus placed in location <NUM>. Data object "B" also hashes to location <NUM>, but because "A" is stored in location <NUM> object "B" is forced to be placed in location <NUM>. Data object "C" hashes to location <NUM> and is placed there. Data object "D" hashes to location <NUM>, but cannot go in any of locations <NUM>, <NUM> or <NUM> because they are occupied, so object "D" is stored in location <NUM>. If item "A" was subsequently deleted then object "B" would move to location <NUM> and object "D" would move to location <NUM>. Object "C" would not move. This procedure would be the same if the chain began in location <NUM> and wrapped around to location <NUM>.

Data objects being deleted from the locations may not be actually affected by an erase operation, unless overwritten by another object being moved on top of them. Instead, PHashSet can employ the occupancy flags <NUM> to determine whether an object at a location should be read or not. This is a significant gain in performance.

When an erase is performed the erase count is incremented, which will cause all smart-pointers created before that time to create an error. This could be refined at a cost to performance and memory use, by having an erase count per flag word with each smart-pointer tracking the erase count for its flag word; only becoming invalid when that flag word is altered during an erase.

A further exemple of the present disclosure is illustrated with respect to <FIG> which illustrates an exemplary arrangement of data structures in accordance with examples of the present disclosure. According to the further exemple, instead of cached hashes, objects, and empty flag words being stored in separate data structures such as separate arrays, they can be stored as nested objects. Such an arrangement can be referred to as PHashSetStruct which is a container object containing a single flag word (<NUM> bits, indicating <NUM> slots) as well as a set of <NUM> hashes, each directly followed by the object that created them, as illustrated in <FIG>. This means when searching for a hash key (in the insert/find method), loading the precomputed hash value is also likely to load the object into the cache, meaning checking for key equality is less likely to cause a cache miss.

Insofar as examples of the present disclosure are implementable, at least in part, using a software-controlled programmable processing device, such as a microprocessor, digital signal processor or other processing device, data processing apparatus or system, it will be appreciated that a computer program for configuring a programmable device, apparatus or system to implement the foregoing described methods is envisaged as an aspect of the present disclosure.

Suitably, the computer program is stored on a carrier medium in machine or device readable form, for example in solid-state memory, magnetic memory such as disk or tape, optically or magneto-optically readable memory such as compact disk or digital versatile disk etc., and the processing device utilises the program or a part thereof to configure it for operation. The computer program may be supplied from a remote source embodied in a communications medium such as an electronic signal, radio frequency carrier wave or optical carrier wave. Such carrier media are also envisaged as aspects of the present disclosure.

Claim 1:
A computer implemented method of storing a data object (<NUM>) in a computer memory (<NUM>) wherein the data object is over <NUM> bytes in size and is stored at a location in an object store (<NUM>) as a portion of the memory, the location being determined by a hashing process (<NUM>) based on a generated hash key, the memory further storing: a set of <NUM>-bit binary words (<NUM>) in which each bit of each word identifies an occupancy state of a location in the object store such that an occupancy state of all locations is stored in the set of binary words; and a truncated hash key set (<NUM>) storing, for each occupied location in the object store, a truncated hash key for a data object stored at the location, each truncated hash key being <NUM> bits in length,
wherein:
the hashing process uses linear probing in which an occupancy of the location in the object store for storage of the data object is determined (<NUM>) by reference to the set of binary words, and the linear probing further determines (<NUM>) identity of the data object and an object stored in the occupied location, the identity being determined based on a comparison (<NUM>) of the stored truncated hash key for the occupied location with a corresponding part of the generated hash key for the data object, and
a determination of identity based on the comparison is confirmed (<NUM>) by a comparison of the data object for storage and a data object stored in the occupied location.