#设计思路简介
[TOC]
以前看到阿里中间件的比赛, 单机实现百万队列引擎，要求如下:
消息数量在20亿, 大小在58byte左右. 一共有100万个队列。对每个队列都可以执行put & get两种操作。
get可以并发执行,要求能支持任意位置的消息(随机读)
会先执行put操作,然后执行随机读和顺序读。其中随机读会对每个队列执行1到2次读取,顺序读会针对20%的队列全部读完
工作线程数量在10个左右
因为这个时候比赛已经过去很久了，所以先自己想了下，然后也参考了晚上一些成绩较好选手的方案，分析如下:
1 首先内存需要做缓存, 这里的方案是每个队列一个page(4K),写满后刷入磁盘
2 读取的时候如果对于同一个队列的消息能够比较集中,那么读取是有好处的,可以增加缓存命中率
3 实现一个二级缓冲(16M),一级缓冲需要将消息刷入这个二级缓冲, 如果缓冲满了,刷入一个队列, 然后由 单/多线程异步的写磁盘
4 读取缓存的时候, 使用了自己构建的pageCache缓存,写入使用direct io,避免pagecache(降低内存使用)
5 写入的时候,使用一个随机数在3.5k - 4k之间刷入buffer,避免同时进行写入
6 系统上有个 sprintf和fwrite一起使用会导致冲突严重,猜测是fwrite如果没有绑定缓存,会使用和sprintf一样全局默认缓存。所以可以使用fwrite的时候绑定局部缓存或者直接使用write|pwrite.
- 需要一个并发队列从 name -> queue的查找, 首先可以分成4096的segment,每个segment是一个独立的hash
- 最开始使用unordered_map,后来发现性能有瓶颈,查询的时候比较慢, 针对项目的特点进行了手动优化:
> a. 我们只插入不删除, 读写比例很大, 数量大小可以提前确定, 所以可以使用静态分配的内存来实现hash,平均一个slot也就只有 1到2个节点
> b. 使用MurmurHash2进行hash,一级segment和二级hash都使用这个,因为32bit对于百万队列足够了,不需要算两个不同的
> c. 每个segment使用一个spinlock保护,因为冲突的概率很小。注意如果冲突一定次数及时yield线程,否则容易造成性能问题
> d. 先比较hash,然后再比较key
- 每一个page对应一个索引，索引保存在内存里面, 由于一个队列的索引数量大约在30多,直接进行二分查找就挺快了
- 由于知道大约消息的大小,可以估算每一个index大约对应60多个消息,因此可以直接计算出大概的index定位,然后稍微左右遍历一下就找到了
- 每一个索引可以和一个pagecache绑定,如果是最后一个索引,那么当前的page还没有刷入buffer里面,可以直接读取,否则需要单独分配一个page用来从文件里面读出来
- 由于缓存有限,采取循环分配,对单个page加spinlock的方式访问，所以index对应的缓存可能会失效,这个是通过一个version来判断的,如果version不一样,那么说明已经失效了(allocate一次就++)
- index需要维护磁盘文件的编号和offset,这样才能在缓存失效的时候正确进行读取,这个依赖于刷入buffer的时候,就需要提前计算好当前应该写到哪个文件,写到文件的offset开始是多少
##异步线程的设计
1 用锁和条件变量来保护队列,每次直接swap队列到本地变量,然后将整个buffer写入到对应的文件里面 2 文件如果超过8G就换一个新文件(这是为了以后压缩比较方便) 3 即便没有写满，也每s刷新一次buffer,目的是为了不让缓存积累太久,避免一些index到时候从文件里面读取不到 4可以很容易的扩展到多个线程来同时刷新, SSD在大块数据对齐写入的时候并发写性能有所提高,也有利于减少缓存在内存的积累
1 因为不知道线上实际的测评程序, demo程序里面sprintf就花费大量的时间成为瓶颈,所以分成两种测试了下10亿的数据
2 消除sprintf的情况下, 写入100s左右, 如果要sprintf和动态分配,需要370s左右
3 读取的情况都差不多, 顺序读60s, 随机读50s左右
4 当然机器要好很多,所以不能直接和选手成绩比较了
5 难点除了设计以外,比较麻烦的地方还是需要考虑各种加锁和同步的情况,有时候容易出错