大规模队列的外围诉求，不仅须要「快」，还须要兼顾「偏心」。
01 引言
HTTP 是一种罕用的通信协议，除了常见网站拜访、上传下载，HTTP 协定还常常被用在音讯推送场景上。
构想你搭建了一个电商平台，有很多大型商家入驻了该电商平台并售卖各类商品，在消费者购买某个商品后，平台会通过 HTTP 协定将消费者购买商品的信息告诉商家，商家则会在后盾接管平台推送过去的音讯。
个别状况下，所有的零碎都失常工作。但忽然有一天，A 商家呈现了爆款产品，使得销售量迅速回升，因为 A 商家的后盾服务解决能力是无限的，便会呈现平台始终在给 A 商家推送商品售卖信息，而将其余商家的音讯都排在前面，这便导致大量其余商家不能及时晓得商品的售卖状况。
这种状况也会产生在某个大客户零碎异样、响应急剧变慢，导致平台推送能力降落影响其余客户。因而，实现不同客户音讯推送的隔离与管制就显得非常重要。
除了音讯推送场景，相似的需要也产生在平台型的 工作解决场景和资源调度场景。
在工作解决场景，很多客户会应用平台来解决工作，比方：通过通信平台发送语音告诉，每个客户都有大量的语音告诉业务申请须要解决。
因为资源是无限的，所以须要给每个客户配额肯定的解决能力，当客户提交的申请大于配额的时候，平台会按最高配额的处理速度来解决客户的申请，并将超过配额的局部积压延后解决，这样会防止因为某些头部客户的申请量过大导致其余客户的申请长时间无奈解决的状况。
在资源调度场景，假如平台有很多资源用于解决客户的申请，尽管每个资源都能解决某些类型的工作，然而资源的实时处理能力是受限的。
比方：资源只能实时处理 100QPS 的申请，这时须要建设一套机制，将对应资源能解决的工作抉择进去，并按资源的理论解决能力提交给对应的资源进行解决，保障所有资源都能满负荷运行。
02 问题剖析
下面三个场景看似不同，但背地其实暗藏的是同样的问题模型：
| 零碎解决能力受限，或者零碎能承诺解决能力受限。
| 理论的申请量可能 在某个工夫点远大于零碎的解决能力。
| 个体与个体之间是独立且存在差别的，平台上有不同的客户，不同客户对时效的要求是不一样的，不同客户的工作规模也是不一样的。
| 超高的并发，比方十万甚至百万 QPS 的 HTTP 音讯推送申请。
对于这种类型的问题，咱们如何解决呢？
其实，不论是资源还是客户，都能够形象为一个实时处理能力受限的队列。
对于音讯推送场景，能够为每个客户建设一个队列，把须要推送的音讯放到对应的客户队列里，并按客户最大配置流量轮流进行推送。
对于工作接管场景，每个客户都能够被当作是一个队列，只有能管制每个队列的最大生产速度，就能保障不会因为头部客户的突发流量导致其余客户被影响。
对于资源调度场景，能够为每个资源建设一个队列，而后将对应资源能解决的工作放在队列外面，再依照队列的实时处理能力，生产外面的数据。
此外，即便同个客户或者同个资源里，业务外部也是有优先级的，所以 队列外部也须要反对业务的优先级。
因而，这类队列模型于一般的生产消费者模型存在显著的区别：
队列数量十分多，队列的生产速度须要满足下限，反对优先级。
如何构建这类面向百万并发、反对优先级的大规模队列的生产生产零碎？
03 技术选型
提到生产生产模型，很天然会想到一些成熟的消息中间件，如 METAQ，KAFKA 等。然而通过调研发现：当队列数量的量级十分大，达到千级甚至万级的时候，这些中间件还是存在较大瓶颈的。
以 METAQ 为例，因为 METAQ 是一个线程池模式，一个 TOPIC 就有一个线程池，所以当 TOPIC 十分多的时候，机器上须要开十分多的线程，这显然是不可能的。通过剖析发现，METAQ 的问题次要是实现机制的问题，所以另一个思路是：基于开源的 METAQ 源代码，对其生产端进行二次开发。
但这也会存在一系列的问题……
首先，METAQ 的代码自身十分宏大，相熟外面的细节就须要投入十分大的老本。此外，METAQ 的设计思路与面向大规模队列的场景有着本质区别，METAQ 外围设计思路是“快”。
然而，大规模队列的外围诉求不仅须要“快”，还须要兼顾 ” 偏心 ”，即保障所有的队列都能达到本人的性能指标。
这就导致 METAQ 外面有大量的逻辑其实并不匹配大规模队列的生产生产模型。同时，思考到后续 METAQ 的版本迭代等的稳定性危险也是十分难以管制的。
不论是 METAQ 还是 KAFFA，在队列优先级的反对上比拟弱，这些中间件在设计的时候，并非次要面向多优先级的音讯。因而，反对这个个性也十分难，革新的老本也十分高。
通过综合评估，基于分布式根底队列进行自建会更稳固、牢靠、可落地。通过零碎调研发现阿里云的 LINDORM 和 REDIS 都提供根底的队列操作，LINDORM 提供的 STRONG CONSISTENCY（SC）级别的数据一致性能力，能够反对数据写入后 100% 被立刻读出。而 REDIS 次要采纳的是一种异步备份的机制，所以从数据的高牢靠思考，抉择 LINDORM 是更牢靠的计划。
LINDORM 是一个反对多模型的 NOSQL 零碎，兼容 HBASE/CASSANDRA、OPENTSDB、SOLR、SQL、HDFS 等多种开源标准接口，反对的模型包含：KV，WIDECOLUMN，TABULAR 和队列模型等，这里应用的就是它的队列模型。
尽管 LINDORM 也叫队列模型，然而它跟 METAQ 音讯队列不一样，他外围的次要只有两个操作接口: 一个是 PUT，把数据放入到某个队列的队尾，胜利后会返回音讯对应的偏移，另一个是 GET(I)，从某个偏移地址获取对应的数据，且单队列最大只反对 150QPS。
到这里便能够发现现实与事实的微小鸿沟，咱们生产生产零碎的指标是要反对十万、百万并发，并且心愿能主动解决生产进度治理、异样的复原等问题，以 LINDORM 目前的情况来看都是没有的。
04 大规模队列生产生产零碎总体设计
通过前文剖析发现 LINDORM 只提供了插入数据及获取数据两个根底操作，单队列只反对 150QPS，而且没有生产进度治理和异样灰度机制，这些问题该如何解决？
这里将构建百万并发、反对多优先级的大规模队列生产生产零碎称为 EMQ(ENORMOUSE SCALE MESSAGE QUEUE)。EMQ 零碎次要分为 6 个模块：队列拆分、队列调配、队列生产、容量管制、生产进度治理、容错机制。
- 队列拆分
为了便于了解，将之前提到的客户对应的队列及资源对应的队列对立称之为逻辑队列，将 LINDORM 的队列称之为物理队列。
LINDORM 单队列只反对 150QPS，且任何物理队列都存在容量限度。然而，咱们零碎设计的指标是一百万 QPS（只管这个一百万 QPS 是所有逻辑队列的总和）。
单个逻辑队列超过 1000QPS 在理论状况中十分常见，且从设计角度来讲，逻辑队列的 QPS 也非常难管制。因而，必须把逻辑队列拆分成一个个 150QPS 以内的物理队列。
- 队列调配
在队列拆分完后，零碎须要生产这些物理队列，因而须要把队列正当的调配到利用集群的机器上。
每台机器上须要启动对应的客户端去生产各队列外面的数据，因为把一个反对 1000QPS 的队列拆分成了 20 个小的物理队列，所以每个队列反对 50QPS。
这里通过单队列容量 50QPS 乘以总的物理队列数等于 1000QPS 来实现逻辑队列反对 1000QPS 的指标，然而从逻辑上如果存在数据歪斜的时候，会存在总容量不满 1000PQS 的状况。
思考到该零碎次要面向的是一个海量数据场景，因而从概率上来讲，这是能够承受的。
- 队列生产
队列调配完后，还须要构建一个反对高性能的生产客户端。该客户端的高性能次要体现在：实现防止网络 IO 拜访导致的性能降落；能疾速解决本台机器上的所有队列，保障既不会轮不到，又能满负荷解决；同时，在生产完音讯后能疾速的执行业务零碎的工作。
- 容量管制
当实现队列生产后，仍须要构建一个生产进度的治理模块，即治理以后队列生产的点位和曾经生产的数据的点位，这样子能力分明地晓得下一个须要生产的数据以及队列的积压量。
- 容错机制
零碎的容错机制次要包含三个方面：首先，如果某个偏移量没有数据的时候，须要能发现并跳过对应的偏移；其次，因为生产完的数据须要提交各业务层进行解决，如果业务层解决失败后咱们应该有肯定的异样复原机制，如果业务层继续失败的时候咱们须要有肯定的兜底机制；此外，当机器因为异样宕机的时候，在原来机器上生产的队列须要平滑迁徙到其余机器，从而实现无损复原。
05 EMQ 集群模型
队列模型如下图为 EMQ 的队列模型：
ROOT 节点下分两个节点：一是 ONLINE 节点，次要是面向生产环境，二是 SANBOX，次要面向生产前的测试，这能保证系统在更新某个性能的时候能够先进行充沛的测试而后再同步到生产环境。
在 ONLINE 节点上面是一个个 TOPIC，这里的 TOPIC 就是咱们之前说的逻辑队列，也就是调配给客户的队列或者为每个资源分配的队列（后文应用 TOPIC 代指逻辑队列）。每个 TOPIC 有肯定的容量，也就是咱们说的 QPS。
每个 TOPIC 下有若干个 GROUP，每个 GROUP 有独立的容量，其值为 TOPIC 的容量除以总的 GROUP 数，并且要求这个值须要小于 LINDORM 物理队列反对的最大 QPS。
每个 TOPIC 上面有分优先级的 QUEUE，该设计次要是为了反对优先级能力设计的。本文为了形容不便，会以高中低三个优先级为例介绍。这三个优先级的 QUEUE 是共享 GROUP 的容量，也就是说如果 GROUP 反对 50QPS，那么三个 QUEUE 的总 QPS 是 50。这里 QUEUE 才是真正对应 LINDORM 的物理队列，这也是为什么要求 GROUP 的容量须要小于 LINDROM 物理队列反对的最大 QPS。
对于资源调度场景，假如有一个资源的 QPS 是 500QPS。那么，他会对应一个 TOPIC，这个 TOPIC 上面有 10 个 GROUP，每个 GROUP 有 3 个优先级，也就是它会生产 3 *10 = 30 个 LINDORM 队列。
- 队列调配模型
假如每个 GROUP 的 QPS 为 50，那么对于 100 万并发的零碎将有约 6 万个物理队列，如何将这么大数量级的队列调配到机器下来？队列调配应该满足哪些准则?
首先，尽可能将队列平均分配到每台机器上，避免出现某个机器生产队列数据量太多产生性能问题；其次，当机器下线、宕机或置换的时候，机器上生产的队列尽可能不要产生大面积的迁徙；最初，当队列新增或者删除的时候，机器上生产的队列也尽可能得不要产生大面积的迁徙。
基于这些准则，设计了如下图所示的队列调配模型。
首先，引入一个 ZOOKEEPER 集群，在主节点上面建设两个节点，一个是 RUNNING 节点，用于保留机器的心跳信息，在机器上线的时候会创立一个以机器 IP 为名字的长期节点，在机器下线的时候会销毁对应节点。二是 SERVERLIST 节点，该节点保留的是所有生产的机器 IP 为名字的子节点，而在子节点里保留的是机器生产的所有队列。
当初有一个队列结汇合和有一个机器列表汇合，须要把队列尽可能均匀的调配到机器上。一个简略的办法就是取所有的队列除以机器总数，平均分配到所有机器。这看似简略又完满的办法其实存在一些问题，当机器下线的时候，这个计算的过程就要从新来一把，可能导致大量的机器生产的队列迁徙。
如果不从新计算而是在第一次取均匀，即在机器下线的时候把这个机器上的队列平均分配到其余机器，机器上线的时候把其余机器上队列抽取一部分过去，这种计划在逻辑上是可行的。
然而，如果有队列新增的时候要执行队列的配置，在队列删除的时候要从新均衡机器的生产队列，这个无疑是非常复杂的。最为重要的是，这种增量变更的形式如果在其中某次调配存在问题，那么前面可能始终无法挽回。
综合思考下，采纳了一致性 HASH 的计划，思考到一致性 HASH 的平衡性，能保障所有机器调配的队列数较为靠近，同时，因为一致性 HASH 的枯燥性，不论是机器变更或者队列变更，不会导致大量的队列机器关系发生变化。
在引入一个核心计算工作后，当机器发生变化或生产的队列发生变化时，都会全量的从新计算每台机器生产的队列。如果机器生产的队列有新增，那么它会新增生产对应的队列，如果有缩小，就会勾销对应队列的生产。
06 EMQ 单机模型
通过后面的一系列设计，曾经实现了队列的拆分，并且将队列调配到集群机器上。那还有最重要的一件事件，就是 构建一个高效牢靠生产客户端。
保障能准确无误高性能地生产队列的外面的数据，保障在队列有数据的状况下按队列配额的最大容量进行生产，以及当队列里的数据比拟少的时候所有数据都疾速被生产。
在原型机验证环节，设计指标依照在 8 核 16G 的机器上，单机 3000 队列的时候反对 1000QPS 并发的解决。如下图，是 EMQ 的单机模型图，次要包含分布式物理队列、近程数据拉取模块、本地缓冲解决模块、缓冲队列散发 & 速度管制模块、音讯工作解决模块以及生产进度治理模块。
- 分布式物理队列
分布式物理队应用的是 LINDORM 的队列模型，思考到后续的扩大，通过对 LINDORM 的操作做了一层形象，只有实现适配层的办法，便能够疾速反对其余根底队列模型，比方：SWIFT，REDIS 等。
- 近程数据拉取模块
近程数据拉取模块次要包含 IO 工作孵化器，外围是一个线程池会周期性地孵化一些工作，将远端队列外面的数据拉取到本地，保障本地队列缓冲区外面的数据达到肯定阈值。它的完结条件是本地缓冲区里的数据满足将来一段时间内的解决要求，或者所有远端的数据都曾经拉取到本地缓冲区。
- 本地缓冲区
本地缓冲区是一系列的本地队列，与这台机器上生产的 LINDORM 上物理队列是一一对应的。也就是说：在远端这台机器有多少要生产的 LINDORM 队列，本地就有多少个对应的队列。
- 缓冲队列散发 & 速度管制
缓冲队列散发与速度管制次要包含一个缓冲工作孵化器，它的外围职责是孵化一些队列工作以及生产本地缓冲区外面的数据，直到达到以后队列的 QPS 下限设置，或者缓冲区的数据空了。
- 生产进度治理
当生产实现一个新的数据之后，会更新对应通道的生产进度的点位，下次再生产的时候从新的点位开始生产，这样保障生产进度一直向前推移。同时，还会将生产进度的信息周期性的实例化到数据库，保障如果机器产生异样或者迁徙的时候，能从新复原之前的生产点位开始生产，因为这个备份是异步且有延时的，这便于所有的消息中间件一样，一个音讯是可能重推的，须要业务解决的时候反对幂等操作。
这里再重点介绍一下，生产速度管制，要单机生产几千个队列，然而每台机器的线程是无限的，所以肯定采纳的是线程池的计划，如下图:
每个队列都有一个独立的生产计数器，每秒钟会执行若干个 LOOP，每个 LOOP 会为每个队列生成一个生产的工作，这个工作蕴含指标队列和生产的最大的工作数。
每次执行拉取的时候会先对以后队列的生产计数器加一，提前预占，而后去生产队列外面的数据，如果胜利了，那么流程完结，如果失败了会将计数器减一，实现回滚的操作。当越到前面的时候，有些队列的以后秒须要拉取的数据曾经足够了，就无需再持续拉取了。
07 优先级管制
在实现 EMQ 集群模型和单机模型的设计之后，曾经可能实现面向大规模队列百万并发的生产生产零碎能力，然而 在很多业务场景下咱们的工作都是存在肯定优先级的。
比方以短信发送场景为例，短信分为告诉业务、营销业务、验证码业务，一个资源如果既能解决告诉业务，也能解决营销和验证码业务，在失常状况咱们必定是心愿验证码的工作能优先被解决，而后再解决告诉业务，最初才去解决去解决营销业务。
也就是在资源调度场景，咱们为每个资源建设了一个逻辑队列，在 EMQ 外面也就是一个 TOPIC，这个队列是须要能反对优先级调度的，如果验证码的工作最初进入到队列，它外面曾经沉积了大量的营销业务申请，咱们也心愿这个验证码的申请能优先于其余营销类型的申请被解决。
如果对应通用的队列机制是不事实的，通用的队列外围的逻辑就是先进先出。
那咱们当初要实现优先级抢占，必须要在队列设计上做文章，如下图:
咱们须要将一个队列拆分成 N 个队列，N 是须要反对的优先级个数。以三个优先级为例，咱们会构建高，中，低三个优先级的队列，这个三个优先级队列组成一个 GROUP，共享这个 GROUP 的容量。也就是说如果这个 GROUP 的 QPS 是 50，那么在一秒钟生产高中低三个优先级队列的总 QPS 不能超过 50。
在生产队列音讯的时候，会先生产高优先级的队列外面的数据，而后再生产中优先级队列外面的数据，最初才生产低优先级队列外面的数据。这样子就保障，高优先级外面的数据肯定会先于中优先级外面的数据被解决。中优先级外面队列的数据也会先于低优先级外面的数据被解决。
本文重点介绍了如何疾速、低成本地构建面向百万并发多优先级的大规模队列生产生产零碎。在领有根底能力当前，在下面做各种简单的业务能力设计便非常容易。比方：文章最开始提到的 HTTP 推送场景，那么假如某个客户忽然有超 10 万 QPS 的音讯须要推送，零碎只反对 10 万 QPS 推送能力，如果按先进先出，那么可能其余客户的音讯都无奈推送了。然而，如果基于 EMQ 构建生产者消费者模型，为每个客户（或客户组）建设一个队列，并且配置这个队列反对的下限推送的 QPS，音讯在发送前先推送到 EMQ 队列，按配置的限额生产。那么，即便客户霎时有很大的信息推送申请，也不会影响到其余客户的失常业务解决。