You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@qpid.apache.org by "Ken Giusti (JIRA)" <ji...@apache.org> on 2010/10/11 23:15:32 UTC
[jira] Updated: (QPID-2897) C++ broker: improve scale and speed of
route matching algorithm for topic exchanges.
[ https://issues.apache.org/jira/browse/QPID-2897?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Ken Giusti updated QPID-2897:
-----------------------------
Attachment: TrieMapLookup.cpp
TrieMapLookup.h
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
> C++ broker: improve scale and speed of route matching algorithm for topic exchanges.
> ------------------------------------------------------------------------------------
>
> Key: QPID-2897
> URL: https://issues.apache.org/jira/browse/QPID-2897
> Project: Qpid
> Issue Type: Improvement
> Components: C++ Broker
> Affects Versions: 0.6
> Reporter: Ken Giusti
> Assignee: Ken Giusti
> Priority: Minor
> Attachments: TrieMapLookup.cpp, TrieMapLookup.h
>
>
> The current route match algorithm used by a topic exchange is merely a linear search across all bindings, resulting in O(n) performance (n=# of bindings).
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
Apache Qpid - AMQP Messaging Implementation
Project: http://qpid.apache.org
Use/Interact: mailto:dev-subscribe@qpid.apache.org