小菜一碟

    上完课考完试已经两周多了，下班后没有课上没有作业写的日子多少有些不习惯，懒得学新游戏，打打本科时候老RPG。界面还是一样，却找不到当时的感觉；至于看小说，动辄三五十万字，是想都不敢想的奢望。反倒是喊些“很傻的宅男”（by阿兔）在家下棋的感觉不错。。。

    查了下分数，T大的老师还是很厚道的，付出劳动花了心思的课也能给上90，一般上上课的80多，纯粹混过去的70多，到不完全是电风扇算法。说起算法，为了毕业论文，现在开始假装学术开始看算法，有点感觉像小学五年级开始学围棋，岁数大了，脑子常转不过来。anyway,要动脑子的事情，越早开始越好。

    对了下学分，好像该上的课都上了，还差篇论文就OK了，1年多的bt生活算是告一段落。本来说在职读书2年没有周末，现实当然没这么惨，还是有周末的，时间也不到两年，但确实有些辛苦。promise的事情，尤其是说大话吹大牛挖大坑的事，今后还是要慎重。。。

    挖坑，很重要，眼前没啥再挖大坑的计划。8月份的坑已经很大了，9月、10月各挖了一个小的，其实能填一个就谢天谢地了。再小的目标，原地踏步一辈子也到不了成功的彼案；再大的目标，愚公移山总能看到希望的曙光。千里之行，始于足下，跑步去先！

      时隔两年，再次在家上网。家中首博以纪念。

      两年前刚刚来西王庄的时候，家里是有铁通的宽带的。那时候不怎么用，铁通的网络也很一般，再加上经常能搜索到楼上楼下的免费wifi，就让房东把宽带给停了。

      去年觉得家里有个网络还是不错的，就跑到网通营业厅。结果网通说西王庄是老小区，线路已满，装不了。于是搁置。

      前天突发奇想，决定装网络。跑到铁通，铁通也说线路满了，郁闷；跑到网通，居然说有线路了，交钱登记，OK。

      昨天网通的工程师来装宽带时说，碰巧遇到前一家停了宽带，刚刚好把小区最后一个端口用上了。

         

总结一下：

    “懒是不需要理由的。”--俺写在家中断网两年后

    “我们伟大的跳进了西王庄最后一个坑”--KY

声明：

1. 本文为伪技术贴

2. 本文对NBA选秀乐透流程(NBA Draft Lottery)进行了分析，感兴趣请参阅华丽的分界线以上；

3. 本文将流媒体服务器集群进行了生搬硬套的类比，有兴趣请参阅华丽分界线以下，谢谢您的耐心；

4. 本文是某课程论文的副产品，欢迎复制分发修改，开源许可证GPLV3版权公约。

 

故事开始：

在一个月前的纽约，本赛季联盟倒数第9的芝加哥公牛(33胜49负)幸运的抽到了状元签；而2006年总冠军如今联盟倒数第一的迈阿密热火（15胜67负）拿到了榜眼签。一些很自然的问题，这个状元签是按照什么样的规则产生的？为什么战绩更差的热队的签位要比公牛低？

并不是所有简单的问题都很容易回答，就像这个问题一样。那么就让我们找个草堆坐下，先抽口烟，看看夜晚天空上的银河，然后想一想要从哪里开始讲起。嗯，也许这样开始比较好……

很久很久以前，有一群人，他们很喜欢打篮球，就成立了一个联盟，叫NBA,那年是1946。第二年开始，联盟要有补充新鲜血液了，那时NBA刚刚起步时，联盟处于生存阶段，球队需要获得当地球迷的大量支持。因此联盟推出了所谓“本地选秀（Territorial Picks）”的策略，一个球队允许放弃第一轮选秀权而直接去挑选一名本地新秀。本地选秀的优先级比第一轮选秀的优先级要高，类似与现在的所谓高考填报”零”志愿。张伯伦（Chamberlain）就是1959年的本地新秀。

到了1966年，在NBA成立20年时。联盟决定让两个分区的副班长采用“投掷硬币(coin flip)”的方法来决定状元签。在状元签决定后，剩下球队按战绩排名逆序选择。有一些有趣的故事，比如1979年的时候，26胜56负的新奥尔良爵士队（现在的犹他爵士）在投掷硬币的竞争中获胜得到状元签；对了，爵士队早先在一场球员交易过程中将第一轮新秀权已经交易给了湖人队；所以湖人最终拿到了状元签，选中了魔术师约翰逊(Magic Johnson)。

到了1984年，火箭队为了获得奥拉朱旺(Olajuwon)非常努力的去争取的分区倒数第一。于是，联盟决定改革状元签制度为了让较弱球队不会为了状元签消极比赛的念头。在1985年，选秀第一次采用乒乓球（也就是乐透，lottery）。所有7支没有打进季后赛的球队都有平等的机会获得包括状元签在内的前七名新秀权。

1985年的改革显然对成绩很差的球队过于不利。到了1987年，联盟将乐透的产生的新秀权由7名减少到3名。从第四名开始按战绩排列，从而保证战绩最差的球队运气最背也能获得第四名新秀（原先最坏结果是第七）。在1987年，战绩最差的快船队在新规则保护下拿到了第四名新秀。1988年，成绩最差的三支球队里只有一支在乐透中被抽中。

到了1990年，联盟为了进一步保证战绩较弱球队有优先获得状元签的机率，开始加入乐透的权重（Weighted Lottery System）。没有季后赛资格的11支球队，最后一名11签，倒数第二名10签。。。第一名1签，共66签中抽取前三名。魔术队在92年(10/66)93年(1/66)连续撞大运抽中状元签，奥尼尔+韦伯。

到了1994年，为了改变魔术带来的不良影响。联盟再次更改规则。原先最后一名在乐透中的机率从16.7%提高到25%，第一名的1.5%降到了0.5%。随着猛龙、灰熊、山猫的加入，这些机率发生了变化，有了今天的规则。

 

在如今的规则下，14只标有号码(1到14)的乒乓球被放入一只桶里。抽签时，会从14只球中拿出4只。不考虑排列顺序，4个号码总共由1001种(就是C（14，4）)组合。抽签前，组织者会把1000种组合(排除了11,12,13,14的组合)，根据常规赛战绩，分给参加抽签的球队。之后将会抽出4只乒乓球，形成一个组合。拥有这个组合的球队就有头号选秀权。之后，球被放回桶中，重复整个过程来决定二号选秀权和三号选秀权。

 

14支球队的排名与乐透组合数如下表所示：

排名	乐透组合	中奖机率
1	250	25%
2	199	19.90%
3	156	15.60%
4	119	11.90%
5	88	8.80%
6	63	6.30%
7	43	4.30%
8	28	2.80%
9	17	1.70%
10	11	1.10%
11	8	0.80%
12	7	0.70%
13	6	0.60%
14	5	0.50%

 

因此最终的各个队抽中各个顺位的概率如下。回到开篇，公牛队以1.7%的概率抽中乐透，实在是可喜可贺，应当BG的。热火本来就有75%的概率抽不中状元秀，第二名也算不错的成绩了，哈哈。再仔细看下表，第六名球队有千分之一的概率抽到9号签，也就是说第七名到第十四名包揽乐透前三甲的概率是千分之一；第七名球队抽中10号签的概率小到忽略不计，也就是说第八名到第十四名包揽乐透前三名的概率可以小到忽略不计啦～～概率，果然是牛X的东西！

 

 

参考文献：

http://www.nba.com/news/lottery02_evolution.html

http://www.nba.com/features/inside_lottery_050524.html

http://en.wikipedia.org/wiki/Territorial_pick

http://en.wikipedia.org/wiki/NBA_Draft_Lottery#History

http://hoopedia.nba.com

http://baike.baidu.com/view/405413.htm

 

========☆华丽的分界线★=========

如果要分析一下NBA在选秀权分配上使用的算法，并不复杂。在前三名乐透的阶段，首先为14支球队分配筹码，然后使用轮赌旋转法，即被选中的概率与它们的筹码数成正比，筹码数越多，被选中的概率也越大。但并不保证概率最高的球队一定能够抽中乐透。在前三名乐透之后，使用的则是非典型的加权轮转法，看似每个球队都只有一个第一轮选秀权，但是第四名新秀权显然要优于第十四名选秀权，体现了权重的价值。

揣测下NBA新秀权用乐透的思想：

1.       战绩差的球队优先获得高顺位选秀权;

2.       战绩差的球队不能保证获得高顺为选秀权;

3.       战绩差的球队在RP差的时候，最坏结果不至于太糟;

4.       允许战绩相对好的球队以低概率博大彩，增加意外效果

è让战绩差的球队又更高概率获得高的顺位

è从而缩小球队之间的实力差距

è实力接近的球队之间的比赛才好看

 

看这张图。我有一个联赛，30支球队，1个管理结构。为了了解球队状况，通过常规赛、季后赛对他们进行排名；另一方面，对于新秀可以派球探进行考察(考查准不准另说)。在每年季后赛结束后，NBA官方会收到非常多份加入申请。NBA管理结构的职责的职责就是要结合各个球队的排名，将有潜质的新秀分配到各个球队，力争各个球队之间实力更加均衡。

 

绕了很久的弯，回到标题，开始谈服务器集群。我们来看下面这张图。假定我有一个视频网站，30台服务器做视频服务，1台服务器用做负载均衡服务器。为了了解服务器的状况，我们可以通过定时对服务器CPU、内存、IO、连接数、硬盘转速等进行考量；另一方面，对于用户请求，我们可以挖掘用户过去的请求记录，预测其请求时间和强度。（预测准不准另说）在一个很短的时间间隔里，负载均衡服务器会接收到非常多的请求。负载均衡服务器的职责要充分考虑各个视频服务器的状况，将这些请求合理的分配到各个视频服务器上保证负载均衡。

 

 

       NBA有新秀、有球员成长、有交易，有工资帽，有球员退役。服务器集群里有新的请求、有请求变革、有任务迁移，有负载上限，有请求终止。很多概念非常像，举下面一个交易和任务迁移的例子。

       在NBA球队运营过程中，新秀不断成长，某球队（公牛）的某些新秀展现出的潜质更加适合另外一支球队（马刺）；那么马刺队可以考虑尝试交易这名新秀，在交易成本可以接受的前提下，交易的代价可能是另一名新秀，也许是下一年的选秀权。

       在服务器集群调度过程中，某些服务器B处理某种任务(比如看欧洲杯)有优势；服务器A上的对看欧洲杯球赛的请求可以考虑重新调度到B服务器，在迁徙代价可以接受的前提下，迁移的补偿，也许是从B也调度某种任务给A，或许是下一轮分配任务时，B的任务给A来做。

 

       我们设计负载均衡算法时，在处理新请求的过程中，也可以用这样的乐透思想。

1.       负载低的服务器优先获得高强度任务;

2.       负载低的服务器不能保证获得高强度任务;

3.       负载低的服务器在RP差的情况下。结果不至于太糟;

4.       允许负载相对较高的服务器拿到适量高负荷任务

è让低负荷服务器由高概率获得更多、更强的任务

è从而缩小服务器之间负荷差异

è服务器负载平衡有利于集群维护

 

       在两个模型有相似之处，角色有近似，连过程也很像的情况下。很自然的想到，可以试着将