Leveldb源码 skiplist 跳表

概述

跳表是一种有序数据结构,它通过在每个节点维持多个指向其他节点的指针,从而达到快速访问节点的目的。

跳表基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)。

插入新节点时,该节点层数随机。

更详尽的解释参见维基百科或自行google。贴两张维基百科的图片,便于大家理解。

大家有兴趣也可以去看redis的skiplist实现(zskiplist)。

继续阅读“Leveldb源码 skiplist 跳表”

Leveldb源码 Arena 内存池

概述

一个高性能的服务器端程序,内存的使用非常重要。多次的申请和释放引起的内存碎片,一旦碎片到达一定程度,即使剩余内存总量够用,但由于缺乏足够的连续空闲空间,导致内存不够用的假象。为了避免小块内存的频繁分配,最简单的做法就是申请大块的内存,多次分给客户。

一般的策略都是:
小块内存–>从内存池里拿;不够的话,内存池向系统申请新的大块。
大块内存–>直接问系统拿。

如果对这块感兴趣可以自行研究一下:ptmalloc、tcmalloc、Jemalloc、Nginx内存池。

Redis默认使用jemalloc,我们公司的项目也是使用jemalloc。

Redis的Makefile片段:

# Default allocator
ifeq ($(uname_S),Linux)
	MALLOC=jemalloc
else
	MALLOC=libc
endif

# Backwards compatibility for selecting an allocator
ifeq ($(USE_TCMALLOC),yes)
	MALLOC=tcmalloc
endif

ifeq ($(USE_TCMALLOC_MINIMAL),yes)
	MALLOC=tcmalloc_minimal
endif

ifeq ($(USE_JEMALLOC),yes)
	MALLOC=jemalloc
endif

ifeq ($(USE_JEMALLOC),no)
	MALLOC=libc
endif

好,言归正传。leveldb中实现了一个”一次性”的简单的内存池Arena,不是所有的地方都使用了这个内存池,主要是memtable(skiplist)使用

继续阅读“Leveldb源码 Arena 内存池”

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原理剖析”