{-
-Copyright (C) 2009 Google Inc.
+Copyright (C) 2009, 2010 Google Inc.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
module Ganeti.HTools.Cluster
(
-- * Types
- AllocSolution
+ AllocSolution(..)
, Table(..)
, CStats(..)
, AllocStats
, doNextBalance
, tryBalance
, compCV
+ , compDetailedCV
, printStats
, iMoveToJob
-- * IAllocator functions
, tryAlloc
+ , tryMGAlloc
, tryReloc
, tryEvac
, collapseFailures
-- * Allocation functions
, iterateAlloc
, tieredAlloc
+ , tieredSpecMap
+ -- * Node group functions
+ , instanceGroup
+ , findSplitInstances
+ , splitCluster
) where
+import Data.Function (on)
import Data.List
import Data.Ord (comparing)
import Text.Printf (printf)
import qualified Ganeti.HTools.Container as Container
import qualified Ganeti.HTools.Instance as Instance
import qualified Ganeti.HTools.Node as Node
+import qualified Ganeti.HTools.Group as Group
import Ganeti.HTools.Types
import Ganeti.HTools.Utils
import qualified Ganeti.OpCodes as OpCodes
-- * Types
-- | Allocation\/relocation solution.
-type AllocSolution = ([FailMode], Int, [(Score, Node.AllocElement)])
+data AllocSolution = AllocSolution
+ { asFailures :: [FailMode] -- ^ Failure counts
+ , asAllocs :: Int -- ^ Good allocation count
+ , asSolutions :: [Node.AllocElement] -- ^ The actual result, length
+ -- of the list depends on the
+ -- allocation/relocation mode
+ , asLog :: [String] -- ^ A list of informational messages
+ }
+
+-- | The empty solution we start with when computing allocations
+emptySolution :: AllocSolution
+emptySolution = AllocSolution { asFailures = [], asAllocs = 0
+ , asSolutions = [], asLog = [] }
-- | The complete state for the balancing solution
data Table = Table Node.List Instance.List Score [Placement]
- deriving (Show)
+ deriving (Show, Read)
data CStats = CStats { csFmem :: Int -- ^ Cluster free mem
, csFdsk :: Int -- ^ Cluster free disk
, csScore :: Score -- ^ The cluster score
, csNinst :: Int -- ^ The total number of instances
}
- deriving (Show)
+ deriving (Show, Read)
-- | Currently used, possibly to allocate, unallocable
type AllocStats = (RSpec, RSpec, RSpec)
, (1, "mem_load_cv")
, (1, "disk_load_cv")
, (1, "net_load_cv")
- , (1, "pri_tags_score")
+ , (2, "pri_tags_score")
]
detailedCVWeights :: [Double]
mem_l = map Node.pMem nodes
dsk_l = map Node.pDsk nodes
-- metric: memory covariance
- mem_cv = varianceCoeff mem_l
+ mem_cv = stdDev mem_l
-- metric: disk covariance
- dsk_cv = varianceCoeff dsk_l
+ dsk_cv = stdDev dsk_l
-- metric: count of instances living on N1 failing nodes
n1_score = fromIntegral . sum . map (\n -> length (Node.sList n) +
length (Node.pList n)) .
filter Node.failN1 $ nodes :: Double
res_l = map Node.pRem nodes
-- metric: reserved memory covariance
- res_cv = varianceCoeff res_l
+ res_cv = stdDev res_l
-- offline instances metrics
offline_ipri = sum . map (length . Node.pList) $ offline
offline_isec = sum . map (length . Node.sList) $ offline
off_pri_score = fromIntegral offline_ipri::Double
cpu_l = map Node.pCpu nodes
-- metric: covariance of vcpu/pcpu ratio
- cpu_cv = varianceCoeff cpu_l
+ cpu_cv = stdDev cpu_l
-- metrics: covariance of cpu, memory, disk and network load
(c_load, m_load, d_load, n_load) = unzip4 $
map (\n ->
pri_tags_inst = sum $ map Node.conflictingPrimaries nodes
pri_tags_score = fromIntegral pri_tags_inst::Double
in [ mem_cv, dsk_cv, n1_score, res_cv, off_score, off_pri_score, cpu_cv
- , varianceCoeff c_load, varianceCoeff m_load
- , varianceCoeff d_load, varianceCoeff n_load
+ , stdDev c_load, stdDev m_load , stdDev d_load, stdDev n_load
, pri_tags_score ]
-- | Compute the /total/ variance.
allocateOnSingle nl inst p =
let new_pdx = Node.idx p
new_inst = Instance.setBoth inst new_pdx Node.noSecondary
- new_nl = Node.addPri p inst >>= \new_p ->
- return (Container.add new_pdx new_p nl, new_inst, [new_p])
- in new_nl
+ in Node.addPri p inst >>= \new_p -> do
+ let new_nl = Container.add new_pdx new_p nl
+ new_score = compCV nl
+ return (new_nl, new_inst, [new_p], new_score)
-- | Tries to allocate an instance on a given pair of nodes.
allocateOnPair :: Node.List -> Instance.Instance -> Node.Node -> Node.Node
allocateOnPair nl inst tgt_p tgt_s =
let new_pdx = Node.idx tgt_p
new_sdx = Node.idx tgt_s
- new_nl = do -- Maybe monad
- new_p <- Node.addPri tgt_p inst
- new_s <- Node.addSec tgt_s inst new_pdx
- let new_inst = Instance.setBoth inst new_pdx new_sdx
- return (Container.addTwo new_pdx new_p new_sdx new_s nl, new_inst,
- [new_p, new_s])
- in new_nl
+ in do
+ new_p <- Node.addPri tgt_p inst
+ new_s <- Node.addSec tgt_s inst new_pdx
+ let new_inst = Instance.setBoth inst new_pdx new_sdx
+ new_nl = Container.addTwo new_pdx new_p new_sdx new_s nl
+ return (new_nl, new_inst, [new_p, new_s], compCV new_nl)
-- | Tries to perform an instance move and returns the best table
-- between the original one and the new one.
tryBalance :: Table -- ^ The starting table
-> Bool -- ^ Allow disk moves
-> Bool -- ^ Only evacuate moves
+ -> Score -- ^ Min gain threshold
+ -> Score -- ^ Min gain
-> Maybe Table -- ^ The resulting table and commands
-tryBalance ini_tbl disk_moves evac_mode =
+tryBalance ini_tbl disk_moves evac_mode mg_limit min_gain =
let Table ini_nl ini_il ini_cv _ = ini_tbl
all_inst = Container.elems ini_il
all_inst' = if evac_mode
fin_tbl = checkMove node_idx disk_moves ini_tbl reloc_inst
(Table _ _ fin_cv _) = fin_tbl
in
- if fin_cv < ini_cv
+ if fin_cv < ini_cv && (ini_cv > mg_limit || ini_cv - fin_cv >= min_gain)
then Just fin_tbl -- this round made success, return the new table
else Nothing
-- | Update current Allocation solution and failure stats with new
-- elements
concatAllocs :: AllocSolution -> OpResult Node.AllocElement -> AllocSolution
-concatAllocs (flst, cntok, sols) (OpFail reason) = (reason:flst, cntok, sols)
+concatAllocs as (OpFail reason) = as { asFailures = reason : asFailures as }
-concatAllocs (flst, cntok, osols) (OpGood ns@(nl, _, _)) =
- let nscore = compCV nl
- -- Choose the old or new solution, based on the cluster score
+concatAllocs as (OpGood ns@(_, _, _, nscore)) =
+ let -- Choose the old or new solution, based on the cluster score
+ cntok = asAllocs as
+ osols = asSolutions as
nsols = case osols of
- [] -> [(nscore, ns)]
- (oscore, _):[] ->
+ [] -> [ns]
+ (_, _, _, oscore):[] ->
if oscore < nscore
then osols
- else [(nscore, ns)]
+ else [ns]
-- FIXME: here we simply concat to lists with more
-- than one element; we should instead abort, since
-- this is not a valid usage of this function
- xs -> (nscore, ns):xs
+ xs -> ns:xs
nsuc = cntok + 1
-- Note: we force evaluation of nsols here in order to keep the
-- memory profile low - we know that we will need nsols for sure
-- in the next cycle, so we force evaluation of nsols, since the
-- foldl' in the caller will only evaluate the tuple, but not the
-- elements of the tuple
- in nsols `seq` nsuc `seq` (flst, nsuc, nsols)
+ in nsols `seq` nsuc `seq` as { asAllocs = nsuc, asSolutions = nsols }
+
+-- | Given a solution, generates a reasonable description for it
+describeSolution :: AllocSolution -> String
+describeSolution as =
+ let fcnt = asFailures as
+ sols = asSolutions as
+ freasons =
+ intercalate ", " . map (\(a, b) -> printf "%s: %d" (show a) b) .
+ filter ((> 0) . snd) . collapseFailures $ fcnt
+ in if null sols
+ then "No valid allocation solutions, failure reasons: " ++
+ (if null fcnt
+ then "unknown reasons"
+ else freasons)
+ else let (_, _, nodes, cv) = head sols
+ in printf ("score: %.8f, successes %d, failures %d (%s)" ++
+ " for node(s) %s") cv (asAllocs as) (length fcnt) freasons
+ (intercalate "/" . map Node.name $ nodes)
+
+-- | Annotates a solution with the appropriate string
+annotateSolution :: AllocSolution -> AllocSolution
+annotateSolution as = as { asLog = describeSolution as : asLog as }
-- | Try to allocate an instance on the cluster.
tryAlloc :: (Monad m) =>
ok_pairs = filter (\(x, y) -> Node.idx x /= Node.idx y) all_pairs
sols = foldl' (\cstate (p, s) ->
concatAllocs cstate $ allocateOnPair nl inst p s
- ) ([], 0, []) ok_pairs
- in return sols
+ ) emptySolution ok_pairs
+
+ in if null ok_pairs -- means we have just one node
+ then fail "Not enough online nodes"
+ else return $ annotateSolution sols
tryAlloc nl _ inst 1 =
let all_nodes = getOnline nl
sols = foldl' (\cstate ->
concatAllocs cstate . allocateOnSingle nl inst
- ) ([], 0, []) all_nodes
- in return sols
+ ) emptySolution all_nodes
+ in if null all_nodes
+ then fail "No online nodes"
+ else return $ annotateSolution sols
tryAlloc _ _ _ reqn = fail $ "Unsupported number of allocation \
\destinations required (" ++ show reqn ++
"), only two supported"
--- | Try to allocate an instance on the cluster.
+-- | Given a group/result, describe it as a nice (list of) messages
+solutionDescription :: Group.List -> (Gdx, Result AllocSolution) -> [String]
+solutionDescription gl (groupId, result) =
+ case result of
+ Ok solution -> map (printf "Group %s (%s): %s" gname pol) (asLog solution)
+ Bad message -> [printf "Group %s: error %s" gname message]
+ where grp = Container.find groupId gl
+ gname = Group.name grp
+ pol = apolToString (Group.allocPolicy grp)
+
+-- | From a list of possibly bad and possibly empty solutions, filter
+-- only the groups with a valid result
+filterMGResults :: Group.List
+ -> [(Gdx, Result AllocSolution)]
+ -> [(Gdx, AllocSolution)]
+filterMGResults gl=
+ filter ((/= AllocUnallocable) . Group.allocPolicy .
+ flip Container.find gl . fst) .
+ filter (not . null . asSolutions . snd) .
+ map (\(y, Ok x) -> (y, x)) .
+ filter (isOk . snd)
+
+-- | Sort multigroup results based on policy and score
+sortMGResults :: Group.List
+ -> [(Gdx, AllocSolution)]
+ -> [(Gdx, AllocSolution)]
+sortMGResults gl sols =
+ let extractScore = \(_, _, _, x) -> x
+ solScore (gdx, sol) = (Group.allocPolicy (Container.find gdx gl),
+ (extractScore . head . asSolutions) sol)
+ in sortBy (comparing solScore) sols
+
+-- | Try to allocate an instance on a multi-group cluster.
+tryMGAlloc :: Group.List -- ^ The group list
+ -> Node.List -- ^ The node list
+ -> Instance.List -- ^ The instance list
+ -> Instance.Instance -- ^ The instance to allocate
+ -> Int -- ^ Required number of nodes
+ -> Result AllocSolution -- ^ Possible solution list
+tryMGAlloc mggl mgnl mgil inst cnt =
+ let groups = splitCluster mgnl mgil
+ -- TODO: currently we consider all groups preferred
+ sols = map (\(gid, (nl, il)) ->
+ (gid, tryAlloc nl il inst cnt)) groups::
+ [(Gdx, Result AllocSolution)]
+ all_msgs = concatMap (solutionDescription mggl) sols
+ goodSols = filterMGResults mggl sols
+ sortedSols = sortMGResults mggl goodSols
+ in if null sortedSols
+ then Bad $ intercalate ", " all_msgs
+ else let (final_group, final_sol) = head sortedSols
+ final_name = Group.name $ Container.find final_group mggl
+ selmsg = "Selected group: " ++ final_name
+ in Ok $ final_sol { asLog = selmsg:all_msgs }
+
+-- | Try to relocate an instance on the cluster.
tryReloc :: (Monad m) =>
Node.List -- ^ The node list
-> Instance.List -- ^ The instance list
let em = do
(mnl, i, _, _) <-
applyMove nl inst (ReplaceSecondary x)
- return (mnl, i, [Container.find x mnl])
+ return (mnl, i, [Container.find x mnl],
+ compCV mnl)
in concatAllocs cstate em
- ) ([], 0, []) valid_idxes
+ ) emptySolution valid_idxes
in return sols1
tryReloc _ _ _ reqn _ = fail $ "Unsupported number of relocation \
let ex_nodes = map (`Container.find` nl) ex_ndx
all_insts = nub . concatMap Node.sList $ ex_nodes
in do
- (_, sol) <- foldM (\(nl', (_, _, rsols)) idx -> do
- -- FIXME: hardcoded one node here
- (fm, cs, aes) <- tryReloc nl' il idx 1 ex_ndx
- case aes of
- csol@(_, (nl'', _, _)):_ ->
- return (nl'', (fm, cs, csol:rsols))
- _ -> fail $ "Can't evacuate instance " ++
- show idx
- ) (nl, ([], 0, [])) all_insts
- return sol
+ (_, sol) <- foldM (\(nl', old_as) idx -> do
+ -- FIXME: hardcoded one node here
+ -- (fm, cs, aes)
+ new_as <- tryReloc nl' il idx 1 ex_ndx
+ case asSolutions new_as of
+ csol@(nl'', _, _, _):_ ->
+ -- an individual relocation succeeded,
+ -- we kind of compose the data from
+ -- the two solutions
+ return (nl'',
+ new_as { asSolutions =
+ csol:asSolutions old_as })
+ -- this relocation failed, so we fail
+ -- the entire evac
+ _ -> fail $ "Can't evacuate instance " ++
+ Instance.name (Container.find idx il) ++
+ ": " ++ describeSolution new_as
+ ) (nl, emptySolution) all_insts
+ return $ annotateSolution sol
-- | Recursively place instances on the cluster until we're out of space
iterateAlloc :: Node.List
-> Instance.Instance
-> Int
-> [Instance.Instance]
- -> Result (FailStats, Node.List, [Instance.Instance])
+ -> Result (FailStats, Node.List, Instance.List,
+ [Instance.Instance])
iterateAlloc nl il newinst nreq ixes =
let depth = length ixes
newname = printf "new-%d" depth::String
newi2 = Instance.setIdx (Instance.setName newinst newname) newidx
in case tryAlloc nl il newi2 nreq of
Bad s -> Bad s
- Ok (errs, _, sols3) ->
+ Ok (AllocSolution { asFailures = errs, asSolutions = sols3 }) ->
case sols3 of
- [] -> Ok (collapseFailures errs, nl, ixes)
- (_, (xnl, xi, _)):[] ->
- iterateAlloc xnl il newinst nreq $! (xi:ixes)
+ [] -> Ok (collapseFailures errs, nl, il, ixes)
+ (xnl, xi, _, _):[] ->
+ iterateAlloc xnl (Container.add newidx xi il)
+ newinst nreq $! (xi:ixes)
_ -> Bad "Internal error: multiple solutions for single\
\ allocation"
+-- | The core of the tiered allocation mode
tieredAlloc :: Node.List
-> Instance.List
-> Instance.Instance
-> Int
-> [Instance.Instance]
- -> Result (FailStats, Node.List, [Instance.Instance])
+ -> Result (FailStats, Node.List, Instance.List,
+ [Instance.Instance])
tieredAlloc nl il newinst nreq ixes =
case iterateAlloc nl il newinst nreq ixes of
Bad s -> Bad s
- Ok (errs, nl', ixes') ->
+ Ok (errs, nl', il', ixes') ->
case Instance.shrinkByType newinst . fst . last $
sortBy (comparing snd) errs of
- Bad _ -> Ok (errs, nl', ixes')
+ Bad _ -> Ok (errs, nl', il', ixes')
Ok newinst' ->
- tieredAlloc nl' il newinst' nreq ixes'
+ tieredAlloc nl' il' newinst' nreq ixes'
+
+-- | Compute the tiered spec string description from a list of
+-- allocated instances.
+tieredSpecMap :: [Instance.Instance]
+ -> [String]
+tieredSpecMap trl_ixes =
+ let fin_trl_ixes = reverse trl_ixes
+ ix_byspec = groupBy ((==) `on` Instance.specOf) fin_trl_ixes
+ spec_map = map (\ixs -> (Instance.specOf $ head ixs, length ixs))
+ ix_byspec
+ in map (\(spec, cnt) -> printf "%d,%d,%d=%d" (rspecMem spec)
+ (rspecDsk spec) (rspecCpu spec) cnt) spec_map
-- * Formatting functions
ReplaceSecondary ns -> [ opR ns ]
ReplaceAndFailover np -> [ opR np, opF ]
FailoverAndReplace ns -> [ opF, opR ns ]
+
+-- * Node group functions
+
+-- | Computes the group of an instance
+instanceGroup :: Node.List -> Instance.Instance -> Result Gdx
+instanceGroup nl i =
+ let sidx = Instance.sNode i
+ pnode = Container.find (Instance.pNode i) nl
+ snode = if sidx == Node.noSecondary
+ then pnode
+ else Container.find sidx nl
+ pgroup = Node.group pnode
+ sgroup = Node.group snode
+ in if pgroup /= sgroup
+ then fail ("Instance placed accross two node groups, primary " ++
+ show pgroup ++ ", secondary " ++ show sgroup)
+ else return pgroup
+
+-- | Compute the list of badly allocated instances (split across node
+-- groups)
+findSplitInstances :: Node.List -> Instance.List -> [Instance.Instance]
+findSplitInstances nl il =
+ filter (not . isOk . instanceGroup nl) (Container.elems il)
+
+-- | Splits a cluster into the component node groups
+splitCluster :: Node.List -> Instance.List ->
+ [(Gdx, (Node.List, Instance.List))]
+splitCluster nl il =
+ let ngroups = Node.computeGroups (Container.elems nl)
+ in map (\(guuid, nodes) ->
+ let nidxs = map Node.idx nodes
+ nodes' = zip nidxs nodes
+ instances = Container.filter ((`elem` nidxs) . Instance.pNode) il
+ in (guuid, (Container.fromAssocList nodes', instances))) ngroups
projects / ganeti-local / blobdiff