|
1
|
- 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
|
- 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
|
- 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
|
|
4
|
- 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
|
|
|
6
|
- 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
|
- 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
|
- 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
|
- 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
|
- 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
|
- More server information leads to shorter routing path
- Lazy update
|
|
12
|
- Experiment Environment
- 41 Linux nodes (rogue cluster)
- P III 650MHz
- 100Mb/s Ethernet
- Intercommunication
- 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
|
- 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
|
- 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
|
- 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
|
- 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
|