多处理器优化：优化对大型数据集合的并发访问

服务器应用程序的成功与否迟早将归结为性能。但是，服务器应用程序中的性能不完全等同于纯粹的速度。您还必须考虑并发性 — 即您能够同时为多少个客户端提供服务。实际上，对于服务器而言，并发性通常要比纯速度更为重要，尤其是对带有许多 CPU 的高端硬件而言。具有低并发性的服务器应用程序只是无法利用多个 CPU（无论该应用程序有多么快）。

我不知道是否有简单明了的用于优化并发性的处方，但多年以来，我已经形成了大量能够提供巨大帮助的窍门。其中一个窍门可以很好地同步对大型集合中的对象的访问，而不会牺牲并发性。本文将演示我的技巧。首先，我将说明一个小型多线程示例程序，该程序演示了并发访问大型集合中的对象的需要。然后，我将开发一个能够解决该问题的可重用类，并且将比较得到的性能数值。作为一项附加的好处，该示例程序将包含一组便于使用的、用于创建和同步线程的类（当然是可重用的）。

示例代码可在 Windows 98 Second Edition、带有 Service Pack 6a 的 Windows NT 或带有 Service Pack 1 的 Windows 2000 上运行（它或许可以在其他版本上运行，但以上版本是我测试过的全部版本。）而且，该代码要求有带有 Service Pack 4 的 Visual C++ 6.0。

请注意，我使用了与 Windows 编程界规范稍微不同的编码风格。具体说来，我使用标识符前缀 k_ 表示常数和枚举，使用 g_ 表示全局变量、静态全局变量以及静态类成员，使用 m_ 表示类成员。

构造块

在分析该示例程序的实质内容之前，我将讨论它包含的一些构造块。第一个构造块是 Exception 类（参见图 1），它主要用于将 Win32 API 错误转换为 C++ 异常。对于该类实在没有太多好说的，所以我不会向您一一介绍它的所有细节。（如果您感兴趣，请通过本文顶部的链接下载完整的示例源代码。）Exception 的一项有趣的功能是：getErrorMsg 方法使用 Win32 API FormatMessage 获取与 Win32 错误代码对应的文本错误说明。这使得跟踪 Win32 API 错误变得更为快速。例如，与只是看到错误代码 120 不同，它将告诉您“This function is not supported on this system”（该系统不支持这一功能）。

Timer 类（参见图 2）用于对示例程序测试运行进行计时。它同样是一个极为简单的类，甚至比 Exception 还要简单。它完全是内联的，因此它只有一个头文件。Timer 在其构造函数中调用 Win32 API GetSystemTimeAsFileTime 以获取开始时间，然后再次在 stop 方法中调用它来获取结束时间。getXxx 方法将二者之间的差值转换为多种容易感知的单位。

CritSec 类包装了一个临界区（参见图 3）。首先，有些人发现该类是如此简单，以至于他们不相信它有用。然而，第一印象可能是靠不住的。该类之所以重要，有以下三个原因。首先，它使临界区成为面向对象的，从而使其在 C++ 程序中看起来非常合适。这是非常有用的，因为现代 C++ 使用与 C 极为不同的编程风格，因此直接使用 C 函数会强迫程序员频繁改变编程风格，从而导致代码难于阅读和维护。关于这一点，没有比围绕线程同步对象进行的错误处理更为明显的了。CritSec 将 Win32 API 错误转换为异常（使用 Exception 类），从而产生了干净得多的代码。

其次，CritSec（与不久将讨论的 LockKeeper 结合）使临界区具有异常安全性。换句话说，您必须确保在引发异常后，没有任何临界区处于锁定状态。这对于在从错误状态中恢复时避免死锁是非常重要的。

第三，通过在类中包装临界区，您可以使其独立于平台。跨平台的实现超出了本文的范围，但是可以用 Unix 上的 POSIX 线程 API 实现这一相同的 CritSec 类接口。

LockKeeper 模板类（同样参见图 3）与 CritSec 结合使用。我通常不是直接调用 acquire 和 release 方法，而是在堆栈上实例化一个 LockKeeper 实例。构造函数为我调用 acquire 方法，而当 LockKeeper 离开作用域时，析构函数将自动调用 release 方法。这可以消除一个代码行，但更为重要的是，它确保了在锁被占有时引发的异常能够在该异常传播到 LockKeeper 实例的作用域以外时，自动释放该锁。

注意，因为 LockKeeper 是一个模板，所以可以在任何其 acquire 和 release 方法不带参数的类上使用它。这非常方便，因为在真正的多线程应用程序中，将会有许多个这样的类 — Mutex、Semaphore 以及其他类（您不久就将看到）。

与前面的构造块类不同，要向您解释清楚 Thread 类有一点儿困难（参见图 4）。对于那些了解 Java 的读者而言，它非常像 Java Thread 类，不同之处在于它不支持单独的 Run 接口 — 它要求直接从 Thread 派生。

对于那些不熟悉 Java 的线程机制的读者而言，以下是您使用 Thread 类的方法。首先，从 Thread 派生一个类（假设为 MyThread），然后重写纯虚拟方法 run。在该方法中放入您希望新线程执行的代码。然后，构建一个 MyThread 类型的对象，并调用 start。此时，新的线程将开始在您的 run 方法中执行。如果您希望另一个线程等待至 MyThread 线程退出，请调用 wait。（当然，您绝不能从 run 方法内部调用 wait 方法。）

以这种方式对线程进行建模的优点之一是：它使得与线程的通讯变得容易多了。要将信息传递给线程，您需要做的全部事情就是将这些信息存储在您的 MyThread 类的数据成员中。我通常在构造函数中完成这一工作。要向您的线程外部传递信息，只须完成相反的工作 — 在您的 run 方法中，将信息存储在您的 MyThread 类的数据成员中，然后实现 getter 方法以使其他线程可以获取该数据。

很重要的一点是您的线程类的任何数据成员都是私有的，并带有用于访问它们的 getter 和/或 setter 方法。这是因为将很可能从多个线程中访问这些数据成员，因此您需要使用封装所提供的控制来保证正确的线程同步。

Thread 类的实现有几个难点（参见图 5）。首先，请观察私有和静态 entryPoint 方法：

static unsigned __stdcall entryPoint(void* pArg);

该方法是传递给 _beginthreadex API 以启动线程运行的函数。您不能传递一个非静态方法（如 run），因为非静态方法的调用约定与 _beginthreadex 预期的调用约定不同。（它不知道如何传递该指针。）但是，被声明为 __stdcall 的静态方法将完全适用。对 _beginthreadex API（它位于 start 方法中）的调用会传递一个指向 entryPoint 方法的指针和 this 指针。当新的线程开始在 entryPoint 中执行时，pArg 参数将是传递给 _beginthreadex 的 this 指针。然后，entryPoint 方法将它转换为 Thread* 并调用 run。虚拟方法的魔力将接管工作，并将执行传递给您的 MyThread::run 方法。

entryPoint 方法还具有另外一个用途。它为最可能的异常类型提供最后的异常处理程序。这可以确保您在某个环节恰好出错时，能够获得有用的错误消息。

Thread 类的另外一个微妙的方面值得提一下。在 start 方法中，您将注意到线程是在挂起状态中创建的，然后线程 ID 和句柄被赋给类成员。最后，线程被恢复执行。这一挂起是必要的，可防止出现竞争情形。假设新线程是在运行状态中创建的。如果新线程在 run 方法中比较早地调用了 getId 或 getHandle，则它可能在 start 方法已经进行赋值之前访问这些成员。

示例服务器程序

有关示例程序的预备知识已经足够了。既提供一个实际的服务器应用程序示例，同时又要使其足够简单以便在一篇短文中加以介绍，这是很困难的，因此此处显示的示例有一点儿人为的痕迹。实际上，它根本不是一个真正的服务器应用程序。但是，我已经尝试虚构了一个可信的服务器应用程序方案，以便您能够参照实际方案来观察该应用程序，而无须运用太多的想象力。

示例 ConcurrencyDemo（或简称为 CD）模拟了简单的内存中数据库。DBEntry 类（参见图 6）代表该数据库中的一个项，由一个数值键和一些文本组成。客户端可以读取与给定键关联的文本，也可以更新特定键的文本。对象个数在启动时确定。

CD 示例包含一个辅助线程池。在实际情况下，这些线程将通过某种远程调用机制（如 TCP、DCOM、IIOP 或 SOAP — 如果您恰好正在使用尖端技术的话）获得来自客户端的请求。在该示例中，请求的生成经过了模拟，而不是真实的。

CD 示例采用了以下命令行参数：数据库中的项数、要执行的测试迭代的次数以及要使用的辅助线程的数目。如果指定了多个线程数目，则该程序将用每个数目运行一次测试。

当 CD 启动时，它将首先解释其命令行参数，然后创建数据库（参见图 7）。接下来，CD 将打印输出标题。（如果它在您看来不像是合法的 C++，则您尚未学习有关便利的 C 预处理器功能的内容。该预处理器将所有仅由空格分隔的字符串文字连接在一起。）最后，CD 针对命令行上指定的每个线程数目调用 doTest 两次。第一次测试以最明显的方式同步对数据库的访问。第二次使用我的经过优化的技巧。为了确保得到有用的错误消息，主函数还会捕获最可能的异常类型。

图 8 显示了 doTest 函数。该函数开始时创建了一个线程池，它是指向 WorkerThread 对象的指针的向量。实际上，更准确地说，它是 auto_ptr 对象的向量，以便在销毁该数组时，还将删除所有 WorkerThread 对象。在下一部分中，我将详细讨论 WorkerThread 类。

接下来，doTest 创建一个计时器来对测试进行计时，启动每个线程运行，并且等待各个线程以确保它们全部完成该测试。最后，DoTest 停止计时器并打印结果。请注意，输出格式有一点儿奇怪。它采用逗号分隔值 (CSV) 格式。这样，我可以将输出重定向到具有 .csv 文件扩展名的文件中，并将其直接导入 Microsoft Excel。这可以快速而轻松地创建漂亮的图表。

WorkerThread 类

WorkerThread 类（参见图 9 和图 10）显然派生自 Thread。构造函数获得一串输入参数，并且只是将其存储到数据成员中以便供以后使用。run 方法使用其中前三个参数来控制循环。这在开始时可能看起来有点奇怪，但其意义在于尽可能均匀地将迭代总次数分配到所有线程中，即使迭代次数并不能由线程个数整除。如果发生这种情况，则某些线程将比其他线程多迭代一次。

在每次迭代中，run 方法都会调用 getRequest 以获取下一个请求的参数。在实际程序中，getRequest 将通过某种网络传输机制来从客户端获取输入。为使讨论简单化，我编写了 getRequest 以生成随机请求。为了防止这一方法使结果失真，我不得不使用我自己的随机数生成器。这是因为编译器的随机数生成器使用全局种子，因此需要一个临界区。这会引入额外的线程同步，从而掩盖我试图观察的结果。我的随机数生成器使用线程本地种子（存储在 WorkerThread 类中），因此不需要同步。

根据请求类型的不同，run 方法随后会调用 doUpdate 或 doRead。这些方法中的每个方法都会获取一个对所指示的数据库项的引用，锁定该引用，执行请求的操作，然后返回。请注意，使用了 LockKeeper 对象来直接锁定数据库项。这是一个示例，说明了如何使用 LockKeeper 模板来锁定任何具有不带任何参数的 acquire 和 release 方法的对象。稍后，我将详细讨论 DBEntry 类上的 acquire 和 release 方法。

还请注意，doUpdate 和 doRead 方法调用了 simulateWork 方法。在实际的服务器中，更新和读取（尤其是更新）会引起一些开销。为了使 doUpdate 和 doRead 占用足够的执行时间来显示期望的结果，我需要添加对 simulateWork 的调用。在我用作基准测试的计算机上，这会使 doRead 和 doUpdate 的执行时间分别增加大约 20 和 200 微秒。（这里需要称赞一下 Visual C++ 优化器：我必须向 simulateWork 添加一个全局访问，以防止该方法以及对它的调用被完全优化掉。）

在 doRead 和 doUpdate 中有一个难以发现的微妙之处。如果您大体考察一下 CD 代码，您会发现每当将字符串作为 in 参数传递给方法时，该参数的类型都是 const 字符串引用，而每当从方法中返回字符串时，返回类型都是字符串。然而，DBEntry 上的 setValue 和 getValue 方法却获取并返回 const char*。您可能认为这只是我在 C++ 标准库出现之前的多年 C 和 C++ 编码经验所遗留下来的习惯，但这完全是有意的。两个字符串对象可以包含对同一字符串数组的引用，以便优化内存使用率，减少复制字符串所花的时间。如果 setValue 获取 const 字符串引用并将其赋给 m_value 成员，则该成员将仅包含对传入的字符串的引用。这可能导致两个线程同时访问同一字符串数组。因为字符串类未经过同步，所以这可能导致堆损坏。我的解决方案是改为传递（或返回）const char*。这会在锁被 DBEntry 对象占有时强制进行字符串复制。进行复制之后，其他线程就可以接触 DBEntry 而不会造成损害。

问题和可能的解决方案

既然您已基本了解该示例程序所做的工作，那么让我们考察一下下面的问题：如何同步对数据库项的访问？您不能允许辅助线程杂乱无章地获取和设置数据库项，因为产生的竞争情形在最好的情况下会导致不正确的结果，在最坏的情况下会导致服务器崩溃。

最简单且最明显的解决方案是使用单个临界区。任何要读取或更新某个项的线程都必须首先获取临界区。在许多情况下，这是最适当的解决方案。然而，请注意它会过分地同步线程。两个正在访问不同项的线程根本无须进行同步，但使用单个临界区却无论如何都会将它们同步。如果多个线程经常需要同时访问不同的项，则这将在您的服务器中导致瓶颈，并且限制它的并发性。

另一种解决方案是在 DBEntry 本身内部嵌入一个临界区。该解决方案具有两个讨厌的问题。首先，它会消耗数量惊人的系统资源。每个临界区都使用 24 字节的内存以及一个事件内核对象。因此，如果您的数据库中含有 1,000,000 个项，则该方法将消耗 24MB 内存和 1,000,000 个事件，而这一切仅仅是为了进行同步！这将不会受到您的客户的欢迎。

该方法的另一个问题是您无法使用它来同步项的删除。（这在该示例中不是一个问题，但在实际情况中通常是一个问题。）要删除某个项，您需要锁定它，然后删除它。然后，另一个正在等待读取该对象的线程将获取驻留在已删除的内存中的临界区。这一点绝对不会受到客户的欢迎。

我的针对这一问题的解决方案是封装在 CritSecTable 类中（参见图 11 和图 12）。该类的接口看起来几乎与 CritSec 的接口完全相同，不同之处在于 acquire 和 release 方法采用 void* 参数。

要使用该类，需要将一个 CritSecTable 实例与您希望对其进行并发访问的大型集合（在这种情况下，即内存中的数据库）相关联。当您希望锁定或取消锁定某个项时，需要分别在 CritSecTable 对象上调用 acquire 或 release，并将该项的地址作为 void* 参数进行传递。有关示例，请参见 DBEntry 类的 acquire 和 release 方法的实现（如图 13 所示）。（我已经实现了这些方法，以便它们可以为整个数据库使用单个临界区，或者使用一个 CritSecTable，具体取决于全局标志 g_useSingleCritSec 的设置。）

CritSecTable 在内部维护了一个 CritSec 实例数组（在我的实现中，包含 256 个实例）。当您调用 acquire 或 release 时，它将根据该 void* 参数计算一个哈希，然后使用该哈希对数组进行索引，并在相应的 CritSec 对象上调用 acquire 或 release。这意味着对于任何给定的数据库项，您都将始终使用同一个 CritSec 对象，从而保证您能够保持正确的同步行为。

如果两个线程试图同时锁定不同的项，则其中一个线程阻塞另一个线程的可能性非常低（二百五十六分之一的可能性）。当然，随着试图对数据库进行并发访问的线程数的增加，其中一个或多个线程被阻塞的可能性也将增加。然而，在 Windows 中这通常不是一个问题。运行 Windows 的计算机很少具有八个以上的 CPU，并且（据我所知）上限是 32 个。如果您的服务器应用程序正在使用 I/O 完成端口（正像它应该做的那样），则在任意给定时间，您的服务器中正在运行的线程数目将接近于 CPU 的数目。（注：有关 I/O 完成端口的讨论超出了本文的范围，但最近几年来 MSDN Magazine 中出现过几篇有关该主题的好文章。下面的一个参考资料可供参阅：Windows Sockets 2.0:Write Scalable Winsock Apps Using Completion Ports）

我选择使 CritSec 数组的长度为 256，因为它有利于使用一个非常简单但有效的哈希函数。在此情况下，该哈希函数只是简单地对 void* 的字节进行 XOR 运算，从而得到单个无符号 char。我已经花费了一些时间，针对 void* 的长度为四个字节、八个字节的情况以及一般性情况（针对您恰好在具有 7 字节指针的系统上运行 Windows 的情形）优化该哈希函数。在 32 位 Intel 系统上，Visual C++ 编译器将哈希方法的 32 行 C++ 代码简化为只有六条汇编语言指令。

如果您的应用程序将具有数量大得多的线程试图同时锁定不同的项，则您可能需要更大的 CritSec 数组，但您将需要更为复杂的哈希函数来对其进行哈希运算。

并发性结果

我在具有一个 CPU 的 500 MHz Pentium III 计算机上以及具有四个 CPU 的 550 MHz Pentium III Xeon 计算机上运行了 CD 示例。在每种情况下，我都使用不断增加的辅助线程数目运行了两个测试（一个使用单个临界区，另一个使用 CritSecTable）。图 14 显示了在单 CPU 计算机上使用一到八个辅助线程运行测试的结果。

图 14 单 CPU 计算机上的结果

使用单个临界区时，随着线程数目的增加，用于执行固定次数迭代的时间显著增加。这是因为单个临界区使得线程过于频繁地进行上下文切换，并且 CPU 花费过多的时间在内核模式下执行上下文切换代码。

您可以在 Windows NT 或 Windows 2000 上通过 Performance Monitor 应用程序证实这一点。在 Windows NT 上，您可以在 Start | Programs | Administrative Tools 下找到它。从 Edit 菜单中选择 Add to Chart，将性能对象设置为 System，然后将以下三个跟踪标志添加到您的图表中：% Total Processor Time、% Total Privileged Time 和 Context Switches/sec。在 Windows 2000 上，概念是一样的，但 Redmondtonians（指 Microsoft）已经改变了组件的位置。Performance Monitor 位于 Control Panel 中的 Administrative Tools 下面。单击工具栏上的大加号，将性能对象设置为 Processor，再添加跟踪标志 % Processor Time 和 % Privileged Time。然后，将性能对象设置为 System 并添加 Context Switches/sec。

当您运行 ConcurrencyDemo 时，您将看到在使用大量辅助线程的单个临界区测试期间，特权时间量和上下文切换的次数都大大增加了。与此相反，使用临界区表的测试将执行少得多的上下文切换，从而得到相当稳定的执行时间，如图 14 所示。

图 15 多 CPU 计算机上的结果

四 CPU 计算机上的结果更加令人吃惊（参见图 15）。使用单个临界区时的趋势在最初因为线程数从一个增加为两个而增加以后，变得相当稳定。请注意此处与单 CPU 计算机上的单个临界区情形完全不同的行为。四 CPU 计算机无须疲于应付上下文切换的原因在于，在多 CPU 计算机上，临界区具有一个“旋转计数”。这意味着当一个线程试图获取已经锁定的临界区时，该线程将在循环中“旋转”一会儿，检查该锁是否已被释放，然后进入休眠状态。这是有利的，因为休眠会导致上下文切换，其代价要比浪费在旋转上的周期更大。

使用临界区表时，随着您使用的线程数从一个增加到四个，执行时间会急剧下降（70% 以上）。这表明全部四个 CPU 正在并行工作，以获得最佳的并发性。（实际上，理论上的最佳并发性将显示执行时间下降 75%，但完全按线性比例下降是很罕见的。）请注意，随着您使用的线程数超过四个，性能将会因为上下文切换更为频繁而下降。这表明了使用 I/O 完成端口以使正在运行的线程数非常接近 CPU 个数的重要性。

小结

本文介绍的用于提高并发性的技术具有许多应用。我首先在一个服务器应用程序上设计了这一技术，该应用程序使用 C++ 智能指针并通过引用计数对象实现了垃圾回收。我用临界区表保护了该引用计数。（您可能认为我可以使用 InterlockedXxx 系列函数达到这一目的，但是将引用计数递减到零以及删除该对象的操作必须是需要临界区的原子操作。）

还可以使用临界区表来克服 CD 示例中数据库的一个主要局限，即无法以线程安全且具有高度并发性的方式在该数据库中添加或删除项。创建具有高度并发性的集合是一项艰难的任务，并且超出了本文的范围，但在我已经发现的问题的一个解决方案中，临界区表是一个重要的组件。

我希望您将在自己的服务器应用程序中找到这一技术的用武之地。如果您确实这样做了，那么我非常愿意了解相关情况。

相关文章，请参阅：

Write Scalable Winsock Apps Using Completion Ports

有关背景信息，请参阅：

Advanced Windows 作者 Jeffrey Richter (Microsoft Press, 1997)

Ian Emmons 是 Persistence Software Inc. 的一名软件架构师 (http://www.persistence.com)。他专门致力于高性能服务器应用程序的设计。如果希望与他联系，可发送电子邮件至：ian@persistence.com。

原英文页面