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。

继续阅读

发表在 leveldb | 标签为 | 留下评论

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
发表在 C/C++ | 标签为 , | 留下评论

C 结构体初始化

1.前言

今天阅读linux kernel oom代码,看到一种结构体初始化方式,原来没见过,记录一下。

//结构体定义
struct oom_control {
	/* Used to determine cpuset */
	struct zonelist *zonelist;

	/* Used to determine mempolicy */
	nodemask_t *nodemask;

	/* Memory cgroup in which oom is invoked, or NULL for global oom */
	struct mem_cgroup *memcg;

	/* Used to determine cpuset and node locality requirement */
	const gfp_t gfp_mask;

	/*
	 * order == -1 means the oom kill is required by sysrq, otherwise only
	 * for display purposes.
	 */
	const int order;

	/* Used by oom implementation, do not set */
	unsigned long totalpages;
	struct task_struct *chosen;
	unsigned long chosen_points;
};
//初始化方式
struct oom_control oc = {
	.zonelist = NULL,
	.nodemask = NULL,
	.memcg = NULL,
	.gfp_mask = 0,
	.order = 0,
};

2.struct四种初始化的方式

初始化方式1: 定义时赋值(不可乱序,不可缺省)
初始化方式2: 定义后赋值
初始化方式3: 定义时赋值(可乱序 可缺省. 点号)
初始化方式4: 定义时赋值(可乱序 可缺省 : 冒号)

//测试代码
#include <stdlib.h>
#include <stdio.h>

struct test_struct {

	int    a;
	char*   p;
};

int main()
{
	struct test_struct imp;
	imp.a = 100;
	imp.p = "hello world100";

	struct test_struct imp0 = {
		.a = 0,
		.p = "hello world0"
		};
	struct test_struct imp1 = {
		a : 1,
		p : "hello world1"
	};
	struct test_struct imp2 = {2, "hello world2"};

	printf("imp  a:%d  p: %s\n", imp.a, imp.p);
	printf("imp0 a:%d  p: %s\n", imp0.a, imp0.p);
	printf("imp1 a:%d  p: %s\n", imp1.a, imp1.p);
	printf("imp2 a:%d  p: %s\n", imp2.a, imp2.p);
	
	return 0;
}

3.总结

相比顺序初始化而言,乱序初始化成员可以不按照顺序初始化,而且可以只初始化部分成员,乱序初始化有两种方式,一种是用点(.)符号,一种是用冒号(:)。

参考:https://gcc.gnu.org/onlinedocs/gcc/Designated-Inits.html

发表在 C/C++ | 标签为 | 留下评论

STL vector 扩容

昨天面试,面试官问到一个问题,vector怎么扩容的,我大概记得C++ premier有那么一句扩两倍。我说好像是扩两倍,面试官也没继续问也没反馈对错。甚是好奇对错,索性自己试验一把,并看下源码。

试验

代码

#include<iostream>
#include<vector>
using namespace std;

int main(int argc, char *argv[])
{
	vector<int> vInt;

	for(int i = 0; i < 100; i++ )
	{
		cout << "size:" << vInt.size() << "\t" << "capacity:" << vInt.capacity() << endl;
		vInt.push_back(1);
	}

	return 0;
}

输出

size:0	capacity:0
size:1	capacity:1
size:2	capacity:2
size:3	capacity:4
size:4	capacity:4
size:5	capacity:8
size:6	capacity:8
size:7	capacity:8
size:8	capacity:8
size:9	capacity:16
size:10	capacity:16
size:11	capacity:16
size:12	capacity:16
size:13	capacity:16
size:14	capacity:16
size:15	capacity:16
size:16	capacity:16
size:17	capacity:32
size:18	capacity:32
......

源码

在这只把扩容相关代码贴出来罢了。

//SGI STL v3.3
void push_back(const _Tp& __x) {
if (_M_finish != _M_end_of_storage) {
  construct(_M_finish, __x);
  ++_M_finish;
}
else
  _M_insert_aux(end(), __x);
}

iterator insert(iterator __position, const _Tp& __x) {
size_type __n = __position - begin();
if (_M_finish != _M_end_of_storage && __position == end()) {
  construct(_M_finish, __x);
  ++_M_finish;
}
else
  _M_insert_aux(__position, __x);
return begin() + __n;
}

template <class _Tp, class _Alloc>
void 
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
{
  if (_M_finish != _M_end_of_storage) {
    construct(_M_finish, *(_M_finish - 1));
    ++_M_finish;
    _Tp __x_copy = __x;
    copy_backward(__position, _M_finish - 2, _M_finish - 1);
    *__position = __x_copy;
  }
  else {
    const size_type __old_size = size();
    //原容量为0扩为1,否则扩为原2倍
    const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
    iterator __new_start = _M_allocate(__len);
    iterator __new_finish = __new_start;
    __STL_TRY {
      __new_finish = uninitialized_copy(_M_start, __position, __new_start);
      construct(__new_finish, __x);
      ++__new_finish;
      __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
    }
    __STL_UNWIND((destroy(__new_start,__new_finish), 
                  _M_deallocate(__new_start,__len)));
    destroy(begin(), end());
    _M_deallocate(_M_start, _M_end_of_storage - _M_start);
    _M_start = __new_start;
    _M_finish = __new_finish;
    _M_end_of_storage = __new_start + __len;
  }
}

在push_back或者inster的时候,vetor容量不够扩容为原长度两倍。
这个增长因子和各版本STL实现有关,有的版本用1.5

为什么是扩为原长度2倍

因为每次扩容都涉及到原来元素的copy。空间和时间的权衡。
简单来说, 空间分配的多,平摊时间复杂度低,但浪费空间也多。
具体参见算法导论中,平摊分析那一章关于动态表扩张的分析。

发表在 STL | 标签为 , | 一条评论