algorithm - App Store 如何计算每个应用的唯一下载次数？

Question

“唯一”意味着如果一个应用被用户下载超过 1 次，它的下载计数永远保持为 1，直到另一个用户再次下载该应用。例如，我们跟踪用户下载行为如下：

Date        User        App name
2012-01-01  jack        Angry Birds
2012-01-01  jack        Angry Birds
2012-01-02  jack        Angry Birds
2012-01-02  paul        Angry Birds
2012-01-02  jack        Snappea

这应该给出结果：

Angry Birds        2
Snappea            1

一个简单的实现方式是我们使用数据结构，比如 HashSet 来存储User + App name作为它的 key。但实际上，App Store 拥有大量用户和应用程序。假设用户数是 400M 并且有 650K 的应用程序，HashSet 的大小在最坏的情况下会达到 400M * 650K = 260T 。我们还假设我们需要计算每天的下载次数。

根据Google Play 的 600,000 个应用程序，200 亿的总安装量，App Store 的总下载量在 2012 年 6 月达到 300 亿。这仍然是一个很大的数字。

那么我们怎样才能用更少的空间又快速地实现呢？如果使用hadoop/hbase？

Answer 1

使用数据库：有一个users. 每个用户都应该有下载历史。当用户下载一个应用程序时，它将被添加到下载历史中。如果这是一个新应用程序，它还将更新app表（使用触发器）以增加计数。听起来不错？