TC 2022 Paper，元數(shù)據(jù)論文閱讀匯總

“multiple metadata server (MDS)” 多個元數(shù)據(jù)服務(wù)器

“l(fā)ocality preserving hashing (LPH)” 局部保持哈希

“Multiple Subset Sum Problem (MSSP).” 多子集和問題

“polynomial-time approximation scheme (PTAS)” 多項式時間近似方法

背景

分布式元數(shù)據(jù)的挑戰(zhàn)

目前的分布式文件系統(tǒng)被設(shè)計用于支持 PB 規(guī)模甚至 EB 規(guī)模的數(shù)據(jù)存儲。元數(shù)據(jù)服務(wù)負(fù)責(zé)管理文件屬性信息和全局命名空間樹，對系統(tǒng)性能至關(guān)重要。元數(shù)據(jù)是描述文件系統(tǒng)組織和結(jié)構(gòu)的數(shù)據(jù)，包括文件屬性、文件塊指針等 [1]。元數(shù)據(jù)大小通常占數(shù)據(jù)空間的0.1%到1%，約50%到60%的文件系統(tǒng)訪問指向元數(shù)據(jù) [2]。分布式元數(shù)據(jù)管理方案采用多個元數(shù)據(jù)服務(wù)器（MDS）來存儲元數(shù)據(jù)，為減輕單個服務(wù)器的工作負(fù)載提供了有效的途徑。然而，同時保持良好的元數(shù)據(jù)局部性和多個 MDS 之間的負(fù)載平衡是一個非常復(fù)雜的問題。

根據(jù)POSIX標(biāo)準(zhǔn) [4]，訪問元數(shù)據(jù)節(jié)點時，我們需要執(zhí)行路徑遍歷，遞歸地對其每個祖先節(jié)點執(zhí)行訪問權(quán)限檢查。圖1顯示了將命名空間樹分區(qū)為三個 MDS 的兩種方案。例如，要訪問“c1.tex”，我們應(yīng)該按順序驗證“root”、“etc”、“dir2”和“c1.tex”的元數(shù)據(jù)節(jié)點。在圖1a中，這個訪問操作可以在“MDS＃1”中完成，有很好的元數(shù)據(jù)局部性。例如，子樹分區(qū)方案 [5]，[6] 采用了這個思想。然而，由于命名空間樹分區(qū)不均勻和對一些熱門文件的訪問不平衡，“MDS＃1”面臨著過載的高風(fēng)險。圖1b描述了另一種具有良好負(fù)載平衡的分區(qū)方案，其中元數(shù)據(jù)節(jié)點均勻分配給了三個MDS。通常，基于哈希的映射 [7]，[8] 這樣的元數(shù)據(jù)管理方案采用這個思想，但它們可能會破壞元數(shù)據(jù)的層次局部性。例如，當(dāng)訪問“c1.tex”時，我們需要在“MDS＃1”和“MDS＃2”之間切換執(zhí)行路徑遍歷，從而導(dǎo)致高響應(yīng)延遲。

為了更好地說明問題，根據(jù) AngleCut [14] 對元數(shù)據(jù)局部性和系統(tǒng)負(fù)載平衡進(jìn)行數(shù)學(xué)定義。表1列出了本文中使用的符號表示法。

局部性

假設(shè)在 MDS 中總共有 N 個元數(shù)據(jù)節(jié)點。我們使用 S={ni | 0 ≤ i ≤ N} 表示整個命名空間樹，其中 ni 表示第 i 個節(jié)點，n0 表示根節(jié)點。定義 Hi 為元數(shù)據(jù)節(jié)點 ni 的跳數(shù)，即在執(zhí)行 ni 的POSIX 風(fēng)格路徑遍歷時在不同 MDS 之間切換的次數(shù)。良好的局部性表示平均切換次數(shù)較小，這意味著客戶端文件請求可以通過訪問較少的 MDS 完成。一些熱門元數(shù)據(jù)節(jié)點被高頻訪問，例如，“/etc”是 UNIX 系統(tǒng)中的一個熱門目錄。因此，在衡量元數(shù)據(jù)局部性時，我們應(yīng)考慮此因素。用 Pi 表示元數(shù)據(jù)節(jié)點 ni 的熱門程度。Pi 的值包含對 ni 的專用訪問以及對 ni 的后代元數(shù)據(jù)節(jié)點的訪問?，F(xiàn)在給出局部性 Loc 的定義如下

Loc 越大表示局部性越好，即接近的元數(shù)據(jù)節(jié)點更有可能被分配到同一個 MDS。因此，Hi 的總和較小。在方程（1）中，Pi 是 Hi 的加權(quán)因子，用于對熱門元數(shù)據(jù)節(jié)點進(jìn)行懲罰。直觀地說，如果所有元數(shù)據(jù)節(jié)點都分布到一個 MDS，Loc 就是正無窮。

負(fù)載平衡

假設(shè)總共有 M 個 MDS，Li(1 ≤ i ≤ M) 表示第 i 個 MDS 的當(dāng)前負(fù)載，例如 MDSi 的元數(shù)據(jù)查詢頻率的總和。令 Ci 表示 MDSi 的系統(tǒng)容量，我們可以通過 η = SUM(Li) / SUM(Ci) 計算系統(tǒng)理想負(fù)載因子 η。相應(yīng)地，MDSi 的理想負(fù)載 Gi 定義為：Gi = η * Ci。現(xiàn)在給出負(fù)載平衡度 Bal 的定義如下

Bal 定義為整個 MDS 的負(fù)載的方差的倒數(shù)，Li 的值表示在采樣時刻的 MDS 的狀態(tài)。Bal 越大意味著每個 MDS 的負(fù)載越接近理想負(fù)載。

局部性保持哈希（LPH）

LPH 是一個哈希函數(shù) f，將多維坐標(biāo)空間中的一個或多個點映射到一個標(biāo)量值，如果我們有三個點 A、B 和 C，我們可以得到

現(xiàn)有方法的問題

從本質(zhì)上講，分布式元數(shù)據(jù)管理歸結(jié)為找到一個映射函數(shù) f(x) : x → y，其中 x 表示一個元數(shù)據(jù)節(jié)點，y 表示元數(shù)據(jù)節(jié)點屬于哪個 MDS。傳統(tǒng)的元數(shù)據(jù)管理方案采用各種方法來構(gòu)建 f(x)，可分為基于哈希的映射方法 [7]，[8]和子樹分區(qū)方法，子樹分區(qū)可以根據(jù)命名空間的分區(qū)方式進(jìn)一步分為兩種類型，包括靜態(tài)場景 [5]，[6] 和動態(tài)場景 [6]。

基于哈希的映射通常將元數(shù)據(jù)節(jié)點（例如，文件路徑名或其他標(biāo)識符）映射到哈希key，并通過將元數(shù)據(jù)的 key 投影到 MDS 的 key 來將元數(shù)據(jù)分配到 MDS。靜態(tài)子樹分區(qū)假定同一子樹下的元數(shù)據(jù)節(jié)點應(yīng)映射到同一個 MDS，它將全局命名空間劃分為幾個子樹，每個 MDS 負(fù)責(zé)其中一個或幾個子樹。動態(tài)子樹分區(qū)是靜態(tài)方式的一種優(yōu)化，其核心思想是目錄層次結(jié)構(gòu)子樹可以細(xì)分并映射到不同的 MDS，隨著工作負(fù)載的變化，元數(shù)據(jù)節(jié)點將動態(tài)重新分布。然而，上述方案忽略了數(shù)據(jù)分布，因此無法充分利用現(xiàn)實世界數(shù)據(jù)中的普遍模式，所有傳統(tǒng)的方案 [5]，[6]，[7]，[8]，[9]，[10]，[11]，[12]，[13] 啟發(fā)式地假設(shè)了一個剛性的映射函數(shù)，沒有考慮元數(shù)據(jù)節(jié)點的當(dāng)前分布，從而導(dǎo)致元數(shù)據(jù)局部性差或系統(tǒng)負(fù)載不平衡。

在元數(shù)據(jù)管理的其他方案中，AngleCut [14] 提出了一種保留局部性哈希（LPH）映射方案 [15]，通過對命名空間樹進(jìn)行環(huán)投影和角度分配，可以保留從元數(shù)據(jù)命名空間樹到線性哈希空間的節(jié)點的相對位置。然而，它基于靜態(tài)命名空間樹分配角度，容易導(dǎo)致哈希沖突并且無法很好地處理動態(tài)文件請求。導(dǎo)致上述問題的原因是它們都啟發(fā)式地假設(shè)了一個剛性的映射函數(shù) f(x)，而沒有考慮元數(shù)據(jù)節(jié)點的實際分布。

本文工作

為了實現(xiàn)更靈活的映射方案并服務(wù)于分布式元數(shù)據(jù)管理，我們提出了一種基于機器學(xué)習(xí)的模型的 DeepHash，它利用深度神經(jīng)網(wǎng)絡(luò)（DNN）學(xué)習(xí)自適應(yīng)的局部性保持哈希（LPH）映射方案。DeepHash 首先通過網(wǎng)絡(luò)嵌入技術(shù)將元數(shù)據(jù)節(jié)點轉(zhuǎn)換為特征向量。由于缺乏訓(xùn)練標(biāo)簽，即元數(shù)據(jù)節(jié)點的哈希值，我們設(shè)計了一個具有獨特特征的對比損失函數(shù)來訓(xùn)練 DeepHash，并引入采樣策略以提高訓(xùn)練效率。此外，我們提出了一種有效的算法來動態(tài)平衡工作負(fù)載，并采用緩存模型以提高查詢效率。

我們在 Amazon EC2 平臺上的兩個真實跟蹤數(shù)據(jù)集上進(jìn)行評估了，DeepHash 相對于傳統(tǒng)和最先進(jìn)的方案，能夠保持元數(shù)據(jù)的局部性同時保持高負(fù)載平衡。

• 先前的文獻(xiàn)使用文件路徑名作為映射模型的輸入，這對于神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)位置信息是不適用的。我們采用網(wǎng)絡(luò)嵌入技術(shù)并結(jié)合查詢頻率，將元數(shù)據(jù)節(jié)點嵌入固定長度的特征向量作為訓(xùn)練實例。

• 訓(xùn)練實例沒有相應(yīng)的標(biāo)簽，即我們不知道元數(shù)據(jù)節(jié)點的理想哈希值。受圖像檢索領(lǐng)域中的孿生網(wǎng)絡(luò) [16] 和 FaceNet [17] 的啟發(fā)，我們設(shè)計了一個復(fù)雜的損失函數(shù)，稱為對比損失。核心思想是通過元數(shù)據(jù)的相對位置關(guān)系來訓(xùn)練 DeepHash 網(wǎng)絡(luò)。同時損失函數(shù)的形式融入了 LPH 的屬性，可以保持元數(shù)據(jù)的局部性。

• 為了提高系統(tǒng)的負(fù)載平衡度，我們提出了一種基于多重子集和問題（MSSP）的多項式時間逼近方案（PTAS），以有效地在 MDS 間分配元數(shù)據(jù)節(jié)點。我們進(jìn)一步設(shè)計了一個三階段算法，在系統(tǒng)運行時動態(tài)平衡系統(tǒng)負(fù)載。

DeepHash 模型

在本節(jié)中，我們詳細(xì)描述了 DeepHash 的設(shè)計。根據(jù)實際情況假設(shè)客戶端的元數(shù)據(jù)請求，即讀取、寫入、刪除、“更新”，大致保持其操作行為，這意味著客戶端操作遵循類似的模式。

圖2描述了 DeepHash 的框架，由三個部分組成。在3.2節(jié)中，DeepHash 首先使用網(wǎng)絡(luò)嵌入方法將每個元數(shù)據(jù)節(jié)點轉(zhuǎn)換為固定大小的特征表示，該表示用作神經(jīng)網(wǎng)絡(luò)的輸入。在3.3節(jié)中，DeepHash 設(shè)計了一個對比損失函數(shù)，用于學(xué)習(xí)一個 LPH 函數(shù)，該函數(shù)可以將元數(shù)據(jù)投影到線性哈?？臻g（例如Chord環(huán) [20]）。學(xué)到的 LPH 函數(shù)可以保持命名空間中元數(shù)據(jù)節(jié)點的相對位置信息，從而保持了元數(shù)據(jù)的局部性。在3.4節(jié)中，我們利用一致性哈希算法將哈?？臻g中的元數(shù)據(jù)分配到相應(yīng)的 MDS，這可以同時保持系統(tǒng)負(fù)載平衡和元數(shù)據(jù)的局部性。為了進(jìn)一步提高系統(tǒng)負(fù)載平衡度，在3.5節(jié)引入了虛擬節(jié)點，并基于多重子集和問題（MSSP）設(shè)計了一個多項式時間逼近方案（PTAS），用于在一致性算法的 MDS 之間分配虛擬節(jié)點。

命名空間樹的坐標(biāo)系

每個元數(shù)據(jù)節(jié)點包括4個屬性，包括標(biāo)簽（tag）、頻率（frequency）、跳數(shù)（hop）和哈希值（hashV），如圖3所示。標(biāo)簽1比特，如果元數(shù)據(jù)節(jié)點是有效的，則設(shè)置為1，一旦節(jié)點被刪除，標(biāo)簽就被更改為0，并變?yōu)闊o效。頻率是一個整數(shù)值，用于記錄元數(shù)據(jù)節(jié)點的查詢頻率。跳數(shù)用于記錄 MDS 之間的跳數(shù)。哈希值表示由 DeepHash 獲取的哈希值，即在哈希環(huán)上的位置。

我們在命名空間樹上建立一個坐標(biāo)系統(tǒng)，這將作為3.3節(jié)中的度量標(biāo)準(zhǔn)。我們根據(jù)元數(shù)據(jù)節(jié)點在樹中的位置對其進(jìn)行編碼，這本質(zhì)上是一個廣度優(yōu)先搜索過程。給定一個命名空間樹，元數(shù)據(jù)節(jié)點 ni 的坐標(biāo) ei 被編碼為 [a1,a2, …,adi]。這里，維度 di 是 ni 所在的層的深度，而 aj(1 ≤ j ≤ di) 表示 ni 在第 j 層上逆時針方向的左兄弟節(jié)點的數(shù)量（包括它本身）。例如，在圖3中，A、B、C、D、E的坐標(biāo)分別為[1, 1, 3], [1, 1, 3, 1], [1, 1, 3, 2], [1, 2, 2], [1, 2, 2, 1]。不同層的元數(shù)據(jù)坐標(biāo)的維度是不同的，元數(shù)據(jù)節(jié)點的深度越深，其坐標(biāo)維度越大。為了更好地在3.3節(jié)中測量兩個元數(shù)據(jù)節(jié)點之間的距離，我們將原始的元數(shù)據(jù)坐標(biāo)擴展為固定長度的坐標(biāo)。將命名空間樹的高度表示為 D（假設(shè)根節(jié)點的高度等于1），對于每個元數(shù)據(jù)節(jié)點 ni，我們將其原始坐標(biāo)擴展到長度為 D 的最終坐標(biāo) ei。ei 中的前 di 個分量是其原始坐標(biāo)，而其余的 D-di 個分量則填充為0。例如，在圖3中，A的坐標(biāo)從[1. 1, 3]擴展為[1, 1, 3, 0]。

元數(shù)據(jù)特征表示

為了訓(xùn)練 DeepHash 模型，我們需要獲取元數(shù)據(jù)節(jié)點的特征表示。簡單的方法是直接使用坐標(biāo) ei 作為元數(shù)據(jù) ni 的特征向量。然而，由于不同的元數(shù)據(jù)節(jié)點在命名空間樹中的位置不同，許多坐標(biāo)將在其尾部填充0，這將影響訓(xùn)練效率。

我們采用 DeepWalk [21]，一種網(wǎng)絡(luò)嵌入算法 [22]，將元數(shù)據(jù)節(jié)點嵌入到固定長度的特征向量中。網(wǎng)絡(luò)嵌入可以將網(wǎng)絡(luò)中的每個節(jié)點轉(zhuǎn)換為低維的獨特特征表示。同時保留網(wǎng)絡(luò)結(jié)構(gòu)，即兩個相鄰的節(jié)點具有相似的特征表示。

我們將命名空間樹視為一個無向網(wǎng)絡(luò)，并采用 DeepWalk 算法獲得每個元數(shù)據(jù)節(jié)點 ni 的 h 維特征表示 vi。DeepWalk 主要有兩個步驟：（1）在命名空間樹上進(jìn)行隨機游走，得到大量路徑序列。所謂的隨機游走是在命名空間樹上重復(fù)地隨機選擇一個行走路徑，最終通過網(wǎng)絡(luò)形成一個路徑序列。從特定的元數(shù)據(jù)節(jié)點開始，每一步的行走都會隨機選擇與當(dāng)前節(jié)點相連的路徑之一，沿著選擇的路徑移動到下一個元數(shù)據(jù)節(jié)點，并持續(xù)重復(fù)這個過程。（2）將路徑序列輸入 SkipGram 算法 [23]，以獲得元數(shù)據(jù)節(jié)點的特征表示。SkipGram 算法是一種語言模型，可以最大化出現(xiàn)在句子的窗口內(nèi)的單詞之間的共現(xiàn)概率，該算法可以自然地捕捉元數(shù)據(jù)節(jié)點之間的層次關(guān)系。

使用 DeepWalk 進(jìn)行元數(shù)據(jù)嵌入[21]主要有四個優(yōu)勢。第一個是并行化。對于大型命名空間樹，可以同時在不同的元數(shù)據(jù)節(jié)點上啟動一定長度的隨機游走，并同時執(zhí)行多個隨機游走，從而減少采樣時間。第二，該算法可以適應(yīng)網(wǎng)絡(luò)中的局部變化。命名空間樹的改變通常影響隨機游走路徑的一部分，我們可以僅使用來自命名空間樹上更改區(qū)域的新隨機游走來更新學(xué)到的模型，而無需重新計算整個網(wǎng)絡(luò)。第三，DeepWalk 獲得的特征向量具有局部敏感性，在命名空間樹中相鄰的元數(shù)據(jù)節(jié)點更有可能具有相似的表示。第四，連續(xù)的表示具有平滑的決策邊界，有助于提高訓(xùn)練效率。

在運行 DeepWalk 算法后，我們將元數(shù)據(jù)節(jié)點 ni 的查詢頻率與相應(yīng)的 vi 連接起來。得到一個大小為N *（h + 1）的特征矩陣，矩陣的每一行表示元數(shù)據(jù) ni 的特征向量，其中0 ≤ i ≤ N。特征向量 vi 包含了元數(shù)據(jù)局部性和用戶查詢模式的信息。

DeepHash 方案

我們準(zhǔn)備構(gòu)建一個神經(jīng)網(wǎng)絡(luò) fW(vi)，它可以學(xué)習(xí)一個 LPH 映射，這個映射可以保留元數(shù)據(jù)節(jié)點在命名空間樹中到線性哈?？臻g的相對位置關(guān)系。如圖2所示，DeepHash 網(wǎng)絡(luò)以元數(shù)據(jù)特征表示 vi 為輸入，輸出 fW(vi) 作為其哈希值。然后，根據(jù)一致性哈希算法 [19] 將元數(shù)據(jù)節(jié)點分配給相應(yīng)的 MDS。如果它們在哈?？臻g中的哈希值接近，那么兩個元數(shù)據(jù)節(jié)點更有可能被分配到同一個 MDS。

然而，對于每個元數(shù)據(jù)節(jié)點都沒有預(yù)定義的標(biāo)簽（即哈希值）。我們提出了一個經(jīng)過精心設(shè)計的配對損失函數(shù)來訓(xùn)練 DeepHash，這受到了圖像檢索研究 [17]，[24] 的啟發(fā)。其核心思想是利用元數(shù)據(jù)節(jié)點的相對位置關(guān)系作為它們的標(biāo)簽。根據(jù)3.1，坐標(biāo) ei 能夠唯一表示元數(shù)據(jù) ni。給定兩個元數(shù)據(jù)向量 vi 和 vj，其中0 ≤ i，j ≤ N，我們可以使用 ei 和 ej 來衡量它們之間的距離。

定義 ||vi - vj|| 為兩個元數(shù)據(jù)節(jié)點的距離。||vi - vj|| 是通過對它們相應(yīng)的坐標(biāo) ei 和 ej 進(jìn)行逐元素比較計算的，即比較它們相應(yīng)坐標(biāo) ei 和 ej 的每個分量 ak，其中 0 ≤ k ≤ D，并記錄分量不同的第一層位置 dp。||vi - vj|| = max(di, dj) - dp。如果 ||vi - vj|| ≤ t，其中 t 是一個閾值，那么 vi 和 vj 在命名空間樹中是近的。否則，vi 和 vj 是遠(yuǎn)的。例如，在圖3中，eB[1,1,3,1]和eD[1,2,2,0]，我們可以得到||vB - vD|| = 3。如果 t 等于4，那么 vB 和 vD 是近的。

使用配對損失模型的 DeepHash 的架構(gòu)如圖2中部所示。假設(shè) (vi, vj) 是元數(shù)據(jù)對的輸入，令 y 為對的二進(jìn)制標(biāo)簽，如果 vi 和 vj 是近的，y = 1；如果它們是遠(yuǎn)的，y = 0。fW(vi) 和 fW(vj) 分別是 ni 和 nj 的哈希值，其中 W 是待學(xué)習(xí)的共享參數(shù)向量矩陣。令 DW = ||fW(vi) - fW(vj)||₂² 用于衡量在哈?？臻g中的 vi 和 vj 之間的距離。如果 vi 和 vj 是近的，DW 的值應(yīng)該很小。否則，如果 DW 超過一個閾值 m，我們需要對 DeepHash 網(wǎng)進(jìn)行懲罰，反之亦然。

對于包含 T 個訓(xùn)練對 (vi, vj) 的訓(xùn)練集，損失函數(shù)定義為：

對于第 k 個訓(xùn)練樣本 (y, vi, vj)^k，將它們的損失定義為：

在公式（6）中，Lc 表示近對的懲罰，Lf 表示遠(yuǎn)對的懲罰。為了適應(yīng) LPH 設(shè)計，Lc 和 Lf 的設(shè)計應(yīng)確保 L(W) 的最小化會減小近對的 DW 并增加遠(yuǎn)對的 DW。受到 Siamese Network [16]的啟發(fā)，我們設(shè)計了如公式（7）所示的 Lc 和 Lf。Siamese 神經(jīng)網(wǎng)絡(luò)是一類包含兩個或更多相同子網(wǎng)絡(luò)的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，它們共同處理兩個不同的輸入向量以計算可比較的輸出。相同意味著子網(wǎng)絡(luò)具有相同的配置和相同的參數(shù)和權(quán)重。參數(shù)更新在兩個子網(wǎng)絡(luò)之間進(jìn)行鏡像。

在公式（7）中，[a]+ = max(a, 0)，正數(shù) m 用作邊緣，以控制在哈希空間中 vi 和 vj 之間的距離。如果近對的距離很大，即大于 m，我們應(yīng)該對其進(jìn)行懲罰。如果遠(yuǎn)對的距離很小，它們也同樣受到懲罰?；诠剑?）和（7），DeepHash 傾向于收斂到一個狀態(tài)，在該狀態(tài)下，L(W, (y, vi, vj)^k) 的最小值在半平面 Lc + m < Lf [16] 內(nèi)。因此，DeepHash 得到的哈希值確切地滿足 LPH 映射的思想。

成對丟失的采樣策略

對于具有 N 個元數(shù)據(jù)項的名稱空間樹，生成所有可能的對 (vi,vj) 將產(chǎn)生 N2 個訓(xùn)練樣本。然而，在實際分布式文件系統(tǒng)中，N 非常大，生成所有訓(xùn)練實例是不切實際的。我們可以在名稱空間樹中對 T 個實例進(jìn)行采樣。對于訓(xùn)練對 (vi,vj)，我們使用前面的定義的 t 來指示它們是近還是遠(yuǎn)。在采樣過程中，我們應(yīng)確保對于不同的 t，滿足 ||vi, vj|| = t 的 (vi, vj) 對的數(shù)量大致相等。這種采樣方法可以有效地防止訓(xùn)練數(shù)據(jù)不平衡的問題，從而加速神經(jīng)網(wǎng)絡(luò)的訓(xùn)練過程。

討論

通過以上幾個部分，我們通過神經(jīng)網(wǎng)絡(luò)構(gòu)建了一個 LPH 函數(shù)。使用機器學(xué)習(xí)方法主要有三個優(yōu)點。第一，DeepHash 是一種數(shù)據(jù)依賴型的哈希方法，旨在從特定的名稱空間樹中學(xué)習(xí) LPH 函數(shù)。與其他方案相比，這種數(shù)據(jù)驅(qū)動的方法對元數(shù)據(jù)分布更為敏感，可以利用真實世界數(shù)據(jù)中的模式。例如，AngleCut [14] 在構(gòu)建名稱空間樹上的 LPH 函數(shù)時需要分配一個分區(qū)角度，這是固定的，并且在動態(tài)環(huán)境中缺乏良好的可伸縮性。相比之下，DeepHash 學(xué)到的 LPH 函數(shù)非常靈活，元數(shù)據(jù)節(jié)點的哈希值是從名稱空間樹的結(jié)構(gòu)中學(xué)到的，更具適應(yīng)性。第二，在運行 DeepHash 模型時無需人工干預(yù)，該過程可以由機器學(xué)習(xí)算法自動執(zhí)行。第三，DeepHash 的能力可以持續(xù)改進(jìn)。隨著提供新數(shù)據(jù)，模型的準(zhǔn)確性和效率可以通過后續(xù)訓(xùn)練得到提高 [26]。當(dāng)名稱空間樹的結(jié)構(gòu)發(fā)生變化時，我們只需使用新的元數(shù)據(jù)訓(xùn)練 DeepHash，無需在整個名稱空間樹上重新訓(xùn)練模型。

DeepHash 模型具有很強的可伸縮性：（1）LPH 網(wǎng)絡(luò)可以將元數(shù)據(jù)節(jié)點投影到足夠容納大型名稱空間樹的任意哈?？臻g。我們利用一致性哈希算法和虛擬節(jié)點分配算法（后面細(xì)說）來進(jìn)一步將元數(shù)據(jù)分配到相應(yīng)的 MDS。對于上述兩個步驟，名稱空間樹的規(guī)模對它們的影響很小。因此，DeepHash 可以適應(yīng)大型分布式系統(tǒng)。（2）對于在名稱空間樹上的神經(jīng)網(wǎng)絡(luò)的整個訓(xùn)練僅發(fā)生在開始時，這是離線的，不會給系統(tǒng)帶來負(fù)擔(dān)。在系統(tǒng)運行時，當(dāng)發(fā)生元數(shù)據(jù)查詢時，神經(jīng)網(wǎng)絡(luò)的推斷操作（僅為矩陣操作）可以非?？焖俚貓?zhí)行。（3）在元數(shù)據(jù)更新時，DeepWalk 算法可以適應(yīng)局部變化，我們只需更新更改的分區(qū)上的元數(shù)據(jù)特征表示。LPH 神經(jīng)網(wǎng)絡(luò)也可以通過增量訓(xùn)練算法 [26]，只在新的元數(shù)據(jù)特征向量上進(jìn)行訓(xùn)練以獲得持續(xù)改進(jìn)，這是非常高效的。

一致性哈希

如圖2的第三部分所示，基于 DeepHash 獲得的哈希值，元數(shù)據(jù)節(jié)點根據(jù)一致性哈希算法 [19]、[20] 分配給相應(yīng)的 MDS。整個哈?？臻g，例如0~23²，被組織成一個哈希環(huán)。首先，每個 MDS 被映射到表示其在環(huán)上位置的哈希值，例如圖2中的 server1 到 server6。同時，元數(shù)據(jù)節(jié)點也根據(jù)它們的哈希值映射到環(huán)上，例如環(huán)上的 a、b、c、d。接下來，每個元數(shù)據(jù)節(jié)點按順時針方向分配給它的鄰近 MDS。例如，a、b分配給server2，c分配給server4。因此，每個MDS負(fù)責(zé)哈希環(huán)的特定范圍，在此范圍內(nèi)的元數(shù)據(jù)節(jié)點將被分配給此 MDS。然而，由于一致性哈希算法在哈希環(huán)上的不均勻分區(qū)，一些 MDS 負(fù)責(zé)哈?？臻g較大，這些 MDS 將管理更多的元數(shù)據(jù)節(jié)點，從而遭受重負(fù)載，導(dǎo)致負(fù)載不平衡問題。為了緩解這個性能問題，我們引入虛擬節(jié)點 [19] 來替代哈希環(huán)上的實際 MDS。虛擬節(jié)點是一個邏輯概念。每個 MDS 管理多個虛擬節(jié)點，并且這些虛擬節(jié)點作為虛擬服務(wù)器分散在哈希環(huán)上。

例如，server1 到 server6 是虛擬節(jié)點，分別由真實的 MDS A、B、C 管理。在這種情況下，分配給虛擬節(jié)點的元數(shù)據(jù)節(jié)點將被重新分配給相應(yīng)的真實 MDS，MDS 的負(fù)載取決于其虛擬節(jié)點的總和。使用虛擬節(jié)點不僅提高了系統(tǒng)的負(fù)載平衡程度，還有助于系統(tǒng)的可擴展性。當(dāng)添加或刪除 MDS 時，虛擬節(jié)點可以在相鄰的 MDS 之間平穩(wěn)遷移。為了提高系統(tǒng)的可用性，我們將數(shù)據(jù)在主節(jié)點上備份到順時針方向的下兩個相鄰節(jié)點。如圖2所示，存儲在 server1 上的數(shù)據(jù)將復(fù)制到 server2 和 server3?；趥浞輽C制，主節(jié)點作為主 MDS 處理元數(shù)據(jù)請求，而復(fù)制節(jié)點可以在主 MDS 崩潰時幫助恢復(fù)數(shù)據(jù)。

虛擬節(jié)點分配

負(fù)載均衡的過程涉及到一個多子集和問題（MSSP），這是一個 NP hard。它涉及如何將 V 個虛擬節(jié)點均勻地分配給 M 個MDS，同時最大化每個 MDS 的利用率。MSSP 是傳統(tǒng)的0-1背包問題的變體。[28]對 MSSP 提供了一個簡單而清晰的定義：有 n 個物品，其重量分別為 w1、w2、…、wn，有 m 個帶有正容量 c1、c2、…、cm 的箱子。MSSP 的目標(biāo)是在滿足其容量約束的情況下最大化箱子中的總重量。[27]通過構(gòu)建 MSSP 的多項式時間逼近方案（PTAS）提供了一個3/4的近似算法來解決這個問題。

在我們的分配算法中，假設(shè)有 V 個具有訪問流行度 p1、p2、…、pV 的虛擬節(jié)點，以及 M 個帶有負(fù)載容量 c1、c2、…、cm 的 MDS。分配算法的目標(biāo)是在滿足它們的容量約束的情況下最大化每個 MDS 的負(fù)載。在這種情況下，當(dāng)將元數(shù)據(jù)分配給虛擬節(jié)點時，DeepHash 的局部性得到了很好的保留，當(dāng)與 MDS 容量成比例的流行度的虛擬節(jié)點分配給 MDS 時，其負(fù)載平衡得到了改善。這個問題可以表示為以下整數(shù)線性規(guī)劃問題：

算法1提供了如何在 MDS 中分配虛擬節(jié)點的簡要算法。在初始化階段給出了一個要求的最壞情況下的相對誤差 ε ∈ (0, 1)。然后，我們定義3/4近似算法參數(shù) ~ε := ε/3，并將虛擬節(jié)點分成具有較大訪問流行度的集合 L := {i∈V：pi > ~εc} 和具有較小訪問流行度的集合 S := {i∈V：pi ≤ ~εc}。如果 L 中的虛擬節(jié)點數(shù)量小于 MDS 的數(shù)量，這意味著虛擬節(jié)點的總數(shù)較小，我們可以簡單地將每個虛擬節(jié)點放入一個空的 MDS 并轉(zhuǎn)到第3階段。

在第1階段，通過項目預(yù)處理以減少 L 中虛擬節(jié)點的數(shù)量。我們首先將 L 中的虛擬節(jié)點劃分為子集 Ij, j = 1, …,?1/~ε?-1，每個子集包含 (j~εc, (j+1)~εc) 中的訪問流行度。設(shè) σj :=?1/j~ε?-1。如果 |Ij| ≤ 2Mσj，我們選擇 Ij 中的所有虛擬節(jié)點，否則，我們僅選擇 Mσj 個最大和 Mσj 個最小的虛擬節(jié)點。R 包含從項目預(yù)處理中選擇的虛擬節(jié)點。

通過第1階段的項目預(yù)處理，虛擬節(jié)點的數(shù)量大大減少。在第2階段，我們使用[29]中提出的動態(tài)規(guī)劃解決方案在 M1 MDS 中找到 R 的最優(yōu)解，該解決方案在虛擬節(jié)點數(shù)量較小時精確且易于實現(xiàn)。我們將虛擬節(jié)點放置在 L-R 中的其他 MDS 上。如果 |L- R| ≤ |M-M1|，所有虛擬節(jié)點都分配到單獨的 MDS 上。否則，我們將較小流行度的虛擬節(jié)點成對放置在同一 MDS 上。正如[27]中證明的那樣，L-R 中最小項獲得的成對數(shù)為 |L- R|-|M-M1|。設(shè)從 L-R 中的最小項獲得的對數(shù)為 P = |L- R|-|M-M1|。我們分配 P 對和剩余的 |L-R|-2P 虛擬節(jié)點到單獨的MDS上。L-R 中的分配方案不如 R 那么精確。但是，它為 L-R 提供了一個快速且接近最優(yōu)解的解決方案。

在第三階段，我們使用貪婪算法將 S 中訪問流行度較小的虛擬節(jié)點添加到 M 個 MDS 的接近最優(yōu)解中，以獲得最終的分配方案。

系統(tǒng)優(yōu)化

動態(tài)負(fù)載均衡

【就是每個 MDS 向監(jiān)視器報告自身狀態(tài)，根據(jù)負(fù)載情況和遷移成本，使用簡單的貪心策略進(jìn)行負(fù)載均衡，設(shè)了一堆閾值來減少震蕩】

有些 MDS 可能在長時間服務(wù)后分配了過多的元數(shù)據(jù)，從而過載。因此，我們需要動態(tài)調(diào)整 MDS 之間的系統(tǒng)負(fù)載，即從過載的服務(wù)器遷移元數(shù)據(jù)到負(fù)載較輕的服務(wù)器。在本節(jié)中，我們提出了一個三階段算法，以在元數(shù)據(jù)放置中實現(xiàn)局部性的和負(fù)載平和。前兩個階段向監(jiān)視器報告元組列表和重新分配 MDS 中的虛擬節(jié)點，用于分配元數(shù)據(jù)，最后一個階段的控制器用于優(yōu)化分配工作流程并避免在遷移頻繁時可能出現(xiàn)的振蕩。

向監(jiān)視器報告元組列表

每個 MDS 定期對其中存儲的元數(shù)據(jù)節(jié)點進(jìn)行采樣，以產(chǎn)生關(guān)于元數(shù)據(jù)的本地統(tǒng)計估算。然后，每個 MDS 構(gòu)建一個元組列表，例如：（虛擬節(jié)點，時間戳，負(fù)載，[nmin, nmax]），其中時間戳用于標(biāo)識記錄；[nmin, nmax] 表示元數(shù)據(jù)范圍，負(fù)載表示駐留在當(dāng)前 MDS 中的虛擬節(jié)點的當(dāng)前負(fù)載。監(jiān)視器將建立一個全局負(fù)載映射，并根據(jù)監(jiān)視器接收到的元組列表構(gòu)建一個遷移表，該遷移表表示需要將哪些虛擬節(jié)點從過載的 MDS 遷移到負(fù)載較輕的 MDS。

重新分配 MDS 中的虛擬節(jié)點

根據(jù)之前的定義，我們可以計算每個 MDS 的理想負(fù)載 Gi，以及全局系統(tǒng)負(fù)載平衡度 Bal。一旦 Bal 小于閾值 τini，DeepHash 開始重新平衡系統(tǒng)負(fù)載。在從監(jiān)視器接收到遷移表后，過載的 MDS 根據(jù)遷移策略和成本表將虛擬節(jié)點平滑地遷移到負(fù)載較輕的 MDS。

將負(fù)載距離定義為當(dāng)前負(fù)載和理想負(fù)載之間的距離，可以表示為 Gi-Li。

遷移表：遷移表用于指定每個 MDS 的工作負(fù)載狀態(tài)。對于每個 MDS，遷移表將構(gòu)建一列，其中包含駐留在該 MDS 中的虛擬節(jié)點的當(dāng)前負(fù)載和該 MDS 的負(fù)載距離，如表2所示。

成本表：用于指定將虛擬節(jié)點從一個 MDS 移動到另一個 MDS 時的遷移成本。對于每個 MDS，成本表將構(gòu)造一行，其中包含遷移成本，如表3所示。

根據(jù)監(jiān)視器受到的信息，監(jiān)控器將構(gòu)建一個描述負(fù)載分布的全局圖。基于全局映射，監(jiān)控器將推薦理想負(fù)載和每個 MDS 可以正常運行的負(fù)載范圍。如果當(dāng)前負(fù)載比推薦的負(fù)載范圍小，我們將該 MDS 的負(fù)載狀態(tài)表示為輕；如果當(dāng)前負(fù)載在負(fù)載范圍內(nèi)，我們將負(fù)載狀態(tài)表示為中等；如果當(dāng)前負(fù)載比負(fù)載范圍重，我們將負(fù)載狀態(tài)表示為重。

遷移策略：如算法2所示，我們將虛擬節(jié)點從負(fù)載最大的 MDS 遷移到負(fù)載較小的 MDS，直到它們的負(fù)載狀態(tài)為中等。如算法2的第8-21行所示，我們使用兩個過濾器來找到期望的 MDS：(1) 在第一個過濾器中，我們過濾負(fù)載較輕的 MDS 并按照從低到高的遷移成本排序。(2) 在第二個過濾器中，我們過濾具有足夠容量接 受遷移節(jié)點的 MDS，并選擇具有最低遷移成本的期望 MDS。我們重復(fù)此過程，直到 Bal 大于閾值τini。在遷移過程中，我們僅在重 MDS 和輕 MDS 之間遷移虛擬節(jié)點。

控制器

由于頻繁的負(fù)載平衡可能導(dǎo)致振蕩，我們設(shè)計了一個控制器來監(jiān)控遷移過程。在控制器中設(shè)置了時間閾值 Tt、時間間隔 Tg 和負(fù)載平衡邊界 τcontrol。只有當(dāng)整體負(fù)載平衡度低于 τcontrol，并且當(dāng)前狀態(tài)持續(xù)時間超過時間閾值 Tt，并且上一次遷移過程和當(dāng)前時間之間的時間間隔大于 Tg 時，DeepHash 才會開始重新分配元數(shù)據(jù)。在控制器中，我們將負(fù)載平衡邊界 τcontrol 設(shè)置為小于 τini。在這種情況下，遷移過程完成后，系統(tǒng)將花費更長的時間才能實現(xiàn)負(fù)載平衡邊界低于 τcontrol，并保持在該狀態(tài)下的時間閾值 Tt。通過這種方式，我們可以有效地避免在分配過程中的振蕩。

緩存管理和元數(shù)據(jù)查詢

由于采用了 POSIX 風(fēng)格，命名空間樹頂部的元數(shù)據(jù)節(jié)點將更頻繁地被訪問。當(dāng)大量客戶端請求指向它們時，一些文件和目錄很可能成為查詢的熱點，例如，“/etc”目錄是 UNIX 系統(tǒng)中的熱門目錄。為了減少訪問延遲，每個 MDS 上都放置了一個緩存模型，該模型存儲未分配給該 MDS 的熱點或正在寫入的元數(shù)據(jù)，特別是命名空間樹的頂部部分。

配備了緩存模型后，元數(shù)據(jù)查詢過程如下：首先，客戶端隨機選擇一個 MDS 并將文件請求發(fā)送給它。當(dāng) MDS 從終端用戶或另一個 MDS 收到“讀/寫”請求時，它首先從其緩存中檢查祖先節(jié)點（前綴 inode）。如果緩存命中，則 MDS 將直接從緩存中讀取/寫入數(shù)據(jù)。否則，MDS 將檢查哈希表并將請求轉(zhuǎn)發(fā)到相應(yīng)的 MDS。緩存設(shè)計極大地減少了網(wǎng)絡(luò)通信負(fù)載并提高了查詢效率。

實驗

在本節(jié)中，我們將評估 DeepHash 的性能。我們使用 PyTorch 實現(xiàn)了 DeepHash，并將該程序部署在 Amazon EC2 上運行實驗。每個實例都運行 Ubuntu 17.04 操作系統(tǒng)。MDS 的實驗數(shù)量范圍從5到30，增量為5。我們還實現(xiàn)了一些其他傳統(tǒng)的元數(shù)據(jù)管理方案，包括靜態(tài)子樹分區(qū)[31]、動態(tài)子樹分區(qū)[6]、基于哈希的映射[7]以及 AngleCut[14]。為了更好地說明實驗結(jié)果的合理性和效率，除了核心元數(shù)據(jù)管理方案外，所有這些方案都實現(xiàn)了相同的增強功能，例如緩存機制。實驗中使用的數(shù)據(jù)集是兩個名為 LiveMap 和 RadiusAuth 的真實世界跟蹤。表4顯示了關(guān)于這兩個數(shù)據(jù)集的詳細(xì)信息。

使用兩層神經(jīng)網(wǎng)絡(luò)來訓(xùn)練 DeepHash，特征向量的維度為32，全連接的隱藏層中的神經(jīng)元數(shù)量為50，激活函數(shù)為ReLU，批量大小為100，學(xué)習(xí)率為1e-3。

對于 MDS 的每個規(guī)模和特定的數(shù)據(jù)集，我們評估 DeepHash 的元數(shù)據(jù)位置和負(fù)載平衡度，并將其與其他方案進(jìn)行比較。我們通過對損失函數(shù)來訓(xùn)練 DeepHash，然后調(diào)整參數(shù) t 來探究其對模型的影響。用一個特定的服務(wù)器與 DeepHash 交互，即分配查詢?nèi)蝿?wù)和生成哈希表。此外，在構(gòu)建 DeepHash 時有兩個超參數(shù)，即樹嵌入的窗口大小和對丟失的距離閾值 t。由于這兩個參數(shù)的參數(shù)空間非常小，因此在為分布式文件系統(tǒng)訓(xùn)練神經(jīng)網(wǎng)絡(luò)時很容易確定最佳參數(shù)值。此外，我們可以利用貝葉斯優(yōu)化方法[32]來進(jìn)一步降低超參數(shù)調(diào)整的成本。

命名空間樹嵌入

不同數(shù)據(jù)集使用不同窗口大小的嵌入結(jié)果，在不同數(shù)據(jù)集間窗口大小不通用

元數(shù)據(jù)局部性和負(fù)載均衡

效果好

t 對 DeepHash 的影響

t 用于確定節(jié)點間是否接近，在不同數(shù)據(jù)集間 t 不通用

動態(tài)負(fù)載均衡

效果好

訓(xùn)練效率

只說了模型訓(xùn)練時間短，沒提準(zhǔn)備訓(xùn)練數(shù)據(jù)的時間（元數(shù)據(jù)特征表示的部分）

相關(guān)工作

元數(shù)據(jù)管理策略：集中式策略、分布式策略

元數(shù)據(jù)分發(fā)策略：

• 子樹劃分：靜態(tài)子樹劃分（NFS [41]，HDFS [38]，Sprite [42]）。動態(tài)子樹劃分（Ceph [35]，Kosha [39]）

• 基于哈希的映射

• 其他方案：Spyglass[11] 利用文件命名空間的局部性，傾斜元數(shù)據(jù)的分布，將命名空間層次結(jié)構(gòu)映射到多維 K-D 樹中，并使用多級版本控制和分區(qū)來保持一致性，從而實現(xiàn)了良好的局部性。Dynamic Dir Grain[1] 觀察到靜態(tài)子樹分區(qū)和動態(tài)子樹分區(qū)的分區(qū)粒度可能太大。它提出了三重<D，D，F(xiàn)>來確定最大粒度。C2[37] 使用虛擬節(jié)點中元數(shù)據(jù)項的初始狀態(tài)。HopeFS[5] 通過根據(jù)其父節(jié)點的索引節(jié)點 ID 對索引節(jié)點進(jìn)行分區(qū)并在服務(wù)器之間均勻分布來實現(xiàn)負(fù)載平衡。D2Tree[43] 提出了一種用于元數(shù)據(jù)管理的分布式雙層命名空間樹劃分方案。

總結(jié)

針對元數(shù)據(jù)管理方法，傳統(tǒng)方法難以同時實現(xiàn)局部性和負(fù)載均衡。作者提出使用深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)自適應(yīng)的局部性保持哈希（LPH）映射方案。提出幾個創(chuàng)新點：作者將路徑映射成坐標(biāo)，通過 DeepWalk 獲取路徑序列，在通過 SkipGram 獲取特征表示，同時將訪問頻率加入元數(shù)據(jù)特征；使用全連接網(wǎng)絡(luò)訓(xùn)練 LPH 映射，通過設(shè)計損失函數(shù)使命名空間中相近節(jié)點映射后依舊相近；只采樣部分?jǐn)?shù)據(jù)，保證不同距離的節(jié)點對數(shù)量近似；通過虛擬節(jié)點優(yōu)化一致性哈希，采用多項式時間的多子集和問題近似算法，計算 V 個虛擬節(jié)點和 M 個元數(shù)據(jù)服務(wù)器間的分配；通過監(jiān)控和貪心策略進(jìn)行動態(tài)負(fù)載均衡。

結(jié)果優(yōu)于子樹劃分和哈希方法。

局限性：模型訓(xùn)練過程中的2個超參數(shù)都基于數(shù)據(jù)集，不同超參數(shù)結(jié)果差別巨大，在不同數(shù)據(jù)集下難以直接使用；文章來源地址http://www.zghlxwxcb.cn/news/detail-788327.html

到了這里，關(guān)于An End-to-End Learning-Based Metadata Management Approach for Distributed File Systems——論文閱讀的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！