Distributed key-value stores are widely adopted to support elastic big data applications, leveraging purpose-built consensus algorithms like Raft to ensure data consistency. However, through systematic analysis, we reveal a critical performance issue in such consistent stores, i.e., overlapping persistence operations between consensus protocols and underlying storage engines result in significant I/O overhead. To address this issue, we present Nezha, a prototype distributed storage system that innovatively integrates key-value separation with Raft to provide scalable throughput in a strong consistency guarantee. Nezha redesigns the persistence strategy at the operation level and incorporates leveled garbage collection, significantly improving read and write performance while preserving Raft's safety properties. Experimental results demonstrate that, on average, Nezha achieves throughput improvements of 460.2%, 12.5%, and 72.6% for put, get, and scan operations, respectively.

Data deduplication eliminates redundant data in backup systems by replacing duplicate chunks with compact references and consolidating unique chunks into larger containers. While effective, this process introduces fragmentation that degrades restore performance. Rewriting techniques mitigate fragmentation by identifying sparse containers (i.e., those referenced by the fewest chunks) and rewriting dependent duplicates. Recent work further integrates delta compression to exploit redundancy among similar but non-duplicate chunks. However, this hybrid approach introduces two challenges for rewriting: (1) prohibitive computational overhead from weak-hash-based sketching required for similarity detection, and (2) dynamic reference conflicts arising from multiple candidate base chunks during sparse container identification. In this paper, we propose Hybrid-Rewrite, a rewriting framework for backup systems that combine deduplication and delta compression. Hybrid-Rewrite integrates two techniques to address these challenges: (1) sketch echoing, which stores chunk sketches in containers and retrieves them via metadata prefetching during deduplication, thus eliminating redundant sketch computations for duplicate chunks, and (2) greedy reference locking, which iteratively detects containers with the most referenced chunks by aggregating all possible references and invalidates conflicting references, thereby isolating the sparse containers. Experimental results demonstrate that, compared to direct extensions of existing rewriting methods to hybrid systems, Hybrid-Rewrite achieves$\mathbf{1. 4 2}$to 1.8x higher compression ratios and up to 1.81x faster restore performance. Additionally, sketch echoing reduces sketch computation by$\mathbf{5 8. 1 5 \%}$to$\mathbf{9 6. 9 5 \%}$.

In multi-domain deployment scenarios, leader-based distributed systems face high latency challenges when processing cross-domain requests. To address this challenge, we propose a novel, network-topology-aware dynamic leader scheduling mechanism. This mechanism utilizes a system model to dynamically evaluate the system latency when the leader is located in different domains, incorporating real-time state information such as network latency, node distribution, and geographic workload distribution. Based on the evaluation results, the mechanism schedules the leader to the optimal domain to minimize latency. Experimental results indicate that it can effectively reduce system latency and improve system Quality of Service (QoS).

Logic bugs can cause DBMSs to silently produce incorrect results for a given query, posing significant threats to software reliability and remaining challenging to detect. Join is a fundamental operation in DBMSs, enabling the combination of data from multiple tables; however, due to its complexity, it is also susceptible to logic bugs. Existing works detect logic bugs in join optimizations by altering query hints and system variables to alter the optimizer's choice of execution plans. However, these approaches struggle to detect logic bugs when query hints or system variables fail to influence the optimizer's behavior, or when the logic bugs reside in join implementation code that is unrelated to optimization. In this paper, we present S et R elation S ynthesis (SRS), a black-box testing approach that detects logic bugs of join implementation in DBMSs by leveraging set relations among different join operations. SRS applies transformations to the original join queries, including modifications to join types, join orders, and join conditions, while ensuring that the outputs of both the original and transformed queries preserve the expected set relations. Violations of these set relations indicate potential logic bugs. We realized SRS and evaluated it on five widely-used and extensively-tested DBMSs: MySQL, MariaDB, TiDB, PostgreSQL, and DuckDB. SRS uncovered 33 previously unknown and unique bugs, all of which have been confirmed, with 12 already fixed. Among these, 33 are logic bugs, demonstrating SRS's effectiveness and practicality in detecting logic bugs in the implementation of join operations within DBMSs.

Delta compression can complement data deduplication by further minimizing redundancy through the compression of non-duplicate data chunks. When adding delta compression to deduplication-based backup systems, however, two primary challenges arise that degrade performance of inline deduplication. First, extra I/Os are introduced along the critical paths of backup and restoration for retrieving base chunks, slowing the system. Second, rewriting techniques prohibit specific data chunks from serving as base chunks for delta compression to improve restore performance, resulting in a loss of compression efficiency. In this paper, we introduce LoopDelta, a framework that seamlessly integrates delta compression into inline deduplication for backup storage, addressing the aforementioned challenges by using three techniques: (1) dual-locality-based similarity tracking leverages both logical and physical locality to detect most of the similar chunks, which, due to their locality, can be prefetched by piggybacking on routine operations during deduplication, thereby eliminating extra I/Os during backup; (2) cache-aware filter identifies base chunks requiring extra I/Os during restore and prevents their referencing, thus eliminating extra restore I/Os; and (3) inversed delta compression, which reverses the roles of base and target chunks in the traditional delta compression approach, thereby allowing for the delta compression of data chunks that are otherwise prohibited as base chunks due to rewriting techniques. Experiments show that LoopDelta increases the compression ratio by 1.28 to 11.33 times over basic deduplication, without significantly affecting backup throughput, and enhances restore performance by up to 3.57 times.

High-performance serverless computing has garnered significant attention. Researchers have developed numerous optimization strategies for serverless frameworks to fully leverage the benefits of serverless computing. However, they often overlook the architectural heterogeneity of various serverless frameworks, leading to performance discrepancies. We designs SwitchFlow by analyzing and characterizing the performance of different serverless frameworks. The core idea is to utilize the time series characteristics of scientific workflows to predict upcoming functions, thereby switching them to the optimal framework for execution. Furthermore, SwitchFlow’s unique design concept enables integration with existing optimization strategies. Experimental results demonstrate that SwitchFlow can effectively reduce overall workflow execution time, optimize resource efficiency, and enhance service availability compared to running on a single serverless framework.

Counting triangles in large graphs, being a crucial problem in graph computing, has attracted significant attention from research communities. There is a large body of work dedicated to algorithmic design and efficient implementation on parallel platforms such as GPUs. Among them, the intersection-based triangle counting algorithm is found to be the most efficient approach and a few GPU implementations have been proposed following this algorithm. However, there remains a gap in understanding how these algorithms perform when confronted with diverse real-world graph datasets. It is a well-established fact that the performance of GPU code is heavily influenced by data characteristics, including graph size and node degree, often leading to issues such as workload imbalances and inefficient memory access. The goal of this study is to systematically evaluate the performance and analyze the behavior of eight recently published intersection-based triangle counting implementations. For that, we developed a unified testing framework that facilitates fast performance assessment of any triangle counting algorithm. Our experiments show that the TRUST algorithm outperforms competitors in most cases. To our surprise, the Polak algorithm, with a simple design, has displayed commendable performance across the board. Notably, it even surpasses the TRUST algorithm when processing small datasets. We conducted an in-depth analysis on the resource consumption patterns of these implementations in relation to their performance and identified key factors that contributed to their behaviors. Based on insights gained from such analysis, we proposed a novel algorithm named GroupTC that delivers outstanding performance under all types of datasets.

Large Language Models (LLMs) have shown their superior capability in natural language processing, promoting extensive LLM-powered applications to be the new portals for people to access various content on the Internet. However, LLM-powered applications do not have sufficient security considerations on untrusted content, leading to potential threats. In this paper, we reveal content poisoning, where attackers can tailor attack content that appears benign to humans but causes LLM-powered applications to generate malicious responses. To highlight the impact of content poisoning and inspire the development of effective defenses, we systematically analyze the attack, focusing on the attack modes in various content, exploitable design features of LLM application frameworks, and the generation of attack content. We carry out a comprehensive evaluation on five LLMs, where content poisoning achieves an average attack success rate of 89.60%. Additionally, we assess content poisoning on four popular LLM-powered applications, achieving the attack on 72.00% of the content. Our experimental results also show that existing defenses are ineffective against content poisoning. Finally, we discuss potential mitigations for LLM application frameworks to counter content poisoning.

Graph Neural Networks (GNNs) have been increasingly adopted for graph analysis in web applications such as social networks. Yet, efficient GNN serving remains a critical challenge due to high workload fluctuations and intricate GNN operations. Serverless computing, thanks to its flexibility and agility, offers on-demand serving of GNN inference requests. Alas, the request-centric serverless model is still too coarse-grained to avoid resource waste.

Abstract As cloud native technology advances, the scale and complexity of applications built on microservice architecture continue to expand, leading to increasingly intricate differences between software within the same application. Microservice applications, offering high flexibility, are deployed in data centers as black boxes from the users' perspective, leaving them with no insight into the orchestration of cloud service providers. Consequently, users face challenges in promptly recognizing performance imbalances within their deployed applications. Meanwhile, cloud service providers may cut costs by offering a mix of qualified and unqualified services, potentially deceiving users. To enhance the understanding of microservice application organization, we propose a non‐intrusive measurement framework, termed NMPI. NMPI facilitates rapid identification of microservice application defects, offering insights into cloud services and detecting fraudulent behavior in microservice‐based applications. We model microservice applications using a queue analysis‐based approach and filter the dominant frequency components of average response time signals by employing k‐means on the fast fourier transform (FFT). Our model constructs a library of performance portraits for various software, with these portraits resembling human fingerprints that carry and mark the software's internal information. Utilizing a two‐tier microservices‐based application incorporating a database as a case study allows us to demonstrate the effectiveness of NMPI. Our experimental results show that NMPI can produce differentiable profiles of data service performance portraits across a diverse and extensive range of workloads, enabling the identification of software types and the analysis of performance conditions.

Carbon neutrality is a growing important objective for human activities, to prevent climate change. As for computer systems, we are urged to provide sustainability in computing to help mitigate such problems. As such, carbon neutrality shall occupy a critical role in the next-generation digital infrastructure. To this end, we have collected 15 established works towards carbon neutrality in computer systems in the Special Issue on Carbon-Neutral Computing for Next-Generation Digital Infrastructures.

The natural bijection between a proposed circuit design and its graph representation shall allow any graph optimization algorithm deploying into many-core systems efficiently. However, this process suffers from the exponentially growing overhead and heavy memory footprint with the signal propagation. To conquer the unique challenge, we systematically study the simulation with millions of gates, and identify that the processing complexity could grow exponentially from the signal inputs, the skewness of the computational graph stays. Thus, we present ZhouBi, a fast and scalable gate-level simulation framework to fully exploit the parallelism from many-core systems. ZhouBi contributes in threefolds, (I) a graph representation that colors gate-level netlists and identifies skew partitions based on the graph skewness; (II) A set of heuristic algorithms that picks opportunistic and conservative algorithms to accelerate the simulation; (III) A system facility that supports selective mapping between simulation and many-core, providing a tradeoff between the risk of concurrent simulation fail and performance gain. We have prototyped ZhouBi and evaluated it with practical baselines. ZhouBi can achieve a 27.6× performance gain, as compared to the state-of-the-practice Veriwell without compromising any correctness. Our framework supports large graphs enabling scale-out gate-level simulations for chip design.

Abstract Re-ranking is to refine the candidate ranking list of recommended items, such that the re-ranked list attracts users to purchase or click more items than the candidate one without re-ranking. Items in the candidate list are often ranked by their relevance to users’ interests. It is thus important to exploit the mutual influence between items in the re-ranking process. Existing re-ranking models focus on only the pairwise influence between two items, and have limited capability to exploit the local mutual influence in a group of items. Users often show successive interests on a group of relevant items, e.g., mobile phone, phone covers, wireless headset, namely scene. We propose a novel re-ranking model that jointly exploits the local mutual influence in scenes and the global mutual influence between different scenes. Scene representations are learned by GNN and multi-head attention, where GNN aims to learn local mutual influence while multi-head attention is to learn global mutual influence. To study the interaction between users and scenes, matrix factorization on users is utilized to obtain the user preference, which can be further applied to scenes to compute the scene scores. The final re-ranking list is generated by sorting the predicted scores of all scenes. To further mine user history information and item related user information, we also develop the extension pretraining module which relies on mask mechanism to support users and items high-quality embedding generation. We conduct a comprehensive evaluation on several real-world datasets. The experimental results demonstrate that our model substantially outperforms existing approaches.

The Raft algorithm maintains strong consistency across data replicas in Cloud. This algorithm places nodes, i.e., leader and follower, to serve read/write requests spanning geo-diverse sites. As the workload increases, Raft shall provide proportional scale-out performance. However, traditional scale-out techniques are bottlenecked in Raft with an exponentially increased performance penalty when provisioned sites exhaust local resources. To provide scalability in Raft, this paper presents a cost-effective mechanism that enables elastic auto scaling in Raft, called BW-Raft. BW-Raft extends the original Raft with the following abstractions: (1)secretarynodes that take over expensive log synchronization operations from the leader, relaxing the performance constraint on locks. (2)observernodes that handle reads only, improving throughput for typical data intensive services. These abstractions are stateless, allowing elastic scale-out on unreliable yet cheap spot instances. In theory, we prove that BW-Raft can preserve the strong consistency guarantee from Raft at scale-out, handling 50X more nodes, compared to the original Raft. We have prototyped the BW-Raft on key-value services and evaluated it with many state-of-the-arts on Amazon EC2 and Alibaba Cloud. Our results show that within the same budget, BW-Raft incurs 5-7X less resource footprint increment than Multi-Raft. Using spot instances, BW-Raft can reduces costs by 84.5%, compared to Multi-Raft. In the real world experiments, BW-Raft improves goodput of the 95th-percentile SLO by 9X, thus, serves an alternative for distributed service scaling out with strong consistency.

Unsupervised deep learning has recently demonstrated the promise of producing high-quality samples. While it has tremendous potential to promote the image colorization task, the performance is limited owing to the high-dimension of data manifold and model capability. This study presents a novel scheme that exploits the score-based generative model in wavelet domain to address the issues. By taking advantage of the multi-scale and multi-channel representation via wavelet transform, the proposed model learns the richer priors from stacked coarse and detailed wavelet coefficient components jointly and effectively. This strategy also reduces the dimension of the original manifold and alleviates the curse of dimensionality, which is beneficial for estimation and sampling. Moreover, dual consistency terms in the wavelet domain, namely data-consistency and structure-consistency are devised to leverage colorization task better. Specifically, in the training phase, a set of multi-channel tensors consisting of wavelet coefficients is used as the input to train the network with denoising score matching. In the inference phase, samples are iteratively generated via annealed Langevin dynamics with data and structure consistencies. Experiments demonstrated remarkable improvements of the proposed method on both generation and colorization quality, particularly in colorization robustness and diversity.

Sharing data and computation among concurrent queries has been an active research topic in database systems. While work in this area developed algorithms and systems that are shown to be effective, there is a lack of logical foundation for query processing and optimization. In this paper, we present PsiDB, a system model for processing a large number of database queries in a batch. The key idea is to generate a single query expression that returns a global relation containing all the data needed for individual queries. For that, we propose the use of a type of relational operators called ψ-operators in combining the individual queries into the global expression. We tackle the algebraic optimization problem in PsiDB by developing equivalence rules to transform concurrent queries with the purpose of revealing query optimization opportunities. Centering around the ψ-operator, our rules not only cover many optimization techniques adopted in existing batch processing systems, but also revealed new optimization opportunities. Experiments conducted on an early prototype of PsiDB show a performance improvement of up to 36X over a mainstream commercial DBMS.

Due to the high level of parallelism, there are unique challenges in developing system software on massively parallel hardware such as GPUs. One such challenge is designing a dynamic memory allocator whose task is to allocate memory chunks to requesting threads at runtime. State-of-the-art GPU memory allocators maintain a global data structure holding metadata to facilitate allocation/deallocation. However, the centralized data structure can easily become a bottleneck in a massively parallel system. In this paper, we present a novel approach for designing dynamic memory allocation without a centralized data structure. The core idea is to let threads follow a random search procedure to locate free pages. Then we further extend to more advanced designs and algorithms that can achieve an order of magnitude improvement over the basic idea. We present mathematical proofs to demonstrate that (1) the basic random search design achieves asymptotically lower latency than the traditional queue-based design and (2) the advanced designs achieve significant improvement over the basic idea. Extensive experiments show consistency to our mathematical models and demonstrate that our solutions can achieve up to two orders of magnitude improvement in latency over the best-known existing solutions.

Embedded operating systems (Embedded OSs) are extensively deployed in many mission-critical industrial scenarios. Any defects within these systems may result in unacceptable losses. Therefore, it is imperative to develop tools to detect bugs within Embedded OSs, thus minimizing potential impacts on industrial infrastructures. Coverage-guided fuzzing is a vulnerability detection technique that has found numerous real-world vulnerabilities within both application programs as well as kernels. However, state-of-the-art kernel fuzzers, e.g., Syzkaller, mainly target general purpose-operating systems, such as Linux, macOS, and Windows, whereas Embedded OSs support is mostly lacking. In this article, we propose Tardis, the first Embedded OSs fuzzer capable of testing a wide selection of Embedded OSs while leveraging coverage feedback. Tardis conducts OS-agnostic code coverage collection and analysis, allowing developers and testers to test a wide range of Embedded OSs without significant manual efforts. We implemented and evaluated Tardis on several well-known Embedded OSs, such as UC/OS and FreeRTOS. Tardis can successfully perform fuzz testing on these kernels without significant manual effort for adaptation. By leveraging coverage feedback, Tardis can cover 51.32% more branches than black-box fuzzing on average on the respective Embedded OSs over 24 h. Tardis also found 17 previously unknown bugs among the target Embedded OSs.

Industrial control system (ICS) employs complex multistate protocols to realize high-reliability communication and intelligent control over automation equipment. ICS has been widely used in various embedded fields, such as autonomous vehicle systems, power automation systems, etc. However, in recent years, many attacks have been performed on ICS, especially its protocols, such as the hijacks over Jeep Uconnect and Tesla Autopilot autonomous systems, also the Stuxnet and DragonFly viruses over national infrastructures. It is important to guarantee the security of ICS protocols. In this article, we presentCharon, an efficient fuzzing platform for the vulnerability detection of ICS protocol implementations. InCharon, we propose an innovative fuzzing strategy that leverages state guidance to maximize cross-state code coverage instead of focusing on isolated states during the fuzzing of ICS protocols. Moreover, we devise a novel feedback collection method that employs program status inferring to avoid the restart of the ICS protocol at each iteration, allowing for continuous fuzzing. We evaluateCharonon several popular ICS protocol implementations, including real-time publish subscribe, IEC61850-MMS, MQTT, etc. Compared with typical fuzzers, such as American fuzzy lop, Polar, AFLNET, Boofuzz, and Peach, it averagely improves branch coverage by 234.2%, 194.4%, 215.9%, 52.58%, and 35.18%, respectively. Moreover, it has already confirmed 21 previously unknown vulnerabilities (e.g., stack buffer overflow) among these ICS protocols, most of which are security critical and corresponding patches from vendors have been released accordingly.

Cloud service providers promote their new field programmable gate array (FPGA) infrastructure as a service (IaaS) as the new era of cloud product. This FPGA IaaS wraps virtualized compute resources with FPGA boards, e.g., Amazon AWS F1, and reserves acceleration capability for specific applications. Though this acceleration technique sounds promising, questions like real world performance, best-fit scenarios, portability, etc., still need further clarification. In this article, we present one of the first few empirical studies that take a close look at FPGA clouds from the tenants’ perspective. We have conducted measurement studies on Amazon AWS, Alibaba, and Huawei clouds for over one year. The experimental results show that: (1) Tenants experience severe performance-cost imbalance on FPGA IaaS platforms; (2) The inter-communication performance in FPGA clouds is tightly constrained by hardware drivers, e.g., small optimization of DMA drivers for PCIe can harvest significant performance gain; (3) The virtualized FPGA clouds are far from mature, e.g., small-sized jobs can greatly degrade the performance of FPGA clouds due to underutilized PCIe bandwidth. Our study not only provides useful hints to help tenants with FPGA service selection, but also sheds some lights for cloud providers to improve the performance of FPGA clouds.

Battery service time is a critical constraint on the availability and functionality of mobile devices. Equipping larger batteries may mitigate such deficiency yet it raises the challenges on thermal limit and physical size. Changing the battery chemistry is another solution, which however usually benefits the energy efficiency of only part of the applications, depending on their software behaviors. To address the challenges of battery energy efficiency and heat dissipation in limited physical space, we propose CAPMAN, a management framework that jointly optimizes thecooling andactivepowermanagement in a smartphone, a typical mobile device, equipped with a hybrid battery pack. We establish the framework with three components. First, we abstract the correlation among the batteries, devices and software into a finite state machine model, whose state transitions can be triggered by actions like system calls and user activities. Second, we propose a battery scheduling algorithm that determines the more suitable battery for cooling/active power use, with respect to the dynamic software behaviors and their impact on the hardware states, based on a Markov decision process (MDP). Third, we design a facility for joint cooling and active power management by coordinating TECs and batteries. With the three major designs, CAPMAN realizes software defined management that schedules heterogeneous batteries and TEC cooling in a timely manner. In addition, CAPMAN provides an online algorithm with a proved O(1.05)-competitiveness performance. With a pair of big.LITTLE batteries, we prototype CAPMAN on multiple popular smartphones and a PYNQ development board. The evaluation with real-world workloads shows that compared to the current mainstream, CAPMAN can achieve 114 percent longer battery service time under skewed loads; compared to the state-of-the-practice baselines, CAPMAN shows 55 percent performance gain and 53 percent less energy use on average. Those results approve that big.LITTLE batteries with sophisticated software defined management is an effective way to prolong the battery service times on mobile devices.

Abstract Cloud markets advocate powerful instances to take computation over from the cyber‐physical system (CPS). Combining the Cloud and CPS layer, the whole Cloud–CPS framework is designed to achieve both accurate data sensing and fast data analysis. While most researchers trust the computation side, and focus on the actuator in the physical space to ensure the service‐level objectives, SLO, that is, deadline misses, cloud can be a threat to the service sustainability as instance may fail, especially when one tries to make a cost‐effective design. Specifically, users must bear the risk of instance failure. These risks can cause the entire cyber‐physical system to collapse. Our work tackles the cloud aspect of the sustainability challenge from the cloud side in a cloud–CPS framework. We have studied the instance selection problem for the CPS systems, and propose a Cost‐Risk Analysis for Instance Recommendation, or CRAIR, to support a sustainable Cloud–CPS framework. We have adopted the classic risk analysis process from the portfolio management in hedge financial market, combining with the system modeling for the CPS instance selection, as an optimization problem. To solve this problem, we formulate it as a multi‐armed bandit problem and solve it with our upper confidence bound bandit algorithm together, our CRAIR can provide an online risk analysis to maximize the profit with a comparative ratio of O(1+ ). We have evaluated CRAIR based on simulations using real‐world Google and Alibaba workloads and cloud market numbers. The results show that, compared to traditional approaches, our approach provides the best tradeoff between SLOs and costs. All users achieve their SLOs goals while minimizing their average expenses by 34.6%. By using CRAIR for instance selection, the CPS service can maximize its benefit under a controlled risk.

Modern smartphone is far from being ubiquitous due to limited energy capacity. Recent research suggests that heterogeneous batteries may expose power saving opportunities that fit dynamic software patterns. Yet it is still a challenge on thermal and power management for a hybrid battery pack in a smartphone. To address this challenge, we propose a system framework, called CAPMAN , which supports joint optimization of cooling and active power management in smartphones. The framework consists of three major techniques: 1) A Markov decision process (MDP) technique that models battery types, and cooling/active power use from state and action nodes; 2) A structural similarity approximation that speeds up the convergence of MDP computation, providing battery scheduling decisions; 3) A TEC and battery management facility to realize the cooling and active power management. In addition, CAPMAN provides an online algorithm with a proved worst-case ${\mathbf{O}}\left( {\frac{1}{{1 - \rho }}} \right)$-competitiveness performance, whereρis the factor of discount. We have prototyped CAPMAN with popular smartphones and heterogeneous batteries, and evaluated them with real-world workloads. Results show that CAPMAN can achieve 114% longer service time under skewed loads, compared to the original phone. Compared to the state-of-the-practice baselines, CAPMAN shows 55% performance gain and 53% less energy use on average. As such, CAPMAN approves that big.LITTLE batteries with a careful system design is an effective way to prolong smartphone service times.

The top-k dominating (TKD) query on skyline groups returns k skyline groups that dominate the maximum number of points in a given data set. The TKD query combines the advantages of skyline groups and top-k dominating queries, thus has been frequently used in decision making, recommendation systems, and quantitative economics. Traditional skylines are inadequate to answer queries from both individual and groups of points. The group size could be too large to be processed in a reasonable time as a single operator (i.e., the skyline group operator). In this paper, we address the performance problem of grouping for TKD queries in skyline database. We formulate the problem of grouping, define the group operator in skyline, and propose several efficient algorithms to find top-k skyline groups. Thus, we provide a systematic study of TKD queries on skyline groups and validate our algorithms with extensive empirical results on synthetic and realworld data.

While work in Techniques based on sharing data and computation among queries developed algorithms and systems that are shown to be effective, there is a lack of logical foundation for query processing and optimization. In this paper, we present PsiDB, a system model for processing a large number of database queries in a batch. The key idea is to generate a single query expression that returns a global relation containing all the data needed for individual queries. For that, we propose the use of a type of relational operators called ψ-operators in combining the individual queries into the global expression. We tackle the algebraic optimization problem in PsiDB by developing equivalence rules to transform concurrent queries with the purpose of revealing query optimization opportunities. Experiments conducted on an early prototype of PsiDB show a major performance improvement over a mainstream commercial DBMS.

Raft is a protocol to maintain strong consistency across data replicas in cloud. It is widely used, especially by workloads that span geographically distributed sites. As these workloads grow, Raft's costs should grow, as least proportionally. However, auto scaling approaches for Raft inflate costs by provisioning at all sites when one site exhausts its local resources. This paper presents Geo-Raft, a scale-out mechanism that enables precise auto scaling for Raft. Geo-Raft extends Raft with the following abstractions: (1) secretaries which takes log processing for the leader and (2) observers which process read requests for followers. These abstractions are stateless, allowing for elastic auto scaling, even on unreliable spot instances. Geo-Raft provably preserves strong consistency guarantees provided by Raft. We implemented and evaluated Geo-Raft with multiple auto scaling techniques on Amazon EC2. Geo-Raft scales in resource footprint increments 5-7X smaller than Multi-Raft, the state of the art. Using spot instances, Geo-Raft reduces costs by 84.5% compared to Multi-Raft. Geo-Raft improves goodput of 95th-percentile SLO by 9X.Geo-Raft operates key-value services for 6 months without losing data or crash.

In cloud computing, workloads that lease instances on demand get to execute exclusively for a set time. In contrast, workloads that lease spot instances execute until a competing workload outbids the current lease. Spot instances cost less than on-demand instances, but few workloads can use spot instances because of the variable leasing period. We present BOSS, a framework that uses spot instances to reduce costs for in-memory storage workloads. BOSS uses on-demand instances to create and update objects. It uses spot instances to handle read-only queries. BOSS leases instances from multiple sites and exploits varying prices between the sites. When spot instances stop abruptly at one site, BOSS places newly created objects at other sites, reducing the impact on response time. BOSS proposes a novel, online replication approach (1) avoids placing data at too many sites and (2) provides O(1.5)-competitive ratio under skewed cost distributions. Within a site, BOSS manages the tradeoff between savings and risks from replicating to spot instances. We implemented BOSS on top of Cassandra and deployed it on up to 78 instances across 8 sites in Amazon and Google clouds. With BOSS hosting TPC-W data, we spent $8 per hour on Amazon. For the same service, we spent $55 per hour to use ElastiCache and $49 per hour to use on-demand instances only. BOSS saved 85% and 84% respectively. Further, BOSS achieved 95th percentile response time within 13% of ElastiCache.

Data centers are well known to consume a large amount of energy. As databases are one of the major applications in a data center, building energy-aware database systems has become an active research topic recently. The quantification of the energy cost of database systems is an important task in design. In this paper, we report our recent efforts on this issue, with a focus on the energy cost estimation of query plans during query optimization. We start from building a series of physical models for energy estimation of individual relational operators based on their resource consumption patterns. As the execution of a query plan is a combination of multiple relational operators, we use the physical models as a basis for a comprehensive energy model for the entire query. To address the challenge of maintaining accuracy under system and workload dynamics, we develop an online scheme that dynamically adjusts model parameters based on statistical signal modeling. Our models are implemented in a real database management system and evaluated on a physical test bed. The results show that our solution achieves a high accuracy (worst-case error 13.7 percent) despite noises. Our models also help identify query plans with significantly higher energy efficiency.

Data centers are well known to consume large amounts of energy. Since database is one of the major applications in a typical data center, building energy-aware database systems has become an active research topic recently. The quantification of the energy cost of database systems is an important task in designing such systems. In this paper, we report our recent efforts on this topic, with a focus on the energy cost estimation of query plans during query optimization. We start from building a series of physical models for energy estimation of individual relational operators based on their resource consumption patterns. Since the execution of individual queries is a combination of relational operators, we use the physical models as a basis for a comprehensive energy cost estimation model for entire query plans. To further improve model accuracy under system dynamics and the variations of workload characteristics, we develop an online model estimation scheme that dynamically corrects the static model based on advanced modeling techniques adopted from control engineering. The models are implemented in a real database and evaluated on a physical test bed with a comprehensive set of experimental workloads. The results show that our solution achieves a high accuracy (above 90%) in energy estimation despite noises from the system and workloads.

Energy conservation is a growing important issue in designing modern database management system (DBMS). This requires a deep thinking about the tradeoffs between energy and performance. Despite the significant amount of efforts at the hardware level to make the major components consume less energy, we argue for a revisit of the DBMS query processing mechanism to identify and harvest the potential of energy saving. However, the state-of-art architecture of DBMS does not take energy usage into consideration in its design. A major challenge in developing an energy-aware DBMS is to design and implement a cost-based query optimizer that evaluates query plans by both performance and energy costs. By following such a strategy, our previous work revealed the fact that energy-efficient query plans do not necessarily have the shortest processing time. This demo proposal introduces PET -- an energy-aware query optimization framework that is built as a part of the PostgreSQL kernel. PET, via its power cost estimation module and plan evaluation model, enables the database system to run under a DBA-specified energy/performance tradeoff level. PET contains a power cost estimator that can accurately estimate the power cost of query plans at compile time, and a query evaluation engine that the DBA could configure key PET parameters towards the desired tradeoff. The software to be demonstrated will also include workload engine for producing large quantities of queries and data sets. Our demonstration will show how PET functions via a comprehensive set of views from its graphical user interface named PET Viewer . Through such interfaces, a user can achieve a good understanding of the energy-related query optimization and cost-based plan generation. Users are also allowed to interact with PET to experience the different energy/performance tradeoffs by changing PET and workload parameters at query runtime.

With the total energy consumption of computing systems increasing in a steep rate, much attention has been paid to the design of energy-efficient computing systems and applications. So far, database system design has focused on improving performance of query processing. The objective of this study is to experimentally explore the potential of power conservation in relational database management systems. We hypothesize that, by modifying the query optimizer in a DBMS to take the power cost of query plans into consideration, we will be able to reduce the power usage of database servers and control the tradeoffs between power consumption and system performance. We also identify the sources of such savings by investigating the resource consumption features during query processing in DBMSs. To that end, we provide an in-depth anatomy and qualitatively analyze the power profile of typical queries in the TPC benchmarks. We perform extensive experiments on a physical testbed based on the PostgreSQL system using workloads generated from the TPC benchmarks. Our hypothesis is supported by such experimental results: power savings in the range of 11% - 22% can be achieved by equipping the DBMS with a query optimizer that selects query plans based on both estimated processing time and power requirements.1