Netflix分布式计数器原理

banq

Netflix 的博客文章讨论了他们的分布式计数器抽象，这是一项旨在处理大规模分布式计数同时保持低延迟的服务。此抽象建立在他们现有的时间序列抽象之上，用于存储和查询大量时间事件数据。

Netflix 的计数要求包括跟踪用户交互、监控功能使用情况以及在 A/B 测试期间计数数据。

这些用例分为两类：

  • Best-Effort尽力而为：需要立即访问准确度较低的计数。对于此类别，计数不必非常准确或持久。但是，此类别需要以低延迟近乎立即访问当前计数，同时将基础设施成本保持在最低水平。
  • 最终一致性：需要准确计数并对延迟有一定的容忍度。此类别需要准确且持久的计数，并且愿意容忍准确性的轻微延迟和稍高的基础设施成本作为权衡。

这两个类别都有共同的要求，例如高吞吐量和高可用性。

分布式计数器抽象
为了满足概述的要求，计数器抽象被设计为高度可配置的。它允许用户在不同的计数模式（例如尽力而为或最终一致）之间进行选择，同时考虑每个选项的记录权衡。选择模式后，用户可以与 API 交互，而无需担心底层存储机制和计数方法。


API
计数器被组织到单独的命名空间中，用户可以根据自己的具体用例进行设置。每个命名空间都可以使用服务的控制平面配置不同的参数，例如计数器类型、生存时间 (TTL) 和计数器基数。

Counter Abstraction API 类似于 Java 的AtomicInteger接口：

AddCount/AddAndGetCount：根据数据集中给定的增量值调整指定计数器的计数。增量值可以是正数或负数。AddAndGetCount 对应函数也会在执行添加操作后返回计数。

{
  "namespace": "my_dataset",
  "counter_name": "counter123",
  "delta": 2,
  "idempotency_token": { 
    "token": "some_event_id",
    "generation_time": "2024-10-05T14:48:00Z"
  }
}

幂等令牌可用于支持幂等令牌的计数器类型。 客户端可以使用此标记安全地重试或对冲其请求。 在分布式系统中，失败是必然的，而拥有安全重试请求的能力可增强服务的可靠性。

GetCount： 读取数据集中指定计数器的计数值。

{
  "namespace": "my_dataset",
  "counter_name": "counter123"
}

ClearCount： 有效地将数据集中指定计数器的计数重置为 0。

{
  "namespace": "my_dataset",
  "counter_name": "counter456",
  "idempotency_token": {...}
}

计数器类型：该服务支持三种类型的计数器：

  • Best-Effort区域计数器：利用 EVCache 实现高吞吐量，但缺乏跨区域复制和一致性保证。
  • 最终一致的全局计数器：旨在实现耐用性和准确性，采用各种策略来管理争用并确保可靠的计数。
  • 精确计数器：一种旨在精确计数的实验类型。

Best-Effort区域计数器
这种计数器由 EVCache 提供支持，EVCache 是 Netflix 基于广受欢迎的 Memcached 构建的分布式缓存解决方案。 它适用于 A/B 实验等使用案例，在这些案例中，许多并发实验的运行时间相对较短，只需进行近似计数即可。 抛开配置、资源分配和控制平面管理的复杂性不谈，该解决方案的核心非常简单：

// counter cache key
counterCacheKey = <namespace>:<counter_name>

// add operation
return delta > 0
    ? cache.incr(counterCacheKey, delta, TTL)
    : cache.decr(counterCacheKey, Math.abs(delta), TTL);

// get operation
cache.get(counterCacheKey);

// clear counts from all replicas
cache.delete(counterCacheKey, ReplicaPolicy.ALL);

EVCache 在单个区域内以低毫秒或更低的延迟提供极高的吞吐量，从而在共享集群内实现多租户设置，节省基础设施成本。

不过，EVCache 也有一些不足之处：它缺乏对增量操作的跨区域复制，也不提供一致性保证，而一致性保证可能是精确计数所必需的。 此外，idempotency 幂等性本身不受支持，因此重试或对冲请求并不安全。

最终一致的全局计数器
虽然有些用户可能会接受Best-Effort计数器的局限性，但其他用户则选择精确计数、持久性和全球可用性。在以下部分中，我们将探讨实现持久和准确计数的各种策略。我们的目标是强调全球分布式计数固有的挑战，并解释我们选择方法的原因。

方法 1：每个计数器存储一行
让我们从简单的开始，在全局复制的数据存储中的表中每个计数器键使用一行。

让我们分析一下这种方法的一些缺点：

  • 缺乏幂等性：存储数据模型中没有幂等性密钥，阻止用户安全地重试请求。实现幂等性可能需要使用外部系统来处理此类密钥，这可能会进一步降低性能或导致竞争条件。
  • 竞争激烈：为了可靠地更新计数，每个写入器都必须使用锁或事务对给定计数器执行“比较和交换”操作。根据操作的吞吐量和并发性，这可能会导致严重的竞争，严重影响性能。

辅助键：在此方法中减少争用的一种方法是使用辅助键，例如bucket_id，它允许通过将给定计数器拆分为bucket来分配写入，同时允许读取在 bucket 之间聚合。挑战在于确定适当的 bucket 数量。静态数字仍可能导致与热键的争用，而跨数百万个计数器动态分配每个计数器的 bucket 数量则会带来更复杂的问题。

让我们看看是否可以迭代我们的解决方案来克服这些缺点。

方法 2：按实例聚合
为了解决热键和实时写入同一行的争用问题，我们可以实施一种策略，让每个实例汇总内存中的计数，然后定期将其刷新到磁盘。在刷新过程中引入足够的抖动可以进一步减少争用。

然而，这个解决方案又带来了一系列新的问题：

  • 容易丢失数据：在实例故障、重启或部署期间，该解决方案容易丢失所有内存数据。
  • 无法可靠地重置计数：由于计数请求分布在多台机器上，因此很难就计数器重置发生的确切时间点达成共识。
  • 缺乏幂等性：与上一种方法类似，这种方法本身并不能保证幂等性。实现幂等性的一种方法是始终将同一组计数器路由到同一个实例。但是，这种方法可能会带来额外的复杂性，例如领导者选举，以及写入路径中可用性和延迟方面的潜在挑战。

尽管如此，这种方法在可以接受这些权衡的场景中仍然适用。但是，让我们看看是否可以使用不同的基于事件的方法来解决其中一些问题。

方法 3：使用持久队列
在这种方法中，我们将计数器事件记录到持久队列系统（如Apache Kafka）中，以防止任何潜在的数据丢失。通过创建多个主题分区并将计数器键散列到特定分区，我们确保同一组消费者处理同一组计数器。此设置简化了幂等性检查和重置计数的过程。此外，通过利用其他流处理框架（如Kafka Streams或Apache Flink），我们可以实现窗口聚合。

然而，这种方法也面临一些挑战：

  • 潜在的延迟：让同一个消费者处理给定分区的所有计数可能会导致备份和延迟，从而导致计数过时。
  • 重新平衡分区：随着计数器基数和吞吐量的增加，这种方法需要自动扩展和重新平衡主题分区。

此外，所有预先汇总计数的方法都很难支持我们对准确计数器的两个要求：

  • 计数审计：审计涉及将数据提取到离线系统进行分析，以确保正确应用增量以达到最终值。此过程还可用于追踪增量的来源。但是，当汇总计数而不存储单个增量时，审计变得不可行。
  • 潜在的重新计数：与审计类似，如果需要调整增量并且需要重新计数时间窗口内的事件，则预先汇总计数会使这变得不可行。
除了上述几个要求外，如果我们确定了正确的方法来扩展队列分区和消费者，同时保持幂等性，这种方法仍然是有效的。但是，让我们探索如何调整这种方法以满足审计和重新计数的要求。

方法 4：单个增量的事件日志
在这种方法中，我们记录每个单独的计数器增量及其event_time和event_id。 event_id 可以包含增量来源的源信息。 event_time 和 event_id 的组合也可以作为写入的幂等性键。

然而，就其最简单的形式而言，这种方法有几个缺点：

  • 读取延迟：每个读取请求都需要扫描给定计数器的所有增量，这可能会降低性能。
  • 重复工作：多个线程可能会在读取操作期间重复聚合同一组计数器的工作，从而导致精力浪费和资源利用率低下。
  • 宽分区：如果使用像Apache Cassandra这样的数据存储，存储同一计数器的许多增量可能会导致宽分区，从而影响读取性能。
  • 大量数据占用空间：单独存储每个增量也可能导致数据占用空间随时间推移而增大。如果没有有效的数据保留策略，这种方法可能难以有效扩展。

这些问题的综合影响可能会导致基础设施成本增加，而这可能很难证明其合理性。然而，采用事件驱动方法似乎是解决我们遇到的一些挑战和满足我们要求的重要一步。

我们如何进一步改进这个解决方案？

Netflix 的方法
我们结合使用上述方法：

  • 将每个计数事件记录为一个事件，
  • 并使用队列和滑动时间窗口在后台持续聚合这些事件。
  • 此外，我们还采用分桶策略来防止出现宽分区。
在以下部分中，我们将探讨这种方法如何解决前面提到的缺点并满足我们的所有要求。

时间序列事件存储：
我们选择TimeSeries 数据抽象作为事件存储，计数器突变被提取为事件记录。将事件存储在 TimeSeries 中的一些好处包括：

  • 高性能：TimeSeries 抽象已经满足了我们的许多要求，包括高可用性和吞吐量、可靠和快速的性能等等。
  • 降低代码复杂性：我们通过将大部分功能委托给现有服务来减少 Counter Abstraction 中的代码复杂性。
  • 处理宽分区：time_bucket和event_bucket列在拆分宽分区方面起着至关重要的作用，可防止高吞吐量计数器事件压垮给定分区。有关这方面的更多信息，请参阅我们之前的博客。
  • 无过度计数：event_time、event_id和event_item_key列构成给定计数器事件的幂等性键，使客户端可以安全地重试，而不会出现过度计数的风险。
  • 事件排序：时间序列按时间降序排列所有事件，使我们能够利用此属性来处理计数重置等事件。
  • 事件保留：TimeSeries Abstraction 包含保留策略，以确保事件不会无限期存储，从而节省磁盘空间并降低基础设施成本。一旦事件被聚合并移动到更具成本效益的存储以供审核，就无需将它们保留在主存储中。

TimeSeries Abstraction 使用 Cassandra 作为底层事件存储，但可以将其配置为与任何持久性存储一起使用。

现在，让我们看看这些事件是如何针对给定的计数器进行聚合的。

聚合计数事件：
如前所述，收集每个读取请求的所有单个增量在读取性能方面成本过高。因此，需要一个后台聚合过程来不断收敛计数并确保最佳读取性能。

但是我们如何在正在进行的写入操作中安全地聚合计数事件？
这就是最终一致性计数概念变得至关重要的地方。

  • 通过故意将当前时间滞后一个安全范围，我们确保聚合始终发生在不可变的窗口内。

让我们详细分析一下：

  • 计数器值最近一次被聚合的时间lastRollupTs：对于第一次运行的计数器，此时间戳默认为过去的合理时间。
  • 不可变窗口和滞后：聚合只能在不再接收计数器事件的不可变窗口内安全地进行。TimeSeries 抽象的“acceptLimit”参数在这里起着至关重要的作用，因为它会拒绝时间戳超出此限制的传入事件。在聚合期间，此窗口会稍微向后推，以解决时钟偏差问题。这确实意味着计数器值将落后于其最新更新一定幅度（通常以秒为单位）。这种方法确实为跨区域复制问题导致的事件遗漏留下了空间。
  • 聚合过程：汇总过程聚合自上次汇总以来的聚合窗口中的所有事件以得出新值。
  • 我们将此聚合的结果保存在持久存储中。下一次聚合将从此检查点继续进行。
  • LastWriteTs：每次给定计数器收到写入时，我们还会在此表中将最后写入时间戳作为列式更新记录下来。这是使用 Cassandra 的USING TIMESTAMP功能可预测地应用 Last-Write-Win (LWW) 语义来实现的。此时间戳与事件的event_time相同。在后续部分中，我们将了解如何使用此时间戳使某些计数器保持活跃的汇总循环，直到它们赶上其最新值。
  • 汇总聚合缓存：为了优化读取性能，这些值会针对每个计数器缓存在 EVCache 中。我们将lastRollupCount和lastRollupTs合并 为每个计数器的单个缓存值，以防止计数与其对应的检查点时间戳之间可能出现的不匹配。

但是，我们如何知道哪些计数器会触发汇总？让我们探索写入和读取路径以更好地理解这一点。

1、添加/清除计数：
添加或清除计数请求会将数据持久写入 TimeSeries Abstraction，并更新 Rollup 存储中的最后写入时间戳。如果持久性确认失败，客户端可以使用相同的幂等性令牌重试其请求，而不会出现计数过高的风险。在 持久性确认后，我们会发送一个即发即弃请求来触发请求计数器的汇总。

2、获取计数：
我们将最后一次汇总计数作为快速点读取操作返回，接受可能提供稍微过时的计数的权衡。我们还会在读取操作期间触发汇总以推进上次汇总时间戳，从而提高后续聚合的性能。如果任何先前的汇总失败，此过程还会自行修复过时的计数。

通过这种方法，计数会不断收敛到最新值。现在，让我们看看如何使用我们的 Rollup Pipeline 将这种方法扩展到数百万个计数器和数千个并发操作。

3、汇总管道：
每个Counter-Rollup服务器都运行一个汇总管道，以高效地汇总数百万个计数器的计数。这是 Counter Abstraction 中大部分复杂性的来源。在以下部分中，我们将分享有关如何实现高效聚合的关键细节。

轻量级汇总事件：如上面的写入和读取路径所示，计数器上的每个操作都会向汇总服务器发送一个轻量级事件

4、内存中汇总队列：
给定的汇总服务器实例运行一组内存中队列来接收汇总事件并并行化聚合。在该服务的第一个版本中，我们决定使用内存中队列来降低配置复杂性、节省基础设施成本，并使重新平衡队列数量变得相当简单。然而，这样做的代价是，如果实例崩溃，汇总事件可能会丢失。有关更多详细信息，请参阅“未来工作”中的“过时计数”部分。

5、尽量减少重复工作：
我们使用快速的非加密哈希（如XXHash）来确保同一组计数器最终位于同一队列中。此外，我们尝试通过使用单独的汇总堆栈来尽量减少重复聚合工作量，该堆栈选择运行更少的 更强大的实例。

...

由于原文对计数器在宏观机制上逻辑证明很少，大部分是琐碎报告，参考原文，有网友抱怨，像Netflix这种全国春晚式的集中式视频流迟早走向衰败。