Skew mitigation - CS 591 K1: Data Stream Processing and Analytics Spring 2020

• 语言: 英语
• 格式: .pdf
• 来源: vasia.github.io

摘要

文档讨论了数据流处理中的偏斜缓解（Skew mitigation）问题，探讨了通过关键分区（Key partitioning）和负载均衡（Load balancing）来解决流数据处理中的不平衡问题。提出了两种分区策略：基于哈希的轮转分区和保留键语义的轮转分区，分析了流行键（Popular keys）导致的负载不平衡问题。进一步介绍了使用两次选择的方法（Power of two choices）在流式设置（Streaming setting）中动态分配任务以减少负载差异，并通过示例说明了如何通过删除满足特定条件的键值对来优化分区。

AI总结

《Skew mitigation - CS 591 K1: Data Stream Processing and Analytics Spring 2020》总结

本文档讨论了数据流处理中的**偏斜缓解（Skew mitigation）**问题，即由于某些键（key）的高频出现导致分布式系统中工作负载不均衡的情况。文档详细介绍了几种分区策略和缓解方法。

1. **分区策略**：
- **轮转分区（Round-robin）**：
- 优点：键分布均衡，无需路由表。
- 缺点：键语义不保留，可能导致相同键被分配到不同工作者。
- **基于哈希的分区**：
- 优点：保留键语义，相同键总是分配到同一个工作者。
- 缺点：热键（popular keys）可能导致负载不平衡。

2. **偏斜缓解方法**：
- **跟踪键频率**：系统需要跟踪键值的频率，使用混合分区函数对正常键和热键进行差异化处理。由于精确计数在大键域中难以实现，通常只需跟踪热键（heavy hitters）。
- **示例中使用的方法**：通过设定阈值（ε=0.2），删除满足条件fx + εx ≤ 1的键，减少负载不平衡。
- **两选力（Power of Two Choices）**：
- 在流设置中应用两选力，保留键语义，通过将键映射到两个选择中负载较低的工作者，降低负载变异。
- 该方法无需路由历史记录，适用于可合并函数的计算场景。

3. **结果与结论**：
- 两选力方法在流设置中实用，能显著降低负载变异。
- 计算必须由可合并函数完成，工作者需能本地计算当前负载。

4. **进一步阅读**：
- Muhammad Anis Uddin Nasir 等人关于两选力在分布式流处理中的应用。
- Manku 和 Motwani 关于数据流中的近似频率计数方法。

总结：文档重点讨论了数据流处理中的负载不平衡问题，并提出了基于键分区和两选力等方法的有效解决方案，适用于分布式流处理引擎的负载均衡优化。