OSDI '23 Technical Sessions

Today's high-performance applications heavily rely on various synchronization mechanisms, such as locks. While locks ensure mutual exclusion of shared data, their design impacts application scalability. Locks, as used in practice, move the lock-guarded shared data to the core holding it, which leads to shared data transfer among cores. This design adds unavoidable critical path latency leading to performance scalability issues. Meanwhile, some locks avoid this shared data movement by localizing the access to shared data on one core, and shipping the critical section to that specific core. However, such locks require modifying applications to explicitly package the critical section, which makes it virtually infeasible for complicated applications with large code-bases, such as the Linux kernel.

We propose transparent delegation, in which a waiter automatically encodes its critical section information on its stack and notifies the waiter. The lock holder executes the shipped critical section on the waiter's behalf using a light-weight context switch. Using transparent delegation, we design a family of locking protocols (TCLocks), which require zero modification to applications' logic. The evaluation shows that TCLocks provide up to 5.2x performance improvement compared with recent locking algorithms.

Context switching between kernel mode and user mode often causes prominent overhead, which slows down applications with frequent system calls (or syscalls), like applications with high I/O. The overhead is further amplified by security mechanisms like KPTI. To accelerate such applications, efforts have been made to remove syscalls from the I/O paths, mainly by combining drivers and apps in the same space, or batching syscalls. Nonetheless, such solutions require developers to refactor their applications, or even update hardware, which impedes their broad adoption.

In this paper, we propose another approach, userspace bypass, to accelerate syscall-intensive applications, by transparently moving userspace instructions into kernel. Userspace bypass requires no modification to userspace binaries or code, achieving full binary compatibility. Specifically, to avoid overhead caused by frequent syscalls, kernel identifies the short userspace execution path between consecutive system calls, and then converts the instructions in the path into code blocks with SFI guarantee. Every time kernel completes a syscall, it does not return to userspace but run the code block to emulate returning to userspace, which avoids the context switching overhead. According to our evaluation, small size I/O can be accelerated by up to 92%, intact Redis RPS can be improved by up to 11% and Nginx RPS increases by 8.5%. Our further analysis on the results show that the performance boost would be reduced if KPTI is turned off, but acceleration ratios are similar between the virtualized and physical environment.

Performance debugging is notoriously elusive—real-world performance problems are rarely clear-cut failures, but manifested through accumulation of fine-grained symptoms. Oftentimes, it is challenging to determine performance anomalies— absolute measures are unreliable, as system performance is inherently relative to workloads. Existing techniques focus on identifying absolute predicates that deviate between executions, which limits their application to performance problems.

This paper introduces relational debugging, a new technique that automatically pinpoints root causes of performance problems. The core idea is to capture and reason out relations between fine-grained runtime events. We show that relations provide immense utilities to explain performance anomalies and locate root causes. Relational debugging is highly effective with a minimal two executions (a good and a bad run), eliminating the pain point of producing and labeling many different executions required by traditional techniques.

We realize relational debugging by developing a practical tool named Perspect. Perspect directly operates on x86 binaries to accommodate real-world diagnosis scenarios. We evaluate Perspect on twelve challenging performance issues with various symptoms in Go runtime, MongoDB, Redis, and Coreutils. Perspect accurately located (or exclude) root causes of these issues. In particular, we used Perspect to diagnose two open bugs, where developers failed to find root causes—the root causes reported by Perspect was confirmed by developers. A controlled user study shows that Perspect can speedup the debugging times by at least 10.87 times.

Credential compromise is currently hard to detect and hard to recover from. To address this problem, we present larch, an accountable authentication framework with strong security and privacy properties. Larch provides strong user privacy while ensuring that every authentication is correctly recorded by the larch log server. Specifically, an attacker that compromises a user’s device cannot authenticate without creating evidence in the log, and the log cannot learn which web service (relying party) the user is authenticating to. To enable fast adoption, larch is backwards-compatible with relying parties that support FIDO2, TOTP, and password-based login. Furthermore, larch does not degrade the security and privacy a user already expects: the log server cannot authenticate on behalf of a user, and larch does not allow relying parties to link a user across accounts. We implement larch for FIDO2, TOTP, and password-based login. Given a client with 4 cores and a log server with 8 cores, an authentication with larch takes 143ms for FIDO2, 76ms for TOTP, and 75ms for passwords (excluding preprocessing, which takes 1.27s for TOTP).

State-of-the-art encrypted databases can be categorized into two types: one shields the whole DBMS engine in a trusted domain (Type-I), and the other uses a protected user-defined function (UDF) plugin (Type-II). However, the former lacks the essential ability of database administrator (DBA) maintainability, while the latter fails to guarantee the security of UDF’s interfaces. In particular, we devise smuggle attack that can infer Type-II’s secrets efficiently and stealthily.

We present HEDB, which prevents the smuggle attack yet retains maintainability. HEDB proposes a dual-mode EDB design based on our study of DBA maintenance tasks. The execution mode serves user query by isolating DBAs from UDF to resist smuggle attack, while the maintenance mode provides authenticated replay for DBMS maintenance and anonymized replay for privacy-preserving UDF troubleshooting. Evaluation shows that HEDB prevents smuggle attack effectively, and supports common maintenance tasks with 5.88% runtime cost and 9.26% storage cost.

GPUs have been deployed as the most ubiquitous accelerators for production applications like machine learning and autonomous driving in modern cloud computing systems. The security features of GPUs in such a public and shared environment becomes vitally important when the processed data are sensitive and expose user privacy. Recent advances in GPU TEEs are promising but fail to address the practical concerns of production applications on real-world legacy GPUs. We present Honeycomb, a software-based, secure, and efficient TEE for GPU computations. Honeycomb adopts commodity CPU TEE, a security monitor, and validated executions to enforce security isolation across different applications. Instead of admitting arbitrary, untrusted applications in conventional TEEs, Honeycomb only admits validated executions into the system. A validated execution consists of the actual GPU kernel in binary code and a corresponding validation proof to show that the runtime behaviors of the kernel confined to the security policy of Honeycomb. Honeycomb enables two TEE applications to securely exchange clear-text data using shared device memory on GPU. We have implemented Honeycomb on top of an AMD 6900XT GPU. Our evaluation shows that Honeycomb incurs a performance overhead for 8% for the inference application of ResNet 18 neural network model.

Confidential computing solutions are crucial to address the cloud privacy concerns. Although SGX has witnessed significant adoption in the cloud, the reliance on hardware implementation is restrictive for cloud providers in terms of orchestrating deployments and providing stronger security to their clients’ enclaves. eOPF addresses this limitation by providing a comprehensive, secure hypervisor-level instrumentation framework with the ability to monitor all enclave-OS interactions and implement protected services. eOPF overcomes several challenges including bridging the semantic gap between the hypervisor and SGX and attesting the co-location of the framework with enclaves. Using eOPF, we implement two protected services that provide platform resource orchestration and complementary enclave side-channel defense. Our evaluation shows that eOPF incurs very low performance overhead (<2%) in its default state and only a modest overhead (geometric mean of 17% on SPEC) when strong, complementary side-channel defenses are enabled, making eOPF an efficient and practical solution for the cloud.

The infinite capacity of cloud computing is an illusion: in reality, cloud providers cannot always have enough capacity of the right type, in the right place, at the right time to meet all demand. Consequently, cloud providers need to implement admission-control policies to ensure high availability to already accepted capacity requests. Admission control in the public cloud is hard because supply and demand change dynamically: hardware can become unavailable for many reasons, and actual VM consumption may vary due to diverse factors such as tenant scale-outs and fulfillment of VM reservations that are made by customers ahead of time. In this paper, we design and implement Kerveros -- a flexible admission-control system that has three desired properties: i) high computational scalability to handle a large inventory, ii) good packing efficiency to optimize resource usage, and iii) providing sufficient capacity for high VM availability. To achieve this, Kerveros uses novel bookkeeping techniques to quickly determine the available capacity for incoming VM requests. Our system has been deployed in PCloud, a large public cloud provider. Results from both simulations and production confirm that Kerveros achieves more than four nines of availability while sustaining request processing latencies of a few milliseconds.

Virtual machines are the basis of resource isolation in today's public clouds, yet the security risks of entrusting that isolation to a cloud provider's hypervisor are substantial. Such concerns have motivated the design of hardware extensions for "confidential VMs" that seek to remove the hypervisor from the trusted computing base by adding a highly-privileged firmware layer that checks hypervisor actions, and supports memory encryption and remote attestation. However, the hypervisor retains control of resource management and observes associated actions of the guest including nested page table faults and CPU scheduling, and thus confidential VMs remain vulnerable to an ever-changing variety of hypervisor-level side channel attacks. Bare-metal cloud servers avoid such leaks, but remain a niche due to the high cost of dedicated hardware.

We observe that typical cloud VMs run with a static allocation of memory and discrete cores, and increasingly rely on I/O offload, thus negating the apparent need for a hypervisor and the fragile hypervisor/guest isolation boundary. Our design, core slicing, enables multiple untrusted guest OSes to run on shared bare-metal hardware. To ensure isolation without the complexity of virtualization, we propose simple hardware extensions that restrict guests to a static slice of a machine's cores, memory and virtual I/O devices, and delegate resource allocation to a dedicated management slice. We demonstrate practicality and evaluate performance with prototypes for RISC-V and x86.

Model parallelism is conventionally viewed as a method to scale a single large deep learning model beyond the memory limits of a single device. In this paper, we demonstrate that model parallelism can be additionally used for the statistical multiplexing of multiple devices when serving multiple models, even when a single model can fit into a single device. Our work reveals a fundamental trade-off between the overhead introduced by model parallelism and the opportunity to exploit statistical multiplexing to reduce serving latency in the presence of bursty workloads. We explore the new trade-off space and present a novel serving system, Beta, that determines an efficient strategy for placing and parallelizing collections of large machine-learning models across a distributed cluster. Evaluation results on production workloads show that Beta can process requests at up to 10x higher rates or 6x more burstiness while staying within latency constraints for more than 99% of requests.

With the growing demand for processing higher fidelity data and the use of faster computing cores in newer hardware accelerators, modern deep neural networks (DNNs) are becoming increasingly memory intensive. A disparity between underutilized computing cores and saturated memory bandwidth has been observed in various popular DNN models. This inefficiency is caused by both the conventional treatment of DNNs as compute-intensive workloads and the lack of holistic memory access optimization in DNN models.

In this paper, we introduce Welder, a deep learning compiler that optimizes the execution efficiency from a holistic memory access perspective. The core of Welder is tile-graph, an abstraction that facilitates fine-grained data management at tile level. By leveraging the observation of optimization independence across memory layers, Welder is able to decompose the whole combinatorial DNN optimization space into several independent ones and effectively trade off between intra- and inter-operator data reuse using a tile traffic-based cost model. This allows Welder to unify previous ad-hoc memory optimizations into a single space, generate efficient execution plans with 74 more optimization patterns, and outperform state-of-the-art solutions significantly. Welder is also able to handle DNN models with arbitrarily large input by combining the existing accelerator memory and host memory as a whole system.

Boosting the execution performance of deep neural networks (DNNs) is critical due to their wide adoption in real-world applications. However, existing approaches to optimizing the tensor computation of a DNN only consider transformations representable by a fixed set of predefined tensor operators, resulting a restricted optimized exploration space. To address this, we propose EINNET, the first derivation-based tensor program optimizer. EINNET optimizes tensor programs by leveraging transformations between general tensor algebra expressions and automatically creating new operators desired by transformations, enabling a significantly larger search space that includes those supported by prior works. Evaluation on seven DNNs shows that EINNET outperforms existing optimizers by up to 2.72× (1.52× on average) on A100 and up to 2.68× (1.55× on average) on V100, respectively.

The increasing size of input graphs for graph neural networks (GNNs) highlights the demand for using multi-GPU platforms. However, existing multi-GPU GNN systems optimize the computation and communication individually based on the conventional practice of scaling dense DNNs. For irregularly sparse and fine-grained GNN workloads, such solutions miss the opportunity to jointly schedule/optimize the computation and communication operations for high-performance delivery.

To this end, we propose MGG, a novel system design to accelerate full-graph GNNs on multi-GPU platforms. The core of MGG is its novel fine-grained dynamic software pipeline to facilitate fine-grained computation-communication overlapping within a GPU kernel. Specifically, MGG introduces GNN-tailored pipeline construction and GPU-aware pipeline mapping to facilitate workload balancing and operation overlapping. MGG also incorporates an intelligent runtime design with analytical modeling and optimization heuristics to dynamically improve the GNN execution performance. Extensive evaluation reveals that MGG outperforms state-of-the-art full-graph GNN systems across various settings: on average 4.55x, 5.10x, and 12.75x faster than DGL, MGG-UVM, and ROC frameworks, respectively. MGG is implemented with ~9.9K LoC and is open-sourced at https://anonymous.4open.science/r/MGG-Artifact-7ECF.

Deep learning recommendation models (DLRMs) are using increasingly larger embedding tables to represent categori- cal sparse features. Each embedding row of the table repre- sents the trainable weight vector of a specific feature instance. While more embedding rows typically enable better model accuracy by considering more feature instances, they lead to large deployment cost and slow model execution.

Unlike existing efforts that primarily focus on optimizing DLRMs for the given embedding, we present a complementary system, AdaEmbed, to reduce the size of embeddings needed for the same DLRM accuracy via in-training embed- ding pruning. Our key insight is that the data distribution of embedding instances and model (embedding) weights vary across embedding rows and over time, implying varying em- bedding importance to model accuracy. However, identifying important embeddings and then enforcing pruning for modern DLRMs with up to billions of embeddings (terabytes) is challenging. Given the total embedding size, AdaEmbed considers embeddings with higher runtime access frequency and larger training gradients to be more important, and it adaptively determines per-feature embedding size to dynamically prune less important embeddings at scale. Our evaluations in industrial settings show that AdaEmbed saves 35-60% embedding size needed in deployment and improves model execution speed by 11-34%, while achieving noticeable accuracy gains.

Work stealing is a widely-used scheduling technique for parallel processing on multicore. Each core owns a queue of tasks and avoids idling by stealing tasks from other queues. Prior work mostly focuses on balancing workload among cores, disregarding whether stealing may adversely impact the owner's performance or hinder synchronization optimizations. Real-world industrial runtimes for parallel processing heavily rely on work-stealing queues for scalability, and such queues can become bottlenecks to their performance.

We present Block-based Work Stealing (BWoS), a novel and pragmatic design that splits per-core queues into multiple blocks. Thieves and owners rarely operate on the same blocks, greatly removing interferences and enabling aggressive optimizations on the owner's synchronization with thieves. Furthermore, BWoS enables a novel probabilistic stealing policy that guarantees thieves steal from longer queues with higher probability. In our evaluation, using BWoS improves performance by up to 1.25x in the Renaissance macrobenchmark when applied to Java GC, provides average 1.26x speedup in JSON processing when applied to Go runtime, and improves maximum throughput of Hyper HTTP server by 1.12x when applied to Rust Tokio runtime. In microbenchmarks, it provides 8-11x better performance than state-of-the-art designs. We have formally verified and optimized BWoS on weak memory models with a model-checking-based framework.

Multi-version concurrency control (MVCC) is a widely used, sophisticated approach for handling concurrent transactions in a database system. vMVCC is the first MVCC-based database that comes with a machine-checked proof of correctness, providing clients with a guarantee that it will correctly handle all transactions despite a sophisticated design and implementation that might otherwise be error-prone. vMVCC is implemented in Go, as a single-node in-memory database, and uses several optimizations, such as RDTSC-based timestamps, to achieve high performance (30--71% the throughput of Silo, a state-of-the-art in-memory database, for YCSB and TPC-C workloads). Formally specifying and verifying vMVCC required adopting sophisticated proof techniques, such as prophecy variables and logical atomicity, owing to the fact that MVCC transactions can linearize at timestamps prior to transaction execution.

We present Seagull, an automated verification framework for concurrent code with shared memory. Seagull scales to complex systems by splitting system-wide proofs into isolated concerns such that each can be substantially automated. As a starting point, Seagull’s ownership type system allows a developer to straightforwardly prove both data safety and the logical correctness of thread-local operations. Seagull then introduces the concept of a Localized Transition System, which connects the correctness of local actions to the correctness of the entire system. We demonstrate Seagull by verifying two state-of-the-art concurrent systems comprising thousands of lines: a library for black-box replication on NUMA architectures, and a highly concurrent page cache.

Datacenter applications have been increasingly applying RDMA for the ultra-low latency and low CPU overhead. However, RDMA-capable NICs (RNICs) of different vendors and different generations from the same vendors do not cooperate well, which causes bandwidth imbalance in the production network. Our observation of the heterogeneous RNICs is that though the data path functions of these RNICs follow the same RoCEv2 specifications, their control path functions are vendor and version specific. To this end, we propose Flor, an open framework that provides a flexible control plane in software and a unified hardware plane by adopting heterogeneous RNICs. The hardware plane requires no changes of current specifications. The software plane can run in NPU of RNICs, DPUs and host CPUs, following which we build up strengthen reliable transport over the large-scale lossy Ethernet. We implemented and evaluated Flor in both testbed and production clusters over Intel E180, Mellanox CX-4 and CX-5 and Broadcom RNICs. Experiments show that Flor achieves comparable performance to vanilla RDMA in many scenarios including 1/4096 packet loss, 6000:1 incast, and large-scale cross-pod communication. Flor mitigates the performance gap of CX-4 and CX-5 RNICs from 24.3% to 1.3% when they are deployed together without PFC dependency.

Datacenter applications are often structured as many interconnected microservices, and service mesh has become a popular approach to route RPC traffic among services. This paper presents perhaps one of the world's largest service meshes called ServiceRouter (SR), which has been in production since 2012. SR differs from publicly known service meshes and load-balancing solutions in several important ways. First, SR is designed from the ground up for hyperscale, currently employing O(10^6) of L7 routers to route O(10^10) of requests per second across O(10^4) services. Second, SR's novel use of an embedded routing library, as opposed to the common approach of using sidecar or remote proxies, reduces the hardware cost of our hyperscale service mesh by O(10^5) machines. Third, SR provides built-in support for sharded services, which account for 92% of the total RPC requests in our fleet, whereas existing general-purpose service meshes do not support sharded services. Finally, SR introduces the concept of locality rings to simultaneously minimize RPC latency and balance load across geo-distributed regions, which to our knowledge has not been attempted before.

Today, most communication between NICs and software requires exchanging fixed sized packet-buffers. This packetized interface was designed for an era when NICs implemented few offloads, and software implemented the logic for translating between application data and packets. However, both NICs and networked software have evolved: modern NICs implement hardware offloads, e.g., TSO, LRO, and serialization offloads that can more efficiently translate between application data and packets. Furthemore, modern software increasingly batches network I/O to reduce overheads. These changes have led to a mismatch between the packetized interface, which assumes that the NIC and software exchange fixed sized buffers, and the features provided by modern NICs and used by modern software. This incongruence between interface and data adds software complexity and I/O overheads, which in turn limit communication performance.

This paper proposes, Ensō, a new streaming NIC to software interface designed to better support how NICs and software interact today. At its core, Ensō eschews fixed size buffers, and instead structures communication as a stream that can be used to send arbitrary data sizes. We show that this change reduces software overheads, reduces PCIe bandwidth requirements, and leads to fewer cache misses. These improvements allow an Ensō based NIC to saturate a 100 Gbps link with minimum-sized packets (forwarding at 148.8 Mpps) using a single core, and improves throughput for high-performance network applications by 1.5-5x.