paldb分析

之前在github上看到一个用java写的nosql，fork下来跟过源码。现在把自己的一些理解记下来。
PalDB，是Linkedin开源的一款只读型的 KV 存储数据库，github地址：https://github.com/SeaRise/PalDB‘
从github的主页可以看到，PalDB是以低内存使用和高吞吐量为卖点的。主页的介绍是内存使用为hashset的1/6，吞吐量是LevelDB或RocksDB的5倍。

看过源码后可以发现，其设计思路是

• 在内存只存储必要的用于读写数据的控制信息，不缓存任何数据（默认情况下）来减小内存使用；
• 磁盘数据文件通过特殊的排列结构让用户可以用尽量少的磁盘操作来拿到自己想要的数据，由此来提高吞吐量。

下面讲讲我通过源码了解到的PalDB的结构。
PalDB是只读型的数据库，这就意味着使用PalDB你要先进行写阶段，写入所有数据，写阶段结束后只能读数据，不能再写或修改数据。从写读两个阶段来分析

• 写
  写数据分为预写入和最终写入
  • 预写入，程序每调用一次 writer.put(Object key, Object value) ，PalDB 就进行一次预写入。
    预写入的结果是在磁盘形成<索引文件,数据文件>对。key序列化后byte数组长度相同的key和value会放在同一个索引文件和数据文件里。
    也就是说每个索引文件内的数据都是相同字节长度的key
  • 最终写入，在所有的<key,value>预写入完成后，将所有的临时文件拼接成一个db文件，形成上面我说的那个特殊排列结构。
    其实说白了,那个排列结构就是如下:

      ------------------
      |meta|keys|values|
      ------------------
             |
    ----------------------------------------------
    |key字节长度1|key字节长度2|.....|key字节长度n|
    ----------------------------------------------
        |
    --------------------
    |开放地址表的哈希表|
    --------------------

meta是一些数据库的控制信息，如key数量之类的。
values是紧密排列的value数据
keys是key的集合。key字节长度为第一级索引。相同字节长度的key组成一个开放地址表哈希表，作为第二级索引。
因为字节长度相等，所以槽的大小固定，分配槽的数量默认为1/0.75倍数量，减小哈希冲突。

• 读
  读阶段首先会读出meta，存储在内存中。
  读的流程如下：

        1.key序列化--->
        2.根据字节长度得到该长度key集合的起始地址--->
        3.对key求哈希值得到在key集合内的偏移量--->
        4.一次磁盘操作,拿到key对应的value的offset--->
        5.一次磁盘操作,通过offset拿到value

• 从上面的流程可以看到在不发生hash冲突的情况下，一次读取操作为2次磁盘操作。若存在hash冲突，4步骤要重复多次，磁盘操作数会递增。
• 其次，读阶段通过内存映射文件打开db文件，所以大大减少了磁盘操作数，但是这样也增大了内存使用。