映射隊列（上）

這篇文章主要介紹Mushroom（這是我項目的名稱，一個多線程索引，即將成為分散式索引？）裡面一個非常關鍵的數據結構——映射隊列。

我沒有在開源代碼中見到過類似的隊列，所以也許這可以算是我的原創隊列？

這個隊列最大的特點在於它在不傷害性能的前提下大規模地減少了new和delete，從而保證了Mushroom非常優雅的內存使用。

這個隊列的建議使用環境

• 隊列元素不適合深拷貝（deep copy），不適合深拷貝的可能原因有，元素佔用內存較大，或者元素使用內存不定
• 程序對內存的使用很敏感

為什麼要寫這個隊列？

1. 對程序內存有著非常可怕的控制欲，在任何循環里出現new和delete都很讓我抓狂
2. 傳統的線程安全隊列無法滿足需求

為什麼傳統的線程安全隊列無法滿足需求？

首先Mushroom支持並發（通過隊列來分配任務），而且涉及大量的索引操作，以短時間內對1000萬索引進行插入為例，假設索引是16位元組，索引頁面是4KB，你能想像對16位元組進行1000萬次new和delete，並且同時對4KB進行幾萬次new後內存的布局嗎？可能會變成下面這樣。

這會帶來兩個問題：

1. 內存分布過於零散
2. 很大程度上限制了支持存儲的索引數量

這也正是不定長隊列存在的問題，另外不定長隊列存在的另外一個問題是大量索引的插入會導致隊列佔用非常多的內存，因為執行插入操作的時間遠大於放置任務所需要的時間。（在Mushroom早期版本里我使用過不定長隊列，結果就是100萬索引放入隊列完畢後即使是4線程插入也僅僅完成了不到40萬，也就是說這個隊列里還有60多萬條索引）

那麼循環隊列呢？循環隊列簡直就是個噩夢，因為元素不進行深拷貝，出隊列後索引在被插入的過程中很有可能被後面入隊列的索引給覆蓋掉，這會直接導致程序出錯。

所以我開始想辦法在既保證不進行大量new和delete的情況下保證程序正確運行。一個非常自然的想法是維護一個自己的內存池，每份內存加個標籤表示是否正在被使用。也就是說我們插入索引時首先向內存池申請，尋找到一份空閑的內存，然後將索引拷貝到這份內存，最後放入循環隊列等待調用。

這個方法我嘗試過，但行不通。為什麼，因為每個線程執行任務的花費的時間可能差距很大，這會造成內存池的空洞。為什麼？

因為沒有線程能保證先開始的先結束，尤其是在遇到B link樹頁面分裂的時候，所以我們自己的內存池在使用一段時間後會可能變成下面這個樣子n

也就是說我們每次獲取索引內存時還需要對內存池來一次遍歷，這。。。

為了解決以上的問題，映射隊列橫空出世。

• 什麼是映射隊列？

映射隊列是通過三個指針維護兩個映射數組的循環隊列，它同時起到了線程安全隊列以及內存資源管理器的作用。以下是核心結構：

template<typename Fuck>nclass BoundedMappingQueuen{n private:n vector<Fuck> elements_;n vector<int> avail_;n vector<int> work_; n int front_;n int avail_back_;n int work_back_;n}n

elements_：存放實際隊列元素

avail_：空閑元素的位置，avail_[0]表示第一個空閑元素在elements_中的位置，也就是說，elements_[avail_[0]]才表示空閑元素的具體位置

work_：使用中元素的位置，和avail_相對應

front_：avail_和work_的指針，avail_[front_]表示下一個空閑元素的位置，work_[front_]表示可以被使用的元素的位置

avail_back_：avail_的指針，avail_[avail_back_]表示最後一個空閑元素的位置

work_back_：work_的指針，work_[work_back_]同樣表示可以被使用的元素的位置

• 這個隊列如何工作？

首先，隊列會這樣被初始化。假設隊列有N個元素，則avail_中的元素依次初始化為0，１，……N-1，而work_中的元素都初始化為-1。

當我們需要往隊列中插入某個元素時，我們首先從avail_中獲取元素的實際位置，然後取得實際元素並進行我們需要的操作（初始化、賦值等等），然後我們更新avail_，將avail_[front_]賦值給work_[front_]，之後將avail_[front_]賦值為-1，並且將front_+1。

當我們的線程池中的線程發現work_[work_back_]大於等於0時，則結束等待，獲取實際元素，並且記錄下此時work_[work_back_]的值，同時將work_[work_back_]賦值為-1，並且work_back_+1，然後進行具體工作的執行。

當工作執行完畢後，利用我們之前記錄的work_[work_back_]的值，將其賦值給avail_[avail_back_]，然後avail_back_+1。

至此一次完整的放置任務、執行任務的過程就結束了。

這個隊列成功地解決了所有在上面被描述過的問題：

1. 在初始化完畢後不需要任何new和delete
2. 隊列佔用內存很少
3. 不會像傳統的循環隊列導致程序出錯
4. 不會出現執行任務的線程時間差異而導致的索引內存的空洞
5. 不損失性能

這個隊列確保了Mushroom在我的電腦（4G內存）可以對億級別16位元組關鍵字進行多線程索引。

使用這個隊列後Mushroom的內存布局是這樣的。

下篇文章將會具體介紹映射隊列的4個API。

Github地址在這：UncP/Mushroom，歡迎star。（src/include/bounded_mapping_queue.hpp，是這個文件，代碼只有150行。）

推薦閱讀：