[dpdk-dev] [RFC] Cuckoo hash for DPDK 2.1

[De Lara Guarch, Pablo]

Hi all,

This RFC is to describe a proposed replacement for the existing rte_hash implementation,
using the cuckoo hash scheme (see http://www.cs.cmu.edu/~dongz/papers/cuckooswitch.pdf),
which should provide better performance, in terms of lookup time, as well as a higher load factor.

This new implementation also shall offer several improvements compared to the existing one, such as:

-        Data return: existing implementation returns an index to the bucket where the key is stored,

whereas the new implementation shall return 8-byte integers or pointers to external data.



-        Increased key length: key length shall be increased more than the existing 64 bytes,

without having a big penalty on performance



-        Increased burst size: current implementation only allows 16 lookups at the same time,

whereas the new implementation shall allow more than that (probably 64)



-        Opening addressing: current implementation does not allow new keys to be added

if its target bucket is full, whereas with Cuckoo hash, it offers an alternative location to store the key.

I am currently working on the implementation, considering several options:


-        Using a single table to store all the signatures, regardless they have used their primary or secondary hash function.



-        Using two tables to store the signatures, one for primary hashes and another for the secondary hashes.


I need to do some testing on both implementations to know which one is more suitable for DPDK.

Any comments/ideas welcome.

Thanks
Pablo