本篇文章是首爾大學(xué)發(fā)表在FAST 2023上的文章。隨著閃存容量的增加，邏輯地址到物理地址的映射表項(xiàng)也相應(yīng)增加。映射表項(xiàng)通常存放在設(shè)備控制器中的SRAM來(lái)加速訪問(wèn)。然而由于成本問(wèn)題SRAM一直無(wú)法增長(zhǎng)，這使得其中只能存放很少量的數(shù)據(jù)表項(xiàng)。而為了解決這一問(wèn)題，現(xiàn)有工作使用部分主機(jī)端內(nèi)存（high performance booster, HPB）來(lái)緩存映射表項(xiàng)。然而文章中發(fā)現(xiàn)，現(xiàn)有的HPB管理策略并不能夠很好的提升用戶體驗(yàn)。這是因?yàn)楝F(xiàn)有的管理策略通?？赡軙?huì)將前臺(tái)應(yīng)用的表項(xiàng)剔除。而為了解決這一問(wèn)題，本文設(shè)計(jì)提出HPBvalve技術(shù)來(lái)盡量緩存前臺(tái)應(yīng)用的映射表項(xiàng)。通過(guò)在搭建的真實(shí)平臺(tái)上的驗(yàn)證，該技術(shù)能夠很好的提升用戶體驗(yàn)。

背景

當(dāng)主機(jī)下發(fā)請(qǐng)求時(shí)會(huì)附上邏輯地址，UFS收到請(qǐng)求后會(huì)在閃存轉(zhuǎn)換層（FTL）進(jìn)行地址轉(zhuǎn)換，將邏輯地址轉(zhuǎn)換為物理地址，如圖1所示。記錄從邏輯地址到物理地址映射信息的稱之為映射表項(xiàng)。而為了加速這一過(guò)程，UFS中通常配備一個(gè)較小的SRAM用于緩存常用的映射表項(xiàng)。然而隨著閃存的迅速發(fā)展，SRAM空間越發(fā)不夠存儲(chǔ)經(jīng)常訪問(wèn)的表項(xiàng)。例如對(duì)于1TB的UFS設(shè)備配備512KB SRAM，則只有0.0005%的表項(xiàng)能夠緩存在其中。顯然這遠(yuǎn)遠(yuǎn)不夠。而為了緩解這一問(wèn)題，現(xiàn)有工作提出使用部分主機(jī)內(nèi)存（HPB）來(lái)緩存映射表項(xiàng)。相較于SRAM來(lái)說(shuō)，主機(jī)能夠提供較大的內(nèi)存，從而緩存更多的映射表項(xiàng)來(lái)加速訪問(wèn)。

動(dòng)機(jī)

為了展示映射表項(xiàng)對(duì)用戶體驗(yàn)的影響，文章中在搭建的平臺(tái)上做了很多實(shí)驗(yàn)。平臺(tái)將在實(shí)驗(yàn)部分介紹。其中設(shè)備容量為1TB，設(shè)備SRAM為512KB，HPB大小為256MB。OPTIMAL為所有映射表項(xiàng)都命中在設(shè)備SRAM的情況。應(yīng)用啟動(dòng)時(shí)間和加載時(shí)間作為衡量用戶體驗(yàn)的指標(biāo)。

圖2展示了映射表項(xiàng)訪問(wèn)確實(shí)對(duì)用戶感知延遲的影響。從中我們可以得出三個(gè)結(jié)論：

通過(guò)對(duì)比OPTIMAL和其他兩個(gè)可以看出，啟動(dòng)延遲和加載延遲都得到了較為明顯的提升。從絕對(duì)值來(lái)看，分別是220ms和183ms，已經(jīng)是用戶可感知的延遲。

通過(guò)比較UFS和UFS+HPB可以發(fā)現(xiàn)，盡管HPB能夠提供較大的容量，然而現(xiàn)有的管理策略并不能夠利用其很好的提升用戶體驗(yàn)。

HPB從主機(jī)端借用了較多的內(nèi)存反而會(huì)使得主機(jī)內(nèi)存壓力增加。

圖3中進(jìn)一步分析了HPB中前臺(tái)應(yīng)用和后臺(tái)應(yīng)用中映射表項(xiàng)的命中情況。從圖中我們可以看出前臺(tái)應(yīng)用的映射表項(xiàng)缺失情況比后臺(tái)應(yīng)用更加嚴(yán)重，這是因?yàn)椋?）傳統(tǒng)HPB采用基于計(jì)數(shù)的取映射表項(xiàng)策略。而后臺(tái)應(yīng)用比前臺(tái)應(yīng)用會(huì)下發(fā)更多的讀請(qǐng)求，這使得后臺(tái)應(yīng)用的映射表項(xiàng)的讀取計(jì)數(shù)通常比前臺(tái)應(yīng)用的高。因此會(huì)更傾向于將后臺(tái)應(yīng)用的映射表項(xiàng)取到HPB中。2）傳統(tǒng)HPB采用基于時(shí)間的映射表項(xiàng)剔除策略。然而當(dāng)用戶切換應(yīng)用并使用一段時(shí)間后，剛才使用應(yīng)用的映射表項(xiàng)也將會(huì)被剔除。這導(dǎo)致用戶再切換回來(lái)后映射表項(xiàng)缺失，影響用戶體驗(yàn)。

圖4和圖5分析了HPB無(wú)法很好預(yù)測(cè)哪些表項(xiàng)會(huì)被使用的原因。這是因?yàn)樵趹?yīng)用啟動(dòng)的時(shí)候，會(huì)有大量隨機(jī)的I/O請(qǐng)求，并且覆蓋很大的邏輯地址空間。這使得很難提高表項(xiàng)命中率。

圖6探索了HPB大小對(duì)用戶體驗(yàn)的影響。從中我們可以發(fā)現(xiàn)最佳的HPB大小隨著應(yīng)用不同而不同。同時(shí)隨著HPB的大小增加，前臺(tái)應(yīng)用下發(fā)的讀取請(qǐng)求也在增加。這是因?yàn)镠PB分配過(guò)多內(nèi)存導(dǎo)致內(nèi)存壓力過(guò)大，會(huì)殺掉一些應(yīng)用。當(dāng)這些應(yīng)用（cold state）之后再被訪問(wèn)的時(shí)候不僅啟動(dòng)時(shí)間增加，而且需要下發(fā)更多的讀取請(qǐng)求，如表1所示。圖7展示的是隨著HPB大小的增加，越來(lái)越多的應(yīng)用會(huì)被殺掉。

設(shè)計(jì)

為了解決上述問(wèn)題，文章中提出了HPBvalve（Hvalve），如圖8所示。Hvalve包含了五個(gè)部分。其中app-detector和mem-detector分別用于判斷應(yīng)用是否為前臺(tái)應(yīng)用、應(yīng)用狀態(tài)變化和內(nèi)存壓力情況。FG profiler維護(hù)了近期使用應(yīng)用會(huì)訪問(wèn)的映射表項(xiàng)，用于預(yù)取映射表項(xiàng)。L2P manager用于單獨(dú)管理前臺(tái)應(yīng)用的映射表項(xiàng)。HPB regulator用于根據(jù)內(nèi)存壓力情況調(diào)整HPB大小，避免過(guò)多應(yīng)用被殺掉。

1. 前臺(tái)/后臺(tái)應(yīng)用識(shí)別：Hvalve在bio結(jié)構(gòu)體中創(chuàng)建新的變量UID，用于記錄下發(fā)請(qǐng)求所屬的應(yīng)用。當(dāng)bio創(chuàng)建請(qǐng)求的時(shí)候，UID也會(huì)集成在請(qǐng)求中。同時(shí)app detector會(huì)通過(guò)安卓活動(dòng)任務(wù)管理器（android activity task manager）來(lái)檢測(cè)是否有新的前臺(tái)應(yīng)用啟動(dòng)。如果有一個(gè)新的前臺(tái)應(yīng)用啟動(dòng)時(shí)，將該應(yīng)用的UID傳遞給HPB。這樣HPB可以將該UID與請(qǐng)求中攜帶的UID進(jìn)行比較，從而判斷應(yīng)用是否為前臺(tái)應(yīng)用。

2. L2P management：Hvalve維護(hù)了三個(gè)LRU鏈表，分別用戶記錄活躍前臺(tái)應(yīng)用、非活躍前臺(tái)應(yīng)用和后臺(tái)應(yīng)用的映射表項(xiàng)。當(dāng)新的前臺(tái)應(yīng)用啟動(dòng)時(shí)，會(huì)將之前的前臺(tái)應(yīng)用表項(xiàng)降級(jí)到非活躍前臺(tái)應(yīng)用鏈表中。當(dāng)需要剔除表項(xiàng)的時(shí)候優(yōu)先提出后臺(tái)應(yīng)用表項(xiàng)，然后是非活躍前臺(tái)應(yīng)用表項(xiàng)。而前臺(tái)應(yīng)用表項(xiàng)不會(huì)被剔除。

3. Hvalve緩存策略：1）其中依舊延續(xù)傳統(tǒng)的基于訪問(wèn)計(jì)數(shù)的方式來(lái)緩存經(jīng)常被訪問(wèn)的表項(xiàng)。2）對(duì)于前臺(tái)應(yīng)用緩存表項(xiàng)未命中時(shí)，立即將該表項(xiàng)取到HPB中。3）根據(jù)FG profiler預(yù)取表項(xiàng)。

4. 前臺(tái)應(yīng)用分析和預(yù)?。簣D9展示了FG-profiler中記錄的信息。FG-profiler記錄近期訪問(wèn)應(yīng)用的映射表項(xiàng)。同時(shí)根據(jù)app detector基于安卓活躍任務(wù)管理器發(fā)出的應(yīng)用啟動(dòng)開(kāi)始和啟動(dòng)結(jié)束信號(hào)，可以將映射表項(xiàng)分為啟動(dòng)表項(xiàng)和運(yùn)行表項(xiàng)。當(dāng)一個(gè)應(yīng)用被切換為前臺(tái)應(yīng)用的時(shí)候，hvalve會(huì)先判斷該應(yīng)用對(duì)應(yīng)的映射表項(xiàng)是否記錄在FG-profiler中。如果在，則將記錄的映射表項(xiàng)預(yù)取到HPB中，以加速訪問(wèn)，如圖10所示。

5. HPB大小動(dòng)態(tài)調(diào)整：mem-detector時(shí)刻監(jiān)測(cè)LMKD。當(dāng)內(nèi)存不足激活LMKD殺進(jìn)程時(shí)，mem-detector會(huì)將將要?dú)⒌舻倪M(jìn)程UID傳送給HPB-regulator。HPB-regulator會(huì)判斷該應(yīng)用在FG-profiler中是否有記錄，如果沒(méi)有說(shuō)明不是近期訪問(wèn)過(guò)的應(yīng)用，則直接殺掉。如果有，則會(huì)根據(jù)LMKD需要釋放內(nèi)存的大小剔除HPB中的表項(xiàng)。優(yōu)先提出后臺(tái)應(yīng)用表項(xiàng)，然后是非活躍應(yīng)用表項(xiàng)。如果剔除之后內(nèi)存仍然不足，則需要重新喚醒LMKD選取應(yīng)用殺掉。該過(guò)程如圖11所示。

實(shí)驗(yàn)

該文章為了探尋HPB不同方面的影響，自己搭建了一個(gè)平臺(tái)，如圖12所示。其中使用高性能SSD作為主要存儲(chǔ)，同時(shí)簡(jiǎn)單實(shí)現(xiàn)了HPB的管理策略，來(lái)進(jìn)行映射表項(xiàng)的存取。應(yīng)用場(chǎng)景也如圖12所示。

性能：性能提升如圖13所示。Hvalve相較于UFS和UFS+HPB均有所改善，并且接近OPTIMAL的場(chǎng)景。

表項(xiàng)未命中模式：圖14展示了前臺(tái)應(yīng)用表項(xiàng)缺失隨著運(yùn)行時(shí)間的分布?？梢钥闯鯤valve很好的控制住了在應(yīng)用剛運(yùn)行時(shí)候的缺失率高的問(wèn)題。

命中率：圖15展示了Hvalve的命中率情況。相較于HPB-only，Hvalve很好的提升了應(yīng)用冷啟動(dòng)時(shí)的映射表項(xiàng)命中率。

HPB大小動(dòng)態(tài)調(diào)整效果：圖16展示了Hvalve動(dòng)態(tài)調(diào)整對(duì)前臺(tái)應(yīng)用的影響?？梢钥闯鯤valve相較于傳統(tǒng)的HPB管理策略減少了被殺掉的應(yīng)用，同時(shí)很好的保護(hù)了高優(yōu)先級(jí)的應(yīng)用，減少了應(yīng)用下發(fā)的讀請(qǐng)求數(shù)量。圖17可以觀察到HPB大小動(dòng)態(tài)調(diào)整的過(guò)程。

總結(jié)

為了提高HPB的使用效率從而提升用戶體驗(yàn)，本文在自己搭建的平臺(tái)上深入的分析了當(dāng)前HPB管理策略存在的問(wèn)題，并在此基礎(chǔ)上設(shè)計(jì)了Hvalve。Hvalve通過(guò)對(duì)前臺(tái)應(yīng)用映射表項(xiàng)的識(shí)別和管理，提高了前臺(tái)應(yīng)用的訪問(wèn)速度，提升用戶體驗(yàn)。同時(shí)根據(jù)內(nèi)存壓力動(dòng)態(tài)調(diào)整HPB大小，避免導(dǎo)致內(nèi)存壓力過(guò)大而殺掉過(guò)多的應(yīng)用，影響用戶體驗(yàn)。實(shí)驗(yàn)結(jié)果顯示，Hvalve提升了用戶前臺(tái)應(yīng)用表項(xiàng)的命中率，減少了被殺掉的應(yīng)用，提升了用戶體驗(yàn)。