KVscan 实现经历

库的选择

这次实现中完全都在学新的东西,一下介绍一下这次学习到的东西以及使用到的库

• Gtest

  Google的单元测试库十分好用以及简单,唯一麻烦的地方是和cmake的配合,通 过网上看别人写的脚本大致学习了一下, 可以说单元测试帮助我将自己的项目 细分方便调试和梳理.

• cmake

  cmake正好是最近在学的东西,可以兼容emacs的irony-mode插件方便自己编写 project,但是很是复杂,这话了我很长时间来学习,但不得不说cmake的项目构 建很帮助我认清这个项目的细节.

• rpclib

  rpclib是一个简单而高效的rpc组件,我将它组合在了我的cmake,它提供了异步 和同步两种API也方便我提供两种API接口,我有一部分未完成的细节就是rpc超 时的判断,通过boost::asio的timer可以实现,因为时间问题,作为一个TODO.

优化实现

我一共想到了三个可以优化的地方,实现了其中两个,以及有一些细节优化未处理,在 这篇中阐述一下

• 服务器端内存优化

  由于服务器端的数据量很大,需要考虑到内存管理,这里我联想到了DBMS的 BufferPoolManager,因为作为服务器应该比OS更加清楚自己的内存管理.

  所以我选择了使用页的方式来管理,页选择了512B来简化实现,可以很好地进行 batch操作,提高IO.缺点在于插入和删除,现在没有很好的解决方案.我想到的 最好方法是用B+树来代替BST.也就是数据库里index的实现方式.

  在evict算法方面我选择了lru,首先因为可以实现所有操作的O(1),再者以前写 过类似的代码可以复用.但是,我也考虑过这个算法的劣势,没有很好的适应总 是顺序调用这个条件,应该由更好的算法来适应这个算法.

  我想到了一系列的小优化,比如说总是把前N个页放在BufferPool里面不 evict.这一部分没有实现,但其实也不难,给page增加一个参数即可,但在插入 时需要动态增改,比较麻烦.

  还有一个优化是meta tree,因为每次我要找页时需要fetchPage,对于BST来说 一次NextPage可能要调用多次,所以我选择只把需要的meta data比如说父亲, 左右子树指针存放在内存里,这对于内存读取是很大的优化.

• 网络传输优化

  传输只传一个K/V是很浪费贷款的,所以我选择了使用页的方式来传输.首先可 以复用页的代码.第二可以进行batch传输,增大IO.当然512B可能有点过小,我 们可以增加页大小来进行适应,这在编程改进方面其实非常简单.

• 客户端缓存优化

  客户端缓存优化其实是一个非常大的优化方式,比前两者可能有更大的性能优 化,但是由于时间原因没有实现,这里讲述一下实现流程.我们完全可以将 BufferPoolManager那段代码加以复用,加上以前前N不让移出BufferPool的算 法,可以很大提升速度,编写方式也很是简单.

项目中学习到的东西

• 我在项目学习到了很多知识,比如说代码复用,单元测试来减少总体测试的困难,模 块化,文档编写,缓存相对于超大型数据的优势以及快速学习及应用.这些也是 我在实现我的SimpleDb以及QCTP时遇到的问题.