上周日与两大牛参加北大校赛，很久没写题，本着打酱油的心态去参赛，最后也真打酱油了，没写过一题代码，就在赛场上坐着、看着、想着，有两个题目我还不知道是啥队友就已经把它过了。回来后，听身边的哥们在讨论“Mission Impossible”这道题，我也就去看了一下，题目地址：http://poj.openjudge.cn/practice/1030/。
这个题目的意思很清晰，给定一个整数N（N > 1），找出满足以下条件的K1, K2, K3, … KN ：
很明显，这是一道数论的题目，以前我在役时，这类型的题目是我的最爱，总想把它给征服了，不过这个题目对N的要求不大，不超过9，可以先暴力求解，再打表，现场有很多队就这么过的，当然暴力也有技巧，不然也不会还有一半的队伍没过，不然我们队刚开始时也不会等很久没等待出结果。周一细细想了许久，找到了一些门道，下面先从最简单的暴力方法开始，慢慢进阶到通关秘诀。
Read more »
gzip是GNU zip的缩写，是一个GNU自由软件的文件压缩程序，也经常用来表示gzip这种文件格式。软件的作者是Jean-loup Gailly和Mark Adler。1992年10月31日第一次公开发布，版本号是0.1，目前最新的稳定版本是1.4。
gzip的基础是DEFLATE，DEFLATE是LZ77与哈夫曼编码的一个组合体。DEFLATE最初是作为LZW以及其它受专利保护的数据压缩算法的替代版本而设计的，当时那些专利限制了compress以及其它一些流行的归档工具的应用。
需要注意的是，gzip仅对单个文件进行压缩，不具备打包归档功能，一般先通过外部归档工具将文件/目录打包后再使用gzip进行压缩。另一种压缩格式zip也使用DEFLATE算法，而且可移植性更好，并且不需要一个外部的归档工具就可以包容多个文件。
HTTP/1.1协议允许客户端可以选择要求从服务器下载压缩内容，这个标准本身定义了两种压缩方法：“gzip”（内容用gzip数据流进行封装）以及“deflate”（内容是原始格式、没有数据头的DEFLATE数据流）。许多HTTP客户端库以及绝大多数当今的浏览器都支持这两种格式。
Read more »
最近在看Erasure Code，多篇论文中总是提到RAID，以前倒是知道RAID是用于做啥的，却没有深刻地认识，本文将去深入地了解RAID的原理。
RAID是一种将多个磁盘合成一个逻辑单元的存储技术，数据可以通过多种不同的方式分布在磁盘上，这些方式称为“RAID levels”，具体采用哪个level取决于需要的冗余级别和性能。
最初，RAID的提出是为了满足磁盘IO性能提升与CPU、内存性能提升相匹配，才能充分利用CPU、内存，避免资源浪费。
RAID是存储虚拟化的一个例子，最初由David Patterson等人在1987年定义为“Redundant Arrays of Inexpensive Disks”，直译过来就是廉价硬盘冗余阵列。后来，工业界试图重新定义该术语，将其描述为“a redundant array of independent disks”，即独立磁盘的冗余阵列，将低成本从RAID技术中分离，商人追求利益最大化，这也是情有可原的。
现在，RAID是能在多块物理磁盘之间分割和复制数据的计算机数据存储方案的总称，这些物理磁盘被称为一个RAID阵列，操作系统将其视为一个单一磁盘。目前有多种不同的方案（比如RAID 0、RAID 1、RAID 2等），每种方案在数据可靠性和读写性能做出不同的权衡。
Read more »
又一个季度过去了，习惯性地总结一下，这事情本应该在一个月前做的，不过最近看上去好忙，抽不出时间来写，这几天放假，静下心来好好想想、写写。事情多与少取决于自己的目标和定位，而累不累由取决于自身心态。
三年的研究生阶段已过去一半，再过三四个月就要开始准备找工作了，要考虑这问题的一天终于到来了，有点手足无措。
小记：
在做测试或性能优化时，经常要知道程序运行的时间，在Linux系统可以使用time命令来计算程序运行运行所消耗的时间，能精确到毫秒，如果要精确到代码块或某个操作运行时所消耗的时间，time命令就不给力了。如果对时间的精度要求不高的话，可以调用标准C的接口time来得到开始和结束的时间，再调用difftime接口来计算时间差，精度是秒，代码如下所示：
如果要让程序休眠3秒，Windows使用Sleep(3000)，Linux使用sleep(3)，即Windows的Sleep接口的参数的单位是毫秒，Linux的sleep接口的参数的单位是秒。
Read more »
Hadoop版本：hadoop-0.20.2
datanode在启动后，会定期向namenode发送心跳报告，并处理namenode返回的命令，经过前面的分析，已经基本弄清楚datanode相关的类，本文将分三部分对剩下的Datanode这个类进行分析，分别是datanode的启动、公共接口和运行。Datanode位于org.apache.hadoop.hdfs.server.datanode这个包，类图如下所示：
Hadoop版本：hadoop-0.20.2
DataBlockScanner是datanode上很重要的部分，用于周期性地对块文件进行校验，当客户端读取整个块时，也会通知DataBlockScanner校验结果。这个类位于包org.apache.hadoop.hdfs.server.datanode中，与DataBlockScanner相关的类图如下所示：
Hadoop版本：hadoop-0.20.2
现在已经知道datanode是通过DataXceiver来处理客户端和其它datanode的请求，在分析DataXceiver时已经对除数据块的读与写之外的操作进行了说明，本文主要分析比较复杂而且非常重要的两个操作：读与写。对于用户而言，HDFS用得最多的两个操作就是写和读文件，而且在大部分情况下，是一次写入，多次读取，满足高吞吐量需求而非低延迟，除去客户端与namenode的协商，剩下的部分主要是客户端直接与datanode通信（数据流的头部在上篇文章中已介绍），发送或接收数据，而这些数据在datanode如何接收并写入磁盘、如何从磁盘读出并发送出去就是本文所要介绍的内容。
Read more »
Hadoop版本：hadoop-0.20.2
之前已经对datanode的结构和存储进行了分析，本文将分析datanode的行为，能明确数据在datanode之间如何传输。在datanode中，块数据的接收和发送主要是通过DataXceiver，这部分的网络传输没有采用RPC，而是传输的TCP连接，这部分所涉及到的类的包结构如下所示 ：
以下是DataXceiver相关的类图：
小王长于广东，高中之前，除了语文课，其它课均用家乡话上课，貌似家乡话也没平舌翘舌、前鼻后鼻之分，自己也没去在意，一直说着比较普通的普通话。直到上了高中，同学来自潮汕各地区，由于潮汕各地区说话各异，无论是从发音或用语都是，跟同是闽南语系的闽南话、台湾话差别更大，这样的变化好比全国很多地区说的话跟普通话是一个语系，但不同地区的人可能彼此不太能听懂对方的话，加之有些老师是外地人，于是我们主要用普通话来交流，但这也没改变说普通话的普通性。上大学了，来到北京，周围说着电视上说的普通话，比较尴尬的我听懂别人说的，别人听不懂我说的，在北京生活快六年了，至今说话有时仍会让人很不解，有时有同学来北京玩，在一起时他（她）们就会说“你的普通话怎么还是那样子”，是的，这几年我的普通话就没进步。
很久以前，就想着要学习普通话，但一直没付诸行动，最近终于有了点进展，先是学习各声母和韵母的发声规则以及舌头的摆放位置，但这似乎还没解决问题，小王从初中接触电脑就学习五笔，一直用到现在，其实很多字我根本就不知道其拼音是啥，有可能同一个字，不同时候发出来的音都不一样。于是最近花半个月的零碎时间整理了一些我可能会混淆的拼音，主要是平舌翘舌、前鼻后鼻，有事没事就拿出来看看，跟背英语单词似的，有人跟我说语言这东西靠的就是记和感觉，挺有道理的。
Read more »
