Learning Memory Access Patterns，資料庫＋機器學習探索

資料庫系統中，數據訪問特徵直接影響到索引、冷熱數據分離機制的效率。如果能根據歷史SQL訪問特徵，準確預測出接下來哪些數據會被訪問，便可提前將數據從低速介質(SSD/HHD)遷移至高速介質(Memory/CPU Cache)，從而縮短數據訪問時延。同時識別出數據冷熱特徵之後後，可以根據數據的冷熱特點來構建索引，進一步提高整體性能。

前言

阿里巴巴集團業務的數據訪問具有典型的冷熱特徵。以交易場景為例，數據訪問的熱點分布十分明顯並隨時間推移。對於一條新插入的記錄，在接下來7天內被訪問到的概率高達99%，而在7天之後的訪問概率非常低。對於熱點數據，現有的機制是通過LRU或者Clock等策略在內存中維護一塊緩衝區，所有的讀操作都會首先訪問緩衝區，沒有命中的話再去磁碟中讀取，然後將數據緩存在緩衝區中。這種策略的缺點在於無法捕捉到更為複雜的數據訪問特徵，數據訪問特徵的記憶窗口等於緩衝區的大小，因此當數據的訪問特徵較為複雜，需要更長的窗口才能捕捉到特徵時，就會造成較多的cache miss，從而使資料庫性能產生抖動。

《Learning Memory Access Patterns》提出了使用深度學習訓練得到prefetcher，通過對內存訪問的物理地址進行建模，使用RNN來捕捉內存訪問的較為複雜的時序特徵。Learned Prefetcher和傳統的硬體Prefetcher相比具有更高的準確率和召回率。雖然論文中的Learned Prefetcher基於靜態數據進行訓練，而且對動態更新RNN模型給系統正常事務帶來的資源競爭也沒有給出很好的解決方案，要在工業界落地還有很長的路要走，但是本文提出的使用深度學習訓練的模型來替代傳統模型的思想和近期的《The Case for Learned Index Structures》不謀而合，對人工智慧和資料庫結合這一新興領域具有重要的啟發意義。這篇文章對於X-Engine後續的智能冷熱數據識別以及分離機制的設計也有很大的借鑒意義。

Prefetcher

Prefetcher是一種能夠根據歷史內存訪問的特點來預測未來內存訪問的硬體結構，主要分為以下兩種類別：

1.Strider prefetcher，記錄訪問地址的差別 (delta table) 來發現簡單的訪問規律，給定四個時間點程序訪問的物理地址 (0, 4, 8, 12)， 那麼Strider prefetcher會預測接下來可能訪問的物理地址為 (16, 20, 24)，並將其prefetch到內存中；

2.Correlation prefetcher，相比於Strider prefetcher只能捕捉到簡單的內存訪問特徵，Correlation prefetcher則會通過保存長時間的歷史訪問記錄來分析得到更加複雜的內存訪問特徵，代表性的實現有 Markov prefetchers，GHB prefetchers等，由於這種prefetcher需要較大的內存的空間來存儲訪存記錄表，一般的現代處理器不會採用這種prefetcher實現。

RNN(Recurrent Neural Network)

適用於序列預測的問題（sequential prediction），諸如語音識別、自然語言處理等依賴較長歷史維度數據來進行特徵抽取的問題都比較適合RNN來處理。

LSTM （Long-Short Term Memory）是RNN的一種變種實現，LSTM通過增加了遺忘單元和使用加法替代乘法進行中間狀態的傳輸，解決了原始RNN中梯度消失的問題。

Prefetch 模型

定義Prefetch對應的ML模型：根據歷史的內存訪問記錄，預測未來哪些內存訪問會命中cache，又有哪些訪問會造成cache miss。 一個程序編譯後包含很多機器指令，其中的訪存指令（load/store）會導致內存訪問。

特徵，PC (PC Counters) (64-bit) ，cache miss 地址 (64-bit)

回歸問題， 直接預測下一個cache miss的物理地址。巨大的物理地址空間帶來稀疏性問題，在實驗中出現O(10M) block cache miss， 然而物理地址空間為2^64，對於NN而言，首先會對輸入的特徵進行歸一化，然而浮點數的表示精度會導致信息損失。

多分類問題，預測每一個地址成為下一次cache miss的概率，從中選取top K作為prefetch的對象。

稀疏性問題，即使在page level進行預測也會有2^52個概率值 (softmax targets)

程序的運行具有局部性的特點，根據training data中程序經常訪問的物理地址作為目標預測值，忽略其他的物理空間地址->Embedding LSTM

首先對cache miss的地址進行聚類，然後對於每一個類別分別訓練LSTM，使用LSTM ID作為bias將所有的訓練器關聯起來->Clustering + LSTM

地址空間布局的隨機性（ASLR），相同的代碼段運行多次會產生不同的物理地址訪問

預測cache miss 地址的變化值（delta）而不是實際地址

Learned Prefetcher

1.Embedding LSTM

多次出現的delta子集（vocabulary）作為feature，訓練集的大小為O(1000)。

在第N時刻，PC和cache miss 的 detla作為feature輸入

embedding後concatenate起來作為input，傳入2-layer LSTM

LSTM預測出來Top K個delta作為prefetching的候選集

Tradeoff： 預取多個預測值會增加下個時刻的cache命中概率，但由於cache大小有限，有可能把有用的page置換出去 論文中設置為prefetch top 10的物理地址

Limitations： vocabulary大小決定了模型的複雜度 對於vocabulary進行剪枝損害了模型的效果 對於較少出現的delta值的處理是一個難點。

2.Clustering + LSTM

可行性：對於一段程序而言，大部分地址空間的訪問都存在局部性（結構體、數組都被存放在連續的地址空間），因此對於局部地址空間進行建模可能會取得較好的prefetch效果。

聚類可視化，在omnetpp benchmark上對於（PC, address）進行聚類，聚類之後delta變小。

Clustering + LSTM的架構如下圖所示，所有特徵進行聚類後經過local LSTM的訓練得到最後的預測結果，這裡仍然採用分類問題的解決方案，如果使用回歸演算法，denomarlization後會造成預測地址的精度損失。

兩種模型的比較

Clustering + LSTM 模型將整個LSTM拆分成幾個較小的local model，在每一個region的delta都在一個量級，可以normalize後直接作為LSTM的輸入，大大降低了embedding matrix的維度。

Clustering + LSTM 模型著重local LSTM的建模，然後通過Cluster ID作為bias將所有的local model 松耦合起來進行訓練，和Embedding LSTM相比，對於整體的模型建模（程序對於不同region的動態訪問）表達能力不足。

實驗

實驗準備

Pin 工具提供了對於指定進程生成 （PC, Virtual Address）的功能；

我們關注只關注cache miss的情況，根據Pin生成的內存訪問軌跡，使用cache simulator來得到cache miss的地址序列；

數據集： memory intensive application：SPEC CPU2006 Google』s web search workload

評價指標： precision recall

模型比較： stream prefetcher GHB PC/DC prefetcher Embedding LSTM Clustering + LSTM

Precision

從準確率來看，Learned Prefetcher模型都要優於傳統的Prefetcher

Clustering + LSTM 和 Embedding在準確率評價指標上各有千秋

Delta 屬性對於準確率的提升貢獻較大

從召回率來看，Clustering + LSTM要更勝一籌

PC 特徵對於提高召回率有一定的幫助

特徵相似的程序代碼有更高的概率聚集到同一類別（循環、指針的解引用），通過數據的訪問的特徵來更好地理解程序的設計。

未來工作

集成學習（Ensemble Learning）。文中的兩種RNN模型準確率相近，但是設計的架構卻有很大區別，通過集成學習的方法將這兩種模型進行融合，理論上可以得到更好的learned prefetcher；

動態模型的實際（Adaptive RNN）。Learned Prefetch會提高cache的命中率，但是也會不可避免的改變cache miss的分布，需要考慮adaptive RNN網路的設計以及動態改變網路模型對於系統正常事務處理性能的影響；

Prefetch的時機設計。如果prefetch過早，那麼page可能還未被命中就會被置換出去，如果prefetch過晚，又會影響cache的命中率，可能的解決方案是預測未來多個時間點的cache miss而不是僅僅預測next step；

總結

隨著資料庫系統結構和數據訪問特徵越來越複雜，基於經驗和規則的模型可能無法真正最優化資料庫的性能。AI和DB的結合，是通過海量數據學習數據的潛在特徵，然後再反哺資料庫，優化資料庫的設計。無論是將資料庫看做黑盒，使用機器學習的演算法學習最優的參數配置，還是將AI演算法真正融合到資料庫系統當中，替代傳統的模型，都是對傳統資料庫領域的革命性創新。雖然目前AI和DB的結合在模型的動態調整，預測誤差等方面還存在難點，離工業落地還有距離，但仍然是一個非常值得研究的領域。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！