performance - 实际应用中是否使用了宽松的数据结构？

Question

我正在学习并发数据结构，并且在偶然的数据结构（例如k松弛队列，堆栈，计数器等）上遇到了广泛的研究文献。例如，请参见此处

https://github.com/cksystemsgroup/scal#data-structures

或在这里

http://www.faculty.idc.ac.il/gadi/MyPapers/2015ST-RelaxedDataStructures.pdf

这个想法是，宽松的数据结构提供了较弱的保证（例如，第k个FIFO队列的出队操作可以自由给出前k个元素中的任何一个）。理想情况下，宽松的数据结构比严格的数据结构提供更好的性能。

问题是，据我所知，这些数据结构仅在某些微基准上（如上面的第一个链接）进行评估，仅测量数据结构操作的纯性能/吞吐量，而没有研究松弛的影响整体应用程序设计和性能。

您是否曾经在实际应用程序中使用过这种宽松的数据结构，或者您是否可以想象将宽松的数据结构插入应用程序以获得性能提升？还是那些数据结构纯粹是学术活动？

Answer 1

快速回答

这是一个类比的快速解答。松弛结构可与正常并发结构相比较，就像正常并发结构可与正常非并发结构相比较一样。

在应用程序中，数据结构的大多数用途是普通形式的非当前用途，这是因为它们没有被共享，或者因为某种类型的粗粒度锁定足以共享它们。它们提供了一个简单的API，并且即使在使用粗粒度锁定时存在并发访问的情况下，也易于推理。举一个具体的例子，您可能会发现20次到100次使用普通Map实现的每种用法。

这不会使ConcurrentMap没有用！在性能上，在5％的使用位置中可能没有真正的替代品！

同样，您通常只会在那些地方找到非松弛的并发结构，但是可能会有5％（因此现在ConcurrentMap使用总量的0.25％）可以从放松的结构中受益（在推理系统时会付出额外的复杂性，并且可能会在理论上改变客户的服务订单）。

长答案

我认为这里有两个单独的隐含问题：


在实际使用中，宽松的数据结构实际上比非宽松的数据结构快吗？
鉴于相关数据结构的保证较弱，在实际应用中是否真的有用？


我可以谈谈他们两个人的个人经历。在我还不知道它们被称为放松结构之前，我就使用过“松弛结构”。

松弛结构实际上更快吗？

首先，也许您是在问松弛结构实际上比非松弛结构快吗？

简单的答案是“是的，但仅在并发访问的极端情况下”。

微基准已经显示出性能的极限。通常，您会拥有一个可以从多个线程连续访问（即占空比接近100％）的结构。在这些极端的竞争中，宽松的数据结构可能显示出比其非宽松表亲要大一个数量级的改进。但是，您必须意识到，绝大多数结构不是以这种方式访问​​的。即使是已经在使用并发数据结构的结构（在Java中认为是Map），通常也很少以占总执行时间的百分比进行访问，并且与性能1相比，使用并发结构对于正确性和高西格玛响应时间而言更为必要。

通常没有

就是说，仅仅因为应用程序中的绝大多数结构不需要更高的并发性能，这并不意味着它毫无用处：少数需要它的结构（如果有的话）可能占总访问量的很大一部分。我的意思是，如果您看一下代码级别：“我的应用程序中需要多少个地图对象声明需要一个快速的并发结构？”，那么答案很可能是“不多”-但是如果您查看运行时级别：“我的应用程序中有多少次对映射对象的访问需要快速并发结构？” -那么答案可能是“很多”。这取决于您是通过“在代码中使用”还是“在运行时使用”来加权。

有时候是的

一旦开始调整高度并发的应用程序，您很可能会在某个时候遇到并发瓶颈。即使您的应用程序非常并行-例如并行处理许多独立的传入请求，您通常也希望引入某种类型的共享状态以进行缓存，日志记录，安全检查，或者仅仅是因为您的应用程序确实具有一定数量的共享可写状态。无论您在此处使用哪种结构，都可能确实遭受高额竞争。

作为第一个问题的最后一点：很多问题还取决于您使用的硬件。竞争结构的典型行为是，在并发访问下，吞吐量趋于趋于平坦，而与访问该结构的核心数量无关，即，与并发无关，该结构的最大吞吐量为X。通常，这实际上是最好的情况：您可以改为以中等数量的并发达到峰值吞吐量，然后总吞吐量下降。

这取决于硬件

其影响取决于您的硬件。如果您使用的是具有4个内核的单路开发机器，那么这种行为就不太可怕了。您可以将并发部件有效地降低到1个内核，但是仍然剩下最大可用功率的25％（一个内核）。因此，如果负载的固有并发部分是总负载的10％，那么尽管有争用，您仍将达到总吞吐量的ConcurrentHashMap。当然，您可以重新组织应用程序。然后，您可以部署到生产环境中，并在2插槽18核机箱上运行，它看起来像1 / (0.9 + 0.1 * 4) = 0.77 = 77%-即由于并发瓶颈，您获得的性能还不到理想性能水平的四分之一。那是个问题。

这就是并发扩展的“简单”视图，其中竞争部分的性能是恒定的-实际上，争用的增加可能会降低性能，从而使性能变差。

摘要

因此，长答案与短答案的完成方式相同-是的，高度并发应用程序中的某些位置可以受益于争用性能更好但数量很少的结构。您必须首先删除发生虚假共享的所有位置，存在非竞争瓶颈的位置，然后找到真正共享并可能受益的位置。

松弛结构可以在实践中使用吗？

绝对没错。这是简单的部分。很多时候，您需要的结构提供的担保要比所需的基础结构弱。例如，如果您将要存储一堆没有重复的对象，并且没有特定的顺序，则可以使用数组/向量或链接列表或类似集合的结构。每个选择都具有相对于其他选择的优势，但在其他情况下却具有一些劣势（例如，数组允许对给定索引的任何元素进行恒定时间访问，但不能在末尾插入其他元素而无需支付< cc>费用）。

您通常不会发现担保比现有担保更弱的结构，因为在并发之外，实际上没有比担保较弱的基本结构还要快的结构。尝试一下-选择一个“集合” API，它在数组，链接列表，哈希表，树等中具有最低的公分母保证。即，它不需要在中间快速插入，它不需要无法按元素提供快速搜索，不提供快速索引等功能-您可以使任何基本操作都更快吗？

这种情况很常见：浏览源代码中您最近编写的所有内容，并检查如何在Java中使用1 / (0.9 + 0.1 / 36) = 0.22 = 22%或在C ++中使用O(n)或仅使用纯数组：在每种情况下，哪种高性能您实际上需要进行哪些操作？通常，您只是持有元素的集合并在以后进行遍历-就是这样！

一旦引入了并发性能的新轴，就可以使用较弱的保证来建立更快的结构。数组是有问题的，因为要保持确切的插入顺序，您总是总是对某种类型的共享大小变量感到满意。链接列表存在问题，因为头/尾节点争用等等。

这里有一个结构较弱的地方。例如，不提供FIFO插入/迭代顺序，不提供相等搜索的快速搜索等“坏”元素。这种削弱有很多用处。

具体来说

这是我在高性能并发系统中实际使用或看到过的放松结构的几个地方：


对于统计信息收集：高并行处理大多数独立请求的系统通常可以很好地扩展，因为这些请求不会共享太多可变数据。但是，一旦开始收集系统范围内的细粒度统计信息，便有一个争用点。通常，您不需要任何类型的FIFO顺序即可进行统计，也不需要可搜索性（无论如何在收集点）-因此，进程内统计收集器代码显然是使用宽松结构的地方。
对于日志记录：与上面的统计方法一样，许多系统都具有全局日志记录功能，这可能会成为争用点。通常，您希望日志消息按FIFO顺序显示，因为混乱的消息非常混乱，但是您可能不太在意日志中来自独立线程的消息的顺序，或者您可能确切知道哪些消息需要在FIFO中发生。订购其他线程。在这里，放松的结构再次自然而然。
处理或重新分配大量传入请求流的一般问题。想象一下任何Web服务器做什么-它处理大量传入的任务。通常，这些请求来自许多不同的用户，并且是否按照请求到达的确切顺序处理这些请求并不重要。但是，有一些排序情况确实很重要-通常是在同一用户或会话的请求中（例如，为使用List提交一些更改然后发出vector重新加载页面的用户成像：她希望请参见POST中反映的与先前GET相比的更改）。因此，处理请求的许多前端结构将放宽对性能的常规订购要求。




0所谓的普通并发结构，是指像POST这样的结构，这些结构被设计为在并发下具有更好的性能，但通常保留其通常的顺序保证等。也就是说，它们与现有API的边界尽可能地并发。

1诚然，这掩盖了平均性能与其他“长尾”性能问题之间的差异。即，平均而言，某个结构可能很少被访问，但是在某些情况下，访问可能会猛增，并且在此特定负载下可能成为瓶颈。