high performance computing on graphics processing units: hgpu.org

In this report, we present an OpenCL-based design of a hashing function which forms a core component of memcached [1], a distributed in-memory key-value store caching layer widely used to reduce access load between web servers and databases. Our work has been inspired by recent research investigations on dataflow architectures for key-value stores that can sustain a consistent 10Gbps line-rate and which bring significant latency benefits through tight coupling of network interface, memory and compute resources [2]. At the heart of a key-value store architecture, such as memcached, is a hash table, which in essence determines the memory address of a value as a function of an incoming key. This is achieved by first applying the chosen hash function to the contents of a key to produce an address in the table. From this location, a pointer to the address within the value storage area can be retrieved. In the work reported here, we focus on the hashing function stage only. In particular, we have focused on the OpenCL design of the Bob Jenkins lookup3 hash function [3], which is used in the open source software version of memcached and is well known to work effectively over a broad range of key types. This function processes variable sized keys iteratively in 96bit chunks and each chunk is split into three 32bit numbers, which are added to a set of state variables. Before the next chunk is read, these state variables are mixed using addition, subtraction and XOR operations. Due to the inherent feedback loop, the hash function cannot be easily pipelined.