@inproceedings{10.1145/3447786.3456225,
author = {Wang, Yawen and Arya, Kapil and Kogias, Marios and Vanga, Manohar and Bhandari, Aditya and Yadwadkar, Neeraja J. and Sen, Siddhartha and Elnikety, Sameh and Kozyrakis, Christos and Bianchini, Ricardo},
title = {SmartHarvest: harvesting idle CPUs safely and efficiently in the cloud},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456225},
doi = {10.1145/3447786.3456225},
abstract = {We can increase the efficiency of public cloud datacenters by harvesting allocated but temporarily idling CPU cores from customer virtual machines (VMs) to run batch or analytics workloads. Even small efficiency gains translate into substantial savings, since provisioning and operating a datacenter costs hundreds of millions of dollars per year. The main challenge is to harvest idle cores with little or no impact on customer VMs, which could be running latency-sensitive services and are essentially black-boxes to the cloud provider.We introduce ElasticVM, a new VM type that can run batch workloads cheaply using mainly harvested cores. We also propose SmartHarvest, a system that dynamically manages the number of cores available to ElasticVMs in each fine-grained time window. SmartHarvest uses online learning to predict the core demand of primary, customer VMs and compute the number of cores that can be safely harvested. Our results show that SmartHarvest can harvest a significant amount of CPU resources without increasing the 99th-percentile tail latency of latency-critical primary workloads by more than 10\%. Unlike static harvesting techniques that rely on offline profiling, SmartHarvest is robust to different primary workloads, batch workloads, and load changes. Finally, we show that the online learning in SmartHarvest is complementary to systems optimizations for VM management.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {1–16},
numpages = {16},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456226,
author = {Jiang, Xiaolin and Xu, Chengshuo and Yin, Xizhe and Zhao, Zhijia and Gupta, Rajiv},
title = {Tripoline: generalized incremental graph processing via graph triangle inequality},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456226},
doi = {10.1145/3447786.3456226},
abstract = {For compute-intensive iterative queries over a streaming graph, it is critical to evaluate the queries continuously and incrementally for best efficiency. However, the existing incremental graph processing requires a priori knowledge of the query (e.g., the source vertex of a vertex-specific query); otherwise, it has to fall back to the expensive full evaluation that starts from scratch.To alleviate this restriction, this work presents a principled solution to generalizing the incremental graph processing, such that queries, without their a priori knowledge, can also be evaluated incrementally. The solution centers around the concept of graph triangle inequalities, an idea inspired by the classical triangle inequality principle in the Euclidean space. Interestingly, similar principles can also be derived for many vertex-specific graph problems. These principles can help establish rigorous constraints between the evaluation of one graph query and the results of another, thus enabling reusing the latter to accelerate the former. Based on this finding, a novel streaming graph system, called Tripoline, is built which enables incremental evaluation of queries without their a priori knowledge. Built on top of a state-of-the-art shared-memory streaming graph engine (Aspen), Tripoline natively supports high-throughput low-cost graph updates. A systematic evaluation with a set of eight vertex-specific graph problems and four real-world large graphs confirms both the effectiveness of the proposed techniques and the efficiency of Tripoline.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {17–32},
numpages = {16},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456227,
author = {Lim, Hwijoon and Bai, Wei and Zhu, Yibo and Jung, Youngmok and Han, Dongsu},
title = {Towards timeout-less transport in commodity datacenter networks},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456227},
doi = {10.1145/3447786.3456227},
abstract = {Despite recent advances in datacenter networks, timeouts caused by congestion packet losses still remain a major cause of high tail latency. Priority-based Flow Control (PFC) was introduced to make the network lossless, but its Head-of-Line blocking nature causes various performance and management problems. In this paper, we ask if it is possible to design a network that achieves (near) zero timeout only using commodity hardware in datacenters.Our answer is TLT, an extension to existing transport designed to eliminate timeouts. We are inspired by the observation that only certain types of packet drops cause timeouts. Therefore, instead of blindly dropping (TCP) or not dropping packets at all (RoCEv2), TLT proactively drops some packets to ensure the delivery of more important ones, whose losses may cause timeouts. It classifies packets at the host and leverages color-aware thresholding, a feature widely supported by commodity switches, to proactively drop some less important packets. We implement TLT prototypes using VMA to test with real applications. Our testbed evaluation on Redis shows that TLT reduces 99\%-ile FCT up to 91.7\% on handling bursts of SET operations. In large-scale simulations, TLT augments diverse datacenter transports, from widely-used (TCP, DCTCP, DCQCN) to state-of-the-art (IRN and HPCC), by achieving up to 81\% lower tail latency.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {33–48},
numpages = {16},
keywords = {RoCE, TCP, datacenter networking, low-latency transport},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456228,
author = {Vasilakis, Nikos and Kallas, Konstantinos and Mamouras, Konstantinos and Benetopoulos, Achilles and Cvetkovi\'{c}, Lazar},
title = {PaSh: light-touch data-parallel shell processing},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456228},
doi = {10.1145/3447786.3456228},
abstract = {This paper presents PaSh, a system for parallelizing POSIX shell scripts. Given a script, PaSh converts it to a dataflow graph, performs a series of semantics-preserving program transformations that expose parallelism, and then converts the dataflow graph back into a script---one that adds POSIX constructs to explicitly guide parallelism coupled with PaSh-provided Unix-aware runtime primitives for addressing performance- and correctness-related issues. A lightweight annotation language allows command developers to express key parallelizability properties about their commands. An accompanying parallelizability study of POSIX and GNU commands---two large and commonly used groups---guides the annotation language and optimized aggregator library that PaSh uses. PaSh's extensive evaluation over 44 unmodified Unix scripts shows significant speedups (0.89--61.1\texttimes{}, avg: 6.7\texttimes{}) stemming from the combination of its program transformations and runtime primitives.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {49–66},
numpages = {18},
keywords = {POSIX, Unix, automatic parallelization, pipelines, shell, source-to-source compiler},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456229,
author = {Wang, Lei and Yin, Qiang and Tian, Chao and Yang, Jianbang and Chen, Rong and Yu, Wenyuan and Yao, Zihang and Zhou, Jingren},
title = {FlexGraph: a flexible and efficient distributed framework for GNN training},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456229},
doi = {10.1145/3447786.3456229},
abstract = {Graph neural networks (GNNs) aim to learn a low-dimensional feature for each vertex in the graph from its input high-dimensional feature, by aggregating the features of the vertex's neighbors iteratively. This paper presents Flex-Graph, a distributed framework for training GNN models. FlexGraph is able to efficiently train GNN models with flexible definitions of neighborhood and hierarchical aggregation schemes, which are the two main characteristics associated with GNNs. In contrast, existing GNN frameworks are usually designed for GNNs having fixed definitions and aggregation schemes. They cannot support different kinds of GNN models well simultaneously. Underlying FlexGraph are a simple GNN programming abstraction called NAU and a compact data structure for modeling various aggregation operations. To achieve better performance, FlexGraph is equipped with a hybrid execution strategy to select proper and efficient operations according to different contexts during aggregating neighborhood features, an application-driven workload balancing strategy to balance GNN training workload and reduce synchronization overhead, and a pipeline processing strategy to overlap computations and communications. Using real-life datasets and GNN models GCN, PinSage and MAGNN, we verify that NAU makes FlexGraph more expressive than prior frameworks (e.g., DGL and Euler) which adopt GAS-like programming abstractions, e.g., it can handle MAGNN that is beyond the reach of DGL and Euler. The evaluation further shows that FlexGraph outperforms the state-of-the-art GNN frameworks such as DGL and Euler in training time by on average 8.5\texttimes{} on GCN and PinSage.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {67–82},
numpages = {16},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456230,
author = {Mariappan, Mugilan and Che, Joanna and Vora, Keval},
title = {DZiG: sparsity-aware incremental processing of streaming graphs},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456230},
doi = {10.1145/3447786.3456230},
abstract = {State-of-the-art streaming graph processing systems that provide Bulk Synchronous Parallel (BSP) guarantees remain oblivious to the computation sparsity present in iterative graph algorithms, which severely limits their performance. In this paper we propose DZiG, a high-performance streaming graph processing system that retains efficiency in presence of sparse computations while still guaranteeing BSP semantics. At the heart of DZiG is: (1) a sparsity-aware incremental processing technique that expresses computations in a recursive manner to be able to safely identify and prune updates (hence retaining sparsity); (2) a simple change-driven programming model that naturally exposes sparsity in iterative computations; and, (3) an adaptive processing model that automatically changes the incremental computation strategy to limit its overheads when computations become very sparse. DZiG outperforms state-of-the-art streaming graph processing systems, and pushes the boundary of dependency-driven processing for streaming graphs to over 10 million simultaneous mutations, which is orders of magnitude higher compared to the state-of-the-art systems.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {83–98},
numpages = {16},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456231,
author = {Kim, Jae-Yun and Lee, Junmo and Koo, Yeonjae and Park, Sanghyeon and Moon, Soo-Mook},
title = {Ethanos: efficient bootstrapping for full nodes on account-based blockchain},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456231},
doi = {10.1145/3447786.3456231},
abstract = {Ethereum is a popular account-based blockchain whose number of accounts and transactions has skyrocketed, causing its data explosion. As a result, ordinary clients using PCs or smartphones cannot easily bootstrap as a full node, but rely on other full nodes to verify transactions, thus being exposed to security risks. The most serious overhead is caused by synchronizing the state of all accounts in the block's state trie, which takes several tens of gigabytes. Observing that more than 95\% of the accounts are dormant, we propose a novel state optimization technique, named Ethanos. Ethanos downsizes the state trie by periodically emptying it, and then re-build it only with the active accounts used in the period's transactions. Ethanos runs transactions using the accounts available in the current period's state trie as well as those available at the end of the previous period's state trie. For an account in neither of the tries, the account first restores itself by transmitting a restore transaction. One important result of this state management is that a node can now bootstrap only with the latest period's state trie, yet can fully verify all transactions thereafter. We evaluated Ethanos with real Ethereum transactions for 300,000 blocks from the 7.0 million block, with a one-week period of emptying the state trie. Our result shows that Ethanos can sharply reduce the state trie, with only a tiny fraction of the restore transactions. More importantly, unlike the Ethereum state trie which continues to grow as time goes on, the Ethanos state trie size at the end of each period is bounded by a few hundred MB, when there are more than one million, one-week-active accounts.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {99–113},
numpages = {15},
keywords = {blockchain, state trie, synchronization},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456232,
author = {Russinovich, Mark and Govindaraju, Naga and Raghuraman, Melur and Hepkin, David and Schwartz, Jamie and Kishan, Arun},
title = {Virtual machine preserving host updates for zero day patching in public cloud},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456232},
doi = {10.1145/3447786.3456232},
abstract = {Host software updates are critical to ensure the security, reliability and compliance of public clouds. Many updates require a virtualization component restart or operating system reboot. Virtual machines (VMs) running on the updated servers must either be restarted or live migrated off. Reboots can result in downtime for the VMs on the order of ten minutes, and has further impact on the workloads running in the VMs because cached state is lost. Live migration (LM) is a technology that can avoid the need to shutdown VMs. However, LM requires turn space in the form of already-patched hosts, consumes network, CPU and other resources that scale with the amount of and level of activity of VM, and has variable impact on VM performance and availability, making it too expensive and disruptive for zero-day security updates that must be applied across an entire fleet on the order of hours. We present a novel update technology, virtual machine preserving host updates (VM-PHU), that does not require turn space, consumes no network and little CPU, preserves VM state, and causes minimal VM blackout time that does not scale with VM resource usage. VM-PHU persists the memory and device state of all running guest VMs, reboots the host and virtualization components into updated code, restores the state of the VMs, and then resumes them. VM-PHU makes use of several techniques to minimize VM blackout time. One is to use kernel soft reboot (KSR) to directly transition to an updated host operating system, bypassing firmware reset of the server and attached devices. To minimize resource consumption and VM disruption, VM-PHU leaves VM memory in physical memory pages and other state in persisted pages across the soft reboot, and VM-PHU implements a mechanism called fast close to enable a reboot to proceed without waiting for the completion of in-flight VM I/Os to remote storage devices. We have implemented VM-PHU in Microsoft Azure hosting millions of servers and show results of several zero-day updates that demonstrate VM blackout times on the order of seconds. VM-PHU provides significant benefits to both customers and public cloud vendors by minimizing application downtime while enabling fast and resource efficient updates, including zero-day patches.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {114–129},
numpages = {16},
keywords = {cloud computing, data centers, virtualization and security},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456233,
author = {Cai, Zhenkun and Yan, Xiao and Wu, Yidi and Ma, Kaihao and Cheng, James and Yu, Fan},
title = {DGCL: an efficient communication library for distributed GNN training},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456233},
doi = {10.1145/3447786.3456233},
abstract = {Graph neural networks (GNNs) have gained increasing popularity in many areas such as e-commerce, social networks and bio-informatics. Distributed GNN training is essential for handling large graphs and reducing the execution time. However, for distributed GNN training, a peer-to-peer communication strategy suffers from high communication overheads. Also, different GPUs require different remote vertex embeddings, which leads to an irregular communication pattern and renders existing communication planning solutions unsuitable. We propose the distributed graph communication library (DGCL) for efficient GNN training on multiple GPUs. At the heart of DGCL is a communication planning algorithm tailored for GNN training, which jointly considers fully utilizing fast links, fusing communication, avoiding contention and balancing loads on different links. DGCL can be easily adopted to extend existing single-GPU GNN systems to distributed training. We conducted extensive experiments on different datasets and network configurations to compare DGCL with alternative communication schemes. In our experiments, DGCL reduces the communication time of the peer-to-peer communication by 77.5\% on average and the training time for an epoch by up to 47\%.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {130–144},
numpages = {15},
keywords = {distributed and parallel training, graph neural networks, network communication},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456234,
author = {Katsarakis, Antonios and Ma, Yijun and Tan, Zhaowei and Bainbridge, Andrew and Balkwill, Matthew and Dragojevic, Aleksandar and Grot, Boris and Radunovic, Bozidar and Zhang, Yongguang},
title = {Zeus: locality-aware distributed transactions},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456234},
doi = {10.1145/3447786.3456234},
abstract = {State-of-the-art distributed in-memory datastores (FaRM, FaSST, DrTM) provide strongly-consistent distributed transactions with high performance and availability. Transactions in those systems are fully general; they can atomically manipulate any set of objects in the store, regardless of their location. To achieve this, these systems use complex distributed transactional protocols. Meanwhile, many workloads have a high degree of locality. For such workloads, distributed transactions are an overkill as most operations only access objects located on the same server - if sharded appropriately.In this paper, we show that for these workloads, a single-node transactional protocol combined with dynamic object re-sharding and asynchronously pipelined replication can provide the same level of generality with better performance, simpler protocols, and lower developer effort. We present Zeus, an in-memory distributed datastore that provides general transactions by acquiring all objects involved in the transaction to the same server and executing a single-node transaction on them. Zeus is fault-tolerant and strongly-consistent. At the heart of Zeus is a reliable dynamic object sharding protocol that can move 250K objects per second per server, allowing Zeus to process millions of transactions per second and outperform more traditional distributed transactions on a wide range of workloads that exhibit locality.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {145–161},
numpages = {17},
keywords = {availability, dynamic sharding, locality, pipelining, replication, strict serializability, transactions},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456235,
author = {Ngoc, Tu Dinh and Teabe, Boris and Tchana, Alain and Muller, Gilles and Hagimont, Daniel},
title = {Mitigating vulnerability windows with hypervisor transplant},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456235},
doi = {10.1145/3447786.3456235},
abstract = {The vulnerability window of a hypervisor regarding a given security flaw is the time between the identification of the flaw and the integration of a correction/patch in the running hypervisor. Most vulnerability windows, regardless of severity, are long enough (several days) that attackers have time to perform exploits. Nevertheless, the number of critical vulnerabilities per year is low enough to allow an exceptional solution. This paper introduces hypervisor transplant, a solution for addressing vulnerability window of critical flaws. It involves temporarily replacing the current datacenter hypervisor (e.g., Xen) which is subject to a critical security flaw, by a different hypervisor (e.g., KVM) which is not subject to the same vulnerability.We build HyperTP, a generic framework which combines in a unified way two approaches: in-place server micro-reboot-based hypervisor transplant (noted InPlaceTP) and live VM migration-based hypervisor transplant (noted MigrationTP). We describe the implementation of HyperTP and its extension for transplanting Xen with KVM and vice versa. We also show that HyperTP is easy to integrate with the OpenStack cloud computing platform. Our evaluation results show that HyperTP delivers satisfactory performance: (1) MigrationTP takes the same time and impacts virtual machines (VMs) with the same performance degradation as normal live migration. (2) the downtime imposed by InPlaceTP on VMs is in the same order of magnitude (1.7 seconds for a VM with 1 vCPU and 1 GB of RAM) as in-place upgrade of homogeneous hypervisors based on server micro-reboot.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {162–177},
numpages = {16},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456236,
author = {Enes, Vitor and Baquero, Carlos and Gotsman, Alexey and Sutra, Pierre},
title = {Efficient replication via timestamp stability},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456236},
doi = {10.1145/3447786.3456236},
abstract = {Modern web applications replicate their data across the globe and require strong consistency guarantees for their most critical data. These guarantees are usually provided via state-machine replication (SMR). Recent advances in SMR have focused on leaderless protocols, which improve the availability and performance of traditional Paxos-based solutions. We propose Tempo - a leaderless SMR protocol that, in comparison to prior solutions, achieves superior throughput and offers predictable performance even in contended workloads. To achieve these benefits, Tempo timestamps each application command and executes it only after the timestamp becomes stable, i.e., all commands with a lower timestamp are known. Both the timestamping and stability detection mechanisms are fully decentralized, thus obviating the need for a leader replica. Our protocol furthermore generalizes to partial replication settings, enabling scalability in highly parallel workloads. We evaluate the protocol in both real and simulated geo-distributed environments and demonstrate that it outperforms state-of-the-art alternatives.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {178–193},
numpages = {16},
keywords = {consensus, fault tolerance, geo-replication},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456237,
author = {Zhang, Wenhui and Zhao, Xingsheng and Jiang, Song and Jiang, Hong},
title = {ChameleonDB: a key-value store for optane persistent memory},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456237},
doi = {10.1145/3447786.3456237},
abstract = {The emergence of Intel's Optane DC persistent memory (Optane Pmem) draws much interest in building persistent key-value (KV) stores to take advantage of its high throughput and low latency. A major challenge in the efforts stems from the fact that Optane Pmem is essentially a hybrid storage device with two distinct properties. On one hand, it is a high-speed byte-addressable device similar to DRAM. On the other hand, the write to the Optane media is conducted at the unit of 256 bytes, much like a block storage device. Existing KV store designs for persistent memory do not take into account of the latter property, leading to high write amplification and constraining both write and read throughput. In the meantime, a direct re-use of a KV store design intended for block devices, such as LSM-based ones, would cause much higher read latency due to the former property.In this paper, we propose ChameleonDB, a KV store design specifically for this important hybrid memory/storage device by considering and exploiting these two properties in one design. It uses LSM tree structure to efficiently admit writes with low write amplification. It uses an in-DRAM hash table to bypass LSM-tree's multiple levels for fast reads. In the meantime, ChameleonDB may choose to opportunistically maintain the LSM multi-level structure in the background to achieve short recovery time after a system crash. ChameleonDB's hybrid structure is designed to be able to absorb sudden bursts of a write workload, which helps avoid long-tail read latency.Our experiment results show that ChameleonDB improves write throughput by 3.3\texttimes{} and reduces read latency by around 60\% compared with a legacy LSM-tree based KV store design. ChameleonDB provides performance competitive even with KV stores using fully in-DRAM index by using much less DRAM space. Compared with CCEH, a persistent hash table design, ChameleonDB provides 6.4\texttimes{} higher write throughput.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {194–209},
numpages = {16},
keywords = {Optane DC, key-value store, persistent-memory},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456238,
author = {Chen, Xusheng and Song, Haoze and Jiang, Jianyu and Ruan, Chaoyi and Li, Cheng and Wang, Sen and Zhang, Gong and Cheng, Reynold and Cui, Heming},
title = {Achieving low tail-latency and high scalability for serializable transactions in edge computing},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456238},
doi = {10.1145/3447786.3456238},
abstract = {A distributed database utilizing the wide-spread edge computing servers to provide low-latency data access with the serializability guarantee is highly desirable for emerging edge computing applications. In an edge database, nodes are divided into regions, and a transaction can be categorized as intra-region (IRT) or cross-region (CRT) based on whether it accesses data in different regions. In addition to serializability, we insist that a practical edge database should provide low tail latency for both IRTs and CRTs, and such low latency must be scalable to a large number of regions. Unfortunately, none of existing geo-replicated serializable databases or edge databases can meet such requirements.In this paper, we present Dast (Decentralized Anticipate and STretch), the first edge database that can meet the stringent performance requirements with serializability. Our key idea is to order transactions by anticipating when they are ready to execute: Dast binds an IRT to the latest timestamp and binds a CRT to a future timestamp to avoid the coordination of CRTs blocking IRTs. Dast also carries a new stretchable clock abstraction to tolerate inaccurate anticipations and to handle cross-region data reads. Our evaluation shows that, compared to three relevant serializable databases, Dast's 99-percentile latency was 87.9\%~93.2\% lower for IRTs and 27.7\%~70.4\% lower for CRTs; Dast's low latency is scalable to a large number of regions.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {210–227},
numpages = {18},
keywords = {distributed transaction, edge computing, scalability, tail-latency},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456239,
author = {Mvondo, Djob and Bacou, Mathieu and Nguetchouang, Kevin and Ngale, Lucien and Pouget, St\'{e}phane and Kouam, Josiane and Lachaize, Renaud and Hwang, Jinho and Wood, Tim and Hagimont, Daniel and De Palma, No\"{e}l and Batchakui, Bernab\'{e} and Tchana, Alain},
title = {OFC: an opportunistic caching system for FaaS platforms},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456239},
doi = {10.1145/3447786.3456239},
abstract = {Cloud applications based on the "Functions as a Service" (FaaS) paradigm have become very popular. Yet, due to their stateless nature, they must frequently interact with an external data store, which limits their performance. To mitigate this issue, we introduce OFC, a transparent, vertically and horizontally elastic in-memory caching system for FaaS platforms, distributed over the worker nodes. OFC provides these benefits cost-effectively by exploiting two common sources of resource waste: (i) most cloud tenants overprovision the memory resources reserved for their functions because their footprint is non-trivially input-dependent and (ii) FaaS providers keep function sandboxes alive for several minutes to avoid cold starts. Using machine learning models adjusted for typical function input data categories (e.g., multimedia formats), OFC estimates the actual memory resources required by each function invocation and hoards the remaining capacity to feed the cache. We build our OFC prototype based on enhancements to the OpenWhisk FaaS platform, the Swift persistent object store, and the RAM-Cloud in-memory store. Using a diverse set of workloads, we show that OFC improves by up to 82 \% and 60 \% respectively the execution time of single-stage and pipelined functions.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {228–244},
numpages = {17},
keywords = {cache, cloud computing, functions as a service (FaaS), latency, serverless},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456240,
author = {Gavrielatos, Vasilis and Katsarakis, Antonios and Nagarajan, Vijay},
title = {Odyssey: the impact of modern hardware on strongly-consistent replication protocols},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456240},
doi = {10.1145/3447786.3456240},
abstract = {Get/Put Key-Value Stores (KVSes) rely on replication protocols to enforce consistency and guarantee availability. Today's modern hardware, with manycore servers and RDMA-capable networks, challenges the conventional wisdom on protocol design. In this paper, we investigate the impact of modern hardware on the performance of strongly-consistent replication protocols.First, we create an informal taxonomy of replication protocols, based on which we carefully select 10 protocols for analysis. Secondly, we present Odyssey, a framework tailored towards protocol implementation for multi-threaded, RDMA-enabled, in-memory, replicated KVSes. We implement all 10 protocols over Odyssey, and perform the first apples-to-apples comparison of replication protocols over modern hardware.Our comparison characterizes the protocol design space, revealing the performance capabilities of different classes of protocols on modern hardware. Among other things, our results demonstrate that some of the protocols that were efficient in yesterday's hardware are not so today because they cannot take advantage of the abundant parallelism and fast networking present in modern hardware. Conversely, some protocols that were inefficient in yesterday's hardware are very attractive today. We distill our findings in a concise set of general guidelines and recommendations for protocol selection and design in the era of modern hardware.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {245–260},
numpages = {16},
keywords = {RDMA, availability, consistency, fault-tolerant, latency, linearizability, replication, throughput},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456241,
author = {Lei, Jiaxin and Munikar, Manish and Suo, Kun and Lu, Hui and Rao, Jia},
title = {Parallelizing packet processing in container overlay networks},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456241},
doi = {10.1145/3447786.3456241},
abstract = {Container networking, which provides connectivity among containers on multiple hosts, is crucial to building and scaling container-based microservices. While overlay networks are widely adopted in production systems, they cause significant performance degradation in both throughput and latency compared to physical networks. This paper seeks to understand the bottlenecks of in-kernel networking when running container overlay networks. Through profiling and code analysis, we find that a prolonged data path, due to packet transformation in overlay networks, is the culprit of performance loss. Furthermore, existing scaling techniques in the Linux network stack are ineffective for parallelizing the prolonged data path of a single network flow.We propose Falcon, a fast and balanced container networking approach to scale the packet processing pipeline in overlay networks. Falcon pipelines software interrupts associated with different network devices of a single flow on multiple cores, thereby preventing execution serialization of excessive software interrupts from overloading a single core. Falcon further supports multiple network flows by effectively multiplexing and balancing software interrupts of different flows among available cores. We have developed a prototype of Falcon in Linux. Our evaluation with both micro-benchmarks and real-world applications demonstrates the effectiveness of Falcon, with significantly improved performance (by 300\% for web serving) and reduced tail latency (by 53\% for data caching).},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {261–276},
numpages = {16},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456242,
author = {Papagiannis, Anastasios and Marazakis, Manolis and Bilas, Angelos},
title = {Memory-mapped I/O on steroids},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456242},
doi = {10.1145/3447786.3456242},
abstract = {With current technology trends for fast storage devices, the host-level I/O path is emerging as a main bottleneck for modern, data-intensive servers and applications. The need to improve I/O performance requires customizing various aspects of the I/O path, including the page cache and the method to access the storage devices.In this paper, we present Aquila, a library OS that allows applications to reduce I/O overhead by customizing the memory-mapped I/O (mmio) path for files or storage devices. Compared to Linux mmap, Aquila (a) offers full mmio compatibility and protection to minimize application modifications, (b) allows applications to customize the DRAM I/O cache, its policies, and access to storage devices, and (c) significantly reduces I/O overhead. Aquila achieves its mmio compatibility, flexibility, and performance by placing the application in a privileged domain, non-root ring 0.We show the benefits of Aquila in two cases: (a) Using mmio in key-value stores to reduce I/O overhead and (b) utilizing mmio in graph processing applications to extend the memory heap over fast storage devices. Aquila requires 2.58\texttimes{} fewer CPU cycles for cache management in RocksDB, compared to user-space caching and read/write system calls and results in 40\% improvement in request throughput. Finally, we use Ligra, a graph processing framework, to show the efficiency of Aquila in extending the memory heap over fast storage devices. In this case, Aquila results in up to 4.14\texttimes{} lower execution time compared to Linux mmap.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {277–293},
numpages = {17},
keywords = {I/O caching, Linux mmap, fast storage devices, key-value stores, memory-mapped I/O},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456243,
author = {Hunt, Guerney D. H. and Pai, Ramachandra and Le, Michael V. and Jamjoom, Hani and Bhattiprolu, Sukadev and Boivie, Rick and Dufour, Laurent and Frey, Brad and Kapur, Mohit and Goldman, Kenneth A. and Grimm, Ryan and Janakirman, Janani and Ludden, John M. and Mackerras, Paul and May, Cathy and Palmer, Elaine R. and Rao, Bharata Bhasker and Roy, Lawrence and Starke, William A. and Stuecheli, Jeff and Valdez, Enriquillo and Voigt, Wendel},
title = {Confidential computing for OpenPOWER},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456243},
doi = {10.1145/3447786.3456243},
abstract = {This paper presents Protected Execution Facility (PEF), a virtual machine-based Trusted Execution Environment (TEE) for confidential computing on Power ISA. PEF enables protected secure virtual machines (SVMs). Like other TEEs, PEF verifies the SVM prior to execution. PEF utilizes a Trusted Platform Module (TPM), secure boot, and trusted boot as well as newly introduced architectural changes for Power ISA systems. Exploiting these architectural changes requires new firmware, the Protected Execution Ultravisor. PEF is supported in the latest version of the POWER9 chip. PEF demonstrates that access control for isolation and cryptography for confidentiality is an effective approach to confidential computing. We particularly focus on how our design (i) balances between access control and cryptography, (ii) maximizes the use of existing security components, and (iii) simplifies the management of the SVM life cycle. Finally, we evaluate the performance of SVMs in comparison to normal virtual machines on OpenPOWER systems.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {294–310},
numpages = {17},
keywords = {KVM, Linux, POWER9, TEE, confidential computing, enclave, firmware, secure computing, trusted execution environment, ultravisor},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456244,
author = {Jangda, Abhinav and Polisetty, Sandeep and Guha, Arjun and Serafini, Marco},
title = {Accelerating graph sampling for graph machine learning using GPUs},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456244},
doi = {10.1145/3447786.3456244},
abstract = {Representation learning algorithms automatically learn the features of data. Several representation learning algorithms for graph data, such as DeepWalk, node2vec, and Graph-SAGE, sample the graph to produce mini-batches that are suitable for training a DNN. However, sampling time can be a significant fraction of training time, and existing systems do not efficiently parallelize sampling.Sampling is an "embarrassingly parallel" problem and may appear to lend itself to GPU acceleration, but the irregularity of graphs makes it hard to use GPU resources effectively. This paper presents NextDoor, a system designed to effectively perform graph sampling on GPUs. NextDoor employs a new approach to graph sampling that we call transit-parallelism, which allows load balancing and caching of edges. NextDoor provides end-users with a high-level abstraction for writing a variety of graph sampling algorithms. We implement several graph sampling applications, and show that NextDoor runs them orders of magnitude faster than existing systems.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {311–326},
numpages = {16},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456245,
author = {Misra, Ujval and Liaw, Richard and Dunlap, Lisa and Bhardwaj, Romil and Kandasamy, Kirthevasan and Gonzalez, Joseph E. and Stoica, Ion and Tumanov, Alexey},
title = {RubberBand: cloud-based hyperparameter tuning},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456245},
doi = {10.1145/3447786.3456245},
abstract = {Hyperparameter tuning is essential to achieving state-of-the-art accuracy in machine learning (ML), but requires substantial compute resources to perform. Existing systems primarily focus on effectively allocating resources for a hyperparameter tuning job under fixed resource constraints. We show that the available parallelism in such jobs changes dynamically over the course of execution and, therefore, presents an opportunity to leverage the elasticity of the cloud.In particular, we address the problem of minimizing the financial cost of executing a hyperparameter tuning job, subject to a time constraint. We present RubberBand---the first framework for cost-efficient, elastic execution of hyperparameter tuning jobs in the cloud. RubberBand utilizes performance instrumentation and cloud pricing to model job completion time and cost prior to runtime, and generate a cost-efficient, elastic resource allocation plan. RubberBand is able to efficiently execute this plan and realize a cost reduction of up to 2x in comparison to static allocation baselines.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {327–342},
numpages = {16},
keywords = {distributed machine learning, hyperparameter optimization},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456246,
author = {Yang, Yanfei and Wu, Mingyu and Chen, Haibo and Zang, Binyu},
title = {Bridging the performance gap for copy-based garbage collectors atop non-volatile memory},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456246},
doi = {10.1145/3447786.3456246},
abstract = {Non-volatile memory (NVM) is expected to revolutionize the memory hierarchy with not only non-volatility but also large capacity and power efficiency. Memory-intensive applications, which are often written in managed languages like Java, would run atop NVM for better cost-efficiency. Unfortunately, such applications may suffer from performance slowdown due to the unmanaged performance gap between DRAM and NVM. This paper studies the performance of a series of Java applications atop NVM and uncovers that the copy-based garbage collection (GC), the mainstream GC algorithm, is an NVM-unfriendly component in JVM. GC becomes a severe performance bottleneck especially when memory resource is scarce. To this end, this paper analyzes the memory behavior of copy-based GC and uncovers that its inappropriate usage on NVM bandwidth is the main reason for its performance slowdown. This paper thus proposes two NVM-aware optimizations: write cache and header map, to effectively manage the limited NVM bandwidth. It further improves the GC performance with hardware instructions like non-temporal memory accesses and prefetching. We have implemented the optimizations on two mainstream copy-based garbage collectors in OpenJDK. Evaluation with various memory-intensive applications shows that our optimizations can improve the GC time, application execution time, application tail latency by up to 2.69\texttimes{}, 11.0\%, and 5.09\texttimes{}, respectively.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {343–358},
numpages = {16},
keywords = {garbage collection, java virtual machine, non-volatile memory},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456247,
author = {Wu, Yidi and Ma, Kaihao and Cai, Zhenkun and Jin, Tatiana and Li, Boyang and Zheng, Chenguang and Cheng, James and Yu, Fan},
title = {Seastar: vertex-centric programming for graph neural networks},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456247},
doi = {10.1145/3447786.3456247},
abstract = {Graph neural networks (GNNs) have achieved breakthrough performance in graph analytics such as node classification, link prediction and graph clustering. Many GNN training frameworks have been developed, but they are usually designed as a set of manually written, GNN-specific operators plugged into existing deep learning systems, which incurs high memory consumption, poor data locality, and large semantic gap between algorithm design and implementation. This paper proposes the Seastar system, which presents a vertex-centric programming model for GNN training on GPU and provides idiomatic python constructs to enable easy development of novel homogeneous and heterogeneous GNN models. We also propose novel optimizations to produce highly efficient fused GPU kernels for forward and backward passes in GNN training. Compared with the state-of-the art GNN systems, DGL and PyG, Seastar achieves better usability, up to 2 and 8 times less memory consumption, and 14 and 3 times faster execution, respectively.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {359–375},
numpages = {17},
keywords = {deep learning systems, graph neural networks},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456248,
author = {Kuenzer, Simon and B\u{a}doiu, Vlad-Andrei and Lefeuvre, Hugo and Santhanam, Sharan and Jung, Alexander and Gain, Gaulthier and Soldani, Cyril and Lupu, Costin and Teodorescu, \c{S}tefan and R\u{a}ducanu, Costi and Banu, Cristian and Mathy, Laurent and Deaconescu, R\u{a}zvan and Raiciu, Costin and Huici, Felipe},
title = {Unikraft: fast, specialized unikernels the easy way},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456248},
doi = {10.1145/3447786.3456248},
abstract = {Unikernels are famous for providing excellent performance in terms of boot times, throughput and memory consumption, to name a few metrics. However, they are infamous for making it hard and extremely time consuming to extract such performance, and for needing significant engineering effort in order to port applications to them. We introduce Unikraft, a novel micro-library OS that (1) fully modularizes OS primitives so that it is easy to customize the unikernel and include only relevant components and (2) exposes a set of composable, performance-oriented APIs in order to make it easy for developers to obtain high performance.Our evaluation using off-the-shelf applications such as nginx, SQLite, and Redis shows that running them on Unikraft results in a 1.7x-2.7x performance improvement compared to Linux guests. In addition, Unikraft images for these apps are around 1MB, require less than 10MB of RAM to run, and boot in around 1ms on top of the VMM time (total boot time 3ms-40ms). Unikraft is a Linux Foundation open source project and can be found at www.unikraft.org.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {376–394},
numpages = {19},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456249,
author = {Alex, Markuze and Vargaftik, Shay and Kupfer, Gil and Pismeny, Boris and Amit, Nadav and Morrison, Adam and Tsafrir, Dan},
title = {Characterizing, exploiting, and detecting DMA code injection vulnerabilities in the presence of an IOMMU},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456249},
doi = {10.1145/3447786.3456249},
abstract = {Direct memory access (DMA) renders a system vulnerable to DMA attacks, in which I/O devices access memory regions not intended for their use. Hardware input-output memory management units (IOMMU) can be used to provide protection. However, an IOMMU cannot prevent all DMA attacks because it only restricts DMA at page-level granularity, leading to sub-page vulnerabilities.Current DMA attacks rely on simple situations in which write access to a kernel pointer is obtained due to sub-page vulnerabilities and all other attack ingredients are available and reside on the same page. We show that DMA vulnerabilities are a deep-rooted issue and it is often the kernel design that enables complex and multistage DMA attacks. This work presents a structured top-down approach to characterize, exploit, and detect them.To this end, we first categorize sub-page vulnerabilities into four types, providing insight into the structure of DMA vulnerabilities. We then identify a set of three vulnerability attributes that are sufficient to execute code injection attacks.We built analysis tools that detect these sub-page vulnerabilities and analyze the Linux kernel. We found that 72\% of the device drivers expose callback pointers, which may be overwritten by a device to hijack the kernel control flow.Aided by our tools' output, we demonstrate novel code injection attacks on the Linux kernel; we refer to these as compound attacks. All previously reported attacks are single-step, with the vulnerability attributes present in a single page. In compound attacks, the vulnerability attributes are initially incomplete. However, we demonstrate that they can be obtained by carefully exploiting standard OS behavior.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {395–409},
numpages = {15},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456250,
author = {Ma, Sixiang and Zhou, Fang and Bond, Michael D. and Wang, Yang},
title = {Finding heterogeneous-unsafe configuration parameters in cloud systems},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456250},
doi = {10.1145/3447786.3456250},
abstract = {With the increasing prevalence of heterogeneous hardware and the increasing need for online reconfiguration, there is increasing demand for heterogeneous configurations. However, allowing different nodes to have different configurations may cause errors when these nodes communicate, even if the configuration of each node uses valid values.To test which configuration parameters are unsafe when configured in a heterogeneous manner, this work reuses existing unit tests but runs them with heterogeneous configurations. To address the challenge that unit tests often share the configuration across different nodes, we incorporate several heuristics to accurately map configuration objects to nodes. To address the challenge that there are too many tests to run, we (1) "pre-run" unit tests to determine effective unit tests for each configuration parameter and (2) introduce pooled testing to test several parameters together. Our evaluation finds 41 heterogeneous-unsafe configuration parameters in Flink, HBase, HDFS, MapReduce, and YARN. We further propose suggestions and workarounds to make a subset of these parameters heterogeneous safe.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {410–425},
numpages = {16},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456251,
author = {Xie, Zhen and Dong, Wenqian and Liu, Jiawen and Liu, Hang and Li, Dong},
title = {Tahoe: tree structure-aware high performance inference engine for decision tree ensemble on GPU},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456251},
doi = {10.1145/3447786.3456251},
abstract = {Decision trees are widely used and often assembled as a forest to boost prediction accuracy. However, using decision trees for inference on GPU is challenging, because of irregular memory access patterns and imbalance workloads across threads. This paper proposes Tahoe, a tree structure-aware high performance inference engine for decision tree ensemble. Tahoe rearranges tree nodes to enable efficient and coalesced memory accesses; Tahoe also rearranges trees, such that trees with similar structures are grouped together in memory and assigned to threads in a balanced way. Besides memory access efficiency, we introduce a set of inference strategies, each of which uses shared memory differently and has different implications on reduction overhead. We introduce performance models to guide the selection of the inference strategies for arbitrary forests and data set. Tahoe consistently outperforms the state-of-the-art industry-quality library FIL by 3.82x, 2.59x, and 2.75x on three generations of NVIDIA GPUs (Kepler, Pascal, and Volta), respectively.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {426–440},
numpages = {15},
keywords = {decision tree ensemble, decision tree inference, performance model, tree structure},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456252,
author = {Choi, Brian and Burns, Randal and Huang, Peng},
title = {Understanding and dealing with hard faults in persistent memory systems},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456252},
doi = {10.1145/3447786.3456252},
abstract = {The advent of Persistent Memory (PM) devices enables systems to actively persist information at low costs, including program state traditionally in volatile memory. However, this trend poses a reliability challenge in which multiple classes of soft faults that go away after restart in traditional systems turn into hard (recurring) faults in PM systems. In this paper, we first characterize this rising problem with an empirical study of 28 real-world bugs. We analyze how they cause hard faults in PM systems. We then propose Arthas, a tool to effectively recover PM systems from hard faults. Arthas checkpoints PM states via fine-grained versioning and uses program slicing of fault instructions to revert problematic PM states to good versions. We evaluate Arthas on 12 real-world hard faults from five large PM systems. Arthas successfully recovers the systems for all cases while discarding 10\texttimes{} less data on average compared to state-of-the-art checkpoint-rollback solutions.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {441–457},
numpages = {17},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456253,
author = {Bindschaedler, Laurent and Malicevic, Jasmina and Lepers, Baptiste and Goel, Ashvin and Zwaenepoel, Willy},
title = {Tesseract: distributed, general graph pattern mining on evolving graphs},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456253},
doi = {10.1145/3447786.3456253},
abstract = {Tesseract is the first distributed system for executing general graph mining algorithms on evolving graphs. Tesseract scales out by decomposing a stream of graph updates into per-update mining tasks and dynamically assigning these tasks to a set of distributed workers. We present a novel approach to change detection that efficiently determines the exact modifications to the algorithm's output for each update to the input graph. We use a disaggregated, multiversioned graph store to allow workers to process updates independently, without producing duplicates. Moreover, Tesseract provides interactive mining insights for complex applications using an incremental aggregation API. Finally, we implement and evaluate Tesseract and demonstrate that it achieves orders-of-magnitude improvements over state-of-the-art systems.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {458–473},
numpages = {16},
keywords = {differential, distributed, dynamic, evolving, graph, graph store, incremental, mining, pattern, processing, streaming, subgraph matching, temporal, tesseract},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456254,
author = {Beischl, Alexander and Kersten, Timo and Bandle, Maximilian and Giceva, Jana and Neumann, Thomas},
title = {Profiling dataflow systems on multiple abstraction levels},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456254},
doi = {10.1145/3447786.3456254},
abstract = {Dataflow graphs are a popular abstraction for describing computation, used in many systems for high-level optimization. For execution, dataflow graphs are lowered and optimized through layers of program representations down to machine instructions. Unfortunately, performance profiling such systems is cumbersome, as today's profilers present results merely at instruction and function granularity. This obfuscates the connection between profiles and high-level constructs, such as operators and pipelines, making interpretation of profiles an exercise in puzzling and deduction.In this paper, we show how to profile compiling dataflow systems at higher abstraction levels. Our approach tracks the code generation process and aggregates profiling data to any abstraction level. This bridges the semantic gap to match the engineer's current information need and even creates a comprehensible way to report timing information within profiling data. We have evaluated this approach within our compiling DBMS Umbra, showing that the approach is generally applicable for compiling dataflow systems and can be implemented with high accuracy and reasonable overhead.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {474–489},
numpages = {16},
keywords = {dataflow systems, profiling, query compilation},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456255,
author = {Thalheim, J\"{o}rg and Unnibhavi, Harshavardhan and Priebe, Christian and Bhatotia, Pramod and Pietzuch, Peter},
title = {rkt-io: a direct I/O stack for shielded execution},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456255},
doi = {10.1145/3447786.3456255},
abstract = {The shielding of applications using trusted execution environments (TEEs) can provide strong security guarantees in untrusted cloud environments. When executing I/O operations, today's shielded execution frameworks, however, exhibit performance and security limitations: they assign resources to the I/O path inefficiently, perform redundant data copies, use untrusted host I/O stacks with security risks and performance overheads. This prevents TEEs from running modern I/O-intensive applications that require high-performance networking and storage.We describe rkt-io (pronounced "rocket I/O"), a direct user-space network and storage I/O stack specifically designed for TEEs that combines high-performance, POSIX compatibility and security. rkt-io achieves high I/O performance by employing direct userspace I/O libraries (DPDK and SPDK) inside the TEE for kernel-bypass I/O. For efficiency, rkt-io polls for I/O events directly, by interacting with the hardware instead of relying on interrupts, and it avoids data copies by mapping DMA regions in the untrusted host memory. To maintain full Linux ABI compatibility, the userspace I/O libraries are integrated with userspace versions of the Linux VFS and network stacks inside the TEE. Since it omits the host OS from the I/O path, does not suffer from host interface/Iago attacks. Our evaluation with Intel SGX TEEs shows that rkt-io is 9\texttimes{}faster for networking and 7\texttimes{} faster for storage compared to host- (Scone) and LibOS-based (SGX-LKL) I/O approaches.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {490–506},
numpages = {17},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456256,
author = {Lion, David and Chiu, Adrian and Yuan, Ding},
title = {M3: end-to-end memory management in elastic system software stacks},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456256},
doi = {10.1145/3447786.3456256},
abstract = {This paper proposes M3, an end-to-end system that dynamically distributes memory resources among competing applications to maximize their overall performance. Today's data center workloads, can adapt to a wide range of memory sizes, and they are built on complex software stacks.M3 consists of a set of mechanisms and policies allowing the layers of the system stack to make coordinated decisions. Applications continuously adapt to current resource availability, and resources are distributed to competing applications according to their needs. Experiments show that compared to the best possible static configurations, M3 achieves up to 3.05x speed-up.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {507–522},
numpages = {16},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456257,
author = {Gandhi, Neeraj and Roth, Edo and Sandler, Brian and Haeberlen, Andreas and Phan, Linh Thi Xuan},
title = {REBOUND: defending distributed systems against attacks with bounded-time recovery},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456257},
doi = {10.1145/3447786.3456257},
abstract = {This paper shows how to use bounded-time recovery (BTR) to defend distributed systems against non-crash faults and attacks. Unlike many existing fault-tolerance techniques, BTR does not attempt to completely mask all symptoms of a fault; instead, it ensures that the system returns to the correct behavior within a bounded amount of time. This weaker guarantee is sufficient, e.g., for many cyber-physical systems, where physical properties - such as inertia and thermal capacity - prevent quick state changes and thus limit the damage that can result from a brief period of undefined behavior.We present an algorithm called REBOUND that can provide BTR for the Byzantine fault model. REBOUND works by detecting faults and then reconfiguring the system to exclude the faulty nodes. This supports very fine-grained responses to faults: for instance, the system can move or replace existing tasks, or drop less critical tasks entirely to conserve resources. REBOUND can take useful actions even when a majority of the nodes is compromised, and it requires less redundancy than full fault-tolerance.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {523–539},
numpages = {17},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456258,
author = {Zhao, Kaiyang and Gong, Sishuai and Fonseca, Pedro},
title = {On-demand-fork: a microsecond fork for memory-intensive and latency-sensitive applications},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456258},
doi = {10.1145/3447786.3456258},
abstract = {Fork has long been the process creation system call for Unix. At its inception, fork was hailed as an efficient system call due to its use of copy-on-write on memory shared between parent and child processes. However, application memory demand has increased drastically since the early days and the cost incurred by fork to simply set up virtual memory (e.g., copy page tables) is now a concern, even for applications that only require hundreds of MBs of memory. In practice, fork performance already holds back system efficiency and latency across a range of uses cases that fork large processes, such as fault-tolerant systems, serverless frameworks, and testing frameworks.This paper proposes On-demand-fork, a fast implementation of the fork system call specifically designed for applications with large memory footprints. On-demand-fork relies on the observation that copy-on-write can be generalized to page tables, even on commodity hardware. On-demand-fork executes faster than the traditional fork implementation by additionally sharing page tables between parent and child at fork time and selectively copying page tables in small chunks, on-demand, when handling page faults. On-demand-fork is a drop-in replacement for fork that requires no changes to applications or hardware.We evaluated On-demand-fork on a range of micro-benchmarks and real-world workloads. On-demand-fork significantly reduces the fork invocation time and has improved scalability. For processes with 1 GB of allocated memory, On-demand-fork has a 65\texttimes{} performance advantage over Fork. We also evaluated On-demand-fork on testing, fuzzing, and snapshotting workloads of well-known applications, obtaining execution throughput improvements between 59\% and 226\% and up to 99\% invocation latency reduction.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {540–555},
numpages = {16},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456259,
author = {Bashir, Noman and Deng, Nan and Rzadca, Krzysztof and Irwin, David and Kodak, Sree and Jnagal, Rohit},
title = {Take it to the limit: peak prediction-driven resource overcommitment in datacenters},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456259},
doi = {10.1145/3447786.3456259},
abstract = {To increase utilization, datacenter schedulers often overcommit resources where the sum of resources allocated to the tasks on a machine exceeds its physical capacity. Setting the right level of overcommitment is a challenging problem: low overcommitment leads to wasted resources, while high overcommitment leads to task performance degradation. In this paper, we take a first principles approach to designing and evaluating overcommit policies by asking a basic question: assuming complete knowledge of each task's future resource usage, what is the safest overcommit policy that yields the highest utilization? We call this policy the peak oracle. We then devise practical overcommit policies that mimic this peak oracle by predicting future machine resource usage. We simulate our overcommit policies using the recently-released Google cluster trace, and show that they result in higher utilization and less overcommit errors than policies based on per-task allocations. We also deploy these policies to machines inside Google's datacenters serving its internal production workload. We show that our overcommit policies increase these machines' usable CPU capacity by 10-16\% compared to no overcommitment.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {556–573},
numpages = {18},
keywords = {datacenters, overcommit, resource management},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456260,
author = {Cangialosi, Frank and Narayan, Akshay and Goyal, Prateesh and Mittal, Radhika and Alizadeh, Mohammad and Balakrishnan, Hari},
title = {Site-to-site internet traffic control},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456260},
doi = {10.1145/3447786.3456260},
abstract = {Queues allow network operators to control traffic: where queues build, they can enforce scheduling and shaping policies. In the Internet today, however, there is a mismatch between where queues build and where control is most effectively enforced; queues build at bottleneck links that are often not under the control of the data sender. To resolve this mismatch, we propose a new kind of middlebox, called Bundler. Bundler uses a novel inner control loop between a sendbox (in the sender's site) and a receivebox (in the receiver's site) to determine the aggregate rate for the bundle, leaving the end-to-end connections and their control loops intact. Enforcing this sending rate ensures that bottleneck queues that would have built up from the bundle's packets now shift from the bottleneck to the sendbox. This enables the sendbox to exercise control over its traffic by scheduling packets according to any policy necessary to achieve the network operator's higher-level objectives. We have implemented Bundler in Linux and evaluated it with real-world and emulation experiments. We find that Bundler allows the sender-chosen policy to be effective: when configured to implement Stochastic Fairness Queueing (SFQ), it improves median flow completion time (FCT) by between 28\% and 97\% across various scenarios.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {574–589},
numpages = {16},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456261,
author = {Ahsan, Shegufta B. and Yang, Rui and Noghabi, Shadi A. and Gupta, Indranil},
title = {Home, safehome: smart home reliability with visibility and atomicity},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456261},
doi = {10.1145/3447786.3456261},
abstract = {Smart environments (homes, factories, hospitals, buildings) contain an increasing number of IoT devices, making them complex to manage. Today, in smart homes when users or triggers initiate routines (i.e., a sequence of commands), concurrent routines and device failures can cause incongruent outcomes. We describe SafeHome, a system that provides notions of atomicity and serial equivalence for smart homes. Due to the human-facing nature of smart homes, SafeHome offers a spectrum of visibility models which trade off between responsiveness vs. isolation of the smart home. We implemented SafeHome and performed workload-driven experiments. We find that a weak visibility model, called eventual visibility, is almost as fast as today's status quo (up to 23\% slower) and yet guarantees serially-equivalent end states.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {590–605},
numpages = {16},
keywords = {fault-tolerance, reliability, routines, smart home},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}

@inproceedings{10.1145/3447786.3456262,
author = {Sajal, Sultan Mahmud and Hasan, Rubaba and Zhu, Timothy and Urgaonkar, Bhuvan and Sen, Siddhartha},
title = {TraceSplitter: a new paradigm for downscaling traces},
year = {2021},
isbn = {9781450383349},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3447786.3456262},
doi = {10.1145/3447786.3456262},
abstract = {Realistic experimentation is a key component of systems research and industry prototyping, but experimental clusters are often too small to replay the high traffic rates found in production traces. Thus, it is often necessary to downscale traces to lower their arrival rate, and researchers/practitioners generally do this in an ad-hoc manner. For example, one practice is to multiply all arrival timestamps in a trace by a scaling factor to spread the load across a longer timespan. However, temporal patterns are skewed by this approach, which may lead to inappropriate conclusions about some system properties (e.g., the agility of auto-scaling). Another popular approach is to count the number of arrivals in fixed-sized time intervals and scale it according to some modeling assumptions. However, such approaches can eliminate or exaggerate the fine-grained burstiness in the trace depending on the time interval length.The goal of this paper is to demonstrate the drawbacks of common downscaling techniques and propose new methods for realistically downscaling traces. We introduce a new paradigm for scaling traces that splits an original trace into multiple downscaled traces to accurately capture the characteristics of the original trace. Our key insight is that production traces are often generated by a cluster of service instances sitting behind a load balancer; by mimicking the load balancing used to split load across these instances, we can similarly split the production trace in a manner that captures the workload experienced by each service instance. Using production traces, synthetic traces, and a case study of an auto-scaling system, we identify and evaluate a variety of scenarios that show how our approach is superior to current approaches.},
booktitle = {Proceedings of the Sixteenth European Conference on Computer Systems},
pages = {606–619},
numpages = {14},
keywords = {cloud computing, performance evaluation, workload analysis},
location = {Online Event, United Kingdom},
series = {EuroSys '21}
}