Programming Servo: an HTTP cache

with some ‘shared mutable state’ added to the mix…

In our previous post, we saw how combining channels with a kind of “non-event-loop” could be a useful technique to ‘drive’ the concurrent logic of your system, and it was hinted at that shared mutable state might be more complicated.

Well, it turns out, shared mutable state can be very useful as well, in a slightly different context.

A good example of such ‘shared mutable state’ in Servo is the HTTP cache, which is used as part of the ‘Fetch’ workflow of, you guessed it, fetching resources over the network(the web, with all it’s specifications, is truly a magical place: “The Fetch standard defines requests, responses, and the process that binds them: fetching”).

Fetch defines the aptly-named concept of “HTTP-network-or-cache-fetch”, and the adventurous among us might be tempted to scroll to step 19 of the spec which describes how one might want to ‘ask the cache for a stored response’.

If the cache doesn’t construct such a response, the spec moves on to the equally aptly-named “HTTP-network fetch”.

The concurrent nature of Fetch, and therefore also the HTTP cache.

The ‘HTTP-network fetch’ section of the spec tells us something quite interesting, namely that:

  1. The cache will be updated with the response in step 10.4
  2. The response will be returned to the calling code in step 13.
  3. The response will be updated with bytes as they come in from the network, “in parallel”, in step 12.

So essentially, the cached resource will most likely initially be an incomplete, perhaps even empty, response.

It’s also worth noting that you can have several ‘fetches’ going on in parallel, so it’s not just step 12 that is done “in parallel”, you could also have entire different ‘instances’ of the fetch workflow happening at the same time.

This means that if a resources is cached as part of step 10.4, and shortly after there is another ‘fetch’ that asks the cache for this very same resource as part of step 19 of “HTTP-network-or-cache-fetch”, well, this other fetch could indeed receive a cached response, yet it could still be an empty or incomplete response if the parallel steps of the other ‘fetch’ haven’t finished yet.

Furthermore, that ‘not-yet-finished’ response that is already cached, well, it could also be aborted before even finishing!

Head spinning already? Looks like we’re dealing with a concurrent piece of logic here…

HTTP caching: shared mutable state

Let’s get the easy part out of the way first.

The HTTP cache in Servo is going to be shared between threads, due to the multi-threaded nature of ‘Fetch’. So the Rust compiler is quite simply going to complain unless you make the “data” inside the cache thread-safe.

How do we do that?

Full code at https://github.com/servo/servo/blob/ad83faa7452f46fe496487f21d2469616417a7b5/components/net/http_cache.rs

First of all, we share the entire thing only inside a “RWLock”, and pass it around inside this thing called the “HTTPState”.

Full code at https://github.com/servo/servo/blob/ad83faa7452f46fe496487f21d2469616417a7b5/components/net/http_loader.rs

After that, for example inside ‘http_network_or_cache_fetch’, the code using the cache will have to ‘take it out of the lock’, and then call methods on it, for example ‘construct_response’, which will optionally return a cached resource matching the current request, or ‘store’, which will cache the response from the network.

It’s worth noting that it’s only the cache itself that will lock for read/write it’s own data, for example when inspecting stored headers to determine if a response can be constructed.

Are we communicating with this shared mutable state?

It’s worth taking a moment to pause and ponder what we are doing with this shared state.

The HTTP cache, and the stuff stored inside it, is shared across threads(instances of the “Fetch’ algorithms essentially), and those threads will read from, or write to, this cache.

Writing something in the cache can potentially change the behavior of another thread, resulting in a cache hit or miss, but are we communicating between threads here?

The way I see it, while writing to the cache could be argued to be a form of ‘communication’, I don’t see it as ‘telling another thread what to do’. I see it more as some form of passive information sharing on a “best effort” basis.

I think it’s quite important to realize that if you are going to share data among threads, it’s going to require ‘shared mutable state’ and a bunch of locking. However, it’s not the same thing as actually orchestrating, or synchronizing work of many different threads by using such shared state. It’s more like a shared database, which needs to be thread-safe because it’s used by different threads, and not a work synchronization mechanism.

A thread ‘writing’ to the cache doesn’t actually care that much whether the other thread concurrently reading from it with get a cache hit or miss, or whether its only a subsequent request that will get a cache hit. We’re not trying to synchronize different instances of ‘Fetch’ here, we’re just trying to have some form of consistent caching across time.

HTTP caching: cross-thread communication

Now there is another part of the cache story in Servo that does require what I would call ‘communication’. And, you might have guessed it, it’s done using channels instead of shared mutable state.

Which part? Well that whole “responses are returned/cached immediately with an empty body, and then updated in parallel with their data as it comes in via the network”.

Essentially, the cache will be updated here, while the actual data of the cached response will still be updated(in some cases at least), via this “fetch worker”.

Update the cache with a new response from the network. https://github.com/servo/servo/blob/ad83faa7452f46fe496487f21d2469616417a7b5/components/net/http_loader.rs#L963

Worth noting, the ‘response body’ is a case of ‘shared mutatble state’, and the content of this body will be updated, and shared across threads, as data comes in via the network.

https://github.com/servo/servo/blob/ad83faa7452f46fe496487f21d2469616417a7b5/components/net/http_loader.rs#L1110

However, ‘telling another thread that data has come in’ will be done via message sending on a channel, see here (the messages are received via a ‘mini event-loop’ called ‘wait_for_response’).

https://github.com/servo/servo/blob/ad83faa7452f46fe496487f21d2469616417a7b5/components/net/fetch/methods.rs#L422

So yes, mutable data will be shared across threads, yet the synchronization of work and logic will be achieved through channels and messages, and some form of an “event-loop”.

So what about the cache? Well, here is how it deals with responses that are still receiving data over the network:

When the response is first stored, we don’t actually care whether it’s “finished” or not. The state of the cached resource only starts to matter when someone asks us for that very same resource.

When we’re asked to create a response from a cached resource, if the body of that resource is still in ‘receiving’ mode, we pass along a “DoneChannel”, and add it to the list of ‘awaiting body’ consumers that want to get notified when the body is ‘finished’.

The code receiving this ‘cached response that is still receiving bytes for it’s body’ will check if there is a “done chan”, and if there is one, quite simply start waiting for the message that tells it the response is done.

https://github.com/servo/servo/blob/ad83faa7452f46fe496487f21d2469616417a7b5/components/net/http_loader.rs#L908

When, in the other thread that made the original request, and cached the response that wasn’t finished yet, the response is finally done, it will simply call a method on the cache and tell it to notify any other threads that might be awaiting that particular response to finish.

https://github.com/servo/servo/blob/ad83faa7452f46fe496487f21d2469616417a7b5/components/net/fetch/methods.rs#L404
https://github.com/servo/servo/blob/ad83faa7452f46fe496487f21d2469616417a7b5/components/net/http_cache.rs#L601

Conclusion

Yes, mutable state/data is shared in mutexes, yet cross-thread work is synchronized by waiting on, and sending, messages.

It might be, the best of both worlds…