基于內存映射文件的進化算法數據存儲引擎

2015-04-14 12:28:14姜三義代真真周愛民

計算機工程與應用 2015年1期

姜三義，代真真，李陽，周愛民

華東師范大學計算機科學技術系，上海 200241

1 引言

基于統計和機器學習的進化算法目前日益引起人們的重視。進化算法[1]是一種通過多次迭代搜索來獲取全局最優解的隨機優化算法[2]。作為一類啟發式搜索算法，是否具備良好的搜索記憶功能，即通過一定方式存儲并利用已搜索的解空間，是評價算法好壞的關鍵之一。從本質上來說，進化算法維護的種群和其他信息實際上可以看作是一個動態變化的數據集（數據庫）。當前及歷史數據集隱含了進化算法搜索的規律，因此可以通過模式識別和機器學習的方法來挖掘隱含在這些數據集中的規律并指導進化算法的搜索。有效存儲和組織當前和歷史群體信息，是實現這類算法的前提。

由于進化算法的搜索空間往往比較大，存儲記憶時需要平衡算法效率和磁盤空間[3]。隨著計算機磁盤容量的迅速增長和單位容量成本的降低，可以將更多的算法數據存儲到磁盤中。但是在性能上，現有的通用數據庫技術或傳統文件存儲方式并不能很好地滿足這種需求。使用通用數據庫時，需要額外搭建專有的數據服務系統，進行數據庫維護，并且由于數據庫索引等機制的存在，數據庫對于大量實時算法數據的存儲效率并不理想。算法設計人員因而往往將數據以文件的形式直接存儲到磁盤上。由于磁盤I/O的效率問題，采用傳統文件方式保存數據會大量增加算法的執行時間。現代操作系統支持基于虛擬內存技術的內存映射文件機制。通過使用內存映射文件，存儲速度相比于傳統文件I/O方式可以得到極大提升[4]。

內存映射是將磁盤上的文件或部分文件內容映射到進程地址空間內部區域的一種機制。通過創建內存映射文件，應用程序可以直接讀寫內存來訪問磁盤文件數據，相比于使用文件的讀寫函數具有更快的I/O速度。在Windows和Linux操作系統中都支持內存映射文件機制，通過使用系統提供的編程接口，應用程序可以利用內存映射機制提高I/O效率。

內存映射文件可以被直接應用于程序中，對于一些簡單的程序是完全可行的。但是在進行復雜數據結構的存儲組織，并且需要確保大量數據和文件的可靠和安全時，需要進行復雜的代碼設計和編碼調試工作，以解決合理分配和動態擴展數據文件，存儲不同數據結構等問題，這對程序編碼人員提出了很高的要求，在很大程度上限制了內存映射文件技術被廣泛利用。

本文介紹了使用C++編程語言實現的嵌入式數據存儲引擎（EADB），EADB利用內存映射文件實現了數據存儲，支持Linux和Windows這兩個不同平臺，提供統一的讀寫接口，支持復雜數據結構的存儲組織。通過使用EADB，應用程序在獲得I/O性能提升的同時，可以減少編碼工作量。通過在進化算法中使用EADB，提高了進化算法執行過程中的數據存儲效率。

2 算法記錄

本文稱進化算法迭代過程中產生的解為“算法記錄”。不同進化算法的執行框架基本相同，首先進行種群隨機初始化和個體適應度計算，然后進行有限次數的迭代使得群體在搜索空間中不斷進化。每一次迭代包含的步驟包括：重組、變異、適應值評估和選擇等。每一次迭代產生的解包含染色體、適應值或其他信息[5]。

進化算法的種群個體（即染色體）可以表示為確定長度的二進制位串或格雷碼，也可以使用符號集、實數或實數數組來表示。進化算法作為一類啟發式搜索算法，也被成功應用于多目標優化領域[6-7]。每個種群個體的適應值，在單目標優化和多目標優化問題中的表示方式是不一樣的。在單目標優化問題中，適應值是一維的變量；而在多目標優化問題中，適應值則一般是多維的向量。由此分析，算法記錄中的內容在形式上包括一維變量和多維向量，所以可以使用數組來統一存儲記錄內容[8-9]。

同一個進化算法在每一次迭代中需要保存的數據記錄的數量有可能不同，例如在基于分解技術的多目標進化算法（Decomposition based Multi-Objective Evolutionary Algorithm，MOEA/D）求解背包問題的算法中，每一代最優群體的個體數量可能是不同的[10]。但是，在同一個進化算法的一次執行過程中，算法記錄的內容在結構上是一致的。

3 內存映射文件

內存映射文件的實現借助于操作系統底層的虛擬內存機制[11]。使用虛擬內存的目的是為了彌補物理內存的容量不足問題。在虛擬內存系統中，每個進程擁有獨立的連續完整的地址空間。基于程序的局部性原理，操作系統僅將運行進程所必需的一部分指令裝入內存，在進程執行時通過請求調入和置換功能進行內外存數據交換，使進程能夠持續運行。

虛擬內存技術不僅僅解決了物理內存容量不足的問題，它的出現使得操作系統發生了巨大的變化。當今大部分操作系統（包括Windows和Linux）在I/O系統中均采用了文件緩存機制（在Windows中稱為系統緩存，在Linux中稱為頁面緩存），在內核虛擬地址空間中分配一個分段用于文件數據緩存。操作系統進一步將該分段劃分為塊，每一塊包含若干分頁（在32位Windows系統中，頁面大小是4 KB，分塊大小是256 KB；在32位Linux系統中，頁面大小是4 KB，分塊大小也是4 KB）。在訪問文件時，操作系統始終按塊為單位（即使只訪問一個字節數據）將文件數據拷貝到文件緩存中。當文件緩存中的頁面被調度到物理內存中后，內存與磁盤文件之間建立了字節上一對一的關系，在頁內的數據訪問都是在物理內存中完成的，避免了頻繁的文件I/O，極大提高了讀寫能力。同時，由于虛擬內存的“按需調度”原則，只將一部分數據而非整個文件調入內存，因而可以節約大量物理內存[12-13]。

內存映射文件在此基礎上進一步加快了文件訪問速度。使用傳統文件I/O方式時，仍然需要通過系統調用（即文件讀寫函數）從內核空間將數據復制到用戶空間，即讀操作使用的內存緩沖區。而建立內存映射文件后，操作系統將進程的虛擬頁面直接映射到系統文件緩存上，使得進程可以直接訪問這一部分內存。通過建立內存映射文件，一方面避免了使用系統調用，訪問速度得到數量級的提升；另一方面，在用戶空間中無需對文件內容進行緩沖，不僅減少了物理內存復制工作，還節省了一半的物理內存空間[14]。

內存映射文件帶來的另一個優點是在編寫數據存儲程序的時候，在內存及外存中只需要定義一套數據結構，可以直接將內存映射區域中的數據看作程序中定義的數據結構類型對應的對象[15]。

內存映射文件允許將文件的一部分映射到內存中，從而可以處理非常大的文件。Windows支持的文件大小最大達到16 EB。Linux支持的最大文件大小在不同的文件系統上略有差別，大部分系統都實現了LFS（大文件系統）技術，文件大小可以達到或超過2 TB。

4 存儲引擎的實現與使用

4.1 存儲引擎的數據表示方法

本研究定義了一種數據描述方法：ASON（Algorithm Structured Object Notation），即算法結構化對象表示法，來描述算法記錄，可以滿足進化算法記錄的數據存儲要求。每一個ASON所描述的算法記錄可以包含若干個數據字段，每一個數據字段都是一個鍵值對（key-value pair），每個鍵名是一串字符串，鍵值是一個數值數組。例如，ASON可以表示如下使用鍵值對描述的算法記錄：

記錄中的“popsiz”、“gen”、“fitness”、“chromo”分別表示種群大小、當前迭代值、個體適應度和染色體。使用ASON可以實現對象內數據字段的靈活組合，不僅可以包含進化算法的適應度及染色體，還可以包含其他的數據字段。本文為簡單起見，只考慮染色體和適應度值信息。

使用C++宏“ASON”在程序中按照C++數據流的序列化方式構建算法記錄，采用STL的std：：vector容器作為數組類型。宏ASON的使用方法參見如下代碼：

宏“ASON”返回的是抽象數據結構類型ASONObj的對象實例。在內存中，一個ASONObj對象表示為二進制字節序列。首先是4個字節表示對象長度，緊接著是若干個數據字段，最后是結束標志符。每個數據字段的第一個1個字節表示字段值類型；然后是一條字符串，表示字段名稱，由字符’