MapFile和BloomMapFile文件

超、凢脫俗 2022-06-09 09:16 92阅读 0赞

# 一. MapFile文件 #

前面说过，SequenceFile文件是用来存储key-value数据的，但它并不保证这些存储的key-value是有序的，而MapFile文件则可以看做是存储有序key-value的SequenceFile文件。MapFile文件保证key-value的有序(基于key)是通过每一次写入key-value时的检查机制，这种检查机制其实很简单，就是保证当前正要写入的key-value与上一个刚写入的key-value符合设定的顺序，但是，这种有序是由用户来保证的，一旦写入的key-value不符合key的非递减顺序，则会直接报错而不是自动的去对输入的key-value排序，它的实现源代码可参考如下：

private void checkKey(WritableComparable key) throws IOException {
          //检查是否和上一个key保持有序
          if(size != 0 && comparator.compare(lastKey, key) > 0)
            throw new IOException("key out of order: "+key+" after "+lastKey);
              
          //将当前key写入缓存
          outBuf.reset();
          key.write(outBuf);                          // write new key
    
          //将当前key替换上一个key
          inBuf.reset(outBuf.getData(), outBuf.getLength());
          lastKey.readFields(inBuf);                  // read into lastKey
    }

很明显，既然MapFile文件存储的是有序的key-value，那么就可以通过对存储的key-value建一个索引来提高其随机读的性能。这样一来的话，MapFile文件的本质实际上则是由两个SequenceFile文件组成，一个用来存储key-value数据(\*/data)，一个用来存储key-value的位置索引(\*/index)。这个实现的源代码如下：

public synchronized void append(WritableComparable key, Writable val) throws IOException {
    
          //保证存储的key-value记录按照key有序
          checkKey(key);
          
          //按照设置的步长对key-value建索引
          if (size % indexInterval == 0) {            // add an index entry
            position.set(data.getLength());           // point to current eof
            index.append(key, position);
          }
    
          //将value写入缓存
          data.append(key, val);                      // append key/value to data
          size++;
        }

index作为文件的数据索引，主要记录了每个Record的key值，以及该Record在文件中的偏移位置。在MapFile被访问的时候，索引文件会被加载到内存，通过索引映射关系可迅速定位到指定Record所在文件位置，相对SequenceFile而言，MapFile的检索效率是高效的，缺点是会消耗一部分内存来存储index数据。需注意的是，MapFile并不会把所有Record都记录到index中去，默认情况下每隔128条记录存储一个索引映射。当然，记录间隔可人为修改，通过MapFIle.Writer的setIndexInterval()方法，或修改io.map.index.interval属性；另外，与SequenceFile不同的是MapFile的KeyClass一定要实现WritableComparable接口,即key值是可比较的。

# 二. BloomMapFile文件 #

BloomMapFile文件构建在MapFile的基础之上，唯一不同之处就是增加了一个bloom文件，该bloom文件主要包含一张二进制的过滤表，该过滤表可以提高key-value的查询效率。在每一次写操作完成时，会更新这个过滤表，其实现源代码如下：

public synchronized void append(WritableComparable key, Writable val) throws IOException {
        //将key-vakue记录写入对应的mapFile文件中
        super.append(key, val);
       
        //用key来更新bloom过滤表   
        buf.reset();
        key.write(buf);
        bloomKey.set(buf.getData(), 1.0);
        bloomFilter.add(bloomKey);
    }

bloom文件格式：

![1343098889_3000.jpg][]  
VERSION: 过滤器的版本号；

nbHash: 哈希函数的数量；

hashType: 哈希函数的类型；

vectorSize: 过滤表的大小；

nr: 该BloomFilter可记录key的最大数量；

currentNbRecord: 最后一个BloomFilter记录key的数量；

numer: BloomFilter的数量；

vectorSet: 过滤表；

# 三. ArrayFile和SetFile    #

**    SetFile**文件是基于MapFile的实现，它只有key，value为不可变的数据(特定的空值)。

public void append(WritableComparable key) throws IOException{
          append(key, NullWritable.get());
    }

**     ArrayFile** 文件也是基于MapFile实现，它就像我们使用的数组一样，key值为序列化的数字，即value对应的数组下标值。

public synchronized void append(Writable value) throws IOException {
          super.append(count, value);                 // add to map
          count.set(count.get()+1);                   // increment count
    }

[1343098889_3000.jpg]: https://img-my.csdn.net/uploads/201207/24/1343098889_3000.jpg