The Curious Incident of the API Call in the Night-Time

A client of ours has it bad. their service is hemorrhaging FLOPS for every API call – the reason: they need to figure out if exact time at the client’s reported location in order to determine desired behavior – this information is supplied by an external, remote service.

So here we have a clear case of “how” – we know who is to blame, we know what why, now all we need to do is figure out the best solution.

let’s look at the two common solutions on the service, maybe there is a hint there:

timezone polygons

  1. Every timezone is can be defined by a strict complex (poly-)polygon.
  2. Those polygons are held in memory, and updated from time to time.
  3. By determining in which polygon the given coordinates fit best, and applying that change to the arrival time of the location update, the service is able to determine the exact time in which the location was sent in local-time.

nearest known location

  1. We hold in memory a geographically sorted set (probably in an R-Tree or something of that sort) of cities (represented as either a central point, or a blocking rectangle) and their respective time zones.
  2. By determining the closest city we can approximate the time zone.
  3. Same as before, now that we know which timezone we are most likely to be in, we can extrapolate the time at the source of the location update.

Basically, nothing much to work with here – both algorithms demand some serious scans of large data structures, and as stateless  and embarrassingly parallel as they may be, the input is so minor no change we do can really make a difference with twicking what we send over the API.

 

Now that we know that, right off the bat there are two naive solutions:

internalize the service

This is the head on approach – the network is two slow? maybe the remote server is too busy? no problem! fix both by developing (or downloading and integrating) the mechanism to do all of that work locally.

pro:  This will probably yield fast performance

con: Add moving parts to an existing system, possibly with parts that need updating from time to time (never mind the possible bugs)

ask the user

This is as simplistic – The user knows their local time, why wouldn’t he sent it over?

pro: simple, straight forward, minimal code change

con: demands an API change, which in our case was a major No-No

Seems that of the time being, we really have no other option than just write some code.. This is tragic no matter how you look at it – not only it’s stopping us from reading our way back to #1 of XKCD, but we also have no clue how to do this.

give it a guess

A third option (or forth, or fifth, depending how you count) is to make an educated guess to whether it is night or day. You know, it’s not like there is a second you can just say “aaaaannd.. now it’s night”, it’s more of a spectrum and if you make “small” mistakes it’s OK.

After reading this answer on Stack Overflow where some guy named Jonah is reaping on the idea of computation only models for determining time zone (and rightly so), inspiration struck. Maybe we don’t really need to determine exact time, but more of “location of sun in the sky” kind of thing, this is easily done computationally with the exact method Jonah is stating as a wrong solution, so that what we did.

This project is in python, so here is the new code:

Simple enough. Under 10 lines, tested well, and deployed under 30 min from encountering the problem.

The trick

What we did here can (as always) be mapped into three distinct steps:

  1. Figure out what is exactly the problem you are trying to solve and what assumptions you may have about it.
  2. Figure out all the possible (and impossible) solutions for the problem.
  3. Figure out what’s good (for you!) and bad (for you!) about each of them And make your choice, but stay alert for new solutions you haven’t thought of. If any arise – return to 1.

What assumptions do you have about the problem you work on right now? Are they essential? Email me or comment below.

 

 

Adam Lev-Libfeld

A long distance runner, a software architect, an HPC nerd (order may change).

Latest posts by Adam Lev-Libfeld (see all)

The Curious Incident of the API Call in the Night-Time

Leave a Reply

Your email address will not be published. Required fields are marked *