stratos-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Rajkumar Rajaratnam <rajkum...@wso2.com>
Subject Re: Bug in round-robin partition selection algorithm
Date Wed, 04 Mar 2015 04:12:14 GMT
Hi Reka,

On Wed, Mar 4, 2015 at 1:03 AM, Reka Thirunavukkarasu <reka@wso2.com> wrote:

> I think that there is small issue in applying the same RR logic for scale
> up and scale down. if it sclaes up, then
>
> p1 -1, p2-1, p3-1, p1-2, p2-2
>
> Then, if we are to continuously scale down, then which partition will we
> choose next? Will it be p3? In that way, it won't be equally
> distributed..In order to equally distributed, we should choose the
> partition in the reverse order in the scale down p2, p1, p3, p2, p1.
>
> Then as you mentioned, we will need another algorithm specially when
> scaling down. We can apply forward RR in scale up and backward RR in
> scaling down in order to equally distributed the instances.
>

Again , if we don't persist current partition index, this logic is also not
a pure RR.

Current logic is working perfectly according to "equally distribute to
partitions" concept in both scale up/down scenarios. But I agree its not a
pure RR.

IMHO, as Lahiru mentioned, intention of having RR is to equally distribute
instances among partitions. So can we stick to this logic for now? If we
find any issues, we can improve it later.

WDYT?

>
> Thanks,
> Reka
>
>
>
> On Tue, Mar 3, 2015 at 12:24 PM, Rajkumar Rajaratnam <rajkumarr@wso2.com>
> wrote:
>
>> What I meant in the previous reply is the following scenario.
>>
>> For eg:
>>
>> p1, p2 , p3
>>
>> If the iteration goes as below:
>> selectedIndex = -1
>>
>> since all the partitions has 0 instances, choose the first partition as
>> the selectedIndex = 1
>>
>> p1 - 1    selectedIndex = 1
>> p2 - 1   selectedIndex =  2
>> p3 - 1    selectedIndex =  3
>> p1 - 2    selectedIndex =  1
>>
>> scale down happens, instance will be removed from p1
>> p1 = 1, p2 = 1, p3 = 1
>>
>> stratos restart
>> selectedIndex = -1
>>
>> p1 = 2, p2=1, p3=1 choose the first lower instances partition which will
>> be p1.
>> selectedIndex=1 now, hence not a pure RR.
>>
>> I guess, it is impossible to implement a pure RR without persisting
>> current partition index.
>>
>> Thanks.
>>
>> On Wed, Mar 4, 2015 at 12:29 AM, Rajkumar Rajaratnam <rajkumarr@wso2.com>
>> wrote:
>>
>>> Hi Reka,
>>>
>>> There is small issue in the way you suggested above. If you consider
>>> scale down scenario, you can't actually say p2 will have min number
>>> instances. It can be p1, if scale down happened from p1. So if we restart
>>> the stratos, RR will select p1 as next partition right? This is not a pure
>>> RR right?
>>>
>>> Thanks.
>>>
>>> On Wed, Mar 4, 2015 at 12:24 AM, Reka Thirunavukkarasu <reka@wso2.com>
>>> wrote:
>>>
>>>> Hi Raj,
>>>>
>>>> I don't think that we will need another algorithm. If we implement RR
>>>> in the way that i explained, then it will even make sure to distribute the
>>>> members equally.
>>>>
>>>> For eg:
>>>>
>>>> p1, p2 , p3
>>>>
>>>> If the iteration goes as below:
>>>> selectedIndex = -1
>>>>
>>>> since all the partitions has 0 instances, choose the first partition as
>>>> the selectedIndex = 1
>>>>
>>>> p1 - 1    selectedIndex = 1
>>>> p2 - 1   selectedIndex =  2
>>>> p3 - 1    selectedIndex =  3
>>>> p1 - 2    selectedIndex =  1
>>>>
>>>> stratos restart
>>>> selectedIndex = -1
>>>>
>>>> p1 = 2, p2=1, p3=1 choose the first lower instances partition which
>>>> will be p2. (sorry i missed this point earlier)
>>>> selectedIndex=2 now
>>>>
>>>> then iteration can start from where it stops before the restart.
>>>>
>>>> p2 - 2    selectedIndex = 2
>>>> p3 - 2    selectedIndex = 3
>>>> p1 - 3    selectedIndex = 1
>>>> p2 - 3    selectedIndex = 2
>>>> p3 - 3    selectedIndex = 3
>>>>
>>>> If we implement RR in this way,  the instances will be equally
>>>> distributed as well.
>>>>
>>>> Thanks,
>>>> Reka
>>>>
>>>>
>>>> Thanks,
>>>> Reka
>>>>
>>>> On Tue, Mar 3, 2015 at 11:43 AM, Rajkumar Rajaratnam <
>>>> rajkumarr@wso2.com> wrote:
>>>>
>>>>> So I guess we have three algorithms :)
>>>>>
>>>>> 1. one-after-another (It will go to next partition only if the current
>>>>> partition is full)
>>>>> 2. round-robin (if we implement as Reka explained above. It will
>>>>> always select the next partition)
>>>>> 3. name-should-be-decided (this will work as Lahiru explained above.
>>>>> It will always distribute the members in the partitions equally)
>>>>>
>>>>> WDYT?
>>>>>
>>>>> Thanks.
>>>>>
>>>>> On Wed, Mar 4, 2015 at 12:01 AM, Reka Thirunavukkarasu <reka@wso2.com>
>>>>> wrote:
>>>>>
>>>>>> I think that if the selectedIndex is initial value as -1, then RR
>>>>>> should traverse through all the partitions and find out who has the
minimum
>>>>>> instances and choose that partition as the selectedIndex in the first
>>>>>> iteration(may be we can exc). Then from the second iteration onwards,
it
>>>>>> can increase the selectedIndex by 1 to choose the next adjacent partition.
>>>>>> This will help in the stratos restart as we don't persist the
>>>>>> selectedIndex. WDYT?
>>>>>>
>>>>>> On Tue, Mar 3, 2015 at 10:53 AM, Lahiru Sandaruwan <lahirus@wso2.com>
>>>>>> wrote:
>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Mar 3, 2015 at 11:15 PM, Rajkumar Rajaratnam <
>>>>>>> rajkumarr@wso2.com> wrote:
>>>>>>>
>>>>>>>> Problem is lowestInstanceCount is initially taking 0. Instead
it
>>>>>>>> should take the non terminated member count of 1st partition.
>>>>>>>>
>>>>>>>> To Fix,
>>>>>>>>
>>>>>>>>         int selectedIndex = 0;
>>>>>>>>         int lowestInstanceCount =
>>>>>>>> partitionContexts[0].getNonTerminatedMemberCount();
>>>>>>>>
>>>>>>>>
>>>>>>> +1. I was thinking the same. We can start with first partition
count.
>>>>>>>
>>>>>>> Thanks.
>>>>>>>
>>>>>>>> wdyt?
>>>>>>>>
>>>>>>>> Thanks.
>>>>>>>>
>>>>>>>> On Tue, Mar 3, 2015 at 10:57 PM, Rajkumar Rajaratnam <
>>>>>>>> rajkumarr@wso2.com> wrote:
>>>>>>>>
>>>>>>>>> Hi Lahiru,
>>>>>>>>>
>>>>>>>>> Actually, current logic is not working as your example.
This logic
>>>>>>>>> only uses the first partition. This will never use any
other partitions.
>>>>>>>>> See my comments within the following code.
>>>>>>>>>
>>>>>>>>>     public PartitionContext
>>>>>>>>> getNextScaleUpPartitionContext(PartitionContext[] partitionContexts)
{
>>>>>>>>>
>>>>>>>>>         int selectedIndex = 0;
>>>>>>>>>         int lowestInstanceCount = 0;
>>>>>>>>>
>>>>>>>>>         for(int partitionIndex = 0; partitionIndex <
>>>>>>>>> partitionContexts.length - 1; partitionIndex++) {
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> if(partitionContexts[partitionIndex].getNonTerminatedMemberCount()
<
>>>>>>>>> lowestInstanceCount) {
>>>>>>>>>
>>>>>>>>> *//  this if condition is always false, because non terminated
>>>>>>>>> count is always >=0*
>>>>>>>>>
>>>>>>>>>                 lowestInstanceCount =
>>>>>>>>> partitionContexts[partitionIndex].getNonTerminatedMemberCount();
>>>>>>>>>                 selectedIndex = partitionIndex;
>>>>>>>>>             }
>>>>>>>>>         }
>>>>>>>>>
>>>>>>>>> *//  selected index is 0 always, so round-robin will
always use
>>>>>>>>> first partition*
>>>>>>>>>
>>>>>>>>> if(partitionContexts[selectedIndex].getNonTerminatedMemberCount()
<
>>>>>>>>> partitionContexts[selectedIndex].getMax()) {
>>>>>>>>>
>>>>>>>>>             if(log.isDebugEnabled()){
>>>>>>>>>                 log.debug(String.format("[round-robin
algorithm]
>>>>>>>>> [scale-up] [partition] %s has space to create members.
" +
>>>>>>>>>                         "[non terminated count] %s [max]
%s"
>>>>>>>>>                         ,
>>>>>>>>> partitionContexts[selectedIndex].getPartitionId(),
>>>>>>>>>
>>>>>>>>> partitionContexts[selectedIndex].getNonTerminatedMemberCount(),
>>>>>>>>>
>>>>>>>>> partitionContexts[selectedIndex].getMax()));
>>>>>>>>>             }
>>>>>>>>>             return partitionContexts[selectedIndex];
>>>>>>>>>         } else {
>>>>>>>>>
>>>>>>>>>             return null;
>>>>>>>>>         }
>>>>>>>>>     }
>>>>>>>>>
>>>>>>>>> May be I am missing something here.
>>>>>>>>>
>>>>>>>>> Thanks.
>>>>>>>>>
>>>>>>>>> On Tue, Mar 3, 2015 at 10:42 PM, Lahiru Sandaruwan <
>>>>>>>>> lahirus@wso2.com> wrote:
>>>>>>>>>
>>>>>>>>>> Hi Raj,
>>>>>>>>>>
>>>>>>>>>> Earlier in 4.0.0 release, we have been using the
partition index.
>>>>>>>>>> If that to be worked correctly we should persist
the index for each
>>>>>>>>>> cluster.
>>>>>>>>>>
>>>>>>>>>> IMO there is a better way to execute the round-robin
method as
>>>>>>>>>> follows,
>>>>>>>>>>
>>>>>>>>>> The intention of round robin algorithm is to distribute
the
>>>>>>>>>> members in the partitions equally. Current method
works as per the
>>>>>>>>>> following example.
>>>>>>>>>>
>>>>>>>>>> Say we have 3 partitions, p1, p2, and p3 and max
of each
>>>>>>>>>> partition is 2.
>>>>>>>>>>
>>>>>>>>>> So according to the algorithm, it will select the
first partition
>>>>>>>>>> who has the lowest member count.
>>>>>>>>>>
>>>>>>>>>> Iteration1: It will select p1.
>>>>>>>>>> Iteration2: It will select p2.
>>>>>>>>>> Iteration3: It will select p3.
>>>>>>>>>> Iteration4: It will select p1.
>>>>>>>>>> Iteration5: It will select p2.
>>>>>>>>>> ....
>>>>>>>>>>
>>>>>>>>>> Thanks.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> On Tue, Mar 3, 2015 at 10:22 PM, Rajkumar Rajaratnam
<
>>>>>>>>>> rajkumarr@wso2.com> wrote:
>>>>>>>>>>
>>>>>>>>>>> Hi Devs,
>>>>>>>>>>>
>>>>>>>>>>> It seems to me that there is a bug in round-robin
implementation
>>>>>>>>>>> of partition algorithm.
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> https://github.com/apache/stratos/blob/0b7734f4c9f1444d064fec93bf9ac59a5883faf2/components/org.apache.stratos.autoscaler/src/main/java/org/apache/stratos/autoscaler/algorithm/RoundRobin.java#L43-L64
>>>>>>>>>>>
>>>>>>>>>>> Shouldn't it work based on current partition
index? For example,
>>>>>>>>>>> if the most recent instance was spin up in partition-1,
the next instance
>>>>>>>>>>> should be spin up in partition-2 and so on. According
to current logic what
>>>>>>>>>>> is happening is, all the instance are spin up
in partition-1.
>>>>>>>>>>>
>>>>>>>>>>> Please correct me If I am wrong.
>>>>>>>>>>>
>>>>>>>>>>> Thanks.
>>>>>>>>>>>
>>>>>>>>>>> --
>>>>>>>>>>> Rajkumar Rajaratnam
>>>>>>>>>>> Committer & PMC Member, Apache Stratos
>>>>>>>>>>> Software Engineer, WSO2
>>>>>>>>>>>
>>>>>>>>>>> Mobile : +94777568639
>>>>>>>>>>> Blog : rajkumarr.com
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> --
>>>>>>>>>> --
>>>>>>>>>> Lahiru Sandaruwan
>>>>>>>>>> Committer and PMC member, Apache Stratos,
>>>>>>>>>> Senior Software Engineer,
>>>>>>>>>> WSO2 Inc., http://wso2.com
>>>>>>>>>> lean.enterprise.middleware
>>>>>>>>>>
>>>>>>>>>> email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
>>>>>>>>>> linked-in:
>>>>>>>>>> http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> Rajkumar Rajaratnam
>>>>>>>>> Committer & PMC Member, Apache Stratos
>>>>>>>>> Software Engineer, WSO2
>>>>>>>>>
>>>>>>>>> Mobile : +94777568639
>>>>>>>>> Blog : rajkumarr.com
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> --
>>>>>>>> Rajkumar Rajaratnam
>>>>>>>> Committer & PMC Member, Apache Stratos
>>>>>>>> Software Engineer, WSO2
>>>>>>>>
>>>>>>>> Mobile : +94777568639
>>>>>>>> Blog : rajkumarr.com
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> --
>>>>>>> Lahiru Sandaruwan
>>>>>>> Committer and PMC member, Apache Stratos,
>>>>>>> Senior Software Engineer,
>>>>>>> WSO2 Inc., http://wso2.com
>>>>>>> lean.enterprise.middleware
>>>>>>>
>>>>>>> email: lahirus@wso2.com blog: http://lahiruwrites.blogspot.com/
>>>>>>> linked-in: http://lk.linkedin.com/pub/lahiru-sandaruwan/16/153/146
>>>>>>>
>>>>>>>
>>>>>>
>>>>>>
>>>>>> --
>>>>>> Reka Thirunavukkarasu
>>>>>> Senior Software Engineer,
>>>>>> WSO2, Inc.:http://wso2.com,
>>>>>> Mobile: +94776442007
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Rajkumar Rajaratnam
>>>>> Committer & PMC Member, Apache Stratos
>>>>> Software Engineer, WSO2
>>>>>
>>>>> Mobile : +94777568639
>>>>> Blog : rajkumarr.com
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Reka Thirunavukkarasu
>>>> Senior Software Engineer,
>>>> WSO2, Inc.:http://wso2.com,
>>>> Mobile: +94776442007
>>>>
>>>>
>>>>
>>>
>>>
>>> --
>>> Rajkumar Rajaratnam
>>> Committer & PMC Member, Apache Stratos
>>> Software Engineer, WSO2
>>>
>>> Mobile : +94777568639
>>> Blog : rajkumarr.com
>>>
>>
>>
>>
>> --
>> Rajkumar Rajaratnam
>> Committer & PMC Member, Apache Stratos
>> Software Engineer, WSO2
>>
>> Mobile : +94777568639
>> Blog : rajkumarr.com
>>
>
>
>
> --
> Reka Thirunavukkarasu
> Senior Software Engineer,
> WSO2, Inc.:http://wso2.com,
> Mobile: +94776442007
>
>
>


-- 
Rajkumar Rajaratnam
Committer & PMC Member, Apache Stratos
Software Engineer, WSO2

Mobile : +94777568639
Blog : rajkumarr.com

Mime
View raw message