Qpid Proton
  1. Qpid Proton
  2. PROTON-200

Credit distribution by messenger is not balanced across all links

    Details

    • Type: Bug Bug
    • Status: Resolved
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 0.3
    • Fix Version/s: 0.6
    • Component/s: proton-c, proton-j
    • Labels:
      None

      Description

      The method used to distribute credit to receiving links may lead to starvation when the number of receiving links is > the available credit.

      The distribution algorithm always starts with the same link - see messenger.c::pn_messenger_flow()

      1. upstream-credit.patch
        2 kB
        Bozo Dragojevic
      2. proton-200.patch
        10 kB
        Ken Giusti

        Issue Links

          Activity

          Hide
          Bozo Dragojevic added a comment -

          My observation was that messenger was willing to hand out all of it's credit to the first link. So when the second client connects, say few seconds later, messenger has no credit left to hand out.

          This is my attempt at mitigating the issue. https://github.com/ttlj/qpid-proton/tree/upstream-credit

          Show
          Bozo Dragojevic added a comment - My observation was that messenger was willing to hand out all of it's credit to the first link. So when the second client connects, say few seconds later, messenger has no credit left to hand out. This is my attempt at mitigating the issue. https://github.com/ttlj/qpid-proton/tree/upstream-credit
          Hide
          michael goulish added a comment -

          I think this bug is a release blocker.

          An implication, that is not immediately obvious, is that if you have one receiver with two senders – one of the senders will hang until the other receiver calls 'stop'.
          This makes it impossible to set up any topology except the simplest possible – one sender, one receiver.

          Show
          michael goulish added a comment - I think this bug is a release blocker. An implication, that is not immediately obvious, is that if you have one receiver with two senders – one of the senders will hang until the other receiver calls 'stop'. This makes it impossible to set up any topology except the simplest possible – one sender, one receiver.
          Hide
          Bozo Dragojevic added a comment -

          For us we could not do anything except 1:1 until we fixed this.

          There is one other implication that is spread over time:

          1) messenger (say a broker) hands out all it's credit (using whatever algorithm) to set of current peers,
          2) these peers choose to not send messages to the broker (consider services registered with a broker, waiting for requests)
          3) then a future peer (a client trying to send a request message via the broker to the service) will not be able to send, since the broker has handed out all of it's credit.

          My solution was to severely limit the credit given out to any link so that messenger always has some credit on hand.
          Not pretty, but it at least allows us to use proton in a hub-and-spokes configuration.
          The fix seems only a band-aid, tho.
          Even if each link gets just one credit, and assuming the code uses a constant value for the pn_messenger_recv() call, it's easy to DOS such a broker by just connecting enough clients that do nothing.

          Show
          Bozo Dragojevic added a comment - For us we could not do anything except 1:1 until we fixed this. There is one other implication that is spread over time: 1) messenger (say a broker) hands out all it's credit (using whatever algorithm) to set of current peers, 2) these peers choose to not send messages to the broker (consider services registered with a broker, waiting for requests) 3) then a future peer (a client trying to send a request message via the broker to the service) will not be able to send, since the broker has handed out all of it's credit. My solution was to severely limit the credit given out to any link so that messenger always has some credit on hand. Not pretty, but it at least allows us to use proton in a hub-and-spokes configuration. The fix seems only a band-aid, tho. Even if each link gets just one credit, and assuming the code uses a constant value for the pn_messenger_recv() call, it's easy to DOS such a broker by just connecting enough clients that do nothing.
          Hide
          Ken Giusti added a comment -

          Patch to rotate available credit across all active links fairly.

          Does not fix PROTON-200 - the case were the # of receivers > available credit still causes a stall.

          Show
          Ken Giusti added a comment - Patch to rotate available credit across all active links fairly. Does not fix PROTON-200 - the case were the # of receivers > available credit still causes a stall.
          Hide
          Rafael H. Schloming added a comment -

          I agree it's a release blocker to fix it in some form. There are actually a number of areas of work involved in fixing this long-term. As mentioned above there are two scenarios:

          1) The messenger has handed out all of its credit and gets a new link. This is in some ways easier to address as it simply requires re-balancing the credit, but in order to do that the engine needs some updates to allow revoking of credit. This is permitted by the protocol, but not currently fully supported by the engine. I'm currently working on a patch for engine support.

          2) The messenger has more links than it has credit to hand out. Once again we're missing a little bit of engine support to fix this properly. The protocol allows a peer with available messages to advertise that fact to its partner (i.e. request credit) via the available field in the flow control frame, and the partner can then use this information to allocate credit. There is already a JIRA for the engine portion of this work (PROTON-39).

          Beyond (1) and (2), another more straightforward measure we can take is to provide an unlimited mode, e.g. in the bindings make the argument to pn_messenger_recv optional, and for C define pn_messenger_recv(-1) to mean "no specific limit". This would allow the internals to dynamically determine how much credit to hand out and would make dealing with these problems relatively simple, although it wouldn't allow the application to limit its exposure to incoming messages. My guess is this is the quickest/most complete fix/workaround for 0.4.

          So to summarize I'd say there are probably n separate chunks of work here each worthy of there own JIRA:

          1) allow pn_messenger_recv(-1) to mean no specific limit
          2) engine support for revoking of credit
          3) engine support for advertising available messages (PROTON-39)
          4) messenger support for re-allocating credit (removing from one peer and giving to another)

          Show
          Rafael H. Schloming added a comment - I agree it's a release blocker to fix it in some form. There are actually a number of areas of work involved in fixing this long-term. As mentioned above there are two scenarios: 1) The messenger has handed out all of its credit and gets a new link. This is in some ways easier to address as it simply requires re-balancing the credit, but in order to do that the engine needs some updates to allow revoking of credit. This is permitted by the protocol, but not currently fully supported by the engine. I'm currently working on a patch for engine support. 2) The messenger has more links than it has credit to hand out. Once again we're missing a little bit of engine support to fix this properly. The protocol allows a peer with available messages to advertise that fact to its partner (i.e. request credit) via the available field in the flow control frame, and the partner can then use this information to allocate credit. There is already a JIRA for the engine portion of this work ( PROTON-39 ). Beyond (1) and (2), another more straightforward measure we can take is to provide an unlimited mode, e.g. in the bindings make the argument to pn_messenger_recv optional, and for C define pn_messenger_recv(-1) to mean "no specific limit". This would allow the internals to dynamically determine how much credit to hand out and would make dealing with these problems relatively simple, although it wouldn't allow the application to limit its exposure to incoming messages. My guess is this is the quickest/most complete fix/workaround for 0.4. So to summarize I'd say there are probably n separate chunks of work here each worthy of there own JIRA: 1) allow pn_messenger_recv(-1) to mean no specific limit 2) engine support for revoking of credit 3) engine support for advertising available messages ( PROTON-39 ) 4) messenger support for re-allocating credit (removing from one peer and giving to another)
          Hide
          Rafael H. Schloming added a comment -

          Also, given the above breakdown of work, I would only make the first chunk of work a 0.4 blocker.

          Show
          Rafael H. Schloming added a comment - Also, given the above breakdown of work, I would only make the first chunk of work a 0.4 blocker.
          Hide
          Ken Giusti added a comment - - edited

          Welcome to my nightmare

          As you can see from the somewhat oldish patch I've included, I've been down this road a bit. You've all hit exactly what I discovered during my testing of the "fix" - that merely balancing the credit across all receivers does not address the issue.

          The fatal failure case occurs when the number of active receiver links is > the amount of credit granted.

          One of the features of Messenger is that it provides an easy-to-use level of abstraction from the gritty details of AMQP 1.0. One of those details is link management - by design, the application using messenger doesn't have to worry about managing the links.

          However, links require credit, and the application has control over that credit by indicating how many messages it can receive - this is the parameter to the Messenger::recv() method.

          The "disconnect" is that the application currently has no mechanisms for controlling the number of receive links when it is operating as a listener (ie. subscribes to a "~" address). By allowing unlimited links, the fixed sized credit pool (given by recv() parameter) can be exhausted by the external clients connecting in.

          These are the alternatives I can think of - a couple of which require API changes - I'd certainly like to hear of any better approaches, 'cause I don't like any of mine:

          1) Have messenger limit the number of active receive links to <= the current amount of available credit.

          A problem with this approach is that the amount of credit is variable - it will drop as it is consumed. Once a link is permitted, there's no guarantee that the application will ever replenish credit to the point where all currently active links are satisfied.

          2) Change the recv() api to allow an "unlimited" flag, rather than an actual credit count.

          To implement this, each link would be guaranteed a bit of credit. The problem, as Bozo points out - opens a door to DoS.

          3) Keep the fixed pool of credit, fairly distributed amount all receive links. When the amount is credit is insufficient to cover all links, periodically revoke unused credit from those links that have it, and redistribute it to those that do not (The Robin Hood Approach).

          The difficulty here involves our heuristic for revoking the credit - I'm not sure if we can do this with 100% accuracy.

          Opinions?

          Show
          Ken Giusti added a comment - - edited Welcome to my nightmare As you can see from the somewhat oldish patch I've included, I've been down this road a bit. You've all hit exactly what I discovered during my testing of the "fix" - that merely balancing the credit across all receivers does not address the issue. The fatal failure case occurs when the number of active receiver links is > the amount of credit granted. One of the features of Messenger is that it provides an easy-to-use level of abstraction from the gritty details of AMQP 1.0. One of those details is link management - by design, the application using messenger doesn't have to worry about managing the links. However, links require credit, and the application has control over that credit by indicating how many messages it can receive - this is the parameter to the Messenger::recv() method. The "disconnect" is that the application currently has no mechanisms for controlling the number of receive links when it is operating as a listener (ie. subscribes to a "~" address). By allowing unlimited links, the fixed sized credit pool (given by recv() parameter) can be exhausted by the external clients connecting in. These are the alternatives I can think of - a couple of which require API changes - I'd certainly like to hear of any better approaches, 'cause I don't like any of mine: 1) Have messenger limit the number of active receive links to <= the current amount of available credit. A problem with this approach is that the amount of credit is variable - it will drop as it is consumed. Once a link is permitted, there's no guarantee that the application will ever replenish credit to the point where all currently active links are satisfied. 2) Change the recv() api to allow an "unlimited" flag, rather than an actual credit count. To implement this, each link would be guaranteed a bit of credit. The problem, as Bozo points out - opens a door to DoS. 3) Keep the fixed pool of credit, fairly distributed amount all receive links. When the amount is credit is insufficient to cover all links, periodically revoke unused credit from those links that have it, and redistribute it to those that do not (The Robin Hood Approach). The difficulty here involves our heuristic for revoking the credit - I'm not sure if we can do this with 100% accuracy. Opinions?
          Hide
          Bozo Dragojevic added a comment -

          DoS is way better than not being able to connect the client no 2 More so for a 0.4 release.

          A way to do that is linked in my first comment above.
          apologize for external link to the patch, I can include it inline if that's more appropriate.

          Show
          Bozo Dragojevic added a comment - DoS is way better than not being able to connect the client no 2 More so for a 0.4 release. A way to do that is linked in my first comment above. apologize for external link to the patch, I can include it inline if that's more appropriate.
          Hide
          Ken Giusti added a comment -

          Hi Bozo - yes, and you upload your patch to this jira?

          Rafi - in addition to the API change described in #1, I still think it makes sense to include the "re-balancing" patch for those apps which don't pass -1 to recv(). Should re-balancing go into 0.4, or just the "-1" fix?

          Show
          Ken Giusti added a comment - Hi Bozo - yes, and you upload your patch to this jira? Rafi - in addition to the API change described in #1, I still think it makes sense to include the "re-balancing" patch for those apps which don't pass -1 to recv(). Should re-balancing go into 0.4, or just the "-1" fix?
          Hide
          Rafael H. Schloming added a comment -

          I'd say first priority for 0.4 is the -1 fix. My sense is re-balancing properly is going to be a 0.5 thing, however if we get the -1 fix in and have extra time and it turns out to be low risk, I'm not opposed to rebalancing for 0.4.

          On the DoS topic, while I agree there are a number of potential DoSes here, I don't think the -1 patch really makes them any worse. In some ways the DoS issue is orthogonal. Currently we could be DoSed anyways by simply holding connections open without involving links at all. I think to address the DoS issue we need a more general inactivity timer. With that in place it would not only address a more general class of DoS, but in this case it would cause the links held by that client to close and their credit to be reclaimed (i.e. doing a primitive destructive sort of rebalancing).

          Show
          Rafael H. Schloming added a comment - I'd say first priority for 0.4 is the -1 fix. My sense is re-balancing properly is going to be a 0.5 thing, however if we get the -1 fix in and have extra time and it turns out to be low risk, I'm not opposed to rebalancing for 0.4. On the DoS topic, while I agree there are a number of potential DoSes here, I don't think the -1 patch really makes them any worse. In some ways the DoS issue is orthogonal. Currently we could be DoSed anyways by simply holding connections open without involving links at all. I think to address the DoS issue we need a more general inactivity timer. With that in place it would not only address a more general class of DoS, but in this case it would cause the links held by that client to close and their credit to be reclaimed (i.e. doing a primitive destructive sort of rebalancing).
          Hide
          Bozo Dragojevic added a comment -

          Here's my stab at the credit issue

          Show
          Bozo Dragojevic added a comment - Here's my stab at the credit issue
          Hide
          Ken Giusti added a comment -

          Reviewboad for proposed fix:

          https://reviews.apache.org/r/9503/

          Show
          Ken Giusti added a comment - Reviewboad for proposed fix: https://reviews.apache.org/r/9503/
          Hide
          Ken Giusti added a comment -

          In order to re-balance credit, messenger will need to drain links that have too much credit. messenger needs to know when the drain has completed.

          Show
          Ken Giusti added a comment - In order to re-balance credit, messenger will need to drain links that have too much credit. messenger needs to know when the drain has completed.
          Hide
          ASF subversion and git services added a comment -

          Commit 1527535 from rhs@apache.org in branch 'proton/trunk'
          [ https://svn.apache.org/r1527535 ]

          Modified the engine to track how much credit is drained vs used. This should simplify PROTON-200.

          Show
          ASF subversion and git services added a comment - Commit 1527535 from rhs@apache.org in branch 'proton/trunk' [ https://svn.apache.org/r1527535 ] Modified the engine to track how much credit is drained vs used. This should simplify PROTON-200 .
          Hide
          ASF subversion and git services added a comment -

          Commit 1532452 from rhs@apache.org in branch 'proton/trunk'
          [ https://svn.apache.org/r1532452 ]

          PROTON-200: modified messenger's credit distribution algorithm to cope with credit scarce scenarios

          Show
          ASF subversion and git services added a comment - Commit 1532452 from rhs@apache.org in branch 'proton/trunk' [ https://svn.apache.org/r1532452 ] PROTON-200 : modified messenger's credit distribution algorithm to cope with credit scarce scenarios
          Hide
          Keith Wall added a comment -

          Yesterday's commit (https://svn.apache.org/r1532452) broke an internal Jenkins build as the change makes use of a Python 2.5 language feature (try/except/finally in the same block - support for which was introduced by Python 2.5). We'd understood that we wanted to remain Python 2.4 compatible.

          We are using python distribution python-2.4.3-24.el5.x86_64 and the box is running Red Hat Enterprise Linux Server release 5.3 (Tikanga).

          Traceback (most recent call last):
          File "./tests/python/proton-test", line 596, in ?
          m = _import_(name, None, None, ["dummy"])
          File "/home/.jenkins/jobs/Trunk-Proton-C/workspace/proton/tests/python/proton_tests/_init_.py", line 23, in ?
          import proton_tests.messenger
          File "/home/.jenkins/jobs/Trunk-Proton-C/workspace/proton/tests/python/proton_tests/messenger.py", line 106
          finally:

          Show
          Keith Wall added a comment - Yesterday's commit ( https://svn.apache.org/r1532452 ) broke an internal Jenkins build as the change makes use of a Python 2.5 language feature (try/except/finally in the same block - support for which was introduced by Python 2.5). We'd understood that we wanted to remain Python 2.4 compatible. We are using python distribution python-2.4.3-24.el5.x86_64 and the box is running Red Hat Enterprise Linux Server release 5.3 (Tikanga). Traceback (most recent call last): File "./tests/python/proton-test", line 596, in ? m = _ import _(name, None, None, ["dummy"] ) File "/home/.jenkins/jobs/Trunk-Proton-C/workspace/proton/tests/python/proton_tests/_ init _.py", line 23, in ? import proton_tests.messenger File "/home/.jenkins/jobs/Trunk-Proton-C/workspace/proton/tests/python/proton_tests/messenger.py", line 106 finally:
          Hide
          ASF subversion and git services added a comment -

          Commit 1532733 from rhs@apache.org in branch 'proton/trunk'
          [ https://svn.apache.org/r1532733 ]

          PROTON-200: removed usage of try except finally with

          Show
          ASF subversion and git services added a comment - Commit 1532733 from rhs@apache.org in branch 'proton/trunk' [ https://svn.apache.org/r1532733 ] PROTON-200 : removed usage of try except finally with
          Hide
          Rafael H. Schloming added a comment -

          Thanks for catching this, I've removed the offending try/finally.

          Show
          Rafael H. Schloming added a comment - Thanks for catching this, I've removed the offending try/finally.
          Hide
          Ken Giusti added a comment -

          Java Messenger is missing this functionality.

          Show
          Ken Giusti added a comment - Java Messenger is missing this functionality.
          Hide
          ASF subversion and git services added a comment -

          Commit 1547534 from Ken Giusti in branch 'proton/trunk'
          [ https://svn.apache.org/r1547534 ]

          PROTON-200: Java implementation of credit scheduler

          Show
          ASF subversion and git services added a comment - Commit 1547534 from Ken Giusti in branch 'proton/trunk' [ https://svn.apache.org/r1547534 ] PROTON-200 : Java implementation of credit scheduler
          Hide
          Keith Wall added a comment - - edited

          Hi Ken,

          That commit (rev 1547534) uses JDK 7 specific features (specifically java.net.StandardSocketOptions) so the build is now breaking. Please see

          https://builds.apache.org/view/M-R/view/Qpid/job/Qpid-proton-j/495/console

          Can we enable tcp no delay on the socket instead?

          regards, Keith.

          btw. to which components does this Jira apply? The Jira title starts [proton-c]..., but the assigned component is proton-j.

          Show
          Keith Wall added a comment - - edited Hi Ken, That commit (rev 1547534) uses JDK 7 specific features (specifically java.net.StandardSocketOptions) so the build is now breaking. Please see https://builds.apache.org/view/M-R/view/Qpid/job/Qpid-proton-j/495/console Can we enable tcp no delay on the socket instead? regards, Keith. btw. to which components does this Jira apply? The Jira title starts [proton-c] ..., but the assigned component is proton-j.
          Hide
          ASF subversion and git services added a comment -

          Commit 1547797 from Ken Giusti in branch 'proton/trunk'
          [ https://svn.apache.org/r1547797 ]

          PROTON-200: use setTcpNoDelay instead of JDK7 only StandardSocketOptions

          Show
          ASF subversion and git services added a comment - Commit 1547797 from Ken Giusti in branch 'proton/trunk' [ https://svn.apache.org/r1547797 ] PROTON-200 : use setTcpNoDelay instead of JDK7 only StandardSocketOptions

            People

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

              Dates

              • Created:
                Updated:
                Resolved:

                Development