comparator

class Comparator一个虚基类，提供用户自定义比较器的接口(默认的比较器实现会带来leveldb的特性中的“Keys and values are arbitrary byte arrays.”)。头文件的注释非常详尽，并且作者提供的实现也很简单，所以不做解释。
但是，值得注意的是，作者再一次使用了如下的方式

// comparator.h
namespace leveldb {
  class Comparator {
   // ...
  };
  extern const Comparator* BytewiseComparator();
}

// comparator.cc
namespace leveldb {
  namespace {
    class BytewiseComparatorImpl : public Comparator {
      // ...
    };
  }
  static port::OnceType once = LEVELDB_ONCE_INIT;
  static const Comparator* bytewise;

  static void InitModule() {
    bytewise = new BytewiseComparatorImpl;
  }

  const Comparator* BytewiseComparator() {
    port::InitOnce(&once, InitModule);
    return bytewise;
  }
}

这里和在Env中的一样，在匿名命名空间中提供了一个实现，然后通过一个函数将这个内通过基类的指针暴露出去，并且，这里的基类也是static修饰的，在什么时候释放掉它指向的内存目前来看也是不清楚的。。。

filter_policy

这个东西是作者用来减少磁盘访问用的(将一些key存放在一个集合里面，如果要查找的key可能在这个集合里面才去访问硬盘获取值)，默认实现使用的是Bloom filter。

// 2016-04-16 更新
下面来看看默认的布隆过滤器的实现。

构造函数

explicit BloomFilterPolicy(int bits_per_key)
      : bits_per_key_(bits_per_key) {
    // We intentionally round down to reduce probing cost a little bit
    k_ = static_cast<size_t>(bits_per_key * 0.69);  // 0.69 =~ ln(2)
    if (k_ < 1) k_ = 1;
    if (k_ > 30) k_ = 30;
}

作者建议bits_pre_key取10为好，这是false positive rate会约等于1%，而这里的k_就是一系列布隆过滤器大小的限制。

创建过滤器

  virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const {
    // Compute bloom filter size (in both bits and bytes)
    size_t bits = n * bits_per_key_;

    // For small n, we can see a very high false positive rate.  Fix it
    // by enforcing a minimum bloom filter length.
    if (bits < 64) bits = 64;

    size_t bytes = (bits + 7) / 8;
    bits = bytes * 8;

    const size_t init_size = dst->size();
    dst->resize(init_size + bytes, 0);
    dst->push_back(static_cast<char>(k_));  // Remember # of probes in filter
    char* array = &(*dst)[init_size];
    for (int i = 0; i < n; i++) {
      // Use double-hashing to generate a sequence of hash values.
      // See analysis in [Kirsch,Mitzenmacher 2006].
      uint32_t h = BloomHash(keys[i]);
      const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
      for (size_t j = 0; j < k_; j++) {
        const uint32_t bitpos = h % bits;
        array[bitpos/8] |= (1 << (bitpos % 8));
        h += delta;
      }
    }
  }

参数中的Slice *key是key的列表，int n是列表中key的个数，std::string* dst是用于存放过滤器的容器。这个函数的前面部分是计算过滤器占用的空间（将bits转化成bytes），并将过滤器容器的容量增加这个大小，并将过滤器大小限制追加到过滤器的尾部。后面部分，作者这里实现的过滤器并不是储存1和0，而是在经过一个循环（保证不会超过过滤器大小限制k_），将key的哈希值（准确的说是哈希值加上某个值，用来替代一系列的散列函数）在过滤器空间中多次映射（同一个地方可能映射多次）。

看到这里，我只想说：布隆过滤器除了节约空间，剩下的都是缺点了（查找快，但是准确度低）。。。

过滤

  virtual bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const {
    const size_t len = bloom_filter.size();
    if (len < 2) return false;

    const char* array = bloom_filter.data();
    const size_t bits = (len - 1) * 8;

    // Use the encoded k so that we can read filters generated by
    // bloom filters created using different parameters.
    const size_t k = array[len-1];
    if (k > 30) {
      // Reserved for potentially new encodings for short bloom filters.
      // Consider it a match.
      return true;
    }

    uint32_t h = BloomHash(key);
    const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
    for (size_t j = 0; j < k; j++) {
      const uint32_t bitpos = h % bits;
      if ((array[bitpos/8] & (1 << (bitpos % 8))) == 0) return false;
      h += delta;
    }
    return true;
  }

如果参数中的key是上面创建过滤器时的一系列key中的一个，并且filter也是由这一系列的产生的，那么这个函数的返回值一定为真，前面条件不满足的话，大部分时候因该返回false。
那么，为什么过滤器的大小小于2就断定为假了呢？ 作者说bits_pre_key用10最好，前面产生过滤器的时候计算过，如果一系列中的key其实只有一个的话bytes = (10 + 7) / 8就是2。。。
那么，为什么过滤器的大小大于30就当作是真的呢？ 作者在构造函数中限定了过滤器大小为30，在创建过滤器时一系列散列的映射都在这个范围内，所以如果大于30的话，作者就不确定了，所以当它在里面吧，大不了多几次硬盘访问。。。
最后用了创建时的逆操作&来判断这个key是否在过滤器中。

暴露接口
又要提一下，上面的实现都是在一个匿名命名空间中的。通过下面的函数暴露出去

const FilterPolicy* NewBloomFilterPolicy(int bits_per_key) {
  return new BloomFilterPolicy(bits_per_key);
}

注意到，这里返回的是一个const类指针，这也是为什么基类里面的只有const成员函数的原因。

完。