再议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 都具有比较好的内存效率,但只读不可写。

继续阅读

Dynamo: Amazon’s highly available key-value store

原文  中文翻译  参考:Kai – An Open Source Implementation of Amazon’s Dynamo

本文一直为分布式key-value 存储系统以及分布式存储的业内人士所推崇,个人觉得有两个原因:

  1. 分布式key-value 存储近年发展迅速。Dynamo 更是集成了近些年最新的技术如:DHT(分布式哈希表)、consistent hashing(一致性哈希)、多版本、副本策略和Merkle tree 等。
  2. 文章从设计、实施者的角度分析了分布式key-value 存储在实践中的问题和解决方法,并总结了Dynamo 在实现、配置等方面的经验与教训,对后来者非常有借鉴意义。

继续阅读

Scalable Consistency in Scatter

原文地址

  • 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 ,但我觉得这个应该同时进行读写操作才能说明问题,如果在现实情况中组操作严重干扰了用户的正常读写的话,试验中的高性能和可用性就不好说了。

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

论文地址  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存储方式。下图是三者的比较

threecompare

  • 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 的偏移指针。

logstore

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

hashstore

  • 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 编码。

formtire

 

entropycoding

存在的问题就是每次查找都要解压整个字典树,当字典树大了时候非常耗时,可以采用分块(bucket)的方法。文中举了一个例子,一个216  大小的key-value 对,可以分为210 个块,每个块存储26 个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 次方大小顺序排列即可)