根据阿里中间件比赛做的一个项目,单机百万队列.zip

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