一个简单的非锁定读并发映射的算法？

Question

我试图编写一个线程安全的映射表，但在读取时不会发生锁定或阻塞。我的尝试是使用只读映射表，在写入时将其复制出来。思路是get()是无锁的，而put()将当前只读基础映射表复制到一个新的映射表中，执行put操作，并将当前基础映射表与新映射表交换(是的，put()效率低下，因为它复制了整个映射表，但我对我的用例不关心)。

我第一次尝试使用std::atomic<*StringMap>作为只读映射表，但是存在一个巨大的错误，可能是由于我的Java背景。 get()以原子方式获取指向基础映射表的指针，加载它时可能是当前映射表也可能不是（这没问题）。但是put()在将其与新映射表交换后删除基础映射表。如果get()在刚好删除旧映射表时调用旧映射表，那么这显然会崩溃。

我的一个朋友建议使用shared_ptr，但他不确定共享指针操作在内部是否执行任何锁定。尽管文档说它是线程安全的，但也有可能不是。所以我的问题是： 1. 这个算法可行吗？2.共享指针操作是否会进行任何锁定，特别是在访问时？

#include <unordered_map>
#include <atomic>
#include <pthread.h>
#include <memory>

typedef std::unordered_map<std::string, std::string> StringMap;

class NonBlockingReadMap {
private:
    pthread_mutex_t fMutex;    
    std::shared_ptr<StringMap> fspReadMapReference;


public:

    NonBlockingReadMap() {
        fspReadMapReference = std::make_shared<StringMap>();
    }

    ~NonBlockingReadMap() {
        //so, nothing here?
    }

    std::string get(std::string &key) {
        //does this access trigger any locking?
        return fspReadMapReference->at(key);
    }

    void put(std::string &key, std::string &value) {
        pthread_mutex_lock(&fMutex);
        std::shared_ptr<StringMap> spMapCopy = std::make_shared<StringMap>(*fspReadMapReference);
        std::pair<std::string, std::string> kvPair(key, value);
        spMapCopy->insert(kvPair);
        fspReadMapReference.swap(spMapCopy);
        pthread_mutex_unlock(&fMutex);
    }

    void clear() {
        pthread_mutex_lock(&fMutex);
        std::shared_ptr<StringMap> spMapCopy = std::make_shared<StringMap>(*fspReadMapReference);
        fspReadMapReference.swap(spMapCopy);
        spMapCopy->clear();
        pthread_mutex_unlock(&fMutex);
    }

};

- marathon

---

“由于它复制整个映射，所以效率低下，但对于我的用例我不在意”--那么您确定需要分层锁定方案的复杂性吗？ - Brian Cain

@BrianCain - 对于我的使用情况，是的。几个线程将不断地访问get()。在初始启动泡沫之后，put()将不经常发生（间隔数天/数周）。 - marathon

有一个 Java 非阻塞哈希表的 C++ 版本，为什么不先看看它呢？如果他们正确实现了底层 FSM，你甚至可以获得实现的正确性证明。如果没有，至少你有一个经过验证的概念可以开始使用。 - Voo

@Voo - 你有相关链接吗？我谷歌了一下，除了Intel TBB之外，没有看到你所描述的任何东西。似乎很难在没有GC的情况下复制Java的功能。 - marathon

@marathon 看起来这个项目自我几年前看过之后就基本上被关闭了.. 遗憾。应该考虑将其移植到其他平台，因为在C++中有一些Java无法轻松实现的功能（当然不包括JNI），这些功能应该能够帮助解决Java设计中的一些问题.. 缺乏GC确实使得各种高性能并发算法变得有趣，但我对此有一些想法。 - Voo

Answer 1

你的代码在 std::shared_ptr 上存在一个 数据竞争（data race），在 C++ 中带有 数据竞争 的程序行为是未定义的。

问题出在：类 std::shared_ptr 不是线程安全的。但是，对于 std::shared_ptr，有特殊的原子操作可以用来解决这个问题。

你可以在以下网页中找到有关这些原子操作的更多信息：

• http://en.cppreference.com/w/cpp/memory/shared_ptr/atomic

- nosid

---

看起来不错，但是在我的平台上（macosx mavericks和CentOS），std::atomic_is_lock_free(&fspReadMapReference)返回“false”。我没戏了吗？ - marathon

@marathon 假设您的平台上有高效的CAS或ll/sc内置函数（现在几乎每种架构都有），那么您可以自己实现它。C++11提供了atomic_compare_exchange，尽管标准中没有禁止它不是无锁的（但那真的很可怕）。 - Voo

Answer 2

读取器应该执行两个操作：获取和放置。获取总是检索新指针并增加原子计数。放置释放指针并递减。当计数为零时删除映射。 写入器创建一个新映射并对其进行获取。然后在旧映射上执行放置以标记它要删除。

- stark