如何使用Rust的gaffer实现优先级的微批处理调度器 - njk


Surve Mobility是一个为共享出行服务提供商提供全方位服务的车队运营,我们从客户那里接收任务,例如充电、清洁、补充耗材等。根据客户和任务,这些任务会在整个过程中一一接收在一天的过程中,在每天的批次中,或者在极少数情况下,在每月的批次中。然后,我们的代理在城市中穿行,步行,乘坐客户车辆和公共交通工具来完成这些任务。Surve 的应用程序将任务交付给代理,导航到任务,并提供对开门等操作的访问权限。
我们有一个路由算法,它为每个活动代理计划任务的旅行,优化旅行距离、任务优先级和截止日期,并维护不变量,例如代理可以完成的任务,他们可以在一天中的什么时间完成,充电点等资源是否可用。
很多时候我们可以允许巡视有点陈旧,但是在一些操作之后用户正在等待查看结果,在诸如更改优先级和拒绝任务等情况下,用户只能查看陈旧数据,直到重新路由完成。
路由算法可能需要一段时间才能运行,大约 10% 的时间需要超过 0.5 秒,并且会给我们的数据库带来相当大的负载。长事务和大量写入和读取的行意味着该算法使用全局锁运行以避免序列化失败。当任务和代理的数量很少并且算法很简单时,这很有效。然后我们成长了,我们有更多的任务和更多的代理,算法变得更加复杂。这种全局锁定使应用程序在用户等待的情况下变得太慢。
 
优化思路
这个问题有一些优化机会,这意味着通过改进调度我们可以获得更可靠的性能,并且我们可以(在短期内)避免担心优化路由算法本身。

  • 分片

这个问题首先要注意的是,它可以很好地按业务区域(城市)进行分片。当代理人在汉堡开始工作时,其影响仅限于在汉堡的旅行。所以我们可以有效地同时运行多个改道,只要它们在不同的城市。分片问题意味着随着我们为更多城市提供服务,应用程序性能不会下降。
  • (微)批处理

我们的路由算法不是插入新任务的迭代算法,它查看所有任务并优化所有旅行以服务它们。所以我们只需要足够频繁地运行路由,以便正确查看数据。如果我们对一个城市的状态进行 100 次更改,我们只需要运行一次算法即可使旅行正确。当我们收到大量数千个订单时,这特别有用,或者如果几个用户在缓慢的重新路由运行时正在更改内容 - 他们只需要等到下一次重新路由结束。
  • 不同的优先级

用户等待:第一优先级是针对诸如协调器已将任务划分优先级,或者代理标记需要跳过任务等情况,在这些情况下,协调器或代理在看到结果之前无法继续他们的工作改道。它应该尽快运行。为了做到这一点,我们可以为此优先级保留保留的计算容量,以便当需要在此级别重新路由时,通常可以立即安排它。
无效数据:第二优先级是当有新信息需要考虑,但没有人特别等待时。这就像来自自动化外部系统的新任务,他们可能会在之后直接发送更多任务,所以我们可以等一下。
Timeout:最后一个只是获取输入中不会触发上述任何其他更改的任何其他更改,它设置了数据陈旧程度的上限。

解决方案
我查看了现有的调度程序,但没有发现任何具有允许我们利用这些优化机会的功能的功能,因此我借此机会构建了一个新的调度程序并发布了我的第一个 Rust crate,决定它需要这个集合特点:

  • 作业入队:可以使用Clone + Send发送者将作业从其他线程入队。
  • 循环作业:如果作业未因某个最大超时而入队,则可以自动将作业入队。
  • Futures:将作业排入队列的其他线程应该能够await得到结果。
  • 优先级:作业队列优先执行,提交顺序次之
  • 作业合并:任何具有相同效果的作业都应合并到队列中以避免不必要的负载。这可能是最重要的功能,它为其他功能带来了一些额外的挑战:
    • 具有不同优先级的合并作业必须合并到最高优先级
    • 具有等待它们的期货的合并作业需要使用合并作业的结果唤醒两者,因此结果需要实现 `Clone` 以便可以将其提供给两者。
  • 并行执行:多个工作线程正在处理作业
  • 并发排除:但有些作业需要获取一些锁,因此不能同时运行
  • 优先级限制:为了让容量为更高优先级的作业做好准备,我们可以限制运行低优先级作业的线程数。

结果是选择gaffer,请查看文档以获取特定示例以及如何使用它。在这里,我将更多地讨论结合这些功能以及其他设计决策所面临的一些挑战。
.... 点击标题