Qpid
  1. Qpid
  2. QPID-2897

C++ broker: improve scale and speed of route matching algorithm for topic exchanges.

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: 0.6
    • Fix Version/s: 0.7
    • Component/s: C++ Broker
    • Labels:
      None

      Description

      The current route match algorithm used by a topic exchange is merely a linear search across all bindings, resulting in O performance (n=# of bindings).

      1. perf.txt
        2 kB
        Ken Giusti
      2. tree_map.patch
        41 kB
        Ken Giusti
      3. TrieMapLookup.cpp
        2 kB
        Ken Giusti
      4. TrieMapLookup.h
        6 kB
        Ken Giusti

        Activity

        Hide
        Ken Giusti added a comment -

        Here's a very rough prototype for a tree-of-maps approach to topic routes. The basic concept is to break a binding route up into tokens, and build an ordered tree of nodes from each token. As binding routes are added, a node may end up having more than one "child" token. In these cases, I store a reference to the child node in a map index by the child's token.

        There are special nodes + children for wildcard tokens (* and #).

        Using a simple benchmark against a large set of synthetic routes, the proposed lookup scales well:

        Routing with 1 routes and sending 10000 messages:
        QpidLinearLookup - Prep: 0 seconds, Lookups:0.03 seconds msgs=30000 matches=0
        TrieMapLookup - Prep: 0 seconds, Lookups:0.06 seconds msgs=30000 matches=0

        Routing with 10 routes and sending 10000 messages:
        QpidLinearLookup - Prep: 0 seconds, Lookups:0.14 seconds msgs=30000 matches=27000
        TrieMapLookup - Prep: 0 seconds, Lookups:0.08 seconds msgs=30000 matches=27000

        Routing with 100 routes and sending 10000 messages:
        QpidLinearLookup - Prep: 0 seconds, Lookups:1.07 seconds msgs=30000 matches=29700
        TrieMapLookup - Prep: 0 seconds, Lookups:0.09 seconds msgs=30000 matches=29700

        Routing with 1000 routes and sending 10000 messages:
        QpidLinearLookup - Prep: 0.01 seconds, Lookups:10.57 seconds msgs=30000 matches=29970
        TrieMapLookup - Prep: 0.01 seconds, Lookups:0.1 seconds msgs=30000 matches=29970

        Routing with 10000 routes and sending 10000 messages:
        QpidLinearLookup - Prep: 0.02 seconds, Lookups:106.42 seconds msgs=30000 matches=29997
        TrieMapLookup - Prep: 0.11 seconds, Lookups:0.11 seconds msgs=30000 matches=29997

        Show
        Ken Giusti added a comment - Here's a very rough prototype for a tree-of-maps approach to topic routes. The basic concept is to break a binding route up into tokens, and build an ordered tree of nodes from each token. As binding routes are added, a node may end up having more than one "child" token. In these cases, I store a reference to the child node in a map index by the child's token. There are special nodes + children for wildcard tokens (* and #). Using a simple benchmark against a large set of synthetic routes, the proposed lookup scales well: Routing with 1 routes and sending 10000 messages: QpidLinearLookup - Prep: 0 seconds, Lookups:0.03 seconds msgs=30000 matches=0 TrieMapLookup - Prep: 0 seconds, Lookups:0.06 seconds msgs=30000 matches=0 Routing with 10 routes and sending 10000 messages: QpidLinearLookup - Prep: 0 seconds, Lookups:0.14 seconds msgs=30000 matches=27000 TrieMapLookup - Prep: 0 seconds, Lookups:0.08 seconds msgs=30000 matches=27000 Routing with 100 routes and sending 10000 messages: QpidLinearLookup - Prep: 0 seconds, Lookups:1.07 seconds msgs=30000 matches=29700 TrieMapLookup - Prep: 0 seconds, Lookups:0.09 seconds msgs=30000 matches=29700 Routing with 1000 routes and sending 10000 messages: QpidLinearLookup - Prep: 0.01 seconds, Lookups:10.57 seconds msgs=30000 matches=29970 TrieMapLookup - Prep: 0.01 seconds, Lookups:0.1 seconds msgs=30000 matches=29970 Routing with 10000 routes and sending 10000 messages: QpidLinearLookup - Prep: 0.02 seconds, Lookups:106.42 seconds msgs=30000 matches=29997 TrieMapLookup - Prep: 0.11 seconds, Lookups:0.11 seconds msgs=30000 matches=29997
        Hide
        Ken Giusti added a comment -

        Patch that implements the tree-of-maps binding lookup implementation. Patch includes additional tests to verify pattern matching behaviour.

        Passes "make check", but I have yet to run any performance tests. Will post results when I do.

        Show
        Ken Giusti added a comment - Patch that implements the tree-of-maps binding lookup implementation. Patch includes additional tests to verify pattern matching behaviour. Passes "make check", but I have yet to run any performance tests. Will post results when I do.
        Hide
        Ken Giusti added a comment -

        Ran perftest against trunk & patched topics for various numbers of bindings.

        Show
        Ken Giusti added a comment - Ran perftest against trunk & patched topics for various numbers of bindings.

          People

          • Assignee:
            Ken Giusti
            Reporter:
            Ken Giusti
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development