C＃中的分片和多线程-深潜

数据库样式的分片能否提高多线程应用程序的性能？

我正在研究一个解决数独谜题的示例应用程序。该应用程序可以在多个线程上快速解决难题。我想跟踪已经检查了多少拼图板。我需要一个可能每秒增加3,000,000次的计数器，所以我开始考虑性能。

计数器的性能可能不会影响我的应用程序的整体性能，但看看不同的实现如何执行会很有趣。为了了解更多信息，我以各种方式实施了计数器。然后，我在我的机器上运行了多个基准测试，包括6个CPU内核和12个虚拟CPU内核。为了减少追逐，这里是结果。更高更好。

每列代表一次基准测试。顶轴显示同时尝试递增单个计数器的任务数。左轴显示计数器在1秒内递增的次数。

因此，例如，让我们考虑第004列。这一列向我们展示，使用4个并发任务，LockingCounter每秒增加超过4000万次，InterlockedCounter每秒增加不到3000万次，并且ShardedCounter增加了每秒近1.4亿次。

该UnsychronizedCounter只是因为不同步计数器没有采取任何措施防止出现在001列，种族condtions代码。尝试从多个线程增加UnsychronizedCounter将导致计数不足。总计数不正确。因此，仅在单个线程递增时检查UnsychronizedCounter的性能是合适的。

基准测试可以解决线程争用的最坏情况：紧密循环中的多个线程竞争读取和写入相同的值。以下是每个任务的内部循环：

while(!cancel.Token.IsCancellationRequested)

counter.Increase(1);

所以最大的问题是，什么是ShardedCounter，为什么当有更多的任务竞相增加它时它会表现得更好？

为了理解答案，让我们看看每个计数器实现，从最简单到最复杂。

UnsynchronizedCounter

图片来源：Shutterstock.com矢量图ID：229462564

UnsychronizedCounter尽可能简单：

publicclassUnsynchronizedCounter : ICounter

{

privatelong_count = 0;

publiclongCount => _count;

publicvoidIncrease(longamount)

{

_count += amount;

}

}

所述计数属性返回私人_count，并且增加（）方法增加了私人_count。

由于UnsynchronizedCounter的开销为零，因此它可以比任何其他计数器更快地计数，但只能在一个线程上计数。

如果多个线程同时调用Increase（），则由于竞争条件，最终计数将低于预期。维基百科对种族条件以及它们如何导致错误有很好的描述。

LockingCounter

该LockingCounter通过持有一个锁，同时读取和写入防止竞争条件_count。

publicclassLockingCounter : ICounter

{

privatelong_count = 0;

privatereadonlyobject_thisLock = newobject();

publiclongCount

{

get

{

lock(_thisLock)

{

return_count;

}

}

}

publicvoidIncrease(longamount)

{

lock(_thisLock)

{

_count += amount;

}

}

}

锁定防止了漏报问题UnsynchronizedCounter遭遇，但正如上面的基准测试结果表明，LockingCounter比慢得多UnsynchronizedCounter。

InterlockedCounter

System.Threading.Interlocked为多个线程共享的值提供原子操作。为了获得更好的性能，C＃的并发集合使用互锁操作来实现 ConcurrentStack之类的集合。在每种情况下，互锁操作都不能用于替换锁定，但在增加计数器的简单情况下，它们可以。InterlockedCounter使用Interlocked.Add（）以永远不会被低估的方式增加计数，并且在等待获取锁时不会阻塞。

publicclassInterlockedCounter : ICounter

{

privatelong_count = 0;

publiclongCount => Interlocked.CompareExchange(ref_count, 0, 0);

publicvoidIncrease(longamount)

{

Interlocked.Add(ref_count, amount);

}

}

看看上面的基准测试结果，我们发现只有一个任务，InterlockedCounter的计数速度是LockingCounter的两倍多。这大大减少了开销。InterlockedCounter是多个线程增加计数器但是没有很多争用的最快选择。

但请注意，当多个线程试图非常快速地递增计数器时，InterlockedCounter和LockingCounter执行大致相同的操作。这是为什么？因为两个实现都不断地从CPU缓存中驱逐计数器的值并再次从RAM加载它。在RAM中查找值至少需要在缓存中查找值的10倍，因此从缓存中清除计数器的值非常昂贵。

这是一个说明问题的框图。

有2个CPU，每个都有自己的缓存。最初，RAM和两个缓存都存储计数器的值0。

首先，左侧的CPU增加计数器。它从缓存中读取计数器值，并将新值写回其缓存和RAM。但另请注意，右侧的缓存不再包含值counter = 0。右侧的缓存条目被逐出，因为它的值已过期。

接下来，右侧的CPU增加计数器。它必须从远程RAM中检索计数器的值，如红色箭头所示，因为它的缓存不再具有该值。

在RAM中查找值至少需要10倍于在缓存中查找它。从RAM中读取值会影响性能，因此实现是使用锁还是System.Threading.Interlocked的魔力并不重要。

我们可以做些什么来避免InterlockedCounter和LockingCounter的性能瓶颈？就在这里。

ShardedCounter

ShardedCounter使用与数据库分片相同的原理，也称为水平分区。简而言之，当数据库执行不佳时，因为太多客户端试图同时访问同一个表，一种解决方案是将其分解为跨多个数据库服务器的多个表。例如，考虑一个地址表：

整个表存储在一个SQL Server中，服务器每秒可以提供20个查询。当许多客户端尝试同时访问该表时，它们总共限制为每秒20个查询。当负载超过每秒20个查询时，客户端的请求需要更长时间，并且整个系统的性能会受到影响。

在这种情况下，可能（根据正在运行的查询类型。在这种情况下，查询需要按状态查询数据）通过将一个Addresses表分成50个Addresses表来提高性能，一个用于每个州。

因为每个SQL Server现在处理一小部分负载，所以总吞吐量增加到每秒20个查询* 50个SQL Server =每秒1000个查询。

ShardedCounter采用相同的策略来增加计数器的吞吐量。它将一个计数器分成多个计数器，每个CPU核心一个计数器。每个计数器都称为分片，因此名称为ShardedCounter。

注：实际上，它打破了柜台分成多个柜台，每个线程。但是由于单个线程倾向于在同一个内核上运行一段时间，因此这种近似使得性能更容易解释。

分割计数器的想法很古老。我第一次在MapReduce中看到它。今天Google搜索“分片计数器”会产生一个主要与Google App Engine和Google Cloud Datastore 相关的分片计数器的讨论。我已经看到它也用在SQL数据库中。

让我们用ShardedCounter重播上面的相同步骤。最初，有两个柜台。两个计数器都存储在RAM中，计数器存储在每个CPU缓存中。

4

左侧的CPU递增计数器。它从缓存中读取counterA，并将值写回缓存和RAM。

然后，右侧的CPU递增计数器。它从缓存中读取counterB ，并将值写回缓存和RAM。

该ShardedCounter因为性能更好的增加操作从来没有（参见下面的注释）读取RAM的值。它总是从缓存中读取值。

注意： 大概永远不会。线程从CPU调度和调度。在CPU上调度新线程时，可能必须从RAM读取该值。

但是，当然，在某些时候，我们需要读取总计数，为此，我们必须从RAM中加载一些值。下图说明了如何计算总计数。

因此，阅读总数仍然有点贵。但是，在我的应用程序，基准测试以及许多实际应用程序中，计数器的读取频率远远低于增加计数器的频率。基准代码每秒读取一次计数器，但每秒增加计数器数百万次。因此，增加的成本使阅读成本相形见绌。

ShardedCounter如何 为每个核心创建一个计数器？从技术上讲，它没有。它为每个线程创建一个计数器。因为线程倾向于在同一个核心上运行一段时间，所以效果类似。

ShardedCounter通过Thread.AllocateDataSlot（）分配一个新的线程本地存储槽。这将为每个线程创建一个存储计数器分片的位置。

publicclassShardedCounter : ICounter

{

// Protects _shards.

privatereadonlyobject_thisLock = newobject();

// The list of shards.

privateList _shards = newList();

// The thread-local slot where shards are stored.

privatereadonlyLocalDataStoreSlot _slot = Thread.AllocateDataSlot();

检索计数需要对所有分片中的计数求和。

publiclongCount

{

get

{

// Sum over all the shards.

longsum = 0;

lock(_thisLock)

{

foreach(Shard shard in_shards)

{

sum += shard.Count;

}

}

returnsum;

}

}

在快速，通用的路径中，增加计数器不需要锁定，只读取和写入其他线程无法读取或写入的值。因此，另一个CPU尝试读取该值并从RAM中获取该值的风险很小。

publicvoidIncrease(longamount)

{

// Increase counter for this thread.

Shard counter = Thread.GetData(_slot) asShard;

if(null== counter)

{

counter = newShard()

{

Owner = Thread.CurrentThread

};

Thread.SetData(_slot, counter);

lock(_thisLock) _shards.Add(counter);

}

counter.Increase(amount);

}

每个分片都是一个InterlockedCounter，因此Count可以查看所有计数器的最新值，从而避免计算不足。

privateclassShard : InterlockedCounter

{

publicThread Owner { get; set; }

}

}

完整的代码，在完成的线程之后清理起来有点复杂，可以在这里找到。

结论

当并发问题减慢代码时，有时使用System.Threading.Interlocked提供的更复杂的并发操作将无法提高性能。问题是太多的参与者试图同时访问相同的值。

在这个特定的例子中，这是一个玩具问题，几乎不会影响应用程序的整体性能。但是，这种分解战斗价值的技术也可以应用于更大的问题。当操作顺序不影响结果时，使用纯关联运算（如加法和乘法）计算值时，分割值尤其容易。