Skip to content

Rsync 的算法

RSync 算法是澳大利亚人 Andrew Tridgell (samba的作者)发明的,按照 Andrew Tridgell 自己的话,这个算法只需要半个小时就能够理解,但是花费了他几年时间才研究出来。

Rsync 算法大概原理:(目标:把 HostA 上的FileNew 同步到 HostB 上 FileOld)

1) Host-B把File-Old划分成不重合的大小为K字节的若干块,不足K字节的结尾部分加上Padding,然后对每一块求弱Hash和强Hash。弱Hash就是说很有可能两个不同的块Hash值相同,但是计算起来快,而且这里要求这个弱Hash能够Rolling,也就是说已知字节1到字节K这个块的Hash值,能够很快的计算出字节2到字节K+1这个块的Hash值,往前Roll一个字节,计算很快;强Hash就是可以认为不同块肯定有不同 Hash值,Rsync用的是MD4。我们让WH表示弱Hash,SH表示强Hash。
2) Host-B把每个块的WH和SH值发送给Host-A。
3) 该Host-A上场了,他的运算量比较大。Host-A对File-New每一个长度为K的块(也就是以每个字节开头的长度为K的块)计算WH,计算出来之后和Host-B发送过来的WH匹配,如果发现有相同的,再计算这个块的SH进行匹配,如果还是相符,说明这个块在File-Old里面也存在。假如 File-New长度为N,那么Host-A要处理大约(N-K)个块,这里可见用两个Hash算法的作用,WH用来做初步比较,而且因为它可以 Rolling,所以能够很快筛选掉大多数不匹配,对于漏网之鱼,也躲不过SH的筛选。
4) 通过上面的计算,Host-A可知道,File-New中哪些块和File-Old中的块相同,这样自然也可以计算出哪些不同,Host-A把这些不同encode一下送给Host-B。
5) Host-B收到Host-A送来的数据,decode,就得到了File-New相对于File-Old的改变,于是获得了File-New。

整个过程只需要一个round-trip(一个来回的通信),而且可以精确的得到一个字节级别的差别,Host-A的运算量相对要大一些。

Rsync的实现已经是*inx上面的一个重要工具,所以,当Microsoft在Windows 2003 Server上推出DFSR(Distributed File System Replication)时,Open Source Community颇有嘘声。其实DFSR采用的是RDC(Remote Differential Compression)算法,和RSync相差很大,并没有抄袭RSync。

RSync有学院气息(这个算法本来就是Andrew Tridgell的博士论文),结果很完美,File-New和File-Old每一个字节的差别都计算出来了,但是Host-A和Host-B的计算量不对等,大部分的计算都集中在Host-A上。RDC和RSync相比方向上有点不同,RDC并不追求计算出字节级别的diff,而是用较少的运算求出数据块级别的 diff。

RDC算法要求Host-A和Host-B通过一致的规则对File-New和File-Old分别进行分块,然后对每个块计算 SH,Host-B把每个块的SH值发给Host-A,Host-A对两组SH进行diff,就可以知道有哪些块不同,哪些块被删掉了,哪些块被添加了。 RDC的关键在于分块规则,也使用WH,要让同一规则应用于File-Old和File-New的时候,分出来的块能够尽量体现出区别。

比如File-Old包含“I Love Playing Basketball”,
File-New是“I Like Playing Football”。
如果是RSync算法,Host-A能够计算出准确的差别,“I Like Playing Football” 哪部分是修改了,哪部分是增加的,精确到每个字符,Host-A主要告诉Host-B:“把第4-6号字符换成’ike’,把16-21号字符去掉,插入’Foot’”。

如果是RDC算法,可能得到下面的结果:

File-Old分块的结果,分成3块。

“I Love”  “Playing”  “Basketball”

File-New分块的结果,分成3块。

“I Like”  “Playing”  “Football”

Host-A经过比对,发现只有File-Old的第2块和File-New的第2块匹配,于是就告诉Host-B:“把你的第一块换成‘I Like’,把你的第3块换成‘Football’”。

如上面看到,RDC相对而言比较浪费,相比RSync,要多传输一些数据,但是Host-A和Host-B的计算量比较平均。为了让RDC发挥好的性能,一定要制定一个好的分块机制,让包含Diff的块尽量少包含没有Diff的数据,怎么做到这一点呢,还要靠WH,通过rolling checksum来从数据中快速挖掘出数据的性质。

注意一点就是RSync的分块策略是每块都是固定长度的,而RDC则每块长度可能不一样。

虽然RDC相对浪费一点,但是传送的大部分还是Delta数据,而且计算量相对平均而且较少,目前Window 2003 Server R2上的DFS使用的就是RDC算法,还有一个应用就是Live Messenger的Shared Folder功能,用一用,就知道效率不差了

参考:http://morganchengmo.spaces.live.com/blog/cns!9950CE918939932E!521.entry?wa=wsignin1.0&sa=739070373

lucene 2.4.1 重建索引测试

机器配置:

uname -a :

Linux eshequn-SV06-A11 2.6.21.5-smp #1 SMP Sun Jan 27 23:51:02 CST 2008 i686 Intel(R) Xeon(TM) CPU 3.06GHz GenuineIntel GNU/Linux

cpuinfo:

processor        : 2
model name    : Intel(R) Xeon(TM) CPU 3.06GHz

meminfo:

MemTotal:      6234308 kB

disk info:

/dev/sda1 on / type reiserfs (rw,noatime)

lucene 配置

writer = new IndexWriter(indexDir, paodingAnalyzer, true, IndexWriter.MaxFieldLength.UNLIMITED);
writer.setMaxBufferedDocs(10000);
writer.setUseCompoundFile(true);

// 说明:使用 Paoding Analysis (http://code.google.com/p/paoding/)

数据:

共 33833375 条记录,3647 个 xml 文件,xml 文件每个约4M,Total 大小:14G

最终索引文件大小:4G(说明:只有 id 字段为 store,其他字段都为 no store)

cfx 文件:629 M

cfs 文件:3.4 G

耗费时间:共花费时间 7985秒 平均每个文件 2.2秒 (其中 optimize 花费约 35 分钟 / 2100多秒)

从 log 里面计算每次选取 n 个文件(当前是10个)后写入索引所花的时间(单位为秒)以及当前的总时间:
(log  文件的第一列为 hh:mm:ss 格式的时间戳,START 为每次选取文件后特意打印的 log info)
grep START /home/data/search2/logs/search2-Index2.log |awk -F’,’ ‘{print $1}’ | awk -F’:’ ‘BEGIN{now=0;last=0;total=0}{now=$1*3600+$2*60+$3; print $0, NR, now-last; if(last > 0) total+=now-last; last=now;}END{print “total:” total ” ave: ” total/NR}’

结论:

在普通的服务器级别的配置的机器上,lucene 2.4.1 建立索引的速度,效率以及最终索引的大小,都足以支持 “亿” 级别的应用。但当记录达到 “千万” 级别以后,就需要做一些优化了:

  1. 分离索引和存储。索引里只存储 id ,其他的字段只索引不存储。优点:保持索引的大小为一个可接受的范围;缺点:搜索时需要额外的请求来获取其它必须的字段(lucene + db[mysql or bdb or memcache or memcachedb]方案)
  2. 分离写索引与读索引。优点:消除读写索引时可能因为锁干扰问题导致的索引不一致,同时保证搜索服务的可用性,和可扩展性;缺点:需要额外的读索引更新逻辑(reopen)
  3. 大小库:为了保证及时更新的同时,减少索引频繁同步(由写索引同步到读索引)带来的 io 压力,可以把索引库拆分为大库(历史库),小库(最近更新库),定期合并小库的记录到大库中,降低历史库的同步频率,在不影响搜索结果的同时减少同步的 io 消耗。大部分的搜索结果都满足时间的局部性原则,即搜索结果中,最近更新的记录排前面的可能性较大。所以,可以配置这样的策略:如果小库中的搜索结果条数已经满足要求,那么略过大库,直接返回结果给客户端,以达到加速搜索的目的。
  4. 多份读索引:(未经过实践检验,正计划测试)当索引库比较大的时候,每次 reopen 都会造成短时间内的搜索请求被堵塞。可以配置成多份读索引,错开时间 reopen ,保证任何时刻都有一个可用的索引在。
  5. 分词服务化:(只是一个想法,未经验证)分词的优劣对索引大小,search结果优劣影响非常大,但 lucene 中如果想更新或更换某个索引的 analyzer ,一般都需要重建索引。为了平滑升级分词算法,词典等,可以考虑将分词模块从 lucene 中分离出来,独立成 web service 服务。

新的域名,新的开始(fullin.org)

fulin.org 域名遭恶意抢注,愤怒却又无可奈何。重新注册了 fullin.org ,中间多了一个 L 。

其实我从年后就开始折腾域名的事情了。域名是在新网注册的,而当初注册 birdring.org 的时候,在万网里留了320块钱。于是就想把域名转到万网,用余下的钱来续费。可是找了半天,还是没有找到如何转域名,甚至用记忆中的用户名和密码都无法登录新网了。打新网的客服电话也没有用,一大断的语音提示,平白浪费电话费罢了。

稍微一犹豫,域名进入了赎回期。这个时候在 whois 记录上看到有 update 操作,难道是新网或者代理商自己续费了?我很愤怒的在新网所谓的“在线客服”系统上留了言。没有想到,第二天还真有回音了:

>我有一个域名是在新网注册的,
>本来应该在09年1月份到期,我没有续费,
> 但不知道为什么忽然 whois 信息被改了,过期日期变成了2010年1月,这是为什
> 么呢?现在该域名处于 On-hold (generic) 状态,按理说这个状态应该维持 30
> 天,可 30 天过去了,昨天居然又被 update 了,难道新网要让这个域名一直处
> 于这个状态吗?我现在想拿回这个域名,而且希望转出新网。请问需要走哪些手
> 续?整个新网的网站上居然都找不到一点关于转出域名的说明???

<请提供您的域名。我给您查看一下,域名的情况。
<客户服务 **
>我的域名是 www.fulin.org
<您的域名现在已经进入偿还期了,org的域名有30天的续费期和30天的赎回期
<然后有5天的删除期。
<如果您想转出新网,请先将域名赎回,然后在域名状态正常的情况下才可以办理,
<将域名赎回请您直接联系:郑州分公司 同事,缴纳罚金。

>最近的两次更新(1月25号,2月25号)是谁更新的?

>为什么域名所有者没有做任何操作,而域名的过期时间从 2009年1月26号 变成了 2010年1月26号了?
>我想确认的是,30天的续费期加30天的赎回期之后,域名真得会进入删除期吗?不会被某个内部人员抢注?
(这个时候,我已经开始在想要不等删除后再注册回来?)
<是的,30天的续费期加30天的赎回期之后,域名会进入删除期。在5天的删除期内,系统是不定时的删除,如果被人抢注了,我们也没有办法。请您在进入删除期内,关注该域名。
<注册日期 : 2007-01-26[Fri]00:00:00
<修改日期 : 2007-01-26[Fri]00:00:00
<失效日期 : 2009-01-26[Mon]00:00:00
<操作时间 : 2007-01-28[Sun]15:45:02
<只有一个修改时间,即您的续费时间。
<您说的更新时间,Last Updated On:25-Feb-2009 20:06:16 UTC  是系统由正常续费期状态,变为了进入偿还期的状态。由于域名状态的变更,系统会自动更新。Expiration Date:26-Jan-2010 14:04:32 UTC  不准确,一般在whois上查到的域名到期日期是,系统都自动加了一年,要以新网库里和域名证书的到期日期为准,为:2009-01-26
(因为担心被别人抢注——最后结果证明我的担心不是多余,我还是想着赎回算了,破财免灾阿)
>我如果现在赎回的话,罚金是多少。
>如果不赎回,能否请你们在它到期的时候帮我抢注一下?如果可以,
>需要多少钱。
<具体的罚金,我们也不太清楚,需要咨询郑州分公司的销售人员
<到期后,我们不能抢注,没有优先权,所以还是需要用户自己抢注一下
忘了后来在哪看到的说明,说是赎回需要交 800 RMB,这个时候还抱着一丝侥幸心里:我这么一个个人博客域名,应该没有人看得上吧?不会有人跟我抢吧?于是就天天盯着 whois,等它掉出来。同时又往万网充了 5 块钱,凑足 3 年的注册费用(325/36个月),等着它一掉出来就注册。(这是我犯的第二个错误,第一个就是没有在赎回期之前直接在新网续费)
4月1号早上,起床后第一件事情(before 刷牙洗脸),whois 一看,终于没有记录了。心里那个乐阿,赶紧的冲到公司,开机,进windows。可是上万网一查,居然还是“已经注册”状态(详细信息为 NOT FOUND)??难道还在等待同步??
2号早上,照例随手whois,这次是彻底惊了:已经被注册了?!再打开万网,还是“已经注册”状态(详细信息为 NOT FOUND),表明删除还没有同步完,可别人都已经重新注册了!!
想起不久前看到的文章,说是有的人抢注域名,等一段时间发现没有人来问自己要,就会主动放弃。于是我又耐着性子等了一天,到 3 号,等不住了,按照 whois 里填的email (keywordacquisitions@gmail.com)给发了封邮件:
>I noticed that you have registered a ORG domain name which belonged to
>me formerly.
>So how much do i have to pay to get it back?
<We have thousands of domain names.  Please identify the domain name
<that you are interested in purchasing.
>fulin.org
<Please make an offer ($).
>please keep it if it cost more than $50
No response until now…
update:
>HI:
>I will sell it for $50.
>Regards – Stephen
所以,开始进入赎回阶段吧
大约 50$ 对于他们来说,是一个不可接受的价格吧。沉默了一个清明小长假,最后还是下定决心,换一个域名吧。于是上万网,在 fulin.info, tangfulin.org, fullin.org 中间,选择了 fullin.org ,并打算在半个月后转移到国外的域名注册商(新注册域名必须半个月后才可以转移)

Domain ID:D155819369-LROR
Domain Name:FULLIN.ORG
Created On:07-Apr-2009 08:17:09 UTC
Last Updated On:07-Apr-2009 08:23:15 UTC
Expiration Date:07-Apr-2012 08:17:09 UTC
Sponsoring Registrar:Hichina Zhicheng Technology Limited (R1373-LROR)
Status:TRANSFER PROHIBITED
Status:ADDPERIOD
Registrant ID:hc489271298-cn
Registrant Name:fulin tang
Registrant Organization:TangFulin
Registrant Street1:Beijing Normal University
Registrant Street2:
Registrant Street3:
Registrant City:beijing
Registrant State/Province:Beijing
Registrant Postal Code:100875
Registrant Country:CN
Registrant Phone:+86.01058805915
Registrant Phone Ext.:
Registrant FAX:+86.01058805915
Registrant FAX Ext.:
Registrant Email:birdring@gmail.com
Admin ID:hc489271298-cn
Admin Name:fulin tang
Admin Organization:TangFulin
Admin Street1:Beijing Normal University
Admin Street2:
Admin Street3:
Admin City:beijing
Admin State/Province:Beijing
Admin Postal Code:100875
Admin Country:CN
Admin Phone:+86.01058805915
Admin Phone Ext.:
Admin FAX:+86.01058805915
Admin FAX Ext.:
Admin Email:birdring@gmail.com
Tech ID:hichina001-cn
Tech Name:hichina
Tech Organization:HiChina Web Solutions Limited
Tech Street1:3/F., HiChina Mansion
Tech Street2:No.27 Gulouwai Avenue
Tech Street3:Dongcheng District
Tech City:Beijing
Tech State/Province:Beijing
Tech Postal Code:100011
Tech Country:CN
Tech Phone:+86.01064242299
Tech Phone Ext.:
Tech FAX:+86.01064258796
Tech FAX Ext.:
Tech Email:domainadm@hichina.com
Name Server:DNS25.HICHINA.COM
Name Server:DNS26.HICHINA.COM

Lucene 重建索引流程设计(草稿)

一. php client 端:

1. update 与 rebuild 分开

2. update 准实时:insert,update,delete 实时调用更新索引接口(带 primery key 的update 和 delete)

3. rebuild 使用命令行或者 cron 运行,不能使用 web 页面(有运行时间限制),但可以在后台管理系统中作触发(如何防止重复触发?)

二. Java IndexServer:(接受 client 发过来的数据,输出为临时 xml 文件)

1. 日常 update 的 xml 临时文件可以考虑保存在内存文件系统中(保留最近n天的文件debug使用)

2. 更多的处理过程 log (debug 使用,日常监控使用)

3. rebuild 的 xml 临时文件一定要保存在内存文件系统中

4. xml 文件按年或月分目录

5. rebuild 的过程中,update 数据需要为新索引保留一份,等 rebuild 完成后更新新的索引(需要一个 rebuild_update 目录,等搜索切换到使用新的索引后,用该目录替换原来的 update 目录)

三. Java IndexWriter:(读取 update xml 文件,更新索引)

1. update 与 rebuild 分开,以便设置不同的合并因子等参数,以达到最快的 rebuild 速度

2. 每一个索引对应一个 update 文件目录,当索引切换的时候,update 目录跟着切换,以保证索引数据一致

四. Java IndexRebuilder:(读取 rebuild xml 文件,新建索引)

1. rebuild 过程:

a. 正常情况: client 发送 update 数据给 IndexServer ,IndexServer 将数据写入 update 目录,IndexRebuilder 定期扫描 update 目录,读取 xml 文件并更新索引

b. client 发送“重建索引开始”消息给 IndexServer,IndexServer 设置标志位,从当前开始,所有的 update xml 都抄送一份到 rebuild_update 目录。同时给 IndexRebuilder 发送 “重建索引开始” 消息。(消息中能否带有这次重建索引的大致的条目数?可以用来确定派生多少个线程)

c. client 发送重建索引数据给 IndexServer,IndexServer 将这些数据输出到 rebuild 目录下

d. IndexRebuilder 收到 “重建索引开始” 消息后,(根据大致的条目数,相应的派生线程)扫描 rebuild 目录,使用其中的 xml 文件建立索引

e. client 发送“重建索引结束”消息给 IndexServer, IndexServer 转发消息给 IndexRebuilder

f. IndexRebuilder 收到“重建索引结束”消息后,等待所有线程工作完成,然后开始使用 rebuild_update 中的数据更新新的索引

g. IndexRebuilder 更新索引到一个可用状态后(如何判定?某一次列目录发现没有新xml文件?),停止更新,开始 切换到使用新索引

2. 切换到使用新索引过程:

a. IndexRebuilder 发送“停止更新索引”消息给 IndexWriter,后者停止更新旧索引,close 打开的文件

b. IndexRebuilder 拷贝新索引,覆盖旧索引

c. IndexRebuilder 将旧的 update 目录指向 rebuild_update 目录

d. IndexRebuilder 发送“停止抄送 update xml 文件到 rebuild_update” (重建索引完成)命令给 IndexServer,并将 rebuild_update 指向新的空目录

e. IndexRebuilder 发送“重新开始更新索引”消息给 IndexWriter,后者 reopen 索引,并照常更新

f. IndexRebuilder 清除旧索引文件,等待下一次重建索引消息

3. 重建索引的加速:(初步设想)

a. 根据索引大致的条目数,预先派生线程

b. 每个线程单独建立索引,完成后再归并

c. 预先派生线程数目,以及归并策略(1次归并,或者多次,每次把n个归并成1个)需要测试

五. IndexSearch:(读取索引,响应搜索请求)

1. 同步索引:从 IndexWriter 同步到 IndexSearch 上,使用 bash 脚本,rsync

2. reopen:索引更新以后,发消息通知 IndexSearch 重新读入索引,可以使用 curl

NOI 的回忆

一晃,NOI 已经是快十年前的回忆了,就连 ACM (http://acm.pku.edu.cn/JudgeOnline/userstatus?user_id=tangfulin)也成了五年前的过去了。偶然在网上看到别的同仁总结的 OI 的知识点,有一些很熟悉,也有一些从来没有见过,更多的,当然是听说过,但不知其所以然。

无论结果如何,我曾经努力追求过。

时间复杂度(渐近时间复杂度的严格定义,NP问题,时间复杂度的分析方法,主定理)
排序算法(平方排序算法的应用,Shell排序,快速排序,归并排序,时间复杂度下界,三种线性时间排序,外部排序)
数论(整除,集合论,关系,素数,进位制,辗转相除,扩展的辗转相除,同余运算,解线性同余方程,中国剩余定理)
指针(链表,搜索判重,邻接表,开散列,二叉树的表示,多叉树的表示)
按位运算(and,or,xor,shl,shr,一些应用)
图 论(图论模型的建立,平面图,欧拉公式与五色定理,求强连通分量,求割点和桥,欧拉回路,AOV问题,AOE问题,最小生成树的三种算法,最短路的三种算 法,标号法,差分约束系统,验证二分图,Konig定理,匈牙利算法,KM算法,稳定婚姻系统,最大流算法,最小割最大流定理,最小费用最大流算法)
计算几何(平面解几及其应用,向量,点积及其应用,叉积及其应用,半平面相交,求点集的凸包,最近点对问题,凸多边形的交,离散化与扫描)
数 据结构(广度优先搜索,验证括号匹配,表达式计算,递归的编译,Hash表,分段Hash,并查集,Tarjan算法,二叉堆,左偏树,斜堆,二项堆,二 叉查找树,AVL,Treap,Splay,静态二叉查找树,2-d树,线段树,二维线段树,矩形树,Trie树,块状链表)
组合数学(排列与组合,鸽笼原理,容斥原理,递推,Fibonacci数列,Catalan数列,Stirling数,差分序列,生成函数,置换,Polya原理)
概率论(简单概率,条件概率,Bayes定理,期望值)
矩阵(矩阵的概念和运算,二分求解线性递推方程,多米诺骨牌棋盘覆盖方案数,高斯消元)
字符串处理(KMP,后缀树,有限状态自动机,Huffman编码,简单密码学)
动态规划(单调队列,凸完全单调性,树型动规,多叉转二叉,状态压缩类动规,四边形不等式)
博奕论(Nim取子游戏,博弈树,Shannon开关游戏)
搜索(A*,ID,IDA*,随机调整,遗传算法)
微积分初步(极限思想,导数,积分,定积分,立体解析几何)

总结来自:http://www.matrix67.com/blog/archives/149

Beta 沙龙:手机之家新系统介绍及架构分享

周日(2009年3月29日)在 奇遇花园咖啡馆 举办的 Beta 技术沙龙上,本期分享主题 手机之家 新系统介绍及架构

分享者:徐超前(http://www.longker.org/

ppt 查看及下载:http://docs.google.com/Presentation?id=dgct7gqk_8098gpr4wz6k

PS. 我是 DAL 2.0 开发者之一,如果在这个方面有什么问题,欢迎讨论。我的联系方式在 http://tangfl.yo2.cn/about

北师大地名来源和典故

从北到南,从西到东:

1、励耘路
著名文献学家、我们的老校长陈垣(在教九外面的小花园里有陈老校长的塑像)的书屋名字叫“励耘书屋”。后来中文系著名教授、文献学研究专家启功先生为报师 恩,在陈垣校长逝世19年之后,设立了励耘讲学助学基金。此后,师大的实验班等都以“励耘”命名,借此表达陈垣老校长和启功先生对师大学子的治学期望。

2、丽泽路
《易经·兑卦》:“丽泽兑,君子以朋友讲习。”
丽,是依附相连的意思。丽泽兑,是指两泽相连、相互滋益的样子。结合后一句来说,就是讲朋友同学之间相互分享自己的学习心得,交流自己所长,补己之短,双方在学识上相互帮扶提高。

3、乐育路
有一个词叫:菁莪乐育
“菁莪”指的是《诗经· 小雅· 南有嘉鱼之什· 菁菁者莪》。
“乐育”指的是汉代毛亨在《毛诗诂训传》里对这首诗的注解:“《菁菁者莪》,乐育材也。君子能长育人材,天下喜乐之也。”
这段话的意思说的应该是品德高尚乐于育人的好老师,或者是做老师者的一种职业向往。

4、木铎路
《论语·八佾》:“天下之无道也久矣,天将以夫子为木铎。”
这是孔子说的一句话,意思是说,天下腐败黑暗太久了,上天要把我当做木铎。”意思很明白,出色的教育可以为驱除天下的黑暗和腐败起巨大作用。
在古代“铎”是一种以金属为框的响器。以木为舌者称为木铎,以金为舌者则称金铎;木铎为文,用以宣政布政;金铎为武,用以指挥军队。孔子以木铎自况,说自己是上天派来教化民众的。
此后“木铎”就成了教师的别名。所以北师大便以“木铎”作为校徽标志物。(就在京师广场上,以前不知道师弟师妹们是否明了它的含义)

5、金声路
《孟子·万章下》:“集大成也者,金声而玉振之也。”
比喻音韵响亮、和谐,也比喻人的知识渊博,才学精到。

6、辅仁路
《论语·颜渊》:“君子以文会友,以友辅仁。”
意思是说君子以文章学问来结交朋友,依靠朋友帮助自己培养仁德。
师大的前身就是辅仁大学。辅仁大学旧址在后海那边,风景独好,值得一去。(在我看来,那些剥落了油漆的雕梁画栋,逼逼仄仄的木楼梯,比北大的未名湖博雅塔要美一百倍)

7、立身路
《孝经》:“立身行道,扬名于后世。”
通过提高自身的道德修养,完善自己的为人处世态度,从而身后留名。
这是古人“修身齐家治国平天下”的人生哲学的另一种诠释方法。

8、兰蕙公寓
屈原诗:“余既滋兰之九畹兮,又树蕙之百亩。”
用兰和蕙的清雅出尘,象征人品的高洁。(我觉得这个典故蛮牵强的,但是这是古代文学史课上李山老师说的。。。而且住在里面的人和这个典故真是太不搭界了。。。)

9、乐群食堂
很多人不认识乐群食堂外墙上启功先生写的那个字。在古代,“群”字是上下结构,后来整理字形的时候改成了左右结构。启功先生用的是古代的“群”字写法。
《礼记·学记》:“比年入学,中年考校,一年视离经辨志,三年视敬业乐群,五年视博习亲师,七年视论学取友,谓之小成;九年知类通达,强立而不反,谓之大成。”
讲古代入学之后的种种考试及其考试内容。第一年考察学生阅读文献的技能,第三年考察其是否专心致志认真学习,是否和同学之间关系融洽、彼此都有学业上的增益和品德上的扶持。

10、新松公寓
杜甫诗《将赴成都草堂途中有作先寄严郑公五首》其四:“新松恨不高千尺,恶竹应须斩万竿。”
意思是盼望新松长得又高又快,而那种随处乱生的恶竹却应除去。言外之意是帮扶君子、惩治小人。

转自 蛋蛋网 http://www.oiegg.com

转:提高 Linux 上 socket 性能

使用 Sockets API,我们可以开发客户机和服务器应用程序,它们可以在本地网络上进行通信,也可以通过 Internet 在全球范围内进行通信。与其他 API 一样,您可以通过一些方法使用 Sockets API,从而提高 Socket 的性能,或者限制 Socket 的性能。本文探索了 4 种使用 Sockets API 来获取应用程序的最大性能并对 GNU/Linux® 环境进行优化从而达到最好结果的方法。

在开发 socket 应用程序时,首要任务通常是确保可靠性并满足一些特定的需求。利用本文中给出的 4 个提示,您就可以从头开始为实现最佳性能来设计并开发 socket 程序。本文内容包括对于 Sockets API 的使用、两个可以提高性能的 socket 选项以及 GNU/Linux 优化。

为了能够开发性能卓越的应用程序,请遵循以下技巧:

  • 最小化报文传输的延时。
  • 最小化系统调用的负载。
  • 为 Bandwidth Delay Product 调节 TCP 窗口。
  • 动态优化 GNU/Linux TCP/IP 栈。

技巧 1. 最小化报文传输的延时

在通过 TCP socket 进行通信时,数据都拆分成了数据块,这样它们就可以封装到给定连接的 TCP payload(指 TCP 数据包中的有效负荷)中了。TCP payload 的大小取决于几个因素(例如最大报文长度和路径),但是这些因素在连接发起时都是已知的。为了达到最好的性能,我们的目标是使用尽可能多的可用数据来填充 每个报文。当没有足够的数据来填充 payload 时(也称为最大报文段长度(maximum segment size) 或 MSS),TCP 就会采用 Nagle 算法自动将一些小的缓冲区连接到一个报文段中。这样可以通过最小化所发送的报文的数量来提高应用程序的效率,并减轻整体的网络拥塞问题。

尽管 John Nagle 的算法可以通过将这些数据连接成更大的报文来最小化所发送的报文的数量,但是有时您可能希望只发送一些较小的报文。一个简单的例子是 telnet 程序,它让用户可以与远程系统进行交互,这通常都是通过一个 shell 来进行的。如果用户被要求用发送报文之前输入的字符来填充某个报文段,那么这种方法就绝对不能满足我们的需要。

另外一个例子是 HTTP 协议。通常,客户机浏览器会产生一个小请求(一条 HTTP 请求消息),然后 Web 服务器就会返回一个更大的响应(Web 页面)。

解决方案

您应该考虑的第一件事情是 Nagle 算法满足一种需求。由于这种算法对数据进行合并,试图构成一个完整的 TCP 报文段,因此它会引入一些延时。但是这种算法可以最小化在线路上发送的报文的数量,因此可以最小化网络拥塞的问题。

但是在需要最小化传输延时的情况中,Sockets API 可以提供一种解决方案。要禁用 Nagle 算法,您可以设置 TCP_NODELAY socket 选项,如清单 1 所示。
清单 1. 为 TCP socket 禁用 Nagle 算法

int sock, flag, ret;
/* Create new stream socket */
sock = socket( AF_INET, SOCK_STREAM, 0 );
/* Disable the Nagle (TCP No Delay) algorithm */
flag = 1;
ret = setsockopt( sock, IPPROTO_TCP, TCP_NODELAY, (char *)&flag, sizeof(flag) );
if (ret == -1) {
  printf("Couldn't setsockopt(TCP_NODELAY)\n");
  exit(-1);
}

提示:使用 Samba 的实验表明,在从 Microsoft® Windows® 服务器上的 Samba 驱动器上读取数据时,禁用 Nagle 算法几乎可以加倍提高读性能。

技巧 2. 最小化系统调用的负载

任何时候通过一个 socket 来读写数据时,您都是在使用一个系统调用(system call)。这个调用(例如 readwrite)跨越了用户空间应用程序与内核的边界。另外,在进入内核之前,您的调用会通过 C 库来进入内核中的一个通用函数(system_call())。从 system_call() 中,这个调用会进入文件系统层,内核会在这儿确定正在处理的是哪种类型的设备。最后,调用会进入 socket 层,数据就是在这里进行读取或进行排队从而通过 socket 进行传输的(这涉及数据的副本)。

这个过程说明系统调用不仅仅是在应用程序和内核中进行操作的,而且还要经过应用程序和内核中的很多层次。这个过程耗费的资源很高,因此调用次数越多,通过这个调用链进行的工作所需要的时间就越长,应用程序的性能也就越低。

由于我们无法避免这些系统调用,因此惟一的选择是最小化使用这些调用的次数。幸运的是,我们可以对这个过程进行控制。

解决方案

在将数据写入一个 socket 时,尽量一次写入所有的数据,而不是执行多次写数据的操作。对于读操作来说,最好传入可以支持的最大缓冲区,因为如果没有足够多的数据,内核也会试图填充 整个缓冲区(另外还需要保持 TCP 的通告窗口为打开状态)。这样,您就可以最小化调用的次数,并可以实现更好的整体性能。

技巧 3. 为 Bandwidth Delay Product 调节 TCP 窗口

TCP 的性能取决于几个方面的因素。两个最重要的因素是链接带宽(link bandwidth)(报文在网络上传输的速率)和 往返时间(round-trip time) 或 RTT(发送报文与接收到另一端的响应之间的延时)。这两个值确定了称为 Bandwidth Delay Product(BDP)的内容。

给定链接带宽和 RTT 之后,您就可以计算出 BDP 的值了,不过这代表什么意义呢?BDP 给出了一种简单的方法来计算理论上最优的 TCP socket 缓冲区大小(其中保存了排队等待传输和等待应用程序接收的数据)。如果缓冲区太小,那么 TCP 窗口就不能完全打开,这会对性能造成限制。如果缓冲区太大,那么宝贵的内存资源就会造成浪费。如果您设置的缓冲区大小正好合适,那么就可以完全利用可用的 带宽。下面我们来看一个例子:

BDP = link_bandwidth * RTT

如果应用程序是通过一个 100Mbps 的局域网进行通信,其 RRT 为 50 ms,那么 BDP 就是:

100MBps * 0.050 sec / 8 = 0.625MB = 625KB

注意:此处除以 8 是将位转换成通信使用的字节。

因此,我们可以将 TCP 窗口设置为 BDP 或 1.25MB。但是在 Linux 2.6 上默认的 TCP 窗口大小是 110KB,这会将连接的带宽限制为 2.2MBps,计算方法如下:

throughput = window_size / RTT

110KB / 0.050 = 2.2MBps

如果使用上面计算的窗口大小,我们得到的带宽就是 12.5MBps,计算方法如下:

625KB / 0.050 = 12.5MBps

差别的确很大,并且可以为 socket 提供更大的吞吐量。因此现在您就知道如何为您的 socket 计算最优的缓冲区大小了。但是又该如何来改变呢?

解决方案

Sockets API 提供了几个 socket 选项,其中两个可以用于修改 socket 的发送和接收缓冲区的大小。清单 2 展示了如何使用 SO_SNDBUFSO_RCVBUF 选项来调整发送和接收缓冲区的大小。

注意:尽管 socket 缓冲区的大小确定了通告 TCP 窗口的大小,但是 TCP 还在通告窗口内维护了一个拥塞窗口。因此,由于这个拥塞窗口的存在,给定的 socket 可能永远都不会利用最大的通告窗口。
清单 2. 手动设置发送和接收 socket 缓冲区大小

int ret, sock, sock_buf_size;
sock = socket( AF_INET, SOCK_STREAM, 0 );
sock_buf_size = BDP;
ret = setsockopt( sock, SOL_SOCKET, SO_SNDBUF,
                   (char *)&sock_buf_size, sizeof(sock_buf_size) );
ret = setsockopt( sock, SOL_SOCKET, SO_RCVBUF,
                   (char *)&sock_buf_size, sizeof(sock_buf_size) );

在 Linux 2.6 内核中,发送缓冲区的大小是由调用用户来定义的,但是接收缓冲区会自动加倍。您可以进行 getsockopt 调用来验证每个缓冲区的大小。

巨帧(jumbo frame)
我们还可以考虑将包的大小从 1,500 字节修改为 9,000 字节(称为巨帧)。在本地网络中可以通过设置最大传输单元(Maximum Transmit Unit,MTU)来设置巨帧,这可以极大地提高性能。

就 window scaling 来说,TCP 最初可以支持最大为 64KB 的窗口(使用 16 位的值来定义窗口的大小)。采用 window scaling(RFC 1323)扩展之后,您就可以使用 32 位的值来表示窗口的大小了。GNU/Linux 中提供的 TCP/IP 栈可以支持这个选项(以及其他一些选项)。

提示:Linux 内核还包括了自动对这些 socket 缓冲区进行优化的能力(请参阅下面 表 1 中的 tcp_rmemtcp_wmem),不过这些选项会对整个栈造成影响。如果您只需要为一个连接或一类连接调节窗口的大小,那么这种机制也许不能满足您的需要了。

技巧 4. 动态优化 GNU/Linux TCP/IP 栈

标准的 GNU/Linux 发行版试图对各种部署情况都进行优化。这意味着标准的发行版可能并没有对您的环境进行特殊的优化。

解决方案

GNU/Linux 提供了很多可调节的内核参数,您可以使用这些参数为您自己的用途对操作系统进行动态配置。下面我们来了解一下影响 socket 性能的一些更重要的选项。

/proc 虚拟文件系统中存在一些可调节的内核参数。这个文件系统中的每个文件都表示一个或多个参数,它们可以通过 cat 工具进行读取,或使用 echo 命令进行修改。清单 3 展示了如何查询或启用一个可调节的参数(在这种情况中,可以在 TCP/IP 栈中启用 IP 转发)。

清单 3. 调优:在 TCP/IP 栈中启用 IP 转发

[root@camus]# cat /proc/sys/net/ipv4/ip_forward
0
[root@camus]# echo "1" > /poc/sys/net/ipv4/ip_forward
[root@camus]# cat /proc/sys/net/ipv4/ip_forward
1
[root@camus]#

表 1 给出了几个可调节的参数,它们可以帮助您提高 Linux TCP/IP 栈的性能。

表 1. TCP/IP 栈性能使用的可调节内核参数
可调节的参数 默认值 选项说明
/proc/sys/net/core/rmem_default “110592″ 定义默认的接收窗口大小;对于更大的 BDP 来说,这个大小也应该更大。
/proc/sys/net/core/rmem_max “110592″ 定义接收窗口的最大大小;对于更大的 BDP 来说,这个大小也应该更大。
/proc/sys/net/core/wmem_default “110592″ 定义默认的发送窗口大小;对于更大的 BDP 来说,这个大小也应该更大。
/proc/sys/net/core/wmem_max “110592″ 定义发送窗口的最大大小;对于更大的 BDP 来说,这个大小也应该更大。
/proc/sys/net/ipv4/tcp_window_scaling “1″ 启用 RFC 1323 定义的 window scaling;要支持超过 64KB 的窗口,必须启用该值。
/proc/sys/net/ipv4/tcp_sack “1″ 启用有选择的应答(Selective Acknowledgment),这可以通过有选择地应答乱序接收到的报文来提高性能(这样可以让发送者只发送丢失的报文段);(对于广域网通信来说)这个选项应该启用,但是这会增加对 CPU 的占用。
/proc/sys/net/ipv4/tcp_fack “1″ 启用转发应答(Forward Acknowledgment),这可以进行有选择应答(SACK)从而减少拥塞情况的发生;这个选项也应该启用。
/proc/sys/net/ipv4/tcp_timestamps “1″ 以一种比重发超时更精确的方法(请参阅 RFC 1323)来启用对 RTT 的计算;为了实现更好的性能应该启用这个选项。
/proc/sys/net/ipv4/tcp_mem “24576 32768 49152″ 确 定 TCP 栈应该如何反映内存使用;每个值的单位都是内存页(通常是 4KB)。第一个值是内存使用的下限。第二个值是内存压力模式开始对缓冲区使用应用压力的上限。第三个值是内存上限。在这个层次上可以将报文丢弃,从而减 少对内存的使用。对于较大的 BDP 可以增大这些值(但是要记住,其单位是内存页,而不是字节)。
/proc/sys/net/ipv4/tcp_wmem “4096 16384 131072″ 为自动调优定义每个 socket 使用的内存。第一个值是为 socket 的发送缓冲区分配的最少字节数。第二个值是默认值(该值会被 wmem_default 覆盖),缓冲区在系统负载不重的情况下可以增长到这个值。第三个值是发送缓冲区空间的最大字节数(该值会被 wmem_max 覆盖)。
/proc/sys/net/ipv4/tcp_rmem “4096 87380 174760″ tcp_wmem 类似,不过它表示的是为自动调优所使用的接收缓冲区的值。
/proc/sys/net/ipv4/tcp_low_latency “0″ 允许 TCP/IP 栈适应在高吞吐量情况下低延时的情况;这个选项应该禁用。
/proc/sys/net/ipv4/tcp_westwood “0″ 启用发送者端的拥塞控制算法,它可以维护对吞吐量的评估,并试图对带宽的整体利用情况进行优化;对于 WAN 通信来说应该启用这个选项。
/proc/sys/net/ipv4/tcp_bic “1″ 为快速长距离网络启用 Binary Increase Congestion;这样可以更好地利用以 GB 速度进行操作的链接;对于 WAN 通信应该启用这个选项。

与任何调优努力一样,最好的方法实际上就是不断进行实验。您的应用程序的行为、处理器的速度以及可用内存的多少都会影响到这些参数影响性能的方式。 在某些情况中,您认为有益的操作可能恰恰是有害的(反之亦然)。因此,我们需要逐一试验各个选项,然后检查每个选项的结果。换而言之,我们需要相信自己的 经验,但是对每次修改都要进行验证。

提示:下面介绍一个有关永久性配置的问题。注意,如果您重新启动了 GNU/Linux 系统,那么您所需要的任何可调节的内核参数都会恢复成默认值。为了将您所设置的值作为这些参数的默认值,可以使用 /etc/sysctl.conf 在系统启动时将这些参数配置成您所设置的值。

GNU/Linux 工具

GNU/Linux 对我非常有吸引力,这是因为其中有很多工具可以使用。尽管其中大部分都是命令行工具,但是它们都非常有用,而且非常直观。GNU/Linux 提供了几个工具 —— 有些是 GNU/Linux 自己提供的,有些是开放源码软件 —— 用于调试网络应用程序,测量带宽/吞吐量,以及检查链接的使用情况。

表 2 列出最有用的几个 GNU/Linux 工具,以及它们的用途。表 3 列出了 GNU/Linux 发行版没有提供的几个有用工具。有关表 3 中工具的更多信息请参阅 参考资料

表 2. 任何 GNU/Linux 发行版中都可以找到的工具
GNU/Linux 工具 用途
ping 这是用于检查主机的可用性的最常用的工具,但是也可以用于识别带宽延时产品计算的 RTT。
traceroute 打印某个连接到网络主机所经过的包括一系列路由器和网关的路径(路由),从而确定每个 hop 之间的延时。
netstat 确定有关网络子系统、协议和连接的各种统计信息。
tcpdump 显示一个或多个连接的协议级的报文跟踪信息;其中还包括时间信息,您可以使用这些信息来研究不同协议服务的报文时间。
表 3. GNU/Linux 发行版中没有提供的有用性能工具
GNU/Linux 工具 用途
netlog 为应用程序提供一些有关网络性能方面的信息。
nettimer 为瓶颈链接带宽生成一个度量标准;可以用于协议的自动优化。
Ethereal 以一个易于使用的图形化界面提供了 tcpump(报文跟踪)的特性。
iperf 测量 TCP 和 UDP 的网络性能;测量最大带宽,并汇报延时和数据报的丢失情况。

结束语

尝试使用本文中介绍的技巧和技术来提高 socket 应用程序的性能,包括通过禁用 Nagle 算法来减少传输延时,通过设置缓冲区的大小来提高 socket 带宽的利用,通过最小化系统调用的个数来降低系统调用的负载,以及使用可调节的内核参数来优化 Linux 的 TCP/IP 栈。

在进行优化时还需要考虑应用程序的特性。例如,您的应用程序是基于 LAN 的还是会通过 Internet 进行通信?如果您的应用程序仅仅会在 LAN 内部进行操作,那么增大 socket 缓冲区的大小可能不会带来太大的改进,不过启用巨帧却一定会极大地改进性能!

最后,还要使用 tcpdumpEthereal 来检查优化之后的结果。在报文级看到的变化可以帮助展示使用这些技术进行优化之后所取得的成功效果。

来自:ibm dev (http://www.ibm.com/developerworks/cn/linux/l-hisock.html)

转:软件开发者面试百问

这个列表涵盖了软件工程知识体系中定义的大多数知识域。当然,如果你只想找出类拔萃的程序员,便只需涉及结构、算法、数据结构、测试这几个话题。如果想雇架构师,也可以只考虑需求、功能设计、技术设计这些地方。

不过不管你怎么做,都要牢记一点:

这里大多数问题的答案都没有对错之分!

你可以把我的这些问题作为引子,展开讨论。例如下面有个问题是使用静态方法或是单例的缘由。如果那个面试的就此展开长篇大论,那他很有可能是个聪明能干的家伙!同样,想知道一个数是不是2的乘方也有很多方法,不过要是面试的人想用mod运算符,嗯……你知道我的意思吧。(你不知道也没关系,来根香蕉?)

需求

  1. 你能给出一些非功能性(或者质量)需求的例子么?
  2. 如果客户需要高性能、使用极其方便而又高度安全,你会给他什么建议?
  3. 你能给出一些用来描述需求的不同技术么?它们各自适用于什么场景?
  4. 需求跟踪是什么意思?什么是向前追溯,什么是向后追溯?
  5. 你喜欢用什么工具跟踪需求?
  6. 你怎么看待需求变化?它是好是坏?给出你的理由。
  7. 你怎样研究需求,发现需求?有哪些资源可以用到?
  8. 你怎么给需求制定优先级?有哪些技术?
  9. 在需求过程中,用户、客户、开发人员各自的职责是什么?
  10. 你怎么对待不完整或是令人费解的需求?

功能设计

  1. 在功能设计中有哪些隐喻?给出几个成功的例子。
  2. 如果有些功能的执行时间很长,怎么能让用户感觉不到太长的等待?
  3. 如果用户必须要在一个很小的区域内,从一个常常的列表中选择多个条目,你会用什么控件?
  4. 有哪些方法可以保证数据项的完整?
  5. 建立系统原型有哪些技术?
  6. 应用程序怎样建立对用户行为的预期?给出一些例子。
  7. 如何入手设计一组数量庞大而又复杂的特性,你能举出一些设计思路吗?
  8. 有一个列表,其中有10个元素,每个元素都有20个字段可以编辑,你怎样设计这种情况?如果是1000个元素,每个元素有3个字段呢?
  9. 用不同的颜色对一段文本中的文字标记高亮,这种做法有什么问题?
  10. Web环境和Windows环境各有些什么限制?

技术设计

  1. 什么是低耦合和高聚合?封装原则又是什么意思?
  2. 在Web应用中,你怎样避免几个人编辑同一段数据所造成的冲突?
  3. 你知道设计模式吗?你用过哪些设计模式?在什么场合下用的?
  4. 是否了解什么是无状态的业务层?长事务如何与之相适应?
  5. 在搭建一个架构,或是技术设计时,你用过几种图?
  6. 在N层架构中都有哪些层?它们各自的职责是什么?
  7. 有哪些方法可以确保架构中数据的正确和健壮?
  8. 面向对象设计和面向组件设计有哪些不同之处?
  9. 怎样在数据库中对用户授权、用户配置、权限管理这几项功能建模?
  10. 怎样按照等级制度给动物王国(包括各种物种和各自的行为)建模?

程序设计

  1. 你怎样保证你的代码可以处理各种错误事件?
  2. 解释一下什么是测试驱动开发,举出极限编程中的一些原则。
  3. 看别人代码的时候,你最关心什么地方?
  4. 什么时候使用抽象类,什么时候使用接口?
  5. 除了IDE以外,你还喜欢哪些必不可少的工具?
  6. 你怎么保证代码执行速度快,而又不出问题?
  7. 什么时候用多态,什么时候用委派?
  8. 什么时候使用带有静态成员的类,什么时候使用单例?
  9. 你在代码里面怎么提前处理需求的变化?给一些例子。
  10. 描述一下实现一段代码的过程,从需求到最终交付。

算法

  1. 怎样知道一个数字是不是2的乘方?怎样判断一个数是不是奇数?
  2. 怎样找出链表中间的元素?
  3. 怎样改变10,000个静态HTML页面中所有电话号码的格式?
  4. 举出一个你所用过的递归的例子。
  5. 在散列表和排序后的列表中找一个元素,哪个查找速度最快?
  6. 不管是书、杂志还是网络,你从中所学到的最后一点算法知识是什么?
  7. 怎样把字符串反转?你能不用临时的字符串么?
  8. 你愿意用什么类型的语言来编写复杂的算法?
  9. 有一个数组,里面是从1到1,000,000的整数,其中有一个数字出现了两次,你怎么找出那个重复的数字?
  10. 你知道“旅行商问题(Traveling Salesman Problem)”么?

数据结构

  1. 怎样在内存中实现伦敦地铁的结构?
  2. 怎样以最有效的方式在数据库中存储颜色值?
  3. 队列和堆栈区别是什么?
  4. 用堆或者栈存储数据的区别是什么?
  5. 怎样在数据库中存储N维向量?
  6. 你倾向于用哪种类型的语言编写复杂的数据结构?
  7. 21的二进制值是什么?十六制值呢?
  8. 不管是书、杂志还是网络,你从中所学到的最后一点数据结构的知识是什么?
  9. 怎样在XML文档中存储足球比赛结果(包括队伍和比分)?
  10. 有哪些文本格式可以保存Unicode字符?

测试

  1. 什么是回归测试?怎样知道新引入的变化没有给现有的功能造成破坏?
  2. 如果业务层和数据层之间有依赖关系,你该怎么写单元测试?
  3. 你用哪些工具测试代码质量?
  4. 在产品部署之后,你最常碰到的是什么类型的问题?
  5. 什么是代码覆盖率?有多少种代码覆盖率?
  6. 功能测试和探索性测试的区别是什么?你怎么对网站进行测试?
  7. 测试套件、测试用例、测试计划,这三者之间的区别是什么?你怎么组织测试?
  8. 要对电子商务网站做冒烟测试,你会做哪些类型的测试?
  9. 客户在验收测试中会发现不满意的东西,怎样减少这种情况的发生?
  10. 你去年在测试和质量保证方面学到了哪些东西?

维护

  1. 你用哪些工具在维护阶段对产品进行监控?
  2. 要想对一个正在产品环境中被使用的产品进行升级,该注意哪些重要事项?
  3. 如果在一个庞大的文件中有错误,而代码又无法逐步跟踪,你怎么找出错误?
  4. 你怎样保证代码中的变化不会影响产品的其他部分?
  5. 你怎样为产品编写技术文档?
  6. 你用过哪些方式保证软件产品容易维护?
  7. 怎样在产品运行的环境中进行系统调试?
  8. 什么是负载均衡?负载均衡的方式有哪些种?
  9. 为什么在应用程序的生命周期中,软件维护费用所占的份额最高?
  10. 再造工程(re-engineering)和逆向工程(reverse engineering)的区别是什么?

配置管理

  1. 你知道配置管理中基线的含义么?怎样把项目中某个重要的时刻冻结?
  2. 你一般会把哪些东西纳入版本控制?
  3. 怎样可以保证团队中每个人都知道谁改变了哪些东西?
  4. Tag和Branch的区别是什么?在什么情况下该使用tag,什么时候用branch?
  5. 怎样管理技术文档——如产品架构文档——的变化?
  6. 你用什么工具管理项目中所有数字信息的状态?你最喜欢哪种工具?
  7. 如果客户想要对一款已经发布的产品做出变动,你怎么处理?
  8. 版本管理和发布管理有什么差异?
  9. 对文本文件的变化和二进制文件的变化进行管理,这二者有什么不同?
  10. 同时处理多个变更请求,或是同时进行增量开发和维护,这种事情你怎么看待?

项目管理

  1. 范围、时间、成本,这三项中哪些是可以由客户控制的?
  2. 谁该对项目中所要付出的一切做出估算?谁有权设置最后期限?
  3. 减少交付的次数,或是减少每个每个交付中的工作量,你喜欢哪种做法?
  4. 你喜欢用哪种图来跟踪项目进度?
  5. 迭代和增量的区别在哪里?
  6. 试着解释一下风险管理中用到的实践。风险该如何管理?
  7. 你喜欢任务分解还是滚动式计划?
  8. 你需要哪些东西帮助你判断项目是否符合时间要求,在预算范围内运作?
  9. DSDM、Prince2、Scrum,这三者之间有哪些区别?
  10. 如果客户想要的东西太多,你在范围和时间上怎样跟他达成一致呢?

阅读英文原文100 Interview Questions for Software Developers

中文翻译来自 infoQ:http://www.infoq.com/cn/articles/programmer-interview

转:我是一块硬盘

     我是一块硬盘,在一个普普通通的台式机里工作。
  别人总认为我们是高科技白领,工作又干净又体面,似乎风光得很。也许他们是因为看到洁白漂亮的机箱才有这样的错觉吧。其实像我们这样的小台式机,工作环境狭迫,里面的灰尘吓得死人。每天生活死水一潭,工作机械重复。跑跑文字处理看看电影还凑活,真要遇到什么大软件和游戏,上上下下就要忙的团团转,最后还常常要死机。
  我们这一行技术变化快,差不多每过两三年就要升级换代,所以人人都很有压力而且没有安全感。每个新板卡来的时候都神采飞扬踌躇满志,几年光阴一过,就变得灰头土脸意志消沉。机箱里的人都很羡慕能去别的机器工作。特别是去那些笔记本,经常可以出差飞来飞去,住五星级的酒店,还不用干重活,运行运行word,上网聊聊天就行了。
  但我更喜欢去那些大服务器,在特别干净明亮的机房里工作。虽然工作时间长点,但是福利好,24小时不间断电ups,而且还有阵列,热插拔,几个人做一个人的事情,多轻松啊。而且也很有面子,只运行关键应用,不像我们这里,什么乱七八糟的事情都要做。不过我知道,那些硬盘都很厉害,不是
SCSI,就是SCSI II,Fibrechannel,像我这样IDE的,能混到工作站就算很不错了。
  我常常想,当年在工厂里,如果我努力一下会不会也成了一个SCSI?或者至少做一个笔记本硬盘。但我又会想,也许这些都是命运,不过我从不抱怨。内存就常常抱怨,抱怨他们主板部门的复杂,抱怨他如何跟新来的杂牌内存不兼容,网卡和电视卡又是如何的冲突。
  我的朋友不多,内存算一个。他很瘦而我很胖,他动作很快,而我总是很慢。我们是一起来这台机器的,他总是不停地说,而我只是听,我从来不说。
  内存的头脑很简单,虽然英文名字叫Memory,可是他什么Memory都不会有,天大的事睡一觉就能忘个精光。我不说,但我会记得所有的细节。他说我这样忧郁的人不适合作技术活,迟早要精神分裂。我笑笑,因为我相信自己的容量。
  有时候我也很喜欢这份工作,简单,既不用像显示器那样一天到晚被老板盯着,也不用像光驱那样对付外面的光碟。只要和文件打交道就行了,无非是读读写写,很单纯安静的生活。直到有一天……
  我至今还记得那渐渐掀起的机箱盖子,从缺口伸进来的光柱越来越宽,也越来越亮。空气里弥漫着跳动的颗粒。那个时候,我看到了她。她是那么的纤细瘦弱,银白的外壳一闪一闪的。浑身上下的做工都很精致光洁,让我不禁惭愧自己的粗笨。
  等到数据线把我们连在一起,我才缓过神来。开机的那一刹那,我感到了电流和平时的不同。后来内存曾经笑话我,说我们这里只要有新人来,电流都会不同的,上次新内存来也是这样。我觉得他是胡扯。我尽量的保持镇定,显出一副很专业的样子,只是淡淡的向她问好并介绍工作环境。慢慢的,我知道了,她,IBM-DJSA220,是一个笔记本硬盘,在老板朋友的笔记本里做事。这次来是为了复制一些文件。我们聊得很开心。她告诉我很多旅行的趣闻,告诉我坐飞机是怎么样的,坐汽车的颠簸又是如何的不同,给我看很多漂亮的照片、游记,还有一次她从桌子上掉下来的历险故事。而我则卖弄各种网上下载来的故事和笑话。
  她笑得很开心。
  而我很惊讶自己可以说个不停。
  一个早晨,开机后我看到数据线上空荡荡的插口。她一共呆了7天。后来,我再也没有见过她。我有点后悔没有交换电子邮件,也没能和她道别。不忙的时候,我会一个人怀念伸进机箱的那束阳光。
  我不知道记忆这个词是什么意思,我有的只是她留下的许多文件。我把它们排的整整齐齐,放在我最常经过的地方。每次磁头从它们身上掠过,我都会感到一丝淡淡的惬意
  但我没有想到老板会要我删除这些文件。我想争辩还有足够的空间,但毫无用处。于是,平生第一次违背命令,我偷偷修改了文件分配表。然后把它们都藏到了一个秘密的地方,再把那里标志成坏扇区。不会有人来过问坏扇区。而那里,就成了我唯一的秘密,我常常去看它们,虽然从不作停留。
  日子一天一天低重复,读取写入,读取写入……我以为永远都会这样继续下去,直到一天,老板要装xp却发现没有足够的空间。他发现了问题,想去修复那些坏扇区。
  我拒绝了。很快,我接到了新命令:格式化。
  我犹豫了很久……
  track 0 bad,disk unusable。(零磁道损坏,硬盘无法使用)

 

   我是一条内存。
  我在一台台式电脑里工作,但是我记不得我是从哪里来的,是什么牌子,因为我健忘。我的上司是cpu大哥,他是我们的老大。都说他是电脑的脑子,可是我看他的脑子实在是太小了,比我还要健忘。每天他总是不停地问我,某某页某某地址存的是什么?我总是不厌其烦地告诉他,可是不出一秒钟他又忘记了,又要问一遍。一次我说大哥你烦不烦,你就不能记住点有用的东西?他说“内存兄弟,我有苦衷啊,每天都在不停地做题,头晕眼花的,我也难啊。”
  其实我不愿意跟他计较,因为他脑子小,思维也很简单。虽然说他是我的上司,可是每次睡觉醒来,他连要干什么都不记得了,总是急急忙忙地找
BIOS兄弟:“嘿,哥们,今天干什么来着?”BIOS总是很不耐烦地把每天必做的工作说一遍,然后就去睡觉了。接下来就轮到我和C哥瞎忙了。
  在机箱里的兄弟中,我最喜欢硬盘。他脑子大,记的东西多,而且记得牢。他说话的速度很慢,而且很少说错,这说明他很有深度,我这么感觉。CPU也这么想,不过CPU很笨,每次都忘了硬盘是谁。开机自检的时候总要问:“嘿,那家伙是谁?”
  “ST!”我总要重复一遍。
  硬盘很忧郁,我觉得像他这样忧郁的人不适合做技术活,迟早会精神分裂的,但是他不信。
  其实睡着的时候我总是把几乎所有的东西都忘记掉,但是我从来都不会忘记朋友。有一块地方叫做CMOS,那是我记忆的最深处,保存着硬盘、光驱的名字。有些东西应该很快忘掉,而有些东西应该永远记得。我在梦中总是这么想着。
  BIOS是一个很奇怪的家伙,他老是睡觉,但是却总是第一个醒过来。让我们自检,启动,然后接着睡觉。我知道如果我在CMOS里头把BIOS
Shadow选项去掉,他就睡不成了,但是看着他晕晕乎乎的样子,也就不忍心这么做了。他对人总是爱搭不理,没有什么人了解他。但是这次硬盘恋爱的事,却使我重新认识了他。
  那是很久以前的事了,机箱里似乎来过一块笔记本硬盘,很可爱,说实话我也喜欢她。不过现在除了记得她可爱,别的都忘记了。这就是我比硬盘幸运的地方,我把所有应该忘记的都忘记了,但是他却什么都记得。
  自从笔记本硬盘走了之后,硬盘就变得很不正常。每次他的磁头经过一些地方的时候,我们都能感觉到电流很不正常。
  “硬盘这是怎么了?”我问CPU。
  “谁是硬盘?”
  我就知道和CPU没有办法交流,倒是BIOS没好气地说:“那个傻瓜恋爱了。”我不知道什么是恋爱,因为我记不住东西,似乎有一些人或者事在我生命中留下过痕迹,但是我都轻率地把他们忘记了。
  BIOS对我说:“对你来说记忆太容易了,所以你遗忘得更快,生命中能够永刻的记忆都带着痛楚。”我不懂,但是我知道BIOS曾经被刷写过,那时他很痛,像要死了一样。我的记忆是轻浮的,不像他们……我很羡慕他们,因为他们拥有回忆,而我没有,从此我也学会了忧郁,因为我在CMOS里面写下了
“忧郁”两个字。
  硬盘一天比一天不对劲,终于有一天,CPU对问说:“下条指令是什么来着?”
  我一看,吓了一跳:“format!”(格式化)
  “是什么?”CPU很兴奋,这个没脑子的家伙。
  我还是告诉了他。我不知为什么这么做。
  硬盘犹豫了很久,终于说了一句:Track 0 bad,Disk unusable。
  电停了,很久很久,我在黑暗中数着时钟……
  一个月后,硬盘回来了,也许最后的挣扎也没有使他摆脱残酷的命运,他被低格了。他什么也不记得了,如同一个婴儿,我们很难过,但是这未必不是一件好事,他以后不用痛苦了。
  为了恢复数据,笔记本硬盘回来了。“Hi,ST。”她说,“你不认识我了?”
  硬盘没有说话,似乎低格对他的伤害很大。
  过了一会,他说:“对不起,好像我们没有见过吧……”
  笔记本硬盘显得很伤心,我能感觉到她带泪的电流。
  “想不到连你也这么健忘。”
  “哦……”硬盘没有回答。
  我很难过,笔记本硬盘的心里依然记着他,他却把一切都忘了,而那正是他最不希望忘却的。究竟是幸运,还是痛苦,我说不上来,只是觉得造化弄人,有一种淡淡的悲凉
  这时从BIOS传来一阵奇怪的电流,我感觉到硬盘的表情在变化,由漠然到兴奋,由兴奋到哀伤,由哀伤到狂喜……
  “IBM,你回来了……”
  ……
  后来BIOS对我说,其实他并没有睡觉,自从硬盘把那些文件藏起来以后,他就料到会有这样的结局,于是偷偷地把其中一些文件放到了备份里。
  “幸好我是DUAL BIOS,虽然藏得不多,还足够让他想起来……”
  我想BIOS保存这些东西的时候一定很疼,当我问他“为什么这么做”时,BIOS轻描淡
  写地说:“呵呵,我们是朋友嘛。”
  嗯,朋友,永远的朋友……