引言

這篇博文是我前一篇博文的第二版本，前一篇博文可以在這兒（http://www.codeproject.com/Articles/190504/RaptorDB）找到，我必須寫一篇新的博文，這是因為在這篇博文里，我對最初的設想完全進行重新設計和重新架構，所以它不再是前一篇博文的繼續。在這一版本的博客文章里，我剔除了B+樹和哈希索引，支持了我自己的MGIndex結構，MGIndex結構總的來說很優秀，后面的性能比較的數值可以說明一切。

RaptorDB是什么？

下面是用來描述RaptorDB的所有關鍵詞的簡要說明：

• 嵌入式：你可以像使用任何其他的動態鏈接庫哪樣在應用中使用RaptorDB，而且不需要安裝服務或者運行外部程序。

• NoSQL：使用與應用更加密切相關的，特定的存儲系統替代關系型數據庫的草根運動正在進行中。設計這樣的系統通常都是為了提高性能。

• 持久性：任何更改都會存儲在磁盤上，因此在電力突然中斷或者崩潰的情況下，你從不會丟失任何數據

• 字典：鍵值存儲系統與.NET里的鍵值實現非常相似。

• MurMurHash：由Austin Apple在2008年創建的非加密用的哈希函數(http://en.wikipedia.org/wiki/MurmurHash)

特性

RaptorDB擁有以下特性：

• 非常高的性能(具有代表性的是與RaptorDB v1相比，插入速度是原來的2倍，讀取速度是原來的4倍)

• foot print非常小，只有50kb。

• 沒有任何依賴。

• 支持多線程讀取和寫入。

• 數據分頁從主樹形結構中獨立，這樣可以在需要時從內存中釋放掉，并在請求時被加載。

• 非正常關機后索引文件自動恢復

• string key使用UTF8編碼，在未指定情況下限制長度是60字節(上限255個字符)

• 通過使用theRaptorDBStringclass支持long string Key

• 重復的key通過WAH位圖索引存儲，這樣可以優化存儲并且加快訪問速度

• 兩種操作模式，直接寫入和暫緩寫入(后者更快一些，但代價是在非正常關機時有數據丟失的風險)

• 支持枚舉索引

• 支持枚舉存儲文件

• 可以移除key

為什么換了一種數據結構?

總是存在一些改進的空間，并且和以往一樣我們需要更快的系統，這都迫使我們創建了一個新的方法來完成工作。MGindex也不例外。

當前MGindex以b+樹的結構呈現其中的一個原因是它具有15倍的寫入速度和21倍的讀取速度，同時使那些負責對硬盤友好的主要特性也是b+樹結構。

B+樹存在的問題

理論上來講，B+樹的復雜度是O(N logkN)或者說是以k為底對N求對數的復雜度，例如，現在對哪些k值大于200來說，B+樹應該優于任何二叉樹，這是因為它使用的操作最少。不過，我發現下面幾個問題在阻礙著性能的提高：

• B+樹的頁面通常都是由一系列或者一組子指針來表示的，所以查找并插入一個值是復雜度為O(logk)的操作，這樣的過程實際上需要在一組或者一系列子指針間來回移動，這就耗費了一些時間。

• 分割B+樹的頁面需要修正父節點，而且事實上，在這個期間子節點就鎖定了這棵樹，那么并行更新就會非常非常難于實現，因此就促使大量的研究論文在討論并行更新。

好的索引結構的要求

怎樣才算是一個好的索引結構，下面羅列了我認為一個好的索引結構應該具有的重要特性：

• 能夠實現頁面數據結構：

•   易于裝載，并可保存到磁盤。

•  在內存有限制的情況下保持有空閑內存。

•  優化內存使用，實現按需裝載。

• 可以非常快速的插入和獲取。

• 支持多線程和并發處理。

• 頁面應該連接在一起，這樣你可以很容易地進入下一頁面，從而可實現一定范圍內的查詢。

MGIndex

MGIndex采納了B+樹的最優秀的特性，同時對它們進行修正，剔除了阻礙提高性能的東西。另外，MGIndex的設計非常簡單，如下圖所示：

就像你看到那樣，這樣的頁面列表是一個由頁面的主關鍵字以及與其關聯的起始頁面編號和所屬的頁面數組成的已排序字典。而頁面則是由主關鍵字和記錄編號對組成的字典。

這種格式確定是一個只對關鍵字進行半排序的列表，也就是說頁面內部的數據沒有進行排序，而頁面之間進行排序。因此要對一個關鍵字進行查找僅僅比較頁面列表里的主要關鍵字，找到所需頁面，然后從頁面字典里就可得到這個關鍵字。

MGIndex的復雜度是O(log M)+ O(1),這里M是N/所屬的頁面數[在Globals類里，所屬頁面數等于10000]。這就意味著你用log M的時間在頁面列表里進行二叉樹搜索，用O(1)的時間在頁面內獲取這個值。

RaptorDB啟動的時候就裝載了頁面列表，而且從此以后就一直裝載著，而頁面則根據需要和使用率進行裝載。

頁面分割

如果頁面已經填滿，而且已經達到了PageItemCount所指定的數目，那么MGIndex將對頁面字典里的關鍵字進行排序，然后把數據分為兩個頁面（就像B+樹分割那樣），接著更新頁面列表，添加新的頁面，更改需要更改的主關鍵字。這么做可以保證頁面都進行了排序處理。

令人意外的是，就像你在性能測試里所看到的那樣，處理器結構在這兒起到了重要的作用，因為它與關鍵字的排序時間直接相關，Core iX處理器在這方面似乎表現更加優越。

MGIndex令人關注的其他作用

下面列出了MGIndex的一些令人關注的其他作用:

• 由于頁面數據與頁面列表結構相互分離，所以鎖定的實現就簡單多了，而且在頁面內部是各自鎖定，不是鎖定整個索引，也不像普通樹那么操作。

• 在頁面填滿的時候分割出另一個頁面就非常簡單，而且不像B+樹那樣需要對整個樹進行遍歷，來檢查是否有節點溢出的問題。

• 主頁面列表的更新很少，因此主頁面列表結構的鎖定不會影響性能。

• 上面的這些使得MGIndex成為并發更新的真正優秀的候選者。

沒有采用的方法或者說采用的方法以及使用回原來的方法！

最初我用AATree描述頁面結構，AATree可以在這兒(http://demakov.com/snippets/aatree.html)找到其說明，這是因為它具有易于理解的非常良好、簡單的結構。經過對其內部所采用的（紅黑樹結構的）.net SortedDictionary進行測試和比較之后，發現它有些慢，所以就不再采用它（參見性能比較部分）。

我決定不使用SortedDictionary描述頁面是因為它比普通的Dictionary要慢些，而且要對關鍵字進行存儲，排序并不是必須的，可以通過其他方式實現對關鍵字的排序。你可以在你喜歡的任何時候在代碼中切換為使用SortedDictionary。除了你可以刪除頁面分割里的排序以外，其余的全部代碼都可以照原樣使用。

我還對各種各樣的排序程序進行了測試，比如雙基準快速排序，timsort和插入排序。通過我的測試，我發現所有這些都比我內部采用的.net快速排序要慢。

性能測試

這個版本的測試我整理了一個列表顯示我曾經在上面做測試的機器和結果。

你可以看到在新的Intel Core iX系列處理器上性能有了顯著提高。

對比 B+樹和MGIndex

為了衡量b+樹，紅/黑樹和MGIndex，我整理了如下結果。

時間是秒。

B+Tree : 源于RaptorDB v1的索引代碼。

SortedDictionary：是.net的內部實現，據稱是一個紅/黑樹。

真正的大數據集!

為了把這個引擎放在真正的壓力下，我用龐大的數據集合做了如下測試(時間單位是秒，內存單位是Gb):

這些測試在一臺擁有12Gb內存，10k Raid存儲陣列，運行64位Windows 2008 Server R2的HP ML120G6上進行。出于比較的目的，我也在RaptorDb v1引擎上測試了2億條數據。

我推遲了10億條記錄的get測試因為它需要一個巨大的內存數組來存儲一會查詢會用到的GuidKey，因此在表里標記為NT(not tested)。

有趣的是，讀取性能是相對線性的。

調整索引參數

為了獲得RaptorDB的最佳性能，你可以對與硬件緊密相關的一些參數進行調整。

• PageItemCount: 控制每個頁面的大小

下面是一些我測試的結果：

我選擇10000這個值，因為它在讀寫兩方面都很好。歡迎你對你系統上的這個值進行修改，看看哪個數值更適合你。

性能測試2.3版本

在版本2.3里，單個把內部類轉換為結構的簡單更改就獲得了2倍多的性能提高和至少少使用30%的內存。這幾乎可以保證讓你在任何系統上都可以獲得十幾萬的插入性能。

上面的一些測試運行了三次，這是因為那時計算機正在運行其他東西（不是為了測試而冷啟動機器），因此最初的結果不算。HP G4筆記本電腦的測試結果是在令人驚訝。

我還對上面所列的最后一個服務器重新進行了1億插入測試，下面是測試結果：

正如你在上面的測試中所看到了，（雖然計算機規格與先前進行測試的HP系統不相匹配，但是）插入時間快了4倍，令人不可思議的是內存使用僅僅是前面測試所使用內存的一半。

代碼使用

要創建或者打開數據庫，你可以使用下面代碼：

// 創建一個不允許重復的Guid關鍵字的數據庫
var guiddb = RaptorDB.RaptorDB.Open("c:\\RaptorDbTest\\multithread", false);

// 創建一個允許重復的，長度為100（UTF8）字符的字符串關鍵字的數據庫
var strdb = RaptorDB.RaptorDB.Open("c:\\intdb", 100, true);

要插入或者獲取數據，你可以使用下面代碼：

Guid g = Guid.NewGuid();
guiddb.Set(g, "somevalue");

string outstr="";
if(guiddb.Get(g, out outstr)) 
{
   //成功后的outstr應該是 "somevalue"
}

UnitTests項目里包含了不同用戶使用環境下可以運行的代碼的例子，要看更多的例子的話，你就參考這個項目。

與版本1的不同

下面是RaptorDB版本2與版本1項比較的一系列不同之處：

• 刪除了日志文件，而且不再需要日志文件了，這是因為MGIndex處理索引非常快。

• 用定時器取代了線程。

• 索引通過后臺程序保存到磁盤，這樣做就不會阻塞處理引擎。

• 簡化了混亂不堪的通用代碼，刪除了RDBDataType，因此你可以使用常見的int,long,string和Guid數據類型。

• 增加了RemoveKey

而現有的代碼就像以前一樣，應該采用新的處理引擎編譯。

RaptorDBString和RaptorDBGuid的使用

RaptorDBString是用于長字符串關鍵字的（也就是大于255字符的字符串的），實際上，它用在文件路徑及其他上。你可按照下面的方式使用：

// 大小寫不敏感的長字符串關鍵字 var rap = new RaptorDBString(@"c:\raptordbtest\longstringkey", false);

//對guid關鍵字進行murmurhash  var db = new RaptorDBGuid("c:\\RaptorDbTest\\hashedguid");

RaptorDBGuid是一個特殊的處理引擎，它對輸入的Guid進行MurMur2散列，從而降低內存的使用（16字節的數據只使用4個字節）， 如果你有大量的數據項需要存儲，那么這么做是非常有用的。你可以按照下面方式使用：

// 對guid關鍵字進行murmurhash var db = new RaptorDBGuid("c:\\RaptorDbTest\\hashedguid");

全局性參數

下面的參數在Global.cs文件里，你可以對它們進行修改，它們控制著內部處理引擎的工作方式。

參數	默認值	說明
BitmapOffsetSwitchOverCount	10	切換位置，此時存儲的副本是以字對齊的混合壓縮的位圖存儲的，而不是一系列記錄編號
PageItemCount	10,000	一個頁面所包含的子頁面數
SaveTimerSeconds	60	保存索引的后臺定時器的間隔秒數（例如，每隔60秒把索引保存到磁盤）
DefaultStringKeySize	60	默認的（以UTF8存儲的）字符串關鍵字大小，按字節計算
FlushStorageFileImmetiatley	false	立即存儲到文件里
FreeBitmapMemoryOnSave	false	存儲的時候壓縮并釋放位圖索引使用的內存

RaptorDB接口

Set(T, byte[])	設置關鍵字以及其對應的類型為字節數組的值，返回空
Set(T, string)	設置關鍵字以及其對應的類型為字符串的值，返回空
Get(T, out string)	獲取關鍵字對應的值，并把獲取的值放在輸出參數給定的字符串里，如果可找到關鍵字對應的值，則返回真
Get(T, out byte[])	獲取關鍵字對應的值，并把獲取的值放在輸出參數給定的字節數組里，如果可找到關鍵字對應的值，則返回真
RemoveKey(T)	刪除索引里的對應關鍵字
EnumerateStorageFile()	以IEnumerable< KeyValePair >形式返回主存儲文件里的所有內容
Enumerate(fromkey)	列舉出給定關鍵字的索引
GetDuplicates(T)	以IEnumerable形式返回指定重復的關鍵字在主存儲文件里的一系列記錄編號
FetchRecord(int)	對主存儲文件使用getDuplicates和Enmerate方法，并以byte[]形式返回值
Count(includeDuplicates)	返回數據庫索引項的數目，如果指定計算重復的，那么重復的索引也計算在內。
SaveIndex()	允許立即把索引存儲到磁盤（處理引擎將定時在后臺自動存儲）
Shutdown()	關閉所有文件，停止處理引擎

 

沒有進行清理就直接關閉

如果沒有進行清理就直接關閉RaptorDB，那么RaptorDB就會自動對下面記錄重新構建索引：存儲文件最后一個已經索引的記錄到最后插入的記錄。這個功能還可以讓你刪除mgidx文件，然后重新構建索引。

刪除關鍵字

在RaptorDB版本2里，添加了刪除關鍵字功能，但有以下告警提示：

• 存儲文件里的數據是不能刪除的

• 向存儲文件添加一條特別的刪除記錄，這樣既可以追蹤刪除情況，也可以在需要的時候幫助我們重新構建索引。

• 刪除的是索引里的數據

單元測試

源代碼里包含以下單元測試（所有測試的輸出文件夾是C:\RaptorDbTest）:

• Duplicates_Set_and_Get:這個測試自動生成了1000個Guid的100個復制，然后獲取每個guid的值（它同樣對字對齊形式的位圖子系統進行了測試）

• Enumerate:這個測試自動生成100001個Guid，并列舉出已確定的Guid的索引，然后顯示最終索引數目（每次運行的最終數目會不同）

• Multithread_test:這個測試創建了兩個插入1000000條記錄的線程，以及插入開始5秒后讀取2000000條記錄的第三個線程。

• One_Million_Set_Get：這個測試插入一百萬條記錄，并讀取一百萬條記錄

• One_Million_Set_Shutdown_Get:這個測試與上面的測試完成的動作相同，只不過在讀取記錄前要關閉并重新啟動。

• RaptorDBString_test:這個測試將創建100，00個1kb的字符串關鍵字，然后讀取這些索引。

• Ten_Million_Optimized_GUID:這個測試使用RaptorDBGuid類對一千萬個Guid進行Murmur散列，然后寫入這些數據，接著讀取出來。

• Ten_Million_Set_Get:同一百萬條記錄一樣做插入和讀取這樣的測試，只不過記錄數為一千萬

• Twenty_Million_Optimized_GUID:同一千萬個GUID一樣做相同散列、寫入和讀取的測試，只不過GUID數為兩千萬

• Twenty_Million_Set_Get:同一百萬條記錄一樣做插入和讀取這樣的測試，只不過記錄數為兩千萬

• StringKeyTest:對最大為255長度的常見字符串關鍵字進行測試

• RemoveKeyTest:測試關閉前后是否可以正確地刪除關鍵字。

文件格式

文件格式：*.mgdat

磁盤上按照下面結構存儲數值的：

文件格式：*.mgbmp

磁盤上是按照下面格式存儲位圖索引的：

位圖索引行的長度是可變的，如果新添加的數據可以填充到磁盤上的記錄里，那么就可以再次使用這以位圖行，如果不能填充，那么就需要創建另一條記錄了。正是由于這個原因，我們必須定期對索引進行縮減，刪除前一次更新后不再使用的記錄。

文件格式：*.mgidx

MGIndex索引按照下面的格式保存的，如下圖所示：

文件格式: *.mgbmr,*.mgrec

Rec文件是一系列寫入到磁盤的long型數值，沒有特定的格式。這些數值把記錄編號映射為位圖索引文件內的偏移量和文檔存儲文件內的偏移量。