張文杰， 彭智勇， 彭煜瑋

（武漢大學(xué) 計(jì)算機(jī)學(xué)院，武漢 430072）

0 引 言

族譜又稱為家譜、宗譜，是一種記錄家族世代繁衍和重要人物事跡的圖文體裁.族譜文獻(xiàn)對(duì)于我們了解人文歷史有很大的幫助，并且在政治經(jīng)濟(jì)學(xué)、地理學(xué)、群體遺傳學(xué)等方面都有著潛在的研究價(jià)值［1］.傳統(tǒng)的中國式族譜通常以紙質(zhì)、布質(zhì)等形式的譜書為承載形式，各族、各家擁有自己獨(dú)立的譜書.這些譜書在存在形式上相互獨(dú)立，但是在內(nèi)容上卻有很強(qiáng)的相關(guān)性.傳統(tǒng)的譜書式族譜在信息交互和共享方面存在著先天不足，且實(shí)體的譜書不便于后續(xù)的修改（續(xù)修）以及保存.因此，近年來族譜數(shù)字化受到了社會(huì)的廣泛關(guān)注.

數(shù)字化族譜系統(tǒng)除了能提供給用戶錄入族譜信息、利用族譜信息的功能之外，還需要兼顧中國式族譜的特殊需求——譜書.家族在編修族譜時(shí)，通常都需要以采集好的族譜數(shù)據(jù)為基礎(chǔ)，通過編輯、排版形成內(nèi)容豐富、圖文并茂、樣式美觀的譜書，然后將其印刷成冊(cè)并分發(fā)給族人.目前，國內(nèi)外在數(shù)字化族譜系統(tǒng)方面已有一些研究和開發(fā)工作.著名的族譜網(wǎng)站FamilySearch［2］中，用戶可以方便地創(chuàng)建和管理個(gè)性化族譜空間，但沒有提供族譜數(shù)據(jù)紙質(zhì)化輸出功能.文獻(xiàn)［3－4］都實(shí)現(xiàn)了基于單機(jī)形式的族譜錄入軟件：將族譜的制作工作分割成多個(gè)任務(wù)，由多位制作人員分別完成這些任務(wù)并以文件存儲(chǔ)任務(wù)中的族譜數(shù)據(jù)，最后將多個(gè)數(shù)據(jù)文件合并，編輯形成最終的族譜.但是這種數(shù)據(jù)管理方式不利于信息的共享，而且多個(gè)數(shù)據(jù)文件之前存在較多的冗余以及沖突，無法自動(dòng)完成數(shù)據(jù)文件合并.為了加快族譜數(shù)字化進(jìn)程，結(jié)合實(shí)際的應(yīng)用需求，本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于B／S架構(gòu)的族譜信息系統(tǒng)，該系統(tǒng)提供了族譜數(shù)據(jù)的錄入、查詢服務(wù)、紙質(zhì)化輸出等功能.結(jié)合族譜信息系統(tǒng)中的實(shí)際需求，本系統(tǒng)的數(shù)據(jù)存儲(chǔ)采用了分布式結(jié)構(gòu)和內(nèi)存數(shù)據(jù)管理技術(shù)，大大加快了族譜信息錄入和檢索的速度.

本文內(nèi)容組織如下：第1節(jié)介紹族譜信息數(shù)據(jù)的特點(diǎn)；第2節(jié)介紹系統(tǒng)功能，并分析引入內(nèi)存數(shù)據(jù)管理技術(shù)的必要性；第3節(jié)將簡單介紹本系統(tǒng)中所涉及的相關(guān)內(nèi)存數(shù)據(jù)管理技術(shù)；第4節(jié)介紹內(nèi)存數(shù)據(jù)管理技術(shù)在族譜信息系統(tǒng)中的具體應(yīng)用；第5節(jié)對(duì)本文工作進(jìn)行總結(jié)并對(duì)未來工作進(jìn)行展望.

1 族譜數(shù)據(jù)簡介

族譜數(shù)據(jù)通常由三部分構(gòu)成：世系數(shù)據(jù)、文檔數(shù)據(jù)以及多媒體數(shù)據(jù).

（1）世系數(shù)據(jù)包括人物數(shù)據(jù)和人物之間的親緣關(guān)系數(shù)據(jù).其中親緣關(guān)系主要分為父子（父女）、母子（母女）、配偶、過繼（從親屬中收養(yǎng)子女）、兼祧（一位男子同時(shí)繼承多家）.世系數(shù)據(jù)是族譜數(shù)據(jù)中最重要的部分.

（2）文檔數(shù)據(jù)包括在族譜中家族大事件的文字記錄和重要的人物傳記，族譜中的文檔數(shù)據(jù)除文本之外還包含圖表等，呈現(xiàn)一種圖文并茂的形式.

（3）多媒體數(shù)據(jù)包括族譜中記錄人物或者家族大事件的圖像、音頻、視頻，這里的多媒體數(shù)據(jù)并不包括文檔數(shù)據(jù)中含有的圖表.

族譜數(shù)據(jù)中的文檔數(shù)據(jù)、多媒體數(shù)據(jù)和一般的文檔數(shù)據(jù)、多媒體數(shù)據(jù)在組織和存儲(chǔ)形式上并無明顯區(qū)別，而世系數(shù)據(jù)作為族譜數(shù)據(jù)中的核心數(shù)據(jù)，其特點(diǎn)鮮明.

如果把世系數(shù)據(jù)中每個(gè)人物作為節(jié)點(diǎn)，人物之間的關(guān)系作為邊，則世系數(shù)據(jù)就構(gòu)成了一種類似樹的結(jié)構(gòu)，下文中也把這種結(jié)構(gòu)稱為世系樹，如圖1所示.

如果考慮更廣泛的親緣關(guān)系（如聯(lián)姻），很多世系數(shù)據(jù)就會(huì)聯(lián)系在一起構(gòu)成類似森林的結(jié)構(gòu)，這和社會(huì)網(wǎng)絡(luò)［5］數(shù)據(jù)非常相似.但是世系數(shù)據(jù)比社會(huì)網(wǎng)絡(luò)數(shù)據(jù)所表達(dá)的人物群體更加特定，人物之間的關(guān)系更加明確.

總結(jié)起來，世系數(shù)據(jù)具有以下特點(diǎn)：

（1）表達(dá)對(duì)象是特定的人物“群體”——家族（或者支系），人物關(guān)系是親緣關(guān)系，相比其他人際關(guān)系要更加緊密和牢固.

（2）如果把人物視作節(jié)點(diǎn)，把人物之間的關(guān)系視作邊，世系數(shù)據(jù)構(gòu)成了一種特殊的層次結(jié)構(gòu)—世系樹.

（3）如果把多個(gè)世系樹用聯(lián)姻關(guān)系聯(lián)系在一起，會(huì)構(gòu)成一種特殊的圖結(jié)構(gòu)，類似于森林和社會(huì)化網(wǎng)絡(luò)數(shù)據(jù).

圖1 世系樹示例圖Fig.1 The tree structure of genealogy data

2 族譜信息系統(tǒng)

傳統(tǒng)族譜信息系統(tǒng)采用的是單機(jī)管理不易于擴(kuò)展功能，數(shù)據(jù)分散且有大量冗余，無法利用這些族譜數(shù)據(jù)向公眾用戶提供服務(wù).為了更好地收集和利用族譜數(shù)據(jù)，我們?cè)O(shè)計(jì)并開發(fā)了一款基于B／S架構(gòu)的族譜信息系統(tǒng).該系統(tǒng)支持多用戶并行錄入同一族譜中的數(shù)據(jù)，并統(tǒng)一對(duì)族譜數(shù)據(jù)進(jìn)行管理，同時(shí)通過本系統(tǒng)還可向公眾用戶提供對(duì)已錄入族譜數(shù)據(jù)的檢索.

族譜信息系統(tǒng)的主要功能包括數(shù)據(jù)錄入、數(shù)據(jù)服務(wù)和數(shù)據(jù)輸出.

2.1 數(shù)據(jù)錄入

數(shù)據(jù)錄入功能主要包括三部分：世系數(shù)據(jù)錄入、文檔數(shù)據(jù)錄入、多媒體數(shù)據(jù)錄入.其中世系數(shù)據(jù)錄入是指錄入人物的基本數(shù)據(jù)以及錄入人物之間的聯(lián)系數(shù)據(jù).

2.2 數(shù)據(jù)服務(wù)

數(shù)據(jù)服務(wù)功能主要包括數(shù)據(jù)展示、統(tǒng)計(jì)檢索、一鍵尋祖和一鍵尋親.

（1）數(shù)據(jù)展示

數(shù)據(jù)展示功能包括族譜展示和對(duì)照預(yù)覽.族譜展示功能主要顯示一個(gè)族譜的基本信息.對(duì)照預(yù)覽則用于在正式輸出紙質(zhì)化族譜之前以各種不同的樣式來預(yù)覽輸出的效果.

（2）統(tǒng)計(jì)檢索

統(tǒng)計(jì)檢索提供了對(duì)系統(tǒng)中的族譜數(shù)據(jù)進(jìn)行統(tǒng)計(jì)和檢索的功能.族譜統(tǒng)計(jì)是顯示整個(gè)族譜的統(tǒng)計(jì)信息，如總?cè)藬?shù)、男女比例、生死狀況等.簡單檢索和組合檢索是在某些族譜屬性或者人物屬性上進(jìn)行檢索的功能.

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

一鍵尋祖可以從族譜中根據(jù)人物之間的親緣關(guān)系得到指定人物在指定范圍內(nèi)（比如限定世代數(shù)）的祖先.一鍵尋親則是指在族譜數(shù)據(jù)中找到兩個(gè)指定人物之間的親緣關(guān)系鏈（即兩人是通過哪些人關(guān)聯(lián)在一起）.

2.3 數(shù)據(jù)輸出

為了滿足用戶傳統(tǒng)紙質(zhì)譜書的需求，族譜信息系統(tǒng)中提供了數(shù)據(jù)輸出功能，主要包括族譜編排、族譜生成.

（1）族譜編排

譜志編排功能是通過用戶的個(gè)性化需求對(duì)譜書的樣式、數(shù)據(jù)出現(xiàn)的順序、名詞的表達(dá)方式等進(jìn)行設(shè)置.

（2）族譜生成

族譜生成功能主要是在族譜編排過后，按照用戶的個(gè)性化需求從原始族譜數(shù)據(jù)中轉(zhuǎn)換生成電子版的譜書以供印刷.

2.4 應(yīng)用內(nèi)存數(shù)據(jù)管理技術(shù)的必要性

通過對(duì)族譜信息系統(tǒng)的功能分析，族譜信息系統(tǒng)具有以下特點(diǎn).

（1）數(shù)據(jù)源單一.在數(shù)據(jù)錄入過程中，對(duì)每個(gè)錄入用戶來說，只能操作自己參與錄入的族譜數(shù)據(jù).同時(shí)，數(shù)據(jù)輸出過程中，只需要去訪問要生成電子族譜的特定族譜的數(shù)據(jù).（2）數(shù)據(jù)量較大.每個(gè)族譜都存有數(shù)量和容量龐大的世系數(shù)據(jù)、文檔數(shù)據(jù)、多媒體數(shù)據(jù).（3）實(shí)時(shí)性要求高.由于本系統(tǒng)基于B／S模式設(shè)計(jì)，無論是數(shù)據(jù)錄入、數(shù)據(jù)服務(wù)還是數(shù)據(jù)輸出功能，系統(tǒng)響應(yīng)時(shí)間都應(yīng)該很短.

族譜信息系統(tǒng)的大數(shù)據(jù)量和高實(shí)時(shí)性的特點(diǎn)對(duì)系統(tǒng)實(shí)現(xiàn)提出了挑戰(zhàn).而隨著主存的成本顯著降低，許多成熟的內(nèi)存數(shù)據(jù)管理技術(shù)為族譜信息系統(tǒng)的實(shí)現(xiàn)提供了解決方案［6］.

3 內(nèi)存數(shù)據(jù)管理技術(shù)

內(nèi)存數(shù)據(jù)管理［7］的關(guān)鍵技術(shù)包括存儲(chǔ)結(jié)構(gòu)［8］、索引結(jié)構(gòu)［9］、并發(fā)控制［10］、同步策略［11］、故障恢復(fù)［12］等.本節(jié)將重點(diǎn)介紹系統(tǒng)中用到的索引結(jié)構(gòu)和同步策略.

3.1 索引結(jié)構(gòu)

內(nèi)存數(shù)據(jù)庫由于其工作的主版本保存在內(nèi)存中，所以內(nèi)存數(shù)據(jù)庫的索引選擇應(yīng)結(jié)合存儲(chǔ)介質(zhì)的特點(diǎn)，從而通過索引的建立來保證內(nèi)存數(shù)據(jù)庫查詢操作的高效性.目前在內(nèi)存數(shù)據(jù)庫中經(jīng)常選用的索引結(jié)構(gòu)有hash索引和T樹索引.

（1）hash索引［13］定義了一個(gè)hash函數(shù)，通過將關(guān)系表的索引項(xiàng)傳入到hash函數(shù)可以計(jì)算出相應(yīng)的hash值，從而在索引項(xiàng)和hash值之間建立起對(duì)應(yīng)關(guān)系，通過hash索引查找數(shù)據(jù)只需常數(shù)時(shí)間的復(fù)雜度.

（2）在內(nèi)存數(shù)據(jù)庫中目前較廣泛使用的一種樹是結(jié)合B樹［14］和AVL樹進(jìn)化而來的T樹［14］.T樹的單個(gè)節(jié)點(diǎn)有多個(gè)數(shù)據(jù)，因此擁有良好的修改和存儲(chǔ)特性.由于T樹屬于AVL樹的一種演進(jìn)，具有AVL樹的平衡特性，從而進(jìn)一步提升了樹的搜索性能.因此T樹在時(shí)間和空間兩者間具備較好的平衡性.

hash索引在進(jìn)行定值的查找時(shí)效率很高，而T樹索引一方面具有樹的二叉性而且其設(shè)計(jì)符合內(nèi)存數(shù)據(jù)庫存儲(chǔ)介質(zhì)的特性，所以當(dāng)前主流的內(nèi)存數(shù)據(jù)庫都至少提供了這兩種索引結(jié)構(gòu).

3.2 同步策略

內(nèi)存數(shù)據(jù)管理的數(shù)據(jù)同步更新技術(shù)大致可以分為表復(fù)制技術(shù)、事務(wù)復(fù)制技術(shù)、觸發(fā)器技術(shù)和影子表技術(shù).這里主要介紹表復(fù)制技術(shù)和事務(wù)復(fù)制技術(shù)［15］.

（1）表復(fù)制技術(shù)：采用把某一時(shí)刻源數(shù)據(jù)表的內(nèi)容通過網(wǎng)絡(luò)發(fā)送到復(fù)制的副本，因?yàn)閺?fù)制的內(nèi)容是表的某一時(shí)刻的狀態(tài)，所以又被形象地稱為表快照.表快照的復(fù)制不是以事務(wù)為基礎(chǔ)，所以副本缺乏基本的關(guān)系完整性.基于表復(fù)制技術(shù)不需依賴特別的機(jī)制，不占用額外的系統(tǒng)資源，管理和操作也非常容易，而且在同步初始化和崩潰恢復(fù)時(shí)是必須的.但是全表更新效率很低.

（2）事務(wù)復(fù)制技術(shù)：事務(wù)復(fù)制技術(shù)是把修改源數(shù)據(jù)的事務(wù)通過網(wǎng)絡(luò)發(fā)送到復(fù)制的副本，復(fù)制可以是修改的表項(xiàng)事務(wù)或事務(wù)日志.復(fù)制的時(shí)間可根據(jù)應(yīng)用需求而確定.副本接收到復(fù)制內(nèi)容后，要重復(fù)一遍接收到的事務(wù)操作來實(shí)現(xiàn)與數(shù)據(jù)源的一致.一般是基于數(shù)據(jù)庫日志通過分析日志的信息來獲得數(shù)據(jù)的差異，最后達(dá)到數(shù)據(jù)同步.

4 內(nèi)存數(shù)據(jù)管理技術(shù)在系統(tǒng)中的應(yīng)用

在族譜信息系統(tǒng)中需要大量的遞歸查詢操作，而且系統(tǒng)對(duì)數(shù)據(jù)存取的實(shí)時(shí)性要求比較高，只依靠基于磁盤的傳統(tǒng)數(shù)據(jù)庫系統(tǒng)無法滿足族譜信息系統(tǒng)的要求.為了保證數(shù)據(jù)處理的實(shí)時(shí)性和可靠性，族譜信息系統(tǒng)中采用內(nèi)存和外部存儲(chǔ)設(shè)備（如磁盤）共同作為數(shù)據(jù)的存儲(chǔ)介質(zhì).族譜信息系統(tǒng)將實(shí)時(shí)或關(guān)鍵性數(shù)據(jù)的操作放在內(nèi)存數(shù)據(jù)庫中進(jìn)行，由于內(nèi)存的數(shù)據(jù)存取速度比磁盤快，引入內(nèi)存數(shù)據(jù)管理技術(shù)會(huì)使族譜信息系統(tǒng)更高效，更迅捷.

4.1 族譜信息系統(tǒng)結(jié)構(gòu)

在族譜信息系統(tǒng)的業(yè)務(wù)邏輯中，系統(tǒng)的運(yùn)營商負(fù)責(zé)分配錄入任務(wù)給各個(gè)代理商，各代理商再將任務(wù)分割為多個(gè)子任務(wù)，并組織多位錄入人員進(jìn)行錄入.為了增加子系統(tǒng)的可靠性和靈活性，族譜信息系統(tǒng)采用分布式結(jié)構(gòu)［16］（如圖2所示）.系統(tǒng)中包括了一個(gè)中心數(shù)據(jù)節(jié)點(diǎn)和多個(gè)分布數(shù)據(jù)節(jié)點(diǎn).中心數(shù)據(jù)節(jié)點(diǎn)儲(chǔ)存了所有的族譜數(shù)據(jù)；而每個(gè)代理商擁有一個(gè)分布數(shù)據(jù)節(jié)點(diǎn)，存儲(chǔ)了本代理商代理錄入完成的族譜數(shù)據(jù).

每個(gè)分布數(shù)據(jù)節(jié)點(diǎn)都是由一個(gè)磁盤數(shù)據(jù)庫和一個(gè)內(nèi)存管理單元組成.其中內(nèi)存管理單元包括內(nèi)存數(shù)據(jù)庫、用戶請(qǐng)求處理模塊、接收隊(duì)列、發(fā)送隊(duì)列、節(jié)點(diǎn)狀態(tài)管理模塊、資源管理模塊和數(shù)據(jù)同步模塊，內(nèi)存數(shù)據(jù)庫采用列存儲(chǔ)模型來實(shí)現(xiàn)存儲(chǔ).用戶請(qǐng)求處理模塊主要是接收用戶請(qǐng)求，并根據(jù)用戶請(qǐng)求進(jìn)入不同的處理分支.接收隊(duì)列用于接收用戶提交的新增的數(shù)據(jù)或者是修改的數(shù)據(jù).發(fā)送隊(duì)列用于發(fā)送給用戶所要求的查詢結(jié)果數(shù)據(jù).數(shù)據(jù)同步模塊用來維持分布數(shù)據(jù)節(jié)點(diǎn)和中心數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)同步.資源管理模塊主要是對(duì)內(nèi)存資源進(jìn)行分配和回收.

4.2 數(shù)據(jù)錄入功能的內(nèi)存管理策略

在數(shù)據(jù)錄入功能中，每個(gè)錄入用戶登錄之后首先會(huì)選擇自己要錄入的族譜，系統(tǒng)自動(dòng)連接該族譜隸屬的代理商的分布數(shù)據(jù)節(jié)點(diǎn).

分布數(shù)據(jù)節(jié)點(diǎn)中的用戶請(qǐng)求處理模塊會(huì)識(shí)別用戶數(shù)據(jù)錄入請(qǐng)求，把用戶選擇的族譜數(shù)據(jù)作為熱點(diǎn)數(shù)據(jù)存入到內(nèi)存數(shù)據(jù)庫當(dāng)中.由于數(shù)據(jù)錄入功能的主要操作是插入新元組，所以元組集合在內(nèi)存數(shù)據(jù)庫中采用堆組織以便高效地插入新元組；同時(shí)按照鍵值建立哈希索引，其中重名的會(huì)依次放在指針數(shù)組中.

圖2 族譜信息系統(tǒng)架構(gòu)Fig.2 The structure of the genealogy information system

當(dāng)用戶插入新元組時(shí)，新元組會(huì)加入到系統(tǒng)的接收隊(duì)列，分布數(shù)據(jù)節(jié)點(diǎn)會(huì)把新增元組加入到內(nèi)存中存儲(chǔ)；當(dāng)用戶需要請(qǐng)求檢索數(shù)據(jù)時(shí)，對(duì)應(yīng)分布數(shù)據(jù)節(jié)點(diǎn)會(huì)根據(jù)索引快速定位數(shù)據(jù)位置并返回給用戶；當(dāng)用戶修改數(shù)據(jù)時(shí)會(huì)把修改后的數(shù)據(jù)加入到系統(tǒng)的接收隊(duì)列，分布數(shù)據(jù)節(jié)點(diǎn)會(huì)把接收隊(duì)列中的數(shù)據(jù)依次更新；當(dāng)用戶刪除數(shù)據(jù)的時(shí)候，分布數(shù)據(jù)節(jié)點(diǎn)會(huì)通過索引定位到該數(shù)據(jù)并執(zhí)行刪除，同時(shí)內(nèi)存資源管理模塊進(jìn)行內(nèi)存資源回收.

4.3 數(shù)據(jù)服務(wù)功能的內(nèi)存管理策略

由于在數(shù)據(jù)服務(wù)功能中主要是對(duì)世系數(shù)據(jù)的大量結(jié)構(gòu)化查詢，分布數(shù)據(jù)節(jié)點(diǎn)采用T樹索引結(jié)構(gòu)來存儲(chǔ)元組信息.其中每個(gè)節(jié)點(diǎn)的數(shù)據(jù)中都含有人物對(duì)象的詳細(xì)信息和分別指向父親、母親、過繼或兼祧父親、過繼或兼祧母親的四個(gè)指針.同時(shí)建立哈希索引（同第4.2節(jié)）.

當(dāng)數(shù)據(jù)錄入導(dǎo)致本族譜世系數(shù)據(jù)發(fā)生改變的時(shí)候，會(huì)對(duì)內(nèi)存T樹索引和哈希索引進(jìn)行更新，分為以下幾種情況.

（1）如果需要增加新的元組，系統(tǒng)會(huì)對(duì)T樹索引做插入操作并更新哈希索引；

（2）如果需要更新某個(gè)元組，系統(tǒng)會(huì)通過T樹索引找到舊元組直接進(jìn)行更新如需要?jiǎng)t同時(shí)更新哈希索引；

（3）如果需要?jiǎng)h除某個(gè)元組，系統(tǒng)會(huì)先通過T樹索引找到該元組然后刪除該元組，更新T樹索引和哈希索引，同時(shí)資源管理模塊進(jìn)行內(nèi)存資源回收.

在數(shù)據(jù)服務(wù)功能中，當(dāng)用戶請(qǐng)求一鍵尋祖的時(shí)候輸入要尋祖的人物譜名和祖先的世代數(shù)（可以不輸入，默認(rèn)為族譜中最小的世代數(shù)），分布數(shù)據(jù)節(jié)點(diǎn)會(huì)首先通過哈希索引找到T樹索引中對(duì)應(yīng)的人物對(duì)象元組節(jié)點(diǎn).如果存在多個(gè)重名的人物對(duì)象則會(huì)返回幾個(gè)人物對(duì)象的具體信息供用戶選擇；如果該譜名只對(duì)應(yīng)一個(gè)人物對(duì)象或者用戶從重名人物中選擇了一個(gè)人物對(duì)象，則分布數(shù)據(jù)節(jié)點(diǎn)會(huì)從世系樹中該人物對(duì)象節(jié)點(diǎn)開始循環(huán)地通過父親或兼祧父親指針尋找祖先節(jié)點(diǎn)；當(dāng)該祖先的世代數(shù)等于用戶輸入的值，則停止循環(huán)并返回該祖先節(jié)點(diǎn)元組給用戶.

4.4 數(shù)據(jù)輸出功能的內(nèi)存管理策略

在數(shù)據(jù)輸出功能中，每個(gè)用戶需要首先選擇族譜，分布數(shù)據(jù)節(jié)點(diǎn)把對(duì)應(yīng)的族譜數(shù)據(jù)作為熱點(diǎn)數(shù)據(jù)載入到內(nèi)存數(shù)據(jù)庫中，在后續(xù)的族譜編排和族譜生成中可以直接訪問分布數(shù)據(jù)節(jié)點(diǎn)的內(nèi)存，并建立T樹索引（同第4.2節(jié)）.

當(dāng)用戶對(duì)世系數(shù)據(jù)進(jìn)行分組（可以按照個(gè)人或者是世代分組）時(shí)，分布數(shù)據(jù)節(jié)點(diǎn)會(huì)通過T樹索引檢索對(duì)應(yīng)人物更新其分組號(hào)；當(dāng)用戶按照需求對(duì)世系和文檔進(jìn)行分卷時(shí)，會(huì)對(duì)世系分組和文檔數(shù)據(jù)進(jìn)行排序用于生成對(duì)應(yīng)的電子族譜，同時(shí)分布數(shù)據(jù)節(jié)點(diǎn)會(huì)按照用戶的編排順序?qū)?nèi)存中的數(shù)據(jù)進(jìn)行排序；當(dāng)用戶選擇相應(yīng)的模板請(qǐng)求族譜生成的時(shí)候，分布數(shù)據(jù)節(jié)點(diǎn)會(huì)根據(jù)模板的格式生成族譜并返回給用戶.

4.5 數(shù)據(jù)同步策略

在族譜信息系統(tǒng)中，每個(gè)分布數(shù)據(jù)節(jié)點(diǎn)的內(nèi)存數(shù)據(jù)庫保存著實(shí)時(shí)數(shù)據(jù)，但是內(nèi)存屬易失性存儲(chǔ)，為了提高數(shù)據(jù)的可靠性，必須和外存數(shù)據(jù)庫進(jìn)行數(shù)據(jù)同步.同時(shí)中心數(shù)據(jù)節(jié)點(diǎn)作為所有分布數(shù)據(jù)節(jié)點(diǎn)族譜數(shù)據(jù)的副本也需要和分布數(shù)據(jù)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)同步.

4.5.1 分布數(shù)據(jù)節(jié)點(diǎn)內(nèi)外存數(shù)據(jù)同步

分布數(shù)據(jù)節(jié)點(diǎn)內(nèi)外存數(shù)據(jù)同步屬于單向同步，除了內(nèi)存數(shù)據(jù)初始化外，數(shù)據(jù)都是從內(nèi)存數(shù)據(jù)庫傳輸?shù)酵獯鏀?shù)據(jù)庫當(dāng)中.

在族譜信息系統(tǒng)中，分布數(shù)據(jù)節(jié)點(diǎn)的內(nèi)外存數(shù)據(jù)同步是由常駐后臺(tái)進(jìn)程MMSyn來實(shí)現(xiàn)的.分布數(shù)據(jù)節(jié)點(diǎn)啟動(dòng)后，MMSyn進(jìn)程就會(huì)自動(dòng)啟動(dòng).MMSyn進(jìn)程啟動(dòng)時(shí)需要初始化系統(tǒng)設(shè)置的同步周期時(shí)間和進(jìn)程數(shù)閥值.MMSyn進(jìn)程在上次同步操作完成和下次同步操作開始之間會(huì)休眠一個(gè)同步周期.每次MMSyn進(jìn)程被喚醒之后，會(huì)通過事務(wù)日志來檢測是否存在數(shù)據(jù)更新，如果有而且當(dāng)前的進(jìn)程數(shù)低于閥值就進(jìn)行數(shù)據(jù)更新，否則MMSyn進(jìn)程繼續(xù)休眠.MMSyn進(jìn)程在數(shù)據(jù)更新過程前會(huì)讀取存儲(chǔ)的上次完成同步的事務(wù)日志序列號(hào)，從下一事務(wù)日志開始在外存里重做事務(wù)操作從而完成同步.

4.5.2 分布數(shù)據(jù)節(jié)點(diǎn)與中心數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)同步

分布數(shù)據(jù)節(jié)點(diǎn)分散存儲(chǔ)著各個(gè)代理商代理錄入的族譜信息，而中心數(shù)據(jù)節(jié)點(diǎn)作為穩(wěn)定的中心數(shù)據(jù)備份必須和分布數(shù)據(jù)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)同步.分布數(shù)據(jù)節(jié)點(diǎn)與中心數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)同步屬于單向同步，除了分布數(shù)據(jù)節(jié)點(diǎn)崩潰從中心數(shù)據(jù)節(jié)點(diǎn)恢復(fù)以外，數(shù)據(jù)都是從分布數(shù)據(jù)節(jié)點(diǎn)傳輸?shù)街行臄?shù)據(jù)節(jié)點(diǎn)當(dāng)中.

在族譜信息系統(tǒng)中，分布數(shù)據(jù)節(jié)點(diǎn)與中心數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)同步是由分布數(shù)據(jù)節(jié)點(diǎn)常駐后臺(tái)進(jìn)程DSyn和中心數(shù)據(jù)節(jié)點(diǎn)常駐后臺(tái)進(jìn)程CSyn來實(shí)現(xiàn)的.在族譜信息系統(tǒng)啟動(dòng)后，CSyn和DSyn進(jìn)程會(huì)自動(dòng)啟動(dòng).

和MMsyn進(jìn)程相似，DSyn進(jìn)程在啟動(dòng)時(shí)需要初始化系統(tǒng)設(shè)置的同步周期時(shí)間和進(jìn)程數(shù)閥值.每次DSyn進(jìn)程被喚醒之后，會(huì)讀取存儲(chǔ)的上次完成同步的事務(wù)日志序列號(hào)n，如果當(dāng)前最大的日志序列號(hào)m＞n（日志序列號(hào)是遞增的），則將n＜日志序列號(hào)＞m的日志發(fā)送給中心數(shù)據(jù)節(jié)點(diǎn).

中心數(shù)據(jù)節(jié)點(diǎn)一旦啟動(dòng)，就會(huì)開啟CSyn進(jìn)程.當(dāng)分布數(shù)據(jù)節(jié)點(diǎn)發(fā)送過來日志序列時(shí)，CSyn重做事務(wù)操作從而完成同步.

5 結(jié) 論

本文設(shè)計(jì)并實(shí)現(xiàn)的族譜信息系統(tǒng)采用了B／S架構(gòu)，能更好地支持族譜數(shù)據(jù)的分散錄入以及集中共享的現(xiàn)實(shí)需求.在族譜數(shù)據(jù)管理方面采用了分布式結(jié)構(gòu)，其中包括中心數(shù)據(jù)節(jié)點(diǎn)和分布數(shù)據(jù)節(jié)點(diǎn).中心數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)全部族譜的數(shù)據(jù)，分布數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)對(duì)應(yīng)代理商錄入的族譜數(shù)據(jù)，通過同步策略實(shí)現(xiàn)中心數(shù)據(jù)節(jié)點(diǎn)和各個(gè)分布數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)同步，大大加強(qiáng)了系統(tǒng)的可靠性和靈活性.

分布數(shù)據(jù)節(jié)點(diǎn)引入了內(nèi)存數(shù)據(jù)管理技術(shù)，采用列存儲(chǔ)模型存儲(chǔ)結(jié)構(gòu)，并根據(jù)用戶具體的請(qǐng)求初始化熱點(diǎn)數(shù)據(jù)，建立索引.用戶的操作在分布數(shù)據(jù)節(jié)點(diǎn)內(nèi)存中進(jìn)行，加快了系統(tǒng)的響應(yīng)速度.同時(shí)，系統(tǒng)利用事務(wù)日志進(jìn)行分布數(shù)據(jù)節(jié)點(diǎn)的內(nèi)外存同步和內(nèi)存數(shù)據(jù)庫恢復(fù)，增強(qiáng)了系統(tǒng)的可靠性.

未來的工作還需要考慮熱點(diǎn)數(shù)據(jù)的優(yōu)化選擇、分布數(shù)據(jù)節(jié)點(diǎn)負(fù)載均衡等問題.

［1］ 張卓.開發(fā)利用族譜檔案的意義［J］.云南檔案，2006（3）：32－33.

［2］ FamilySearch［EB／OL］.http：／／familysearch.org.

［3］ 啟航宗譜［EB／OL］.http：／／www.qhzprj.com.

［4］ 中根網(wǎng)［EB／OL］.http：／／www.zongen.com.

［5］ GRANOVETTER M.Economic action and social structure：the problem of embeddedness［J］.American Journal of Sociology，1985，19（3）：481－510.

［6］ FREITAS R F，WILCKE W W.Storage－class memory：The next storage system technology［J］.IBM Journal of Research and Development，2008，52（4／5）：439－447.

［7］ LEHMAN T J，CAREY M J.A study of index structures for main memory database management systems［C］／／Conference on Very Large Data Bases.1986，294.

［8］ ABADI D J，MADDEN S R，HACHEM N.Column－stores vs.row－stores：how different are they really？［C］／／Proceedings of the 2008 ACM SIGMOD international conference on Management of data.ACM，2008：967－980.

［9］ GRAEFE G，IDREOS S，KUNO H，et al.Benchmarking adaptive indexing［M］／／Performance Evaluation，Measurement and Characterization of Complex Systems.Berlin：Springer，2011：169－184.

［10］ ALCANTARA D A，SHARF A，ABBASINEJAD F，et al.Real－time parallel hashing on the GPU［C］／／ACM Transactions on Graphics（TOG）.ACM，2009，28（5）：154.

［11］ DEWITT D J，KATZ R H，OLKEN F，et al.Implementation techniques for main memory database systems［M］.ACM，1984.

［12］ OUSTERHOUT J，AGRAWAL P，ERICKSON D，et al.The case for RAMClouds：scalable high－performance storage entirely in DRAM［J］.ACM SIGOPS Operating Systems Review，2010，43（4）：92－105.

［13］ LEHMAN T J，CAREY M J.A study of index structures for main memory database management systems［C］／／Conference on Very Large Data Bases.1986，294.

［14］ LU H J，Yuet Yeung Ng，Tian Z P.T－tree or b－tree：Main memory database index structure revisited［C］／／Database Conference，2000.ADC2000.Proceedings.11th Australasian.IEEE，2000：65－73.

［15］ LEE S W，MOON B.Design of flash－based DBMS：an in－page logging approach［C］／／Proceedings of the 2007 ACM SIGMOD international conference on Management of data.ACM，2007：55－66.

［16］ KALLMAN R，KIMURA H，NATKINS J，et al.H－store：a high－performance，distributed main memory transaction processing system［J］.Proceedings of the VLDB Endowment，2008，1（2）：1496－1499.