load_balancing.py

This example looks at cloud load balancing to keep a service running in the cloud at reasonable cost by reducing the expense of running cloud servers, minimizing risk and human time due to rebalancing, and doing balance sleeping models across servers.

The different KPIs are optimized using multiobjective solve. This optimization is achieved by the minimize_static_lex() method.

  1# --------------------------------------------------------------------------
  2# Source file provided under Apache License, Version 2.0, January 2004,
  3# http://www.apache.org/licenses/
  4# (c) Copyright IBM Corp. 2015, 2018
  5# --------------------------------------------------------------------------
  6
  7# Source: http://blog.yhathq.com/posts/how-yhat-does-cloud-balancing.html
  8
  9from collections import namedtuple
 10
 11from docplex.mp.model import Model
 12
 13
 14# ----------------------------------------------------------------------------
 15# Initialize the problem data
 16# ----------------------------------------------------------------------------
 17class TUser(namedtuple("TUser", ["id", "running", "sleeping", "current_server"])):
 18    def __str__(self):
 19        return self.id
 20
 21
 22SERVERS = ["server002", "server003", "server001", "server006", "server007", "server004", "server005"]
 23
 24USERS = [("user013", 2, 1, "server002"),
 25         ("user014", 0, 2, "server002"),
 26         ("user015", 0, 4, "server002"),
 27         ("user016", 1, 4, "server002"),
 28         ("user017", 0, 3, "server002"),
 29         ("user018", 0, 2, "server002"),
 30         ("user019", 0, 2, "server002"),
 31         ("user020", 0, 1, "server002"),
 32         ("user021", 4, 4, "server002"),
 33         ("user022", 0, 1, "server002"),
 34         ("user023", 0, 3, "server002"),
 35         ("user024", 1, 2, "server002"),
 36         ("user025", 0, 1, "server003"),
 37         ("user026", 0, 1, "server003"),
 38         ("user027", 1, 1, "server003"),
 39         ("user028", 0, 1, "server003"),
 40         ("user029", 2, 1, "server003"),
 41         ("user030", 0, 5, "server003"),
 42         ("user031", 0, 2, "server003"),
 43         ("user032", 0, 3, "server003"),
 44         ("user033", 1, 1, "server003"),
 45         ("user034", 0, 1, "server003"),
 46         ("user035", 0, 1, "server003"),
 47         ("user036", 4, 1, "server003"),
 48         ("user037", 7, 1, "server003"),
 49         ("user038", 2, 1, "server003"),
 50         ("user039", 0, 3, "server003"),
 51         ("user040", 1, 2, "server003"),
 52         ("user001", 0, 2, "server001"),
 53         ("user002", 0, 3, "server001"),
 54         ("user003", 5, 4, "server001"),
 55         ("user004", 0, 1, "server001"),
 56         ("user005", 0, 1, "server001"),
 57         ("user006", 0, 2, "server001"),
 58         ("user007", 0, 4, "server001"),
 59         ("user008", 0, 1, "server001"),
 60         ("user009", 5, 1, "server001"),
 61         ("user010", 7, 1, "server001"),
 62         ("user011", 4, 5, "server001"),
 63         ("user012", 0, 4, "server001"),
 64         ("user062", 0, 1, "server006"),
 65         ("user063", 3, 5, "server006"),
 66         ("user064", 0, 1, "server006"),
 67         ("user065", 0, 3, "server006"),
 68         ("user066", 3, 1, "server006"),
 69         ("user067", 0, 1, "server006"),
 70         ("user068", 0, 1, "server006"),
 71         ("user069", 0, 2, "server006"),
 72         ("user070", 3, 2, "server006"),
 73         ("user071", 0, 1, "server006"),
 74         ("user072", 5, 3, "server006"),
 75         ("user073", 0, 1, "server006"),
 76         ("user074", 0, 1, "server006"),
 77         ("user075", 0, 2, "server007"),
 78         ("user076", 1, 1, "server007"),
 79         ("user077", 1, 1, "server007"),
 80         ("user078", 0, 1, "server007"),
 81         ("user079", 0, 3, "server007"),
 82         ("user080", 0, 1, "server007"),
 83         ("user081", 4, 1, "server007"),
 84         ("user082", 1, 1, "server007"),
 85         ("user041", 0, 1, "server004"),
 86         ("user042", 2, 1, "server004"),
 87         ("user043", 5, 2, "server004"),
 88         ("user044", 5, 2, "server004"),
 89         ("user045", 0, 2, "server004"),
 90         ("user046", 1, 5, "server004"),
 91         ("user047", 0, 1, "server004"),
 92         ("user048", 0, 3, "server004"),
 93         ("user049", 5, 1, "server004"),
 94         ("user050", 0, 2, "server004"),
 95         ("user051", 0, 3, "server004"),
 96         ("user052", 0, 3, "server004"),
 97         ("user053", 0, 1, "server004"),
 98         ("user054", 0, 2, "server004"),
 99         ("user055", 0, 3, "server005"),
100         ("user056", 3, 1, "server005"),
101         ("user057", 0, 3, "server005"),
102         ("user058", 0, 2, "server005"),
103         ("user059", 0, 1, "server005"),
104         ("user060", 0, 5, "server005"),
105         ("user061", 0, 2, "server005")
106         ]
107
108# ----------------------------------------------------------------------------
109# Prepare the data for modeling
110# ----------------------------------------------------------------------------
111DEFAULT_MAX_PROCESSES_PER_SERVER = 50
112
113
114def _is_migration(user, server):
115    """ Returns True if server is not the user's current
116        Used in setup of constraints.
117    """
118    return server != user.current_server
119
120
121# ----------------------------------------------------------------------------
122# Build the model
123# ----------------------------------------------------------------------------
124
125def build_load_balancing_model(servers, users_, max_process_per_server=DEFAULT_MAX_PROCESSES_PER_SERVER, **kwargs):
126    m = Model(name='load_balancing', **kwargs)
127
128    # decision objects
129
130    users = [TUser(*user_row) for user_row in users_]
131
132    active_var_by_server = m.binary_var_dict(servers, name='isActive')
133
134    def user_server_pair_namer(u_s):
135        u, s = u_s
136        return '%s_to_%s' % (u.id, s)
137
138    assign_user_to_server_vars = m.binary_var_matrix(users, servers, user_server_pair_namer)
139
140    m.add_constraints(
141        m.sum(assign_user_to_server_vars[u, s] * u.running for u in users) <= max_process_per_server for s in servers)
142    # each assignment var <u, s>  is <= active_server(s)
143    for s in servers:
144        for u in users:
145            ct_name = 'ct_assign_to_active_{0!s}_{1!s}'.format(u, s)
146            m.add_constraint(assign_user_to_server_vars[u, s] <= active_var_by_server[s], ct_name)
147
148        # sum of assignment vars for (u, all s in servers) == 1
149        for u in users:
150            ct_name = 'ct_unique_server_%s' % (u[0])
151            m.add_constraint(m.sum((assign_user_to_server_vars[u, s] for s in servers)) == 1, ct_name)
152
153    number_of_active_servers = m.sum((active_var_by_server[svr] for svr in servers))
154    m.add_kpi(number_of_active_servers, "Number of active servers")
155
156    number_of_migrations = m.sum(
157        assign_user_to_server_vars[u, s] for u in users for s in servers if
158        _is_migration(u, s))
159    m.add_kpi(number_of_migrations, "Total number of migrations")
160
161    max_sleeping_workload = m.integer_var(name="max_sleeping_processes")
162    for s in servers:
163        ct_name = 'ct_define_max_sleeping_%s' % s
164        m.add_constraint(
165            m.sum(
166                assign_user_to_server_vars[u, s] * u.sleeping for u in users) <= max_sleeping_workload,
167            ct_name)
168    m.add_kpi(max_sleeping_workload, "Max sleeping workload")
169    # Set objective function
170    # m.minimize(number_of_active_servers)
171    m.minimize_static_lex([number_of_active_servers, number_of_migrations, max_sleeping_workload])
172
173    # attach artefacts to model for reporting
174    m.users = users
175    m.servers = servers
176    m.active_var_by_server = active_var_by_server
177    m.assign_user_to_server_vars = assign_user_to_server_vars
178    m.max_sleeping_workload = max_sleeping_workload
179
180    return m
181
182
183def lb_report(mdl):
184    active_servers = sorted([s for s in mdl.servers if mdl.active_var_by_server[s].solution_value == 1])
185    print("Active Servers: {0} = {1}".format(len(active_servers), active_servers))
186    print("*** User/server assignments , #migrations={0} ***".format(
187        mdl.kpi_by_name("number of migrations").solution_value))
188    # for (u, s) in sorted(mdl.assign_user_to_server_vars):
189    #     if mdl.assign_user_to_server_vars[(u, s)].solution_value == 1:
190    #         print("{} uses {}, migration: {}".format(u, s, "yes" if _is_migration(u, s) else "no"))
191    print("*** Servers sleeping processes ***")
192    for s in active_servers:
193        sleeping = sum(mdl.assign_user_to_server_vars[u, s].solution_value * u.sleeping for u in mdl.users)
194        print("Server: {} #sleeping={}".format(s, sleeping))
195
196
197def make_default_load_balancing_model(**kwargs):
198    return build_load_balancing_model(SERVERS, USERS, **kwargs)
199
200
201def lb_save_solution_as_json(mdl, json_file):
202    """Saves the solution for this model as JSON.
203
204    Note that this is not a CPLEX Solution file, as this is the result of post-processing a CPLEX solution
205    """
206    import json
207    solution_dict = {}
208    # active server
209    active_servers = sorted([s for s in mdl.servers if mdl.active_var_by_server[s].solution_value == 1])
210    solution_dict["active servers"] = active_servers
211
212    # sleeping processes by server
213    sleeping_processes = {}
214    for s in active_servers:
215        sleeping = sum(mdl.assign_user_to_server_vars[u, s].solution_value * u.sleeping for u in mdl.users)
216        sleeping_processes[s] = sleeping
217    solution_dict["sleeping processes by server"] = sleeping_processes
218
219# user assignment
220    user_assignment = []
221    for (u, s) in sorted(mdl.assign_user_to_server_vars):
222        if mdl.assign_user_to_server_vars[(u, s)].solution_value == 1:
223            n = {
224                'user': u.id,
225                'server': s,
226                'migration': "yes" if _is_migration(u, s) else "no"
227            }
228            user_assignment.append(n)
229    solution_dict['user assignment'] = user_assignment
230    json_file.write(json.dumps(solution_dict, indent=3).encode('utf-8'))
231
232# ----------------------------------------------------------------------------
233# Solve the model and display the result
234# ----------------------------------------------------------------------------
235
236if __name__ == '__main__':
237    lbm = make_default_load_balancing_model()
238
239    # Run the model.
240    lbs = lbm.solve(log_output=True)
241    lb_report(lbm)
242    # save json, used in worker tests
243    from docplex.util.environment import get_environment
244    with get_environment().get_output_stream("solution.json") as fp:
245        lb_save_solution_as_json(lbm, fp)
246    lbm.end()
247