程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 世界上最簡單的無鎖哈希表

世界上最簡單的無鎖哈希表

編輯：C++入門知識

無鎖哈希表Lock-Free Hash Table ）可以提高多線程下的性能表現，但是因為實現一個無鎖哈希表本身的復雜度不小。ps：真正的復雜在於出錯之後的調試，因為多線程下的調試本身就很復雜，引入無鎖數據結構之後，傳統的看堆棧信息和打印log都基本上沒有意義了。堆棧中的數據可能被並發訪問破壞，而打印log本身可能會改變程序執行時對數據訪問的時序。一個比較可行的做法是實現一個無鎖版本和一個傳統數據結構+鎖的版本，出錯後通過替換來定位是無鎖數據結構本身的bug還是其他邏輯的 bug）。所以對一個項目而言，無鎖數據結構基本上是一把雙刃劍。

據我所知，第一個用於實際開發的無鎖哈希表是 Dr. Cliff Click 為Java而寫。在2007年他發布了這個無鎖哈希表的源碼並且在google做了關於它的報告視頻）。我承認，在我第一次看這個報告的時候，我對它的大部分內容都不理解。Dr. Cliff Click是這個領域的先驅。(Maged M. Michael 在IBM做了大量關於無鎖數據結構的研究。這個是2002年的一篇論文，關於哈希表，http://www.research.ibm.com/people/m/michael/spaa-2002.pdf)

很幸運，6年時間足夠我理解Dr. Cliff Click所做的研究。事實上，你不必做一些前沿的探索，去實現一個完美的無鎖哈希表。在這裡我將分享我實現的這個版本。我相信有使用C++進行多線程開發經驗的程序員，可以通過這篇博客梳理以前的經驗，並且完全理解它。

約束

作為一個程序員，平時我們實現一個數據結構會本能的盡可能通用。這不是一件壞事，但是當我們把通用當作一個更重要的目標時，它可能會阻礙我們。在這裡我走向另一個極端，實現了一個盡可能簡單的，僅用於一些特殊環境的哈希表，下面是它的設計約束：

table 只接受類型為32位整數的key和value
所有key必須非零
所有的value必須非零
table的最大數目固定且必須是2的冪
唯一可用的操作是SetItem和getItem
有沒有刪除操作

當然你掌握了這種算法實現機制之後，可以在此基礎上進行擴展，而不受這些限制的約束。rehash，刪除和遍歷，這些都會增加復雜度，而且有引發新的ABA問題的可能性）。

實現方法

有很多種方法來實現一個哈希表。這裡我選擇了用我以前的帖子中描述的ArrayOfItems類做一個簡單的修改，前置擴展閱讀） A Lock-Free… Linear Search?

這個哈希表被我稱為HashTable1，和ArrayOfItems一樣，它采用了一個巨大的key-value pairs數組實現。

struct Entry  
{  
    mint_atomic32_t key;  
    mint_atomic32_t value;  
};  
Entry *m_entries;

在hashtable1中，僅僅只有數組本身而沒有使用鏈接來處理碰撞。數組全部初始化為0,key為0時對應的節點為空。插入時，會通過線性搜索找到一個空節點。

ArrayOfItems和HashTable1之間唯一的區別是，ArrayOfItems是從0開始做線性搜索，而HashTable1使用MurmurHash3′s integer finalizer算法得到一個hash值，然後以這個hash值為起點開始搜索()

inline static uint32_t integerHash(uint32_t h) 
{ 
    h ^= h >> 16; 
    h *= 0x85ebca6b; 
    h ^= h >> 13; 
    h *= 0xc2b2ae35; 
    h ^= h >> 16; 
    return h; 
}

當我們使用相同的key做參數調用SetItem或GetItem方法時，它會在相同的index開始做線性搜索，而使用不同的key時，會在不同的 index開始搜索。通過這種方式，可以提高查找到對應key所在節點的速度，並且保證多線程並發調用SetItem或GetItem的安全性。

HashTable1采用環形的搜索，當搜索到尾部時，會從數組頭部開始繼續搜索。在數組滿之前，每次搜索都可以保證返回對應key所在的節點，或者是一個空節點。這種技巧被稱為open addressing with linear probing,，在我看來這無疑是對lock-free最友好的hash算法，事實上在Dr. Cliff Click為java實現的哈希表中也使用了相同的技巧。

代碼

SetItem的實現。它會掃描整個數組並且將value保存在與key對應的節點或空節點。這段代碼與ArrayOfItems:: SetItem幾乎相同，唯一的區別是計算了hash值並且按位與，保證index在數組邊界內。

void HashTable1::SetItem(uint32_t key, uint32_t value) 
{ 
    for (uint32_t idx = integerHash(key);; idx++) 
    { 
        idx &= m_arraySize - 1; 
  
        uint32_t prevKey = mint_compare_exchange_strong_32_relaxed(&m_entries[idx].key, 0, key); 
        if ((prevKey == 0) || (prevKey == key)) 
        { 
            mint_store_32_relaxed(&m_entries[idx].value, value); 
            return; 
        } 
    } 
}

GetItem的實現也同樣和ArrayOfItems::GetItem有類似的改變。

uint32_t HashTable1::GetItem(uint32_t key) 
{ 
    for (uint32_t idx = integerHash(key);; idx++) 
    { 
        idx &= m_arraySize - 1; 
  
        uint32_t probedKey = mint_load_32_relaxed(&m_entries[idx].key); 
        if (probedKey == key) 
            return mint_load_32_relaxed(&m_entries[idx].value); 
        if (probedKey == 0) 
            return 0;          
    } 
}

上述功能都是線程安全的，無鎖的ArrayOfItems出於同樣的原因：對數組的元素采用原子操作，使用cas操作修改節點的key值(使用內存柵障保證線程安全，事實上就是重新排列了內存訪問指令的執行次序)。在上一篇中有更詳細的討論。

最後，就像在以前的帖子中，我們可以優化SetItem，第一次判斷是否可以避免使用CAS操作。如下這種優化，可以使示例應用程序運行快大約20％。

void HashTable1::SetItem(uint32_t key, uint32_t value) 
{ 
    for (uint32_t idx = integerHash(key);; idx++) 
    { 
        idx &= m_arraySize - 1; 
  
        // Load the key that was there. 
        uint32_t probedKey = mint_load_32_relaxed(&m_entries[idx].key); 
        if (probedKey != key) 
        { 
            // The entry was either free, or contains another key. 
            if (probedKey != 0) 
                continue;           // Usually, it contains another key. Keep probing. 
                  
            // The entry was free. Now let's try to take it using a CAS. 
            uint32_t prevKey = mint_compare_exchange_strong_32_relaxed(&m_entries[idx].key, 0, key); 
            if ((prevKey != 0) && (prevKey != key)) 
                continue;       // Another thread just stole it from underneath us. 
  
            // Either we just added the key, or another thread did. 
        } 
          
        // Store the value in this array entry. 
        mint_store_32_relaxed(&m_entries[idx].value, value); 
        return; 
    } 
}

這個就是幾乎可以精簡的最簡單的無鎖哈希表，這裡是它的代碼鏈接: source and header。

一個忠告：與ArrayOfItems一樣，HashTable1上的所有操作都采用了relaxed memory ordering做限制。因此，當在HashTable1中設置標記，共享一些數據供其他線程訪問時，必須事先插入release fence。同樣訪問數據的線程在調用GetItem前需要acquire fence。

// Shared variables 
char message[256]; 
HashTable1 collection; 
  
void PublishMessage() 
{ 
    // Write to shared memory non-atomically. 
    strcpy(message, "I pity the fool!"); 
      
    // Release fence: The only way to safely pass non-atomic data between threads using Mintomic. 
    mint_thread_fence_release(); 
      
    // Set a flag to indicate to other threads that the message is ready. 
    collection.SetItem(SHARED_FLAG_KEY, 1) 
}

簡單樣例

對HashTable1的一些測試對比，在上一篇帖子我做個一個類似的測試。它交替執行2個測試：一個采用2個線程，每個線程交替插入6000個key不同的item，另一個每個線程交替插入12000個key相同但是value不同的item。

代碼放在GitHub上，你可以自己編譯和執行。編譯說明見README.md

在HashTable1沒有滿時—少於80%時—HashTable1表現的很好，我也許應該為這個說法做一些基准測試。但是以以往的常規的哈希表作為基准，我敢肯定你很難實現出性能更好的無鎖哈希表。這似乎奇怪，HashTable1基於ArrayOfItems，看起來會很低效。當然，任何哈希表中，總會有發生碰撞的風險，而降階到ArrayOfItems的風險並不為0。但是使用一個足夠大的數組和類似MurmurHash3這樣的hash函數，這種情況出現的很少。

在實際的工作中，我已經使用了一個和這個類似的hash-table。這是一個游戲開發的項目，我的工作是解決使用內存分配跟蹤工具(memory tracker)之後對一個讀寫鎖激烈的爭用。遷移到無鎖哈希表的過程非常棘手。相對HashTable1需要更復雜的數據結構，key和value都是指針而不是簡單的整數。因此有必要在哈希表內部插入memory ordering。最終在此模式下運行：最壞情況下游戲的幀率提高了4-10 FPS。

譯文鏈接：http://blog.jobbole.com/39186/