Breaking boundaries: How Freightos achieved high speed graph search in the cloud

(c)iStock.com/suriyasilsaksom

The problem

Freightos’s application runs heavy-duty graph algorithms against a very large dataset. This requires some unusual design principles, which no cloud platform today is optimised for. But we succeeded in building the application on top of the Google App Engine Flexible Environment, a new offering from Google, positioned somewhere between Platform as a Service (PaaS) and Infrastructure as a Service (IaaS). Even Flexible Environment, which is still in beta, does not yet fully meet the needs of high-speed large-scale graph traversal, but we can say that it is moving in the right direction and may yet be the first platform to do this.

How it began

When Freightos started to build a global freight-shipping marketplace, there were two choices in the Google Cloud Platform for deploying our Software as a Service, along with the parallel offerings from Amazon Web Services (AWS).

The first was the Google Compute Engine (GCE), an IaaS, where we would implement plumbing ourselves; the other was Google App Engine, a PaaS which would give us the plumbing ready to use.

Designed specifically for web apps, App Engine bundles an application server, HTTP request-handling, load balancing, databases, autoscaling, logging, monitoring, and more. Google automatically scales, upgrades, and migrates App Engine instances as needed.

If we had gone with GCE, we would have had to integrate and maintain all these components ourselves, on top of the operating system. This would require writing scripts to install a Java VM and other runtime plumbing; as well as integrating with remote services like databases, whether served from Google Cloud Platform or elsewhere.

The convenience of the PaaS was attractive, and Google’s strength is in App Engine, so we went with that. App Engine is easier to use than GCE. But that ease comes with restrictions. App Engine’s design, aimed at web apps, imposes some strict limitations. State is not meant to persist memory across HTTP requests except in session caches, and a maximum of 1GB of RAM is made available to applications. Requests must finish within 60 seconds (extendable to 10 minutes with task queues for asynchronous execution) and instances must warm up within 60 seconds as well. Spawned threads also must have a short lifetime, finishing by the end of the HTTP request that spawns them. Long-running background threads are not possible.

App Engine imposes other limitations to achieve isolation of instances and automated lifecycle management. A customised Java VM with a special Security Manager keeps code tightly sandboxed. There’s no access to the underlying OS, including file system, sockets, and more. Persistence, networking, and other services that usually come from the OS have to go through provided APIs. In fact, you can only use a specific white-list of classes from the Java Runtime Environment.

Running into App Engine’s walls

Way back at the beginning, when Freightos offered only a small selection of freight services, App Engine’s constraints were not a problem.

But as Freightos grew to manage millions of freight prices, spanning air, ocean and land around the globe, we ran into a wall, as our application’s needs went way beyond App Engine’s assumptions.

The most important assumption that came up against is that applications hold limited data in memory. But our application needed quick access to 200 GB worth of route data–a lot more than App Engine allows. Of course Freightos’ need for routing in big graphs is not unique, and is shared by travel and mapping applications. Freightos does have extra dimensions in the data though. Travel applications route people, and mapping apps route vehicles. With freight on the other hand, weights, volumes, and commodities impact the routing and pricing of each leg.

Our application works on a Google Datastore instance holding millions of potential routes from a large and changing collection of freight services. On each new quote request, a uniform-cost graph search algorithm traverses the network of shipping legs, optimising for price, transit time, and other variables.

As the data set for the freight routes grew to massive scale, we implemented several new approaches for accessing the data fast enough to quickly meet requests for quotes.

Loading the entire dataset into memory on each request is prohibitively slow, especially without locally attached SSD storage. Accessing these gigabytes from Memcache or other caching mechanisms provides good performance for some parts of the functionality, though still not fast enough for good user experience for full graph traversals.

Ideally, the application would lazily load only what’s needed for a specific request for a freight quote. This requires predictive algorithms to know what to load, since a route might potentially go through any shipping lane worldwide. One quote request might be from Shanghai to New York, and another from London to Sydney, and the optimal path depends on what ships are sailing and available pricing. Databases don’t let you index paths of a graph, but on the basis of massive historical data on access patterns, it’s possible to target the lazy loading at most commonly accessed paths and so optimise the response times for common requests.

Precomputation of top routes can also work, once these predictive algorithms in place, though there are too many combinations to compute all possible freight routes and all possible loads in advance. Ultimately selective caching and selective precomputation are of little use when the enormous search space is so fragmented and diverse.

One part of the solution is to load all relevant objects into RAM on initialisation. Though it’s a relatively rare architecture, there has been a trend towards holding lots of data into memory as RAM becomes less expensive. Redis, for example, is a popular in-memory database that uses massive RAM for high-speed data access. However, loading all the data takes far longer than App Engine’s 60-second limit, and is also too slow for Google’s approach to scaling, maintenance, and upgrade, which involves the frequently starting and stopping of instances with little warning.

Just when our application was about to give up under the strain, an early version of the App Engine Flexible Environment (back then called Managed VMs) became available. This variant on App Engine removed the restrictions on threads, startup time, Java-class access, and memory size. Our application could now take as long as it needed to load data, and hold up to 200 GB in memory. It still benefitted from the plumbing of App Engine, like Datastore, BigQuery, and logging, and all the existing API calls to the App Engine worked without change.

Google App Engine Flexible Environment

We have already described the challenges of an application that needed superfast access to 200 GB of routing data to run uniform-cost graph search algorithms. Google App Engine Flexible environment let us do this by loosening some of the restrictions of the standard App Engine, particularly the limits on memory and thread lifespan. But Flexible Environment, as we will explain, was still not quite flexible enough.

We needed little access to new resources that Flexible Environment opened up, like local filesystem and sockets; but we did need more of what we already had, like RAM and thread lifetime. Partly this was because our application was developed within App Engine’s limits, but it was also because App Engine really does provide a good variety of services and does it well. And if we really had decided to access the operating system directly for any but trivial requirements, we would just have moved to GCE.

Is it infrastructure or is it platform?

Flexible Environment is somewhere between IaaS and Paas. On the one hand, it is based on GCE, letting you use, for example, the full RAM of a GCE instance, and allowing you to ssh into the server. Just as you can deploy Docker on Google Container Engine, you can swap in your own Docker container on Flexible Environment, including customisations like a different Java VM. (We did that, to let us switch on the G1 garbage collection algorithm more suitable to a big-heap application.)

But Flexible Environment is not really an IaaS. It is better seen as a variant of the legacy App Engine PaaS (now renamed “App Engine Standard Environment”). Flexible Environment has all of App Engine’s APIs and some of its limitations. This means that you cannot fully leverage the power of the IaaS virtual machines (VMs) on which it is implemented. For example, the 200GB maximum is of little use when instances can be restarted without warning.

Though you can treat Flexible Environment as an IaaS and break out of the sandbox and work on the OS level, it is rare that you need to do that. If you do, consider moving to GCE.

The Flexible Environment is a bit stiff

We started with Flexible Environment when it was first available in alpha; it’s developed since then, but it’s still in beta and is not optimised for large-scale in-memory data.

Google shuts down the instances weekly for updates to the OS and infrastructure libraries, which causes problems for an application that takes tens of minutes to warm up. Though we arranged to configure this to happen less frequently, in doing so we lost an important advantage of Flexible Environment, the automatic maintenance and scaling. And Google still does shut down instances for maintenance, so that without special efforts, all the replicated instances of a single application can be down at the same time.

Bulk-loading data is not easy. The App Engine API and the Google Datastore implementation assume you’ll query data sequentially by indexes, rather than loading most of a large dataset in parallel.

The load-balancing algorithm is inflexible, detecting only whether an application is healthy or not. That may work for short-lived App Engine instances that are either up or down, but with long-lived instances, load balancers need to direct traffic to the healthiest of the available instances, based on current memory load, processing load, or any other parameter that makes sense for the needs of the application. Google makes these capabilities available in the HTTP Load Balancer, but only in GCE, not in the Flexible Environment.

Deploying Docker containers is doable, but nowhere near as easy as in GKE, the Google Container Engine. As mentioned, we set up a Docker container with a customised version of the Java 7 runtime with the the G1 garbage collector. To do this, we had to move from the convenient App Engine-specific SDK to the more generic, and less convenient command-line Google Cloud SDK. The process is convoluted, requiring multiple steps of building, both locally and in the cloud.

Ultimately, an application on Flexible Environment is running on plumbing that you did not design and cannot control, just as with PaaS. Though you can work around those challenges, say, by turning off the weekly upgrades, or using a different database, breaking out of the default assumptions loses some of the benefits of the App Engine Flexible Environment. In that case, GCE is the better fit.

The future platform for in-RAM processing in the cloud

Many specialist applications run complex algorithms such as traversing large graphs quickly. Examples include our marketplace for international shipping, as well as travel and mapping applications. These algorithms need a combination of approaches for accessing that data: Fast querying, caching, and pre-loading. The fastest way to access data is in memory, but scaling up memory is not easy. This raised some special requirements that is not fully met by today’s cloud platforms.

The market is wide-open for a vendor who can meet these requirements in a PaaS-like layer.

– Loading massive data into memory quickly. This requires parallelisation and a data layer that can iterate over a dataset fast, in chunks.

– Smart load balancing which respects the complex behaviour of long-lived server instances.

– Minimising the stopping and starting of instances for maintenance and scaling. When restarting an instance is absolutely necessary, all the rest should remain available. Since restart is slow, it is preferable to enable “hot” changes: automated memory and library updates at runtime.

– Implementing garbage collection that works on the assumption of huge, rarely-changing datasets. (The Java VM’s G1 is a step in that direction.)

Why not IaaS?

The best solution today is to build and fine-tune a solution yourself, typically on a IaaS layer like Google Cloud Engine (GCE) or AWS Elastic Compute Cloud (EC2), using as big an instance as possible. Google offers up to 420 GB in new beta offering, and Amazon up to 2 TB.

If App Engine’s architecture, aimed at a very specific type of web application, is too restrictive, then why not just move to GCE?

In our case, we had already made heavy use of App Engine’s services, such as memcache, logging, task queues, email service, and did not want to leave them behind.

But there are more reasons to get as much functionality as possible from a PaaS layer. To use GCE, you have to do a lot more coding. For API integrations to Google services like Datastore, Memcache, and BigQuery, you use the less convenient remote client APIs, which are automatically generated from JSON, as compared to the built-in App Engine SDK in native Java. You write scripts to install the Java VM and other plumbing, and to deploy builds. There is a performance overhead too.

Integrating with underlying services is a hassle. For a service as simple as logging, for example, you set up a log analytics environment like ELK Stack – itself composed of storage, indexer, and search engine, and graphical tools. You then manage all these over time, making sure they get just the right amount of RAM, disk, I/O and other resources to meet requirements but keep down expenses. You do the same for every other component, including messaging queues and database. You also have to take care that each component is upgraded regularly and is compatible with all the others.

Staying in Flexible Environment lets you avoid all that. There may ultimately be no choice, but that will depend on whether Flexible Environment matures to fully support the special needs of a memory-intensive application.

Halfway to breaking the boundaries

It’s the old “best of breed” vs “integrated systems” dilemma, and as usual, neither answer is always right. Fast traversal of large datasets has special requirements, and though Flexible Environment handles some of these better than App Engine, it’s not quite there yet. Perhaps as it comes out of beta, it will allow a lifecycle that respects non-trivial initialisation times.

When that happens, Google App Engine Flexible Environment will be the first cloud platform that breaks out of the usual assumptions and enables this broad category of applications whose needs are not yet met by cloud providers. Amazon and Microsoft, listen up.

ICLOUD PE