MachineTypeChange.scala

/**
 * How to convert a distributed fleet from what type of hardware to
 * another without degrading (too much) your service.
 *
 */

case class Machine(name: String, ECU: Double, mem: Int, disk: Int, TCO: Float)
object Machine {
  val m1Xlarge = Machine("m1.xlarge", ECU = 1, mem = 7, disk = 700, TCO = 600)
  val m2Xlarge = Machine("m2.xlarge", ECU = 2.6, mem = 14, disk = 1400, TCO = 400)
}

object MachineTypeChange {

  import Machine._
  val incStep = 10
  val decStep = 10
  val cfgStep = 1
  val degradationServiceTolerance = .75
  val maxConns = 3000
  val connsVariance = 10

  case class Fleet(size: Int, hwType: Machine) {
    override def toString = s"${hwType.name} * $size"
  }
  val from = new Fleet(size = 90, hwType = m1Xlarge)
  val to = new Fleet(size = 60, hwType = m2Xlarge)

  case class Config(nbProcessesPerBox: Int) {
    override def toString = s"#proc: $nbProcessesPerBox"
  }
  val initialConfig = new Config(12)

  case class State(f1: Fleet, f2: Fleet, cfg: Config) {
    def nbConns = cfg.nbProcessesPerBox * (f1.size + f2.size)
    override def toString = s"State($f1, $f2, $cfg, $nbConns conns)"
  }
  val initialState = new State(from, to.copy(size = 0), initialConfig)

  sealed trait Operation {
    def change(s: State): State
  }
  case class Increase(n: Int) extends Operation {
    def change(s: State) = s.copy(f2 = s.f2.copy(size = s.f2.size + n))
  }
  case class Decrease(n: Int) extends Operation {
    def change(s: State) = s.copy(f1 = s.f1.copy(size = s.f1.size - n))
  }
  case class ConfigIncreaseDbConn(n: Int) extends Operation {
    def change(s: State) =
      s.copy(cfg = s.cfg.copy(nbProcessesPerBox = s.cfg.nbProcessesPerBox + n))
  }

  /**
   * deliver the possible moves with an affinity for the one in arg
   * by putting it first
   */
  def moves(head: Option[Operation]) = {
    val allMoves = List(
      Increase(to.size / (incStep/2)),
      Decrease(from.size / (decStep/2)),
      Increase(to.size / incStep),
      Decrease(from.size / decStep),
      ConfigIncreaseDbConn(cfgStep)
    )
    head map { m => m :: allMoves.filter(_ != m) } getOrElse allMoves
  }

  class Path(history: List[Operation], val state: State) {
    def extend(o: Operation) = new Path(o :: history, o change state)
    /**
     * build a compressed history where contiguous operations of the
     * same kind are merged into one
     */
    lazy val compress = (List[Operation]() /: history){
      case (Increase(i) :: ls, Increase(j)) => Increase(i+j) :: ls
      case (Decrease(i) :: ls, Decrease(j)) => Decrease(i+j) :: ls
      case (ConfigIncreaseDbConn(i) :: ls, ConfigIncreaseDbConn(j)) =>
        ConfigIncreaseDbConn(i+j) :: ls
      case (ls, o) => o :: ls
    }
    def lastOp: Option[Operation] = history.headOption
    override def toString = compress.size +" steps: \n" +
      (compress mkString " ") + "\n --> " + state
  }
  val initialPath: Path = new Path(List(), initialState)

  val allTimeConstraints: List[State => Boolean] = List(
    _.nbConns < maxConns,
    _.nbConns > initialState.nbConns * degradationServiceTolerance,
    _.f1.size >= 0,
    _.f2.size <= to.size
  )

  def from(paths: Set[Path], seenStates: collection.mutable.Set[State])
      : Stream[Set[Path]] =
    if (paths.isEmpty) Stream.empty
    else {
      val more = for { path <- paths
                       p    <- moves(path.lastOp) map path.extend
                       if !(seenStates contains p.state) &&
                         (true /: allTimeConstraints)(_ && _(p.state))
      } yield {
        seenStates += p.state
        p
      }
      if (more.isEmpty) sys.error("no solutions")
      else paths #:: from(more, seenStates)
    }
  val paths = from(Set(initialPath), collection.mutable.Set(initialState))

  // def isGood(s: State): Boolean = s.f1.size == 0
  def isGood(s: State): Boolean =
    s.f1.size == 0 && s.f2.size == to.size &&
      math.abs(s.nbConns - initialState.nbConns) < connsVariance

  def solution: Stream[Path] =
    for { ps <- paths
          p  <- ps if isGood(p.state)
    } yield p

  def main(args: Array[String]): Unit = println(solution.head)

}