On Wed, Jun 17, 2015 at 07:11:12PM +0200, 'Klaus Aehlig' via ganeti-devel wrote:
In the current computation of `iterateAlloc` most of the time
is spent in checking whether the obtained situation is globally
N+1 redundant. However, actually finding a non N+1 redundant
situation only happens at the very end in a long sequence of iterations
in an hspace-like use case. Therefore, we allocate a group of instances
in one block without checking global N+1 redundancy; if that happens to
yield a globally N+1 redundant situation, we can continue from there.
Only when that heuristics fails, we do allocation step by step checking
global N+1 redundancy in each allocation step.
Signed-off-by: Klaus Aehlig <[email protected]>
---
src/Ganeti/HTools/Cluster.hs | 37 +++++++++++++++++++++++++++++++++----
1 file changed, 33 insertions(+), 4 deletions(-)
diff --git a/src/Ganeti/HTools/Cluster.hs b/src/Ganeti/HTools/Cluster.hs
index 7f024b2..6b61b5b 100644
--- a/src/Ganeti/HTools/Cluster.hs
+++ b/src/Ganeti/HTools/Cluster.hs
@@ -108,7 +108,7 @@ import Ganeti.HTools.Cluster.Metrics ( compCV,
compCVfromStats
import Ganeti.HTools.Cluster.Moves (setInstanceLocationScore, applyMoveEx)
import Ganeti.HTools.Cluster.Utils (splitCluster, instancePriGroup
, availableGroupNodes, iMoveToJob)
-import Ganeti.HTools.GlobalN1 (allocGlobalN1)
+import Ganeti.HTools.GlobalN1 (allocGlobalN1, redundant)
import qualified Ganeti.HTools.Instance as Instance
import qualified Ganeti.HTools.Nic as Nic
import qualified Ganeti.HTools.Node as Node
@@ -786,8 +786,8 @@ tryChangeGroup opts gl ini_nl ini_il gdxs idxs =
-- This places instances of the same size on the cluster until we're
-- out of space. The result will be a list of identically-sized
-- instances.
-iterateAlloc :: AlgorithmOptions -> AllocMethod
-iterateAlloc opts nl il limit newinst allocnodes ixes cstats =
+iterateAllocSmallStep :: AlgorithmOptions -> AllocMethod
+iterateAllocSmallStep opts nl il limit newinst allocnodes ixes cstats =
let depth = length ixes
newname = printf "new-%d" depth::String
newidx = Container.size il
@@ -805,10 +805,39 @@ iterateAlloc opts nl il limit newinst allocnodes ixes
cstats =
Just (xnl, xi, _, _) ->
if limit == Just 0
then newsol
- else iterateAlloc opts xnl (Container.add newidx xi il)
+ else iterateAllocSmallStep opts xnl (Container.add newidx xi il)
newlimit newinst allocnodes (xi:ixes)
(totalResources xnl:cstats)
+-- | A speed-up version of `iterateAllocSmallStep`.
+--
+-- This function returns precisely the same result as `iterateAllocSmallStep`.
+-- However the computation is speed up by the following heuristic: allocate
+-- a group of instances iteratively without considering global N+1 redundancy;
+-- if the result of this is globally N+1 redundant, then everything was OK
+-- inbetween and we can continue from there. Only if that fails, do a
+-- step-by-step iterative allocation.
+iterateAlloc :: AlgorithmOptions -> AllocMethod
+iterateAlloc opts nl il limit newinst allocnodes ixes cstats =
+ if not $ algCapacity opts
+ then iterateAllocSmallStep opts nl il limit newinst allocnodes ixes cstats
+ else let bigstepsize = 20
+ (limit', newlimit) = maybe (Just bigstepsize, Nothing)
+ (Just . min bigstepsize
+ &&& Just . max 0 . flip (-) bigstepsize)
+ limit
+ opts' = opts { algCapacity = False }
+ in case iterateAllocSmallStep opts' nl il limit'
+ newinst allocnodes ixes cstats of
+ Bad s -> Bad s
+ Ok res@(_, nl', il', ixes', cstats') | redundant nl' il' ->
+ if newlimit == Just 0 || length ixes' == length ixes
+ then return res
+ else iterateAlloc opts nl' il' newlimit newinst allocnodes
+ ixes' cstats'
+ _ -> iterateAllocSmallStep opts nl il limit newinst allocnodes
+ ixes cstats
+
-- | Predicate whether shrinking a single resource can lead to a valid
-- allocation.
sufficesShrinking :: (Instance.Instance -> AllocSolution) -> Instance.Instance
--
2.4.3.573.g4eafbef
LGTM
