This paper presents zBuffer, a zero-copy and metadata-free serialization library for high-performance and low-cost RPCs. At the core of zBuffer is scatter-gather reflection, a novel technique that collaboratively (i) leverages the NIC scatter-gather hardware feature to offload the costly data coalescing, and (ii) utilizes the static reflection mechanism of modern programming languages to enable type queries on complex data objects without requiring explicit metadata construction. We leverage C++ language features, mainly including template meta-programming and macros, to realize static reflection at compile time. Based on zBuffer, we design a fast RPC system (called zRPC) which eliminates all RPC memory copy overheads not only in (de)serialization but also in network transmission. Extensive evaluation shows that zBuffer/zRPC significantly outperforms state-of-the-art serialization/RPC mechanisms: zBuffer is approximately 7× faster than Cornflakes in serialization for complex data objects; and zRPC reduces 99th percentile latency by 21% and achieves 62% higher throughput than eRPC on the Masstree key-value (KV) store with the YCSB benchmark.

Fast consensus protocols, such as CURP-Q and NOPaxos, have coupled objectives of reducing latency and tolerating faults, but doing so incurs considerable processing overhead and/or necessitates complex changes to existing architectures. Our insight is that when no adverse execution conditions (including operation conflicts, node failures, and network failures) occur, replication can be done safely without consensus at all. Rather than pursuing one single consensus protocol for fast and fault-tolerant replication, we propose to decouple low latency from fault tolerance, and design a hybrid solution that seamlessly integrates client-coordinated two-phase commit (2PC) with consensus, respectively to reduce latency in normal situations and tolerate faults in faulty situations. In the absence of faults, the system enters the Fast mode, where the client directly broadcasts its requests to all replicas with 2PC completing all updates in the first phase, i.e., in one RTT. Otherwise, the system enters the Consensus mode, which resorts to a consensus protocol to tolerate faults. We have applied the hybrid solution to the widely-used Raft consensus protocol to design xRaft, which can adaptively switch between the Fast and Consensus modes, ensuring correctness with minimal switching overhead. Evaluation shows that xRaft significantly outperforms state-of-the-art consensus protocols.

Connected Components (CC) computation is a fundamental graph analytics kernel. While BFS-sampling has emerged as the state-of-the-art approach for power-law graphs, its performance in existing implementations is severely limited by inheriting unnecessary BFS semantics. The core issue is a fundamental mismatch: BFS requires strict level-synchronization to compute shortest paths, while CC only needs eventual label consistency without ordering constraints. This semantic mismatch manifests as three critical bottlenecks: (i) severe load imbalance from vertex-centric task allocation, which fails to distribute the massive workload of high-degree hub vertices; (ii) redundant writes from dynamic push/pull mode switching, which necessitates costly frontier reconstruction; and (iii) redundant synchronization and computation from enforcing BFS’s strict ordering guarantees, which are superfluous for CC computation. We introduce FastCC , a lightweight multiprocess system-algorithm co-designed solution that breaks this semantic mismatch. The cornerstone of our approach is the strategic decision to fix the highest-degree vertex as the BFS root, creating a predictable computation topology. This enables three synergistic innovations: (1) hybrid task partitioning that employs edge-centric allocation in the critical first iteration to eliminate load imbalance at its source; (2) predictable mode switching that leverages the deterministic computation graph to bypass expensive frontier reconstruction; and (3) lightweight, custom synchronization primitives that relax BFS’s strict ordering to match CC’s eventual consistency requirements, while allowing earlier label propagation within the same iteration to reduce the overall computational workload. Extensive evaluation on large-scale real-world and synthetic power-law graphs demonstrates that FastCC achieves significant performance improvements, with speedups of 10.6-55.5× faster (average: 37.8×) over state-of-the-art CC implementations including ConnectIt and vGraph. FastCC also reduces peak memory footprint by up to 2.87× and exhibits superior, more predictable scalability. The practical efficacy of our approach is validated by its deployment as the core engine in a top-ranked GreenGraph500 solution.

ByteScheduler partitions and rearranges tensor transmissions to improve the communication efficiency of distributed Deep Neural Network (DNN) training. The configuration of hyper-parameters (i.e., the partition size and the credit size) is critical to the effectiveness of partitioning and rearrangement. Currently ByteScheduler adopts Bayesian Optimization (BO) to find the optimal configuration for the hyper-parameters beforehand. In practice, however, various runtime factors (such as worker node status and network conditions) change over time, making the statically-determined one-shot configuration result suboptimal for real-world DNN training. To address this problem, in this paper we present a realtime configuration method (called AutoByte) that automatically and timely searches the optimal hyper-parameters as the training systems dynamically change. AutoByte extends the ByteScheduler framework with a meta network, which takes the systems’ runtime statistics as its input, dynamically adjusts the triggering threshold based on system environment characteristics, and outputs predictions for speedups under specific configurations. Evaluation results on various DNN models show that AutoByte can dynamically tune the hyper-parameters with low resource usage, and deliver up to 33.2% higher performance than the best static configuration method on the ByteScheduler framework.

Modern data-intensive applications increasingly demand efficient and scalable file systems that can operate across distributed and cross-domain environments. However, existing file systems are inefficient in metadata management, synchronization efficiency, and system scalability under high-concurrency and metadata-intensive workloads in cross-domain environments. To address these challenges, this article introduces CrossFS (CFS), a cross-domain distributed file system that enhances consistency guarantees and metadata indexing. Specifically, CFS leverages conflict-free replicated data types (CRDTs) to synchronize metadata, achieving strong eventual consistency with minimal synchronization overhead, even across network partitions. Furthermore, CFS employs a Hybrid Tree indexing structure, tailored for distributed environments, which optimizes metadata operations by reducing query latency by up to 33.4% and write amplification by 30.7%. Additionally, CFS achieves adaptive caching strategies and a hybrid synchronization model that effectively balances consistency latency with data availability. Extensive evaluations show that CFS outperforms CephFS and GlusterFS, achieving up to 33.9% higher metadata throughput, 36% lower latency, and 42% better data operation efficiency.

KVM is the dominant VM hypervisor on Linux, and relies on QEMU to realize the backends of the virtio family of devices such as virtio-blk. However, KVM/QEMU-based paravirtualization prolongs the guest I/O path with multiple context switches. As fast NVMe storage devices have been widely used, the software overhead becomes non-negligible. To shorten the I/O path, virtio-blk’s variations, vhost-kernel-blk and vhost-user-blk, respectively perform all guest I/O processing in kernel and user spaces. Unfortunately, they essentially forsake the collaboration between KVM and QEMU, sacrifice important QEMU features including live migration, snapshots, and flexible image format support. This article presents EXO, an extension of virtio-blk for efficient KVM/QEMU-based storage paravirtualization. The insight is that no matter how complex the QEMU backend’s processing is, to handle a guest I/O request, the host storage stack only needs to know the request’s guest-to-host address mapping. Therefore, we preserve the original slow I/O path of virtio-blk as a fallback, and leverage eBPF to introduce an in-kernel fast path that directly queries the address mapping without switching to the user-space backend processing. Extensive evaluation shows that EXO achieves similar or even higher performance compared to the variations (vhost-kernel-blk/vhost-user-blk) of virtio-blk, while preserving virtio-blk’s flexibility, safety, and compatibility.

High-bandwidth memory (HBM) is regarded as a promising technology for fundamentally overcoming the memory wall. It stacks up multiple DRAM dies vertically to dramatically improve the memory access bandwidth. However, this architecture also comes with more severe reliability issues, since HBM not only inherits error patterns of the conventional DRAM, but also introduces new error causes. In this article, we conduct the first systematical study on HBM errors, which cover over 460 million error events collected from 19 data centers and span over two years of deployment under a variety of services. Through error analyses and methodology validations, we confirm that the HBM exhibits different error patterns from conventional DRAM, in terms of spatial locality, temporal correlation, and sensor metrics which make empirical prediction models for DRAM error prediction ineffective for HBM. We design and implement Calchas , a hierarchical failure prediction framework for HBM based on our findings, which integrate spatial, temporal, and sensor information from various device levels to predict upcoming failures. The results demonstrate the feasibility of failure prediction across hierarchical levels.

Non-volatile memory (NVM) opens up new opportunities to resolve scaling restrictions of main memory, yet it is still hindered by the write disturbance (WD) problem. The WD problem mistakenly transforms the values of NVM cells, hence seriously deteriorating memory reliability and downgrading access performance. Existing studies mainly mitigate the WD problem via encoding WD-prone data patterns under in-place updates, yet we find that when turning to out-of-place updates, they can gain the potential to reduce more WD errors. We present LearnWD, an approach that mitigates the WD problem in NVM via coupling machine learning with out-of-place updates. LearnWD first employs clustering algorithms to classify the stale data based on the error proneness. To perform a write operation, LearnWD carefully examines the aggressivity of new data and the error proneness of stale data, so as to speculatively minimize the resulting WD errors. We conduct extensive experiments using 15 real-world datasets with different data types, showing that LearnWD can assist a variety of data encoding schemes to further reduce 19.5% of WD errors, shorten 10.1% of write latency, and extend 22.2% of write endurance.

Accurate workload prediction is essential to ensure application Quality of Service (QoS), cost efficiency, and compliance with Service Level Agreements (SLAs) during cloud-based deployment. However, existing methods struggle to achieve accurate forecasts across multiple temporal scales and often fail to generalize well with limited historical data. To tackle these problems, we propose LLM4Load-Turbo, a Prompt-Driven LLM Framework with Knowledge Distillation for Efficient Multi-Scale Workload Prediction. Firstly, we design a structured prompt with dataset introduction, task description, and workload features characterization to extract multi-scale features. Secondly, we introduce a cross-modality alignment mechanism combined with label embedding to further enhance predictive accuracy and generalization, effectively mitigating the container cold-start problem. Thirdly, we propose a two-level knowledge distillation strategy, enabling LLM4Load-Turbo to maintain high accuracy while substantially reducing inference latency, memory footprint, and computational cost. Specifically, our framework achieves up to an 89.27% improvement in inference speed and a 93.30% reduction in model parameter scale compared to state-of-the-art baselines. Extensive experiments on four real cloud workload datasets validate the effectiveness of our framework. For multi-scale workload prediction, LLM4Load-Turbo improves up to 50.44%. For container cold-start scenarios, LLM4Load-Turbo improves up to 93.54%. These results demonstrate the potential of LLM4Load-Turbo to enable dynamic and efficient resource management in modern cloud systems.

Fail-slow is a failure mode that exists in various components such as disks, SSDs, CPUs, memory, and networks, manifested as decreased performance but not causing crashes. We investigated the manifestation of fail-slow in HBM systems and proposed a fault detection framework based on a light regression model. It can detect potential fail-slow faults while HBM devices are undergoing factory testing. In our small-scale simulation tests, we found a fail-slow phenomenon in one single HBM device. In addition, We assemble a large-scale HBM log dataset from our production traces, based on which we provide root cause analysis on fail-slow HBM devices covering a variety of ill-implemented scheduling, hardware defects, and environmental factors. We have released the dataset to the public for further study.

Large Language Models (LLMs) with extended context lengths face significant computational challenges during the pre-filling phase, primarily due to the quadratic complexity of self-attention. Existing methods typically employ dynamic pattern matching and block-sparse low-level implementations. However, their reliance on local information for pattern identification fails to capture global contexts, and the coarse granularity of blocks leads to persistent internal sparsity, resulting in suboptimal accuracy and efficiency. To address these limitations, we propose AnchorAttention, a difference-aware, dynamic sparse attention mechanism that efficiently identifies critical attention regions at a finer stripe granularity while adapting to global contextual information, achieving superior speed and accuracy. AnchorAttention comprises three key components: (1) Pattern-based Anchor Computation, leveraging the commonalities present across all inputs to rapidly compute a set of near-maximum scores as anchor; (2) Difference-aware Stripe Sparsity Identification, performing difference-aware comparisons with anchor to quickly obtain discrete coordinates of significant regions in a stripe-like sparsity pattern; (3) Fine-grained Sparse Computation, replacing the traditional contiguous loading strategy with a discrete key-value loading approach to maximize sparsity rates while preserving hardware computational potential. Additionally, we integrate the identification strategy into a single operator to maximize parallelization potential. With its finer-grained sparsity strategy, AnchorAttention achieves higher sparsity rates at the same recall level, significantly reducing computation time. Compared to previous state-of-the-art methods, at a text length of 128k, it achieves a speedup of 1.44\times while maintaining higher recall rates.

Object stores usually maintain the mapping of objects to data servers' disk volumes (referred to as volume metadata) in a central directory, while storing the object data's in-volume offsets (referred to as offset metadata) together with the data on data servers. Unfortunately, the separation between volume/offset metadata complicates the processing of an object put: to ensure consistency, the multiple writes of the object's volume/offset metadata and object data have to be orchestrated in a particular order, which severely lowers object I/O performance. We propose a write-optimal structure called MetaX that aggregates all metadata of a put, including both volume and offset metadata as well as other meta information such as data checksum and temporary meta-log. Based on MetaX, we design the Cheetah object store, which organizes object storage into rich metadata storage (on meta servers) and raw data storage (on data servers). Cheetah removes the distributed ordering constraint on the multiple metadata/data writes by enforcing local atomicity of writing MetaX, while still ensuring consistency. Evaluation shows that Cheetah significantly outperforms existing object stores.

Emerging memory-semantic fabrics such as CXL and UB enable direct load/store access to remote memory at byte granularity, opening new opportunities for cluster-wide memory pooling and sharing. However, building a high-performance, fault-tolerant memory pool atop such fabrics remains challenging. Systems must coordinate application transparency with heterogeneous memory topologies, ensure safe memory reuse across machines, and handle instruction-level memory failures that manifest as hardware exceptions in user code. We present Oak, a resilient, high-performance memory pool service that enables transparent and efficient memory pooling and sharing across machines via memory-semantic interconnects. Oak decouples memory metadata from control logic via a stateless global memory manager, which is backed by a distributed KV store enabling scalable, fault-tolerant orchestration. To tolerate memory faults ranging from device loss to single-page uncorrectable errors, Oak provides a lightweight kernel-user cooperative recovery mechanism that intercepts memory failures in the kernel, performs microsecond-scale recovery, and defers metadata updates to user-space asynchronously. We demonstrate Oak's practicality by building Oak-KV, a fault-tolerant, zero-copy key-value store that runs entirely on Oak-managed shared memory. Evaluations show that Oak-KV delivers higher throughput than representative baselines under both normal and failure conditions.

The GPU-CPU-SSD hierarchical memory systems are commonly employed for large-scale GNN training. However, existing solutions inefficiently utilize high-bandwidth memory due to coarse-grained memory management and poor data placement that ignores graph access patterns. This paper presents HMGraph, a GNN training system unleashing the full potential of hierarchical memory architectures. The core design of HMGraph is Coordinated Cache, integrating GPU memory and CPU memory as a cache layer for the hierarchical memory system and improving GNN efficiency through fine-grained data and memory management. For this goal, three main designs are proposed. First, we design an automatic cache management mechanism that optimizes cache allocation based on the graph data access pattern to enhance the overall cache hit rate. Second, we propose a dynamic data space management strategy to improve the efficiency of dynamic cache. Third, we develop a hierarchical memory-aware data partitioning strategy that further improves the utilization of high-bandwidth memory. Our evaluation of various large-scale graphs reveals that HMGraph significantly outperforms other state-of-the-art systems by 1.4-36.7 ×.

BERT-like models have been widely adopted in text mining and web search due to their high accuracy. However, large BERT-like models suffer from inefficient online inference on GPUs for two main reasons. First, their high accuracy relies on large model depth, which linearly increases sequential computation on GPUs. Second, stochastic and dynamic online workloads lead to extra costs due to batching and padding. To address the problem, we present Student Parallelism for efficient GPU inference of BERT-like models under real-world online workloads. At its core, Student Parallelism adopts stacking distillation and boosting ensemble, distilling the original deep model into a group of shallow but virtually stacked student models running in parallel. This enables Student Parallelism to achieve a low model depth (e.g., two layers), and thus low inference latency while maintaining accuracy. In addition, we design adaptive student pruning to adjust the number of students according to the dynamic online workloads. For example, during workload bursts, it can temporarily decrease the number of students with minimal accuracy loss to improve system throughput. Extensive experiments on real-world datasets and workloads show that Student Parallelism achieves up to 4.1× lower latency while maintaining accuracy and up to 22.27× higher throughput during workload bursts.

Model fusion combines multiple Large Language Models (LLMs) with different strengths into a more powerful, integrated model through lightweight training methods. Existing works on model fusion focus primarily on supervised fine-tuning (SFT), leaving preference alignment (PA) —a critical phase for enhancing LLM performance—largely unexplored. The current few fusion methods on PA phase, like WRPO, simplify the process by utilizing only response outputs from source models while discarding their probability information. To address this limitation, we propose InfiFPO, a preference optimization method for implicit model fusion. InfiFPO replaces the reference model in Direct Preference Optimization (DPO) with a fused source model that synthesizes multi-source probabilities at the sequence level, circumventing complex vocabulary alignment challenges in previous works and meanwhile maintaining the probability information. By introducing probability clipping and max-margin fusion strategies, InfiFPO enables the pivot model to align with human preferences while effectively distilling knowledge from source models. Comprehensive experiments on 11 widely-used benchmarks demonstrate that InfiFPO consistently outperforms existing model fusion and preference optimization methods. When using Phi-4 as the pivot model, InfiFPO improves its average performance from 79.95 to 83.33 on 11 benchmarks, significantly improving its capabilities in mathematics, coding, and reasoning tasks.

Recent advances in large language models (LLMs) have intensified efforts to fuse heterogeneous open-source models into a unified system that inherits their complementary strengths. Existing logit-based fusion methods maintain inference efficiency but treat vocabulary dimensions independently, overlooking semantic dependencies encoded by cross-dimension interactions. These dependencies reflect how token types interact under a model's internal reasoning and are essential for aligning models with diverse generation behaviors. To explicitly model these dependencies, we propose \textbf{InfiGFusion}, the first structure-aware fusion framework with a novel \textit{Graph-on-Logits Distillation} (GLD) loss. Specifically, we retain the top-$k$ logits per output and aggregate their outer products across sequence positions to form a global co-activation graph, where nodes represent vocabulary channels and edges quantify their joint activations. To ensure scalability and efficiency, we design a sorting-based closed-form approximation that reduces the original $O(n^4)$ cost of Gromov-Wasserstein distance to $O(n \log n)$, with provable approximation guarantees. Experiments across multiple fusion settings show that GLD consistently improves fusion quality and stability. InfiGFusion outperforms SOTA models and fusion baselines across 11 benchmarks spanning reasoning, coding, and mathematics. It shows particular strength in complex reasoning tasks, with +35.6 improvement on Multistep Arithmetic and +37.06 on Causal Judgement over SFT, demonstrating superior multi-step and relational inference.

In-memory key-value (KV) caching bridges the performance gap between high-performance networks and disk devices. However, prior in-memory KV caching systems either consider large objects or introduce additional memory overhead. In this paper, we conduct a systematic analysis over 56 production traces, and make three observations: (i) small objects dominate the traces and data accesses are highly skewed; (ii) the hotness of objects keeps stable across days; and (iii) the multi-get operation that retrieves multiple objects from the same node incurs much shorter tail latency than purely using the single-get operation.

GPU Direct Storage (GDS) plays a vital role in GPU-based training and inference systems, leveraging Peer-to-Peer Direct Memory Access (P2P-DMA) to establish a direct data transfer path between the GPU and the storage device. The direct I/O path reduces GPU storage access latency and CPU overhead, thus improving the efficiency of data transfer. Currently, however, GDS employs a phony buffer in the host memory to interact with the Linux kernel, which results in suboptimal I/O performance, extra resource consumption, and high deployment complexity.

Mixture-of-Expert (MoE) models outperform conventional models by selectively activating different subnets, named experts, on a per-token basis. This gated computation generates dynamic communications that cannot be determined beforehand, challenging the existing GPU interconnects that remain static during distributed training. In this paper, we advocate for a first-of-its-kind system, called MixNet, that unlocks topology reconfiguration during distributed MoE training. Towards this vision, we first perform a production measurement study and show that the MoE dynamic communication pattern has strong locality, alleviating the need for global reconfiguration. Based on this, we design and implement a regionally reconfigurable high-bandwidth domain that augments existing electrical interconnects using optical circuit switching (OCS), achieving scalability while maintaining rapid adaptability. We build a fully functional MixNet prototype with commodity hardware and a customized collective communication runtime. Our prototype trains state-of-the-art MoE models with in-training topology reconfiguration across 32 A100 GPUs. Large-scale packet-level simulations show that MixNet achieves performance comparable to a non-blocking fat-tree fabric while boosting the networking cost efficiency (e.g., performance per dollar) of four representative MoE models by 1.2×–1.5× and 1.9×–2.3× at 100 Gbps and 400 Gbps link bandwidths, respectively.

Currently, ride-hailing service has tens of millions of registered drivers and hundreds of millions of registered passengers, serving tens of millions of rides per day. Different from social media applications like Facebook and LinkedIn, ride hailing needs to read/write/query a large number of small objects (like photos and audio/video pieces)always fast, so that it can support critical online computations such as face comparison and sentiment analysis on audio/video records. This is of particular importance for ride-hailing service to recognize and avoid potential dangers. Existing object stores (like Haystack and Tectonic) usually store object data in files and place object metadata in a separate key-value store (like RocksDB), which is unsuitable for ride-hailing service mainly because the objects' file-related information is placed together with the object data. This severely affects the I/O performance of object storage: first, for crash consistency, the writes of object data and object metadata must be conducted inseparatephases of one transaction, which significantly increases I/O latency; second, the space of deleted objects needs to be reclaimed viacompaction, which could sharply lower I/O performance when the system is busy in serving normal read/write requests. This paper describes FrigateBird, a continuously fast object store for ride-hailing service. FrigateBird differs from existing object stores in three aspects. First, we present a metadata/data decoupled service architecture for object storage, where therichmetadata service realizes efficient queries and updates of object metadata, and therawdata service purely performs disk I/O to read/write object data from/to raw disks. Second, we propose a rich metadata structure (calledRichmeta) taking the write operation logs as part of object metadata, which allows FrigateBird tosimultaneouslywrite the object data to raw disks (without filesystem overhead) and write the metadata to a key-value store, guaranteeing crash consistency by checking whether the transaction is completed and rolling back if not. Third, we design a compaction-free deletion mechanism which can efficiently delete an object by only updating the metadata without involving the data service, so that FrigateBird can efficiently support ride-hailing service's frequent delete operations while avoiding data-migration-caused performance hiccup. Evaluation shows that FrigateBird outperforms the state-of-the-art object stores by up to$3.36\times$and$27.9\times$in the mean I/O latency for normal and in-compaction scenarios, respectively.

Virtualization-based cloud computing has gained popularity owing to its system-isolation security and near-native performance. However, a critical challenge for cloud computing arises from the presence of numerous redundant memory pages across independent virtual machines (VMs), significantly reducing memory efficiency. For instance, each VM typically loads data from its virtual disk into its memory without considering the existing data in other VMs’ memory. The state-of-the-art solution for addressing memory efficiency is kernel same-page merging (KSM), which performs memory deduplication by merging pages with identical data from different processes on the host. However, KSM operates reactively after memory redundancy has occurred, adding computational overhead due to periodic scanning, rendering it inefficient for cloud computing environments with high-density VMs.

State machine replication (SMR) uses consensus as its core component for reaching agreement among a group of processes, in order to provide fault-tolerant services. Most SMR protocols, such as Paxos and Raft, are designed in the partial synchrony model. Partially synchronous protocols rely on timing assumptions to elect a special role (such as the leader), which may become the performance bottleneck under a heavy workload. From an engineering perspective, partially synchronous protocols have to wait for a pre-defined period of time and implement a (complicated) failover mechanism in order to replace the faulty leader. In contrast, asynchronous protocols are immune to such problems.

Graph pooling technique in GNNs for learning expressive graph-level representation is critical yet still chal-lenging. Existing pooling methods either struggle to capture local substructures or fail to utilize high-order dependency, thus diminishing the expression capability. To solve this problem, we propose HAP, a hierarchical graph-level representation learning framework adaptively sensitive to graph structures. Specifically, HAP utilizes a novel cross-level attention mechanism MOA to naturally focus more on the close neighborhood while effectively capturing higher-order dependency. It also learns a global graph content GCont that extracts the graph pattern properties to stabilize the pre- and post-coarsening graph content, thus providing global guidance in graph coarsening. Experiments show that HAP significantly outperforms the state-of-the-art graph pooling methods.

Traditional local disk file systems like Ext4, XFS, and Btrfs excel in managing file data but struggle with metadata-intensive workloads and small file accesses, especially across distributed and cross-domain environments.In this paper, we present CrossFS (CFS), a new cross-domain file system designed to overcome these challenges.CrossFS leverages Conflict-free Replicated Data Types (CRDTs) for efficient metadata synchronization and merging, enhancing both performance and consistency across systems.We organize metadata into a single sparse table using a Log-Structured Merge Tree (LSMT), minimizing metadata overhead and optimizing access efficiency.Additionally, by stacking another local file system as an object store, our system ensures efficient large file allocation and access, while preserving local performance through FUSE integration and rest rpc framework, for cross-regional capabilities.Experimental evaluations demonstrate significant performance enhancements over existing solutions, with our system achieving up to 2× the performance of traditional local file systems and a 40% improvement over distributed systems.

Object storage has been widely used in the cloud. Traditionally, the size of object metadata is much smaller than that of object data, and thus existing object storage systems (such as Ceph and Oasis) can place object data and metadata, respectively, on hard disk drives (HDDs) and solid-state drives (SSDs) to achieve high I/O performance at a low monetary cost. Currently, however, a wide range of cloud applications organize their data as large numbers of small objects of which the data size is close to (or even smaller than) the metadata size, thus greatly increasing the cost if placing all metadata on expensive SSDs. This article presents x Meta , an SSD-HDD-hybrid optimization for metadata maintenance of cloud-scale object storage. We observed that a substantial portion of the metadata of small objects is rarely accessed and thus can be stored on HDDs with little performance penalty. Therefore, x Meta first classifies the hot and cold metadata based on the frequency of metadata accesses of upper-layer applications and then adaptively stores the hot metadata on SSDs and the cold metadata on HDDs. We also propose a merging mechanism for hot metadata to further improve the efficiency of SSD storage and optimize range key query and insertion for hot metadata by designing composite keys. We have integrated the x Meta metadata service with Ceph to realize a high-performance, low-cost object store (called xCeph). The extensive evaluation shows that xCeph outperforms the original Ceph by an order of magnitude in the space requirement of SSD storage, while improving the throughput by up to 2.7×.

This article presents MST, a communication-efficient message library for fast graph traversal on exascale clusters. The key idea is to follow the multi-level network topology to perform topology-aware message aggregation, where small messages are gathered and scattered at each level of domain. To facilitate message aggregation, we equip MST with flexible buffer management including active buffer switching and dynamic buffer expansion. We implement MST on the newest-generation Tianhe supercomputer and evaluated its performance using various traversal-centric algorithms on both synthetic trillion-scale graphs and real-world big graphs. The results show that MST-based graph traversal is orders of magnitude faster than that based on Active Messages Library (AML). For the Graph500-BFS benchmark, MST-based Tianhe (with 77.2 K nodes) outperforms the Fugaku supercomputer (with 148.5 K nodes) by 18.53%, while Fugaku is ranked No. 1 in the latest Graph500-BFS ranking (June 2023). MST also greatly improves graph processing performance on other commercial large-scale computing systems at the National Supercomputing Center in Changsha (NSCC) and WuzhenLight.

To accommodate the increasingly large-scale models within limited-capacity GPU memory, various coarse-grained techniques, such as recomputation and swapping, have been proposed to optimize memory usage. However, these methods have encountered limitations, either in terms of inefficient memory reduction or diminished training performance. In response to this, our article introduces dynamic tensor offloading and recomputation (DELTA), an innovative approach for memory-efficient large-scale model training that combines fine-grained memory optimization and prefetching technology to reduce memory usage while maintaining high training throughput concurrently. Initially, we formulate the problem of memory-throughput joint optimization as an easy-solving 0/1 Knapsack problem. Leveraging this formalization, we use an improving polynomial complexity heuristic algorithm to address the problem effectively. Furthermore, we introduce, to the best of our knowledge, a novel bidirectional prefetching technology into dynamic memory management that significantly accelerates the model training when compared to relying solely on recomputation or swapping. Finally, DELTA offers users an automated training execution library, eliminating the need for manual configuration or specialized expertise. Experimental results demonstrate the effectiveness of DELTA in reducing GPU memory consumption. Compared to state-of-the-art methods, DELTA achieves substantial memory savings ranging from 40% to 72%, while maintaining comparable convergence performance for various models, including ResNet-50, ResNet-101, and BERT-Large. Notably, DELTA enables the training of GPT2-Large and GPT2-XL with batch sizes increased by 5.5× and 6×, respectively, showcasing its versatility and practicality in enabling large-scale model training on GPU hardware.

This paper presents URSAL, an HDD-only block storage system that achieves ultra-efficiency, reliability, scalability and availability at low cost. Compared to existing block stores such as URSA, Ceph, and Sheepdog, URSAL has the following distinctions. First, since parallelism is harmful to the random I/O performance on HDDs, we restrict URSAL storage servers to conservatively perform parallel I/O on HDDs for avoiding I/O contention and reducing tail latency. Second, URSAL designs a proxy-based storage architecture to separate the high-level and low-level I/O logic, where for each virtual machine (VM) there is one URSAL proxy process running at the client VM side to control (at a high level) the procedure of server-side low-level I/O. Third, to alleviate the problem of low random write performance of HDDs, URSAL selectively performs direct block writes on raw HDDs or indirect log appends to HDD journals (which are then asynchronously replayed to raw HDDs), depending on the characteristics of the workloads. Fourth, software failures are nontrivial in large-scale block storage systems of which the availability is vital to client VMs, and thus for high availability we design an efficient fault-tolerance mechanism by isolating the connection management module of URSAL proxy. We have implemented URSAL and deployed it at scale. Extensive evaluation results demonstrate that URSAL achieves much higher performance than the state-of-the-art solutions for underloaded scenarios.

Businesses increasingly need agile and elastic computing infrastructure to respond quickly to real-world situations. By offering efficient process-based virtualization and a layered image system, containers are designed to enable agile and elastic application deployment. However, creating or updating large container clusters is still slow due to the image downloading and unpacking process. In this article, we present DADI Image Service (DADI), a block-level image service for increased agility and elasticity in deploying applications. DADI replaces the waterfall model of starting containers (downloading image, unpacking image, starting container) with fine-grained on-demand transfer of remote images, realizing instant start of containers. To accelerate the cold start of containers, DADI designs a pull-based prefetching mechanism that allows a host to read necessary image data beforehand at the granularity of image layers. We design a peer-to-peer–based decentralized image sharing architecture to balance traffic among all the participating hosts and propose a pull-push collaborative prefetching mechanism to accelerate cold start. DADI efficiently supports various kinds of runtimes including cgroups, QEMU, and so on, further realizing “build once, run anywhere.” DADI has been deployed at scale in the production environment of Alibaba, serving one of the world’s largest ecommerce platforms. Performance results show that DADI can cold start 10,000 containers on 1,000 hosts within 4 s.

Distributed edge inference emerges to be a promising paradigm to speed up inference. Previous works make physical partitions on CNNs to realize it, but there are the following challenges for vision transformers: (1) high communication costs for the large model; (2) stragglers because of heterogeneous devices; (3) time-out exceptions due to unstable edge devices.Therefore, we propose a novel Model Decomposition and Parallelization(MDP) for large vision transformers. Inspired by the implicit boosting ensemble in the vision transformer, MDP decomposes it into an explicit boosting ensemble of different and parallel sub-models. It sequentially trains all sub-models to gradually reduce the residual errors. To minimize dependency and communication among sub-models, We adopt stacking distillation to bring every sub-model extra information about others for better error correction. Different sub-models can take both different image sizes and model sizes to run on heterogeneous devices and improve the ensemble diversities. To handle the timeout exception, we add vanilla supervised learning on every submodel for the bagging ensemble in case of the early termination of boosting ensemble. As a result, all sub-models can not only run in parallel without much communication but also can be adapted to the heterogeneous devices, while maintaining accuracy even with time-out exceptions. Experiments show that MDP can outperform other baselines by $5 . 2 \times \sim 2 . 1 \times$ in latency and $5 . 1 \times \sim 1 . 7 \times$ in throughput with comparable accuracy.

It is increasingly important for the next-generation exascale supercomputers to extend its applications beyond traditional high-performance computing (HPC) scenarios, so as to achieve high social and economic benefit. Similar to Amazon Web Services (AWS) and Alibaba Cloud, cloud-style virtual HPC service is a promising application scenario on supercomputers, for which remote block storage is the key to provide tenants with supercomputers’ extremely high storage performance. Unfortunately, the state-of-the-art block storage software systems (such as URSA and Ceph) cannot adapt to the advanced hardware features of supercomputers. This article presents UrsaX, an efficient block storage service for our next-generation Tianhe exascale supercomputer that is equipped with the high-performance global express (GLEX) network and nonvolatile memory express (NVMe) SSDs. UrsaX’s virtual disks, which can be mounted like normal physical ones, enable not only traditional HPC applications but also supercomputer-oblivious POSIX applications to enjoy the high performance of supercomputers. At the core of UrsaX is with a novel design of the efficient integration of on-disk block I/O and in-network message transfer on supercomputers. UrsaX utilizes the NVMe Fabrics kernel module to expand the NVMe standard on the supercomputer network, and separates metadata I/O and data I/O of blocks, respectively, being handled over the mini packet (MP) and remote direct memory access (RDMA) protocols. We thoroughly explore the design space for remote block storage on supercomputers, including parallelism, scalability, fault tolerance, and consistency. We conduct an extensive evaluation on a subset of our exascale supercomputer consisting of 44 storage machines (each with four NVMe SSDs). The result shows that UrsaX achieves local-storage-level I/O latency (tens of microseconds) while being able to linearly increase the aggregate performance (IOPS and throughput) as the system scale increases, an order of magnitude higher than the state-of-the-art block storage systems.

Graph neural networks (GNN) have been proven to be mature enough for handling graph-structured data on node-level graph representation learning tasks. However, the graph pooling technique for learning expressive graph-level representation is critical yet still challenging. Existing pooling methods either struggle to capture the local substructure or fail to effectively utilize high-order dependency, thus diminishing the expression capability. In this paper we propose HAP, a hierarchical graph-level representation learning framework, which is adaptively sensitive to graph structures, i.e., HAP clusters local substructures incorporating with high-order dependencies. HAP utilizes a novel cross-level attention mechanism MOA to naturally focus more on close neighborhood while effectively capture higher-order dependency that may contain crucial information. It also learns a global graph content GCont that extracts the graph pattern properties to make the pre- and post-coarsening graph content maintain stable, thus providing global guidance in graph coarsening. This novel innovation also facilitates generalization across graphs with the same form of features. Extensive experiments on ten datasets show that HAP significantly outperforms twelve popular graph pooling methods on graph classification task with an maximum accuracy improvement of 20.18%, and exceeds the performance of state-of-the-art graph matching and graph similarity learning algorithms by over 3.42% and 16%.

This article systematically studies 99 distributed performance bugs from five widely deployed distributed storage and computing systems (Cassandra, HBase, HDFS, Hadoop MapReduce and ZooKeeper). We present the TaxPerf database, which collectively organizes the analysis results as over 400 classification labels and over 2,500 lines of bug re-description. TaxPerf is classified into six bug categories (and 18 bug subcategories) by their root causes; resource, blocking, synchronization, optimization, configuration, and logic. TaxPerf can be used as a benchmark for performance bug studies and debug tool designs. Although it is impractical to automatically detect all categories of performance bugs in TaxPerf, we find that an important category of blocking bugs can be effectively solved by analysis tools. We analyze the cascading nature of blocking bugs and design an automatic detection tool called PCatch , which (i) performs program analysis to identify code regions whose execution time can potentially increase dramatically with the workload size; (ii) adapts the traditional happens-before model to reason about software resource contention and performance dependency relationship; and (iii) uses dynamic tracking to identify whether the slowdown propagation is contained in one job. Evaluation shows that PCatch can accurately detect blocking bugs of representative distributed storage and computing systems by observing system executions under small-scale workloads.

The newly emerging “fail-slow” failures plague both software and hardware where the victim components are still functioning yet with degraded performance. To address this problem, this article presents Perseus , a practical fail-slow detection framework for storage devices. Perseus leverages a light regression-based model to quickly pinpoint and analyze fail-slow failures at the granularity of drives. Within a 10-month close monitoring on 248K drives, Perseus managed to find 304 fail-slow cases. Isolating them can reduce the (node-level) 99.99th tail latency by 48%. We assemble a large-scale fail-slow dataset (including 41K normal drives and 315 verified fail-slow drives) from our production traces, based on which we provide root cause analysis on fail-slow drives covering a variety of ill-implemented scheduling, hardware defects, and environmental factors. We have released the dataset to the public for fail-slow study.

The migration of traditional desktop and server applications to the cloud brings challenge of high performance, high reliability, and low cost to the underlying cloud storage. To satisfy the requirement, this article proposes a hybrid cloud-scale block storage system called Ursa . Trace analysis shows that the I/O patterns served by block storage have only limited locality to exploit. Therefore, instead of using solid state drives (SSDs) as a cache layer, Ursa proposes hybrid storage structure that directly stores primary replicas on SSDs and replicates backup replicas on hard disk drives (HDDs) . At the core of Ursa ’s hybrid storage design is an adaptive journal that can bridge the performance gap between primary SSDs and backup HDDs for random writes by transforming small backup writes into journal appends, which are then asynchronously replayed and merged to backup HDDs. To efficiently index the journal, we design a novel range-optimized merge-tree structure that combines a continuous range of keys into a single composite key {offset,length} . Ursa integrates the hybrid structure with designs for high reliability, scalability, and availability. Experiments show that Ursa in its hybrid mode achieves almost the same performance as in its SSD-only mode (storing all replicas on SSDs), and outperforms other block stores (Ceph and Sheepdog) even in their SSD-only mode while achieving much higher CPU efficiency (IOPS and throughput per core).

Object-based storage systems have been widely used for various scenarios such as file storage, block storage, blob (e.g., large videos) storage, and so on, where the data is placed among a large number of object storage devices (OSDs). Data placement is critical for the scalability of decentralized object-based storage systems. The state-of-the-art CRUSH placement method is a decentralized algorithm that deterministically places object replicas onto storage devices without relying on a central directory. While enjoying the benefits of decentralization such as high scalability, robustness, and performance, CRUSH-based storage systems suffer from uncontrolled data migration when expanding the capacity of the storage clusters (i.e., adding new OSDs), which is determined by the nature of CRUSH and will cause significant performance degradation when the expansion is nontrivial. This article presents MapX , a novel extension to CRUSH that uses an extra time-dimension mapping (from object creation times to cluster expansion times) for controlling data migration after cluster expansions. Each expansion is viewed as a new layer of the CRUSH map represented by a virtual node beneath the CRUSH root. MapX controls the mapping from objects onto layers by manipulating the timestamps of the intermediate placement groups (PGs). MapX is applicable to a large variety of object-based storage scenarios where object timestamps can be maintained as higher-level metadata. We have applied MapX to the state-of-the-art Ceph-RBD (RADOS Block Device) to implement a migration-controllable, decentralized object-based block store (called Oasis ). Oasis extends the RBD metadata structure to maintain and retrieve approximate object creation times (for migration control) at the granularity of expansion layers. Experimental results show that the MapX -based Oasis block store outperforms the CRUSH-based Ceph-RBD (which is busy in migrating objects after expansions) by 3.17× ∼ 4.31× in tail latency, and 76.3% (respectively, 83.8%) in IOPS for reads (respectively, writes).

Distributed stochastic gradient descent (SGD) approach has been widely used in large-scale deep learning, and the gradient collective method is vital to ensure the training scalability of the distributed deep learning system. Collective communication such as AllReduce has been widely adopted for the distributed SGD process to reduce the communication time. However, AllReduce incurs large bandwidth resources while most gradients are sparse in many cases since many gradient values are zeros and should be efficiently compressed for bandwidth saving. To reduce the sparse gradient communication overhead, we propose Sparse-Sketch Reducer (S2 Reducer), a novel sketch-based sparse gradient aggregation method with convergence guarantees. S2 Reducer reduces the communication cost by only compressing the non-zero gradients with count-sketch and bitmap, and enables the efficient AllReduce operators for parallel SGD training. We perform extensive evaluation against four state-of-the-art methods over five training models. Our results show that S2 Reducer converges to the same accuracy, reduces 81% sparse communication overhead, and achieves 1.8× distributed training speedup compared to state-of-the-art approaches.

Graph algorithms, such as Breadth First Search (BFS), Single Source Shortest Path (SSSP), PageRank (PR), and Connected Components (CC), are increasingly important in big data processing and analytics. As graph scales (numbers of vertices and edges) have increased from billions to trillions, Supercomputers have huge numbers (up to hundreds of thousands) of computing nodes (CNs) that can provide ultra-high aggregate computing power and memory capacity, thus being particularly suitable for processing extreme-scale graphs with trillions of vertices and edges. However, existing cluster-based graph-parallel systems perform poorly when deployed on supercomputers, since their partitioning methods overlook the hierarchical nature of supercomputer networks and incur prohibitive communication storm. This paper presents XTree, an efficient traversal-based partitioning method for minimizing communication overhead of graph processing on supercomputers. We observe that supercomputers' huge numbers of CNs are usually organized into hierarchical communication domains, which can be modeled as a domain tree where communication in lower-level domains is significantly faster than that in higher-level ones. Therefore, the key idea of XTree's partitioning is to exploit hierarchical locality by viewing the graph as a BFS tree and leveraging the topology knowledge to map the graph's BFS tree onto the domain tree, We evaluate the effectiveness of XTree by running various graph algorithms, on both real-world big graphs and synthetic trillion-scale graphs. XTree substantially reduces communication overhead and achieves orders of magnitude speedup against the Graph500 reference implementations with the state-of-the-art 2D-decomposition partitioning.

Distributed GNN training tends to generate huge volumes of communication. To reduce communication cost, the state-of-the-art sampling-based techniques sample and retrieve only a subset of the nodes. However, our analysis shows that current sampling algorithms are still inefficient in network communication for distributed GNN training, which is mainly because of three problems: first, they overlook the locality of the sampled neighbor nodes in the cluster; second, they sample data only at the coarse-grained graph node level; and third, some mechanisms they adopted fall short in distributed scenarios. This paper presents a graph sampling framework (DGS) for distributed GNN training, which effectively reduces network communication cost while preserving the final GNN model accuracy. To achieve this, DGS samples neighborhood information based on the locality of the neighbor nodes in the cluster, and samples data at the levels of not only graph nodes but also node features based on explanation. Specifically, DGS constructs an explanation graph which preserves the relationship between the local graph and remote nodes, and leverages the recently-proposed model explanation technique to design an online explanation scheme that interprets the importance of nodes and features. Evaluation results show that DGS achieves up to 1.25× throughput speedup over the state-of-the-art FastGCN and reduces the communication cost by up to 28.3%, while preserving the final model accuracy almost the same as that of full-batch training.

Distributed data-parallel training has been widely adopted for deep neural network (DNN) models. Although current deep learning (DL) frameworks scale well for dense models like image classification models, we find that these DL frameworks have relatively low scalability for sparse models like natural language processing (NLP) models that have highly sparse embedding tables. Most existing works overlook the sparsity of model parameters thus suffering from significant but unnecessary communication overhead. In this paper, we propose EmbRace, an efficient communication framework to accelerate communications of distributed training for sparse models. EmbRace introduces Sparsity-aware Hybrid Communication, which integrates AlltoAll and model parallelism into data-parallel training, so as to reduce the communication overhead of highly sparse parameters. To effectively overlap sparse communication with both backward and forward computation, EmbRace further designs a 2D Communication Scheduling approach which optimizes the model computation procedure, relaxes the dependency of embeddings, and schedules the sparse communications of each embedding row with a priority queue. We have implemented a prototype of EmbRace based on PyTorch and Horovod, and conducted comprehensive evaluations with four representative NLP models. Experimental results show that EmbRace achieves up to 2.41 × speedup compared to the state-of-the-art distributed training baselines.

ByteScheduler partitions and rearranges tensor transmissions to improve the communication efficiency of distributed Deep Neural Network (DNN) training. The configuration of hyper-parameters (i.e., the partition size and the credit size) is critical to the effectiveness of partitioning and rearrangement. Currently, ByteScheduler adopts Bayesian Optimization (BO) to find the optimal configuration for the hyper-parameters beforehand. In practice, however, various runtime factors (e.g., worker node status and network conditions) change over time, making the statically-determined one-shot configuration result suboptimal for real-world DNN training.To address this problem, we present a real-time configuration method (called AutoByte) that automatically and timely searches the optimal hyper-parameters as the training systems dynamically change. AutoByte extends the ByteScheduler framework with a meta-network, which takes the system’s runtime statistics as its input and outputs predictions for speedups under specific configurations. Evaluation results on various DNN models show that AutoByte can dynamically tune the hyper-parameters with low resource usage, and deliver up to 33.2% higher performance than the best static configuration in ByteScheduler.

Distributed mixed-criticality system (DMCS) has been widely used in various critical domains such as self-driving cars and space crafts. To guarantee the end-to-end QoS (i.e., deadline/jitter requirements) of sensing-controlling-actuating control loops (CL) applications, DMCS adopts Time-Sensitive Networking (TSN), an emerging real-time Ethernet technology, for communication between end systems (ES). TSN provides a synchronized global clock and guarantees bounded delay for time-critical traffic in CLs, making it possible for DMCS to collaboratively schedule the computation (on ES) and communication (in TSN) to meet the Quality of Service (QoS) requirement. However, as modern DMCS tends to use fully-fledged Linux distributions (rather than a custom real-time OS) on ES to enjoy Linux’s mature ecosystem, it is challenging for DMCS to realize TSN-based QoS guarantees because the event-triggered scheduling of Linux on ES is incompatible with TSN.This paper proposes TAsk Scheduling Puppeteer (TASP), a mechanism that schedules CL tasks based on TSN without modifying the Linux OS. The key idea of TASP is to manipulate task scheduling by controlling the timing of CL packet submissions at the interface between TSN and ES. Specifically, TASP extracts two parameters: Fore Guardband (ForeGB) and Back Guardband (BackGB). During the ForeGB period before a CL packet’s submission, TASP forbids any packets’ submission; while during the BackGB period after a CL packet’s submission, TASP forbids any other CL packets’ submission. ForeGB and BackGB can ensure that there is at most one schedulable task on the ES at any time, and thus Linux has no choice but to schedule the only task, making the Linux scheduler a puppet. We have deployed TASP and evaluated it in real-world TSN switches based on an open-source TSN project, OpenTSN. The TASP-enabled ES can achieve task scheduling precisely based on TSN’s global clock, which outperforms the original ES by reducing end-to-end jitter from milliseconds to microseconds.

To lower the monetary/energy cost, single-machine multicore graph processing is gaining increasing attention for a wide range of traversal-centric graph algorithms such as BFS, SSSP, CC, and PageRank, of which the processing is relatively simple and the topology data (vertices and edges) dominates the memory footprint. This paper presents$v$Graph, a NUMA-aware, memory-efficient multicore graph processing system for traversal-centric algorithms.$v$Graph proposes an ultralight NUMA-aware graph preprocessing scheme which eliminates almost all complex preprocessing steps and pipelines per-NUMA graph loading and compressing, to effectively reduce inter-NUMA memory accesses while keeping both preprocessing cost and peak memory footprint low. We further optimize$v$Graph with effective HPC techniques including prefetching and work-stealing. Evaluation on a 384GB-memory, four-NUMA machine shows that compared to the state-of-the-art NUMA-aware/-unaware systems,$v$Graph can process much larger real-world and synthetic graphs with various traversal-centric algorithms, achieving significantly higher memory efficiency and lower processing time.

Summary Performance evaluation is the basis for choosing appropriate system‐level configurations for large‐scale data centers. While the change of a system‐level configuration would impact lots of jobs in the data centers, traditional load‐testing benchmarks are not sufficient to support the decision‐making because they cannot accurately reproduce the complex behaviors of a large number of jobs. Therefore, we expect to further evaluate the system configuration based on the production environment. However, there are technical challenges, namely, the lack of a holistic evaluation method that can unite the evaluation results of various jobs, and the uninterruptable production environment that should not be affected by the evaluation procedure. To address these challenges, we propose a holistic performance evaluation methodology and design its implementation platform. We introduce a simple but powerful performance metric, ERU (effectiveness of resource usage), and combine the ERU of involved jobs into a summarized value to measure the effect of a configuration change. We validate our ERU metric by comparing it with the CPI (Cycle per Instruction) and QPS (query per second) metrics, deploy the platform to production data centers and demonstrate the effectiveness for measuring system‐level configurations of both software (JVM compiler update) and hardware (NUMA on/off) to save 14.44% and 11% resources respectively in advance.

Online-transaction-processing (OLTP) applications require the underlying storage system to guarantee consistency and serializability for distributed transactions involving large numbers of servers, which tends to introduce high coordination cost and cause low system performance. In-network coordination is a promising approach to alleviate this problem, which leverages programmable switches to move a piece of coordination functionality into the network. This paper presents a fast and scalable transaction processing system called SwitchTx. At the core of SwitchTx is a decentralized multi-switch in-network coordination mechanism, which leverages modern switches' programmability to reduce coordination cost while avoiding the central-switch-caused problems in the state-of-the-art Eris transaction processing system. SwitchTx abstracts various coordination tasks (e.g., locking, validating, and replicating) as in-switch gather-and-scatter (GaS) operations, and offloads coordination to a tree of switches for each transaction (instead of to a central switch for all transactions) where the client and the participants connect to the leaves. Moreover, to control the transaction traffic intelligently, SwitchTx reorders the coordination messages according to their semantics and redesigns the congestion control combined with admission control. Evaluation shows that SwitchTx outperforms current transaction processing systems in various workloads by up to 2.16X in throughput, 40.4% in latency, and 41.5% in lock time.

Spectral clustering (SC) is an unsupervised learning method that has been widely used in industrial product analysis. Compressive spectral clustering (CSC) effectively accelerates clustering by leveraging graph filter and random sampling techniques. However, CSC suffers from two major problems. First, the direct use of the dichotomy and eigencount techniques for estimating Laplacian matrix's$k$kth eigenvalue is expensive. Second, the computation of interpolation is time-consuming because it requires to repeat matrix-vector product for every cluster in each iteration. To address these problems, we propose a new method calledfast compressive spectral clustering(FCSC). Our method addresses the first problem by assuming that the eigenvalues approximately satisfy local uniform distribution, and addresses the second problem by recalculating the pairwise similarity between nodes with low-dimensional representation to reconstruct denoised laplacian matrix. The time complexity of reconstruction is linear with the number of non-zeros in Laplacian matrix. As experimentally demonstrated on both artificial and real-world datasets, our method significantly reduces the computation time while preserving high clustering accuracy comparable to previous designs, demonstrating the effectiveness of FCSC.

Commercial clouds now heavily use CPUs in DL (deep learning) because there are large numbers of CPUs which would otherwise sit idle during off-peak periods. Following the trend, CPU vendors have not only released high-performance many-core CPUs but also developed efficient math kernel libraries. However, current DL platforms cannot scale well to a large number of CPU cores, making many-core CPUs inefficient in DL computation. We analyze the memory access patterns of various layers and identify the root cause of the low scalability, i.e., the per-layer barriers that are implicitly imposed by current platforms which assign one single instance (i.e., one batch of input data) to a CPU. The barriers cause severe memory bandwidth contention and CPU starvation in the access-intensive layers (like activation and BN). This paper presents a novel approach called ParaX, which boosts the performance of DL on multi-NUMA (non-uniform memory access) many-core CPUs by effectively alleviating bandwidth contention and CPU starvation. Our key idea is to assign one instance to each CPU core instead of to the entire CPU, so as to remove the per-layer barriers on the executions of the many cores. ParaX designs an ultralight scheduling policy which sufficiently overlaps the access-intensive layers with the compute-intensive ones to avoid contention, and proposes a NUMA-aware gradient server mechanism for training which leverages shared memory to substantially reduce the overhead of per-iteration parameter synchronization. We have implemented ParaX on MXNet. Extensive evaluation on a two-NUMA Intel 8280 CPU shows that ParaX significantly improves the training/inference throughput for all tested models (for image recognition and natural language processing) by$1.73\times \sim 2.93{\times}$.

As the era of exascale supercomputing is coming, it is vital for next-generation supercomputers to find appropriate applications with high social and economic benefit. In recent years, it has been widely accepted that extremely-large graph computation is a promising killer application for supercomputing. Although Tianhe series supercomputers are leading in the world-wide competition of supercomputing (ranked No. 1 in the Top500 list for six times), previously they had been inefficient in graph computation according to the Graph500 list. This is mainly because the previous graph processing system cannot leverage the advanced hardware features of Tianhe supercomputers. To address the problem, in this paper we present our integrated optimizations for improving the graph computation performance on our next-generation Tianhe supercomputing system, mainly including sorting with buffering for heavy vertices, vectorized searching with SVE (Scalable Vector Extension) on matrix2000+ CPUs, and group communication on the proprietary interconnection network. Performance evaluation on a subset of the Tianhe supercomputer (with 512 nodes and 196,608 cores) shows that our customized graph processing system effectively improves the graph search performance and achieves the BFS performance of 2131.98 GTEPS.

Gradient quantization has been widely used in distributed training of deep neural network (DNN) models to reduce communication costs. However, existing quantization methods overlook that gradients have a nonuniform distribution changing over time, which can lead to significant gradient variance that requires a higher number of quantization bits (and consequently higher communication cost) to keep the validation accuracy as high as stochastic gradient descent (SGD). In this paper, we propose Cluster-Aware Sketch Quantization (CASQ), a novel sketch-based gradient quantization method for SGD. CASQ models the nonuniform distribution of gradients via clustering, and adaptively allocates appropriate numbers of hash buckets based on the statistics of different clusters to compress gradients. The extensive evaluation shows that compared to existing quantization methods CASQ-based SGD (i) achieves the same validation accuracy when decreasing quantization level from 3 bits to 2 bits, and (ii) reduces the training time to convergence by up to 43% for the same training loss.

Modern distributed machine learning (ML) systems leverage large-scale computing infrastructures to achieve fast model training. For many servers jointly training a model, failure recovery becomes an important challenge when a training task could be accomplished in minutes rather than days. The state-of-the-art checkpointing mechanism cannot meet the need of efficient recovery for large-scale ML, because its high cost prevents timely checkpointing and a server failure will likely cause a substantial loss of intermediate results when the checkpointing intervals are comparable to the entire training times. This paper proposes FreeLauncher (FLR), a lossless recovery mechanism for large-scale ML which performs ultralight replication (instead of checkpointing) to guarantee all intermediate training results (parameters) to be timely replicated. Our key insight is that in the parameter-server (PS) architecture there already exist multiple copies for each intermediate result not only in the server but also in the workers, most of which are qualified for failure recovery. FLR addresses the challenges of parameter sparsity (e.g., when training LDA) and staleness (e.g., when adopting relaxed consistency) by selectively replicating the latest copies of the sparse/stale parameters to ensure at least k up-to-date copies to be existent, which can handle any k-1 failures by re-launching the failed servers with recovered parameters from workers. We implement FLR on Tensorflow. Evaluation results show that FLR achieves lossless failure recovery (almost requiring no recomputation) at little cost.

The major usage of a distributed block storage integrated with a cloud computing platform is to provide the storage for VM (virtual machine) instances. Traditional desktop and server applications tend to be written with small I/O being dominant, and in limited parallelism. Hence the performance of block storage serving these applications migrated to cloud is largely determined by latency of small I/O. This paper presents IndigoStore, an optimized Ceph backend to implement cloud-scale block storage that provides virtual disks for cloud VMs. The design of IndigoStore aims to optimize Ceph BlueStore backend, the state-of-the-art distributed storage backend, to reduce both average and tail latency of small I/O, meanwhile not waste disk bandwidth serving large I/O. We use both microbenchmarks and our production workloads to demonstrate that IndigoStore achieves 29%∼44 % lower average latency, and up to 1.23×lower 99.99thpercentile tail latency than BlueStore, without any notable negative effects on other performance metrics.

Blockchain(e.g., Bitcoin) has widespread use in digital currency, which is entirely public to all participants, revealing users' privacy and transaction details. Anonymous blockchains without auditing capability can offer strong privacy guarantees, they could be used by illegal activities. However, anonymous blockchains with auditing capability suffer from two limitations: (i) inefficient auditing capability; (ii) lower degree of decentralization. To address these problems, this paper presents IAP, an instant auditing protocol based on anonymous blockchain with strong anonymity guarantees, which uses audit node cluster to implement decentralized instant auditing. The experimental results show that IAP only needs 60 milliseconds to complete an audit on average with 16 audit nodes, which accounts for one thousand of a complete transaction time. IAP can still complete efficient auditing when there are more than half of the nodes are honest in the audit node cluster. Moreover, its performance is virtually unaffected by increased number of transactions.

Abstract With the rapid growth of RDF (resource description framework) data volume, it is challenging to answer queries over dynamic RDF graphs of which the data frequently changes (by insertion/deletion) over time. This article presents QRDF, an efficient RDF graph processing system that supports not only efficient storage but also fast query of dynamic RDF graphs. QRDF (i) adopts a red‐black (RB) tree for quick RDF data insertion/deletion and (ii) asynchronously moves data from the RB tree into a vector for efficient RDF query. QRDF performs early pruning on its index structure for various RDF query patterns. Experimental results show that the query performance of QRDF over RDF graphs is about 2x higher than that of the state‐of‐the‐art RDF processing systems.

Abstract GPUs and CPUs have been widely used for model training of deep learning (DL) in the cloud, where both DL workloads and resource usage might heavily change over time. Traditional training methods require beforehand specification on the type (either GPUs or CPUs) and amount of computing devices, and thus cannot elastically schedule the dynamic DL workloads onto available GPUs/CPUs. In this paper, we propose Elastic Scheduler (ES), a novel approach that efficiently supports both heterogeneous training (with different device types) and dynamic training (with varying device numbers). ES (i) accumulates local gradients and simulates multiple virtual workers on one GPU to alleviate the performance gap between GPUs and CPUs for achieving similar accuracy in heterogeneous GPU‐CPU‐hybrid training as in homogeneous training and (ii) uses local gradients stabilizes batch sizes for high accuracy without long compensation. Experiments show that ES achieves significantly higher performance than existing methods for heterogeneous and dynamic training as well as inference.

Despite the fact that GPUs and accelerators are more efficient in deep learning (DL), commercial clouds like Facebook and Amazon now heavily use CPUs in DL computation because there are large numbers of CPUs which would otherwise sit idle during off-peak periods. Following the trend, CPU vendors have not only released high-performance many-core CPUs but also developed efficient math kernel libraries. However, current DL platforms cannot scale well to a large number of CPU cores, making many-core CPUs inefficient in DL computation. We analyze the memory access patterns of various layers and identify the root cause of the low scalability, i.e., the per-layer barriers that are implicitly imposed by current platforms which assign one single instance (i.e., one batch of input data) to a CPU. The barriers cause severe memory bandwidth contention and CPU starvation in the access-intensive layers (like activation and BN). This paper presents a novel approach called ParaX, which boosts the performance of DL on many-core CPUs by effectively alleviating bandwidth contention and CPU starvation. Our key idea is to assign one instance to each CPU core instead of to the entire CPU, so as to remove the per-layer barriers on the executions of the many cores. ParaX designs an ultralight scheduling policy which sufficiently overlaps the access-intensive layers with the compute-intensive ones to avoid contention, and proposes a NUMA-aware gradient server mechanism for training which leverages shared memory to substantially reduce the overhead of per-iteration parameter synchronization. We have implemented ParaX on MXNet. Extensive evaluation on a two-NUMA Intel 8280 CPU shows that ParaX significantly improves the training/inference throughput for all tested models (for image recognition and natural language processing) by 1.73X ~ 2.93X.

For many data-parallel computing systems like Spark, a job usually consists of multiple computation stages and inter-stage communication (i.e., coflows). Many efforts have been done to schedule coflows and jobs independently. The simple combination of coflow scheduling and job scheduling, however, would prolong the average job completion time (JCT) due to the conflict. For this reason, we propose a new abstraction of scheduling unit, named coBranch, which takes the dependency between computation stages and coflows into consideration, to schedule coflows and jobs jointly. Besides, mainstream coflow schedulers are order-preserving, i.e., all coflows of a high-priority job are prioritized than those of a low-priority job. We observe that the order-preserving constraint incurs low inter-job parallelism. To overcome the problem, we employ an urgency-based mechanism to schedule coBranches, which aims to decrease the average JCT by enhancing the inter-job parallelism. We implement the urgency-based coBranch Scheduling (BS) method on Apache Spark, conduct prototype-based experiments, and evaluate the performance of our method against the shortest-job-first critical-path method and the FIFO method. Results show that our method achieves around 10 and 15 percent reduction in the average JCT, respectively. Large-scale simulations based on the Google trace show that our method performs better and reduces JCT by 23 and 35 percent, respectively.

Under-allocating or over-allocating computation resources (e.g., CPU cores) can prolong the completion time of data-parallel jobs in a distributed system. We present a predictor, ReLocag, to find the near-optimal number of CPU cores to minimize job completion time (JCT). ReLocag includes a graph convolutional network (GCN) and a fully-connected network (FCNN). The GCN learns the dependency between operations from the workflow of a job, and then the FCNN takes the workflow dependency together with other features (e.g., the input size, the number of CPU cores, the amount of memory, and the number of computation tasks) as input for JCT prediction. The prediction result can guide the user to determine the near-optimal number of CPU cores. Besides, we propose two effective strategies to overcome the time-consuming issue of training sample collection in big data applications. First, we develop an adaptive sampling method to collect essential samples judiciously. Second, we further design a cross-application transfer learning model to exploit the training samples collected from other applications. We conduct extensive experiments in a Spark cluster for 7 types of exemplary Spark applications. Results show that ReLocag improves the JCT prediction accuracy by 4-14 percent. Moreover, the CPU core consumption decreases by 58.2 percent.

Distributed graph computation is central to applications ranging from language processing to social networks. However, natural graphs tend to have skewed power-law distrbutions where a small subset of the vertices have a large number of neighbors. Existing graph-parallel systems suffer from load imbalance, high communication cost, and inefficient processing. To address this problem, in this paper we present GraphA, an adaptive scheme for efficient large-scale graph computation. At the core of GraphA is an adaptive and uniform graph partitioning algorithm, which partitions the datasets by using an incremental number of mapping functions. GraphA further improves and leverages the ART index structure to realize fine-grained and low-cost graph storage. We have implemented GraphA both on Spark and on GraphLab. Extensive evaluation shows that GraphA significantly outperforms state-of-the-art graph-parallel systems (GraphX and PowerLyra) in ingress time, execution time and storage cost, for both real-world and synthetic graphs. GraphA achieves up to 7.1 x performance improvement over GraphX and 19.7 percent improvement over PowerLyra.

Network monitoring is vital in modern clouds and data center networks that need diverse traffic statistics ranging from flow size distributions to heavy hitters. To cope with increasing network rates and massive traffic volumes, sketch based approximate measurement has been extensively studied to trade the accuracy for memory and computation cost, which unfortunately, is sensitive to hash collisions.This paper presents a clustering-preserving sketch method to be resilient to hash collisions. We provide an equivalence analysis of the sketch in terms of the K-means clustering. Based on the analysis result, we cluster similar network flows to the same bucket array to reduce the estimation variance and use the average to obtain unbiased estimation. Testbed shows that the framework adapts to line rates and provides accurate query results. Real-world trace-driven simulations show that LSS remains stable performance under wide ranges of parameters and dramatically outperforms state-of-the-art sketching structures, with over 103to 105times reduction in relative errors for per-flow queries as the ratio of the number of buckets to the number of network flows reduces from 10% to 0.1%.

Large-scale cloud block storage provides virtual disks for various applications and services like online booking, gaming, and offline data analytics. The state-of-the-art URSA [1] block store adopted a hybrid storage structure which placed primary data on solid-state drives (SSDs) and stored backup data on hard-disk drives (HDDs). URSA used small SSD journals to bridge the performance gap between SSDs and HDDs. Although URSA's SSD-HDD-hybrid storage structure achieves SSD-like I/O performance while using only one third of the SSDs required by the SSD-only storage pattern (storing both primary data and backup data on SSDs), we argue that the traditional HDDonly storage structure is still preferable for a large variety of relatively low-end customers and underloaded applications that are sensitive to the per-bit storage cost.To lower the storage cost, in this paper we design URSAL, an HDD-only block store which provides ultra efficiency, reliability, scalability and availability at low cost. Compared to existing block stores such as URSA, Ceph, and Sheepdog, URSAL has the following distinctions. First, URSAL designs the proxy-based storage architecture, where a proxy server process runs together with each virtual machine (VM) client mounting virtual disks and controls the procedure of all block-level I/O. Second, URSAL selectively performs direct block writes on raw HDDs or indirect log appends to HDD journals (which are then asynchronously replayed to raw HDDs), depending on the characteristics of the workloads. Third, URSAL runs one storage server process for each physical HDD, which conservatively has at most one active thread reading/writing the HDD to avoid I/O contention. We have implemented URSAL. Evaluation results show that URSAL significantly outperforms state-of-the-art HDD-only block stores (Ceph and Sheepdog) when providing virtual disks for underloaded applications.

Graph is a significant data structure that describes the relationship between entries. Many application domains in the real world are heavily dependent on graph data. However, graph applications are vastly different from traditional applications. It is inefficient to use general-purpose platforms for graph applications, thus contributing to the research of specific graph processing platforms. In this survey, we systematically categorize the graph workloads and applications, and provide a detailed review of existing graph processing platforms by dividing them into general-purpose and specialized systems. We thoroughly analyze the implementation technologies including programming models, partitioning strategies, communication models, execution models, and fault tolerance strategies. Finally, we analyze recent advances and present four open problems for future research.

Deep reinforcement learning (RL) has become one of the most popular topics in artificial intelligence research. It has been widely used in various fields, such as end-to-end control, robotic control, recommendation systems, and natural language dialogue systems. In this survey, we systematically categorize the deep RL algorithms and applications, and provide a detailed review over existing deep RL algorithms by dividing them into modelbased methods, model-free methods, and advanced RL methods. We thoroughly analyze the advances including exploration, inverse RL, and transfer RL. Finally, we outline the current representative applications, and analyze four open problems for future research.

Efficient graph partitioning is vital for high-performance graph-parallel systems. Traditional graph partitioning methods attempt to both minimize communication cost and guarantee load balancing in computation. However, the skewed degree distribution of natural graphs makes it difficult to simultaneously achieve the two objectives. This article proposes topology refactorization (TR), a topology-aware method allowing graph-parallel systems to separately handle the two objectives: refactorization is mainly focused on reducing communication cost, and partitioning is mainly targeted for balancing the load. TR transforms a skewed graph into a more communication-efficient topology through fusion and fission, where the fusion operation organizes a set of neighboring low-degree vertices into a super-vertex, and the fission operation splits a high-degree vertex into a set of sibling sub-vertices. Based on TR, we design an efficient graph-parallel system (TopoX) which pipelines refactorization with partitioning to both reduce communication cost and balance computation load. Prototype evaluation shows that TopoX outperforms PowerLyra by up to 78.5% (from 37.2%) on real-world graphs and is faster than most other graph-parallel systems, while only introducing small overhead and memory consumption.

Block storage provides virtual disks that can be mounted by virtual machines (VMs). Although erasure coding (EC) has been widely used in many cloud storage systems for its high efficiency and durability, current EC schemes cannot provide high-performance block storage for the cloud. This is because they introduce significant overhead to small write operations (which perform partial write to an entire EC group), whereas cloud-oblivious applications running on VMs are often small-write-intensive. We identify the root cause for the poor performance of partial writes in state-of-the-art EC schemes: for each partial write, they have to perform a time-consuming write-after-read operation that reads the current value of the data and then computes and writes the parity delta, which will be used to “patch” the parity in journal replay. In this article, we present a speculative partial write scheme (called P ARI X) that supports fast small writes in erasure-coded storage systems. We transform the original formula of parity calculation to use the data deltas (between the current/original data values), instead of the parity deltas, to calculate the parities in journal replay. For each partial write, this allows P ARI X to speculatively log only the new value of the data without reading its original value. For a series of n partial writes to the same data, P ARI X performs pure write (instead of write-after-read) for the last n -1 ones while only introducing a small penalty of an extra network round-trip time to the first one. Based on P ARI X, we design and implement P ARI X Block Storage (PBS), an efficient block storage system that provides high-performance virtual disk service for VMs running cloud-oblivious applications. PBS not only supports fast partial writes but also realizes efficient full writes, background journal replay, and fast failure recovery with strong consistency guarantees. Both microbenchmarks and trace-driven evaluation show that PBS provides efficient block storage and outperforms state-of-the-art EC-based systems by orders of magnitude.

This paper presents URSA, a hybrid block store that provides virtual disks for various applications to run efficiently on cloud VMs. Trace analysis shows that the I/O patterns served by block storage have limited locality to exploit. Therefore, instead of using SSDs as a cache layer, URSA proposes an SSD-HDD-hybrid storage structure that directly stores primary replicas on SSDs and replicates backup replicas on HDDs, using journals to bridge the performance gap between SSDs and HDDs. URSA integrates the hybrid structure with designs for high reliability, scalability, and availability. Experiments show that URSA in its hybrid mode achieves almost the same performance as in its SSD-only mode (storing all replicas on SSDs), and outperforms other block stores (Ceph and Sheepdog) even in their SSD-only mode while achieving much higher CPU efficiency (performance per core). We also discuss some practical issues in our deployment.

With growing scale of the data volume and neural network size, we have come into the era of distributed deep learning. High-performance training and inference on distributed computing systems has been attracting increasing research attention in both academia and industry. Meanwhile, diversity of existing machine learning frameworks (e.g. TensorFlow, Pytorch and MXNet) and the explosion of deep learning hardwares (e.g. CPUs, GPUs, FPGAs and ASICs) bring more challenges for users to leverage new deep learning technologies and accelerating capability of hardware devices. We firstly search around the state-of-the-art work in the area which open our mind to take a vision upon the future deep learning framework. Then, we propose HPDL, a general framework for high-performance distributed deep learning which is compatible with existing frameworks and adaptive to various hardware architectures. At last, we discuss and foresee the key technologies fulfilling high-performance and large-scale deep learning, including optimization algorithm, hybrid communication mechanism, model parallelization, resource scheduling and single-node execution optimization.

A data-parallel job is characterized as a directed acyclic graph (DAG) which usually consists of multiple computation stages and across-stage data transfers. However, classical DAG scheduling strategies like the critical path method ignore other stages off the main path and do not give specific consideration of data locality, transfer costs, etc. In practice, complicated DAGs include multiple paths which overlap with each other. The intersection of different paths in a DAG job forms an important synchronization. The synchronization significantly impacts the job completion time and however, no known scheduling methods are designed to speed up the completion time of the synchronization especially when complicated DAGs involve nested and hierarchical synchronizations. To the end, we propose a new abstraction, named branch, which is referred to a disjoint path in DAGs, and design a branch scheduling method to decrease the average job completion time of multiple data-parallel jobs. The branch scheduling method leverages the urgency of branches to speed up the synchronization of multiple parallel branches. We have implemented the BS method on Apache Spark and conducted prototype-based experiments. Compared with Spark FIFO and the shortest-job-first with the critical path methods, results show that the branch scheduling method achieves around 10-15% reduction in the average job completion time.

Traditional graph partitioning methods attempt to both minimize communication cost and guarantee load balancing in computation. However, the skewed degree distribution of natural graphs makes it difficult to simultaneously achieve the two objectives. This paper proposes topology refactorization (TR), a topology-aware method allowing graph-parallel systems to separately handle the two objectives: refactorization is mainly focused on reducing communication cost, and partitioning is mainly targeted for balancing the load. TR transforms a skewed graph into a more communication-efficient topology through fusion and fission , where the fusion operation organizes a set of neighboring low-degree vertices into a super-vertex, and the fission operation splits a high-degree vertex into a set of sibling sub-vertices. Based on TR, we design an efficient graph-parallel system (TopoX) which pipelines refactorization with partitioning to both reduce communication cost and balance computation load. Prototype evaluation shows that TopoX outperforms state-of-the-art PowerLyra by up to 78.5% (from 37.2%) on real-world graphs and is significantly faster than other graph-parallel systems, while only introducing small refactorization overhead and memory consumption.

Unikernel specializes a minimalistic LibOS and a target application into a standalone single-purpose virtual machine (VM) running on a hypervisor, which is referred to as (virtual) appliance . Compared to traditional VMs, Unikernel appliances have smaller memory footprint and lower overhead while guaranteeing the same level of isolation. On the downside, Unikernel strips off the process abstraction from its monolithic appliance and thus sacrifices flexibility, efficiency, and applicability. In this article, we examine whether there is a balance embracing the best of both Unikernel appliances (strong isolation) and processes (high flexibility/efficiency). We present KylinX, a dynamic library operating system for simplified and efficient cloud virtualization by providing the pVM (process-like VM) abstraction. A pVM takes the hypervisor as an OS and the Unikernel appliance as a process allowing both page-level and library-level dynamic mapping. At the page level, KylinX supports pVM fork plus a set of API for inter-pVM communication (IpC, which is compatible with conventional UNIX IPC). At the library level, KylinX supports shared libraries to be linked to a Unikernel appliance at runtime. KylinX enforces mapping restrictions against potential threats. We implement a prototype of KylinX by modifying MiniOS and Xen tools. Extensive experimental results show that KylinX achieves similar performance both in micro benchmarks (fork, IpC, library update, etc.) and in applications (Redis, web server, and DNS server) compared to conventional processes, while retaining the strong isolation benefit of VMs/Unikernels.

Distributed RAM storage aggregates the RAM of servers in data center networks (DCN) to provide extremely high I/O performance for large-scale cloud systems. For quick recovery of storage server failures, MemCube [53] exploits the proximity of the BCube network to limit the recovery traffic to the recovery servers’ 1-hop neighborhood. However, the previous design is applicable only to the symmetric BCube( n , k ) network with n k +1 nodes and has suboptimal recovery performance due to congestion and contention. To address these problems, in this article, we propose CubeX, which (i) generalizes the “1-hop” principle of MemCube for arbitrary cube-based networks and (ii) improves the throughput and recovery performance of RAM-based key-value (KV) store via cross-layer optimizations. At the core of CubeX is to leverage the glocality (= globality + locality) of cube-based networks: It scatters backup data across a large number of disks globally distributed throughout the cube and restricts all recovery traffic within the small local range of each server node. Our evaluation shows that CubeX not only efficiently supports RAM-based KV store for cube-based networks but also significantly outperforms MemCube and RAMCloud in both throughput and recovery time.

Cloud-based application systems are rapidly deployed worldwide in production use via virtualization and services computing technologies. The scaling demands for these application capabilities to the cloud providers, compound with differentiated requirements on the quality of services, have brought severe technical challenges. This special section focuses on the techniques of virtualization and services for cloud-based application systems, mainly including multi-scale resource management and sharing, elastic scheduling and allocation of computing and network resources, monitoring and diagnosis for cloud-based services, and cloud-based mobile systems. The articles of this special section illustrate recent advances in virtualization and services provisioning for cloud-based application systems. We expect that this special section will provide an integrated view of the state-of-the-art techniques, identify new challenges as well as opportunities, and promote collaboration among researchers in this field. We received 34 submissions and we finally accepted 4 articles. The acceptance rate is as low as 11.8 percent.

Presents corrections to author affiliation information in the paper, “Guest Editor’s Introduction: Special Section on Virtualization and Services for Cloud-Based Application Systems,” (Zhange, Y. et al), IEEE Trans. Serv. Comput., vol. 12, no. 1, pp. 88–90, Jan./Feb. 2019.

Distributed systems have become the backbone of modern clouds. Users often expect high scalability and performance isolation from distributed systems. Unfortunately, a type of poor software design, which we refer to as performance cascading bugs (PCbugs), can often cause the slowdown of non-scalable code in one job to propagate, causing global performance degradation and even threatening system availability.

Virtual machines (VMs) and processes are two important abstractions for cloud virtualization, where VMs usually install a complete operating system (OS) executing user processes. Although existing in different layers in the virtualization hierarchy, VMs and processes have overlapped functionalities. For example, they are both intended to provide execution abstraction (e.g., physical/virtual memory address space), and share similar objectives of isolation, cooperation and scheduling. However, neither of them could provide the benefits of the other: VMs provide higher isolation, security and portability, while processes are more efficient, flexible and easier to schedule and cooperate. Currently, this heavyweight architecture degrades both efficiency and security of cloud services. There are two trends for cloud virtualization: the first is to enhance processes to achieve VM-like security, and the second is to reduce VMs to achieve process-like flexibility. Based on these observations, our vision is that in the near future VMs and processes might be fused into one new abstraction for cloud virtualization that embraces the best of both, providing VM-level isolation and security while preserving process-level efficiency and flexibility. We describe a reference implementation, dubbed cKernel (customized kernel), for the new abstraction. Essentially, cKernel enhances the exokernel architecture by (i) adopting the LibOS paradigm to assemble isolated, smallest possible "execution environments", and (ii) following the the "core-shell" model to dynamically add traditional process features to the environments.

Depthwise convolutions provide significant performance benefits owing to the reduction in both parameters and mult-adds. However, training depthwise convolution layers with GPUs is slow in current deep learning frameworks because their implementations cannot fully utilize the GPU capacity. To address this problem, in this paper we present an efficient method (called diagonalwise refactorization) for accelerating the training of depthwise convolution layers. Our key idea is to rearrange the weight vectors of a depthwise convolution into a large diagonal weight matrix so as to convert the depthwise convolution into one single standard convolution, which is well supported by the cuDNN library that is highly-optimized for GPU computations. We have implemented our training method in five popular deep learning frameworks. Evaluation results show that our proposed method gains 15.4× training speedup on Darknet, 8.4× on Caffe, 5.4× on PyTorch, 3.5× on MXNet, and 1.4× on TensorFlow, compared to their original implementations of depthwise convolutions.

In recent years cloud computing provides a new way to address the constraints of limited energy, capabilities, and resources. Distributed hash table (DHT) based distributed networks have become increasingly important for efficient communication in large-scale cloud systems. Previous studies mainly focus on improving the performance such as latency, scalability and robustness, but seldom consider the security demands on the routing paths, for example, bypassing untrusted intermediate nodes. Inspired by Internet source routing, in which the source nodes specify the routing paths taken by their packets, this paper presents CSR, a tag-based, Classified Source Routing scheme in distributed networks to satisfy the security demands on the routing paths. Different from Internet source routing which requires some map of the overall network, CSR operates in a distributed manner where nodes with certain security level are tagged with a label and routing messages requiring that level of security are forwarded only to the qualified next-hops. We show how this can be achieved efficiently, by simple extensions of the traditional routing structures, and safely, so that the routing is uniformly convergent. The effectiveness of our proposals is demonstrated through theoretical analysis and extensive simulations.

The modular datacenter networks (MDCN) comprise inter- and intra-container networks. Although it simplifies the construction and maintenance of mega-datacenters, interconnecting hundreds of containers and supporting online data-intensive services is still challenging. In this paper, we present meGautz, which is the first inter-container network that isolates inter- and intra-container traffic, and it has the following advantages. First, meGautz offers uniform high capacity among servers in the different containers, and balances loads at the container, switch, and server levels. Second, it achieves traffic isolation and allocates bandwidth evenly. Therefore, even under an all-to-all traffic pattern, the inter- and intra-container networks can deal with their own flows without interfering with each other, and both can gain high throughput. meGautz hence improves the performance of both the entire MDCN and individual servers, for there is no performance loss caused by resource competition. Third, meGautz is the first to achieve as graceful performance degradation as computation and storage do. Results from theoretical analysis and experiments demonstrate that meGautz is a high-capacity, fault-tolerant, and traffic isolated inter-container network.

Large-scale graph computation is central to applications ranging from language processing to social networks. However, natural graphs tend to have skewed power-law distributions where a small subset of the vertices have a large number of neighbors. Existing graph-parallel systems suffer from load imbalance, high communication cost, or suboptimal and complex processing. In this paper we present GraphA, an Adaptive approach to efficient partitioning and computation of large-scale natural graphs. GraphA provides an adaptive and uniform graph partitioning algorithm, which partitions the datasets in a load-balanced manner by using an incremental number of hash functions. We have implemented GraphA both on Spark and on GraphLab. Extensive evaluation shows that GraphA remarkably outperforms state-of-the-art graph-parallel systems (GraphX and PowerLyra) in ingress time, execution time and storage overhead, for both real-worldand synthetic graphs.

Cloud computing has completely changed the economics of IT industry. Recently, the new form of "shared global economy" requires cloud services to be collaboratively provisioned by different cloud providers in a Geo-distributed manner, which brings severe challenges in service performance and cost. To address this problem, in this paper we propose JointCloud, a cross-cloud cooperation architecture for integrated Internet service customization. JointCloud borrows the idea from airline alliances and aims at empowering the cooperation among multiple clouds to provide efficient cross-cloud services. JointCloud focuses not only on the vertical integration of cloud resources but also on the horizontal cooperation among different cloud vendors. This paper describes the concept and architecture of JointCloud, as well as the initial design of the key components, namely, communication, storage, and computation.

Compressive spectral clustering (CSC) efficiently leverages graph filter and random sampling techniques to speed up clustering process. However, we find that CSC algorithm suffers from two main problems: i) The direct use of the dichotomy and eigencount techniques for estimating laplacian matrix’s k-th eigenvalue is expensive. ii) The computation of polynomial approximation repeats in each iteration for every cluster in the interpolation process, which occupies most of the computation time of CSC. To address these problems, we propose a new approach called FCSC for fast compressive spectral clustering. FCSC addresses the first problem by assuming that the eigenvalues approximately satisfy local uniform distribution, and addresses the second problem by recalculating the pairwise similarity between nodes with low-dimensional representation to reconstruct denoised laplacian matrix. The time complexity of reconstruction is linear with the number of non-zeros in laplacian matrix. As experimentally demonstrated on artificial and real-world datasets, our approach significantly reduces the computation time while preserving high clustering accuracy comparable to previous designs, verifying the effectiveness of FCSC.

Locality Sensitive Hashing (LSH) is a widely used similarity search technique for many web services, such as content-based retrieval services for images and videos. Due to its popularity, much research effort has been devoted to improving the search quality, and the indexing and query performance of LSH. However, most existing variants of LSH can only run on single node, which limits their applicability to large-scale data. In this paper, we present a Shuffle-Efficient Similarity Search scheme based on LSH, which can be efficiently executed in distributed environments, to serve a massive amount of data. In SES-LSH, a shuffle efficient indexing scheme is proposed to reduce the data shuffle when constructing hash tables, and a location-aware querying scheme is proposed to improve the query performance. We have implemented a prototype of SES-LSH based on Spark, and several optimizations have been utilized to improve the fine-grained hash table operations of distributed LSH. Extensive experiments using large-scale real-world datasets show that SES-LSH is remarkably more efficient than existing methods.

Service optimization and energy conservation requires a thorough understanding of the performance impact of different hardware configurations. In this paper we focus on the configuration of memory and investigate the impact of memory dynamic voltage and frequency scaling (DVFS) on the performance of services/applications. We propose a quantitative metric called frequency sensitivity (FS) and study memory FS of various benchmarks. Our experiments yield several insights for memory DVFS based performance tuning.

Flow completion times (FCTs) are critical for many cloud applications. To minimize the average FCT, recent transport designs, such as pFabric, PASE, and PIAS, approximate the Shortest Remaining Time First (SRTF) scheduling. A common, implicit assumption of these solutions is that the remaining time is only determined by the remaining flow size. However, this assumption does not hold in many real-world scenarios where applications generate data at diverse rates that are smaller than the network capacity. In this paper, we look into this issue from system perspective and find that the operating system (OS) kernel can be exploited to better estimate the remaining time of a flow. In particular, we use the rate of copying data from user space to kernel space to measure the data generation rate. We design RAX, a rate aware flow scheduling method, that calculates the remaining time of a flow more accurately, based on not only the flow size but also the data generation rate. We have implemented a RAX prototype in Linux kernel and evaluated it through testbed experiments and ns-2 simulations. Our testbed results show that RAX reduces FCT by up to 14.9%/41.8% and 7.8%/22.9% over DCTCP and PIAS for all/medium flows respectively.

RAM-based storage aggregates the RAM of servers in data center networks (DCN) to provide extremely high storage performance. For quick recovery of storage server failures, Mem-Cube [1] exploits the proximity of the BCube network to limit the recovery traffic to the recovery servers' 1-hop neighborhood. However, previous design is applicable only to BCube, and has suboptimal recovery performance due to congestion and contention. To address these problems, in this paper we propose CubeX, which generalizes the “1-hop” principle of MemCube for all cube-based networks, and improves the throughput and recovery performance of RAM-based key-value (KV) store via cross-layer optimizations. At the core of CubeX is to leverage the glocality (= globality + locality) of cube-based networks: it scatters backup data across a large number of disks globally distributed throughout the cube, and restricts all recovery traffic within the small local range of each server node. Our evaluation shows that CubeX efficiently supports RAM-based KV store for cube-based networks, and CubeX remarkably outperforms MemCube in both throughput and recovery time.

Summary The proliferation of Internet applications, cloud systems, and mobile social networks results in unprecedented data set scale and high data generation rate. For us to be able to extract any meaningful information, it is important to achieve real‐time online data analytics. Skyline queries are important in many online data applications such as real‐time Web mining, multipreference analysis, and decision making. Most existing studies mainly focus on centralized systems, and distributed skyline query processing is still an emerging and challenging topic. In this paper, we propose SkyStorm, a delay‐bounded parallel skyline computing approach for large‐scale real‐time data analytics by dividing the search into multiple rounds and limiting the search in each round within a budget‐restricted range. The effectiveness of our proposals is demonstrated through analysis and simulations.

In-memory storage has the benefits of low I/O latency and high I/O throughput. Fast failure recovery is crucial for large-scale in-memory storage systems, bringing network-related challenges, including false detection due to transient network problems, traffic congestion during the recovery, and top-of-rack switch failures. In order to achieve fast failure recovery, in this paper, we present CubicRing, a distributed structure for cube-based networks, which exploits network proximity to restrict failure detection and recovery within the smallest possible one-hop range. We leverage the CubicRing structure to address the aforementioned challenges and design a network-aware in-memory key-value store called MemCube. In a 64-node 10GbE testbed, MemCube recovers 48 GB of data for a single server failure in 3.1 s. The 14 recovery servers achieve 123.9 Gb/s aggregate recovery throughput, which is 88.5% of the ideal aggregate bandwidth and several times faster than RAMCloud with the same configurations.

This paper studies the communication pattern of data-parallel applications from the perspective of job execution, and discovers multiple inter-coflow dependencies. These inter-coflow dependencies, collectively named as semantic flow (seflow), can expose job-level semantics. It is observed that most distributed computing frameworks describe their job execution as directed acyclic graphs (DAG). So a seflow comprises not only all the coflows of a job but also the DAG-based relationship between them. Seflow, coflow and flow can be viewed as the top-down abstractions for communication of jobs.

This paper presents SmartPartition, an efficient approach to partition large-scala natural graphs [5]. We design a new partitioning algorithm which can perceive graph layout locality to improve the performance of graph computation. Experimental results demonstrate that SmartPartition can achieve significant reduction in ingress time and execution time for both real-world and synthetic graph datasets.

The design of maintenance mechanisms ofdistributed hash tables (DHTs) is usually specific totheir initial graphs, and thus it is complicated anderror-prone. Zhang and Liu propose in [4] the "distributedline graphs" (DLG) mechanism, a universaltechnique for designing DHTs based on arbitraryregular graphs while preserving the main features ofthe initial graphs. However, two important propertiesof DLG, the expandability and fidelity, have notbeen studied with detailed explanations or analysis.In this paper, we study the above two properties ofDLG transformations, and prove that (i) the DLGtransformations are incrementally expandable, and(ii) the DLG transformations from Gi to Gi+1 keepfidelity.

Task-aware flow schedulers collect task information across the data center to optimize task-level performance. However, the majority of the tasks, which generate short flows and are called tiny tasks, have been largely overlooked by current schedulers. The large number of tiny tasks brings significant overhead to the centralized schedulers, while the existing decentralized schedulers are too complex to fit in commodity switches. In this paper we present OPTAS, a lightweight, commodity-switch-compatible scheduling solution that efficiently monitors and schedules flows for tiny tasks with low overhead. OPTAS monitors system calls and buffer footprints to recognize the tiny tasks, and assigns them with higher priorities than larger ones. The tiny tasks are then transferred in a FIFO manner by adjusting two attributes, namely, the window size and round trip time, of TCP. We have implemented OPTAS as a Linux kernel module, and experiments on our 37-server testbed show that OPTAS is at least 2.2× faster than fair sharing, and 1.2× faster than only assigning tiny tasks with the highest priority.

The tasks of data-parallel computation jobs come up with diverse and time-varying resource requirements. The dynamic nature of task requirements brings challenges on making good scheduling decisions, due to it is hard to keep work-conserving. In this paper, we present BETS to cope with the requirement dynamics that aims at utilizing cluster resources fully. BETS employs a task model that represents for runtime task requirements, a coarse-grained task pipeline to make use of resources in a time-division multiplexing fashion, and fine-grained resource management to guarantee performance.

Internet-based virtual computing environment (iVCE) has been proposed to combine data centers and other kinds of computing resources on the Internet to provide efficient and economical services. Virtual machines (VMs) have been widely used in iVCE to isolate different users/jobs and ensure trustworthiness, but traditionally VMs require a long period of time for booting, which cannot meet the requirement of iVCE’s large-scale and highly dynamic applications. To address this problem, in this paper we design and implement VirtMan, a fast booting system for a large number of virtual machines in iVCE. VirtMan uses the Linux Small Computer System Interface (SCSI) target to remotely mount to the source image in a scalable hierarchy, and leverages the homogeneity of a set of VMs to transfer only necessary image data at runtime. We have implemented VirtMan both as a standalone system and for OpenStack. In our 100-server testbed, VirtMan boots up 1000 VMs (with a 15 GB image of Windows Server 2008) on 100 physical servers in less than 120 s, which is three orders of magnitude lower than current public clouds.

Data clustering is usually time-consuming since it by default needs to iteratively aggregate and process large volume of data. Approximate aggregation based on sample provides fast and quality ensured results. In this paper, we propose to leverage approximation techniques to data clustering to obtain the trade-off between clustering efficiency and result quality, along with online accuracy estimation. The proposed method is based on the bootstrap trials. We implemented this method as an Intelligent Bootstrap Library (IBL) on Spark to support efficient data clustering. Intensive evaluations show that IBL can provide a 2x speed-up over the state of art solution with the same error bound.

With the help of simulation tools, users can evaluate new proposals in cluster environment efficiently. However, current cloud simulators cannot meet the needs of application-driven simulation scenarios. In this paper, we propose Pallas, a task and network simulation framework that supports various cloud applications. Task-aware network scheduling and network-perceived task placement algorithms can be easily implemented in Pallas. We present the architecture and main components of Pallas and evaluate its effectiveness by comparing algorithm improvements to the actual results.

Data-parallel computing frameworks (DCF) such as MapReduce, Spark, and Dryad etc. Have tremendous applications in big data and cloud computing, and throw tons of flows into data center networks. In this paper, we design and implement FLOW PROPHET, a general framework to predict traffic flows for DCFs. To this end, we analyze and summarize the common features of popular DCFs, and gain a key insight: since application logic in DCFs is naturally expressed by directed acyclic graphs (DAG), DAG contains necessary time and data dependencies for accurate flow prediction. Based on the insight, FLOW PROPHET extracts DAGs from user applications, and uses the time and data dependencies to calculate flow information 4-tuple, (source, destination, flow size, establish time), ahead-of-time for all flows. We also provide generic programming interface to FLOW PROPHET, so that current and future DCFs can deploy FLOW PROPHET readily. We implement FLOW PROPHET on both Spark and Hadoop, and perform extensive evaluations on a testbed with 37 physical servers. Our implementation and experiments demonstrate that, with time in advance and minimal cost, FLOW PROPHET can achieve almost 100% accuracy in source, destination, and flow size predictions. With accurate prediction from FLOW PROPHET, the job completion time of a Hadoop TeraSort benchmark is reduced by 12.52% on our cluster with a simple network scheduler.

In the data flow models of today's data center applications such as MapReduce, Spark and Dryad, multiple flows can comprise a coflow group semantically. Only completing all flows in a coflow is meaningful to an application. To optimize application performance, routing and scheduling must be jointly considered at the level of a coflow rather than individual flows. However, prior solutions have significant limitation: they only consider scheduling, which is insufficient. To this end, we present Rapier, a coflow-aware network optimization framework that seamlessly integrates routing and scheduling for better application performance. Using a small-scale testbed implementation and large-scale simulations, we demonstrate that Rapier significantly reduces the average coflow completion time (CCT) by up to 79.30% compared to the state-of-the-art scheduling-only solution, and it is readily implementable with existing commodity switches.

Most proposed DHTs engage certain topology maintenance mechanisms specific to the static graphs on which they are based. The designs of these mechanisms are complicated and repeated with graph-relevant concerns. In this paper, we propose the “distributed line graphs” (DLG), a universal technique for designing DHTs based on arbitrary regular graphs. Using DLG, the main features of the initial graphs are preserved, and thus people can design a new DHT by simply choosing the graph with desirable features and applying DLG to it. We demonstrate the power of DLG by illustrating four DLG-enabled DHTs based on different graphs, namely, Kautz, de Bruijn, butterfly, and hypertree graphs. The effectiveness of our proposals is demonstrated through analysis, simulation, and implementation.

Abstract Distributed Hash Tables (DHTs) are scalable, self‐organizing, and adaptive to underlying topology changes, thus being a promising infrastructure for hosting large‐scale distributed applications. The ever‐wider use of DHT infrastructures has found more and more applications that require support for range queries. Recently, a number of DHT‐based range query schemes have been proposed. However, most of them suffer from high query delay or imbalanced load distribution. To address these problems, in this paper we first present an efficient indexing structure called Balanced Kautz (BK) tree that uniformly maps them‐dimensional data space onto DHT nodes, and then propose a BK tree‐based range query scheme called ERQ that processes range queries in a parallel fashion and guarantees to return the results in a bounded delay. In a DHT withNnodes, ERQ can answer any range of query in less thanrmlog N(2loglog N+ 1) hops in a load‐balanced manner, irrespective of the queried range, the whole space size, or the number of queried attributes. The effectiveness of our proposals is demonstrated through experiments. Copyright © 2010 John Wiley & Sons, Ltd.

DHTs are scalable, self-organizing, and adaptive to underlying topology changes, thus being a promising infrastructure for realizing autonomic communications in distributed systems. To provide the above advantages, however, DHTs sacrifice flexibility, that is, all messages are routed by using a common algorithm in a DHT on the assumption that all participant nodes are homogeneous. In practice, nodes in large-scale systems might be heterogeneous with respect to their capabilities, reputations, affiliations of administrative domains, and so on, which consequently makes it preferable to distinguish the heterogeneity of participant nodes and enable flexible control of routing destinations and paths. To achieve this, in this paper we propose a novel approach that supports organizing nodes into groups and enables routing control in a DHT. The effectiveness of our proposals is demonstrated through theoretical analysis and extensive simulations.

DHTs are scalable, self-organizing, and adaptive to underlying topology changes, thus being a promising infrastructure for realizing efficient Web service discovery. Range queries play an important role in service discovery, and in recent years a number of DHT-based range query schemes have been proposed. However, most of them suffer from high query delay and high processing cost. This paper presents ERQ, an Efficient scheme for delay bounded Range Query processing over DHTs. We first emulate the PHT structure and design a balanced Kautz (BK) tree to uniformly map the m-dimensional data space onto DHT nodes, and then present a novel algorithm that processes range queries in a parallel fashion, where an on-the-fly space pruning mechanism is adopted to reduce the processing cost. In a DHT with N nodes, ERQ can answer any range query in less than logN (2loglogN+1) hops with low processing cost, irrespective of the queried range, the whole space size, or the number of queried attributes. The effectiveness of ERQ is demonstrated through extensive experiments.

Most proposed DHTs have their unique maintenance mechanisms specific to the static graphs on which they are based. In this paper we propose distributed line graphs (DLG), a universal framework for building DHTs based on arbitrary constant-degree graphs. We prove that in a DLG-enabled, N-node DHT, the out-degree is d, the in-degree is between 1 and 2d, and the diameter is less than 2(logdN-logdN0+D0+1), where d, D0and N0represent the degree, diameter and number of nodes of the initial graph, respectively. The maintenance cost of DLG-enabled DHTs is O(logdN). We show the power of DLG technique by applying it to Kautz graphs to propose a new DHT scheme.

In most DHTs proposed so far, all nodes are assumed to be homogeneous, and all messages are routed using a common algorithm. In practice, however, nodes in large-scale systems might be heterogeneous with respect to their capabilities, reputations, affiliations of administrative domains, and so on, which consequently makes it preferable to distinguish the heterogeneity of participant nodes. To achieve this, in this paper we present Grouped Tapestry (GTap), a novel Tapestry-based DHT that supports organizing nodes into groups and allows flexible DHT routing. The effectiveness of our proposals is demonstrated through theoretical analysis and extensive simulations.

Searching in large-scale unstructured peer-to-peer networks is challenging due to the lack of effective hint information to guide queries. In this paper, we propose POP, a Parallel, collaborative and Probabilistic search mechanism, in which query messages are viewed as search units to collaborate with each other and aggregate the distributed hints during the search process. A scheme called distributed Bloom filter (DBF) is presented to propagate the hints with a bandwidth-aware manner, in which a node divides the received Bloom filter vector into subvectors and disseminates the fragments to its neighbors according to their bandwidth capacity. The effectiveness of POP is demonstrated through theoretical analysis and extensive simulations.