Skip to content
Fetching contributors…
Cannot retrieve contributors at this time
371 lines (245 sloc) 10.6 KB

<2011-09-13 Tue 20:42>

Problem

Scheduling as an HTTP service: Users can request via an HTTP service that jobs be scheduled for periodic execution. These jobs are themselves HTTP endpoints. Users can do normal CRUD operations on schedules - create schedules, list schedules, show schedule details, delete schedules.

The requirements and scope are specifically vague - feel free to approach it however you’d like in terms of language, framework, (non)-persistence, depth, etc. It would be nice to see it deployed to Heroku/Cedar though (:

The idea with the project is just to see how you approach the types of problems that we work on here at Heroku. Hopefully you find it fun as well. Don’t feel like you need to spend too long on this - even doing a solid job on a small piece of it would be interesting to see. In fact I would suggest timeboxing yourself to a small amount of time for v1.

High Level

  • Clojure web
  • Cron?
  • java.util.Timer (wrapped)

Restrictions

  • The same URI can’t be scheduled twice, even for different periods
    • Scaling and thread management implications.
  • SLA?

V1

  • Soft timing requirements, we’ll do our best to schedule jobs on time, but no guarantees.
  • Highly imperative (side effect city) :(.

todo

  • Set timeout on http request
  • Using an async http client should allow a high request cap.
  • Human readable input format (10 seconds / 10 s vs 10000)
  • Log data should be cleaned on input (ie don’t log a start lag of 1 bil ms)
  • Cleaner separation between presentation / persistence
  • Human readable worker names
  • Make database interaction less brittle (have to remember to :upsert? false).
  • Allow view of historical data for deleted endpoints.
  • Better error handling (even though heroku will restart crashed workers)

High Level

  • Scales nicely
  • Jobs are picked up from total restart nicely

Scheduler Ideas

  • Executor per delta
    • {10000 #(run-10-second-period 10-second-period-jobs)}

I’m not familiar with idiomatic ways to temporally scheule events in clojure / java (other than libraries). However, some of the potential pitfalls I can see:

  • Thread starvation.
    • Through soft testing I’ve found that Heroku web processes are capped somewhere between 20-80 threads.
    • The most straightforward way to spin off jobs on a constant time delta would be to use agents. However, I’ll have to look into how to cap agent thread pools. This is also a source of skew:
      • Say we’ve got 1 thread executing 10 jobs that take 1 second to run, and these jobs are scheduled every 1 second (all of them). Using agents would allow us to execute these requests in parallel, but too many jobs at the same time would exhaust the thread pool and skew job start times.
  • Error Propagation.
    • Job execution start time should not be affected by the run time of jobs.

Timers use a single thread for running tasks, so need to spawn a thread to do the actual http call.

Resources

  • Network Sockets
  • Threads
  • Memory

Changes

Initially, I was allowing the same endpoint for multiple periods, but this seems like it would just a source of confusion for end users.

Switch to ScheduledThreadPoolExecutor

Entry Points

CRUD

Read – GET /<url>/<timeout> Create – PUT /<url>/<timeout> Delete – DELETE /<url>/<timeout>

No need for update at this point, url + timeout is a unique entry. However, it seems like this is wrong conceptually.

Error Handling

  • How to handle errors?
  • Malformed URLS
  • 4xx / 5xx errors

Config

min-period – smallest allowable period max-period – largest allowable period entpoint-timeout – timeout for http endpoint requests (in ms).

~~~~~~~~~

Cancelation?

The use of filter is an O(n) operation, might be better to use a constant time removal of jobs.

Duplicate uris (uris as keys?)

Changing it up, jobs are represented as maps, no longer functions.

Auto cleanup of timers (removal if no jobs run)?

Urls

/3000/http%3A%2F%2Fgoogle.com

Thread tracking – each URI represents one thread, so max of x URIs per server.

Thread overhead: Jetty 2 Timer 1 URLs rest

Scaling Out Naptime

Correct operation is the number one priority, jobs cannot go unworked(?).

Failure Scenarios

Thread Starvations

  • (agents)

Could restrict period to a multiple of greater than the maximum http timeout, then the maximum number of URIs per period is equal to the maximum threads allowed by a heroku web process.

  • Jobs can only be scheduled in 5 second increments.
    • Provides garunty (sp?!) around no thread errors and no jobs starting way after scheduled time.
  • If you pass in a value that’s not mod 5, it rounds up to the next mod

5.

  • Double ended check, check central hash once for existence of URL, if not found create.
  • Worker process actually does the checking.
  • Need a distributed hash with locking.
  • Workers have a polling loop and are responsible for knowing how “full” they are. So when they’re full they don’t pull any more urls off the of the queue.

Workers responsible for pulling work, need distributed locking hash.

How to handle node failure?

Ok, a lot churn here, but I think it’s best to ditch the timer mechanism and go with a mongo-backed solution.

Using mongo as the coordination mechanism will allow a cleaner, worker-focused implementation, meaning the rate at which work is consumed is as fast as the worker can consume work, where the knowledge of how much capacity the worker has is contained.

Here’s the new look:

Workers will have a run loop.

At the beginning of the run loop, the worker will check to see if it has any free threads to do http queries.

If so, the worker will fetch-update from mongo where the last run time is greater than the job’s period. The fetch-update will atomically update the last run time to the current time, so that two workers can’t pull the same job.

Next the worker will atomically increment a counter (used capacity), and execute the job.

At the end of the run loop, the used capacity counter gets decremented.

Failure levers

  • Pulling smallest last-run-period delta gives you more correct periodic execution (jobs where the delta is large don’t get run when you’re over capacity)
  • Pulling largest last-run-period delta runs all jobs eventually, but possible way off of what their period is.

In a nutshell, are dropped jobs or late jobs better?

With this method, errors do propagate, but I think that’s ok for V1. Potential ways of handling this are:

  • tracking start time modulo period, and adjusting last execution time to pare down drift.
  • tracking error delta and adjusting last execution time to pare down drift.

The nice thing about not caring about error is that eventually jobs will naturally be distributed into a steady state that minimizes this error.

Lock Timeouts

First pass is same lock timeout for all jobs. It would be nice to have a lock timeout per job, but not as simple due to the fact that the lock timeout has to be set atomically at the time of locking, else a failure between grabbing the lock and setting the timeout is, however unlikely, possible.

Could update expiry after the atomic op, but the gap still exists.

A lock expiry (current-time + default-lock-timeout) could be set, then a better lock expiry (current-time + period) could be set soon after.

So what happens when the lock timeout is hit?

  • lock expiry cleared
  • leave last :next-update?
    • Yes, lock expirys are hit only when the worker fails, either catastrophically, or due to a long request. There’s the potential for strangeness when job periods are longer than the lock timeout (request is still pending, but the job is unlocked and available for another worker to pick up. This is solved (is it?) by lock timeout >= period.

Not quite happy with this yet, I’ll be happier when I can implement lock expiry based on period.

Atomic Operations

  • schedule endpoint
  • unschedule endpoint
  • update last execution time

Maybe calculate next run time at last execution time.

find one where next execution is less than than current time Execute it, and calculate next execution time.

Pruning of jobs can be done either in the worker process or in a secondary process, nice to have flexibility here.

<2011-09-21 Wed 12:14>

Getting rid of with-next-job… It’s confusing and dosen’t work well, because everything that happens to the job needs to be done in the future anyway.

I need a better way to split out what’s done to the job (from user), from how the coordination is handled (from system).

Basically, the future needs to be part of with-next-job (renamed to run-job). Better, because:

  1. nil can be handled instead of passing that off to the calling code.
  2. Used capacity atom management dosen’t have to be handled by user either.

Might get rid of the used-capacity-atom by using some implicit mechanism?

Recursion? Data struture? Lazy seq? Queues?

The underlying problem is that my mental model collects this flow that’s spread across multiple procecesses into one “unit”.

<2011-09-28 Wed 21:12>

Better Statistics

ATM the stats are very rudamentry, and the displayed history is n-dependent (last n entries are shown) instead of time-dependent (last m seconds are shown), and I’d like to have the latter..

This boils down to 2 problems, conversion from n-domain to time-domain, and rendering of time domain.

N-Domain to Time-Domain

Bucketing mechanism – Stats are inserted into buckets by each worker, should resolution be stored along side so that

Bucket on key:

(/ TIMESTAMP 1000) => second bucket (/ TIMESTAMP (* 1000 60) => minute bucket (/ TIMESTAMP (* 1000 60 60) => hour bucket

Collision after:

1317268189 (seconds) 21954470 (minutes)

diff: 1295313719 minutes ~ 2464 years, I’m cool with that.

So collision on keys between seconds and minutes after 2464 years.

Or just use different collections, but it’s nice to know this could all go in a single map if it needs to, plus entries are deleted out of the map, so what this really means is that data would have to be collected for 2400 years without stats calculation being run.

Just have to watch the 4 meg document limit for mongo.

Race condition is ok, because the data will get overwritten with the same data.

Process

  1. If on new bucket, process previous bucket and create new bucket.
  2. Delete

get-next-complete-bucket

Rendering

It’d be nice if the resolution can be increased/decreased, lets say min resolution of a datapoint is 1s and max is 1s * 60 * 60 * 24 = 86,400 s (1 day).

Ugh, returning 86k rows from the database is no fun.

So what if we average under a fixed resolution, say, second, minute, and hour.

Maybe show ‘last m units’ where m is fixed and units is one of [seconds minutes hours days whatever].

Jump to Line
Something went wrong with that request. Please try again.