从fsck 看数据一致性Consistency

昨晚和fumin 聊到数据一致性的时候,他问及什么是数据一致性Consistency,我只能机械的背出数据一致性的概念:所访问的数据是所期望的数据而不是其他数据或者垃圾数据。上午重新翻了《操作系统设计与实现》文件系统这一章,谈到了fsck 所进行的操作,fsck 是类UNIX 操作系统用于数据一致性检查的工具,它进行了以下工作:

首先数据块使用情况:建立两个表,一个是遍历所有所有inode 节点,记录块使用情况,数据块每使用一次在其位置上加一,则n 表示该数据块被使用n 次,0表示没有在使用;二是遍历空闲块链表或者blockmaps 记录所有空闲块的表,1 表示空闲,0 表示不空闲,那么正常情况应如下:

0011001001001 使用中的块

1100110110110 空闲块

所有的块要么不是在使用中,要么就在空闲块中,且只使用一次。数据不一致的情况之一有:

0011001001001 使用中的块

0100110110110 空闲块

第一个块即不在使用中的块,也不再空闲块中,这就浪费了存储空间,修正的方法就是把其添加到空闲块链表或者修改blockmaps。另一种情况是:

0011001001001 使用中的块

2100110110110 空闲块

也就是第一块在空闲块链表中记录了两次(不可能在blockmaps 里面出现这样的情况)。这种情况比较简单,将空闲块链表中多余块删除,更严重的情况:

1011001001001 使用中的块(情况A)

1100110110110 空闲块

2011001001001 使用中的块(情况B)

0100110110110 空闲块

情况A 第一个数据块即在空闲块表中也在使用块表中,如果将这个空闲块分配给新的数据,那么以前的数据就完全被覆盖且无法恢复了,为了避免这种情况的发生,应该将此空闲块从空闲块中删除。情况B 是一个数据块被两个文件所使用,可以复制该数据块内容到新的数据块,并修改对应的一个inode 该块数据地址到新的复制块的地址。

接着在检查完块使用情况后检查链接,每个文件的inode 上会有一个计数器,在文件创建的时候,计数器设置为1,每增加一个该文件的硬链接计数器加1,一般情况下只有该文件的计数器为1的时候才能够删除。在fsck 的过程中会统计每个文件的硬链接的个数,和对应文件的计数器进行比较,可能出现以下几种不一致的情况:

1、硬链接数目小于计数器值,这样即使所有硬链接都删除了,该文件也不能删除

2、硬链接数目大于计数器值,问题较严重,以后可能导致硬链接指向了被重新分配内容的区域(发生了不一致性)。

两种通过实际的硬链接数进行修改为正确的值即可。

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

HDFS—configuration

org.apache.hadoop.conf      提供访问配置文件的借口

配置文件是 name/value 的XML 文件,通常每一个元素都是以<code>String</code> 或者 {@link Path} 的方式给出的,如果是以前者的方式给出的,则会配合类路径来检查这个文件,如果是后者方式给出的,则直接检查对应的文件,比如有下面的定义:

 1: <property>
 2:     <name>basedir</name>
 3:     <value>/user/{user.name}</value>
 4: </property>
 5:
 6: <property>
 7:     <name>tempdir</name>
 8:     <value>{basedir}/tmp</value>
 9: </property>

当有conf.get(“tempdir”) 这样的调用时,{basedir} 被解析为配置的另一个属性,同样{user.name}最终也被解析为系统中具有这个名称的值。