Many peer-to-peer systems, such as file sharing networks, require the ability to search for files by metadata. This functionality is not easy to implement efficiently. Many current file sharing networks are implemented using techniques such as centralized indexes, which lack the scalability and resilience of a distributed system, or query flooding, which is notoriously inefficient. Often, they trade-off scalability for correctness, resulting in either systems that scale well but sacrifice completeness of search results or vice-versa.
Distributed hash tables have become a standard for constructing peer-to-peer systems because they overcome the difficulties of quickly and correctly locating peers. However, the lookup by name DHT operation is not immediately sufficient to perform complex search by content queries of the data stored in the network. It is not clear how to perform searches without sacrificing scalability or query completeness. Indeed, the obvious approaches to distributed full-text document search scale poorly. Our work addresses the problem when searches are restricted to file metadata. Peer-to-peer indexing for metadata remains feasible, because the datasets we consider have a small number of metadata keywords per file (on the order of 5-10), which is much smaller than the full text of an average Web page.
We have designed Arpeggio [1,2], a novel file sharing system based on the Chord distributed hash table [3]. Arpeggio includes a system for building a distributed index of file metadata that is fully decentralized but able to efficiently answer search queries with near-perfect recall. This is accomplished via a distributed keyword-set index. In addition, Arpeggio also includes a separate content distribution subsystem for identifying peers that have a particular file available.
Our system is based on a distributed inverted index. In this scheme, the DHT maps each keyword to a list of all files whose metadata contains that keyword. Traditionally, some form of index joining is required to perform a multi-keyword query: in the simplest instance, a node obtains the index lists for each query and intersects them. This may generate tremendous network traffic since the keyword index lists can become prohibitively long, particularly for very popular keywords. Instead, we improve performance by using index-side filtering instead of joining at the querying node. Because our application postulates that metadata is small, the entire contents of each item's metadata can be kept in the index as a metadata block, along with information on how to obtain the file contents. To perform a query involving a keyword, we send the full query to the corresponding index node, and it performs the filtering and returns only relevant results. This dramatically reduces network traffic at query time, since only one index needs to be contacted and only results relevant to the full query are transmitted.
While filtering reduces network usage, query load may be unfairly distributed, overloading nodes responsible for popular keywords. To overcome this problem, we propose to build inverted indexes not only on keywords but also on keyword sets. As before, each unique file has a corresponding metadata block that holds all of its metadata. Now, however, an identical copy of this metadata block is stored in an index corresponding to each subset of at most K metadata terms. The maximum set size K is a parameter of the network. This is the Keyword-Set Search system (KSS) introduced by Gnawali [4].
Essentially, this scheme allows us to precompute the full-index answer to all queries of up to K keywords. For queries of more than K keywords, the index for a randomly chosen K-keyword subset of the query can be filtered. This approach has the effect of querying smaller and more distributed indexes whenever possible, thus alleviating unfair query load caused by queries of more than one keyword.
Because peers are constantly joining and leaving the network, the search index must respond dynamically to the shifting availability of the data it is indexing and the nodes on which the index resides. Furthermore, certain changes in the network, such as nodes leaving without notification, may go unnoticed, and polling for these changing conditions is too costly, so the index must be maintained by passive means. We introduce techniques for minimizing the cost of index maintenance by relaxing consistency guarantees, and using an index gateway to aggregate the cost of insertions of common files.
Arpeggio has been implemented, including an indexing layer that implements the algorithms described above, and user interface components that provide query access via web search and plugins for a popular BitTorrent client. Using corpora from the FreeDB index, various BitTorrent search sites, and a trace of the Gnutella network, we evaluated the feasibility of maintaining an index via analysis and simulation. Our results show that for reasonable values of the parameter K, keyword-set indexing is feasible and improves query load distribution.
This research was conducted as part of the IRIS project (http://project-iris.net/), supported by the National Science Foundation under Cooperative Agreement No. ANI0225660. Dan R. K. Ports was supported by the Office of Naval Research under a National Defense Science and Engineering Graduate (NDSEG) Fellowship.
[1] Dan R. K. Ports. Arpeggio: Metadata Indexing in a Structured Peer-to-Peer Network, Master's thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA, February 2007.
[2] Austin T. Clements, Dan R. K. Ports, and David R. Karger. Arpeggio: Metadata Searching and Content Sharing with Chord. In The Proceedings of the Fourth International Workshop on Peer-to-Peer Systems (IPTPS '05), Ithaca, New York, USA, February 2005.
[3] Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica. Wide-area cooperative storage with CFS. In Proc. of the 18th ACM Symposium on Operating System Principles (SOSP '01), October 2001.
[4] Omprakash D. Gnawali. A Keyword Set Search System for Peer-to-Peer Networks, Master's thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA, June 2002.