海量<int,int>键值对存储的内存优化与性能提升问询

最近折腾一批海量的(ID1, ID2)→value结构数据，纯二进制未压缩大概2.5GiB，按理说16GiB内存完全能装下，但架不住大量小对象的分配开销，直接爆内存了。下面是我试过的各种方案，以及最终搞定的思路：

初始踩坑：按ID1分组的小对象存储 #

一开始想当然地把相同ID1的数据塞进自定义对象：

class DataStore { 
    int ID1; 
    std::unordered_map<int, int> data; // ID2 -> value 
};

结果加载数百万个这种对象时，不管是new实例化还是直接丢容器里，内存直接炸了——小对象的内存分配 overhead 太恐怖了，完全扛不住。

嵌套哈希表优化：内存降了但仍有瓶颈 #

换成嵌套哈希表之后，内存占用降到了约9.2GiB，我测了几种组合：

• google::sparse_hash_map<int, google::sparse_hash_map<int, int>>
• std::map<std::map<int, int>>
• std::unordered_map<std::unordered_map<int, int>>
  这里必须吹一波google::sparse_hash_map的组合，内存利用率比标准库的哈希表高一大截，是这几个里表现最好的。

那些没用的尝试 #

• 试了std::map<std::pair<int, int>, int>，结果内存和性能双拉胯，直接pass。
• 把(ID1, ID2)合并成long int当键插哈希表，插入速度慢到离谱，估计是合并后的键哈希冲突多或者计算成本太高。
• 想过用内存池分配器优化小对象开销，但没摸清楚怎么适配我的场景，暂时没出成果。
• 测了boost::flat_map，内存效率倒是达标，但插入慢到让人抓狂，不符合我「查询优先但插入不能太差」的要求。

单哈希表存双键：内存优但查询场景不兼容 #

后来试了google::sparse_hash_map<std::pair<unsigned int, unsigned int>, unsigned int, boost::hash<std::pair<unsigned int, unsigned int>>>，内存直接降到6.3GiB，优化后甚至到4.9GiB，内存表现绝了。但问题来了：我需要频繁查询某个特定ID1对应的所有键值对，这个结构要做这种查询只能全量遍历，一次要2秒，完全没法用。

最终解：LevelDB序列化存储 #

最后没办法，转而去用LevelDB存序列化后的数据，没想到效果出奇好——针对特定ID1的查询只需要50ms，比全量遍历快了40倍，完美满足查询优先的需求，插入性能也在可接受范围内。

内容的提问来源于stack exchange，提问作者dvs23