Skip to content

Instantly share code, notes, and snippets.

@philipithomas
Last active August 29, 2015 14:20
Show Gist options
  • Save philipithomas/f0d8dd58d94013504a93 to your computer and use it in GitHub Desktop.
Save philipithomas/f0d8dd58d94013504a93 to your computer and use it in GitHub Desktop.
Docker Container Scheduling as a Knapsack Problem in Julia/JuMP
using JuMP
using Cbc
#=
We pass in the variable "pools" in this format that goes through a separate
pre-processing script that pipes JSON to a Julia JSON loader.
{
"awesome-pool-prod": {
"quantity": 3, // Number of containers in the pool
"memory": 1000, // Megabytes
"cpu": 30, // Average cpu utilization in units of "percentage of a core"
"inbound": 3.14159, // MB/s
"outbound": 2.7182818 // MB/s
},
{
"awesome-pool-stage": {
"quantity": 1,
"memory": 303,
"cpu": 11.2,
"inbound": 3.14159,
"outbound": 2.7182818
}
}
=#
# Build a list of the string keys of the pools. This allows us to identify
# each pool with an integer index, and we can convert that index to the
# pool string id by using i_keys[i]
i_keys = collect(keys(pools))
pool_count = length(pools)
m = Model(
# CBC solver is open-soucre. Use an MILP solver of your choice.
solver=CbcSolver(
threads=Base.CPU_CORES,
)
)
# Main decision variable
# How many instances from a pool are assigned to each host
@defVar(m, x[1:pool_count, 1:HOST_COUNT] >= 0, Int)
# Secondary decision variable - the max cpu usage across hosts
@defVar(m, cpu_ceil <= HOST_PROCESSOR)
for i in 1:pool_count
# Constraint one: Assign each container in a pool to a host.
@addConstraint(m,
pools[i_keys[i]]["quantity"] == sum{x[i, j], j=1:HOST_COUNT}
)
# Constraint 2: Basically "No containers from the same pool on same host",
# but scaled to pool_count > HOST_COUNT
ceiling = ceil(pools[i_keys[i]]["quantity"] / HOST_COUNT)
for j in 1:HOST_COUNT
setUpper(x[i, j], ceiling)
end
end
for j in 1:HOST_COUNT
@addConstraints(m, begin
# Note: All variable that end with "_LIMIT" are a multiple times the actual
# host capacity in order to account for fluctuations. I used limit = .6 * capacity.
# Constraint 3: Memory
sum{pools[i_keys[i]]["memory"] * x[i, j], i=1:pool_count; pools[i_keys[i]]["inbound"] > 0} <= HOST_MEMORY_LIMIT
# Constraint 4: Inbound bandwidth
sum{pools[i_keys[i]]["inbound"] * x[i, j], i=1:pool_count; pools[i_keys[i]]["inbound"] > 0} <= HOST_INBOUND_LIMIT
# Constraint 5: Outbound bandwidth
sum{pools[i_keys[i]]["outbound"] * x[i, j], i=1:pool_count; pools[i_keys[i]]["outbound"] > 0} <= HOST_OUTBOUND_LIMIT
# Constraint 5: Total CPU usage. Note that it is less than a variable
# that we minimize.
sum{pools[i_keys[i]]["cpu"] * x[i, j], i=1:pool_count; pools[i_keys[i]]["cpu"] > 0} <= cpu_ceil
end)
end
# Overall goal: Minimize the highest CPU usage across hosts.
@setObjective(m, Min, cpu_ceil)
status = solve(m)
if status != :Optimal
println("Infeasible. Try adding more hosts.")
exit(1)
end
# Format results by calling getValue() on the variables
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment