root / src / Cluster.hs @ 0a0f2533
History | View | Annotate | Download (25 kB)
1 | e4f08c46 | Iustin Pop | {-| Implementation of cluster-wide logic. |
---|---|---|---|
2 | e4f08c46 | Iustin Pop | |
3 | e4f08c46 | Iustin Pop | This module holds all pure cluster-logic; I\/O related functionality |
4 | e4f08c46 | Iustin Pop | goes into the "Main" module. |
5 | e4f08c46 | Iustin Pop | |
6 | e4f08c46 | Iustin Pop | -} |
7 | e4f08c46 | Iustin Pop | |
8 | e4f08c46 | Iustin Pop | module Cluster |
9 | e4f08c46 | Iustin Pop | ( |
10 | e4f08c46 | Iustin Pop | -- * Types |
11 | e4f08c46 | Iustin Pop | NodeList |
12 | e4f08c46 | Iustin Pop | , InstanceList |
13 | e4f08c46 | Iustin Pop | , Placement |
14 | e4f08c46 | Iustin Pop | , Solution(..) |
15 | e4f08c46 | Iustin Pop | , Table(..) |
16 | e4f08c46 | Iustin Pop | , Removal |
17 | e4f08c46 | Iustin Pop | -- * Generic functions |
18 | e4f08c46 | Iustin Pop | , totalResources |
19 | e4f08c46 | Iustin Pop | -- * First phase functions |
20 | e4f08c46 | Iustin Pop | , computeBadItems |
21 | e4f08c46 | Iustin Pop | -- * Second phase functions |
22 | e4f08c46 | Iustin Pop | , computeSolution |
23 | e4f08c46 | Iustin Pop | , applySolution |
24 | e4f08c46 | Iustin Pop | , printSolution |
25 | e4f08c46 | Iustin Pop | , printNodes |
26 | e4f08c46 | Iustin Pop | -- * Balacing functions |
27 | e4f08c46 | Iustin Pop | , checkMove |
28 | e4f08c46 | Iustin Pop | , compCV |
29 | e4f08c46 | Iustin Pop | , printStats |
30 | e4f08c46 | Iustin Pop | -- * Loading functions |
31 | e4f08c46 | Iustin Pop | , loadData |
32 | e4f08c46 | Iustin Pop | ) where |
33 | e4f08c46 | Iustin Pop | |
34 | e4f08c46 | Iustin Pop | import Data.List |
35 | e4f08c46 | Iustin Pop | import Data.Maybe (isNothing, fromJust) |
36 | e4f08c46 | Iustin Pop | import Text.Printf (printf) |
37 | e4f08c46 | Iustin Pop | import Data.Function |
38 | e4f08c46 | Iustin Pop | |
39 | e4f08c46 | Iustin Pop | import qualified Container |
40 | e4f08c46 | Iustin Pop | import qualified Instance |
41 | e4f08c46 | Iustin Pop | import qualified Node |
42 | e4f08c46 | Iustin Pop | import Utils |
43 | e4f08c46 | Iustin Pop | |
44 | e4f08c46 | Iustin Pop | type NodeList = Container.Container Node.Node |
45 | e4f08c46 | Iustin Pop | type InstanceList = Container.Container Instance.Instance |
46 | e4f08c46 | Iustin Pop | type Score = Double |
47 | e4f08c46 | Iustin Pop | |
48 | e4f08c46 | Iustin Pop | -- | The description of an instance placement. |
49 | c5c295bc | Iustin Pop | type Placement = (Int, Int, Int, Score) |
50 | e4f08c46 | Iustin Pop | |
51 | e4f08c46 | Iustin Pop | {- | A cluster solution described as the solution delta and the list |
52 | e4f08c46 | Iustin Pop | of placements. |
53 | e4f08c46 | Iustin Pop | |
54 | e4f08c46 | Iustin Pop | -} |
55 | e4f08c46 | Iustin Pop | data Solution = Solution Int [Placement] |
56 | e4f08c46 | Iustin Pop | deriving (Eq, Ord, Show) |
57 | e4f08c46 | Iustin Pop | |
58 | e4f08c46 | Iustin Pop | -- | Returns the delta of a solution or -1 for Nothing |
59 | e4f08c46 | Iustin Pop | solutionDelta :: Maybe Solution -> Int |
60 | e4f08c46 | Iustin Pop | solutionDelta sol = case sol of |
61 | e4f08c46 | Iustin Pop | Just (Solution d _) -> d |
62 | e4f08c46 | Iustin Pop | _ -> -1 |
63 | e4f08c46 | Iustin Pop | |
64 | e4f08c46 | Iustin Pop | -- | A removal set. |
65 | e4f08c46 | Iustin Pop | data Removal = Removal NodeList [Instance.Instance] |
66 | e4f08c46 | Iustin Pop | |
67 | e4f08c46 | Iustin Pop | -- | An instance move definition |
68 | e4f08c46 | Iustin Pop | data IMove = Failover |
69 | e4f08c46 | Iustin Pop | | ReplacePrimary Int |
70 | e4f08c46 | Iustin Pop | | ReplaceSecondary Int |
71 | e4f08c46 | Iustin Pop | deriving (Show) |
72 | e4f08c46 | Iustin Pop | |
73 | e4f08c46 | Iustin Pop | -- | The complete state for the balancing solution |
74 | e4f08c46 | Iustin Pop | data Table = Table NodeList InstanceList Score [Placement] |
75 | e4f08c46 | Iustin Pop | deriving (Show) |
76 | e4f08c46 | Iustin Pop | |
77 | e4f08c46 | Iustin Pop | -- General functions |
78 | e4f08c46 | Iustin Pop | |
79 | e4f08c46 | Iustin Pop | -- | Cap the removal list if needed. |
80 | e4f08c46 | Iustin Pop | capRemovals :: [a] -> Int -> [a] |
81 | e4f08c46 | Iustin Pop | capRemovals removals max_removals = |
82 | e4f08c46 | Iustin Pop | if max_removals > 0 then |
83 | e4f08c46 | Iustin Pop | take max_removals removals |
84 | e4f08c46 | Iustin Pop | else |
85 | e4f08c46 | Iustin Pop | removals |
86 | e4f08c46 | Iustin Pop | |
87 | e4f08c46 | Iustin Pop | -- | Check if the given node list fails the N+1 check. |
88 | e4f08c46 | Iustin Pop | verifyN1Check :: [Node.Node] -> Bool |
89 | e4f08c46 | Iustin Pop | verifyN1Check nl = any Node.failN1 nl |
90 | e4f08c46 | Iustin Pop | |
91 | e4f08c46 | Iustin Pop | -- | Verifies the N+1 status and return the affected nodes. |
92 | e4f08c46 | Iustin Pop | verifyN1 :: [Node.Node] -> [Node.Node] |
93 | e4f08c46 | Iustin Pop | verifyN1 nl = filter Node.failN1 nl |
94 | e4f08c46 | Iustin Pop | |
95 | e4f08c46 | Iustin Pop | {-| Add an instance and return the new node and instance maps. -} |
96 | e4f08c46 | Iustin Pop | addInstance :: NodeList -> Instance.Instance -> |
97 | e4f08c46 | Iustin Pop | Node.Node -> Node.Node -> Maybe NodeList |
98 | e4f08c46 | Iustin Pop | addInstance nl idata pri sec = |
99 | e4f08c46 | Iustin Pop | let pdx = Node.idx pri |
100 | e4f08c46 | Iustin Pop | sdx = Node.idx sec |
101 | e4f08c46 | Iustin Pop | in do |
102 | e4f08c46 | Iustin Pop | pnode <- Node.addPri pri idata |
103 | e4f08c46 | Iustin Pop | snode <- Node.addSec sec idata pdx |
104 | e4f08c46 | Iustin Pop | new_nl <- return $ Container.addTwo sdx snode |
105 | e4f08c46 | Iustin Pop | pdx pnode nl |
106 | e4f08c46 | Iustin Pop | return new_nl |
107 | e4f08c46 | Iustin Pop | |
108 | e4f08c46 | Iustin Pop | -- | Remove an instance and return the new node and instance maps. |
109 | e4f08c46 | Iustin Pop | removeInstance :: NodeList -> Instance.Instance -> NodeList |
110 | e4f08c46 | Iustin Pop | removeInstance nl idata = |
111 | e4f08c46 | Iustin Pop | let pnode = Instance.pnode idata |
112 | e4f08c46 | Iustin Pop | snode = Instance.snode idata |
113 | e4f08c46 | Iustin Pop | pn = Container.find pnode nl |
114 | e4f08c46 | Iustin Pop | sn = Container.find snode nl |
115 | e4f08c46 | Iustin Pop | new_nl = Container.addTwo |
116 | e4f08c46 | Iustin Pop | pnode (Node.removePri pn idata) |
117 | e4f08c46 | Iustin Pop | snode (Node.removeSec sn idata) nl in |
118 | e4f08c46 | Iustin Pop | new_nl |
119 | e4f08c46 | Iustin Pop | |
120 | e4f08c46 | Iustin Pop | -- | Remove an instance and return the new node map. |
121 | e4f08c46 | Iustin Pop | removeInstances :: NodeList -> [Instance.Instance] -> NodeList |
122 | e4f08c46 | Iustin Pop | removeInstances = foldl' removeInstance |
123 | e4f08c46 | Iustin Pop | |
124 | e4f08c46 | Iustin Pop | -- | Compute the total free disk and memory in the cluster. |
125 | e4f08c46 | Iustin Pop | totalResources :: Container.Container Node.Node -> (Int, Int) |
126 | e4f08c46 | Iustin Pop | totalResources nl = |
127 | e4f08c46 | Iustin Pop | foldl' |
128 | 962367fe | Iustin Pop | (\ (mem, dsk) node -> (mem + (Node.f_mem node), |
129 | 962367fe | Iustin Pop | dsk + (Node.f_dsk node))) |
130 | e4f08c46 | Iustin Pop | (0, 0) (Container.elems nl) |
131 | e4f08c46 | Iustin Pop | |
132 | e4f08c46 | Iustin Pop | {- | Compute a new version of a cluster given a solution. |
133 | e4f08c46 | Iustin Pop | |
134 | e4f08c46 | Iustin Pop | This is not used for computing the solutions, but for applying a |
135 | e4f08c46 | Iustin Pop | (known-good) solution to the original cluster for final display. |
136 | e4f08c46 | Iustin Pop | |
137 | e4f08c46 | Iustin Pop | It first removes the relocated instances after which it places them on |
138 | e4f08c46 | Iustin Pop | their new nodes. |
139 | e4f08c46 | Iustin Pop | |
140 | e4f08c46 | Iustin Pop | -} |
141 | e4f08c46 | Iustin Pop | applySolution :: NodeList -> InstanceList -> [Placement] -> NodeList |
142 | e4f08c46 | Iustin Pop | applySolution nl il sol = |
143 | c5c295bc | Iustin Pop | let odxes = map (\ (a, b, c, _) -> (Container.find a il, |
144 | c5c295bc | Iustin Pop | Node.idx (Container.find b nl), |
145 | c5c295bc | Iustin Pop | Node.idx (Container.find c nl)) |
146 | e4f08c46 | Iustin Pop | ) sol |
147 | e4f08c46 | Iustin Pop | idxes = (\ (x, _, _) -> x) (unzip3 odxes) |
148 | e4f08c46 | Iustin Pop | nc = removeInstances nl idxes |
149 | e4f08c46 | Iustin Pop | in |
150 | e4f08c46 | Iustin Pop | foldl' (\ nz (a, b, c) -> |
151 | e4f08c46 | Iustin Pop | let new_p = Container.find b nz |
152 | e4f08c46 | Iustin Pop | new_s = Container.find c nz in |
153 | e4f08c46 | Iustin Pop | fromJust (addInstance nz a new_p new_s) |
154 | e4f08c46 | Iustin Pop | ) nc odxes |
155 | e4f08c46 | Iustin Pop | |
156 | e4f08c46 | Iustin Pop | |
157 | e4f08c46 | Iustin Pop | -- First phase functions |
158 | e4f08c46 | Iustin Pop | |
159 | e4f08c46 | Iustin Pop | {- | Given a list 1,2,3..n build a list of pairs [(1, [2..n]), (2, |
160 | e4f08c46 | Iustin Pop | [3..n]), ...] |
161 | e4f08c46 | Iustin Pop | |
162 | e4f08c46 | Iustin Pop | -} |
163 | e4f08c46 | Iustin Pop | genParts :: [a] -> Int -> [(a, [a])] |
164 | e4f08c46 | Iustin Pop | genParts l count = |
165 | e4f08c46 | Iustin Pop | case l of |
166 | e4f08c46 | Iustin Pop | [] -> [] |
167 | e4f08c46 | Iustin Pop | x:xs -> |
168 | e4f08c46 | Iustin Pop | if length l < count then |
169 | e4f08c46 | Iustin Pop | [] |
170 | e4f08c46 | Iustin Pop | else |
171 | e4f08c46 | Iustin Pop | (x, xs) : (genParts xs count) |
172 | e4f08c46 | Iustin Pop | |
173 | e4f08c46 | Iustin Pop | -- | Generates combinations of count items from the names list. |
174 | e4f08c46 | Iustin Pop | genNames :: Int -> [b] -> [[b]] |
175 | e4f08c46 | Iustin Pop | genNames count1 names1 = |
176 | e4f08c46 | Iustin Pop | let aux_fn count names current = |
177 | e4f08c46 | Iustin Pop | case count of |
178 | e4f08c46 | Iustin Pop | 0 -> [current] |
179 | e4f08c46 | Iustin Pop | _ -> |
180 | e4f08c46 | Iustin Pop | concatMap |
181 | e4f08c46 | Iustin Pop | (\ (x, xs) -> aux_fn (count - 1) xs (x:current)) |
182 | e4f08c46 | Iustin Pop | (genParts names count) |
183 | e4f08c46 | Iustin Pop | in |
184 | e4f08c46 | Iustin Pop | aux_fn count1 names1 [] |
185 | e4f08c46 | Iustin Pop | |
186 | e4f08c46 | Iustin Pop | {- | Computes the pair of bad nodes and instances. |
187 | e4f08c46 | Iustin Pop | |
188 | e4f08c46 | Iustin Pop | The bad node list is computed via a simple 'verifyN1' check, and the |
189 | e4f08c46 | Iustin Pop | bad instance list is the list of primary and secondary instances of |
190 | e4f08c46 | Iustin Pop | those nodes. |
191 | e4f08c46 | Iustin Pop | |
192 | e4f08c46 | Iustin Pop | -} |
193 | e4f08c46 | Iustin Pop | computeBadItems :: NodeList -> InstanceList -> |
194 | e4f08c46 | Iustin Pop | ([Node.Node], [Instance.Instance]) |
195 | e4f08c46 | Iustin Pop | computeBadItems nl il = |
196 | e4f08c46 | Iustin Pop | let bad_nodes = verifyN1 $ Container.elems nl |
197 | e4f08c46 | Iustin Pop | bad_instances = map (\idx -> Container.find idx il) $ |
198 | e4f08c46 | Iustin Pop | sort $ nub $ concat $ |
199 | e4f08c46 | Iustin Pop | map (\ n -> (Node.slist n) ++ (Node.plist n)) bad_nodes |
200 | e4f08c46 | Iustin Pop | in |
201 | e4f08c46 | Iustin Pop | (bad_nodes, bad_instances) |
202 | e4f08c46 | Iustin Pop | |
203 | e4f08c46 | Iustin Pop | |
204 | e4f08c46 | Iustin Pop | {- | Checks if removal of instances results in N+1 pass. |
205 | e4f08c46 | Iustin Pop | |
206 | e4f08c46 | Iustin Pop | Note: the check removal cannot optimize by scanning only the affected |
207 | e4f08c46 | Iustin Pop | nodes, since the cluster is known to be not healthy; only the check |
208 | e4f08c46 | Iustin Pop | placement can make this shortcut. |
209 | e4f08c46 | Iustin Pop | |
210 | e4f08c46 | Iustin Pop | -} |
211 | e4f08c46 | Iustin Pop | checkRemoval :: NodeList -> [Instance.Instance] -> Maybe Removal |
212 | e4f08c46 | Iustin Pop | checkRemoval nl victims = |
213 | e4f08c46 | Iustin Pop | let nx = removeInstances nl victims |
214 | e4f08c46 | Iustin Pop | failN1 = verifyN1Check (Container.elems nx) |
215 | e4f08c46 | Iustin Pop | in |
216 | e4f08c46 | Iustin Pop | if failN1 then |
217 | e4f08c46 | Iustin Pop | Nothing |
218 | e4f08c46 | Iustin Pop | else |
219 | e4f08c46 | Iustin Pop | Just $ Removal nx victims |
220 | e4f08c46 | Iustin Pop | |
221 | e4f08c46 | Iustin Pop | |
222 | e4f08c46 | Iustin Pop | -- | Computes the removals list for a given depth |
223 | e4f08c46 | Iustin Pop | computeRemovals :: Cluster.NodeList |
224 | e4f08c46 | Iustin Pop | -> [Instance.Instance] |
225 | e4f08c46 | Iustin Pop | -> Int |
226 | e4f08c46 | Iustin Pop | -> [Maybe Cluster.Removal] |
227 | e4f08c46 | Iustin Pop | computeRemovals nl bad_instances depth = |
228 | e4f08c46 | Iustin Pop | map (checkRemoval nl) $ genNames depth bad_instances |
229 | e4f08c46 | Iustin Pop | |
230 | e4f08c46 | Iustin Pop | -- Second phase functions |
231 | e4f08c46 | Iustin Pop | |
232 | e4f08c46 | Iustin Pop | -- | Single-node relocation cost |
233 | e4f08c46 | Iustin Pop | nodeDelta :: Int -> Int -> Int -> Int |
234 | e4f08c46 | Iustin Pop | nodeDelta i p s = |
235 | e4f08c46 | Iustin Pop | if i == p || i == s then |
236 | e4f08c46 | Iustin Pop | 0 |
237 | e4f08c46 | Iustin Pop | else |
238 | e4f08c46 | Iustin Pop | 1 |
239 | e4f08c46 | Iustin Pop | |
240 | e4f08c46 | Iustin Pop | {-| Compute best solution. |
241 | e4f08c46 | Iustin Pop | |
242 | e4f08c46 | Iustin Pop | This function compares two solutions, choosing the minimum valid |
243 | e4f08c46 | Iustin Pop | solution. |
244 | e4f08c46 | Iustin Pop | -} |
245 | e4f08c46 | Iustin Pop | compareSolutions :: Maybe Solution -> Maybe Solution -> Maybe Solution |
246 | e4f08c46 | Iustin Pop | compareSolutions a b = case (a, b) of |
247 | e4f08c46 | Iustin Pop | (Nothing, x) -> x |
248 | e4f08c46 | Iustin Pop | (x, Nothing) -> x |
249 | e4f08c46 | Iustin Pop | (x, y) -> min x y |
250 | e4f08c46 | Iustin Pop | |
251 | e4f08c46 | Iustin Pop | -- | Compute best table. Note that the ordering of the arguments is important. |
252 | e4f08c46 | Iustin Pop | compareTables :: Table -> Table -> Table |
253 | e4f08c46 | Iustin Pop | compareTables a@(Table _ _ a_cv _) b@(Table _ _ b_cv _ ) = |
254 | e4f08c46 | Iustin Pop | if a_cv > b_cv then b else a |
255 | e4f08c46 | Iustin Pop | |
256 | e4f08c46 | Iustin Pop | -- | Check if a given delta is worse then an existing solution. |
257 | e4f08c46 | Iustin Pop | tooHighDelta :: Maybe Solution -> Int -> Int -> Bool |
258 | e4f08c46 | Iustin Pop | tooHighDelta sol new_delta max_delta = |
259 | e4f08c46 | Iustin Pop | if new_delta > max_delta && max_delta >=0 then |
260 | e4f08c46 | Iustin Pop | True |
261 | e4f08c46 | Iustin Pop | else |
262 | e4f08c46 | Iustin Pop | case sol of |
263 | e4f08c46 | Iustin Pop | Nothing -> False |
264 | e4f08c46 | Iustin Pop | Just (Solution old_delta _) -> old_delta <= new_delta |
265 | e4f08c46 | Iustin Pop | |
266 | e4f08c46 | Iustin Pop | {-| Check if placement of instances still keeps the cluster N+1 compliant. |
267 | e4f08c46 | Iustin Pop | |
268 | e4f08c46 | Iustin Pop | This is the workhorse of the allocation algorithm: given the |
269 | e4f08c46 | Iustin Pop | current node and instance maps, the list of instances to be |
270 | e4f08c46 | Iustin Pop | placed, and the current solution, this will return all possible |
271 | e4f08c46 | Iustin Pop | solution by recursing until all target instances are placed. |
272 | e4f08c46 | Iustin Pop | |
273 | e4f08c46 | Iustin Pop | -} |
274 | e4f08c46 | Iustin Pop | checkPlacement :: NodeList -- ^ The current node list |
275 | e4f08c46 | Iustin Pop | -> [Instance.Instance] -- ^ List of instances still to place |
276 | e4f08c46 | Iustin Pop | -> [Placement] -- ^ Partial solution until now |
277 | e4f08c46 | Iustin Pop | -> Int -- ^ The delta of the partial solution |
278 | e4f08c46 | Iustin Pop | -> Maybe Solution -- ^ The previous solution |
279 | e4f08c46 | Iustin Pop | -> Int -- ^ Abort if the we go above this delta |
280 | e4f08c46 | Iustin Pop | -> Maybe Solution -- ^ The new solution |
281 | e4f08c46 | Iustin Pop | checkPlacement nl victims current current_delta prev_sol max_delta = |
282 | e4f08c46 | Iustin Pop | let target = head victims |
283 | e4f08c46 | Iustin Pop | opdx = Instance.pnode target |
284 | e4f08c46 | Iustin Pop | osdx = Instance.snode target |
285 | e4f08c46 | Iustin Pop | vtail = tail victims |
286 | e4f08c46 | Iustin Pop | have_tail = (length vtail) > 0 |
287 | e4f08c46 | Iustin Pop | nodes = Container.elems nl |
288 | c5c295bc | Iustin Pop | iidx = Instance.idx target |
289 | e4f08c46 | Iustin Pop | in |
290 | e4f08c46 | Iustin Pop | foldl' |
291 | e4f08c46 | Iustin Pop | (\ accu_p pri -> |
292 | e4f08c46 | Iustin Pop | let |
293 | e4f08c46 | Iustin Pop | pri_idx = Node.idx pri |
294 | e4f08c46 | Iustin Pop | upri_delta = current_delta + nodeDelta pri_idx opdx osdx |
295 | e4f08c46 | Iustin Pop | new_pri = Node.addPri pri target |
296 | e4f08c46 | Iustin Pop | fail_delta1 = tooHighDelta accu_p upri_delta max_delta |
297 | e4f08c46 | Iustin Pop | in |
298 | e4f08c46 | Iustin Pop | if fail_delta1 || isNothing(new_pri) then accu_p |
299 | e4f08c46 | Iustin Pop | else let pri_nl = Container.add pri_idx (fromJust new_pri) nl in |
300 | e4f08c46 | Iustin Pop | foldl' |
301 | e4f08c46 | Iustin Pop | (\ accu sec -> |
302 | e4f08c46 | Iustin Pop | let |
303 | e4f08c46 | Iustin Pop | sec_idx = Node.idx sec |
304 | e4f08c46 | Iustin Pop | upd_delta = upri_delta + |
305 | e4f08c46 | Iustin Pop | nodeDelta sec_idx opdx osdx |
306 | e4f08c46 | Iustin Pop | fail_delta2 = tooHighDelta accu upd_delta max_delta |
307 | e4f08c46 | Iustin Pop | new_sec = Node.addSec sec target pri_idx |
308 | e4f08c46 | Iustin Pop | in |
309 | e4f08c46 | Iustin Pop | if sec_idx == pri_idx || fail_delta2 || |
310 | e4f08c46 | Iustin Pop | isNothing new_sec then accu |
311 | e4f08c46 | Iustin Pop | else let |
312 | e4f08c46 | Iustin Pop | nx = Container.add sec_idx (fromJust new_sec) pri_nl |
313 | c5c295bc | Iustin Pop | upd_cv = compCV nx |
314 | c5c295bc | Iustin Pop | plc = (iidx, pri_idx, sec_idx, upd_cv) |
315 | e4f08c46 | Iustin Pop | c2 = plc:current |
316 | e4f08c46 | Iustin Pop | result = |
317 | e4f08c46 | Iustin Pop | if have_tail then |
318 | e4f08c46 | Iustin Pop | checkPlacement nx vtail c2 upd_delta |
319 | e4f08c46 | Iustin Pop | accu max_delta |
320 | e4f08c46 | Iustin Pop | else |
321 | e4f08c46 | Iustin Pop | Just (Solution upd_delta c2) |
322 | e4f08c46 | Iustin Pop | in compareSolutions accu result |
323 | e4f08c46 | Iustin Pop | ) accu_p nodes |
324 | e4f08c46 | Iustin Pop | ) prev_sol nodes |
325 | e4f08c46 | Iustin Pop | |
326 | e4f08c46 | Iustin Pop | -- | Apply a move |
327 | e4f08c46 | Iustin Pop | applyMove :: NodeList -> Instance.Instance |
328 | e4f08c46 | Iustin Pop | -> IMove -> (Maybe NodeList, Instance.Instance, Int, Int) |
329 | e4f08c46 | Iustin Pop | applyMove nl inst Failover = |
330 | e4f08c46 | Iustin Pop | let old_pdx = Instance.pnode inst |
331 | e4f08c46 | Iustin Pop | old_sdx = Instance.snode inst |
332 | e4f08c46 | Iustin Pop | old_p = Container.find old_pdx nl |
333 | e4f08c46 | Iustin Pop | old_s = Container.find old_sdx nl |
334 | e4f08c46 | Iustin Pop | int_p = Node.removePri old_p inst |
335 | e4f08c46 | Iustin Pop | int_s = Node.removeSec old_s inst |
336 | e4f08c46 | Iustin Pop | new_p = Node.addPri int_s inst |
337 | e4f08c46 | Iustin Pop | new_s = Node.addSec int_p inst old_sdx |
338 | e4f08c46 | Iustin Pop | new_nl = if isNothing(new_p) || isNothing(new_s) then Nothing |
339 | e4f08c46 | Iustin Pop | else Just $ Container.addTwo old_pdx (fromJust new_s) |
340 | e4f08c46 | Iustin Pop | old_sdx (fromJust new_p) nl |
341 | e4f08c46 | Iustin Pop | in (new_nl, Instance.setBoth inst old_sdx old_pdx, old_sdx, old_pdx) |
342 | e4f08c46 | Iustin Pop | |
343 | e4f08c46 | Iustin Pop | applyMove nl inst (ReplacePrimary new_pdx) = |
344 | e4f08c46 | Iustin Pop | let old_pdx = Instance.pnode inst |
345 | e4f08c46 | Iustin Pop | old_sdx = Instance.snode inst |
346 | e4f08c46 | Iustin Pop | old_p = Container.find old_pdx nl |
347 | e4f08c46 | Iustin Pop | old_s = Container.find old_sdx nl |
348 | e4f08c46 | Iustin Pop | tgt_n = Container.find new_pdx nl |
349 | e4f08c46 | Iustin Pop | int_p = Node.removePri old_p inst |
350 | e4f08c46 | Iustin Pop | int_s = Node.removeSec old_s inst |
351 | e4f08c46 | Iustin Pop | new_p = Node.addPri tgt_n inst |
352 | e4f08c46 | Iustin Pop | new_s = Node.addSec int_s inst new_pdx |
353 | e4f08c46 | Iustin Pop | new_nl = if isNothing(new_p) || isNothing(new_s) then Nothing |
354 | e4f08c46 | Iustin Pop | else Just $ Container.add new_pdx (fromJust new_p) $ |
355 | e4f08c46 | Iustin Pop | Container.addTwo old_pdx int_p |
356 | e4f08c46 | Iustin Pop | old_sdx (fromJust new_s) nl |
357 | e4f08c46 | Iustin Pop | in (new_nl, Instance.setPri inst new_pdx, new_pdx, old_sdx) |
358 | e4f08c46 | Iustin Pop | |
359 | e4f08c46 | Iustin Pop | applyMove nl inst (ReplaceSecondary new_sdx) = |
360 | e4f08c46 | Iustin Pop | let old_pdx = Instance.pnode inst |
361 | e4f08c46 | Iustin Pop | old_sdx = Instance.snode inst |
362 | e4f08c46 | Iustin Pop | old_s = Container.find old_sdx nl |
363 | e4f08c46 | Iustin Pop | tgt_n = Container.find new_sdx nl |
364 | e4f08c46 | Iustin Pop | int_s = Node.removeSec old_s inst |
365 | e4f08c46 | Iustin Pop | new_s = Node.addSec tgt_n inst old_pdx |
366 | e4f08c46 | Iustin Pop | new_nl = if isNothing(new_s) then Nothing |
367 | e4f08c46 | Iustin Pop | else Just $ Container.addTwo new_sdx (fromJust new_s) |
368 | e4f08c46 | Iustin Pop | old_sdx int_s nl |
369 | e4f08c46 | Iustin Pop | in (new_nl, Instance.setSec inst new_sdx, old_pdx, new_sdx) |
370 | e4f08c46 | Iustin Pop | |
371 | e4f08c46 | Iustin Pop | checkSingleStep :: Table -- ^ The original table |
372 | e4f08c46 | Iustin Pop | -> Instance.Instance -- ^ The instance to move |
373 | e4f08c46 | Iustin Pop | -> Table -- ^ The current best table |
374 | e4f08c46 | Iustin Pop | -> IMove -- ^ The move to apply |
375 | e4f08c46 | Iustin Pop | -> Table -- ^ The final best table |
376 | e4f08c46 | Iustin Pop | checkSingleStep ini_tbl target cur_tbl move = |
377 | e4f08c46 | Iustin Pop | let |
378 | e4f08c46 | Iustin Pop | Table ini_nl ini_il _ ini_plc = ini_tbl |
379 | 0a0f2533 | Iustin Pop | (tmp_nl, new_inst, pri_idx, sec_idx) = applyMove ini_nl target move |
380 | e4f08c46 | Iustin Pop | in |
381 | e4f08c46 | Iustin Pop | if isNothing tmp_nl then cur_tbl |
382 | e4f08c46 | Iustin Pop | else |
383 | e4f08c46 | Iustin Pop | let tgt_idx = Instance.idx target |
384 | e4f08c46 | Iustin Pop | upd_nl = fromJust tmp_nl |
385 | e4f08c46 | Iustin Pop | upd_cvar = compCV upd_nl |
386 | e4f08c46 | Iustin Pop | upd_il = Container.add tgt_idx new_inst ini_il |
387 | 0a0f2533 | Iustin Pop | upd_plc = (tgt_idx, pri_idx, sec_idx, upd_cvar):ini_plc |
388 | e4f08c46 | Iustin Pop | upd_tbl = Table upd_nl upd_il upd_cvar upd_plc |
389 | e4f08c46 | Iustin Pop | in |
390 | e4f08c46 | Iustin Pop | compareTables cur_tbl upd_tbl |
391 | e4f08c46 | Iustin Pop | |
392 | 256810de | Iustin Pop | checkInstanceMove :: [Int] -- Allowed target node indices |
393 | 256810de | Iustin Pop | -> Table -- Original table |
394 | 256810de | Iustin Pop | -> Instance.Instance -- Instance to move |
395 | 256810de | Iustin Pop | -> Table -- Best new table for this instance |
396 | 256810de | Iustin Pop | checkInstanceMove nodes_idx ini_tbl target = |
397 | 4e25d1c2 | Iustin Pop | let |
398 | 4e25d1c2 | Iustin Pop | opdx = Instance.pnode target |
399 | 4e25d1c2 | Iustin Pop | osdx = Instance.snode target |
400 | 9dc6023f | Iustin Pop | nodes = filter (\idx -> idx /= opdx && idx /= osdx) nodes_idx |
401 | 4e25d1c2 | Iustin Pop | aft_failover = checkSingleStep ini_tbl target ini_tbl Failover |
402 | 9dc6023f | Iustin Pop | all_moves = concatMap (\idx -> [ReplacePrimary idx, |
403 | 9dc6023f | Iustin Pop | ReplaceSecondary idx]) nodes |
404 | 4e25d1c2 | Iustin Pop | in |
405 | 4e25d1c2 | Iustin Pop | -- iterate over the possible nodes for this instance |
406 | 9dc6023f | Iustin Pop | foldl' (checkSingleStep ini_tbl target) aft_failover all_moves |
407 | 4e25d1c2 | Iustin Pop | |
408 | e4f08c46 | Iustin Pop | -- | Compute the best next move. |
409 | 256810de | Iustin Pop | checkMove :: [Int] -- ^ Allowed target node indices |
410 | 256810de | Iustin Pop | -> Table -- ^ The current solution |
411 | e4f08c46 | Iustin Pop | -> [Instance.Instance] -- ^ List of instances still to move |
412 | 256810de | Iustin Pop | -> Table -- ^ The new solution |
413 | 256810de | Iustin Pop | checkMove nodes_idx ini_tbl victims = |
414 | 4e25d1c2 | Iustin Pop | let Table _ _ _ ini_plc = ini_tbl |
415 | 4e25d1c2 | Iustin Pop | -- iterate over all instances, computing the best move |
416 | 256810de | Iustin Pop | best_tbl = |
417 | 256810de | Iustin Pop | foldl' |
418 | 256810de | Iustin Pop | (\ step_tbl elem -> compareTables step_tbl $ |
419 | 256810de | Iustin Pop | checkInstanceMove nodes_idx ini_tbl elem) |
420 | 256810de | Iustin Pop | ini_tbl victims |
421 | aaaa0e43 | Iustin Pop | Table _ _ _ best_plc = best_tbl |
422 | 0a0f2533 | Iustin Pop | in |
423 | 0a0f2533 | Iustin Pop | if length best_plc == length ini_plc then -- no advancement |
424 | 0a0f2533 | Iustin Pop | ini_tbl |
425 | 0a0f2533 | Iustin Pop | else |
426 | 0a0f2533 | Iustin Pop | -- FIXME: replace 100 with a real constant |
427 | 0a0f2533 | Iustin Pop | if (length best_plc > 100) then best_tbl |
428 | 0a0f2533 | Iustin Pop | else checkMove nodes_idx best_tbl victims |
429 | e4f08c46 | Iustin Pop | |
430 | e4f08c46 | Iustin Pop | {- | Auxiliary function for solution computation. |
431 | e4f08c46 | Iustin Pop | |
432 | e4f08c46 | Iustin Pop | We write this in an explicit recursive fashion in order to control |
433 | e4f08c46 | Iustin Pop | early-abort in case we have met the min delta. We can't use foldr |
434 | e4f08c46 | Iustin Pop | instead of explicit recursion since we need the accumulator for the |
435 | e4f08c46 | Iustin Pop | abort decision. |
436 | e4f08c46 | Iustin Pop | |
437 | e4f08c46 | Iustin Pop | -} |
438 | e4f08c46 | Iustin Pop | advanceSolution :: [Maybe Removal] -- ^ The removal to process |
439 | e4f08c46 | Iustin Pop | -> Int -- ^ Minimum delta parameter |
440 | e4f08c46 | Iustin Pop | -> Int -- ^ Maximum delta parameter |
441 | e4f08c46 | Iustin Pop | -> Maybe Solution -- ^ Current best solution |
442 | e4f08c46 | Iustin Pop | -> Maybe Solution -- ^ New best solution |
443 | e4f08c46 | Iustin Pop | advanceSolution [] _ _ sol = sol |
444 | e4f08c46 | Iustin Pop | advanceSolution (Nothing:xs) m n sol = advanceSolution xs m n sol |
445 | e4f08c46 | Iustin Pop | advanceSolution ((Just (Removal nx removed)):xs) min_d max_d prev_sol = |
446 | e4f08c46 | Iustin Pop | let new_sol = checkPlacement nx removed [] 0 prev_sol max_d |
447 | e4f08c46 | Iustin Pop | new_delta = solutionDelta $! new_sol |
448 | e4f08c46 | Iustin Pop | in |
449 | e4f08c46 | Iustin Pop | if new_delta >= 0 && new_delta <= min_d then |
450 | e4f08c46 | Iustin Pop | new_sol |
451 | e4f08c46 | Iustin Pop | else |
452 | e4f08c46 | Iustin Pop | advanceSolution xs min_d max_d new_sol |
453 | e4f08c46 | Iustin Pop | |
454 | e4f08c46 | Iustin Pop | -- | Computes the placement solution. |
455 | e4f08c46 | Iustin Pop | solutionFromRemovals :: [Maybe Removal] -- ^ The list of (possible) removals |
456 | e4f08c46 | Iustin Pop | -> Int -- ^ Minimum delta parameter |
457 | e4f08c46 | Iustin Pop | -> Int -- ^ Maximum delta parameter |
458 | e4f08c46 | Iustin Pop | -> Maybe Solution -- ^ The best solution found |
459 | e4f08c46 | Iustin Pop | solutionFromRemovals removals min_delta max_delta = |
460 | e4f08c46 | Iustin Pop | advanceSolution removals min_delta max_delta Nothing |
461 | e4f08c46 | Iustin Pop | |
462 | e4f08c46 | Iustin Pop | {- | Computes the solution at the given depth. |
463 | e4f08c46 | Iustin Pop | |
464 | e4f08c46 | Iustin Pop | This is a wrapper over both computeRemovals and |
465 | e4f08c46 | Iustin Pop | solutionFromRemovals. In case we have no solution, we return Nothing. |
466 | e4f08c46 | Iustin Pop | |
467 | e4f08c46 | Iustin Pop | -} |
468 | e4f08c46 | Iustin Pop | computeSolution :: NodeList -- ^ The original node data |
469 | e4f08c46 | Iustin Pop | -> [Instance.Instance] -- ^ The list of /bad/ instances |
470 | e4f08c46 | Iustin Pop | -> Int -- ^ The /depth/ of removals |
471 | e4f08c46 | Iustin Pop | -> Int -- ^ Maximum number of removals to process |
472 | e4f08c46 | Iustin Pop | -> Int -- ^ Minimum delta parameter |
473 | e4f08c46 | Iustin Pop | -> Int -- ^ Maximum delta parameter |
474 | e4f08c46 | Iustin Pop | -> Maybe Solution -- ^ The best solution found (or Nothing) |
475 | e4f08c46 | Iustin Pop | computeSolution nl bad_instances depth max_removals min_delta max_delta = |
476 | e4f08c46 | Iustin Pop | let |
477 | e4f08c46 | Iustin Pop | removals = computeRemovals nl bad_instances depth |
478 | e4f08c46 | Iustin Pop | removals' = capRemovals removals max_removals |
479 | e4f08c46 | Iustin Pop | in |
480 | e4f08c46 | Iustin Pop | solutionFromRemovals removals' min_delta max_delta |
481 | e4f08c46 | Iustin Pop | |
482 | e4f08c46 | Iustin Pop | -- Solution display functions (pure) |
483 | e4f08c46 | Iustin Pop | |
484 | e4f08c46 | Iustin Pop | -- | Given the original and final nodes, computes the relocation description. |
485 | e4f08c46 | Iustin Pop | computeMoves :: String -- ^ The instance name |
486 | e4f08c46 | Iustin Pop | -> String -- ^ Original primary |
487 | e4f08c46 | Iustin Pop | -> String -- ^ Original secondary |
488 | e4f08c46 | Iustin Pop | -> String -- ^ New primary |
489 | e4f08c46 | Iustin Pop | -> String -- ^ New secondary |
490 | e4f08c46 | Iustin Pop | -> (String, [String]) |
491 | e4f08c46 | Iustin Pop | -- ^ Tuple of moves and commands list; moves is containing |
492 | e4f08c46 | Iustin Pop | -- either @/f/@ for failover or @/r:name/@ for replace |
493 | e4f08c46 | Iustin Pop | -- secondary, while the command list holds gnt-instance |
494 | e4f08c46 | Iustin Pop | -- commands (without that prefix), e.g \"@failover instance1@\" |
495 | e4f08c46 | Iustin Pop | computeMoves i a b c d = |
496 | e4f08c46 | Iustin Pop | if c == a then {- Same primary -} |
497 | e4f08c46 | Iustin Pop | if d == b then {- Same sec??! -} |
498 | e4f08c46 | Iustin Pop | ("-", []) |
499 | e4f08c46 | Iustin Pop | else {- Change of secondary -} |
500 | e4f08c46 | Iustin Pop | (printf "r:%s" d, |
501 | e4f08c46 | Iustin Pop | [printf "replace-disks -n %s %s" d i]) |
502 | e4f08c46 | Iustin Pop | else |
503 | e4f08c46 | Iustin Pop | if c == b then {- Failover and ... -} |
504 | e4f08c46 | Iustin Pop | if d == a then {- that's all -} |
505 | e4f08c46 | Iustin Pop | ("f", [printf "failover %s" i]) |
506 | e4f08c46 | Iustin Pop | else |
507 | e4f08c46 | Iustin Pop | (printf "f r:%s" d, |
508 | e4f08c46 | Iustin Pop | [printf "failover %s" i, |
509 | e4f08c46 | Iustin Pop | printf "replace-disks -n %s %s" d i]) |
510 | e4f08c46 | Iustin Pop | else |
511 | e4f08c46 | Iustin Pop | if d == a then {- ... and keep primary as secondary -} |
512 | e4f08c46 | Iustin Pop | (printf "r:%s f" c, |
513 | e4f08c46 | Iustin Pop | [printf "replace-disks -n %s %s" c i, |
514 | e4f08c46 | Iustin Pop | printf "failover %s" i]) |
515 | e4f08c46 | Iustin Pop | else |
516 | e4f08c46 | Iustin Pop | if d == b then {- ... keep same secondary -} |
517 | e4f08c46 | Iustin Pop | (printf "f r:%s f" c, |
518 | e4f08c46 | Iustin Pop | [printf "failover %s" i, |
519 | e4f08c46 | Iustin Pop | printf "replace-disks -n %s %s" c i, |
520 | e4f08c46 | Iustin Pop | printf "failover %s" i]) |
521 | e4f08c46 | Iustin Pop | |
522 | e4f08c46 | Iustin Pop | else {- Nothing in common -} |
523 | e4f08c46 | Iustin Pop | (printf "r:%s f r:%s" c d, |
524 | e4f08c46 | Iustin Pop | [printf "replace-disks -n %s %s" c i, |
525 | e4f08c46 | Iustin Pop | printf "failover %s" i, |
526 | e4f08c46 | Iustin Pop | printf "replace-disks -n %s %s" d i]) |
527 | e4f08c46 | Iustin Pop | |
528 | e4f08c46 | Iustin Pop | {-| Converts a solution to string format -} |
529 | e4f08c46 | Iustin Pop | printSolution :: InstanceList |
530 | e4f08c46 | Iustin Pop | -> [(Int, String)] |
531 | e4f08c46 | Iustin Pop | -> [(Int, String)] |
532 | e4f08c46 | Iustin Pop | -> [Placement] |
533 | e4f08c46 | Iustin Pop | -> ([String], [[String]]) |
534 | e4f08c46 | Iustin Pop | printSolution il ktn kti sol = |
535 | 671b85b9 | Iustin Pop | let |
536 | 671b85b9 | Iustin Pop | mlen_fn = maximum . (map length) . snd . unzip |
537 | 671b85b9 | Iustin Pop | imlen = mlen_fn kti |
538 | 671b85b9 | Iustin Pop | nmlen = mlen_fn ktn |
539 | 671b85b9 | Iustin Pop | pmlen = (2*nmlen + 1) |
540 | 671b85b9 | Iustin Pop | in |
541 | 671b85b9 | Iustin Pop | unzip $ map |
542 | c5c295bc | Iustin Pop | (\ (i, p, s, c) -> |
543 | 671b85b9 | Iustin Pop | let inst = Container.find i il |
544 | 671b85b9 | Iustin Pop | inam = fromJust $ lookup (Instance.idx inst) kti |
545 | 671b85b9 | Iustin Pop | npri = fromJust $ lookup p ktn |
546 | 671b85b9 | Iustin Pop | nsec = fromJust $ lookup s ktn |
547 | 671b85b9 | Iustin Pop | opri = fromJust $ lookup (Instance.pnode inst) ktn |
548 | 671b85b9 | Iustin Pop | osec = fromJust $ lookup (Instance.snode inst) ktn |
549 | 671b85b9 | Iustin Pop | (moves, cmds) = computeMoves inam opri osec npri nsec |
550 | 671b85b9 | Iustin Pop | ostr = (printf "%s:%s" opri osec)::String |
551 | 671b85b9 | Iustin Pop | nstr = (printf "%s:%s" npri nsec)::String |
552 | 671b85b9 | Iustin Pop | in |
553 | c5c295bc | Iustin Pop | (printf " %-*s %-*s => %-*s %.8f a=%s" |
554 | 671b85b9 | Iustin Pop | imlen inam pmlen ostr |
555 | c5c295bc | Iustin Pop | pmlen nstr c moves, |
556 | 671b85b9 | Iustin Pop | cmds) |
557 | 671b85b9 | Iustin Pop | ) sol |
558 | e4f08c46 | Iustin Pop | |
559 | e4f08c46 | Iustin Pop | -- | Print the node list. |
560 | e4f08c46 | Iustin Pop | printNodes :: [(Int, String)] -> NodeList -> String |
561 | e4f08c46 | Iustin Pop | printNodes ktn nl = |
562 | e4f08c46 | Iustin Pop | let snl = sortBy (compare `on` Node.idx) (Container.elems nl) |
563 | e4f08c46 | Iustin Pop | snl' = map (\ n -> ((fromJust $ lookup (Node.idx n) ktn), n)) snl |
564 | af53a5c4 | Iustin Pop | m_name = maximum . (map length) . fst . unzip $ snl' |
565 | af53a5c4 | Iustin Pop | helper = Node.list m_name |
566 | ced859f3 | Iustin Pop | header = printf "%2s %-*s %5s %5s %5s %5s %5s %3s %3s %7s %7s" |
567 | ced859f3 | Iustin Pop | "N1" m_name "Name" "t_mem" "f_mem" "r_mem" |
568 | ced859f3 | Iustin Pop | "t_dsk" "f_dsk" |
569 | ced859f3 | Iustin Pop | "pri" "sec" "p_fmem" "p_fdsk" |
570 | ced859f3 | Iustin Pop | in unlines $ (header:map (uncurry helper) snl') |
571 | e4f08c46 | Iustin Pop | |
572 | e4f08c46 | Iustin Pop | -- | Compute the mem and disk covariance. |
573 | d6be0775 | Iustin Pop | compDetailedCV :: NodeList -> (Double, Double, Double, Double) |
574 | e4f08c46 | Iustin Pop | compDetailedCV nl = |
575 | 0335fe4a | Iustin Pop | let |
576 | 0335fe4a | Iustin Pop | nodes = Container.elems nl |
577 | 0335fe4a | Iustin Pop | mem_l = map Node.p_mem nodes |
578 | 0335fe4a | Iustin Pop | dsk_l = map Node.p_dsk nodes |
579 | e4f08c46 | Iustin Pop | mem_cv = varianceCoeff mem_l |
580 | e4f08c46 | Iustin Pop | dsk_cv = varianceCoeff dsk_l |
581 | 34a6e127 | Iustin Pop | n1_l = length $ filter Node.failN1 nodes |
582 | 34a6e127 | Iustin Pop | n1_score = (fromIntegral n1_l) / (fromIntegral $ length nodes) |
583 | d6be0775 | Iustin Pop | res_l = map Node.p_rem nodes |
584 | d6be0775 | Iustin Pop | res_cv = varianceCoeff res_l |
585 | 34a6e127 | Iustin Pop | in (mem_cv, dsk_cv, n1_score, res_cv) |
586 | e4f08c46 | Iustin Pop | |
587 | e4f08c46 | Iustin Pop | -- | Compute the 'total' variance. |
588 | e4f08c46 | Iustin Pop | compCV :: NodeList -> Double |
589 | e4f08c46 | Iustin Pop | compCV nl = |
590 | d6be0775 | Iustin Pop | let (mem_cv, dsk_cv, n1_score, res_cv) = compDetailedCV nl |
591 | d6be0775 | Iustin Pop | in mem_cv + dsk_cv + n1_score + res_cv |
592 | e4f08c46 | Iustin Pop | |
593 | e4f08c46 | Iustin Pop | printStats :: NodeList -> String |
594 | e4f08c46 | Iustin Pop | printStats nl = |
595 | d6be0775 | Iustin Pop | let (mem_cv, dsk_cv, n1_score, res_cv) = compDetailedCV nl |
596 | d6be0775 | Iustin Pop | in printf "f_mem=%.8f, r_mem=%.8f, f_dsk=%.8f, n1=%.3f" |
597 | d6be0775 | Iustin Pop | mem_cv res_cv dsk_cv n1_score |
598 | e4f08c46 | Iustin Pop | |
599 | e4f08c46 | Iustin Pop | -- Balancing functions |
600 | e4f08c46 | Iustin Pop | |
601 | e4f08c46 | Iustin Pop | -- Loading functions |
602 | e4f08c46 | Iustin Pop | |
603 | e4f08c46 | Iustin Pop | {- | Convert newline and delimiter-separated text. |
604 | e4f08c46 | Iustin Pop | |
605 | e4f08c46 | Iustin Pop | This function converts a text in tabular format as generated by |
606 | e4f08c46 | Iustin Pop | @gnt-instance list@ and @gnt-node list@ to a list of objects using a |
607 | e4f08c46 | Iustin Pop | supplied conversion function. |
608 | e4f08c46 | Iustin Pop | |
609 | e4f08c46 | Iustin Pop | -} |
610 | e4f08c46 | Iustin Pop | loadTabular :: String -> ([String] -> (String, a)) |
611 | e4f08c46 | Iustin Pop | -> (a -> Int -> a) -> ([(String, Int)], [(Int, a)]) |
612 | e4f08c46 | Iustin Pop | loadTabular text_data convert_fn set_fn = |
613 | e4f08c46 | Iustin Pop | let lines_data = lines text_data |
614 | e4f08c46 | Iustin Pop | rows = map (sepSplit '|') lines_data |
615 | e4f08c46 | Iustin Pop | kerows = (map convert_fn rows) |
616 | e4f08c46 | Iustin Pop | idxrows = map (\ (idx, (k, v)) -> ((k, idx), (idx, set_fn v idx))) |
617 | e4f08c46 | Iustin Pop | (zip [0..] kerows) |
618 | e4f08c46 | Iustin Pop | in unzip idxrows |
619 | e4f08c46 | Iustin Pop | |
620 | 01f6a5d2 | Iustin Pop | -- | For each instance, add its index to its primary and secondary nodes |
621 | 01f6a5d2 | Iustin Pop | fixNodes :: [(Int, Node.Node)] |
622 | 01f6a5d2 | Iustin Pop | -> [(Int, Instance.Instance)] |
623 | 01f6a5d2 | Iustin Pop | -> [(Int, Node.Node)] |
624 | 01f6a5d2 | Iustin Pop | fixNodes nl il = |
625 | d4f62d4e | Iustin Pop | foldl' (\accu (idx, inst) -> |
626 | d4f62d4e | Iustin Pop | let |
627 | d4f62d4e | Iustin Pop | assocEqual = (\ (i, _) (j, _) -> i == j) |
628 | d4f62d4e | Iustin Pop | pdx = Instance.pnode inst |
629 | d4f62d4e | Iustin Pop | sdx = Instance.snode inst |
630 | d4f62d4e | Iustin Pop | pold = fromJust $ lookup pdx accu |
631 | d4f62d4e | Iustin Pop | sold = fromJust $ lookup sdx accu |
632 | d4f62d4e | Iustin Pop | pnew = Node.setPri pold idx |
633 | d4f62d4e | Iustin Pop | snew = Node.setSec sold idx |
634 | d4f62d4e | Iustin Pop | ac1 = deleteBy assocEqual (pdx, pold) accu |
635 | d4f62d4e | Iustin Pop | ac2 = deleteBy assocEqual (sdx, sold) ac1 |
636 | d4f62d4e | Iustin Pop | ac3 = (pdx, pnew):(sdx, snew):ac2 |
637 | d4f62d4e | Iustin Pop | in ac3) nl il |
638 | 01f6a5d2 | Iustin Pop | |
639 | a0529a64 | Iustin Pop | -- | Compute the longest common suffix of a [(Int, String)] list that |
640 | a0529a64 | Iustin Pop | -- | starts with a dot |
641 | a0529a64 | Iustin Pop | longestDomain :: [(Int, String)] -> String |
642 | a0529a64 | Iustin Pop | longestDomain [] = "" |
643 | a0529a64 | Iustin Pop | longestDomain ((_,x):xs) = |
644 | a0529a64 | Iustin Pop | let |
645 | a0529a64 | Iustin Pop | onlyStrings = snd $ unzip xs |
646 | a0529a64 | Iustin Pop | in |
647 | a0529a64 | Iustin Pop | foldr (\ suffix accu -> if all (isSuffixOf suffix) onlyStrings |
648 | a0529a64 | Iustin Pop | then suffix |
649 | a0529a64 | Iustin Pop | else accu) |
650 | a0529a64 | Iustin Pop | "" $ filter (isPrefixOf ".") (tails x) |
651 | a0529a64 | Iustin Pop | |
652 | a0529a64 | Iustin Pop | -- | Remove tails from the (Int, String) lists |
653 | a0529a64 | Iustin Pop | stripSuffix :: String -> [(Int, String)] -> [(Int, String)] |
654 | a0529a64 | Iustin Pop | stripSuffix suffix lst = |
655 | a0529a64 | Iustin Pop | let sflen = length suffix in |
656 | a0529a64 | Iustin Pop | map (\ (key, name) -> (key, take ((length name) - sflen) name)) lst |
657 | e4f08c46 | Iustin Pop | |
658 | e4f08c46 | Iustin Pop | {-| Initializer function that loads the data from a node and list file |
659 | e4f08c46 | Iustin Pop | and massages it into the correct format. -} |
660 | e4f08c46 | Iustin Pop | loadData :: String -- ^ Node data in text format |
661 | e4f08c46 | Iustin Pop | -> String -- ^ Instance data in text format |
662 | e4f08c46 | Iustin Pop | -> (Container.Container Node.Node, |
663 | e4f08c46 | Iustin Pop | Container.Container Instance.Instance, |
664 | a0529a64 | Iustin Pop | String, [(Int, String)], [(Int, String)]) |
665 | e4f08c46 | Iustin Pop | loadData ndata idata = |
666 | 01f6a5d2 | Iustin Pop | let |
667 | 01f6a5d2 | Iustin Pop | {- node file: name mem disk -} |
668 | e4f08c46 | Iustin Pop | (ktn, nl) = loadTabular ndata |
669 | 01f6a5d2 | Iustin Pop | (\ (i:jt:jf:kt:kf:[]) -> (i, Node.create jt jf kt kf)) |
670 | e4f08c46 | Iustin Pop | Node.setIdx |
671 | 01f6a5d2 | Iustin Pop | {- instance file: name mem disk -} |
672 | 01f6a5d2 | Iustin Pop | (kti, il) = loadTabular idata |
673 | 01f6a5d2 | Iustin Pop | (\ (i:j:k:l:m:[]) -> (i, |
674 | 01f6a5d2 | Iustin Pop | Instance.create j k |
675 | 01f6a5d2 | Iustin Pop | (fromJust $ lookup l ktn) |
676 | 01f6a5d2 | Iustin Pop | (fromJust $ lookup m ktn))) |
677 | 01f6a5d2 | Iustin Pop | Instance.setIdx |
678 | 01f6a5d2 | Iustin Pop | nl2 = fixNodes nl il |
679 | 01f6a5d2 | Iustin Pop | il3 = Container.fromAssocList il |
680 | e4f08c46 | Iustin Pop | nl3 = Container.fromAssocList |
681 | 01f6a5d2 | Iustin Pop | (map (\ (k, v) -> (k, Node.buildPeers v il3 (length nl2))) nl2) |
682 | a0529a64 | Iustin Pop | xtn = swapPairs ktn |
683 | a0529a64 | Iustin Pop | xti = swapPairs kti |
684 | a0529a64 | Iustin Pop | common_suffix = longestDomain (xti ++ xtn) |
685 | a0529a64 | Iustin Pop | stn = stripSuffix common_suffix xtn |
686 | a0529a64 | Iustin Pop | sti = stripSuffix common_suffix xti |
687 | e4f08c46 | Iustin Pop | in |
688 | a0529a64 | Iustin Pop | (nl3, il3, common_suffix, stn, sti) |