Cluster.hs 32 KB
Newer Older
Iustin Pop's avatar
Iustin Pop committed
1
2
3
{-| Implementation of cluster-wide logic.

This module holds all pure cluster-logic; I\/O related functionality
Iustin Pop's avatar
Iustin Pop committed
4
goes into the "Main" module for the individual binaries.
Iustin Pop's avatar
Iustin Pop committed
5
6
7

-}

8
module Ganeti.HTools.Cluster
Iustin Pop's avatar
Iustin Pop committed
9
10
11
12
    (
     -- * Types
     NodeList
    , InstanceList
13
    , NameList
Iustin Pop's avatar
Iustin Pop committed
14
15
16
17
    , Placement
    , Solution(..)
    , Table(..)
    , Removal
Iustin Pop's avatar
Iustin Pop committed
18
    , Score
Iustin Pop's avatar
Iustin Pop committed
19
20
21
22
23
24
25
26
    -- * Generic functions
    , totalResources
    -- * First phase functions
    , computeBadItems
    -- * Second phase functions
    , computeSolution
    , applySolution
    , printSolution
27
    , printSolutionLine
28
    , formatCmds
Iustin Pop's avatar
Iustin Pop committed
29
30
31
32
33
34
35
    , printNodes
    -- * Balacing functions
    , checkMove
    , compCV
    , printStats
    -- * Loading functions
    , loadData
36
    , checkData
Iustin Pop's avatar
Iustin Pop committed
37
38
39
40
41
42
    ) where

import Data.List
import Data.Maybe (isNothing, fromJust)
import Text.Printf (printf)
import Data.Function
43
import Control.Monad
Iustin Pop's avatar
Iustin Pop committed
44

45
46
47
48
import qualified Ganeti.HTools.Container as Container
import qualified Ganeti.HTools.Instance as Instance
import qualified Ganeti.HTools.Node as Node
import Ganeti.HTools.Utils
Iustin Pop's avatar
Iustin Pop committed
49
50
51

type NodeList = Container.Container Node.Node
type InstanceList = Container.Container Instance.Instance
52
53
-- | The type used to hold idx-to-name mappings
type NameList = [(Int, String)]
Iustin Pop's avatar
Iustin Pop committed
54
-- | A separate name for the cluster score type
Iustin Pop's avatar
Iustin Pop committed
55
56
57
type Score = Double

-- | The description of an instance placement.
58
type Placement = (Int, Int, Int, Score)
Iustin Pop's avatar
Iustin Pop committed
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

{- | A cluster solution described as the solution delta and the list
of placements.

-}
data Solution = Solution Int [Placement]
                deriving (Eq, Ord, Show)

-- | Returns the delta of a solution or -1 for Nothing
solutionDelta :: Maybe Solution -> Int
solutionDelta sol = case sol of
                      Just (Solution d _) -> d
                      _ -> -1

-- | A removal set.
data Removal = Removal NodeList [Instance.Instance]

-- | An instance move definition
Iustin Pop's avatar
Iustin Pop committed
77
data IMove = Failover                -- ^ Failover the instance (f)
Iustin Pop's avatar
Iustin Pop committed
78
79
80
81
           | 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)
Iustin Pop's avatar
Iustin Pop committed
82
83
84
85
86
87
             deriving (Show)

-- | The complete state for the balancing solution
data Table = Table NodeList InstanceList Score [Placement]
             deriving (Show)

88
89
90
91
-- | Constant node index for a non-moveable instance
noSecondary :: Int
noSecondary = -1

Iustin Pop's avatar
Iustin Pop committed
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
-- General functions

-- | Cap the removal list if needed.
capRemovals :: [a] -> Int -> [a]
capRemovals removals max_removals =
    if max_removals > 0 then
        take max_removals removals
    else
        removals

-- | Check if the given node list fails the N+1 check.
verifyN1Check :: [Node.Node] -> Bool
verifyN1Check nl = any Node.failN1 nl

-- | Verifies the N+1 status and return the affected nodes.
verifyN1 :: [Node.Node] -> [Node.Node]
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 nl idata pri sec =
  let pdx = Node.idx pri
      sdx = Node.idx sec
  in do
      pnode <- Node.addPri pri idata
      snode <- Node.addSec sec idata pdx
      new_nl <- return $ Container.addTwo sdx snode
                         pdx pnode nl
      return new_nl

-- | Remove an instance and return the new node and instance maps.
removeInstance :: NodeList -> Instance.Instance -> NodeList
removeInstance nl idata =
  let pnode = Instance.pnode idata
      snode = Instance.snode idata
      pn = Container.find pnode nl
      sn = Container.find snode nl
      new_nl = Container.addTwo
               pnode (Node.removePri pn idata)
               snode (Node.removeSec sn idata) nl in
  new_nl

-- | Remove an instance and return the new node map.
removeInstances :: NodeList -> [Instance.Instance] -> NodeList
removeInstances = foldl' removeInstance

-- | Compute the total free disk and memory in the cluster.
totalResources :: Container.Container Node.Node -> (Int, Int)
totalResources nl =
    foldl'
Iustin Pop's avatar
Iustin Pop committed
143
144
    (\ (mem, dsk) node -> (mem + (Node.f_mem node),
                           dsk + (Node.f_dsk node)))
Iustin Pop's avatar
Iustin Pop committed
145
146
147
148
149
150
151
152
153
154
155
156
157
    (0, 0) (Container.elems nl)

{- | Compute a new version of a cluster given a solution.

This is not used for computing the solutions, but for applying a
(known-good) solution to the original cluster for final display.

It first removes the relocated instances after which it places them on
their new nodes.

 -}
applySolution :: NodeList -> InstanceList -> [Placement] -> NodeList
applySolution nl il sol =
158
159
160
    let odxes = map (\ (a, b, c, _) -> (Container.find a il,
                                        Node.idx (Container.find b nl),
                                        Node.idx (Container.find c nl))
Iustin Pop's avatar
Iustin Pop committed
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
                    ) sol
        idxes = (\ (x, _, _) -> x) (unzip3 odxes)
        nc = removeInstances nl idxes
    in
      foldl' (\ nz (a, b, c) ->
                 let new_p = Container.find b nz
                     new_s = Container.find c nz in
                 fromJust (addInstance nz a new_p new_s)
           ) nc odxes


-- First phase functions

{- | Given a list 1,2,3..n build a list of pairs [(1, [2..n]), (2,
    [3..n]), ...]

-}
genParts :: [a] -> Int -> [(a, [a])]
genParts l count =
    case l of
      [] -> []
      x:xs ->
          if length l < count then
              []
          else
              (x, xs) : (genParts xs count)

-- | Generates combinations of count items from the names list.
genNames :: Int -> [b] -> [[b]]
genNames count1 names1 =
  let aux_fn count names current =
          case count of
            0 -> [current]
            _ ->
                concatMap
                (\ (x, xs) -> aux_fn (count - 1) xs (x:current))
                (genParts names count)
  in
    aux_fn count1 names1 []

{- | Computes the pair of bad nodes and instances.

The bad node list is computed via a simple 'verifyN1' check, and the
bad instance list is the list of primary and secondary instances of
those nodes.

-}
computeBadItems :: NodeList -> InstanceList ->
                   ([Node.Node], [Instance.Instance])
computeBadItems nl il =
211
  let bad_nodes = verifyN1 $ filter (not . Node.offline) $ Container.elems nl
Iustin Pop's avatar
Iustin Pop committed
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
      bad_instances = map (\idx -> Container.find idx il) $
                      sort $ nub $ concat $
                      map (\ n -> (Node.slist n) ++ (Node.plist n)) bad_nodes
  in
    (bad_nodes, bad_instances)


{- | Checks if removal of instances results in N+1 pass.

Note: the check removal cannot optimize by scanning only the affected
nodes, since the cluster is known to be not healthy; only the check
placement can make this shortcut.

-}
checkRemoval :: NodeList -> [Instance.Instance] -> Maybe Removal
checkRemoval nl victims =
  let nx = removeInstances nl victims
      failN1 = verifyN1Check (Container.elems nx)
  in
    if failN1 then
      Nothing
    else
      Just $ Removal nx victims


-- | Computes the removals list for a given depth
238
computeRemovals :: NodeList
Iustin Pop's avatar
Iustin Pop committed
239
240
                 -> [Instance.Instance]
                 -> Int
241
                 -> [Maybe Removal]
Iustin Pop's avatar
Iustin Pop committed
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
computeRemovals nl bad_instances depth =
    map (checkRemoval nl) $ genNames depth bad_instances

-- Second phase functions

-- | Single-node relocation cost
nodeDelta :: Int -> Int -> Int -> Int
nodeDelta i p s =
    if i == p || i == s then
        0
    else
        1

{-| Compute best solution.

    This function compares two solutions, choosing the minimum valid
    solution.
-}
compareSolutions :: Maybe Solution -> Maybe Solution -> Maybe Solution
compareSolutions a b = case (a, b) of
  (Nothing, x) -> x
  (x, Nothing) -> x
  (x, y) -> min x y

-- | Compute best table. Note that the ordering of the arguments is important.
compareTables :: Table -> Table -> Table
compareTables a@(Table _ _ a_cv _) b@(Table _ _ b_cv _ ) =
    if a_cv > b_cv then b else a

-- | Check if a given delta is worse then an existing solution.
tooHighDelta :: Maybe Solution -> Int -> Int -> Bool
tooHighDelta sol new_delta max_delta =
    if new_delta > max_delta && max_delta >=0 then
        True
    else
        case sol of
          Nothing -> False
          Just (Solution old_delta _) -> old_delta <= new_delta

{-| Check if placement of instances still keeps the cluster N+1 compliant.

    This is the workhorse of the allocation algorithm: given the
    current node and instance maps, the list of instances to be
    placed, and the current solution, this will return all possible
    solution by recursing until all target instances are placed.

-}
checkPlacement :: NodeList            -- ^ The current node list
               -> [Instance.Instance] -- ^ List of instances still to place
               -> [Placement]         -- ^ Partial solution until now
               -> Int                 -- ^ The delta of the partial solution
               -> Maybe Solution      -- ^ The previous solution
               -> Int                 -- ^ Abort if the we go above this delta
               -> Maybe Solution      -- ^ The new solution
checkPlacement nl victims current current_delta prev_sol max_delta =
  let target = head victims
      opdx = Instance.pnode target
      osdx = Instance.snode target
      vtail = tail victims
      have_tail = (length vtail) > 0
      nodes = Container.elems nl
303
      iidx = Instance.idx target
Iustin Pop's avatar
Iustin Pop committed
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
  in
    foldl'
    (\ accu_p pri ->
         let
             pri_idx = Node.idx pri
             upri_delta = current_delta + nodeDelta pri_idx opdx osdx
             new_pri = Node.addPri pri target
             fail_delta1 = tooHighDelta accu_p upri_delta max_delta
         in
           if fail_delta1 || isNothing(new_pri) then accu_p
           else let pri_nl = Container.add pri_idx (fromJust new_pri) nl in
                foldl'
                (\ accu sec ->
                     let
                         sec_idx = Node.idx sec
                         upd_delta = upri_delta +
                                     nodeDelta sec_idx opdx osdx
                         fail_delta2 = tooHighDelta accu upd_delta max_delta
                         new_sec = Node.addSec sec target pri_idx
                     in
                       if sec_idx == pri_idx || fail_delta2 ||
                          isNothing new_sec then accu
                       else let
                           nx = Container.add sec_idx (fromJust new_sec) pri_nl
328
329
                           upd_cv = compCV nx
                           plc = (iidx, pri_idx, sec_idx, upd_cv)
Iustin Pop's avatar
Iustin Pop committed
330
331
332
333
334
335
336
337
338
339
340
341
342
343
                           c2 = plc:current
                           result =
                               if have_tail then
                                   checkPlacement nx vtail c2 upd_delta
                                                  accu max_delta
                               else
                                   Just (Solution upd_delta c2)
                      in compareSolutions accu result
                ) accu_p nodes
    ) prev_sol nodes

-- | Apply a move
applyMove :: NodeList -> Instance.Instance
          -> IMove -> (Maybe NodeList, Instance.Instance, Int, Int)
Iustin Pop's avatar
Iustin Pop committed
344
-- Failover (f)
Iustin Pop's avatar
Iustin Pop committed
345
346
347
348
349
350
351
applyMove nl inst Failover =
    let old_pdx = Instance.pnode inst
        old_sdx = Instance.snode inst
        old_p = Container.find old_pdx nl
        old_s = Container.find old_sdx nl
        int_p = Node.removePri old_p inst
        int_s = Node.removeSec old_s inst
352
353
354
355
        new_nl = do -- Maybe monad
          new_p <- Node.addPri int_s inst
          new_s <- Node.addSec int_p inst old_sdx
          return $ Container.addTwo old_pdx new_s old_sdx new_p nl
Iustin Pop's avatar
Iustin Pop committed
356
357
    in (new_nl, Instance.setBoth inst old_sdx old_pdx, old_sdx, old_pdx)

Iustin Pop's avatar
Iustin Pop committed
358
-- Replace the primary (f:, r:np, f)
Iustin Pop's avatar
Iustin Pop committed
359
360
361
362
363
364
365
366
applyMove nl inst (ReplacePrimary new_pdx) =
    let old_pdx = Instance.pnode inst
        old_sdx = Instance.snode inst
        old_p = Container.find old_pdx nl
        old_s = Container.find old_sdx nl
        tgt_n = Container.find new_pdx nl
        int_p = Node.removePri old_p inst
        int_s = Node.removeSec old_s inst
367
368
369
370
371
        new_nl = do -- Maybe monad
          new_p <- Node.addPri tgt_n inst
          new_s <- Node.addSec int_s inst new_pdx
          return $ Container.add new_pdx new_p $
                 Container.addTwo old_pdx int_p old_sdx new_s nl
Iustin Pop's avatar
Iustin Pop committed
372
373
    in (new_nl, Instance.setPri inst new_pdx, new_pdx, old_sdx)

Iustin Pop's avatar
Iustin Pop committed
374
-- Replace the secondary (r:ns)
Iustin Pop's avatar
Iustin Pop committed
375
376
377
378
379
380
applyMove nl inst (ReplaceSecondary new_sdx) =
    let old_pdx = Instance.pnode inst
        old_sdx = Instance.snode inst
        old_s = Container.find old_sdx nl
        tgt_n = Container.find new_sdx nl
        int_s = Node.removeSec old_s inst
381
382
383
        new_nl = Node.addSec tgt_n inst old_pdx >>=
                 \new_s -> return $ Container.addTwo new_sdx
                           new_s old_sdx int_s nl
Iustin Pop's avatar
Iustin Pop committed
384
385
    in (new_nl, Instance.setSec inst new_sdx, old_pdx, new_sdx)

Iustin Pop's avatar
Iustin Pop committed
386
-- Replace the secondary and failover (r:np, f)
Iustin Pop's avatar
Iustin Pop committed
387
388
389
390
391
392
393
394
applyMove nl inst (ReplaceAndFailover new_pdx) =
    let old_pdx = Instance.pnode inst
        old_sdx = Instance.snode inst
        old_p = Container.find old_pdx nl
        old_s = Container.find old_sdx nl
        tgt_n = Container.find new_pdx nl
        int_p = Node.removePri old_p inst
        int_s = Node.removeSec old_s inst
395
396
397
398
399
        new_nl = do -- Maybe monad
          new_p <- Node.addPri tgt_n inst
          new_s <- Node.addSec int_p inst new_pdx
          return $ Container.add new_pdx new_p $
                 Container.addTwo old_pdx new_s old_sdx int_s nl
Iustin Pop's avatar
Iustin Pop committed
400
401
    in (new_nl, Instance.setBoth inst new_pdx old_pdx, new_pdx, old_pdx)

Iustin Pop's avatar
Iustin Pop committed
402
403
404
405
406
407
408
409
410
-- Failver and replace the secondary (f, r:ns)
applyMove nl inst (FailoverAndReplace new_sdx) =
    let old_pdx = Instance.pnode inst
        old_sdx = Instance.snode inst
        old_p = Container.find old_pdx nl
        old_s = Container.find old_sdx nl
        tgt_n = Container.find new_sdx nl
        int_p = Node.removePri old_p inst
        int_s = Node.removeSec old_s inst
411
412
413
414
415
        new_nl = do -- Maybe monad
          new_p <- Node.addPri int_s inst
          new_s <- Node.addSec tgt_n inst old_sdx
          return $ Container.add new_sdx new_s $
                 Container.addTwo old_sdx new_p old_pdx int_p nl
Iustin Pop's avatar
Iustin Pop committed
416
417
    in (new_nl, Instance.setBoth inst old_sdx new_sdx, old_sdx, new_sdx)

Iustin Pop's avatar
Iustin Pop committed
418
419
420
421
422
423
424
425
checkSingleStep :: Table -- ^ The original table
                -> Instance.Instance -- ^ The instance to move
                -> Table -- ^ The current best table
                -> IMove -- ^ The move to apply
                -> Table -- ^ The final best table
checkSingleStep ini_tbl target cur_tbl move =
    let
        Table ini_nl ini_il _ ini_plc = ini_tbl
426
        (tmp_nl, new_inst, pri_idx, sec_idx) = applyMove ini_nl target move
Iustin Pop's avatar
Iustin Pop committed
427
428
429
430
431
432
433
    in
      if isNothing tmp_nl then cur_tbl
      else
          let tgt_idx = Instance.idx target
              upd_nl = fromJust tmp_nl
              upd_cvar = compCV upd_nl
              upd_il = Container.add tgt_idx new_inst ini_il
434
              upd_plc = (tgt_idx, pri_idx, sec_idx, upd_cvar):ini_plc
Iustin Pop's avatar
Iustin Pop committed
435
436
437
438
              upd_tbl = Table upd_nl upd_il upd_cvar upd_plc
          in
            compareTables cur_tbl upd_tbl

439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
-- | 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 True tdx =
    [ReplaceSecondary tdx,
     ReplaceAndFailover tdx,
     ReplacePrimary tdx,
     FailoverAndReplace tdx]

possibleMoves False tdx =
    [ReplaceSecondary tdx,
     ReplaceAndFailover tdx]

-- | Compute the best move for a given instance.
454
455
456
457
458
checkInstanceMove :: [Int]             -- Allowed target node indices
                  -> Table             -- Original table
                  -> Instance.Instance -- Instance to move
                  -> Table             -- Best new table for this instance
checkInstanceMove nodes_idx ini_tbl target =
Iustin Pop's avatar
Iustin Pop committed
459
460
461
    let
        opdx = Instance.pnode target
        osdx = Instance.snode target
462
        nodes = filter (\idx -> idx /= opdx && idx /= osdx) nodes_idx
463
464
465
466
467
        use_secondary = elem osdx nodes_idx
        aft_failover = if use_secondary -- if allowed to failover
                       then checkSingleStep ini_tbl target ini_tbl Failover
                       else ini_tbl
        all_moves = concatMap (possibleMoves use_secondary) nodes
Iustin Pop's avatar
Iustin Pop committed
468
469
    in
      -- iterate over the possible nodes for this instance
470
      foldl' (checkSingleStep ini_tbl target) aft_failover all_moves
Iustin Pop's avatar
Iustin Pop committed
471

Iustin Pop's avatar
Iustin Pop committed
472
-- | Compute the best next move.
473
474
checkMove :: [Int]               -- ^ Allowed target node indices
          -> Table               -- ^ The current solution
Iustin Pop's avatar
Iustin Pop committed
475
          -> [Instance.Instance] -- ^ List of instances still to move
476
477
          -> Table               -- ^ The new solution
checkMove nodes_idx ini_tbl victims =
Iustin Pop's avatar
Iustin Pop committed
478
479
    let Table _ _ _ ini_plc = ini_tbl
        -- iterate over all instances, computing the best move
480
481
        best_tbl =
            foldl'
482
483
484
485
            (\ step_tbl elem ->
                 if Instance.snode elem == noSecondary then step_tbl
                    else compareTables step_tbl $
                         checkInstanceMove nodes_idx ini_tbl elem)
486
            ini_tbl victims
Iustin Pop's avatar
Iustin Pop committed
487
        Table _ _ _ best_plc = best_tbl
488
489
490
491
    in
      if length best_plc == length ini_plc then -- no advancement
          ini_tbl
      else
492
          best_tbl
Iustin Pop's avatar
Iustin Pop committed
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568

{- | Auxiliary function for solution computation.

We write this in an explicit recursive fashion in order to control
early-abort in case we have met the min delta. We can't use foldr
instead of explicit recursion since we need the accumulator for the
abort decision.

-}
advanceSolution :: [Maybe Removal] -- ^ The removal to process
                -> Int             -- ^ Minimum delta parameter
                -> Int             -- ^ Maximum delta parameter
                -> Maybe Solution  -- ^ Current best solution
                -> Maybe Solution  -- ^ New best solution
advanceSolution [] _ _ sol = sol
advanceSolution (Nothing:xs) m n sol = advanceSolution xs m n sol
advanceSolution ((Just (Removal nx removed)):xs) min_d max_d prev_sol =
    let new_sol = checkPlacement nx removed [] 0 prev_sol max_d
        new_delta = solutionDelta $! new_sol
    in
      if new_delta >= 0 && new_delta <= min_d then
          new_sol
      else
          advanceSolution xs min_d max_d new_sol

-- | Computes the placement solution.
solutionFromRemovals :: [Maybe Removal] -- ^ The list of (possible) removals
                     -> Int             -- ^ Minimum delta parameter
                     -> Int             -- ^ Maximum delta parameter
                     -> Maybe Solution  -- ^ The best solution found
solutionFromRemovals removals min_delta max_delta =
    advanceSolution removals min_delta max_delta Nothing

{- | Computes the solution at the given depth.

This is a wrapper over both computeRemovals and
solutionFromRemovals. In case we have no solution, we return Nothing.

-}
computeSolution :: NodeList        -- ^ The original node data
                -> [Instance.Instance] -- ^ The list of /bad/ instances
                -> Int             -- ^ The /depth/ of removals
                -> Int             -- ^ Maximum number of removals to process
                -> Int             -- ^ Minimum delta parameter
                -> Int             -- ^ Maximum delta parameter
                -> Maybe Solution  -- ^ The best solution found (or Nothing)
computeSolution nl bad_instances depth max_removals min_delta max_delta =
  let
      removals = computeRemovals nl bad_instances depth
      removals' = capRemovals removals max_removals
  in
    solutionFromRemovals removals' min_delta max_delta

-- Solution display functions (pure)

-- | Given the original and final nodes, computes the relocation description.
computeMoves :: String -- ^ The instance name
             -> String -- ^ Original primary
             -> String -- ^ Original secondary
             -> String -- ^ New primary
             -> String -- ^ New secondary
             -> (String, [String])
                -- ^ Tuple of moves and commands list; moves is containing
                -- either @/f/@ for failover or @/r:name/@ for replace
                -- secondary, while the command list holds gnt-instance
                -- commands (without that prefix), e.g \"@failover instance1@\"
computeMoves i a b c d =
    if c == a then {- Same primary -}
        if d == b then {- Same sec??! -}
            ("-", [])
        else {- Change of secondary -}
            (printf "r:%s" d,
             [printf "replace-disks -n %s %s" d i])
    else
        if c == b then {- Failover and ... -}
            if d == a then {- that's all -}
569
                ("f", [printf "migrate -f %s" i])
Iustin Pop's avatar
Iustin Pop committed
570
571
            else
                (printf "f r:%s" d,
572
                 [printf "migrate -f %s" i,
Iustin Pop's avatar
Iustin Pop committed
573
574
575
576
577
                  printf "replace-disks -n %s %s" d i])
        else
            if d == a then {- ... and keep primary as secondary -}
                (printf "r:%s f" c,
                 [printf "replace-disks -n %s %s" c i,
578
                  printf "migrate -f %s" i])
Iustin Pop's avatar
Iustin Pop committed
579
580
581
            else
                if d == b then {- ... keep same secondary -}
                    (printf "f r:%s f" c,
582
                     [printf "migrate -f %s" i,
Iustin Pop's avatar
Iustin Pop committed
583
                      printf "replace-disks -n %s %s" c i,
584
                      printf "migrate -f %s" i])
Iustin Pop's avatar
Iustin Pop committed
585
586
587
588

                else {- Nothing in common -}
                    (printf "r:%s f r:%s" c d,
                     [printf "replace-disks -n %s %s" c i,
589
                      printf "migrate -f %s" i,
Iustin Pop's avatar
Iustin Pop committed
590
591
                      printf "replace-disks -n %s %s" d i])

592
593
{-| Converts a placement to string format -}
printSolutionLine :: InstanceList
594
595
              -> NameList
              -> NameList
596
597
598
              -> Int
              -> Int
              -> Placement
599
              -> Int
600
              -> (String, [String])
601
printSolutionLine il ktn kti nmlen imlen plc pos =
602
603
604
605
606
607
608
609
610
611
612
613
614
    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
        (moves, cmds) =  computeMoves inam opri osec npri nsec
        ostr = (printf "%s:%s" opri osec)::String
        nstr = (printf "%s:%s" npri nsec)::String
    in
615
616
      (printf "  %3d. %-*s %-*s => %-*s %.8f a=%s"
       pos imlen inam pmlen ostr
617
618
619
       pmlen nstr c moves,
       cmds)

620
621
formatCmds :: [[String]] -> String
formatCmds cmd_strs =
622
    unlines $
623
    concat $ map (\(a, b) ->
624
625
626
        (printf "echo step %d" (a::Int)):
        (printf "check"):
        (map ("gnt-instance " ++) b)) $
627
628
        zip [1..] cmd_strs

Iustin Pop's avatar
Iustin Pop committed
629
630
{-| Converts a solution to string format -}
printSolution :: InstanceList
631
632
              -> NameList
              -> NameList
Iustin Pop's avatar
Iustin Pop committed
633
634
635
              -> [Placement]
              -> ([String], [[String]])
printSolution il ktn kti sol =
Iustin Pop's avatar
Iustin Pop committed
636
637
638
639
640
    let
        mlen_fn = maximum . (map length) . snd . unzip
        imlen = mlen_fn kti
        nmlen = mlen_fn ktn
    in
641
642
      unzip $ map (uncurry $ printSolutionLine il ktn kti nmlen imlen) $
            zip sol [1..]
Iustin Pop's avatar
Iustin Pop committed
643
644

-- | Print the node list.
645
printNodes :: NameList -> NodeList -> String
Iustin Pop's avatar
Iustin Pop committed
646
647
648
printNodes ktn nl =
    let snl = sortBy (compare `on` Node.idx) (Container.elems nl)
        snl' = map (\ n -> ((fromJust $ lookup (Node.idx n) ktn), n)) snl
Iustin Pop's avatar
Iustin Pop committed
649
650
        m_name = maximum . (map length) . fst . unzip $ snl'
        helper = Node.list m_name
Iustin Pop's avatar
Iustin Pop committed
651
652
653
654
        header = printf
                 "%2s %-*s %5s %5s %5s %5s %5s %5s %5s %5s %3s %3s %7s %7s"
                 " F" m_name "Name"
                 "t_mem" "n_mem" "i_mem" "x_mem" "f_mem" "r_mem"
655
656
657
                 "t_dsk" "f_dsk"
                 "pri" "sec" "p_fmem" "p_fdsk"
    in unlines $ (header:map (uncurry helper) snl')
Iustin Pop's avatar
Iustin Pop committed
658
659

-- | Compute the mem and disk covariance.
660
compDetailedCV :: NodeList -> (Double, Double, Double, Double, Double)
Iustin Pop's avatar
Iustin Pop committed
661
compDetailedCV nl =
662
    let
663
664
        all_nodes = Container.elems nl
        (offline, nodes) = partition Node.offline all_nodes
665
666
        mem_l = map Node.p_mem nodes
        dsk_l = map Node.p_dsk nodes
Iustin Pop's avatar
Iustin Pop committed
667
668
        mem_cv = varianceCoeff mem_l
        dsk_cv = varianceCoeff dsk_l
669
670
        n1_l = length $ filter Node.failN1 nodes
        n1_score = (fromIntegral n1_l) / (fromIntegral $ length nodes)
671
672
        res_l = map Node.p_rem nodes
        res_cv = varianceCoeff res_l
673
674
675
676
677
678
679
        offline_inst = sum . map (\n -> (length . Node.plist $ n) +
                                        (length . Node.slist $ n)) $ offline
        online_inst = sum . map (\n -> (length . Node.plist $ n) +
                                       (length . Node.slist $ n)) $ nodes
        off_score = (fromIntegral offline_inst) /
                    (fromIntegral $ online_inst + offline_inst)
    in (mem_cv, dsk_cv, n1_score, res_cv, off_score)
Iustin Pop's avatar
Iustin Pop committed
680
681
682
683

-- | Compute the 'total' variance.
compCV :: NodeList -> Double
compCV nl =
684
685
    let (mem_cv, dsk_cv, n1_score, res_cv, off_score) = compDetailedCV nl
    in mem_cv + dsk_cv + n1_score + res_cv + off_score
Iustin Pop's avatar
Iustin Pop committed
686
687
688

printStats :: NodeList -> String
printStats nl =
689
690
691
    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
Iustin Pop's avatar
Iustin Pop committed
692
693
694
695
696
697
698
699
700
701
702
703

-- 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.

-}
704
705
706
707
708
709
710
711
712
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
Iustin Pop's avatar
Iustin Pop committed
713

Iustin Pop's avatar
Iustin Pop committed
714
715
716
717
718
-- | 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 =
Iustin Pop's avatar
Iustin Pop committed
719
720
721
722
723
724
725
726
    foldl' (\accu (idx, inst) ->
                let
                    assocEqual = (\ (i, _) (j, _) -> i == j)
                    pdx = Instance.pnode inst
                    sdx = Instance.snode inst
                    pold = fromJust $ lookup pdx accu
                    pnew = Node.setPri pold idx
                    ac1 = deleteBy assocEqual (pdx, pold) accu
727
728
729
730
731
732
733
734
735
736
737
738
                    ac2 = (pdx, pnew):ac1
                in
                  if sdx /= noSecondary then
                      let
                          sold = fromJust $ lookup sdx accu
                          snew = Node.setSec sold idx
                          ac3 = deleteBy assocEqual (sdx, sold) ac2
                          ac4 = (sdx, snew):ac3
                      in ac4
                  else
                      ac2
           ) nl il
Iustin Pop's avatar
Iustin Pop committed
739

740
-- | Compute the longest common suffix of a NameList list that
741
-- | starts with a dot
742
longestDomain :: NameList -> String
743
744
745
746
747
748
749
750
751
752
753
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
754
stripSuffix :: String -> NameList -> NameList
755
756
757
stripSuffix suffix lst =
    let sflen = length suffix in
    map (\ (key, name) -> (key, take ((length name) - sflen) name)) lst
Iustin Pop's avatar
Iustin Pop committed
758

759
760
761
762
763
764
765
766
767
768
-- | 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 ++ "'"

769
770
771
772
-- | 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
Iustin Pop's avatar
Iustin Pop committed
773
      Nothing -> fail $ "Unknown node '" ++ node ++ "' for instance " ++ inst
774
775
      Just idx -> return idx

Iustin Pop's avatar
Iustin Pop committed
776
-- | Load a node from a field list
777
778
loadNode :: (Monad m) => [String] -> m (String, Node.Node)
loadNode (name:tm:nm:fm:td:fd:fo:[]) = do
779
780
781
782
783
784
785
786
787
788
  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
789
790
791
  return (name, new_node)
loadNode s = fail $ "Invalid/incomplete node data: '" ++ (show s) ++ "'"

Iustin Pop's avatar
Iustin Pop committed
792
-- | Load an instance from a field list
793
794
795
796
loadInst :: (Monad m) =>
            [(String, Int)] -> [String] -> m (String, Instance.Instance)
loadInst ktn (name:mem:dsk:status:pnode:snode:[]) = do
  pidx <- lookupNode pnode name ktn
797
798
  sidx <- (if null snode then return noSecondary
           else lookupNode snode name ktn)
799
800
  vmem <- tryRead name mem
  vdsk <- tryRead name dsk
801
802
  when (sidx == pidx) $ fail $ "Instance " ++ name ++
           " has same primary and secondary node - " ++ pnode
803
  let newinst = Instance.create vmem vdsk status pidx sidx
804
805
806
  return (name, newinst)
loadInst _ s = fail $ "Invalid/incomplete instance data: '" ++ (show s) ++ "'"

Iustin Pop's avatar
Iustin Pop committed
807
808
809
810
{-| 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
811
812
813
         -> Result (Container.Container Node.Node,
                    Container.Container Instance.Instance,
                    String, NameList, NameList)
814
815
loadData ndata idata = do
  {- node file: name t_mem n_mem f_mem t_disk f_disk -}
816
  (ktn, nl) <- loadTabular ndata loadNode Node.setIdx
817
      {- instance file: name mem disk status pnode snode -}
818
  (kti, il) <- loadTabular idata (loadInst ktn) Instance.setIdx
819
820
821
822
823
824
825
826
827
828
829
  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)
830
831
832
833
834
835
836
837

-- | 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

Iustin Pop's avatar
Iustin Pop committed
838
839
840
841
842
843
844
845
-- | 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)

846
847
848
-- | Check cluster data for consistency
checkData :: NodeList -> InstanceList -> NameList -> NameList
          -> ([String], NodeList)
849
checkData nl il ktn _ =
850
851
852
    Container.mapAccum
        (\ msgs node ->
             let nname = fromJust $ lookup (Node.idx node) ktn
853
854
855
856
857
858
859
860
                 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
Iustin Pop's avatar
Iustin Pop committed
861
862
863
                 delta_dsk = (truncate $ Node.t_dsk node)
                             - (Node.f_dsk node)
                             - (nodeIdsk node il)
864
865
                 newn = Node.setFmem (Node.setXmem node delta_mem)
                        (Node.f_mem node - adj_mem)
866
                 umsg1 = if delta_mem > 512 || delta_dsk > 1024
Iustin Pop's avatar
Iustin Pop committed
867
868
869
870
871
                         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)
872
        ) [] nl