Indexing data-oriented overlay networks using belief propagation
In this paper we discuss the problem of data-oriented partitioning in large-s cal overlay networks, as required by peer-to-peer databases or by peer-to-peer information retrieval. The goal is to partition a large set of nodes into k partitions with the additional requirement of meeting certain load-balancing c o straints without global knowledge of the network’s parameters, i.e., the desired number of partitions and the partition distribution function are not known in advance and change dynamically as the network evolves. This k ey problem in large-scale decentralized systems has so far received only very limited attention. The novel contrib utions described in the following are (1) the definition of a distributed algorithm for local estimation of the partitioning distr ibution function, which does not preclude the network’s topology, and (2) a distributed method for perfo rming the actual partitioning. As additional advantages, the algorithms do not require global knowledge and works highly parallel which provides a low latency of the partitioning process. Both algorithms are based on the max-produc t belief propagation algorithm and give exact results on trees, and sufficiently accurate approximations on graphs co ntaining cycles. We show the accuracy of the proposed algorithms in terms of the number of nodes per partition and the g ood load balancing of partitions in the network by simulation. Our algorithms are scalable and the accuracy of the partitioning improves with larger network sizes. Having shown the efficiency of our proposed algorithms, we disc uss a natural application for our algorithm in the data-oriented P2P system P-Grid (http://www.p-grid.org/). Using P-G rid’s underlying tree abstraction, we can apply our algorithm recursively to achieve optimal partitioning results in sho rt times relative to the tree diameter. I. I NTRODUCTION Currently the standard way of indexing in nearly all overlay networks is to compute uniformly distributed keys from the data to be indexed, e.g., by using standard hashing. With some simple additional partition assignment and maintenance algorithms (joining/leaving of nodes), this e n ures that the key space is evenly distributed among the participating nodes, i.e., the storage load is balanced amo ng the peers. This standard model for overlay networks also assumes that peers essentially join and leave in a seque ntial way and the resulting maintenance schemes to repair inconsistencies or re-balance load essentially cor respond to updating database indexing structures which has been studied extensively in the literature. Approaches following this basic strategy work fine for scena rios where semantic relations among the data items are irrelevant and only very simple query predicates, i.e., equality, have to be supported. A typical example for such applications would be a naming service, statically bin ding a set of attributes to an identifier. However, in typical data-oriented scenarios the standard strategy out lined above, will no longer work or become very inefficient. In data-oriented applications, for example, re-indexing d ue to a change in the data distribution, or a new data field to be indexed, or the need to preserve key-ordering rela tions implies that uniform hashing cannot be applied anymore as it destroys these properties. In consequence the distribution of keys will be unknown, most likely be skewed, and a more powerful, explicit partitioning scheme e nsuring load-balancing will be required. Additionally, the indexing/partitioning strategy should support a high d egree of parallelism to minimize latency. Adaptive Eager Partitioning [2] (AEP) is an efficient, compl etely decentralized, parallel, partitioning algorithm which meets these requirements. It uses an analytically pro ven strategy, verified by simulation and through an implementation in the P-Grid overlay network [1] (http://w w .p-grid.org/), to estimate the key distribution based on local knowledge and ensures storage and replication load ba l ncing, i.e., each data partition contains approximately the same number of keys and approximately the same number of p eers (nodes) are responsible for each partition. The work presented in this paper was supported (in part) by th e European project Evergrow No 001935. We have used the implementation in P-Grid as a proof-of-conc ept, but the essential elements of AEP are applicable to all overlay networks using fixed key space partitioning sc hemes, for example, CAN [9] or Pastry [10]. In this paper we present an alternative strategy based on bel ief propagation to achieve the same goal, i.e., to partition a large set of nodes into k partitions. By applying this recursively we ensure routing consistency and meet AEP’s storage and replication load-balancing constraints . We do not assume global knowledge of the network’s parameters, i.e., the desired number of partitions and the p artition distribution function are not known in advance and change dynamically as the network evolves. The motivation f or this work was to have another generally applicable strategy at hand and to test and compare it with AEP. A. Local estimation of the data distribution As the first step in the approach we need to estimate the distri bution of the data set to be indexed. As we assume a P2P environment, we cannot assume global knowledge of all th e the data. Thus we have to estimate the distribution as good as possible based on local information. The followin g example illustrates this problem: Assume nodes index dictionary words, and we have 26 partitions correspon ding to the letters A–Z. We would like to estimate what is the fraction of nodes needed to store words starting w th each letter. This is highly important especially for skewed distributions where some partitions require more st orage space relative to the others. Given a set ofn + 1 nodes, where each node has small subset of neighbors and its l ocal stored keys. We assume that each key belongs to exactly one partition and eac h node should have an estimation of the partitioning distribution function. Formally, we would like each node to calculate a vector of size k, wherek is the number of different partitions, such that p1, . . . , pk is the percentage of keys in partition i and ∑k i=1 pi = 1. B. K-Partitioning Problem Given a set P ofn + 1 peers which hold keys from a keyspace K, we would like to partition the set into (0, 1, . . . , k) sets such that the load measured in number of data keys relate d to he partitions1, . . . , k is expressed in a probability distributionp1, . . . , pk, which is termedpartitioning function. The partitions we would like to achieve should have the follo wing properties: 1) Proportional replication: Each peer has to decide for one partition such that (in expectation) a fraction pi of the peers decides for partition i. 2) Referential integrity: a) The graph has to be connected, i.e., each peer has sufficien t links to reach any other partition (in-)directly. b) Each peer strives to maximize the number of neighbors from different partitions under its degree constraint. Note that without the proportional replication requiremen t, the peers could decide for a partition based on the partitions probability function, and in expectation achie ve the desired partitioning. However, this would not ensure approximately uniform availability of all the data. The ref erential integrity function ensures routing consistency a nd can be exploited to achieve better load balancing of partiti ons. For being able to evaluate the quality of a solution for the ab ove problems we need to define some metrics. As for the estimation problem we might take the mean square erro r of an estimate relative to the correct partitioning distribution function. In the K-partitioning problem we have two metrics that might be contradicting. First, we want to have an exact numeric partitioning of nodes as close as possible to the par titioning distribution function. Here we can take the mean square error as well. Another metric is the link satisfa ction ratio, where we would like to minimize the number of neighboring nodes which are partitioned into a com m n partition. The first metric arises from the need to allocate a proportional number of nodes based on the stora ge needs. The second metric is important in terms of load balancing where we would like to prevent unbalanced p lacement of a partition in a small neighborhood of nodes. This is bad in terms of resiliency to failures, and net work load. II. PROPOSED ALGORITHMS For solving the two problems of distributed partitioning fu nction estimation and the extended partitioning problem we will use the max-product belief propagation algorithm wh ich we will briefly outline in this section. Then we present the technical details needed for constructing bo th algorithms. First, we run the distributed estimation algorithm to equip nodes with local knowledge of the partiti oning distribution function and then we run the Kpartitioning algorithm using the result of the estimation a lgorithm as its input.