Shell's Home

Dec 19, 2006 - 1 minute read - Comments

出差到宁波

名义上是出差,其实基本没干嘛。倒是看到了Gigi同学去过的天一广场。因为没带相机,所以啥也没有,就这样。

Dec 15, 2006 - 1 minute read - Comments

P2P和DHT的结构

最近P2P是越来越盛行,按照公司要求,我们要写一个P2P下载支持。老板发话,越小越好。想想有道理,只是要减轻服务器压力,又不是要和P2P下载商抢生意。不过老板又发话,必须保持核心服务器高可用性。偶当场啥掉,怎么办? 说起P2P下载的原始面目,其实是很简单的技术。假定你一个人在下载一个文件,同时你又知道所有有这个文件或者在下这个文件(那就有一部分)的人的套接字。那么连接上去下载,并且提供你可以提供的部分就好了。其中只有两个问题(也和算法没啥关系),应该先下谁的,应该先给谁。但是困难在于,你如何知道谁有某个文件呢? 按照获得这个信息的方法不同,P2P分成三代。 第一代是核心服务器型的,术语叫做中心化拓扑(Centralized Topology)[1],例如Napster[4]。这种类型的P2P下载可以说是传统下载和P2P下载的结合体。他同时具备了P2P的特性,例如带宽占用分布,高容错,高可用。也具备了核心模式的特性,例如中心依赖,可模糊搜索。Napster可以说就是因为核心依赖性而输掉了官司。 这代P2P的运作方式是,用户上线的时候把自身的资源提交到服务器。由服务器维护表来做查询,并且定时删除过期的客户。用户查找文件的时候需要向服务器提交请求,服务器返回拥有文件的客户端。由于文件信息提交到服务器端,因此服务器上可以说是拥有版权文件的索引。 第二代是泛洪/限制性泛洪型的,术语叫做全分布式非结构化拓扑(Decentralized Unstructured Topology)[1],代表就是Gnutella[3]。这种类型的P2P才是完全意义上的P2P,因为去掉了核心服务器,因此没有中心依赖性。拥有P2P良好的带宽占用分布,高容错,高可用性能。但是致命缺点是,当网络节点扩展时,维护网络的带宽消耗就会成几何扩展。在大规模应用中,这无疑是不可接受的。所以有限制性泛洪的结构,不过限制性泛洪只是增强网络的抗性,没有根本的改变现状。 这类P2P的运作方式是,用户维护自身拥有文件的列表,和其他一些客户的列表。当一个用户需要知道谁有一个文件的时候,就向他所有知道的其他客户查询。如此反复层级查询,并且用SPT或者TTL来做优化,最后可以得到结果。不过可想而知,网络消耗是惊人的。 这代P2P有个变形,术语叫做半分布式拓扑(Partially Decentralized Topology)[1],代表是KaZaa。简单来说就是把核心服务器型的一个核心服务拆成多个分布在某些比较强大的节点上。核心服务间使用泛洪/限制性泛洪型的方式通讯,核心和非核心间还是核心服务器查询的老路子。这类P2P修正了核心服务器型的中心依赖问题,并且可模糊搜索。也修正了泛洪的带宽占用问题。但是资源消耗分布不均匀,结构比较复杂,而且长期运行的核心节点可能莫名其妙就成为了被告,因为核心节点也拥有版权文件的索引。 第三代是DHT型,术语叫做全分布式结构化拓扑(Decentralized Structured Topology)[1],代表就是Chord[6],Pastry[5],Kadamila[2]。这种的P2P也是去核心的,拥有P2P良好的带宽占用分布,高容错,高可用性能。同时资源消耗比较平均,网络消耗小,扩展性好,抗网络不稳定能力强。缺点就是失去了模糊搜索的能力,只能变通的模糊搜索。 DHT是Distributed Hash Table的缩写,用于节点搜索的。在此之前,我们先来想想数据结构课程的一些东西(没学的就表看了,看下面的吧,这节看了铁晕)。如果我需要知道一个对象,找出关联的一个对象,那应该用哪种结构?map!那如果要增加map的效率怎么办?hash table!那么hash table的内存布型怎么处理?如果要经常删除添加,那应该用链表。OK,我们想像一下,假设一个节点就持有链表中的一项,上下项的指针改成上下节点的网络描述,那是啥?Bingo,DHT。当然,DHT不会傻到让一个节点就保存两个网络描述,那一旦断裂就全玩完。DHT中是先给予所有节点一个ID,然后定义一个距离算法,再按照ID来保存hash的。一个节点保存和他的ID相邻的一定距离的hash(当然还包括值),并且保存一些ID近的节点的网络描述和一些节点远的网络描述。就好像在hash table里面,一个节点保存了上下临节点的同时,也保存了很远的节点的指针。这样在链表查询的时候速度可以更快。 DHT的运作原理是,一个节点加入DHT网络,就会生成一个不重复的ID。然后会寻找一些节点来扩充自己的相邻节点列表,并且获取于自己相邻到一定程度的Hash的内容。当节点够多的时候,所有的Hash都会有一个以上的节点来维护,这样就有了足够的容错性,性能,稳定性。在寻取一个内容的时候,会寻找自己的临节点列表中最近的节点,然后向他查询进一步的消息。这个在几次循环后就可以足够近到获得目标信息了。当然,大家可以看出,要寻取一个对象,就必须有这个对象的hash,因此是不可模糊的。 Kadamila是eMule所用的服务,很多BT中也使用了兼容协议。 另外顺便在此提出一个P2P流的思想。传统的P2P下载是基于块的,简单来说就是文件。现在很多P2P技术可以基于流,就是可以在允许一定延时的情况下,将延时允许区域内的数据作为一个块来传送。这种技术对于P2P的要求更高,但是应用范围更加广阔。例如用于视频流播放,广播,股票数据传输等等。现在的流技术都是针对特定协议来展开的,例如视频流点播就用PPstream。我们可以将P2P流封装成一个独立服务,从发起端上连接一个接口,到客户端上监听一个接口,中间过程透明化。简单来说,发送端上运行一个服务,客户端上运行一个服务。发送端上的服务连接到一个特定端口来获得数据,然后通过P2P流来传输给客户端,客户端的P2P服务再监听到一个端口上,向所有(或者有限)连接上的接口提供数据。除去只能接受数据,并且存在一定延迟和丢包外。整个过程就被掩盖在了单纯的网络传输下面。这样很多协议可以在不修改协议(但是至少要可以对抗错包丢包等等网络状况)的情况下直接P2P流化。当然,P2P流在实时性,安全性上的要求会更加高。 顺便说一下网状模型的一个修改吧,几年前的东西了,可惜一直弄不出算法来。当前的网状模型是一个节点传输给其他节点,然后层级传递。理论上应该将发起节点最近的和提供带宽最高的节点放在顶层,以减少网的层数。不过将底层的节点带宽废弃还是可惜了点。我们可以将一个流分成两个部分(如果先天就可以分离最好,例如视频和音频,不过他们不对等),然后组成两颗树。这样网络中的底层节点就可以在另外一颗树中被定义为次层节点。如此会对带宽利用更加彻底,当然,程序也会更加复杂。 参考和引用: 1.P2P网络的拓扑结构:http://www.intsci.ac.cn/users/luojw/P2P/ch02.html 2.Kademlia协议:http://www.itslife.net/blog/?p=132 :http://blog.csdn.net/colinchan/archive/2006/05/08/712760.aspx 3.Gnutella协议:http://www9.limewire.com/developer/gnutella_protocol_0.4.pdf 4.Napster官方网站:http://www.napster.com/ 5.Pastry 工程:http://research.microsoft.com/~antr/PAST/pastry.pdf 6.Chord 工程:http://pdos.csail.mit.edu/chord/ 7.对等网络中主流分布式哈希算法比较分析:http://www.p2psky.com/tech/article1274.html 8.细说 Kademlia:http://www.vshj.com/Article/2005/200512/Article_18386.shtml

Dec 14, 2006 - 1 minute read - Comments

Boost

谢天谢地,好久没有正常的用blog了。无论哪里都是能看不能改,痛苦死我。 先写个技术文,关于Boost库的。 首先,你得装Vs2003.net。VC++6的编译器在支持列表里面一片血红,用那个不如用Linux跑GCC。如果有MSVC8(不要脑子转不过来,就是Vs2005.net),那就比较完美了。基本和Linux下的GCC4.1平分秋色。下面是按照Vs2003.net+windows的例子来讲的。 然后,下载一个boost的库源代码,解压安装,没有一点困难。好的很。 接下来,请在PATH里面确认添加C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\bin;C:\Program Files\Microsoft Visual Studio .NET 2003\Common7\IDE;或者等效路径,关键是要能将cl.exe,link.exe,vcvars32.bat,mspdb71.dll纳入搜索路径。然后切换到boost的目录boost_1_33_1libs\regex\build,运行vcvars32.bat,再运行nmake -f vc71.mak,或者等效的指令(其实就是71还是70 80)。再运行nmake -f vc71.mak install,向VC的lib目录里面添加库。至此boost库的regex组件库算是编译好了能用,如果你不用正则表达式,抱歉,上面的话在耍你。 然后是用法,倒不难。 cmatch what; regex reg("^abc$); if(regex_search(str.c_str(), what, reg)){ .... } what里面会保存从正则表达式里面匹配出来的东西。 利用这个库可以很好的做字符串拆分,验证的操作,弥补了C++没有正则表达式的缺憾。 我写了一个类,可以从流里面获得每行,然后做匹配,然后派发到相应函数里面去。有需要的可以联系我。

Dec 2, 2006 - 1 minute read - Comments

我工作了

最近我又被朋友们拷问关于工作的问题。恩,没错,我工作了,地点在曹杨路,当然是程序员,薪水不太满意。从9点到6点。 没缺什么吧?

Nov 16, 2006 - 1 minute read - Comments

某件事情

恩,今天应当事人要求,我需要讲某件事情,请大家评评理。应当事人要求,特地隐去名字,称为某君。但是在说事情以前,我必须坦诚另外一件事情,我谈恋爱了。 相信这年头,谈恋爱不是啥应当游街批斗的罪过,当然接吻也不是。问题就出在我和某君接吻后面—— 她和我的某位亲戚是同学,所以在接吻后没多久就主动找上我这位亲戚分享心得。言语中谈及什么我一直不知,据某君本人说也记不清楚了。不过就我辗转得知,其中应当有“是不是姿势错误”和“口水满脸都是”云云。我的这位亲戚觉得某君言语说的太过露骨,将来说给其他人知道,于我不利。于是找上我的长上和盘托出,长上听后颇为不齿,斥为“二百五,这种事情怎么好说的阿。”。于是又找上在下的高堂,托她转告。高堂特意约谈我,说“这事情不应该这么做。这么做让人觉得——按你XX的话说,有点二百五”。我听了颇为尴尬,于是又约谈某君,说其侵犯隐私云云。某君不服,认为此事不应怪她,虽然事情因她而起,可是她不应承担主要责任。好比导火线一样,虽然造成爆炸,本身没有什么过错。言称我那位亲戚到处乱说,才当是罪魁祸首。又说我的长上道听途说即说其是“二百五”,话语太重,下结论太随便。我本人未就此事向此二位长上辩解,未克尽男友的责任云云。 我反驳她,说她随便说话已经不是首次。接吻当天就向她的母亲完全坦诚此事,导致她母亲下令禁止她再到我这里来。随后又主动找上我的亲戚,言及我的私隐。就此两件事情,何谓不承担主要责任。长上说小辈一句“二百五”,就是我自己这些年也被说了无数次,又有什么委屈呢?说到道听途说,除非说我那位亲戚随意编造。可此事只有我和某君知道,我没有说,某君没有说,我那位亲戚又不是千里眼,怎么连细节都知道呢?至于我未就此事向二位长上辩解,不说事情因何而起,单单我为人晚辈,是否合适辩解呢? 大家应当知道整个事情来龙去脉了,可以评评理看,倒底事情如何?知道详情的也可以在下面补充,看看我哪里没有说到。

Nov 7, 2006 - 1 minute read - Comments

租屋公告

最近碰到朋友——除了问头发,还经常被问到出租屋的事情。好吧好吧,我租出来了。 具体请看这里。 别说我没说过。

Nov 6, 2006 - 1 minute read - Comments

剪发公告

最近碰到朋友——老问我,你最近如何。我说还行,就是头发剪了。然后就被要求照片。好,现在特此公告。照片如下。 别说我没说过。

Nov 6, 2006 - 1 minute read - Comments

一只小狗

今天老妈跑到我租的房子里面的时候,在门口看到一个小狗。(关于我租房子的事情后面再说,我很懒,就这样)脖子上有个牌子,看来是有主人的狗。看上去很乖巧很可怜的一个小狗,趴在我家门口附近。不知道哪里来的。老妈看看可爱,又看看有主人的,放心的喂了块肉。结果,麻烦大了。 到中午我去吃饭,把早饭时候的锅子带回去。结果出门发现,它还在那里。看到我出来,一下子站起来。有没有搞错,别说我可不是老妈。就算是,也不能在空锅子里面变出肉来阿。赶紧给老妈打了个电话,老妈还说我大惊小怪。好好好,见怪不怪。我出去看到它注意力正被邻居引开了,干脆一溜烟跑下去。 晚上去吃饭,发现还在——有没有搞错阿——就算黑猫叔叔也要休息的好吧。没办法,和老妈说了,你喂的肉,你搞定。老妈想想也没办法,吃了晚饭到我哪里准备抱下去。结果路上看到一个邻居的狗,也跟我们上来了。 两个狗见面了非常有意思,互相闻来闻去。然后邻居的狗居然想骑那个可怜的狗了。它(或者应该叫她?)到处跑。我赶快跑到屋子里面,省得看狗打架。老妈赶快把狗抱到下面去,结果发现110来了。看来是刚刚他们打架的声音太大,吓到谁了。邻居的狗应该没事,不过这只可怜的小狗就麻烦了。虽然有狗牌,但是不能用来查找主人。(狠狠鄙视下中国的动物管理制度,收了钱不管理的么)派出所的人看看也很可怜,问我妈说要不要养。养的话省下1000来挂狗牌,不养的话回去他们也是处理了。(其实就是人道毁灭)我妈听了也很想,问题是这狗可带不回北京阿——即使带回去也没法养。原来的狗就是一个证明。所以很无奈的看着给接走了。

Oct 25, 2006 - 1 minute read - Comments

上海电信ADSL宽带测试报告

总算把该死的有线通换成ADSL了——现在我们看看电信的宽带质量。 我做了几项测试,因为时间关系(我要吃饭了——),没有做的很足,回头补个详细的。 1.tcp连接丢包率 根据我的测试,有一次出现了4%的丢包率,其余时间是0。 2.网络时延测试 www.google.com的测试结果是 平均/抖动=295.3⁄591.7 www.sina.com.cn的测试接过是 平均/抖动=435.1⁄714.3 3.TTL状态 平均TTL大约在12-18左右,略略好于有线通1-2个路由器。 4.动态丢包测试 P2P/HTTP混合实际使用下1分钟8863个包,丢包2.7%。 5.网络压力测试 未进行。 从以上参数中可以看出,电信的质量略略好于有线通的。但是网络时延大,带有数据丢包。这个要去检查是否是信号线上的问题。 下午仔细检测了ADSL的详细状况,然后得出了一个更详细的表,附录如下: 1.tcp连接丢包率&网络时延测试 #hping -p 80 www.sina.com.cn #hping -p 80 www.google.com 2.TTL状态 NTOP测定,平均TTL大约在12-18左右,略略好于有线通1-2个路由器。 3.动态丢包测试 wireshark测定。 1.无网络压力状态下测试 双机器自然负荷,仅仅开启MSN等IM软件。 --- www.google.com hping statistic --- 96 packets transmitted, 95 packets received, 2% packet loss round-trip min/avg/max = 36.1/39.3/57.6 ms 平均/抖动=39.3⁄21.5 --- www.sina.com.cn hping statistic --- 96 packets transmitted, 96 packets received, 0% packet loss round-trip min/avg/max = 10.

Oct 21, 2006 - 1 minute read - Comments

通过LPIC1

总算正式通过LPIC1了,搞了半年这个东西,真的差点让我崩溃。通过可以有两种方法,背考古题,或者拥有深厚的功底。 里面最让我觉得不爽的就是很多莫名其妙的参数还需要记忆。例如tracroute -n的n,是阻止R-DNS的意思。这个如果是RHCE,一个man就知道了——可是这里,就需要人自行记忆。除非相当长时间的使用,让你对这些参数了如指掌,否则——考古题。 不过里面对于功底的考察蛮细致的,有的题目会问你一些正常不会细究的东西。我为了通过考试,自行研究了整个Linux引导的详细过程。从开机到initrd,然后从服务到启动X,到自动执行脚本。非常详细的了解了整个Linux的基础,并且可以自行定制一个Live系统。这里面需要非常详细的研究,一般的大路货考试好像还没有这个必要—— 不过我要说的是——这些东西——纯粹是自己吓自己。事实上,LPI-101我考了550分,LPI-102我考了640。不是啥高分,不过远远超过通过分数。原因是对于考试评价过高——还特意拖了很久——等很多事情稳定了,而且功底扎实了才去。没想到这么简单,扫兴。 总体来说——考试通过的感觉还不错,不过没有什么好惊讶的。意料中的事情——除了多出来的1300块钞票——我的钱阿——