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 内存池"