diff options
Diffstat (limited to 'doc/guides/prog_guide/member_lib.rst')
-rw-r--r-- | doc/guides/prog_guide/member_lib.rst | 420 |
1 files changed, 420 insertions, 0 deletions
diff --git a/doc/guides/prog_guide/member_lib.rst b/doc/guides/prog_guide/member_lib.rst new file mode 100644 index 00000000..caca8dc2 --- /dev/null +++ b/doc/guides/prog_guide/member_lib.rst @@ -0,0 +1,420 @@ +.. BSD LICENSE + Copyright(c) 2017 Intel Corporation. All rights reserved. + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in + the documentation and/or other materials provided with the + distribution. + * Neither the name of Intel Corporation nor the names of its + contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + + +.. _member_library: + +Membership Library +================== + +Introduction +------------ + +The DPDK Membership Library 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 structure (for example +Bloom Filter [Member-bloom]) 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" on whether a member belongs to a set, +and as discussed in detail later, there are two advantages of using such a +set-summary rather than operating on a "full-blown" complete list of elements: +first, 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. + +We use the term "Set-Summary" in this guide to refer to the space-efficient, +probabilistic membership data structure that is provided by the library. A +membership test for an element will return the set this element belongs to or +that the element is "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, +data-centric networks, flow table summaries, network statistics and +traffic monitoring. A set-summary is useful for applications who need to +include a list of elements while a complete list requires too much space +and/or too much processing cost. In these situations, the set-summary works as +a lossy hash-based representation of a set of members. It can dramatically +reduce space requirement and significantly improve the performance of set +membership queries at the cost of introducing a very small membership test error +probability. + +.. _figure_membership1: +.. figure:: img/member_i1.* + + Example Usages of Membership Library + +There are various usages for a Membership Library in a very +large set of applications and workloads. Interested readers can refer to +[Member-survey] for a survey of possible networking usages. The above figure +provide a small set of examples of using the Membership Library: + +* Sub-figure (a) + depicts a distributed web cache architecture where a collection of proxies + attempt to share their web caches (cached from a set of back-end web servers) to + provide faster responses to clients, and the proxies use the Membership + Library to share summaries of what web pages/objects they are caching. With the + Membership Library, a proxy receiving an http request will inquire the + set-summary to find its location and quickly determine whether to retrieve the + requested web page from a nearby proxy or from a back-end web server. + +* Sub-figure (b) depicts another example for using the Membership Library to + prevent routing loops which is typically done using slow TTL countdown and + dropping packets when TTL expires. As shown in Sub-figure (b), an embedded + set-summary in the packet header itself can be used to summarize the set of + nodes a packet has gone through, and each node upon receiving a packet can check + whether its id is a member of the set of visited nodes, and if it is, then a + routing loop is detected. + +* Sub-Figure (c) presents another usage of the Membership + Library to load-balance flows to worker threads with in-order guarantee where a + set-summary is used to query if a packet belongs to an existing flow or a new + flow. Packets belonging to a new flow are forwarded to the current least loaded + worker thread, while those belonging to an existing flow are forwarded to the + pre-assigned thread to guarantee in-order processing. + +* Sub-figure (d) highlights + yet another usage example in the database domain where a set-summary is used to + determine joins between sets instead of creating a join by comparing each + element of a set against the other elements in a different set, a join is done + on the summaries since they can efficiently encode members of a given set. + +Membership Library is a configurable library that is optimized to cover set +membership functionality for both a single set and multi-set scenarios. Two set-summary +schemes are presented including (a) vector of Bloom Filters and (b) Hash-Table based +set-summary schemes with and without false negative probability. +This guide first briefly describes these different types of set-summaries, usage examples for each, +and then it highlights the Membership Library API. + +Vector of Bloom Filters +----------------------- + +Bloom Filter (BF) [Member-bloom] is a well-known space-efficient +probabilistic data structure that answers set membership queries (test whether +an element is a member of a set) with some probability of false positives and +zero false negatives; a query for an element returns either it is "possibly in +a set" (with very high probability) or "definitely not in a set". + +The BF is a method for representing a set of ``n`` elements (for example flow keys +in network applications domain) to support membership queries. The idea of BF is +to allocate a bit-vector ``v`` with ``m`` bits, which are initially all set to 0. Then +it chooses ``k`` independent hash functions ``h1``, ``h2``, ... ``hk`` with hash values range from +``0`` to ``m-1`` to perform hashing calculations on each element to be inserted. Every time when an +element ``X`` being inserted into the set, the bits at positions ``h1(X)``, ``h2(X)``, ... +``hk(X)`` in ``v`` are set to 1 (any particular bit might be set to 1 multiple times +for multiple different inserted elements). Given a query for any element ``Y``, the +bits at positions ``h1(Y)``, ``h2(Y)``, ... ``hk(Y)`` are checked. If any of them is 0, +then Y is definitely not in the set. Otherwise there is a high probability that +Y is a member of the set with certain false positive probability. As shown in +the next equation, the false positive probability can be made arbitrarily small +by changing the number of hash functions (``k``) and the vector length (``m``). + +.. _figure_membership2: +.. figure:: img/member_i2.* + + Bloom Filter False Positive Probability + +Without BF, an accurate membership testing could involve a costly hash table +lookup and full element comparison. The advantage of using a BF is to simplify +the membership test into a series of hash calculations and memory accesses for a +small bit-vector, which can be easily optimized. Hence the lookup throughput +(set membership test) can be significantly faster than a normal hash table +lookup with element comparison. + +.. _figure_membership3: +.. figure:: img/member_i3.* + + Detecting Routing Loops Using BF + +BF is used for applications that need only one set, and the +membership of elements is checked against the BF. The example discussed +in the above figure is one example of potential applications that uses only one +set to capture the node IDs that have been visited so far by the packet. Each +node will then check this embedded BF in the packet header for its own id, and +if the BF indicates that the current node is definitely not in the set then a +loop-free route is guaranteed. + + +.. _figure_membership4: +.. figure:: img/member_i4.* + + Vector Bloom Filter (vBF) Overview + +To support membership test for both multiple sets and a single set, +the library implements a Vector Bloom Filter (vBF) scheme. +vBF basically composes multiple bloom filters into a vector of bloom filers. +The membership test is conducted on all of the +bloom filters concurrently to determine which set(s) it belongs to or none of +them. The basic idea of vBF is shown in the above figure where an element is +used to address multiple bloom filters concurrently and the bloom filter +index(es) with a hit is returned. + +.. _figure_membership5: +.. figure:: img/member_i5.* + + vBF for Flow Scheduling to Worker Thread + +As previously mentioned, there are many usages of such structures. vBF is used +for applications that need to check membership against multiple sets +simultaneously. The example shown in the above figure uses a set to capture +all flows being assigned for processing at a given worker thread. Upon receiving +a packet the vBF is used to quickly figure out if this packet belongs to a new flow +so as to be forwarded to the current least loaded worker thread, or otherwise it +should be queued for an existing thread to guarantee in-order processing (i.e. +the property of vBF to indicate right away that a given flow is a new one or +not is critical to minimize response time latency). + +It should be noted that vBF can be implemented using a set of single bloom +filters with sequential lookup of each BF. However, being able to concurrently +search all set-summaries is a big throughput advantage. In the library, certain +parallelism is realized by the implementation of checking all bloom filters +together. + + +Hash-Table based Set-Summaries +------------------------------ + +Hash-table based set-summary (HTSS) is another scheme in the membership library. +Cuckoo filter [Member-cfilter] is an example of HTSS. +HTSS supports multi-set membership testing like +vBF does. However, while vBF is better for a small number of targets, HTSS is more suitable +and can easily outperform vBF when the number of sets is +large, since HTSS uses a single hash table for membership testing while vBF +requires testing a series of Bloom Filters each corresponding to one set. +As a result, generally speaking vBF is more adequate for the case of a small limited number of sets +while HTSS should be used with a larger number of sets. + +.. _figure_membership6: +.. figure:: img/member_i6.* + + Using HTSS for Attack Signature Matching + +As shown in the above figure, attack signature matching where each set +represents a certain signature length (for correctness of this example, an +attack signature should not be a subset of another one) in the payload is a good +example for using HTSS with 0% false negative (i.e., when an element returns not +found, it has a 100% certainty that it is not a member of any set). The packet +inspection application benefits from knowing right away that the current payload +does not match any attack signatures in the database to establish its +legitimacy, otherwise a deep inspection of the packet is needed. + +HTSS employs a similar but simpler data structure to a traditional hash table, +and the major difference is that HTSS stores only the signatures but not the +full keys/elements which can significantly reduce the footprint of the table. +Along with the signature, HTSS also stores a value to indicate the target set. +When looking up an element, the element is hashed and the HTSS is addressed +to retrieve the signature stored. If the signature matches then the value is +retrieved corresponding to the index of the target set which the element belongs +to. Because signatures can collide, HTSS can still has false positive +probability. Furthermore, if elements are allowed to be +overwritten or evicted when the hash table becomes full, it will also have a +false negative probability. We discuss this case in the next section. + +Set-Summaries with False Negative Probability +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +As previously mentioned, traditional set-summaries (e.g. Bloom Filters) do not +have a false negative probability, i.e., it is 100% certain when an element +returns "not to be present" for a given set. However, the Membership Library +also supports a set-summary probabilistic data structure based on HTSS which +allows for false negative probability. + +In HTSS, when the hash table becomes full, keys/elements will fail to be added +into the table and the hash table has to be resized to accommodate for these new +elements, which can be expensive. However, if we allow new elements to overwrite +or evict existing elements (as a cache typically does), then the resulting +set-summary will begin to have false negative probability. This is because the +element that was evicted from the set-summary may still be present in the target +set. For subsequent inquiries the set-summary will falsely report the element +not being in the set, hence having a false negative probability. + +The major usage of HTSS with false negative is to use it as a cache for +distributing elements to different target sets. By allowing HTSS to evict old +elements, the set-summary can keep track of the most recent elements +(i.e. active) as a cache typically does. Old inactive elements (infrequently +used elements) will automatically and eventually get evicted from the +set-summary. It is worth noting that the set-summary still has false positive +probability, which means the application either can tolerate certain false positive +or it has fall-back path when false positive happens. + +.. _figure_membership7: +.. figure:: img/member_i7.* + + Using HTSS with False Negatives for Wild Card Classification + +HTSS with false negative (i.e. a cache) also has its wide set of applications. +For example wild card flow classification (e.g. ACL rules) highlighted in the +above figure is an example of such application. In that case each target set +represents a sub-table with rules defined by a certain flow mask. The flow masks +are non-overlapping, and for flows matching more than one rule only the highest +priority one is inserted in the corresponding sub-table (interested readers can +refer to the Open vSwitch (OvS) design of Mega Flow Cache (MFC) [Member-OvS] +for further details). Typically the rules will have a large number of distinct +unique masks and hence, a large number of target sets each corresponding to one +mask. Because the active set of flows varies widely based on the network +traffic, HTSS with false negative will act as a cache for <flowid, target ACL +sub-table> pair for the current active set of flows. When a miss occurs (as +shown in red in the above figure) the sub-tables will be searched sequentially +one by one for a possible match, and when found the flow key and target +sub-table will be inserted into the set-summary (i.e. cache insertion) so +subsequent packets from the same flow don’t incur the overhead of the +sequential search of sub-tables. + +Library API Overview +-------------------- + +The design goal of the Membership Library API is to be as generic as possible to +support all the different types of set-summaries we discussed in previous +sections and beyond. Fundamentally, the APIs need to include creation, +insertion, deletion, and lookup. + + +Set-summary Create +~~~~~~~~~~~~~~~~~~ + +The ``rte_member_create()`` function is used to create a set-summary structure, the input parameter +is a struct to pass in parameters that needed to initialize the set-summary, while the function returns the +pointer to the created set-summary or ``NULL`` if the creation failed. + +The general input arguments used when creating the set-summary should include ``name`` +which is the name of the created set-summary, *type* which is one of the types +supported by the library (e.g. ``RTE_MEMBER_TYPE_HT`` for HTSS or ``RTE_MEMBER_TYPE_VBF`` for vBF), and ``key_len`` +which is the length of the element/key. There are other parameters +are only used for certain type of set-summary, or which have a slightly different meaning for different types of set-summary. +For example, ``num_keys`` parameter means the maximum number of entries for Hash table based set-summary. +However, for bloom filter, this value means the expected number of keys that could be +inserted into the bloom filter(s). The value is used to calculate the size of each +bloom filter. + +We also pass two seeds: ``prim_hash_seed`` and +``sec_hash_seed`` for the primary and secondary hash functions to calculate two independent hash values. +``socket_id`` parameter is the NUMA socket ID for the memory used to create the +set-summary. For HTSS, another parameter ``is_cache`` is used to indicate +if this set-summary is a cache (i.e. with false negative probability) or not. +For vBF, extra parameters are needed. For example, ``num_set`` is the number of +sets needed to initialize the vector bloom filters. This number is equal to the +number of bloom filters will be created. +``false_pos_rate`` is the false positive rate. num_keys and false_pos_rate will be used to determine +the number of hash functions and the bloom filter size. + + +Set-summary Element Insertion +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +The ``rte_member_add()`` function is used to insert an element/key into a set-summary structure. If it fails an +error is returned. For success the returned value is dependent on the +set-summary mode to provide extra information for the users. For vBF +mode, a return value of 0 means a successful insert. For HTSS mode without false negative, the insert +could fail with ``-ENOSPC`` if the table is full. With false negative (i.e. cache mode), +for insert that does not cause any eviction (i.e. no overwriting happens to an +existing entry) the return value is 0. For insertion that causes eviction, the return +value is 1 to indicate such situation, but it is not an error. + +The input arguments for the function should include the ``key`` which is a pointer to the element/key that needs to +be added to the set-summary, and ``set_id`` which is the set id associated +with the key that needs to be added. + + +Set-summary Element Lookup +~~~~~~~~~~~~~~~~~~~~~~~~~~ + +The ``rte_member_lookup()`` function looks up a single key/element in the set-summary structure. It +returns as soon as the first match is found. The return value is 1 if a +match is found and 0 otherwise. The arguments for the function include ``key`` which is a pointer to the +element/key that needs to be looked up, and ``set_id`` which is used to return the +first target set id where the key has matched, if any. + +The ``rte_member_lookup_bulk()`` function is used to look up a bulk of keys/elements in the +set-summary structure for their first match. Each key lookup returns as soon as the first match is found. The +return value is the number of keys that find a match. The arguments of the function include ``keys`` +which is a pointer to a bulk of keys that are to be looked up, +``num_keys`` is the number +of keys that will be looked up, and ``set_ids`` are the return target set +ids for the first match found for each of the input keys. ``set_ids`` is an array +needs to be sized according to the ``num_keys``. If there is no match, the set id +for that key will be set to RTE_MEMBER_NO_MATCH. + +The ``rte_member_lookup_multi()`` function looks up a single key/element in the +set-summary structure for multiple matches. It +returns ALL the matches (possibly more than one) found for this key when it +is matched against all target sets (it is worth noting that for cache mode HTSS, +the current implementation matches at most one target set). The return value is +the number of matches +that was found for this key (for cache mode HTSS the return value +should be at most 1). The arguments for the function include ``key`` which is a pointer to the +element/key that needs to be looked up, ``max_match_per_key`` which is to indicate the maximum number of matches +the user expects to find for each key, and ``set_id`` which is used to return all +target set ids where the key has matched, if any. The ``set_id`` array should be sized +according to ``max_match_per_key``. For vBF, the maximum number of matches per key is equal +to the number of sets. For HTSS, the maximum number of matches per key is equal to two time +entry count per bucket. ``max_match_per_key`` should be equal or smaller than the maximum number of +possible matches. + +The ``rte_membership_lookup_multi_bulk()`` function looks up a bulk of keys/elements in the +set-summary structure for multiple matches, each key lookup returns ALL the matches (possibly more +than one) found for this key when it is matched against all target sets (cache mode HTSS +matches at most one target set). The +return value is the number of keys that find one or more matches in the +set-summary structure. The arguments of the +function include ``keys`` which is +a pointer to a bulk of keys that are to be looked up, ``num_keys`` is the number +of keys that will be looked up, ``max_match_per_key`` is the possible +maximum number of matches for each key, ``match_count`` which is the returned number +of matches for each key, and ``set_ids`` are the returned target set +ids for all matches found for each keys. ``set_ids`` is 2-D array +containing a 1-D array for each key (the size of 1-D array per key should be set by the user according to ``max_match_per_key``). +``max_match_per_key`` should be equal or smaller than the maximum number of +possible matches, similar to ``rte_member_lookup_multi``. + + +Set-summary Element Delete +~~~~~~~~~~~~~~~~~~~~~~~~~~ + +The ``rte_membership_delete()`` function deletes an element/key from a set-summary structure, if it fails +an error is returned. The input arguments should include ``key`` which is a pointer to the +element/key that needs to be deleted from the set-summary, and ``set_id`` +which is the set id associated with the key to delete. It is worth noting that current +implementation of vBF does not support deletion [1]_. An error code ``-EINVAL`` will be returned. + +.. [1] Traditional bloom filter does not support proactive deletion. Supporting proactive deletion require additional implementation and performance overhead. + +References +----------- + +[Member-bloom] B H Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors," Communications of the ACM, 1970. + +[Member-survey] A Broder and M Mitzenmacher, "Network Applications of Bloom Filters: A Survey," in Internet Mathematics, 2005. + +[Member-cfilter] B Fan, D G Andersen and M Kaminsky, "Cuckoo Filter: Practically Better Than Bloom," in Conference on emerging Networking Experiments and Technologies, 2014. + +[Member-OvS] B Pfaff, "The Design and Implementation of Open vSwitch," in NSDI, 2015. |