BalancedShardsAllocator's algorithm


(whnannan) #1

Hi,
I had a quick look at BalancedShardsAllocator , but I don't understand
about the algorithm it used. Is there any information about the algorithm
used in BalancedShardsAllocator?

--
You received this message because you are subscribed to the Google Groups "elasticsearch" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elasticsearch+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.


(simonw-2) #2

What exactly do you want to know?

simon

On Friday, September 13, 2013 5:01:14 AM UTC+2, whna...@gmail.com wrote:

Hi,
I had a quick look at BalancedShardsAllocator , but I don't understand
about the algorithm it used. Is there any information about the algorithm
used in BalancedShardsAllocator?

--
You received this message because you are subscribed to the Google Groups "elasticsearch" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elasticsearch+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.


(whnannan) #3

I don't understand the method to chose the minNode when (currentWeight ==
minWeight).
I don't understand about the annotation below :
/* we have an equal weight tie breaking:

    1. if one decision is YES prefer it
    1. prefer the node that holds the primary for this index with the next
      id in the ring ie.
  • for the 3 shards 2 replica case we try to build up:
  • 1 2 0
  • 2 0 1
  • 0 1 2
  • such that if we need to tie-break we try to prefer the node holding a
    shard with the minimal id greater
  • than the id of the shard we need to assign. This works find when new
    indices are created since
  • primaries are added first and we only add one shard set a time in this
    algorithm.
    */

thanks

在 2013年9月13日星期五UTC+8下午3时30分02秒,simonw写道:

What exactly do you want to know?

simon

On Friday, September 13, 2013 5:01:14 AM UTC+2, whna...@gmail.com wrote:

Hi,
I had a quick look at BalancedShardsAllocator , but I don't understand
about the algorithm it used. Is there any information about the algorithm
used in BalancedShardsAllocator?

--
You received this message because you are subscribed to the Google Groups "elasticsearch" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elasticsearch+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.


(simonw-2) #4

if you have 3 nodes and an index with 3 shards 1 replicas you can end up
with an unbalanced cluster like this

after allocation round 1:

node 1 has shards [0]
node 2 has shards [1]
node 3 has shards [2]

if you do round 2 you might end up with this after adding replicas for
shard 0 & 1:

node 1 has shards [0, 1]
node 2 has shards [1, 0]
node 3 has shards [2]

now you are in a deadlock since you can't allocate a replica for shard 2
anymore on node 3 since it already has a replica of the same shard.

With the combinatorial allocation step you are looking at there I try to
prevent these situations

hope this makes more sense now.

simon

On Friday, September 13, 2013 10:13:17 AM UTC+2, whna...@gmail.com wrote:

I don't understand the method to chose the minNode when (currentWeight ==
minWeight).
I don't understand about the annotation below :
/* we have an equal weight tie breaking:

    1. if one decision is YES prefer it
    1. prefer the node that holds the primary for this index with the next
      id in the ring ie.
  • for the 3 shards 2 replica case we try to build up:
  • 1 2 0
  • 2 0 1
  • 0 1 2
  • such that if we need to tie-break we try to prefer the node holding a
    shard with the minimal id greater
  • than the id of the shard we need to assign. This works find when new
    indices are created since
  • primaries are added first and we only add one shard set a time in this
    algorithm.
    */

thanks

在 2013年9月13日星期五UTC+8下午3时30分02秒,simonw写道:

What exactly do you want to know?

simon

On Friday, September 13, 2013 5:01:14 AM UTC+2, whna...@gmail.com wrote:

Hi,
I had a quick look at BalancedShardsAllocator , but I don't
understand about the algorithm it used. Is there any information about the
algorithm used in BalancedShardsAllocator?

--
You received this message because you are subscribed to the Google Groups "elasticsearch" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elasticsearch+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.


(whnannan) #5

Thank you very much !

在 2013年9月13日星期五UTC+8下午6时36分11秒,simonw写道:

if you have 3 nodes and an index with 3 shards 1 replicas you can end up
with an unbalanced cluster like this

after allocation round 1:

node 1 has shards [0]
node 2 has shards [1]
node 3 has shards [2]

if you do round 2 you might end up with this after adding replicas for
shard 0 & 1:

node 1 has shards [0, 1]
node 2 has shards [1, 0]
node 3 has shards [2]

now you are in a deadlock since you can't allocate a replica for shard 2
anymore on node 3 since it already has a replica of the same shard.

With the combinatorial allocation step you are looking at there I try to
prevent these situations

hope this makes more sense now.

simon

On Friday, September 13, 2013 10:13:17 AM UTC+2, whna...@gmail.com wrote:

I don't understand the method to chose the minNode when (currentWeight ==
minWeight).
I don't understand about the annotation below :
/* we have an equal weight tie breaking:

    1. if one decision is YES prefer it
    1. prefer the node that holds the primary for this index with the next
      id in the ring ie.
  • for the 3 shards 2 replica case we try to build up:
  • 1 2 0
  • 2 0 1
  • 0 1 2
  • such that if we need to tie-break we try to prefer the node holding a
    shard with the minimal id greater
  • than the id of the shard we need to assign. This works find when new
    indices are created since
  • primaries are added first and we only add one shard set a time in this
    algorithm.
    */

thanks

在 2013年9月13日星期五UTC+8下午3时30分02秒,simonw写道:

What exactly do you want to know?

simon

On Friday, September 13, 2013 5:01:14 AM UTC+2, whna...@gmail.com wrote:

Hi,
I had a quick look at BalancedShardsAllocator , but I don't
understand about the algorithm it used. Is there any information about the
algorithm used in BalancedShardsAllocator?

--
You received this message because you are subscribed to the Google Groups "elasticsearch" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elasticsearch+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.


(simonw-2) #6

you are welcome! if you have more questions I am happy to help.

simon

On Saturday, September 14, 2013 6:48:02 AM UTC+2, whna...@gmail.com wrote:

Thank you very much !

在 2013年9月13日星期五UTC+8下午6时36分11秒,simonw写道:

if you have 3 nodes and an index with 3 shards 1 replicas you can end up
with an unbalanced cluster like this

after allocation round 1:

node 1 has shards [0]
node 2 has shards [1]
node 3 has shards [2]

if you do round 2 you might end up with this after adding replicas for
shard 0 & 1:

node 1 has shards [0, 1]
node 2 has shards [1, 0]
node 3 has shards [2]

now you are in a deadlock since you can't allocate a replica for shard 2
anymore on node 3 since it already has a replica of the same shard.

With the combinatorial allocation step you are looking at there I try to
prevent these situations

hope this makes more sense now.

simon

On Friday, September 13, 2013 10:13:17 AM UTC+2, whna...@gmail.com wrote:

I don't understand the method to chose the minNode when (currentWeight
== minWeight).
I don't understand about the annotation below :
/* we have an equal weight tie breaking:

    1. if one decision is YES prefer it
    1. prefer the node that holds the primary for this index with the
      next id in the ring ie.
  • for the 3 shards 2 replica case we try to build up:
  • 1 2 0
  • 2 0 1
  • 0 1 2
  • such that if we need to tie-break we try to prefer the node holding a
    shard with the minimal id greater
  • than the id of the shard we need to assign. This works find when new
    indices are created since
  • primaries are added first and we only add one shard set a time in
    this algorithm.
    */

thanks

在 2013年9月13日星期五UTC+8下午3时30分02秒,simonw写道:

What exactly do you want to know?

simon

On Friday, September 13, 2013 5:01:14 AM UTC+2, whna...@gmail.comwrote:

Hi,
I had a quick look at BalancedShardsAllocator , but I don't
understand about the algorithm it used. Is there any information about the
algorithm used in BalancedShardsAllocator?

--
You received this message because you are subscribed to the Google Groups "elasticsearch" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elasticsearch+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.


(system) #7