DiST

1	DiST: Fully Decentralized Indexing for Querying Distributed Multidimensional Datasets= Beomseok Nam, Alan Sussman Department of Computer Science & Institute for Advanced Computer Studies http://www.cs.u= md.edu/projects/hpsl/chaos/ResearchAreas/gmil
2	Motivation Multidimensional range query Retrieves data that overlaps query range an important problem in data/compute-intensive applications in distributed systems or Grid Multidimensional Index can speed up the performance Distributed datasets Scientific datasets are often huge in size And stored in distributed storage systems
3	How to index dis= tributed datasets? Centralized index server An entire index is stored in a central server Hierarchical two level indexing Global index vs. local index Both are vulnerable to a single point of failure and potential bottlenecks Decentralized indexing More scalable and robust
4	Hierarchical Two= Level Indexing Global Index in a top-level index server Stores MBRs (Minimum Bounding Rectangles) of each local index All the queries must look-up global index first, then local indexes next Potential performance bottleneck DiST: Decentralized version of Two Level Indexing Lazy replication of global index
5	DiST: Overview
6	Principles of Decentralized Indexing 1. Distribution Index needs to be partitioned across a large # of servers 2. Dynamism Nodes may join, leave, or fail at any time 3. Correctness for a query A search for data i succeeds if i is stored in a server that has not failed. If some servers in routing path fail, alternative route mus= t be found. 4. Efficiency for a query # of network hops should be logarithmic # of servers accessed should be logarithmic
7	Dynamism: Decent= ralized Node Join None of servers has the whole global index, but only some part of it= Algorithm: Root BBX for local index is converted into high dimensional point d= ata. Contact any server Find parent responsible for new node’s partition using query routing algorithm Insert node’s point into the parent’s global index and = get a copy of the global index
8	Correctness: Decentralized Query Routing Algorithm: If the query bbx overlaps any sub-partition, forward the query to t= he server that owns the sub-partition Example: A query submitted to A, which does not know about C, is forwarded t= o B, that knows about C. Dead Space Problem: Although the query does not overlap the converted point exactly, the query must be forwarded because a node does not know whether another node joined recently
9	Dynamism: Failure Recovery Example: If server B fails, the query submitted to server A cannot be forwar= ded to server C due to network partition Failure recovery option: Multiple servers in a single partition Makes algorithm more robust, but can still fail Neighbor list as in CAN (Content-Addressable-Network) If a server detects another server’s node failure, delete it from its index Forward the query to the server that takes over the failed partiti= on In the example, C is known to A, hence the failure of B is no prob= lem
10	Another Failure Recovery Example A,B,C,D servers will about know each other from neighbor list What if A failed and server E received the query? Step 1: E will find out A has failed Step 2: Delete it from the KD-tree index Step 3: forward the query to the server using the updated index Step 4: The replacement server (D) will find alternative routing pa= th Unlike CAN, each server can maintain rectangular partitions
11	Efficiency: Pig= gyback Updates More server information leads to shorter routing path Lazy update
12	Performance Eva= luation Experiment Environment 41 Linux nodes (rogue cluster) P III 650MHz 100Mb/s Ethernet Intercommunication LAM/MPI Datasets AVHRR GAC level 1B satellite datasets 3 dimensions (Latitude, Longitude, Time) One month of data (30GB) Partitioned into 700,000 chunks Index MBR of each chunk 5,000 chunks in each of 136 virtual nodes
13	Experiments (1)= 40 servers For two-level, an extra global index server was used (41 total) Varying # of clients Each of them submits 2,000 sequential queries Global index in DiST is moderately balanced Each server joined in random order
14	Experiments (2)= Varying # of servers More servers (more clients) leads to more network messages Without piggyback index update Skewed global index generates 3 times more network messages With piggyback the performance gap between skewed and balanced index decreases significantly
15	Experiments (3)= The number of global index update messages delivered to each server = is negligible compared to the total number of messages If servers join and fail frequently, the # of global index update messages would increase A single query can be forwarded to the same server multiple times For a skewed global index without piggyback updates, 1% of messages= are duplicates
16	Conclusions &am= p; Future Works DiST Comparable performance to centralized two-level indexing And resilient to failures Targets large distributed systems without centralized control Future work More experiments Multiple servers in the same partition Scalability simulation Failure recovery Modify DiST for P2P systems Adapt P2P techniques (CAN) to DiST partial global index