Thinking, Fast and Slow

This essay has nothing to do with the book of the same name; I mainly want to revisit this diagram again, because someone asked about it.

Path Separation

Back when I was still green, the design of ScreenOS at my old employer Juniper taught me a great deal. A firewall is split into a control plane and a data plane: the control plane handles the slow work — the UI, protocol-layer preprocessing such as establishing IKE’s phase 1 SA / phase 2 SA (though this isn’t an absolute rule; it depends on the use case) — while the data plane devotes itself single-mindedly to stateful inspection, filtering, and forwarding of traffic. The data plane is in turn subdivided, as needed, into a first path and a fast path, to optimize forwarding efficiency across different scenarios.

On the surface, the control/data and first/fast splits look much alike — both separate a fast lane from a slow lane — but they are not the same.

The relationship between the control plane and the data plane is that the control plane supplies the data plane with the data it needs at runtime. Hardware makes heavy use of path separation; in a router, for instance, control generally goes over PCIe while data travels on a proprietary data channel.

Some protocols, such as FTP and SIP, likewise separate control from data.

The first path, by contrast, builds an optimized runtime — stored in the session corresponding to that connection — out of the packets within a single connection. If you think of the countless feature points (functions) in a system as so many Lego bricks, then the first path sorts out the series of functions that are necessary for this particular connection and assembles them in order (a chain of responsibility), constructing a pipeline that belongs to this connection alone. Subsequent packets in the same session simply walk down the functions on that pipeline, one by one, until the job is done. In theory, a perfectly designed system could make the resulting fast path branch-free, traveling from A to B with single-minded purpose along a line straighter than a laser beam.

Path separation is a very important design idea: beyond improving runtime efficiency, it draws the layers very clearly, effectively avoiding entanglements of state, letting God and Caesar each go their own way.

Take REST APIs, for example: nearly every language’s API framework is designed as a middleware chain, where developers predefine an entire pipeline to handle incoming requests. But that pipeline is static — it doesn’t route paid users, authenticated users, and anonymous users down different, customized pipelines. In the extreme case, we could, at the moment a session is first established, define for each user a dedicated, optimized pipeline during the authentication phase, preload the relevant data, and place it in cache, so that subsequent requests go straight into the fast lane. This approach, together with other QoS measures, can deliver the best possible experience to those users you cherish in your system (usually paying customers, or core contributors).

The potential problem with path separation is that we can all produce very pure, highly efficient designs at the outset, but as features pile up, maintainers who don’t hold to the same attitude can easily compromise, making a path originally designed for one specific scenario ever more “general” and ever more bloated, dragging down runtime efficiency.

Runtime Separation

In earlier slides I argued that we should distinguish: package time, compile time, load time, and run time.

package time - which resources we plan to pre-generate when packaging the software.

Software is a collection of executables, configuration, and resources.

What is configuration? Configuration is a data structure describing the parameters a piece of software needs at runtime. Typically, we generate configuration when deploying a service.

What is a resource? A resource is a data structure generated offline that supports the running of the software. Map files in a game and the dictionaries used for spell checking in a word processor both fall into the category of resources. Often, some data in a system would require enormous computation to process online and could hardly satisfy real-time access, so it’s better to do some preprocessing offline, package it into some kind of resource, and thereby improve online computational efficiency. Thus the generation of resources and the generation of the software’s executable may live in two completely different pipelines, and then be packaged together.

Making judicious use of resource files can greatly improve a system’s runtime efficiency. In those earlier slides I gave the example of the bloomfilter in Chrome, so I won’t repeat it here.

compile time - what transformations we perform at the compile time of the executable to boost efficiency.

Typical examples are Elixir’s Unicode handling and the router in Plug.

Let’s talk about the Plug router. Route matching in Elixir’s Plug-based web servers (Phoenix, for instance) is extremely efficient, precisely because routes like the following:

get "/api/v1/route1", do: ...
get "/api/v1/route2", do: ...
get "/api/v1/route3/sub", do: ...
get "/api/v1/route3/:id", do: ...

get transformed into (pseudo-code, not the real code):

def match(:get, ["api", "v1", "route1"]), do: ...
def match(:get, ["api", "v1", "route2"]), do: ...
def match(:get, ["api", "v1", "route3", "sub"]), do: ...
def match(:get, ["api", "v1", "route3", id]), do: ...

…and then get parsed by the Erlang VM’s pattern matching into a structure equivalent to a trie. Hence route matching is extremely efficient, and the more routes and the more URL variations there are, the more efficient it gets — far more efficient than the regex-based linear matching used in many other frameworks’ routing systems, such as node-restify / express.

If the language you use can do things at compile time, then you can “waste” time in that phase to make runtime more efficient. My earlier essay on the policy engine follows exactly this line of thinking.

Now let’s talk about load time.

In the narrow sense, load time means system initialization. It’s no big deal if this phase is slow; we can do things here that speed up subsequent computation. The pipelines that should be set up, the data that should be loaded, the hooks and events that should be registered, even the warming of certain critical caches — all can be completed in this phase.

In the broad sense, load time also includes the process of data initialization.

Take some piece of data in a database. If it has never been loaded, the first load is a database query that yields the raw data. Through transformations on the raw data, we produce an intermediate state of the data that is flexible enough to suit different use cases — this is what load time does: from cold data to hot data, with the corresponding transformations. Afterward, for requests from different services (or clients), we perform further transformation per the specific requirement to get the final result. We can memoize that result, so that the next time it is accessed with the same parameters, it can be returned at nearly zero cost.

In this way, we subdivide the whole data loading and processing flow into a pipeline: load - initial transformation - final transformation - memoize. The first access runs the entire pipeline; subsequent accesses, depending on the request, run only memoize load or transformation - memoize save.

Lock the Bad Guys in a Cage

Often we expend great effort optimizing the path of normal access — or rather, of legitimate users’ access — while overlooking malicious access. We build our control/data and fast/slow path separation, construct an efficient data pipeline, yet fail to consider that abnormal access may walk an entirely slow path from start to finish, needlessly consuming the system’s compute resources. Many DoS attacks work by finding exactly such holes in a system to asymmetrically drain the target’s resources. For example, accessing /api/v1/user/1234 returns a user profile: for a legitimate user id, the first access queries the DB and does a lot of processing, taking 200ms to return; subsequent accesses hit the cache and return in 10ms. But /api/v1/user/1234858668881993 matches no data and returns with an exception midway through, taking roughly 100ms, and every later access to the same URL goes through the same flow again, returning at a nearly constant ~100ms.

Here we can solve it with a sinkhole. When an abnormal request arrives, we can set aside a separate cache area to store its processing result. Next time the same abnormal request arrives, it hits the cache and the error is returned immediately.

Note that for a system, abnormal situations always far outnumber normal ones, so we must be careful that the sinkhole doesn’t swallow too much of the server resources that were already precious to begin with. We can set a threshold for abnormal states — for instance, only after the same abnormal access has occurred three times do we create a sinkhole to catch it; alternatively, we can cap the sinkhole and use an LRU algorithm for eviction.

Sometimes, normal access arriving at an overloaded system can also use a sinkhole to relieve the pressure on the overloaded service. If we know full well that a service keeps returning 503 (Service Unavailable) / 504 (Gateway Timeout) and still keep forwarding client requests to it, we only make service quality worse. A better approach: once errors reach a certain threshold, immediately create a sinkhole with a fixed timeout, during which all client requests are swallowed by it, giving the overloaded service a chance to recover.

The counterpart to “locking the bad guys in a cage” is strictly filtering every input that enters the system.

In an earlier essay where I took defensive coding to task, I mentioned that we should try to keep a system’s interior pure and clean — trusting the purity (note: not the correctness) of data flowing inside. And at the places where the internal system interleaves with external systems, filter strictly:

• Service request parameters must be checked not only for type but also matched against a predefined domain; anything that doesn’t match is filtered out and never enters the system. For example, if a certain id in the system ranges from 6000000 to 90000000, then any id outside that range is illegal.
• Data the service reads from the outside world must be strictly validated. For instance, data read from databases, from files, from other services must also be strictly filtered by type and value domain.

If we can do this, most malicious access can be nipped in the bud, not only improving the system’s robustness but also greatly increasing its efficiency.