第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

初赛部分

第一节    赛题重述及理解

    题目主要是实现一个进程内消息引擎，程序主要分为两个阶段：第一阶段需要将输入的消息序列化，以topic和queue进行分类后存储到磁盘上；第二阶段需要将对应的topic和queue的消息从磁盘上以正确的顺序读出。

赛题考察点如下：

    l  高效序列化反序列化算法

    l  紧实的数据存储结构设计

    l  并发缓存结构设计

    l  高效IO策略

    l  pagecache等系统机制理解利用

我们针对赛题考察点总结的思路主要如下：

    l  基于预分配缓存空间的unsafe序列化/反序列化方法

    l  基于结尾标志的流化数据紧实存储结构

    l  基于内存池的内存复用异步磁盘写入方法

    l  离散写入顺序读取的pagecache利用策略

    l  基于块数据预读的连续解析策略

第二节    总体设计

    经过预热赛的测试分析表明，程序的主要瓶颈集中在IO上，故最大化利用pagecache便成了提升程序速度的主要优化方向。初赛的数据在经过合理化设计存储结构后，数据量在3.4G左右，略大于最大可利用的pagecache空间，故如果使用顺序写入顺序读取的策略，pagecache的淘汰机制会导致cache数据完全被丢弃，故最后我们使用单个文件存储一个topic和queue的存储方案。

    这种存储方案在读取时是完整的读完一个topic或queue后再读取下一个文件，由于push线程的随机push策略，最终实现了离散写入，连续读出的整体程序逻辑，最大化了cache利用。最后通过设计第一阶段的写入缓冲，提升写入性能，即可达到整体的性能最优。

第三节    数据存储结构设计

    消息序列化后占用空间的大小决定了pagecache的利用率，故本程序使用自己实现的序列化算法提升运算速度的同时，减少不必要的内存分配，同时最小化序列化后占用的空间。经过研究发现，消息主要由动态的kv数据和一段二进制数据构成。

    具体的存储结构如下：kv集合由1字节prefix作为kv数据类型和结束标志，字符串数据，value数据的元组组成。二进制数据使用4字节长度和二进制数据直接存储。

第四节    写入缓冲设计

    程序的写入缓冲核心代码如图1-1所示，在调用线程的内存上先完成消息的序列化，在同步状态下仅完成私有缓冲到bucket缓冲的拷贝，将写满的bucket缓冲替换出来，在同步之外调用异步写入。这样的设计减少了互斥态的时间，同时每个bucket有独立的锁，基本上不会出现竞争的情况，同时在没有引入单独的写入线程的情况下完成了缓冲满的写入操作，减少了线程切换和额外线程的overhead。异步写入机制能够充分利用操作系统在写入磁盘时的调度优化，IO队列中的写入请求能在总体时间最短的情况下被完成。

图1-1 写入缓冲核心代码

图1-2 缓冲内存复用

    图1-2显示的是缓冲内存复用的代码，所有bucket共享一套内存池，这样保证总占用内存极少的情况下，又能自动提升各个bucket的额外缓冲可用性，实现资源共享，负载均衡。

第五节    预读策略设计

    为了保证读取的连续性，同时保证写入针对读取的相对离散性，增大pagecache利用率，读取线程完全读取完成一个topic或queue后才会切换到下一个文件读取。核心代码如图1-3所示。

图1-3 读取核心代码

    读取直接使用同步IO，因为始终需要等待IO完成才能处理，而且存在pagecache的同步IO的相对于异步IO的overhead少，第一次读取4MB，解码超过2MB界限后，将后2MB移动到前2MB上同时读取后2MB数据，这样能够保证解码的连贯性，不存在分块加载造成的割裂。单文件处理的策略也有利于操作系统对文件读取的加速。

第六节    创新点及工程价值

本程序的创新点及工程价值主要在于：

1、设计了一套基于unsafe的序列化/反序列化算法，能够工作于一段连续的内存上，通过指定index后，能以流的方式连续写入/读取，使用CPU的大小端设置，最大化编码速度，同时不产生任何中间对象，效率比其他序列化方式都高，适用于工程上固定结构数据的序列化/反序列化。

2、设计了一种Map数据存储的方法，通过开头的1字节标志位能够判断数据类型和结尾，能够存储任意长度的Map数据，节省了存储Map大小的额外开销。

3、设计了一套基于共享内存池的缓存写入策略，通过topic和queue细化锁的范围，减小锁占用的时间，减少了竞争，提升了系统整体的吞吐量。同时共享的内存池在总体占用内存较小的情况下（push程序堆内内存的使用只有180MB），平衡了各个bucket直接的负载，减少了程序等待IO的时间。这种缓冲内存池的设计非常适合工程上多文件写入的IO优化。

4、利用了push消息时的随机性，将写入的数据相对于读取顺序离散化，避开了pagecache先入先出的特性，最大化了pagecache利用，即使存储数据大于剩余的cache空间，也能以很高的概率命中cache。这相对于传统的连续写入和连续读取，提出了一种利用pagecache的新思路。

5、pull线程预读数据，以块为单位预读，同时使用整体块滑动方式，有效去除了反序列化时边界判断，保证解码连贯性，提升了读取的性能。

第七节    初赛总结

    初赛的问题处理流程非常简单，用最简单最朴素的算法就能完成题目提出的任务，但是想要提升程序的性能需要对操作系统的各种机制有完整的了解，同时需要掌握高性能程序的设计技巧，在性能日志的帮助下找到性能瓶颈，并提出解决方案。利用现有的数据信息，作出针对性的优化也是必不可少的。

复赛部分

第一节    赛题重述及理解

    题目主要解决的是数据同步领域范畴：实时增量同步，主要的技术挑战为模拟数据库的主备复制，提供"高效"的实时同步能力。即给定一批固定的增量数据变更信息，程序需要收集增量变更信息，并进行一定的数据重放计算，然后将最终结果输出到给定的目标文件中。增量数据的变更信息为了简化处理，会给出明文的数据，主要包含数据库的insert/update/delete三种类型的数据。具体的增量数据变更信息的数据格式见格式描述部分。数据重放主要是指模拟数据库的insert/update/delete语义，允许使用一些中间过程的存储。

赛题考察点如下：

    l  高效“读取-解析-重放”框架设计

    l  数据库操作并发重放算法

    l  高效结构化数据“传输-解析-落盘”框架设计

我们针对赛题考察点总结的思路主要如下：

    l  基于行并发的三级流水线处理模型（低等待率，较慢）

    l  基于块并发的二级流水线处理模型（较低的等待率，较快）

    l  基于列更新逻辑时间的并发更新模型

    l  适用于主键变更的“等待-懒惰删除”重放算法

    l  适用于无主键变更的CAS重放算法

    l  表存储结构按重放范围分区，选择合适的存储方式

    l  基于工作队列的并发解码顺序落盘的客户端设计

第二节    总体设计

程序的整体框架如图2-1所示：

图2-1 程序整体结构

最优成绩程序中一共包含2个版本：

    1、第一个版本为针对该次比赛的特殊数据设计的文件重放程序。程序接口位于SequentialDecoderAsync.java。（最优程序应用该类）

    2、第二个版本为较为通用版本，鲁棒性高，可以对绝大部分增量数据文件重放。程序接口位于SequentialDecoderUnion.java。

    程序的思路均为，单线程顺序读取增量数据文件，并通过多线程并发处理的方式重放，提升重放计算的速度。使用细粒度锁和事件等待机制保证关键操作的顺序，因为重放操作在多线程下的先后执行顺序会影响到重放结果的正确性。

    最初版本的程序的整体读取及处理思路如下图2-2所示。

主要步骤为：

（1）    首先是单线程顺序读取文件，使用RandomAccessFile一次读取8MB的数据，放入图一所示的（单线程block队列）文件块队里中。使用的内存全部从一个freeQueue中取，以保证读的不会太快。

（2）    每个块都有512字节的块尾，单线程读取时将一个块的尾部512字节附在下个月块开头，这样保证一行数据不会被分块读割裂或丢失。

（3）    第二层的处理是多线程处理，从前往后扫描增量数据文件中所有换行符，记录对应的块内偏移和总行数，通过一定界限策略保证处于边界上的行只在唯一的块内处理，防止重复处理。

（4）    最后在同步的情况下，以块的顺序将带尾且做好切分的块放入图2-1的最下面的队列中等待处理。

（5）    最终的并发重放线程每次获取一个自增的逻辑id，然后读取这个id对应的某一具体块内的行，进行数据解析和重放。最后将读完的块放回单线程读取的BlockingQueue中，实现内存的复用和读取速度控制。

图2-2 最初版本数据处理思路

    由于是以行为单位的并发，所以最快的线程比最慢的的线程不会差太大的距离，其次关键操作会等待之前关键操作完成后进行，故不会发生错误顺序重放导致错误数据。

    后期的实验发现，如果增大线程间距离，等待也不会太多，故设计了基于2级流水线的最优成绩版本的模型，如图2-3所示。

图2-3 线上最优成绩通用版本模型

最优成绩程序使用了更快速的基于数组的等待队列，且将块尾部填充放到了多线程中实现，进一步提升了系统的吞吐量。其模型如图2-4所示。

图2-4 线上最优成绩模型

第三节    数据存储结构设计

    考虑到数据量大，故尽量减少GC，通过对canal研究发现，其对mysql的int类型转换成数字，而其他转换为字符串。而对数据进行统计后，可以使用最长的字符串做定长的存储空间限定，即每行可以用一个定长的数组存储（实际情况下也可以通过DDL确定最大行长度，或者使用变长数组进行数据存储）。最后每行数据的每一列都附带一个逻辑时间的变量，用于多线程并发重放时的数据同步。存储的形式如图2-5所示。

图2-5 数据存储形式

    对于整体表的存储，在查询范围不是很大的情况下，可以使用Object数组进行存储，超出范围的使用HashMap进行存储，其中key为主键，这样不仅能节省存储空间，还能加速查询时的速度。其中，HashMap可以使用多个，减小操作Map时锁的粒度。

    对于表存储的操作如图2-6所示。

图2-6 表存储操作

第四节    数据重放同步原则

4.1 数据重放设计流程

    由于存在逻辑时间，对数据的update操作可以并发进行，只需要对该行加锁，并比较操作的逻辑时间和对应更新列的逻辑时间，在操作逻辑时间大时更新数据和该列对应的逻辑时间。删除操作可以看做一种特殊的update，可将列置为无效值，更新策略和平台update策略一致。

    需要注意的是，update操作需要在该行存在的时候才能进行操作，所以需要等待最初的insert操作和update主键的操作，这可以通过主键哈希到细粒度的锁上进行等待，这样能有效减少冲突。算法流程图如图2-5所示，具体的等待代码如图2-6所示。

图2-5 算法流程图

图2-6 数据等待部分代码

    在进行主键变更的时候使用懒惰删除机制删除之前的主键，这样可以保证被延迟的针对update主键之前的该条目的update能正确重放，并且产生的数据变化能正确作用到主键变更后的行上。如图2-7所示，新旧键值都指向同一个存储单元，update目标为1的变更操作也能作用到正确的数据上。这个算法在主键是增长的情况下不存在新插入的数据覆盖原有条目的问题。最后为了防止map中存储过多过于老旧的变更前主键，可以使用老化机制，超过一定期限的旧主键记录可以删除。

图2-7 主键变更操作

    而对应的insert操作只需要简单的将行解析后插入到表存储中即可，并同时调用对应锁的notifyAll，唤醒所有等待的线程。

4.2 数据重放鲁棒性设计方案（对应最优提交代码SequentialDecoderUnion.java）

    针对主键变更不是非常频繁的情况，我们基于最初的思路提出的二级流水线模型，如图2-3所示（之前方案在线上纯重放计算时间在14s左右，该方案在7s左右）。该方案的改进主要是去除中间的解析层，将单行解析和重放计算放在一起处理，即重放计算线程直接获取队列中的原始数据块，以块号和块内编号作为逻辑时间（图2-8所示），按照之前的原则进行重放计算，由于DML的特性，同一个主键的数据变更操作往往不会和插入靠的很紧，选择较小的块大小就能避免长时间等待，通过之前数据的测试，6kw的操作，块大小选择512KB，所有等待次数只有数百次，等待时间基本忽略不计。

图2-8 基于块号的逻辑时间

4.3 数据重放针对线上数据的优化方案（对应最优提交代码的SequentialDecoderAsync.java）

算法线上测试数据具有一定特点，具体的针对性处理有：

1、对表的字段进行了hardcode处理，提升了查找列的速度。

2、对字符串型数据进行了重新编码压缩，时其存储传输仅占用一个int变量。

3、仅重放范围内的操作，没有重放范围外转到范围内的数据。

4.4 线上最优成绩算法设计思路

    如图2-4所示，最优成绩算法设计思路和改进方案很像，是单线程读取，多线程并发处理，使用freeQueue存储定量的堆外内存块，以异步方式读取后，多线程获取数据并进行重放计算。

数据重放的基本逻辑如图6所示，使用CAS机制插入新行到表存储数组中，对单行数据的更新则在存储数据的锁（即行锁）中进行，能够减少冲突的发生。

图6 数据重放基本逻辑

第五节    创新点及工程价值

1、使用java的CAS机制实现无锁操作，减少高并发下的等待。

2、使用细粒度的锁，提高系统的吞吐量。

3、使用最新的异步IO机制，提升IO性能。

4、使用堆外内存，减少堆内外拷贝的时间。

5、使用块序号和块内行序号代替全局逻辑时间，减少并发线程之间的相关性。

6、内存重复使用，GC友好。

7、数据编码存储，减少overhead，全部重放数据存储仅占300MB，结果数据20MB。

8、直接在内存中操作，全部解析过程中不new任何对象，server和client端均无GC发生。

9、充分利用AtomicInteger，减少synchronized的使用。

10、客户端文件写入采用边接收边解码边写入的策略，同时使用线程池工作队列并发处理，从server端发送数据开始250ms以内就能完成客户端接收落盘并退出。

11、健壮性

    本程序设计之初充分考虑了健壮性，除了对字符串进行编码压缩存储（改成byte[]的引用也十分容易，核心机制并不会改变），懒惰删除和等待insert的机制就是为了主键变更所设计的，在mysql主键自动递增（这是很常见的）的前提下不存在任何逻辑问题，不仅能保证高并发下的吞吐量，同时能保证数据的正确性。此方案在没有使用异步IO优化的情况下能在线上取得10s左右的成绩。

    由于采用了字符串编码，字符串只能处理1-2个字的中文（这是对官方提供的所有的公开和线上测评数据总结的普适压缩方法），而最优成绩的算法（SequentialDecoderAsync）的部分使用了字段hardcode，只能适用于该表，且不能处理范围外变更到范围内的操作。但是程序中有范围判断，一旦判断范围不是特定的范围，则会重放全部数据且自动重新解析字段类型（调用SequentialDecoderUnion），性能会略有损失，但能保证结果正确性。

12、工程价值

    本程序的并发重放算法基于最基础的逻辑时间对比，原理简单易懂且容易扩展维护，更新时无需线程间交互，锁定范围小（行锁），对比粒度细（没列均有逻辑时间），在更多的CPU核心上也能很好的并发并提升性能（测试时在56核的CPU上跑出近5000%的CPU占用）。

    对于存在主键变更的情况下，由于数据库主键是自增的，等待-懒惰删除策略能完美运行，在官方之前提供的带有主键变更的数据上能完美计算出正确答案，虽然会占用更多的内存空间，但整体的多线程效率提升也十分明显（线上通过增加线程弥补等待，都能将CPU利用到100%）。

    对于不存在主键变更的情况，CAS操作能以更高的效率运行，3种数据库操作能融合成一种流程处理。

    虽然基于逻辑时间对比完全重放所有操作是非常占用CPU的，但多核并发对于性能的提升非常明显，在行锁竞争不激烈时，性能几乎随线程数呈线性增长，相对于其他设计精巧的操作分发算法，没有明显的排序或分发瓶颈，能用简单的硬件算力提升整体性能，非常适合工程应用。

第六节    复赛总结

    复赛的竞争非常激烈，最好成绩的记录由一开始的30s逐渐推进到10s，最后几天，每天都有人把成绩提升1s，甚至到最后难以置信的2.2s。比赛后期大家都开始利用测评数据特性提升成绩，而我们队仅利用了没有主键变更进范围的特征，对于100w到800w范围内数据的所有操作都进行了重放，然而计算量并没有减少太多（过滤后的数据仍占原有的70%左右），导致最终成绩不是很理想。这次比赛前期，我们队伍的重点任务是处理所有类型数据库重放，增强程序稳定性和鲁棒性，前期一直排名前5以内。后期我们队伍发现本次比赛测评数据强度并不高，但是考虑到比赛的定位，我们没有太多利用测评数据的规律，导致后期发力不足。最终排名靠后，但是从这次比赛中，我们学习到了很多知识，同时认识到了团队配合的重要性。

致谢

    感谢阿里巴巴中间件部门给予的这次竞赛机会，感谢“万少”在旺信中及时的解答我们队伍遇到的各种问题。复赛中没有取得优异的成绩，至今还是很遗憾。很期待明年继续参加阿里中间件部门举办的类似比赛。

致敬主办方——阿里巴巴中间件部门。