P-Grid

Last updated July 07, 2024

In distributed data storage, a P-Grid is a self-organizing structured peer-to-peer system, which can accommodate arbitrary key distributions (and hence support lexicographic key ordering and range queries), still providing storage load-balancing and efficient search by using randomized routing.

Salient features

Good storage load-balancing despite arbitrary load-distribution over the key-space.^[1]
Range queries can be naturally supported and efficiently processed on P-Grid because P-Grid abstracts a trie-structure, and supports (rather) arbitrary distribution of keys, as observed in realistic scenarios.^[1]
A Self-referential directory is realized to provide peer identity persistence over multiple sessions.^[1]
A gossip primitive based update mechanism for keeping replicated content up-to-date.^[1]
Easy merger of multiple P-Grids, and hence decentralized bootstrapping of the P-Grid network.^[1]
Query-adaptive caching is easy to realize on P-Grid to provide query load-balancing where peers have restricted capacity.^[1]

Overview

For the sake of simplicity, this figure does not show replication. PGrid.jpg — For the sake of simplicity, this figure does not show replication.

P-Grid abstracts a trie and resolves queries based on prefix matching. The actual topology has no hierarchy. Queries are resolved by matching prefixes. This also determines the choice of routing table entries. Each peer, for each level of the trie, maintains autonomously routing entries chosen randomly from the complementary sub-trees.^[2] In fact, multiple entries are maintained for each level at each peer to provide fault-tolerance (as well as potentially for query-load management). For diverse reasons including fault-tolerance and load-balancing, multiple peers are responsible for each leaf node in the P-Grid tree. These are called replicas. The replica peers maintain an independent replica sub-network and uses gossip based communication to keep the replica group up-to-date.^[3] The redundancy in both the replication of key-space partitions as well as the routing network together is called structural replication. The figure above shows how a query is resolved by forwarding it based on prefix matching.^{[ citation needed ]}

Range queries in P-Grid

P-Grid partitions the key-space in a granularity adaptive to the load at that part of the key-space. Consequently, its possible to realize a P-Grid overlay network where each peer has similar storage load even for non-uniform load distributions. This network probably provides as efficient search of keys as traditional distributed hash tables (DHTs) do. Note that in contrast to P-Grid, DHTs work efficiently only for uniform load-distributions.^[4]

Hence we can use a lexicographic order preserving function to generate the keys, and still realize a load-balanced P-Grid network which supports efficient search of exact keys. Moreover, because of the preservation of lexicographic ordering, range queries can be done efficiently and precisely on P-Grid. The trie-structure of P-Grid allows different range query strategies, processed serially or in parallel, trading off message overheads and query resolution latency.^[5] Simple vector-based data storage architectural frameworks are also subject to variable query limitations within the P-Grid environment.^[6]

Related Research Articles

<span class="mw-page-title-main">Client–server model</span> Distributed application structure in computing

The client–server model is a distributed application structure that partitions tasks or workloads between the providers of a resource or service, called servers, and service requesters, called clients. Often clients and servers communicate over a computer network on separate hardware, but both client and server may reside in the same system. A server host runs one or more server programs, which share their resources with clients. A client usually does not share any of its resources, but it requests content or service from a server. Clients, therefore, initiate communication sessions with servers, which await incoming requests. Examples of computer applications that use the client–server model are email, network printing, and the World Wide Web.

Peer-to-peer (P2P) computing or networking is a distributed application architecture that partitions tasks or workloads between peers. Peers are equally privileged, equipotent participants in the network, forming a peer-to-peer network of nodes.

In computer science, a trie, also called digital tree or prefix tree, is a type of k-ary search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters. In order to access a key, the trie is traversed depth-first, following the links between nodes, which represent each character in the key.

In computing, load balancing is the process of distributing a set of tasks over a set of resources, with the aim of making their overall processing more efficient. Load balancing can optimize response time and avoid unevenly overloading some compute nodes while other compute nodes are left idle.

A distributed hash table (DHT) is a distributed system that provides a lookup service similar to a hash table. Key–value pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key. The main advantage of a DHT is that nodes can be added or removed with minimum work around re-distributing keys. Keys are unique identifiers which map to particular values, which in turn can be anything from addresses, to documents, to arbitrary data. Responsibility for maintaining the mapping from keys to values is distributed among the nodes, in such a way that a change in the set of participants causes a minimal amount of disruption. This allows a DHT to scale to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures.

JXTA (Juxtapose) was an open-source peer-to-peer protocol specification begun by Sun Microsystems in 2001. The JXTA protocols were defined as a set of XML messages which allow any device connected to a network to exchange messages and collaborate independently of the underlying network topology.

GNUnet is a software framework for decentralized, peer-to-peer networking and an official GNU package. The framework offers link encryption, peer discovery, resource allocation, communication over many transports and various basic peer-to-peer algorithms for routing, multicast and network size estimation.

Kademlia is a distributed hash table for decentralized peer-to-peer computer networks designed by Petar Maymounkov and David Mazières in 2002. It specifies the structure of the network and the exchange of information through node lookups. Kademlia nodes communicate among themselves using UDP. A virtual or overlay network is formed by the participant nodes. Each node is identified by a number or node ID. The node ID serves not only as identification, but the Kademlia algorithm uses the node ID to locate values.

In cryptography and computer science, a hash tree or Merkle tree is a tree in which every "leaf" node is labelled with the cryptographic hash of a data block, and every node that is not a leaf is labelled with the cryptographic hash of the labels of its child nodes. A hash tree allows efficient and secure verification of the contents of a large data structure. A hash tree is a generalization of a hash list and a hash chain.

Replication in computing involves sharing information so as to ensure consistency between redundant resources, such as software or hardware components, to improve reliability, fault-tolerance, or accessibility.

BitVault is a content-addressable distributed storage system, developed by Microsoft Research in China. BitVault uses peer-to-peer technology to distribute the tasks of storing and managing data. As such, there is no central authority responsible for management of the system. Rather, it is self-managing, provides high availability, reliability and scales up in a self-organizing manner, with low administrative overhead, which is almost constant irrespective of the size of the distributed overlay network.

Tapestry is a peer-to-peer overlay network which provides a distributed hash table, routing, and multicasting infrastructure for distributed applications. The Tapestry peer-to-peer system offers efficient, scalable, self-repairing, location-aware routing to nearby resources.

A prefix hash tree (PHT) is a distributed data structure that enables more sophisticated queries over a distributed hash table (DHT). The prefix hash tree uses the lookup interface of a DHT to construct a trie-based data structure that is both efficient, and resilient.

Magma is a distributed file system based on a distributed hash table, written in C, compatible with Linux and BSD kernels using FUSE.

Peer-to-peer caching is a computer network traffic management technology used by Internet Service Providers (ISPs) to accelerate content delivered over peer-to-peer (P2P) networks while reducing related bandwidth costs.

TomP2P is a distributed hash table which provides a decentralized key-value infrastructure for distributed applications. Each peer has a table that can be configured either to be disk-based or memory-based to store its values.

A data grid is an architecture or set of services that allows users to access, modify and transfer extremely large amounts of geographically distributed data for research purposes. Data grids make this possible through a host of middleware applications and services that pull together data and resources from multiple administrative domains and then present it to users upon request.

<span class="mw-page-title-main">Oracle NoSQL Database</span> Distributed database

Oracle NoSQL Database is a NoSQL-type distributed key-value database from Oracle Corporation. It provides transactional semantics for data manipulation, horizontal scalability, and simple administration and monitoring.

A distributed file system for cloud is a file system that allows many clients to have access to data and supports operations on that data. Each data file may be partitioned into several parts called chunks. Each chunk may be stored on different remote machines, facilitating the parallel execution of applications. Typically, data is stored in files in a hierarchical tree, where the nodes represent directories. There are several ways to share files in a distributed architecture: each solution must be suitable for a certain type of application, depending on how complex the application is. Meanwhile, the security of the system must be ensured. Confidentiality, availability and integrity are the main keys for a secure system.

Elliptics is a distributed key–value data storage with open source code. By default it is a classic distributed hash table (DHT) with multiple replicas put in different groups. Elliptics was created to meet requirements of multi-datacenter and physically distributed storage locations when storing huge amount of medium and large files.

References

1 2 3 4 5 6 Antonopoulos, Nick (2010). Handbook of Research on P2P and Grid Systems for Service-Oriented Computing: Models, Methodologies and Applications: Models, Methodologies and Applications. IGI Global. pp. 323–892.
↑ Ray, Chhanda (2009). Distributed Database Systems. Pearson Education India. pp. 87–121.
↑ Jepsen, Thomas (2013). Distributed Storage Networks: Architecture, Protocols and Management. John Wiley & Sons. pp. 37–79.
↑ Pitoura, Pitoura; Ntarmos, Nikos; Triantafillou, Peter (2006). Replication, load balancing and efficient range query processing in DHTs. International Conference on Extending Database Technology. pp. 131–148. doi:10.1007/11687238_11.
↑ Datta, A.; Hauswirth, M.; John, R.; Schmidt, R.; Aberer, K. (2005). Range queries in trie-structured overlays. Fifth IEEE International Conference on Peer-to-Peer Computing. pp. 57–66. doi:10.1109/P2P.2005.31. ISBN 0-7695-2376-5.
↑ Oliker, Leonid; Canning, Andrew; Carter, Jonathan; Shalf, John; Ethier, Stéphane (2008). "Scientific Application Performance on Leading Scalar and Vector Supercomputering Platforms". The International Journal of High Performance Computing Applications. 22: 5–20. doi:10.1177/1094342006085020. S2CID 5347699.

External links

manfredhauswirth.org

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Antonopoulos-1] 1 2 3 4 5 6 Antonopoulos, Nick (2010). Handbook of Research on P2P and Grid Systems for Service-Oriented Computing: Models, Methodologies and Applications: Models, Methodologies and Applications. IGI Global. pp. 323–892.

[Ray-2] Ray, Chhanda (2009). Distributed Database Systems. Pearson Education India. pp. 87–121.

[Jepsen-3] Jepsen, Thomas (2013). Distributed Storage Networks: Architecture, Protocols and Management. John Wiley & Sons. pp. 37–79.

[Pitoura-4] Pitoura, Pitoura; Ntarmos, Nikos; Triantafillou, Peter (2006). Replication, load balancing and efficient range query processing in DHTs. International Conference on Extending Database Technology. pp. 131–148. doi:10.1007/11687238_11.

[Datta-5] Datta, A.; Hauswirth, M.; John, R.; Schmidt, R.; Aberer, K. (2005). Range queries in trie-structured overlays. Fifth IEEE International Conference on Peer-to-Peer Computing. pp. 57–66. doi:10.1109/P2P.2005.31. ISBN 0-7695-2376-5.

[Oliker-6] Oliker, Leonid; Canning, Andrew; Carter, Jonathan; Shalf, John; Ethier, Stéphane (2008). "Scientific Application Performance on Leading Scalar and Vector Supercomputering Platforms". The International Journal of High Performance Computing Applications. 22: 5–20. doi:10.1177/1094342006085020. S2CID 5347699.

[1]

[2]

[3]

[4]

[5]

[6]