John Fremlin's blog: The mmap pattern

There are many choices in software engineering that are visible only to the developers on the project: for example, the separation of responsibilities into different parts of the program are (hopefully) invisible to the user. These choices can descend into a question of personal taste and I personally lean towards simplicity. My experience has shown that people tend to create complex generic interface hierarchies, only to have them hide a single implementation. What's the point in that? On the other hand, there are architectural decisions that affect the way the program behaves. For example, whether processing occurs on a server or mobile device ends up changing how the system can be used.

I want to bring up an underused architectural choice: the defined memory layout persisted to disk by the operating system via mmap. All malloc memory on modern UN*X systems is mmap'd. But explicitly choosing a file and mapping that into the memory space of the program means it can persist across crashes. And it doesn't just persist in terms of storage on a backing device, but the OS is aware the pages are mapped into memory, so on start-up there will be no disk read, no serialization delay and everything is ready. In many systems the effort of reading in data, whatever trivial transformation is being performed, can be extremely costly in terms of CPU time (instructions and dcache thrashing). With a mmap'd file, this time can be reduced to nothing.

One very key architectural decision for a system is the degree of reliability that it should possess. This is an explicit trade-off between the rapidity of development (in particular the level of indoctrination needed before new contributors are able to augment the feature set) and the operational stability. By preserving state explicitly to memory backed files, several classes of unexpected events causing the program to crash can be recovered from with minimal disruption. The benefit here is that the system can be developed rapidly with code reviews focusing on data integrity and paying less attention to complex interactions that can lead to crashes.

Modern CPUs have the ability to arbitrarily (generally at a 4kB granularity) map memory addresses as visible to a program to physical RAM addresses. The technique I am advocating here is a way of exploiting this hardware functionality in conjunction with operating system support via the mmap call (that turns a file into a range of memory addresses). It is quite possible to share mmap regions across processes so this gives a very high bandwidth unsynchronized interprocess communication channel. Additionally, the regions can be marked read-only (another nice capability afforded by CPUs) so data-corruption failure cases can be avoided entirely.

The main implementation difficulty with using a mmap'd region is that pointers into it must be relative to its base address. Suppose one were to try to persist a linked list into such a region. Each next pointer in the list is relative to the base address of the region. There are multiple approaches: store the base address in a separate (maybe global) variable, and add it each time, or try to mmap each region to a well-known start address (and fail if it cannot obtain that address). Generally with some trickery it is possible to exploit the memory remapping capabilities of the underlying CPU to reduce this overhead (i.e. store the base offset in a segment or other register). Each of these alternatives has advantages and disadvantages which can be debated; in practice, once the idea of persisting state to mmap files is introduced into an architecture, there are various reasons to try to use multiple regions (e.g. to support fixed-sized and non-fixed-size records, and to enable atomic exchange of multiple versions of the state).

Though there are low-level opportunities, this technique can actually be extremely beneficial in garbage-collected scripting languages where dealing with large amounts of data is generally inefficient. By mmap'ing a region and then accessing into it, the overhead of creating multitudes of small interlinked items can be reduced hugely. Large amounts of data can be processed without garbage collection delays. Additionally, the high cost of text-processing can be paid just once, when first building up the data-structure and later manipulations of it can proceed very rapidly, and interactive exploration becomes very convenient. The instant availability of data can reinvigorate machine learning work-flows where iteration speed from experiment to experiment is a constraining factor.

Despite the advantages, this technique is not widely exploited, which is why I'm writing about it. For Lisp there is manardb, and in industry there are several very large systems of the order of petabytes of RAM which use this idea heavily. Consider it for your next project!