A Paired report on PeerDB and PIER Systems.
Summary
PeerDB is a distributed data sharing system that distinguishes itself from the traditional P2P database systems by providing data management facilities like content-based searching. Various distributed systems today need a system that will enable them to share their data (and resources) in spite of their differing individual schema. Different groups of people like groups of researchers or businessmen define their own schema to document their work (data). Hence, a system that can be used to perform content-based search on the varying schema of individual databases of various participating nodes is the need of the hour. The different participating nodes of the system also seek independence to join and leave the network dynamically. PeerDB has been presented by a group of database and network researchers to answer the above issues. PeerDB integrates the two emerging technologies: mobile agents and P2P technologies. The P2P system accounts for the sharing of resources between nodes, and mobile agents are agents that can carry data as well as code to the remote nodes; therefore the filtering task can be performed at the remote end.
The database research community has delved into various issues like scalability and sustainability of very large distributed database systems. But, the degree of distribution has been a scalability metric that they have not yet excelled. This drawback has prevented the database technologies from having an impact on the massively parallel systems like the Internet. One of the primary goals of the Internet systems is to operate on a very large scale. Therefore, while operating on such a large scale, availability is one of the primary concerns, and trivial consistency semantics can be tolerated in the face of availability concerns. PIER (Peer-to-peer information Exchange and Retrieval) is a query-processing engine which aims to bring database querying facilities to the widely distributed networks, like the Internet. PIER uses DHTs (Distribute Hash Tables), which are overlay networks. DHTs provide naming and network routing facilities and are reused for a range of other functions that are handled by separate modules in a traditional DBMS.
Analysis
2.1 Background
PeerDB
Peer-to-peer (P2P) technology is an emerging technology that is capable of revising the architecture of existing massively distributed systems like the Internet. Most of the domain specific P2P systems like the Napster (music), Gnutella have certain limitations. The limitations include lack of data-management capabilities and content-based search; also most of the existing P2P systems have static peers. In order to further exploit the advantages of a Peer-to-Peer architecture, a self-configurable distributed database system with data management capabilities needs to be designed. PeerDB is a P2P database system that is a network of database-enabled nodes, which has been designed to make best use of all the features provided by the P2P system.
PeerDB distinguishes itself from the existing P2P systems in the following ways:
Supports content-based searching, aids sharing of data without shared schema, uses mobile agents to perform operations at the client’s site and hence improves network-bandwidth performance and the PeerDB network is self-configurable.
PIER
It has already been mentioned in the summary that degree of distribution is one of the performance metrics which has been of huge concern to the database community. Currently, the Internet makes it easy to put information into cyberspace which can be accessed by all. The web has become a common platform for the delivery of applications and information. The good news for the database research community is that the web is one huge database. However, the database research community has not contributed much to the web so far [1]. They have failed to be an integral part of the web and appear in peripheral roles. The inability to attain scalability on large-scale distributed systems can be one of the primary reasons for this.
PIER is a massively distributed query engine based on overlay networks, which intends to bring database query facilities to massively distributed systems like the Internet [2]. The PIER is targeted at in situ querying of data that pre-exists in the system. The scalability of PIER was demonstrated for over 10,000 nodes, which is unique in database literature [2]. The PIER system has been implemented in Java, it has unique methods of using the relational query engine and it makes up multi-purpose use of overlay networks. This paper focuses on the design and architecture of PIER.
Technical approach
In the PeerDB system, one of the main issues is keeping track of all the nodes entering and leaving the network, and the reconfigurability of the network. BestPeer provides PeerDB’s P2P enabling technologies. BestPeer is a platform used to develop P2P applications.
In the PeerDB system, the network mainly consists of two entities: many computers (nodes) and a few location-independent global names lookup (LIGLO) servers. BestPeer integrates the P2P and the mobile agent technologies, which is the principal idea that drives the PeerDB system. BestPeer enables finer granularity of data sharing, where a part of a file can be shared and it also shares the computational power.
It is the BestPeer network that ensures the re-configurability of the network. The BestPeer network can reconfigure itself by having peers that are most rewarding.
One of the primary requirements of the PeerDB network is to keep track of the nodes entering and leaving the system. In the PeerDB network, the BestPeer introduces a LIGLO server, which does the above function. The two main functions of the LIGLO server are: generation of a unique global identity BPID (BestPeer Global Identity) and maintaining the peer’s current status (online or offline). This maintained directory (LIGLO server) can be further used to route queries between various nodes.
The PeerDB further extends BestPeer in the following ways: each node has a database system, data can be shared without a global schema and the ability of mobile agents is further exploited by using them for query processing.
2.3 Architecture
2.3.1 PeerDB Architecture:
Each PeerDB node consists of four units that are loosely coupled. The first is a data management system that uses MySQL. For each relation created in the system, the metadata is stored in the Local Dictionary. There is another Data Dictionary known as the Export Dictionary that stores the metadata of the sharable objects.
The second component is a Database agent called the DBA agent. This agent provides the environment for mobile agents to operate on. The third is a cache manager; it is used to cache remote data in secondary storage and determine caching policy. The fourth component is a user interface through which the users’ to submit their queries.
PIER, which is a large-scale Internet-query processor, adopts a slightly different approach for querying over the Internet. It tries to strike a balance between the Internet and the database approaches. The semantics of PIER are slightly relaxed because it is targeted at a large scale. However, it provides data independence including relational data model and indexing facilities, which can be used to manipulate data at any location in the network.
Internet-scale query systems (P2P systems) need to keep track of nodes joining and leaving the P2P network. PIER uses a decentralised approach based on overlay networks in contrast to the centralised approach used in PeerDB. DHTs (Distribute Hash Tables) are the overlaynetworks used by PIER to ensure location independence, where the DHTs assign an identifier to every node and object.
2.3.2 PIER Architecture:
The DHT’s 3 main components include –naming, routing and state.
Naming: Every PIER object in the DHT is named using three parts: namespace, partitioning key and suffix.
Routing: In contrast to the BestPeer’s centralised list of nodes, each node keeps track of a ‘selected’ set of neighbors. Therefore, every node can route directly only to a few nodes and arbitrary nodes are reached through multi-hop. One of the key features of multi-hop is the ability of nodes along the forwarding path to intercept the messages.
State: In soft state, a node stores each item for a short time period, after which it is discarded.
The decentralised approach signifies that PIER is more of a self-administered system, and the burden of the administration is not borne by any single system. Though this approach is advantageous in terms of the cost and responsibility of maintaining a well-administered server, it makes the system very hard to administer and security measures will be hard to impose.
2.4 Security aspects:
One of the distinguishing features of BestPeer is its ability to provide secure access to node’s resources. Each node in system can have two types of data: public data and sharable data. The other nodes can only access the data that is classified as sharable.
This distinction between sharable and private data can be made with the aid of stored Metadata.
PIER has a decoupled architecture where the storage is decoupled from the query engine. Due to this process of decoupling storage and querying, PIER does not have a stored metadata catalogue found in traditional DBMS and PeerDB system. Hence there is no explicit way to distinguish between private data and sharable data in the PIER architecture
2.5 Query Processing
2.5.1 Sharing Data without shared schema
Another important issue that needs to be addressed by the PeerDB system is sharing of data without shared schema. This is ensured by the use of metadata stored in the Data Dictionary. The metadata stored during the creation of a table are keywords provided by the users.
Consider a query Q based on (R, A, C), where R is the set of Relations, A is the set of target attributes and V is the set of conditions. When this query is routed to other nodes, the relation matching agent accesses the relations that are specified by the keywords and attributes mentioned in the export Dictionary.
The degree to which a relation D with attributes T matches Q is determined by a formula [3].
With the aid of the formula, the set of relations that contain matches for Q are determined as relations that have scores which exceed a certain threshold value. Hence using the above strategy data can be shared without shared schema.
In contrast to BestPeer, the PIER system is based on DHTs as overlay networks; hence the query operators expect a defined schema. In the absence of metadata, there is no option provided for relation matching. If a tuple does not match the schema expected by the operator, the tuple is simply discarded.
2.5.2 Query processing strategy
Another major advantage provided by PeerDB is the efficient use of network bandwidth with the aid of mobile agents.
PeerDB adopts a two-phase query processing strategy. The relation matching strategy is applied in the first phase, to locate the potential relations. These relations are then returned to the user so that he can select the relevant relations. It aids in better utilisation of network bandwidth, because minimises transmission of data not useful to the client. It also enables the node to update its statistics for enhanced future search.
In PeerDB’s query processing strategy, it is the agents that are sent out and they interact with the node’s DBMS. They are two types of queries: local queries and remote queries. A query is local if it is initiated at that node and remote otherwise. The query processing strategy for local and remote queries is similar apart from the fact that the agent will search the export dictionary instead of the local dictionary. Also, for a remote query it is an agent that arrives at the node.
Phase1
The relation matching strategy is applied to local dictionary (or export dictionary) and promising relations are returned. Also, the master agent will make copies of the relation matching agents and send them to other nodes. Along with the query, the node carries IP address of the node that initiates the query and TTL (Time to Live) .The process of cloning and forwarding continues till the agent lifetime expires. For peers that return a number of relations, only one relation is returned based on the score. Then, the answers will be returned to the user for selection.
Phase2
For each relation that the user selects, the master agent will clone a copy of the data retrieval agent. The agent will formulate a SQL query and submit it to the DBMS. If the required target relations are present on the remote node, then the worker agent will be sent with the query node’s IP address. Once the answers are returned, if any further processing needs to be performed, the agent performs it (with the help of the code that it carries) and returns summarised data.
PIER
It has already been mentioned that PIER does not maintain system metadata. Hence, every tuple in PIER needs to be self-describing, containing table name, column name and so on. In PIER the column values are stored as Java objects. Tuples enter the system through access methods. The access method inserts the tuple into the dataflow performs type conversion.
A data flow language called UFL (Unnamed Flow Language) has been described for PIER. UFL queries are direct specifications of physical query execution plans. An UFL query plan is made up of opgraphs (operator graphs). Opgraphs help in selectively routing the query to only those nodes required by that portion of the query. Once a query is composed, the client establishes a connection with a PIER node. This PIER node acts as the proxy node, which is responsible for dissemination of the query and forwarding the results to the client.
Query parsing converts the UFL of the query into Java representation. Once the query is parsed, it will be disseminated to nodes needed to process that portion of the query. PIER maintains a distribution tree that can be used by all queries. Though broadcasting is one of the options for query dissemination, it is not efficient. Hence, PIER uses distributed indexes to determine the network nodes needed for the processing of a particular query. PIER currently has three kinds of indexes: a true-predicate index (for queries that range over all the data), Equality predicate index (operations that need to find a specific value), Prefix Hash Tree (for range search).
Though most of the query operators of PIER are similar to traditional DBMS, it has certain non-traditional operators like result handler, in-memory materialiser. Hierarchical Aggregation and Hierarchical join are few of the salient features of PIER. While computing the aggregate, the in-bandwidth load is distributed to multiple tuples. The nodes are arranged into a tree and each node calculates partial aggregate and sends it to a root identifier mentioned in the query. In the case of a hierarchical join, the out-bandwidth of a node can be reduced. While tuples are being forwarded, intermediate nodes intercept it and cache a copy. When, two tuples cached at a node can be joined, the join result is produced and sent directly to the proxy.
Dataflow: PIER uses a “non-blocking” iterator model that uses ‘pull’ for control messages, and push for the dataflow. In a query tree, the parents in a tree are connected to their children via a control channel based on function calls. Asynchronous requests for data (probes) are issued which are similar to ‘open’ call in iterators. When a tuple arrives at a node, it is pushed from child to parent in the opgraph via a data channel based on function calls. Each operator calls the parent with the tuple as an argument. The tuple will continue to flow from child to parent till it is removed from the dataflow (by an operator like selection) or is consumed by an operator like join. The process is repeated for each tuple that matches the probe.
During execution, any node may produce the answer. This is then forwarded to the proxy node. The proxy delivers the tuple to the client. A node continues to execute an opgraph till a time out is specified.
2.6 Execution environment and evaluation
For PeerDB the experimental setup employed consists of with 32PCs with Intel 200M PCs and 64M of RAM. The physical network layout is depicted in the (figure 4) [3]. The 3 different systems compared in the evaluation strategy are the CS (Client Server), PDMS (Peer data management system with static nodes), PDMR (Peer data management system with dynamic nodes). Effect of Storage Capacity on Caching has been observed using storage ratio. As storage ratio increases, both methods response time increases, but PeerDB outperforms CS [3] (fig 5). Under the above-described experimental set up of 32 nodes, queries are issued and average time is noted. PDMR outperforms CS and PDMS due to its reconfigurable ability [3] (fig 6). The out performance of PDMR is further depicted in (fig 7b)[3], which shows that by the time CS has received only 40% of the answers, both PDMR & PDMS already receive 100% of the answers.
Another experiment has been conducted to prove the advantages of using mobile agents. The experiment shows the comparison between using message-passing protocol and agent-based protocol. The completion time of the message based-protocol increases with the data size. There are two experiments; one with single remote execution and the other with multiple remote executions has been performed. Due to the transfer of code in the agent-based protocol, all operations can be performed at the remote node once transmitted and hence it results it optimisation of network resources and bandwidth. The results are shown in (fig8, 9) [3].
The PIER system requires an experimental set up with multitude of nodes. Therefore, the PIER system uses a simple Virtual Runtime Interface (VRI), which can be bound to a real-world environment or a simulation environment. All events in PIER are implemented by a single thread with no preemption. The physical runtime environment comprises of system clock, queue of events in the scheduler, asynchronous I/O thread, and a set of networking libraries. The simulation environment is capable of simulating thousands of virtual nodes on a single machine, providing each node with independent logical clock and network interface.
The benefits of using the PIER system and the real world results have been presented in [4]. The hybrid system of Gnutella and PIER has been used to where Gnutella is used to find replicated nearby items and PIER to find rare items.
2.7 Related work
There is a lot of related work in the fields of PeerDB and PIER, which was studied to produce this paired reading report.
In relation to the PeerDB system the related work studied includes Relational data sharing in peer-based data management [5], schema mapping in P2P networks[6]. In relation to the PIER system, mainly two papers were referred to: Enhancing P2P File-sharing with an internet scale query processor[4] and The case for a hybrid P2P infrastructure[8].
3. Critique
PeerDB is a distributed data sharing system that has been built by extending BestPeer. The clarity of expression throughout the paper is appreciable, appropriate examples have been used for illustration where necessary. Though the process of sharing data without a shared schema has been explicitly explained, there are still a few gaps regarding relation matching and caching that need to be noted. The formula used for finding match between a query and the relation [3], uses certain parameters like the weights (wt), whose relevance has not been clearly described. It has just been stated that the weights are used to reflect the importance of matching the relation and attribute names. Determining these weights would be one of the important steps in relation matching, and needs to be given careful thought. Another important question that has not been answered effectively is the question related to determining the threshold value. It has been mentioned that answers to a query (Q) in the match formula, are those that have scores above a certain threshold value. Nothing has been mentioned about the factors that determine this threshold value. Caching techniques employed have also not been dealt in relevant depth.
Though the work cannot be classified as completely novel, it is an integration of the P2P and mobile agent technologies. It is one of the first attempts to enable data sharing without a shared schema. Though, the relation matching strategy for shared schema without a global schema makes assumption that in most scientific data sharing communities, there exists some generally acknowledged terms or names among users. In situations, where this assumption fails PeerDB fails to locate relations similar to query relations [5]. Another major disadvantage of PeerDB is that it requires human intervention, which is inefficient for large networks and dynamic sources [6].
The evaluation study has been performed on 32 PCs, does not provide sufficient evidence and estimation of real world issues that might crop up. This might hinder the system’s march towards real-world implementation.
In recent times, there has been a lot of ongoing work on the PIER system, since it has been being built for the past three years. Since the vision of PIER and the real-world results showing the advantages of using PIER have already been published, this paper primarily delves into the architecture of PIER. The paper clearly states the challenges that need to be addressed by the research community to make the PIER system realisable. Owing to the fact that PIER system is built on the basis of DHTs, only exact key-match is supported [5]. Mostly, the results produced are based on the simulated environments, and thus there may be many more challenges that need to be faced when implementing on a large scale in the real world. Also, it has been stated that the result fidelity may be affected both due to node failures and network failures. Currently, the simulator is only capable of simulating node failures but not network loss[7].
The PIER approach is aimed at applications that run on many end users’ nodes where centralisation is undesirable. Though it displayed significant advantages when implemented along with the Gnutella file sharing system, it still has a long way to go before it can have significant real world impact because of the security and the fault tolerance issues introduced by the decentralised approach. The existing code base does not implement any of the defences mentioned in the paper – they are still being studied.
At the beginning of the paper it was stated that the real world advantages of using PIER have been mentioned in [4] and [8]. In those experiments it was tested as a hybrid system along with Gnutella. Evaluation and evidence for the performance of PIER in isolation is lacking, and should have been provided by this paper.
4. References
Philip A. Bernstein, Michael L. Brodie, Stefano Ceri, David J. DeWitt, Michael J. Franklin, Hector Garcia-Molina, Jim Gray, Gerald Held, Joseph M. Hellerstein, H. V. Jagadish, Michael Lesk, David Maier, Jeffrey F. Naughton, Hamid Pirahesh, Michael Stonebraker, Jeffrey D. Ullman: The Asilomar Report on Database Research. SIGMOD Record 27(4): 74-80 (1998)
Ryan Huebsch, Joseph M. Hellerstein, Nick Lanham, Boon Thau Loo, Scott Shenker, and Ion Stoica. Querying the Internet with PIER. In
Proc. of the 29th International Conference on Very Large Data Bases, September 2003.
Wee Siong Ng, Beng Chin Ooi, Kian-Lee Tan, and Aoying Zhou: PeerDB: A P2P-based System for Distributed Data Sharing. ICDE 2003: 633-644
Boon Thau Loo, Joseph M. Hellerstein, Ryan Huebsch, Scott Shenker, and Ion Stoica. Enhancing P2P File-Sharing with an Internet-Scale Query Processor. In Proc. of the 30th International Conference on Very Large Data Bases, September 2004.
Beng Chin Ooi , Yan Feng Shu , Kian Lee Tan:Relational Data Sharing in Peer-based Data Management Systems http://citeseer.ist.psu.edu/cache/papers/cs2/476/http:zSzzSzxena1.ddns.comp.n us.edu.sgzSzp2pzSzp2psigrec.pdf/ooi03relational.pdf
Guoliang Li1, Beng Chin Ooi2, Bei Yu2, and Lizhu Zhou1 : Schema Mapping in P2P
Networks based on Classification and Probing http://dbgroup.cs.tsinghua.edu.cn/ligl/papers/DASFAA2007-SchemaMapping.pdf
Ryan Huebsch, Brent N. Chun, Joseph M. Hellerstein, Boon Thau Loo, Petros Maniatis, Timothy Roscoe, Scott Shenker, Ion Stoica, Aydan R. Yumerefendi: The Architecture of PIER: an Internet-Scale Query Processor. CIDR 2005: 28-43
Boon Thau Loo, Ryan Huebsch, Ion Stoica, and Joseph M. Hellerstein. The Case for a Hybrid P2P Search Infrastructure. In Proc. of the 3rd
International Workshop on Peer-to-Peer Systems (IPTPS), San Diego,CA, February 2004.