Tair ldb（leveldb存储引擎）实现介绍 nosqlfan

winston

前两天分享了淘宝核心系统研发团队的资料《leveldb实现解析.pdf》，文章对leveldb的内部实现和运行机制都做了深入的分析。而下面文章来自同一位作者，为大家详细描述了淘宝开源的Tair在结合leveldb作为存储引擎上遇到的挑战和实战经验。
文章来源：rdc.taobao.com
Tair是淘宝开源的分布式KV缓存系统，内部将功能模块化，抽离出底层存储细节，可以接入不同的存储引擎。leveldb是Google开源的单机存储引擎，目前，已经作为Tair的持久化存储引擎ldb上线使用，这里对接入leveldb所做的处理以及修改进行介绍。
Tair首先是一个分布式的框架，有一系列策略满足CAP（数据备份，迁移复制等）。另外，还有针对应用场景的功能特性（namespace，数据过期时间，原子计数等）。接入leveldb时主要对KV操作之外的功能做相应的处理。leveldb本身的实现介绍参见leveldb实现解析。一. 修改配置
leveldb中有一系列参数会与读写的效率有关，将相关的配置以及编译常量统一修改成可运行时配置参数，测试选取最佳配置值。二. 实例个数控制
首先确定在一个tair server上要启几个leveldb实例？
Tair中以桶来组织数据，如果按照一个桶一个leveldb实例，在做迁移复制的时候会很方便，但考虑如果在一块磁盘上起多个实例，那么整体看来，多个顺序写变成了随机写，每个实例的compact进程会加剧整个磁盘的随机IO，所以并不采用每个桶一个实例，而是针对磁盘的数量由相关配置控制实例的个数。三. 内部key的格式
为实现Tair中的功能逻辑，ldb传入leveldb的user-key格式如下：

• Tair中的数据可以设置过期时间，过期时间保存可以保存在在value的meta中，但考虑能在leveldb内部提前检查，省去解析value的消耗，将过期时间保存在key中，但并不参与排序。
• Tair中的数据组织以及迁移复制都是以桶（bucket）单位，为获得一个桶的数据，添加桶号前缀，保证一个桶的数据都存储在一起。leveldb内部对key做前缀压缩，桶号基本都可以被压缩掉。
• Tair中的数据区分namespace，会将namespace作为客户端传入key的前缀存储。

四. 自定义comparator
为了实现Tair中的功能逻辑，实现自定义的comparator传入leveldb，实现自定义的排序逻辑(传入leveldb的user-key中表示过期时间的前四个字节不参与排序)，并为comparator添加两个判断数据是否有效的逻辑接口（ShouldDrop()/ShouldDropMaybe()）,修改leveldb内部做遍历以及compact时判断数据是否有效（kTypeValue/kTypeDeletion）的逻辑。

• ShouldDropMaybe(): 用来判断数据是否已经过期。解析key中的expired_time即可。
• ShouldDrop(): 用来判断数据是否属于已经清理掉的数据（bucket已经迁移或者namespace已经被清理）。
• 区分过期数据与清理数据的判断，是因为丢弃过期数据必须保证该key是数据的最后出现，否则删除该数据会让该key失去最后的更新状态，而清理数据有gc信息保证，不需要关心数据的状态。

五. 清理数据/自定义的内部compact逻辑
这里把清理数据的操作称为gc。1.    迁移的bucket以及清理的namespace中的数据
一旦发生bucket迁移或者清理namespace，会把相应的信息保存下来（GcNode） struct GcNode {   // 迁移走的bucket或者清掉的namespace   int32_t key_;   // 清理发生时的SequnceNumber,用来判断数据的时间点   uint64_t sequence_;   // 清理发生时的FileNumber，用来缩小compact的范围   uint64_t file_number_;   // 清理发生时的时间   uint32_t when_; };

• Tair中会有桶迁移或者namespace清理的操作，废弃的数据并不会立刻清理，依靠后续的compact进程清理。但同时桶又可能被迁移回来，namespace也可能继续使用。leveldb中的SequnceNumber恰好可以标识数据的时间点，所以在做数据清理的时候，记录下当时的SequnceNumber（sequnce_），在做判断的时候，只有小于sequnce_的数据才认为可以被丢弃。
• filenumber_是为了缩小主动compact的范围。

leveldb自身进行compact的过程中，加入自实现 comparator 的 ShouldDropMaybe()/ShouldDrop() 判断逻辑，会将对应的gc数据清理。但leveldb自身的compact进程并不能保证将所有的数据清理掉，所以添加compact的定时线程，主动触发compact做数据清理。对于清理的bucket或者namespace，根据key的格式，可以构造出需要compact的key-range，但直接使用leveldb提供的CompactRange有以下问题：

• 如果某个sstable在记录gc之后已经被compact过，所要清理的数据就已经丢弃掉了，并不需要再做compact。
• 主动触发的compact并不是基于均衡db状态，所以造成的level迁移可能会有反作用。

对于1、2的问题，做以下策略：

• FileNumber全局递增可以用来标识时间点，gc时，记录下当时的FileNumber，主动compact时，只需要选取符合key-range并且FileNumber小于记录的filenumber_的sstable即可，缩小需要compact的sstable范围。
• 主动触发的compact只选取level-n中的sstable，compact后，也只生成level-n中的sstable，level之间的均衡，仍由内部compact进程负责。
• 基于上述1） 2），为leveldb添加CompactRangeSelfLevel()逻辑，实现1） 2）中的策略，主动触发compact以清理数据，整个db的均衡仍由内部的机制保证。

gc信息会同时记binlog，在server重启时replay。2.    过期的数据
因为过期是一个持续的时间状态，如果要完全回收过期的数据，只能对全db做compact，这样做的性能比不合算，所以目前对过期数据不做特别的主动清理，依靠内部以及外部触发的compact进程中回收空间。六. 上层cache
leveldb内部有sstable元信息和block数据的cache，优化读的效率，在leveldb上层再嵌入Tair自带的mdb做KV层面的cache，并添加cache的信息统计。当前统计看到，热点数据的读基本落在mdb中。七. 后续的优化

• leveldb本身的一些优化（参见leveldb的实现解析）。
• 优化网络的使用，使用新的网络框架。
• ssd使用优化。leveldb内部做的一些细节优化针对于sas盘的IO性能，当前使用的ssd IO能也未充分利用。后续针对提升ssd使用性能做相应的IO优化（dio）。
• 内存的优化使用。大内存的使用有很大的优化余地，避免swap的使用，pagecache的相应回写策略配置。
• 对不存在数据查找的优化，采用mock value处理或者添加bloomilter。
• range 以及数据dump功能的实现。

欢迎大家对leveldb的使用优化提出宝贵建议。
广告时间: Tair现在已经将Redis的存储部分抽离出来，作为非持久化的存储引擎rdb，即将上线使用，欢迎大家强势围观。

相关文章：
LevelDB实现解析	用Kyoto Tycoon挂载LevelDB存储	LevelDB学习交流	LevelDB内部实现	cpy-leveldb：Python版的LevelDB
无觅