流处理中的同步建模

### 流处理中的同步建模 #### 1. 引言 一个设计良好且调度合理的数据流管理系统（DSMS）应能满足期限要求并提供可预测的性能。实际的流数据库是高度复杂的系统，会实现不同的优化算法。 元组的大延迟可能由临时过载导致。在这种情况下，计算无法流畅进行，流队列会迅速变长，最终可能因存储资源短缺而导致系统崩溃。若系统允许生成不完整结果，可以采用负载丢弃策略，即从数据流中随机删除一些元组，以减少待处理的数据量，满足部分数据的延迟要求。 平均延迟时间的估计有助于调整调度器，使其在时间和内存优化之间切换，也有助于调整部分结果的生成时间。在流处理中，二元运算符（如连接）的输入同步会导致元组进入下游运算符的方式出现偏差，从而导致延迟估计出现重大误差，我们希望减少这种误差。 经过大量实验，我们得到了一个启发式模型，该模型描述了利用率水平、查询定义和延迟之间的关系。此模型不考虑节点临时过载超过其 CPU 容量的情况，也不关注网络链路的影响，但与 DSMS 中流行的平均值分析相比，其准确性更高。 #### 2. 基本术语 - **流查询**：流查询 Q 被定义为有向无环图（DAG），其节点和弧分别表示流运算符和流。查询 Q 被划分为子查询 Q = {u1, u2, ..., un}，每个子查询部署在分布式系统的计算节点上，计算节点可以是流数据库中的独立处理器或计算机。 - **流运算符参数**： - **选择性（Selectivity）sx**：运算符 x 处理一个输入元组所产生的平均输出元组数。 - **生产率（Productivity）ux**：运算符 x 处理一个输入元组时生成至少一个元组的概率。对于选择、投影和映射运算符，生产率和选择性相等；而连接运算符的生产率和选择性不同。 - **处理成本（Processing cost）cx**：运算符 x 处理一个输入元组所需的时间。 - **元组**：流传输的单个数据部分是元组，它有一个时间戳，定义了其进入系统的时间。每个流包含按时间顺序排列的元组，每个流由平均元组延迟 l 描述。 - **延迟分解**：延迟可分解为三个元素：运算符处理时间、同步时间和排队时间。 - **运算符分类**：根据输入流的数量，流运算符可分为一元运算符（一个输入流）和二元运算符（两个输入流）。流运算符按时间顺序处理元组，对于二元运算符，只有当两个输入流都不为空时，才能确定具有最小时间戳的元组。 - **全局选择性**：连接源 a 和运算符 b 的运算符序列定义为路径 path = {a, ..., b}，路径上的全局选择性 spath = ∏i∈path si，表示一个元组通过该路径处理时，运算符 b 输出的平均元组数。 - **源运算符**：定义集合 Src 由源运算符 1, ..., K 组成，这些运算符的平均输出速率由向量 X = (X(1), X(2), ..., X(K)) 定义。 #### 3. 基本方法 基于利特尔法则的平均值分析是建模排队系统的基本方法，在流数据库中很流行，因为它仅基于查询参数的平均指标。我们的模型假设流数据库由多个处理节点组成，每个处理节点为多个类别的客户端服务，每个处理节点 i 评估子查询 ui。 以下是相关公式： - **累积延迟**： \[ l_b = \frac{\sum_{a \in Src} X(a)n_{a,b}l_{a,b}}{\sum_{a \in Src} X(a)n_{a,b}} \] 其中，$n_{a,b}$ 是处理来自源 a 的一个元组后流入运算符 b 的平均元组数，$l_{a,b}$ 是处理来自源 a 的元组后运算符 b 输出的平均元组延迟。 - **计算节点的利用率**： \[ U_{(o,k)}^i = X_{(k)}^o\overline{B}_{(o)}^i = X_{(k)}\overline{D}_{(o,k)}^i \] 其中，$\overline{D}_{(o,k)}^i = B_{(o)}^i n_{k,o}$，$\overline{B}_{(o)}^i$ 是部署在处理节点 i 上的运算符 o 处理一个元组的平均时间。 \[ U_i = \sum_{o \in u_i} \sum_{k = 1}^{K} U_{(o,k)}^i \] 当所有 $U_i