‍Philip Clifton is a Senior Software Engineer 2 and Team Lead, responsible for guiding the overall implementation of Web technologies at FlightAware.

For many users of FlightAware, one of the most visible and visual experiences on the website are the maps, depicting flight data in various forms—individual flights, traffic to/from airports, and airline fleets. Perhaps the most visible application, however, is the FlightAware live map—a product that attempts to depict all en route aircraft around the world. Making this map function presents significant challenges—there can be upwards of 10,000 aircraft en route at any given time, and that’s a lot of data to fetch, process, transport to the client browser, and render. Each of these steps needs to work promptly and efficiently—after all, even the most compelling map depiction will lose some of its impact if users must wait 10+ seconds for the depiction to actually load!

Web maps and tiling

Before we get into the meat of these challenges, we’ll briefly discuss some mapping concepts. Web-based map products are ubiquitous these days thanks to tools like Google Maps, and with their popularity has come plenty of standardization in how maps work. Particularly pertinent to this discussion is how maps use tiles to provide a solid user experience.

When we talk about “tiles,” what we’re really talking about is breaking up data or imagery for a map into small, bite-sized chunks. Let’s use FlightAware’s classic blue base layer as an example. While we certainly have the ability to render all the content as a single large image, in practice we break this up into individual smaller images. By doing this, when a user is looking at a small subset of the globe, we can load only the tiles needed for what’s visible in the map viewport. This, in turn, saves unnecessary work and data transport—that is, loading imagery that the user cannot view.

For most cases where we use tiles on FlightAware maps, we use a three-dimensional coordinate system, which identifies tiles based on their geographical location (X/Y coordinates, corresponding to longitude and latitude) and their zoom level (a Z “coordinate”). The third zoom dimension is important, as it allows us to tailor what’s depicted on a tile to the current zoom level. When a user zooms in closely on an area, we want to show lots of detail—minor roads, airport runways, etc.—but if that same user zooms out to look at the entire US, then depicting every minor road and runway at that level would seriously clutter the map!

There is, however, a pertinent consequence of this three-dimensional system: the number of possible XYZ combinations grows at an astonishing rate. Each time we increase the zoom level by a whole number, we double the scale of the map. That is, if a distance of one mile took up ten pixels on screen, at the next zoom level it would take up twenty. The consequence of this is that given any viewport size, increasing the zoom by one means we decrease the geographical area depicted in that viewport by a factor of four.

Meanwhile, every tile image is always a constant pixel size, so by extension, a single tile also covers only ¼ the geographical area of the next-lower zoom level. As a result, each time we increase the zoom level by one whole number, we require four times as many tiles to represent the entire world. Extrapolating this over a typical range of zoom levels, say, 1-20, there are potentially billions of possible tiles.

More info on this XYZ tiling strategy is available at the OpenStreetMap Wiki.

Types of tile data

Now that we’ve talked about tiling strategies, let’s move on to discussing what sorts of data we can provide in these tiles. Much like image files, tiles take two general forms: raster and vector. The delineation between the two can be thought of in terms of the point at which raw geographical data is transformed into something that’s (hopefully) visually pleasing to the end user.

Raster tiles are rendered server-side into common image formats: JPG, PNG, etc. The tiles are shipped down to the browser like any other image, where the in-browser mapping software places it in its proper place alongside other tiles.

Vector tiles, however, are passed to the browser as simple raw data in a format such as GeoJSON. The mapping software is then responsible for creating a visualization of this data, placing the features described by the data in the proper place on the map, and using styling rules to control the appearance of the features.

Examples of both of these types of tiles can be seen when examining the FlightAware live map. The classic blue base layer tiles are raster images, while the aircraft are depicted as vector features. Essentially, the client receives a very long list of points (the location of each aircraft) along with other metadata that’s used to decide how to depict the aircraft. The aircraft type (e.g. Boeing 737) determines what icon is used, the aircraft’s current heading determines where it’s pointed, and other flight data such as altitude and groundspeed are used to display an informational block adjacent to an aircraft icon on a map.

Putting it into practice: vector data for the live map (the “old” way)

When the live map was first conceptualized, the approach taken to fetching data was straightforward: client-side maps were configured with a vector layer (that is, a layer populated with vector features), which utilized the XYZ tiling scheme outlined previously. Retrieval of the data was handled by an AJAX endpoint, which accepted the XYZ coordinates as parameters. Logic in this endpoint was responsible for transforming these coordinates into a latitude/longitude bounding box, representing the geographical bounds of the tile, which was in turn used to retrieve all current aircraft positions within that box.

A major advantage of this approach is that it’s straightforward to implement. OpenLayers, the client-side map library we use, provides very robust built-in classes for making such requests; as such, client-side code was simple (essentially reduced to the level of configuration), and server-side code was similarly straightforward. Put simply, this approach was easy to put into practice—and it worked.

However, there are some definite drawbacks to this approach. As we’ve already outlined, the nature of XYZ tile coordinate systems is that there is an entirely unique set of tiles for each zoom level, and this zoom-level specificity can be useful for providing different levels of data detail at different zoom levels. In this case, we weren’t leveraging that specificity potential at all—every tile request simply amounted to “return all the aircraft in this rectangular region.”

As a result, we were quite literally doing redundant work. Imagine if a user allowed all aircraft to load at, say, zoom level 3, and then zoomed the map in. Since this means the new map viewport is a smaller geographical area than before, and since we already loaded all known aircraft in that larger geographical area, the client already has all the data required to display after zooming—but the tiling implementation dictated that all aircraft on the map be reloaded from a blank slate!

Still, it worked, and provided a great showcase product for FlightAware for many years—until increases in position data began to turn shortcomings into actual problems.

Performance issues surface

For the final piece of the performance puzzle, let’s briefly discuss how FlightAware stores and retrieves positions and tracks for flights. While we use PostgreSQL as our primary relational database engine, the sheer volume of positional data we receive makes storing this data in Postgres untenable. Instead, we use a separate storage system for en route flights, allowing for much better update and retrieval performance. The first iteration of this system was birdseye—an in-memory position database built on top of Speedtables. Birdseye served us well for many years until 2018 when it was replaced with popeye, which used SQLite as its underpinnings rather than Speedtables.

Both of these share a similar performance concern, though this concern was much more prevalent with birdseye. Specifically, for the bounding-box search use case, the amount of time needed to retrieve a set of positions is roughly proportional to the number of matching positions found in the result set. For example, a bounding box containing 1,000 aircraft positions would take approximately ten times as long to fetch as a box containing 100 positions.

One might be tempted to think that this problem would only apply to boxes (aka tiles) of vastly different sizes, but that’s not the case. After all, en route aircraft aren’t evenly distributed around the globe by any stretch of the imagination. To illustrate this, let’s look at an exemplar live map, overlaid with the applicable XYZ tile grid:

Now, imagine loading the North and South Atlantic Ocean tiles (2,1,-2 and 2,1,-3 respectively) in a map client. The South Atlantic tile loads in less than a second, while North American tiles could take several seconds. The result, to the end user, looks somewhere between not great and outright broken. It’s certainly a bad look for a flagship visualization of our flight data.

A traditional way to reduce the impact of this discrepancy would be via strategic caching, but here our choice of tile grid becomes problematic again: as we discussed, there are potentially billions of distinct tiles, which means the chances that any particular tile is cached at any particular time is slim. There’s far too much variance in possible tiles for caching to be effective.

Moving forward

We’ve now seen the state of the live map as of a few years ago: slow, patchy loads on the client, redundant calls to data endpoints putting unnecessary extra load on our services, and mostly-ineffective caching. Clearly, this was a situation that called for a new solution, and the direction in which we decided to go involved ditching XYZ in favor of a bespoke tile grid system.

The issues with the previous system led to a short set of goals:

• Keep the number of aircraft in each tile relatively uniform, thus allowing all tiles to have a relatively uniform load time.
• Limit the number of possible tiles to allow for much-improved cache sharing, while also keeping the number of aircraft per tile low enough to keep a cache-miss load acceptably short.

The solution that we decided to explore was to generate a tile grid based on analysis of flight position data. The idea was to gather all known in-flight positions at a point in time, and then divide the entire data set into tiles, such that every tile contained a nearly identical and manageable number of aircraft. Doing this analysis was going to be to expensive to do live, which meant it had to be an offline job. Another factor to consider was that the geographical distribution of aircraft would vary significantly by time of day; while one half of the world is wide awake, the other is asleep. Thus, a tile grid optimized for, say, the middle of the day in the US would be very poorly optimized twelve hours later, when the density of aircraft would favor the opposite side of the globe. As a result, this tile grid would need to be periodically regenerated throughout the day.

Making it work

After thinking through a couple of ideas on how to perform the necessary analysis, we settled on a fairly rudimentary, iterative approach, essentially a trial-and-error process. The basic idea was to take a large rectangular area, which contained a series of points, and split it up until the desired point density was reached. The non-uniform distribution of points meant that these smaller rectangles would necessarily vary widely in size.

The first iteration of this idea took the word “split” rather literally. The iterative process went as follows:

• Given an arbitrary rectangle, try splitting it at its midpoint. The decision of whether to split a rectangle vertically or horizontally was based simply on what dimension was wider: height or width.
• After this initial split, count the number of points on each side of the split point.
• Move the split point in the direction of the larger point population, in an amount proportional to the count imbalance.
• Repeat this process until an “equal” split is achieved
• In practice, the definition of “equal” is a bit fuzzy, since perfection may not actually be achievable—for example, the original rectangle might contain an odd number of points.
• Recursively repeat this splitting process until the desired number of points per tile is reached.

Visually, this process for a single split action looks like this:

While the basic methodology of performing a rectangle split works as outlined above, there’s a major shortcoming with this process—specifically, since all split operations involve splitting one rectangle into two, we’re limited to final tile counts that are powers of two: one rectangle becomes two, which become four, then eight, sixteen, thirty-two, and so on.

Recalling that one of our goals was to carefully optimize both the total tile count and the number of aircraft per tile, this result was problematic. Using this approach, we only have very coarse control over the final result. Suppose that we have a set of 4,000 points and we want to target 400 points per tile—using this approach, the recursion looks like:

• 2 tiles = 2000 aircraft per tile; too dense
• 4 tiles = 1000 aircraft per tile; still too dense
• 8 tiles = 500 aircraft per tile; getting close but still too dense
• 16 tiles = 250 aircraft per tile; now we’ve significantly overshot our density target

Clearly, if we wanted this analysis to achieve our goals, we needed to refine it a bit.

Making it work better

The most obvious approach to this was finding a way to be much more flexible in performing our tile splits. Previously, the only split we knew how to do was an even split: take a population of points and split it into two equal smaller populations.

The key to making this change was a simple yet powerful mental reframing: Instead of thinking of our previous approach as “split this population in half,” we could rephrase the operation as “split this population into two populations, where the ratio between the two new populations is 1:1.” By doing this, and by massaging the split logic to match, we opened the door to being able to split populations to arbitrary ratios. This, in turn, allows for splitting a rectangle into an equally arbitrary number of smaller rectangles; for example, to split a single rectangle into three smaller ones, we’d split the original rectangle and target a 1:2 ratio; we’d then split the larger one again at a 1:1 ratio, resulting in three rectangles with “equal” populations.

Still, we were only halfway to a working algorithm, because we had to figure out how to use this new arbitrary-ratio ability. Previously, the end state of our recursive splitting was easy to define: each time we split our set of rectangles, we’d check the tile density and see if it was low enough; if not, split all the rectangles again (doubling the tile count) and check again. Once the tile density fell below our threshold, we could stop splitting.

That sort of stepwise recursion doesn’t work for arbitrary splits. Returning to our example of splitting a rectangle into three smaller ones, we have to know before splitting how many rectangles we should end up with. This leads us to the second fundamental reframing necessary to make arbitrary splits work: instead of using tile density as our starting metric and splitting recursively until that goal is reached, we must decide before starting how many tiles we need to end up with, and recursively split until we reach that number. Figuring out this tile count is, of course, straightforward: simply divide the total number of aircraft by the desired tile density, rounding up to the next integer.

After determining our desired tile count, we call a function (split_rect_to_count) whose sole purpose is to split a rectangle into an arbitrary number of smaller rectangles (example: “split the entire world into 33 rectangles”); from there, the logic proceeds as follows:

• Determine the ratio for the first split operation by dividing the requested count by two, then using the floor and ceiling of the resultant number to determine the split ratio. (eg 33/2 = 16.5 => 16/17 ratio)
• Call a second function (split_rect) whose sole job is to split a population into two rectangles using the requested ratio. This function returns a list of two rectangles and their point populations, in the same order as the requested ratio. (e.g., 16/17 split returns the smaller rectangle first, followed by the larger)
• We now know that the first rectangle needs to be split into 16 smaller rectangles, and the second into 17. Armed with this information, we can now recursively call split_rect_to_count for each of these two rectangles.
• From the top level, this recursion results in two lists of rectangles, one 16 long and the other 17 long, which we concatenate to yield the final list of rectangles.

Visually, this recursion (using a smaller target count of five) looks somewhat like this (though it’s of course not quite this stepwise in practice:

That’s the entirety of the procedure: with this refined approach, we can come as close as humanly possible to nailing our desired tile density.

Putting it into practice

Now that we’ve talked a lot of theory let’s take a look at what we actually get from this tile grid generation approach in practice.

To begin with, let’s look at an example of an actual production tile grid. This particular grid is targeting a density of 400 aircraft per tile:

The first thing to notice here is that we now have exactly 26 tiles to cover the entire world. Recall that the XYZ grid choice results in billions of discrete tiles—we’ve reduced that number by nine orders of magnitude. This is huge for cache performance!

The second, more abstract (and, to me at least, beautiful) thing to notice is that we can use the geographical size of a tile as an indicator of aircraft density. After all, each tile will contain the same number of aircraft, so aircraft in smaller tiles must necessarily be more densely packed. And we see that this leads to reasonable conclusions with this image—we have high densities over the continental US, Europe, and to a lesser extent Asia, and absurdly low densities in the southern hemisphere.

This leads to a second example: an exaggerated tile grid. For this grid, the target density was 100 aircraft per tile, which of course means we have four times as many tiles. It also means that we get a finer-grained look at aircraft density distribution across the globe:

We can also use these exaggerated tile grids to get a look at how the distribution of airborne aircraft changes over the course of a day. To create this animation, a tile grid was generated once per hour for 24 hours, and the resulting set of grids was animated on a map, along with a representation of the day/night boundary. This allows us to see clearly how aircraft activity follows the sun around the world. At night, a region goes quiet, then becomes active again as morning gives way to daytime.

‍

Finally, we can see one more sobering illustration. All of the preceding tile grid examples were generated in Fall of 2019 as part of a conference presentation. The following is a more recent actual production tile grid from May 2020:

What’s next?

Maps are obviously here to stay, since they allow for intuitive and engaging displays of FlightAware’s data. This means it’s on us to continually improve these experiences. It may very well be that tiling strategies for data like this are not the future—for example, the live map is the only map product we offer that uses tiling. All other maps use a loose pub/sub model, by which the client map asks for targeted data that’s relevant to it—for example, all flights to/from KIAH, or a single flight. Future improvements might involve going to a similar pub/sub model for the live map, or for other, more feature-rich products that might even supplant the live map.

To make a long story short—the sky’s the limit!