原文

摘要

文章分析了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.

这是对应的流程图：

这样实际上，为了保证写的原子性，会有大量的重命名操作，可见为保证写的原子性系统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 文件系统）。

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

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。

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 ，唯一的问题就是启动问题。

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 手机的结构图。

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.

应用的数据和配置文件既可以装在内部存储设备，也可以装在外部的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。

• 修改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）比较图

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