title: Scalable delayed task execution with Redis
body: <p>I need to design a Redis-driven scalable task scheduling system.</p>
  
  <p>Requirements:</p>
  
  <ul>
  <li>Multiple worker processes.</li>
  <li>Many tasks, but long periods of idleness are possible.</li>
  <li>Reasonable timing precision.</li>
  <li>Minimal resource waste when idle.</li>
  <li>Should use synchronous Redis API.</li>
  <li>Should work for Redis 2.4 (i.e. no features from upcoming 2.6).</li>
  <li>Should not use other means of RPC than Redis.</li>
  </ul>
  
  <p>Pseudo-API: <code>schedule_task(timestamp, task_data)</code>. Timestamp is in integer seconds.</p>
  
  <p>Basic idea: </p>
  
  <ul>
  <li>Listen for upcoming tasks on list.</li>
  <li>Put tasks to buckets per timestamp. </li>
  <li>Sleep until the closest timestamp. </li>
  <li>If a new task appears with timestamp less than closest one, wake up.</li>
  <li>Process all upcoming tasks with timestamp ≤ now, in batches (assuming
  that task execution is fast). </li>
  <li>Make sure that concurrent worker wouldn't process same tasks. At the same time, make sure that no tasks are lost if we crash while processing them.</li>
  </ul>
  
  <p>So far I can't figure out how to fit this in Redis primitives...</p>
  
  <p>Any clues?</p>
  
  <p><em>Note that there is a similar old question: <a href="https://stackoverflow.com/questions/4138951/delayed-execution-scheduling-with-redis">Delayed execution / scheduling with Redis?</a> In this new question I introduce more details (most importantly, many workers). So far I was not able to figure out how to apply old answers here — thus, a new question.</em></p>