博文

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

JAVA是我用过的语言中对多线程支持最好的

JAVA 6是06年底发布的。2006年啊!!那时候我还没大学毕业呢,小毛孩一个!JAVA是个跨平台的东西,它能屏蔽底层硬件差异而提供一个统一的内存模型,这点十分了不起!换句话说,想用JAVA写出高性能的程序,并不必怎么了解CPU架构,而且,06年的时候,Intel还没有Nehalem呢!!!我最近一直在看那本《The Art of Multiprocessor Programming》,今天终于看到SkipList了。然后我在想,如果用SkipList实现一个Map,然后用它来管理cache,该多好啊?结果,结果,发现JAVA 6在发布的时候已经实现了这个了 ,ConcurrentSkipListMap,那时5年前了啊!关键是,人家的标准库,真的是该有的都有了,而不是像pthreads那样,除了mutex/condition variable之外一无所有。不过JDK中满足non-blocking性质的数据结构没几个,我知道就ConcurrentLinkedQueue、ConcurrentHashMap、ConcurrentSkipListMap、ConcurrentSkipListSet这么四个。目前我所看过的所有paper也都集中在链表、hash map以及skip list上。我本想用ConcurrentSkipListMap来管理cache,但是ConcurrentSkipListMap有个缺点,它的size方法是O(n)的。这个给做lru带来了麻烦。于是,我不能每次insert的时候都检查一下是否达到capacity上限了。如果你自认为精通“JAVA”或“数据结构”或“多线程编程”中的任何一个,那么去看看ConcurrentSkipListMap的代码吧,一定会被惊倒的!我觉得我有生之年写不出这么优秀的东西…… 嗯,但是我读懂了一个关键点:为数据结构设计并发算法的时候,核心在于找到那个不变的东西!无论数据怎么插怎么删,总有一个性质,始终保持不变!

2011-06-23

去年就一直想搞一套家用存储系统了,琢磨了很久。到底是自己买个小机箱然后用freebsd/zfs这样来搭软raid呢,还是买一个商用的家用NAS,还是单纯的买硬盘盒。我想把我电子书、照片、电影啊什么的通通搬进去,然后用它对现在的笔记本电脑上的整个硬盘做全盘备份。考虑到具体实际情况,我家也没有几台电脑,未来3年内也不会有多台电脑,只是我自己的电脑在用,所以用NAS显得有些浪费。另外,NAS一般都是走千兆以太网,而硬盘盒可以走eSATA/USB3.0,后者的带宽更大一些。很难说这个是否有明显差别。千M以太网理论最大传输带宽是125MB/s,除去overhead之后大概是100MB/s左右吧?而现在的硬盘在不做RAID的情况下,单盘顺序读的速度也可达到130MB/s左右。但是硬盘有多少时间是工作在这么高速下呢?Rarely。在淘宝看了一圈,计划这么买:orico 3548rus3 四盘位硬盘盒 RMB:2180
http://item.tmall.com/item.htm?id=9117739002
orico ENU3536-U3E原装usb3.0/eSATA扩展卡 RMB:238.00
http://item.tmall.com/item.htm?id=99924132724块2T的硬盘做raid10,价格大约2400-4000左右。
如果是4块1T的硬盘,大概1600。
倾向于买2T的,坏了再换嘛。总计:4800-6400左右。因为这也是一笔大花费啊,先发上来征求下意见。eSATA、USB3.0,我也不知道哪个更好一点。单纯的比较理论最大带宽没有意义,芯片的成熟度?实际传输延迟?加密功能是谁来支持呢?硬盘还是硬盘盒?反正我采购的这些都不支持。我计划是TrueCrypt+PKCS#11卡。有谁这么尝试过吗?给下经验。

2011-6-18

昨天晚上2点才睡,导致今天早上10点才起。打开电脑捣鼓了一会儿,11点就去吃饭了。回来之后在京东上买几本书,1点的时候,就被人叫出去。结果9点才回到家。这不,才10点,就又困了。还好今天在路上看了一小会儿书,不算是太荒废。周末对我来讲是很珍贵的,因为好不容易有一整天, 可以让我做我喜欢做的事情。我在想优秀的程序员为什么总是睡的很晚?是因为怕被打扰吗?那能不能关掉IM、关掉手机、不看邮件,人为的制造一个“安静的夜晚”呢?或是背其道而行,早上5点起来看书、写代码,也是不错的尝试哦?择某日回完美一趟,把我准备写xdb v2的想法给他们说说。我担心我想的不够严密。That’s my Weekend Project.(最近废话很多,是为了坚持每日一更新。)

2011-06-17

今天继续在看BSD db1.8的代码。mpool_get(3),文档中说"The flags argument is not cur- rently used.“ 实际上这个参数是有效的,只有一个标志位:MPOOL_IGNOREPIN。而这个标志位只给内部代码用。mpool的hash table是静态hash,这个我觉得十分应当改进。HASHSIZE=128,也就是说槽就128个,多了就溢出到链表上。128*4=512K,在现代OS上,这么小的cache…… 或者,既然max cache在mpool_open的时候已经给出来了,那么hash table所存储的对象的最大个数也可知道了啊,用它来设置bucket数组的大小都比用128好。谁去把代码稍微修修吧,最好直接做成动态hash,再开放一个动态调整cache size的接口。想做单元测试。gtest、cppunit、qt test,哪个好?我现在比较倾向于gtest,像google的其它东西一样,简洁小巧且功能强大。我发现网上讲jni的文章很少,好不容易找到本书是12年前的。jni和C++配合起来简直就是噩梦。比如,如何把C++的pointer存在一个java的object中?网上给的方法基本都是强转成long。貌似大家都默认,sizeof(long)==sizeof(void*)。的确,大部分编译器都是如此,但是在指针和整数之间搞这种转换,真是很讨厌的代码。再者,二者的异常机制要粘合起来,更是恶心。每个java native method的实现需要用try…catch…包装起来,把所有C++的异常转成JAVA的。而C++中每次调完一个JAVA的函数,都得赶紧check一把看刚才有没有exception。这些,这些转来转去的代码,很容易就把原本的代码的逻辑给淹没了。一眼望去全是exception处理。睡觉。

2011-06-16

太困了。随便写点然后就睡。今天在看FreeBSD的db 1.8x的代码。所有的文件读写都由mpool完成。每个database(也就是mysql中的table)对应一个mpool。这个mpool的容量上限是在opendb的时候指定的,根据字节数换算成pages。只有两种情况会引发写文件操作:关闭database的时候,需要把所有脏页刷到硬盘上。get a page from the cache的时候,发现cache满了,于是就需要遍历lru列表,找出可被丢弃的页丢掉一个。这个页面可以是脏的,那么此时就需要写回硬盘。我在想怎么把日志系统加进去。我计划的更改:加入一个定期刷脏页的功能。cache满了之后,应优先丢干净的页面。或者做成只丢干净的页面。或者做成此时不丢页面,只在flush完毕后丢。有必要对内存的使用量控制那么精确吗?(walk?)write ahead, redo log。先做成单线程的吧。Question: 一个进程打开多个database是否可以?也就是说,dbopen打开一个database之后,不关。再打开另外一个,可以吗?目前我看起来貌似没有什么问题。

multiverse STM 初窥

Multiverse 的0.7版是一个很大的分水岭。它的页面上说0.7已经release了,http://multiverse.codehaus.org/release-0.7.html 但是我所能下载到的依然是snapshot版。Multiverse 0.7暂时不支持Instrumentation,从以前的版本中去除了这个功能。我不清楚是否运行的时候依然需要加上-javaagent参数。另外就是它的文档很糙,文档中到处都是未写完的小节,所以我只能去读它的代码了。所以还好,目前看来,只要不涉及JVM自身,其它代码我勉强还是可以读懂。我目前只下了一个jar,multiverse-gamma-0.7-RC-2-SNAPSHOT.jar。貌似只要它,我的代码就可以编译了。它的Closure我很喜欢。以前我为了把一个int从一个anonymous inner class中传出来,还不得不定义一个Interger[1]这样的数组。对于side effect这事,其实也好办,做成一个TransactionListener,如果 TransactionEvent是PostCommit,那么怎样怎样怎样。例如所有的待发送的数据包都可以放在ThreadLocal中,等听到PostCommit事件后,唰的一下全扔出去。可惜在 Multiverse 中我没有看到persistence相关的代码。虽然它的作者早在blog中提到想做这样的事情。睡觉!就算它再难懂,也没有女人的心难懂。我相信我能搞定!

MVCC and Snapshot Isolation

MVCC: Multi-version concurrency control。事务处理系统中,为了使得多个事务能够并发执行并得到正确结果,需要采用一定的并发控制协议。一类最常见的并发控制协议就是Lock-Based Protocol,其中我最熟悉的就是立即更新悲观上锁,其实现方式如下:当需要读/写一个item的时候,获取对应的锁,一直持有到commit或abort。所有的更新操作是立即修改对应数据,修改发生之前会试图把这个item的前像(pre-image)存下来,如果已存在则不用了。如果发生rollback,利用前像恢复到事务开始之前的状态。如果成功commit,那么丢弃所有前像。MVCC则是另一类并发控制协议。其基本思想是:每个事务在提交时,这个时刻该数据库的所有已提交数据构成一个快照,每个快照对应一个版本号。每个事务工作在一个特定的版本上,也就是这个事务开始时数据库的版本,提交时再把它所修改的数据与数据库当前版本进行合并,不成功则retry。前面所说的“并发执行并得到正确结果”是个很模糊的说法,准确来说,并发控制的目的是为了达到特定的隔离度。SQL-92标准定义了4种隔离度:READ UNCOMMITTED、READ COMMITTED、REPEATABLE READ、SERIALIZABLE。最初,大多数数据库都是在这4种隔离度的定义下设计并实现的,但是现在又多了一种,Snapshot Isolation。最早是Oracle先整出来的,MS SQL Server从2005版开始加入这个。 MySQL InnoDB没有明确的把snapshot作为一个隔离度提出来,它声称提供了SQL92标准的全部4种隔离度,但是其实拿着snapshot、mvcc在里面混水摸鱼,搞的四不像。InnoDB的repeatable read isolation其实要比SQL92标准中规定的强,例如一个transaction反复执行select * from tableA;另一个往tableA里面插入数据。那么第二个尽管已经提交了,但是第一个还是看不到,也就是说他的repeatable read是没有幻影的(Phantom),它是用next-key locking去除了phantom。我觉得归根结底,隔离度的分类不是从理论出发的而是从实现出发的。单从理论讲,只要一种就够了啊,我就要S…

2011-06-03

前天买了一本好书,〈The Art of Multiprocessor Programming〉。这名字挺俗的,但是内容却是很好。整本书一分为二,上半部是理论,下半部是实际算法。讲理论的时候不忘记给出实际的能工作的 JAVA 代码,volatile这样的关键字也用的是恰到好处。我看的慢,也就刚看到第二章。这一章在讲啥呢?在帮我回答之前我的leader(LCH)给我们出的一个自测题:自己实现一个互斥锁,不使用kernel的任何系统调用。这不仅要脑袋特别灵活,能巧妙的设计出一中locking protocol,而且要求对processor或者language的memory model非常熟悉。我有个朋友把微博比做车站,公交车站或者地铁站或者火车站,我觉得像极了。人来人往,吵杂,烦躁,疲惫。大量的信息不通过大脑直接点转发。看见一条消息,写下它的评论,中间也就间隔2-3秒的时间。我今天在微博上问:“对于一个key-value数据库来说,Repeatable Read和Serializable这两种隔离度的区别是什么?我一直不明白,key-value数据库怎么会有幻影呢”。后面的评论五花八门。大部分人不会去回忆SQL92标准中4种隔离度到底是什么?然后一些资深人士就开始讲数据库是如何实现事务的,我看的云里雾里的,不敢说他对,也不敢说他不对。直到最后经某人在微博上提醒,“对于支持range query的key-value store”可能存在幻读的问题。然后我去比较了一下Berkeley DB C版本和JAVA版的接口之后,发现JAVA版提供了根据key的range query的功能,我才豁然明白了。拿JAVA来说,假如当初是你,你来设计这门语言,那么为什么选用这样的memory model,就是一个足够难以回答的问题。当设计一个底层平台的时候,这些形而上的问题是最最难解决的问题。比如Berkeley DB C版本的有3种不同的事务隔离度,而JAVA版本则有4种?SQL92标准的全部4种? 最难的是发明一种新的编程模型,还能被广泛接受。这方面我十分的佩服LCH。拿JAVA写大型数据库应用的时候有一个弊病,内存太大导致GC很慢。但是貌似这并不是没办法解决的问题。比如,最近看到一个database,采用软引用来管理cache,理由是gc的时候更容易。是吗?我怎么觉得软引用才是恶梦…