基于內存映射文件的復雜對象快速讀取方法

黃向平，彭明田，楊永凱

(1.中國民航信息網絡股份有限公司，北京 101318;2.民航旅客服務智能化應用技術重點實驗室，北京 101318)

0 引 言

后臺高并發高性能系統設計過程中，經常碰到數據訪問寫少讀多的場景。比如民航航班運價搜索平臺，航班運價數據更新不頻繁，但搜索過程需讀取并處理大量復雜數據。如何解決復雜數據讀取效率的問題，是系統性能優化的關鍵問題之一。

Linux環境下高并發高效率的數據訪問技術有NoSQL內存數據庫[1]、嵌入式數據庫[2]等。NoSQL(not only SQL)內存數據庫典型代表有redis[3]，它是一種key-value類型的數據庫產品，在大數據平臺[4]、緩存系統[5]中得到了廣泛的應用，相對于關系型數據庫，具有服務響應快、并發訪問高、易于擴展、易于開發等優點。嵌入式數據庫是一種輕量級的、與應用進程在同一個地址空間的數據庫，Berkeley DB是目前應用較廣泛、較穩定的技術選擇，不但適用于嵌入式系統，也同樣適用于高性能后臺服務系統[6]，優點是不需要進程間通信，讀取效率很高。

對上述兩種高性能數據庫的研究發現，當數據結構復雜、讀取頻繁時仍會有性能問題。鑒于此，文中提出了基于內存映射文件的復雜對象快速讀取方法。主要從三個方面對讀取過程進行改進：(1)通過內存映射文件[7]，省掉了內核態到用戶態的內存拷貝操作，從而提高數據讀取效率；(2)優化文件內數據格式，無需轉化即可直接使用，從而提高數據格式轉化的效率；(3)復用模板庫和容器，避免重新編碼實現一些常用數據結構，從而提高開發效率。

1 傳統數據庫技術

1.1 內存數據庫

近年來，隨著計算機技術的不斷發展，特別是互聯網應用的擴張普及，對于高并發環境下的數據庫技術提出了高可用、高性能的要求。在一些諸如交通、電信、金融、電子商務之類的應用中，對于響應時間有非常高的要求。當前隨著半導體技術的發展，摩爾定律依然有效，內存芯片的價格不斷降低，服務器內存存儲容量已經向TB級別邁進。相應的64位CPU和Linux操作系統的普及，操作系統尋址空間達到了2的64次方。內存資源緊張昂貴的歷史一去不復返，如何充分、有效地利用內存資源成了軟件設計的重點。因此，對于那些數據訪問實時性要求很高的應用來說，開始考慮把整個數據庫或者部分數據存儲于內存之中，從而產生了內存數據庫的概念。

一般定義上的內存數據庫，是指數據常駐內存，在數據讀寫執行過程中沒有內外存之間的數據I/O，顯然，它需要較多的物理內存，但也不一定把整個數據庫置于內存當中。和傳統的基于機械磁盤來存儲數據的數據庫系統相比，擁有更快的數據讀寫速度，因為內存數據庫在指令執行過程當中沒有磁盤讀寫操作。同時，內存I/O性能遠高于磁盤，所以基于內存的數據庫讀寫性能也遠高于傳統磁盤數據庫。

典型的內存數據庫如memcached和redis，是一種nosql數據庫，也是一種鍵值對數據庫。通過在內存里維護一個統一的巨大的哈希表，能夠存儲各種格式的數據。一般的使用方法是減少數據庫訪問次數，以此提高系統服務響應時間，也可以把全量數據存儲于內存數據庫當中，完全替代傳統關系型數據庫。通常情況下，受制于物理內存空間大小，在數據容量達到指定值后，系統就基于LRU(least recent used)算法[8]自動刪除不適用的數據。可以說這類內存數據庫是為緩存而設計的服務器，并沒有過多考慮數據的永久性問題。不過redis加入了virtual memory改進方案，把很少使用的value保存到磁盤，而所有key保存于內存當中。因此redis可以應用于海量復雜數據的高性能讀寫場景。

此類內存數據庫是基于epoll網絡事件處理模型的C/S服務架構，支持高并發的網絡連接，充分利用了網絡I/O能力。如果把客戶端與服務端部署于同一臺服務器，則能避免網絡延遲，只需進程間通信即可完成數據訪問，提升響應速度。

1.2 嵌入式數據庫

嵌入式數據庫通常與嵌入式操作系統及具體的應用集成在一起，無需獨立運行數據庫服務實例，由程序直接調用響應的API即可讀寫數據，不需要對某種查詢語言進行解析，也不需要生成解析計劃。不僅僅適用于嵌入式操作系統，在一些高性能系統當中也直接連接嵌入式數據庫，和應用程序運行在同一個地址空間，避免了進程間通信的消耗，因此具有較高的運行效率。

Berkeley DB是目前使用較多的一種嵌入式數據庫，作為一種輕量級嵌入式數據庫，為許多編程語言提供了API接口，包括c、c++、java、python等，所有數據庫相關操作都由Berkeley DB庫函數負責統一完成。這樣在多進程讀寫并行訪問，或者在同一個進程內多線程競爭訪問，都可以保證數據的一致性、完整性。底層的數據加鎖、事務日志和存儲管理等都在Berkeley DB庫函數中實現，它們對于應用程序而言是完全透明的。

Berkeley DB對于任何存入的value數據都是原樣拷貝到數據文件當中，無論是文本數據還是二進制數據。它提供了四種存儲數據的模式：btree、hash、queue和recno，在打開數據庫的時候，需要指定其中一種存儲模式。雖然有多種存儲模式，但鍵值對是數據庫的基礎數據結構。用API函數訪問數據庫時，只需提供關鍵字就能夠訪問相應的數據。鍵值對結構在Berkeley DB中都是用一個名叫DBT的簡單數據結構來表示的，它的作用主要是保存相應的內存地址和長度。

1.3 數據傳輸轉化過程

數據的讀取過程，就是數據從數據庫傳輸到應用進程，并轉化為運行時數據結構的過程。為了獲得比傳統內存數據庫、嵌入式數據庫更高讀取性能的讀取方法，在此分解研究數據傳輸轉化過程，并依此提出優化目標對象。

進程地址空間分為內核態和用戶態[9]，其中內核態地址空間為所有進程與內核共享，用戶態地址空間為每個進程獨有。不管是跨網絡、跨進程，還是讀取文件的數據傳輸方式，都涉及到內核態數據拷貝至用戶態的過程。具體過程如圖1所示。

圖1 數據庫數據傳輸轉化過程

(1)內存數據庫有獨立運行的數據庫引擎實例，數據依賴網絡傳輸，數據包到來后網卡通過DMA將數據送入內核態地址空間，交由內核協議棧來處理，用戶進程通過系統調用拷貝該數據包至用戶態地址空間。如果內存數據庫與用戶進程部署于同一臺服務器，則通過Linux回環接口(loopback)傳輸，它是一個虛擬網絡接口，不與任何硬件相連，數據包的傳輸不經過網卡直接送入內核態地址空間，之后的協議處理傳輸與網絡過程相同。

(2)嵌入式數據庫把數據存儲于數據文件當中。為了避免頻繁重復的磁盤訪問，Linux操作系統在內核態地址空間內存里維護了一個頁面緩存(page cache)[10]，這樣在從磁盤讀取文件內容前查找這頁面緩存是否已經裝載了，只有沒有命中緩存時才真正的從磁盤讀取數據。頁面緩存的價值有兩個方面：第一，訪問磁盤的速度遠遠低于訪問內存的速度，因此，從內存訪問數據比磁盤訪問更快；第二，數據一旦被訪問，就很可能在短期內再次被訪問到。這種在短期內集中訪問同一片數據的原理被稱作臨時局部原理(temporal locality)。臨時局部原理能保證，如果在第一次訪問數據時緩存它，那就極有可能在短期內再次被高速緩存命中。

數據格式轉化一般由序列化和反序列化[11]過程組成。將程序運行過程中的對象轉化成可以存儲或運輸的形式的過程，就是序列化(serialization)。反之，序列化結果轉化成對象形式的過程，就是反序列化(de-serialization)。在傳統的關系型數據庫中，序列化和反序列化操作都隱含在數據庫讀寫操作當中，對用戶是透明的。內存數據庫和嵌入式數據庫的序列化和反序列化過程一般需要用戶自定義[12]。由于各個系統的軟硬件規格不同，一般需要編程語言無關的格式來序列化數據，常見的有xml/json[13]等可見字符文本，以及效率更高的二進制數據流傳輸方式protocol buffers[14]。當數據量很大，或者獲取頻次很高時，序列化和反序列化會大量消耗系統資源。

2 基于內存映射文件的快速讀取方法

針對上述提出的內核態到用戶態的內存拷貝，以及反序列化等帶來的讀取性能問題，文中針對性地提出改進方法。

2.1 減少內存拷貝

為了盡可能地減少拷貝操作，降低內存消耗，可采用系統調用mmap，即內存映射技術。內存映射技術是Linux的一種內存管理方法，通過這種方法，在不占用額外的內存空間條件下，就能實現目標磁盤文件與進程用戶態虛擬內存空間的對應關系，省去了文件IO等操作。

圖2 內核態與用戶態的內存拷貝與映射

以讀取性能較優的嵌入式數據庫Berkeley DB為例，比較分析mmap的性能優勢。Berkeley DB以文件的形式存儲數據，讀取數據所采用的系統調用是read。read和mmap方式的差異比較如圖2所示。磁盤文件裝載于內核態的頁面緩存區域，進程以read方式訪問文件，在其用戶態地址空間獨立拷貝一份數據，每個read進程獨享一份數據拷貝。也可以在多個read進程間共享一份用戶態數據拷貝，其弊端是為了保證數據一致性需要額外的鎖機制，讀取頻繁時多個進程競爭等待造成讀取效率降低，由于此問題較復雜且與該文相關度不高，不再詳述。相對而言，mmap方式既簡單又高效，不但沒有拷貝操作，內存消耗也很低，整個物理內存只存在一份文件數據(在頁面緩存區域)。應用程序不需要考慮文件映射內的數據是否已經裝載，也不需要考慮如何在多個進程間共享，這些Linux內核都已處理，對用戶透明。如果磁盤文件過大超過了物理內存大小，Linux內核會以LRU(least recent used)算法把冷數據置換出來，從而釋放內存來存儲新數據，最終在頁面緩存中的數據是經常被訪問的熱數據。

2.2 優化數據格式

復雜對象不但數據量大，且數據間關系復雜，體現在數據結構上就是指針引用較多。當把復雜對象序列化于文件時，指針就失效了，必須將相應的指針轉化為指針指向的目標數據塊在文件中的偏移量。如圖3所示的哈希表，哈希桶內的指針指向鍵值對結構，當序列化于文件時，該指針需修改為鍵值對結構在文件中的偏移量。當用戶進程讀取該哈希表時，得到的文件偏移量加上文件映射首地址，即是目標鍵值對結構的內存地址。

圖3 復雜對象的指針轉化

在64位地址空間[15]當中，有大量的空閑空間可供程序使用。因此，經過如下步驟(見圖4)，則可在文件中直接存儲指針，避免文件偏移量的轉化：

(1)序列化進程在指定虛擬內存區域內分配對象內存，直至整個復雜對象存儲于該指定虛擬內存區域。

(2)把該內存區域內的二進制數據dump到內存鏡像文件。

(3)由反序列化進程映射該內存鏡像文件，映射地址為之前指定的虛擬內存區域。

(4)復雜對象不需要任何格式轉化，即可被反序列化進程使用。

圖4 復雜對象共享過程

2.3 復用模板庫和容器

如2.2節所述，優化數據格式的重點在于如何把一個復雜對象序列化于指定虛擬內存區域。假設某個復雜對象為多重key-value結構(value部分又是一個key-value結構)，這就要求開發人員開發一個特定的哈希表數據結構。當復雜對象使用的數據結構更多時，相應的特定數據結構開發工作也更多，開發效率低下。由此，引入了可復用組件C++標準模板庫[16]。

C++標準模板庫STL(standard template library)是一套標準化組件，由六大組件組成：

(1)container:泛型容器，基本數據結構有數組vector，鏈表list，二叉樹map，哈希表unordered_map等。

(2)algorithms:泛型算法，常見的排序sort，搜索search等。

(3)iterator:迭代器，借此container和algorithms解耦，兩者可以各自獨立發展互不關聯。

(4)function object:是一種模板函數對象，常見的有map容器中的比較對象std∷less。

(5)adaptor:適配器，修飾container或function object接口的一種組件。比如棧stack作為容器適配器，可以實現為基礎容器類型(vector，list)的適配。

(6)allocator:內存分配器，STL提供了默認內存分配器。

泛型容器提供了一些常用的數據結構，可以嵌套使用，比如借助unordered_map可實現多重key-value結構。內存分配器負責數據對象的內存分配，默認內存分配器是基于gnu libc的內存分配算法[17]，內存分配分散于進程堆空間之中，無法區分共享數據與私有數據，兩類數據交錯存放。通過自定義內存分配器，使得需要共享的大小不一的各種C++對象從指定的地址空間中分配，其他私有對象仍然從進程堆空間分配。最終，序列化進程把指定內存區域內的連續內存塊數據dump出來保存，即為可共享的數據文件。

3 系統關鍵實現與對比驗證

該方案的實現關鍵點在于如何把對象序列化于數據文件當中。數據的讀取操作相對簡單，把文件映射獲得的內存區域首地址指針強制轉化為C++對象指針類型即可。

3.1 創建空洞文件

初始階段創建空文件用以存放目標復雜對象。由于對象長度大小事先無法確定，因此一般做法是創建一個較小的空文件，隨著復雜對象的擴張而不斷延長文件長度。這個辦法的缺點是實現相對復雜，延長操作過多的話會影響寫入性能。

借助空洞文件，可以解決該問題。在Linux文件操作中，文件位移量是可以大于文件的當前長度的，在這種情況下，對該文件的下一次寫將延長該文件，并在文件中構成一個空洞，即為空洞文件。位于文件中但沒有寫過的字節都被預設為0。空洞是否占用硬盤空間由文件系統決定，在一般文件系統中不占用硬盤空間，意味著不需要大量的寫0操作，創建過程耗時極短。

在寫C++對象數據文件前，先創建一個空洞文件，文件長度為預估數據量的若干倍，比如10倍。無需擔心浪費磁盤空間，因為最終序列化完畢時，可以根據實際數據量縮減文件長度。

3.2 基于內存映射技術的內存分配器

內存分配器是處理應用對于內存的分配和釋放要求的，默認內存分配器所分配內存處于進程堆空間。該方案自定義的基于內存映射技術的內存分配器，可分配內存來至磁盤文件映射出的連續內存空間。其主要接口和成員變量如下：

class MemoryMapAllocator

{

public:

MemoryMapAllocator(const char* filePath, unsigned long maxSize, void* address);

～MemoryMapAllocator();

void* allocate(unsigned long size);

void release(const void* ptr);

private:

void* m_currentPointer;

};

構造函數的作用是根據數據文件目錄位置，以及預估的數據最大大小，創建空洞文件，并映射入指定的用戶態地址空間(函數參數address)，成員變量m_currentPointer初始化為映射空間的首地址。

析構函數的主要功能是以msync系統函數同步數據寫入磁盤，再以munmap系統函數撤銷內存映射，即數據持久化過程。

成員函數allocate是內存分配操作方法，首先m_currentPointer指針自增函數輸入參數size字符數，然后函數返回自增前m_currentPointer的值。一般為了提升內存訪問效率，對輸入參數size做對齊工作，向上取整8的倍數(64位操作系統環境)。

成員函數release是釋放內存操作方法，在方案中并不必要。所有C++對象都分配于映射地址空間，所有數據寫入之后，撤銷文件映射并把內存數據同步于磁盤文件，所有對象內存自然釋放，因此release函數內部實現可以為空操作。一種更復雜的實現是重復利用釋放的內存，借助精細的內存管理機制(如slab算法[18])，記錄所有釋放的內存，內存分配算法優先在其中尋找符合大小要求的閑置空間。實際應用當中，此類釋放內存數量有限，重復利用價值不高，且代碼復雜度高，可維護性差，不建議使用。

3.3 多線程支持

在創建數據文件時，如果數據量很大，可借助多線程并發處理能力來加速處理。為此內存分配器需設計成線程安全。

最簡單的方法是在類MemoryMapAllocator中新增鎖對象，每次調用allocate方法時加鎖，函數返回時釋放鎖，保證只有一個線程在修改m_currentPointer指針，其余試圖申請內存的線程處睡眠等待狀態。當線程爭搶鎖劇烈時，頻繁的線程切換就會成為性能瓶頸。

為了解決鎖帶來的弊端，可采用原子操作[19]。所謂的原子操作是指不會被線程調度機制打斷的操作，一旦操作開始，就一直運行到結束，中間不會被其他線程操作打斷。其實現原理是依靠硬件的支持，在X86平臺上，CPU提供了在指令執行期間對總線加鎖的手段。避免了線程切換，提升處理速度。

GCC編譯器當前已經支持了原子操作，可以對1、2、4、8字節的數值或指針類型進行原子的加、減、與、或、異等操作。對于m_currentPointer的加法操作，可以靠原子操作函數__sync_fetch_and_add(type *ptr, type value)完成，其實現細節是將value加到*ptr，結果更新到*ptr，并返回操作之前*ptr的值。

3.4 讀取效率對比

為了對改進復雜對象讀取性能做進一步的分析，對傳統內存數據庫redis、嵌入式數據庫berkeley DB和基于內存映射文件的復雜對象讀取方法進行了性能對比測試。測試目的是在讀取相同數據量的前提下，比較各個方案的響應時間值。軟件配置為Linux內核2.6.32，redis libhiredis 0.13，berkeley DB libdb_cxx 4.7；硬件配置CPU頻率2.60 GHz，內存256 G。

在以上測試環境中，創建一個進程順序進行三次不同方案的數據讀取操作，保證了軟硬件資源一致。其中內存數據庫redis服務端與客戶端部署于同一臺服務器，避免網絡延時帶來的誤差。內存映射文件數據庫采用了C++標準模板庫容器unordered_map。

三個數據庫存儲相同key-value鍵值對1 024個，每個key平均2.9 Bytes，每個value平均2 986 Bytes，讀取程序設計為遍歷讀取這1 024個key共600遍，即614 400次查詢操作，實驗結果見表1。

表1 三種數據庫方案讀取性能測試結果

從結果上看，文中提出方法的讀取性能相對于傳統方案有非常顯著的提升，與性能較優的嵌入式數據庫相比其讀取響應時間提升10倍以上。而且如前所述，內存數據庫與嵌入式數據庫的內存消耗量與讀取進程個數成線性增長，因為每個進程都要拷貝存儲數據，而內存映射文件數據庫不需要拷貝，其內存消耗量與讀取進程個數基本不相關。

該方案的另一個優點在于支持各種復雜對象，而不單限于key-value結構。由于內存數據庫、嵌入式數據庫支持的結構類型有限，故只比對了key-value結構。如果把一個復雜對象分拆成多個key-value鍵值對存儲于普通數據庫中，其性能更無法與面向對象的內存映射文件數據庫相提并論。原因是前者需要多次索引搜索才能組裝成完整的復雜對象，而后者沒有這個過程，所有的對象內數據關系都已經通過指針關聯。

4 結束語

傳統數據庫在高并發應用場景中，數據拷貝操作頻繁，數據量較大時容易成為性能瓶頸。當數據對象結構復雜時，不但數據庫表結構、索引設計復雜，而且序列化與反序列化過程耗時嚴重。該方案通過內存映射文件、自定義內存分配器、標準模板庫容器等技術，有效解決了復雜對象讀取性能問題。讀取過程沒有進程間通信，不需要數據拷貝，不需要反序列化過程即可直接引用對象，與傳統數據庫讀取效率對比的實驗表明性能可提升10倍以上。同時，還具有底層技術成熟穩定、開發代碼量少、易于維護等優點。內存映射文件技術得到了廣泛的支持，Linux等類Unix操作系統中都提供了相關系統調用。標準模板庫提供了諸多常用數據結構，大大降低了復雜對象結構設計與開發成本。借由此類成熟技術，開發過程周期短，易于實現，后期維護更新成本低，在實際應用中運行穩定。在數據庫災備設計方面，由于數據存儲于文件，易于傳輸，如果數據丟失，可以很快從災備數據文件中恢復。因此，該方案實用性高，適用于數據訪問方式寫少讀多的高并發高性能搜索、計算等后臺服務系統，在工程實踐中有重要的典型意義。