分布式在線社交網(wǎng)絡(luò)數(shù)據(jù)存儲(chǔ)及優(yōu)化技術(shù)研究.pdf

1、近年來，在線社交網(wǎng)絡(luò)（Online Social Network,OSN）取得了巨大成功，在全球范圍內(nèi)擁有數(shù)十億用戶。通過 OSN，用戶可以結(jié)交新的朋友或與自己的朋友共享信息。目前比較流行的商用OSN包括 Facebook，Twitter，人人網(wǎng)，新浪微博，騰訊微信等，它們都采用了集中式數(shù)據(jù)存儲(chǔ)架構(gòu)，所有的用戶數(shù)據(jù)集中存儲(chǔ)到服務(wù)提供商所運(yùn)維的服務(wù)器上。服務(wù)提供商可以使用和分析這些數(shù)據(jù)，甚至直接將之出售給第三方，破壞了用戶隱私。因此，這種

2、集中式在線社交網(wǎng)絡(luò)（Centralized Online Social Network,COSN）中存在嚴(yán)重的用戶數(shù)據(jù)隱私泄露問題，已經(jīng)引起了廣泛的關(guān)注。
　　在此背景下，分布式在線社交網(wǎng)絡(luò)（DecentralizedOnline Social Network,DOSN）被提出來解決上述用戶數(shù)據(jù)隱私泄露問題。盡管DOSN還不如COSN流行和成熟，但是業(yè)界對它的研究非?；钴S，正處于快速發(fā)展時(shí)期。在 DOSN中，為了保護(hù)隱私，用戶數(shù)據(jù)

3、繞過服務(wù)器直接在朋友圈內(nèi)存儲(chǔ)和轉(zhuǎn)發(fā)。DOSN雖然能防止服務(wù)提供商泄露用戶隱私數(shù)據(jù)，但是存在數(shù)據(jù)可用性低下的問題：當(dāng)某一用戶處于離線狀態(tài)時(shí)，其它用戶不能訪問存儲(chǔ)在該離線用戶處的數(shù)據(jù)。為了在數(shù)據(jù)隱私保護(hù)約束條件下提高數(shù)據(jù)可用性，必須設(shè)計(jì)適用于DOSN場景的數(shù)據(jù)存儲(chǔ)方案及相應(yīng)的優(yōu)化策略，這是目前DOSN研究中的最大挑戰(zhàn)之一。
　　DOSN具有如下特點(diǎn)：1）用戶動(dòng)態(tài)性高；2）接入終端存儲(chǔ)資源有限；3）大部分用戶的朋友圈不大；4）社交數(shù)據(jù)以

4、小數(shù)據(jù)為主，且很少修改。本文通過深入研究已有的DOSN數(shù)據(jù)存儲(chǔ)技術(shù)和存儲(chǔ)優(yōu)化相關(guān)工作發(fā)現(xiàn)，已有工作主要關(guān)注用戶動(dòng)態(tài)性，而忽略了其它特點(diǎn)對數(shù)據(jù)存儲(chǔ)優(yōu)化目標(biāo)的影響。
　　針對現(xiàn)有工作的不足，本文系統(tǒng)地研究了以數(shù)據(jù)隱私保護(hù)約束下提高數(shù)據(jù)可用性為主要目標(biāo)的DOSN數(shù)據(jù)存儲(chǔ)和存儲(chǔ)優(yōu)化問題，主要包括如下幾個(gè)方面：
　　1.存儲(chǔ)容量敏感的DOSN數(shù)據(jù)可用性建模與分析
　　已有的DOSN數(shù)據(jù)存儲(chǔ)方案通常假設(shè)朋友總是能為用戶提供足夠的存

5、儲(chǔ)容量保存用戶發(fā)布的數(shù)據(jù)，然而，這個(gè)假設(shè)在 DOSN中是不合適的。為了保證不泄露用戶隱私，未受保護(hù)的用戶隱私數(shù)據(jù)只能存儲(chǔ)在朋友圈內(nèi)。而如下原因?qū)?dǎo)致朋友圈內(nèi)的總存儲(chǔ)容量有限：1）在線朋友數(shù)量有限；2）DOSN用戶通常使用移動(dòng)智能設(shè)備，它們的存儲(chǔ)容量通常有限。直觀地，有限的朋友圈總存儲(chǔ)容量降低了數(shù)據(jù)可用性。但是僅僅知道這一粗略結(jié)論是不夠的，我們還希望獲悉存儲(chǔ)容量對數(shù)據(jù)可用性的影響程度，以確定是否有必要進(jìn)行數(shù)據(jù)存儲(chǔ)優(yōu)化。因此，在重新設(shè)計(jì) D

6、OSN數(shù)據(jù)存儲(chǔ)方案之前，有必要定量分析朋友圈可貢獻(xiàn)的總存儲(chǔ)容量與所能達(dá)到的數(shù)據(jù)可用性之間的關(guān)系，這是本文要解決的首要問題。
　　針對此問題，本文提出了一個(gè)存儲(chǔ)容量敏感的數(shù)據(jù)可用性模型，深入分析了朋友圈可貢獻(xiàn)的總存儲(chǔ)容量與所能達(dá)到的數(shù)據(jù)可用性之間的定量關(guān)系。此外，朋友圈內(nèi)的在線朋友高度動(dòng)態(tài)變化，影響了朋友圈可貢獻(xiàn)的總存儲(chǔ)容量，進(jìn)而導(dǎo)致數(shù)據(jù)可用性也高度動(dòng)態(tài)變化。針對這一問題，本文通過預(yù)測朋友圈實(shí)時(shí)總存儲(chǔ)容量預(yù)測實(shí)時(shí)數(shù)據(jù)可用性，進(jìn)一步研

7、究了朋友圈總存儲(chǔ)容量與所能達(dá)到數(shù)據(jù)可用性之間的動(dòng)態(tài)變化關(guān)系。最后，本文還進(jìn)行了大量實(shí)驗(yàn)，驗(yàn)證了存儲(chǔ)容量敏感的數(shù)據(jù)可用性模型的有效性?；诖鎯?chǔ)容量敏感的數(shù)據(jù)可用性模型，給定預(yù)期數(shù)據(jù)可用性可以確定朋友圈所需的最小總存儲(chǔ)容量，進(jìn)而可以確定每個(gè)朋友所需貢獻(xiàn)的平均最小存儲(chǔ)容量，為應(yīng)用程序存儲(chǔ)容量的分配提供依據(jù)；反之，給定朋友圈總存儲(chǔ)容量，可以確定朋友圈所能達(dá)到的最大數(shù)據(jù)可用性，從而可以確定預(yù)期數(shù)據(jù)可用性是否能夠得到滿足，并指導(dǎo)下一步的數(shù)據(jù)存儲(chǔ)方案

8、設(shè)計(jì)。
　　2.云輔助的DOSN數(shù)據(jù)存儲(chǔ)方案Cadros
　　如上文所述，DOSN中，為了保證用戶隱私不被泄露，數(shù)據(jù)在未受保護(hù)的情況下只能冗余存儲(chǔ)在朋友圈內(nèi)。但是 DOSN是一個(gè)高度動(dòng)態(tài)的網(wǎng)絡(luò)，用戶可以隨時(shí)添加和刪除朋友，且朋友可以隨時(shí)上線和下線，所以朋友圈內(nèi)在線朋友集合和所貢獻(xiàn)的總存儲(chǔ)容量是有限且動(dòng)態(tài)變化的。如果僅依賴朋友圈冗余存儲(chǔ)用戶數(shù)據(jù)，將不能獲得較高的數(shù)據(jù)可用性。以數(shù)據(jù)隱私保護(hù)約束下提高數(shù)據(jù)可用性為主要目標(biāo)，設(shè)計(jì)適用

9、于DOSN的數(shù)據(jù)存儲(chǔ)方案是本文要解決的第二個(gè)關(guān)鍵問題。
　　針對該問題，本文基于存儲(chǔ)容量敏感的數(shù)據(jù)可用性模型，提出了一種云輔助的DOSN數(shù)據(jù)存儲(chǔ)方案Cadros，引入云服務(wù)器提高數(shù)據(jù)可用性。當(dāng)朋友圈不能滿足數(shù)據(jù)存儲(chǔ)需求時(shí)，將多余數(shù)據(jù)用糾刪碼技術(shù)分片編碼后存儲(chǔ)到云服務(wù)器中，且保證云服務(wù)器中存儲(chǔ)的數(shù)據(jù)片段數(shù)量不超過恢復(fù)原始數(shù)據(jù)所需要的數(shù)據(jù)片段數(shù)量，以防止云服務(wù)提供商獲得原始數(shù)據(jù)，從而保護(hù)了用戶數(shù)據(jù)隱私。本文定量研究了Cadros的數(shù)據(jù)

10、存儲(chǔ)能力，討論了Cadros的數(shù)據(jù)可用性，從理論上證明了Cadros方案的可行性和有效性；同時(shí)還建立了朋友圈內(nèi)朋友動(dòng)態(tài)行為的概率模型，通過預(yù)測朋友圈將來的數(shù)據(jù)存儲(chǔ)能力和存儲(chǔ)需求，建立了Cadros實(shí)時(shí)數(shù)據(jù)可用性預(yù)測模型，可以為下一步設(shè)計(jì)數(shù)據(jù)存儲(chǔ)策略提供依據(jù)。
　　3.社交數(shù)據(jù)在DOSN中的存儲(chǔ)優(yōu)化技術(shù)
　　上一研究中的實(shí)時(shí)數(shù)據(jù)可用性預(yù)測結(jié)果只是表明Cadros在給定朋友圈總存儲(chǔ)容量的前提下有能力達(dá)到相應(yīng)的數(shù)據(jù)可用性。朋友圈最

11、終是否能獲得預(yù)期的數(shù)據(jù)可用性還依賴于數(shù)據(jù)存儲(chǔ)策略。即使朋友圈能提供足夠的存儲(chǔ)容量，如果沒有一個(gè)好的數(shù)據(jù)存儲(chǔ)策略，也不能獲得理想的數(shù)據(jù)可用性。在Cadros數(shù)據(jù)存儲(chǔ)方案中，如何基于實(shí)時(shí)數(shù)據(jù)可用性預(yù)測結(jié)果，針對DOSN用戶行為特征，設(shè)計(jì)一個(gè)適用的數(shù)據(jù)存儲(chǔ)策略是本文要解決的第三個(gè)關(guān)鍵問題。
　　針對這一問題，本文進(jìn)一步優(yōu)化Cadros數(shù)據(jù)存儲(chǔ)方案，研究社交數(shù)據(jù)在DOSN中的存儲(chǔ)優(yōu)化技術(shù)，首先提出了一個(gè)開銷敏感的數(shù)據(jù)劃分方法和存儲(chǔ)策略，分

12、別確定存儲(chǔ)到朋友圈內(nèi)和云服務(wù)器中的數(shù)據(jù)，可充分利用朋友圈可用存儲(chǔ)容量，使系統(tǒng)開銷最?。蝗缓?，提出一個(gè)可用性驅(qū)動(dòng)的DOSN數(shù)據(jù)副本放置方法，合理地將數(shù)據(jù)放置到朋友圈內(nèi)，可實(shí)現(xiàn)預(yù)期的數(shù)據(jù)可用性，且能均衡系統(tǒng)負(fù)載，降低系統(tǒng)為實(shí)現(xiàn)數(shù)據(jù)可用性所造成的維護(hù)開銷。
　　4.社交數(shù)據(jù)在云服務(wù)器中的存儲(chǔ)優(yōu)化技術(shù)
　　如上文所述，Cadros數(shù)據(jù)存儲(chǔ)方案不僅將用戶數(shù)據(jù)冗余存儲(chǔ)在朋友圈內(nèi)，還在朋友圈不能滿足數(shù)據(jù)存儲(chǔ)需求時(shí)將一部分?jǐn)?shù)據(jù)存儲(chǔ)到云服務(wù)器

13、中。云服務(wù)器具有長期高可用的特點(diǎn)，因此云服務(wù)器上數(shù)據(jù)的可用性可近似認(rèn)為達(dá)到100％，不存在數(shù)據(jù)可用性問題。然而當(dāng)用戶訪問云服務(wù)器上社交數(shù)據(jù)時(shí)，卻存在訪問性能不高的問題。社交數(shù)據(jù)以小數(shù)據(jù)為主，并很少修改。云服務(wù)器通常采用傳統(tǒng)的分布式文件系統(tǒng)來存儲(chǔ)和管理用戶數(shù)據(jù)，在處理海量社交小數(shù)據(jù)時(shí)性能較低。如何提高云服務(wù)器中社交小數(shù)據(jù)的訪問性能是本文要解決的第四個(gè)關(guān)鍵問題。
　　為了解決這個(gè)問題，本文首先研究了分布式文件系統(tǒng)處理海量社交小數(shù)據(jù)的性

14、能瓶頸；然后提出了一種輕量級的文件系統(tǒng)iFlatLFS對社交小數(shù)據(jù)進(jìn)行優(yōu)化存儲(chǔ)和管理。iFlatLFS大大簡化了元數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)訪問流程。新的元數(shù)據(jù)總量僅占原元數(shù)據(jù)總量的一小部分，可以被全部緩存到服務(wù)器內(nèi)存中，消除了小數(shù)據(jù)尋址開銷，提高了性能。最后本文在CentOS5.5操作系統(tǒng)中實(shí)現(xiàn)了一個(gè)iFlatLFS原型，并集成到了開源分布式文件系統(tǒng)TFS中。本章最后進(jìn)行了大量實(shí)驗(yàn)，結(jié)果證明，iFlatLFS能夠優(yōu)化存儲(chǔ)海量社交小數(shù)據(jù)，大幅提高數(shù)

15、據(jù)訪問性能。
　　綜上所述，針對DOSN數(shù)據(jù)存儲(chǔ)及存儲(chǔ)優(yōu)化問題研究面臨的挑戰(zhàn)和現(xiàn)有工作的分析與總結(jié)，本文首先定量分析了朋友圈貢獻(xiàn)的總存儲(chǔ)容量與所能達(dá)到的數(shù)據(jù)可用性之間的關(guān)系；在此基礎(chǔ)之上，針對朋友圈總存儲(chǔ)容量有限所導(dǎo)致的數(shù)據(jù)可用性低下問題，提出了一種云輔助的DOSN數(shù)據(jù)存儲(chǔ)方案Cadros，解決了數(shù)據(jù)隱私保護(hù)問題，提高了數(shù)據(jù)可用性，并從理論上證明了Cadros方案的可行性和有效性，建立了實(shí)時(shí)數(shù)據(jù)可用性預(yù)測模型；然后研究了社交數(shù)據(jù)在