A proposal for a new DPDK library that is called “Membership Library”. It provides an API for DPDK applications to insert a new member, delete an existing member, or query the existence of a member in a given set, or a group of sets. For the case of a group of sets the library will return not only whether the element has been inserted before in one of the sets but also which set it belongs to.
The Membership Library is an extension and generalization of a traditional filter (for example Bloom Filter) structure that has multiple usages in a wide variety of workloads and applications. In general, the Membership Library is a data structure that provides a “set-summary” and responds to set-membership queries whether a certain member belongs to a set(s). 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 themselves, and secondly checking an element membership (or other operations) in this set-summary is much faster than checking it for the original full-blown complete list of elements. A membership test for an element will return the set this element belongs to or null (meaning not found) with very high probability of accuracy. Set-summary is a fundamental data aggregation component that can be used in many network (and other) applications. It is a crucial structure to address performance and scalability issues of diverse network 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 membership library to optimize flow lookup for Open vSwitch (OvS) shows a speed up of about 3X. Signed-off-by: Yipeng Wang<yipeng1.w...@intel.com> Signed-off-by: Sameh Gobriel<sameh.gobr...@intel.com> Signed-off-by: Charlie Tai<charlie....@intel.com> Signed-off-by: Ren Wang<ren.w...@intel.com> Yipeng Wang (1): Add Membership Library MAINTAINERS | 7 + config/defconfig_x86_64-native-linuxapp-gcc | 3 + doc/guides/prog_guide/img/memship_i1.svg | 1269 ++++++++++++++++++++++ doc/guides/prog_guide/img/memship_i2.svg | 36 + doc/guides/prog_guide/img/memship_i3.svg | 148 +++ doc/guides/prog_guide/img/memship_i4.svg | 428 ++++++++ doc/guides/prog_guide/img/memship_i5.svg | 123 +++ doc/guides/prog_guide/img/memship_i6.svg | 233 ++++ doc/guides/prog_guide/img/memship_i7.svg | 277 +++++ doc/guides/prog_guide/index.rst | 14 + doc/guides/prog_guide/membership_lib.rst | 421 +++++++ lib/Makefile | 3 +- lib/librte_eal/common/eal_common_log.c | 1 + lib/librte_eal/common/include/rte_log.h | 1 + lib/librte_membership/Makefile | 48 + lib/librte_membership/rte_membership.c | 378 +++++++ lib/librte_membership/rte_membership.h | 321 ++++++ lib/librte_membership/rte_membership_bf.c | 254 +++++ lib/librte_membership/rte_membership_bf.h | 99 ++ lib/librte_membership/rte_membership_cache.c | 345 ++++++ lib/librte_membership/rte_membership_cache.h | 95 ++ lib/librte_membership/rte_membership_ht.c | 471 ++++++++ lib/librte_membership/rte_membership_ht.h | 98 ++ lib/librte_membership/rte_membership_vbf.c | 391 +++++++ lib/librte_membership/rte_membership_vbf.h | 85 ++ lib/librte_membership/rte_membership_version.map | 15 + mk/rte.app.mk | 1 + test/test/Makefile | 2 + test/test/test_membership.c | 459 ++++++++ 29 files changed, 6025 insertions(+), 1 deletion(-) create mode 100644 doc/guides/prog_guide/img/memship_i1.svg create mode 100644 doc/guides/prog_guide/img/memship_i2.svg create mode 100644 doc/guides/prog_guide/img/memship_i3.svg create mode 100644 doc/guides/prog_guide/img/memship_i4.svg create mode 100644 doc/guides/prog_guide/img/memship_i5.svg create mode 100644 doc/guides/prog_guide/img/memship_i6.svg create mode 100644 doc/guides/prog_guide/img/memship_i7.svg create mode 100644 doc/guides/prog_guide/membership_lib.rst create mode 100644 lib/librte_membership/Makefile create mode 100644 lib/librte_membership/rte_membership.c create mode 100644 lib/librte_membership/rte_membership.h create mode 100644 lib/librte_membership/rte_membership_bf.c create mode 100644 lib/librte_membership/rte_membership_bf.h create mode 100644 lib/librte_membership/rte_membership_cache.c create mode 100644 lib/librte_membership/rte_membership_cache.h create mode 100644 lib/librte_membership/rte_membership_ht.c create mode 100644 lib/librte_membership/rte_membership_ht.h create mode 100644 lib/librte_membership/rte_membership_vbf.c create mode 100644 lib/librte_membership/rte_membership_vbf.h create mode 100644 lib/librte_membership/rte_membership_version.map create mode 100644 test/test/test_membership.c -- 1.9.1
