Camel
  1. Camel
  2. CAMEL-5039

Make WeightedRandomLoadBalancer really random

    Details

    • Type: Improvement Improvement
    • Status: Resolved
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 2.10.0
    • Component/s: camel-core
    • Labels:
      None
    • Estimated Complexity:
      Unknown

      Description

      As Mark Harwood explained in last comment of CAMEL-3197 the WeightedRandomLoadBalancer is not doing a good load balancing job if some weight are a lot bigger than some other weight.
      See in the attached example (current-impl-result.txt), the first and third routes are always called at the very beginning of every 50 iterations loadbalancing round.
      I propose a modified algorithm that do a more balanced loadbalancing (new-impl-result.txt)

      Attached the test program with the proposed implementation.

      1. out.txt
        16 kB
        Xavier Fournet
      2. CamelLoadBalancerTest.java
        16 kB
        Xavier Fournet
      3. new-impl-result.txt
        4 kB
        Xavier Fournet
      4. current-impl-result.txt
        4 kB
        Xavier Fournet
      5. CamelLoadBalancerTest.java
        4 kB
        Xavier Fournet

        Issue Links

          Activity

          Hide
          Ashwin Karpe added a comment -

          Hi Mark & Xavier,

          I understand where you are coming from... I will change the behavior suitably and add make it truly random.

          Cheers,

          Ashwin...

          Show
          Ashwin Karpe added a comment - Hi Mark & Xavier, I understand where you are coming from... I will change the behavior suitably and add make it truly random. Cheers, Ashwin...
          Hide
          Ashwin Karpe added a comment -

          Hi,

          Here is a simple and cleaner implementation, I propose. However being random, the weighted delivery can only be checked in a roundabout way.

          The pseudo code shows how I would like to implement the solution. Note that the final implementation will be more refined and account for many different/additional ratios (i.e X:Y:Z:A:B:C).

          The challenge of course will be the testing aspect of the truly random distribution and I welcome feedback in this regard.

          Please comment...

          Cheers,

          Ashwin...

          ---------------------------------------------------------------------------------------
          Proposal.
          ---------
          For a given distribution ratio (X:Y:Z:A)

          [pseudo_code]

          range1 = X
          range2 = X+Y
          range3 = X+Y+Z
          range4 = X+Y+Z+A
          random_seed = X+Y+Z+A

          selection = random(random_seed);
          if (selection <= range1)

          { dispatchToRoute1(); }

          else if (selection > range1) && (selection <= range2)

          { dispatchToRoute2(); }

          else if (selection > range2) && (selection <= range3)

          { dispatchToRoute3(); }

          else if (selection > range1) && (selection <= range2)

          { dispatchToRoute4(); }
          Show
          Ashwin Karpe added a comment - Hi, Here is a simple and cleaner implementation, I propose. However being random, the weighted delivery can only be checked in a roundabout way. The pseudo code shows how I would like to implement the solution. Note that the final implementation will be more refined and account for many different/additional ratios (i.e X:Y:Z:A:B:C). The challenge of course will be the testing aspect of the truly random distribution and I welcome feedback in this regard. Please comment... Cheers, Ashwin... --------------------------------------------------------------------------------------- Proposal. --------- For a given distribution ratio (X:Y:Z:A) [pseudo_code] range1 = X range2 = X+Y range3 = X+Y+Z range4 = X+Y+Z+A random_seed = X+Y+Z+A selection = random(random_seed); if (selection <= range1) { dispatchToRoute1(); } else if (selection > range1) && (selection <= range2) { dispatchToRoute2(); } else if (selection > range2) && (selection <= range3) { dispatchToRoute3(); } else if (selection > range1) && (selection <= range2) { dispatchToRoute4(); }
          Hide
          Xavier Fournet added a comment -

          Hi Ashwin,

          your pseudo code is quite similar with the mine I had attached before. The difference is in the strict application of the round robin at each round or a statistical application of the weights on a long number of execution.

          I just notice that this is quite similar with the coding challenge recently proposed by Cedric Beust, see
          http://beust.com/weblog/2012/02/16/a-new-coding-challenge-2/
          http://beust.com/weblog/2012/02/20/various-ways-to-get-randomness-wrong/

          I used and adapted his method to check the randomness of the repartition. I also added some stats on distances between the choice of the same processor.
          I also worked on the round robin implementation that suffer the same kind of default

          I have tested three random implementation:

          • CurrentWeightedRandomLoadBalancer: the current camel random implentation
          • NewStrictWeightedRandomLoadBalancer: a random algorithm with strict weight loadbalancing at each turn (ie the one I had previously proposed)
          • NewApproximateWeightedRandomLoadBalancer: a random algorithm with non-strict weight loadbalancing at each turn (ie the one you propose if I had correctly implemented it)
            and 2 two round robin implementation
          • CurrentWeightedRoundRobinLoadBalancer: the current camel random implementation
          • NewWeightedRoundRobinLoadBalancer: a new implementation that try to do a better loadbalacing (ie avoid peak)

          Results (the out.txt attachment has been created by using 2 14 3 1 weights as program arguments)

          • every algorithm respect the weight (see last line of Distribution matrix)
          • CurrentWeightedRandomLoadBalancer is clearly not random if we consider the criteria exposed by Cedric (see Max of error and Average of error, both are in percentage)
          • NewStrictWeightedRandomLoadBalancer and NewApproximateWeightedRandomLoadBalancer can be considered random and performs equally in regards of this criterias. However considering the standard deviations of the distances between two same choosen endpoint, the NewStrictWeightedRandomLoadBalancer is doing a better job especially on routes with lowest weigths ie it minimize the risk of peaks)
          • NewWeightedRoundRobinLoadBalancer do a better job for pure round robin but is not perfect. I used a naive approach, may be someone could have better idea to implement it ? the goal is to minize at the maximum the distance stddev

          best regards,

          Xavier

          Show
          Xavier Fournet added a comment - Hi Ashwin, your pseudo code is quite similar with the mine I had attached before. The difference is in the strict application of the round robin at each round or a statistical application of the weights on a long number of execution. I just notice that this is quite similar with the coding challenge recently proposed by Cedric Beust, see http://beust.com/weblog/2012/02/16/a-new-coding-challenge-2/ http://beust.com/weblog/2012/02/20/various-ways-to-get-randomness-wrong/ I used and adapted his method to check the randomness of the repartition. I also added some stats on distances between the choice of the same processor. I also worked on the round robin implementation that suffer the same kind of default I have tested three random implementation: CurrentWeightedRandomLoadBalancer: the current camel random implentation NewStrictWeightedRandomLoadBalancer: a random algorithm with strict weight loadbalancing at each turn (ie the one I had previously proposed) NewApproximateWeightedRandomLoadBalancer: a random algorithm with non-strict weight loadbalancing at each turn (ie the one you propose if I had correctly implemented it) and 2 two round robin implementation CurrentWeightedRoundRobinLoadBalancer: the current camel random implementation NewWeightedRoundRobinLoadBalancer: a new implementation that try to do a better loadbalacing (ie avoid peak) Results (the out.txt attachment has been created by using 2 14 3 1 weights as program arguments) every algorithm respect the weight (see last line of Distribution matrix) CurrentWeightedRandomLoadBalancer is clearly not random if we consider the criteria exposed by Cedric (see Max of error and Average of error, both are in percentage) NewStrictWeightedRandomLoadBalancer and NewApproximateWeightedRandomLoadBalancer can be considered random and performs equally in regards of this criterias. However considering the standard deviations of the distances between two same choosen endpoint, the NewStrictWeightedRandomLoadBalancer is doing a better job especially on routes with lowest weigths ie it minimize the risk of peaks) NewWeightedRoundRobinLoadBalancer do a better job for pure round robin but is not perfect. I used a naive approach, may be someone could have better idea to implement it ? the goal is to minize at the maximum the distance stddev best regards, Xavier
          Hide
          Ashwin Karpe added a comment - - edited

          Hi Xavier,

          Your analysis is entirely correct. My original implementation was weight-biased and the proposed one is skewed towards randomness.

          More importantly, upon closer review, your algorithm offers the right balance between weighting and randomness. In addition, the solution offers better ability to test that the weighting criteria is being met periodically.

          I will review your code and apply it to the trunk.

          Thanks for your input. I appreciate it.

          Cheers,

          Ashwin...

          Show
          Ashwin Karpe added a comment - - edited Hi Xavier, Your analysis is entirely correct. My original implementation was weight-biased and the proposed one is skewed towards randomness. More importantly, upon closer review, your algorithm offers the right balance between weighting and randomness. In addition, the solution offers better ability to test that the weighting criteria is being met periodically. I will review your code and apply it to the trunk. Thanks for your input. I appreciate it. Cheers, Ashwin...
          Hide
          Ashwin Karpe added a comment -

          Hi Xavier,

          I have made the fix based on your code submission, Many thanks to you for your time and effort in identifying and submitting this patch along with the documented test cases.

          The committed revision is https://svn.apache.org/viewvc?view=revision&revision=1294693.

          Sincerely,

          Ashwin...

          Show
          Ashwin Karpe added a comment - Hi Xavier, I have made the fix based on your code submission, Many thanks to you for your time and effort in identifying and submitting this patch along with the documented test cases. The committed revision is https://svn.apache.org/viewvc?view=revision&revision=1294693 . Sincerely, Ashwin...
          Hide
          Ashwin Karpe added a comment -

          Fixed and committed to Subversion 1294693. Many thanks again to Xavier Fournet for the patch...

          • Ashwin...
          Show
          Ashwin Karpe added a comment - Fixed and committed to Subversion 1294693. Many thanks again to Xavier Fournet for the patch... Ashwin...
          Hide
          Xavier Fournet added a comment -

          Hi Ashwin,
          many thanks for integrating the fix!
          Cheers,

          Show
          Xavier Fournet added a comment - Hi Ashwin, many thanks for integrating the fix! Cheers,

            People

            • Assignee:
              Ashwin Karpe
              Reporter:
              Xavier Fournet
            • Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development