基于內存云架構的帶寬負載均衡算法

劉建礦，于 炯，2＋，英昌甜，魯 亮

（1.新疆大學 信息科學與工程學院，新疆 烏魯木齊830046；2.新疆大學 軟件學院，新疆 烏魯木齊830008）

0 引 言

近些年來，以網絡搜索、電子商務、社交網絡等為代表的在線數據密集型 （on line data Intensive，OLDI）應用逐漸成為工業界和學術界的研究熱點。除了傳統數據密集型應用的特點外，OLDI應用還具有延遲受限、查詢條件多樣等特點，對數據訪問的性能 （如帶寬、延遲等）和數據查詢的多樣性 （如多屬性區間查詢、Skyline查詢等）提出迫切需求［1］。在現有云計算平臺下，虛擬化技術得以普及，CPU 與內存性能優越，但網絡帶寬和磁盤I／O 卻成為制約OLDI應用發展的瓶頸［2］。以Amazon為例，每當其響應一個HTTP 請求而生成一個HTML 頁面時，都需要應用服務器做出100～200個內部請求［3］，若延遲控制不好，將會在很大程度上影響用戶體驗。隨著內存成本的不斷降低和技術的不斷成熟，內存云 （RAMCloud）［4］的出現很好地解決了以上問題，它是由大量普通服務器的內存組成的一種新型數據中心存儲系統，任何時刻的所有信息都存儲在這些動態隨機訪問存儲器 （DRAM，即內存）中，傳統硬盤被內存取代，而硬盤只作為備份。由于DRAM 無可比擬的優越性，內存云可以提供比基于磁盤存儲的系統大100～1000倍的吞吐量，以及低于100～1000倍的訪問延遲 （僅5～10微秒），使內存云架構在處理OLDI應用中優勢顯著。

RAMCloud將數據中心遷移至服務器的內存上，大量數據在內存中的傳輸就變得很重要。由于數據相關性［5］，數據訪問常以順序串行的形式實現，而內存帶寬的發展相對于內存容量的發展較慢，所以內存的帶寬是影響RAMCloud服務性能的重要因素［6］。由于在線密集型數據訪問頻率的差異性［7，8］，RAMCloud不同服務器上的數據吞吐量也存在差異，因此服務器的帶寬利用率也不相同，RAMCloud集群就出現了帶寬負載不均衡的現象。在帶寬負載較高的服務器上，單位時間內吞吐的數據量大，服務器剩余的帶寬能力減小，數據在被訪問時處于等待帶寬的狀態，服務器的時延增加，導致較差的用戶體驗［9］；而帶寬負載低的服務器數據訪問量不足，服務器的帶寬利用率低，造成帶寬資源的浪費，RAMCloud集群的性能降低。

RAMCloud采用段式存儲結構［10］，在一段時間內服務器的數據訪問頻率，是服務器所有數據段訪問頻率的集合。服務器的數據訪問頻率與服務器上數據段的訪問頻率存在表現不完全一致性的特點［11］，在數據訪問頻率高，即內存帶寬負載高的服務器上也存在訪問量很低的數據段，相反在內存帶寬負載低的服務器上也存在訪問量高的數據段。根據這一特點，本文提出一種數據段交換 （data－segments exchanging，DSE）算法，周期性地選擇內存帶寬負載不均衡的服務器，在內存帶寬負載低服務器上選擇訪問頻率較低的數據段，與內存帶寬負載高服務器上的訪問頻率較高數據段進行交換。通過數據段的交換，降低高帶寬負載服務器的數據訪問次數，降低服務器的帶寬負載從而降低服務器時延；同時提升低帶寬負載服務器的數據訪問量，提高其帶寬利用率，實現服務器集群的帶寬負載均衡，提高集群性能。

1 內存云的段式存儲結構

在RAMCloud 中，每一個RAMCloud 集群擁有一個Coordinator節點，用來存儲每一個文件的Mapping 信息，即運用鍵值對保存用戶所請求的信息在哪一臺主服務器上，類似于HDFS （hadoop distributed file system）中的Name－Node節點［12］。Coordinator節點根據用戶 （client）發出的請求信息，通過數據中心網絡找到所請求服務器，每臺服務器都包含兩個部分：Master和Backup。Master管理了存儲在內存中的數據對象，Backup使用本地的機械硬盤或者固態硬盤保存了其它服務器的數據備份。Coordinator管理了Master和Backup配置信息，但是Coordinator并不涉入數據的讀寫操作，因此不會降低系統的可擴展性。其整體結構如圖1所示。

圖1 內存云基本結構模型

在RAMCloud集群中，數據采用基于日志結構的存儲方式進行存儲。文件系統保存的服務器內存信息包括文件數據塊、屬性 （類型、所有者及權限等）、索引塊、目錄和所有用來管理文件的其它信息，還包含數據塊的地址，一個或多個間接塊的地址，每一個間接塊包含多塊數據塊的地址或間接塊的地址［13］。文件系統將服務器的內存的信息及改動保存為日志，并切分成段，將每一段分別保存到不同備份服務器的內存緩沖區 （buffer）［14］中，同時通過哈希表進行記錄 （如圖2所示）。哈希表記錄了每一個存儲在服務器上數據的表項，它支持數據的快速查找，并給出數據的＜table，key＞值。每個數據都有一個指針，存儲在它的哈希表項中。為了保證數據的持久性，避免服務器崩潰和電源故障，每個主服務器必須保持它的對象的備份副本存儲在其它的備份服務器中。每個主服務器都有自己的日志，它將日志分為8 MB 的塊稱為段 （segments），每個段復制幾個備份 （通常是兩個或3個）。

圖2 內存云段式存儲結構

2 RAMCloud的內存帶寬模型

2.1 內存帶寬模型

內存帶寬 （memory bandwidth）是指單位時間內CPU訪問內存時內存通道可以傳輸的最大數據量，單位是GB／s。內存帶寬與數據傳輸通道容量和數據傳輸的速度有關，內存的數據傳輸通道容量與傳輸總線的位數有關，傳輸總線位數越大傳輸的數據量越大，內存頻率決定數據傳輸的速度，頻率越大內存傳輸速率越快，單位時間內傳輸的數據量越大。所以內存帶寬與內存的總線位數和內存頻率存在計算公式

其中，倍增系數λ 是指一個時鐘周期內相對于SDRAM 的數據倍數，目前DDR 的倍增系數是2，DDR2的倍增系數是4，DDR3的倍增系數是8。

吞吐量 （throughput）是指內存在一段時間內所處理的數據量，內存帶寬利用率是單位時間內內存的數據吞吐量占用帶寬的大小，是衡量內存性能的重要指標。單位時間內內存的數據吞吐量越大，占用的內存帶寬越高，則帶寬利用率越高。用TP 表示一段時間t內內存訪問的數據吞吐量。公式表達為

內存時延表示系統進入數據存取操作就緒狀態前等待內存響應的時間。為了進一步研究內存時延與數據吞吐量的關系，本文選用1333 MHz的內存，做一個內存時延隨著單位時間內數據吞吐量增加的微基準測試，所得到的內存時延的變化曲線如圖3所示。

圖3 內存時延的變化曲線

由圖3可以看出，內存時延隨著內存吞吐量的增加呈現出超線性增加。當內存吞吐量的增加時，內存帶寬負載增加，內存的剩余帶寬可以通過的數據量減少，數據平均隊列的長度增加，內存時延增加。當吞吐量接近內存帶寬時，此時內存帶寬飽和，無法通過更多的數據，內存時延無限大。內存的時延與內存吞吐的數據量存在關系如下

式中：MemLatency——內存時延，IdleLatency——空閑時延，slope——參數遞增系數。

2.2 RAMCloud的內存帶寬模型

RAMCloud日志文件結構中的內存信息記錄了數據段的大小、訪問次數和數據段所在位置等信息。一個RAMCloud集群有m 臺服務器，一臺服務器由n 個數據段構成，從段的日志中獲取內存云服務器一段時間t內的一個文件塊的訪問次數，用矩陣Fm×n進行存儲。服務器數據段的訪問次數用 （M［i］［j］）m×n（1≤i≤m，1≤j≤n）表示，其中i表示服務器號，j表示服務器上的第j 個數據段。t時間內一臺服務器的訪問次數是n 個段文件塊的訪問次數的總數，用Mtotal［i］可以表示為

t時間內RAMCloud集群的平均訪問次數是集群中m臺服務器的訪問次數的平均值，用Mavg 表示

式中：Mavg——所有服務器平均在一臺服務器上訪問次數，反應了集群的平均訪問頻率。經過統計在t時間內Mavg是常量。

定義1 若一臺服務器的訪問次數Mtotal［i］滿足關系Mtotal［i］＞Mavg，則服務器i為高內存帶寬負載服務器；若服務器的訪問次數Mtotal［i］滿足關系Mtotal［i］＜Mavg，則服務器i為低內存帶寬負載服務器。

定義2 給定一個參數α，用來表示集群帶寬負載均衡的范圍。若服務器的訪問次數Mtotal［i］滿足關系Mavg＊（1－α）≤Mtotal［i］≤Mavg＊（1＋α），則服務器i為內存帶寬負載均衡服務器。

在RAMCloud上一臺服務器的數據吞吐量是一段時間t內，服務器對所有數據段的訪問總量，用Size 表示RAMCloud上數據段的大小，公式可表示為

3 內存帶寬負載均衡算法

RAMCloud的內存帶寬負載均衡算法過程如下，首先由Coordinator節點從集群中所有服務器數據段的訪問次數Mtotal［i］中選中的訪問次數最少的服務器Mtotal［low］，以及訪問次數最大的服務器Mtotal［high］的兩臺服務器，即一臺帶寬負載最小的服務器low 和一臺帶寬負載最大的服務器high。在低負載服務器low 上選擇一個訪問次數最小的數據段，用常量M［low］［min］表示；然后在高負載服務器high上選一個數據段，用常量M［high］［max］表示，將兩個數據段進行交換，低負載服務器low 的訪問次數增加了M［high］［max］－ M［low］［min］，高負載服務器high的訪問次數減少了 M［high］［max］－ M［low］［min］，兩臺服務器上的數據訪問量趨于均衡。

兩臺服務器實現數據段交換的過程是，從文件日志的哈希表中找到兩個數據段在服務器中的位置以及在磁盤中的備份位置，然后服務器從磁盤中讀取需要交換的另一個數據段信息，覆蓋掉原有數據段的信息，并且將交換后的文件內容、磁盤中位置等信息保存到段日志文件中，更新哈希表。數據在哈希表項中的指針能夠找到數據的位置，保證了數據訪問的連續性。

DSE算法代碼如下：

DSE算法每次都根據Mtotal［i］選擇一臺帶寬負載最低的服務器Mtotal［low］和一臺帶寬負載最高的服務器Mtotal［high］。首先在低內存的帶寬負載服務器上選擇一個訪問次數最小的數據段M［low］［min］，此時這個數據段所在的服務器還需要Mavg－Mtotal［low］訪問次數即可達到均衡，所以交換得到的數據段的訪問次數大小不超過M［low］［min］＋Mtotal－Mtotal［low］。然后在高內存帶寬負載服務器上選擇一個數據段與已經選擇的M［low］［min］進行交換，此時高內存帶寬負載服務器上還需要減少Mtotal［high］－Mavg個訪問次數即可達到均衡，交換后高內存帶寬負載服務器得到數據段M［low］［min］，所以被交換出去的數據段的訪問次數不能超過M［low］［min］＋Mtotal［high］－Mavg。在高內存帶寬負載服務器上選擇數據段的訪問次數既不能超過M［low］［min］＋Mavg－Mtotal［low］，又不能超過M［low］［min］＋Mtotal［high］－Mavg。為了以最少的數據段交換次數實現負載均衡，在高內存帶寬負載服務器上選擇數據段時盡可能的選擇范圍內訪問次數最大的數據段。

4 實 驗

通過仿真實驗，模擬10臺以型號為64GB－1333 MHz大小內存作為內存服務器構成內存云集群。利用式 （1），計算出1333 MHz內存的帶寬MemBW 為10.664 Gb／s。RAMCloud的數據段大小Size為8M，所以一臺64G 內存云服務器中有8192個數據段。某一內存云服務器同時作為其它服務器的備份服務器，需預留一定的存儲空間作為備份。在本文實驗中，設定一臺服務器上有8G 作為服務器的備份空間，所以有60G 作為主服務器數據存儲與訪問，共計7168個有效數據段。實驗通過蒙特卡洛算法隨機生成一組10＊7168條0－100000的數據組成矩陣，表示在初始階段時，10臺服務器7168個數據段在60分鐘內的訪問次數。分別根據式 （4）和式 （6）計算出服務器初始狀態的訪問次數Mavg，以及吞吐量TP［i］，再根據式 （2）和式（3），相繼計算出服務器初始狀態的帶寬利用率η以及服務器時延MemLatency。

實驗1：DSE 算法的一般性實驗。分別設置集群負載均衡因子α為0.1和0.2，訪問次數在Mavg＊（1±α）時處于負載均衡，根據DSE 算法進服務器的數據塊進行交換，調整服務器的吞吐量，達到集群帶寬負載均衡狀態。然后計算出均衡后服務器的訪問次數Mtotal［i］，吞吐量TP［i］，帶寬負載η 以及服務器時延MemLatency，對比服務器初始狀態以及DSE 算法執行前后，服務器帶寬利用率η和時延變化MemLatency，如圖4、圖5所示。

圖4 服務器帶寬負載變化

圖5 服務器時延變化

由圖4可以看出整個集群的帶寬負載是不均衡的，有3臺服務器的帶寬利用率低于50%，有4臺服務器的帶寬利用率超過80%。這3臺低負載服務器的帶寬利用率遠低于集群的帶寬利用率 （64.25%），造成了帶寬資源的浪費，而由圖5可以看出，在高負載服務器上的時延明顯高于集群其它服務器。服務器數據吞吐量的差異，導致了集群的性能差異。

DSE算法對服務器的數據段進行交換，集群中每臺服務器的數據吞吐量更加均衡，降低了4臺高負載服務器的帶寬負載，同時也提高了低負載服務器的帶寬利用率，使集群的帶寬利用率更加均衡。DSE 算法明顯地降低了高負載服務器的時延，而低負載服務器的時延只是小幅度增加，最終集群中每臺服務器的時延都趨于均衡。α是影響負載均衡的因子，從圖中可以看出，當α＝0.2時集群帶寬利用率和時延的變化幅度都要比α＝0.1 時大。由圖4 可以看出，通過DSE 算法高負載服務器的時延有了大幅度的下降，α＝0.1時集群的時延比初始時延降低了12.61%，α＝0.2時集群的時延比初始時延降低了11.77%。

實驗2：集群服務器吞吐量低的實驗。初始數據段的訪問次數較低，服務器的數據吞吐量低，集群帶寬負載低。根據DSE算法對服務器的數據塊進行交換，然后對比服務器初始狀態以及DSE 算法執行前后，服務器帶寬利用率η和時延變化MemLatency，如圖6、圖7所示。

圖6 服務器帶寬負載變化

圖7 服務器時延變化

可以看出初始狀態下，集群的帶寬負載是不均衡的，整個集群的帶寬利用率都不高，高負載服務器的帶寬利用率也不超過80%。經過DSE算法，集群中每臺服務器達到了帶寬負載均衡。時延方面，帶寬負載均衡因子α＝0.1與α＝0.2時都能使高負載服務器的時延明顯降低，α＝0.1時，集群的時延比初始降低了3.87%，α＝0.2時集群的時延比初始降低了3.56%。顯然當集群服務器數據吞吐量較低時，DSE算法在減少服務器時延方面的效果不理想。在低負載服務器上，α的取值只會影響服務器的帶寬負載均衡的范圍，對降低時延的影響不明顯。

實驗3：集群服務器吞吐量高的實驗。實驗初始數據段的訪問次數高，服務器的數據吞吐量高，集群帶寬負載高。根據DSE算法對服務器的數據塊進行交換，然后對比服務器初始狀態以及DSE 算法執行前后，服務器帶寬利用率η和時延變化MemLatency，如圖8、圖9所示。

圖8 服務器帶寬負載變化

圖9 服務器時延變化

可以看出初始狀態下，集群的帶寬負載不均衡，整個集群的帶寬利用率很高，甚至有2臺服務器的帶寬利用率高于90%，同時他們產生了非常高的時延。經過DSE 算法，集群中每臺服務器達到了帶寬負載均衡。當帶寬負載均衡因子α＝0.1 時，集群的時延比初始降低了14.21%，α＝0.2時集群的時延比初始降低了10.05%。當集群服務器數據吞吐量較高時，DSE 算法可以大幅度的減少集群的時延。在高負載服務器上，α的取值不僅會影響服務器的帶寬負載均衡的范圍，而且對時延的降低也有顯著的影響。

5 結束語

實驗驗證了在RAMCloud集群上，通過DSE 算法周期性地對進行數據段交換，可以解決由于數據段訪問差異性造成的服務器內存帶寬負載不均衡的現象，從而達到集群帶寬負載均衡降低集群時延的目的。DSE 算法對數據吞吐量低的集群效果不明顯，對數據吞吐量高的集群效果顯著。集群帶寬負載均衡的范圍受到負載均衡因子的影響，可以根據用戶的需求來動態調整。負載均衡因子的取值在降低集群時延方面也有影響，負載均衡因子的取值越小，集群的時延降低越多。需要注意的是，負載均衡因子的取值，影響算法的時間復雜度，所以對于負載均衡因子的取值根據集群的負載以及用戶需求進行設置。

［1］ZHANG Yiming，PENG Yuxing，LI Dongsheng.Survery on distributed storage for on line data intensive applications ［EB／OL］. ［2013－03－26］.http：／／www.paper.edu.cn／releasepaper／content／201303－838（in Chinese）.［張一鳴，彭宇行，李東升.面向在線數據密集型應用的分布式存儲研究綜述［EB／OL］.［2013－03－26］.http：／／www.paper.edu.cn／releasepaper／content／201303－838.］

［2］Armbrust M，Fox A，Griffith R，et al.A view of cloud computing ［J］.Communications of the ACM，2010，53 （4）：50－58.

［3］DeCandia G，Hastorun D，Jampani M，et al.Dynamo：Amazon’s highly available key－value store［C］／／Proceedings of the 21st ACM Symposium on Operating Systems Principles.Washington DC：ACM，2007：205－220.

［4］Ousterhout JK，Agrawal P，Erickson D，et al.The case for RAMClouds：Scalable high－performance storage entirely in DRAM ［J］.ACM SIGOPS Operating Systems Review，2010，43 （4）：92－105.

［5］Tinnefeld C，Kossmann D，Boese JH，et al.Parallel join executions in RAMCloud ［C］／／Proceedings of the 30th International Conference on Data Engineering Workshops，2014：182－190.

［6］Goel B，Titos－Gil R，Negi A，et al.Performance and energy analysis of the restricted transactional memory implementation on haswell［C］／／Proceedings of the 28th IEEE International Parallel and Distributed Processing Symposium， 2014：615－624.

［7］Cabarcas F，Rico A，Etsion Y，et al.Interleaving granularity on high bandwidth memory architecture for CMPs［C］／／Proceedings of the International Conference on Embedded Computer Systems：Architectures，Modeling and Simulation，2010：250－257.

［8］Tolle KM，Tansley D，Hey AJG.The fourth Paradigm：Data－intensive scientific discovery ［J］.Proceedings of the IEEE，2011，99 （8）：1334－1337.

［9］Bao Y，Chen M，Ruan Y，et al.HMTT：A platform independent full－system memory trace monitoring system ［J］.ACM SIGMETRICS Performance Evaluation Review，2008，36 （1）：229－240.

［10］Rumble SM，Kejriwal A，Ousterhout JK.Log－structured memory for DRAM－based storage ［C］／／Proceedings of the 12th USENIX Conference on File and Storage Technologies，2014：1－16.

［11］Nakazato H，Nishio M，Fujiwara M.Data allocation method considering server performance and data access frequency with consistent hashing ［C］／／Proceedings of the 14th Asia－Pacific Network Operations and Management Symposium，2012：1－8.

［12］Shvachko K，Kuang H，Radia S，et al.The Hadoop distributed file system ［C］／／Proceedings of the IEEE 26th Symposium on Mass Storage Systems and Technologies，2010：1－10.

［13］Chen Lijun，Liu Zhaoyuan，Jia Weiwei.A snapshot system based on cloud storage log－structured block system ［C］／／Proceedings of the IEEE 11th International Conference on Networking，Sensing and Control，2014：392－398.

［14］NING Xingwang，LIU Peiyu.Log system design in support of linkage analysis of security audit and computer forensics［J］.Computer Engineering and Design，2009，30 （24）：5580－5583 （in Chinese）. ［寧興旺，劉培玉.支持審計 與取證聯動的日志系統設計 ［J］.計算機工程與設計，2009，30（24）：5580－5583.］