A File is Not a File: Understanding the I/O Behavior of Apple Desktop Applications

原文

 

摘要

文章分析了iBench 的I/O 行为,揭示了iBench 和一般文件系统在组织文件、顺序读写、异步与原子性操作等方面的差别。文章为下一代的本地文件系统和基于云的存储系统给出了意见。(这里ramification 不懂什么意思)

引言

分析包括两个Apple 软件套件:iWork(Pages,Numbers 和keynote)和iLife(iPhoto,iTune和iMovie)。为了分析iBench 套件的I/O 行为,建立了一个称为DTrace 的框架并开发了一个基于Apple-script 的应用。得出以下结论:

  1. A file is not a file.用户看来的一个文件实际上也是由多个小文件组成的。
  2. Sequential access is not sequential.顺序访问也不是真正的顺序访问
  3. Auxiliary files dominate.辅助文件占据主导地位
  4. Writes are often forced.写操作是被强迫了,许多程序定期的会使用fsync 刷到磁盘里
  5. Renaming is popular.重命名是十分常见的(一致性)
  6. Multiple threads perform I/O.有些应用会起上百个线程来进行I/O ,所以存储/文件系统应该是可感知线程的,这样才能够合理的分配带宽。
  7. Frameworks influence I/O.开发框架影响I/O ,里面举例了在引用cocoa.h 头文件时会从689个文件中包含112047行代码。

文章的主要贡献:

  1. tracing framework
  2. 解构iBench I/O 行为
  3. 描述了哪些性质上的变化影响了I/O
  4. present the 34 traces from the iBench task suite

Case Study

通过创建一个文档,接着插入15 幅JPEG 图(每个2.5MB)并保存文档为一个Microsoft .doc 文档格式。观察这个过程中十个线程对六类文档进行的I/O 解释了引言中的七个结论。

IBENCH TASK SUITE

这个section 用前面提到的iWork 和iLife 作为workload 进行了iBench 的测试。系统调用的traces 是通过DTrace 收集(The system call traces were gathered using DTrace)。

ANALYSIS OF IBENCH TASKS

一开始就提出了四个问题:

  1. 访问了哪些文件,以及这些文件的大小?
  2. 读和写文件时如何访问的?是顺序的?还是预留空间(预取)的?
  3. 什么是事务性(transactional)属性?写是通过fsck 命令写入还是自动执行的?
  4. 多线程的应用是如何把I/O 分担到各个线程中的?

文章比对了iPhoto, iTunes, iMovie, Pages, Numbers, Keynote 在iBench 测试操作(start,Dup 等)时获取文件类型的个数和比率,以及指定类型文件的个数和比率,这里需要提出的是文章把访问的文件类型分为了multimedia,productivity(像doc,xls等),plist,sqlite,strings,other 六个类型。接着将文件大小分别对文件个数和操作文件总大小取加权。对应的得出四个表:

  1. 访问某类型(六个中一个)文件个数占所有访问类型文件个数的比率
  2. 访问某类型文件总大小占所有访问文件大小的比率
  3. 访问某大小文件(<4KB, <64KB, <1MB, <10MB, >10MB)个数占所有文件个数的比率
  4. 访问某大小文件的总大小占所有文件大小的比率

从1,2 两个图可以看出iPhoto,iTunes 和iMovie 访问multimedia 类型文件的个数和大小都比较大,从文件大小的个数来看,访问<4KB 文件个数占访问所有文件个数的比率都比较高,特别是Pages,Numbers 和Keynote 应用超过60% 访问文件的格式是<4KB 文件。很有意思的是,虽然访问4KB 文件数目很多,但由于这些文件很小所以占所有文件大小的比率很小,我想如果对访问这些文件的耗时进行下分析,可能会对系统性能提高有更好说服力。

下面一部分是关于sequentiality 的分析,我又回头看了下对这些workload 的操作:start 打开对应的应用程序,open 是打开媒体或文档等文件,imp 是将media 等导入到媒体库library 中,new 是创建新的文件并保存。

首先看这些操作读的连续性,所有workload 中start 操作读的连续性超过了75%,可见这些程序在开启的时候大部分I/O 是连续的(这点其实可以拆分来看,虽然连续读操作在容量上占了大部分,但是时间上可能还是随机写所占的时间更长,可以考虑在这方面做工作)。iPhoto 和iTunes 中Imp 操作类似于一个copy 操作,所以连续性较好;有点不理解iTunes 中PlayS (播放10 首歌曲)全部是近似读操作,而PlayM (播放三分钟电影)几乎就没有连续的操作(WHY)。

接着说了预取在除了copy 之外的操作上基本没有什么用!大部分操作也没有过多的采用预取。

Writes typically involve a trade-off between performance and durability.

写操作往往是在性能和持久性之前做了一个权衡。这部分是对sync 命令的分析:

The graph further subdivides the source of the fsync activity into six categories. SQLite indicates that the SQLite database engine is responsible for calling fsync; Archiving indicates an archiving library frequently used when accessing ZIP formats; Pref Sync is the Preferences Synchronize function call from the Cocoa library; writeToFile is the Cocoa call writeToFile with the atomically flag set; and finally, Flush-Fork is the Carbon FSFlushFork routine.

fsync 被具体分类六类:SQLite 是SQLite 数据库调用fsync,archiving 为在访问ZIP 格式文档的时候产生,Pref Sync 是cocoa 库中一个函数调用的fsync ,writeToFile同上,Flush-Fork 是Carbon 库调用的。图看的眼花了~~

中间插一段atomic write(原子性写),即写操作要么失败,回滚到写之前状态,要么成功               – Step W1: Acquire “write lock” on the existing file. (this is usually part of your app semantics, so you might not need any Win32 APIs here)
– Step W2: Copy the old file in a new temporary file. (copy Foo.txt Foo.Tmp.txt)
– Step W3: Apply the writes to the new file (Foo.Tmp.txt).
– Step W4: Flush all the writes (for example those being remaining in the cache manager).
– Step W5: Rename the old file in an Alternate form (ren Foo.txt Foo.Alt.txt)
– Step W6: Rename the new file into the old file (ren Foo.Tmp.txt Foo.txt)
– Step W7: Delete the old Alternate file (del Foo.Alt.txt)
– Step W8: Release “write lock” on the existing file.

这是对应的流程图:

write

这样实际上,为了保证写的原子性,会有大量的重命名操作,可见为保证写的原子性系统I/O付出了较大代价。

再就是多线程和异步,家用电脑为了提高交互性能及减少对用户的延迟,常常采用异步写策略。实验得出的结论却是异步读写在所实验的内容中很少采用,但一旦采用了操作中异步I/O比率占用较高。另外iBench 中任务为了会使用很多线程进行I/O 减少对用户的延时(有些可能是上百个线程)。

相关工作

关键字:研究的对象,学术和工程环境,个人应用程序行为,多媒体应用程序,动态workloads,元数据特征,静态存储,长期存储

讨论和结论

有一段话非常有意思:

The iBench tasks also illustrate that file systems are now being treated as repositories of highly-structured “databases” managed by the applications themselves. In some cases, data is stored in a literal database (e.g., iPhoto uses SQLite), but in most cases, data is organized in complex directory hierarchies or within a single file (e.g., a .doc file is basically a mini-FAT file system).

文件系统现在越来越被当作为应用程序管理的高度结构化“数据库”。在一些情况下,数据保存在字母顺序的数据库中,大部分情况下,数据通过复杂目录层次结构组织起来,或者只是一个文件(比如.doc文件实际上就是一个mini-FAT 文件系统)。

完了完了~~~这篇看的还是太慢!

Design Implications for Enterprise Storage Systems via Multi-Dimensional Trace Analysis

文章结构

1.Introduction 引言

2.Motivation and Background 动机和背景

2.1 need for insight at different layer在不同的层次上了解

2.2 need for multi-dimensional insight 在多方面进行了解

3.Methodolgy 方法

3.1 trace analyzed trace 分析{1000 employees in marketing 500 employees in engining}

3.2 Access unit 进行存储访问的单元{sessions,applications,instances,会话,应用,实例}

3.3 Analyze process 分析过程

            step 1:trace collection trace 收集

            step 2:select layers/define features 选取层次/定义特征

            step 3:compute numerial feature value 计算特征的数值

            step 4:identify access patterns by k-means 通过k-means 的结果得出访问样式

            step 5:Interpret results 解析结果

            step 6:Design implications 给出适应于反馈结果的设计

        3.3.1 Selecting features for each unit<step2> 为每个层次单元选择特征

        3.3.2 Indentifying access patterns via k-means<step4>通过k-means 得出访问的样式

        3.3.3 Interpreting and generalizing the result<step5>解析并概括结果

    4.Analysis result&implicance 分析结果和含义

4.1 Client side access patterns 客户端访问样式
            4.1.1 Sessions 会话<观察结果1-3>
            4.1.2 Applications 应用<观察结果4-6>
        4.2 Server side access patterns 服务器端访问样式
            4.2.1 Files 文件<观察结果7-10>
            4.2.2 Deepest subtrees 最深子树<观察结果11、12>
        4.3 Access pattern evoluation over time 时间变化下访问样式的变化

    5. Architecture Implications 结果在系统结构上的提示

    6. Conclusion and feature work 结论和未来的工作

内容:

文章首先提到了先前文章的trace 分析存在的一些问题:

  • 带有经验主义的偏见
  • 单方面、单维度的分析
  • 分析的层面较为单一(文中从至少从Client session 和Server 等层面分析)

文章的实验样例有两块,一块客户端是拥有1000个雇员的商业市场公司,一块客户是拥有500个雇员的工程人员的公司。下面讲讲文章核心的12 个观察:

  1. <sessions>The sessions with IO sizes greater than 128KB are either read-only or write-only, except for the full-day work sessions. 除了全天的会话,超过128KB 会话的IO都是只读或者只写的。
  2. <sessions>The full-day work, content-viewing, and content-generating sessions all do ≈10MB of IO. 全天工作、内容查看和内容生成会话IO 约为10MB。
  3. <sessions>The number of human-generated sessions and supporting sessions peaks on Monday and decreases steadily to 80% of the peak on Friday. 人为产生的会话在星期一为顶峰,之后下滑,直至星期五下滑到峰值的80。
  4. <applications>The small content viewing application and content update application instances have <4KB total reads per file open and access a few unique files many times. 较小的内容查看程序和内容更新程序实例在每次打开文件的时候都会有<4KB的读并多次访问一些特殊文件。(理解的不知道是否正确)
  5. <applications>We see >50% sequential read and write ratio for the content update applications instances (corporate)and the content viewing applications instances for human generated content (both corporate and engineering). 内容更新程序和查看人为内容的查看程序有超过50%的读或者写。
  6. <applications>Engineering applications with >50% sequential reads and >50% sequential writes are doing code compile tasks. 工程应用有超过50%的顺序读和顺序写是在编译代码。
  7. <files>For files with >70% sequential reads or sequential writes, the repeated read and overwrite ratios are close to zero. 那么>70% 顺序读或者顺序写的文件,再次被读写的概率几乎为0。
  8. <files>In the engineering trace, only the edit code and compile output files have a high % of repeated reads. 在工程客户得出的trace 中,只有编写代码和编译输出文件才会有高比率的重读操作。
  9. <files>Almost all files are active (have opens, IO, and metadata access) for only 1-2 hours over the entire trace period, as indicated by the typical opens/read/write activity of all access patterns. 几乎所有的文件在整个会话(trace 追踪的是会话)周期只有1-2个小时是活跃的。
  10. <files>All files have either all random access or >70% sequential access. 所有文件要么都是随机访问,要么就是超过了70% 的顺序访问。
  11. <deepest subtree(我的理解是只包含叶子节点的目录)>Directories with sequentially accessed files almost always contain randomly accessed files also. 目录中有顺序访问的文件就也会包含随机访问的文件。反过来,一个subtree 却可以只有随机访问的文件。
  12. <deepest subtree>The client cacheable subtrees and temporary subtrees aggregate files with repeated reads or overwrites. 客户端缓存的文件会被反复的读和重写。反复读写往往来自一个客户端。

文中针对这12 个观察结果给出了相应的提示,具体参见原文

Consistency Without Ordering

1 Introduction:

The current state of the art in file-system crash consistency as follews.

At one extreme is a lazy, optimistic approach that writes blocks to disks in any order;

At the other extreme are eager, pessimistic approaches that carefully order disk writes;

2 Background

File system consistency: Metadata/Data/Version

Teches for consistency: File system check/Journaling/Soft updates(检查内存元数据块之间的依赖关系,然后顺序地写入到磁盘)/Copy-on-write

3 Design

里面解释了什么是数据的consistency 觉得挺有道理的:Data consistency provides the guarantee that all the data accessed by a file belongs to that file; it may not be garbage data or belong to another file.

文章的idea 之一就是Backpointers ,就是在所有的目录和文件的后面添加一个指向父节点的指针(这点代价我看来是很小的,因为每次文件、目录访问都是要访问其父节点才会访问孩子节点)。通过其来进行一致性验证,文中提到了:This checking happens both at the file level and the data block level.这里能够进行块一级的校验有点不明白,为什么块一级也可以呢,这个backpointers 不是只在文件一级的么?

还有一个idea 是non-persistent allocation structures。

backpointer

4 Implementation

Backpointer 有三种: Block backpointer{inode, block offset}数据块回溯到所在的inode 的指针,Directory backpointer{directory block backpointer}目录块回溯到所在inode,Backlinks{parent inode}当前inode 回溯到之前的父inode 。(注:这里我有个小疑问,Directory backpointer 实际上就是当前目录的指针,这个在原有的文件系统中不是就有么,用一个黑点’.’代替的么?)。

接下来就讲了在create ,read ,write 等操作的时候这些指针的变化,以及在crash 的时候如何使用backpointer 进行恢复。

Non-persistent allocation structure 是ext2 中bitmaps 和组描述符的替代,不同的是它不在硬盘上持久化存储,而是启动的时候根据backpointers 生成的。(这点和hdfs 以及很多分布式文件系统的元数据管理很类似,1.hdfs 中文件->块的映射是开机时产生的,所以和本文NoFS 同样有冷启动问题。2.hdfs 中目录树结构永久性存储在硬盘上fsImage,但是开机会加载到内存)。

文中提到了,元数据(inode)和数据的扫描都是顺序扫描而不是按目录结构,这样就速度更快。

5 Evaluation评估

这部分分为可靠性测试和性能测试,可靠性测试使用了伪磁盘驱动器进行了错误注入,并查看NoFS 和ext2 文件系统的检测和纠错机制;性能测试比对了NoFS 和ext2、ext3 读写和IOPS 等性能(感觉性能测试接近于ext2 是因为作者就是根据ext2 来改的,做的唯一冗余就是添加了backpointer ,所以结果略差接近于ext2 也是显而易见的,这点感觉是想说明在性能没有损失的前提下可靠性强)。后面关于scan 性能的没怎么看。

6 Discusion

ext2 没有提供强数据一致性,ext3 通过日志记录保证数据一致性,NoFS 提供了强一致性且没有数据上的冗余,性能上也优于ext3 ,唯一的问题就是启动问题。

Revisiting Storage for Smartphones

FAST’12 的 best paper (迄今为止见过最好的实验报告了)

1 引言

手机设备的存储表现十分重要,而且预期其影响会变得更大,因为以下原因:Storage performance on mobile devices is important for end-user experience today, and its impact is expected to grow due to several reasons(下面几点可以大约归为存在问题

首先,新兴的无线技术比如802.11n(600 Mbps 峰值吞吐量)和802.11ad(7 Gbps 峰值吞吐量)为手机设备均有更高网络吞吐量提供了潜能。First, emerging wireless
technologies such as 802.11n (600 Mbps peak throughput) and 802.11ad (or “60 GHz”, 7 Gbps peak throughput) offer the potential for significantly higher network throughput to mobile devices.(全文测试的一个重点也是测试网络环境下FLASH 的I/O 性能。)

其次,从感观上网络吞吐量增加了,而延时却没有改善。(言下之意就是改善latency 的工作—存储,没有做好。)Second, while network throughput is increasing phenomenally, latency is not.

第三,手机设备越来越被当做电脑来使用,运行了一些之前不能想象的高性能的任务。Third, mobile devices are increasingly being used as the primary computing device, running more performance intensive tasks than previously imagined.

本文工作

  • 详细分析了基于Android 系统的智能手机和flash 存储的I/O 表现 we present a detailed analysis of the I/Obehavior of mobile applications on Android-based smartphones and flash storage drives.
  • 关注的主要应用有:Google Maps, Facebook 和 email . focus on popular applications used by the majority of mobile users, such as, web browsing, app install, Google Maps, Facebook, and email.
  • 提出了pilot solution(试点方案/试点方法)来克服存在的一些问题

 

下面是基于分析和设计工作得出一些观察结果:Through our analysisand design we make several observations

  • 存储影响应用的性能 Storage affects application performance
  • SD 卡标称的速度等级没有实质效果 Speed class considered irrelevant
  • 存储介质越慢越消耗CPU  Slower storage consumes more CPU
  • 对应用的了解有助于高效的解决方法 Application knowledge ensues efficient solutions

 

本文的主要贡献有(和工作有所重叠):

  • 第一,我们介绍了我们定制测量框架,包括自定义安装的固件和基于 Android 设备的软件,用于进行深入地 I/O 分析。 First, we describe our measurement infrastructure that enables custom setup of the firmware and software stack on Android devices to perform in-depth I/O analysis(实验测试软件安装
  • 第二,我们给出了在实际Android 智能机和flash 设备上存储性能的详细分析。Second, we present a detailed analysis of storage performance on real Android smartphones and flash devices;(实验结果,提出问题)
  • 第三,我们提出评估了一种试点解决方法来Third, we propose and evaluate pilot solutions to address the performance issues on mobile devices.

 

2 手机设备综述

Figure 2:是Android 手机的结构图。

archtecture

Figure 3则是Google Nexus One 手机内部NAND flash 和外部(插卡)flash 文件系统存储情况。 Figure 3 shows the internal raw NAND and external flash storage on the Google Nexus One phone.

internalandexternal

应用的数据和配置文件既可以装在内部存储设备,也可以装在外部的SD 卡中。Android 使用了SQLite 数据库作为存储结构化数据的主要方法。(好处就是节省资源) Applications can store configuration and data on the device’s internal storage as well as on the external SD card. Android uses SQLite database as the primary means for storage of structured data.

3 Android 测量工具安装

  • Android Debug Bridge (ADB) [1] on a Linux machine running Ubuntu 10.10

  • 需要通过USB 接口进行反向限制的一些工具,能够格式化存储设备等功能的设备。(最后选用 both CyanogenMod and AOSP distributions)custom partition the storage, and access to a wider range of system tools and Linux utilities for development
  • 为了能够比较不同存储设备的性能,我们改变了Android 系统的init 过程来挂载内部的分区或者是外部的存储设备。compare and contrast application performance on different storage devices. In order to observe and measure all I/O activity, we change Android’s init process to mount the different internal partitions on the external storage
  • 为了比较在wifi 环境下的性能,使用笔记本做了一个ap 搭建了个web 服务。并也使用了USB 连接进行比较
  • SD 卡读写测试(结果如下)

Table 3 是八款SD 卡的读写性能比较,左边的是在工作站的读卡器的速度,右边是在手机上的速度,W/R代表写和读,q/n 代表顺序(sequence)和随机(random)。数据量为100 M顺序读写,随机I/O 大小为4 KB。

eightflash

  • 修改microSD 卡驱动器,使得可以读取/proc 中的“buyness”信息;写了一个后台监控软件定期读取proc 信息;利用blktrace 工具收集块一级的traces。
  • 安装MonkeyRunner 。

完成这些工作后,下面是实验的流程:

  1. 开启监控器,收集资源使用情况并标记PID。First, we start the Monitor tool to collect resource utilization information and note its PID.
  2. 使用MonkeyRunner 启动应用程序。收集触屏信息。Second, we start the application under test using MonkeyRunner which. defines“button actions”to emulate pressing of various keys on the device’s touchscreen.
  3. 当交互操作(按键)进行的时候,记录下CPU 使用信息以定义什么时候交互结束。Third, while the various button actions are being performed. CPU usage is tracked in order to automatically determine the end of an interactive action.
  4. 当一系列的行为完成后,执行必要的清理工作然后返回到Home。 Fourth, once the sequence of actions is completed, we perform necessary cleanup actions and return to the default home screen.
  5. 停止监控器,将资源使用信息返回到主机电脑。Fifth, the Monitor tool is stopped and the resource usage data is dumped to the host computer.

介绍几个 benchmark

  • WebBench 是作者自己写的计量web 浏览性能的程序。
  • AppInstall 安装Google Android Market 十个软件
  • AppLaunch 使用MonkeyRunner 启动
  • Facebook
  • Google Maps
  • Email
  • RLBench 使用SQL 请求对Android SQLite 的综合测试
  • Pulse News  a popular reader app that fetches news articles from a number of websites and stores them locally
  • Background

4 性能评估

这个section 包括四个部分:一、比较internal flash 和SD 卡;二、应用启动时间;三、并发应用;四、CPU 消耗。

首先是internal flash 和SD 卡差距的比较。通过wifi 得到的一些runtime数据(括号里面是Kingston 的数据,这里百分比应该是最好情况和最差情况的之差的比例),The difference between the best and worst case performance varies from 195% (225%) for AppInstall, 80% (1670%) for email, 60% (660%) for Maps, 80% (575%) for Facebook, 130% (2210%) for RLBench, and 97% (168%) for Pulse. 文中分析并实验证实了这个差距是以为对SQLite 的写是随机写,所以性能差距较大,而Kingston 随机写性能表现最差。

第二个启动时间,通过把所有的SD 卡中的应用内容读到RAMdisk 中,进行比较启动时间,差距不大。(我认为可能这里存储并不是瓶颈)

第三个不知所云,里面提到了一个很有意思的是在两个小时中,从网上下载的数据为1.6 MB,但是写入到flash 的量却是30 MB(放大系数为20)。这让我想到了前篇文章 SILT 中提到的读写放大。

第四个是CPU 消耗,发现flash I/O 性能越差,CPU 消耗也越大。

5 解决方案

基于以上分析实验提出了几个解决方法:

  1. 使用更好的存储介质(比如实验中的PCM)
  2. 固件和设备驱动器能够有效地利用好最新的存储设备
  3. 应用软件层次有效地利用存储接口

实验使用了不同的SD 作为baseline(A)、RAID over SD(B)、使用log-structure File System,SQLite on Nilfs2(C)、修改SQLite 接口selective sync(D 这个还不明白)、PCM 相变存储器(E)、All in RAM(F)比较图

compare

 

总算写完了,整篇文章就像一提出问题,分析问题和解决问题的实验报告,工作量比较大,有些内容比较适合于做教科书的一些规则,感觉这也是作为best rewarded paper 的重要原因—有一定理论上的概括。以后写这样的笔记尽量短些吧,太耗时了。

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 次方大小顺序排列即可)