浅析存储系统SILT的基本结构

年前最后一场技巧盛宴 | 1月27日与京东、日记易技巧大年夜咖畅聊智能化运维成长趋势！

SILT存储体系经由过程应用多个根本的键值存储构造，每个针对不合的操作进行响应的优化：(1)键值的更新操作经由过程写竽暌古化的存储构造长进行。(2)大年夜多半键值对存储在存储高效的构造中。固然在存储构造之外的数据很少应用高效的存储索引，然则每个键的平均索引的价值是很低的。(3)SILT可声调剂以应对极端情况，即萌芽在最后、比来的存储构造中。SILT经由过程应用内存的过滤器，许可所有的萌芽在1+（nbcl）flash攫取时光内完成。

SortedStore是一个静态的键值存储构造。其存储按照flash上key的次序进行排序的键值(key, value)，应用基于熵编码的trie树进行索引，平均每个键消费0.4字节进行存储。

SILT的构造和根本存储构造(LogStore, HashStore, SortedStore)如图 1所示。

图1 SILT存储构造

LogStore对于写操作有很高的效力，其重要用来进行PUT和DELETE操作。为了达到很高的体系机能，写数据的结不雅直接添加到flash上log文件的末尾。因为这些记录是按照响应的时光进行排序的，LogStore经由过程内存中的hash表以键和响应在log文件中的偏移对其进行映射。SILT应用cuckoo hash大年夜而在最小内存消费的情况下，达到很高的机能。本文中提出的部分键的cuckoo hash在较低的计算价值和内存消费的情况下，占用93%的空间。比拟其他两个只读的存储构造，其数据存储紧凑，LogStore必须要存储4字节的指针。SILT是以只应用一个LogStore。

SortedStore在flash上按一个指定的次序保护键值对数据，其应用一个异常简洁的情势对索引进行变更。因为对于排序的数据进行单个更新时，其价值是异常高的，是以SILT周期性的将HashStore表的内容归并的到SortedStore中。

LogStore次序讲PUT和DELETE操作写入flash中，大年夜而达到高的写吞吐量。其内存的部分键cuckoo hash索引可以高效的实现键到响应log文件中地位的映射（如图 2所示）。

LogStore应用一个基于cuckoo hash的hash表。其应用两个函数和实现键值到响应的地位的映射。在新的键参加hash表中是，如不雅两个地位中有一个是空的，则将其参加这个空的地位；不然新的键调换两个地位的一个，被调换的键按上述过程进行迭代，直到找到其可选的地位中。

当LogStore中存储饱和之后，LogStore将转换成固定不变的HashStore。HashStore数据以hash表的情势存储在flash上，其不须要内存的索引对记录或数据进行检索。SILT在将其归并到SortedStore之前可以应用多个HashStore。每个HashStore应用一个高效的内存过滤器过滤掉落不存在的键。

图2 LogStore设计筹划

为了使其尽可能的简洁，hash表并不存储全部键，而只是存储键的一个tag。只有当萌芽于响应的tag相符才持续进行后续操作，如许可以实现对不存在的键进行过滤。

固然存储tag可以在必定程度上节约内存的空间，然则同样出现问题：将键移动到其可选的另一个地位须要事先知道其另一个hash值。然则，响应的键值存储在flash中，是以在这种情况下须要进行flash攫取操作。为懂得决这个问题，在响应的hash表中将其可选地位的索引作为tag。例如，如不雅键被放在地位，其另一个hash值将作为其tag存储在地位中，反之亦然。

当LogStore中内容达到饱和时，SILT将其转化查对于内存应用率更高的数据构造。直接对LogStore进行排序，并将其归并到SortedStore须要重写大年夜量的数据。别的，保存大年夜量的LogStore会造成很高的内存消费。是以，为懂得决这个问题，SILT起首将LogStore转化为一个弗成变的HashStore。当HashStore的数量达到指定命值瓯，其被归并到SortedStore中(如图 3所示)。

HashStore经由过程修改索引的构造，对于flash上的(key, value)进行按hash次序进行排序，可以节俭大年夜量的内存。

HashStore的过滤器异常简单，只是将LogStore中hash表中的tag复制，并去掉落响应的指针。

图3 LogStore转换为HashStore

此外，SILT应用Flash上的排序数据(Using Sorted Data on Flash)，将大年夜多半的键值保存在单个的SortedStore，然则其基于熵编码的trie树不许可进行插入和删除。是以，为了将HashStore归并到SortedStore中，SILT必须从新生成SortedStore。是以，SortedStore的构建速度成为SILT整体机能的一个重要的身分。

经由过程排序可以很快完成的构建工作：(1)排序许可新数据的参加：新的数据经由过程排序，按次序归并到已排序的数据中。(2)排序的相干技巧异常成熟：SILT可以应用高度优化的排序体系，如Nsort等

【编辑推荐】

【底层道理】存储数据包的平生（上）
回想十年收集与存储产生了哪些变更？
弗成思议：俄罗斯研究出将数据存储逾100万年永远光盘
通俗易懂系列：分布式文件体系FastDFS详解
1/2 1 2 下一页尾页

　　推荐阅读

　　存储系统为何要用SAS？

年前最后一场技巧盛宴 | 1月27日与京东、日记易技巧大年夜咖畅聊智能化运维成长趋势！一、什么是SAS为保护用>>>详细阅读

本文标题：浅析存储系统SILT的基本结构

地址：http://www.17bianji.com/lsqh/40368.html

1/2 1