In this work, we design SnapBPF, an eBPF-based snapshot prefetching mechanism, targeting VM-sandboxed serverless functions, which enables the efficient capture and prefetching of function working sets in kernel-space. SnapBPF deduplicates function working sets in memory and obviates the need for separately serializing them on disk. We complement SnapBPF with a lightweight paravirtualized interface to efficiently handle VM-sandbox memory allocations without requiring any snapshot pre-processing. Our evaluation shows that SnapBPF is able to match and improve state-of-the-art performance with regard to i) function invocation latency and ii) memory usage for concurrent function invocations, without separately serializing working sets on disk or requiring any preemptive snapshot scanning.

With the proliferation of Serverless Computing, the Function-asa-Service (FaaS) paradigm is nowadays ubiquitous. As a result, the domain has attracted extensive research, both in industry and academia, identifying opportunities and addressing limitations across all aspects of this new Cloud paradigm. Recently, FaaS providers have released production workload traces of their commercial platforms. These expose important characteristics, such as the execution time of function invocations, their number and the distribution of their inter-arrival times, which must be taken into account for a concrete evaluation of innovative solutions. Nevertheless, the Serverless ecosystem still lacks a unified evaluation methodology based on such information.

Large pages have been the de facto mitigation technique to address the translation overheads of virtual memory, with prior work mostly focusing on the large page sizes supported by the x86 architecture, i.e., 2MiB and IGiB. ARMv8-A and RISC- V support additional intermediate translation sizes, i.e., 64KiB and 32MiB, via OS-assisted TLB coalescing, but their performance potential has largely fallen under the radar due to the limited system software support. In this paper, we propose Elastic Translations (ET), a holistic memory management solution, to fully explore and exploit the aforementioned translation sizes for both native and virtualized execution. ET implements mechanisms that make the OS memory manager coalescing- aware, enabling the transparent and efficient use of intermediate- sized translations. ET also employs policies to guide translation size selection at runtime using lightweight HW -assisted TLB miss sampling. We design and implement ET for ARMv8-A in Linux and KVM. Our real-system evaluation of ET shows that ET improves the performance of memory intensive workloads by up to 39 % in native execution and by 30 % on average in virtualized execution.

Abstract Concurrent search trees (STs) are among the most widely used data structures to store and retrieve data in contemporary multithreaded applications. Despite the high amount of prior work, it still remains challenging to implement highly efficient concurrent STs. This is mainly due to the fact that both traditional synchronization methods (i.e., locks and atomic operations) and more novel ones (i.e., read‐copy‐update and transactional memory) fail to provide solutions that are generic and at the same time able to attain high performance under diverse workloads and contention levels. In this work, we present RCU‐HTM, a technique that combines read‐copy‐update (RCU) and hardware transactional memory (HTM), and: (a) supports the implementation of a concurrent version of any type of search tree, and (b) achieves high performance across all execution scenarios. We also incorporate a low‐overhead, epoch‐based memory reclamation scheme to make our RCU‐HTM trees practical for large‐scale long‐running applications. To showcase the capabilities of our technique, we implement and evaluate multiple RCU‐HTM trees and compare their performance with several state‐of‐the‐art competitors. More specifically, we apply RCU‐HTM to 12 different types of binary, B+ and (a,b)‐trees and compare against 18 state‐of‐the‐art implementations that use four different synchronization mechanisms, namely, locks, atomic operations, RCU, and HTM. We evaluate the trees under different levels of contention by varying the size of the tree, the operations mix, and the number of threads, for a total of 210 execution scenarios for each implementation. Our evaluation shows that in the majority of executions, RCU‐HTM trees outperform their state‐of‐the‐art alternatives, and even in the cases where they do not, their performance is very close to that of the best implementation.

In this work, we exploit RCU-HTM, a synchronization mechanism that combines Read-Copy-Update (RCU) and Hardware Transactional Memory (HTM) to support linearizable and highly efficient range queries in a concurrent B+-tree. Range queries in our B+-tree start with an asynchronized traversal and then perform a horizontal scan of leaf nodes, by following sibling pointers, using hardware transactions. Despite its simplicity, our RCU-HTM based B+-tree with range query support greatly outperforms state-of-the-art map data structures for range queries in several execution scenarios.

Designing scalable concurrent priority queues for contemporary NUMA servers is challenging. Several NUMA-unaware implementations can scale up to a high number of threads exploiting the potential parallelism of the insert operations. In contrast, in deleteMin-dominated workloads, threads compete for accessing the same memory locations, i.e. the first item in the priority queue. In such cases, NUMA-aware implementations are typically used, since they reduce the coherence traffic between the nodes of a NUMA system.

In this paper we introduce RCU-HTM, a technique that combines Read-Copy-Update (RCU) with Hardware Transactional Memory (HTM) to implement highly efficient concurrent Binary Search Trees (BSTs). Similarly to RCU-based algorithms, we perform the modifications of the tree structure in private copies of the affected parts of the tree rather than in-place. This allows threads that traverse the tree to proceed without any synchronization and without being affected by concurrent modifications. The novelty of RCU-HTM lies at leveraging HTM to permit multiple updating threads to execute concurrently. After appropriately modifying the private copy, we execute an HTM transaction, which atomically validates that all the affected parts of the tree have remained unchanged since they've been read and, only if this validation is successful, installs the copy in the tree structure.We apply RCU-HTM on AVL and Red-Black balanced BSTs and compare theirperformance to state-of-the-art lock-based, non-blocking, RCU- and HTM-basedBSTs. Our experimental evaluation reveals that BSTs implemented with RCU-HTMachieve high performance, not only for read-only operations, but also for update operations. More specifically, our evaluation includes a diverse range of tree sizes and operation workloads and reveals that BSTs based on RCU-HTM outperform other alternatives by more than 18%, on average, on a multi-core server with 44 hardware threads.

Hardware Transactional Memory (HTM) is nowadays available in several commercial and HPC targeted processors and in the future it will likely be available on systems that can accommodate a very large number of threads. Thus, it is essential for the research community to target on evaluating HTM on as many cores as possible in order to understand the virtues and limitations that come with it. In this paper we utilize HTM to parallelize accesses on a classic data structure, a red-black tree. With minimal programming effort, we implement a red-black tree by enclosing each operation in a single HTM transaction and evaluate it on two servers equipped with Intel Haswell-EP and IBM Power8 processors, supporting a large number of hardware threads, namely 56 and 160 respectively. Our evaluation reveals that applying HTM in such a simplistic manner allows scalability for up to a limited number of hardware threads. To fully utilize the underlying hardware we apply different optimizations on each platform.