module Ganeti.HTools.Cluster
(
-- * Types
- NodeList
- , InstanceList
- , NameList
+ NameList
, Placement
, Solution(..)
, Table(..)
, Removal
, Score
+ , IMove(..)
-- * Generic functions
, totalResources
-- * First phase functions
, formatCmds
, printNodes
-- * Balacing functions
+ , applyMove
, checkMove
, compCV
, printStats
- -- * Loading functions
- , loadData
- , checkData
+ -- * IAllocator functions
+ , allocateOnSingle
+ , allocateOnPair
) where
import Data.List
import qualified Ganeti.HTools.Container as Container
import qualified Ganeti.HTools.Instance as Instance
import qualified Ganeti.HTools.Node as Node
+import Ganeti.HTools.Types
import Ganeti.HTools.Utils
-type NodeList = Container.Container Node.Node
-type InstanceList = Container.Container Instance.Instance
--- | The type used to hold idx-to-name mappings
-type NameList = [(Int, String)]
-- | A separate name for the cluster score type
type Score = Double
-- | The description of an instance placement.
-type Placement = (Int, Int, Int, Score)
+type Placement = (Idx, Ndx, Ndx, Score)
{- | A cluster solution described as the solution delta and the list
of placements.
_ -> -1
-- | A removal set.
-data Removal = Removal NodeList [Instance.Instance]
+data Removal = Removal Node.List [Instance.Instance]
-- | An instance move definition
data IMove = Failover -- ^ Failover the instance (f)
- | ReplacePrimary Int -- ^ Replace primary (f, r:np, f)
- | ReplaceSecondary Int -- ^ Replace secondary (r:ns)
- | ReplaceAndFailover Int -- ^ Replace secondary, failover (r:np, f)
- | FailoverAndReplace Int -- ^ Failover, replace secondary (f, r:ns)
+ | ReplacePrimary Ndx -- ^ Replace primary (f, r:np, f)
+ | ReplaceSecondary Ndx -- ^ Replace secondary (r:ns)
+ | ReplaceAndFailover Ndx -- ^ Replace secondary, failover (r:np, f)
+ | FailoverAndReplace Ndx -- ^ Failover, replace secondary (f, r:ns)
deriving (Show)
-- | The complete state for the balancing solution
-data Table = Table NodeList InstanceList Score [Placement]
+data Table = Table Node.List Instance.List Score [Placement]
deriving (Show)
-- General functions
verifyN1 nl = filter Node.failN1 nl
{-| Add an instance and return the new node and instance maps. -}
-addInstance :: NodeList -> Instance.Instance ->
- Node.Node -> Node.Node -> Maybe NodeList
+addInstance :: Node.List -> Instance.Instance ->
+ Node.Node -> Node.Node -> Maybe Node.List
addInstance nl idata pri sec =
let pdx = Node.idx pri
sdx = Node.idx sec
return new_nl
-- | Remove an instance and return the new node and instance maps.
-removeInstance :: NodeList -> Instance.Instance -> NodeList
+removeInstance :: Node.List -> Instance.Instance -> Node.List
removeInstance nl idata =
let pnode = Instance.pnode idata
snode = Instance.snode idata
new_nl
-- | Remove an instance and return the new node map.
-removeInstances :: NodeList -> [Instance.Instance] -> NodeList
+removeInstances :: Node.List -> [Instance.Instance] -> Node.List
removeInstances = foldl' removeInstance
-- | Compute the total free disk and memory in the cluster.
their new nodes.
-}
-applySolution :: NodeList -> InstanceList -> [Placement] -> NodeList
+applySolution :: Node.List -> Instance.List -> [Placement] -> Node.List
applySolution nl il sol =
let odxes = map (\ (a, b, c, _) -> (Container.find a il,
Node.idx (Container.find b nl),
those nodes.
-}
-computeBadItems :: NodeList -> InstanceList ->
+computeBadItems :: Node.List -> Instance.List ->
([Node.Node], [Instance.Instance])
computeBadItems nl il =
let bad_nodes = verifyN1 $ filter (not . Node.offline) $ Container.elems nl
placement can make this shortcut.
-}
-checkRemoval :: NodeList -> [Instance.Instance] -> Maybe Removal
+checkRemoval :: Node.List -> [Instance.Instance] -> Maybe Removal
checkRemoval nl victims =
let nx = removeInstances nl victims
failN1 = verifyN1Check (Container.elems nx)
-- | Computes the removals list for a given depth
-computeRemovals :: NodeList
+computeRemovals :: Node.List
-> [Instance.Instance]
-> Int
-> [Maybe Removal]
-- Second phase functions
-- | Single-node relocation cost
-nodeDelta :: Int -> Int -> Int -> Int
+nodeDelta :: Ndx -> Ndx -> Ndx -> Int
nodeDelta i p s =
if i == p || i == s then
0
solution by recursing until all target instances are placed.
-}
-checkPlacement :: NodeList -- ^ The current node list
+checkPlacement :: Node.List -- ^ The current node list
-> [Instance.Instance] -- ^ List of instances still to place
-> [Placement] -- ^ Partial solution until now
-> Int -- ^ The delta of the partial solution
) prev_sol nodes
-- | Apply a move
-applyMove :: NodeList -> Instance.Instance
- -> IMove -> (Maybe NodeList, Instance.Instance, Int, Int)
+applyMove :: Node.List -> Instance.Instance
+ -> IMove -> (Maybe Node.List, Instance.Instance, Ndx, Ndx)
-- Failover (f)
applyMove nl inst Failover =
let old_pdx = Instance.pnode inst
Container.addTwo old_sdx new_p old_pdx int_p nl
in (new_nl, Instance.setBoth inst old_sdx new_sdx, old_sdx, new_sdx)
+allocateOnSingle :: Node.List -> Instance.Instance -> Node.Node
+ -> (Maybe Node.List, Instance.Instance)
+allocateOnSingle nl inst p =
+ let new_pdx = Node.idx p
+ new_nl = Node.addPri p inst >>= \new_p ->
+ return $ Container.add new_pdx new_p nl
+ in (new_nl, Instance.setBoth inst new_pdx Node.noSecondary)
+
+allocateOnPair :: Node.List -> Instance.Instance -> Node.Node -> Node.Node
+ -> (Maybe Node.List, Instance.Instance)
+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
+ return $ Container.addTwo new_pdx new_p new_sdx new_s nl
+ in (new_nl, Instance.setBoth inst new_pdx new_sdx)
+
checkSingleStep :: Table -- ^ The original table
-> Instance.Instance -- ^ The instance to move
-> Table -- ^ The current best table
-- | Given the status of the current secondary as a valid new node
-- and the current candidate target node,
-- generate the possible moves for a instance.
-possibleMoves :: Bool -> Int -> [IMove]
+possibleMoves :: Bool -> Ndx -> [IMove]
possibleMoves True tdx =
[ReplaceSecondary tdx,
ReplaceAndFailover tdx,
ReplaceAndFailover tdx]
-- | Compute the best move for a given instance.
-checkInstanceMove :: [Int] -- Allowed target node indices
+checkInstanceMove :: [Ndx] -- Allowed target node indices
-> Table -- Original table
-> Instance.Instance -- Instance to move
-> Table -- Best new table for this instance
foldl' (checkSingleStep ini_tbl target) aft_failover all_moves
-- | Compute the best next move.
-checkMove :: [Int] -- ^ Allowed target node indices
+checkMove :: [Ndx] -- ^ Allowed target node indices
-> Table -- ^ The current solution
-> [Instance.Instance] -- ^ List of instances still to move
-> Table -- ^ The new solution
-- iterate over all instances, computing the best move
best_tbl =
foldl'
- (\ step_tbl elem -> compareTables step_tbl $
- checkInstanceMove nodes_idx ini_tbl elem)
+ (\ step_tbl elem ->
+ if Instance.snode elem == Node.noSecondary then step_tbl
+ else compareTables step_tbl $
+ checkInstanceMove nodes_idx ini_tbl elem)
ini_tbl victims
Table _ _ _ best_plc = best_tbl
in
solutionFromRemovals. In case we have no solution, we return Nothing.
-}
-computeSolution :: NodeList -- ^ The original node data
+computeSolution :: Node.List -- ^ The original node data
-> [Instance.Instance] -- ^ The list of /bad/ instances
-> Int -- ^ The /depth/ of removals
-> Int -- ^ Maximum number of removals to process
printf "replace-disks -n %s %s" d i])
{-| Converts a placement to string format -}
-printSolutionLine :: InstanceList
- -> NameList
- -> NameList
- -> Int
- -> Int
- -> Placement
- -> Int
- -> (String, [String])
-printSolutionLine il ktn kti nmlen imlen plc pos =
+printSolutionLine :: Node.List
+ -> Instance.List
+ -> Int
+ -> Int
+ -> Placement
+ -> Int
+ -> (String, [String])
+printSolutionLine nl il nmlen imlen plc pos =
let
pmlen = (2*nmlen + 1)
(i, p, s, c) = plc
inst = Container.find i il
- inam = fromJust $ lookup (Instance.idx inst) kti
- npri = fromJust $ lookup p ktn
- nsec = fromJust $ lookup s ktn
- opri = fromJust $ lookup (Instance.pnode inst) ktn
- osec = fromJust $ lookup (Instance.snode inst) ktn
+ inam = Instance.name inst
+ npri = Container.nameOf nl p
+ nsec = Container.nameOf nl s
+ opri = Container.nameOf nl $ Instance.pnode inst
+ osec = Container.nameOf nl $ Instance.snode inst
(moves, cmds) = computeMoves inam opri osec npri nsec
ostr = (printf "%s:%s" opri osec)::String
nstr = (printf "%s:%s" npri nsec)::String
zip [1..] cmd_strs
{-| Converts a solution to string format -}
-printSolution :: InstanceList
- -> NameList
- -> NameList
+printSolution :: Node.List
+ -> Instance.List
-> [Placement]
-> ([String], [[String]])
-printSolution il ktn kti sol =
+printSolution nl il sol =
let
- mlen_fn = maximum . (map length) . snd . unzip
- imlen = mlen_fn kti
- nmlen = mlen_fn ktn
+ nmlen = Container.maxNameLen nl
+ imlen = Container.maxNameLen il
in
- unzip $ map (uncurry $ printSolutionLine il ktn kti nmlen imlen) $
+ unzip $ map (uncurry $ printSolutionLine nl il nmlen imlen) $
zip sol [1..]
-- | Print the node list.
-printNodes :: NameList -> NodeList -> String
-printNodes ktn nl =
+printNodes :: Node.List -> String
+printNodes nl =
let snl = sortBy (compare `on` Node.idx) (Container.elems nl)
- snl' = map (\ n -> ((fromJust $ lookup (Node.idx n) ktn), n)) snl
- m_name = maximum . (map length) . fst . unzip $ snl'
+ m_name = maximum . map (length . Node.name) $ snl
helper = Node.list m_name
header = printf
"%2s %-*s %5s %5s %5s %5s %5s %5s %5s %5s %3s %3s %7s %7s"
"t_mem" "n_mem" "i_mem" "x_mem" "f_mem" "r_mem"
"t_dsk" "f_dsk"
"pri" "sec" "p_fmem" "p_fdsk"
- in unlines $ (header:map (uncurry helper) snl')
+ in unlines $ (header:map helper snl)
-- | Compute the mem and disk covariance.
-compDetailedCV :: NodeList -> (Double, Double, Double, Double, Double)
+compDetailedCV :: Node.List -> (Double, Double, Double, Double, Double)
compDetailedCV nl =
let
all_nodes = Container.elems nl
in (mem_cv, dsk_cv, n1_score, res_cv, off_score)
-- | Compute the 'total' variance.
-compCV :: NodeList -> Double
+compCV :: Node.List -> Double
compCV nl =
let (mem_cv, dsk_cv, n1_score, res_cv, off_score) = compDetailedCV nl
in mem_cv + dsk_cv + n1_score + res_cv + off_score
-printStats :: NodeList -> String
+printStats :: Node.List -> String
printStats nl =
let (mem_cv, dsk_cv, n1_score, res_cv, off_score) = compDetailedCV nl
in printf "f_mem=%.8f, r_mem=%.8f, f_dsk=%.8f, n1=%.3f, uf=%.3f"
mem_cv res_cv dsk_cv n1_score off_score
-
--- Balancing functions
-
--- Loading functions
-
-{- | Convert newline and delimiter-separated text.
-
-This function converts a text in tabular format as generated by
-@gnt-instance list@ and @gnt-node list@ to a list of objects using a
-supplied conversion function.
-
--}
-loadTabular :: (Monad m) => String -> ([String] -> m (String, a))
- -> (a -> Int -> a) -> m ([(String, Int)], [(Int, a)])
-loadTabular text_data convert_fn set_fn = do
- let lines_data = lines text_data
- rows = map (sepSplit '|') lines_data
- kerows <- mapM convert_fn rows
- let idxrows = map (\ (idx, (k, v)) -> ((k, idx), (idx, set_fn v idx)))
- (zip [0..] kerows)
- return $ unzip idxrows
-
--- | For each instance, add its index to its primary and secondary nodes
-fixNodes :: [(Int, Node.Node)]
- -> [(Int, Instance.Instance)]
- -> [(Int, Node.Node)]
-fixNodes nl il =
- foldl' (\accu (idx, inst) ->
- let
- assocEqual = (\ (i, _) (j, _) -> i == j)
- pdx = Instance.pnode inst
- sdx = Instance.snode inst
- pold = fromJust $ lookup pdx accu
- sold = fromJust $ lookup sdx accu
- pnew = Node.setPri pold idx
- snew = Node.setSec sold idx
- ac1 = deleteBy assocEqual (pdx, pold) accu
- ac2 = deleteBy assocEqual (sdx, sold) ac1
- ac3 = (pdx, pnew):(sdx, snew):ac2
- in ac3) nl il
-
--- | Compute the longest common suffix of a NameList list that
--- | starts with a dot
-longestDomain :: NameList -> String
-longestDomain [] = ""
-longestDomain ((_,x):xs) =
- let
- onlyStrings = snd $ unzip xs
- in
- foldr (\ suffix accu -> if all (isSuffixOf suffix) onlyStrings
- then suffix
- else accu)
- "" $ filter (isPrefixOf ".") (tails x)
-
--- | Remove tails from the (Int, String) lists
-stripSuffix :: String -> NameList -> NameList
-stripSuffix suffix lst =
- let sflen = length suffix in
- map (\ (key, name) -> (key, take ((length name) - sflen) name)) lst
-
--- | Safe 'read' function returning data encapsulated in a Result
-tryRead :: (Monad m, Read a) => String -> String -> m a
-tryRead name s =
- let sols = readsPrec 0 s
- in case sols of
- (v, ""):[] -> return v
- (_, e):[] -> fail $ name ++ ": leftover characters when parsing '"
- ++ s ++ "': '" ++ e ++ "'"
- _ -> fail $ name ++ ": cannot parse string '" ++ s ++ "'"
-
--- | Lookups a node into an assoc list
-lookupNode :: (Monad m) => String -> String -> [(String, Int)] -> m Int
-lookupNode node inst ktn =
- case lookup node ktn of
- Nothing -> fail $ "Unknown node " ++ node ++ " for instance " ++ inst
- Just idx -> return idx
-
-loadNode :: (Monad m) => [String] -> m (String, Node.Node)
-loadNode (name:tm:nm:fm:td:fd:fo:[]) = do
- new_node <-
- if any (== "?") [tm,nm,fm,td,fd] || fo == "Y" then
- return $ Node.create 0 0 0 0 0 True
- else do
- vtm <- tryRead name tm
- vnm <- tryRead name nm
- vfm <- tryRead name fm
- vtd <- tryRead name td
- vfd <- tryRead name fd
- return $ Node.create vtm vnm vfm vtd vfd False
- return (name, new_node)
-loadNode s = fail $ "Invalid/incomplete node data: '" ++ (show s) ++ "'"
-
-loadInst :: (Monad m) =>
- [(String, Int)] -> [String] -> m (String, Instance.Instance)
-loadInst ktn (name:mem:dsk:status:pnode:snode:[]) = do
- pidx <- lookupNode pnode name ktn
- sidx <- lookupNode snode name ktn
- vmem <- tryRead name mem
- vdsk <- tryRead name dsk
- when (sidx == pidx) $ fail $ "Instance " ++ name ++
- " has same primary and secondary node - " ++ pnode
- let newinst = Instance.create vmem vdsk status pidx sidx
- return (name, newinst)
-loadInst _ s = fail $ "Invalid/incomplete instance data: '" ++ (show s) ++ "'"
-
-{-| Initializer function that loads the data from a node and list file
- and massages it into the correct format. -}
-loadData :: String -- ^ Node data in text format
- -> String -- ^ Instance data in text format
- -> Result (Container.Container Node.Node,
- Container.Container Instance.Instance,
- String, NameList, NameList)
-loadData ndata idata = do
- {- node file: name t_mem n_mem f_mem t_disk f_disk -}
- (ktn, nl) <- loadTabular ndata loadNode Node.setIdx
- {- instance file: name mem disk status pnode snode -}
- (kti, il) <- loadTabular idata (loadInst ktn) Instance.setIdx
- let
- nl2 = fixNodes nl il
- il3 = Container.fromAssocList il
- nl3 = Container.fromAssocList
- (map (\ (k, v) -> (k, Node.buildPeers v il3 (length nl2))) nl2)
- xtn = swapPairs ktn
- xti = swapPairs kti
- common_suffix = longestDomain (xti ++ xtn)
- stn = stripSuffix common_suffix xtn
- sti = stripSuffix common_suffix xti
- return (nl3, il3, common_suffix, stn, sti)
-
--- | Compute the amount of memory used by primary instances on a node.
-nodeImem :: Node.Node -> InstanceList -> Int
-nodeImem node il =
- let rfind = flip Container.find $ il
- in sum . map Instance.mem .
- map rfind $ Node.plist node
-
--- | Compute the amount of disk used by instances on a node (either primary
--- or secondary).
-nodeIdsk :: Node.Node -> InstanceList -> Int
-nodeIdsk node il =
- let rfind = flip Container.find $ il
- in sum . map Instance.dsk .
- map rfind $ (Node.plist node) ++ (Node.slist node)
-
-
--- | Check cluster data for consistency
-checkData :: NodeList -> InstanceList -> NameList -> NameList
- -> ([String], NodeList)
-checkData nl il ktn _ =
- Container.mapAccum
- (\ msgs node ->
- let nname = fromJust $ lookup (Node.idx node) ktn
- nilst = map (flip Container.find $ il) (Node.plist node)
- dilst = filter (not . Instance.running) nilst
- adj_mem = sum . map Instance.mem $ dilst
- delta_mem = (truncate $ Node.t_mem node)
- - (Node.n_mem node)
- - (Node.f_mem node)
- - (nodeImem node il)
- + adj_mem
- delta_dsk = (truncate $ Node.t_dsk node)
- - (Node.f_dsk node)
- - (nodeIdsk node il)
- newn = Node.setFmem (Node.setXmem node delta_mem)
- (Node.f_mem node - adj_mem)
- umsg1 = if delta_mem > 512 || delta_dsk > 1024
- then [printf "node %s is missing %d MB ram \
- \and %d GB disk"
- nname delta_mem (delta_dsk `div` 1024)]
- else []
- in (msgs ++ umsg1, newn)
- ) [] nl