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

背景

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

動機

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

圖2展示了映射表項訪問確實對用戶感知延遲的影響。從中我們可以得出三個結(jié)論：

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

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

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

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

圖4和圖5分析了HPB無法很好預(yù)測哪些表項會被使用的原因。這是因為在應(yīng)用啟動的時候，會有大量隨機的I/O請求，并且覆蓋很大的邏輯地址空間。這使得很難提高表項命中率。

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

設(shè)計

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

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

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

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

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

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

實驗

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

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

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

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

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

總結(jié)

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