高效分布式计数

4
我有一系列事件在系统中流动(例如披萨订购系统),我想通过时间计算每个事件的某些属性。例如,我可能想看看在过去的5分钟内有多少独特的人订购了意大利辣香肠披萨,或者John Doe在过去一周里订购了多少披萨。
由于事件数量非常多,所以我们使用类似Cassandra或HBase的东西来存储,因为即使计数也无法存储在内存中。此外,由于我们需要跟踪集合成员资格(为了计算订购特定类型披萨的独特人数,例如),它会变得更大。
我们可以存储订单列表,然后查询以进行计数,但这很慢。而且我们大多数时候不关心谁订购了意大利辣香肠披萨,只关心有多少独特的订单被制作,并且在给定的时间窗口内。
例如在Cassandra中存储此信息的最佳方法是什么,以便可以在某些时间间隔内检索该信息?
我最初尝试使用Redis +布隆过滤器,但是存储布隆过滤器位向量将需要事务以避免竞争条件,因此我使用了Redis集合。
然后我意识到整个东西太大了,不能仅仅存在于内存中,因此我决定切换到磁盘支持的存储。但是,与Redis不同,没有本地集合。
我查看了HyperLogLog之类的草图/流算法,但是得出的结论是要保存hyperloglog对象,我需要存储位数组(或pickle对象或其他任何内容)...这是否可以,如果是解决方案,则最佳实践是什么?
我曾经尝试过将每个事件单独保存并带有时间戳,然后按需查询和计数,但这很慢。如果有更好的方法,我正在寻找它。

示例请求:

  • 在过去的10分钟内有多少独特的人订购了意大利辣香肠披萨
  • 在过去30分钟内,某个名为John Doe的人订购了多少独特的意大利辣香肠披萨

你要搬多少披萨?!? - VoronoiPotato
每秒大约有200个披萨...而且我们正在计算每个披萨的6-7个不同属性(谁点的,点餐人的父母是谁等等,开个玩笑)。 - Sam
那么假设Jim Doe订了3个披萨,然后20分钟后回来又订了2个披萨(他有暴饮暴食的问题),这些是否被视为2个独立的订单?或者订单的唯一性是基于客户身份的? - VoronoiPotato
1
现在我感到饥饿 :D - Aditya
1
你可能需要更详细地说明你希望支持的查询类型。无论如何,我可能只会建议使用关系型数据库管理系统(RDBMS)。 - Bernhard Barker
显示剩余4条评论
2个回答

1

从我学到的知识来看,有几种解决这个问题的方法。

  1. 使用锁定+设置成员身份/计数数据结构,例如hyperloglog或布隆过滤器。 只要没有太多争抢特定锁,事情应该没问题。
  2. 使用具有内置集合/集合支持的数据库。 它们在内部基本上实现了#1。

0

我的猜测:

  • Cassandra支持计数器 - 我想我看到了一些可以并发工作的增量操作 - 通过在事件上使用自由运行计数器,您只需要设置一些在指定间隔(5分钟?)内对所有计数器进行采样的东西,然后您就可以在两个样本之间给出估计值 (http://wiki.apache.org/cassandra/Counters)
  • Cassandra可以超时列...我从未真正使用过它,但这可能值得一试

递增Cassandra计数器显然可以用于实际计数,但如何在O(1)时间和亚线性空间内处理集合成员资格呢?布隆过滤器/超大记忆体很容易想到,但问题在于如何在类似Cassandra这样的分布式数据库环境中使用它们。 - Sam
如果你假装Cassandra中不存在计数器列,那么你的生活会更美好。因为很容易出错,而且不支持TTLs,除了分区键之外,不能在同一列族中混合使用计数器和非计数器。 - Matt

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接