相逢
凌晨三四点，冒着严寒做着核酸
大家心事重重，表情凝重不堪
生活，是黑暗冰冷的荒原
乐观，如满天星河般绚烂
初冬的清晨，黄叶翩翩
快到来吧，那久违的笑脸
快过去吧，这该死的新冠
我吹过你吹过的风，这算不算相拥
我走过你走过的路，这叫不叫相逢
簇拥的人群，错位的时空
共享过的基站，沐浴过的霓虹
800米，或无所事事，或行色匆匆
10分钟，看天高云淡，却暗流涌动
时光流逝，网格纵横
不经意的交叉，在同一片天空
红黄绿码，万人同梦
看不见的坚强，有同一种感动
她叫成都，2500万的并发，心跳怦怦
这是中国，140M个对象，携手同工
疫无反顾，患难与共
天涯咫尺，云上相逢
一衣带水，原始见终
悸动
32岁，码农的倒数第二个本命年，平淡无奇的生活总觉得缺少了点什么，内卷的社会让我感受到些许的折磨；
想要去创业，却害怕家庭承受不住再次失败的挫折，想要生二胎，带娃的压力让我想着还不如好好地活着；所以我只好在生活中寻找一些小感动，去看一些老掉牙的电影，然后把自己感动得稀里哗啦，去翻一些泛黄的信件，在回忆里寻找一丝丝曾经的深情满满；去学习一些冷门的知识，最后把自己搞得晕头转向，去参加一些有意思的比赛，捡起那10年走来，早已被刻在基因里的悸动；
晚风
那是夏末的一个傍晚，我和同事正闲聊着西湖的美好，他们说想去瞧瞧，我便说阿里有免费的机票，他们问是否可靠，我说：阿里挺可靠，不过我只有九成的把握，另外一成层得找我媳妇儿要；
那一天，Ninety Percent战队应运而生，云原生MQ的赛道上，又多了一个艰难却坚强的选手；
人到中年，仍然会做出一些冲动的决定，那种屁股决定脑袋的做法，像极了领导们的睿智和18岁时我朝三暮四的日子；夏季的ADB比赛，已经让我和女儿有些疏远，奖金都给了老婆，仍然没法抹去对我的成见；此次MQ一战，必然是要暗度陈仓，卧薪尝胆，不到关键时刻，不能让家里人知道我又在卖肝；
那个傍晚，心里是无法压抑的冲动，窗外是阵阵飒爽的晚风
开工
你还别说，或许是人类的本性使然，这种背着家人"偷偷干坏事"的感觉还真不错，从上路到上分，一路顺风顺水，乐得合不拢嘴；断断续续花了大概两天的时间，成功地在A榜拿下了first blood；再一次把第一名和最后一名同时纳入囊中；
快男总是不会让大家失望了，800秒的成绩，成为了比赛的base line;
10年的老码农，读懂赛题的那一刻，心里就有了一个大体的方案，第一个版本并没有做太多细节的考虑，目的就是把流程跑通，尽快出分，然后在保证正确性的前提下，逐步去优化细节，避免一开始就过度设计，导致迟迟不能出分，影响士气；
整体架构
赛题赏析
在解决存储类的问题时，往往会在“随机写+顺序读”和“顺序写+随机读”之间做权衡
根据赛题描述，有100 个topic，每个topic有5000个queueId，总的queueId的数量为50w，这使得从queueId的维度上看，消息的写入和读取都是非常的稀疏的，再考虑到有一块巨大的AEP作为缓存，缓解读取的压力，“顺序写+随机读”的方案毫无疑问地就成了天选之子；
由于在测评的过程中，会模拟宕机的情况，这使得pageCache不再是可靠的存储介质，所以在append消息返回之前，对应的消息必须要落到ssd上；
该ssd的iops为21800，最大吞吐为320MiB/s，这意味着，每次刷盘的数据需要大于320MiB/21800≈15k才能将吞吐打满，然而每条消息的大小在100B到17kb之间，平均大小只有8.5k，如果每条消息就进行一次刷盘，整体的吞吐显然会非常的低；
异步聚合
多线程聚合落盘可以有效地解决上述的问题，append时，会将消息放到一个队列当中，然后当前线程进入等待状态；后台有一个异步的线程从队列中获取多条消息，生成一个消息列表，每一个消息列表就是后续刷盘的基本单元；然后将该消息列表再放到另外的队列中，由多个异步的刷盘线程进行刷盘处理；刷盘结束后，再对等待的append线程进行唤醒；
该方案有几个关键点需要进行进一步说明
1、为什么要用队列进行异步聚合，而不直接基于请求线程进行同步聚合，多一层队列存取的逻辑不会带来性能损耗吗？
使用异步聚合的方式可以使得线程状态的控制更加的简单，同时，聚合的线程拥有上帝视角，可以实现更加灵活的聚合策略；举个例子：聚合的时候可以知道有哪些待聚合的数据，可以按照策略挑选一部分数据进行聚合；
至于异步化带来的额外开销，由于是重IO的场景，瓶颈在也妥妥地在IO(且云ssd的IO还有buffer效应)，就算sleep一下也丝毫不影响成绩；
2、为什么要由一个线程进行聚合，然后"又双叒"放到另外的队列里，让多个线程进行刷盘? 而不直接用多个线程进行聚合，然后直接在聚合线程里面落盘？
想象一下，假设现在有32条待聚合的消息，当前的聚合策略要求我们每次聚合10条消息；如果聚合的线程是4个，这可能导致4个聚合线程都拿不满10条消息，使得这32条消息都处于等待写入的状态；如果聚合线程是1个，那么就只会有2条消息处理等待写入的状态；
3、聚合策略是怎么样的？
程序里面有一个聚合控制器，会准实时地统计近期活跃的append线程数，然后基于该活跃线程数、刷盘线程数、每个刷盘线程上批次扣留的消息数(消息扣留策略，后面会细讲)，计算出一个聚合的数量，该数量就是本次需需要聚合的消息数；具体的细节后面会详细讲；
SSD存储
由于涉及到数据恢复的逻辑，所以消息的索引数据也必须进行持久化存储，为了减少刷盘的次数，自然就选择了“索引+消息体”混合存储的方式；
缓存分级
赛题中，缓存介质分为了dram和aep，不同的介质，其读写速度不一样，显然我们希望效益高的存储介质能够被更加频繁地使用，因此我对缓存进行了一个分级，优先使用dram缓存，当dram缓存使用完之后，再使用aep缓存，这样在测评的二阶段，dram缓存就能被不停地复用；Dram的容量虽然只占整体缓存容量的10%，但在测评的第二阶段，却提供了53%的缓存服务；这种分级的概念，在热读权重高的场景效果非常的好；
JVM参数的限制
按照官方的描述，“JVM配置为6G堆内+2G堆外”，且选手不能自定义jvm参数，这就意味着，年轻代和老年代的比例是使用的默认值1:2；当我们想要使用4G的老年代来做缓存时，年轻代就会达到2G，而这2G的内存基本是浪费；
想要浪费少一点，年轻代就必须要小一点，老年代也就必须要小一点；整个jvm的堆内也就小了；
从jvm上压缩出来的这一部分内存显然可以用来作为pageCache，但是由于整个测评过程中，pageCache的竞争非常的激烈，这使得pageCache的命中率会比较低；做了一些尝试，负面优化的效果非常的明显。。。。
一阵折腾后，我又想到了MMAP，本质上他也是一个DirectByteBuffer，如果有办法让某个mmap对应的pageCache尽量不被释放，那这段pageCache的命中率就会非常高了；因此囫囵吞枣地查阅了一些和pageCache回收算法相关的文章，心里便有了一些想法；
我构建了一些MMAP对象，然后在程序初始化的时候，疯狂地对这些MMAP进行读写操作，以使得对应的pageCache拥有很高的权重，从而不容易被淘汰掉；
但是在缓存写入阶段，对这些mmap的写入会仍然不定期地触发刷盘，这将影响到主线程的刷盘效益。那么有没有什么办法可以让它跳过刷盘的逻辑？ 答案是copy on write模式的mmap；该模式下的mmap会在写对应区的数据的时候生成一个副本，从此和存储介质脱节，完美地满足我这个场景的需求；
或许这就是比赛吧，像极了生活的起起落落，总会有一些努力没有收获，也总会有一些意外会带来硕果
消息写入
聚合控制器
每次append方法被调用时，都会记录该线程的最近活跃时间，然后程序会定时对这些信息进行统计，计算出近期内活跃的线程数，以及火雨线程数波动系数，当波动系数较大时，说明活跃线程数出现了较大变化，会加快定时器的频率，以减小聚合参数更新不及时对集合效率的影响；同时降低聚合超时时间，使得聚合线程在大概率凑不齐数据的时候，能够快速的结束等待；
同时在聚合时，还需要考虑刷盘线程扣留的上批次的消息(为了4k对齐，刷盘线程会扣留一部分数据，放到下一次进行刷盘)，假设近期获取的append线程为48个，刷盘线程为4个，那个每次聚合的消息数应该为12个，若某个刷盘线程上批次扣留了3条消息，则本次只需要额外为该刷盘线程聚合9条消息即可；这样在聚合时就不会出现持有了一些消息，然后却进行进行长时间等待的情况；
4K对齐
和IO相关的问题，永远绕不开4K这个话题；以每次刷盘的平均大小为85K为例，通过简单的尾部填充，可以减少2.5G左右的写IO，以及11G的读IO(当未对齐时，下一次写数据，需要先读一个4k，当然由于写是连续的，所以这个读的pageCache命中率基本上为100%)；
填充策略仍然需要额外写入3G左右的空白数据，因此在每次刷盘时，可以只刷4k对齐的部分，然后将未对齐的部分扣留下来，compact到头部，和下一批消息一起刷盘，这部分compcat的数据关联的消息也会被扣留，对应的append线程会在下一次刷盘之后才进行唤醒；
扣留策略解决了额外空白IO的问题，但是扣留过多的线程会导致整体的append并发降低，影响到写入速度；举个例子，在极端情况下，聚合到的一批消息整体大小都没到达4k，那就需要扣留大量的线程；这种情况下直接使用填充策略会是更好的选择；
因此我希望在填充成本和扣留成本之间做平衡；填充成本可以换算成IO耗时，扣留成本可以换算成测评线程的额外耗时(比如测评程序自己的逻辑耗时为10秒，扣留率为10%时，并发减小 10%；会导致测评程序的耗时变成11秒，该推导不完全严密，但有一定的趋向性)；最后一阵折腾，计算出没扣留一个append线程的成本等同于填充161B数据的成本，这样在程序运行时，何时进行填充，何时进行扣留，就能动态地进行控制了；
然后这并没有什么提升，这又和云ssd的buffer效应有关，所以最后我只在极端情况下(一批数据的总大小小于4k)时使用了填充方案，其余情况下全部使用的扣留方案；
索引
消息的索引和缓存的索引都是使用的一个100(topic数量)x5000(queueId数量)的二维数组
消息的索引对象里面包含了本条消息所在的文件下标、数据在文件中的位置、消息大小、以及缓存的位置；
缓存的索引里面包含了一个缓存块的列表，以及一个数值指针；
当往缓存中写入一块数据后，若当前写入位置为P，则会返回N*3K+P作为该块数据的访问标识；其中N为当前列表中的缓存块数量，32K为每个缓存块的大小；
缓存
写入流程
缓存在写入时支持提供了同步模式和异步模式
同步模式虽然会阻塞主线程(云SSD的buffer效应能够包容该阻塞带来的耗时)，但是可以保证消息append后，就算马上进行查询也能命中缓存中的数据；
线上最优成绩是使用的异步模式，因为写缓存和写ssd是并行进行的，写缓存的速度比写ssd块很多，所以基本也不会append后，对应的数据还没来得及写缓存的情况；
为了后续更好地进行缓存的释放，缓存设计中期望消息在缓存中的存储顺序是按offset升序排列的，这就要求我们只能有一个线程进行缓存的写入；
在缓存写入时，会按照topic和queueId找到对应的索引对象，然后看缓存块列表中的最后个缓存块是否能够哦放下当前数据，若放不下，则从缓存池里面获取一个新的缓存块放到列表中，然后进行数据的复制；
在消费阶段，由于是按offset顺序消费，所以当某次缓存读取到第N块数据时，则将第1到第N-1块缓存块全部回收掉；
在使用AEP时，引入了LLPL的库，在这种模式下，AEP的缓存块本质上也是一块直接内存地址，可通过unsafe进行访问；所以我将基于byteArray、DirectByteBuffer、MMAP、AEP的缓存对象，都进行了抽象，使得上层应用时能够更加的友好；
准入策略
由于缓存中放不下所有的数据，所以在查询阶段，必然会有一部分数据需要从ssd进行读取，这部分数据的中大小是一定的；所以我们希望这些从ssd中读取的数据都是尽量大的块，这样可以有效地降低IO的次数；
所以我们需要寻找一个阈值，能够使得当我们只把小于该阈值的消息写缓存时，最后缓存刚好又能写满；
虽然赛题的相关参数是固定的，但是硬编码显然也不是一个很好的方式；
所以我又回忆了一把青春，把该问题转换成了中学时代的三角形面积问题(严格意义上来讲是一个梯形面积问题，但是由于梯形有一个底非常短，所以可以近似地认为是一个三角西面积问题)，在程序启动时，按照实际的参数动态地计算出缓存的准入阈值；
共享缓存
缓存块是以topic+queueId为单位进行隔离的，一阶段结束后，所有queueId的最后一个缓存块大概率都是写不满的，以每个缓存块32k为例，其平均余量为16K，这部分没写满的缓存如果能够充分地利用起来，又会是一个不小的提升；
因此当公共缓存池里面的资源耗尽时，我对所有的queueId的最后一个缓存块进行了遍历，按照余量放入到一个按照余量分级的列表中；同时这些缓存块进行编号，放到一个一维的数组中；
当某个queueId在写入缓存时，如果公共缓冲池里面没有资源，且自己的缓存块列表中的余量也写不下当前数据时，会按照当前数据的大小，按照最小化原则，从共享缓存列表中获取一个共享缓存块，进行数据的写入，同时将写入位置，以及共享缓存块的编号写入到消息的所以中；使用完共享缓存后，还需按照最新的余量情况，将共享缓存块迁移到新的分级列表中；
线上测评的总的queueId为20w左右，这意味着该方案可以积压出20w*16kb=3.2G的内存空间，命中率为50%，也就是该方案会带来1.6G / 320M/s = 5秒的成绩提升；
部分缓存
由于4k机制，在我们进行数据读取时，会存在IO放大的问题，我们不得不因为很小的一部分数据(比如极端情况下的1B)，而去额外读取一个4K区；
因此程序里面引入了部分缓存的机制，若未对齐的区域小于1k时，就将该区域剪切下来放到缓存中，读取的时候，该部分数据就不需要从ssd加载了，有效避免了IO放大的问题；
这种情况下剪切下来放缓存的数据的平均大小为512B，却能减少4K的IO，缓存效益是传统缓存的8倍；
至于为什么阈值设置成1k，是因为缓存分级里面会产生很多1k左右的缓存碎片，刚好在这个场景中可以利用起来；
其他优化点
预写文件
在不纳入测评耗时的构造方法里面，提前生成好文件，并且按照预估的大小顺序写一遍，可以使得后续测评时磁盘的吞吐大幅提升；
底层的原理比较繁琐，网上很容易找到详细的介绍，我这里以一种接地气的方式进行简单地描述；
假设我们在某个盘上创建了一个文件，然后在这个文件里不停地写入1，直到把整块盘都写满；次数磁盘上的物理状态已经全部都是1；然后我们把这个文件删除，删除文件是一瞬间的事，所以文件系统肯定没有对全盘做zero的操作，磁盘上的物理状态仍然全是1；接着我们新建一个空白的文件，假设大小设置成10G，也是一瞬间的事，所以这10G的文件肯定也没有做zero的操作；最后我们去读这个文件里面的数据，会发现读出来全是0，而并非1；
这是因为文件系统的inode里面有记录文件的哪些区域是写过数据的，哪些是没写过的，对于没写过数据的区域，我们进行访问时，会直接返回0；
所以在某个区域首次进行写入时，inode里面会进行update，并且刷盘，这将付出一定的资源代价；
因此，在不纳入测评耗时的构造方法里面预写一遍文件，就成为了一个大大的优化点；
这个优化点实施起来非常的简单，效果非常的明显，基本上可以说是前10的入场券；这说明阿里的比赛不但是在考验选手们的知识深度，在知识广度上也对大家提了一定的要求；
消息顺序整理
4k是一个永远也卷不完的点
4k未对齐时，会有读放大的问题，当我们拿到一个消息列表之后，通过对里面的消息顺序进行适当的调整，总能得到一个排列顺序，使得读放大处于一个最低的水平；
先进行了一个大块置顶的调整，这使得需要从ssd读取的大块数据至少有一端是4k对齐，这大概带来了1s左右的提升；
后来又进行了全局规划，使消息快尽量不要出现脚踏两只船的情况(两端都不对齐一点点)；但这是一个np问题，加上自己算法这块不太行，当时做得比较痛苦，后来突然意识到，缓存的准入阈值在16k左右，所以需要从ssd读取的数据都在16k到17k之间，这些数据若存在两端不对齐的情况，两端溢出的大小一定小于1k，这部分小于1k的数据，能够被部分缓存机制完美解决掉，因此全局规划在赛题的范围内已经没什么意义；
一行排序带来5秒提升
由于使用了队列进行消息的聚合，因此哪些慢一拍的测评线程append的消息总容易出现在队列的尾部，在聚合后，也更容易出现在聚合列表的尾部；在唤醒时也会最后被唤醒，这视乎是一个恶性循环；结合消息的扣留机制，尾部的线程是极容易被扣留了，这就使得有一部分线程经常被扣留，其进度会比其他线程慢不少；这就导致了在收尾阶段，消息的写入并发非常的低，无法打满磁盘IO；
因此我对聚合的消息列表按照其append线程的进度进行了排序，让那些被扣留得越多的线程越排在前面，这样所有的线程最终的进度能够基本保持一致，收尾的时候就不会出现长尾问题；
这一行排序的代码带来了5秒多的提升；
可以看出，这个优化点其实是在为前面的优化点买单，因为如果没有扣留的方案，就不会有长尾的问题；
程序的世界就是这样，对于某一个点，没有绝对的好与坏，今天挖的井有可能会变成明天隐藏的坑；
缓存连续复制与多线程加载
当需要访问的缓存在缓存块上是连续的时候，可以直接以缓存块为单位进行连续复制，以减少copy的次数；
多线程加载这一块儿，开始一直没太注重，总觉得磁盘的吞吐是恒定的，且并发数也足够高，在消息消费的时候再分裂线程进行多线程加载完全是没有意义的；
但通过实践发现使用多线程加载确实能提升成绩；
首先多线程的并发读会带来速度的提升，但是对写会带来负面的影响，并且多线程join也会带来额外的时间开销；所以很难量化出多线程带来的提升到底是怎么样的，也就很难决策出需要开多少个线程进行多线程加载；
最后拍了个脑门，当某次需要加载的消息数量大于10的时候，就是用两个线程进行并行加载；
被抛弃的迁移方案
比赛刚开始的时候，看了官方小哥哥的解析视频，里面有提到数据的迁移，所以流程跑通后，就进行了迁移的尝试；
先是进行了顺序读的迁移尝试，当内存耗尽时(当时还没做缓存的准入策略)，记录次数各个文件的位置，在二阶段开始的时候，从记录的位置开始，把数据顺序读出来，写入到缓存中；这样做的好处是可以大幅减少SSD的随机读，代价是迁移的数据后续被查询到的概率只有50%；最后线上跑了几次，负面优化的效果非常明显。。。
接着进行了随机读的迁移，当某个queueId被读取时，异步把这个queueId下的所有消息随机读出来，迁移到缓存中；但是当时写了一个bug，把迁移的触发机制设置成了某个Q首次访问SSD的时候，因为本来从SSD中读取的数据都非常少，某个Q第一次读SSD大概率就是他最后一次读SSD；所以最后提交了几次，成绩没有任何提升的迹象；
我当时做了一个自我总结，认为由于IO恒定，因此做迁移是不可能对成绩有提升的；
至此，我完美地错过了这个优化点，当然，塞翁失马，焉知非福，如果不是因为错过了这个点，我可能也不会在其他点上做到极致；
云SSD
概念
虽然接触云SSD已经有一定的时间了，也一直在用阿里的云SSD的产品，但是这次比赛加强了我对它的了解；
本质上他是一堆普通的磁盘加上一个增强的文件系统；
这个概念像极了云计算，讲述的都是蚂蚁啃大象的故事；
我的YY
由于自己的圈子不大，云ssd底层的一些细节我没有找到了解的渠道，这里就结合这次比赛的一些领悟，做一些猜想
buffer现象
前面多次提到了云ssd的buffer现象，在每次都force刷盘的情况下，云SSD有如下神奇的现象
1、写入的头几秒速度能到400m/s，然后逐步降低到320m/s
2、写几秒停几秒，在写的那几秒里，速度也能达到400m/s
3、同步写缓存或者直接短暂sleep，不会影响整体的速度
该现象给了程序很大的宽容度，程序里面的一些耗时操作，都会被该buffer现象容忍掉，所以提前对资源进行池化这种常规的优化手段，在该次比赛中基本没什么效果；
对应buffer现象的根本原因，大概有三种可能
1、云ssd中有一块容量较小的高性能存储介质，数据写进该介质后请求就会返回，然后在异步将数据复制到其他盘之后，对该块数据进行删除，该介质的写入速度是能超过320的；但是当该介质被写满后，速度就会受到其他盘的制约，稳定在320M/s；
2、写入数据的时候，数据会先被持久化到一个副本当中，然后请求就会返回，其他副本的同步是异步执行的(从内存到磁盘)；当写入速度过大时，内存中会有很多没来得及异步同步的数据，导致速度受到影响；
3、存储介质中，改变存储状态的物理、化学变化本身存在buffer的现象；
并发读的奥秘
IO固定，并发读为什么能够提升整体的效益？此处做一些猜测
当我们读取一块数据的时候，请求会被路由到一些磁盘上，这些磁盘的写入速度会受到影响，我们假设这些磁盘叫A；
此时若某一个请求需要写一块数据，该写入请求被路由到了A和B上，由于A磁盘写入速度受限，导致B写完后不得不进行等待；
这样对磁盘A的写入带来的负面影响就被放大了，为了10m/s的读取速度，牺牲了20m/s的写入速度，整体吞吐就达不到320了；所以当读取的线程足够大时（极端情况为所有盘都在读数据），该放大现象就会被缓解；
但是在消费的时候开太多的线程本身也是一种消耗，若线程太多，每个线程只读少量的数据，可能倒还会得不偿失；因此集中式地进行数据的多线程迁移便成了一个非常隐秘但又非常有效的优化点；
关于云SSD的这部分猜想，仅仅代表个人观点，不出意外的话，里面会有不少错误的观念，期待有朝一日能通过某些渠道了解到权威的答案；
个人感悟
这次比赛的体验非常好，赛题有挑战、导师们也非常热情；不亏是 比赛圈里面的标杆；然后比赛周期也适中，让我既有时间冲刺，也避免了频繁熬夜导致的家庭矛盾，家里的人是在最后一周看到了天池的页面，才发现我在打比赛；
今年参加了两次阿里云的比赛，都取得了不错的成绩，这再一次证明了我适合做技术，不适合做管理；今年工作的体验很不好，大概也是因为代码写少了吧；
这种被生活和工作夹在中间的感觉很难受，做决策引擎的自己是时候做个决策了，是为了事业再次开启一轮拼搏，还是为了生活找一个轻松的工作；
以为早已看透一切，但终究是遇上了迷茫；以为早已看淡一切，但还是被无奈打湿了眼眶；工作为了什么，生活为了什么，总是让自己陷入这种无聊的漩涡；
很多问题或许不需要答案，一路向前，有人陪伴，上坡下坡，都有快乐。
总结
阿里的比赛从来没让大家失望过，既磨炼了技术、又学得了知识，还能结交到朋友；这类比赛也是了解阿里云产品的一个窗口，很多东西别人宣传得再好，也没有自己体验一次来得实在；通过深度了解后作出的决定，永远比商务沟通带来的结果更加让人信服；云中一哥，技术的楷模！
总之，希望优秀的产品越卖越好，优秀的比赛越办越俏，优秀的企业永远不老！也希望更多的同学能够参与到这样的比赛中来，希望在下次的比赛中，能够遇见缘气满满的你~
