请选择 进入手机版 | 继续访问电脑版

SSD 中GC源码解析

2017-7-8 01:57 193 0
0
摘要: 垃圾回收(gc)是 SSD 中很重要的一个过程,在 ssdmodel 模块中进行垃圾回收,是在ssd_activate_elem()函数中触发的。每次有请求过来时,都会进行垃圾回收的判断,当满足一定的要求时就会进行垃圾回收,垃圾回收结束之 ...

垃圾回收(gc)是 SSD 中很重要的一个过程,在 ssdmodel 模块中进行垃圾回收,是在 ssd_activate_elem() 函数中触发的。每次有请求过来时,都会进行垃圾回收的判断,当满足一定的要求时就会进行垃圾回收,垃圾回收结束之后,会退出该函数,并不会继续处理进来的请求,请求会放在下一次来完成,如果没有达到垃圾回收的条件,那么会响应该请求。整个流程如下:

这是一个简化的流程图,实际过程比这个较为复杂。

media is busy? 是通过 elem->media 是否等于 true 来判断的。

cleanning is background? 是属于 SSD 的一个属性,在配置文件中进行设置。是否允许后台进行垃圾回收主要的区别在于,如果允许后台垃圾回收,不管该 element 上有没有请求都会触发程序去检查是否需要垃圾回收,然后决定是否回收。如果不允许后台垃圾回收,只有当该 element 上有请求的时候才会触发程序去进行垃圾回收的检查。

reqs_waiting 是通过 elem->metadata.reqs_waiting 来获得的,表示该 elements 是否有请求正在等待响应。

关于是否满足垃圾回收的条件,在实际的程序处理中是根据 SSD 的 copy_back (how active pages are assigned in an element) 属性来分别进行判断的。所以上面的图可以进行如下的细分。

SSD后台GC的操作与普通GC操作有哪些区别

普通 GC 是指当一个写请求到来时,如果这个 element 上没有空闲的 page 了或者空闲的 page 到达了预先设定的下限,那么就会触发相应的 GC 操作等 GC 结束后才会进行写入操作。很明显这是会影响响应时间的。

后台 GC 是指当 SSD 处于空闲状态时,来检查 SSD 是否是需要进行 GC,如果不需要就不用进行 GC 了,如果要的话就进行 GC,由于这个时候 SSD 是处于空闲状态,这个时候进行 GC 操作就不会影响 SSD 的响应时间了。

在 ssdmodel 中,普通 GC 与后台 GC 大致有两点不同:(1)普通 GC 只有在这个 element 上有请求在排队时,才会检查是否要去GC。对于后台 GC 不管这个 element 有没有请求都会去检查是否要 GC 。(2)普通 GC 只有当请求来的时候才会去触发,也就是说只有当需要写且没有地方写的时候才会触发GC,如果是后台 GC 的话,那么完成一次写请求之后,都会去检查这次的写是不是把SSD写“满”了,如果是就触发 GC,而不用等下一个写来了且写不下去了才触发 GC。

代码实现

前面介绍了 GC 操作是在 ssd_activate_elem(ssd_t *currdisk, int elem_num) 函数中进行的,进入该函数后首先是判断该 element 是否处于 busy 状态,如果是的话就直接返回了。

进入到 ssd_activate_elem() 中有两种途径,第一种是在 ssd_media_access_request_element() 这个函数,这个函数主要是将一个请求分成几个以 page 为大小的小请求,然后将该请求加入到相应的 element 的队列中,然后调用 ssd_activate_elem() 去执行这个请求。

第二种途径是在 ssd_access_complete_element() 这个函数中,每完成一个 element 上的请求时都会都会在这个函数中调用了 ssd_activate_elem()

ssd_activate_elem() 函数中 gc 部分的代码如下:

代码分析

如果从 ssd_media_access_request_element() 函数中调用 ssd_activate_elem() 这个函数,这个时候 element 的队列中一定是有请求的,所以这个时候 ssd_activate_elem() 中的 elem->metadata.reqs_waiting > 0 一定是成立的,所以这个时候后台 GC 与普通的 GC 是没有太大区别的。所以说后台 GC 与普通 GC 最大的区别在于从 ssd_media_access_request_element() 这个函数进入到ssd_activate_elem()


我们假设这样的一种情况,当一个 element 上的请求全部完成了,恰恰这个时候 element 上没有多余的 page 可以用了。

如果有后台 GC,这个时候从 ssd_media_access_request_element() 进入到 ssd_activate_elem() 时,会进行 GC 的判断,由于没有空闲块了,那么就会进行 GC 操作,这个时候该 element 上已经没有请求了,所以这个时候 GC 操作对 SSD 的响应时间是没有影响的。

如果没有后台 GC,只是普通 GC 的话,由于该 element 的队列上已经没有请求了,所以这个不会进行 GC 的判断,当该 element 上的下一个请求到来时,会触发 GC 操作,下一个请求的响应时间自然提高了。


什么时候触发GC

判断是否需要进行 GC 操作是分为两种不同的情况来判断的:有 copyback 和没有 copyback 。

在 ssd_clean.c 中的 ssd_clean_element() 函数中会根据是否有 copyback 来调用不同的函数区执行 GC 操作。

下面分别介绍在这两种情况下,达到什么条件时会触发 GC 操作.

无copyback

这种情况是最简单的,直接判断该 element 上的空闲块是否达到了预先所设定的阈值。

在 ssd_clean_element_no_copyback() 中会调用 ssd_start_cleaning(int plane_num, int elem_num, ssd_t *s) 函数。ssd_start_cleaning() 函数的内容如下:

因为在 ssd_clean_element_no_copyback() 中调用 ssd_start_cleaning() 时传入的第一个参数为 -1 所以这个时候在 ssd_start_cleaning() 中实际上只执行了两行代码:

low 在这里表示的就是每个 element 上的 blocks 的数量乘以最低空闲块的百分比。所以这种方式下,只要某个 element 上的空闲块低于阈值,就会判定为需要垃圾回收。

有copyback

这种判定方式稍微复杂些。是在 ssd_clean_element_copyback(int elem_num, ssd_t *s) 函数中判定的。

当我们需要判断某个 element 上是否需要进行垃圾回收时,首先会依次遍历这个 element 上的每一个并行单元(由几个plane组成),对于每个并行单元会依次遍历这个并行单元里的每个 plane 并调用ssd_start_cleaning() 这个函数(这个时候需要传入 plane_num,跟上面的不同),如果这个 plane 上的空闲 block 低于预先设定的阈值,那么就标记这个 plane 表示需要进行垃圾回收。

这种情况下,一个 element 上的每个并行单元里的每一个 plane 都要检查判断,但是一个并行单元里只要检查出一个 plane 需要进行垃圾回收其他的就不用检查了。只要有一个并行单元里检查除了需要垃圾回收的 plane,那么这个 element 就需要进行进行垃圾回收。

因为每个并行单元之间的写是并行的,所以在这种情况下做垃圾回收时,需要对每个并行单元都检查,从每个并行单元中都要选出一个 plane 进行垃圾回收(如果这个并行单元不需要垃圾回收就可以不用选),以保证下次的并行写能够同时对这几个并行单元进行写操作。

流程图如下:




在 ssdmodel 中是如何具体实现 GC 操作

在 ssdmodel 中实现 GC 的算法大概分为两种(准确的说应该是三种吧)。

  • 随机算法:在回收某个 element(或plane)的时候随机在其中选择一个符合要求的 block 进行回收。

  • 贪心算法:在回收某个 element(或plane)的时候从其中选择有效页最少的 block 进行回收。(这种算法又分为考虑 wear-aware 和不考虑 wear-aware 的情况)

除了这两种(或者三种吧)算法外,在 ssdmodel 实现中有 copyback 和没 copyback 的回收也是不一样的。

下面主要介绍在没有 copyback 情况下利用贪心算法如何来实现 GC。

结合前面的理一理垃圾回收的操作的整个流程吧。

ssd_activate_elem() —> ssd_invoke_element_cleaning() —> _ssd_invoke_element_cleaning() —>ssd_clean_element() —> (if no copyback) —> ssd_clean_element_no_copyback() —> (if达到gc条件) —> (if贪心算法) —> ssd_clean_blocks_greedy()

好了,今天就主要介绍 ssd_clean_blocks_greedy(int plane_num, int elem_num, ssd_t *s) 中是如何利用贪心算法来进行垃圾回收的。如果这里的 plane_num=-1 则表示把该 element 当成一个整体来进行垃圾回收,否则的话就是把这个 element 上编号为 plane_num 的 plane 当成一个整体进行回收。

step1. 建立 table

首先会调用 ssd_build_usage_table(elem_num, s) 这个函数来建立一个 table,tabel 可以看成是一个数组吧,数组大小等于一个 block 中 page 的数量,数组的成员为 usage_table 结构体。程序中对 usage_table 的定义如下:

step2. 计算平均剩余生命值 avg_lifetime

这里会调用 ssd_compute_avg_lifetime(plane_num, elem_num, s) 这个函数来计算当前 element(或plane) 中 block 的平均剩余生命值(剩余的可擦除次数),如果这里 plane_num=-1 那么就是计算整个 element 中 block 的平均剩余生命值,否则就是计算这个 element 上指定的 plane 中 block 的平均剩余生命值。

step3. 执行垃圾回收操作

这一步主要是依次遍历 table 数组,从有效页数量最少的开始(也就是从 table[0] 开始),每次遍历一个 table 元素的时候都会依次遍历它的 block[] 属性中的每一个 block,对它进行回收。每完成对其中一个 block 的回收后都要调用 ssd_stop_cleaning() 判断当前 element(或plane) 中的空闲块是否达到预先设定的值,如果达到了就不再行垃圾回收了。

遍历 table 用的是一个 for 循环,i从0一直到最大值(一个 block 中 page 的数量),表示优先回收有效页少的 block。对于 table[i],也是用一个for循环依次遍历一个 usage_table 元素中的 block[] 属性,也就是遍历 table[i] 中的 block[],j从0到 table[i].len。

对于最内层的循环,每次其实是选取出来了一个 block 进行回收,这个回收过程大致分为如下几个步骤:

(1) 对于 plane_num!=-1 的情况,每一个将要进行回收的 block 都要判断该 block 是否在该 plane 上,如果不在的话就重新选择下一个block,如果 plane_num=-1,则不需要此步骤的判断。

(2) 判断该 block 是否已经不可用了,也就是判断该 block 的剩余生命值block_life (剩余可擦出次数)是否为0。如果为0的话就重新选择下一个 block,否则继续下一步。

(3) 调用 ssd_can_clean_block() 判断该 block 是否处于可回收状态,如果不是则重新选择下一个block,如果是继续下一步。

(4) 这一步主要是针对需要考虑 wear-aware 情况的,如果不需要考虑 wear-aware ,可以直接跳到下一步。这一步主要判断当前 block 的剩余生命值是否不低于平均生命值avg_lifetime的某个百分比SSD_LIFETIME_THRESHOLD_X(程序约定好的)。如果不低于,直接进入到下一步。如果高于的话就以一定的概率放弃回收这个块,继续选择下一个待回收的block。

这个一定的概率是多大呢,block_life/avg_lifetime/SSD_LIFETIME_THRESHOLD_X,这么大(/ 表示除以,不是整除,带小数的那种除)。以一定的概率放弃回收这个块是怎么实现的呢,抛出一个随机数如果大于这个概率值就放弃回收这个块,继续选择下一个block,否则进入到下一步回收这个block。

(5) 经过层层筛选,如果这个 block 还能保留到现在,那就回收它吧,就是它了。调用_ssd_clean_block_fully() 回收这个 block。

(6) 调用 ssd_stop_cleaning() 判断当前 element(或plane)中的有效块是否达到了程序预先设定的值,如果是的话跳出循环,停止垃圾回收,否则继续循环。因为这里有两层循环,所以 ssd_stop_cleaning() 这个函数在两个循环的末尾都要被调用,从而跳出两层循环。

没有 copyback 的情况下利用随机算法如何实现 GC 操作

接着理一理程序的流程:

ssd_activate_elem() —> ssd_invoke_element_cleaning() —> _ssd_invoke_element_cleaning() —>ssd_clean_element() —> (if no copyback) —> ssd_clean_element_no_copyback() —> (if达到gc条件) —> (if随机算法) —> ssd_clean_blocks_random()

今天就主要介绍 ssd_clean_blocks_random(int plane_num, int elem_num, ssd_t *s) 中是如何利用随机算法来进行垃圾回收的。如果这里的 plane_num=-1 则表示把该 element 当成一个整体来进行垃圾回收,否则的话就是把这个 element 上编号为 plane_num 的 plane 当成一个整体进行回收。

随机算法实在是太简单了,就直接上图吧。


原文转载于:http://www.pdl.cmu.edu/DiskSim/



每天一个段子:某人发朋友圈:在中国古时候,男人只要兄弟武功高强,够义气;媳妇漂亮,这辈子就值了。楼下有人回复:北宋时候,有个人兄弟武功高强,够义气;媳妇漂亮,他是卖炊饼的。

注:本文由SSD PK社区提供,如有错误和不足之处欢迎在留言中批评指正,如果您喜欢本文,也可以分享给你的朋友。转载本文请务必保留原文出处,更多热门请关注SSD PK 社区网,www.pkssd.com是有关SSD最专业的社区网,提供全球有关SSD的最新热门资讯、各大厂商产品热门评测,最新前沿技术动态、有关企业级SSD选型以及最佳实践。


鲜花

握手

雷人

路过

鸡蛋
分享到

最新评论

    TylerDong

    管理员
    这个人很懒什么都没写!
    • 40

    • 文章
    • 0

    • 收听
    • 0

    • 听众

    热门文章

    SSD社区微信公众号

    SSD社区微信公众号

    扫我关注
    返回顶部