很多小技术team,面对快速成长的业务,感到力不从心。他们觉得,迫切需要牛人,可是牛人总是,不是要价高,就是只想呆大公司,还不想在小企业冒风险,要了高薪还要期权…其实,牛人不需要多,牛人不总是能呆得住,牛人不解决一切问题。我想总结点什么,不过没啥经验,嗯。随便想点儿。不算指导,算是留此存照,将来有机会自己拉队队干革命,希望能解决好这个问题。
嗯 团队成长是痛苦Di,费心Di,让人头疼地。小团队,要稳步前进。
嗯,基本上这些题都答得好 那就… 直接上题.
昨天忽然发现别的孕妈妈都老早去医院检查、建档了,我们还没有准备,再一看,呀,好多医院根本挂不上号,于是,赶紧请假,今天早上一大早就去医院排队了。 光是选在哪个医院建档,就很费神。开始一直想在中日,后来说中日基本无法挂上号,因为一天只有5个号,而且不知道有多少人盯着中日呢,根据排不上号,又选煤炭总医院,结果在网上看评价不好。于是最后选了306医院。 早上那可真是早啊,不过,已经有很多人在排队了。每个队都有10多个人了。后来到三楼妇产科时,看到等假区人满为患,这才知道北京生孩子的人还真是不少啊。这还只是一般的医院啊,不知道朝阳妇幼 和朝阳医院 ,又会是怎么一幅情形呢。 今天都没怎么查到,因为B超这周都排不上了,护士小MM给在周五下午加了个塞儿。从来没听说过检查项还要提前好几天预订的。 今天的一些结果: 胎心:150 (嗯 网上好多说胎心在145以上的尤其是150以上的,一般都是女宝宝~) 嗯,周五下午我就不陪着去了,不过周六又得起一个大大的早啊。
在网上看到的: 1分钟内用户上线的数目是60万,如果用户在5分钟内重复上线,就给他发警告,问如何设计?
嗯,让我这个自以为是的不知天高地厚的家伙来看看该怎么设计。 嗯,首先确认的是,出题者应该是想考实际算法的,和应试者解决难题的方法,全方位思考问题的意识。所以”花600百万美刀花一套oracle的顶级牛B数据库然后把五分钟内的用户记录入库,连数据库查询“这样回答可能确实解决问题 不过不是出题想要的。 好吧,哪,准确地说,啥数据结构,啥算法? 让我们先想象数据容量和运算量。嗯,五分钟内可能有300万用户名要存储。这个嘛,不大,完全在单机范围之内,内存稍大的机呖器,就能全装下这个量级的用户名或id数据。再看时间要求:一分钟内要上线60万用户,每个用户上线时都要查询是否重复了,呀,这是一秒钟1万次查询。如果说是网络服务器的话,比如web这种效率低一点的服务,一万次每秒还是相当复杂的。不过如果是机器内运算1万次,嗯,还是可行的。 接下来,咱们要看是最麻烦的部分,也是要点一:如何应对一秒内完成一万次对该用户是否在五分钟后上线过的查询。这实际是一个要查询一个数据是否在一个列表中存在的问题。嗯,当然我们可以挨个去比对,这个列表比对完了我们就知道这个数据是不是存在了。不过,做为搞软件开发的,大家都知道,如果这个列表能够事先排好序,那是最好不过了。好吧,让我们确定一点:我们最好应该将某一时间的用户名排个序。 接下来我们假定我们把每秒钟内上线的1万个用户放在一个桶里,然后对该秒中的所有用户按名字排序,从小到大或都是从大到小,都行。现在我们时间每推进一秒,我们就噌地新建建一桶,这一秒时间内的新增的一万用户呀,就存这个桶里了。嗯,做为开发者,实际情况是,我们一始就建了300秒这么多桶,申请了大小为300的内存块。然后每块内存里要能有足够容纳一万个用户的内存大小。 嗯,每当时间的车轮进入新的一秒,我们就去这300个中间去找到已经过期的那一“秒“,给它打上当前时间标记,嗯,把它个1万个用户数据清空。每进来一个用户,我们就丢进去,让它们按用户名大小排队。 每一个新用户上线时,我们都需要向这个300个桶发出查询请求。嗯,学过二分法的话,就应该知道,一万个排好序的数据,要查询是否包含某一数据只需要log10000就行了,啊,大概是14次查找。嗯,比你一万个挨个查好了吧,那可是1万次查找啊。 再接下来,我们再思考一下,检查一下:如果是实际场景的话,我们用户们可能不那么听话,每分钟内的60万用户未必刚好平均分配到一秒一万。嗯,而且就跟电灯炮一般能承受的电压都不是220v,而会高出不少,比如250v也能工作,180v也能点亮。比如,明天突然出了个重大新闻,一秒钟内涌进了13000名用户,那我们这么桶的大小就不能承受了。这个,我们做一点点改进,因为二分法最多反正也得比较14次,我们就以2的14次方做为桶大小。如果再还不能承受,那就在用户超出时2的14次方时单独再申请内存。 嗯,这样看上去好多了,不过,排序也是一个比较繁琐的过程,嗯。假设这样一个场景….算了,直接说吧。对于这种从一堆数据中查询是否存在某一个数据的做法,有一个算法叫布隆算法,可以google 一下bloom algorithm或是bloom filter,就专门干这些事。布隆算法做这个查询会有误差,比如,有的用户明明是没有登陆,可是却被提示重复登陆了。这个误差机率我们是可以计算的。 接下来我们可以试际测试一下,看看单机测试的结果。如果实在还不行,那就需要把这300个秒上的数据分布到几台机器上去计算。比如每分钟内的时间分在一台机器上… 有的哥们是这样考虑的: 做一个长度为300的循环链表,每个链接项的数据是一个hashtable,这样来判断。也是删掉过期数据。我觉得这样难度挺大的,因为这样每秒种进1万个用户,对300个链表项中每一个项的1万个数据都要做比较,大致相当于一秒内做了10k*300*10k次比较。我的印象中,就是一亿次for循环,每个循环基本上啥也不干,这个时间,也应该在一秒左右。我偷了下懒, 用c写了个简单的测试: #include “stdlib.h” #include “stdio.h”
int main(int argc,void ** argv){ int i=0; int j=10000*10000*3; for(;i } printf("done"); } 编译后: $time ./a.out done real 0m1.363s user 0m1.268s sys 0m0.008s 如果再100倍,时间就远超出1秒了。还没有做其他事情呢。我用的是10000*10000*3是因为,如果是10000*10000*300,就溢出了。 不过至于究竟分桶排序后效率如何,也还不好说。没有实战。只是我凭经验觉得一秒钟几百亿次比较是不靠谱的。嗯,不知道有没有时间写个程序验证一下。
不知不觉,已经满了二十六岁。 我总是遇到跟我同年同月同日生的兄弟。 大学的室友,某次聊起来,突然发现,原来居然是同一天出生的,而且,居然都是早上五点至七点之间的。哈,八字都是相同的。 雅虎的同事,超超同学,跟我的身份证上出生年月日是相同的~ 现在雅虎资讯的工程师,就只留下他和我了….当年的雅虎新媒体,上百号开发工程师呀~ 今年国庆回家,不知不觉就把二十六岁生日过了。呀,一下子就二十七了,忽然发现离三十岁好近了。嗯 ,再也不是小孩子了。 明年,我就要做父亲了。。。可我还觉得似乎没有准备好。 回家玩了几天,发现家里变化很大。农村里安静多了,也不知道是因为安静,还是因为回家了什么压力都没有,睡得很踏实。晚上11:00睡,早上7:00就起来,还觉得很有精神。 家乡的山,绿绿的,水,镜平如画。于是特意拍了几张照片,放在yupoo上的相册上。看看家乡的山水,我在想,如果能在家里生活该多好啊。 一天下午,看到挂在浴室里的两张鱼网。想起父亲说过,这几年政府大力治理环境,河里有不少鱼了。于是拿了张网,去一个浅水区下着了。不一会儿果然就有些小鱼儿可怜地粘上了。不过半小时后这些小家伙就全跑了,可能是鱼网太大了吧,应该下到深潭里才对。不过有什么关系呢,我无所谓了,只想找找那种感觉罢了。十几岁的时候,最喜欢的事就是拿着一把大锤到河里砸鱼。过程很简单,用大锤狠狠地敲石头,石头下藏着的鱼儿就被震晕了,然后掀开石头,用手在手里一捞,就能凭有没有粘液知道有没有鱼。几秒钟后鱼儿就会翻着肚皮浮上来。唯一不爽的事,这事一般都得两三个人一起,至少得一人抡大锤一人拎鱼篓。那种快乐,无法言说。 假期的其他日子,便是窝沙发里看电视。便又想起来小时候,村里人们都还没有彩电和录像机这些东西,DVD就更不用说了,那会儿还没有。一旦有人结婚,小孩满月这种大喜事,一般就会大摆宴席,夜晚远来的亲戚无处安歇,主人便会请来放电影的或是放录像的,通霄放映。其实很多大人们是没有办法只能去看,小孩子才最喜欢这些,李连杰的少林小子啊什么的,吸引得小孩们不惧磕睡和深夜里的寒气。往往到天亮,小孩们都是大人们抱回去的。那时的人们无法想象后来的40寸电视和100个频道。当然,也无法想象某些省的卫视能放丰胸产品电视连着放一个小时。 嗯,不乱想了,房东打电话让准备一下房租。接下来半年的,一万多呢,加上水电煤气得一万五了吧。呀,我还得再算算信用卡要还多少钱…..