之前的文章谈到了高效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 都具有比较好的内存效率，但只读不可写。

继续阅读 →

原文地址

• idea：可扩展、一致性的分布式key-value 存储（evaluation of Scatter, a scalable and consistent distributed key-value storage system）
• key insight：基于DHT 的一致性组
• DHT 功能简介：传统DHT 中，应用数据和节点ID 都哈希为键值key，数值保存在先于或紧接着键值key 的那个节点
• 为什么会发生一致性问题：1.Assignment violation 节点加入或者离开时对keyID 范围的声明的重叠。2.节点加入和离开对临近指针的影响。

Scatter Design

goal：一致性，可扩展性，自适应性

方法：用组来代替单个节点，RSM 基于paxos 一致性算法，组内使用一致性协议维持内部一致性，但是如静态指定组会存在一些问题：

1. 当大量nodes 离开或者加入会使得该组失效
2. 健壮性、可扩展性问题
3. 当组内节点增多，一致性算法性能下降
4. 热点问题

因此Scatter 允许多组操作：

1. split       组一分为二
2. merge   两临近组合二为一
3. migrate 将组员从一组移动到另一组
4. repartition 临近两组交换键值空间

强一致性在拓扑结构不是原子变化的情况下是很难保证的，因此文章引出“自创”的nested consensus 老保证原子性，但实际上nested consensus 就是组内的paxos 算法保证强一致性，组间两阶段提交保证弱一致性。

接着文章从发起方coordinator group，参与方participant group 解释了nested consensus 过程，实际上就是两阶段提交，文章也指出这样的交互过程需要大量的广播和消息，可以作为future work 进行改进。

整个Scatter 系统对外提供存储服务，每个组中会利用paxos 算法选举出一个master，组间交互只通过master，而具体数据时存在组内所有成员，存储对应数据的称为primary。文章谈到了所做的一些性能优化，lease，diskless paxos（信息不用存盘）、relaxed reads 等。

最后进行了测试并与openDHT 比较了consistency。

个人体会：

文章主要是提出了可扩展和一致性的key-value 存储系统，最大的创新在于把传统DHT 中单个节点的方法改成了一个组，节点的加入和退出就限制在了组内，对外这个组的状态和功能还是不变的。为了满足可扩展性，组可以进行分裂合并操作，通过形式上说明和实验组操作的OPs/sec、延时说明这个方法是可行、高效的。一致性是通过paxos 算法和两阶段提交实现，也不能说有新意。文章通过与openDHT 的比较，说明Scatter 不损失性能和可用性的情况下，一致性上比openDHT要好。但我有个小问题，组操作如果是手动的话就谈不上adaptive 了，如果是自动的话，这种组操作在节点加入和离开的时候频不频繁，虽然文章也给出了组操作的thoughput 和latency ，但我觉得这个应该同时进行读写操作才能说明问题，如果在现实情况中组操作严重干扰了用户的正常读写的话，试验中的高性能和可用性就不好说了。

论文地址  paper address (recommened by 煲仔)

This paper is from SOSP 2011, and introduces a Memory-Efficient, High-Performance key-value store system SILT (Small Index Large Table) . It requires only 0.7 bytes of DRAM per entry and retrieves key/value pairs using on average 1.01 flash reads each.

这篇文章来自于会议SOSP 2011，它介绍了一个节省内存且高性能的key-value 存储系统SILT。每个项平均在内存中只需要0.7 个bytes，检索每个key-value 对仅需要1.01 flash读放大。（这里的  读放大=应用程序所需数据/从磁盘或者SSD中读取的数据。文章假设以SSD 为存储介质，所以尽量减小读写放大。）

SILT is based on the three common key-value stores: LogStore, HashStore and SortedStore, while SILT combines their advantages and reduces the size of the keys as much as possible.

SILT 是基于三个普通的key-value 存储：LogStore，HashStore 和SortedStore，然而SILT 结合了他们的优点，并使得keys 大小被压缩到最小，在讲述SILT key-value操作过程同时，简述下这三个key-value存储方式。下图是三者的比较

• LogStore 是一个简单的将key-value 以日志方式按时间顺序保存，在查询时候按时间由新到旧的方式进行查询，直至查询到最新的key-value 进行返回，其他操作类似。

SILT 对所有的keys 进行cuckoo hash 处理（采用布谷鸟哈希是为了解决哈希冲突问题），对应的每个key 都有两个哈希函数，那么每个key 可以有两个候选的位置，如果两个位置都空的，那么任选一个位置保存，如果只有一个位置放在该位置，如果两个位置都是空的，则踢出去一个哈希值，让其去找这个被踢出key哈希的另一个哈希结果进行存放。如果没有空余的位置了，或者这个被踢出（置换）的过程反复次数过长，则认为这个Logstore 保存满了，则使用新的Logstore 进行保存。

为了节省内存，哈希表保存的不是整个key，而是key 的一部分—tag。当要进行查询的时候比对key 生成的tag 即可。而且tag 在LogStore 是唯一标识的。另外引用tag 带来的问题是当发生位置替换（被踢出）的时候，只有知道了整个key 才能得出对应的两个位置，这样被提出的tag 才能找到它的下家位置，文中是这样解释的：

To solve this costly displacement problem, our partial-key cuckoo hashing algorithm stores the index of the alternative bucket as the tag; in other words, partial-key cuckoo hashing uses the tag to reduce flash reads for non-existent key lookups as well as to indicate an alternative bucket index to perform cuckoo displacement without any flash reads.

为了解决位置置换耗费大的问题，部分键的cuckoo hashing 算法保存另一个哈希结果作为这个哈希位置的标签（tag）；换句话说，部分键的cuckoo hashing 算法使用标签减少了对键不存在的flash 读以及位置置换时不再需要对其进行flash 读操作。

在SILT 中每个key 为 160 bits 的哈希值，使用其中15 bits 作为tag，所以哈希表的每条包括15 bits 的tag ，一个bit 的可用位，32 bits 的偏移指针。

• HashStore 对flash 中保存的完整key 使用tag 顺序进行排序（K2,K4,K1,K3），这样key 原来是类似于LogStore 按时间的顺序排序的（K1, K2, K3, K4）。

• SortedStore 是一个静态（一旦产生就补修改）的key-value 存储，通过key 的顺序保存key-value 对，由一个称为Entropy-coded tire 作为索引，这个索引被尽可能的压缩，每个key 平均在索引中只占用0.4 bytes 。

这个Entropy 的索引是按照下图（Figure 5和6）顺序生成的：

1. 通过每个key（文中用的是key，但我认为是tag，因为tag 已经就可以足够构造这个树了，key 又要在SSD 上读取）的最短不同前缀（shortest unique prefixes）构造了字典树
2. 树的每个非叶子节点进行统计，格式为a/b ，a 为该节点左边叶子个数，b 为右边叶子个数，这里有两个规律，一个非叶子节点f 的 a/b 是其左边/右边所有非叶子节点a 与b 的总和（如果这个叶子f 有非叶子节点的话），另一个规律是所有最后一级的非叶子节点a/b形式都是1/1。这些规律为编码提供了方便
3. 对树进行编码，（b）的编码规律为先根节点，再左右节点依次遍历，记录下所有节点的左节点数字得到（b）。
4. （c）是通过（b）的Entropy coding 得到的，Entropy coding 是无损编码的总称，比如可以是Huffman 编码。

存在的问题就是每次查找都要解压整个字典树，当字典树大了时候非常耗时，可以采用分块（bucket）的方法。文中举了一个例子，一个2¹⁶  大小的key-value 对，可以分为2¹⁰ 个块，每个块存储2⁶ 个key-value。这样解压的代价就小很多。

I think ‘batch’ and ‘compression’ are the main ideas of this paper.  

总结全文，我认为“批处理”和“压缩”是全文的主要思想，上面只是对key-value 在内存中的压缩进行了小结。所有key-value 操作被批量的进行hash、排序，批量的写入到flash。压缩是对key 排序结果的字典树进行最大限度的压缩。但是还是有两个问题：

Two Question：

1. If each item in the tire includes the offset of the key？字典树的每个叶子节点中包含了key-value 的指针吗？如果没有包含指针怎么读取？

2. How the items are partitioned into several buckets based on the first k bits  of their key to bound the lookup time?文中提到了最后树如果太大，查询时间会很长，使用key的前k 个bits 将字典树分成 2 的k 次方块，那么在查询的时候怎么能找到对应的是哪个树呢？（现在想想可以按这2的k 次方大小顺序排列即可）