KiZUNA: P2P 1,a) 1 1 1 P2P KiZUNA KiZUNA Pure P2P P2P 1 Skip Graph ALM(Application Level Multicast) Pub/Sub, P2P Skip Graph, Bloom Filter KiZUNA: An Implementation of Distributed Microblogging Service over P2P Networks HARIMA Yuta 1,a) ABE Kota 1 ISHIBASHI Hayato 1 MATSUURA Toshio 1 Abstract: This paper describes a design of KiZUNA, a pure P2P-based microblogging service. Subscription and distribution of messages are implemented using ALM (Application Level Multicast) over a skip graph, a structured P2P network. Hashtags, full-text search, search stream, and replica management are also discussed. Keywords: Microblogging, Pub/Sub, P2P, Skip Graph, Bloom Filter 1. Twitter Weibo Twitter 1 Graduate School for Creative Cities, Osaka City University a) harima@sousei.gscc.osaka-cu.ac.jp Twitter P2P KiZUNA KiZUNA Pure P2P KiZUNA Twitter 1
Publish/Subscribe KiZUNA P2P 2 Publish/Subscribe KiZUNA 2. KiZUNA 1 Skip Graph BF Skip Graph BF Skip Graph Skip Graph Skip Graph DDLL 2.1 Skip Graph Skip Graph 1 w w =2 Skip Graph i w i =2 i 0 i (> 0) i Skip Graph IP u i u.left[i], u.right[i] Skip Graph O(log n) Skip Graph ALM (Application Level Multicast) ALM O(log n) 2.2 DDLL 2.1 Skip Graph Level 3 Level 2 Level 1 Level 0 Membership Vector Fig. 1 3 3 1 5 5 8 5 8 11 11 18 18 18 3 5 8 11 18 000 100 110 010 101 Skip Graph Example of a Skip Graph. DDLL [1] DDLL KiZUNA Skip Graph DDLL DDLL X X k u u u u q u q k 2.3 Skip Graph Skip Graph Skip Graph [2] (value) value Skip Graph u i (i >0) [u.left[i + 1],u.left[i]) value *1 1 Skip Graph O(log n) *1 [2] 2
2.4 BF Skip Graph BF Skip Graph [3] Skip Graph value Bloom Filter Bloom Filter n-gram Bloom Filter u i(i >0) [u.left[i+1],u.left[i]) Bloom Filter OR Bloom Filter q Bloom Filter q q Bloom Filter q BF Skip Graph AND Bloom Filter Bloom Filter Bloom Filter O(log n) BF Skip Graph Skip Graph 3. P2P Megaphone[4] Cuckoo[5] 3.1 Megaphone Megaphone Pure P2P Pastry ALM Scribe Web 3.2 Cuckoo Cuckoo P2P 2 Gossip Cuckoo P2P Megaphone 4. KiZUNA 4.1 Twitter KiZUNA KiZUNA Twitter KiZUNA Twitter @ + Mention @ + p q q p q # + KiZUNA Pure P2P u u u u 4.2 P2P KiZUNA 4 P2P SG msg (Skip Graph) 3
SG stream SG full DHT (BF Skip Graph) (BF Skip Graph) (Skip Graph) KiZUNA P2P Skip Graph KiZUNA P2P PIAX[6] PIAX DHT Skip Graph 4.3 Twitter KiZUNA KiZUNA UID UID 4.11 u UID u.uid 4.5 4.13 4.4 u P2P u UID 4.5 u u u DHT u u.uid u u u UID Level 0 購読者 UID 部乱数部 u 1, 0 u 1, 38 u 2, 12 u 2, d8 u 2, fa u 1 u 3 u 3 u 4 u 1 u 1 を購読するユーザ集合 u 2 を購読するユーザ集合 u 3, 0 u 3, cc u 3 u 4 u 3 を購読するユーザ集合 2 SG msg 0 Fig. 2 Structure of SG msg (Level 0). u DHT u.uid u 4.6 / KiZUNA Skip Graph (SG msg ) ALM 2.1 Skip Graph ALM KiZUNA (1) u SG msg u (2)u u ALM u [7] 4.10 u u u (u.uid, rnd) 1 SG msg rnd 1 rnd RNDMAX 2 (uid 1, rnd 1 ) (uid 2, rnd 2 ) uid 1 uid 2 rnd 1 rnd 2 u [(u.uid, 1), (u.uid, RNDMAX)] u (u.uid, 0) (1) u u u (2) u u 4.11 SG msg 2 0 u 1 u 3 u 2 u 3 u 4 u 1 u 3 u 4 (u 2, 0) u 2 4
q SG msg (q.uid, rnd) 4.7 4.1 u m @ +h h h u u h u h u u h u u h u h SG stream h h SG stream h h m h m h @ +h m 4.11 4.8 SG msg h t h # +t t (u.uid, rnd) m t SG msg [ # +t, # +t] ALM m h m # +t m 4.9 m m m del m m del m del m m del m del m 4.10 u u 4.5 u u u u u u u SG msg [(u.uid, 0), (u.uid, RNDMAX)] u v SG msg (v.uid, rnd) v r u u r DDLL SG msg u p 0 p k 2.2 p (u.uid, any) u r r k k r u p p UID SG msg u q q q u q SG msg UID 4.11 1 BF Skip Graph SG full 5
n-gram Bloom Filter BF Skip Graph u u u SG full KiZUNA SG msg u t SG full t SG msg 0 4.10 t k k t SG full u SG full u Bloom Filter SG full 4.7 u SG full u SG full 4.3 Bloom Filter Bloom Filter Bloom Filter Bloom Filter 4.12 [3] P2P BF Skip Graph 4.1 BF Skip Graph Bloom Filter m m Bloom Filter BF Skip Graph SG stream u SG stream u.uid 4.13 P2P UID DHT DHT DHT put DHT 5. KiZUNA P2P PIAX[6] PIAX DDLL DDLL Skip Graph Skip Graph BF Skip Graph KiZUNA 6. P2P KiZUNA KiZUNA P2P DTN (Delay/Disruption Tolerant Network) JSPS 24500089 [1] DDLL Vol. 2010-DPS-144, No. 1, pp. 1 8 (2010). [2] Abe, K., et al.: Aggregation Skip Graph: A Skip Graph Extension for Efficient Aggregation Query over P2P Networks, International Journal on Advances in Internet Technology, Vol. 4, No. 3, pp. 103 110 (2012). [3] P2P Skip Graph Bloom Filter Vol. 2011-DPS-146, No. 28, pp. 1 8 (2011). [4] Perfitt, T. et al.: Megaphone: Fault Tolerant, Scalable, and Trustworthy P2P Microblogging, Proc. of 2010 5th Intl. Conf. on Internet and Web Applications and Services, IEEE, pp. 469 477 (2010). [5] Xu, T. et al.: Cuckoo: Towards Decentralized, Socio- Aware Online Microblogging Services and Data Measurement, Proc. of 2nd ACM Intl. Workshop on Hot Topics in Planet-scale Measurement, ACM, pp. 4:1 4:6 (2010). [6] PIAX Inc.: PIAX. http://www.piax.org/ (2013 12 19 ). [7] Pub/Sub Vol. 113, No. 364, pp. 41 46 (2013). 6