member: implement HT mode
authorYipeng Wang <yipeng1.wang@intel.com>
Wed, 4 Oct 2017 03:12:20 +0000 (20:12 -0700)
committerThomas Monjalon <thomas@monjalon.net>
Sun, 8 Oct 2017 22:02:45 +0000 (00:02 +0200)
commit904ec78a239c249ff5fb688809d9a64e8242814e
treeaba22f2dd5ffb996a38e6f6a5c603b385a46719f
parent857ed6c68cf2800a5e8311c431389b9ba50d7949
member: implement HT mode

One of the set-summary structures is hash-table based
set-summary (HTSS). One example is cuckoo filter [1].

Comparing to a traditional hash table, HTSS has a much more
compact structure. For each element, only one signature and
its corresponding set ID is stored. No key comparison is required
during lookup. For the table structure, there are multiple entries
in each bucket, and the table is composed of many buckets.

Two modes are supported for HTSS, "cache" and "none-cache" modes.
The non-cache mode is similar to the cuckoo filter [1].
When a bucket is full, one entry will be evicted to its
alternative bucket to make space for the new key. The table could
be full and then no more keys could be inserted. This mode has
false-positive rate but no false-negative. Multiple entries
with same signature could stay in the same bucket.

The "cache" mode does not evict key to its alternative bucket
when a bucket is full, an existing key will be evicted out of
the table like a cache. Thus, the table will never reject keys when
it is full. Another property is in each bucket, there cannot be
multiple entries with same signature. The mode could have both
false-positive and false-negative probability.

This patch adds the implementation of HTSS.

[1] B Fan, D G Andersen and M Kaminsky, “Cuckoo Filter: Practically
Better Than Bloom,” in Conference on emerging Networking
Experiments and Technologies, 2014.

Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
Reviewed-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
lib/librte_member/Makefile
lib/librte_member/rte_member.c
lib/librte_member/rte_member.h
lib/librte_member/rte_member_ht.c [new file with mode: 0644]
lib/librte_member/rte_member_ht.h [new file with mode: 0644]