在DSPS中（例如storm）调度问题上有性能瓶颈：如何在集群中的所有可用节点中部署storm应用拓扑的组件。
TOSS基于结构的调度器：
1.节点间的流量
2.考虑基于拓扑结构形式的调度器
3.减少运行时重新调度的开销
目的：通过缩短总体通信成本来减少进程间的平均延迟，同时平衡多个集群节点的负载。
原理：
TOSS在静态拓扑结构上识别具有大量通信的边，将这种通信密集型的边分到一组slot中
（由α自我调整参数管理的slot）。
将一组executors分配到工作负载最小的节点上。
优点：
1.通过分析拓扑结构绕过昂贵成本的重新调度
2.采用自我调整参数适应工作负载环境的机制，而不是手动设置系统参数
storm整体吞吐量很大程度上取决于事件处理延迟。对于计算延迟的原因：
1.一组executors之间的通信可能会带来大量的网络流量
这些executors可以在不同的worker进程和工作节点worker node上分配和执行。executor之间的通信成本差异很大，很大程度取决于分配策略。在storm拓扑结构中确定了定向的数据流。
executor之间通信是对storm最佳调度产生不利影响的主要因素之一。很大程度取决于executor被分配到的位置。
1.节点间通信
2.进程间通信
3.线程间通信
但完全以最小化通信开销为目的的调度策略可能导致将executors都分配给一个worker而造成瓶颈。
所以要利用基本的负载平衡原理，TOSS在高吞吐量和低延迟之间做了权衡。
2.storm应用拓扑需要更灵活的参数配置
基于静态结构的预测工作负载、与运行时工作负载不同。
大多数调度器配置线性参数确定拓扑结构，但缺乏运行时的工作负载的反馈，由线性参数控制的拓扑组件来分配策略并不是最优的。这会导致运行时严重重新调度成本。
设计：
TOSS分两个阶段实现减少通信开销提高性能：
1.分析静态拓扑结构，对executors进行分区。
2.TOSS利用历史数据运行时的流量信息估计当前的通信流量数据，然后调整线性参数来控制executor的分区，而不依赖于运行时的重新调度。
TOSS调度策略两阶段：
分区：
1.需要所有拓扑应用的集合Ω中取一组拓扑、要分配的executors的集合E
2.TOSS首先分析静态拓扑结构，一发现通信量大的executor之间的边（热边）。（当没有运行时的工作数据时，只考虑组件之间的连接性，而不是用运行时的流量来确定热边）。
3.TOSS将拓扑结构表示为有向无环图DAG
4.通过图的遍历算法，经executors划分为以热边为中心的几个顶点，放在同一个节点中。
5.在将executors划分到slots中时，努力最大化利用worker node节点上的可用资源（即最大允许的executor分配αi）。
分区后，TOSS会生成一组任务集合的分配，规定了如何将executor分配到worker node节点中。
1.TOSS寻找可用的worker node节点来运行executors组
为了平衡工作负载，TOSS在部署拓扑结构之前，从worker node节点中收集工作负载信息存到中央数据库来估计未来工作负载。
2.同构集群用CPU利用率衡量工作负载
异构不仅要用cpu利用率，还要用cpu速度（因为cpu利用率高的高速节点可能比cpu利用率低的低端节点维持更好的计算性能）
问题表述：
负载：
Li表示executor在节点ni产生的负载
Li=ui*si
（ui表示节点ni的cpu利用率、si表示节点ni的cpu速度（在多核处理器中，cpu速度为核数*单核速度））
为了定量的衡量负载平衡性能，引入负载偏差，最小化负载偏差，负载平衡的目标可以通过最小化所有节点ni中的最大负载实现：
executors之间流量测量：
TOSS收集ei从ej中（i!=j）接收到的元组的速率，秒单位元组数tuples/sec
汇总所有不同worker node节点之间executor传输的总流量，TOSS目标就是最小化节点间的流量：无论哪几个节点之间的传输的流量之和是最小的。
对于一次分配，必须满足约束条件：
θi表示第i个worker node节点上分配executor的数量
Θ表示一个拓扑应用wi中的所有executor总数量（？在上述图表中含义是：要分配的分配集合）
αi表示可以分配给θi的executor的最大比例，区间【0,1）
实现细节：
算法1通过算法2获得了参数α
通过图的遍历算法DFS搜索出一条链，链就是具有通信的边。
这样将具有通信边的executor进行分组，放到同一个slot中减少通信
算法2负责将分配 Θ表示一个拓扑应用wi中的所有executor总数量，分配到可用的slots或者worker node节点中。
算法2原则：寻找一个运行时工作负载最低的worker node节点（通过公式：Li计算公式，得到所有worker node节点的工作负载）
自我调整机制的目标：
优化系统参数（αi），为了在节点之间均匀地分配工作负载。
例如：
初始约束向量[α1，α2，...，αm]设置为[0.1、0.2、0.1、0.2、0.1、0.2、0.1]。
即：当α1设置为0.1时，在分配1这组中要分组的最大executor数量是executor总数的10%
工作负载被均匀的分为：
W是所有节点的工作负载之和，M是参数α设置的个数
设计了一个自我调整系统，减少高工作负载节点的executor数量，而增加工作负载较轻的节点的executor数量。采用线性回归技术，利用梯度下降（一种迭代优化算法）进行参数调整，可以提供一个最优值（设想为均匀分布的工作负载）：
通过监控之前分配的所有各个节点的工作负载{L1…Lm}，可以调整参数：
ξ是控制调优速率的参数，需要为它设置一个合适的值，避免调节速率过慢或者爬坡。
它确保了α的值保持在[0,1）之间。
系统架构：
1.TOSS主动收集来自worker node 节点的所有运行时的工作负载，数据库存放运行时的工作负载、以前分配的工作负载
2.分区阶段，TOSS调整分配参数α实现平衡负载
3.完成分区阶段后，TOSS将所有的executor分配到所有的worker node 节点上。
实验
性能指标：
延迟：事件通过整个拓扑所经历的延迟。（包含了传输时间和所有bolt处理时间）
the latency metric is measured as the summation of traffic time and total bolt process time.
The traffic time can be reduced by aggregating multiple executors exhibiting a massive amount of communicated data, whereas the bolt process time can be dwindled by alleviating the bottleneck occurrence.
传输时间：可通过将大量通信的executor放在同一个worker或者节点来减少
处理时间：通过减轻瓶颈的发生来减少。
吞吐量：元组通过所有的bolt的平均吞吐量
网络敏感型拓扑结构（SQL）：
spout反复生成固定大小10kb字节的随机字符串作为输入元组，元组经过中间bolt附加一个字符，最后bolt是计数功能。
因为bolt中的处理逻辑是直接和简单的，所以测量的吞吐量很大程度上取决于storm集群的网络连通性。
由于executor的部署和初始化引起的高延迟，这样的初始时间间隔叫做冷启动。
一般忽略20-30s的第一个时间窗口的延迟测量，在冷启动阶段，延迟会急剧下降，executors会在冷启动阶段被部署和初始化，之后延迟会变得稳定。
计算密集型拓扑（rolling wordcount）：
它应用一个滑动窗口来挑选有效的输入范围，任何超过改时间窗口的文本都被认为是过期的输入。
spout从本地文件中产生大量的文本，然后传给分割单词的bolt，最后传到一个滚动计数的bolt，最后将所有输出传递给写入本地文件的bolt。
总结与思考：
此参数调整机制有缺点：参数自调优的目标是使调度器能够自动配置约束向量，而无需手动调优过程。不幸的是，梯度下降方案依赖于参数ξ来控制调优速率，而这不是由当前的调优系统管理的。这种缺点可以通过用先进的参数调优技术取代梯度下降来解决。
自调优机制无法更改参数集的大小。在我们的研究中，参数集m的大小导致了分配的总数。如果自调优机制忽略了设置大小m的重要性，那么在某些情况下，这种恒定的大小可能不会导致最优的拓扑部署。
参数调整方法：有很多优于梯度下降法的调参方法
【28】“Parameter tuning for configuring and analyzing evolutionary algorithms,”
https://www.sciencedirect.com/science/article/pii/S2210650211000022
【29】“Parameter tuning for the artificial bee colony algorithm
https://www.researchgate.net/publication/220906495_Parameter_Tuning_for_the_Artificial_Bee_Colony_Algorithm
