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