[nanomsg] Re: Generalized subscription upstreaming
- From: Alex Elsayed <eternaleye@xxxxxxxxx>
- To: nanomsg@xxxxxxxxxxxxx
- Date: Sat, 20 Sep 2014 08:02:03 -0700
Martin Sustrik wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hi Alex,
>
> Couple of comments:
>
> 1. The subscriber should start with no subscriptions rather that
> "subscribe to all" subscription. In the latter case it could be
> overloaded by incoming messages before it manages to turn to "all"
> subsription off.
I was under the impression that currently, entering a topology with no
explicit subscriptions at all subscribed to everything; thus I didn't want
to break ABI. If that's not the case, then the initial subscription to the
empty string can go away, yes - It's not especially core to the protocol.
However, it has a benefit in the case of failure to upstream (see below).
> 2. The fundamental problem with subscription upstreaming is the case
> when there are multiple producers attached to a single consumer. In
> such case you can handle slow/stuck producer in two ways: a.) you can
> drop subscriptions to that producer b.) you can block adding new
> subscripions. Both options have undesirable consequences. The only
> good solution I've heard so far was limiting the amount of
> subscriptions (e.g. at most 1 subscription) so that the upsreaming
> never gets stuck. That, however, prevents upstreaming subscriptions
> beyone 1 hop (the device in the middle would have to aggregate the
> subscriptions from the downstream and thus exceed the limit).
Well, since this is defined as a synchronization protocol (and the user
needs to do receive-side filtering anyway), they can continue adding new
subscriptions at the API level even if the upstreaming hangs.
Similarly, since a separate trie is kept for each upstream, a slow upstream
cannot block other upstreams.
If you want to avoid backlogging, you could limit the SUBSCRIBE/REJECT/RESET
messages in-flight to a fixed value, add another bit to the bitmap for
"UNTRIED", and add a scan-for-UNTRIED step to the CONFIRM-received step.
In that case, failure-to-upstream-subscriptions simply results in the same
behavior as no-sender-side-filtering - and is one of the reasons that the
initial "" subscription is valuable, since you still have the "firehose"
minus any negative subscriptions that _were_ successfully upstreamed (an
efficiency win). It fails safe.
It would also force the multi-hop upstreamer to upstream a "" subscription,
so that again makes it work - if the aggregating node hits the limit during
the sync protocol, it can fail-safe to "", and the protocol "peaks" in the
middle and then _declines_ in terms of memory usage as it prunes the non-
CANONICAL entries. Since the final "commit" of removing "" occurs after the
pruning, any memory allocation failure will occur when a "" subscription is
present.
However, if a user adds a POSITIVE CANONICAL child for a NEGATIVE SYNCED
not-CANONICAL node, and cannot sync it, they'd have to drop and reconnect
regardless.
> Thoughts?
> Martin
>
> On 20/09/14 01:47, Alex Elsayed wrote:
>> This is an attempt to define a general system for upstreaming
>> subscriptions on bidirectional transports. All comments welcome and
>> deeply appreciated.
>>
>> Note that all messages from subscribers to producers expect a
>> confirmation, and thus when I say that S sends something, it is
>> assumed that S will resend the message if a timeout elapses. To
>> facilitate this, the effects of repeat messages on producers are
>> idempotent.
>>
>> The subscriber maintains a trie of subscriptions, where each leaf
>> carries a bitfield of the following: POSITIVE (when absent, is a
>> "negative" or "ignore" subscription) SYNCHRONIZED (Has the upstream
>> acknowledged the subscription?) PENDING (...have we asked them?)
>> CANONICAL (Is this a subscription by the user, or an internal
>> synchronization artifact?)
>>
>> the subscriber S' trie begins with a single subscription to "",
>> which is POSITIVE, SYNCHRONIZED, CANONICAL, and not PENDING.
>>
>> When the user explicitly subscribes to a topic, the CANONICAL flag
>> is cleared from the empty-string subscription. The inserted entry
>> for the explicit subscription is POSITIVE and CANONICAL, but
>> neither SYNCHRONIZED nor PENDING.
>>
>> If the empty-string subscription is not present, a SUBSCRIBE
>> message is immediately sent upstream, and the PENDING flag _is_
>> set.
>>
>> On receiving a normal message, S will look up the topic in the
>> trie.
>>
>> If no prefix of the topic is found in the trie, a leaf is created
>> for shortest prefix for which there was no entry, with PENDING true
>> and all other fields false. The subscriber then sends a REJECT
>> message upstream.
>>
>> Otherwise, over a list of all leaves that are prefixes to the topic
>> (root first, end last), the following occurs:
>>
>> for leaf in list: if leaf is SYNCHRONIZED or PENDING: continue
>> else if leaf is CANONICAL and POSITIVE: mark leaf PENDING send
>> SUBSCRIBE message upstream break
>>
>> With this, a natural throttle is placed on the rate of
>> subscriptions.
>>
>> P also keeps a trie, but a much simpler one - the value is a single
>> bit, indicating POSITIVE vs NEGATIVE.
>>
>> On P receiving a REJECT message, a NEGATIVE entry is inserted, and
>> on receiving a SUBSCRIBE message, a POSITIVE entry is inserted.
>> Then, P sends S a CONFIRM (REJECT|SUBSCRIBE) message as
>> appropriate.
>>
>> On receiving a CONFIRM (REJECT or SUBSCRIBE) message, S: 1.) Marks
>> the appropriate node N as SYNCHRONIZED and clears PENDING 2.) Walks
>> from the node towards the root until it encounters a node X that is
>> not CANONICAL 3.) If all entries in the tree under X either: a.)
>> Are SUBSCRIBED or b.) Have a SUBSCRIBED node on the path between
>> them and X, then S sets the PENDING flag on X, and sends a RESET
>> message upstream for X.
>>
>> On P receiving a RESET message, it deletes the relevant node from
>> its trie, and sends a CONFIRM RESET message to S.
>>
>> On S receiving a CONFIRM RESET message, it removes the node from
>> its trie, and then executes steps 2 and 3 from above.
>>
>>
>> With this, the subscription state of the producer converges on that
>> of the subscriber, while restricting the subscription messages to 1
>> per producer message. Negative subscriptions suppress broad
>> categories of useless messages, and then are removed once all
>> canonical subscriptions have been upstreamed. In the case of an
>> unresponsive peer, disconnection is viable, because re-connection
>> will not cause a flood of subscription messages.
>>
>> A subscriber wishing to subscribe to multiple producers would keep
>> one trie for each producer, and insert CANONICAL entries into all
>> tries.
>>
>> Adding a producer after tries already exist also works, as one can
>> simply walk any of the existing tries and insert the CANONICAL
>> nodes into the new trie.
>>
>> Messages are only passed to the user if they match a POSITIVE,
>> CANONICAL entry in the trie.
>>
>>
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
> Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
>
> iQEcBAEBAgAGBQJUHTbbAAoJENTpVjxCNN9YOrkH/iOiez9Nz5uJCUjemcco0zbI
> 3CXQucHxlZ6lHfuuX78YZ+LJJTrwJujO+Nebo2Sm+GeJOfEgbC03u8K6PpA0WRFI
> XFPUZM9SYsc7y6bT9+Tbm16aAteVWCW8SSJZqrqqfaATohJrzLvWl/LNCwmO0/EI
> 6cw43hjKmMOWGngNDOfZFeqfMrbxDJBLYIZa21ey82sNbo8pVHh6rMIcjuhIsxie
> oAMJCy0EypfaClPyQQgPN3QrGZsZe/JdBTMG34COw+NYYBj3LxkYDohRyCCSE6os
> eWG0Znigvs/0fGttsmcwsKli2EYW4wH9/1BitWIym/0VuvMcRRQeMxGrGNf9Zgs=
> =iBCI
> -----END PGP SIGNATURE-----
Other related posts:
