Single level wildcard and 'future' topics

[Michael Combs]

 I have a question regarding the use of wildcards. I am assuming that subscriptions using wildcards also applies to 'future' topics. For instance: A broker contains topics A/B and A/C. A client subscribes to A/# and recieves messages published to A/B and A/C. A new topic is then added A/D. The subscriber would then receive messages published to A/D also. 

The reason I ask is that it creates difficulty in storing subscriptions within a topic 'tree' (the seemingly obvious data structure for topics).  Non wildcard subscriptions are easily stored at each topic node. Multi Level wildcards '#' are also easily stored at the node (flagged as multilevel). This works because the multilevel wildcard may only be used as the last character in a topic, hence the last node in a query. All children are always included in the subscription. The single level wildcard '+' may be used in the middle of a topic string and cannot be stored so deterministically at the topic node. For instance: Given  broker topics  A/1/C/D and A/2/C/D a client might subscribe to A/+/C/D. The matching subscriptions could include both A/1/C/D and A/2/C/D and could be stored at the 2 separate D nodes in the tree. However, adding topic A/3/C/D would require reevaluation of subscriptions (at least single level widlcards) to identify that the client subscribing to A/+/C/D should be added as a subscription to the D node in the A/3/C/D subtree. Is the solution to reevaluate non detemrinistic subscriptions each time a new topic is added or are future topics included in a subscription?

[Nicholas O'Leary]

Hi Michael,

A subscription is a request to receive all messages published to topics that match the filter at the point of publication. So a subscriber would receive any messages sent to 'future' topics as you describe it. But really, mqtt doesn't distinguish between past, present and future topics. A broker may allow you to administratively configure options on a topic before it is used, such as security, but this is above and beyond what the spec defines.

There are various ways to represent the subscriptions in the broker. The most crude way is a ordered list that each message is compared against as they arrive to find the subscriptions that match. This isnt very efficient.

An alternative is to store the subscriptions in a tree structure - note I mean the subscriptions, not the topics. So the tree will have nodes that are the wildcards. When a message arrives, a simple tree traversal can find all the leaf nodes, including those that hang off wildcards that identify the clients that hold those subscriptions.

The key distinction here is that it is a tree of subscriptions.

Toopics can be used in a highly ephemeral way that means you don't want to be creating a tree of them all. For example, a logger may publish to app/log/[timestamp]. So effectively, each time it publishes it uses a unique topic. Trying to store those topics in a tree would be highly inefficient. It would be much better to store the subscription to app/log/+ in a subscription tree and match against that.

Hope that makes sense.

Nick

On Tuesday, November 12, 2013, Michael Combs wrote:

 I have a question regarding the use of wildcards. I am assuming that subscriptions using wildcards also applies to 'future' topics. For instance: A broker contains topics A/B and A/C. A client subscribes to A/# and recieves messages published to A/B and A/C. A new topic is then added A/D. The subscriber would then receive messages published to A/D also. 

The reason I ask is that it creates difficulty in storing subscriptions within a topic 'tree' (the seemingly obvious data structure for topics).  Non wildcard subscriptions are easily stored at each topic node. Multi Level wildcards '#' are also easily stored at the node (flagged as multilevel). This works because the multilevel wildcard may only be used as the last character in a topic, hence the last node in a query. All children are always included in the subscription. The single level wildcard '+' may be used in the middle of a topic string and cannot be stored so deterministically at the topic node. For instance: Given  broker topics  A/1/C/D and A/2/C/D a client might subscribe to A/+/C/D. The matching subscriptions could include both A/1/C/D and A/2/C/D and could be stored at the 2 separate D nodes in the tree. However, adding topic A/3/C/D would require reevaluation of subscriptions (at least single level widlcards) to identify that the client subscribing to A/+/C/D should be added as a subscription to the D node in the A/3/C/D subtree. Is the solution to reevaluate non detemrinistic subscriptions each time a new topic is added or are future topics included in a subscription?

--
--
To learn more about MQTT please visit http://mqtt.org
 
To post to this group, send email to mq...@googlegroups.com
To unsubscribe from this group, send email to
mqtt+uns...@googlegroups.com
 
For more options, visit this group at
http://groups.google.com/group/mqtt
 
---
You received this message because you are subscribed to the Google Groups "MQ Telemetry Transport" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mqtt+uns...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Michael Combs]

Thanks for clearing that up and for the advice. I hadn't considered 'not' storing the topics nor publishing to distinct topics each time (i.e. the timestamp example you provided).  I can see the ineffciency of a sparse or unbalanced topic tree in such as case. 

Thanks again.

On Tuesday, November 12, 2013 6:18:02 PM UTC-6, knolleary wrote:

Hi Michael,

A subscription is a request to receive all messages published to topics that match the filter at the point of publication. So a subscriber would receive any messages sent to 'future' topics as you describe it. But really, mqtt doesn't distinguish between past, present and future topics. A broker may allow you to administratively configure options on a topic before it is used, such as security, but this is above and beyond what the spec defines.

There are various ways to represent the subscriptions in the broker. The most crude way is a ordered list that each message is compared against as they arrive to find the subscriptions that match. This isnt very efficient.

An alternative is to store the subscriptions in a tree structure - note I mean the subscriptions, not the topics. So the tree will have nodes that are the wildcards. When a message arrives, a simple tree traversal can find all the leaf nodes, including those that hang off wildcards that identify the clients that hold those subscriptions.

The key distinction here is that it is a tree of subscriptions.

Toopics can be used in a highly ephemeral way that means you don't want to be creating a tree of them all. For example, a logger may publish to app/log/[timestamp]. So effectively, each time it publishes it uses a unique topic. Trying to store those topics in a tree would be highly inefficient. It would be much better to store the subscription to app/log/+ in a subscription tree and match against that.

Hope that makes sense.

Nick

On Tuesday, November 12, 2013, Michael Combs wrote:

 I have a question regarding the use of wildcards. I am assuming that subscriptions using wildcards also applies to 'future' topics. For instance: A broker contains topics A/B and A/C. A client subscribes to A/# and recieves messages published to A/B and A/C. A new topic is then added A/D. The subscriber would then receive messages published to A/D also. 

The reason I ask is that it creates difficulty in storing subscriptions within a topic 'tree' (the seemingly obvious data structure for topics).  Non wildcard subscriptions are easily stored at each topic node. Multi Level wildcards '#' are also easily stored at the node (flagged as multilevel). This works because the multilevel wildcard may only be used as the last character in a topic, hence the last node in a query. All children are always included in the subscription. The single level wildcard '+' may be used in the middle of a topic string and cannot be stored so deterministically at the topic node. For instance: Given  broker topics  A/1/C/D and A/2/C/D a client might subscribe to A/+/C/D. The matching subscriptions could include both A/1/C/D and A/2/C/D and could be stored at the 2 separate D nodes in the tree. However, adding topic A/3/C/D would require reevaluation of subscriptions (at least single level widlcards) to identify that the client subscribing to A/+/C/D should be added as a subscription to the D node in the A/3/C/D subtree. Is the solution to reevaluate non detemrinistic subscriptions each time a new topic is added or are future topics included in a subscription?

--
--
To learn more about MQTT please visit http://mqtt.org
 
To post to this group, send email to mq...@googlegroups.com
To unsubscribe from this group, send email to

mqtt+unsubscribe@googlegroups.com

 
For more options, visit this group at
http://groups.google.com/group/mqtt
 
---
You received this message because you are subscribed to the Google Groups "MQ Telemetry Transport" group.

To unsubscribe from this group and stop receiving emails from it, send an email to mqtt+unsubscribe@googlegroups.com.