sundayhut's Blog

这是一篇论文的阅读笔记，这个论文讲的是测试Android系统的一个工具链

文章链接

AndroStep consists of workload generator:Mobibench   and workload analyzer: MOST

我们关注的是MOST

3.2 MOST:Moblie Storage Analyzer

MOST consist of (i)a modified Linux kernel that maintins processes and file-related information for IOs;(ii)a block analyzer that enables identification of a file for a given block,(iii)blktrace utility

the information nedds to be collected from different layer.MOST collects the IOtrace at the block device driver level to deduces the file information and then it process information for each respective block.MOST addresses three reverse-mapping issue:LBA-to-file,LBA-to-process and retrospective LBA mapping

1.LBA-to-file即使用debugfs实现

2.LBA-to-process ：create a process-to-block mapping table.the entry of the table is <LBA,process id>.When the IO scheduler inserts the IO request into the queue,MOST inserts the<LBA,process id>information into the process-to-block mapping table.当后期给出一个LBA，可以通过这个table可以用重新获得process id

3.retrospectve LBA mapping.In Android,many files are shortlives and are created and rapidly delete by SQLite.They are fsync()ed to NAND storage.We need file information for a given LBA when a trace is recored not when posthumously analyzed.但MOST准备分析一个LBA时，这个文件也许都已经被删掉了。怎么解决这个问题呢：MOST 创建了一个file-to-block的表，表的每一项是<LBA,FILE>.当IO调度器plugs in the LBA to the 调度队列，MOST向表中插入一项<LBA,FILE>，之后通过给定的LBA再在这个表里查需要的信息。为了减小表的大小。只为temporary file向表中插入信息。

Mobile Storage Analyzer的输出：

IO完成时间。

读or写

IO大小和扇区号

进程编号、进程名字

Block类型，元数据块、日志块or数据块

数据块存放文件的名字

chp1

1.实际投入是时间乘以效率

2.如何让brain满载：make full use of dark time。效率高了，可以做到一个非你本专业专业领域的卓越，roller-skating  badmintion whatever

3.process switching costs large amount of time.Set only two goals a day

4.Do not tell youself you don't have interents for excuse. The key is whether you have the fuel to keep your intreset burning.你的性格里是否有维持兴趣火种不停燃烧的燃料，而不是风一吹、水一泼就灭了---我觉得区别他们呢和其他人的，并不是他们超过常人的兴趣，而是他们拥有超人的毅力。。maybe it's right

5.Don't be the donkey which starving to die between the haymow.学A还是学B，纠结之中时间就过了

6.The knowledge you have don't depend on how many points you can remember,but depend on whether you can get the point in your brain when you want to use it.知识存放于大脑中，关键是在恰当的时候能够想起来去使用。

7.We need clue to help us get the knowledge in our brain.So try every possible means to indurate the clue.把记忆的场景连同环境、味道、声音都于记忆的内容编码在一起。这样可以使记忆的调取有坚固的线索

8.Create oportunite to review.eg. discuss with someone else、file your notes、tell someone else the point you learned. 通过讲述、笔记、整理笔记的方式让自己不断的复习

9.对重要的事情采取主动关注，即惦念着这件事情，杂乱的事情采取被动关注，即它trouble到你时再去处理，如收拾桌子、衣柜、收衣服。。quite like me

10.When you learn something new.ask yourself three question； 本质是什么、第一原则是什么、知识结构式怎样的。

11.often ask these question when studying and thinking :你的问题到底是什么；到现在为止的收获；将自己的东西讲给别人听；讲给一个完全不懂得外行听；反省自己的思维过程，看自己思维那个环节有漏洞；养成反驳自己的习惯

12.重视提前积累的强大力量。if you can make your plan one year earlier, 你可以有多一年的时间来为你的目标来准备、积累

13.思维的东西是跨学科的，you can use it in any time, 用好了可以事半功倍

14.知识结构。抓住不变量，抓住本质的知识，如在我们这行，硬件体系结构式本质，操作系统的重要实现机制是本质，数据结构、经典算法时不变的

chp2

1. Why human being always can't be satisfied with what they already have? 在生物的进化史中，你必须于残酷的优胜劣汰的环境做斗阵。经过漫长的塞选和淘汰，如今剩下来的基因都是“挣钱基因”。从数学角度来说，自然选择过程试图优化的目标函数是“繁衍概率”，而不是人们都想追求的“幸福感”

2.用理性的声音to reason the primitive man in your mind

3.A few lines of reasoning can change the way we see the world.人类强大的力量之一：归纳和推理，从别人的错误中总结经验

4.Nowadays we live in a city interpersonal relationship is often change. the costy of the fialure of social intercourse is nearly zero.勇敢地迈出第一步。

5.我们对于很多事情的决策判断都刻画在天性里面，天性往往会让我进入选择的困境。We are primitive man liveing in a information society

6.大脑中有一个思维的钢印，terrible

7.能够改变习惯的，依靠的不是自制力、而是知识

8.我不想与我不能。告诉自己亿万年进化得到的麻木的大脑不要“自利归因”

9.困难的路越走越容易，容易的道路越走越难。 do not agree totally.live in the moment is what i always believe.

本文章为A New Metadata Update Method for Fast Recovery of SSD Cache的解读

1.SSD做缓存时元数据更新传统方法

在对SSD进行元数据更新操作时，最为保险的做法是“标记-写入-更新”

“标记”的作用是标记SSD正在写入的位置，标记作用是为了防止意外断电等特殊情况。比如在发生意外断电时再开机后，SSD中元数据被标记的部分就表示该部分的数据是更新操作未完成的操作。故这部分数据无效。

“写入”操作就是进行数据写入操作。

“更新”操作时写完后进行元数据的更新，比如将clean置位dirty。

“标记-写入-更新”三部曲虽然保险，即在断电时可以判断到底哪些数据时无效数据，但是其存在一个致命的缺点，那就是写操作要进行三次写SSD。影响了写的性能

2.Flashcache中元数据更新方法

在flashcache的实现中，将传统保险的“标记-写入-更新”这三步操作简化为“写入-更新”两部。省略第一步可以加快写操作。但是带来了一个很严重的问题。即意外断电时，存在部分写入的数据未更新，则有一些标记为clean的数据可能是还未来得及进行ditry置位操作。则SSD元数据记录中的为标记为clean的元数据对应的块全都不能使用。则cache中有效的块只有dirty状态的块。这就导致cache中大量数据的浪费，降低了性能。

3.论文思想

那么怎么解决这个问题呢？

本论文就提出一种基于“标记-写入-更新”的改进方法，核心思想主要是将第三部更新操作不单独进行，也就是并非写入完成后就立马更新元数据，而是在对该页的其他块做“标记”时，顺便进行整个块的更新。

3.1piggybacking ACK

我们知道SSD的写入单元是页，每页有多个元数据项，假设某页第一个元数据项对应的数据要进行写操作，那么我首先要标记该元数据，表明我准备进行写操作，那么在标记这个元数据时要写整个页，所以，我可以把内存中显示“更新”完成的元数据页同步到SSD中。那么相当于“更新”和“标记”合并在一起完成，不必进行三次写入操作。由于SSD上的元数据的“更新”操作不是及时的，故论文里把这个方法叫做Lazy-Update Following an Update-Write。

为了实现上述思想，每个元数据项有个标记为，该位表示SSD数据正在被更新。下面以一个实际操作为例，说明该流程。现要对一个page进行写操作。

step1：进行RAM和SSD上元数据置1操作，表明元数据对应数据进行写操作，即图中1,2

step2：进行SSD数据的写操作，即图中3

step3：对RAM的元数据进行及时更新，即图中4，由1置位0，表明当前是有用数据

最后图中箭头的piggybacking是指更新SSD中的元数据，即由当SSD元数据所在的page要进行别的块的step1操作时，顺带更新。

3.1总结：

思想基于“标记-写-更新”这一元数据处理的策略，将同一page不同元数据的“更新”和“标记”在写元数据页时同时完成。通过这种方式将“标记-写-更新”的三次写SSD操作下降至两次。但与此同时，有了“正在更新”的标记，使得系统意外断电后重启时，SSD中clean标记位的数据就成了可用数据，在这点上与flashcache实现相比，很大程度上提高了意外断电时缓存数据的可用率

3.2滑动窗口思想

在SSD中最后一步的“更新”操作虽然是延后的，但是由于写操作具有局部性，所以说，元数据页被写的频率是很高的，也就是说基本能及时将“更新”标记从内存中同步。但是也要考虑极端情况，该情况如下：

假设SSD中每个元数据页存放了320个元数据项，在意外断电发生时，每个元数据页中都有1个元数据项没有及时地跟内存中的元数据同步，也就是还未进行最后一步的元数据“更新”操作，那么这些元数据对应的数据就为无效数据，若缓存SSD的总容量为320G，则重新启动时SSD缓存中就有1G的内容是无效的。为了进一步减少无效数据的大小，论文提出了另一种机制：滑动窗口

这个滑动窗口里记录了整个SSD中写操作的最后一步“更新”还未来得及与内存同步的元数据项，当窗口中元数据项的个数达到了窗口大小设定的阈值时，就回进行强制写回操作。

之所以叫做滑动窗口，是因为采取了类似于TCP的滑动窗口方法，这个窗口只有当最先一个元数据被确定做完了“更新”操作后，才会滑动。另外这个窗口在每次进行SSD元数据页的更新时都会写入到SSD，滑动窗口是带有时间戳标志的。

3.2总结

滑动窗口从全局上对SSD上未做更新的元数据进行了把控，在3.1的基础上进一步增大了意外断电重启的缓存中可用数据的量。

但关于这一部分我还没有很看懂，关于为什么要滑动窗口，为什么滑动窗口还要有时间戳都没有理解。欢迎大家进行讨论

该论文网址：

http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=06665346