[翻译]最简单的无锁hash table

标签: 翻译 hash table | 发表时间:2013-06-07 16:02 | 作者:芊芊水
出处:http://www.cnblogs.com/

原文链接: http://preshing.com/20130605/the-worlds-simplest-lock-free-hash-table


无锁hash table可以提高多线程下的性能表现,但是因为实现一个无锁hash table本身的复杂度不小(ps:真正的复杂在于出错之后的调试,因为多线程下的调试本身就很复杂,引入无锁数据结构之后,传统的看堆栈信息和打印log都基本上没有意义了(堆栈中的数据可能被并发访问破坏,而打印log本身可能会改变程序执行时对数据访问的时序)。一个比较可行的做法是实现一个无锁版本和一个传统数据结构+锁的版本,出错后通过替换来定位是无锁数据结构本身的bug还是其他逻辑的bug)。so,对一个项目而言,无锁数据结构基本上是一把双刃剑。


据我所知,第一个用于实际开发的lock-free hash table是 Dr. Cliff Click为java而写。在2007年他发布了这个lock-free hash table的源码并且在google做了关于它的报告。我承认,在我第一次看这个报告的时候,我对它的大部分内容都不理解。Dr. Cliff Click是这个领域的先驱。( Maged M. Michael在IBM做了大量关于无锁数据结构的研究。这个是2002年的一篇论文,关于hash table, http://www.research.ibm.com/people/m/michael/spaa-2002.pdf)


    


 


很幸运,6年的时间足够我理解Dr. Cliff Click所做的研究。事实上,你不必做一些前沿的探索,去实现一个完美的lock-free hash table。在这里我将分享我实现的这个版本。我相信有使用c++进行多线程开发经验的程序员,可以通过这篇博客梳理以前的经验,并且完全理解它。


Limitations


作为一个程序员,平时我们实现一个数据结构会本能的尽可能通用。这不是一件坏事,但是当我们把通用当作一个更重要的目标时,它可能会阻碍我们。在这里我走向另一个极端,实现了一个尽可能简单的,仅用于一些特殊环境的hash table,下面是它的设计约束:


table 只接受类型为32位整数的key和value
所有key必须非零
所有的value必须非零
table的最大数目固定且必须是2的幂
唯一可用的操作是SetItem和getItem
有没有删除操作


当然你掌握了这种算法实现机制之后,可以在此基础上进行扩展,而不受这些限制的约束。(rehash,删除和遍历,这些都会增加复杂度,而且有引发新的ABA问题的可能性)


The Approach


有很多种方法来实现一个hash table。这里我选择了用我以前的帖子中描述的ArrayOfItems类做一个简单的修改,(前置扩展阅读)  A Lock-Free… Linear Search?


这个hash table被我称为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实现的hash table中也使用了相同的技巧。


The Code


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;
}
}


这个就是几乎可以精简的最简单的lock-free hash table,这里是它的代码链接:  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)
}


Sample Application


对HashTable1的一些测试对比,在上一篇帖子我做个一个类似的测试。它交替执行2个测试:一个采用2个线程,每个线程交替插入6000个key不同的item,另一个每个线程交替插入12000个key相同但是value不同的item。



 


代码放在github上,你可以自己编译和执行。编译说明见 README.md



 


在HashTable1没有满时—少于80%时—HashTable1表现的很好,我也许应该为这个说法做一些基准测试。但是以以往的常规的hash table作为基准,我敢肯定你很难实现出性能更好的lock-free hash table。这似乎奇怪,HashTable1基于ArrayOfItems,看起来会很低效。当然,任何哈希表中,总会有发生碰撞的风险,而降阶到ArrayOfItems的风险并不为0。但是使用一个足够大的数组和类似MurmurHash3这样的hash函数,这种情况出现的很少。


我已经使用了一个和这个类似的hash-table在实际的工作中。这是一个游戏开发的项目,我的工作是解决使用内存分配跟踪工具(memory tracker)之后对一个读写锁激烈的争用。迁移到lock-free hash table的过程非常棘手。相对HashTable1需要更复杂的数据结构,key和value都是指针而不是简单的整数。因此有必要在hash table内部插入memory ordering。最终在此模式下运行:最坏情况下游戏的帧率提高了4-10 FPS。

本文链接

相关 [翻译 hash table] 推荐:

[翻译]最简单的无锁hash table

- - 博客园_首页
原文链接: http://preshing.com/20130605/the-worlds-simplest-lock-free-hash-table. 无锁hash table可以提高多线程下的性能表现,但是因为实现一个无锁hash table本身的复杂度不小(ps:真正的复杂在于出错之后的调试,因为多线程下的调试本身就很复杂,引入无锁数据结构之后,传统的看堆栈信息和打印log都基本上没有意义了(堆栈中的数据可能被并发访问破坏,而打印log本身可能会改变程序执行时对数据访问的时序).

一致性hash

- - 互联网 - ITeye博客
一致性hash算法 - consistent hashing. 分类:  算法艺术2010-02-02 09:19 69836人阅读  评论(97)  收藏  举报. 算法 cache object 服务器 存储 c. 一致性 hash 算法( consistent hashing ).

Table冻结表头

- - CSDN博客Web前端推荐文章
序号. 内容. 序号. 内容. 作者:zyuc_wangxw 发表于2013-8-20 17:32:14 原文链接. 阅读:36 评论:0 查看评论.

Hash Collision DoS 问题

- mazhechao - 酷壳 - CoolShell.cn
最近,除了国内明文密码的安全事件,还有一个事是比较大的,那就是 Hash Collision DoS (Hash碰撞的拒绝式服务攻击),有恶意的人会通过这个安全弱点会让你的服务器运行巨慢无比. 这个安全弱点利用了各语言的Hash算法的“非随机性”可以制造出N多的value不一样,但是key一样数据,然后让你的Hash表成为一张单向链表,而导致你的整个网站或是程序的运行性能以级数下降(可以很轻松的让你的CPU升到100%).

局部敏感Hash

- - xiaobaoqiu Blog
之前在项目中做数据聚合去重的逻辑的时候简单看过局部敏感Hash(Locality Sensitive Hashing,简称LSH)这个东东. LSH可以理解为一种衡量文本相似度的算法,特点是散列前的相似点经过哈希之后,也能够在一定程度上相似,并且具有一定的概率保证. 其有坚实的理论依据(98年左右理论就提出来了,99年有第一版实现)并且在高维数据空间中表现优异.

花瓶茶几:Flo Table

- 阳阳 - 爱…稀奇~{新鲜:科技:创意:有趣}
没看过花瓶茶几(Flo Table),你就不知道粗腿原来也能如此优雅:把茶几的一条腿变成了玻璃花瓶,木材的实成与透明玻璃的轻盈,就如此完美地结合在了一起~于是,尽管随手插点桃红柳绿在花瓶中吧,任何一点属于自然的色彩,都能将这个家点缀得充满生气~. 亲爱的,这些东西也会对你胃口:. Felt Stool Bookshelf Table:凳子、书架和茶几.

Hash算法的使用

- khsing - Glider's home
在对语料文本进行2,3元切分时,需要借助hash表来获得切分内容在内存中的位置,以便能够记录语料库中出现的次数. 以前知道有很多hash算法,但没认真研究过,今天才知道hash算法差距还是很明显的. 首先我选择的是暴雪在魔兽里的hash算法,这个算法很高级,是time33类型的一个变种(有关time33的介绍,可以参考:http://www.cnblogs.com/napoleon_liu/articles/1911571.html),而且很巧妙的借助3次hash避免字符串比较这种费时的操作,并且不用链表来存储冲突,3次hash冲突值能相等的可能行只有1/10的23次方,应该说不可能冲突了.

Min-Hash和推荐系统

- - xlvector - Recommender System
前几年看Google News Recommendation的那篇Paper,对里面提到的MinHash的算法基本没有注意,因为之前的习惯都是只注意论文的模型那块,至于怎么优化模型一般都只是扫一眼. 不过最近看了大量的Google Paper,发现Google在实现一个算法方面确实有很多独到之处. 其实,Min-Hash是LSH(Locality Sensitive Hash)的一种,我之前对LSH的了解仅仅限于知道它能把两个相似的东西Hash成两个汉明距离接近的2进制数.

一致性HASH算法

- - 企业架构 - ITeye博客
一致性 hash 算法( consistent hashing ). consistent hashing 算法早在 1997 年就在论文 . Consistent hashing and random trees 中被提出,目前在cache 系统中应用越来越广泛;. 比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ;.

MySQL Temporary Table相关问题的探究

- comain - 淘宝核心系统团队博客
让我们先来观察几条非常简单的MySQL语句:. 这是丁奇提出的引导性的问题,几条语句看似简单,不过接下来我们提出的一连串问题与进. 看到以上语句,你很容易会产生类似于以下的疑问:. 上述语句在一个session中先后创建了两个名为’tmp’的table,只不过一个是temporary. table,一个是normal table.