在考慮地域鄰近性與群組化的點對點範圍查詢系統的搜尋與快取機制

Search and Cache Mechanism in A Proximity-Aware and Group-Based Peer-to-Peer System for Range Queries

黃曉梅(Hsiao-Mei Huang)

指導教授 ： 莊裕澤

國立臺灣大學/管理學院/資訊管理學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.00634

摘要

點對點系統近年來成為大規模分散式資訊系統的強大平台，搜尋系統資源是此種平台的一種十分重要的功能，並且已經有不少的研究提出改善系統搜尋效能的方法；然而，點對點平台並不是對於任何類型的查詢都能有效的支援，例如對於範圍查詢的支援仍然有限。要在點對點平台上有效的支援範圍查詢，首先我們必須解決影響效能的相關問題﹕系統內部的高通訊成本、點與點之間的負載不平衡以及維持系統裡物件的有效性。Donuts是滿足上述效能要求的點對點範圍查詢系統，它可以維持物件的有效性及有效地支援範圍查詢，利用群組化的概念來解決地域鄰近性與負載平衡之間的衝突；然而Donuts提供的搜尋演算法-“先搜尋鄰居列表與群組成員鄰居列表、再利用繞路表搜尋”的方式所花費的搜尋成本過於昂貴，且模擬的搜尋樣式與真實點對點系統的情形並不相符。

在本篇論文裡我們提出與實際搜尋行為較相似的搜尋樣式-“考量地域性與物件受歡迎程度的搜尋樣式”，並以之為基礎研究搭配Donuts特性的搜尋與快取策略。我們的實驗結果證明了Chordal Ring是適合Donuts的系統資料結構，並且比較了傳統快取方法-本地端快取與沿路快取的搜尋效能；最後比較搭配Donuts特性的合作式鄰居搜尋的快取方式與傳統快取的效能，深入討論最適合的搜尋與快取策略。

關鍵字

點對點網路 ； 範圍查詢 ； 鄰近性 ； 群組化 ； 負載平衡 ； 快取

並列摘要

Peer-to-peer systems have emerged as a powerful platform for large-scale distributed information systems in recent years; important functionalities, such as searching, have been added to improve the system's lookup capability. The efficient support of range queries in a P2P system is still a challenging problem. To resolve this problem, some other related issues must first be addressed, such as high communication overheads, load imbalance among peers and preservation of object availability. Donuts satisfies above requirement and maintain object availability and effectively range queries. Within a grouping environment, peers are divided into several groups to provide the flexibility of proximity and feasibility of load balance in a range queries system. However, Donuts' search algorithm with cooperative search is not efficient. The search cost is tremendous. Also the query pattern in Donuts is not similar to real word.

This thesis provide more factual query pattern to simulate search behavior. Considering locality and popularity, we try to find the best search and cache strategy. The result of experiment prove that chordal ring is the better system data structure. We also compare the performance of local cache with the one of cache by path. Finally, we compare cooperative neighbor cache with traditional cache and make a conclusion for best search and cache method.

並列關鍵字

P2P network ； range query ； proximity ； grouping ； load balance ； cache

參考文獻

[5] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari

[6] Antony Rowstron and Peter Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proceeding of IFIP/ACM International Conference on Distributed Systems Platforms, pages 329–350, November 2001.

[10] S. Patro and Y. C. Hu. Transparent query caching in peer-to-peer overlay networks. In Proceedings of International Parallel and Distributed Processing Symposium (IDCS’03), 2003

[12] M. Kacimi and K. Yetongnon. Evaluation study of a distributed caching based on query similarity in P2P network. In Proceedings of The 2nd International Conference on Scalable Information Systems (INFOSCALE 2007), 2007

[13] L. Fan, P. Cao, J. Almeida and A. Z. Border. Summary Cache: A scalable wide-area Web cache sharing protocal. In IEEE/ACM Transactions on networking, 8(3): 281-293, 2000