從刷臉打卡到各種應(yīng)用的 “猜你喜歡”，當(dāng)前機(jī)器學(xué)習(xí)（特別是深度學(xué)習(xí)技術(shù)）已經(jīng)廣泛應(yīng)用于我們?nèi)粘Ｉ畹姆椒矫婷妗Ｉ疃葘W(xué)習(xí)框架（如：TensorFlow，PyTorch等）和 AI專用芯片（如：TPU、NPU等）等軟硬件系統(tǒng)的設(shè)計(jì)極大地提升了機(jī)器學(xué)習(xí)的性能并擴(kuò)展了其應(yīng)用場(chǎng)景。與此同時(shí)，機(jī)器學(xué)習(xí)方法本身可否用于優(yōu)化計(jì)算機(jī)系統(tǒng)設(shè)計(jì)甚至是取代傳統(tǒng)設(shè)計(jì)模式呢？谷歌技術(shù)大神Jeff Dean領(lǐng)導(dǎo)的研究小組在2018年的SIGMOD學(xué)術(shù)會(huì)議上發(fā)表了一個(gè)有趣的工作：The Case for Learned Index   Structures [1]   。本文簡(jiǎn)要介紹了Learned Index Structures的實(shí)現(xiàn)和優(yōu)缺點(diǎn)，希望可以給大家?guī)?lái)一些系統(tǒng)設(shè)計(jì)的啟發(fā)和思路。

一、什么是 Learned Index Structures？

Index（索引）是數(shù)據(jù)庫(kù)、文件系統(tǒng)等領(lǐng)域常見的數(shù)據(jù)結(jié)構(gòu)，最經(jīng)典的莫過(guò)于B-Tree。B-Tree是一種范圍索引（Range Index）數(shù)據(jù)結(jié)構(gòu)，查詢時(shí)給定一個(gè)key（或一些確定范圍的keys），B-Tree會(huì)索引到包含該key的對(duì)應(yīng)范圍的葉子節(jié)點(diǎn)，在葉子節(jié)點(diǎn)內(nèi)對(duì)key進(jìn)行搜索。如果該key在索引中存在，就會(huì)得到其對(duì)應(yīng)的位置。一般在一個(gè)邏輯頁(yè)內(nèi)的記錄會(huì)用一個(gè)key來(lái)索引。如圖1（a）所示，輸入是一個(gè)key，輸出是對(duì)應(yīng)要查詢記錄的位置區(qū)間。除了范圍索引，還有點(diǎn)索引（Point Index）如：哈希表（Hash Map），和存在索引（Existence Index）如：Bloom Filters，也都是常用的索引數(shù)據(jù)結(jié)構(gòu)。Learned Index Structures的主要思想是將這里B-Tree或是Bloom Filters等數(shù)據(jù)結(jié)構(gòu)替換為機(jī)器學(xué)習(xí)的模型——查找操作變成了根據(jù)key做索引數(shù)據(jù)位置的預(yù)測(cè)，如圖1（b）所示。我們以范圍索引為例，來(lái)詳細(xì)介紹下Learned Index Structures的設(shè)計(jì)和實(shí)現(xiàn)思路。

圖 1 B-Tree和Learned Index示意圖

圖 1就是一個(gè)傳統(tǒng)B-tree和Learned Index的對(duì)比。可以看到，Learned Index的輸入是Key，輸出是這個(gè)key對(duì)應(yīng)的檢索結(jié)果的位置（可能有誤差），誤差的上限是葉子節(jié)點(diǎn)一個(gè)數(shù)據(jù)頁(yè)中的結(jié)果條目（即所需檢索結(jié)果在數(shù)據(jù)頁(yè)的末尾）。

那么針對(duì)范圍索引，如何設(shè)計(jì)機(jī)器學(xué)習(xí)的模型呢？這里只考慮一維聚簇索引的情況（即數(shù)據(jù)是按照用于查找的 key來(lái)排序的，非聚簇索引可以通過(guò)聚簇索引加一層到真實(shí)數(shù)據(jù)排列的指針實(shí)現(xiàn)），Learned Index Structures很巧妙的給出了如圖2所示的洞察，索引位置實(shí)際上是隨著Key增長(zhǎng)而增長(zhǎng)的單調(diào)遞增函數(shù)。雖然具體的索引可能是離散的,整體上還是可以用一個(gè)函數(shù)來(lái)描述：

p = F(Key) * N

其中， p是估計(jì)得到的位置，N是索引Key的數(shù)量，F(xiàn)(key)是索引數(shù)據(jù)的累計(jì)分布函數(shù)（CDF）。F（key）的含義是小于等于key的索引數(shù)據(jù)條目總和（即key的位置估計(jì)）。本質(zhì)上體現(xiàn)了數(shù)據(jù)集的分布特征。相比B-Tree的通用設(shè)計(jì)，Learned Index Structures考慮了數(shù)據(jù)集的內(nèi)在分布特點(diǎn)并將其用于優(yōu)化索引的結(jié)構(gòu)。Learned Index誤差上限可控，只需要在誤差范圍內(nèi)根據(jù)預(yù)測(cè)的位置向左或向右二分查找即可準(zhǔn)確找到查找目標(biāo)。

圖 2 索引位置的累計(jì)概率分布（CDF）

那么如何學(xué)習(xí)得到 F(Key) 呢？ Learn Index Structures作者首先嘗試了用TensorFlow搭建一個(gè)每層32個(gè)神經(jīng)元，兩層全連接的神經(jīng)網(wǎng)絡(luò)，使用一個(gè)web server日志的數(shù)據(jù)集訓(xùn)練后發(fā)現(xiàn)效果遠(yuǎn)差于B-Tree。問(wèn)題在于：

1）TensorFlow是用于大規(guī)模神經(jīng)網(wǎng)絡(luò)的訓(xùn)練的，小規(guī)模場(chǎng)景的調(diào)用開銷變得不可忽視。

2）欠擬合問(wèn)題，如圖2所示機(jī)器學(xué)習(xí)模型可以很好的估計(jì)CDF的整體趨勢(shì)，但在單一數(shù)據(jù)項(xiàng)上很難得到精確的表示。而B-Tree可以簡(jiǎn)單高效的使用if語(yǔ)句精確劃分范圍，為了優(yōu)化“最后一公里” 機(jī)器學(xué)習(xí)模型要付出較大的存儲(chǔ)空間和計(jì)算資源消耗。

3）B-Tree的CPU和cache行為是經(jīng)過(guò)高度優(yōu)化設(shè)計(jì)的，每次查找只需使用少量索引。機(jī)器學(xué)習(xí)模型則需要使用全部參數(shù)權(quán)重完成一次預(yù)測(cè)。

最終 Learn Index Structures的模型使用了如圖3所示的Staged Model實(shí)現(xiàn)。每一個(gè)Model都可以是任意一個(gè)機(jī)器學(xué)習(xí)模型，從最簡(jiǎn)單的線性回歸（LR）到深度神經(jīng)網(wǎng)絡(luò)（DNN）都可以。實(shí)踐中，越簡(jiǎn)單的模型越好（避免查找時(shí)在模型上花太多時(shí)間）。當(dāng)進(jìn)行查找時(shí)，最上層的模型（只有一個(gè)模型），將選擇一個(gè)第二層的模型來(lái)處理這個(gè)key。然后第二層的模型，會(huì)接著選擇一個(gè)下一層的模型來(lái)處理這個(gè)key，直到最底層的模型，才會(huì)給出這個(gè)key對(duì)應(yīng)的預(yù)測(cè)位置。但實(shí)際上上層每個(gè)模型輸出的都是預(yù)測(cè)位置，這個(gè)預(yù)測(cè)被用于選擇下層模型（模型id = (預(yù)測(cè)位置 / 記錄總數(shù)) * 該層模型數(shù)）。

整個(gè) Staged Model分層訓(xùn)練，先訓(xùn)練最頂層，然后進(jìn)行數(shù)據(jù)分發(fā)。數(shù)據(jù)分發(fā)指的是，上層模型將key預(yù)測(cè)到哪個(gè)下層Model，該Model就擁有這條訓(xùn)練數(shù)據(jù)作為他的訓(xùn)練集。所以隨著層數(shù)的加深，以及每一層模型數(shù)量的提升，每個(gè)越底層模型擁有的訓(xùn)練數(shù)據(jù)是越少的。這樣的優(yōu)點(diǎn)是，底層模型可以非常容易的擬合這一部分?jǐn)?shù)據(jù)的分布（缺點(diǎn)是較少的數(shù)據(jù)量帶來(lái)了模型的選擇限制，復(fù)雜模型沒(méi)法收斂）。[1]中采用的結(jié)構(gòu)是：只在頂層使用神經(jīng)網(wǎng)絡(luò)模型，在其余層使用線性回歸模型。

圖 3 用于Learned Index Structures的Staged Model

點(diǎn)索引和存在索引的 Learned Index Structure 這里不再一一贅述，感興趣的話可以閱讀論文[1]，以及基于論文實(shí)現(xiàn)的RMI（Recursive Model Indexes）代碼[2]。

二、如何評(píng)價(jià)Learned Index Structures？

總的來(lái)說(shuō)，Learned Index Structures向我們展示了機(jī)器學(xué)習(xí)在系統(tǒng)領(lǐng)域的巨大潛力，但還存在諸多待解決的問(wèn)題（如：過(guò)擬合、索引的增刪改等問(wèn)題）。對(duì)于過(guò)擬合，若新索引的key依然滿足CDF則并不需要重新訓(xùn)練，直接insert到預(yù)測(cè)出來(lái)的位置即可。若數(shù)據(jù)分布會(huì)發(fā)生變化，則需要嘗試在線學(xué)習(xí)（Online learning）的方法。對(duì)于數(shù)據(jù)更新頻繁的系統(tǒng)，可采用delta-index技術(shù)增量更新learned index。

實(shí)際上，以Learned Index Structures為代表的機(jī)器學(xué)習(xí)優(yōu)化方法并不是系統(tǒng)設(shè)計(jì)優(yōu)化的終結(jié)者。比如spline B-tree [6] 使用B-tree的每個(gè)葉子節(jié)點(diǎn)只存一個(gè)spline（即key和其位置），兩個(gè)spline之間的數(shù)據(jù)用兩點(diǎn)之間的直線來(lái)預(yù)測(cè)。這樣一個(gè)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，很多時(shí)候效果相當(dāng)于復(fù)雜的Learn Index，甚至更好。在Point Index 領(lǐng)域，Learned Index通過(guò)減少?zèng)_突實(shí)現(xiàn)的優(yōu)化可以被bucketized cuckoo hashing [7] 輕松打敗，該方法只是簡(jiǎn)單的將每個(gè)key同時(shí)hash到兩個(gè)bucket而已。

但這并不能否定機(jī)器學(xué)習(xí)在系統(tǒng)設(shè)計(jì)上的 價(jià)值，通過(guò)機(jī)器學(xué)習(xí)可以啟發(fā)系統(tǒng)設(shè)計(jì)的優(yōu)化和思考，探索出之前未曾發(fā)現(xiàn)的系統(tǒng)設(shè)計(jì)思路。在優(yōu)化原理清晰、場(chǎng)景固定的情況下，顯然由人加以解釋和重新實(shí)現(xiàn)在效率和穩(wěn)定性上更勝機(jī)器學(xué)習(xí)方法一籌。在數(shù)據(jù)分布等特征動(dòng)態(tài)變化的場(chǎng)景，機(jī)器學(xué)習(xí)方法 可以針對(duì)性優(yōu)化和適應(yīng)數(shù)據(jù)特征，理論上可以優(yōu)于通用的算法和數(shù)據(jù)結(jié)構(gòu)。

三、機(jī)器學(xué)習(xí)+系統(tǒng)設(shè)計(jì) = ？

也許Learned Index Structures還存在很多不足，但無(wú)法忽略的是將機(jī)器學(xué)習(xí)應(yīng)用于計(jì)算機(jī)系統(tǒng)設(shè)計(jì)的趨勢(shì)已經(jīng)到來(lái)。如果說(shuō)Learn Index Structures是機(jī)器學(xué)習(xí)打入計(jì)算機(jī)系統(tǒng)設(shè)計(jì)領(lǐng)域的一聲炮響，2019年發(fā)布的機(jī)器學(xué)習(xí)系統(tǒng)白皮書  [5]  就是正式確立了機(jī)器學(xué)習(xí)和計(jì)算機(jī)系統(tǒng)設(shè)計(jì)交叉研究方向的誕生。如Jeff Dean在SysML18會(huì)議上主旨演講所言：“使用啟發(fā)式技術(shù)的任何系統(tǒng)領(lǐng)域，都是可能應(yīng)用機(jī)器學(xué)習(xí)的好地方——編譯器、網(wǎng)絡(luò)、操作系統(tǒng)、芯片設(shè)計(jì)等”。要取得成功，關(guān)鍵點(diǎn)有兩個(gè)：

1) 找到一個(gè)能用數(shù)字精確表示的優(yōu)化指標(biāo)；

2) 有一個(gè)集成機(jī)器學(xué)習(xí)的清晰接口（模型的輸入輸出定義，訓(xùn)練、測(cè)試數(shù)據(jù)集的獲取等）。

對(duì)于計(jì)算機(jī)系統(tǒng)領(lǐng)域的優(yōu)化，這兩個(gè)要求似乎是比較容易實(shí)現(xiàn)的。