周權彪 張興軍 梁寧靜 霍文潔 董小社

(西安交通大學計算機科學與技術系 西安 710049) (zhouquanbiao1991@163.com)

在當前計算機應用向數(shù)據(jù)密集型轉變的大趨勢下，現(xiàn)代計算機系統(tǒng)對外存IO性能的要求不斷提高.磁盤作為傳統(tǒng)外存設備，雖然容量大、成本低，但是由于固有機械部件的限制，其IO性能無法滿足當下快速交互型應用的需求.閃存作為一種無機械結構存儲介質(zhì)，性能遠優(yōu)于磁盤，具有隨機存取速度快、能耗低、抗震能力好等優(yōu)點，是外存介質(zhì)的理想選擇.隨著閃存技術的不斷成熟，閃存被廣泛應用于消費電子和企業(yè)級計算機系統(tǒng)中，以大容量緩存或外存的形式存在[1].

閃存采用浮柵型場效應管作為數(shù)據(jù)儲存單元，通過場效應管內(nèi)浮置柵極存儲的電荷量多少表示不同的數(shù)據(jù).這種不同于磁盤的數(shù)據(jù)存儲方式，使得閃存具有其獨特的讀寫性質(zhì)，包括“按頁讀寫”、“按塊擦除”和“寫前先擦除”[2]，其含義分別是：1)“按頁讀寫”是指對閃存的讀寫操作必須以物理頁為單位進行；2)“按塊擦除”是指閃存擦除操作必須以物理塊為單位進行；3)“寫前先擦除”(erase-before-write)是指1個閃存單元在經(jīng)過1次寫入操作后，必須對該閃存單元進行1次擦除操作后，才能夠寫入新數(shù)據(jù).

由于這3個性質(zhì)的限制，對閃存的數(shù)據(jù)更新操作必須采取“異地更新”(out-of-place update)[3]的方式完成.“異地更新”是指在閃存中，對某一邏輯地址的寫入操作，不能直接將新的數(shù)據(jù)內(nèi)容覆蓋寫到原有邏輯地址對應的物理地址上，而必須將新數(shù)據(jù)內(nèi)容寫入一個新的空閑物理地址,然后通過修改邏輯地址和物理地址映射信息的方式，使邏輯地址指向新的物理地址，并將原物理地址的數(shù)據(jù)無效化，從而達到更新數(shù)據(jù)的目的.

由于閃存擁有這些獨特的性質(zhì)和操作，在閃存存儲系統(tǒng)中，為了屏蔽閃存與傳統(tǒng)磁盤不一樣的讀寫特性，需要一個專用軟件層來對閃存進行管理和優(yōu)化，這就是閃存轉換層(flash translation layer，F(xiàn)TL)[4].閃存轉換層作為閃存系統(tǒng)中的核心軟件管理層，在整個閃存軟件棧中起到屏蔽閃存底層存取細節(jié)，向上層文件系統(tǒng)提供存取接口的作用.通過閃存轉換層，閃存固態(tài)盤被封裝成像磁盤一樣的塊設備，上層文件系統(tǒng)不需要修改，即可像讀寫磁盤一樣，正常地讀寫閃存固態(tài)盤.閃存轉換層具有一些重要的功能，如地址映射、垃圾回收、磨損均衡、壞塊管理、讀寫數(shù)據(jù)緩存、閃存數(shù)據(jù)糾錯和數(shù)據(jù)加密等[4].

閃存轉換層地址映射方法的優(yōu)劣極大影響到閃存的性能和壽命.DFTL(demand-based FTL)[5]是經(jīng)典的地址映射方法，它把較大的全局映射表放在閃存中，只將常用的映射項放在緩存中，根據(jù)映射項訪問的近期性作為緩存替換的依據(jù).

DFTL同樣存在一些問題.首先，DFTL采用最近最少使用(least recently used, LRU)替換算法充分尊重了時間局部性原理，但忽略了負載的空間局部性特點，使得在負載訪問的地址空間發(fā)生變化時會發(fā)生頻繁的緩存失效，導致緩存命中率的下降.

此外，在發(fā)生緩存失效時，如果被換出的映射項是臟映射項，即若該映射項曾被修改，那么必須將該臟映射項寫回閃存，以保證元數(shù)據(jù)映射信息的一致性.而臟映射項的頻繁換出，會帶來對閃存的頻繁寫操作，為閃存的性能和壽命帶來額外負擔.

另一方面，DFTL無法優(yōu)化閃存中存在的由于垃圾回收導致的寫放大(write amplification)[6]問題.寫放大問題指對閃存系統(tǒng)實際寫入的數(shù)據(jù)量大于文件系統(tǒng)請求寫入的數(shù)據(jù)量.閃存的垃圾回收過程是造成寫放大問題的主要因素之一.在垃圾回收過程中，若被回收物理塊內(nèi)有未被覆寫的有效數(shù)據(jù)頁，則必須進行有效頁遷移操作，每個有效頁需要至少1次讀操作和1次寫操作來完成遷移過程.此外，有效頁的遷移還會導致其對應的邏輯地址和物理地址映射信息發(fā)生改變，從而引起額外的元數(shù)據(jù)讀寫操作.被回收物理塊內(nèi)的有效頁越多，則需要遷移的有效頁也越多，對閃存性能和壽命帶來的負面影響也更大.

針對上述問題，本文研究采用基于緩存映射項重用距離的地址映射方法IRR-FTL(inter-reference recency-based FTL)，優(yōu)化閃存地址映射過程.本文的貢獻主要在：1)通過設置獨立的映射頁緩存槽，充分利用負載的空間局部性，提高緩存映射表的命中率.2)通過基于緩存映射項重用距離的負載自適應寫緩存映射表冷熱分區(qū)方法，將寫緩存映射表分為熱寫緩存映射表和冷寫緩存映射表，并對冷寫緩存映射表采取非臟映射項優(yōu)先換出和臟映射項最大化批量更新的策略，減少映射頁寫回次數(shù).3)針對閃存垃圾回收中存在的寫放大問題，實現(xiàn)基于緩存映射項重用距離的冷熱數(shù)據(jù)分離存儲，提高垃圾回收效率.

1 相關工作

閃存轉換層的地址映射過程是指SSD系統(tǒng)將上層文件系統(tǒng)請求的邏輯地址，通過地址映射表轉換為下層閃存物理地址的過程.閃存轉換層的地址映射策略[4]，可以根據(jù)地址映射粒度的大小，大致分為3種，即頁級地址映射策略[5,7-10]、塊級地址映射策略[4]和基于日志塊的混合地址映射策略[11-13].

在頁級地址映射策略中，每一個邏輯頁地址可以映射到任意一個物理頁地址.因此在頁級地址映射表中，需要記錄每一個邏輯頁和對應物理頁的映射關系.這種映射方式靈活高效、優(yōu)化空間大、性能較好，但由于映射粒度較小，導致映射表條目較多，因此需要維護一個較大的頁級地址映射表.但由于目前固態(tài)盤容量越來越大，而在固態(tài)盤中往往采用存取速度極快、單位存儲成本較高的RAM，因此一般完整的頁級地址映射表無法全部裝入RAM中，因此純頁級映射策略在實際中應用較少.

在塊級地址映射策略中，每一個邏輯塊可以映射到任意一個物理塊上，塊內(nèi)的數(shù)據(jù)頁則需要嚴格按照邏輯地址的塊內(nèi)偏移量進行排列[4].相比于頁級地址映射策略，塊級地址映射策略的映射粒度大，所以塊級地址映射表較小，占用的RAM空間較少.但是，為了維護塊內(nèi)數(shù)據(jù)頁的偏移量，塊級地址映射策略在進行垃圾回收過程中，需要進行數(shù)據(jù)塊合并操作，這種合并操作往往涉及到大量數(shù)據(jù)頁的拷貝和移動，對閃存的性能影響較大.因此，相對于頁級地址映射策略而言，塊級地址映射策略是以犧牲映射靈活性和性能為代價，換取空間開銷的減少.

在基于日志塊的混合地址映射策略中，閃存分為數(shù)據(jù)塊區(qū)(data block area)和日志塊區(qū)(log block area).其中數(shù)據(jù)塊區(qū)采用塊級地址映射策略，而日志塊區(qū)采用頁級地址映射策略，日志塊區(qū)僅占閃存總容量的3%[13].通過日志塊暫時接納寫入的無序數(shù)據(jù)，當日志塊區(qū)滿時，再使用合并操作(merge operation)，將日志塊與對應的數(shù)據(jù)塊進行合并.由于日志塊采用性能較好的頁級地址映射策略，因此可以較好地吸收隨機寫入的數(shù)據(jù).但是由于在日志塊與數(shù)據(jù)塊的合并過程中，有較大幾率發(fā)生開銷較大的“全合并”(full merge)操作，因此基于日志塊的混合地址映射策略同樣會出現(xiàn)閃存性能下降的現(xiàn)象.典型的基于日志塊的混合地址映射策略包括BAST[11]，F(xiàn)AST[12]，SuperBlock[13].

為了解決基于日志塊的混合地址映射策略中合并操作帶來的額外讀寫開銷問題，2009年Gupta等人[5]提出了基于需求的閃存轉換層地址映射方法DFTL.DFTL采用頁級地址映射策略，無需數(shù)據(jù)塊合并操作，它將占用空間較大的全局頁級地址映射表以映射頁的形式存放在容量較大的閃存中，在容量較小而速度較快的RAM中設置緩存映射表，根據(jù)負載需求，動態(tài)地將最近最常使用的映射信息換入緩存映射表中，實現(xiàn)性能和RAM空間開銷的平衡.此外，DFTL還在RAM中設置全局映射目錄(global translation directory， GTD)記錄映射頁在閃存中的物理位置.DFTL采用邏輯頁級的LRU算法保證緩存映射表的命中率，減少由于緩存失效造成的元數(shù)據(jù)換入換出操作；通過批量更新和推遲拷貝技術，減少由于元數(shù)據(jù)更新而造成的閃存映射頁寫回操作，提高閃存IO性能.但DFTL未充分利用負載的空間局部性特點提高緩存命中率.緩存中臟映射項的頻繁換出也會帶來額外映射頁操作開銷.此外，DFTL也未能對閃存垃圾回收過程中存在的有效頁遷移開銷進行優(yōu)化.

此后，針對DFTL存在的問題，國內(nèi)外有許多基于DFTL的研究被提出[7-10, 14-17].LazyFTL[7]通過設置更新數(shù)據(jù)區(qū)和冷數(shù)據(jù)區(qū)分離冷熱數(shù)據(jù)，并通過設置更新映射表推遲映射信息的更新操作；通過設置標志位，選擇更新開銷最小的映射信息進行更新，減少映射頁額外操作.OAT[8]則將緩存映射信息的粒度從映射項增大到映射頁，以提高命中率；同時，為了解決DFTL的垃圾回收過程中涉及過多映射頁的問題，通過將映射頁對應的數(shù)據(jù)頁聚集到同一物理塊內(nèi)，減少垃圾回收過程中的映射頁操作.TPFTL[9]則充分挖掘負載的空間局部性，根據(jù)緩存中映射項特征，動態(tài)調(diào)整預取的映射項數(shù)量，提高緩存命中率.CPFTL[10]將映射表劃分為冷映射表和熱映射表，對冷映射表采用頁聚簇的方法，減少由于映射項換出而導致的額外映射頁操作.與文獻[7-10]不同，本文通過獨立的映射頁緩存槽挖掘負載的空間局部性，提高緩存命中率.此外，通過緩存映射項重用距離，實現(xiàn)負載自適應的寫緩存映射表冷熱分區(qū)方法，優(yōu)先換出冷寫緩存映射表中已被更新的非臟映射項，并且采用臟映射項最大化批量更新策略，減少由于緩存失效造成的映射頁操作開銷.

另一方面，在閃存中冷熱數(shù)據(jù)分離存儲對減少垃圾回收開銷、提高垃圾回收效率有重要作用[3].通過將熱度相近的頁面存儲在同一物理塊中，使得同一物理塊內(nèi)的頁面更有可能在相近的時間段內(nèi)被更新，從而減少在垃圾回收過程時進行的有效頁遷移次數(shù)，提高垃圾回收效率.有諸多文獻是通過閃存冷熱數(shù)據(jù)分離存儲[14-17]，減少垃圾回收過程中的有效頁遷移開銷，提高閃存性能.

LAST[14]采用不同的地址映射策略管理隨機請求和連續(xù)請求，同時通過冷熱數(shù)據(jù)分離，減少垃圾回收開銷.HFTL[15]則基于多Hash框架，先識別冷熱邏輯塊，再進一步判斷熱邏輯塊內(nèi)部的邏輯頁冷熱性質(zhì)，找出被頻繁更新的邏輯頁，實現(xiàn)冷熱數(shù)據(jù)分離.文獻[16]采用多層布隆過濾器的方法分離冷熱數(shù)據(jù)，不僅考慮了數(shù)據(jù)存取頻率，還考慮了數(shù)據(jù)使用的近期性，采用滑動窗口的方式捕捉細粒度的數(shù)據(jù)近期性信息，實現(xiàn)閃存冷熱數(shù)據(jù)分離.不同于上述基于數(shù)據(jù)存取頻率判別數(shù)據(jù)冷熱性質(zhì)的方法，本文將數(shù)據(jù)訪問的重用距離作為判斷冷熱數(shù)據(jù)的標準，相比數(shù)據(jù)訪問頻率，數(shù)據(jù)訪問重用距離對數(shù)據(jù)的冷熱變化更敏感.而對于閃存而言，數(shù)據(jù)頁的寫入重用距離即是數(shù)據(jù)頁被無效化的時間間隔，因此也更適合作為閃存冷熱數(shù)據(jù)分離標準.

ASA-FTL[17]將邏輯頁寫入間隔作為冷熱數(shù)據(jù)分離的依據(jù)，記錄每一個邏輯頁面的寫入間隔大小，并采用抽樣聚類的方式將頁面分組存儲，實現(xiàn)冷熱數(shù)據(jù)分離.與之類似，本文同樣將頁面寫入間隔，即數(shù)據(jù)頁寫入重用距離作為判斷冷熱性質(zhì)的依據(jù)，但是相比ASA-FTL，IRR-FTL不需要記錄所有頁面的重用距離，而是通過分離出在當前負載中熱度較高的緩存映射項，從而識別出當前熱度較高的數(shù)據(jù)頁，從而在節(jié)省空間開銷的同時降低記錄和計算頁面重用距離的復雜性.

2 負載自適應的寫緩存冷熱分區(qū)方法

針對寫緩存映射表，本文提出一種基于緩存映射項重用距離的寫緩存映射表冷熱分區(qū)方法.不同于采用訪問頻率作為分離標準，本方法將緩存映射表中的寫緩存映射項分為重用距離較短的熱映射項和重用距離較長的冷映射項，并根據(jù)冷熱重用距離閾值將寫緩存映射表分為熱寫緩存映射表和冷寫緩存映射表.同時，該方法能夠根據(jù)負載局部性情況動態(tài)調(diào)節(jié)冷熱分區(qū)的相對大小，實現(xiàn)負載自適應.

2.1 數(shù)據(jù)對象熱度評價標準

一般而言，對數(shù)據(jù)對象的熱度有2種評價方法：1)根據(jù)數(shù)據(jù)對象在一定時間間隔內(nèi)的訪問次數(shù)即訪問頻率來判斷頁面熱度[13].訪問頻率越高的頁面，則其熱度越高;相反，若某頁面在一個較長時間間隔內(nèi)訪問次數(shù)較少，則證明其熱度較低.2)數(shù)據(jù)對象熱度評價方法，則是根據(jù)數(shù)據(jù)對象2次訪問之間的時間間隔[18]，即重用距離進行判斷.若數(shù)據(jù)對象2次訪問之間的時間間隔較短，則該數(shù)據(jù)對象更有可能是熱度較高的數(shù)據(jù)對象.

基于數(shù)據(jù)對象訪問頻率的冷熱數(shù)據(jù)判別方法是判斷冷熱數(shù)據(jù)最直接的方法.但是，由于現(xiàn)實中的工作負載處于不斷變化的過程之中，在前一個時間段內(nèi)訪問次數(shù)較多的熱數(shù)據(jù)可能會因為負載變化而冷卻成為訪問較少的冷數(shù)據(jù)，但此時熱數(shù)據(jù)可能會由于前一個時間段較高的訪問次數(shù)，而需要經(jīng)過較長的時間后才會被冷卻.相比之下，數(shù)據(jù)對象2次訪問的時間間隔，即重用距離，對負載的變化則更為敏感.當新數(shù)據(jù)對象的訪問時間間隔短于熱數(shù)據(jù)最后一次訪問時間點距離當前時間點的時間間隔時，新數(shù)據(jù)對象即可取代原來的熱數(shù)據(jù)對象，成為新的熱數(shù)據(jù).在本文中，數(shù)據(jù)對象是指緩存映射項，重用距離特指對特定邏輯頁地址的2次寫入操作之間的時間間隔.

對閃存而言，某一邏輯頁面的2次寫入操作之間的時間間隔，代表了該頁面在第1次寫入閃存后，其數(shù)據(jù)頁在閃存中作為有效數(shù)據(jù)頁存在直至被無效化的時間間隔.若該時間間隔越短，則該頁面熱度越高，同時也意味著該頁面被無效化越快，在垃圾回收時更有可能不需要進行額外的有效頁遷移操作.因此，相對于使用頁面訪問頻率作為冷熱數(shù)據(jù)判斷標準，頁面的寫入時間間隔，即重用距離，更適合作為閃存數(shù)據(jù)冷熱分離的判斷依據(jù).

2.2 緩存映射項重用距離

映射項重用距離(inter-reference recency，IRR)[18]，此處特指寫入重用距離，是指對某一映射項的2次寫入之間，間隔地被其他寫入請求訪問的不同的映射項數(shù)量.例如對于寫入訪問序列：{1，2，3，2，4，1，4}、映射項1的2次訪問之間，間隔了3個不同的邏輯頁映射項2，3，4，因此映射項1的重用距離是3.同理，映射項4的重用距離是1.

采用映射項重用距離作為區(qū)分冷熱元數(shù)據(jù)的標準，是因為相對于映射項訪問頻率而言，重用距離對映射項熱度的變化更敏感.此外，映射項的重用距離也隱含了映射項對應的數(shù)據(jù)頁在閃存中被無效化的寫入間隔.如果一個映射項的重用距離為5，則意味著在經(jīng)過5次寫入操作之后，該映射項對應的數(shù)據(jù)頁被無效化.因此，重用距離更適合用于閃存冷熱數(shù)據(jù)分離.

本文在緩存映射表中使用LRU鏈表來計算緩存映射項的重用距離.在某時刻，在緩存映射表的LRU鏈表中，某命中的映射項的重用距離，可以表征為：該映射項被命中時，其結點所在位置距離鏈表首部的距離.如圖1所示，若此時映射項1被命中，則映射項1的重用距離為該映射項距離鏈表首部的距離，此時是3.

Fig. 1 Translation entry’s IRR in cache mapping table圖1 緩存映射表中被命中映射項的重用距離

Fig. 2 The workload adaptive hot/cold cache mapping area based on IRR圖2 基于重用距離的負載自適應寫緩存映射表冷熱分區(qū)

同時，我們定義某時刻映射項的潛在重用距離為：當前時刻，該映射項結點距離鏈表首部的距離.若當前時刻，該映射項被命中，則該映射項潛在重用距離等于重用距離.某一時刻某一映射項的潛在重用距離，表征在當前時刻該映射項可能達到的最短重用距離，該映射項下一次命中時的重用距離大于或等于潛在重用距離，若該時刻該映射項命中，則等號成立.

在基于緩存映射項重用距離的緩存映射表中，將映射項根據(jù)上一次命中時重用距離的大小分為冷緩存映射項和熱緩存映射項.緩存映射項鏈表同樣遵循LRU規(guī)則，每次命中的映射項，無論是冷緩存映射項或是熱緩存映射項，都會被移動到鏈表首部.而在緩存中，冷熱重用距離閾值即為鏈表中最后一個熱映射項的潛在重用距離.

冷熱映射項之間的轉換規(guī)則可以定義為：當某一冷映射項命中時，若該冷映射項的重用距離比最后一個熱映射項的潛在重用距離更短，即若該冷映射項比最后一個熱映射項更靠近鏈表首部，則該冷映射項可以取代最后一個熱映射項成為熱映射項.這是因為，在某時刻，若某冷映射項命中時，其位置在最后一個熱映射項之前，則該命中的冷映射項當前的重用距離必定比最后一個熱映射項未來命中時的重用距離更短.因此，該冷映射項可以代替原來的最后一個熱映射項轉變?yōu)闊嵊成漤?，而最后一個熱映射項作為潛在重用距離最長的熱映射項，將被轉換為冷映射項.

舉例分析，有如圖2(a)所示的LRU鏈表，當冷映射項5被命中時，此時映射項5的重用距離為7，而最后一個熱映射項6的潛在重用距離為11，意味著熱映射項6在未來命中時的重用距離大于等于11，比冷映射項5的重用距離更長，因此冷映射項5可以取代熱映射項6成為新的熱映射項，而熱映射項6則被冷卻為冷映射項.

2.3 基于IRR的寫緩存冷熱分區(qū)方法

如圖2所示，本文基于緩存映射項的重用距離，以最后一個熱映射項為界，將寫緩存映射表分為熱寫緩存映射表(hot write cache mapping table,HW-CMT)和冷寫緩存映射表(cold write cache mapping table,CW-CMT).潛在重用距離小于冷熱重用距離閾值的映射項在HW-CMT中，潛在重用距離大于冷熱重用距離閾值的映射項在CW-CMT中.

HW-CMT中存放的是最后一個熱映射項之前的映射項，即所有的熱映射項和一部分最近發(fā)生寫入操作的冷映射項.由于該部分冷映射項最近曾被訪問，如果再次命中，則由于其重用距離比最后一個熱映射項的潛在重用距離更短，因此可以代替最后一個熱映射項，轉換為新的熱映射項，并被放到HW-CMT鏈表首部.

Fig. 3 The overall framework of IRR-FTL圖3 IRR-FTL整體框架

CW-CMT中存放的是最后一個熱映射項之后的冷映射項.CW-CMT中的冷映射項即使再次命中，因為其當前命中的重用距離大于最后一個熱映射的潛在重用距離，所以無法轉換為熱映射項，而是以冷映射項的形式再次插入HW-CMT鏈表首部，給予其在HW-CMT被命中而轉換為熱映射項的機會.當寫緩存發(fā)生失效且寫緩存已滿時，系統(tǒng)會從CW-CMT中采用特定策略選擇映射項進行換出操作.

當HW-CMT中的最后一個熱映射項被轉換為冷映射項或最后一個熱映射項因被命中而被移動到HW-CMT隊首時，會進行“剪枝”操作，即將HW-CMT鏈表尾部所有的非熱映射項移動到CW-CMT中，保證了冷熱寫緩存映射表分區(qū)原則，即HW-CMT鏈表的最后一個映射項是熱映射項.如圖2(a)所示，當冷映射項5因命中而轉變?yōu)闊嵊成漤棔r，最后一個熱映射項6將轉化為冷映射項.此時，由于HW-CMT最后一個映射項不是熱映射項，因此發(fā)生“剪枝”操作，如圖2(b)所示，冷映射項12，9，6將落入CW-CMT中.而最后一個熱映射項變?yōu)橛成漤?，冷熱重用距離閾值將變?yōu)?.

2.4 負載自適應的冷熱緩存映射區(qū)比例

如圖2所示，在本方法中，HW-CMT和CW-CMT的總大小是固定的.但是，它們的相對大小是不斷變化的.HW-CMT和CW-CMT的相對大小由最后一個熱映射項的潛在重用距離決定的.若最后一個熱映射項距離鏈表首部越遠，則HW-CMT越大、CW-CMT越小.當冷熱映射項的比例一定時，若負載的局部性越強，則最后一個熱映射項越靠近鏈表首部，HW-CMT越小，CW-CMT越大；相同負載環(huán)境下，若熱映射項比例越小，則最后一個熱映射項距離鏈表首部更近，HW-CMT越小，CW-CMT越大.

因此，為了保證CW-CMT不為空，需要維持CW-CMT的長度處于一個合理的區(qū)間內(nèi).當CW-CMT小于該區(qū)間時，系統(tǒng)會通過減少熱映射項數(shù)量的方式，使最后一個熱映射項位置靠前，使得更多的映射項落入CW-CMT中；當CW-CMT大于該區(qū)間時，系統(tǒng)會通過增大熱映射項數(shù)量的方式，使最后一個熱映射項位置靠后，從而使更多映射項被保留在HW-CMT中.

3 基于IRR的閃存轉換層地址映射方法

本文基于頁級地址映射策略，提出一種基于緩存映射項重用距離的閃存轉換層地址映射方法IRR-FTL.圖3展示了IRR-FTL系統(tǒng)整體框架.

IRR-FTL通過設置獨立的映射頁緩存槽，充分利用負載的空間局部性，提高緩存命中率；通過讀寫緩存映射表分離，避免讀請求對計算寫入重用距離造成影響；通過基于緩存映射項重用距離的負載自適應寫緩存映射冷熱分區(qū)方法，分離出重用距離較長的熱映射項和重用距離較短的冷映射項，并將其對應數(shù)據(jù)寫入不同的閃存區(qū)域，實現(xiàn)冷熱數(shù)據(jù)分離；此外，將冷寫緩存映射表分為非臟緩存映射區(qū)和臟緩存映射區(qū)，通過非臟映射項優(yōu)先換出和臟映射項最大化批量更新的方式，減少映射信息寫回開銷，提高閃存性能.

3.1 系統(tǒng)架構

IRR-FTL將閃存分為冷數(shù)據(jù)區(qū)(cold data block area)、熱數(shù)據(jù)區(qū)(hot data block area)和映射塊區(qū)(mapping block area)，分別存儲冷用戶數(shù)據(jù)、熱用戶數(shù)據(jù)和全局映射表.全局映射表以映射頁的形式存儲在閃存的映射塊區(qū)中.在RAM中，使用全局轉換目錄(global translation directory，GTD)記錄映射頁在閃存中的物理位置.系統(tǒng)分別設置讀緩存映射表(read cache mapping table,R-CMT)和寫緩存映射表(write cache mapping table,W-CMT).通過分離讀寫緩存映射表，避免讀請求對寫請求重用距離計算造成的影響.同時，為了適應負載變化，系統(tǒng)會根據(jù)前一段時間負載的讀寫比例，動態(tài)調(diào)整R-CMT和W-CMT的相對大小.

W-CMT中存放的是被寫請求訪問過的映射項.根據(jù)第2節(jié)中論述的基于緩存映射項重用距離的負載自適應寫緩存映射表冷熱分區(qū)方法，W-CMT被分為HW-CMT和CW-CMT.而CW-CMT又被進一步分為冷臟寫緩存映射表和冷非臟寫緩存映射表.冷臟寫緩存映射表(dirty cold write cache mapping table,DCW-CMT)存放冷映射項中未同步寫回閃存的臟映射項，該部分映射項的換出需要進行映射頁寫回操作；冷非臟寫緩存映射表(clean cold write cache mapping table,CCW-CMT)存放冷映射項中已被寫回閃存的非臟映射項，由于該部分映射項已經(jīng)被寫回閃存，所以可以直接丟棄，而不需要換出開銷.

下面分別介紹IRR-FTL的關鍵數(shù)據(jù)結構.

1) 映射頁緩存槽TPCS

本文在RAM中設置大小為1個映射頁的映射頁緩存槽(translation page cache slot, TPCS)，用以緩存每次讀入的映射頁(如圖3中箭頭1所示).每個映射頁包含了一定邏輯地址范圍內(nèi)的映射項信息，有利于吸收連續(xù)的和較大的讀寫請求，充分挖掘負載的空間局部性.同時，為了保證元數(shù)據(jù)的一致性，當某映射項被讀或寫時，該映射項會被從TPCS移動到R-CMT或W-CMT中(如圖3中箭頭2和箭頭3所示).在地址轉換過程中，將會先檢索讀寫緩存映射表中是否有目標映射項，若找不到則才會檢索TPCS.當發(fā)生緩存失效時，TPCS內(nèi)原有的映射信息將被丟棄，然后再將需求的映射頁換入TPCS.

2) 讀緩存映射表R-CMT

讀緩存映射表(read cache mapping table,R-CMT)中存放的是只被讀請求訪問過的映射項，以LRU方式組織.由于閃存讀操作并不會改變映射信息，因此，讀緩存映射表的換出操作沒有映射項寫回開銷.當讀請求導致緩存失效且R-CMT滿時，將以LRU方式換出R-CMT的最后一個映射項.但是，當R-CMT中的映射項被寫請求命中時，由于映射項將被寫請求修改，因此需要將該映射項移動到HW-CMT中(如圖3中箭頭4所示).

3) 熱寫緩存映射表HW-CMT

HW-CMT以LRU鏈表的方式組織，鏈表中的每一個結點是一個映射項，并使用flag標記每個映射項的冷熱性質(zhì)，任何被命中的映射項都會被移動到HW-CMT的鏈表首部.同時，由于本文第3節(jié)闡明的原因，HW-CMT鏈表必須保證鏈表的末尾是一個熱映射項，否則將進行HW-CMT“剪枝”操作(pruning)，即HW-CMT末尾的冷映射項將被移動到DCW-CMT中(如圖3中箭頭5所示).有2種情況會觸發(fā)HW-CMT“剪枝”操作：1)當HW-CMT中最后一個熱映射項被命中時，由于該映射項會被移動到首部，因此此時最后一個映射項可能不是熱映射項；2)當HW-CMT中的冷映射項被命中時，會發(fā)生冷熱映射項的轉換，被命中的冷映射項會被轉換為熱映射項，此時，尾部的最后一個熱映射項將被轉換成冷映射項.

4) 冷臟寫緩存映射表DCW-CMT

DCW-CMT被分為若干個映射頁結點項(translation page node, TP-Node)，每個TP-Node內(nèi)的臟映射項屬于同一個映射頁，從HW-CMT中淘汰的冷臟映射項，會根據(jù)其所屬的映射頁號，放在其映射頁對應的TP-Node中.如果未找到，則會為其新建一個TP-Node.TP-Node內(nèi)的臟映射項按照該臟映射項進入DCW-CMT的時間順序排列.全部TP-Node以大頂堆的形式組織，大頂堆按照每個TP-Node內(nèi)的臟映射項數(shù)量為關鍵字進行排序，臟映射項數(shù)目最多的TP-Node會被放在大頂堆頂部.在需要進行臟映射項寫回時，將選擇頂部的TP-Node進行批量寫回(如圖3中箭頭8所示).通過這種方法，我們可以快速找到并優(yōu)先寫回擁有臟映射項最多的映射頁，最大化寫回閃存的映射項數(shù)量，從而降低臟映射項寫回而帶來的元數(shù)據(jù)更新代價.此外，根據(jù)負載的空間局部性原理，若某個TP-Node內(nèi)冷映射項較多，也意味著該TP-Node映射頁所代表的邏輯地址范圍的熱度出現(xiàn)下降，優(yōu)先寫回該映射頁，符合負載的空間局部性原理的要求.被批量更新后的臟映射項會變成非臟映射項并被移動至CCW-CMT中(如圖3中箭頭6所示).若DCW-CMT內(nèi)的映射項被寫請求命中，會被以冷映射項的形式移至HW-CMT首部(如圖3中箭頭7所示)，以便計算其近期的重用距離，給予其變成熱映射項的機會.

5) 冷非臟緩存映射表CCW-CMT

CCW-CMT存放的均是從DCW-CMT中被批量更新的映射項.在寫緩存映射表滿，需要進行換出時，優(yōu)先選擇CCW-CMT中的映射項換出，避免頻繁的臟映射項換出導致額外映射頁操作.若CCW-CMT內(nèi)的映射項被寫請求命中，基于第3節(jié)的原因，會被以冷映射項的形式移至HW-CMT首部(如圖3中箭頭7所示)，給予其變成熱映射項的機會，并由于寫操作再次成為臟映射項.

3.2 冷熱數(shù)據(jù)分離

通過寫緩存映射表冷熱分區(qū)方法可以有效區(qū)分重用距離較長的冷映射項和重用距離較短的熱映射項.由于元數(shù)據(jù)映射信息的頻繁使用，意味著其所對應的邏輯地址具有較高熱度，因此分離冷熱映射項對于分離寫入冷熱數(shù)據(jù)有重要意義.另一方面，重用距離較短的熱映射項能夠產(chǎn)生更多的無效頁，因此將重用距離相近的邏輯數(shù)據(jù)放在同一物理區(qū)域，使得同一物理塊內(nèi)的數(shù)據(jù)頁有更大概率在垃圾回收前被無效化，從而有效減少在閃存垃圾回收過程中需要進行的有效頁遷移次數(shù).因此，對于HW-CMT內(nèi)映射項對應邏輯地址的寫入操作，其數(shù)據(jù)將會被寫入到閃存的熱數(shù)據(jù)塊區(qū)中；對于CCW-CMT，DCW-CMT或R-CMT內(nèi)映射項對應的邏輯地址的寫入操作，將會被寫入到閃存的冷數(shù)據(jù)塊區(qū)中；由于垃圾回收時被回收塊內(nèi)的有效頁相對于被無效頁來說是相對熱度較低的數(shù)據(jù)頁，因此被回收塊內(nèi)的有效頁也將遷移至冷數(shù)據(jù)塊區(qū).

3.3 地址轉換過程

算法1展示了IRR-FTL的地址轉換過程.輸入是請求的邏輯頁地址和請求類型，經(jīng)過地址轉換過程后，請求被完成并且結束地址轉換過程.

算法1. IRR-FTL算法.

/*LPN:請求的邏輯頁號、Request_type:請求的操作類型*/

輸入：LPN,Request_Type.

① if (請求類型是讀請求)

② if (LPN在R-CMT或W-CMT中命中)

③ 在緩存找到對應物理地址并返回；

④ else if (LPN不在TPCS中)

⑤ 從閃存中將目標映射頁裝入TPCS；

⑥ end if

⑦ if (R-CMT已滿)

/*此時目標映射項在TPCS中，需要將目標映射項放入R-CMT*/

⑧ 根據(jù)LRU規(guī)則淘汰R-CMT的映射項；

⑨ end if

⑩ 從TPCS將目標映射項裝入R-CMT；

/*寫請求的邏輯地址觸發(fā)緩存失效*/

算法2展示了當寫緩存映射表滿時，如何選擇換出的映射項.當寫緩存映射表滿，需要換出映射項時會首先檢查CCW-CMT，由于非臟映射項的換出不需要執(zhí)行閃存寫回操作，因此優(yōu)先換出非臟映射項，能夠有效減少映射頁寫回操作次數(shù)；如果CCW-CMT為空，則會選擇DCW-CMT頂部的結點，對該結點對應的臟映射項鏈表進行批量更新，由于該結點內(nèi)的映射項最多，因此寫回更新代價相對較小.之后，將該鏈表插入CCW-CMT中，再換出最后一個映射項.

算法2. W-CMT_swap_out算法.

/*寫緩存映射項換出算法*/

① if (CCW-CMT≠?)

/*優(yōu)先從CCW-CMT中換出非臟映射項*/

② 按照LRU規(guī)則淘汰CCW-CMT中的映射項；

③ el se

/*若CCW-CMT≠?，則按照最大化批量更新策略，更新DCW-CMT大頂堆頂部的映射頁結點*/

④ 將DCW-CMT堆頂?shù)腡P_node中的映射項批量寫回閃存；

⑤ 更新GTD；

⑥ 將更新后的clean entries從DCW-CMT移動到CCW-CMT；

⑦ 換出CCW-CMT中最后一個映射項；

⑧ end if

算法3.Pruning_HW-CMT剪枝算法.

/*HW-CMT剪枝算法*/

① while(HW-CMT鏈表最后一個映射項不是冷映射項時)

② 將HW-CMT鏈表尾部所有的冷映射項移動到DCW-CMT；

③ end while

4 實驗與結果

4.1 實驗設置

本文實驗使用被廣泛運用在科研領域的開源閃存模擬器Flashsim[19]，我們在Flashsim上分別實現(xiàn)了基于緩存映射項重用距離的閃存轉換層地址映射算法IRR-FTL和DFTL算法，并將兩者進行比較.本文衡量系統(tǒng)有效性的主要指標包括系統(tǒng)響應時間、塊擦除次數(shù)、緩存命中率、映射頁的寫回次數(shù)、垃圾收集過程中拷貝的有效頁數(shù)量.

表1列出了本實驗中對閃存模擬器Flashsim的參數(shù)設置.考慮到標準負載數(shù)據(jù)集寫入數(shù)據(jù)總量的大小，本實驗模擬的SSD大小為2 GB，著重考查IRR-FTL對閃存垃圾回收性能的提高.

Table 1 Flash Memory Configuration表1 實驗閃存配置參數(shù)

表2列出了各個標準負載數(shù)據(jù)集的特點.本文分別使用多個具有不同特點的標準負載數(shù)據(jù)集進行實驗，以便能夠客觀評價本方法的有效性和普適性.

Table 2 Characteristics of Traces表2 標準數(shù)據(jù)集特征

實驗采用的標準負載數(shù)據(jù)集包括Financial1[20]，F(xiàn)inancial2[20]，MSR-mds[21]，MSR-prn[21]，Sysdisk，Video.其中，F(xiàn)inancial1和Financial2來自于SPC的金融型OLTP應用標準負載數(shù)據(jù)集.Financial1的特點是請求中寫操作比例較高，但是寫請求大小比較??；Financial2的特點是寫操作比例較低，請求的平均長度較小.MSR-mds和MSR-prn來自于微軟的企業(yè)級服務器數(shù)據(jù)集，特點是請求中寫操作比例較高，而且請求平均長度較大，連續(xù)寫入較多.數(shù)據(jù)集Sysdisk和Video是通過DiskMon工具，在本地計算機上收集的負載數(shù)據(jù)集.其中，Sysdisk是日常辦公的負載集，Video是網(wǎng)絡視頻負載集.

基于第3節(jié)的敘述，在本實驗中，通過動態(tài)調(diào)整熱數(shù)據(jù)項數(shù)量的方式，確保HW-CMT和冷寫緩存映射表的比例在1∶0.1到1∶0.5之間.

4.2 實驗結果及分析

實驗結果如圖4～8所示，下面將逐一分析各個指標的實驗結果.

圖4是不同負載下DFTL和IRR-FTL的緩存命中率比較.閃存緩存命中率直接影響閃存性能和壽命，若頻繁發(fā)生緩存失效，則需要進行更多的全局映射表讀操作和緩存映射項換出操作，而臟映射項的換出，又會導致閃存寫回操作，對閃存性能和壽命帶來負面影響.可以看到IRR-FTL相對于DFTL在不同負載下，緩存命中率均有較大提高.特別是在負載的平均請求大小較大的情況下，命中率表現(xiàn)更好.緩存命中率平均提高達29.1%.緩存命中率的提高主要得益于映射頁緩存槽和基于緩存映射項重用距離的冷熱寫緩存映射表，有效地吸收了連續(xù)讀寫請求，同時優(yōu)先換出冷映射項，延長熱映射項在緩存中保留的時間.

Fig. 4 Cache hit ratio under different workloads圖4 不同負載下的緩存命中率

Fig. 5 Number of valid pages under different workloads圖5 不同負載下的有效頁拷貝次數(shù)

垃圾收集過程中有效頁拷貝是閃存額外讀寫的重要來源，在垃圾收集過程中被回收塊內(nèi)的每一個有效頁都會引發(fā)1次閃存讀和閃存寫操作，還會引起由于有效頁遷移而導致的映射關系的改變.因此，減少垃圾收集過程中有效頁拷貝次數(shù)對優(yōu)化閃存數(shù)據(jù)寫放大和元數(shù)據(jù)寫放大有重要意義.圖5是不同負載下DFTL和IRR-FTL的垃圾收集過程中有效頁拷貝次數(shù)的比較，縱坐標表示的是歸一化的垃圾收集過程中有效頁拷貝次數(shù).可以看到，IRR-FTL有效地減少了垃圾收集過程中有效頁拷貝次數(shù)，平均降低了39.9%的有效頁拷貝次數(shù).特別在MSR-mds負載上，由于MSR-mds負載的邏輯地址冷熱性質(zhì)較為清晰，因此冷熱數(shù)據(jù)分離效果更好，有效頁拷貝次數(shù)下降了88.5%.

由于臟映射項換出而導致的閃存映射頁操作是元數(shù)據(jù)寫放大的重要來源.圖6是在不同負載下DFTL和IRR-FTL由于臟映射項換出而導致的閃存映射頁寫回操作數(shù)量，縱坐標是歸一化的閃存寫回次數(shù).可以看到，在不同負載環(huán)境下，IRR-FTL比DFTL平均減少了70.8%的額外閃存寫回次數(shù).特別在MSR-prn，Sysdisk，Video等平均請求較大的負載場景下，IRR-FTL減少了80%以上的映射項寫回操作.能夠取得上述優(yōu)良的效果，得益于冷寫緩存映射表的非臟映射項優(yōu)先換出策略和臟映射項最大化批量更新策略，實驗證明這都能夠有效減少由于臟映射項換出而導致的閃存寫回操作，同時減少對緩存命中率的影響.

Fig. 6 Number of translation page write back圖6 不同負載下的映射頁寫回次數(shù)

Fig. 7 Average response time under different workloads圖7 不同負載下的系統(tǒng)響應時間

系統(tǒng)平均響應時間是衡量閃存性能的重要指標.圖7展示了各個不同負載下IRR-FTL和DFTL的系統(tǒng)平均響應時間的對比，其中縱坐標表示歸一化的系統(tǒng)平均響應時間.可以看出，得益于在緩存命中率、垃圾回收效率、元數(shù)據(jù)寫放大等指標上的優(yōu)異表現(xiàn)，IRR-FTL較DFTL系統(tǒng)平均響應時間降低了27.3%.

塊擦除次數(shù)是衡量閃存壽命的重要指標.圖8展示了各個不同負載下，IRR-FTL和DFTL的塊擦除次數(shù)的對比，其中，縱坐標是歸一化的塊擦除次數(shù).可以看到，由于在垃圾回收時遷移有效頁數(shù)量的減少和元數(shù)據(jù)映射項寫回次數(shù)的減少，從而盡可能的減少閃存中發(fā)生的不必要的數(shù)據(jù)遷移和元數(shù)據(jù)同步.相應的在擦除次數(shù)上，IRR-FTL較DFTL平均降低了約10.7%，有效地減少了閃存內(nèi)部發(fā)生的額外寫入次數(shù)，提高了閃存壽命.

Fig. 8 Erase times under different workloads圖8 不同負載下的塊擦除次數(shù)

在IRR-FTL中，空間開銷主要來源于每一個映射項會增加1個冷熱標志位，這個標志位僅占用1 b空間.按每個映射項8 B計算，每個映射項增加1 b大小，則需要額外空間占原大小的1.5%.此外，DCW-CMT中的大頂堆中每個結點都有一個映射項數(shù)量計數(shù)器，而大頂堆中的結點數(shù)隨著負載的變化而動態(tài)分配與釋放，因此占用空間大小并不確定.但是，根據(jù)負載的空間局部性原理可以推斷負載某時間段內(nèi)訪問涉及的TP-Node數(shù)量有限，同時以TP-Node映射頁為單位的批量更新策略也可以有效更新和控制DCW-CMT中的TP-Node.

5 總 結

本文提出一種基于緩存映射項重用距離的閃存轉換層地址映射方法IRR-FTL.針對DFTL中存在的對負載的空間局部性利用不強、頻繁映射頁寫回和垃圾回收導致的寫放大等問題，通過設置獨立映射頁緩存槽，充分挖掘負載的空間局部性.通過基于緩存映射項重用距離的負載自適應寫緩存映射表冷熱分區(qū)方法，將寫緩存映射表分為熱寫緩存映射表和冷寫緩存映射表，并將不同區(qū)域內(nèi)映射項對應的冷熱數(shù)據(jù)分別寫入閃存不同區(qū)域，實現(xiàn)冷熱數(shù)據(jù)分離，減少數(shù)據(jù)寫放大；同時對于冷寫緩存映射表，采取臟映射項最大化批量更新和非臟映射項優(yōu)先換出策略，減少元數(shù)據(jù)寫放大.在實驗部分，本文通過多個不同負載類型數(shù)據(jù)集，驗證IRR-FTL的有效性，結果證明IRR-FTL較DFTL緩存命中率提高29.1%，同時減少了39.9%的由于垃圾回收造成的額外讀寫操作和70.8%的映射頁寫回操作，使得整體系統(tǒng)響應時間降低了27.3%，擦除次數(shù)降低了10.7%.

[1]Lu Youyou, Shu Jiwu. Survey on flash-based storage systems[J]. Journal of Computer Research and Development, 2013, 50(1): 49-59 (in Chinese)

(陸游游, 舒繼武. 閃存存儲系統(tǒng)綜述[J]. 計算機研究與發(fā)展, 2013, 50(1): 49-59)

[2]Chen Feng, Koufaty D A, Zhang Xiaodong. Understanding intrinsic characteristics and system implications of flash memory based solid state drives[C] //Proc of the 35th ACM SIGMETRICS Int Conf on Measurement and Modeling of Computer Systems. New York: ACM, 2009: 181-192

[3]Agrawal N, Prabhakaran V, Wobber T, et al. Design tradeoffs for SSD performance[C] //Proc of the 19th USENIX Annual Technical Conference(ATC). Berkeley, CA: USENIX Association, 2008: 57-70

[4]Ma Dongzhe, Feng Jianhua, Li Guoliang. A survey of address translation technologies for flash memories[J]. ACM Computing Surveys, 2014, 46(3): 238-276

[5]Gupta A, Kim Y, Urgaonkar B. DFTL: A flash translation layer employing demand-based selective caching of page-level address mappings[C] //Proc of the 14th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2009: 229-240

[6]Grupp L M, Davis J D, Swanson S. The bleak future of NAND flash memory[C] //Proc of the 10th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2012: 17-24

[7]Ma Dongzhe, Feng Jianhua, Li Guoliang. LazyFTL: A page-level flash translation layer optimized for nand flash memory[C] //Proc of the 30th ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2011: 1-12

[8]Zhang Qi, Wang Linzhang, Zhang Tian, et al. Optimized address translation method for flash memory[J]. Journal of Software, 2014, 25(2): 314-325 (in Chinese)

(張琦, 王林章, 張?zhí)? 等. 一種優(yōu)化的閃存地址映射方法[J]. 軟件學報, 2014, 25(2): 314-325)

[9]Zhou You, Wu Fei, Huang Ping, et al. An efficient page-level FTL to optimize address translation in flash memory[C] //Proc of the 10th European Conf on Computer Systems. New York: ACM, 2015: 227-242

[10]Yao Yingbiao, Du Chenjie, Wang Fakuan. A clustered page-level flash translation layer algorithm based on classification strategy[J]. Journal of Computer Research and Development, 2017, 54(1): 142-153 (in Chinese)

(姚英彪, 杜晨杰, 王發(fā)寬. 一種基于分類策略的聚簇頁級閃存轉換層算法[J]. 計算機研究與發(fā)展, 2017, 54(1): 142-153)

[11]Kim J, Kim J M, Noh S H. A space-efficient flash translation layer for compactflash systems[J]. IEEE Trans on Consumer Electronics, 2002, 48(2): 366-375

[12]Lee S W, Park D J, Chung T S. A log buffer-based flash translation layer using fully-associative sector translation[J]. ACM Trans on Embedded Computing Systems, 2007, 6(3): 70-96

[13]Jung D, Kang J U, Jo H, et al. Superblock FTL: A superblock-based flash translation layer with a hybrid address translation scheme[J]. ACM Trans on Embedded Computing Systems, 2010, 9(4): 658-673

[14]Lee S, Shin D, Kim Y J, et al. LAST: Locality-aware sector translation for NAND flash memory-based storage systems[J]. ACM SIGOPS Operating Systems Review, 2008, 42(6): 36-42

[15]Lee H S, Yun H S, Lee D H. HFTL: Hybrid flash translation layer based on hot data identification for flash memory[J]. IEEE Trans on Consumer Electronics, 2009, 55(4): 2005-2011

[16]Park D, Du D. Hot data identification for flash-based storage systems using multiple bloom filters[C] //Proc of the 27th IEEE Symp on Mass Storage Systems and Technologies (MSST). Los Alamitos, CA: IEEE Computer Society, 2011: 1-11

[17]Xie Wei, Chen Yong, Roth P. ASA-FTL: An adaptive separation aware flash translation layer for solid state drives[J]. Parallel Computing, 2016, 61: 3-17

[18]Jiang Song, Zhang Xiaodong. LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance[C] //Proc of the 28th ACM SIGMETRICS Int Conf on Measurement and Modeling of Computer Systems. New York: ACM, 2002: 31-42

[19]Kim Y, Tauras B, Gupta A, et al. Flashsim: A simulator for NAND flash-based solid-state drives[C] //Proc of the 1st Int Conf on Advances in System Simulation. Los Alamitos, CA: IEEE Computer Society, 2009: 125-131

[20]Liberate M, Shenoy P. OLTP trace from umass trace repository[EB/OL]. [2016-12-19]. http://traces.cs.umass.edu/index.php/Storage

[21]Microsoft. MSR cambridge traces[EB/OL]. [2016-12-19]. http://iotta.snia.org/traces/388