Dropbox 面试题 - 设计点击计数器

原文：Dropbox Interview – Design Hit Counter

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

我们从一个简单的问题开始 - 如果你正在构建一个网站，你如何计算过去一分钟的访客数量？

最近，包括 Dropbox 在内的很多公司都提出了“设计点击计数器”的问题，这个问题比看起来要困难得多。本周，我们将揭开这个问题的所有奥秘。这篇文章讨论了几个主题，包括基本的数据结构设计，各种优化，并发和分布式计数器。

这个问题有什么特别之处？

我总是喜欢告诉我们的读者为什么我们选择这个问题进行分析，以便你确切知道是否值得你花时间阅读。作为一名面试官，我非常喜欢那些在最简单的情况下不难解决的问题，但是通过删除/添加特定的条件，讨论可以越来越深入。这个问题正是如此。

而且，这个问题不是无中生有的，而是有真实的用例。对于今天的许多系统，我们需要一个系统，不仅跟踪用户数量，而且实时跟踪不同类型的请求数量。

如果你还没有想过这个问题，那么在阅读以下部分之前，请花点时间研究一下。

简单的情况

忘记所有的并发问题和可扩展性问题，比方说，我们只有一台没有并发请求的机器，过去一分钟内如何获得访客数量？

显然，最简单的解决方案是将所有访客的时间戳存储在数据库中。当有人请求过去一分钟的访客数量时，我们只需查看数据库，并进行过滤和计数。一点点的优化是通过时间戳来排序用户，这样我们就不会扫描整个表。

由于时间复杂度为O(N)，其中N是访客的数量，所以该解决方案效率不高。如果网站的访问量很大，函数不能立即返回数量。

优化

有几种方法来思考这个问题。由于上述方法不仅返回访客数量，而且还返回过去一分钟的访客，这在问题中是不需要的。这是我们可以优化的东西。从另一个角度来看，我们只需要过去一分钟的数量而不是任何时间范围，这是我们可以改进的另一个地方。简而言之，通过删除不必要的功能，我们可以优化我们的解决方案。

一个简单的想法是只保留过去一分钟的用户，随着时间的推移，我们不断更新列表及其长度。这使我们能够立即获得数量。本质上，我们减少了获取数量的代价，但是必须不断更新列表。

我们可以使用队列或链表来存储过去一分钟的用户。我们保留所有元素，当最后一个用户（最早的用户）的时间为一分钟以上时，从列表中删除它并更新长度。

空间优化

由于我们可以在O(1)时间内返回访客数量，所以提高速度的余地不大。但是，存储过去一分钟的所有用户可能空间上开销很大。一个简单的优化是只保留列表中的用户时间戳，而不是用户对象，这可以节省大量的空间，特别是当用户对象很大时。

如果我们想进一步减少空间使用量，你会采取什么方法？

考虑这个问题的一个好方法就是为了改善空间复杂度，我们应该牺牲什么？既然我们仍然想保持时间复杂性为O(1)，我们可以妥协的一件事就是准确性。如果我们不保证返回最准确的数字，我们可以使用更少的空间。

我们不追踪过去一分钟的用户，只追踪过去一秒的用户。由此，我们确切知道最后一秒有多少访客。为了获得过去一分钟的访客数量，我们维护了 60 个元素的队列/链表，代表过去的 60 秒。每个元素都存储那一秒的访客数量。所以，每一秒钟，我们从列表中删除最后一个（最早的）元素，并添加一个新的，过去一秒的访客数量。过去一分钟的访客人数是 60 个元素的总和。

分钟数可以按照过去一秒的请求来计算。而且你可以通过调整单位来控制准确度和空间之间的权衡。你可以保存过去量秒钟的用户，并在列表中有 30 个元素。

并发请求如何？

在生产系统中，并发是人们面临的最常见的问题。 如果可能存在多个用户同时访问网站，以前的方法是否仍然有效？

部分。 显然，基本理念依然成立。 但是，当两个请求同时更新列表时，可能会有竞争条件。 最初更新列表的请求可能不会最终包含在内。

最常见的解决方案是使用锁来保护列表。 每当有人想要更新列表（通过添加新元素或删除尾部），对列表上锁。 操作完成后，对列表解锁。

当你没有大量的请求或性能不是一个问题时，这个作品相当好。 在某些时候上锁可能开销很大，并且当并发请求过多时，这个锁可能会阻塞系统并成为性能瓶颈。

分布式计数器

当单台计算机流量过多，性能成为问题时，现在是考虑分布式解决方案的最佳时机。分布式系统通过将系统扩展到多个节点，显着减轻单个机器的负担，但是同时增加了复杂性。

假设我们将访问请求平均分配给多台机器。我想首先强调平均分配的重要性。如果特定的机器比其他机器获得更多的流量，那么系统不能完全利用，在设计系统时考虑到这一点非常重要。在我们的例子中，我们可以获取用户电子邮件的散列，并通过散列分配（直接使用电子邮件不是一个好主意，因为有些字母可能比其他字母更频繁出现）。

为了统计这个数量，每台机器独立工作，从过去的一分钟开始统计自己的用户。当我们请求全局数量时，我们只需要把所有的计数器加在一起。

总结

我喜欢这个问题的原因之一是，最简单的解决方案可能是一个编成问题，并且为了解决并发性和可扩展性问题，这成为一个系统设计问题。 而且，这个问题本身在生产系统中有广泛的用途。

同样，解决方案本身不是最重要的东西。 我们所关注的是展示如何分析问题。 比如，权衡是一个很好的概念，当我们试图优化一个地方时，想想还有什么应该牺牲的东西。 通过这样的思考，它为你打开了很多思路。

顺便提一下，如果你想得到资深的面试官的更多指导，可以查看 Gainlo，以便与 Google，Facebook 等公司的工程师进行模拟面试。