951
技術社區[雲棲]
RAMCloud：內存雲存儲的內存分配機製
現在全閃存陣列已經見怪不怪了，EMC的XtremIO，還有VNX-F（Rockies），IBM FlashSystem。全閃存真正為效率而生，重新定義存儲速度。憑借極致性能，高可用性，為您極大提高企業級應用效率。提到閃存的優勢，那麼毋庸置疑的就是速度！而在速度優勢背後，SSD則麵臨著價格、容量以及壽命等方麵的限製。
當然隨著技術的發展，成本的下降，SSD有可能會取代機械硬盤，成為下一代企業存儲的主要介質。機械硬盤可能轉變為磁帶的角色。
但是，閃存速度的確就是現在存儲係統的極限嗎？現在有需要基於內存的數據庫，比如Redis，TimesTen。也不得不提緩存係統的極佳實踐memcached。spark也把操作的中間數據全都放入到內存中，避免了Hadoop實時性和可用性差的問題，有可能對Hadoop的生態圈產生深遠影響。spark已經於2014年2月27日正式成為Apache基金會的頂級項目了。
RAMCloud，是一個完全使用DRAM的存儲係統，它的所有數據都保存到內存中。當然了為了故障恢複RAMCloud會將日誌和數據的備份持久化到普通硬盤中。在2014年的FAST會議中，RAMCloud發表了關於內存分配及管理機製的paper，並且被評為best paper，拜讀此文後，形成此文以分享心得。
1. Why not use malloc?
現在又很多memory allocator，比如C的malloc，Google的tcmalloc。當然了還有Java的內存管理及GC。但是它們有幾個問題，一個是效率底下，在訪問模式變化多端時極容易產生內存碎片。實驗表明，使用malloc隻能使內存的利用率最大到50%。
memory allocator可以分成兩類：non-copying and copying。non-copying allocator就是在內存分配後不會再移動它。對於單一的程序來說，這種分配方式非常自然，因為畢竟這些內存一旦申請它的大小也基本上不會再變了。但是對於存儲係統來說，文件可以修改，比如增大或者減小，那麼如果使用malloc，需要重新申請新的內存塊，那麼就非常容易產生碎片。比如係統剛開始新建了一片100B大小的文件，後來部分文件增大到130B，那麼，釋放的100B的空間有可能會產生碎片，比如以後沒有再寫<=100B大小的文件。（注：內存碎片的確在這種內存存儲係統中非常容易產生，而且作者設計的測試用例的確也使得malloc的內存利用率最大也就到50%。但是實際生產環境是否是這個樣子現在不得而知。總之RAMCloud的內存分配和管理的確挺好，但是malloc是否在生產環境下是否是真的如此不堪，現在也無法定論。關於malloc的內存分配，請閱《malloc內存分配與free內存釋放的原理》）。
對於copying allocator，通過garbage collector的確可以解決碎片的問題。但是缺點就是需要遍曆所有的數據才能夠重新分配。但是，處於性能的考慮，需要很多額外的內存（1.5倍到5倍）。這樣也就失去了通過碎片管理來提高內存使用率的初衷了。而且還有一個問題是需要長時間的服務暫停。拿Java的GC來說，它需要3-4秒，這個時間對於RAMCloud來說，已經可以檢測到一個故障的節點並且恢複64GB的數據了。（注: 不知道是否是不恰當的使用Java使得在此蒙冤了，盡管的確它是有問題）
2. RAMCloud概述
由於本文主要為了闡述基於日誌的內存分配管理，因此本節主要介紹storage的management，和為什麼需要基於日誌的內存分配管理機製，而摒棄原有的。
RAMCloud最適合的場景是已經將服務器分為應用服務器（主要實現生成網頁和執行業務規則等應用邏輯）和存儲服務器（為應用服務器提供長期共享存儲）的數據中心。這些數據中心一般支持許多應用，有的很小，隻使用一台服務器的一部分能力，有的很大，要用到數千台專用應用和存儲服務器。
而且，內存雲中保存的信息必須和硬盤一樣持久，單個存儲服務器的故障不能造成數據丟失和哪怕幾秒鍾的服務不可用。RAMCloud將所有數據存放在DRAM中，性能可以達到比目前最高性能的硬盤存儲係統還要高100～1000倍。在訪問延遲方麵，RAMCloud方案中運行在應用服務器中的一個進程從同一數據中心的存儲服務器中通過網絡讀取數百字節數據隻需5～10μs，而目前實際係統一般要花費0.5～10ms，具體取決於數據是在服務器內存緩存中，還是硬盤中。而且，一台多核存儲服務器每秒可以服務至少100萬次小讀取請求。而硬盤係統中同樣的機器每秒隻能服務1000～10000次請求。
係統架構圖如下。
每個storage server都包含兩個部分： Master和Backup。Master管理了存儲在memory中的object。Backup使用本地的機械硬盤或者固態硬盤保存了其他server的數據備份。Coordinator管理了Master和Backup配置信息，比如集群各個server之間的關係和各個備份的分配。但是Coordinator並不涉入數據的讀寫操作，因此也不會成為cluster的bottleneck或者降低係統的scalability。
RAMCloud提供了一個簡單的key-value的數據模型，數據（稱為object）都是連續存儲的。每個object都被長度不一的唯一的key標記。多個object被保存到table中，這個table有可能跨越多個server。object隻能以整體的方式進行讀寫。它為小object做了專門的優化，這也非常適合超大規模的web並發的請求。
每個Master都有自己的日誌，這些日誌被分成8M的塊，成為segment（段）。每個segment都會冗餘到其他的server的Backup，典型的配置都是冗餘2-3塊。在client寫操作的時候，冗餘發送到其他的節點，這些節點在把冗餘寫到memory的buffer後就會返回，而不是保存到本地磁盤後才返回，這樣保證了client的高速度寫入。這些buffer在某些時間點會flush到本地存儲。
3. Log Metadata
在基於日誌的文件係統中，為了快速的訪問日誌數據，日誌中使用了各種索引。RAMCloud是使用了hash table來訪問在memory中的數據。硬盤中的日誌在正常工作的環境下是永遠用不到的。它唯一被用到的機會就是故障恢複。日誌一共分為三種：
1). 元數據
包含了存儲基本單元object的table id，key，version，value。在數據恢複時，將根據最新version的條目來重建hash table。
2). 日誌摘要(log digest)
每一個新的日誌段都會有一個日誌摘要，這個摘要包含了所有屬於這個段的日誌。在數據恢複時，將根據段的最新的日誌摘要來加載所有的元數據。
3). tombstone(墓碑？)
這個日誌是比較特殊的。它代表了被刪除的object。日誌一旦寫入就不可修改，那麼如果一個object被刪除怎麼辦？在日誌中添加一條tombstone的記錄。記錄包含table id，key和version。在平時的操作中，tombstone是不會用到。但是在數據恢複時，它能保證被刪除的object不會被重建。
tombstone的機製很簡單但是也有很多問題。其中一個問題就是它的GC，畢竟它最終要在log中刪除。隻有在object被刪除後，tombstone才能被刪除。否則也就違背了引入tombstone的初衷了：通過它來防止被刪除的object的重建。在cleaner處理tombstone的log時，它會檢查tombstone所指定的segment是否不在任何的log中。如果不在，那麼說明object已經被刪除，否則說明該segment還有有效數據，該tombstone不能被刪除。
4. Two-level Cleaning
對於基於日誌的內存分配，主要的瓶頸就在於log cleaner。碎片管理，或者說內存回收是非常昂貴的，這就需要巧妙的設計。特別是隨著內存利用率的上升，回收的成本也越來越大。例如，對於一個內存利用率80%的情況，為了獲取2B的可用空間，平均情況下需要移動8B的數據。如果是90%，那麼移動9B的數據隻能帶來1B的空間。見下圖的上半部分。
對於Memory來說，帶寬不是問題，我們關注的是空間的利用率，畢竟相對來說DRAM還是比較貴的。對於硬盤來說，帶寬是昂貴的，可以說很多係統的瓶頸都是在硬盤的IO讀寫速度上，這也催生了很多基於memory的各種解決方案，當然也是RAMCloud需要解決的問題。因此，RAMCloud對於memory和disk采取了兩種不同的回收策略。
兩個階段的cleaning，使得memory的cleaning可以不影響Backup，這個結果就是一般來說memory的利用率要高於disk。memory的利用率可以達到90%，disk的要低得多。當然因為disk的cleaning的頻率更低，這也就可以理解了。
第一個level的cleaning，成為segment compaction，僅僅是處理了in-memory的segment，並沒有消耗網絡或者disk的IO。它每次壓縮一個segment，將它上麵的數據拷貝到其他的segment，這樣空出來的segment可以為其它所用。segment compaction在memory和disk中都維持了相同的log。但是由於在memory中的segment中刪除的object和tombstone都已經被徹底刪除了，因此它實際上占用了更少的空間。入下圖所示。
第二個level的cleaning稱為combined cleaning。顧名思義，這一level的cleaning不單單會cleaning disk的，同樣也會cleaning memory的。因為已經有segment compaction了，因此這一level的cleaning也是很有效率的。而且因為這一階段被延後進行了，可以合並更多的刪除操作了。
4.1 seglet
如果沒有segment compaction，那麼所有的segment都有相同的大小，默認情況下是8MB。因為有了壓縮，因此segment可以有不同的大小。當然我們不能采用傳統的heap allocator，因為那會產生碎片。RAMCloud將segment分為64KB的seglet。每個segment分為不同的seglet，seglet的數量就決定了segment的大小。你可能也有疑問，seglet的引入肯定也會引入碎片。實際上，對於一個segment來說，隻可能產生大約1/2個seglet大小的碎片，也就是32KB/8MB = 1/64=1.5%。也是由於seglet的引入，log現在變得不連續了，因為log有可能跨越多個seglet，RAMCloud使用了額外的機製來處理這種情況。
4.2 clean的觸發機製
two-level的cleaning的引入，引入了一個新的問題：什麼時候觸發segment compaction，什麼時候觸發combined cleaning？這個選擇將會影響到係統的性能，因為combined cleaning占用了係統珍貴的disk IO和network IO。這個policy 模塊，稱為balancer。接下來簡要的介紹一下balancer的機製。
一般情況下，在memory和disk的利用率不是很高的情況下，cleaner是不會工作的。因為cleaner的提早工作並不會有多高的效率。相反，如果cleaner的工作延後，那麼可以處理更多的刪除的object，可以回收更多的空間資源，因此，延後的cleaner是非常有意義而且有好處的。
那麼如何判斷memory的剩餘空間已不足呢？balancer通過以下方式進行判斷：假設L代表live objects所占用的空間使用率，F代表未分配的seglet所占整個空間的使用率，那麼如果F <= min( 0.1, ( 1 - L )/2 )，那麼cleaner就要開始工作了。一方麵，cleaner會盡量的延後工作使得回收工作更有效率，另一方麵，當預測到係統有可能會run out-of-memory時，cleaner會立即啟動以回收memory以保證有更多的memory可以使用。
那麼選擇segment compaction呢，還是選擇combined cleaner呢？一般來說，compaction會優先考慮因為它更有效率。但是有兩種情況下必須啟動combined cleaner：第一種情況就是tombstone太多了。因為segment compaction是不能單獨把tombstone標記的數據刪除的，它必須將這些數據從backup中刪除之後才可以刪除在memory中的tombstone。由於tombstone的越來越多，使得memory的使用率越來越高，導致compaction越來越低效。最終，選擇combined cleaner可以是係統刪除那些tombstone，也會使得以後的segment compaction更有效率。
那麼如何計算tombstone的多寡呢？balancer通過以下公式：假設T代表live tombstone所占用的空間使用率，L as above，T/( 1 - L ) >= 40%。也就是說，當tombstone占用了超過40%的可用空間的時候，combined cleaner會啟動以刪除這些tombstone，回收空間。40%是通過不同的條件，不同的負載下測試得出的經驗值。從這個公式也可以得出，在有很多小文件的使用場景下，這種cleaner會頻繁的調用。
第二個原因就是on-disk log太大時，為了防止disk run out-of-space，也為了避免係統恢複時重建時間太久，都會啟動combined cleaner。
小結一下，balancer在未使用的空間率太低時會啟動segment compaction並且a)disk space使用率較低 和b) tombstone不多。
5. Parallel Cleaning
現在CPU的主頻已經打破了摩爾定律了，但是CPU的核心數不斷增加。現在16 core，32 core的server CPU已經非常常見了。RAMCloud也充分利用了CPU 的multi-Core： 同時以多線程執行cleaner。
因為log的結構和簡單的meta-data，使得cleaner的並行執行變得簡單。因為log是不可修改的，cleaner在複製移動object時就不必擔心這些object會被修改。而且，hash table存儲的也是object的間接地址，因此更新hash table的object reference變得很簡單。因此基本的clean機製也變得簡單起來：
cleaner 拷貝live data到新的segment，也就自動的更新了hash_table的object reference，最後將cleaned segment就釋放出來了。
在clean線程和service線程在處理讀寫請求時有三個地方需要注意：
- 它們都需要在log的head添加數據
- 它們在更新hash table可能會有衝突
- 當segment在被某些service線程使用的時候，cleaner不能釋放它們。
5.1 日誌的並發更新
最簡單的cleaning方法就是把需要移動的數據添加到log的頭部。但是這樣話的會和service的寫請求衝突。為了避免這種情況，RAMCloud是將這些需要移動的數據移動到一個新的segment。每個cleaner都會申請一組segment用於保存移動的數據，隻有在申請segment的時候需要同步。在申請完成後，每個cleaner就可以操作自己所屬的segment了而無需額外的同步操作。在移動完成後，cleaner會把這些segment放到下一個的log digest中，同時被回收的segment也會在下一個log digest中也會被刪除。而且將這些數據移動到不同的segment而不是head segment中還有另外的好處：這些segment可以備份到不同的disk中，可以提高Master的吞吐量。
5.2 Hash Table的爭奪
Hash Table由於同時被cleaner和service threads使用，因此會有同步的問題。Hash table標明了哪些object是可用的並且保存了在memory中的地址。cleaner使用Hash table去確定某個object是否alive：通過判斷指向的地址是否真的是該object，如果是alive的，他就將Hash table中更新該object中的新地址。同時，service線程通過Hash table來讀
取或者刪除某個object。RAMCloud現在使用在每個hash的bucket上使用一個fine-gained lock來同步。
5.3 釋放內存空間的時機
當cleaner thread clean完成一個segment後，這個segment的空間可以被釋放或者被重用。在這個時間點，所有service thread都不會看到這個segment的數據，因為沒有hash table的條目指向這個segment。但是有可能老的service thread還在使用這個segment。所以free這個segment可能會導致非常嚴重的問題。
RAMCloud采用了一個非常簡單的機製來處理這個問題：係統直到所有當前的service thead數據請求處理完成才會釋放該segment。當然的service thread處理完成之後，釋放segment是安全的，因為所有後來的service thread都不可能使用到這個segment。這個設計很簡單，避免了使用鎖來完成這個普通的讀寫操作。
5.4 釋放disk空間的時機
當segment被clean後，在backup上的冗餘備份也需要刪除。然而，這個刪除隻能在被移動到的segment正確的寫到on-disk中的日誌之後。這需要兩個步驟。
- 合並後的segment需要在backup中完成冗餘拷貝。因為所有的冗餘拷貝都是異步進行傳輸的，因此隻有cleaner在接收到所有的響應接到後。
- 新的log digest必須包含新的合並的segment和刪除被clean的segment。
隻有上述數據被持久化後，這個冗餘備份就可以被安全的刪除了。
6. Avoiding Cleaner Deadlock
由於clean的過程中需要額外的內存，因此在內存利用率高的時候，clean的過程中有可能會耗掉最後的內存，run out-of-memory。因此形成了deadlock。
RAMCould為了避免這種deadlock采取了多種技術，首先，它會為cleaner申請一個seglet的pool。使得不會因為seglet的申請而導致死鎖。而且，它在clean一個segment時，會計算是否這個clean會帶來空間的利用率升高。比如下圖這個例子的clean會導致碎片更大，反而導致了空間的浪費。
還有一個措施是會申請專門的log digest以免申請額外的log digest時導致內存耗盡。
綜合以上技術，RAMCloud的空間利用率可以達到98%，而不會產生deadlock。
7. RAMCloud的未來
首先聲明本節內容不是來自於paper，而是搜集自網絡。
7.1 對比SSD
基於DRAM存儲設備比基於閃存的存儲設備速度更快，但成本也要高得多。
比如，2TB大小基於閃存的存儲設備成本大約為18萬美元；相比之下，存儲容量相同但基於DRAM的存儲設備成本高達約100萬美元。基於DRAM的驅動器讀取或寫入數據的時間隻要0.015毫秒，工作狀態下隨機速度達到了每秒可以處理40萬次I/O。這種驅動器最適合以寫操作為主的軟件以及使用高性能數據庫應用係統的公司。
基於閃存的存儲驅動器讀取或寫入數據的時間為0.2毫秒，工作狀態下最高讀取速度為每秒10萬次I/O，最高寫入速度為每秒2.5萬次I/O。這項技術也更適合以讀操作為主的應用。
7.2 應用場景
首先，RAMCloud可以是一個數據密集型應用的新架構，傳統的架構是應用程序連同代碼和數據被加載到一台服務器的主存儲中，瓶頸也是顯而易見的，各種複雜的數據操作，應用程序的大小，機器的處理能力都是瓶頸。
而在過去的10年中，一種服務於數百萬用戶的大型WEB應用架構出現了。其主要將應用程序代碼和數據存放於同一個數據中心中的不同服務器中。應用服務器隻存儲當前請求和處理瀏覽器的需求，而這種架構允許應用程序擴展到成千上萬的應用服務器和存儲。
但是不幸的是，在大型架構圖中，當服務器增加了4-5個數量級後，應用程序的複雜性，數據的訪問延遲都成了問題。比如當Facebook收到一個HTTP請求訪問網頁時，應用服務器必須發出130個以上的數據以生成HTML頁麵，這當中有指令請求的順序，而這些請求指令的累積是造成給用戶整體響應時間延遲的因素之一，所以需要相當大的開發量，以盡量減少對服務器請求的代碼大小和數量。
Mapreduce是最近幾年興起的一個新的技術，目的在於提高數據接入速度，消除了延遲問題，現在它解決了大規模的問題，但是如果是連續的數據訪問，將使得Mapreduce僅僅限於在隨機訪問數據的應用中使用。
RAMCloud則充分結合了兩者的優勢——規模化和低延遲：保留了Web應用程序的可擴展性，同時降低了數據訪問延遲以接近傳統的應用程序。
過去所有的Web應用程序都使用關係型數據庫存儲，但隨著數據規模的擴大，一個單一的關係型數據庫已經不能滿足他們的I/O需求。因此大家開始做係統升級，引進新的技術來擴展自己的存儲係統（比如多個數據庫間的數據分區）。
比如，盡管Facebook在2009年的時候就有4000個MySQL服務器，但由於大量交互式數據的調用，現有的存儲係統依舊不能滿足它的I/O需求，所以Facebook用了2000個Memcached用作分布式內存對象緩存服務器——將一些鍵值存儲於主內存中，但其瓶頸在於，需要處理Memcached和MySQL服務器之間的一致性，需要對應用軟件進行管理（比如刷新緩存值以更新數據庫），這無疑增加了應用的複雜性。
因此，NoSQL開始出現，用非關係型數據庫以鍵值對存儲，它的結構不固定，每一個元組可以有不一樣的字段，每個元組可以根據需要增加一些自己的鍵值對，這樣就不會局限於固定的結構，可以減少一些時間和空間的開銷，但是他們瓶頸依然是磁盤速度。
RAMCloud的原理之一是提供一個通用的存儲係統，其規模遠遠超出現有的係統，應用程序開發人員不需要采取特殊的方式（如NoSQL係統）。理想的狀態是，RAMCloud提供一個簡單的模型，易用、並且有擴展性，並對應用程序的城戰不需要做架構上的改變。
7.3 實際案例
目前一個可行的RAMCloud配置，每台服務器配置24GB的DRAM，這是高性價比的配置。擴展內存會導致成本的急劇增加。2000服務器會配備48TB的存儲空間，平均每GB成本65美元。據預測，到2020年，隨著DRAM技術的不斷完善，激勵1PB-10PB配置的RAMCloud時每GB成本僅需6美元。
RAMCloud已經在實際中有所應用。例如一個大型的網絡零售商或航空公司使用RAMCloud的花費在幾十萬美元。截止2009年8月Facebook所有非圖像數據大約有260TB。這可能接近了當今RAMCloud實用的上限。
像電視頻、照片、歌曲等數據還沒有大規模應用RAMCloud，然而RAMCloud實際已經可以用在所有在線的數據。隨著DRAM技術的不斷改進，RAMCloud在未來會更具吸引力。
7.4 號外
連12306都采用內存計算平台了，或許，基於memory的計算，
中國鐵路客戶服務中心12306網站選擇Pivotal GemFire分布式內存計算平台改造方案，根據係統運行數據記錄，在隻采用10幾台X86服務器實現了以前數十台小型機的餘票計算和查詢能力，單次查詢的最長時間從之前的15秒左右下降到0.2秒以下，縮短了75倍以上。
7.5 DRAM存儲係統是未來？
圖靈獎得主Jim Gray很早就提出了“內存將成為硬盤，硬盤將成為磁帶”的說法（出自2006年Tim Bray一篇討論網格計算的博客，2003年的訪談中他已經表達了同樣的意思）。2008年Dare Obsanjo在分析Twitter的架構時也看到，類似的新型應用的最大負擔是硬盤I/O，因此會傾向於將隨機操作都放到RAM裏，隻將順序操作留給硬盤。
尊重原創，轉載請注明出處： https://www.anzhan.me/index.php/archives/195
參考資料：
1. https://www.usenix.org/system/files/conference/fast14/fast14-paper_rumble.pdf
2. https://highscalability.com/are-cloud-based-memory-architectures-next-big-thing
3. https://www.ciotimes.com/cloud/ccc/52711.html
最後更新：2017-04-03 12:55:46