分片：简单粗暴细化锁的粒度的通用方法
引子：Concurrent Hashmap
假设我们需要一个支持并发的 Hashmap。当然，已经有很多的库实现了这个数据结构，但是这里我们假设我们需要自己编写一个。为了简单起见，我们只支持三种操作：get, put 和 remove。
最朴素的方法
我们知道 std::unordered_map 是个 Hashmap，但是并不是线程安全的。所以说最简单朴素的方法就是用一个大大的锁锁住它。
class KVBigLock {
std::mutex m_mutex;
std::unordered_map<std::string, int> m_map;
public:
void put(const std::string &key, int value) {
std::lock_guard lock(m_mutex);
m_map.emplace(key, value);
}
std::optional<int> get(const std::string &key) {
std::lock_guard lock(m_mutex);
auto it = m_map.find(key);
if (it != m_map.end())
return it->second;
return {};
}
bool remove(const std::string &key) {
std::lock_guard lock(m_mutex);
auto n = m_map.erase(key);
return n;
}
};
这是一个可行的答案，它能正常运行，不会出错。然而这样会运行得很慢，因为所有的线程都要等待获得这个大锁。好，问题很明显了，锁的粒度太大。我们喜欢细粒度的锁。
粒度“最细”的锁
我们可以考虑在每一个元素上面都加一个锁，也就是说把 std::string 映射到 std::pair<std::mutex, int>。这样一来锁的粒度总足够小了吧？可惜这连一个正确的答案都算不上。
考虑同时获取和删除同一个键。为了防止其他线程读取这个元素，remove 函数自始至终都需要拿着这个元素的锁。然而，销毁一个锁上了的锁是一种未定义行为。
The behavior of a program is undefined if a mutex is destroyed while still owned by any threads.
即使销毁这个锁上的锁没有造成什么不良的影响，这依然挡不住另外一个线程获取 std::pair 里面的值，然而这个值已经被释放掉了。
此外，再考虑同时插入和删除一个键。两个线程会并发地修改 std::unordered_map 里面的数据结构，并且没有受到任何所的保护。
读写锁
显然我们需要保护的是 std::unordered_map 的数据结构本身，而不是容器保存的元素。我们可以用读写锁来提升 get 的性能，假设 std::unordered_map::get 不会修改 std::unordered_map 的数据结构本身，是线程安全的，那么多个线程就可以同时读取。
class KVSharedLock {
std::shared_mutex m_mutex;
std::unordered_map<std::string, int> m_map;
public:
void put(const std::string &key, int value) {
std::lock_guard lock(m_mutex);
m_map.emplace(key, value);
}
std::optional<int> get(const std::string &key) {
std::shared_lock lock(m_mutex);
auto it = m_map.find(key);
if (it != m_map.end())
return it->second;
return {};
}
bool remove(const std::string &key) {
std::lock_guard lock(m_mutex);
auto n = m_map.erase(key);
return n;
}
};
实际上这会跑得更快吗？如果读取操作占了大多数，那么应该会快一些。如果不是的话，甚至可能会跑的更慢，因为读写锁要比普通的锁更复杂。我们可以把读写锁想象成一个普通的锁加上一个 Conditional Variable。
分片
注意到不同的元素之间没有逻辑的联系，我们可以根据键把 Hashmap 分成若干个片，这样也不会影响到正确性。只要访问分片的分布足够均匀、分片的数量足够多，那么两个线程等待同一个锁的概率就会足够小。
class KVSharded {
const size_t m_mask;
std::vector<KVBigLock> m_shards;
KVBigLock& get_shard(const std::string &key) {
std::hash<std::string> hash_fn;
auto h = hash_fn(key);
return m_shards[h & m_mask];
}
public:
KVSharded(size_t num_shard): m_mask(num_shard-1), m_shards(num_shard) {
if ((num_shard & m_mask) != 0)
throw std::runtime_error("num_shard must be a power of two");
}
void put(const std::string &key, int value) {
get_shard(key).put(key, value);
}
std::optional<int> get(const std::string &key) {
return get_shard(key).get(key);
}
bool remove(const std::string &key) {
return get_shard(key).remove(key);
}
};
这个实现非常的简单。首先根据键来计算哈希值，再对哈希值取模来得到分片的编号。只要哈希函数的分布是均匀的，得到的分片编号也是均匀的。
Benchmark
我跑了个 Benchmark。get, put 和 remove 三种操作的数量比约是 1:1:1。总共有1000000个字符串键，10000000个操作。并发的线程数是8个，正好是CPU核数。每个测试重复运行16次。另外，作为比较，我还测试了无锁 Hashmap 的一个实现 libcuckoo，以及 Intel TBB。Benchmark 程序可以在这里看到 https://gist.github.com/abcdabcd987/53b7aa6fdb8f7dbe46798fa6df2f5871
从图中我们可以看到，分成32片的版本比大锁的版本快了80%。读写锁的版本甚至比大锁还要慢，这是因为 get 操作只占了三分之一而读写锁的额外开销又太大了。Intel TBB 不知为何跑得异常地慢，我甚至怀疑我是不是使用方法不正确。另外，分片版本比无锁数据结构还要快50%。
我觉得这个结果非常好，因为我们不费吹灰之力就达到了最好的性能。
分片数量
我还跑了一个关于分片数量的 Benchmark。
一开始，随着分片数量的增加，性能显著增加，之后在128分片的时候开始收敛。128分片并不是很多，所以额外的空间开销其实很小。
能不能从理论上计算出来需要多少分片呢？我不知道，我觉得这是一件很难的事情，跟具体的负载有关。或许用具体的负载进行模拟才是最简单的方法吧。
另外注意到在我们的 Hashmap 例子里面，除了微小的空间开销以外就没有别的额外开销了。在别的应用里面，可能需要考虑更多的因素。比方说如果固定了 Buffer Pool 的内存大小，随着分片的数量增加，每个分片的内存大小就减小了，这样可能会导致换页更加频繁地发生。
又通用又简单粗暴
我觉得这个分片的技巧很棒，因为它非常的通用，而且简单粗暴。前面的例子中我们已经知道它用起来非常简单：
- 写一个朴素的大锁的版本
- 根据键分成若干个分片即可
除了前面的 Hashmap，这个分片的技巧还可以用在很多别的地方。
比方说，现在我手头上在写的这个数据库原先是没有 Buffer Pool 的。原先换页算法是和具体的数据结构耦合在一起的。当时我想要重构，用一个 Buffer Pool 来管理所有换页的事情。当我写完了之后，在单元测试上比原先快了20%，并且整个代码看起来非常地优雅。然而当我运行并发测试的时候，我发现它竟然比原先慢了10倍。
非常感谢知乎上的这个答案让我知道了分片这个技巧，用上这个技巧之后性能立马提升了。而且我发现 MySQL 也用了这个技巧。
当然，你总是可以尝试去设计一些非常厉害的无锁数据结构，但是要把它调对、证明它是对的会非常花时间和精力。而且很多时候你需要为某一个特定的实现来专门设计一些无锁数据结构。比方说，换页算法有很多。现在你要保护的不仅仅是一个 Hashmap，还有换页算法所需要的那些数据结构。如果用锁的话，你可以很容易地实现多个不同的换页算法，然后选择使用哪一个，这可能只需要从一个派生类对象换成另一个派生类对象就行了。Hashmap 和换页算法此时是解耦的。然而如果使用无锁数据结构的话，可能这两者就不得不耦合在一起了。我对无锁数据结构不是很了解，如果我说得不对的话欢迎指出来。