博文

目前显示的是 五月, 2011的博文

2011-5-30

先说魔兽。最近我只要一在UU的QQ群里露面,就会被围观。原因是我的名字最近在他的小说中出现的频率很高。虽然他写的很不靠谱,操纵原子弹发射装置之类的,但是大家还是很津津乐道。搞的我很想把我在游戏里面的名字也换成小说的中的那个,可是目前这个名字也挺好听的,“在变老前远去”。一个悲剧的诗人,一段伤感的诗,一场话剧,一些朋友,一些回忆。今天下了3次本,彻底把双倍经验用完了。顺便把天赋洗了,还是恶魔,但是重新点一次。以前我打的很简单,见小怪就扔种子,杀BOSS就是腐蚀、厄运、献祭,然后狂丢暗影箭。现在稍微专业点,见了BOSS知道变身,而且更喜欢元素诅咒。看见熔火的buff就放烧尽,偶尔再放个灵魂之火。在闪电大厅杀了很多装备,可是都是78、79级的装备。我现在才77啊。今天把adobe cs 5.5装了,master collection,下载了10多个小时,装了40多分钟。其实我最想要的是adobe acrobat X pro,因为想拿它给我的kindle做6寸PDF。可惜,打不开。其它貌似都好用,还多了很多之前我没用过的新软件,比如adobe Contribute,貌似可以代替windows live writer来作为wordpress client。我其实想,如果它能用来编辑wiki就好了,这样才名副其实嘛。呼,明天一定要搞清楚 Berkeley DB JE的range lock是怎么回事。

读写锁

Locker: 谁拥有锁。例如Transaction、Thread。Lock: 锁。一个有状态的对象。Locked Object: 需要多线程并发访问,所以被用锁保护的对象,如table、data record。相容性RWROXWXX读写锁的实现多种多样,而posix标准关于细节上却写的很含糊。所以每拿到一个读写锁的实现的时候,我要先考虑如下疑问:Release preference: 如果一个writer释放它所拥有的写锁,此时既有reader也有writer在等锁,那么谁将获得锁? reader? writer? 还是无论类型,谁先请求谁就先得到?读写优先级:如果一个locker已经拥有读锁,一个locker来请求写锁,那么必然会被阻塞。此后,另一个locker来请求读锁,那么它能立即获得读锁吗?降级:如果一个locker已经获得写锁,它想换成读锁。那么释放写锁和获取读锁这两个操作是原子的吗?(很少用,所以下面不考虑它)升级:如果一个locker已经获得读锁,它想升级成写锁。此时已经有其它的locker也在请求锁,这个locker是否具有优先于其它locker的权利立马获得写锁?读锁升级操作很容易造成死锁,假设有两个locker A、B都已获得读锁,然后A申请升级,此时还不能得到锁,因为B的锁还没释放。之后B也去申请升级,那么就死锁了。对于事物处理系统,一般来说,读数据的时候,自动获取读锁,写数据的时候自动获取写锁,如果要达到可串行化的隔离度,那么所有的锁都保持到存储过程结束才释放。如果不明白读写锁的升级操作的可怕之处,那么死锁将会四处潜伏。下面以一段基于BerkeleyDB的代码为例:voidmyfunc(DB_TXN* txn){ DBT key,value; key=…..; //读出来。此时拿的是读锁。 db->get(db, txn,&key,&value,0); //修改 *((int*)value.data)=0; //写回去。此时需要申请写锁。 db->put(db, txn,&key,&value,0); } 如果有两个线程试图同时执行上面这个函数,则有可能会发生死锁。为此,Berkeley DB为get方法提供了一个flags字段,D…

2011-5-28

今天是个有意思的周末。今天没有找到人和我打三国杀,于是吃完午饭后抱着笔记本去万圣的醒客咖啡坐了一下午。第一次去醒客,略微失望。首先,大部分座位都光线过暗,很不适合看书。其次,它家是那种传统的中国古典风格的家具,木椅或藤椅。老实说,我对这些看的很厌了,无爱。于是饮料,品种很多,这些才应该是它的重点。只是偏偏我对喝的东西特别特别挑剔,它家那22块钱一杯的龙井茶啊,还不如我在家喝的那种很普通的绿茶呢。我给我以前公司很多同事都带过,那股非常自然的清香味,绝对是一流的!呃……不过,我基本上1-2个月才会喝一次茶。于是服务员给我换了免费的柠檬水,最后,还是应我的要求换成了白开水。我大多数时候只喝白开水。可能因为今天是周六,醒客十分吵。人很多,以至于比我后来的人,一圈一圈的找,找不到合适的桌子。我背后是一个外国女人在玩mac book,我对面也是个mac book,看样子是中国人,在等一个女学生,之后,她们凡是日常话语,都用中文,学术问题,就全是英文。里屋有个大桌子,几个60+的老头子,操着南方口音,在讨论sina微博怎么用,怎么注册。我本想拿kindle看会儿小说,最近在看《我们无处安放的青春》,可惜光线太暗,就放弃了。打开笔记本电脑,认真写点东西。一直有个想法,像阿北那样,捧着笔记本整天泡在咖啡馆,把自己的想法用自己的代码,变成产品。ok,恰好我最近不是很忙,恰好我有东西想做,恰好最近天气不是很热,恰好我最近是一个人。只是不恰好的是,我家周围没有醒客这样的地方。我蛮喜欢这里的,一边写代码,一边听一个中年人讲文学作品的叙事方式,什么是结构化叙事什么是非结构化叙事,不是讲课,是讲他最近看书和创作中的一些心得。而我今天的收获是,终于把rwlock的死锁的问题想明白了。晚上约了几个朋友一起吃饭,相谈甚欢。技术人员很容易能找到共同话题。只是我觉得baidu技术沙龙那样的活动太高端了,我听完总是在云里雾里,只能知道他们在做什么方向但是从不知具体细节以及为何,所以在我成为XX公司的CTO之前我绝对不会再去的。我现在特想搞个transactional database研讨班,人数3-8人左右,地点定在北京的某个咖啡馆,稍微大点的桌子,没有麦克风没有投影仪甚至可以没有PPT,share你的想法。一个典型问题:它是如何实现的以及为什么这么实现?它=BDB、redis、wdb、xdb、mysql…

2011-5-25

我突然觉得,google只能帮助解决一些临时的、简单的技术问题,比如编译的时候报某个错、运行的时候某个错误消息,一搜,就解决了。但是稍微深一点的,就无奈了。离开了学校真是很郁闷,虽然在google 学术搜索中搜出好多我感兴趣的paper,但是下不了、下不了。所以,为了中国互联网事业的可持续发展,我一定要竭尽全力的勾搭各个高校的小学妹们,上门指导如何查询学术期刊,诱骗她们帮我下paper。嗯,就这么定了!我又在想死锁的问题。secondary index引发deadlock是普遍现象,很多数据库实现中都遇到了此问题。例如mysql也有这样的问题。假设有一张表名为user,主键是userid,有一列是status。status上有索引,也就是说,它是这个表的secondary index、非聚簇索引。userid(PK)status…10…1002…………100000001…99944545453…线程A执行查询"UPDATE user SET status=4 where status=1 ORDER BY userid LIMIT 1“,线程B执行查询"UPDATE user SET status=2 where userid=2;” 。Storage Engine是InnoDB,事务提交方式是autocommit。原因很简单,就是和Berkeley DB一样的,到底是先访问Primary Key,还是先访问secondary index,顺序不同而导致死锁。MySQL的slave一直是以单线程的方式执行SQL,这个目前看来已经是一个越来越大的瓶颈。首先是,主库是以多线程并行执行的,而从库却是单线程的,假设机器配置都一样,那么显然主库不能太busy,否则就会导致主从不同步。其次,因为binlog是顺序写入的,所以要求在主库上执行的所有事务必须存在可串行化的调度,而且是哪个事务先执行,就该哪个先完成。这就导致了update … set …. where xxxx的时候,应该把where中的条件所扫描过的所有行都用排它锁锁住,而不仅仅是最终匹配的那些行。以上面的表为例,假设status上没有索引,那么where status=3则会导致全表扫描并且锁全表,从而大大降低了并发。要解决这个问题,必须把事务的隔离度降低到read-committed,并且…

2011-5-24

好几次把 Berkeley DB Java Edition 的代码下载下来想看,结果都没能开始做。然后就忘了,做别的事情去了。但愿我这次可以整明白。Berkeley DB Java Edition在查询的时候是对记录以读写锁的方式加行锁,这种读写锁是写优先的,我猜就是JAVA的fair Read Write Lock。我比较不爽的是它的死锁检测,它无法直接检测死锁,它是通过限制每个锁持有的最长时间来打断死锁。通过设置je.txn.deadlockStackTrace可以打出当时的堆栈。je.txn.dumpLocks还会把当时的锁都打出来。我不明白为什么不直接用JRE本身的死锁检测功能呢?对于互斥锁,想描述清楚什么是死锁是一件很容易的事情,从而也很容易指明如何预防死锁。但是读写锁就比较麻烦,尤其是读写锁的功能实现更是五花八门。我在网上找了一半天,没有找到一篇文章系统的讲解读写锁的死锁。睡了。明天再说。

读写锁优先级的问题解决了

这个问题就是:对于一个共享的数据结构,读的频率远远大于写,所以用了读写锁.但是发现写线程总是抢不到锁.按The Open Group 的Single UNIX Specification所说,"The pthread_rwlock_rdlock() function applies a read lock to the read-write lock referenced by rwlock. The calling thread acquires the read lock if a writer does not hold the lock and there are no writers blocked on the lock. It is unspecified whether the calling thread acquires the lock when a writer does not hold the lock and there are writers waiting for the lock" 意思就是说,没有writer在等写锁的时候,reader是可以拿到读锁的。但是没有规定,如果有writer在等待写锁,该如何?还好,Linux有pthread_rwlockattr_setkind_np这个函数,可惜我用man查不到这个函数。我是在pthread.h头文件中发现的。enum { PTHREAD_RWLOCK_PREFER_READER_NP, PTHREAD_RWLOCK_PREFER_WRITER_NP, PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP, PTHREAD_RWLOCK_DEFAULT_NP = PTHREAD_RWLOCK_PREFER_READER_NP }; /* Set reader/write preference. */externintpthread_rwlockattr_setkind_np(pthread_rwlockattr_t *__attr,int __pref) __THROW __nonnull((1)); 看到这些,我以为这事不就这么简单的就解决了吗?默认是reader优先,改成writer优先不就行了吗?…

2011-5-21

今天玩了一整天游戏.早上起来先是玩魔兽世界玩到11点,然后去吃饭,然后奔往北大东门和同学玩三国杀,一直杀到11点,没有车了,只好打车回来.之所以最近又开始玩魔兽世界,是因为很偶然的,一个很痴迷游戏的大学同学(lwb)问我们最近在玩什么游戏,然后我就说魔兽世界,一问,恰好他也是PVE的联盟,于是就忽悠他转服过来一起玩,以两张点卡诱惑之。哈哈!成功了。于是这周我就忙着升级,从73升到75.5。我对任务不熟,所以下副本比做任务快多了。我比较喜欢下种子,杀伤力很大。尤其是一片片伤害数字冒起来的时候,非常happy!要不洗个专门下种子的天赋?好久没玩痛苦术士了。不得不说,随机本是个很悲催的设计。因为有了他,公会的作用小了很多。至少在我满级之前,加入大工会是没有必要的。各打各的,需要下副本的时候排随机本,BOSS打完立马就散,真是很冷漠啊。明天又是很忙碌的一天.

Linux下pthread的读写锁的优先级问题

有这么一个情况:有一个C实现的HashMap,需要在多个线程之间共享。对它的读操作远远大于写操作。所以采用了pthread的读写锁来保障并发读写时的一致性。现在测试发现的问题是:因为读操作太多,导致写操作一直拿不到锁。按理说不应该啊,假如有三个线程,线程1 先申请读锁并成功拿到,然后线程2申请写锁那么必然会陷入等待,之后线程3去申请读锁,那么应该是陷入等待才对,因为pthread_rwlock_rdlock的man pages上说"The calling thread acquires the read lock if a writer does not hold the lock and there are no writers blocked on the lock",可是实际我的测试结果是线程3拿到读锁了。为了模拟这个场景,我着实想了好一阵子。因为我怎么确定线程2已经陷入等待状态了呢?后来我的测试是这么做的线程1 线程2 线程3
rdlock
barrier barrier barrier
wrlock while(true) {rdlock;unlock;}代码如下:#include <iostream>#include <pthread.h>#include <stdio.h>#include <assert.h>static pthread_barrier_t barr; static pthread_barrier_t barr2; static pthread_rwlock_t rwlock; void * thr1_entry(void *arg){ int threadCount=*(int*)arg; std::cout<<"this is thread "<<threadCount<<std::endl; if(pthread_rwlock_rdlock(&rwlock)!=0) return NULL; std::cout<<"thread1 got the read lock "<<std::endl…

分析sina微博上的一张图

图片
这是一篇牢骚文.只有清然明白我咋的跟大姨妈来了似的全身不爽.输入数据:100,000,000条。key是6-10字节的变长字符串,a-zA-Z0-9。value是3字节定长。那么对于输入数据,最节约的存储方法就是key1,'\0',value1,key2,'\0',value2...原始数据=((6+10)/2+3+1)*100000000 = 1144M每个页面能存的key的个数=(pageSize-pageHeaderSize)/(keysize+sizeof(page id))。pageHeaderSize=12+6+44+4+1+1=68而keysize=(6+10)/2+2+4=14。加2是因为offset array,加4是因为需要存keysize所以每页最多可以存储(4096-68)/14=287个key。在leaf pages上,itemsize=sizeof(u_int32_t) + sizeof(u_int32_t) + sizeof(u_char) +(6+10)/2+3=20。所以每页最多可以存储(4096-68)/20=201个item。所以leaf page大约有100000000/201 * 1.5=746268 pages  约等于2915M,假设索引有1%的overhead,那么总计约等于2944M。库文件占比 2900/1144 约等于 253%写这么多是为了说明我估算出来的东西和他的实验结果大致吻合。嗯哼? 下面不说细节只列公式输入集合的取值的可能性的总数=62^10-62^5=839299364952207392 itemSize=(6+10)/2+1+3-prefixLen
itemPerPage=(pagesize-10-prefixLen-1)/itemSize
totalPages = 100000000/itemPerPage
prefixLen >= ln(totalPages)/ln(62)
total size= total pages * pagesize=100000000*(12-prefixLen)*pagesize/(pagesize-prefixLen-11)
当pagesize=4096 时,假设prefixLen 都等于3(这是最保守的估计),可…

2011-5-12

5.12,一个举国沉默的日子。很快就被淡忘,如SARS一般。只是那些经历过灾害的人不会忘记,大灾在心里留下的创伤,都是一辈子的。我老家是陕西汉中。很多人不知道,那次地震的震中,在缓缓迁移到汉中之后,地震就消失了。先是从媒体上消失,因为奥运会开幕了。再过了许久,地震真的消失了。今天看到一条消息,我老家那边正在启动一项中国最大规模的移民工程,涉及当地1/4的人口。回想当年为了修三峡,重庆库区搬迁了110多万人,为此,诞生了大量的争论,以及文艺作品。而我老家这边,陕南一共3个市,准备搬迁240多万人。按人均2万来算,那么就需要500个亿!!!实际给出的规划是,光建设投资大概就需要1000多个亿,这还不含安置、补助费用。陕西那么穷,这笔钱从哪来?目前给出的口风是,省里每年给2亿,市县自己再拨2亿。计划10年完成,那么就是每年需要100亿的投资。相比而下,政府拨款简直就是九牛一毛。怎么办呢?找企业要、找银行贷。但是这么大的资金缺口,国家总理看了都发愁吧?除了钱的问题,还有耕地的问题。搬走去哪?这么大多数都是起伏不平的山地,可耕种的土地很少。给搬下来的人即便是每人半亩地,也没那么多资源。再那么就是多给点钱、土地没了、变成居民,按我从我爸那了解到的情况,每户需要10多万的安置费。那么这将是一场规模浩大的现代圈地运动。而实际的情况是,安置费都用来买了商品房,然后四壁空空,没有收入来源。如果他们有能力在城市里打工赚钱,早就出来打工了,不会在山里窝到现在。再加上不适应新环境,种种问题。导致很多人最后又偷偷的搬回去。为什么要搞这么大的一个工程? 官方的理由有两个,一是地质灾害多发,二是山区太穷。对于前者,我专门看了一下中国地质环境监测院的统计数据,陕南虽然地质灾害多发,但是和全国其它地方相比,根本不算是灾害密集区。http://www.cigem.gov.cn/BigClass.asp?TypeId=22&BigClassid=81 至于第二个理由,更是不靠谱。其实不必搬迁,只要政府钱够多,每人给个好几万,穷人就都不穷了。显然不能拿着几千亿用这种方式解决贫困问题。最后说点技术。我发现zookeeper真是个好东西,至少用它来代替JNDI是个很不错的选择。naming service是分布式系统的基础部件,所以我觉得几乎所有的项目都应该考虑下它。比如,栅栏,这样的同步方式,不是很…