分布式數(shù)據(jù)處理系統(tǒng)內(nèi)存對象管理問題分析

張雄　陸路　石宣化

摘要：通過從程序語言的特性、垃圾回收機(jī)制、內(nèi)存對象的序列化機(jī)制到基于區(qū)域的內(nèi)存管理機(jī)制分析了內(nèi)存對象的管理存在的問題，并分析了內(nèi)存對象的生命周期在內(nèi)存對象管理中能發(fā)揮的作用。提出了基于內(nèi)存對象的生命周期對內(nèi)存進(jìn)行區(qū)域化管理的思路，可以從根本上解決垃圾回收問題。

關(guān)鍵詞：大數(shù)據(jù)；內(nèi)存對象管理；分布式數(shù)據(jù)處理系統(tǒng)

Abstract：Through analysis of the characteristics of program languages， mechanism of garbage collection， serialization of in-memory data-objects and region-based memory management， most existing problems with memory management are exposed. Whats more， the lifetime of in-memory data objects can be key factor in memory management. Thus a solution is region-based memory management combined with the lifetime of in-memory data objects， which can solve the garbage collection problem.

Key words：big data； in-memory data-object management； distributed data processing system

以MapReduce為代表的分布式數(shù)據(jù)處理系統(tǒng)使得人們可以以增加硬件資源的方法來處理海量數(shù)據(jù)。已有的大量研究集中在多核或分布式環(huán)境下的可擴(kuò)展性和容錯性。最新的研究工作表明：這類系統(tǒng)計(jì)算執(zhí)行效率是一個被忽視的重要問題。導(dǎo)致執(zhí)行效率低下的一個重要原因是代表性的開源系統(tǒng)，如Hadoop和Spark，都使用帶有托管執(zhí)行環(huán)境的高級語言開發(fā)，從而降低分布式環(huán)境下的部署和調(diào)試的難度。托管環(huán)境提供內(nèi)建的高級功能，比如自動內(nèi)存管理和并發(fā)模型，使得其對象模型的底層實(shí)現(xiàn)非常復(fù)雜，帶來額外的內(nèi)存和中央處理器（CPU）開銷。工業(yè)級托管環(huán)境的現(xiàn)代即時編譯優(yōu)化很大程度上解決了中間代碼（IR）的解釋執(zhí)行效率問題，但是難以解決復(fù)雜對象模型實(shí)現(xiàn)帶來的對象管理開銷問題。以Java虛擬機(jī)（JVM）為例：（1）每個對象在JVM中會有一個頭結(jié)構(gòu)保存元數(shù)據(jù)，頭結(jié)構(gòu)除了記錄對象類型，還要支持垃圾收集和并發(fā)加鎖優(yōu)化；（2）所有（非原生類型）對象都在堆中創(chuàng)建，因此每個存活對象至少要有一個額外變量保存其引用；（3）泛型容器的元素如果是基本類型，必須首先被裝箱為對象類型；（4）主流垃圾收集算法都是基于對象追蹤的，因此堆中有大量的存活對象時，垃圾收集器需要耗費(fèi)大量CPU周期來標(biāo)記存活對象[1]。隨著處理數(shù)據(jù)量的增大，內(nèi)存對象越來越多，尤其是長駐內(nèi)存對象的存在[2]，內(nèi)存對象管理會帶來嚴(yán)重的內(nèi)存膨脹和CPU開銷問題。內(nèi)存膨脹會間接影響執(zhí)行性能：如果內(nèi)存足夠，更大的內(nèi)存占用會導(dǎo)致更頻繁的垃圾回收；如果內(nèi)存不足，緩存的數(shù)據(jù)需要部分丟棄或者換出到磁盤，導(dǎo)致額外的重計(jì)算或輸入輸出（IO）開銷。

最初用來解決這類問題的方法是垃圾收集優(yōu)化。垃圾收集優(yōu)化分為兩個方面：一方面是通過參數(shù)[3]調(diào)優(yōu)，避免頻繁垃圾收集；另一方面是通過優(yōu)化垃圾收集算法實(shí)現(xiàn)來提高垃圾收集的性能[4]。垃圾收集優(yōu)化的方法只是減緩了垃圾收集操作的影響，實(shí)際上內(nèi)存對象管理所存在的問題仍然存在。后續(xù)的性能優(yōu)化方案逐漸從垃圾收集的優(yōu)化深入到內(nèi)存對象管理本身，針對數(shù)據(jù)對象在內(nèi)存中的存儲進(jìn)行優(yōu)化，主要包括序列化存儲[5]，基于區(qū)域的內(nèi)存管理[6]。這種解決方案從根本上解決了對象對內(nèi)存資源的占用，但是仍然無法避免對象的存在。在對象存儲優(yōu)化的基礎(chǔ)上，目前分布式系統(tǒng)的一些上層特定應(yīng)用，例如Spark 結(jié)構(gòu)化查詢語言（SQL），利用特定的數(shù)據(jù)結(jié)構(gòu)解決了對象存儲優(yōu)化的不足，從根本上消除對象。當(dāng)然，由于是特定的應(yīng)用系統(tǒng)，使用范圍窄。

1 垃圾收集優(yōu)化

垃圾收集問題是內(nèi)存對象管理中最重要的問題之一，也是影響系統(tǒng)性能的關(guān)鍵因素。因此，最初針對內(nèi)存對象管理問題的解決方法都是從垃圾收集入手。

1.1 垃圾收集調(diào)優(yōu)

垃圾收集調(diào)優(yōu)是最傳統(tǒng)的垃圾收集優(yōu)化技術(shù)，也是一些長時間運(yùn)行的低延遲Web服務(wù)所推薦的方法。一些開源分布式數(shù)據(jù)處理系統(tǒng)，例如Cassandra和HBase都使用以延遲為中心的方法來避免長時間垃圾收集開銷[7]。以上所述垃圾收集調(diào)優(yōu)方法的關(guān)鍵在于：用標(biāo)記清除算法（CMS）的垃圾收集控制器代替原有以吞吐量為中心的垃圾收集；調(diào)整標(biāo)記清除算法的垃圾收集控制器參數(shù)以降低垃圾收集開銷。

1.2 垃圾收集算法優(yōu)化

目前的垃圾收集算法有引用計(jì)數(shù)法、標(biāo)記清除算法、拷貝收集算法等，不同的垃圾收集算法讓內(nèi)存對象管理有更多的選擇來處理對象的回收。垃圾收集算法的優(yōu)化性能要到達(dá)最優(yōu)一般有特定場景，例如非統(tǒng)一內(nèi)存訪問（NUMA）感知的垃圾回收器[8]。并且，垃圾收集算法的優(yōu)化只是掩蓋了內(nèi)存對象管理的問題，內(nèi)存對象的自動化管理存在的問題仍然存在，頻繁調(diào)用垃圾收集的本質(zhì)因素沒有解決。

1.3 程序語言優(yōu)化

分布式數(shù)據(jù)處理系統(tǒng)使用高級面向?qū)ο笳Z言進(jìn)行開發(fā)會導(dǎo)致內(nèi)存對象管理的問題，而傳統(tǒng)的面向機(jī)器的語言，如C、C++，則不存在內(nèi)存對象管理存在的問題。為了追求性能上的優(yōu)勢，一部分企業(yè)機(jī)構(gòu)會選擇用這些傳統(tǒng)的語言來改寫目前的分布式數(shù)據(jù)處理系統(tǒng)，但是失去了高級語言特性的系統(tǒng)開發(fā)難度非常之大，并且不利于系統(tǒng)的更新。

2 對象存儲的優(yōu)化策略

垃圾收集的優(yōu)化并沒有考慮內(nèi)存對象管理所存在的問題的本質(zhì)，即內(nèi)存中的對象仍然是自動化管理的。所以一些系統(tǒng)將對象用序列化的方式存放到內(nèi)存以減少內(nèi)存的占用來防止頻繁垃圾收集，或者將常規(guī)的內(nèi)存對象管理方法替換為針對對象標(biāo)記回收的區(qū)域內(nèi)存管理方法來消除垃圾收集。這一類方法從內(nèi)存對象管理的本質(zhì)上考慮了性能問題。

2.1 序列化存儲

目前的分布式數(shù)據(jù)處理系統(tǒng)，如Hadoop和Spark，都支持將中間數(shù)據(jù)對象序列化為byte數(shù)組，從而減少對象在內(nèi)存中存儲的占用。Hadoop系統(tǒng)中的對象大部分都是臨時的數(shù)據(jù)對象，因此Hadoop僅將Map的輸出數(shù)據(jù)序列化成byte數(shù)據(jù)，存放到磁盤，然后通過Shuffle傳輸給reduce task。盡管不存在內(nèi)存對象管理的問題，但是序列化機(jī)制確實(shí)對分布式數(shù)據(jù)處理系統(tǒng)有重要作用。Spark系統(tǒng)不僅在Shuffle階段提供序列化機(jī)制，還在Cache時提供了序列化選擇，Cache時Spark會將彈性分布式數(shù)據(jù)集（RDD）中的數(shù)據(jù)保存到內(nèi)存，用戶可以選擇是否采用序列化保存數(shù)據(jù)。Spark之所以支持非序列化保存，是因?yàn)樾蛄谢瘷C(jī)制存在序列化和反序列化的開銷。一般來說，序列化機(jī)制能夠有效降低內(nèi)存對象的占用，但是要在Cache數(shù)據(jù)對象時執(zhí)行序列化操作，而在使用對象時執(zhí)行反序列化操作。

序列化存儲降低了內(nèi)存對象的占用，但是應(yīng)用仍然基于對象執(zhí)行的。因此在序列化和反序列化的基礎(chǔ)上，內(nèi)存對象管理仍然需要考慮中間對象的管理，當(dāng)數(shù)據(jù)量大時，對象的回收仍然會影響系統(tǒng)的性能[9]。

2.2 基于區(qū)域的內(nèi)存管理

無論是基于垃圾收集調(diào)優(yōu)還是序列化存儲，都是由內(nèi)存管理機(jī)制自動標(biāo)注對象的生命周期，始終存在對象的操作，就必然會需要內(nèi)存管理機(jī)制根據(jù)標(biāo)注回收無需再使用的對象，也就必然會導(dǎo)致垃圾收集。從內(nèi)存對象相反的一個方向分析，C、C++等語言完全手動的標(biāo)注內(nèi)存中使用的對象，手動的回收對象?；趨^(qū)域的內(nèi)存管理綜合了自動化和完全手動標(biāo)注內(nèi)存對象的兩種策略，采取了繞過垃圾收集的策略，將一部分對象統(tǒng)一標(biāo)記后直接存儲到堆外區(qū)域，整塊回收區(qū)域內(nèi)的對象，從而消除頻繁垃圾收集，解決內(nèi)存對象管理的問題。

FACADE[10]系統(tǒng)是基于區(qū)域的內(nèi)存管理的典型實(shí)例。FACADE以程序分析為基礎(chǔ)，在程序代碼中由用戶標(biāo)識需要轉(zhuǎn)換的Java對象。FACADE會首先識別用戶標(biāo)注的Java對象，將其轉(zhuǎn)換為輕量級的FACADE對象并通過byte形式保存FACADE到堆外內(nèi)存，極大地減少了對象對內(nèi)存的占用，而FACADE相比序列化更加進(jìn)一步消除對象之處在于它同時轉(zhuǎn)換了Java對象的操作代碼。用戶自定義的操作函數(shù)是基于Java對象的，F(xiàn)ACADE轉(zhuǎn)換Java對象為FACADE對象后，同時將操作函數(shù)轉(zhuǎn)換為基于FACADE對象的操作函數(shù)，完全實(shí)現(xiàn)了對象的消除。FACADE的內(nèi)存對象管理采取了整塊分配和整塊回收的原則，一方面配合FACADE對象的存儲方式；一方面減少了垃圾收集開銷，相比傳統(tǒng)的內(nèi)存對象管理取得了非常好的效果。

盡管FACADE的內(nèi)存對象管理已經(jīng)從很大程度上解決了對象管理的垃圾收集問題，但是它基于一個很強(qiáng)烈的假設(shè)：在整塊分配和整塊回收的操作間隔內(nèi)的所有對象在內(nèi)存中的存活時間都是相同的。在一些分布式數(shù)據(jù)處理系統(tǒng)中，例如Spark和Flink，將作業(yè)劃分為有向無環(huán)圖，按照每個階段執(zhí)行。這類系統(tǒng)中的數(shù)據(jù)對象在內(nèi)存中的存活時間就非常復(fù)雜，如果有用戶將數(shù)據(jù)Cache到內(nèi)存，數(shù)據(jù)對象的存活時間持續(xù)整個作業(yè)執(zhí)行期；如果是Shuffle階段的數(shù)據(jù)對象，數(shù)據(jù)對象可能會在多個階段的執(zhí)行期內(nèi)都存活在內(nèi)存中。所以，F(xiàn)ACADE在內(nèi)存對象的管理上忽略了內(nèi)存對象的生命周期。

Broom[11]綜合考慮了基于區(qū)域的內(nèi)存管理的特點(diǎn)以及內(nèi)存對象的生命周期的特點(diǎn)，Broom以NET CLR平臺為研究對象，將內(nèi)存對象的存放區(qū)域進(jìn)一步區(qū)分為：可轉(zhuǎn)移區(qū)域，用來存放操作的傳遞消息，同一時間只有一個操作可以訪問該區(qū)域；操作所需區(qū)域，針對某個操作私有的對象存儲區(qū)域，該區(qū)域內(nèi)的對象的生命周期與相應(yīng)的操作生命周期相同；臨時區(qū)域，存放一些臨時的數(shù)據(jù)對象。由于Broom基于閉源的系統(tǒng)實(shí)現(xiàn)而且作為short paper對系統(tǒng)實(shí)現(xiàn)提及較少，所以能夠獲取的信息只在于基于區(qū)域的內(nèi)存管理與內(nèi)存對象生命周期特點(diǎn)的結(jié)合是消除垃圾收集所必須考慮的兩個因素。

3 特定應(yīng)用領(lǐng)域的優(yōu)化

大多優(yōu)秀的開源分布式數(shù)據(jù)處理系統(tǒng)，如Hadoop和Spark，都基于底層的系統(tǒng)實(shí)現(xiàn)了上層應(yīng)用領(lǐng)域的生態(tài)系統(tǒng)[12]，例如Spark生態(tài)系統(tǒng)包括Spark SQL、Spark Streaming、Spark GraphX和Spark MLlib。特定應(yīng)用領(lǐng)域的分布式數(shù)據(jù)處理系統(tǒng)在底層數(shù)據(jù)系統(tǒng)的基礎(chǔ)上定義了特定的計(jì)算結(jié)構(gòu)，從而可以實(shí)現(xiàn)更加復(fù)雜的內(nèi)存對象管理機(jī)制。在最初Java等高級語言被應(yīng)用在數(shù)據(jù)分析系統(tǒng)時，除了受益于高級語言的特性，一些系統(tǒng)也意識到其在內(nèi)存對象管理上的不足，因此結(jié)合特定的結(jié)構(gòu)進(jìn)行優(yōu)化[13]，例如SQL。Shark等針對data-intensive的數(shù)據(jù)庫管理系統(tǒng)，將Java對象轉(zhuǎn)化為Telegraph數(shù)據(jù)流，在內(nèi)存分配上整存整取，繞過Java的內(nèi)存管理方法[14]。Shark使用基于列的內(nèi)存存儲和動態(tài)查詢優(yōu)化來提高SQL查詢的性能。Apache項(xiàng)目Tungsten基于Spark SQL實(shí)現(xiàn)，將傳統(tǒng)的關(guān)系表結(jié)果轉(zhuǎn)換為以列為結(jié)構(gòu)的字節(jié)序列，同時將SQL操作全部轉(zhuǎn)換為基于字節(jié)序列的操作。

分布式數(shù)據(jù)處理系統(tǒng)內(nèi)存對象管理的解決方案各具優(yōu)點(diǎn)和缺點(diǎn)，具體見表1。

4 結(jié)束語

分布式數(shù)據(jù)處理系統(tǒng)按照數(shù)據(jù)流的路徑可以分為控制路徑和數(shù)據(jù)路徑，控制路徑由系統(tǒng)框架支持和實(shí)現(xiàn)，數(shù)據(jù)路徑由用戶定義和實(shí)現(xiàn)。我們發(fā)現(xiàn)：控制路徑的編程實(shí)現(xiàn)更多的從對象模型的高級特性中獲益，包括類型的運(yùn)行時動態(tài)識別、并發(fā)同步操作的偏向鎖優(yōu)化和自動對象內(nèi)存管理等。數(shù)據(jù)路徑的編程實(shí)現(xiàn)很少使用語言的高級特性。數(shù)據(jù)路徑的實(shí)現(xiàn)由用戶自定義，具體包括用戶自定義類型（UDT）和用戶自定義方法（UDF）。UDT定義的是數(shù)據(jù)路徑中實(shí)際操作的對象類型，而UDF定義了對這些數(shù)據(jù)類型執(zhí)行的操作。UDT通常是基本類型的淺層組合和常用方法的實(shí)現(xiàn)封裝，很少會使用復(fù)雜的繼承層次和多態(tài)。

比如，通過定義接口來抽象化模塊之間的交互，進(jìn)而通過工廠模式，依賴注入來支持靈活的模塊和插件加載，而這些設(shè)計(jì)模式依賴于多態(tài)和反射等語言特性。框架負(fù)責(zé)任務(wù)的并行化執(zhí)行和同步機(jī)制，因此依賴于托管環(huán)境的并發(fā)執(zhí)行模型，比如線程創(chuàng)建和加鎖操作。由于并發(fā)執(zhí)行由框架負(fù)責(zé)，UDF本身都是串行代碼，在UDF內(nèi)部使用加鎖操作通常沒有意義，更不可能會在UDT數(shù)據(jù)對象上加鎖。因此，UDT并不依賴于一個復(fù)雜的對象模型實(shí)現(xiàn)。比如：（1）當(dāng)沒有多態(tài)導(dǎo)致的虛方法派發(fā)時，也沒有使用反射時，不需要在對象頭部記錄對象的運(yùn)行時類型；（2）當(dāng)對象沒有加鎖操作時，也不需要在頭部存儲偏向鎖狀態(tài)；（3）UDT數(shù)據(jù)對象的生命周期具有很強(qiáng)的規(guī)律性，如果能夠跳過JVM的內(nèi)存管理，不僅消除了垃圾收集的CPU開銷，也不需要在對象頭部存儲垃圾收集所需的狀態(tài)信息。

最重要的一點(diǎn)是：數(shù)據(jù)對象的生命周期具有很強(qiáng)的規(guī)律性。我們發(fā)現(xiàn)：在以Spark為代表的新一代通用數(shù)據(jù)并行系統(tǒng)中，作業(yè)執(zhí)行時通常有幾類數(shù)據(jù)容器會持有數(shù)據(jù)對象，而數(shù)據(jù)對象的生命周期和持有它的數(shù)據(jù)容器的生命周期有很強(qiáng)的關(guān)聯(lián)性：

（1）UDF變量。包括UDF對象的字段和UDF局部變量，前者的生命周期剛好為一個任務(wù)的執(zhí)行時間，其存活時間內(nèi)時所持有的對象生命周期由該字段的賦值操作決定，但最長不超過任務(wù)的執(zhí)行時間；后者的生命周期為一次UDF方法的調(diào)用，因此其持有的數(shù)據(jù)對象最多存活一次方法調(diào)用，可以視為臨時對象。

（2）緩存數(shù)據(jù)集。緩存數(shù)據(jù)集的生命周期由應(yīng)用程序顯示決定，其持有的數(shù)據(jù)對象的生命周期具有與該RDD等同的生命周期。

（3）Shuffle緩沖區(qū)。不考慮溢出到磁盤的情況，Shuffle緩沖區(qū)的生命周期也剛好為一個任務(wù)的執(zhí)行時間。其持有的數(shù)據(jù)對象的生命周期較為復(fù)雜，在聚合計(jì)算的過程中，Shuffle buffer僅為一個Key數(shù)據(jù)對象保存一個數(shù)據(jù)對象作為當(dāng)前聚合的結(jié)果。

一種可行的方法是通過自動轉(zhuǎn)換數(shù)據(jù)處理應(yīng)用程序來減少程序運(yùn)行時創(chuàng)建的UDT數(shù)據(jù)對象的數(shù)量。轉(zhuǎn)換工作對應(yīng)用開發(fā)人員完全透明，不會限制數(shù)據(jù)并行編程模型的表達(dá)能力和靈活性。

致謝

本研究得到華中科技大學(xué)金海教授的指導(dǎo)，謹(jǐn)致謝意！

參考文獻(xiàn)

[1] JONES R， HOSKING A， MOSS E. The Garbage Collection Handbook ： the Art of Automatic Memory Management [M]. USA： CRC Press， 2012

[2] ZAHARIA M， CHOWDHURY M， DAS T， et al. Resilient Distributed Datasets： a Fault-Tolerant Abstraction for in-Memory Cluster Computing [C]//Proceeding in 9th USENIX Conference on Networked Systems Design and Implementation （NSDI）. USA： USENIX Association， 2012： 141-146

[3] Cassandra Garbage Collection Tuning， Find and Fix Long GC Pauses [EB/OL]. [2013-11-14]. http：//aryanet.com/blog/cassandra-garbage-collector-tuning

[4] Laboratory for Web Algorithmic [EB/OL]. [2014-10-12].http：//law.di.unimi.it/datasets.php

[5] CARPENTER B， FOX G， KO S H， et al. Object Serialization for Marshalling Data in a Java Interface to MPI[C]//ACM Java Grande Conference. USA： ASM， 1970： 66-67

[6] MADS T， JEAN-PIERRE T. Region-Based Memory Management [J]. Information & Computation， 1997， 132（2）：109-176

[7] The Garbage Collector and Apache Hbase [EB/OL]. （2016-02-18）[2014-03-22].http：//hbase.apache.org/book.html#gc

[8] 浦云明. JAVA垃圾收集器算法分析及垃圾收集器的運(yùn)行透視[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2003 （11）： 39-41

[9] MILLER H， HALLER P， BURMAKO E， et al. Instant Pickles： Generating Object-Oriented Pickler Combinators for Fast and Extensible Serialization [J]. ACM Sigplan Notices， 2013， 48（10）：183-202

[10] NGUYEN K， WANG K， BU Y， et al. FACADE： A Compiler and Runtime for （Almost） Object-Bounded Big Data Applications [J]. ACM Sigplan Notices， 2015， 50（4）：675-690. DOI： 10.1145/2775054.2694345

[11] GOH I， GICEVA J， SCHWARZKOPF M， et al. Broom： Sweeping Out Garbage Collection from Big Data Systems [C]//15th Workshop on Hot Topics in Operating Systems （HotOS XV）. USA： ACM， 2015

[12] 胡俊， 胡賢德， 程家興. 基于Spark的大數(shù)據(jù)混合計(jì)算模型[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2015（4）： 214-218

[13] SHAH M A， FRANKLIN M J， MADDEN S， et al. Java Support for Data-Intensive Systems： Experiences Building the Telegraph Dataflow System [J]. Sigmod Record， 2001， 30（4）：103-114

[14] XIN R. S， ROSEN J， ZAHARIA M， et al. Shark： SQL and Rich Analytics at Scale[C]// Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. USA： ASM， 2013：13-24. DOI： 10.1145/2463676.2465288