之前的文章谈到了高效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里。过程如下图所示：

下面详细讲讲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 不会产生误判为已经存在。