Problem of the Day
A new programming or logic puzzle every Mon-Fri

That one side project you've been working on for years has finally taken off and now you need to think about load balancing. To handle the additional load you scale from 1 to 4 servers. Your servers have different specs so they can each handle a different amount of requests. You realize you need some load balancing software to handle this so you set off to build some.

Server 1: 357 requests
Server 2: 651 requests
Server 3: 101 requests
Server 4: 230 requests

Requests always fill based on which server is most empty (current requests/total capacity). You can decide how to handle ties. Unfortunately, since today is April Fool's Day, someone introduced a bug into your code which is causing an issue with removing requests from each servers' queue. A request is removed from a random server after every 10 requests made to the load balencer. Eventually you won't be able to handle all the traffic you're getting and when this happens simply print out "Happy April Fools" and you're done.

Comments:

• Daniel - 10 years, 9 months ago

  My entry in C# using the same function I created to get the smallest integer a week or so ago. With a bit of debug code to watch to the process.

  public class LoadBalancer
  {
      private int mintServer1 = 0;
      private int mintServer2 = 0;
      private int mintServer3 = 0;
      private int mintServer4 = 0;
  
      private int mintServer1max = 357;
      private int mintServer2max = 651;
      private int mintServer3max = 101;
      private int mintServer4max = 230;
  
      private bool mblnRun = true;
      private int mintCount = 0;
      private int mintTotalCount = 0;
  
      public void Balance()
      {
          while (mblnRun)
          {
              Add();
              mintCount++;
              if (mintCount == 10) Drop();
              if ((mintServer1 == mintServer1max) && (mintServer2 == mintServer2max) && (mintServer3 == mintServer3max) && (mintServer4 == mintServer4max))
              {
                  mblnRun = false;
              }
  
          }
          Console.WriteLine("Happy April Fools");
          Console.ReadKey();
      }
      private void Drop()
      {
          mintCount = 0;
          mintTotalCount++;
          System.Random r = new System.Random();
          int i = r.Next(1, 100);
          if (i >= 1 && i <= 25) mintServer1--;
          if (i >= 26 && i <= 50) mintServer2--;
          if (i >= 51 && i <= 75) mintServer3--;
          if (i >= 76 && i <= 100) mintServer4--;
          Console.WriteLine(String.Format("Connection dropped from server {0}", (i >= 1 && i <= 25 ? "1" : (i >= 26 && i <= 50 ? "2" : (i >= 26 && i <= 50 ? "3" : "4")))));
          ShowCount();
      }
      private void Add()
      {
          mintTotalCount++;
          int i = FindLowest();
          if (i == 1) mintServer1++;
          if (i == 2) mintServer2++;
          if (i == 3) mintServer3++;
          if (i == 4) mintServer4++;
          Console.WriteLine(String.Format("New connection added to server {0} - Total Connections {1}", i.ToString(), mintTotalCount.ToString()));
          ShowCount();
      }
  
      private int FindLowest()
      {
          double dblS1 = ((double)mintServer1 / (double)mintServer1max) * 1000;
          double dblS2 = ((double)mintServer2 / (double)mintServer2max) * 1000;
          double dblS3 = ((double)mintServer3 / (double)mintServer3max) * 1000;
          double dblS4 = ((double)mintServer4 / (double)mintServer4max) * 1000;
          int i = Min((int)dblS1, Min((int)dblS2, Min((int)dblS3, (int)dblS4)));
          return (i == (int)dblS1 ? 1 : (i == (int)dblS2 ? 2 : (i == (int)dblS3 ? 3 : 4)));
      }
  
      private int Min(int x, int y)
      {
          return y + ((x - y) & ((x - y) >> (sizeof(int) * 8 - 1)));
      }
  
      private void ShowCount()
      {
          Console.WriteLine(String.Format("Connections: {0}/{1} - {2}/{3} - {4}/{5} - {6}/{7}", mintServer1.ToString(), mintServer1max.ToString(), mintServer2.ToString(), mintServer2max.ToString(), mintServer3.ToString(), mintServer3max.ToString(), mintServer4.ToString(), mintServer4max.ToString()));
      }
  }
  

  reply permalink

• Pyro - 10 years, 9 months ago

  My solution in python!

  from random import randint
  
  Server_load=[0,0,0,0]
  Server_max=[357,651,101,230]
  Server_relation=[0,0,0,0]
  Server_full=[False,False,False,False]
  
  flag=False
  n=0
  n_server=0
  
  while flag==False:
      n=n+1
      for i in range (4):
          if Server_full[i]==False:
              Server_relation[i]=(float(Server_load[i]))/Server_max[i]
              if Server_relation[i]==1:
                  Server_full[i]=True
      if sum(Server_full)==4:
          print "Happy April Fools!"
          break
      i=Server_relation.index(min(Server_relation))
      Server_load[i]=Server_load[i]+1
      print Server_load
      print Server_relation
      if n==10:
          n_server=randint(0,3)
          Server_load[n_server]=Server_load[n_server]-1
          print "Bug!"
          print Server_load
          n=0
  

  reply permalink

• Anonymous - 10 years, 9 months ago

  package main
  
  import "fmt"
  
  func main() {
      //HA! that one side project I've been working on will never take off!
      fmt.Println("Happy April Fools")
  }
  

  reply permalink

• Hueho - 10 years, 9 months ago

  Nobody will ever know!

  reply permalink

• Greg - 10 years, 9 months ago

  Okay, gonna try this formatting thing again today...

  object Main extends App {
    val bal = Balancer
    var count = 0
    while(!bal.fullCheck){
      if (count < 10) {
        bal.request
        count += 1
      } else {
        bal.disconnect
        count = 0
      }
    }
    println("Happy April Fools!")
  }
  
  class Server(val max : Int, var current : Int){
    def join {if (current <= max) current+= 1}
    def ServerIsFull = {
       val isFull = current == max
       isFull
    }
    def leave {if (current > 0) current -= 1}
  }
  
  object Balancer{
    val servers = Array(new Server(357, 0),  new Server(651, 0), new Server(101, 0), new Server(230, 0))
  
    def request{
      var server = servers(1)
      for(s <- servers if s.current.toFloat/s.max.toFloat < server.current.toFloat/server.max.toFloat) server = s
      server.join
      println("Connect: " + server.current + " " + server.max)
    }
  
    def disconnect{
      val rando = scala.util.Random
  
      val num = rando.nextInt(servers.length)
      var server = servers(num);
      while(server.current == 0) server = servers(rando.nextInt(servers.length))
      server.leave
      println("Disconnect: " + server.current + " " + server.max)
    }
  
    def fullCheck = {
      var allFull = true
      for(s <- servers if !s.ServerIsFull) allFull = false
      allFull
    }
  }
  

  reply permalink

• Jt - 10 years, 9 months ago

  C#, here's what I came up with

  namespace ProblemOtd
  {
    using System;
    using System.Collections.Generic;
    using System.Linq;
  
    class Program
    {
      private static List<WebServer> WebServers = new List<WebServer>();
      private static long RequestsAdded;
  
      static void Main(string[] args)
      {
        WebServers.Add(new WebServer(357));
        WebServers.Add(new WebServer(651));
        WebServers.Add(new WebServer(101));
        WebServers.Add(new WebServer(230));
  
        try
        {
          while (1 == 1)
          {
            AddRequest();
            RequestsAdded++;
  
            if (RequestsAdded > 1 && (RequestsAdded - 1) % 10 == 0)
            {
              Random random = new Random();
              List<WebServer> usedWebServers = WebServers.Where(server => server.Usage > 0).ToList();
              usedWebServers[random.Next(0, usedWebServers.Count() - 1)].RemoveRequest();
            }
  
            PrintStatus();
          }
        }
        catch
        {
          Console.WriteLine("Happy April Fools");
        }
  
        Console.WriteLine("Finished press enter to exit");
        Console.ReadLine();
      }
  
      private static void AddRequest()
      {
        double minUsage = WebServers.Min(server => server.Usage);
        WebServer webServer = WebServers.First(server => server.Usage == minUsage);
        webServer.AddRequest();
      }
  
      private static void PrintStatus()
      {
        foreach (WebServer webServer in WebServers)
        {
          Console.WriteLine(string.Format("{0} / {1}", webServer.CurrentRequests, webServer.MaxRequests));
        }
  
        Console.WriteLine();
      }
  
      private class WebServer
      {
        public WebServer(int maxRequests)
        {
          this.MaxRequests = maxRequests;
        }
  
        public double CurrentRequests { get; private set; }
        public double MaxRequests { get; private set; }
        public double Usage
        {
          get
          {
            return CurrentRequests / MaxRequests;
          }
        }
  
        public void AddRequest()
        {
          if (this.CurrentRequests + 1 > this.MaxRequests)
          {
            throw new Exception("Server Full, can't take any more requests");
          }
  
          this.CurrentRequests++;
        }
  
        public void RemoveRequest()
        {
          if (CurrentRequests <= 0)
          {
            throw new Exception("Server doesn't have any requests to remove");
          }
  
          this.CurrentRequests--;
        }
      }
    }
  }
  

  reply permalink

• Daniel - 10 years, 9 months ago

  I like the use of Linq in this one. Although I'd have never thought to throw an exception to print "Happy April Fools". Nice work. :)

  reply permalink

• Hueho - 10 years, 9 months ago

  class Server
  
    class ServerError < StandardError
      def initialize(server)
        @message = "Capacity exceeded for #{server.name}: #{server.capacity} max requests."
      end
    end
  
    attr_reader :capacity, :name
  
    def initialize(name, capacity)
      @capacity, @name = capacity, name
      @requests = []
    end
  
    def full?
      @requests.size == @capacity
    end
  
    def enqueue(req)
      raise ServerError.new if full?
      @requests.push req
      puts "[SERVER][#{@name}]Processing #{req}"
    end
  
    def dequeue
      @requests.shift
    end
  
    def load
      @requests.size.to_f / @capacity
    end
  
  end
  
  
  class LoadBalancer
  
    attr_reader :servers
  
    def initialize(servers = [])
      @servers = Array.new servers
    end
  
    def full?
      @servers.all?(&:full?)
    end
  
    def enqueue(req)
      return false if full?
  
      @servers.min_by { |s| s.load }.enqueue req
      return true
    end
  
  end
  
  # The mean hidden bug in some obscure file
  class LoadBalancer
  
    alias_method :old_full?, :full?
    alias_method :old_initialize, :initialize
  
    def initialize(*args)
      @bug = 0
      old_initialize(*args)
    end
  
    def full?
      if (@bug += 1) >= 10
        @servers.sample.dequeue
        @bug = 0
      end
      old_full?
    end
  end
  
  balance = LoadBalancer.new [
    Server.new('Uno', 357),
    Server.new('Dos', 651),
    Server.new('Tres', 101),
    Server.new('Quatro', 230)
  ]
  
  counter = 0
  counter += 1 while balance.enqueue(rand 2**16)
  
  puts 'Happy April Fools!'
  puts "#{counter} requests served."
  

  reply permalink