在Erlang/OTP22中，带有WRITE_CONTURRENT选项的ORDERED_SET类型的ETS表的可伸缩性比以前的版本要好得多。在某些极端情况下，与Erlang/OTP 21相比，Erlang/OTP 22的吞吐量有望提高100倍以上。这种改进的原因是一种新的数据结构，称为竞争自适应搜索树(CA tree，简称CA树)。这篇博客文章将让您深入了解CA树是如何工作的，并向您展示比较OTP 21和OTP 22中ETS ORDERED_SET表性能的基准测试结果。
该脚本使您可以方便地在安装了Erlang/OTP22+的您自己的计算机上尝试新的ORDERED_SET实现。
ESCRIPT测量P个Erlang进程将N个整数插入到ORDERED_SET ETS表中所需的时间，其中P和N是ESCRET的参数。仅当ETS表选项ORDERED_SET和{WRITE_CONTURRENT，TRUE}处于活动状态时才使用CA树。因此，人们可以很容易地将新数据结构的性能与旧数据结构(由单个读取器-写入器锁保护的AVL树)进行比较。在Erlang/OTP 22发布之前，WRITE_CONTURRENT选项对ORDERED_SET表没有影响。
当我们在具有两个内核(英特尔(R)酷睿(TM)i7-7500U [email protected] GHz)的开发人员笔记本电脑上运行ESCRIPT时，我们会得到以下结果：
$escript INSERT_DISCOCT_ranges.erl旧1 10000000时间：3.352332秒$ESCRIPT INSERT_DISCOCT_Ranges.erl旧2 10000000时间：3.961732秒$ESCRIPT INSERT_DISCOCT_ranges.erl旧4 10000000时间：6.382199秒$ESCRIPT INSERT_DISCOCT_ranges.erl新1 10000000时间：3.832119秒$ESCRIPT INSERT_DISCOCT_ranges.erl新2 10000000时间：2.109476秒$ESCRIPT INSERT_DISCOCT_RAMes.erl新4 10000000时间：1.66509秒。
我们看到，在这个特定的基准测试中，CA树比旧的数据结构具有更好的可扩展性。使用新数据结构和四个进程时，基准测试的运行速度大约是使用旧数据结构和一个进程时的两倍(机器只有两个核心)。在描述了CA树的工作方式之后，我们将在稍后更详细地查看新的基于CAtree的实现的性能和可伸缩性。
CA树区别于其他并发数据结构的关键特征是，CA树根据在数据结构中检测到的争用程度动态地改变其同步粒度。这样，当许多操作并行发生时，CA树可以避免因使用许多不必要的锁而产生的性能和内存开销，而不会牺牲性能。例如，让我们设想这样一个场景：CA树最初由多个线程并行填充，然后仅从单个线程使用。在此方案中，CA树将在填充阶段调整为使用细粒度同步(当细粒度同步减少争用时)。然后，CA树将更改为在单线程阶段使用粗粒度同步(当粗粒度同步减少锁定和内存开销时)。
CA树中存储的实际项目位于底层的顺序数据结构中。这些顺序数据结构由中间层基节点中的锁保护。基本节点锁具有与其相关联的计数器。当在基本节点锁中检测到争用时，基本节点锁的计数器增加，当检测到无这种争用时，基本节点锁的计数器减少。此基本节点锁的值决定在基本节点中执行操作后是否应该发生拆分或联接。上图顶部的路由节点形成了二叉搜索树，用于指导特定项目的搜索。路由节点还包含锁和标志。这些是在联接基本节点时使用的。关于如何拆分和合并工作的详细信息不会在本文中描述，但感兴趣的读者可以在此CA树状文件(预印本PDF)中找到详细说明。现在，我们将通过一个示例说明CA树如何更改其同步粒度：
最初，CA树仅由具有顺序数据结构的单个基本节点组成，如下图所示：
如果并行线程访问CA树，则基节点的计数器的值最终可能达到指示应该拆分基节点的阈值。基本节点分裂将基本节点中的项划分为两个新的基本节点，并用两个新的基本节点所在的路由节点替换原始的基本节点。下图显示了拆分树根指向的基本节点后的CA树：
只要在基节点锁中存在足够的竞争，或者直到达到路由层的最大深度，基节点分裂过程就会继续。下图显示了CAtree在另一次拆分后的外观：
例如，如果CA树的特定部分比其余部分更频繁地并行访问，则ACA树的不同部分中的同步粒度可能不同。下图显示了另一次拆分后的CA树：
可以连接保持相邻项目范围的两个基本节点。在操作发现基节点计数器的值低于特定阈值后，将触发SUCHA JOIN。请记住，如果线程在获取基节点的锁时没有遇到延迟，则会减少基节点的计数器。
您可能已经从上面的插图中注意到，拆分和连接会导致旧的基本节点和路由节点从树中拼接出来。这些节点占用的内存需要回收，但这不能在它们被拼接出来之后直接发生，因为一些线程可能仍在丢失它们。Erlang运行时系统有一种称为线程进度的机制，ETS CA树实现使用它来安全地回收这些节点。
新的基于CA树的ETS Order_setimplementation的性能已经在一个基准测试中进行了评估，该基准测试衡量了许多情况下的吞吐量(每秒操作数)。基准测试允许可配置数量的Erlang进程在单个ETS表上执行可配置的操作分布。读者可以在TestSuite Forets中找到基准测试的源代码。
下图显示了在采用两个英特尔®至强®CPU E5-2673 [email protected] GHz(总共32个内核，带超线程)的计算机上进行此基准测试的结果。所有场景中的平均集合大小约为500K。有关基准机器和配置的更多详细信息，请参阅此页面。
我们看到，当我们将内核一直添加到64个内核时，基于CA树的有序集(OTP-22)的吞吐量会有所提高，而旧实现(OTP-21)的吞吐量通常会随着进程的增加而变得更差。旧实现的写操作被序列化，因为数据结构受单读写器锁保护。旧版本在添加MORECORE时的速度减慢主要是由于MORECORE试图获取相同的锁时增加的通信开销，以及竞争内核频繁地使彼此的高速缓存线无效的事实。
100%查找场景的图表(上面图表列表中的最后一个图表)乍一看有点奇怪。在这种情况下，为什么CA树的伸缩性比旧的实现要好得多？如果不知道ORDERED_SET表类型的实现细节，几乎不可能猜到答案。首先，CA树对其基节点锁使用相同的读取器-写入器锁实现，就像旧实现用来保护整个表一样。因此，差异不是由于任何锁定差异造成的。默认的ORDERED_SET实现(当WRITE_CONTCURREY为OFF时处于活动状态)的优化主要改进了使用场景，例如，单个进程通过一系列对ets：next/2函数的调用来迭代表中的项。此优化为每个表保留一个静态堆栈。一些操作使用此堆栈来减少需要遍历的树节点的数量。例如，如果栈的顶部包含与传递给该操作的键相同的键，则ets：next/2操作不需要重新创建栈(请参见此处)。由于只有一个静态堆栈可执行，并且可能有许多读取器(由于读取器-写入器锁定)，静态堆栈必须由当前使用它的线程保留。不幸的是，静态堆栈处理在上面100%查找的场景中是一个可伸缩性瓶颈。CAtree实现没有这种类型的优化，因此它不会受到这种可伸缩性瓶颈的影响。然而，这也意味着当表主要被顺序访问时，旧实现可能比新实现执行得更好。10%插入、10%删除、40%查找和40%nextseq1000(1000ETS：NEXT/2调用的序列)场景的单进程情况(上面图表列表中的第二个最后一个图表)是旧实现(仍然可以通过将write_conency选项设置为false来使用)执行得更好的一个示例。
因此，我们可以得出结论，如果表是从多个进程并行访问的，则为ORDERED_SET表打开WRITE_CONCURRENT可能是个好主意。不过，如果您主要按顺序访问表，关闭WRITE_CONTURRENT可能会更好。
CA树实现并不是Erlang/OTP 22中引入的唯一优化，它影响了带WRITE_CONTURRENT的ORDERED_SET的可伸缩性。Erlang/OTP22中还引入了一个优化，即打开WRITE_CONTURREY的ORDERED_SET表中的分散计数器(参见此处)。Erlang/OTP23中引入了在所有表类型中启用相同优化的选项(请参阅此处)。您可以在这里找到比较表的可伸缩性的基准结果，这些表有分散计数器和没有分散计数器。
下面的文章比这篇博客文章更详细地描述了CA树和一些优化(其中一些还没有应用于ETS CA树)。文中还与相关数据结构进行了实验比较。
并发有序集(预印本)的一种争用自适应方法。并行和分布式计算杂志，2018年。康斯坦蒂诺斯·萨戈纳斯和谢尔·温布拉德。
还有一种CA树的无锁变体，将在下面的文章中介绍。无锁CA树在其基本节点中使用不可变的数据结构来显著减少时间范围查询的量，并且类似的操作可能与其他操作冲突。
无锁争用自适应搜索树(预印本)。在第30届算法与架构并行性研讨会(SPAA 2018)的会议记录中。谢尔·温布拉德、康斯坦蒂诺斯·萨戈纳斯和本特·琼森。
本文是第一篇与CA树相关的文章，讨论和评估了ETS的一个原型CA树实现。
使用改编的ETS可伸缩性更强的有序集(预印本)。在关于二郎岛的第十三届ACM SIGPLAN研讨会上(2014)。康斯坦蒂诺斯·萨戈纳斯和谢尔·温布拉德。
如果您对具体的实现细节感兴趣，可以直接查看ETS CA树源代码。最后，如果您想获得更多相关工作的链接，或者想更多地了解适应争用的并发数据结构的动机，那么查看作者的博士论文可能也很有趣。
Erlang/OTP22版本引入了一个新的ETS ordered_setimplementation，该功能在WRITE_CONTURRENT选项启用时处于活动状态。该数据结构(争用自适应搜索树)在许多不同的场景中具有对旧数据结构的卓越可伸缩性，并且其设计使其在受益于不同同步粒度的各种场景中具有优异的性能。