基於可編程交換機的分布式存儲傾斜工作負載平衡方法與流程
2023-06-09 16:11:48 3
1.本發明涉及分布式存儲領域，具體涉及一種基於可編程交換機的分布式存儲傾斜工作負載平衡方法。
背景技術：
2.存儲系統的真實工作負載通常表現出高度傾斜的對象訪問模式，即一小部分熱對象比其餘對象接收的請求要多出很多。許多這樣的工作負載可以使用zipfian訪問分布進行建模，但一些實際的工作負載可能表現很高的傾斜級別（例如，使用α》1的zipf分布，zipf是zipfian分布的特例）。此外，熱對象的集合會動態變化，在某些情況下，熱對象平均會在10分鐘內失去熱度。
3.分布式存儲系統通常在多個存儲伺服器上存儲對象，以實現可伸縮性和負載分配。工作負載的高傾斜意味著跨存儲伺服器的負載也是不均勻的：存儲最熱對象的少數存儲伺服器將比其他存儲伺服器接收不成比例的流量。訪問傾斜過高可能會使對象的負載超過單個存儲伺服器的處理能力，從而導致存儲伺服器過載。為了減少性能損失，系統需要過度配置，大大增加了總體成本。
4.傾斜的工作負載包括很多種，例如重讀工作負載（超過95%的請求是讀請求）、重寫工作負載以及混合工作負載。此外，對象（值）大小也有很大區別，例如在一個程序內，系統可以存儲較小的值（幾個字節）、較大的值（千字節到兆字節）或兩者的組合。因此，需要更好的傾斜工作負載平衡方法來處理上述情況。
5.現有技術：緩存：長期以來，緩存一直是加速資料庫支持的web應用程式的標準方法，理論上和實踐上均證明了緩存方法的有效性。然而，緩存方法有兩個限制：首先，緩存的有效性取決於是否能夠構建一個可以處理更多數量級數據的緩存，另外還要求這個緩存的請求速度比存儲伺服器快很多。當緩存系統本身採用內存存儲硬體不受限制時，上述目標很容易實現。但由於目前的硬體限制，使得通過緩存方法實現上述目標成為一項艱巨的挑戰。其次，由於在存儲伺服器處理寫操作之前，緩存副本必須失效，所以緩存解決方案只對重讀工作負載有好處。
6.選擇性複製：選擇性複製是實現負載平衡的另一種常見解決方案。通過有選擇地複製熱對象到多個存儲伺服器，對這些熱對象的請求可以發送到任何一個具有副本的存儲伺服器，有效地在存儲伺服器之間分配負載。然而，現有的選擇性複製方法面臨兩個挑戰。首先，客戶端必須能夠識別熱對象及其副本位置，但熱對象及其副本位置可能會隨著對象熱度的變化而變化。雖然可以通過使用集中的目錄服務或者通過將目錄複製到客戶端來實現，但兩者都存在可伸縮性的限制，因為一個集中的目錄服務很容易成為一個瓶頸，並且很難在成百上千的客戶端之間進行目錄同步。選擇性複製方案的第二個挑戰是為熱對象提供一致性，現有技術無法解決上述問題。
技術實現要素：
7.為解決上述技術問題，本發明提供一種基於可編程交換機的分布式存儲傾斜工作負載平衡方法。
8.為解決上述技術問題，本發明採用如下技術方案：一種基於可編程交換機的分布式存儲傾斜工作負載平衡方法，用於對客戶端與分布式的存儲伺服器之間的工作負載進行平衡，客戶端向存儲伺服器發出包含應用層報文的請求，請求包括將鍵所對應的值存儲到存儲伺服器的寫請求，以及將鍵所對應的值從存儲伺服器讀取出來的讀請求；存儲伺服器向客戶端返回包含應用層報文的應答；工作負載包括客戶端請求和存儲伺服器應答，工作負載均經過可編程交換機；存儲伺服器包括主存儲伺服器和多個副本存儲伺服器；應用層報文包括鍵以及鍵的對象版本號的信息；工作負載平衡方法具體包括以下內容：p1：可編程交換機統計客戶端與存儲伺服器交互時最熱的o(nlogn)個熱鍵，n表示所有的不同的鍵的數量，表示複雜度；可編程交換機將熱鍵在主存儲伺服器中對應的值的副本存儲到副本存儲伺服器，並通過可編程交換機記錄熱鍵、熱鍵的最高對象版本號ver_completed以及值所在的存儲伺服器列表；p2：客戶端向存儲伺服器發出寫請求時：可編程交換機依次為每個寫請求的鍵分配一個遞增的對象版本號；如果寫請求中的鍵在可編程交換機中存在記錄，則該鍵為熱鍵，可編程交換機從所有存儲伺服器中選擇一個或多個存儲伺服器來轉發寫請求；如果寫請求中的鍵在可編程交換機中不存在記錄，則將寫請求轉發至主存儲伺服器；客戶端向存儲伺服器發出讀請求時：如果讀請求中的鍵在可編程交換機中存在記錄，則該鍵為熱鍵，找到熱鍵的值所在的存儲伺服器來轉發讀請求；如果讀請求中的鍵在可編程交換機中不存在記錄，則將讀請求轉發至主存儲伺服器；p3：主存儲伺服器記錄所有鍵的對象版本號以及鍵的值，副本存儲伺服器記錄熱鍵的對象版本號以及熱鍵的值；當處理一個寫請求時，存儲伺服器比較寫請求中鍵的對象版本號ver和存儲伺服器中鍵的對象版本號，僅當寫請求中鍵的對象版本號ver更高時，存儲伺服器更新該鍵的值和對象版本號；p4：任一存儲伺服器向客戶端返回應答，且應答中的鍵在可編程交換機中存在記錄，則：比較應答中熱鍵的對象版本號ver和可編程交換機記錄的熱鍵的最高對象版本號ver_completed，如果ver＞ver_completed，則將ver_completed的值更新為ver，並將編程交換機記錄的熱鍵對應的存儲伺服器列表內容清空後，再將存儲伺服器加入存儲伺服器列表；如果ver=ver_completed，將存儲伺服器加入存儲伺服器列表。
9.具體地，應用層報頭包括op欄位、keyhash欄位、ver欄位和serverid欄位；op欄位表示工作負載類型，keyhash欄位內容為在可編程交換機內生成的鍵的哈希值，ver欄位內容為可編程交換機為工作負載分配的鍵的對象版本號ver，serverid欄位內容為存儲伺服器在應答時填充的存儲伺服器標識；op欄位的內容包括read、write、read-reply或write-reply，read表示讀請求，write表示寫請求，read-reply表示對讀請求的應答，write-reply表示寫請求的應答。
10.具體地，所述可編程交換內具有網絡內一致性目錄，網絡內一致性目錄通過一個散列表對熱鍵、熱鍵的對象版本號以及值所在的存儲伺服器進行記錄。
11.具體地，當一個鍵失去熱度時，即鍵不再為最熱的o(nlogn)個熱鍵的任意一個時，可編程交換機對鍵進行標記，並在可編程交換機收到包含鍵的應答時，刪除可編程交換機對鍵的記錄。
12.具體地，當需要從主存儲伺服器將熱鍵的值複製到副本存儲伺服器時，可編程交換機發出虛擬寫命令，將主存儲伺服器中熱鍵的對象版本號修改為可編程交換機記錄的熱鍵的最高對象版本號ver_completed，並將熱鍵、熱鍵對應的值和熱鍵的對象版本號發送至副本存儲伺服器進行存儲。
13.與現有技術相比，本發明的有益技術效果是：本發明利用了可編程交換機，能夠比現有負載平衡方法增加10倍的吞吐量或減少90%的存儲伺服器數量。
14.本發明可以快速響應熱鍵發生變化的情況，通過僅複製少量熱對象的方式便能夠提供較好地負載平衡特性，使得不管是在熱對象保持不變的情況或者是熱對象快速變化的情況下，都可以快速識別並追蹤熱對象。
15.本發明適用於多種工作負載，例如重讀工作負載和重寫工作負載，同時對於具有不同大小的對象和不同傾斜級別的工作負載也適用。
附圖說明
16.圖1為本發明的系統模型圖；圖2為本發明工作負載的應用層報頭數據格式示意圖。
具體實施方式
17.下面結合附圖對本發明的一種優選實施方式作詳細的說明。
18.本發明通過具有可編程數據平面的可編程交換機實現，如具有barefoottofino、cavium xpliant或broadcomtrident3系列晶片的可編程交換機。這些晶片具有以下特性：(1)特定於應用層包頭的可編程解析；(2)靈活的包處理管道，包處理管道通常由10-20個管道階段組成，每個階段都能夠進行匹配查找和一個或多個alu操作；(3)10mb量級的通用內存。而且上述特性都在可編程交換機的數據平面上，這意味著這些晶片可以在以全線速率處理數據包時使用。本發明中的傾斜工作負載平衡方法在機架級提供負載均衡，即32個至256個存儲伺服器通過一個可編程交換機連接，但不提供機架內部的容錯保證。
19.本發明使用機架頂部(tor)可編程交換機作為系統的中心點，tor可編程交換機位於每個客戶端請求和存儲伺服器應答的路徑上，故能夠在tor可編程交換機中實現網絡內一致性目錄的抽象。tor可編程交換機可以通過網絡內一致性目錄跟蹤系統中每個熱對象（值）的位置，並將請求轉發到有可用容量的存儲伺服器，甚至可以通過確定發送寫請求的位置來更改值副本的數量或位置。利用這個網絡內一致性目錄，本發明設計了一個基於版本的一致性協議，它保證了線性性，並且在處理值更新時非常高效。即使是寫密集型的工作負載，本發明也能夠提供良好的負載平衡。
20.如圖1所示，本實施例中，在一個機架級存儲系統中實現了一個網絡內一致性目錄。存儲系統包括多個存儲伺服器，所有存儲伺服器都位於一個機架中。存儲伺服器包括主存儲伺服器和副本存儲伺服器，主存儲伺服器為值原本所在的存儲伺服器，副本存儲伺服器為值變為熱對象後存儲值副本的存儲伺服器。本發明所採用的系統包括可編程交換機和可編程交換機的控制器。
21.每個鍵與存儲伺服器上儲存的一個值相對應；客戶端能夠發出請求；存儲伺服器能夠進行數據儲存並對客戶端發出的請求進行應答。如果為讀請求，存儲伺服器根據讀請求中的鍵找到存儲的值，並將值返回給客戶端；如果為寫請求，存儲伺服器對寫請求中需要寫入的值進行保存。
22.一、可編程交換機以tor可編程交換機為例，介紹本發明維護的網絡內一致性目錄：網絡內一致性目錄中存儲了一組熱鍵、每個熱鍵的最高對象版本號以及每個熱鍵對應的值所在的存儲伺服器列表rset。為了減少可編程交換機資源開銷並支持任意大小的鍵，網絡內一致性目錄通過一個固定大小的散列表對鍵進行存儲。
23.本發明定義了一個嵌入在四層（l4）工作負載中的應用層報頭，如圖2所示。本發明為可編程交換機保留一個特殊的udp埠來匹配系統數據包。應用層報頭包括eth欄位、ip欄位、udp欄位、op欄位、keyhash欄位、ver欄位、serverid欄位。op欄位內容可以是read、write、read-reply或write-reply，read表示讀請求，write表示寫請求，read-reply表示讀請求的應答，write-reply表示寫請求的應答；keyhash欄位內容為在可編程交換機內生成的、固定大小的鍵哈希值，ver欄位內容為可編程交換機為工作負載分配的鍵的對象版本號；serverid欄位內容為存儲伺服器的唯一標識，由存儲伺服器在應答時填充。
24.非本發明的系統報文轉發使用標準的二層（l2）或三層（l3）路由，保持可編程交換機與現有網絡協議完全兼容。
25.二、控制器本發明的可編程交換機控制器決定哪些鍵為熱鍵，它負責用最熱的o(nlogn)個鍵更新網絡內一致性目錄，n表示所有不同的鍵的數量。為此，本發明在可編程交換機中設計了一個請求統計引擎，使用可編程交換機的數據平面和可編程交換機cpu跟蹤每個鍵的訪問速率。控制器可以運行在可編程交換機cpu或遠程存儲伺服器上，從請求統計引擎讀取每個鍵的訪問速率，將最常用的鍵作為熱鍵。控制器只保持軟狀態，故障時可立即更換。控制器將熱鍵所對應的值從主存儲伺服器複製到副本存儲伺服器。
26.三、請求處理對請求的處理分為客戶端請求處理和存儲伺服器應答處理兩種，客戶端請求和存
儲伺服器應答均屬於工作負載。
27.客戶端請求的處理算法（算法一）：1：if pkt1.op=write then2：
ꢀꢀꢀꢀꢀ
pkt1.ver
←
ver_next++；3：end if；4：if rkeys.contains(pkt1.keyhash)then5：
ꢀꢀꢀꢀꢀ
if pkt1.op=readthen6：
ꢀꢀꢀꢀꢀꢀꢀꢀ
pkt1.dst
←
select replica from rset[pkt1.keyhash]；7：
ꢀꢀꢀꢀꢀ
elseif pkt1.op= write then8：
ꢀꢀꢀꢀꢀꢀꢀꢀ
pkt1.dst
←
select from all servers；9：
ꢀꢀꢀꢀꢀ
endif；10：end if；11：forward packet；其中pkt1表示客戶端請求，pkt1.op表示pkt1的op欄位內容，pkt1.ver表示pkt1的ver欄位內容，即鍵的對象版本號，ver_next表示下一個對象版本號，pkt1.keyhash表示pkt1的keyhash欄位內容，pkt1.dst表示請求被轉發的目標存儲伺服器，rset[pkt1.keyhash]表示pkt1中的熱鍵所對應的存儲伺服器列表rset，forward packet表示發出請求的數據包。rkeys表示可編程交換機維護的網絡內一致性目錄。
[0028]
針對客戶端請求的處理，算法一的第1行至3行：本發明的可編程交換機為每個寫請求（write）分配一個對象版本號，將ver_next寫入請求的ver欄位後，為ver_next加1。算法一的第4行至10行：通過將請求的鍵哈希值與網絡內一致性目錄進行匹配來確定如何轉發請求：如果鍵不是熱鍵，則將請求轉到原始目的地，即鍵的主存儲伺服器；對於熱鍵的讀請求，則通過從該熱鍵的存儲伺服器列表rset中選擇一個存儲伺服器來轉發讀請求；對於熱鍵的寫請求，則從所有存儲伺服器中選擇一個或多個存儲伺服器來轉發寫請求，具體根據存儲伺服器選擇策略決定。
[0029]
存儲伺服器維護每個鍵的對象版本號以及鍵的值。當處理一個寫請求時，存儲伺服器比較應用層報頭ver欄位中的對象版本號和存儲伺服器中的鍵的對象版本號，只有當ver欄位中的對象版本號更高時，存儲伺服器才更新鍵的值和鍵的對象版本號。
[0030]
存儲伺服器應答的處理算法（算法二）：1：if rkeys.contains(pkt2.keyhash)then2：
ꢀꢀꢀꢀꢀ
if pkt2.ver》ver_completed[pkt2.keyhash]then3：
ꢀꢀꢀꢀꢀꢀꢀꢀ
ver_completed[pkt2.keyhash]
←
pkt2.ver；4：
ꢀꢀꢀꢀꢀꢀꢀꢀ
rset[pkt2.keyhash]《-set(pkt2.serverid)；5：
ꢀꢀꢀꢀꢀ
elseif pkt2.ver=ver_completed[pkt2.keyhash]then6：
ꢀꢀꢀꢀꢀꢀꢀꢀ
rset[pkt2.keyhash].add(pkt2.serverid)；7：
ꢀꢀꢀꢀꢀ
endif；8：end if；9：forward packet；pkt2表示存儲伺服器的應答，pkt2.keyhash表示pkt2的keyhash欄位內容，ver_
completed表示可編程交換機內存儲的鍵的最高對象版本號；pkt2.serverid表示表示pkt2的serverid欄位內容，即應答的存儲伺服器的標識id。
[0031]
算法二第1行至7行：針對存儲伺服器應答的處理，當可編程交換機收到read-reply或write-reply類型的應答時，在可編程交換機網絡內一致性目錄中查找應答中的鍵，如果包含該鍵，則應答中的鍵為熱鍵，可編程交換機將應用層報頭ver欄位中的對象版本號與可編程交換機存儲的該熱鍵的最新對象版本號ver_completed中進行比較：如果應答中的熱鍵有更高的對象版本號，可編程交換機更新ver_completed並重置該熱鍵對應的存儲伺服器列表rset，然後將發出應答的伺服器存儲到該熱鍵對應的存儲伺服器列表rset；如果兩個對象版本號相等，可編程交換機直接將發出應答的伺服器存儲到該熱鍵對應的存儲伺服器列表rset。
[0032]
算法一和算法二的效果如下：關於一個鍵的寫請求被發送到一個或者多個存儲伺服器後，當存儲伺服器完成並確認寫操作，可編程交換機可以記錄這些存儲伺服器，會將所有未來的關於鍵的讀請求發送給這一個或者多個存儲伺服器，這足以確保線性性。
[0033]
四、添加和刪除熱鍵鍵的熱度是不斷變化的，本發明的可編程交換機控制器持續監視鍵的訪問頻率，並通過最熱的o(nlogn)個鍵來更新網絡內一致性目錄。當一個新的鍵變為熱鍵時，需為它創建一個目錄條目，控制器通過添加一個鍵到主存儲伺服器來實現目錄條目的創建，主存儲伺服器中鍵的對象版本號即為可編程交換機內存儲的該鍵的最高對象版本號ver_completed。最後，控制器將熱鍵添加到網絡內一致性目錄中。另外，一個鍵變為熱鍵後，不會立即將該熱鍵的值移動或複製到其他存儲伺服器，稍後的關於該熱鍵的寫請求將被發送到一個新的存儲伺服器，從而實現該熱鍵的值副本的創建。
[0034]
當一個鍵不再是熱鍵後，控制器只需在網絡內一致性目錄中對該鍵進行標記；該鍵的下一個寫請求被發送到它的主存儲伺服器，一旦可編程交換機收到對該鍵的寫請求的應答，該鍵就從網絡內一致性目錄中刪除。
[0035]
上面的方案只在一個鍵的下一次寫請求時，將該鍵的值移動或複製到新的存儲伺服器。雖然這簡化了設計，但不適用於只讀的值或不經常修改的值。本發明在需要移動或複製一個鍵的值時，也可以通過執行不更改值的寫操作來解決這個問題。更準確地說，控制器可以通過向鍵的主存儲伺服器發出虛擬寫命令來強制複製或者移動該鍵的值，指示存儲伺服器將存儲的該鍵的對象版本號增加到可編程交換機內存儲的該鍵的最高對象版本號ver_completed，並將該鍵的值轉發給其他存儲伺服器，然後通過這些存儲伺服器的應答將這些存儲伺服器添加到該鍵對應的存儲伺服器列表rset，幫助提供讀取服務。
[0036]
五、存儲伺服器選擇策略本發明目前可以選擇以下兩種存儲伺服器選擇策略：第一種策略是隨機選擇一個存儲伺服器，並依賴統計進行負載平衡。另一種策略是使用加權輪詢：根據收集的存儲伺服器的負載統計數據，控制器向每個存儲伺服器賦予權重，並指示可編程交換機以與權重成比例的頻率選擇存儲伺服器。
[0037]
讀請求僅被發送到一個存儲伺服器，寫請求可以發送到一個或多個存儲伺服器。較大的存儲伺服器為未來的讀請求提供了更多的選項，從而改善了負載平衡，但較大的存儲伺服器會增加寫操作的成本。對於寫負載大的工作負載，增加寫成本很容易抵消任何負
載平衡的好處。
[0038]
本發明選擇熱鍵的值副本個數（複製因子）時，可編程交換機跟蹤一段時間內每個熱鍵的讀次數，選擇與讀次數成比例的複製因子，可以限制開銷。
[0039]
六、哈希碰撞本發明的網絡內一致性目錄僅保存熱鍵，而並非保存所有鍵。如果存在熱鍵與非熱鍵的散列衝突，則對非熱鍵的請求可能被發送到錯誤的存儲伺服器上。為了解決這個問題，每個存儲伺服器跟蹤所有當前熱鍵(由控制器保持最新)。有了這些信息，存儲伺服器就可以將不正確轉發的請求轉發到正確的存儲伺服器上。由於熱鍵的數量比較少，而且非熱鍵的請求也比較少，所以這種請求連結方法對性能影響很小。當兩個熱鍵罕見地發生哈希衝突時，本發明僅對一個熱鍵的值產生副本，以確保正確性。
[0040]
七、對象版本號對象版本號必須單調遞增。本發明使用64位對象版本號，可編程交換機全線速率處理超過100年，才有可能產生對象版本號溢出的情況，生存時間極長。
[0041]
八、垃圾收集在處理熱鍵的寫請求時，本發明不會顯式地使舊版本失效或刪除舊版本。雖然網絡內一致性目錄能夠保證將所有請求被轉發到最新版本，不會影響正確性，但永遠保留過時的值副本會浪費存儲伺服器上的存儲空間。本發明通過垃圾收集來處理這個問題。控制器已通知存儲伺服器哪些鍵為熱鍵，並定期報告鍵的最高對象版本號。然後，如果存儲伺服器中某個鍵的版本過時，或者鍵不再是熱鍵且存儲伺服器不是該鍵的主存儲伺服器，那麼每個存儲伺服器都可以安全地刪除該鍵。
[0042]
本發明提供了一種基於可編程交換機的分布式存儲傾斜工作負載平衡方法，具有以下特點：1)為高傾斜的動態工作負載提供良好的負載平衡；2)能夠與快速內存存儲系統共同工作；3)能夠處理任意大小的對象；4)保證線性性；5)對重讀工作負載、重寫工作負載和混合讀寫工作負載同樣有效。
[0043]
另外，本發明能夠在不引入其他的性能損失的情況下，通過使用網絡內一致性目錄保證數據的一致性，特別是線性性（linearity），並通過使用內存存儲來達到更快的性能。
[0044]
對於本領域技術人員而言，顯然本發明不限於上述示範性實施例的細節，而且在不背離本發明的精神或基本特徵的情況下，能夠以其他的具體形式實現本發明。因此無論從哪一點來看，均應將實施例看作是示範性的，而且是非限制性的，本發明的範圍由所附權利要求而不是上述說明限定，因此旨在將落在權利要求的等同要件的含義和範圍內的所有變化囊括在本發明內，不應將權利要求中的任何附圖標記視為限制所涉及的權利要求。
[0045]
此外，應當理解，雖然本說明書按照實施方式加以描述，但並非每個實施方式僅包含一個獨立技術方案，說明書的這種敘述方式僅僅是為了清楚起見，本領域技術人員應當將說明書作為一個整體，各實施例中的技術方案也可以經適當組合，形成本領域技術人員可以理解的其他實施方式。