题目

给定一批数据增量日志，大概10G大小，要求单线程顺序读取，然后回放数据，客户端查询某个区间的数据，将在该区间的数据的最终结果返回给客户端。
主要有Insert/Update/Delete三种类型的操作。其中update操作可以改变主键。

线上服务器配置

32G内存，16核

解题思路

由服务器端回放数据，利用多核处理能力尽量让回放的操作并行处理，客户端服务接受数据和落盘。核心算法在于服务器端。

关键步骤：

• 单线程读文件，通过MappedBuffer使用堆外内存，减少内存拷贝
• 使用byte[]保存数据，不生成string对象，防止GC过于严重，减低效率
• 多线程处理数据，将update pk之间的依赖映射到同一个线程中。

屏幕快照 2017-07-24 下午9.30.17.png

• 其中一个Reader线程顺序的读文件，如上图所示，黑线实线表示reader线程处理的流程，解析出每行数据的Type和主键oldPK,newPK,这样生成的每行数据的index，然后写入每个文件的index中间文件
• 同时，启动N个线程等待处理所有的index文件，所有的线程都会遍历这x个index文件。
  *如果没有updatePK该多好，所有的操作，根据pk%N 映射成被处理线程。但是事实不是这样的，因为有pk可能被改变，为了保证更新UpdatePk（old,new）,newPK的更新依赖于oldPk，需要将newPK更新交由处理oldPK的线程处理。这样需要使用一个Map<pk,x>,表示pk是被x线程处理的，那么新的更新操作，交个x线程。

线程处理根据Type类型数据不同，有以下规则

• 若Type是Insert，如果线程的id == pk%N,则处理该数据,并将(pk,id)插入map中
• 若Type是Delete， 则删除该数据，并将该PK从Map中删除
• 若Type是Update，则分以下两种情况
  1） 不更新pk，则线程id == Map.get(pk)时，更新数据
  2） 更新pk, 找到id == Map.get(pk)时，更新数据，并且更新map<oldpk,id>,修改成map<newpk, id>。
• 最终，将合并的是数据保存在一个临时文件中，将查询区间的数据发送给客户端。

关键几点

• 减少内存拷贝，使用mappedBuffer
• 减少对象生成，使用byte[]，不能傻乎乎的序列化成string对象，内存爆炸，导致整个程序效率低
• 避免加锁，避免对资源加锁，影响多线程执行效率
• 使用数组代替hashMap,开1000万的数组来表示映射（id,x）,id表示下表，array[id]表示映射的值，当超过1000万的时候，通过map来实现，这样提高map的整体效率
  第一版：序列化byte[]成string,同时生成每行的对象，并通过Map<pk,x>,同意映射到x编号的线程处理，程序的整体效率是60s，瓶颈在Map。
  第二版：不序列化string，40s+
  第三版：改进分发线程部分，30s+
  ...
  第N版：如上文所讲的方式，最后终于进了20s,变成18s，第一名2.2s。这个差距还是有点大。最后好不容易排在4