Systems, methods and computer program products for reducing hash table working-set size for improved latency and scalability in a processing system

A computer program product for storing data in a memory device, the computer program product comprising:

• a tangible storage medium readable by a computer system and storing instructions for execution by the computer system for performing a method comprising:
• performing compression on a data item by compressing key portions and payload portions;
• computing a plurality of hash functions of data values in the data item;
• determining a corresponding memory location for one of the plurality of hash functions of data values in the data item, wherein each memory location is of a cacheline size;
• storing data in the memory location, comprising:
• storing the data item in the memory location, wherein each memory location stores a plurality of stored data items;
• storing a compressed key portion of all data items contiguously within the memory location;
• storing a compressed payload portion of all data items contiguously within the memory location, wherein the memory location comprises a bucket in a bucketized hash table;
• and each bucket is sized to store the multiple pairs of compressed key portions and compressed payload portions;
• receiving a compressed input key;
• computing a hash value for the compressed input key;
• probing one or more buckets in the hash table for a match, each bucket including multiple chunks;
• wherein probing comprises:
• for a bucket in the hash table, searching chunks in that bucket by comparing the hash value with stored values, such that if a value stored in a chunk equals the hash value of the compressed input key, then a match is declared;
• if a value stored in a chunk correspond to an empty slot, then a mismatch is declared;
• otherwise, if no chunks remain to be searched in the bucket, searching a next bucket in the hash table;
• and
• wherein multiple key portions include multiple pairs comprising compressed key portions and compressed payload portions stored in a fully associative manner and packed as bit-aligned in a fixed-sized memory location.

A system for storing data in a memory device, comprising:

• a hash table module that performs a compression operation on a data item by compressing key portions and payload portions;
• an insertion module that computes a plurality of hash functions of data values in the data item, and determines a corresponding memory location for one of the plurality of hash functions of data values in the data item, wherein each memory location is of a cacheline size;
• wherein the insertion module stores data in the memory location by:
• storing the data item in the memory location, wherein each memory location stores a plurality of stored data items;
• storing a compressed key portion of all data items contiguously within the memory location;
• storing a compressed payload portion of all data items contiguously within the memory location, wherein the memory location comprises a bucket in a bucketized hash table;
• and each bucket is sized to store the multiple pairs of compressed key portions and compressed payload portions;
• a probing module that receives a compressed input key, computes a hash value for the compressed input key, and probes one or more buckets in the hash table for a match, each bucket including multiple chunks;
• wherein the probing module probes by:
• for a bucket in the hash table, searching chunks in that bucket by comparing the hash value with stored values, such that if a value stored in a chunk equals the hash value of the compressed input key, then a match is declared;
• if a value stored in a chunk correspond to an empty slot, then a mismatch is declared;
• otherwise, if no chunks remain to be searched in the bucket, searching a next bucket in the hash table;
• and
• wherein multiple compressed key portions include multiple pairs comprising compressed key portions and compressed payload portions stored in a fully associative manner and packed as bit-aligned in a fixed-sized memory location.