./ahmedhashim

Delivering value to customers in realtime often means performing expensive computations on the fly. As your customer base grows, operations such as creating a shop, generating invoices, or updating an orderbook can fan out and grow quickly. A simple & elegant data structure called a PromiseMap can help ease the burden to a system under such load.

Popularity contest

Suppose we’re working on a social network with millions of daily active users stored in a distributed database.

Whenever someone requests a users profile, the application runs an expensive “scatter & gather” query across partitions to compile the information into a UserProfile object which can be rendered by the frontend.

In typescript, this object might look like:

const profile: UserProfile = {
  avatar: 'https://ahmedhashim.com/images/low_poly_avatar.png',
  bio: 'definitely not a bot',
  joined: 1663424830,
  location: {
    latitude: -27.09962924203303,
    longitude: -109.34637304606693,
  },
  username: 'ahmed',
}

Running the query on demand is an acceptable performance trade-off for the long tail of users that are requested infrequently. However, popular users in the 95th percentile can be requested many times per second, making running the query on the fly extremely ineffcient.

For these users, each request adds additional load to the database while returning the same static information. When left unchecked, this can lead to system faults such as thrashing or thundering herds on a viral profile.

We can absolutely do better.

Did you get the memo?

A common technique to deal with expensive runtime computations is memoization, which “stores the results of expensive function calls and returns the cached result when the same inputs occur again”.

An in-memory cache seems likes a good place to start tackling the issue. This memoization strategy can be implemented in typescript with an ordinary Map of the user ID and their profile data:

const cache: Map<number, UserProfile> = new Map();

Now when requesting a users profile we can check the cache for their user ID first, and only run the expensive query if it’s not set:

const getProfile = (userId: number): UserProfile => {
  if (!cache.has(userId)) {
    cache.set(userId, await db.getUserProfile(userId));
  }

  return cache.get(userId);
}

Ignoring memory limits and the difficulties of cache-invalidation for a moment, this ordinary Map key/value cache is pretty effective at reducing computational load.

However, there is a slight hiccup with the code above.

Cache me if you can

Notice that whenever a cache miss occurs, the application needs to await for the database to return a value in order to populate the cache.

  // cache isn't set until the `await` expression returns
  cache.set(userId, await db.getUserProfile(userId));

During this brief wait period, while the database is dealing with the initial request, other requests for the same users profile might be coming in. Because the cache hasn’t set a value yet (due to the first request still being processed), every subsequent request that hits it during the await period will result in a cache miss.

At first glance, leaking a small amount of requests through the cache layer might not seem like such a big deal. But for the 95th percentile of users requested, the load can grind the UX to a halt. This becomes even more apparent as our customer base grows.

How do we solve this? Well, you can either:

1. await the calling function one level up the call stack:

await getProfile(userId); // main thread is blocked

While this fixes the cache miss problem, it also moves the the bottleneck from the database to the application server because now we’re blocking the main thread whenever there’s a unique user profile request.

2. Cache the database request instead, and evaluate the response later when it’s needed.

  cache.set(userId, db.getUserProfile(userId));
  ...
  // await when the value is required some time later
  return await cache.get(userId);

In single threaded languages, this allows the equivalent of an event loop to continue processing incoming requests without blocking the main thread, while only incurring a cache miss for the first unique profile request.

This is exactly what a PromiseMap does.

Promising the world

A PromiseMap can be implemented in any language that supports promises/futures, and it looks something like this:

type PromiseMap<Key, Value> = Map<Key, Promise<Value>>

It’s just an ordinary Map with a Promise wrapped around the value. We can easily convert our cache object over to use it:

const cache: PromiseMap<number, UserProfile> = new Map();

In languages like typescript, this works well for two reasons:

1. Promises are eagerly invoked.
2. Promises can be await-ed on multiple times, and always resolve to the same value.

Eager invocation means that when a PromiseMap populates a request for a specific key for the first time, all subsequent requests for that key will evaluate to a cache hit.

What’s returned when evaluating the cache key is, of course, a Promise. Which is where the second point comes in: if multiple requests await the same promise, it will resolve to the same value.

This means if many users request the same profile from the cache, only a single promise is evaluated & returned every time. This allows the database to breathe a little and only have to process unique incoming requests, while the cache object handles the rest.

An added bonus is that while this is all happening, the event loop continues to process items on the call stack (e.g., more requests). If the promise has fulfilled by the time the application evaluates it, it will resolve instantly & no time will be spent blocking the main thread.

Now this is podracing!

Is that legal?

As with every optimization there are trade-offs involved.

One area where this caching technique breaks down is error handling. Namely, if the result of a promise is an invariant that needs to be checked before it’s used, then the PromiseMap’s lazy evaluataion technique can introduce potential bugs.

Another quirk is long timeouts. Awaiting on a promise that might never fulfill at runtime will cause your application to hang. Extra error handling dealing with timeouts should be used in this case.

Finally, there could be hidden corner cases depending on how promises/futures are implemented in your language of choice.

An elegant weapon for a more civilized age

Nonetheless, when used properly, initial benchmarks show that using a PromiseMap can be a very effective data-structure in your development toolkit.

With this optimization our social network can finally ensure a snappy UX for loading popular users, while the database has more legroom to deliver other critical data (such as “pokes”) in real time.

You don’t have to be working on a large social network to reap the benefits of a PromiseMap. Some common use cases include:

• Hydrating components on an SPA frontend.
• Memoizing expensive queries on a node backend.
• Real time event sourcing from a log-based queue.

Every byte that doesn’t need to be reprocessed is another dollar in your budget, and a better experience for your customers.