Group Scalability in Distributed Systems - Adaptively Parallelizing Distributed Range Queries
Speaker(s) : Dr. Ymir Vigfusson (IBM Research, Haifa)
Title: Group Scalability in Distributed Systems
We address shortcomings of two important group communication paradigms, IP Multicast and gossip based message dissemination, both of which have scalability issues when the number of groups grows.
First, we propose a transparent and backward-compatible layer called Dr. Multicast to allow data center administrators to enable IPMC for large numbers of groups without causing scalability issues. Dr. Multicast optimizes IPMC resources by grouping together similar groups in terms of membership to minimize redundant transmissions as well as the cost of filtering unwanted messages.
Second, we argue that when nodes belong to multiple groups, gossip based communication loses its appealing property of using a fixed amount of bandwidth. We propose a platform called GO (Gossip Objects) that bounds each node's bandwidth use to a customizable limit, prohibiting applications from joining groups that would cause the limit to be exceeded. We make the observation that gossip rumors tend to be small, and propose a utility-based heuristic to stack rumors into packets to optimize delivery speed, with rumors sometimes traveling through indirect paths.
Features joint work with Hussam Abu-Libdeh, Mahesh Balakrishnan, Ken Birman, Robert Burgess, Gregory Chockler, Qi Huang, Jure Leskovec, Haoyuan Li, Deepak Nataraj and Yoav Tock.
Title: Adaptively Parallelizing Distributed Range Queries
Abstract: We consider the problem of how to best parallelize range queries in a massive scale distributed database. In traditional systems the focus has been on maximizing parallelism, for example by laying out data to achieve the highest throughput. However, in a massive scale database such as the PNUTS system  or BigTable , maximizing parallelism is not necessarily the best strategy: the system has more than enough servers to saturate a single client by returning results faster than the client can consume them, and when there are multiple concurrent queries, maximizing parallelism for all of them will cause disk contention, reducing everybody’s performance.
How can we find the right parallelism level for each query in order to achieve high, consistent throughput for all queries? We propose an adaptive approach with two aspects. First, we adaptively determine the ideal parallelism for a single query execution, which is the minimum number of parallel scanning servers needed to satisfy the client, depending on query selectivity, client load, client-server bandwidth, and so on. Second, we adaptively schedule which servers will be assigned to different query executions, to minimize disk contention on servers and ensure that all queries receive good performance. Our scheduler can be tuned based on different policies, such as favoring short versus long queries or high versus low priority queries.
An experimental study demonstrates the effectiveness of our techniques in the PNUTS system.
Joint work with Brian Cooper, Adam Silberstein and Rodrigo Fonseca.
--- Biography: Ymir Vigfusson is a researcher at IBM Research in Haifa. He completed his Ph.D. in Computer Science from Cornell University in August 2009, where he worked with Prof. Ken Birman on exploiting group similarity and scalability in distributed systems. Besides Dr. Multicast and GO, his research projects include characterization of large-scale human preference patterns, algorithms for distributed slicing, and Ajil - distributed rate limiting for data centers. Ymir received a B.Sc. degree in Mathematics from the University of Iceland in 2005, and his work has been partially supported by a Fulbright Scholarship and a Yahoo! Research Grant. In his sparse free time, Ymir enjoys flying, ballroom dancing and playing the piano.