Browsed by
月度归档: 2016年1月

leveldb原理剖析

leveldb原理剖析

最近在读leveldb源码,发现了这篇文章,感觉蛮不错,转载了过来。

转载:https://www.ezlippi.com/blog/2014/11/leveldb.html

 

在说LevelDb之前,先认识两位大牛,Jeff Dean和Sanjay Ghemawat,这两位是Google公司重量级的工程师,为数甚少的Google Fellow之二。

Jeff Dean其人:http://research.google.com/people/jeff/index.html,Google大规模分布式平台Bigtable和MapReduce主要设计和实现者。

Sanjay Ghemawat其人:http://research.google.com/people/sanjay/index.html,Google大规模分布式平台GFS,Bigtable和MapReduce主要设计和实现工程师。

LevelDb就是这两位大神级别的工程师发起的开源项目,简而言之,LevelDb是能够处理十亿级别规模Key-Value型数据持久性存储的C++ 程序库。正像上面介绍的,这二位是Bigtable的设计和实现者,如果了解Bigtable的话,应该知道在这个影响深远的分布式存储系统中有两个核心的部分:Master Server和Tablet Server。其中Master Server做一些管理数据的存储以及分布式调度工作,实际的分布式数据存储以及读写操作是由Tablet Server完成的,而LevelDb则可以理解为一个简化版的Tablet Server。

Read More Read More

Hash 散列函数

Hash 散列函数

今天读leveldb代码,看到murmur散列方法,突然想起以前公司关于hash的故事。所在产品线的一套代码十几年,一直在维护,新需求来了就是在上面增加模块,不带第三方库毫不夸张几十万行,记得某个文件没重构之前3w行。经手的人一多,加上产品线平台基础库推广力度不够,就是各种造轮子。



其中用的最多的哈希表 初始化是这个样子的,(当然hash表的实现也很多) :


//** bucket_cnt     :桶的个数
//** hash_key_func_t:哈希函数指针
//** hash_compare_t :键值比较函数指针
//** hash_destroy_func_t:释放节点中data数据的函数指针
//** hash_nodesize_cnt_t:哈希节点占用内存大小计算函数指针
//** bucket_depth	:桶的深度,设置为0表示不做限制
//**************************************************************************
hash_t *hash_init (	int	bucket_cnt, 
						hash_key_func_t     key_func, 
						hash_compare_t      compare_func,
						hash_destroy_func_t destroy_node_func,
						hash_nodesize_cnt_t nodesize_cnt_func = NULL,
						int	bucket_depth = 0);



感觉接口设计挺好的,但,hash函数需要自己实现,导致系统种各种散列函数的存在,加乘异或移位,其中当然有好的实现,但是那么一两个我竟然看到了&,为什么没出事我也不太清楚,可能是数据不多。



某一天,系统(DPDK收包然后处理)出现丢包现象,最后的定位问题是哈希表散列性不好,导致某些桶特别深,查询出现热点,相当于在一个相当长的list上遍历比较,一直返回不了,数据量一大就出现丢包,最后修改散列函数后改善。此事之后凡是用到哈希表,单元测试都要求对其随机分布性做测试。

Leveldb使用的murmur hash变种,redis也有用到murmur hash。

MurmurHash 是一种非加密哈希函数,适用于一般的哈希检索操作。由Austin Appleby在2008年发明,并出现了多个变种,都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比,对于规律性较强的key,MurmurHash的随机分布特征表现更良好。–wiki

在这里贴一下leveldb的源码:

#ifndef FALLTHROUGH_INTENDED
#define FALLTHROUGH_INTENDED do { } while (0)
#endif

namespace leveldb {

uint32_t Hash(const char* data, size_t n, uint32_t seed) {
  // Similar to murmur hash
  const uint32_t m = 0xc6a4a793;
  const uint32_t r = 24;
  const char* limit = data + n;
  uint32_t h = seed ^ (n * m);

  // Pick up four bytes at a time
  while (data + 4 <= limit) {
    uint32_t w = DecodeFixed32(data);
    data += 4;
    h += w;
    h *= m;
    h ^= (h >> 16);
  }

  // Pick up remaining bytes
  switch (limit - data) {
    case 3:
      h += static_cast<unsigned char>(data[2]) << 16;
      FALLTHROUGH_INTENDED;
    case 2:
      h += static_cast<unsigned char>(data[1]) << 8;
      FALLTHROUGH_INTENDED;
    case 1:
      h += static_cast<unsigned char>(data[0]);
      h *= m;
      h ^= (h >> r);
      break;
  }
  return h;
}


}  // namespace leveldb