Hadoop中VIntWritable编码方式解析

最近因为实验室的云计算项目，开始学习Hadoop，有时间就记录一下自己在学习过程中的一些小收获吧。

《Hadoop权威指南》在序列化这一节有个例子程序，叫做TextPair，代码略长，就不贴上来了，它implements了WritableComparable<TextPair>，将两个Text对象打包到一起。TextPair以静态内部类的形式实现了WritableComparator，这样，不从数据流中deserialize出对象也可以对TextPair进行比较了。实现的这个Comparator中的compare方法如下：

Java代码  

1. @Override  
2.     public int compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {  
3.   
4.         try {  
5.         int firstL1 = WritableUtils.decodeVIntSize(b1[s1])  
6.             + readVInt(b1, s1);  
7.         int firstL2 = WritableUtils.decodeVIntSize(b2[s2])  
8.             + readVInt(b2, s2);  
9.         int cmp = TEXT_COMPARATOR.compare(b1, s1, firstL1, b2, s2,  
10.             firstL2);  
11.         if (cmp != 0) {  
12.             return cmp;  
13.         }  
14.         return TEXT_COMPARATOR.compare(b1, s1 + firstL1, l1 - firstL1,  
15.             b2, s2 + firstL2, l2 - firstL2);  
16.         } catch (IOException e) {  
17.         throw new IllegalArgumentException(e);  
18.         }  
19.     }  

  中间有两行代码比较有意思，int firstL1 = WritableUtils.decodeVIntSize(b1[s1])+ readVInt(b1, s1); 以及它之后的那一行类似的。第一个方法，decodeVIntSize，先看代码：

Java代码  

1. public static int decodeVIntSize(byte value) {  
2.     if (value >= -112) {  
3.       return 1;  
4.     } else if (value < -120) {  
5.       return -119 - value;  
6.     }  
7.     return -111 - value;  
8.   }  

  这个方法的功能是判断VInt的长度。这里还是稍微记一下VInt和Text，以免将来忘记。

  在decodeVIntSize方法中，现在只能是看到做了分类处理，但是具体是怎么分类还不太清楚。接着是readVInt这个方法，它是WritableComparator中的静态工具方法，我在WritableUtils工具类中也看到了类似的方法，这个在后边会贴出来。

Java代码  

1. public static int readVInt(byte[] bytes, int start) throws IOException {  
2.     return (int) readVLong(bytes, start);  
3.   }  
4.   
5. public static long readVLong(byte[] bytes, int start) throws IOException {  
6.     int len = bytes[start];  
7.     if (len >= -112) {  
8.       return len;           //1  
9.     }  
10.     boolean isNegative = (len < -120);    //2  
11.     len = isNegative ? -(len + 120) : -(len + 112);   //3  
12.     if (start+1+len>bytes.length)    //4  
13.       throw new IOException(  
14.                             "Not enough number of bytes for a zero-compressed integer");  
15.     long i = 0;  
16.     for (int idx = 0; idx < len; idx++) {    //5  
17.       i = i << 8;  
18.       i = i | (bytes[start+1+idx] & 0xFF);  
19.     }  
20.     return (isNegative ? (i ^ -1L) : i);     //6  
21.   }  

  readVInt引用了readVLong方法，readVLong从字节序列中尝试读取出一个采用变长编码方案的Long。因此，关键就在这个readVLong中了。

在标号1的地方，如果第一个byte>=-112，就将这个byte返回，亦即代表这就是我们想要的那个数，可以再结合 decodeVIntSize这个方法，可以确定，在VInt或VLong中，一个字节能表示的数是从0~127, -112~-1的，当数字小于了-112就会做特殊处理了，这就是开始用两个字节来存放。

往下看，在标号2的地方，又做了判断。要注意到的是，代码走到这里，表示要去的那个Int或Long已经不是用一个byte来表示的了，也就是说，第一个byte是用作长度标识了，但是从标号2这里又可以看出，第一个byte还可以用来判断这个数字是正数还是负数，从标号三可以看出，正负数的长度存储是不同的，原因从后面的代码可以看出。另外，这里分别为正数和负数做了最大8个byte长度的限制。VLongWritable的最大长度就是9，这里减一即是8.

在到达标号4时候，这个数字的长度已经计算出来了，剩下的就是解码出数字了，但是，如果解码出数字所需的byte数目超出了这个bytes数组的boundary，就只能抛出异常了。

从标号5开始对剩下的数据进行解码，对java的byte处理有点了解的都应该看得懂，只做一个对自己的提醒，使用bytes[start+1+idx] & 0xFF是为了确保获得正确的byte值，以防java帮你自动转换。如果你的byte的most significant bit是1，也就是说明这个byte是表示的负数，如果将这个负数与一个Long进行位的或操作，这个byte的所有高于第9位的所有位都会被填充上1，这可不是我们想要的。

标号6，之前做的判断这里用到了，如果是负数，就对它取-1，也就是11111111...（64个1，-1的二进制表示），的反，这么做的原因是在写入这个VInt或VLong的时候做了相反的操作，具体为什么这样我也高步太懂，但是这么做所有的数据byte（就是除了第一个byte）的most significant bit都是0.

以上两个方法 decodeVIntSize + readVInt 就完美地解析出了一个完整Text的长度。

在WritableComparator中并没有写VIntWritable或VLongWritable的方法，这时候找到VIntWritable。

Java代码  

1. public void readFields(DataInput in) throws IOException {  
2.     value = WritableUtils.readVInt(in);  
3.   }  
4.   
5.   public void write(DataOutput out) throws IOException {  
6.     WritableUtils.writeVInt(out, value);  
7.   }  

  嗯，大哥来了，WritableUtils，代码参上。同样，writeVInt引用了writeVLong

Java代码  

1. public static void writeVLong(DataOutput stream, long i) throws IOException {      
2.    if (i >= -112 && i <= 127) {  
3.       stream.writeByte((byte)i);  
4.       return;  
5.     }  
6.         
7.     int len = -112;  
8.     if (i < 0) {  
9.       i ^= -1L; // take one's complement'  
10.       len = -120;  
11.     }  
12.         
13.     long tmp = i;  
14.     while (tmp != 0) {  
15.       tmp = tmp >> 8;  
16.       len--;  
17.     }  
18.         
19.     stream.writeByte((byte)len);  
20.         
21.     len = (len < -120) ? -(len + 120) : -(len + 112);  
22.         
23.     for (int idx = len; idx != 0; idx--) {  
24.       int shiftbits = (idx - 1) * 8;  
25.       long mask = 0xFFL << shiftbits;  
26.       stream.writeByte((byte)((i & mask) >> shiftbits));  
27.     }  
28.   }  

  如果已经看到这里，我想也没有太多好说的了，先判断可不可以用一个byte表示，然后分为正负数处理，之后再计算长度，最后将数字编码成byte写入流。其实我写到这里才觉得，如果先找到write方法，什么都一目了然了，但是都写了这么多了，哎。。。就将就这样吧。

最后把大哥的readVLong也贴出来，这个方法是直接从stream中而不是从byte数组中读取，所以略有不同，但是思想还是一样的。

Java代码  

1. public static long readVLong(DataInput stream) throws IOException {  
2.     byte firstByte = stream.readByte();  
3.     int len = decodeVIntSize(firstByte);    //这个函数应该还是比较熟悉了吧  
4.     if (len == 1) {  
5.       return firstByte;  
6.     }  
7.     long i = 0;  
8.     for (int idx = 0; idx < len-1; idx++) {  
9.       byte b = stream.readByte();  
10.       i = i << 8;  
11.       i = i | (b & 0xFF);  
12.     }  
13.     return (isNegativeVInt(firstByte) ? (i ^ -1L) : i);  
14.   }  

内容比较乱，东西也比较简单，主要目的还是给自己理清一下思路，方便以后回头能直接了然于心。