記憶體資料管理技術在族譜資訊系統中的應用論文
記憶體資料管理技術在族譜資訊系統中的應用論文
設計並實現了具有資料錄入、資料服務、資料輸出功能的族譜資訊系統。 族譜資訊系統採用了分散式結構，在每個分佈資料節點引入記憶體資訊管理技術，採用列儲存模型，自動初始化熱點資料，並根據使用者請求組織資料建立索引，同時利用事務日誌對每個分佈資料節點的內外存進行資料同步，對中心資料節點和分佈資料節點進行資料同步。
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架構，能更好地支援族譜資料的分散錄入以及集中共享的現實需求。 在族譜資料管理方面採用了分散式結構，其中包括中心資料節點和分佈資料節點。 中心資料節點儲存全部族譜的資料，分佈資料節點儲存對應代理商錄入的族譜資料，透過同步策略實現中心資料節點和各個分佈資料節點的資料同步，大大加強了系統的可靠性和靈活性。
分佈資料節點引入了記憶體資料管理技術，採用列儲存模型儲存結構，並根據使用者具體的請求初始化熱點資料，建立索引。 使用者的操作在分佈資料節點記憶體中進行，加快了系統的響應速度。 同時，系統利用事務日誌進行分佈資料節點的內外存同步和記憶體資料庫恢復，增強了系統的可靠性。
未來的工作還需要考慮熱點資料的最佳化選擇、分佈資料節點負載均衡等問題。