From: andrew cooke <andrew@...>

Date: Fri, 12 Oct 2012 05:42:00 -0300

Update: A higher-level, easier to read account is now available.

You can jump directly to Implementation or Lessons Learned if you don’t want the background details.

Parts below are critical of the original design; since I had a chance to comment on the original design, before it was implemented, this is largely self-criticism.

• The Original Cache
  • Background
  • Problem 1 - Schizophrenic API
  • Problem 2 - Multiple Data Models
  • Problem 3 - Granularity And Efficiency
  • Problem 4 - No Generations
  • Problem 5 - Not Distributed
• The New Cache
  • Background
  • Solution 5 - Distributed Cache
  • Solution 4 - Generationed Data
  • Solution 3 - Expansion To Generic Requests
  • Solution 2 - Single Data Model
  • Solution 1 - Emphasise One Vision Of API
• Implementation
• Lessons Learned

The Original Cache

Background

The cache provides a local Python interface to a remote service (called the “source” below) that speaks XMLRPC.

For confidentiality reasons I don’t want to use the original domain model here, but it was analogous to the following: a set of workers that are continuously measured for performance against various metrics; each metric has ratings; each worker has a history of what periods they had which ratings; the rules used to rate workers may vary from individual to individual; several other worker attributes are stored.

So it’s a fairly complex, hierarchical set of data that includes time series.

The source provides various views into these data. It has evolved over time and duplicates information in various places. A typical call might return ratings over some time range, for a given worker, or all workers in a certain class. All data are structured in terms of lists and maps (XMLRPC structs).

The original cache reified the model described above as Python classes. The structure of these classes is pretty much as expected (a Worker contains Rules and Metrics, Metrics contain time series of Ratings, etc etc).

Problem 1 - Schizophrenic API

There are two different “visions” of the cache API in the description above. One is a service that provides “fragments” of data (presumably tailored to particular, historical needs). The other is a graph of related objects.

Either vision could be used to provide an API, but the initial code tried to provide both. So, for example, you could request a fragment of a time series (and receive the appropriate objects). Or you could request a Worker instance (say) and then use methods on that to locate the related data (ie navigate the graph of connected objects).

Unfortunately, to provide all this in a consistent way, without duplicating or omitting data, introduces complexity:

• To guarantee a consistent graph, the cache would need to maintain references to generated objects so that it could “patch them in” to new, related data, as they are requested.

• To support retrieval of related data, some backlinks were needed within the graph of data model instances.

And in practice, this was incompletely implemented (fragments were disconnected). The result was inconsistencies and duplications in the retrieved data.

Problem 2 - Multiple Data Models

The “object-graph” part of the API was new to the cache. Code in the source (and other, related services) structured the data in a more tabular form - as nested lists and maps. The XMLRPC calls returned sections of this tabular structure.

This led to a mindset which considered the tabular form of the data as fundamental. So the original cache used this as the internal data format.

Since data within the cache were stored in tabular form, rather than as instances of the model provided in the API, the cache was not able to “patch together” a consistent graph (see previous section).

It was also unclear exactly what data had already been retrieved, since the source provided a “patchwork” view over the table and the format had no natural way to indicate where data were missing.

And, finally, the tabular format was undocumented and open to change. The only reliable reference was the implementation used in the source, but although that was available as a separate module, it was re-implemented for the cache.

Problem 3 - Granularity And Efficiency

The main cost (in time spent) when using the source is constant per-connection. So it makes much more sense to request a large amount of data in a single call, rather than across multiple calls.

Clients that used the cache, therefore, would “pre-load” the cache by making a very general call (eg current health for all Workers) before requesting more specific data.

Because of the limitations of the internal tabular format (see above) the cache was unable to detect what data had been pre-loaded. So the API was extended to provide explicit control for when to use the internal table and when to contact the source.

This, in turn, led to more complex clients.

Problem 4 - No Generations

Even though the source updated in definite steps the protocol did not include version data.

This, together with the fragmented view of data provided by the source, led to overlapping, inconsistent data being retrieved over time.

Also, the cache was implemented / used as a single instance, so any “flush” operation would apply to all cache users. This effectively forced single-threaded use.

Problem 5 - Not Distributed

Because the cache was in-memory (in Python code) it could not be shared across machines. Clients on multiple machines produced repeated, duplicate requests to the source.

The New Cache

Background

Work for the new cache was motivated by problem 4 (no generations) above. Multiple clients were over-taxing the server; a new implementation that used memcache to support distributed clients was requested.

The new cache implementation had to be generally compatible with the initial version, but client code was available and could be modified to accommodate small changes, if necessary.

Not all clients of the source use the cache; some call the protocol “directly” (via Python’s XMLRPC libraries). The code for these clients could not be modified, so modifications to existing XMLRPC procedures were not acceptable.

Solution 5 - Distributed Cache

As described above, memcache was used to cache the data received from calls to the source. The key is, essentially, the URL; the value is the returned data.

Solution 4 - Generationed Data

The XMLRPC protocol was extended to include information on the current version of data in the server.

The source already contained two separate generations of data (one current, one being constructed). It was relatively easy to extend this to a configurable number of generations, providing access to each via a new, different port (while preserving access to the “current” generation through the original port). This allows cache instances to access a particular generation without changing the existing protocol.

Memcache keys include the source address (with port, which is tied to generation number). This allows multiple generations to be cached without overwriting data.

To simplify management of generations in clients, the new cache implementation has a method that returns a fresh instance for the latest generation. This, combined with other changes (below) that remove the need for explicit cache control, supports a much simpler pattern of use: a cache is instantiated for a single, short task (eg generating a web page) that requires consistent data from a single generation. Re-running the task, or similar tasks in other threads, use a new instance of the cache.

Finally, a new service was introduced to the system, called the Primer. This monitors the source, detects a new generation, and pre-loads commonly-used, generic data (see below) to memcache. It then modifies an entry in memcache that describes the current generation; this allows new cache instances to identify and access the latest data.

Solution 3 - Expansion To Generic Requests

Although the original cache interface was very broad, the problems outlined earlier led to it being used in a very restricted way - global information was loaded (ie health for all Workers) and then, for each Worker that required further data, all data was loaded for that instance.

So, in practice, only two source calls were used to populate the cache.

The new cache intercepts all calls and generates responses from the internal model (described below). Because the internal model contains sufficient information to identify incomplete data the appropriate calls to the source can be made automatically. Only the two calls described above are used, so the implementation is quite simple.

For examples: an initial query to retrieve a single Worker will trigger the retrieval of all Workers (the “global information” described above); the first request for detailed data for a given Worker will load all data for that instance.

Solution 2 - Single Data Model

The data stored in memcache are direct snapshots of the source calls. The new cache uses that data to construct an in-memory graph of instances using the same classes exposed by the cache API.

As described above, the graph is constructed in two stages. First, “global data” are loaded; second, calls to retrieve data for particular Workers trigger retrieval of the data for those instances (only). It may seem costly to keep this in memory, but since they are also the results returned to clients they are likely held in memory by the caller. And cache lifetimes tend to be short (discarded for each new generation), so the in-memory cache does not have time to grow too large.

There is no attempt to reconstruct the “tabular” format used in the source (cf the old client, as described above).

Solution 1 - Emphasise One Vision Of API

The new client prioritises the “graph of objects” API. Calls to request fragments are still supported, but trigger the creation of the appropriate section of the object graph before returning a filtered subset of that model.

This guarantees (with generationed data) a consistent set of results.

Implementation

The cache has four responsibilities:

1. Expansion of specific calls (targeting a particular detail) to generic requests (targetting all workers, or all information for one worker).

2. Caching responses from the source in a way that can be accessed by a distributed set of clients.

3. Translation of (tabular) responses into data model instances.

4. Management of generations.

It is implemented using a layered approach. The lowest level is a “dumb” wrapper around memcache. For each method in the cache API (which corresponds pretty closely to each XMLRPC procedure) memcache is checked; if no data are available a call is made to the source and the results stored in memcache and returned to the caller.

The data model is a separate module that includes translation from the tabular format (as received from XMLRPC) into the graph of objects. The lowest level cache translates each fragment separately, so the client receives unconnected fragments on successive calls.

The middle level of the cache manages an in-memory set of Worker instances. The first call for a Worker is converted to a call (via the lower level) for all workers; the results (as data model instances) are stored by name. Subsequent calls then pull Workers directly from this in-memory store.

The top level of the cache is similar to the middle level, but intercepts calls for detailed data. The parent Worker is retrieved from the mid-level and, if that is missing the required information, a request is made for all data for that Worker; the response is used to construct the entire graph. Finally, the client receives the appropriate fragment taken from the complete, consistent object graph. In this way the client receives connected fragments.

This is implemented using inheritance: the lowest level is the base class; the middle and top levels are successive sub-classes.

The base level must be generation-aware as the memcache keys depend on the generation used. This level also implements the method that returns a new cache instance for the latest generation. By using type(self)(....) (and the same constructor arguments for all classes) sub-classes are automatically accommodated. The previous cache implementation was modified return itself when this call is invoked. This allows it to be used as a direct replacement when generations are not required.

Preserving the cache API and implementing functionality in progressive layers made it easy to test for consistency during development.

Lessons Learned

In no particular order:

• Identify common usage patterns and use those to simplify how data are loaded. It’s OK to load too much data, within reason (and in a sense it gets more OK as the number of clients increases, since they are all doing the same, and so hitting memcache, and not the source).

• Make generations (if you need them) an end-to-end property. In other words, think about this as early as possible in system design.

• Use a new instance of the cache for each generation (if this is returned from a method on the previous cache then a non-generational cache can return itself).

• Carefully consider the balance between distributed and in-memory stores. We keep a snapshot of the returned data in memcache, but save the “processed” object graph in memory - this reduces server load while keeping the caches responsive to simple queries.

• Try to develop the cache and source in tandem, so all clients can be isolated from the protocol details.

• Make memcache a direct copy of the wire data. This makes it easy to “read through” and supports alternative cache implementations (eg with a different data model implementation).

• Take care to separate the “direct cache” from any “translation layer” that converts the results into a more usable data model.

• Make sure that you can identify “missing data” in your data model.

Following these gave a replacement cache that is significantly simpler than the original implementation, while leaving the cache API, service protocol, and cache clients largely unchanged. It also performs better with multiple, distributed clients and provides stronger guarantees about the consistency of the results (both in time - via generationed data - and “space” - as a single connected graph of data model instances).