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 等公司的工程师进行模拟面试。