elasticsearch/elasticsearch — pull request #4259 by geidies (2013-11-26 16:54:37+00:00)
Title: AllocationDeciders should be executed in order, starting at "cheap execution" and "most likely to return no"

The different AllocationDeciders are more or less expensive processing wise. They are also more or less likely to return a Decision.NO or Decision.THROTTLE. For large clusters this can result in a 10-15% speedup in recalculating the cluster state (tested with https://github.com/geidies/elasticsearch/blob/optimize_RoutingNodes/src/test/java/org/elasticsearch/cluster/routing/allocation/MassiveClusterRebalanceRoutingTests.java - 3.7 seconds on my test machine compared to 4.2 seconds without the optimization).

ConcurrentRebalanceAllocationDecider - loops over all ShardRoutings, O(n), optimization to O(1) for that in separate PR
DisableAllocationDecider - is O(1)
ClusterRebalanceAllocationDecider - is O( #shards_unassigned ) + O( #shards ) or O( 1 ) + O( #shards ) - optimization for that in separate PR, making it O( 2 )
DiskThresholdDecider - O( 2 )
SnapshotInProgressAllocationDecider - O( 1 )
ReplicaAfterPrimaryActiveAllocationDecider and RebalanceOnlyWhenActiveAllocationDecider - O( #shards ) with current implementation of RoutingNodes.getShardsRoutingFor( MutableShardRouting ) - optimization in separate PR, making it O( #shards in replica set )
ShardsLimitAllocationDecider is O( # shards on node ) + O( 1 ).
AwarenessAllocationDecider is O( # shards in cluster ) * # awareness attributes, making it the most expensive, but least likely to be turned on.
SameShardAllocationDecider is O( # shards on node ) * # nodes on host
ThrottlingAllocationDecider, which is O( #shards_per_node ) + O( #shards_per_node )

In addition to the re-ordering, instead of applying all AllocationDeciders, skip the rest of one return a Decision.NO. This logic is ported from the Decision.Multi class.