哈希/分片的ActionBlocks

Question

我有一些需要并行处理的特定项目流，因此我正在使用 TPL Dataflow。但是问题在于，具有相同键（类似于字典）的项目应按照先进先出（FIFO）顺序进行处理，而不应该彼此并行处理（它们可以与具有不同值的其他项目并行处理）。

所做的工作非常耗费 CPU 资源，异步锁极少，因此我的解决方案是创建一个大小为 Environment.ProcessorCount 的 ActionBlock<T> 数组，并根据键的 GetHashCode 值将其发布到其中。

创建：

_actionBlocks = new ActionBlock<Item>[Environment.ProcessorCount];
for (int i = 0; i < _actionBlocks.Length; i++)
{
    _actionBlocks[i] = new ActionBlock<Item>(_ => ProcessItemAsync(_));
}

使用方法：

bool ProcessItem(Key key, Item item)
{
    var actionBlock = _actionBlocks[(uint)key.GetHashCode() % _actionBlocks.Length];
    return actionBlock.Post(item);
}

所以，我的问题是，这是我问题的最佳解决方案吗？我是否影响了性能/可扩展性？我有没有遗漏什么？

- i3arnon

---

我喜欢它。我想不出另一种不需要存储的方法。只要确保哈希码正确分布，这应该没问题。 - spender

依赖于“GetHashCode”的值对我来说听起来很奇怪，为什么你要这样做呢？实际需求是“相等的项应按FIFO顺序处理”吗？ - svick

@svick 更像是应该按照FIFO顺序处理具有相同键的项，类似于使用字典的方式（不一定要是相同的Item类型）。我会更新问题以使其更清晰。 - i3arnon

@I3arnon 你怎么知道所有的线程都会有差不多数量的工作要做？(uint)key.GetHashCode() % _actionBlocks.Length 存在一种可能，即分布不均，某些核心不会执行任何操作。 - MarcinJuraszek

@MarcinJuraszek 这是真的。我已经确保哈希值尽可能均匀地分配，并通过测试发现确实如此。但是...这就是我将其发布在这里的原因之一。 - i3arnon

Answer 1

我认为你的方法是合理的，前提是你知道哈希码会得到很好的分布。

如果您想更好地保护自己免受不良分布的影响，可以使用更多的ActionBlock，同时通过使用单个自定义{{link1：TaskScheduler}}来限制它们的总并发级别。您可以在{{link2：ParallelExtensionsExtras}}或{{link3：MSDN}}中找到这样的调度程序。

- svick

---

那么这将如何解决分布不良的问题？如果我有一个比其他哈希更常用的“特殊”哈希，那么拥有许多相互阻塞的ActionBlocks与使用% _actionBlocks.Length有什么不同呢？在您的情况下，“特殊”哈希将使其队列相对于其他队列更大... - i3arnon

是的，它仍然比其他的大，但很可能比小块时要小，因为那个特殊哈希会有更少的碰撞。例如，如果一半的哈希值为0，其余的均匀分布，则使用2个块，3/4的所有项将进入块0。但是使用4个块，只有5/8，使用无限块，则为1/2。 - svick

但是你仍然只有2个线程。一个线程将处理5/8块和1/8块（6/8 = 3/4），另一个线程将处理剩下的2个1/8块（2/8 = 1/4）。我错过了什么吗？我明白当你增加线程数时可以这样做，但是这段代码非常CPU密集型，据我所知，每个核心建议使用单个线程。 - i3arnon

不，那不是我的意思，你会有2个线程，但它们将在所有4个块之间共享。这样，即使块的负载不同，线程的负载也应该基本均匀分布。 - svick

过度订阅甚至是必要的，以充分利用 CPU，因为随机分布不是均匀分布。一些块将被低效利用，而另一些则会过度利用。 - usr