Today's processors provide a rich source of statistical informationon application execution through hardware counters. In this paper, we explore the utilization of these statistics as request signaturesin server applications for identifying requests and inferring high-level request properties (e.g., CPU and I/O resource needs). Our key finding is that effective request signatures may be constructed using a small amount of hardware statistics while the request is still in an early stage of its execution. Such on-the-fly request identification and property inference allow guided operating system adaptation at request granularity (e.g., resource-aware request scheduling and on-the-fly request classification). We address the challenges of selecting hardware counter metrics for signature construction and providing necessary operating system support for per-request statistics management. Our implementation in the Linux 2.6.10 kernel suggests that our approach requires low overhead suitable for runtime deployment. Our on-the-fly request resource consumption inference (averaging 7%, 3%, 20%, and 41% prediction errors for four server workloads, TPC-C, TPC-H, J2EE-based RUBiS, and a trace-driven index search, respectively) is much more accurate than the online running-average based prediction (73-82% errors). Its use for resource-aware request scheduling results in a 15-70% response time reduction for three CPU-bound applications. Its use for on-the-fly request classification and anomaly detection exhibits high accuracy for the TPC-H workload with synthetically generated anomalous requests following a typical SQL-injection attack pattern.

Object replication is a common approach to enhance the availability of distributed data-intensive services and storage systems. Many such systems are known to have highly skewed object request probability distributions. In this paper, we propose an object replication degree customization scheme that maximizes the expected service availability under given object request probabilities, object sizes, and space constraints (e.g., memory/storage capacities). In particular, we discover that the optimal replication degree of an object should be linear in the logarithm of its popularity-to-size ratio. We also study the feasibility and effectiveness of our proposed scheme using applications driven by real-life system object request traces and machine failure traces. When the data object popularity distribution is known a priori, our proposed customization can achieve 1.32-2.92 "nines" increase in system availability (or 21-74% space savings at the same availability level) compared to uniform replication. Results also suggest that our scheme requires a moderate amount of replica creation/removal overhead (weekly changes involve no more than 0.24% objects and no more than 0.11% of total data size) under realistic object request popularity changes.

A multi-object operation incurs communication or synchronization overhead when the requested objects are distributed over different nodes. The object pair correlations (the probability for a pair of objects to be requested together in an operation) are often highly skewed and yet stable over time for real-world distributed applications. Thus, placing strongly correlated objects on the same node (subject to node space constraint) tends to reduce communication overhead for multi-object operations. This paper studies the optimization of correlation-aware data placement. First, we formalize a restricted form of the problem as a variant of the classic Quadratic Assignment problem and we show that it is NP-hard. Based on a linear programming relaxation, we then propose a polynomial-time approximation algorithm that finds an object placement with communication overhead at most two times that of the optimal placement. We further show that the computation cost can be reduced by limiting the optimization scope to a relatively small number of most important objects. We quantitatively evaluate our approach on keyword index placement for full-text search engines using real traces of 3.7 million web pages and 6.8 million search queries. Compared to the correlation-oblivious random object placement, our approach achieves 37-86% communication overhead reduction on a range of optimization scopes and system sizes. The communication reduction is 30-78% compared to a correlation-aware greedy approach.

Bloom filters are compact set representations that support set membership queries with small, one-sided error probabilities. Standard Bloom filters are oblivious to object popularity in sets and membership queries. However, sets and queries in many distributed applications follow known, stable, highly skewed distributions (e.g., Zipf-like). This paper studies the problem of minimizing the false-positive probability of a Bloom filter by adapting the number of hashes used for each data object to its popularity in sets and membership queries. We model the problem as a constrained nonlinear integer program and propose two polynomial-time solutions with bounded approximation ratios -- one is a 2-approximation algorithm with O(Nc) running time (c ≥ 6 in practice); the other is a (2+ε)-approximation algorithm with running time O(N2/ε)$, ε > 0. Here N denotes the total number of distinct data objects that appear in sets or queries. We quantitatively evaluate our proposed approach on two distributed applications (cooperative caching and full-text keyword searching) driven by real-life data traces. Compared to standard Bloom filters, our data popularity-conscious Bloom filters achieve up to 24 and 27 times false-positive probability reduction for the two applications respectively. The quantitative evaluation also validates our solution's bounded approximation ratio to the optimal.

Network structure construction and global state maintenance are expensive in large-scale dynamic peer-to-peer (P2P) networks. With inherent topology independence and low state maintenance overhead, random walk is an excellent tool in such network environments. However, the current uses are limited to unguided or heuristic random walks with no guarantee on their converged node visitation probability distribution. Such a convergence guarantee is essential for strong analytical properties and high performance of many P2P applications. In this paper, we investigate an approach for random walks to converge to application-desired node visitation probability distributions while only requiring information about the direct neighbors of each peer. Our approach is guided by the Metropolis-Hastings algorithm for Monte Carlo Markov Chain sampling. Our contributions are threefold. First, we analyze the convergence time of the random walk node visitation probability distribution on common P2P network topologies. Second, we analyze the fault tolerance of our random walks in dynamic networks with potential walker losses. Third, we present the effectiveness of random walks in assisting three realistic network applications: random membership subset management, search, and load balancing. Both search and load balancing desire random walks with biased node visitation distributions to achieve application-specific goals. Our analysis, simulations, and Internet experiment demonstrate the advantage of our random walks compared with alternative topology-independent index-free approaches.

No abstract available.

Existing random membership management algorithms provide each node with a small, uniformly random subset of global participants. However, many applications would benefit more from non-uniform random member subsets. For instance, non-uniform gossip algorithms can provide distance-based propagation bounds and thus information can reach nearby nodes sooner. In another example, Kleinberg shows that networks with random long-links following distance-based non-uniform distributions exhibit better routing performance than those with uniformly randomized topologies. In this paper, we propose a scalable non-uniform random membership management algorithm, which provides each node with a random membership subset with application-specified probability e.g., with probability inversely proportional to distances. Our algorithm is the first non-uniform random membership management algorithm with proved convergence and bounded convergence time. Moreover, our algorithm does not put specific restrictions on the network topologies and thus has wide applicability.