“Tair LDB基于Prefixkey的范围查找性能优化”这个项目刚好进行了一个月，这一个月主要是熟悉项目、掌握项目和提出设计方案的过程，下面从几个方面总结下个人在该项目上所做的工作及自己的个人所得所感。

项目工作简单总结

1. 项目实施计划的确定

        不管什么类型的项目（大、小，难、易），在项目开展之前都应该有个可实施的计划，一方面能够确保项目的进度，另一方面也能防止有些人三天打鱼两天晒网的心态。在导师的细心指导下，我们确定了下面的几个基本计划及其最迟完成时间估计。

（1）搭建测试环境，把现有的Tair LDB接口测试一下，重点是Get/Put/Del和对应的Prefix系列接口以及衍生出来的getrange接口（该接口就是我们需要优化的）。包括思考今后的性能对比测试该如何进行和准备相应的测试工具。

完成时间：7.12之前

（2）分析Get/Put/Del和对应Prefix系列接口的数据在leveldb中存储有什么不同。

完成时间：7.15之前

（3）在这个过程中细致理解leveldb存储原理。

完成时间：7.23之前

（4）同时可以参考下rocksdb，其他系统和paper。

完成时间：7.28之前

（5）1-4点完成后，看看是否有可实施的方案出来。

完成时间：8.1之前

2. 项目环境的搭建和基本接口测试

        在了解tair这个开源KV缓存系统的基本功能和基本架构后，首先需要做的就是把环境搭好，然后根据官方TAIR命令说明进行基本接口如put/get/delete/get_range/prefix系列的命令行测试，让自己对这个系统的使用和基本功能有个大概的掌握。第一次搭环境总是各种不顺，系统库版本的冲突、依赖软件、环境变量的设置、安装成功却启动失败等等问题，导致搭个环境花了一整天的时间，可能是自己经验不足，好在最终搭建成功，并在第二天记录下了整个搭环境的过程及期间出现的有价值的错误解决方案，一方面为后面安装多台dataserver时作参考，另一方面也希望能为tair新手提供一点小小的帮助，尽量将搭环境浪费的时间降至最低。

淘宝分布式 key/value 存储引擎Tair安装部署过程及Java客户端测试一例

在测试过程中，发现tairJava客户端及命令行测试中都没有加入get_range测试接口，好在tairC++客户端已经实现了该接口，只是没有封装成命令供客户端调用，而我们的项目主要就是优化这个接口，对其进行测试必不可少，因此在掌握命令封装方法的基础上为其添加了get_range接口的命令测试，此时已经对基本接口的实现有了初步的了解，这些接口在客户端和服务端都有实现，客户端负责用户的请求解析，并将请求封装成数据包发送给服务端进行处理，服务端就是各种存储引擎，如我们关心的leveldb引擎，其真正实现了用户的请求操作，并将结果反馈给客户端。

tair中对get/get_range接口的理解及为get_range添加命令行测试接口

3. tair性能对比测试方案

        关于性能对比测试，自己没有什么经验，一方面自己写过的性能相关的C++程序或项目都不那么复杂，使用Linux内置的C++性能测试工具如gprof就已足够，没用过其它什么复杂的框架；另一方面tair是分布式系统，相对较复杂，调研适用于分布式系统的C++性能测试工具也比较少，就算找到了工具还要花时间学习、费力去适应工具的条件，由于我们的需求相对不是很复杂，完全没有必要去使用复杂的工具。在导师的指导下，我们最终决定自己写一个简单的性能测试工具，可以借鉴rocksdb等存储引擎的基准测试程序思路，主要关心服务端的极限QPS和单个操作的响应时间rt这两个衡量指标。

tairldb存储引擎性能测试方案

4. leveldb中prefix系列接口的特点及理解leveldb的存储原理

        关于leveldb的存储思想及原理看了不少参考资料和文档，每天看一点并结合源码分析，渐渐明白了为什么不选B+树存储数据而采用LSM的存储结构，知道了为什么要有skiplist这样优化链表的结构，还下载了相关的论文想要细细研究其具体的实现原理。这些是基础，在此之上还有leveldb的分层存储和分级存储，分层指的是leveldb的数据首先存在memtable中，Put的数据达到一定量后变成immutable memtable，最后存到sstable file中，而sst file又进行分级管理（level 0 ~ level n），level 0的files中key可能互相有重叠，而其它级的key都不会重叠，每个level上的数据都是排好序的。还有其它的知识点，比如版本管理实现的比较巧妙，通过引用计数能够有效的保护并发更新。一开始不知道get_range接口的数据都来自prefix_put/prefix_incr这样的接口，因此对prefix系列的接口没有投入很多的关注，以为与其它接口的区别就是prefix系列接口方便用户一次性能够put和get有着共同prefix的所有数据。后来在导师的指导下才知道prefix接口的优势在于：由于tair是根据hash分区的，而prefix系列的接口是根据prefixkey去hash的，所以能确保拥有相同prefix的key在同一台服务器上。这样在查找时就快得多，在查询有着相同prefix的数据时就不用到每个服务器上找一遍。

Tair存储引擎之一Leveldb中数据的存储思想

5.  对rocksdb存储引擎及相关paper的调研

        由于我们的项目是对范围查找进行优化，并提议使用bloomfilter的方案。bloomfilter之前有过了解并使用过简单的例子，由于hash不支持范围查找，因此bloomfilter本身也是不支持范围查找的，因此项目一开始我就进行了大量的调研，看能不能采取某种策略或优化手段使得bloomfilter能够支持范围查找，以证明方案的可行性。最后找到了几篇相关的论文，提到让bloomfilter支持范围查找确是可行的，只是需要修改数据结构或方法，比如有一篇论文提出了一种分段Bloomfilter+多阶段查询的方法使得支持范围查找，另一篇论文提出了一种类似于Bloomfilter的基于Trie数据结构的bloomfilter改造版，存储空间与原bloomfilter相当且查询性能较高。这些论文中提出的方案虽然具有可行性，但毕竟是实验性质的且算法较复杂，不适用于所有类型的范围查找。比如leveldb中的get_range接口，其中的pkey参数即key的prefix没有利用到。后来对leveldb的“升级版”rocksdb（Facebook开源存储引擎）进行了大量调研，因为在其官网blog中提到说rocksdb利用prefix信息使得bloomfilter能够支持范围查找。为了研究其如何实现范围查找，就深入研究了rocksdb的部分代码，发现其对key的prefix信息生成bloomfilter实现前缀过滤功能，且这里的prefix长度是由用户指定，但rocksdb本身并没有实现范围查找的接口。受到这种利用prefix进行bloomfilter过滤思想的启发，我们提出了自己的方案，即使用prefix bloomfilter进行范围查找的过滤。当然rocksdb优化的地方还有很多，抱着学习的目的，我也简单总结了我研究rocksdb部分代码时所看到的优化措施。

对LevelDB的“升级版”存储引擎RocksDB的调研成果

6.  基本可实施方案的成型

        有了基本思想后，我们就要考虑在leveldb中如何利用该思想形成一个可实施的方案，我首先根据自己对leveldb的理解做了一个初步的方案，不够简洁，且没有考虑tair客户端一些数据的特点。后来在导师的指导和建议下一步步改进方案，最终形成一份简洁的可实施方案。有了方案后，方案的具体实现就很重要了，比如需要改动源码中的哪些模块、具体怎么改动等，当然原则是改动越少越好，尽量不影响原来系统中已有的数据结构，遵循开闭原则。根据方案我首先给出了方案实现的伪代码，由于经验不足还是有诸多欠缺的地方及没有深入考虑的地方，这些不足导师都帮我一点点指出来并给出了建议方案，不仅让我更加深入掌握了tair ldb的更多知识，也让自己深感在C++项目方面经验的不足，需要不断深入的学习。

Tair LDB基于Prefixkey的范围查找性能优化项目提议方案

个人总结

这一个月来，与其说是在做项目，不如说是在不断地学习。

（1）首先这是个C++项目，对于一个以前专攻Java的我来说算是个挑战，Java项目大大小小做过不少，看Java代码非常轻松，自己也维护过大型Java项目，帮其写过注释啥的。而C++项目只做过一个，就是前不久完成的研究生论文项目（本科的课程设计就不说了，太水），还是自己一个人独立完成，没有任何指导，做出的东西相信也是不完善的。好在自己看过一些C++开源项目，如Google的RE2正则表达式库，当时还对Google的C++测试方案进行了一定的研究（从Google开源RE2库学习到的C++测试方案），这对现在看Google的leveldb库有了一定的帮助。看tair项目过程中学到了不少以前未掌握的C++基础知识，比如在函数传对象参数时最好使用引用方式传递（加&）而非复制方式传递，因为引用方式传递时形参和实参指向同一块地址，就不需要创建临时对象，避免了内存拷贝，节省内存空间。还有一些语言细节方面的，比如在使用vector时用emplace_back代替push_back避免冗余的copy and move，还使用了一些C++11的特性如使用继承控制关键词override来防止在类层次结构上的不一致等等。虽然都是一些语言细节，但对于C++菜鸟来说非常值得学习和掌握。

（2）其次，这是一个分布式系统，本以为自己对这块没有太大问题，因为自己以前用过一些Java的分布式通信框架如Corba、WebService、RMI等，基本的通信原理还是清楚的，不过自己只限于了解原理却没有深入的去了解其具体是如何实现的。一开始只知道分布式系统有个客户端实现和服务器端实现，但两者具体如何交互链接、采用什么通信手段还是不清楚，后来在导师的指导下知道了两者的交互接口文件，加上底层的通信代理机制RPC渐渐对分布式通信原理有了更深入的理解。当然分布式系统除了分布式通信机制外还包括服务器端的负载均衡、数据的分布特点等，目前对这块知识还是稍有欠缺，只知道tair中使用了config  Server和data Server两种角色，使用一致性hash算法实现负载均衡，对照表描述bucket与其存储节点标示符（如IP地址）间的映射，但具体的实现还是不甚了解，导致对tair系统的整体性把握不太好。自己对这块的实现还是很感兴趣的，只是目前苦于找工作的压力只能将该模块的研究延后。

（3）最后，自己对自己在该项目中的表现不太满意，可能有两方面的原因：一是自己的技术能力还不够强，看C++代码看的比较慢，有时候想不通一个问题思考许久还不得果，还好导师耐心指导，一点即通；二是个人性格所致，自己一向比较贪玩，一到周末就想着各种happy，还有不注意身体得了点小病，这些都影响了项目的进度，自知感到羞愧。后面的时间更加紧凑，一方面克服惰性尽自己所能做好项目，一方面还要准备工作，我会合理安排时间，做好这个于我而言非常有价值的C++开源项目。