memtable是LevelDB的核心数据结构之一,它的底层实现是SkipList,是一个内存层面的容器,负载主要的写需求。
SkipList
SkipList其实一个一个多层次链表,在查找时,先在最后层次进行查找,找到比较大的数据时就往低层次退,
直到找到相等的key或者已经遍历完层次1。skiplist算法分析
SkipList有几个主要底层的函数:
- FindGreaterOrEqual
- KeyIsAfterNode
- Insert
- FindLessThan
- FindLast
- RandomHeight
实际上skiplist的对外API Seek的主要实现就是FindGreaterOrEqual,
FindGreaterOrEqual包揽了几乎所有的逻辑,因为在插入和查找时,都需要先进行FindGreaterOrEqual。
按照多层次的思想就很容易理解FindGreaterOrEqual。
- 选定skiplist的最高层(L5)。
- 从选定层(L5)开始直接跳到>= K43的位置。
- 以最终结果(红色方格)的上一跳的元素(橙色方格)开始,退到下一层(L4)再进行跳跃。
- 重复步骤2直到找到跟K43相等的元素或者已经遍历完L1(最底层)为止。
从leveldb实现上需要注意FindGreaterOrEqual(const Key& key, Node** prev)。
FindGreaterOrEqual在遍历过程中会把图中橙色方格的指针通通记录到prev内,供Insert步骤修改指针使用。
理解FindGreaterOrEqual后,Insert步骤也迎刃而解。
初始状态
FindGreaterOrEqual
插入完成
Insert步骤实际上就是使用FindGreaterOrEqual找到结果以后,再利用结果修改指针,插入数据,具体步骤:
- 使用RandomHeight生成新节点的层高(图中是L6),按照这个层高new一个新Node。
- 如果层高超过原有的最高层高,需要开辟新层次,直接把新层高指向NULL,如果没有超过则忽略步骤2。
- 进行FindGreaterOrEqual。
- 根据prev返回的结果,修改prev里所有的Node的指针到新Node,同时把新Node的指针指向原有Node指向的对象。
Memtable
memtable主要作用是对skiplist,arena,comparator进行和组合和管理,功能函数上只是屏蔽了底层操作,对使用者更加优雅,所以无需再次分析。
其中arena是leveldb自己实现的内存池,按一定对齐字节分配,实现简单,这里不作具体分析。
memtable会对自身做一个refs计数,当refs为零的时候,memtable执行自行清理。
Memtable在leveldb中的整体作用
memtable在leveldb中所起到的作用是提供随机写的一个容器,相当于一层在leveldb中的外层屏障,肩负最大的写入压力。
当memtable增长一定的内存时。leveldb会把它转化为一个immutable_memtable,然后紧接着放到后台进行compaction操作,
使memtable里面的数据落地。
至此,Memtable的主要功能都分析完毕了。