4. 应用程序扩展

可扩展性（Scalability）是软件系统的一种属性，它使系统能够通过按比例增加资源来处理更多的工作，同时仍能维持系统所承诺的服务水平协议（Service Level Agreements，SLAs）。一个可扩展的系统允许你通过投入更多资金（即添加更多硬件）来解决流量或工作量增加的问题；而一个不可扩展的系统，即使增加资源，也根本无法处理负载。

例如，假设有一个后端软件服务，它提供的API对某个应用程序很有用。但同样重要的是，该API必须在保证的时间内返回数据，这样应用程序的用户才不会感受到延迟或无响应。一个没有考虑可扩展性的系统，其表现如下：

随着流量增加，响应时间会急剧上升！相比之下，一个设计为可扩展的系统，其响应时间大致保持不变，即呈现出以下特性：

性能和可扩展性之间有一个关键区别：

• 如果一个系统无法按照所需的服务水平协议满足单个用户的请求，那么它存在性能问题。
• 如果一个系统对单个用户来说表现良好，但随着并发用户数量的增加，服务水平协议受到影响，那么它存在可扩展性问题。

在本章中，我们将探讨可扩展性如何受到以下因素的影响：

• 算法
• 数据结构
• 线程模型
• 本地状态

我们还将研究以下内容：

• 瓶颈
• 系统扩展的不同方式
• 扩展部署

扩展算法

一个问题可以用多种方法解决。不同的算法在时间和空间复杂度方面具有不同的特性。此外，有些算法比其他算法更容易并行化。本节回顾各种算法的复杂度分析，并展示其对稳定性的影响。本节还包含关于分布式算法的内容。

算法复杂度

算法的时间复杂度（Time complexity）定义了算法运行所需的时间与输入规模之间的函数关系。同样，算法的空间复杂度（Space complexity）衡量了算法在特定输入长度下运行所需的空间（内存）大小。这些复杂度指标定义了随着数据量（算法需要处理的输入）的增加，算法所需的时间和空间。

例如，考虑两个数相加的问题。我们需要查看两个整数中的每一对数字，将它们相加，然后处理下一对数字。如果用T(n)表示执行这个加法操作所需的时间，我们可以将其建模为T(n) = c * n：

• 这里T(n)是两个n位整数相加所需的时间。
• c是一对数字相加所需的时间。

直观地说，我们可以感觉到所需时间与数字的位数成正比。

在深入探讨之前，让我们回顾一个关键的数学概念：增长阶数。对于任意两个单调函数f(n)和g(n)，当存在常数 c > 0 和 n0 > 0 时，如果满足：

f(n) ≤ c * g(n)，对于所有n ≥ n0

我们就说 f(n) = O(g(n)) 。

（此图由维基百科提供)

这意味着对于所有足够大的n，函数f(n)的增长速度不会比g(n)快，或者说函数g(n)是f(n)的一个上界。因此，如果我们能以上述形式对T(N)进行建模，就能得到给定n值下算法的最坏情况运行时间！

为了具体说明复杂度对可扩展性的影响，让我们来看两种对整数数组进行排序的方法。冒泡排序（Bubble sort）通过比较数组中相邻的元素，如果它们顺序不对就进行交换。因此，在每一轮外层循环中，最大的元素会 “冒泡” 到数组的末尾。下面是一个用Go语言实现的冒泡排序：

func bubbleSort(array []int) {
    swapped := true
    for swapped {
        swapped = false
        for i := 0; i < len(array)-1; i++ {
            if array[i+1] < array[i] {
                array[i+1], array[i] = array[i], array[i+1]
                swapped = true
            }
        }
    }
}

如你所见，这里有两个遍历整个数组的for循环。如前所述，外层for循环总是将下一个最大的元素推到未排序元素的末尾。让我们用一个示例输入数组[15, 1, 4, 3, 8]来演示。

外层for循环的第一轮：

• [15, 1, 4, 3, 8] -> [1, 15, 4, 3, 8]：因为15 > 1，所以交换
• [1, 15, 4, 3, 8] -> [1, 4, 15, 3, 8]：因为15 > 4，所以交换
• [1, 4, 15, 3, 8] -> [1, 4, 3, 15, 8]：因为15 > 3，所以交换
• [1, 4, 3, 15, 8] -> [1, 4, 3, 8, 15]：因为15 > 8，所以交换

第二轮：

• [1, 4, 3, 8, 15] -> [1, 4, 3, 8, 15]
• [1, 4, 3, 8, 15] -> [1, 3, 4, 8, 15]：因为4 > 3，所以交换

此时数组已经排序，但我们的算法需要完整遍历一次且没有交换操作，才能知道数组已排序。下一轮会将swapped设为false，然后代码结束。在最坏的情况下，我们需要进行n * n次比较，即n²次操作。

假设每次操作需要一个单位时间，那么这个算法的最坏情况复杂度为O(n²)，也就是二次复杂度。

快速排序（Quicksort）是解决排序问题的另一种方法。它是一种分治策略的算法设计，基于选择数组中的一个元素作为枢轴，并围绕该枢轴对数组进行分区，使得枢轴左边的元素小于枢轴值，右边的元素大于枢轴值。下面是一个Go语言实现：

func quickSort(array []int) []int {
    if len(array) <= 1 {
        return array
    }
    left, right := 0, len(array)-1
    // 随机选择一个枢轴并将其移到末尾
    pivot := rand.Int() % len(array)
    a[pivot], a[right] = a[right], a[pivot]
    // 分区
    for i := range array {
        if array[i] < array[right] {
            array[i], array[left] = array[left], array[i]
            left++
        }
    }
    // 将枢轴放到正确的位置
    array[left], array[right] = array[right], array[left]
    // 递归
    quickSort(array[:left])
    quickSort(array[left+1:])
    return array
}

从代码中可以看出，在每一步中：

• 都有对数据的线性扫描。
• 输入被分成两部分，代码对其进行递归处理。用数学形式表示，所需时间如下： T(n) = 2T(n/2) + n 不深入数学细节，这个式子可以简化为nlogn。因此，快速排序的时间复杂度为O(nlogn)。

代码稍微复杂了一些，但我们将复杂度从n²降低到了nlogn。这真的值得吗？为了理解其中的差异，假设你要对一个包含一百万个元素的数组进行排序。冒泡排序在最坏情况下需要10¹²次操作，而快速排序只需要20×10⁶次操作！如果每次操作需要一毫秒，冒泡排序需要超过10天的时间，而快速排序大约5小时就能完成任务！这对算法的可扩展性有极大的提升。

下图展示了各种大O复杂度（Big-O Complexity）所需的操作次数：

因此，分析和剖析代码、识别非最优算法以提高代码的可扩展性非常重要。

分布式算法

有时，即使是最有效的算法，在单台机器上运行时，也无法在合理的时间内给出答案。有时，数据集太大，单台机器的内存或磁盘无法容纳。这个问题的明显解决方案是将任务分配到多台机器上。

然而，这涉及到许多棘手的底层细节，例如：

• 自动并行化
• 通信和协调
• 分布
• 网络和磁盘访问优化

谷歌的MapReduce库是构建通用库的首次尝试，它提供了一个简单的编程模型，可用于解决许多问题。在MapReduce中，程序员主要指定两个方法：

• Map (C) -> [(kx, vy)]：从记录中提取信息，并生成键值对元组。
• Reduce (k, [vx,vy... []]) -> (k,vagg)：归约器（Reducer）获取在映射阶段生成的、按键分组的键值对元组，并生成一个聚合结果。

MapReduce库处理上述复杂的细节，还会对映射器的输出进行分组（混洗和排序），以便在归约器中使用。

分布式计算中著名的 “Hello World” 示例是单词计数。给定一个文件（文档），统计每个单词出现的次数。这里，两个函数的作用如下：

• Map函数处理文档的一部分，将其拆分成单词，并为类似 “This is good.” 这样的句子生成如下类型的键值对元组：[("this", "1"), ("is", "1"), ("good", "1")]。
• 在归约阶段，所有单词会被分组，归约器函数会为每个单词获取一个包含计数1的数组，例如：Reduce(key="this", values = "1", "1")。在这种情况下，归约器只需要统计值数组的长度，就能得到该单词在整个文档中的出现次数！

在Go语言中，有几个库提供类似的分布式处理框架。例如，有一个名为Glow的项目，它提供了一个主/从框架（这里，从节点被称为代理）。代码会被序列化并发送到代理上执行。下面的单词计数实现取自Glow的作者克里斯·卢（Chris Lu）关于Glow的博客（https://blog.gopheracademy.com/advent-2015/glow-map-reduce-for-golang/）：

func main() {
    flow.New().TextFile(
        "/etc/passwd", 3,
    ).Filter(func(line string) bool {
        return!strings.HasPrefix(line, "#")
    }).Map(func(line string, ch chan string) {
        for _, token := range strings.Split(line, ":") {
            ch <- token
        }
    }).Map(func(key string) int {
        return 1
    }).Reduce(func(x int, y int) int {
        return x + y
    }).Map(func(x int) {
        fmt.println("count:", x)
    }).Run()
}

此后，作者一直在致力于一个名为Gleam的项目，该项目旨在为计算流的动态组合提供更大的灵活性。

扩展数据结构

我们为算法存储数据的方式对该算法的可扩展性有巨大影响。不同的数据结构在不同操作上具有不同的复杂度。以下部分将描述各种数据结构以及不同操作的特点。

剖析数据结构

算法的可扩展性选择通常也体现在数据结构的选择上。此表展示了常见数据结构及其操作的时间和空间复杂度：

举个例子，为了阐明最坏情况下的性能，考虑向空的二叉搜索树（Binary Search Tree，BST）和红黑树中插入以下数字：3、4、5、6、7、8、9。

对于二叉搜索树来说，这属于最坏情况，它会退化为链表，如下所示：

这是因为普通二叉搜索树没有重新平衡机制。然而，对于红黑树而言，它会定期进行旋转操作以保持其特性不变。

红黑树是一种自平衡二叉搜索树，在每个节点的每个阶段都必须维持以下特性：

• 每个节点都有颜色，要么是红色，要么是黑色。
• 树的根节点始终为黑色。
• 不存在两个相邻的红色节点（一个红色节点不能有红色父节点或红色子节点）。
• 从根节点到叶子节点的每条路径上的黑色节点数量相同。

每次插入时，插入的初始步骤与二叉搜索树相同，但如果特性发生变化，就会进行旋转以实现自平衡。例如，对于相同的插入操作，红黑树如下所示：

总之，根据你想要对数据结构执行的操作、操作的频繁程度，你可以为特定任务选择合适的数据结构。

在数据结构方面另一个需要考虑的因素是，随着数据量的增加，空间分配会如何变化。例如，数组的长度是固定的，因此其数据结构的可扩展性受限于分配时的大小。相比之下，链表无需预先分配总容量，但它不具备数组O(1)的访问时间特性。话虽如此，有些混合数据结构，如 ArrayList，兼具两者的优点。

此外，对于大量数据，思考如何高效存储信息很有用。例如，如果要为网站上的所有用户存储一个布尔标志，有两种选择：

• 布尔数组：每个标志/用户占用一个字节。
• 位集（Bitset）：每个用户/标志占用一个位。

第一种选择编码稍微简单些，但5000万用户使用第一种方案需要47MB空间，而第二种方案大约只需6MB。如果针对不同用例有多个这样的标志，不难想象位集能让我们在内存中存储更多数据，从而提高性能。

概率数据结构

有时，可扩展性问题仅仅是数据结构必须处理的元素数量过多。这个问题可以通过概率数据结构来解决。考虑在一个集合中找出出现频率最高的K个元素的问题，其中不同值的数量非常大。一种直接的解决方案可能是使用哈希表统计频率，并使用按元素频率排序的最小堆。然而，这需要与集合中元素数量成比例的空间。另一种数据结构是计数-最小草图（count - min sketch）。它内部由一个二维矩阵组成。每个元素通过d个不同且独立的哈希函数映射到d行中的每个位置。然后，这些单独的值会通过一个权重向量进行缩放。矩阵的每个位置都是一个计数器。如下图所示：

每当插入一个新值时，相应的计数器就会增加并汇总。然后，我们可以将其作为最小堆中频率的一个良好估计值。如果频率计数大于堆顶元素的频率，那么就弹出堆顶元素并插入新元素。

另一个相关问题如下：给定大量元素，设计一个函数，该函数从集合中返回一个元素子集，并且返回元素的概率应与集合中元素的总数成比例。在现实生活中，这类问题表现为以下情况：

• 给出销量排名前十的手机型号。
• 给出我们网络中通话次数最多的前十款手机。

处理这个问题的简单方法当然是使用一个大数组，并从这个数组中随机（无放回）选择元素。然而，这意味着需要存储所有元素，根据问题描述，这并不可行。我们需要一种更巧妙的数据结构。

蓄水池抽样（Reservoir sampling）是一种算法/数据结构，可用于处理这类查询。首先，我们创建一个大小等于所需样本大小的蓄水池（数组）。在我们的例子中，假设为10。最初的10个元素直接放入集合中。现在假设我们正在处理第11个元素。此时，新元素进入所选集合的概率为10/11。但这样做会不会对集合中已有的元素不公平呢？以集合中的第5个元素为例，它被选入10个元素的集合的概率为100%（因为有10个位置）。它被选中替换的概率是1/10。因此，该元素从集合中被移除的概率为：第5个元素不在集合中的概率 = 选择第11个元素的概率×选择第5个元素被替换的概率 = 10/11×1/10 = 1/11。

因此，第5个元素在集合中的概率为：1 - 第5个元素不在集合中的概率 = 1 - 1/11 = 10/11。这与选择第11个元素的概率相同！事实上，通过这种方法，数组中的每个索引在集合中的概率都是10/11。因此，如果一个元素出现多次，它的概率与该元素在集合中的基数直接成比例！这可以从处理11个元素推广到处理任意n个元素的情况。

扩展数据

数据在数据库中的存储方式也对系统的可扩展性有着巨大影响。这种影响主要体现在两个方面：

• 如同前面提到的算法和数据结构的复杂度建模一样，元素数量众多可能会导致查找特定元素的效率低下。在关系型数据库中，当搜索查询中的列没有相关索引时，通常就会出现这种情况。
• 数据库存在大量并发更新操作。通常，大多数数据库会优先保证安全性。这意味着在为一个客户端进行更新或读取操作时，其他一些客户端会被锁定。

在本书后面的内容中，我们将更深入地探讨数据库设计和扩展问题。

可扩展性瓶颈

可扩展性瓶颈是指那些导致并行操作串行化（或受阻）的系统因素。存在瓶颈时，系统并行处理更多工作的能力会下降；因此，可扩展系统的一个主要设计目标就是消除这些瓶颈。

为了理解系统瓶颈，让我们来看一些架构师近期遇到的非常有趣的问题：

• C10K问题：在Apache服务器上观察到的一种Web服务器瓶颈。
• 惊群问题（The Thundering Herd problem）。

C10K问题

在21世纪初，工程师们遇到了一个可扩展性瓶颈：Web服务器无法处理超过10000个并发连接。例如，对于Apache服务器来说，其性能与并发连接数成反比。丹尼尔·凯格尔（Daniel Kegel）撰写了一篇论文（http://www.kegel.com/c10k.html ）详细阐述了这个问题，并介绍了他为使一台Web服务器处理10000个连接所做的优化。

Apache（在2.4版本之前）可以配置为以两种主要模式运行：预派生模式或工作进程多进程模式（MPM）。无论哪种方式，系统中每有一个当前处于活动状态的请求，就会占用一个线程，该线程会与其他所有线程竞争CPU和内存等资源。除了资源占用问题，线程数量的增加还会导致上下文切换增多。如果每个请求的持续时间较短，即使吞吐量（每秒事务数 - TPS）很高，并发连接数也不会有太大变化，可能不会达到并发连接限制。然而，如果每个请求的持续时间变为10秒，在相同的1000TPS吞吐量下，将会有10000个连接处于打开状态，系统性能就会急剧下降！

另一个问题是内核中不同网络领域的算法不够优化。例如：

• 每个新数据包都必须遍历内核中的所有10000个进程，以确定哪个线程应该处理该数据包。
• select/poll结构需要进行线性扫描，以确定哪些文件描述符有事件发生。

基于这些经验教训，基于完全不同编程模型（称为事件驱动模型）的Web服务器应运而生。Nginx就是这类Web服务器的一个例子。其关键架构特性如下：

• 进程数量是固定的，通常每个核心对应一个进程。
• 每个进程使用异步I/O处理大量并发连接，且无需创建单独的线程。本质上，每个进程管理一组文件描述符（FDs），每个未完成的请求对应一个文件描述符，并使用高效的epoll系统调用来处理这些文件描述符上的事件。

下图描述了Nginx的架构： 参考：http://www.aosabook.org/en/nginx.html#fig.nginx.arch (opens new window)

惊群问题

假设我们使用缓存来避免一些繁重的计算。例如，在我们的旅游网站上缓存卖家价格。但由于缓存是临时的，通常是按需构建的，这可能会引发一些非直观的问题。

假设我们为所有键设置了5秒的生存时间（TTL）。对于一个非常热门的缓存键（比如纽约 - 洛杉矶航班列表），会有多个请求同时访问缓存，这些请求都会发现缓存中没有该键，进而访问后端服务以将数据加载到缓存中。如果缓存是每个服务器独立的，假设有50台服务器，那么数据会在大约同一时间被缓存在50个地方。你可能觉得这还不算太糟。但问题在于，所有这些缓存会同时过期，导致50个请求同时访问后端！一种避免这种情况的方法是稍微随机化缓存的TTL（例如设置为4.8到5.2秒，而不是统一的5秒）。

惊群情况在操作系统的进程调度问题中也会出现。例如，假设有多个进程在等待同一个事件发生。当该事件发生时，所有有资格处理该事件的等待进程都会被唤醒。最终，实际上只有其中一个进程能够执行工作，但其他所有进程都会先被唤醒并竞争CPU时间，然后再被重新挂起。如果这种情况每秒发生多次，对性能的影响会非常显著。

来源

以下部分描述了系统架构各个方面一些常见的瓶颈来源：http://highscalability.com/blog/2012/5/16/big - list - of - 20 - common - bottlenecks.html

编程

我们已经了解了算法和数据结构的选择如何对性能和可扩展性产生重大影响。除此之外，编程方面的其他瓶颈来源如下：

• 锁（Locks）：让多个线程并行执行任务，结果却因为加锁而变成串行执行，这可没什么意义。在一个线程安全的应用程序中，一致性是必须的，但你需要考虑所加锁的粒度。一个常见的错误来源是将临界区（加锁保护的代码部分）设置得过大，并非所有操作都需要在加锁的情况下完成。
• 死锁（Deadlocks）：在多线程应用程序中，如果线程需要多个资源才能完成工作，就很有可能陷入死锁。当持有锁的线程死亡，而系统若不重启就无法继续运行时，也会发生死锁。为避免这些情况，可以考虑以下几点：
  • 所有线程必须以相同的顺序获取锁。
  • 获取锁时应设置不同时长的超时时间，以避免出现 “世界停止”（stop-the-world）的情况。 数据库通常提供多版本并发控制（multiversion concurrency control），并且超时机制能使数据保持一致状态。然而，如果你使用带超时的锁，就需要确保数据能恢复到一致状态。同样，锁的粒度在这里是一个重要因素。例如，假设我们要更新一个大型对象。我们可以计算出更新后的对象副本，然后在加锁的情况下只更新对原始对象的引用。通常，指针更新是原子操作，所以即使在加锁情况下，对象要么被更新为新版本，要么保持旧版本，不会出现部分更新的情况。
• 读写锁（Reader/Writer locks）：互斥锁（Mutex）和信号量（semaphores）是常见的锁。然而，很多时候，我们只是想避免并发的写 - 写或读 - 写场景，读 - 读并发场景则没有问题。在这种情况下，使用读写锁可以显著提高代码的可扩展性。使用互斥锁或信号量时，锁的状态只有锁定和未锁定两种，并且同一时间只有一个线程能锁定它。但使用读写锁时，有三种可能的状态：
  • 读锁定：多个线程可以在这种状态下获取锁。
  • 写锁定：锁只被一个线程持有，其他线程无法以任何状态获取该锁。
  • 未锁定。 这种锁在多读少写的场景中非常高效。 上下文切换（Context switches）：过多的线程或上下文切换会对性能产生巨大影响，随着系统在管理上下文上花费过多时间，性能会急剧下降。这样的系统也违背了大多数CPU架构和操作系统构建所基于的引用局部性原则。

操作系统

在编写应用程序代码时，我们往往会忽略一个庞大的操作系统生态系统在支持着这些代码。如何利用这些资源是代码可扩展性的关键。这类瓶颈的一些常见来源如下：

• 磁盘相关（Disk-related）：大多数磁盘针对块访问和顺序I/O进行了优化，而非随机I/O。如果你的代码进行大量磁盘寻道操作，会严重降低代码运行速度，并导致一些难以察觉的瓶颈。此外，不同磁盘的性能（IOPS，每秒输入/输出操作次数）特性也不同。尽可能在高I/O场景中使用本地固态硬盘（SSD），只有在数据需要远程传输时才使用网络驱动器。例如，如果你正在编写一个编译器，它需要将输出写入远程驱动器，那么其实你并不需要将中间文件也存储在同一位置！代码可以将最终文件、中间文件（包括日志）存储在不同位置，从而获得更好的性能和可扩展性。代码如何使用操作系统的磁盘缓存（缓冲区缓存，buffer cache）也很重要，频繁且不必要的fsync操作肯定会导致性能下降。
• 网络（Networking）：常见的瓶颈来源如下：
  • 中断请求处理程序（Interrupt Request handler，IRQ）饱和：软中断占用100%的CPU资源。
  • 非最优的TCP缓冲区：TCP使用慢启动算法来避免拥塞堵塞或低带宽链路。在任何时刻，它都会根据拥塞窗口缓冲区大小来决定一次可以发送多少数据包。拥塞窗口越大，吞吐量越高。慢启动算法的工作方式是，初始时设置一个适中的缓冲区大小，每次未检测到拥塞时就增大缓冲区大小。在大多数操作系统中，最大拥塞窗口大小是可调节的，它定义了内核为每个套接字分配的缓冲区空间大小。虽然有默认值，但单个程序可以在打开套接字前通过系统调用覆盖这个值。如果缓冲区大小过小，发送方会受到限制；如果过大，发送方可能会使接收方不堪重负，从而触发拥塞控制。为了实现最大吞吐量，根据所使用的网络链路设置合适的缓冲区大小至关重要。设置缓冲区大小的一个经验法则是，将延迟时间乘以带宽再乘以2（缓冲区大小 = 2×带宽×延迟）。ping工具可以轻松获取往返时间（RTT），也就是延迟的两倍，所以你可以将其与链路带宽相乘得到缓冲区大小。
  • DNS查找等辅助服务：如果你使用内部DNS服务器，需要确保其设置符合所需的规模。
  • 文件描述符限制：在大多数现代系统（如Linux）中，几乎所有东西都可以用文件描述符表示。操作系统会为这些文件描述符设置默认上限，你需要确保将其设置到合适的水平，以避免进程失败。在Linux系统中，你可以使用ulimit命令来获取和设置这些限制，如下所示：

​

内存使用

有时，我们对内存（无论是堆内存还是栈内存）的使用方式过于简单，在某些情况下可能会超出限制，导致内存不足（Out Of Memory，OOM）崩溃。对于堆内存，在非垃圾回收语言的运行时环境中，常见的错误来源是内存泄漏，即分配了内存块但不再有引用指向它们。对于栈内存，如果简单地使用递归，并且数据规模急剧增大，就可能发生内存溢出。

在由运行时管理实际内存分配的语言中，垃圾回收器（Garbage Collector，GC）的暂停是一个可能导致瓶颈的关键系统因素。下面先概述一下垃圾回收过程中通常会发生的情况：

• 通常有几个GC根（GC roots）。这些是程序起始的代码块，可能是主驱动程序或静态对象。
• 每个根都有分配内存的功能。GC运行时会构建一个分配图，每个图组件都以其中一个GC根为起点。
• GC会定期运行进行内存回收，分两个阶段进行：
  • 阶段1：从每个根开始运行，将每个节点标记为已使用。
  • 阶段2：对于那些未分配的内存块，GC回收其空间。 在大多数早期的GC算法中，阶段1涉及一个 “世界停止” 活动，在此期间应用程序实际上被锁定。对于低延迟应用程序来说，这是个问题，因为在 “世界停止” 阶段运行时，应用程序会失去响应。

GC算法已经有了很多改进，人们也在努力减少这种暂停时间。例如，在Go v1.5中，基于1978年Dijkstra首次提出的一个想法（http://dl.acm.org/citation.cfm?id=359655 ）构建了一个新的垃圾回收器（并发、三色、标记 - 清除回收器）。在这个算法中，每个对象要么是白色、灰色，要么是黑色，堆被建模为一个由各种根组成的图。在GC周期开始时，所有对象都是白色的。GC会定期选择一个灰色对象，将其涂黑，然后扫描它指向其他对象的指针。如果扫描到的对象是白色的，就将其变为灰色。这个过程（即GC周期）持续进行，直到没有灰色对象为止。此时，白色对象被认为是不可达的，会被回收。关键的区别在于，标记阶段不需要停止应用程序，它与应用程序的运行是并发进行的。这是通过运行时维护一个不变量来实现的，即没有黑色对象指向白色对象，这意味着不存在悬空指针。每当堆上的指针被修改时，目标对象会被标记为灰色。

结果显示，这种方式可将暂停时间减少多达85%（Alan Shreve的生产服务器图表，https://twitter.com/inconshreveable/status/620650786662555648 ）：

状态丢失

许多网站希望为用户提供个性化的有状态体验。例如，它们会通过cookie（在有限时间内）让用户保持登录状态，并且管理用户的偏好设置。但有时，这种状态会蔓延到后端服务中。系统在称为会话（sessions）的对象中记住上次发生的事情。这些是服务器端的信息块，希望在用户与应用程序的整个交互过程中一直存在。会话为后续请求提供上下文。随着需求的增加，大量状态信息被塞进会话对象中，对这些信息的低延迟访问也变得至关重要。

常见的做法是在服务器本地保存会话状态，并让负载均衡器将用户的所有请求路由到特定服务器。细心的读者会注意到这种结构的一个问题：特定用户的所有请求都需要发送到同一台服务器，这样请求才能利用会话信息。这可能会导致热点问题，即被分配到某台服务器的特定用户的活动量开始比其他用户多很多。如下图所示：

这种设计的另一个问题是容错性：如果上图部署中的Server1崩溃，userA和userB将丢失保存的状态，甚至可能会被注销！这显然不理想。

解决这个问题首先想到的办法是：我们可以将会话存储转移到一个中央位置吗？看下面这个图：

然而，如红色部分所示，这会使公共会话存储成为瓶颈。虽然可以通过复制存储来缓解这个问题，但它仍然不是一个没有瓶颈的设计。

一个没有瓶颈的解决方案是将所有状态都委托给客户端。这使得服务器都变为无状态的：

在这个设计中，客户端会话存储在客户端。服务器是无状态的，这意味着任何服务器都可以随时为任何客户端提供服务；不存在会话亲和性或粘性。会话（状态）信息根据需要传递给服务器。

对于熟悉REST（表述性状态转移，Representational State Transfer）范式的人来说，这就是状态转移（State Transfer，ST）的由来。状态在API请求时从客户端转移到服务器。我们将在第7章 “构建API” 中介绍REST API。

从本质上讲，我们将会话管理委托给了客户端，有效地分摊了成本。这也意味着系统在一定程度上可以随着新客户端的加入自动扩展，因为每个客户端都自带会话管理功能。

和大多数事情一样，这种设计也并非没有代价：

• 客户端需要保留状态，因此客户端的复杂性（处理和存储需求）增加了。

• 每次都需要将状态发送到服务器，这增加了流量，对于移动应用来说，可能意味着用户流量费用增加。

• 多个客户端（例如移动应用和网页端）无法共享状态。

  注意这并不排除其他设计模式的混合使用。例如，购物车等业务对象的关键信息仍然可以保留在服务器端，而频繁变化的/应用程序状态可以保存在客户端。

扩展系统

现在是时候从更高的层面来看待可扩展性了。我们编写好代码并进行部署后，如何对其进行扩展呢？

《可扩展性的艺术》（The Art of Scalability，http://theartofscalability.com/ ）一书中描述了一个非常有用的三维可扩展性模型，以扩展立方体的形式呈现：

每个轴都代表了一种特定的方式，通过这种方式可以增强应用程序，使其在面对不断增加的负载/流量时具备可扩展性。下一节将对它们进行介绍。

X轴扩展

X轴扩展意味着在负载均衡器后运行多个应用程序副本（实例）。如果有n个实例，那么每个实例处理1/n的负载。这是通过增加硬件资源来提高可扩展性的最简单方法。

然而，这种方法存在缺点和局限性：

• 应用程序及其分发必须能够随着负载的增加良好地扩展。例如，如果请求需要处理的工作量不均衡，那么这种策略将无法奏效，并且资源会被低效使用。
• 如果实例之间需要相互通信或共享相同的数据，那么这将成为瓶颈。你会发现所有实例都在等待同一组资源，导致操作无法并行进行。
• 最后，也是最重要的一点，这并不能解决软件架构日益复杂的问题，而这可能正是可扩展性问题的根源。

因此，要想X轴扩展有效，必须与其他轴的扩展以及代码重构同步进行：

Y轴扩展

Y轴扩展的目标是将应用程序拆分为多个不同的服务。每个服务负责一个或多个紧密相关的功能。这与我们之前讨论的微服务相关，本质上是面向服务架构的一种完美部署策略。这种架构的好处是，硬件资源可以仅用于应用程序中需要的部分。例如，在一个旅游网站上，通常搜索功能的流量会比预订功能高得多（相比预订，更多的人会进行更多次搜索）。这意味着我们可以为搜索功能分配比预订功能更多的机器，也可以为每个微服务选择合适的硬件：

对于这种架构，需要考虑的一点是如何实现聚合功能。例如，在旅游网站的典型产品详情页面上，数据可能来自以下各种服务：

• 产品目录：主要是关于产品的静态信息，如酒店名称、地址。
• 定价服务：产品价格。
• 可用性服务：产品库存/可预订情况。
• 评论和评分：客户评论、照片等。
• 钱包：显示适用于客户的奖励积分详情。

当客户端需要组合这些不同服务的功能时，它是否需要进行n次调用呢？这里有几点需要考虑：

• 微服务提供的API粒度通常与客户端的需求不同。而且随着服务数量（分区）的变化，这种粒度可能会随时间改变。这种重构应该对客户端透明。
• 不同的客户端需要不同的数据。例如，酒店详情页面的浏览器版本与移动版本相比，布局不同，因此信息需求也不同。
• 网络性能可能不稳定。原生移动客户端使用的网络与服务器端Web应用程序使用的局域网相比，性能特征差异很大。这种差异导致客户端的往返时间和延迟各不相同。根据网络连接情况，API通信可能需要进行调整（批量处理）。

解决这些问题的方法是实现一个API网关：这是一个客户端调用的端点，它负责处理服务之间的通信编排和组合，以满足客户端的需求。Nginx是一个流行的高性能Web服务器，除了有大量的配置选项外，甚至还具备Lua脚本编写能力。所有这些使其能够作为API网关满足各种不同的用例。

另一个API网关的优秀示例是Netflix的API网关（http://techblog.netflix.com/2013/02/rxjava-netflix-api.html）。Netflix的流媒体服务被数百种不同类型的设备使用，每种设备都有不同的需求和特点。最初，Netflix试图为其流媒体服务提供单一的API。然而，该公司发现，由于请求的多样性以及我们前面讨论的问题，这种方式无法扩展。因此，它转向了API网关，通过运行特定设备的适配代码，为每种设备提供定制的API。这段代码平均会对六到七个后端服务进行组合。Netflix的API网关每天要处理数十亿个请求。更多详细信息，请访问https://medium.com/netflix-techblog/embracing-the-differences-inside-the-netflix-api-redesign-15fd8b3dc49d：

这种模式的另一个有趣变体称为后端为前端（Backend-For-Frontend）。很多时候，我们前面提到的设备特定需求很快就会变得复杂，在像Nginx（使用Lua脚本）这样的受限环境中进行设计会变得很困难。解决方案是为每种类型的客户端设置一个特定的后端服务作为API网关。该解决方案如下图所示：

Z轴扩展

在Z轴扩展模式下，每个实例运行相同的代码，但处理不同的数据子集。也就是说，每个服务器仅负责数据的一个子集。前面提到的编排器现在变得更加智能，必须将请求路由到拥有相关数据的特定实例，以便完成请求。一种常用的路由参数是请求所涉及属性的主键：例如，要获取特定用户的预订信息，我们可以根据用户ID来路由请求。我们不仅可以根据特定ID进行路由，还可以根据分段进行路由；例如，旅游网站可以通过将请求路由到特定的高容量服务器池，为高级客户提供比其他客户更好的服务水平协议（SLA）。

Z轴扩展要求数据（以及数据库）在不同的实例组之间进行拆分，这称为分片（sharding）。分片通常基于数据的主键进行，将整个数据集划分为多个分区。分区逻辑可以配置：可以是随机分布，也可以是更具业务针对性的分布，比如我们前面提到的高级客户与其他客户的区分方式。

需要注意的是，这种类型的扩展通常与X轴扩展同步进行。每个分片通常会运行多个代码实例，并且与之连接的数据库有一组副本以处理请求：

Z轴扩展有很多好处：

• 解决了请求负载的不规则模式问题。我们可以通过分区将高负载的任务分布到各个分区。
• 提高了硬件（CPU/缓存）的利用率，减少了跨服务的I/O操作。
• 改进了故障检测和隔离。很容易看出系统的哪一部分出现了问题，并且更容易实现容错。

Z轴扩展也有一些缺点：

• 增加了应用程序的复杂性。
• 我们需要在一开始就确定正确的分区方案。如果流量模式发生变化，我们的分布将不再高效。处理这种情况需要复杂的工程设计。

扩展部署

应用程序的部署位置和部署拓扑结构也会对系统的可扩展性产生重大影响。例如，如果你将代码部署在数据中心的物理系统上，那么可扩展性将受到获取硬件频率的限制。这会带来以下影响：

• 部署缺乏弹性：你无法在几分钟内轻松实现扩展或缩减规模。
• 成本难以灵活调整：硬件具有特定的容量和成本。而且，如果你想缩减规模，也很难收回硬件成本。

相比之下，在像亚马逊网络服务（Amazon Web Service，AWS）这样的云环境中，你可以按需启动、计算和存储细粒度容量的资源。你只需按实际使用资源的时间付费。此外，它们还具备自动扩展功能，可以根据流量增加等信号自动启动和关闭资源。

我们将在第11章“部署规划”中更详细地讨论部署方面的考虑因素。

总结

在本章中，我们探讨了构建应用程序可扩展性的各个原则。它从代码层面（算法、数据结构等）开始，一直延伸到系统层面的可扩展性设计。

由于我们的应用程序不会仅在一台机器上运行，因此我们需要用Go语言构建分布式系统，这将是下一章的主题。