第5讲-P2P网络的增强机制

P2P网络的增强机制

1在完成核心、基础部件之后，P2P网络还应该是一个高效、高可用的分布式网络，为提高性能所要做的工作，统称为“P2P增强机制”2章节内容5.1P2P系统的性能5.2复制与缓存5.3分片5.4负载均衡、异构性与热点问题5.5拓扑一致性问题35.1P2P系统的性能结点度：通常为路由表项数，一个结点连接到的其它结点数，也称“邻居数”。结点度决定了每个P2P结点所要维护的路由表项数，也就决定了结点自适应工作的开销，并且对于整个网络的连通度有基础性作用定位效率：定位任意一个结点或者数据对象所需要走过的覆盖网路由跳数，或理解为任意一条消息从源结点出发要到达目的结点所走过的覆盖网跳数。P2P网络最重要的外在性能4定位时延：定位所需要的时间，反映了真正的物理网工作情况，为简化，通常用物理跳数（如IP跳数）近似Stretch(伸展性)：描述P2P覆盖网与物理网之间一致性程度的主要参数，通常定义为Stretch=物理网跳数/覆盖网跳数，也可以用时延来定量定义异构性：反映P2P网络中结点能力的差异，开发异构性的目的是为了充分利用结点能力5负载均衡：数据对象在网络结点中分布得是否均匀，以及每个结点为其他结点消息路由所承担的负载是否均衡，由分布式散列表所决定。对均衡的理解有两种态度：“平均”或“各尽所能”查询负载：为查询一个数据对象，P2P网络需要付出的开销，即需要路由多少消息，也是P2P网络的重要外在性能6自适应开销：随着新结点不断加入、旧结点不断离开或失效，为维护网络拓扑结构和保持结点状态更新所需要的消息，用以衡量P2P网络动态结点算法的工作效率可扩展性：当P2P网络规模增大、结点增多时，是否还能正常工作，其他各项性能发生的变化是否仍然合理、可以接受。可扩展性是衡量一个分布式系统性能的关键属性7可用性：表示P2P网络中一个数据对象能被获取到的概率（包括副本）容错性：含义广泛，粗略地讲表示P2P网络对错误行为的容忍程度匿名性：P2P网络能否保护用户的隐私和重要信息安全性：P2P网络在一个不可靠的环境中能否正常工作，在受到恶意结点攻击时能否正常工作，以及应对攻击的合理措施85.2复制与缓存P2P系统中复制技术的优点效率：通过复制数据对象到多个结点，可以有效地减少获取该对象所需要的路由跳数可用与容错：复制是一种冗余技术，可提高可用性与容错性复制技术的问题冗余代价副本一致性问题缓存：一般采用路径缓存9从可用性角度看复制假设要求某个数据对象的可用性为a，单个副本的可用性为p，则副本数r应该为：计算的可用性为：a=1-(1-p)^r，从而有若p=0.9，要求可用性a=0.999，则只需要复制3份10无结构P2P网络的复制方案均匀复制：所有数据对象复制份数相同比例复制：数据对象复制的份数正比于其被查询到的概率，越热门的数据复制份数越多方根复制：数据对象复制的份数正比于它被查询到的概率的平方根问题：哪种方案好？评估数据对象的平均查询距离和副本的利用率11无结构P2P网络的复制方案假设网络中共有n个节点、m个数据对象,qi表示对第i个数据对象的查询概率。设R代表系统资源总量(即所有节点可存放的对象数总和），设ρ代表系统资源在节点上的平均分配量，则ρ=R/n。。ri：复制份数ri相关于复制策略Ai：数据对象i的平均查询距离Ai

=n/ri,i∈{1,m}A：整网的平均查询距离

A=ΣriAi/R(所有key查询的平均距离）Ui：数据对象i的一个副本平均被查询到的次数（利用率）12方根复制能产生最小的平均查询距离，而其利用率介于均匀复制、比例复制之间且可以接受，综合性能最好方根复制的实现方法：每当完成一次查询后，对象i的cn/ri个副本被复制到网络不同结点上以符号ri’表示ri的导数，有对该式积分可知13结构化P2P网络中的复制和缓存普遍采用“ID邻近复制”：ID邻近的结点能很快找到；这些结点均匀分布在网络中，同时失效的可能性很小，数据可用性高数据缓存在查询路径上：提高定位和数据获取速度CAN的“隐式”复制方法：多空间、多散列、区域超载OceanStore的“冗余编码”技术，次要副本复制PAST的“副本转移”与“文件转移”技术145.3分片传统的分片方法把一个文件分成多个等大小的片，将这些分片分散存储或者分开传输，从而获得并发效果新的分片技术如“冗余编码”除了提高效率外，能以适度的存储开销获得可用性、容错性的大幅提升15冗余编码技术P：源数据可用性n：编码后的数据块数k:重构源数据需要的块数N：网络中计算机（结点）总数M：当前不可用的计算机（结点）总数16在数据可用性上冗余比复制的优势设网络中共有100万台计算机，其中10%不可用（失效），即N=100万，M=10万。假设对源数据只以复制的方法存储2个副本，那么其可用性是1-0.1*0.1=0.99若使用冗余编码，在消耗同样的存储容量情况下，冗余编码率应该为r=1/2（因为复制了2个副本）。如果将源数据编码为64块(n=64)，需要其中32块来重构（k=32)，低入P中可得17冗余编码vs.复制图7.3-3：横坐标为服务器可用性（即单个结点可用性），纵坐标为“Replication/StretchRatio”，Replication为复制的存储开销（即副本数），StretchRatio为冗余编码的存储开销(编码率的倒数）。三条曲线分别表示可用性为0.999、0.9999、0.99999。服务可用性高有利于复制，数据可用性高有利于冗余。因此，冗余宜在服务器可用性低并且数据可用性需求高时使用(OceanStore)。18冗余编码技术的优缺点优点：服务器可用性较低、所要求的数据可用性较高时，冗余编码的效果好，可以在同样的开销下将可用性提高很多个数量级缺点：系统实现代价高；从多个节点下载多个分块所需时延可能很大（取决于最远的那个分块）更新文件困难结论：除非对数据可用性要求极高，并且网络环境非常不可靠时考虑使用冗余编码，否则，简单的复制方法是正确的选择。195.4负载均衡、异构性与热点问题P2P网络的负载均衡本质上来源于其分布式散列表，但没有考虑结点异构性，并未做到“各尽所能”异构性网络异构性：在像Internet这样的大规模网络中，任意两个结点间的连接，在传输时延和带宽上各不相同，在覆盖网中的逻辑连接差别更大节点异构性：网络结点的带宽、存储容量、处理速度的差异20设计利用异构性结构化之P2P网络如Chord的设计中，采用每个实际的网络结点负责多个“虚拟服务器”的方法，并在某个结点负载过重时转移到负载较轻的结点。[Raoetal.,2003]设计了静态环境下的负载均衡方案(virtualserver)；[Godfreyetal.,2004]在此基础上设计了动态环境下的负载均衡算法[Raoetal.03]Ananth

Rao,Karthik

Lakshminarayanan,Sonesh

Surana,RichardKarp,IonStoica.LoadBalancinginStructuredP2PSystems.InIPTPS2003,pp.68-79.[Godfreyetal.04]BrightenGodfrey,Karthik

Lakshminarayanan,RichardKarp,IonStoica.LoadBalancinginDynamicStructuredPeer-to-PeerSystems.InINFOCOM2004,pp.46-50.无结构P2P网络通过使用“超结点+普通结点”的双层结构开发了结点的异构性21VirtualServersChordRingContiguousregionoftheIDspace.Eachnodecanberesponsibleformanyvirtualservers.UsedinChord/CFS.NodeANodeCNodeB22VirtualServersContiguousregionoftheIDspace.Eachnodecanberesponsibleformanyvirtualservers.UsedinChord/CFS.ChordRingNodeANodeCNodeB23StaticMappingofVirtualServersHeterogeneity:Numberofvirtualserversisproportionaltonode’scapacity.T=50T=15T=35ChordRingHeavyL=45L=31L=3L=41NodeCNodeBNodeA202011310153024ChordRing20113102015DynamicMappingofVirtualServersAllowdynamicre-mappingofloadinasystem.Virtualserveristhebasicunitofloadmovement.NodeANodeCNodeBT=50T=15T=35HeavyL=45L=31L=3L=413025DynamicMappingofVirtualServersAllowdynamicre-mappingofloadinasystem.Virtualserveristhebasicunitofloadmovement.ChordRing20113103015NodeANodeCNodeBT=50T=15T=35L=45L=31L=14L=3026LoadBalancingScheme-DirectoriesDirectoryNodesAllnodes,heavyorlight,periodicallyreportinformationtodirectories.SoftStateDirectoriesperiodicallycomputethetransferscheduleandreportitbacktothenodes,whichthendotheactualtransfer.HeavynodesH3H2H1DirectoriesD1D2L4LightnodesL1L2L3L4L527Unload2576410843T=6,L=7T=20,L=17T=24,L=25ABCPoolT=6,L=5AT=24,L=2228Insert5764108423ABCT=24,L=22T=20,L=17T=6,L=5T=20,L=20PoolT=24,L=2429Gia——异构性自适应的无结构P2P网络模型Gia：无结构P2P网络，充分利用节点异构性，优化网络拓扑Gia是SIGCOMM’03会议上由P2P领域的多位专家提出的无结构P2P网络理论模型，对Gnutella进行改进：拓扑自适应：核心设施，其作用在于不断调整无结构P2P网络的组织方式，让高能力结点拥有高的连接度，形成“集群效应”，以开发网络异构性流控制：每个结点周期性地发给邻居正比于自身能力的一定数量的令牌，只有拥有令牌的邻居可以向自己发送消息一跳复制：每个结点动态地维护其邻居结点所拥有数据的索引，以提高查询速度30Gia拓扑自适应算法（邻居选择）31热点问题热点问题：网络领域中“flashcrowds”，形象地描述某个网络资源在极短的时间内，发生不可预料的、大量的、快速增长的获取请求，导致难以应付的拥挤解决方法：结构化P2P网络中的对象索引路径缓存、Gia中的一跳复制（对索引的热点问题）；传统的数据复制或缓存（对象本身的热点问题）；32用P2P技术来解决C/S热点问题PROOFS(P2PRandomizedOverlaystoObviateFlash-crowdSymptoms)[Stavrouetal.,2004]为消除热点现象而构建的无结构P2P随机覆盖网随机交换拓扑，减少查询热点随机、局部性查询相结合[Stavrouetal.04]Angelos

Stavrou,DanRubenstein,Sambit

Sahu.ALightweight,RobustP2PSystemstoHandleFlashCrowds.IEEEJournalonSelectedAreasinCommunications,2004,Vol.22,No.1,pp.6-17.33ShuffleShufflingisusedtoproduceanoverlaythatis“well-mixed”intheaclient’sneighborsareessentiallydrawnatrandomfromthesetofallclientsthatparticipateintheoverlay.Thereisnoattempttooptimizetheoverlaysuchthatneighborsaretopologicallyadjacent.

PROOFS’scalabilityreliesonthefactthattheobjectaclientsearchesforisalsobeingsearchedforbymanyotherclientsinthenetwork.In34BackSlash:handleflashcrowdsPeer-to-PeerCachingSchemestoAddressFlashCrowdsIPTPS2002BackSlash:acollaborativewebmirroringsystemrunbyacollectiveofwebsitesthatwishtoprotectthemselvesfromflashcrowdsBackSlashvs.PROOFSStructuredvs.UnstructuredHandleflashcrowdsinthesamewebserver(C/SP2P)vs.Handleflashcrowdsforpopularobjects(P2P).35BackSlash：解决FTP/HTTP分发问题问题描述：FTPTraffic:17%oftotaltraffic.78%ofthemarelargerthan10MB.11%ofthemwerefailedduringtransfer.ThelargefilestransferredbyFTPgeneratemuchtraffic,

andmanyofthemtakeslongtime.P2P技术引入：大文件下载问题热点缓存，减轻流量拥塞减小时延，提高传输速度

解决方法：构建一个BackSlash[Stadingetal.,2002]结构化P2P网络来主动缓存“热点对象”，并通过“重定向”方法将大量的查询请求分散到缓存的多个副本中36Os1ConnectivityCloudPeer1OS1

,OS2

:Smallobject

OL1,OL2

:LargeobjectBackSlashModel

HTTP/FTPServerALocalAreaNetworkPeer2Peern,Os2OL1OL2OL1OL1Peer-to-PeerStorageOs1OL1WebProxyCache

withFTPsupportingmoduleHTTP/FTPServerBOs1

Cachewithtwo-layerstorage37实现架构2newcomponentstosupportFTPandlargefiles.PreservetransparencyofFileLocationFTPCacheDaemonStorethestateofFTPconnectionMaketheURLoffilestransferredbyFTPCheckconsistency.P2PStorageManagerControlitsownstorage.Managedbyobjecttableincentralcache.HTTPCacheDaemonFTPCacheDaemonObjectTable

Storage

Manager

FTP/HTTPServerFTP/

HTTPClientP2PStorageManagerFTP/

HTTP

ClientP2PStorageManager134442ControlDataControlandDataconnectionbetweencomponents3839RequestFileCheckProtocolLookupObjectTableCheckConsistencyCheckCachedLocationOpenFTPcontrolconnectionstobothpeerwhichhasfileandpeerwhichrequestsis.MakeFTPdataconnectionsbetweentwothepeers.HTTPFTPnotcachedcachedinconsistentconsistentpeerHandlearequest

likewebproxycacheTransferfileCheckFileSizeCentralcacheopensdataconnectiontoclient.centralserverUpdateObjectTableTransferfileOpensdataconnectionbetweenserverandclientTransferfileServeropensdataconnectiontocentralcache.UpdateObjectTablesmallLargeCentralcacheopensdataconnectiontoclient.TransferfileUpdateObjectTable流程图405.5拓扑意识和一致性问题处理一致性问题的三种传统方法PRS-邻近路由选择(proximityrouteselection)：路由的下一跳选择不仅仅考虑逻辑距离，还根据邻居结点的时延信息进行折中.如CFSPNS-邻近邻居选择(proximityneighborselection)：路由表中维护一定数量物理上邻近、时延很小的邻近邻居，如Pastry的邻居集PIS-邻近ID选择(proximityidentifierselection)：也称为“地理规划”(geographicalayout)，让映射到的ID能反映结点的地理信息或物理网位置信息。最先使用该方法的是“有拓扑意识的CAN”。在一维时，可采用HilbertCoding。41CFS的下一跳选择——邻近路由选择CFS在定位过程中，尽量选择那些时延小、在底层物理网中靠近的结点作为下一跳。CFS论文中称之为ServerSelection.用表示当前结点n取ni作为下一跳的预计开销，有其中表示n取ni作为下一跳后估计剩余的Chord跳数，di表示n到ni的时延，d’表示n所取的每跳平均时延(经验值)。42时延是通过finger建立时得到，从而没有引入extrameasurementsforthelatency若满足三角测量a+b>c，时延估计的效果为更好详细分析及证明见[Dabeketal.01]FrankDabek,M.Frans

Kaashoek,DavidKarger,RobertMorris,IonStoica.Wide-areacooperativestoragewithCFS.InSOSP2001,pp.202-215.以及FrankDabek的硕士论文FrankDabek

的个人主页/research.html博士论文下载：2005

ADistributedHashTable

(pdf)

FrankDabek.PhD.Thesis(MIT)43Pastry的路由表构造——邻近邻居选择当P2P路由局限在某个区域内时，物理网和覆盖网之间的差别不会太大，即通过“局部性”带来一致性Pastry中，每次为新结点X构造路由表时都进行“邻近邻居选择”，则在三角关系近似满足的情况下，可以推出：X从自举结点A中复制第0行作为自己的路由表第0行、从A中复制邻居集作为自己的邻居集、并用邻居集修正过第0行后，X的路由表第0行结点跟X在物理上都是邻近的随着跳数的增加，邻近邻居选择的效果会减弱44Pastry的“邻近邻居选择”。X为新加入结点，A为其自举结点，Level表示路由表行数或路由跳数，圆弧和半径表示物理网距离或时延（图片来自[Pastry01]）。

45希尔伯特编码——邻近ID选择Hilbertcoding：用一条曲线无交叉地穿过一个多维空间的所有单元格，沿着曲线走向，从小到大给每个格子编码，每个大格子里的小格子编码都是紧邻的。该曲线称为“希尔伯特曲线”；将希尔伯特曲线的首尾相连构成一个环，相当于一个使用希尔伯特编码作为散列函数的环结构希尔伯特编码与SHA相比虽然不安全，但能保证在环上邻近的结点在地理上也是邻近的46左图为穿过2维空间的希尔伯特曲线，右图为用希尔伯特曲线贯穿左图形成的数值环47Hilbert编码的性质如果两个结点编码值(nodeID)相差1，它们在地理上一定是紧密相邻的两个结点的编码值相差越小，即它们的nodeID前缀比特匹配越多，则在物理上越临近，反之却未必如果要从编码值完整地反映出结点的邻近关系，必须有一个算法对编码值反运算，从而得到结点的地理位置希尔伯特编码是可调节的：编码越长则划分越细，反映出的位置信息越多48均衡希尔伯特编码：虽然地理位置是均衡分布的，但网络结点在地理上的分布是不均衡的，因此人为地划分地理区域，使网络结点分布越密的区域其区域编码越短49LMT——动态邻近邻居选择location-awaretopolotymatchingtechnique，位置意识的拓扑匹配技术：在维持原查询范围和减少查询回复时间的前提下，通过主动断开低效连接和冗余连接并选择物理上更接近的结点作为覆盖网邻居，来缓解无结构P2P覆盖网与其底层物理网之间的不一致性，尽量减少不必要的通信开销Liuetal.04(a)]YunhaoLiu,XiaomeiLiu,LiXiao,LionelM.Ni,XiaodongZhang.Location-AwareTopologyMatchinginP2PSystems.InINFOCOM2004,pp.2220-2230刘云浩

1995年毕业于清华大学自动化系，获工学学士学位；在北京外国语大学获文学硕士学位；并在美国密歇根州立大学计算机系获得硕士和博士学位。50无结构P2P网络低效的三个原因无结构P2P覆盖网上的消息路由常常在物理网上走过太多重复或者完全不必要的路径，既导致通信开销增加，又导致通信时延变长同样的查询消息常常沿多条路径到达同样的目的地，而其中只有一条是有意义的两个邻居结点收到同样的查询消息时，仍会互发消息，明显多余51S与其邻居N1、N2及其两跳邻居P的四种关系建立模型时延分析：TTL=2，通过时戳来计算52LMT使用的三种主要操作第一种操作：让每个结点S周期性地洪泛广播一种“两跳探测消息”(TTL2-Detector)，S在消息中填入自己的IP和发送时间，第一跳的邻居也填入信息第二、三种操作：两跳后的P可以根据信息比较出覆盖网连接的合理性，从而主动断开低效连接和冗余连接，建立高效连接53LMT的三种操作并未减小无结构P2P网络的洪泛查询范围，但通过主动断开低效连接和冗余连接、主动建立高效连接，一定程度上缓解了覆盖网与底层物理网之间的不一致性，从局部性的角度看确实减少了重复的通信开销；但频繁断开和建立连接，加剧了P2P网络的动态性54思考题：1、Sigcomm02[Cohen2002]建立的无结构P2P网络复制的模型指出三种复制模型。请思考下为何他会提出方根模型？他的Intuition在哪里？还有第四种复制模型吗？2、在什么情况下适用冗余编码而不用复制技术？3、P2P是一种思想，可以用P2P来解决热点问题。此外，P2P的特性还适合解决什么问题？4、Gia提出自适应、流控及一跳复制这些技术改进了无结构的各方面的效率。这些技术其实都是不太复杂，关键在于，如何才能够看到Gnutella无结构拓扑所存在的问题。如果我们今天来看P2P网络及其应用，我们还能够看到什么问题？555、阅读CFS论文，理解其对时延问题的分析。http:///research.html博士论文下载：2005

ADistributedHashTable

(pdf)

FrankDabek.PhD.Thesis(MIT)6、邻近ID技术存在的问题是什么？它带来了负载不均衡，如何解决？7、理解LTM的研究问题的着眼点以及建立模型解决问题的研究方法。56学期论文idea之四：复制/查询优化AbsenceofEvidenc