A Hash Table for Line-Rate Data Processing
Authors:
Open Access
- 24 March 2015
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Reconfigurable Technology and Systems
- Vol. 8 (2) , 1-15
Abstract
FPGA-based data processing is becoming increasingly relevant in data centers, as the transformation of existing applications into dataflow architectures can bring significant throughput and power benefits. Furthermore, a tighter integration of computing and network is appealing, as it overcomes traditional bottlenecks between CPUs and network interfaces, and dramatically reduces latency. In this article, we present the design of a novel hash table, a fundamental building block used in many applications, to enable data processing on FPGAs close to the network. We present a fully pipelined design capable of sustaining consistent 10Gbps line-rate processing by deploying a concurrent mechanism to handle hash collisions. We address additional design challenges such as support for a broad range of key sizes without stalling the pipeline through careful matching of lookup time with packet reception time. Finally, the design is based on a scalable architecture that can be easily parameterized to work with different memory types operating at different access speeds and latencies. We have tested the proposed hash table in an FPGA-based memcached appliance implementing a main-memory key-value store in hardware. The hash table is used to index 2 million entries in 24GB of external DDR3 DRAM while sustaining 13 million requests per second, the maximum packet rate that can be achieved with UDP packets on a 10Gbps link for this application.Keywords
Funding Information
- Enterprise Computing Center
This publication has 14 references indexed in Scilit:
- IbexProceedings of the VLDB Endowment, 2014
- Acceleration of SQL Restrictions and Aggregations through FPGA-Based Dynamic Partial Reconfiguration2013
- An FPGA memcached appliance2013
- Complex event detection at wire speed with FPGAsProceedings of the VLDB Endowment, 2010
- More Robust Hashing: Cuckoo Hashing with a StashSIAM Journal on Computing, 2010
- Streams on wiresProceedings of the VLDB Endowment, 2009
- The shunt2007
- A reconfigurable perfect-hashing scheme for packet inspection2005
- Cuckoo hashingJournal of Algorithms, 2004
- Using multiple hash functions to improve IP lookups2002