互联网公司常见大内存服务场景（数据量约数十G量级，发布频率为周级、天级、小时级更新），在线服务为了服务稳定性通常加载双版本或多版本数据。暴露的问题包括服务重启、上线、回滚效率低下，故障实例无法快速恢复造成稳定性隐患等。该项目（代号Levin）针对该类问题进行优化，设计一种针对低频更新、静态使用、大规模数据的通用快速加载解决方案。

思考以下问题：

• 服务变更场景（上线/回滚/failover），服务重启无数据更新时能否不再重复加载，而是复用原有数据？

进程重启后堆内存和栈内存数据都会随之消亡，而共享内存的存续不依托于进程的生命周期，可以实现跨进程重用。

• 数据更新场景（新版本发布），从硬盘数据文件到内存数据对象，是否存在更高效的转换方式？

在构建数据对象（通常为C++标准容器）内存布局时，需要大量IO和内存分配系统调用，如果事先离线编译出数据对象layout并计算出所需内存size记录入文件，服务启动时进行一次性共享内存分配和IO读取，可以进一步提高加载效率。

• 确定了使用共享内存和离线编译容器对象内存布局的方案，最关键的问题来了，如何将容器放入共享内存？

最大的障碍是指针和内存不连续性。我们的武器是降维：将容器对象内存布局一维化，对于一维连续顺序存储方式的容器，只需首地址加长度就可以表达、读取和复制整个容器对象；由于同一块共享内存会映射到不同进程的不同虚拟地址，因此实现时使用偏移量代替容器中的指针。

BOOST的interprocess库实现了能被使用在托管内存片段上（例如共享内存）的容器。基线测试发现interprocess容器对比标准容器性能表现不佳：常用容器vector/hashmap查询较标准容器慢10%/30%左右。Levin选择了自定义一套常用的共享内存容器，在数据静态使用方式的前提下做了一系列优化，基线测试表明Levin容器查询性能较标准容器持平略有提升，内存使用效率优势明显（具体数据可参考Benchmark）；并实现了一些interprocess不具备但在实际工程应用时不可或缺的功能，如共享容器内存校验、版本管理等。

Levin支持以下Features：

1、支持常用共享内存容器，包括vector、set、map、hashset、hashmap等；

2、支持使用适配、组合、特化等手段自定义共享内存容器；

3、支持离线数据编译：将原始数据编译为进程可直接读入的共享容器对象内存布局二进制文件；

4、支持在线数据加载：加载二进制数据文件至命名共享内存区域，支持共享容器对象申请、校验、加载、释放；

5、支持共享数据版本管理和在线热切换功能；

标准容器	Levin容器	约束	建议
vector<T>	SharedVector<T>	T为POD类型
set<K, Compare>	SharedSet<K, Compare>	K为POD类型	若无需有序，建议使用unordered_set&SharedHashSet
map<K, V, Compare>	SharedMap<K, V, Compare>	K/V为POD类型	若无需有序，建议使用unordered_map&SharedHashMap
unordered_set<K, Hash, Pred>	SharedHashSet<K, Hash, Pred>	K为POD类型
unordered_map<K, V, Hash, Pred>	SharedHashMap<K, V, Hash>	K/V为POD类型
vector<vector<T> >	SharedNestedVector<T, SizeType>	T为POD类型; SizeType为无符号整型	其他共享容器嵌套方式需定制化实现; 定制SizeType旨在优化内存使用效率
unordered_map<K, vector<V> >	SharedNestedHashMap<K, V>	K/V为POD类型	其他共享容器嵌套方式需定制化实现

请参考Getting Started

环境：Centos release6.7 gcc485 开启02编译优化

Levin vector随机存取性能与std::vector基本持平，均优于boost interprocess vector随机存取性能。

三者实现上数据均为连续顺序存储方式，空间使用效率持平。

Levin vector与boost interprocess vector为了进程共享，需要增加一些头部管理字段，在大数据量使用场景，这些额外空间代价可以忽略。

benchmark(1000w int32)	random get(us)	tranversal(us)	memory(kB)
Levin vector	134278	5453	39064
BOOST interprocess vector	146921	43694	39063
STD vector	135492	5639	39064

Levin hashmap实现为二维数组，开链桶不是链表入口，而是记录哈希到该桶的kv数组。

该实现方式具有更佳的数据局部性，与unordered_map相比Levin hashmap查找和遍历性能略胜一筹。Levin桶实现为数组，较链表节省指针域空间，具有更高的空间使用效率。

与红黑树实现的map相比，Levin hashmap和unordered_map查找时间复杂度低，性能优势明显。而map的空间使用率也较低，原因是红黑树节点包含更多的指针域(left/right/parent)、颜色标记字段等。

benchmark(1000w <int64,int32>)	random find(us)	tranversal(us)	memory(kB)
Levin hashmap	678819	14372	243988
STD unordered_map	953674	42082	452824
STD map	13015819	219984	625000
BOOST interprocess map	17461276	425650	468750

更多Levin容器Benchmark，可自行编译测试：test/*_benchmark.cpp