[DebnathSL11]Biplob K. Debnath, Sudipta Sengupta, Jin Li: SkimpyStash: RAM space skimpy key-value store on flash-based storage. SIGMOD 2011:25-36
温馨提示：“论文导读”旨在推荐他人发表的本领域相关论文。本论文摘要由厦门大学计算机系林子雨老师(http://www.cs.xmu.edu.cn/linziyu)翻译，如果您对该论文细节感兴趣，可以阅读英文原文（全文PDF版权归出版商所有，因此需要到出版商网站下载该论文PDF）。
【摘要】我们提出了SkimpyStash，一个RAM空间节省的、基于闪存的键值存储，被设计成支持高吞吐量、低延迟的服务器应用。SkimpyStash的显著特性是，它的设计目标是极低的RAM脚印，大约每个键值对只需要1（正负0.5）字节，这比之前的设计要好得多。SkimpyStash在RAM中使用了一个哈希表目录，来索引键值对，这些键值对是以日志结构的方式存储在闪存上。为了克服每个键需要一个闪存指针（比如说4个字节）的RAM开销这个障碍，它把大部分指针从RAM转移到了闪存中，这些指针是用来确定每个键值对的位置。这是通过下面的方法实现的：（1）使用线性链表解决哈希表冲突，也就是说，当有多个键被映射到同一个哈希桶中时，就会组织成一个链表。（2）把链表存储到闪存上，并且在每个哈希桶中存储一个指向链表头部的指针，因此，这样做就会导致每个查询会包含多个闪存读操作。我们进一步采用了两个技术来改进性能：（3）基于双选的负载均衡，用来减少桶尺寸的变化范围（这样可以减少链表的长度和相应的查找时间），（4）压缩过程，可以把桶链表记录连续地压包到闪存页中，从而减少闪存读。平均的桶尺寸时非常关键的设计参数，它对于实现低RAM使用率和低寻找延迟之间的平衡起到非常重要的作用。
【林子雨推荐理由】SkimpyStash是一个基于闪存的键值存储，这个研究方向会有越来越多的论文。