2013 · 59 citations · 11 references
ComputingComputer EngineeringComputer ScienceCloud InfrastructureDatabasesReconfigurable ComputingData PipelinesHash TablesHigh-throughput ComputingScalability ArchitectureCollision HandlingConcurrent Hash TablesDistributed Key-value StoresHash CollisionsHash Table ImplementationsKey-value StoresPipeline ScalabilityScalability
Common web infrastructure relies on distributed main memory key-value stores to reduce access load on databases, thereby improving both performance and scalability of web sites. As standard cloud servers provide sub-linear scalability and reduced power efficiency to these kinds of scale-out workloads, we have investigated a novel dataflow architecture for key-value stores with the aid of FPGAs which can deliver consistent 10Gbps throughput. In this paper, we present the design of a novel hash table which forms the centre piece of this dataflow architecture. The fully pipelined design can sustain consistent 10Gbps line-rate performance by deploying a concurrent mechanism to handle hash collisions. We address problems 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 parametrized to work with different memory types operating at different access speeds and latencies. We deployed this hash table in a memcached prototype to index 2 million entries in 24GBytes of external DDR3 DRAM while sustaining 13 million requests per second for UDP binary encoded memcached packets which is the maximum packet rate that can be achieved with memcached on a 10Gbps link.
11
Rasmus Pagh, Flemming Friche Rodler · Journal of Algorithms · 2004 · 1.1K citations
Workload analysis of a large-scale key-value store
Berk Atikoglu, Yuehai Xu, Eitan Frachtenberg et al. · 2012 · 904 citations
Yossi Azar, Andrei Broder, Anna R. Karlin et al. · SIAM Journal on Computing · 1999 · 754 citations
Distributed caching with memcached
Brad Fitzpatrick · Linux journal · 2004 · 513 citations
Distributed caching with memcached
FitzpatrickBrad · Linux journal · 2004 · 388 citations