博文

目前显示的是 十一月, 2012的博文

code snippet: 计算HDFS中文件的md5值

org.apache.hadoop.fs.FSDataInputStream os = dfs.open(outputFileName); byte[] buffer = newbyte[1024 * 1024 * 2]; MessageDigest md5 = MessageDigest.getInstance("MD5"); try { while (true) { int bytesRead = os.read(buffer); if (bytesRead <= -1) break; elseif(bytesRead > 0){ md5.update(buffer, 0, bytesRead); } } } finally { os.close(); } byte[] result = md5.digest(); String hexString = DatatypeConverter.printHexBinary(result); Hadoop其实本身给每个文件都存的有checksum,请参见MD5MD5CRC32FileChecksum这个类。但是那个跟md5sum计算出来的md5值并不一样。这是个串行化版本,求更好的实现。

prgmr的硬盘损坏导致客户的VPS数据丢失事件

prgmr.inc是美国加州的一家IaaS服务商,主要是提供基于xen的虚拟机。这个公司本来只有一个人,现在扩张到大概有2-3个。一共有70多台Dom0主机,并承诺99.5%的可用性(实际都在99.9%左右),这些主机主要都由Luke Crawford一人维护,所以我很佩服他的运维能力。但是天有不测风云。这周,有一台Dom0机器(boutros)的硬盘突然坏了。这个机器一共8块硬盘,做的是raid10。结果一次性坏掉了3块(4块?),恰好有两块硬盘是属于同一个Mirror,于是就惨了,RAID整个坏掉处于不可用的状态,只能手工做数据恢复。具体的经过可见这里:http://wiki.prgmr.com/mediawiki/index.php/20121124boutros_post-mortem(困。先睡了,过几天再更新详细的经过)

用Bloom Filter的方式统计网络流量

背景:我现在在一个网站工作,每天都有很多网络爬虫和恶意攻击。我想根据http访问日志统计一下每个IP每天的访问次数,然后大于1万的都认为是机器人。现在寻求一个高效且实时的算法解决这个问题。最简单的做法,就是用一个map来记录所有IP的访问次数。那么这可能会需要几百兆的内存。有一个更好的办法,可以在O(1)的空间复杂度中解决这个问题。算法:我们用一个m 乘 k 的 二维数组来存放所有的计数值。此外,我们还需要m个两两独立的散列函数,每个散列函数将输入(即IP地址)散列到[0,k)范围内的整数。伪代码如下:int count[m][k]; int c=INT_MAX; Object input ; // the ip;for(int i=0;i!=m;++i){ int index=hash(i,input); //用第i个hash函数对input做hash。 c= std::min(c,++count[i][index]); } if(c>10000) printf("catch one robot"); 由代码可以看出,每来一个input的时候,会同时增加m个计数器的值。一个更好的改进是,只增加这m个当中值最小的那个。例如7、5、4 变成 7、5、5。但是7、3、3必须变成7、4、4而不是7、4、3。分析:这是Bloom Filter的一个变种。原始的Bloom Filter算法中,hash对应的是0/1这样的一个bit。而此处把bit改成了一个整数。和Bloom Filter一样,它也存在假阳性的问题,就是,有些IP明明没有访问那么多次,但是我以为它有。降低假阳性率的方式就是提高m和k的数值。同时,和Bloom Filter一样,hash函数的选择也很关键。如果你把hash函数看成是带参数的随机变量,那么它应该尽可能的在值域中均匀、且相互独立。相关问题:问题一:来自《编程之美》这本书,号称是微软面试题。假设我给你的是员工的签到签退记录,里面每一行是时间戳和员工号。每个人应该每天有2次记录。已知今天有人只签了一次(只有一人!),我想让你查一下这个人是谁。要求,空间复杂度是O(1),时间复杂度是O(n)。问题二:原题中,假如我要统计的不是访问次数,而是in/out流量。找出流量最大的IP,该怎么办?

MySQL一个奇怪的IO问题

有一台机器,OS是CentOS release 5.8(2.6.18-308.1.1.el5.centos.plus), MySQL是5.5.27,通过RPM安装。表全是InnoDB(除了mysql的系统表)。MySQL所在的文件系统是xfs。下面这个SQL语句,执行一个多小时多没执行完:select count(*) from (select sum(count) as sum from top_no_ds_query_youku where query_date between '2012-11-01' and '2012-11-20'group by query) as temp_table;cpu负载不高,io wait在12.5%左右。更奇怪的是,有2-3条这样的SQL语句一起执行的时候,io wait会到30%左右,于是整个操作系统会变得特别慢,慢到sshd不接受新的连接。这个太要命了。但是现有的ssh连接可以clone,于是我顺利的用现有的ssh连接clone之后kill掉query。在kill之前我用vmstat看了一下,发现大约有9个进程处于uninterruptible sleep,running队列的长度只有1左右。然后呢,我找了另外一台机器做mysql slave。无RAID,SATA硬盘。内存也比master小,只有8G。OS是fedora 17,kernel是3.6.3-1,文件系统是ext4。MySQL是5.5.28。于是我就把master的my.cnf复制过去,改了一下innodb的buffer pool的大小和server id,其它都没动,然后启动,和主库进行replication。replication结束后,我在从库上测试这个SQL语句,结果只花了20秒就执行完了。期间IO非常正常,在0.4%以下。IO写入量高峰期在60MB/s左右,tps最高在600左右。这算是BUG吗?谁的BUG呢?

又遇到Pig的一个Bug

(这篇blog没啥阅读价值,纯粹工作郁闷吐槽)测试数据,是一个文本文件,每行都是一个整数。[app_admin@test14 data]$ more /tmp/data/data1.txt
1
2
3
4
5
6测试脚本如下:a = load '/tmp/data/data1.txt' USING PigStorage() as (id);
g = group a by id;
d = foreach g {
b1 = FILTER a by id > 1;
b2 = FILTER a by id > 2;
b3 = FILTER a by id > 3;
GENERATE COUNT(b1.id) as c1 ,COUNT(b2.id) as c2 ;
}然后我们看看d的schema:grunt> describe d;
2012-11-20 18:21:33,598 [main] WARN org.apache.pig.PigServer - Encountered Warning IMPLICIT_CAST_TO_INT 6 time(s).
d: {id: bytearray}完全错了。正确的结果是d: {c1: long,c2: long}。原因是因为我写了一行废代码(就是上面标红的那个)。我进行了过滤操作,但是之后没有引用b3这个alias。然后pig就因此产生一个完全错误的schema。然后我去jira上搜了一下,上周已经有人发现这个Bug了:https://issues.apache.org/jira/browse/PIG-2970pig的nested foreach 的BUG超级多,尽量能避则避吧!

Hadoop与jvm gc策略

我最近我新上了几台hadoop机器,kernel用的比较新,是3.x的。然后发现负载常常在30-100左右,程序总是在gc,实际效率很低,这让我很苦恼。其实按常规的来说,把堆加大,加到不需要频繁gc即可。可是我后来发现不是堆大小的问题。post一个gc.log:1.069: [GC 31872K->5284K(122304K), 0.0088550 secs]
6.494: [GC 31690K->4514K(122304K), 0.0099710 secs]
6.508: [GC 33335K->32774K(122304K), 0.0100570 secs]
6.593: [GC 64647K->59923K(154176K), 0.0108310 secs]
6.604: [Full GC 59923K->59653K(200640K), 0.0508330 secs]
6.987: [GC 132863K->107292K(200640K), 0.0085310 secs]
6.995: [Full GC 107292K->106832K(267392K), 0.0401220 secs]
7.183: [GC 170576K->107056K(307264K), 0.0082470 secs]
7.533: [GC 215728K->135600K(322944K), 0.0074970 secs]
12.723: [GC 253360K->173598K(385024K), 0.0124620 secs]
12.735: [Full GC 173598K->173123K(465856K), 0.0724350 secs]
18.332: [GC 352903K->239422K(465728K), 0.0249970 secs]
18.357: [Full GC 239422K->238927K(557312K), 0.1160660 secs]
18.822: [GC 418706K->267380K(621440K), 0.0175090 secs]
19.325: [GC 511412K->267452K(621312K), 0.0022710 secs]
19.780: [GC 51…