再议SILT: A Memory-Efficient, High-Performance Key-Value Store

之前的文章谈到了高效key-value 存储系统SILT,谈的不清楚,昨天和付童鞋谈重复数据删除的时候谈到了SILT ,自己再回顾下。

首先要明白,SILT 融合传统的保存key-value 的三种方式:

  • LogStore 以日志结构方式持久化存储key-value 对,内存保留所有key(来了请求就在内存key 中查找)
  • HashStore 将磁盘或者SSD 上的每条key-value 按照内存中HashTable 的顺序排列,内存只保存了key 的部分哈希结构。
  • SortedStore 按照key 的顺序对内存中原来HashTable 索引进行重新组织。SILT 使用的Tire tree。

HashStore 和SortedStore 都具有比较好的内存效率,但只读不可写。

SILT 支持PUT、GET、DELETE 等操作。首先说GET(查找)操作,首先在LogStore 中查找,没有找到再到HashStore、SortedStore 中查找。三个结构中查找速度分别是 200K keys/s、68K keys/s 和28K keys/s。速度非常快了。PUT/DELETE 都可以看成是UPDATE 操作,首先都是写到LogStore里。过程如下图所示:

three

下面详细讲讲update 操作的过程:

  1. 每来一条key-value 的update 的请求key-value 顺序写入到SSD 中,并在内存利用布谷鸟哈希方式记录下key 哈希后的前15 bits ,记做hi(key) 或者tag,和对应key-value 的地址(32bits)。hi(key) 中i 指的是布谷鸟哈希中有i 个哈希函数,对应的是上图LogStore 中In-memeory->Filter 灰色部分,地址对应LogStore 中In-memeory->Index 白色部分。
  2. 当LogStore 填满之后(衡量标准即布谷鸟哈希哈希表满了),将LogStore 中对应SSD 上key-value 对按照哈希表上顺序进行排列,形成按Hash Table 顺序的key-value 存储,这样就节省了LogStore 中地址所占内存。所以上图在HashStore 中In-memory->Index 不再有白色的地址部分。当LogStore CONVERT 到HashStore 时,就会有新的LogStore 接受新的update 请求,被CONVERT 完毕的HashStore 即可删除。
  3. 多个HashStore 通过批量MERGE 的方式将数据保存到磁盘。磁盘上具有原本按照key 顺序排放好的key-value 对,每次MERGE 都将HashStore 中key-value 批量插入到已经排序好了的SortedStore 中。内存中保存的是压缩了的编码索引树(entropy-coded tire)。

HashStore 有人会问存在的价值,因为直接由LogStore MERGE 到SortedStore 也是可以的,但单个LogStore 不可能很大,每生成一个LogStore 就MERGE 到SSD 中势必带来很多IO,如果将LogStore 也积累到一定大小再MERGE 的话,内存就占用比较高了,故在MERGE 前有个HashStore 即减少了内存,又是批处理的一个缓冲。

SortedStore 我的理解在SSD 中也不止一个,不宜大也不宜小。SortedStore 可以是key 前缀的一个分划,该SortedStore 中所有key 都具有相同的前缀。在将HashStore MERGE到StortedStore 时,根据key 的不同前缀插入到不同的SortedStore 中。

还有一个问题就是HashStore 和LogStore 的key 查询(lookup)问题。作为hi(key) 的tag 很短,只有15 bits。当有一个key 查询请求来临的时候,如果之比较对应的tag 的话,岂不是很容易出现冲突?我的理解是这样的,首先出现冲突的概率很小,出现冲突再访问SSD 获取完整的key 带来的开销的概率也会很小。并且对所有新的key 不会产生误判为已经存在。

再议SILT: A Memory-Efficient, High-Performance Key-Value Store》上有11条评论

  1. 论文给出的LogStore算法中并没有清楚说明put方法对于同一个key的处理方法,在内存索引中没有保存最终的key值,所以没有办法搞清楚是同一个key,还是哈希碰撞。同样关于delete方法也没有很好的说明。请问这个你大概了解么?

    • LogStore 在内存中没有保存key,但保存tag,当PUT 或者DELETE 一个KEY 时,首先在内存中查找LogStore 有没有tag 和对应要PUT 或者DELETE 的KEY 具有相同的tag ,如果没有,则外存储器LogStore 一定没有该KEY, 如果有tag 相同,则LogStore 可能有,也可能没有(碰撞了)该KEY,则进一步到外存储器中查找该key。所以图中PUT&DELETE 的箭头是指向内存和外存储器的。

      • 残念……那LogStore在每次put或者delete的时候不是都要检查SSD?那怎么保证写性能呢?论文上虽说有一个valid标志位,但是和github上的源代码一样,都没有给出这具体的实现或者说明,只说是会把删除作为一个特殊的entry写入LogStore,并在后续合并的时候回收。所以我的理解是,使用put进行更新是可能的,并且是作为delete的一个必须操作。那么剩下的问题就是,put究竟怎么做呢?

        • tag 是key 的一个 filter ,两个不同key 具有相同tag 的概率还是比较小的,而且每个key 用了两个tag ,冲突的概率就更小了,可以详见cuckoo hash。使用tag 保存在内存的方法就是将PUT 和DELETE 操作的I/O次数由两次(一次查KEY,一次更新操作)变为一次,查KEY 大部分在内存中使用查tag 代替了

          • 即使只有一个匹配,还是需要进行一次IO确定键值匹配,然后再进行一次IO写入。不过暂时也没有其他同等的方案,只好作罢。

      • 我估计对于已有值的更新和删除,确实需要至少一个SSD读操作,如果是这样的话,不如把LogStore整个放在内存里,反而来得高效一些。

        • 是的,对已经有的key-value UPDATE 和 DELETE 是要将key 和value 读到内存再更新后写入到外存储器,这里key-value 针对的是一次写、多次读的应用,如果UPDATA 和DELETE 比较多是在放在内存中比较合适

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据