1、多線程內存數據庫服務器設計宋廣華（浙江大學計算機系，杭州）：”摘要文章介紹了一個多踐程內存數據庫服務器（）由于采用多線程技術，克服了多進程率系結構資源消耗多、進程調度開銷大、難以實現大容量共享存儲等主要缺陷。文中詳細闡述了采用“移動平均反饋”事務預潘法（）的實時數據庫引擎（）、動態內存管理（）、用戶數據索引壓并發控制。關鍵詞內存數據庫實時教據庫引擎動態內存管理鎖文獻標識碼中圍分類號文章編號一（）（，）：（）￥（）”（），：】（）。（），引言近年來，磁；數據庫（）技術獲得丁空前的發展并在國內對的研究還處于起步階段尚投有正式的實驗系統問世。在文獻【】巾，介紹丁個基于多進程的支持實時消息處理的內存數

2、據庫系統。文章將介紹一個基于多線程的內存數據席服務器。對佧了改進，它利用現代操作系統的多線稃機制，克服了多進程結構的主要弊端，獲得了較高的性能。的多線程結構體現了如下的一些主要優點：（）線程問切換更快，線程間通信易實現。由于進程中的線程問共享相同的用戶地址空間，切換時不必通過進程桶度；通信可以直接通過共享的內存區進行；商務及事務應用中得到了巨大的成功。然而，）對于高實時性姜求的應用的支持卻顯得軟剝無力。主要原因足，傳統中由于事務所涉及的操作、緩沖區管理、且違例等事件的執行時間的弱實時性及不可壩知性，使得事務的實時性和擷測性較差，宴時數據庫系統（）是為了克服的返些測點而運漸發展起來的。實時系統是

3、指事務具有時效性，即如果事務不能在期卑的時限內完成，其結果可能是無用的甚至足有害的。相應地，是支持實時數據庫成用系統，其事務執行具有強的實時性和可預測性，并具有事務拄制能力以獲得高事務吞吐率的數據庫管理系統。隨著存儲器。，片集成度的提高和造價的降低，算機的主存容譬不斷增加，使得將數據庫中的數據或太部分數據存在俘，成為可能，內存數據庫系統（）應運而生。所謂內行數據庫系統是指事務的執行本身沒有操作內存中的數據是數據蘋的毛拷叭，而外存，的數據只是數據庫的個副拷貝（備份）【。國外對）的究起步較早，已有少數商品化的產品，如、等系統，但對系統的研究大多仍處十實驗系統階段。比較典型的如文獻介紹的“”及文獻【

4、介紹的“”前者是一個基于實時操作系統內核的系統后者是（）并行村度及并干效率提高了，從而提高系統整體性能。進程中的各線程各司其職，線程窯閑（阻塞）時，內核市即會調度進程中的其他線程占有，線程的優先級及執行時問片可以動態調整。在多環境下，線程可以被指定在特定的上運行。（）進程中的各線程共享相同的用戶地址李間，因而可以共享大容量的存儲區。而在多進程結構中共亭只能通過系統提供的共享存儲區進行這個區域中的實際口用牽間小于進程的用戶地址空間。（）方便實現應用，動態地為每個客廣創建一個客戶服務線程。山于線程的管理丹銷較小，可以提高多客戶服務器性能。這里對其中的一些主要技術如實時數據庫引擎（）、動志內存管理器

5、（）、用戶數據的索引以及并發控制等將做詳細闡述。計算機工程與應用個采用多進程其亨存儲體系結構的系統。然向，這釁系統一般都需要專用操作系統支持，通用性較差系統資源肖耗大，因而很難適用于實時應用系統中。的體系結構圖描述了基于多線程的內存數據庫服務器的送往相應優先級的消息隊列。各服務線程從各自的消息隊列中提取客戶請求消息調用相應的數據庫服務例稃，實現對數據庫的訪廿并將應答消息送往應答消息隊列如果消息由于等待資源而阻塞則設置人相應的阻塞隊列中在滿足條件時繼續執行。體系結構，是個典型的模式下的數據庫服務器網絡監聽線程監聽網絡上的客戶請求并且為每一十客戶生成一個客戶服務線程。客戶請求被送往實時數據庫引擎（

6、），以進行處理。客戶請求的應答消息通過專用的應答發送線程發送至客戶。“移動平均反饋”事務預測法（）對于實時數據庫系統，消息處理時間的壩測是非常重安的，它可以有效地控制事務的執行，提高事務執行的正確率及系統的喬吐率。中，消息在被處理前，首先被預測，只有那嶼預測可以在截：期前處理完的消息才會被接量。我們采用一種稱為“移動平均反饋法”（：）的預測方法。進、和叮分別為消息、和，對應的事務的預測執行時間。系統啟動時均棱扔始化為。為了進行事務執行時間的壩測，我們分別為、和，類事務設置了二個“事務歷史執行時閘隊列”，分別為、和它們都是先進先出（）隊列，存放每一類雖近個事務的執時間其中為隊列長度，是系統參數，

7、町進¨存線修改。的基本思想是，用歷史上最新的個該婁事務的成功執行時間的平均值（或加權平均值）作為本類事務的預測執行時閘。圈的體系結構當一個消息到達時，獲得的到達時刪設丁為當前時間，則：實時數據庫引擎（】為消息傳輸時延。假設府答消息的傳輸日延也的組成中的客戶請求消息被分為三類：低優先級消息為兕則此消息的最大允許執為：二）（）、巾等優先級讀消息（）和高優先級消息（）。相應地由一個服務仲裁器（）、三個數據庫服務線程及各自的請求消息隊列組成，如圖。三個數據庫服務線程分別這里星消息的有效時限，以為例，預測算法口以描述為：（盯）拒絕陵消息，并通知客戶；置；接受該消息；獲取消息的優先級；置當前時間

8、，被認為是消息執行的起始時間；將消息連同送相應的消息隊列；當應答消息產生時，將被修改：【足低優先級服務線程（肌）、中優先級服務線程（）和高優先級服務線程（），每個線程的優先級與相應的消息的優先級一致，置刀當前時，即為消息執行結束時問；置仃即為消息執行消耗時間；調整為：，尸（卜），其中為最近第個該類事務的執行時間。算法中。一旦一個消息被拒絕，則被置。這樣后續的圍實時數據庫引鼙消息又有機會被接受，從而避免由于連續成功執行了若干個長事務后，后米的短時限消息總是棱拋棄。當一個客戶請求到達時，服務仲裁器檢杏客戶請求的臺法性（包括客戶身份的臺法性及消息包的合法性），提取請求消息的優先級，預測消息的處理時間

9、，然后將可受理的消息內存管理動態內存管理計算機工程與應用為了優化內存分配、釋放的執行效率提高內存訪問的安全性，合理解決內存碎片問題，在中設置了動態內存管理（）模塊。是操作系統的一次擴展是的最底層中的其他部分都是的用戶。采用堆式內存管理方法，算法的核心有兩條，其一是把數據區與控制分開，其二足使用循環分配算法。數據區與控制區分開把數據區與控制區分開是為了提高系統的安全性。所謂數據區就是供用戶使用的存儲區，所瑁控制區，就是由自己使用的存儲區把數據區與控制區分開大大提高了數據安全性用戶操作數據不會改寫控制區的內容。數據區實際匕是一次性向申請的連續的內存區。控制區存放描述內存塊的控制節點每個節點主要包括

10、以下幾個字段：狀態寧段（），描述挎制結點的狀態和內存塊的狀態。控制區與數據區分離后，在申請一個內存塊時必須申請一個內存塊的控制結點。在申請到一個空閑控制結點后，才能申請一個內存塊所以，該字段有幣取值：寧閉肖點，此時該結點不描述任何內存塊；于【塊，此時該結點描述一個已被占用的內存塊；閑塊，此時該結點描述一個末分配的內存塊。后繼指針（）當結點描述一個忙塊或閑塊時，它指向的結點所描述的內存塊（忙或閑）緊接在本內存塊的后面內存地址連續。前趨指針（），當結點描述一個忙塊或閑塊時，它指向的結點所描述的內存塊（忙或閑）緊接在奉內存塊的前面，內存地址璉續塊大小（），當結點描述一個忙塊或閑塊時，表示內存塊的字節

11、數。塊首地址（），當結點描述一個忙塊或閑塊時，表示內存塊的首地址。由于每一個內存塊都對鹿一個控制節點，所以控制節點在控制區的下標就成了內存塊的內部標識，即句柄。內存句柄的分配、釋放采用方式，即在初始化時，把內存句柄放八一個隊列中分配時從頭取元素，釋放時把句柄插刊尾部。循環內存分配空用內存塊的分配算法采用循環分配算法。其基本思想來源于這樣的假蹬：在半均意義下越早申請的內存越可能先被釋放這些釋放了的內存叉會連成一片較大的內存。因此，申請最久前被分配的內存區，成功的概率相對較大。殳置了一個循環查找指針指向下一個可分配的李閑內存塊內作申請遇到一個較大的內存塊時進行內存塊分裂。分裂的閩值是一個系統參數。

12、分裂時先中請一個牽閑控制結點，用它描述分裂后的空閑內存塊。分裂后，循環查找指針指向分裂出的寧闞塊上。內存釋放遇到一個相鄰的空閑內存塊時，進行內存塊合并若被合并的蚨是循環直找指針指出的內存塊則要把循環查找指釗髑罄到臺并后的太塊上。合并后，釋放被臺并塊的控制結點用戶數據的索引基于可裝卸式分區的用戶數據存儲定艾分區是用于存儲用戶數據的固定度的連續存儲空間。中的用戶數據被存放在各自的歸屬分區中。設系統向申請獲得了個分區，第個分區表示為，分區只中的用戶數據表示為鞏。則中的用廣數據（。）為：廬，且一，由，定義一個分區是在線的，如果這個分區中的用、數據耐用戶是可訪問的；一個分區是離線的，如果這個分區中的用，

13、數據對用戶是不可訪問的。一個分區可眥設置為離線或在線稱這個分區是可裝卸的。裝卸式分區管理町以提高分數據的安全性及動態調整內存數據庫規模，提高系統運行教率。另外，當采用分布式數據庫系統時，可以實現分區在各數據庫節點問的平滑遷移。為了實現對系統中分區的管理，我們申請一塊內存來存放一個系統分區表（）。用戶數據索引為了實現元組的高效索引，采用索引技術是行之有效的。采崩獨立級索引。定義設為用戶數據元組的主鍵，其長度為，的前綴是置最重要的。位的組合，記為（）；的后綴是中最不重要的如位的組臺，記為（）。這里（），（），且如島。廠和是預知的。每一個分區都設置了一個分區可用元組表（），一個分區索引表（）和一個索

14、引溢出表（）。記一個用廣數據元組為，其主鍵為邢。當新增（）這個元組時，一（肼）（邢），（腫）即為丌中獲得一個可用元組槽其往分區中的地址記為（），放置十這個槽中。一（）（僻），（廿）即為無關是第一級函數。若這個人口未被占用，則填人元組的索引信息，即二元組，其中即腫，仃即（）。若這個入口已被占用，則從索引溢出袁中獲得一十可用人，將的索引信息填人這個人口，并將它鏈至的（。，）入口的索引鏈中。當檢索主鍵為的元組時，（腫）（刑）（邢）即為的分區號；一（）（）（）即為；在分區（，）的索引表中的人口，從這葉入口的索引鏈中找到的索引記錄，得到在分（）巾的地址（，）則（）（僻）（。，）即為元組的地址，其中（唧）

15、為分區（腫）的首地址。鎖管理為了實現發控制，必須提供加鎖機制。漫臂了一個鎖管理線程用以鎖的管理，中只有一種粒度的鎖：記錄鎖從而大大提高了并粒度。采用“優計算機工程與應用的分區號，這里，是第一級函數。從這個分區的所在分區（腫）的索引表中的入口。這里與臣回阿固卜嶇巫圖基于分區的二級索先級夭折”及“死鎖檢測”來防止死鎖：（）若一個事務企圖申請對一個已被低優先級事務加鎖的元組加鎖時，將夭折該低優先級事務；庫操作其設計的主要目的是為了提高宴時數據庫應用系統中使用頻繁的一些操作的性能，即插人（）、查詢（）、修改（）和刪除（）。前，正杠一個實時移動交換系統巾運行。運行結果表明采用的技術是可行的，其數據存取性

16、能與相比具有明顯的優勢。（）若一個事務企圖申請對一個已被高優先級事務加饋的元組加鎖時，將天折自己；（若一個事務譙圈申請對一個已被相同優先級事務加鎖的元組加鎖時，進行“死鎖檢測”，如果將發生死鎖，則夭折自己否則將該事務置入阻塞隊列中。檢測的方法是判斷加人奉事務后，是否存在事務依賴同路。如果存在則將發生死鎖，含則不會每一個分壓設置了一個分區鎖袁（），該鎖表記錄丁該分照中所有的鎖，每一把鎖是一個三元組，多線程系統依賴于操作系統的支持，其性能與線程調度策略發臨界資源的訪問效率關系甯切這些方面還需要進一步的優化。（收稿期：年月）參考文獻，！，越、，其中“標識被加鎖的兀組，它，足元組在分區中的地址，是加鎖者標識，足加鎖時間計數器，標識鎖存在的相對時間，加鎖時置為，還管理過老的鎖，它定期掃描每一張表將鎖的增，若達到了系統預設的一個閾值，則認為該鎖加鎖時間過長，解除它并天折相應事務。，；（：（），曲，一，！：“）：，；（）：結論文章介紹了一個基于多線程體系結構的內存數據庫