1

Abstract

Magnolia: A novel DHT Architecture for Keyword-based Searc hing Ashish Gupta, Manan Sanghi, Peter Dinda, Fabian Bustamante Department of Computer Science, Northwestern University Email: {ashish,manan,pdinda,fabianb }@cs.northwestern.edu The class of DHT-based P2P systems like Chord, Pastry, Tapes try, Kademlia greatly improve over unstructured P2P systems lik e GnutellaandKazaabyproviding (1)Scalableandefficient O(log(n)) lookup and routing for any document (2) Good load balancing properties for very large number of keys or documents. Howev er, to lookup a document, its complete initial identifier must be known tocompute itsunique hashed key and route tothe correct node , which is a major disadvantage compared to unstructured systems. Our goal in this ongoing project is to create a DHT-based P2P architecture that supports efficient partial keyword searc hes in a scalable manner. Some recent proposals for keyword search [ 2], [4], [1], [5] have suggested storing all documents pointers for a keyword on a node corresponding to keyID= h(keyword ). For example, all files which have ”usenix” in their title are stored on a single node corresponding to h(”usenix ”). Multiple keyword search can then be made possible bycomputing the hashes for eachkeyword and vi siting corresponding nodes to fetch all results (which can be proce ssed in the network for boolean operations before returning). Thou gh correct, we argue that this approach does not align well with the goals of a DHTsystem forvery largescale andtransient networks. High amount of keyword heterogeneity in occurrence frequency as well as query frequency further aggravate the problem (These have been sh own to follow Zipf distribution): (1) Millions of documents corre sponding to a common keyword can end up on a single node. Overall, distrib ution of these document pointers can be heavily skewed over the nod es (2) When a node disappears, all document pointers correspon ding to keyword(s) stored on this node are removed from the networ k, hampering future searches. This is especially problematic if the nodes storing pointers for popular keywords fail. (3) Nodes can be swamped with search traffic for these popular keywords creat ing routing hotspots (resulting from routing large number of me ssages to a single destination) as well as query hotspots. We have designed a simple DHT architecture Magnolia which is not effected by the fore-mentioned problems while simultan eously providing lognhops for routing and lookup and low, bounded number of nodes visited and traffic generated. Our model scen ario is a large scale P2P file sharing system with over 1 million nod es which show high transiency and is responsible for storing ov er 1 billion documents. Our architecture proposes novel node gr ouping and key distribution methods using a multi-hashing scheme a nd makes use ofhashfunctionproperties toeffectivelydistri butepointers corresponding to every keyword to a tunable number of nodes. Using Multi-hashing each keyword is balanced across a set of nodes in the system with little overlap between different set of node s, which achieves both good load-balance in terms of traffic and key st orage as wellasmakingsearchhighlyrobusttofailures.Wewanttofo rmthese groups such that popular keywords have low probability of be ing assigned to the same group. We also propose a modified DHT rout ing architecture which can then store documents and lookup keyw ord queries in log(n)hops , though the keyword pointers are mapped to multiple nodes. The amount of traffic generated and number of nodes visited is also low and bounded. Figure 1 shows the technique of multi-hashing. We have khash functions h1(), …, h k()where hi()maps a keyword a m′bit key (m′< m, the total number of bits used in nodeID or documentID). For each keyword corresponding to every document instance ( which weassume currentlyare derivedfromitstitleor metainform ationlikewi h1() h2() hk() …. keywordGroupID x=uniform r.v. over {1,…,k} hx(wi) m’ bits m bits nodeID keyword Set of k hash functions Fig. 1. The Multi-hashing process which maps each instance o f a keyword to one of the kpossible KeywordGroupIDs for a particular keyword ID tags in mp3 files) we compute a m′bit key using hx(keyword ) where xis a uniformly distributed random variable over the set 1, …, k. The intuition behind doing this is that the m′bit key corresponds to the first m′bits of the m-bit nodeID which is uniformly distributed over all the nodes. If m′= 16and there are one million nodes, on average220 216= 16nodes would have the same value for a particular m′bit value also called KeywordGroupID in our system. Since each instance of the keyword can map toany o f the hi()hash functions, it can map to any of the kKeywordGroupIDs and be stored on any of these nodes belonging to these groups. The motivation behind this technique to distribute keyword ins tances is that using a novel DHT routing architecture these group of no des belonging to a KeywordGroupID can be reached and searched wi th low and bounded number of hops, providing the same log(n)number of hops as the original proposals which route to a single node . Current Status We have currently worked out the design and details of the mul ti- hashing process and the corresponding DHT routing architec ture which provides low and bounded response time for storage and lookup. Our Technical Report [3] gives more detail along wit h an- alytical treatment for important performance and scalabil ity metrics: Load-balancing of keys (aggregate and per-keyword), routi ng and lookup performance, traffic generated and number of nodes vi sited and the routing state kept at each node. Our next step is to con duct a detailed evaluation of the system to measure important met rics using real world keyword and query distributions to provide a better understanding of advantages of Magnolia. REFERENCES [1] BAUER, D., HURLEY, P., PLETKA, R.,ANDWALDVOGEL ,M. Bringing efficient advanced queries to distributed hash tables. In Proceedings of IEEE LCN (Nov. 2004). [2] GARCES-ERICE, L., FELBER, P., BIERSACK , E. W., U RVOY-KELLER, G.,ANDROSS, K. W. Data indexing in peer-to-peer DHT networks. In24th International Conference on Distributed Computing Sy stems (24th ICDCS'2004) (Tokyo, Japan, Mar. 2004), IEEE Computer Society, pp. 200–208. [3] GUPTA,A., SANGHI,M., D INDA, P.,ANDBUSTAMANTE ,F. Magnolia: A novel dht architecture for keyword-based searching. Technial Report, Northwestern University (March 2005). [4] HARREN, M., H ELLERSTEIN , J. M., H UEBSCH, R., L OO, B. T., SHENKER,S.,ANDSTOICA,I. Complex queries in DHT-based peer-to- peer networks. Lecture Notes in Computer Science 2429 (2002), 242–?? [5] REYNOLDS ,P.,ANDVAHDAT,A. Efficient peer-to-peer keyword search- ing. InMiddleware (2003), pp. 21–40.