內存數據管理技術在族譜資訊系統中的應用論文

設計並實現了具有數據錄入、數據服務、數據輸出功能的族譜資訊系統。 族譜資訊系統採用了分佈式結構，在每個分佈數據節點引入內存資訊管理技術，採用列存儲模型，自動初始化熱點數據，並根據用戶請求組織數據建立索引，同時利用事務日誌對每個分佈數據節點的內外存進行數據同步，對中心數據節點和分佈數據節點進行數據同步。

0引言

族譜又稱爲家譜、宗譜，是一種記錄家族世代繁衍和重要人物事蹟的圖文體裁。 族譜文獻對於我們瞭解人文歷史有很大的幫助，並且在政治經濟學、地理學、羣體遺傳學等方面都有着潛在的研究價值[1]。 傳統的中國式族譜通常以紙質、布質等形式的譜書爲承載形式，各族、各家擁有自己獨立的譜書。 這些譜書在存在形式上相互獨立，但是在內容上卻有很強的相關性。 傳統的譜書式族譜在資訊交互和共享方面存在着先天不足，且實體的譜書不便於後續的修改（續修）以及儲存。 因此，近年來族譜數字化受到了社會的廣泛關注。

數字化族譜系統除了能提供給用戶錄入族譜資訊、利用族譜資訊的功能之外，還需要兼顧中國式族譜的特殊需求——譜書。 家族在編修族譜時，通常都需要以採集好的族譜數據爲基礎，透過編輯、排版形成內容豐富、圖文並茂、樣式美觀的譜書，然後將其印刷成冊並分發給族人。 目前，國內外在數字化族譜系統方面已有一些研究和開發工作。 著名的族譜網站FamilySearch[2]中，用戶可以方便地創建和管理個性化族譜空間，但沒有提供族譜數據紙質化輸出功能。 文獻[34]都實現了基於單機形式的族譜錄入軟件：將族譜的製作工作分割成多個任務，由多位製作人員分別完成這些任務並以檔案存儲任務中的族譜數據，最後將多個數據檔案合併，編輯形成最終的族譜。 但是這種數據管理方式不利於資訊的共享，而且多個數據檔案之前存在較多的冗餘以及衝突，無法自動完成數據檔案合併。 爲了加快族譜數字化進程，結合實際的應用需求，本文設計並實現了一個基於B/S架構的族譜資訊系統，該系統提供了族譜數據的錄入、查詢服務、紙質化輸出等功能。 結合族譜資訊系統中的實際需求，本系統的數據存儲採用了分佈式結構和內存數據管理技術，大大加快了族譜資訊錄入和檢索的速度。

本文內容組織如下：第1節介紹族譜資訊數據的特點；第2節介紹系統功能，並分析引入內存數據管理技術的必要性；第3節將簡單介紹本系統中所涉及的相關內存數據管理技術；第4節介紹內存數據管理技術在族譜資訊系統中的具體應用；第5節對本文工作進行總結並對未來工作進行展望。

第5期張文傑，等：內存數據管理技術在族譜資訊系統中的應用華東師範大學學報（自然科學版）2014年1族譜數據簡介

族譜數據通常由三部分構成：世系數據、文檔數據以及多媒體數據。

（1） 世系數據包括人物數據和人物之間的親緣關係數據。 其中親緣關係主要分爲父子（父女）、母子（母女）、配偶、過繼（從親屬中收養子女）、兼祧（一位男子同時繼承多家）。 世系數據是族譜數據中最重要的部分。 （2） 文檔數據包括在族譜中家族大事件的文字記錄和重要的人物傳記，族譜中的文檔數據除文字之外還包含圖表等，呈現一種圖文並茂的形式。

（3） 多媒體數據包括族譜中記錄人物或者家族大事件的圖像、音頻、視頻，這裏的多媒體數據並不包括文檔數據中含有的圖表。

族譜數據中的文檔數據、多媒體數據和一般的文檔數據、多媒體數據在組織和存儲形式上並無明顯區別，而世系數據作爲族譜數據中的核心數據，其特點鮮明。

如果把世系數據中每個人物作爲節點，人物之間的關係作爲邊，則世系數據就構成了一種類似樹的結構，下文中也把這種結構稱爲世系樹，如圖1所示。

如果考慮更廣泛的親緣關係（如聯姻），很多世系數據就會聯繫在一起構成類似森林的結構，這和社會網絡[5]數據非常相似。 但是世系數據比社會網絡數據所表達的人物羣體更加特定，人物之間的關係更加明確。

總結起來，世系數據具有以下特點：

（1） 表達對象是特定的人物“羣體”——家族（或者支系），人物關係是親緣關係，相比其他人際關係要更加緊密和牢固。

（2） 如果把人物視作節點，把人物之間的關係視作邊，世系數據構成了一種特殊的層次結構—世系樹。

（3） 如果把多個世系樹用聯姻關係聯繫在一起，會構成一種特殊的圖結構，類似於森林和社會化網絡數據。

圖1世系樹示例圖

Fig。1The tree structure of genealogy data

2族譜資訊系統

傳統族譜資訊系統採用的是單機管理不易於擴展功能，數據分散且有大量冗餘，無法利用這些族譜數據向公衆用戶提供服務。 爲了更好地收集和利用族譜數據，我們設計並開發了一款基於B/S架構的`族譜資訊系統。 該系統支援多用戶並行錄入同一族譜中的數據，並統一對族譜數據進行管理，同時透過本系統還可向公衆用戶提供對已錄入族譜數據的檢索。

族譜資訊系統的主要功能包括數據錄入、數據服務和數據輸出。

2。1數據錄入

數據錄入功能主要包括三部分：世系數據錄入、文檔數據錄入、多媒體數據錄入。 其中世系數據錄入是指錄入人物的基本數據以及錄入人物之間的聯繫數據。

2。2數據服務

數據服務功能主要包括數據展示、統計檢索、一鍵尋祖和一鍵尋親。

（1） 數據展示

數據展示功能包括族譜展示和對照預覽。 族譜展示功能主要顯示一個族譜的基本資訊。 對照預覽則用於在正式輸出紙質化族譜之前以各種不同的樣式來預覽輸出的效果。

（2） 統計檢索

統計檢索提供了對系統中的族譜數據進行統計和檢索的功能。 族譜統計是顯示整個族譜的統計資訊，如總人數、男女比例、生死狀況等。 簡單檢索和組合檢索是在某些族譜屬性或者人物屬性上進行檢索的功能。

（3） 一鍵尋祖和一鍵尋親

一鍵尋祖可以從族譜中根據人物之間的親緣關係得到指定人物在指定範圍內（比如限定世代數）的祖先。 一鍵尋親則是指在族譜數據中找到兩個指定人物之間的親緣關係鏈（即兩人是透過哪些人關聯在一起）。

2。3數據輸出

爲了滿足用戶傳統紙質譜書的需求，族譜資訊系統中提供了數據輸出功能，主要包括族譜編排、族譜生成。

（1）族譜編排

譜志編排功能是透過用戶的個性化需求對譜書的樣式、數據出現的順序、名詞的表達方式等進行設定。

（2） 族譜生成

族譜生成功能主要是在族譜編排過後，按照用戶的個性化需求從原始族譜數據中轉換生成電子版的譜書以供印刷。

2。4應用內存數據管理技術的必要性

透過對族譜資訊系統的功能分析，族譜資訊系統具有以下特點。

（1）數據源單一。 在數據錄入過程中，對每個錄入用戶來說，只能操作自己參與錄入的族譜數據。 同時，數據輸出過程中，只需要去訪問要生成電子族譜的特定族譜的數據。

（2）數據量較大。 每個族譜都存有數量和容量龐大的世系數據、文檔數據、多媒體數據。

（3）實時性要求高。 由於本系統基於B/S模式設計，無論是數據錄入、數據服務還是數據輸出功能，系統響應時間都應該很短。

族譜資訊系統的大數據量和高實時性的特點對系統實現提出了挑戰。 而隨着主存的成本顯著降低，許多成熟的內存數據管理技術爲族譜資訊系統的實現提供瞭解決方案[6]。

3內存數據管理技術

內存數據管理[7]的關鍵技術包括存儲結構[8]、索引結構[9]、併發控制[10]、同步策略[11]、故障恢復[12]等。 本節將重點介紹系統中用到的索引結構和同步策略。

3。1索引結構

內存數據庫由於其工作的主版本儲存在內存中，所以內存數據庫的索引選擇應結合存儲介質的特點，從而透過索引的建立來保證內存數據庫查詢操作的高效性。 目前在內存數據庫中經常選用的索引結構有hash索引和T樹索引。

（1） hash索引[13]定義了一個hash函數，透過將關係表的索引項傳入到hash函數可以計算出相應的hash值，從而在索引項和hash值之間建立起對應關係，透過hash索引查找數據只需常數時間的複雜度。

（2） 在內存數據庫中目前較廣泛使用的一種樹是結合B樹[14]和AVL樹進化而來的T樹[14]。 T樹的單個節點有多個數據，因此擁有良好的修改和存儲特性。 由於T樹屬於AVL樹的一種演進，具有AVL樹的平衡特性，從而進一步提升了樹的搜尋性能。 因此T樹在時間和空間兩者間具備較好的平衡性。

hash索引在進行定值的查找時效率很高，而T樹索引一方面具有樹的二叉性而且其設計符合內存數據庫存儲介質的特性，所以當前主流的內存數據庫都至少提供了這兩種索引結構。3。2同步策略

內存數據管理的數據同步更新技術大致可以分爲表複製技術、事務複製技術、觸發器技術和影子表技術。 這裏主要介紹表複製技術和事務複製技術[15]。

（1） 表複製技術：採用把某一時刻源數據表的內容透過網絡發送到複製的副本，因爲複製的內容是表的某一時刻的狀態，所以又被形象地稱爲錶快照。 錶快照的複製不是以事務爲基礎，所以副本缺乏基本的關係完整性。 基於表複製技術不需依賴特別的機制，不佔用額外的系統資源，管理和操作也非常容易，而且在同步初始化和崩潰恢復時是必須的。 但是全表更新效率很低。

（2） 事務複製技術：事務複製技術是把修改源數據的事務透過網絡發送到複製的副本，複製可以是修改的表項事務或事務日誌。 複製的時間可根據應用需求而確定。 副本接收到複製內容後，要重複一遍接收到的事務操作來實現與數據源的一致。 一般是基於數據庫日誌透過分析日誌的資訊來獲得數據的差異，最後達到數據同步。

4內存數據管理技術在系統中的應用

在族譜資訊系統中需要大量的遞歸查詢操作，而且系統對數據存取的實時性要求比較高，只依靠基於磁盤的傳統數據庫系統無法滿足族譜資訊系統的要求。 爲了保證數據處理的實時性和可靠性，族譜資訊系統中採用內存和外部存儲設備（如磁盤）共同作爲數據的存儲介質。 族譜資訊系統將實時或關鍵性數據的操作放在內存數據庫中進行，由於內存的數據存取速度比磁盤快，引入內存數據管理技術會使族譜資訊系統更高效，更迅捷。

4。1族譜資訊系統結構

在族譜資訊系統的業務邏輯中，系統的運營商負責分配錄入任務給各個代理商，各代理商再將任務分割爲多個子任務，並組織多位錄入人員進行錄入。 爲了增加子系統的可靠性和靈活性，族譜資訊系統採用分佈式結構[16]（如圖2所示）。 系統中包括了一箇中心數據節點和多個分佈數據節點。 中心數據節點儲存了所有的族譜數據；而每個代理商擁有一個分佈數據節點，存儲了本代理商代理錄入完成的族譜數據。

每個分佈數據節點都是由一個磁盤數據庫和一個內存管理單元組成。 其中內存管理單元包括內存數據庫、用戶請求處理模組、接收隊列、發送隊列、節點狀態管理模組、資源管理模組和數據同步模組，內存數據庫採用列存儲模型來實現存儲。 用戶請求處理模組主要是接收用戶請求，並根據用戶請求進入不同的處理分支。 接收隊列用於接收用戶提交的新增的數據或者是修改的數據。 發送隊列用於發送給用戶所要求的查詢結果數據。 數據同步模組用來維持分佈數據節點和中心數據節點的數據同步。 資源管理模組主要是對內存資源進行分配和回收。

4。2數據錄入功能的內存管理策略

在數據錄入功能中，每個錄入用戶登入之後首先會選擇自己要錄入的族譜，系統自動連接該族譜隸屬的代理商的分佈數據節點。

分佈數據節點中的用戶請求處理模組會識別用戶數據錄入請求，把用戶選擇的族譜數據作爲熱點數據存入到內存數據庫當中。 由於數據錄入功能的主要操作是插入新元組，所以元組集合在內存數據庫中採用堆組織以便高效地插入新元組；同時按照鍵值建立哈希索引，其中重名的會依次放在指針數組中。 圖2族譜資訊系統架構

Fig。2The structure of the genealogy information system

當用戶插入新元組時，新元組會加入到系統的接收隊列，分佈數據節點會把新增元組加入到內存中存儲； 當用戶需要請求檢索數據時，對應分佈數據節點會根據索引快速定位數據位置並返回給用戶；當用戶修改數據時會把修改後的數據加入到系統的接收隊列，分佈數據節點會把接收隊列中的數據依次更新；當用戶刪除數據的時候，分佈數據節點會透過索引定位到該數據並執行刪除，同時內存資源管理模組進行內存資源回收。

4。3數據服務功能的內存管理策略

由於在數據服務功能中主要是對世系數據的大量結構化查詢，分佈數據節點採用T樹索引結構來存儲元組資訊。 其中每個節點的數據中都含有人物對象的詳細資訊和分別指向父親、母親、過繼或兼祧父親、過繼或兼祧母親的四個指針。 同時建立哈希索引（同第4。2節）。

當數據錄入導致本族譜世系數據發生改變的時候，會對內存T樹索引和哈希索引進行更新，分爲以下幾種情況。

（1） 如果需要增加新的元組，系統會對T樹索引做插入操作並更新哈希索引；

（2） 如果需要更新某個元組，系統會透過T樹索引找到舊元組直接進行更新如需要則同時更新哈希索引；

（3） 如果需要刪除某個元組，系統會先透過T樹索引找到該元組然後刪除該元組，更新T樹索引和哈希索引，同時資源管理模組進行內存資源回收。

在數據服務功能中，當用戶請求一鍵尋祖的時候輸入要尋祖的人物譜名和祖先的世代數（可以不輸入，默認爲族譜中最小的世代數），分佈數據節點會首先透過哈希索引找到T樹索引中對應的人物對象元組節點。 如果存在多個重名的人物對象則會返回幾個人物對象的具體資訊供用戶選擇；如果該譜名只對應一個人物對象或者用戶從重名人物中選擇了一個人物對象，則分佈數據節點會從世系樹中該人物對象節點開始循環地透過父親或兼祧父親指針尋找祖先節點；當該祖先的世代數等於用戶輸入的值，則停止循環並返回該祖先節點元組給用戶。

4。4數據輸出功能的內存管理策略

在數據輸出功能中，每個用戶需要首先選擇族譜，分佈數據節點把對應的族譜數據作爲熱點數據載入到內存數據庫中，在後續的族譜編排和族譜生成中可以直接訪問分佈數據節點的內存，並建立T樹索引（同第4。2節）。

當用戶對世系數據進行分組（可以按照個人或者是世代分組）時，分佈數據節點會透過T樹索引檢索對應人物更新其分組號；當用戶按照需求對世系和文檔進行分卷時，會對世系分組和文檔數據進行排序用於生成對應的電子族譜，同時分佈數據節點會按照用戶的編排順序對內存中的數據進行排序；當用戶選擇相應的模板請求族譜生成的時候，分佈數據節點會根據模板的格式生成族譜並返回給用戶。

4。5數據同步策略

在族譜資訊系統中，每個分佈數據節點的內存數據庫儲存着實時數據，但是內存屬易失性存儲，爲了提高數據的可靠性，必須和外存數據庫進行數據同步。 同時中心數據節點作爲所有分佈數據節點族譜數據的副本也需要和分佈數據節點進行數據同步。

4。5。1分佈數據節點內外存數據同步

分佈數據節點內外存數據同步屬於單向同步，除了內存數據初始化外，數據都是從內存數據庫傳輸到外存數據庫當中。

在族譜資訊系統中，分佈數據節點的內外存數據同步是由常駐後臺進程MMSyn來實現的。 分佈數據節點啓動後，MMSyn進程就會自動啓動。 MMSyn進程啓動時需要初始化系統設定的同步週期時間和進程數閥值。 MMSyn進程在上次同步操作完成和下次同步操作開始之間會休眠一個同步週期。 每次MMSyn進程被喚醒之後，會透過事務日誌來檢測是否存在數據更新，如果有而且當前的進程數低於閥值就進行數據更新，否則MMSyn進程繼續休眠。 MMSyn進程在數據更新過程前會讀取存儲的上次完成同步的事務日誌序列號，從下一事務日誌開始在外存裏重做事務操作從而完成同步。

4。5。2分佈數據節點與中心數據節點的數據同步

分佈數據節點分散存儲着各個代理商代理錄入的族譜資訊，而中心數據節點作爲穩定的中心數據備份必須和分佈數據節點進行數據同步。 分佈數據節點與中心數據節點的數據同步屬於單向同步，除了分佈數據節點崩潰從中心數據節點恢復以外，數據都是從分佈數據節點傳輸到中心數據節點當中。

在族譜資訊系統中，分佈數據節點與中心數據節點的數據同步是由分佈數據節點常駐後臺進程DSyn和中心數據節點常駐後臺進程CSyn來實現的。 在族譜資訊系統啓動後，CSyn和DSyn進程會自動啓動。

和MMsyn進程相似，DSyn進程在啓動時需要初始化系統設定的同步週期時間和進程數閥值。 每次DSyn進程被喚醒之後，會讀取存儲的上次完成同步的事務日誌序列號n，如果當前最大的日誌序列號m>n（日誌序列號是遞增的），則將n<日誌序列號>m的日誌發送給中心數據節點。

中心數據節點一旦啓動，就會開啓CSyn進程。 當分佈數據節點發送過來日誌序列時，CSyn重做事務操作從而完成同步。

5結論

本文設計並實現的族譜資訊系統採用了B/S架構，能更好地支援族譜數據的分散錄入以及集中共享的現實需求。 在族譜數據管理方面採用了分佈式結構，其中包括中心數據節點和分佈數據節點。 中心數據節點存儲全部族譜的數據，分佈數據節點存儲對應代理商錄入的族譜數據，透過同步策略實現中心數據節點和各個分佈數據節點的數據同步，大大加強了系統的可靠性和靈活性。

分佈數據節點引入了內存數據管理技術，採用列存儲模型存儲結構，並根據用戶具體的請求初始化熱點數據，建立索引。 用戶的操作在分佈數據節點內存中進行，加快了系統的響應速度。 同時，系統利用事務日誌進行分佈數據節點的內外存同步和內存數據庫恢復，增強了系統的可靠性。

未來的工作還需要考慮熱點數據的優化選擇、分佈數據節點負載均衡等問題。