title: Cache distribution exercise as presented at googles HashCode 2017
body: <p>I'm currently trying to find an efficient solution to the problem stated in this document <a href="https://hashcode.withgoogle.com/2017/tasks/hashcode2017_qualification_task.pdf" rel="nofollow noreferrer">Hash Code 2017 - Streaming Videos</a>.</p>
  
  <blockquote>
    <p><strong>TLDR;</strong> To minimize latency of youtube videos, cache serves with limited
    capacity are used. However not every cache is connected to every
    endpoint and not every entpoint requests the same videos. The goal is
    to minimize overall latency of the whole network.</p>
  </blockquote>
  
  <p><a href="https://i.stack.imgur.com/cEQH5.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/cEQH5.png" alt="simplified model of the cache architecture"></a></p>
  
  <p>My approach was to simply iterate through each endpoint and each requests block and find the optimal cache with the most <strong>latency reduction</strong> per video size <em>(I'll just call it <strong>request density</strong>)</em>.</p>
  
  <p>When the optimal cache has already reached its capacity, I try to store it in exchange for videos with less <strong>request density</strong> or use a different cache if there is no other possibility <em>(notice that the data center is also a cache in my model)</em>.</p>
  
  <pre><code>def distribute_video_requests(endpoint, excluding_caches=set()):
      caches = endpoint.cache_connections - excluding_caches
  
      for vr in endpoint.video_requests:
          optimal_cache = find_optimum(caches, vr)
  
          exchange = try_put(optimal_cache, vr)
  
          if exchange["conflicting"]:
              excluding_caches.add(optimal_cache)
  
              for elm in exchange["affected"]:
                  distribute_video_requests(elm["from"], excluding_caches)
  
  
  for ep in endpoints:
      distribute_video_requests(ep)
  </code></pre>
  
  <p>You could visualize it as <a href="https://en.wikipedia.org/wiki/Granular_convection" rel="nofollow noreferrer">Brazil nut effect</a> where the video requests are pieces with different density which are sorted in a stack.</p>
  
  <p>The reason I'm explaining all of this is because I can't realy tell if my solution is decent and if it isn't: what are better approaches for this?</p>