世界上最簡單的無鎖哈希表
無鎖哈希表（Lock-Free Hash Table ）可以提高多線程下的性能表現(xiàn)，但是因為實現(xiàn)一個無鎖哈希表本身的復(fù)雜度不小。（ps：真正的復(fù)雜在于出錯之后的調(diào)試，因為多線程下的調(diào)試本身就很復(fù)雜，引入無鎖數(shù)據(jù)結(jié)構(gòu)之后，傳統(tǒng)的看堆棧信息和打印log都基本上沒有意義了。堆棧中的數(shù)據(jù)可能被并發(fā)訪問破壞，而打印log本身可能會改變程序執(zhí)行時對數(shù)據(jù)訪問的時序。一個比較可行的做法是實現(xiàn)一個無鎖版本和一個傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)+鎖的版本，出錯后通過替換來定位是無鎖數(shù)據(jù)結(jié)構(gòu)本身的bug還是其他邏輯的 bug）。所以對一個項目而言，無鎖數(shù)據(jù)結(jié)構(gòu)基本上是一把雙刃劍。
據(jù)我所知，***個用于實際開發(fā)的無鎖哈希表是 Dr. Cliff Click 為Java而寫。在2007年他發(fā)布了這個無鎖哈希表的源碼并且在google做了關(guān)于它的報告（視頻）。我承認，在我***次看這個報告的時候，我對它的大部分內(nèi)容都不理解。Dr. Cliff Click是這個領(lǐng)域的先驅(qū)。(Maged M. Michael 在IBM做了大量關(guān)于無鎖數(shù)據(jù)結(jié)構(gòu)的研究。這個是2002年的一篇論文，關(guān)于哈希表，http://www.research.ibm.com/people/m/michael/spaa-2002.pdf)
很幸運，6年時間足夠我理解Dr. Cliff Click所做的研究。事實上，你不必做一些前沿的探索，去實現(xiàn)一個***的無鎖哈希表。在這里我將分享我實現(xiàn)的這個版本。我相信有使用C++進行多線程開發(fā)經(jīng)驗的程序員，可以通過這篇博客梳理以前的經(jīng)驗，并且完全理解它。
約束
作為一個程序員，平時我們實現(xiàn)一個數(shù)據(jù)結(jié)構(gòu)會本能的盡可能通用。這不是一件壞事，但是當我們把通用當作一個更重要的目標時，它可能會阻礙我們。在這里我走向另一個極端，實現(xiàn)了一個盡可能簡單的，僅用于一些特殊環(huán)境的哈希表，下面是它的設(shè)計約束：
-
table 只接受類型為32位整數(shù)的key和value
-
所有key必須非零
-
所有的value必須非零
-
table的***數(shù)目固定且必須是2的冪
-
唯一可用的操作是SetItem和getItem
-
有沒有刪除操作
當然你掌握了這種算法實現(xiàn)機制之后，可以在此基礎(chǔ)上進行擴展，而不受這些限制的約束。（rehash，刪除和遍歷，這些都會增加復(fù)雜度，而且有引發(fā)新的ABA問題的可能性）。
實現(xiàn)方法
有很多種方法來實現(xiàn)一個哈希表。這里我選擇了用我以前的帖子中描述的ArrayOfItems類做一個簡單的修改，（前置擴展閱讀） A Lock-Free… Linear Search?
這個哈希表被我稱為HashTable1，和ArrayOfItems一樣，它采用了一個巨大的key-value pairs數(shù)組實現(xiàn)。
- struct Entry
- {
- mint_atomic32_t key;
- mint_atomic32_t value;
- };
- Entry *m_entries;
在hashtable1中，僅僅只有數(shù)組本身而沒有使用鏈接來處理碰撞。數(shù)組全部初始化為0,key為0時對應(yīng)的節(jié)點為空。插入時，會通過線性搜索找到一個空節(jié)點。
ArrayOfItems和HashTable1之間唯一的區(qū)別是，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做參數(shù)調(diào)用SetItem或GetItem方法時，它會在相同的index開始做線性搜索，而使用不同的key時，會在不同的 index開始搜索。通過這種方式，可以提高查找到對應(yīng)key所在節(jié)點的速度，并且保證多線程并發(fā)調(diào)用SetItem或GetItem的安全性。
HashTable1采用環(huán)形的搜索，當搜索到尾部時，會從數(shù)組頭部開始繼續(xù)搜索。在數(shù)組滿之前，每次搜索都可以保證返回對應(yīng)key所在的節(jié)點，或者是一個空節(jié)點。這種技巧被稱為open addressing with linear probing,，在我看來這無疑是對lock-free最友好的hash算法，事實上在Dr. Cliff Click為java實現(xiàn)的哈希表中也使用了相同的技巧。
代碼
SetItem的實現(xiàn)。它會掃描整個數(shù)組并且將value保存在與key對應(yīng)的節(jié)點或空節(jié)點。這段代碼與ArrayOfItems:: SetItem幾乎相同，唯一的區(qū)別是計算了hash值并且按位與，保證index在數(shù)組邊界內(nèi)。
- 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的實現(xiàn)也同樣和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出于同樣的原因：對數(shù)組的元素采用原子操作，使用cas操作修改節(jié)點的key值(使用內(nèi)存柵障保證線程安全，事實上就是重新排列了內(nèi)存訪問指令的執(zhí)行次序)。在上一篇中有更詳細的討論。
***，就像在以前的帖子中，我們可以優(yōu)化SetItem，***次判斷是否可以避免使用CAS操作。如下這種優(yōu)化，可以使示例應(yīng)用程序運行快大約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中設(shè)置標記，共享一些數(shù)據(jù)供其他線程訪問時，必須事先插入release fence。同樣訪問數(shù)據(jù)的線程在調(diào)用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的一些測試對比，在上一篇帖子我做個一個類似的測試。它交替執(zhí)行2個測試：一個采用2個線程，每個線程交替插入6000個key不同的item，另一個每個線程交替插入12000個key相同但是value不同的item。
代碼放在GitHub上，你可以自己編譯和執(zhí)行。編譯說明見README.md
在HashTable1沒有滿時—少于80%時—HashTable1表現(xiàn)的很好，我也許應(yīng)該為這個說法做一些基準測試。但是以以往的常規(guī)的哈希表 作為基準，我敢肯定你很難實現(xiàn)出性能更好的無鎖哈希表。這似乎奇怪，HashTable1基于ArrayOfItems，看起來會很低效。當然，任何哈希 表中，總會有發(fā)生碰撞的風(fēng)險，而降階到ArrayOfItems的風(fēng)險并不為0。但是使用一個足夠大的數(shù)組和類似MurmurHash3這樣的hash函 數(shù)，這種情況出現(xiàn)的很少。
在實際的工作中，我已經(jīng)使用了一個和這個類似的hash-table。這是一個游戲開發(fā)的項目，我的工作是解決使用內(nèi)存分配跟蹤工具(memory tracker)之后對一個讀寫鎖激烈的爭用。遷移到無鎖哈希表的過程非常棘手。相對HashTable1需要更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，key和value都是 指針而不是簡單的整數(shù)。因此有必要在哈希表內(nèi)部插入memory ordering。最終在此模式下運行：最壞情況下游戲的幀率提高了4-10 FPS。
原文鏈接：http://preshing.com/20130605/the-worlds-simplest-lock-free-hash-table
