[dpdk-dev] [PATCH v6 0/7] Add Membership Library
yipeng1.wang at intel.com
Wed Oct 4 05:12:18 CEST 2017
DPDK Membership Library provides an API that can be used by many DPDK
applications to conduct one or more set-membership tests (we mention some
possible use cases below, but interested readers can refer to
 for a wider survey of use cases).
The basic functionalities of the Membership Library include
inserting a new member, deleting an existing member, and querying the existence
of a member. The query result would indicate with high accuracy which specific
set this member belongs to among a group of sets.
The Membership Library is an extension and generalization of traditional filter
data structures [2,3], which maintain a space-efficient “set-summary”.
There are two advantages of using such a set-summary rather than operating on a
“full-blown” complete list of elements: firstly it has a much smaller storage
requirement than storing the whole list of elements, and secondly set membership
tests (or other operations) is much more efficient than searching through the
complete list of elements.
A membership test for an element will return the set this element belongs to if
found (or return "not-found") with high accuracy. If needed, the accuracy of the
membership tests could be further increased with larger storage space.
Set-summary is a fundamental data aggregation component that can be used in many
network applications. It is a crucial structure to address performance and
scalability issues of diverse applications including overlay networks, wild card
flow classification, web-caches, load balancing, connection tracking,
data-centric networks, flow table summaries, network statistics and traffic
monitoring. Our Proof of Concept (PoC) using set-summary to optimize flow lookup
in Open vSwitch (OvS) shows a speedup of about 2-3X.
This patch set implements two types of set-summaries, i.e., hash-table based
set-summary (HTSS) and Vector Bloom Filter (vBF). HTSS supports both the
non-cache and cache modes. The non-cache mode can incur a small chance of
false-positives which is the case when the set-summary indicates a key belongs
to a given set while actually it is not. The cache mode can also have
false-negatives in addition to false-positives. False-negatives means the case
when the set-summary indicates a key does not belong to a given set while
actually it does. This happens because cache mode allows new key to evict
existing keys. vBF only has false-positives similar to the non-cache HTSS.
However, one can set the false-positive rate arbitrarily. HTSS's
false-positive rate is determined by the hash-table size and the signature size.
 A Broder and M Mitzenmacher, “Network Applications of Bloom Filters: A
Survey,” in Internet Mathematics, 2005.
 B H Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,”
Communications of the ACM, 1970.
 B Fan, D G Andersen and M Kaminsky, “Cuckoo Filter: Practically Better Than
Bloom,” in Conference on emerging Networking Experiments and Technologies, 2014.
- member lib: minor coding style changes from Pablo's comment and checkpatch
- member lib: minor log message changes.
- member lib: incorperate Pablo's review comments, including: multiple places
with coding style issues, change variable/function names to be more clear,
reorder code blocks, add descriptions, use macros for constant numbers,
fix bugs in log message, etc.
- test: modify the deletion function test to cover more cases.
- test: add check in performance test to check false negatvie for HT non-cache
- MAINTAINERS: complete in multiple commits instead of one as Pablo suggested.
- member lib: change two hash function macros to be one. crc or jhash will be
chosen depending on the architecture.
- member lib: use dynamic log type instead of static one by Thomas' comment.
- member lib: code cleanups (remove unnecessary code, change variable name,
coding style, etc).
- member lib: reorder members in setsummary struct to be more cache friendly.
- member lib: setsummary struct member "name" should be char array rather than
char pointer. Fixed.
- member lib: add check for two hash seeds to make sure they are not equal.
- member lib: vBF lookup speed optimization.
- member lib: revise comments in various places as Pablo suggested.
- member lib: change "void *" to "struct rte_member_setsum *" in public API as
Pablo suggested. test case is modified accordingly to directly use the struct.
- member lib: change order in rte_member_version.map as Pablo suggested.
- MAINTAINERS: change the maintainer block order according to Thomas' comment.
- test: add printf to show which section expects error messages. Change set
count to 16 from 32 for performance test.
- documentation: revise several places according to Pablo's and John's comments.
- documentation: update documentation to incorporate John's review.
- test: add bad parameter test functions to test the creation fail case.
- test: add find existing test.
- member lib: Add num_entries check in rte_member_create_ht.
- member lib: Add multiple checks for rte_member_create_vbf to avoid divide-by-0.
- member lib: remove unnecessary ret from rte_member.c according to Stephen's
- member lib: change the vBF creation function to be not too conservative.
Previous algorithm is too conservative on false positive.
- member lib: fix uninitialized issue fail gcc-4.8 in rte_member_find_existing.
- member lib: add rte_member_find_existing to version map.
- makefile: lib/librte_member/Makefile: change include order according to
- documentation: update the programmer guide for membership library.
Yipeng Wang (7):
member: implement main API
member: implement HT mode
member: implement vBF mode
member: add AVX for HT mode
member: enable the library
test/member: add functional and perf tests
doc: add membership documentation
MAINTAINERS | 8 +-
config/common_base | 5 +
doc/api/doxy-api-index.md | 3 +-
doc/api/doxy-api.conf | 1 +
doc/guides/prog_guide/img/member_i1.svg | 1613 ++++++++++++++++++++++++++++++
doc/guides/prog_guide/img/member_i2.svg | 36 +
doc/guides/prog_guide/img/member_i3.svg | 148 +++
doc/guides/prog_guide/img/member_i4.svg | 450 +++++++++
doc/guides/prog_guide/img/member_i5.svg | 163 +++
doc/guides/prog_guide/img/member_i6.svg | 332 ++++++
doc/guides/prog_guide/img/member_i7.svg | 399 ++++++++
doc/guides/prog_guide/index.rst | 14 +
doc/guides/prog_guide/member_lib.rst | 420 ++++++++
doc/guides/rel_notes/release_17_11.rst | 17 +
lib/Makefile | 2 +
lib/librte_member/Makefile | 51 +
lib/librte_member/rte_member.c | 337 +++++++
lib/librte_member/rte_member.h | 513 ++++++++++
lib/librte_member/rte_member_ht.c | 586 +++++++++++
lib/librte_member/rte_member_ht.h | 94 ++
lib/librte_member/rte_member_vbf.c | 350 +++++++
lib/librte_member/rte_member_vbf.h | 82 ++
lib/librte_member/rte_member_version.map | 16 +
lib/librte_member/rte_member_x86.h | 107 ++
mk/rte.app.mk | 2 +
test/test/Makefile | 3 +
test/test/test_member.c | 744 ++++++++++++++
test/test/test_member_perf.c | 654 ++++++++++++
28 files changed, 7148 insertions(+), 2 deletions(-)
create mode 100644 doc/guides/prog_guide/img/member_i1.svg
create mode 100644 doc/guides/prog_guide/img/member_i2.svg
create mode 100644 doc/guides/prog_guide/img/member_i3.svg
create mode 100644 doc/guides/prog_guide/img/member_i4.svg
create mode 100644 doc/guides/prog_guide/img/member_i5.svg
create mode 100644 doc/guides/prog_guide/img/member_i6.svg
create mode 100644 doc/guides/prog_guide/img/member_i7.svg
create mode 100644 doc/guides/prog_guide/member_lib.rst
create mode 100644 lib/librte_member/Makefile
create mode 100644 lib/librte_member/rte_member.c
create mode 100644 lib/librte_member/rte_member.h
create mode 100644 lib/librte_member/rte_member_ht.c
create mode 100644 lib/librte_member/rte_member_ht.h
create mode 100644 lib/librte_member/rte_member_vbf.c
create mode 100644 lib/librte_member/rte_member_vbf.h
create mode 100644 lib/librte_member/rte_member_version.map
create mode 100644 lib/librte_member/rte_member_x86.h
create mode 100644 test/test/test_member.c
create mode 100644 test/test/test_member_perf.c
More information about the dev