田冰，華中科技大學計算機系統(tǒng)結(jié)構(gòu)專業(yè)22級在讀博士生
VStore: in-storage graph based vector search accelerator
https://dl.acm.org/doi/abs/10.1145/3489517.3530560
今天要介紹的題目是“可計算存儲架構(gòu)下的大規(guī)模近似最近鄰搜索研究”。隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，我們都知道互聯(lián)網(wǎng)上的數(shù)據(jù)量現(xiàn)在是呈著爆炸式的增長，這一增長的趨勢極大地促進了大數(shù)據(jù)和人工智能的蓬勃發(fā)展。雖然在摩爾定律的指導下，我們 CPU 的性能是不斷增強，但是存儲器的發(fā)展卻遠遠落后于CPU，這就導致了我們所謂的馮諾依曼瓶頸的問題。加之我們大數(shù)據(jù)應用需要對海量的數(shù)據(jù)進行處理，導致我們計算單元對存儲的訪問越來越多。近年來由于閃存技術(shù)的不斷進步，閃存的內(nèi)部的帶寬不斷地增加，但是閃存和主機之間的 I/O 接口，它的速度實際上是遠遠低于SSD 就是閃存的內(nèi)部的帶寬的。這些趨勢就意味著日益嚴重的馮諾依曼瓶頸問題，需要一個新的提議結(jié)構(gòu)。
那么什么是馮諾依曼瓶頸？我們都知道傳統(tǒng)的計算機架構(gòu)是以計算為中心，是計算與存儲分離，如果想要計算的話，就是存儲器先把它的數(shù)據(jù)給傳輸給計算器再進行計算。我們前面也提到了，現(xiàn)在的 CPU 的性能是不斷地提高，存儲器的容量也不斷的增大，但是它們之間的數(shù)據(jù)傳輸卻存在著一個很大的問題。第一個問題是首先是數(shù)據(jù)的傳輸速度是比較慢的，因為在存儲內(nèi)存儲器內(nèi)部，它海量的數(shù)據(jù)都需要經(jīng)過系統(tǒng)的這個 I/O 的總線，就是處理器和存儲器之間的數(shù)據(jù)總線，然后之后才能傳輸給CPU。然后其次是數(shù)據(jù)傳輸?shù)囊粋€能耗比較大。那么對于像人工智能還有圖計算這種 I/O 密集型的應用來說，數(shù)據(jù)搬運的能耗其實是遠遠大于我們 CPU 計算的一個能耗的。那么為了解決我們現(xiàn)有的這樣一種馮諾依曼的瓶頸，現(xiàn)在是去中心化的領(lǐng)域?qū)Ｓ眉軜?gòu)正在迅速的一個發(fā)展的趨勢。這樣一個架構(gòu)是利用各種高性能的一個處理單元，然后來對數(shù)據(jù)按照狀態(tài)來進行處理，實現(xiàn)一個數(shù)量級的性能提升，并且更低的一個功耗。比如說現(xiàn)在我們都知道的GPU，然后 TPU，還有 NPU 。這些是主要是數(shù)據(jù)在使用的時候我們?nèi)プ鲇嬎?，比如訓練神?jīng)網(wǎng)絡這些東西。我們這次活動的主辦方他們做的這個類腦計算，還有這個 PIM 就是存內(nèi)計算，就是內(nèi)存內(nèi)計算，然后也在快速地發(fā)展。此外數(shù)據(jù)我們在傳輸?shù)臅r候，我們都知道是CPU，在它要對網(wǎng)絡的包進行一個處理，這個處理任務負擔還是比較大的?？捎嬎愦鎯褪腔谝苿佑嬎惚纫苿訑?shù)據(jù)更高效的思想，在數(shù)據(jù)存儲的地方來做計算，這樣可以充分利用我們存儲器內(nèi)部的帶寬，來減少因數(shù)據(jù)移動它帶來的開銷。
這里我引用了存儲與網(wǎng)絡協(xié)會對可計算存儲的定義，它是一種能夠提供與存儲僅耦合的可以計算的功能，就是賦予存儲器一定的計算資源，將 CPU的一部分計算任務給卸載到存儲器內(nèi)部，來減少數(shù)據(jù)移動的開銷。這里是兩個可計算存儲的通用架構(gòu)，那么左邊是 off-path的一個架構(gòu)，就是說我存儲器內(nèi)部的控制器不僅處理普通的 I/O 的命令，而且還處理我們要卸載的可以計算的函數(shù)功能，就是數(shù)據(jù)的通路都是在一條路上。然后第二種就是 off-path的架構(gòu)。這種是在存儲器內(nèi)部來，就是單獨集成一個可以計算的 FPGA 的計算芯片，然后這個FPGA 計算芯片和存儲器連接。
這是宏觀上傳統(tǒng)架構(gòu)與可計算存儲架構(gòu)加持的一個進數(shù)據(jù)處理的對比。所以就是每個存儲器的內(nèi)部我們都可以進行計算了。之后我們就可以對存儲器內(nèi)部添加一些比如說數(shù)據(jù)庫的過濾的操作，或者說一些數(shù)據(jù)檢索的相關(guān)功能，并且由于我們有了可計算存儲之后，它的擴展機制并不會受到這個 I/O 總線的限制，因為每次擴展的話，它實際上是都是利用了內(nèi)部的帶寬。
回到今天要分享的這篇文章，就是通過利用前面講的可計算存儲設備對基于圖的向量搜索，做了一個加速器。這篇文章是發(fā)表在 22 年的芯片領(lǐng)域的頂會 DAC'22上面。向量搜索，目前它的興起主要是有兩個原因，那首先是由于我們智能手機，物聯(lián)網(wǎng)設備，還有社交媒體，比如說抖音快手它們的快速發(fā)展，這種不受結(jié)構(gòu)的數(shù)據(jù)比如說視頻、圖像以及文本呈著一個爆炸式的增長，那么根據(jù)這個IDC的數(shù)據(jù)表明，到2025 年大約有 80% 的數(shù)據(jù)都是非結(jié)構(gòu)化的。那更重要的是，我們的非結(jié)構(gòu)化的數(shù)據(jù)，它現(xiàn)在是很難直接被計算機系統(tǒng)識別，通常需要使用其語義特征，來實現(xiàn)高質(zhì)量的數(shù)據(jù)處理。
以非結(jié)構(gòu)化數(shù)據(jù)的檢索為例，傳統(tǒng)的解決方案是利用手動特征對圖像進行檢索，他們的檢索的準確度往往都比較低，質(zhì)量會比較差。但是目前隨著深度學習的不斷發(fā)展，現(xiàn)有是利用一個深度的神經(jīng)網(wǎng)絡技術(shù)來獲取我們文本，圖片還有視頻的一個語義特征，將它們映射到一個高維的 embedding上面，以獲得更高的一個檢索的準確度，那么這一種非結(jié)構(gòu)化的數(shù)據(jù)在經(jīng)過神經(jīng)網(wǎng)絡進行編碼為高維向量之后，剩下的工作就是我們今天要講的向量搜索了。
向量搜索它是一種數(shù)據(jù)的處理方式，那它的定義就是我們在一個數(shù)據(jù)集當中，每個實例都是一個包含d個特征的一個向量，假設我們現(xiàn)在是有一個查詢向量的，這時向量搜索的目的就是找到我們這個向量數(shù)據(jù)庫中根據(jù)用戶定義的距離計算函數(shù)，找到與查詢向量最接近的 k 個鄰居。
現(xiàn)在搜索目前是大概是有 4 種方法，分別是暴力搜索、基于哈希的檢索、基于樹的檢索以及目前比較就是最好的方法就是基于圖的檢索，基于圖的向量搜索，它的核心的基礎就是我們把這樣一個高維的向量，把它作為點，向量之間的距離，給它表征成為向量之間的邊，就是向量之間的距離越近，那么它們就越可能成為鄰居。那整個查詢的過程大概就是從起始點開始。迭代的從鄰居節(jié)點，尋找與查詢點距離最近的節(jié)點，這樣不斷地在圖上進行迭代的查找，直到找到滿足我們想要的與查詢向量最近的向量的時候，這個時候就是滿足了條件，然后才終止。那么由于基于圖的方法它表現(xiàn)出非常好的一個性能，所以現(xiàn)在已經(jīng)有大量的研究工作對基于圖的方法做優(yōu)化，比如說最基礎的是KGraph，然后現(xiàn)后來的HNSW ，NSG 等等。
然而隨著語義信息豐富的數(shù)據(jù)集增多，基于圖的向量搜索也對數(shù)據(jù)中心的生產(chǎn)系統(tǒng)提出了更高的要求和挑戰(zhàn)。首先需要以更低的延遲進行搜索，并且還要達到更高的準確度。以推薦系統(tǒng)為例，就是由于我們查詢必須在到達現(xiàn)在搜索階段之前，穿過多個階段。因此現(xiàn)在搜索其實它的執(zhí)行時間僅僅就是要求為微妙級別，甚至是更短。但是如果我們使用 CPU 來查詢 10 億規(guī)模的一個向量數(shù)據(jù)集的話，實際上所需要的時間要超過 100 毫秒。其次是我們需要更小的內(nèi)存占用，還有更低的成本。雖然我們基于圖的向量搜索，它表現(xiàn)出非常優(yōu)異的查詢性能，但是這樣一種結(jié)構(gòu)，它消耗會消耗大量的一個內(nèi)存空間，比如這個SIFT1Billion。對于 10 億級規(guī)模的話，如果我們要在這樣一個數(shù)據(jù)集上構(gòu)建一個圖的話，它的索引大小就就要占到 200 多GB，那么 200 多個 GB 實際上是就是對數(shù)據(jù)中心內(nèi)存空間的壓力還是比較大的，所以如果我們能減少小的內(nèi)存占用，那么就可以釋放我們機器上搜索階段所占用的資源，然后來降低數(shù)據(jù)中心的總的一個擁有的成本。
所以為了從應用層面和系統(tǒng)層面對這個相應搜索進行分析，這篇文章它們是分別運行了 GIST1M 和 DEEP1B 這兩個數(shù)據(jù)集，那么對于應用層面，他們在執(zhí)行相似的查詢過程中頂點的軌跡，可以發(fā)現(xiàn)如果兩個查詢他們的距離特別近的話，那么他們在迭代查詢的過程中實際上是會有大量的數(shù)據(jù)是被重用的。同時對于系統(tǒng)層面的話，如果將 DEEP1B 的圖的索引和相應的數(shù)據(jù)全都存儲到 SSD 的話，那么可以發(fā)現(xiàn)大約有 75% 的總的能耗的一個消耗是由 NAND閃存芯片，還有 I/O 接口之間的數(shù)據(jù)傳輸產(chǎn)生的那么這樣一種現(xiàn)象就表現(xiàn)出一個顯著的 I/O 瓶頸問題。
所以為了在大規(guī)模的銷量數(shù)據(jù)集上提供一個更高成本效益的一個方案，然后這篇文章提出了一種基于可計算存儲的向量搜索的解決方案。它是將原本的基于圖的向量搜索這樣一個功能，全部都卸載到了可計算存儲設備內(nèi)部，然后讓可計算存儲設備做相應搜索，將結(jié)果直接返回給主機。而不是說在搜索的過程中，主機不斷地從SSD當中出取數(shù)據(jù)，再計算結(jié)果。這樣的話，由于數(shù)據(jù)的讀取和計算都是在存儲器內(nèi)部，那么就避免了我們傳統(tǒng)操作系統(tǒng)當中這些復雜的一個數(shù)據(jù) I/O 的存儲棧，還釋放了我們 CPU 和 DRAM 的一個內(nèi)存資源。
Vstore 這篇文章它是嵌入到了 SSD 的控制器內(nèi)部，可以看到它是有 4 個模塊的，分別是查詢編排引擎、向量搜索引擎、地址生成器和最后的請求編排。那么查詢編排引擎就是負責重新的組織傳入的查詢的執(zhí)行順序，因為它之前觀察到的現(xiàn)象就是如果兩個查詢向量的距離比較近的話，那么它們在查詢過程中數(shù)據(jù)的重用率比較高，所以它們就利用這樣一個特性，然后做了一個查詢的請求編排，讓相似的查詢之間按順序的進行執(zhí)行，這樣的話數(shù)據(jù)重用率就比較高。然后向量搜索引擎就是對基于圖的向量搜索算法做了一個定制化的芯片加速器，把原來基于圖的向量搜索給硬件化了。后面我主要是對以下這 3 個做詳細地介紹。
首先是查詢的編排，它主要是通過在存儲器內(nèi)部，緩沖一個查詢的Buffer，然后來捕獲定義時，固定時間窗口內(nèi)的查詢，選擇與當前加速器中正在執(zhí)行查詢相似的查詢，那這樣的話，如果當前的這個查詢執(zhí)行完之后，查詢 6 與查詢 9 他們距離比較近，那么就意味著他們的數(shù)據(jù)重復率比較高，所以就調(diào)整這個窗口內(nèi)的執(zhí)行順序。讓和正在查詢的這樣一個向量與它們距離比較近，然后就優(yōu)先進行查詢，比如說 3 和 6 與 9 距離比較近，那么就優(yōu)先執(zhí)行 3 和6。調(diào)整后，還要對后面就是窗口內(nèi)的其他的查詢，也進行給編排，他們計算剩余的查詢它們之間的一個距離關(guān)系，讓距離相近的查詢，然后按順序這樣查找。
在圖上進行不斷地迭代，搜索過程中要不斷地去請求大量的節(jié)點和對應的鄰居，然后這里它在 SSD 里面是分別維護了 3 個緩沖區(qū)，分別是邊緩沖區(qū)和頂點緩沖區(qū)，還有地址緩沖區(qū)。因為在 SSD 的內(nèi)部它要請求節(jié)點或者鄰居數(shù)據(jù)的話，首先要檢查對應的緩沖區(qū)當中有沒有被命中，如果命中的話就直接做計算就可以了。那么如果有命中的話，就要向底層的 flash 上面去取數(shù)據(jù)。但是我們SSD內(nèi)部是沒有傳統(tǒng)操作系統(tǒng)當中文件系統(tǒng)的這樣一層抽象的，所以不能夠直接去讀取數(shù)據(jù)。這里它是做了一個地址生成器，把向量對應的頂點，映射到對應的閃存的物理頁當中。映射之后，如果要讀取頂點8，就是要讀取 flash 的頁面2。但是由于我們閃 SSD 內(nèi)部它是以頁粒度為讀取單位的，就是我們每次讀取的時候，它的單位都是以頁粒度為大小，一個頁粒度的大小通常是4KB左右，而我們每個向量和邊它們大小通常是幾十到幾百B這么大。所以說有可能會出現(xiàn)同一個物理頁當中包含多個向量頂點和多個鄰居，這樣的話就可能會出現(xiàn)一種情況，就是數(shù)據(jù)頁面的冗余訪問。比如這里有一個情況就是頂點8，它對應的是物理頁2，那么在取完頂點 8 之后，后續(xù)的請求當中頂點 7 它也要去讀取頁面2，如果按這樣一個順序指引的話，就是讀取了重復的頁面2，來去獲取頂點 8 和頂點 7 的數(shù)據(jù)。這樣的話實際上增加了讀取延遲，這里它是做了一個合并請求的一個方案，就是它也是在內(nèi)部先緩沖一些請求，依次就是做地址映射，然后比如說得到頁面 2 是對應著頂點8，還定還對應著頂點7，那么就將這兩個頁面請求進行合并，合并成一個請求之后再去發(fā)送給閃存的控制器，這樣的話就可以減少冗余的頁面訪問。還有一種情況就是SSD 內(nèi)部它是實際上是有多個通道?，F(xiàn)在 SSD 的高帶寬主要的一個原因其實也就是由于它內(nèi)部是有多個channel，然后多個 channel 可以并行地去工作。所以這篇文章他們?yōu)榱顺浞值睦肧SD內(nèi)部的這樣一種并行性，他們是做了一個請求的一個類似于請求的一個調(diào)度的，他們將每一個到來的閃存的請求，通過一個哈希函數(shù)將不同的閃存頁請求進行分區(qū)，然后這樣的話可以就是充分地利用多個 channel并行訪問的這樣一個優(yōu)勢，來提高數(shù)據(jù)的讀取效率，充分地利用通道級的并行。
以上就是大致的 SSD 內(nèi)部的加速器的設計，然后他們實驗用 FPGA 做了一個硬件，又做了一個模擬器的方案，他們分別采用了三種矢量搜索平臺作為一個評估基準，分別是CPU， GPU 和 ZipNN。實驗是選擇了 5 種不同規(guī)模的數(shù)據(jù)集，然后通過 QPS 來衡量它們的搜索效率。功耗的話它們是主要通過功率的，效率就是每瓦特每秒的查詢次數(shù)來評估，后面主要對這兩個指標進行介紹。
首先是性能指標，他們FPGA的實現(xiàn)方案是這個藍色三角后模擬器的方案是橙色的圓，CPU 的方案和其他 GPU 方案都是這些黑線。可以看到 FPGA 的方案實際上是提供了比 CPU 平臺高很多的一個性能，那么隨著數(shù)據(jù)集的規(guī)模增大，他們用的這個 FPGA 平臺是比較就性能不是特別好，所以他的這樣一個方案是比不過 GPU 方案的。但是他們這個 V-SIM做的一個方案是要比CPU、 GPU 和 ZipNN 性能都要好的。這樣一種性能提升實際上就是來源于他們定制了一種硬件實現(xiàn)的優(yōu)化，比如說前面消除了冗余的數(shù)據(jù)訪問，還有并行的利用SSD 內(nèi)部的多 channel 的這樣一種特性。
對于能源效率的話，這個 V-FPGA 就是這個淺藍色是要明顯的比 CPU 的方案要好。他們這個模擬器的方案是比所有的方案都要好，F(xiàn)PGA的方案他們可能比不過 GPU 或者說其他優(yōu)化的方案，但是他們這個模擬器的方案是要比所有的方案都要好。這是由于他們將計算移動到了數(shù)據(jù)附近，減少了主機到 SSD 的一個 I/O 接口，還有主機的 DRAM 以及閃存芯片所產(chǎn)生的能源成本。
然后以上就是Vstore它這篇文章的主要內(nèi)容，這篇文章由于它是發(fā)表在了 DAC 上面， 6 頁左右，所以說內(nèi)容會比較緊湊，然后比較少。通過以上的分享，我們基于他們的工作，我們也有了一些思考。然后首先就是對于磁盤這樣一種方案，它的數(shù)據(jù)集規(guī)模往往是非常大的，比如說 10 億級別或者說百億級別，那么這樣一種情況下，我們還按照原來單個基于圖的索引的方案的話，可能并不能達到非常好的一個性能。目前的研究方案表明，通過基于樹和圖的結(jié)合，或者說基于聚類，或者基于分區(qū)與圖的結(jié)合這樣一種索引,在超大規(guī)模的ANN場景中會表現(xiàn)出一個更好的一個性能。因為我們可計算存儲的話，它主要針對的場景，也就是我們平常在主機里面，就是在 DRAM 里面數(shù)據(jù)集放不下，然后存儲到 SSD 里，那存儲的SSD 里就是對應著超大規(guī)模的一個情況。并且我們還發(fā)現(xiàn)就是現(xiàn)有的工作對這個 ANN卸載到可計算存儲設備的方案中，實際上都沒有考慮到可計算存儲設備的一個處理能力，并且還沒有考慮到就是有了主機的 CPU 和存儲器的可計算存儲這樣一種異構(gòu)的計算資源環(huán)境它們之間的協(xié)作的可能。
這里我們做了一個簡單的實驗，通過將 CPU 和可計算存儲設備一起去做這樣一個搜索的過程，那可以發(fā)現(xiàn)通就是適當?shù)恼{(diào)整它們的卸載比例，也可以達到一個最佳的一個查詢性能，這邊 0: 10 是不進行卸載，對，這邊 0: 10 是全部進行卸載，就是所有的任務都放到可計算存儲設備內(nèi)進行處理。然后 10: 0 是不進行卸載，就是全部放在 CPU 里，然后如果 4: 6 的話，實際上這個搜索效率是要比這兩個方案要高出兩倍的，就在協(xié)同的情況下。然后基于此，我們現(xiàn)在正在做的一個工作就是通過構(gòu)建一種多探針的分區(qū)圖的索引方式，來達到一個訪存優(yōu)化和高效并行的軟硬件協(xié)同的方案。
滬公網(wǎng)安備 31011002003093號