C++11无锁序列号发生器安全？

Question

其目标是在现代C++中实现序列号生成器。上下文位于并发环境中。

需求#1类必须是单例(对于所有线程都是通用的)

Requirement2用于数字的类型是64位整数.

需求3调用者可以请求多个号码

Requirement #4这个类将缓存一系列数字，然后才能服务调用。因为它缓存一个序列，所以它还必须存储上限-> --最大数目--才能返回。

Requirement #5最后但并非最不重要的一点是，在启动(构造函数)时，当没有可用的编号( n_requested > n_avalaible )时，单例类必须查询数据库以获得新的序列。这个来自DB的负载更新了seq_n_和max_seq_n_。

其接口的简要草案如下：

class singleton_sequence_manager {

public:

    static singleton_sequence_manager& instance() {
        static singleton_sequence_manager s;
        return s;
    }

    std::vector<int64_t> get_sequence(int64_t n_requested);

private:
    singleton_sequence_manager(); //Constructor
    void get_new_db_sequence(); //Gets a new sequence from DB

    int64_t seq_n_;
    int64_t max_seq_n_;
}

示例只是为了澄清用例。假设在启动时，DB将seq_n_设置为1000，max_seq_n_设置为1050：

get_sequence.(20); //Gets [1000, 1019]
get_sequence.(20); //Gets [1020, 1039]
get_sequence.(5); //Gets [1040, 1044]
get_sequence.(10); //In order to serve this call, a new sequence must be load from DB

显然，使用锁和std::mutex的实现非常简单。

我感兴趣的是使用std：：原子和原子操作实现一个无锁版本。

我的第一次尝试是：

int64_t seq_n_;
int64_t max_seq_n_;

改为：

std::atomic<int64_t> seq_n_;
std::atomic<int64_t> max_seq_n_;

从DB获取一个新序列，只需设置原子变量中的新值：

void singleton_sequence_manager::get_new_db_sequence() {
    //Sync call is made to DB
    //Let's just ignore unhappy paths for simplicity
    seq_n_.store( start_of_seq_got_from_db );
    max_seq_n_.store( end_of_seq_got_from_db );
    //At this point, the class can start returning numbers in [seq_n_ : max_seq_n_]
}

现在使用原子比较和交换技术的get_sequence函数：

std::vector<int64_t> singleton_sequence_manager::get_sequence(int64_t n_requested) {

    bool succeeded{false};
    int64_t current_seq{};
    int64_t next_seq{};

    do {

        current_seq = seq_n_.load();
        do {
            next_seq = current_seq + n_requested + 1;
        }
        while( !seq_n_.compare_exchange_weak( current_seq, next_seq ) );
        //After the CAS, the caller gets the sequence [current_seq:next_seq-1]

        //Check if sequence is in the cached bound.
        if( max_seq_n_.load() > next_seq - 1 )
            succeeded = true;
        else //Needs to load new sequence from DB, and re-calculate again
            get_new_db_sequence();

    }        
    while( !succeeded );

    //Building the response        
    std::vector<int64_t> res{};
    res.resize(n_requested);
    for(int64_t n = current_seq ; n < next_seq ; n++)
        res.push_back(n);

    return res;
}

思想：

• 我真的很关心无锁版本。实现安全吗？如果我们忽略DB加载部分，显然是的。当类必须从DB加载一个新序列时(至少在我的头脑中)出现了这个问题。来自DB的更新安全吗？两个原子仓库？
• 我的第二次尝试是将seq_n_和max_seq_n_组合成一个名为sequence的结构，并使用单个原子变量std：：max_seq_n_，但是编译器失败了。因为结构序列的大小大于64位。
• 如果序列准备就绪，是否可以使用原子标记来保护DB部件:在等待db加载完成和更新两个原子变量时，将标志设置为false。因此，必须更新get_sequence，以等待将标志设置为true。(使用自旋锁?)

Answer 1

您的无锁版本有一个根本缺陷，因为它将两个独立的原子变量视为一个实体。由于对seq_n_和max_seq_n_的写入是单独的语句，因此在执行过程中可以将它们分开，从而使用一个值与另一个语句配对时不正确的值。

例如，一个线程可以通过CAS内部while循环(对于当前缓存序列来说n_requested太大)，然后在检查它是否被缓存之前挂起。第二个线程可以通过它将max_seq_n值更新为更大的值。然后，第一个线程恢复，并通过max_seq_n检查，因为第二个线程更新了该值。它现在使用的是无效序列。

在get_new_db_sequence中，两个store调用之间也可以发生类似的事情。

由于您正在写入两个不同的位置(即使在内存中相邻)，而且它们不能原子地更新(因为128位的合并大小与编译器不支持原子大小)，所以写必须由互斥保护。

自旋锁只应用于非常短的等待，因为它确实消耗CPU周期。一个典型的用法是使用一个短的自旋锁，如果资源仍然不可用，使用一些更昂贵的东西(如互斥锁)来使用CPU时间等待。