数据库样式的分片能否提高多线程应用程序的性能？
我正在研究一个解决数独谜题的示例应用程序。该应用程序可以在多个线程上快速解决难题。我想跟踪已经检查了多少拼图板。我需要一个可能每秒增加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尽可能简单：
public class UnsynchronizedCounter : ICounter
{ private long _count = 0;
public long Count => _count;
public void Increase(long amount)
{
_count += amount;
}
} |
所述计数属性返回私人_count，并且增加（）方法增加了私人_count。
由于UnsynchronizedCounter的开销为零，因此它可以比任何其他计数器更快地计数，但只能在一个线程上计数。
如果多个线程同时调用Increase（），则由于竞争条件，最终计数将低于预期。维基百科对种族条件以及它们如何导致错误有很好的描述。
LockingCounter
该LockingCounter通过持有一个锁，同时读取和写入防止竞争条件_count。
public class LockingCounter : ICounter
{ private long _count = 0;
private readonly object _thisLock = new object();
public long Count
{
get
{
lock (_thisLock)
{
return _count;
}
}
}
public void Increase(long amount)
{
lock (_thisLock)
{
_count += amount;
}
}
} |
锁定防止了漏报问题UnsynchronizedCounter遭遇，但正如上面的基准测试结果表明，LockingCounter比慢得多UnsynchronizedCounter。
InterlockedCounter
System.Threading.Interlocked为多个线程共享的值提供原子操作。为了获得更好的性能，C＃的并发集合使用互锁操作来实现 ConcurrentStack之类的集合。在每种情况下，互锁操作都不能用于替换锁定，但在增加计数器的简单情况下，它们可以。InterlockedCounter使用Interlocked.Add（）以永远不会被低估的方式增加计数，并且在等待获取锁时不会阻塞。
public class InterlockedCounter : ICounter
{ private long _count = 0;
public long Count => Interlocked.CompareExchange(ref _count, 0, 0);
public void Increase(long amount)
{
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（）分配一个新的线程本地存储槽。这将为每个线程创建一个存储计数器分片的位置。
public class ShardedCounter : ICounter
{ // Protects _shards.
private readonly object _thisLock = new object();
// The list of shards.
private List<Shard> _shards = new List<Shard>();
// The thread-local slot where shards are stored.
private readonly LocalDataStoreSlot _slot = Thread.AllocateDataSlot();
|
检索计数需要对所有分片中的计数求和。
public long Count
{ get
{
// Sum over all the shards.
long sum = 0;
lock (_thisLock)
{
foreach (Shard shard in _shards)
{
sum += shard.Count;
}
}
return sum;
}
} |
在快速，通用的路径中，增加计数器不需要锁定，只读取和写入其他线程无法读取或写入的值。因此，另一个CPU尝试读取该值并从RAM中获取该值的风险很小。
public void Increase(long amount)
{ // Increase counter for this thread.
Shard counter = Thread.GetData(_slot) as Shard;
if (null == counter)
{
counter = new Shard()
{
Owner = Thread.CurrentThread
};
Thread.SetData(_slot, counter);
lock (_thisLock) _shards.Add(counter);
}
counter.Increase(amount);
} |
每个分片都是一个InterlockedCounter，因此Count可以查看所有计数器的最新值，从而避免计算不足。
private class Shard : InterlockedCounter
{
public Thread Owner { get; set; }
}
} |
完整的代码，在完成的线程之后清理起来有点复杂，可以在这里找到。
结论
当并发问题减慢代码时，有时使用System.Threading.Interlocked提供的更复杂的并发操作将无法提高性能。问题是太多的参与者试图同时访问相同的值。
在这个特定的例子中，这是一个玩具问题，几乎不会影响应用程序的整体性能。但是，这种分解战斗价值的技术也可以应用于更大的问题。当操作顺序不影响结果时，使用纯关联运算（如加法和乘法）计算值时，分割值尤其容易。
