which provide it. Any resource on which the server depends for its correct operation is generally mapped into the server's address space only; to access the resource, clients must make structured requests to the servers, typically via socket communication. Server threads listen on those sockets; receive, unpack, and validate requests; perform requested operations; and return results, again via socket communication. Because the server and client are isolated from one another, a correctly functioning server can enforce access rights, check the consistency of arguments, and ensure that every operation preserves resource invariants and executes atomically, even in the face of client crashes.
Unfortunately, socket communication can add substantial overhead to simple services, even when no physical network is traversed. On a recent Intel box in our lab, datagram messaging over Unix domain sockets incurs a minimum round-trip latency of 3.3-9.6 µs, depending on which cores or hyperthreads are running the communicating threads.
Key-value stores are a case in point. The widely used memcached [21] is organized as a process containing an adjustable number of server threads that communicate with clients over sockets. Socket communication allows the server to be used in a data center, where it runs on a different machine from most of its clients. Memcached is also widely used, however, in more local environments, where it shares a single multicore machine with its clients. In such an environment, the latency of socket communication overwhelms that of the actual service, which is essentially a hash table lookup. Moreover much of the complexity of the memcached code baseroughly a fifth-is devoted to communication management. This, too, seems like a waste in the local case.
Concerns over the cost of accessing services are not new. They contributed heavily to the debate over microkernels almost 30 years ago [31]. Researchers sought to increase modularity, reliability, security, and maintainability by moving significant functionality out of the operating system kernel and into user-space servers. Communication with those servers was still mediated by the kernel, however, making the baseline overhead of calls reflected to a server roughly double that of a call that was handled in the kernel. Whether this overhead was significant, and whether it was overshadowed by other issues was hotly debated, but developers largely voted with their feet, and monolithic kernels still dominate today.
Several recent systems have sought to achieve the modularity benefits of microkernels at lower cost. Dune [1] uses hardware virtualization to run each user process in a separate virtual machine, giving it direct access to protected hardware features under control of the hypervisor. Arrakis [27], inspired in part by Dune, separates "control plane" and "data plane" operations in the I/O system, and leverages single-root I/O virtualization (SR-IOV) [15] hardware to allow applications to interact directly with memory-mapped devices. Similar functionality is provided by a variety of other recent systems [13,14,18,23]. IX [2] and ZygOS [29] build upon Dune to provide this same direct-to-device functionality while maintaining a protection boundary between the application and the I/O library. Snap [24] achieves similar protection without virtualization by dedicating one or more cores to actively spinning server threads, which scan shared in-memory queues for client requests.
Most of these recent systems have focused on performance for individual applications, with limited attention to cross-application sharing or system-wide resource management (e.g., to enforce quality of service guarantees). IX and Zygos could potentially accommodate sharing, and Snap already addresses QoS, but each has limitations (its dependence on virtualization or on dedicated cores), and the other systems would be hampered by their lack of a protection boundary between the library and the application.
More recently, our work on the Hodor project [12] has shown how to leverage protection key hardware on recent Intel processors to implement low-overhead protected libraries without the need for virtualization. We noted that such libraries can be used for safe, cross-process sharing; we used this capability to implement shared access to the Silo library database [32] and to Intel's DPDK networking library [13]. Similar functionality is provided (in a similar way) in the concurrently developed ERIM project [34], though the authors focus on applications to intra-process sandboxing for security. Protection between the library and the application might also be provided by a trusted compiler [20,37] or through source or binary rewriting [33,36], but these impose significant instrumentation costs throughout a program's execution.
We observe that any mechanism that allows a library database or network stack to share data safely across applications can be used to convert a server like memcached to provide safe, direct, functioncall access to clients rather than requiring them to communicate over sockets. We have performed this conversion on memcached. The conversion eliminates not only the cost of message packing, transmission, and unpacking, but also the cost of context switches: application threads perform operations on the K-V store themselves.
After a review of Hodor in Section 2, we describe our variant of memcached in Section 3, including its approach to memory management and position independence, the interface provided to applications, the integration with Hodor, and fault tolerance. Section 4 then presents experimental results. For the Yahoo! Cloud Service Benchmark (YCSB) [7], we measure a reduction in latency of 11-56× and a roughly 2× increase in throughput. When use is confined to a single multicore machine, we were also able to eliminate about 26% of the code base, while adding about 2% new code. After returning briefly to related work in Section 5, we summarize conclusions in Section 6, and consider future work, including hybrid (sharing + communication) models and the use of persistent memory.
Full details on the Hodor system can be found in a previous paper [12]; code is available at http://github.com/hedayati/hodor. We review essential concepts here (see Figure 1).
The key idea in Hodor is to control access to a memory-mapped resource by making it accessible only while executing trusted library code. An application gains access to the resource when it calls into a Hodor library; it loses access when it returns. Threads that are executing outside the library are unable to access the resource even when other threads are executing inside the library. Moreover the operating system arranges for each library call to complete (with certain limits on execution time) even if the process to which its thread belongs crashes due to activity in another thread; this allows the library to ensure integrity in the face of independent client failures. (A crash that occurs inside library code is considered unrecoverable.)
The Hodor paper explored three ways to build protected libraries. Our experiments here use the preferred implementation, which is based on the memory protection keys (Protection Keys for Userspace-PKU) of recent Intel processors. PKU harvests four previously unused bits in each page table entry to associate one of 16 "key" values with the page. A new 32-bit pkru register, writable in user space, associates two bits with each key. These bits allow the running thread to reduce permissions for pages marked with that key: (0,0) allows whatever access is otherwise permitted to the page; (0,1) eliminates write access; (1, * ) eliminates all access.
PKU appears to have been designed as a safety feature: it allows an application to minimize the impact of stray pointer or array subscripting bugs by turning off access to critical data structures when they are not being actively used. Hodor arranges for real protection by controlling the circumstances under which the pkru register can be written. Specifically, a modified version of the OS's (trusted) loader scans the binary of an about-to-be-executed program. It dynamically links the code of any specified Hodor libraries for which the application has access rights. For each library entry point, it installs a trampoline that changes stacks and uses the wrpkru instruction to change access rights-dropping restrictions on the protected resource on the way in and re-enabling them on the way out. It also installs an initialization routine, called before main, that enables restrictions at startup.
If the wrpkru opcode appears anywhere in the binary other than a trampoline, the loader places a hardware breakpoint at that address, to prevent its execution. Extensive scans of existing binaries confirm that stray instances are extremely rare. They can be avoided entirely with minor compiler changes. If more than four (the number of breakpoint registers) appear in any one program, they can also be accommodated (at some cost) by changing page permissions.
In addition to changing stacks and the value of the pkru, trampolines can optionally copy arguments and return values into and out of the library, rather than leaving them in the application's main protection domain (where they could potentially be modified by non-library threads while the library is using them). We do not enable this option by default in our experiments; rather we copy, manually, only those arguments that are security-sensitive; more on this in Sections 3.3 and 3.4.
An empty call into a Hodor library takes about 40 ns on the machine in our lab, round trip-about two orders of magnitude faster than an empty messaging round trip on Unix domain sockets.
In converting memcached from a socket-based application to a Hodor protected library, there is actually much more code removal than there is code addition. Standard memcached is a large program (approx. 26 KLoC) in part because of its customizability and flexibility. Clients can issue requests, for example, in either an ASCII based, readable format or a compact, binary format: one offers superior debugability, the other better performance. Without a network interface, the ASCII format loses its attraction. Call parameters will never need to be viewed in a text editor (as they might when debugging the distributed version): they will be viewed in a symbolic debugger, where binary format is perfectly acceptable.
We implemented a modified version of the libmemcached API. Each call takes as an argument a memcached_st, which includes server information, protocol details, and the state of the current operation, none of which are required for direct-through-Hodor calls. We therefore provide two separate APIs-one that is identical to memcached's and one that omits the memcached_st argument. Preservation of the original interface allows us to use our modified memcached as a drop-in replacement in existing applications; provision of the newer API allows a modified application to avoid unnecessary overhead. Calls designed, in the original interface, to change the network protocol configuration are now treated as noops by default; alternatively, they can be flagged as errors in order to facilitate migration to the newer interface.
Memcached also provides an asynchronous API designed to hide the latency of socket-based communication. A programmer can issue a query with a callback function that will be invoked when data is returned. While callbacks could, in principle, be added to a system like Hodor, they are not supported at present, and it would not be trivial to add them. Fortunately, they are not needed for memcached: since all calls complete immediately, our version of libmemcached can call into Hodor for service and invoke the callback immediately after the trampoline returns.
Hodor manages the protection boundary between an application and its shared libraries, but it does not automatically arrange to share space among library instances in separate applications. For that we need to address a variety of challenges, including set-up and clean-up; cross-process synchronization; static and dynamic memory allocation; and background, bookkeeping tasks. For several of these challenges we rely on the Ralloc memory allocator of Cai et al. [3] (code available at http://github.com/qtcwt/ralloc).
Ralloc provides a shared heap abstraction on top of a shared, memory-mapped file. To create a key-value store (an instance of memcached), we launch a bookkeeping process that uses Ralloc to create a shared heap, or to map it into memory if its file already exists. (Ralloc supports the ability to have multiple shared heaps, but we only need one for our experiments.) The bookkeeping process remains alive as long as its K-V store is in use. During operation, it is responsible for intermittent "cleaning" of the store-eviction of less-needed items when space runs low. On shutdown, it flushes all updates back to the underlying file. This convention allows us to restart a store with its contents already intact. (Enhancements to allow the store to survive full-system crashes are a subject of future work; see Section 6.)
Each memcached client, on startup, uses Ralloc to map the shared heap into its own address space. While we might hope to map the heap to the same address in every client process, it is difficult to do so in practice, given the possibility that any given address range might be needed by some client for other purposes. Fortunately, Ralloc provides a persistent pointer (pptr) abstraction that enables the creation of position-independent data. In C++, the pptr type is implemented as a templated smart pointer that holds the signed distance between its own location and that of its target [5,6]. So long as the target resides in the same shared heap, a pptr<T> can be loaded into or stored from a T * , quickly and correctly, in any address space.
We use Ralloc for all dynamic allocation of buckets, keys, and values. Internally, Ralloc uses pptrs for all its metadata; we converted memcached to use them for all pointers in the K-V store as well.
Because threads in multiple address spaces now access the K-V store directly, synchronization must work across process boundaries. We therefore updated the initialization options on all locks in the memcached code base to specify the PTHREAD_PROCESS_ SHARED attribute. Locks used to protect metadata in a conventional allocator would also need to be shared, but Ralloc, it turns out, is entirely nonblocking. It also scales extremely well, due in large part to the extensive use of per-thread caches, and it partitions blocks of different sizes into separate superblocks, leading to low internal fragmentation and no external fragmentation for the block sizes used in memcached. This efficient space management obviates the need for memcached's own "slab-based" allocator, which we deleted.
As a starting point for data structure access (in our case, for access to the K-V store), Ralloc supports the notion of persistent roots. They are statically allocated near the beginning of the shared heap, and contain pptrs to internal structures. Each is identified by a symbolic ID. Figure 2 illustrates the use of persistent roots for data structures that are statically allocated in the Ralloc heap. Memcached's lru_locks, originally a static array of pthread_mutex_t objects, is now, in our version of the code, a pointer to an array of such objects. When the memcached bookkeeping process starts up, it allocates this array in the Ralloc heap using pm_calloc and sets a persistent root to point at it. When a memcached client process starts, it uses pm_get_root to obtain (an address-spaceappropriate version of) the pointer stored in the persistent root.
The lru_locks are used to protect least-recently-used lists that allow the background process to choose victims to evict from the hash table when space runs low. The original version of memcached places items into an LRU list based on the size class to which they belong in the server's custom allocator. Because we now use a separate allocator, we chose to decouple the LRU functionality from the allocator internals. We tried putting all items into a single list, but this caused unacceptable lock contention at high thread counts. We currently use a set of lists, and choose among them (and their locks) based on the hash of an entry's key.
We encountered similar trouble with contention on the lock used to protect statistics on client requests. We therefore chose to scatter these statistics across the slots of a shared array. Most updates are now made to a slot that is not being used concurrently. Statistics-retrieving calls must scan the whole array. Neither the lru_locks nor the statistics lock is a bottleneck in the original memcached code, where requests are serviced less frequently and where the maximum number of active threads is smaller.
To access data structures that may be reallocated during execution, persistent roots can be used with an extra level of indirection. Figure 3 illustrates this idiom for the root of the primary hashtable, whose location may change due to occasional table resizing.
In practice, not all data need to be shared between processes. The threads of the bookkeeping process, for example, maintain information that is not needed by clients during library calls. Memcached also makes use of some temporary buffers during individual calls. These can be local to a single client, so long as they reside in the libmemcached protection domain in Hodor, to prevent concurrent access by threads executing in the main code of the client application.
To integrate our API with Hodor, we identified the internal functions associated with each API call and wrapped them with Hodor trampolines; these in turn are tagged with special macros in the source code. Figure 4 shows our implementation of memcached_get. Memcached incorporates significant machinery to parse and execute commands. These two tasks are deeply interwoven-a fact that made it difficult for us to understand, "unpackage," and replicate the API. The task would presumably have been easier if writing a Hodor application from scratch, because commands would never have been marshalled into network packets.
At the same time, the use of Hodor introduces certain security concerns. Specifically: no privileged information in the library should be leaked into client code, and no data created by the client should be trusted by the library. If arguments to library calls have internal consistency requirements, they should be copied to space that is not writable by the client before performing consistency checks, to prevent concurrent corruption by other client threads. This idiom can be seen in Figure 4, where we copy the client's key into a buffer (key_prot) that we have created inside the library. By contrast, the return value buffer is allocated using the standard malloc, so it will be visible after returning to the client.
Hodor relies on file system permissions to control the mapping of shared libraries. In our case, it executes the libmemcached initialization routine with the effective user ID of the memcached bookkeeping process, allowing it to open and map the file containing the K-V store. Once initialization is complete, it reverts the effective ID to that of the client process. These conventions allow us to share data across protected library instances without leaking the contents of the actual K-V store file.
Our code must take care to ensure that faults experienced in one process do not affect the integrity of the library or of other processes. The original memcached uses locks to ensure that server threads perform their operations atomically. In our version the same code is executed by client threads. Each operation-assuming it completescompletes atomically. The only new issue is the potential for failure in the middle of an operation.
If the process of a Hodor thread is terminated by action outside the library-a SIGKILL signal, for example, or a segmentation fault in a concurrent thread in the client's regular code-Hodor allows the thread in the library to continue running until it has completed its call or a generous timeout has expired.
If a Hodor thread encounters an error of its own-a segfault for example-it will indeed terminate abruptly. Protected libraries, like system call handlers, must be carefully written to avoid this possibility, or to ensure that termination happens only when no locks are held and all invariants still hold. Pointers received from the client are the most common source of potential problems. They cannot safely be dereferenced while locks are held. (Even if they could be verified before use, it would always be possible for a concurrent thread to unmap the target memory while the library was active.) As a standard practice, we therefore copy the targets of all pointers into memory located in a Hodor protected region before acquiring locks or performing other changes to shared state. In Figure 4, key_prot is used for precisely this purpose. For our final allocation, buffer, which we return to the client program, we use ordinary malloc, but only after releasing all resources that we acquired.
We used the Yahoo! Cloud Service Benchmark (YCSB) [7], a workload generator for databases, to test the performance of our protected library implementation against the original version of memcached. YCSB allows users to select from default workloads or to generate their own with specific chosen properties. We created a set of workloads that test the performance of our key-value store on value sizes of 128 bytes and 5 kilobytes, with read/write distributions of 50/50 and 95/5. Our results were collected on a single-socket Dell machine with a 10-core (20-hyperthread) Intel Xeon Gold 5215 processor equipped with 192 GB of DRAM and running at 2.5 GHz.
Since writes are uncommon compared to reads in production environments, we consider a 50/50 split between reads and writes to be a "write heavy" workload; the 95/5 case is considered "read heavy." For workloads with values of size 128 B, we store 4 × 10 7 key-value pairs and perform 10 6 operations on those pairs. For workloads with values of size 5 KB, we store 10 6 key-value pairs so that the total memory consumption of the application remains about the same. Operations were performed with a Zipfian distribution over the keys. Latency is reported in µs for operations in a single thread. Throughput is reported in thousands of transactions per second (KTPS), so higher numbers are better.
For the original memcached, we set the maximum data size to 60 GB; we provide the same limit to Ralloc in our modified version. In the original version, the hash table starts with 2 16 buckets and resizes several times. In our modified version, we report results for a fixed size of 2 25 buckets (our resizing code in the background process is not yet working correctly). If anything, this decision penalizes our code: in the small-key experiments, our table ends up with a load factor of about 1.2.
Once a request is received, the original memcached and our modified version perform the same internal operations. The main difference is that in the absence of socket communication, the overhead of initiating a call in our version is much lower. As shown in Figure 5, calls in the original memcached vary from 13-54 µs; in our version they never take more than 1.5 µs. These numbers represent speedups of 11-56×. When measuring throughput scalability, there is a fundamental mismatch between the original and shared-library versions of memcached: since server and client threads are distinct in the original, their numbers can vary independently; in our version they are always the same. In an attempt at a fair comparison, we vary the number of client threads on the X axis in Figures 6789, and show two curves for the original memcached: one with 4 server threads and one with 8.
With 4 server threads, the original memcached scales linearly to 10 clients-the number of cores on the machine. The addition of hyperthreads has no significant impact, suggesting that the server threads may be a bottleneck. To test this hypothesis, we ran the experiment again with 8 server threads. Performance for client counts up to 10 is virtually identical to the 4-server-thread case, but it continues to scale, at a slower rate, all the way out to the tested limit of 40 clients-2 for every hyperthread on the machine.
The explanation, we believe, lies in an understanding of the critical path of the microbenchmark. When a server thread completes a request in the original code, it calls into the operating system kernel to perform a write on a socket. It then immediately performs a select syscall to obtain another request. Whether that call returns immediately or waits (incurring a context switch to another process) depends on whether another client has already performed its matching write. As the number of client threads increases, the odds that one of them has performed a write on a socket in the select set gradually increases, increasing the probability that the kernel can simply return into the server, rather than switching to a client context.
In our new, protected-library version of memcached, by contrast, client threads perform their own requests. There are no system calls on the critical path, and the overall system bottleneck becomes the synchronization employed in hash table critical sections. In the read-heavy workload, throughput peaks at 6-8 threads. In the write-heavy workload, where the average operation takes a little longer, throughput peaks at slightly fewer transactions per second, and takes a few more active threads to get there. In all cases (large and small values, read-and write-heavy workload), bandwidth degrades slightly as contention increases, out to the number of hyperthreads on the machine (i.e., 20), but remains essentially flat thereafter, at roughly 2× the throughput of the original memcached. At peak throughput, the protected library reaches 3× the throughput of the original memcached. To assess the marginal overhead of the protected library mechanism, we have shown results both with and without Hodor protection. The version without improves throughput by roughly 5%, but of course it is not safe.
As noted in Section 3, our updates to memcached deleted more code than they added. Specifically, on an original base of ∼26 K lines of code, we removed ∼6800 lines and added ∼600, for a net reduction of ∼24%. Of the deleted lines, ∼5200 were devoted to socket communication and to packing and unpacking of message buffers; ∼1600 were devoted to slab-based memory management (Section 3.2).
With regard to conceptual complexity, our subjective impression is that the removed code was more complex than the added code. With Hodor, a thread performs its own request, and the flow of control is very clear. In a separate server, threads must keep track of multiple client connections, select from among their sockets, unpack request buffers, and pack reply buffers for return.
On the other hand, protected libraries in Hodor are significantly more subtle than "ordinary" libraries-particularly when they share data with instances in other processes. As noted in Section 3.4, a Hodor library routine is more akin to a kernel-level syscall handler than it is to an ordinary function: it must check its arguments for consistency, manage its space separately from that of the caller, and ensure that faults (e.g., due to incorrect pointers to client data) never occur while holding locks on shared data. After modifying the first few library routines, we settled on an idiom that copies client data into Hodor-allocated buffers before acquiring any locks.
Over the past decade, extensive research has aimed to limit the operating system's involvement in resource management to what is required for set-up and access control (i.e., the control plane), and to avoid OS intervention on individual operations (i.e., the data plane) once that access has been granted. Specialized I/O stacks (e.g., DPDK [13], SPDK [14], and mTCP [18]) have been designed to bypass the OS and avoid the overhead of the general-purpose system-call path on data transfers. Similarly, our work relies on the OS to set up page table permissions for protected libraries, while avoiding per-op OS interventions when querying memcached.
Unlike our work, most previous efforts at avoiding OS intervention have not considered the possibility of sharing resources across distrusting domains. Our work allows for safe sharing of memcached among independently developed local processes with independent failure modes.
While intra-address space isolation [33,34,36] has been used to protect secrets (e.g., encryption keys) or security critical regions (e.g., shadow stacks) in a single application, researchers have only recently begun to consider isolation for libraries. Hodor [12] protects user-space libraries for kernel-bypass I/O and in-memory databases. Treasury [8] uses Intel PKU to protect a user-space non-volatile memory file system called ZoFS. Our work transforms memcached from a client/server model to a protected library and uses Hodor to provide both protection and sharing.
Exokernel [10] was one of the first projects to compile OS components as libraries and link them to applications as a Library OS. Other such systems include Drawbridge [28] and EbbRT [30]. Separation of components from the kernel offers the prospect of better system security and more rapid evolution of the code base. Unfortunately, library OSes provide no easy way to share the same set Microkernels [9,19], several of which pre-date Exokernel, avoid this problem by separating address spaces and following a client/ server model in which each resource is handled by a user-level server. The main drawback of microkernel design has long been the overhead of communication [25]. While at a higher abstraction level than a traditional OS service, current memcached deployments follow the microkernel pattern. We see recent work on protected libraries, including ours, as a means of combining the isolation and sharing benefits of microkernels with the performance gains of exokernels.
We have presented a new, shared-memory version of the ubiquitous memcached key-value store. Our code is based on the Hodor protected library system [12] and the Ralloc memory allocator [3]. For clients running on the same machine as the server, we achieve an 11-56× improvement in latency and a roughly 2× improvement in throughput compared to communicating with the standard version of the server over Unix domain sockets. In addition to offering better performance, our version is significantly simpler, suggesting that similar servers, written from scratch, would be easier to build using Hodor as a base.
Because our modified memcached only can interact with processes on the same node, it is no longer a distributed key-value store. There is no reason, however (other than code complexity), not to allow the memcached background process to provide a socket-based interface for remote clients while still permitting local clients to use the Hodor interface. We intend to support this option in a future release of the code.
More ambitiously, we are experimenting with the possibility of making memcached resilient to system crashes. As noted in Section 3.2, our Hodor memcached flushes its K-V store contents to the backing file when the bookkeeping process shuts down. Because the data in this file is position independent, it can be loaded back into memory and reused when the bookkeeping process is restarted. Significantly, this reload and reuse adds no extra code to the system. It may be particularly appealing when memcached is used not as a cache for off-line data but as a stand-alone in-memory store.
When memcached is used as a cache, and when the backing file is located on a magnetic or flash device, reloading may be only slightly faster than rebuilding-it saves the hash table update time, but not the I/O time. On the other hand, if the file is located in nonvolatile, direct-access (DAX) memory-e.g., on a machine with Intel Optane DIMMs [17]-then a reload can be almost instantaneous: it will consist only of page table updates.
The challenge, of course, is to support stand-alone use in the face of possible crashes, when rebuilding is not an option. In such an environment, operations must be not only isolated and consistent (in traditional database terminology [11]), but also failure-atomic and durable. Various groups are currently exploring mechanisms to provide failure atomicity for lock-based critical sections or transactions [4,6,16,22,26,35]; we look forward to leveraging this work.