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提供的更复杂的并发操作将无法提高性能。问题是太多的参与者试图同时访问相同的值。

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

  • 发表于:
  • 原文链接:https://kuaibao.qq.com/s/20181023A03U0X00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券