概述

本文力爭簡明扼要介紹ScyllaDB 的內存分配器實現。ScyllaDB 是用C++重寫了Cassandra，據稱在等同配置下，獲得了10倍的性能提升。我們知道，單純用C++重寫Java程序，並不能保證性能得到大幅度提升。一定有其它一些秘密武器，光憑藉這一點，就值得研究。

其實，ScyllaDB在系統設計與實現上，作了一些創新性工作，或者引入了一些比較新的技術方案。例如，用戶態TCP協議棧，用戶態IO調度器，用戶態任務調度器，以及本文要介紹的Log-Structured Memory Allocator 等等。詳情，請見seastar介紹。

本文著重介紹Log-Structured Memory Allocator（下文簡稱LSA）。關於LSA，在RAMCloud中有實現，論文在這裡。

看到Log-Structured 很多會想到Log-Structured Merge Tree(下文簡稱LSM）, leveldb等存儲引擎就是基於此實現的。其實，LSA和LSM有著異曲同工之妙。LSM的寫操作與LSA分配內存操作對應，LSM的刪除數據操作與LSA的釋放內存操作對應，LSM的Compaction操作與LSA的Compaction操作對應，LSM的寫限流功能與LSA的內存使用節流機制對應。 所以，LSA分配器並不陌生。

LSA解決什麼問題？

在存儲引擎實現中，內存利用率是一個非常重要的指標。當產生內存碎片後，系統即便時內存充足，也有可能面臨無法分配內存的情況。通過移動內存，騰挪空間的方式，整理出連續內存區域，是一種很自然想到的辦法。

例如，有些緩存系統在空閑時間，執行內存碎片回收的任務。通常，這類重型任務放在凌晨。 這個方案簡單直觀，能解決部分問題，也有明顯不足：首先，隨著雲計算業務發展，共享是緩存集群就沒有所謂空閑時間段了（各種業務高峰分布趨於均衡）；其次，時效性差，也有可能伺服器無法熬到空閑時期，內存碎片化已經很嚴重了；另外，在內存碎片整理期間，服務質量下降；

有沒有可控的，可持續的方式控制內存碎片程度呢？顯然是有的。LSA分配內存，在形成內存碎片後，能夠在持續可控地移動內存內容，騰挪空間，達到消除內存碎片，從而提升內存利用率。

所以，LSA 解決內存碎片化，利用率不高的問題。

ScyllaDB的LSA如何實現？

ScyllaDB採用Share-Nothing架構。具體地，為CPU的每一個logical-core構建相互獨立的資源，包括獨立的協議棧實例，獨立的任務引擎，獨立的IO調度器等等。顯然，也會為每一個logical-core構建獨立的內存分配器，即LSA實例。 大量採用lock-free設計，代碼就非常容易讀了。

先放一張大圖。

在這種圖中，虛線左邊是LSA的介面，虛線右邊是LSA的實現邏輯。

先看看LSA介面：

• Region: LSA將虛擬內存抽象為若干Region, 分配的內存對象必須屬於某一個Region，並且其所屬的Region負載該內存對象的釋放。
• RegionGroup: 一個Region 屬於唯一一個RegionGroup。RegionGroup主要用於內存容量統計與限制，RegionGroup可以嵌套。根據業務邏輯，將不同的Region聚合在一起。
• Tracker: 這個是一個控制類，通過參數來控制LSA行為；
• AllocationStrategy: 每一個Region擁有唯一的AllocationStrategy對象，通過它來分配內存，釋放內存。

在看看LSA實現部分：

• Segment: LSA管理內存的最小單位, 它將連續內存區域切分為固定尺寸段，稱為Segment;
• SegmentPool: 每一個logical-core 擁有全局的對象，該對象管理內存Segment; 每一個Segment都會對應一個descriptor, 這些descriptor存放在SegmentPool中。該SegmentPool為該logical-core上所有的Region服務。
• SegmentZone: SegmentPool將連續的內存區域切分為若干Segment, 這些Segment的集合，稱之為SegmentZone。SegmentPool向系統申請內存後，就會創建一個SegmentZone, 創建後，它的Size就不會改變。
• ObjectDescriptor：每一個內存對象都會分配一個ObjectDescriptor, 用於描述對象是存活還是被是否，描述對象尺寸，記錄對象遷移函數，對齊尺寸。

系統啟動後，為每一個logical-core構造一個LSA實例。初始狀態，SegmentPool 為空。當某個Region分配內存對象時候，SegmentPool會申請批量的Segment, 構成一個SegmentZone。然後，分配一個Segment 給Region。 Region在該Segment中分配一塊區域即可。

SegmentPool 內存Layout示意圖。

LSA 騰挪空間的過程叫做Compaction，主要做的事情就是通過騰挪空間，回收內存。那麼，Compaction在什麼時機觸發呢？

• 在CPU空閑事情，會依次對可以做Compaction的Region試圖做Compaction動作；
• 在無法分配出要求的內存時候，進入Compaction動作，騰挪一些空間出來；
• 通過API 主動觸發回收內存操作；

LSA通過RegionGroup來實現內存節流機制。如果RegionGroup關聯的Region使用的內存超過閾值了，通過RegionGroup提交的函數就會緩存在隊列中，直到超時，或者有內存空間被回收，導致該RegionGroup關聯的Region內存使用量降低到閾值以下。 這個機制，可以保證某些操作不至於無限制使用內存，而導致其他組件無內存可用，導致服務不可用。

結束

不知道為什麼，分析完代碼後，突然覺得沒什麼好寫的。好尷尬。

最近，在測試Parallel Redis的過程中，發現內存碎片化嚴重。看看ScyllaDB是如何解決的。Log-Structured Memory Allocator 將會被移植到Pedis, 以期提升內存利用率。

最後，Pedis項目期待同仁參與。