星期五, 十二月 09, 2005

[p2p研究笔记]随笔之一

做研究要发展趋势
p2p200是IEEE举办的关于p2p计算的会议,2005年的Topics如下

Security in P2P Systems

Trust and Reputation


Accountability


Applications


Overlay System Monitoring


Agents


Overlay Super Computers


Middleware


Overlay Architectures


Network Management


Wireless


Protocols


Collaboration


Supernodes


Grids


Clusters


Object Location and Retrieval


Storage Systems


e-Commerce




仔细看一下,就会明白现在p2p研究者们都在关心什么样的问题,其一是安全,这是很好理解的,在p2p环境下:分布式而且个体之间的差异特别巨大;其二是overlay虚拟网,这是p2p环境中特有的一个词;其三是路由和查询;其四是应用;最后可以勉强算一个是标准化——协议。

其实在结合它的program来看一下,就更明了了。(注:program应该相当于会议的主题发言和成果展示)

然而有趣的另一个p2p方面比较有权威的会议 ITPTS'06,下面的是明年的call for paper征稿范围

  • peer-to-peer applications and services
  • peer-to-peer systems and infrastructures
  • peer-to-peer algorithms
  • security in peer-to-peer systems
  • robustness in peer-to-peer systems
  • anonymity and anti-censorship
  • performance of peer-to-peer systems
  • workload characterization for peer-to-peer systems
  • experience with deployed peer-to-peer systems
  • incentives for peer-to-peer systems
  • network and infrastructure support for overlays
  • application of peer-to-peer design to novel contexts

  • 这是今年(05)的call for paper的征稿范围:


    peer-to-peer applications and services
    peer-to-peer systems and infrastructures
    peer-to-peer algorithms
    security in peer-to-peer systems
    robustness in peer-to-peer systems
    anonymity and anti-censorship
    performance of peer-to-peer systems
    workload characterization for peer-to-peer systems
    experience with deployed peer-to-peer systems

    还有IPTPS'05的program
    一个很鲜明的感觉就是ITPTS对p2p本身的关注程度更高,仅仅p2p系统他就涉及到 安全性、健壮性、匿名性和去中心化、性能、负载 而且可以注意的是06年比05划分的更细了。至于看05的program(06年的还没有)就可以清楚的知道应该朝哪个方向去看paper了。

    BTW:这两个会议虽然都很好,但是私心认为ITPTS要更好一些,且不说比较牛的文章几乎都在在ITPTS上面,看看发表的范围就明了,p2p2005中间还包含有Grid和Agent,这些可是我们lab中大家日常bs的对象(请你仔细的想一下,有什么Grid项目是成功的?有什么不能和Agent挂上钩?)

    附带着有结论2个:


    • p2p2005是IEEE举办的,应该是官方举办的会议,可是他却并不是最关注于p2p系统的实现,相反地关注的都是一些宏大的主题,都是一些激动人心地、时尚的关键字。比如grid/agent/ Middleware/ super computers/ supernodes/ Clusters /Wireless/ e-Commence/也许做学术的都有这种通病,我的东东可以解决一切,包容一切,你说的我都不能没有,你没有的我还有。看到别人好的就拿过来,往往为一件小事就可以相互bs,吵得不可开交。
      其实,我们大家天天都看到中国现在学术如何如何的腐败,但是国外的情况呢?依我个人的世界,觉得真正有创造力的头脑少的很,有那么多的人都在从事学术,他不要毕业么,不要发paper么?那怎么办么,第一就是制造概念,然后拼命拔高,拼命形式化,拼命抽象,最后都万道归一了。然后再互相吹捧,使其大旗不倒。所以说如果尖酸刻薄点说:Agent就是学术腐败(就像安然是自由世界里的经济腐败一样)。不过说清楚,我并不是bs Agent,最多我只不过会说Agent不是CS而已。




    • 学以致用的观点我觉得应该是我们CSer应该时刻铭记的观点,且不说抱负良心,计算机就是一门工程学科;这一点要向相信有许多人坚持着,这如ITPTS和Apache

    [DHT算法]Chord概述(1)

    Chord项目是MIT的p2p研究项目,并且是受NSF资助的IRIS project(Infrastructure for Resilient Internet Systems)的一部分,而整个IRIS project就是以DHT为基础的,好像拿到了NSF很多钱,大约是2000w吧。
    在分布式系统中,资源的查找是个很重要也很棘手的问题,一般的说来主要有两种方式

    • 一种采用集中式的查找,有一个索引服务器,p2p的开山鼻祖Napster就是这种这种方式,还有诸如LDAP,都是这种方式的代表。这种方式虽然查找起来方便,但是容易受攻击,目录服务器垮了这个系统也就不行了。这显然不能满足p2p的技术要求(但是在其他的distributed系统中,如grid中却可以应用的很好),p2p是针对于一般用户的,它的准入策略不能太严格,在开始的情况下,只能假定所有人都是善意的。

    • 另一种查找方式就是分散式的查找。在Napster因法律问题而受到打压以后,研究人员开始明白仅仅文件时分散是不够的,p2p就是要完全的decentrlized/去中心化,但是怎么解决查找的问题,很自然的一个思路就是采取一种“洪泛”的策略,我把我要查找的信息告诉所有我知道的邻居,他们告诉他们知道的下一家,这样递归的查找下去,最终肯定可以找到所需要的资源。采用这种方式最主要的有GnutellaFreenet,为了采用目录服务器p2p system(Napster)相区分开,一般把以Gnutella/Freenet为代表的p2p system称之为第二代p2p system,而把Napster等称为第一代p2p system。
      这种分散式的查找方式虽然更加符合p2p的初始精神,Decentrlized,Anonymity,Robustness。但是采用“洪泛”的一个显然的弱点是网络里的流量会以指数级的方式迅速增长,这样这种p2p system的参与peer不能太多,否则网络将会因为拥赛而垮掉。但是很不幸,p2p面对可以说就是草根,如果得不到用户,那么它还有什么意义呢?


    行文至此,p2p系统3年前面临的困境要怎样解决呢?Napster方式肯定不适合,首先就不符合p2p的精神,甚至不能真正称之为一个p2p system。
    那么对第二代的p2p system能做什么,自然是改造。控制拥塞是网络里面的老课题,也有很多经验和成熟的技术可用,只是应用环境变了。事实上,现在这种结构p2p system研究者的热点也是集中在这里:怎么样在保证通讯质量的同时,尽量减少通讯量。

    好了,终于轮到DHT和Chord出场了。Creativity!在对原有系统修修补补的同时,另外一些研究者确在思考全新的解决方案。既然集中式和分散式各有优缺点,而且看起来它们之间还是互不的,那么能不能把它们结合起来呢 ?既不完全分散也不完全集中。把所有索引信息,分别存放在很多节点之上,但是这又不能和那种多级索引一样,虽然分散了索引,但是仍然有顶级节点,一旦最上面的索引服务器垮掉,整个系统还是垮了。所以最好还是平面结构,而不要是层次式结构。在一个平面上,能购查找的算法,大家能想到什么?哈希表,也许你已经想到了。而这也正是Chord研究者们所想到的,DHT的全称Distributed Hashing Table,分布式哈希表。从这个名称似乎已经隐约可见端倪了,它的思想正是上面所提到的那样。不过为了哈希表放到不同的节点之上,还是做了很精心的设计的,Chord的设计也是非常巧妙的。
    p2p的研究到此似乎也就走出了困境,而各种DHT算法也在Chord之后如雨后春笋般的发展起来了。由于基于DHT的p2p system和以前的p2p system之间的一个显著的区别是为了保证各个节点能够hash到另外的节点。所有节点的ID必须是预先规定的。因此被称为structured p2p system,有结构的p2p系统。把以前洪泛的p2p 系统称为unstructured p2p system,无结构的p2p系统。

    毫无疑问,DHT是killer级的算法/技术。而使DHT深入人心的正是Chord,看Chord的文章,似乎在他们之前还有类似的想法(PlaxtonCAN),但是也许Plaxton的作者自己都没有太清楚的认识到他们想法的意义。Chord却明确了DHT作为p2p system的基础的地位。

    我自己以为,p2p研究正是在此以后,才获得了非凡的理论意义和基础。以前的p2p思想要么不成熟,要么依附于其他的CS分支。p2p研究正式成为CS科学家和应用者都认可的分布式系统。

    星期四, 十二月 08, 2005

    [读书笔记]CoralCDN的工作原理(翻译+重组)

    tag: p2p dht cdn CoralCDN

    因为朋友要写开题报告,托我看看CoralCDN的论文,我觉得既然看了,就不如看的仔细点。于是有了这片文章。

    Coralcdn是一种p2p方式的web内容分发网络(content delivery network),不过也有人叫它content distributed network,他的特点和使用方法就不说了,想要了解的google一下就ok了。下面我希望能够简单清楚介绍一下coralcdn的工作机制。当然看原始的论文会更清楚一点,而且网站上面还有一个ppt

    Coral的Indexing机制

    coralcdn底层的DHT网络被称之为coral,coral使用一种扩展的DHT方式
    Indexing机制DSHT(distributed sloppy hash table),声称较好的解决了DHT overlay中的locality的问题。不同于经典的DHT方式,coral首先对所有overlay中的node的网络状况进行一个评估, 然后按照RTT的时间代价自然划分为几个等级(coral里称之为按照网络的diameter划分),默认的是3级,L2(<20ms),L1(<60ms),L0(剩余的所有节点)。完整的NodeID的节点空间仍然是由SHA-1生成的160bit,但是查找和放置的时候,不是在整个NodeID空间上查找,而是优先在L2上的节点进行DHT查找,L2 层中找不到合适的节点再去L1层中查找,最后才是L0层。这样做的显然是考虑了locality,但是查找的次数应该对于一般DHT方式的查找次数。所以具体孰优孰劣还是要看实验数据,但是从直观感觉上还是coral要节省时间一点。不过DHT只需要维护一个DHT空间,而coral则需要维护三个,显然在节点加入或离去的时候,系统地自平衡代价也要大一点的。(不知道coral的作者们又没有考虑这个问题,:))

    coral的组成部分


    coral的主要组成部分有两个:Coral DNS Server——dnssrv;Coral Httpproxy——CoralProxy

    dnssrv

    在client查找coralize URL 的时候,dnssrv返回Proxy的IP地址,这些proxies都是在一个合适的cluster(就是前面说的L2、了L1、L0层)之中,同时确保来自于相同client的DNS请求不会离开这个cluster。下面我们就来看看Coral怎样实现。
    所谓的coralize的URL就是加上.nyud.net:8090,但是这实际上是为了方便而采取的一个缩写,完整的应该是.http.L2.L1.L0.nuycd.net,每一个dnssrv都是解析这个域名的nameserver。同时Coral假设dnssrv的了Locality就是WebBrowser的Locality。在每次请求中,dnssrv返回两个数据集,对于IP的proxy地址集,对于name's domain的nameserver。而且client和dnssrv之间的RTT如果在level-i层,那么dnssrv只返回那些在同一个level上Coral node的地址。对于proxy,返回的短的TTL,对于L2、L1是30s,L0是60s。dnssrv同时会在获得DNS授权的数据中查找,并把client锁定到合适的cluster上面。并且给这些nameserver一个比较长的TTL(1h)。对那些长于L1时间的client,dnssrv返回的是域L0.nyucd.net的nameserver,长于L0时间的client,dnssrv返回的是域L1.L0.nyucd.net的nameserver。

    Coral Http Proxy

    Coral设计主要是考虑低延迟、高系统吞吐以及对于源服务器的负载减轻。类似于freenet走过必留痕迹的策略,每个CoralProxy都尽可能的“拉”网页来,如果client请求的URL不再本地cache 中,则他们就会在Coral中查找(Coral的底层就是扩展kademlia), 然后再DSHT中插入一个references,告知系统自己有这个cache,保存的时间为20s,如果这个proxy完整的得到了文件,就会告知系统他会保存这个更长的时间(比如1h)。

    Coral的存贮方式:Sloppy Storage

    据称这种方式减少了hot-spot和tree saturation现象。在本来的kad中,key和node之间的关系是对应的,在插入时,有两个阶段,第一个阶段叫“forward”(相当于正常的kad插入),需要在node处于full或者loaded状态下需要做相应的调整。对一个node如果一个key存储了l(=4)就被称为full;

    在一分钟之内如果一个node上的一个key被请求bata(=12)次,则称nodeloaded。

    这时,就需要把key/value放在更远的node上。




    第二个阶段“reverse”,根据“forward”阶段的结果client试图插入value到最远的节点,如果“forward”这个操作失败,那client就会稍微回退一点(文章中叫做pops stack),把这个值放到次远的节点上(参见上图)。

    取回值的操作其实就是插入操作的逆向操作,这里就不再赘述。


    Coral中的层次式的操作

    这个在前面已经叙述了,这里在解析清楚几个概念再加一张图。Cluster就是Coral中的层次,其中每一对节点之间平均的RTT要小于一个阚值,就可以成为同在一层(Cluster)中。层次式的查找和插入的意思首先在RTT小的Cluster中进行,如果失败,则转入下一层中。参见下图。



    为了实现这种层次式的操作方式,每次Coral RPC都需要返回发送者的Cluster的信息。

    好了到这里,基本上的内容都差不多了。最后想提一下CoralCDN的代码量。Coral是14,000行C++写成的,dnssrv2,000行,HttpProxy4,000行代码。看起来还是很复杂的:)