search

rocketmq-baiji / rocketmq

Mirror of Apache RocketMQ
Apache License 2.0
4 stars 20 forks source link

【百技 第2组 第3题】全局排序consumer #11

Open PhantomGrapes opened 6 years ago

PhantomGrapes commented 6 years ago

百技273期 脱单发财队

第三题 全局排序的Consumer

问题链接 https://github.com/rocketmq-baiji/rocketmq/issues/2

赛题重述

实现全局有序的Consumer，从多个Topic消费的消息在时间上排序。

赛题难点

  1. 用尽量低复杂度的算法解决多个有序队列数据的全局排序问题。
  2. mq队列按长度读取，可能存在因分配不均衡，无法获取某个时间前的全部数据，仍有时间更早的数据在mq队列中的问题。
  3. 同一个producer如果读写速度过快，在获取时间戳的最小粒度下有多次向不同mq的写入操作，无法判定数据的时间先后顺序。
  4. 为鉴权等扩展功能留接口

解决方案

default

针对难点一，用复杂度O(mlogn)的归并排序和堆排序结合算法解决全局排序问题，其中m表示相关的mq个数，n表示每次从每个mq中抽取的数据数目。

我们构建Consumerorderly的类，从多个相关mq多次抽取定长有序数据子队列，利用各个子队列中最早的数据构建长度为m的最小堆，每次弹出堆顶时间最早的数据，然后读取该数据所在自队列中下一个数据进堆，直到子序列全部数据出堆。

针对难点二，每次获取数据排序后分为可信队列和留存队列，只输出可信队列，解决分配不均衡问题。

为了解决分配不均衡导致的每次读取的数据不完全是全局时间最早的前mn个数据，我们根据不同mq读取出的最迟数据(时间记为t)对每次读取的数据排序后进行划分，对于t之前的有序数据称作可信序列，直接输出，对于t之后的数据称为留存数据，无法确定其时间是否比仍在队列中的其他数据时间都早，因此暂时保留，等到下次从mq中拉取数据时再一起归并计算。

案列效果

20180821110400

有待解决的问题及思路

针对难点二，数据分布极端不平衡情况下，本算法可能产生留存数据越来越多的情况，可以根据每个mq队列中的留存数据量来确定下一次拉取数据长度。

针对难点三，在producer生成数据的时候根据producerId\生成时间等信息参考雪花算法生成唯一id，当多mq队列归并排序时遇到时间戳相同则比较生成id的大小，决定先后顺序。

针对难点四，在全局排序前可以添加鉴权函数，鉴权通过后开始抽取和排序。

反思

第三题是算法题，但是基于JAVA语言实现，由于算法同学技术栈不够全面，没有人熟悉JAVA和相关工程，因此实现缓慢。需要加强自身能力,多多熟悉多种语言开发。

AdrianHsu commented 6 years ago

推～～～～～～