欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C++编程笔记丨世界上最简单的无锁哈希表

程序员文章站 2022-07-02 17:44:58
无锁哈希表(Lock-Free Hash Table )可以提高多线程下的性能表现,但是因为实现一个无锁哈希表本身的复杂度不小。(ps:真正的复杂在于出错之后的调试,因为多线程下的调试本身就很复杂,引入无锁数据结构之后,传统的看堆栈信息和打印log都基本上没有意义了。堆栈中的数据可能被并发访问破坏, ......

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

据我所知,第一个用于实际开发的无锁哈希表是 dr. cliff click 为java而写。在2007年他发布了这个无锁哈希表的源码并且在google做了关于它g的报告(视频)。我承认,在我第一次看这个报告的时候,我对它的大部分内容都不理解。dr. cliff click是这个领域的先驱。(maged m. michael 在ibm做了大量关于无锁数据结构的研究。这个是2002年的一篇论文,关于哈希表,)

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

约束

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

(1)table 只接受类型为32位整数的key和value

(2)所有key必须非零

(3)所有的value必须非零

(4)table的最大数目固定且必须是2的幂

(5)唯一可用的操作是setitem和getitem

(6)有没有删除操作

当然你掌握了这种算法实现机制之后,可以在此基础上进行扩展,而不受这些限制的约束。(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的安全性。

C++编程笔记丨世界上最简单的无锁哈希表
 

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;

    }

}

这个就是几乎可以精简的最简单的无锁哈希表,这里是它的代码链接:  and 。

一个忠告:与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。

C++编程笔记丨世界上最简单的无锁哈希表
 

代码放在github上,你可以自己编译和执行。

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

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

博主是一个有着7年工作经验的架构师,对于c++,自己有做资料的整合,一个完整学习c语言c++的路线,学习资料和工具。可以进我的q群7418,18652领取,免费送给大家。希望你也能凭自己的努力,成为下一个优秀的程序员!另外博主的微信公众号是:c语言编程学习基地,欢迎关注!