求助 一道 系统设计 【分布式滑动窗口去重计数】

需求 分布式环境下，计算一段时间内，关联着同一个did的访问中，有多少个不同的uid。
已知解 Redis Zset实现滑动窗口，每一个did对应一个Zset，Zset的key为uid，score为时间戳 缺点是 操作过于复杂，逻辑太重
请教下有无其他更优的解决方案，或相关可以参考的书籍资料，感谢！

我的设计思路
A. 需要做一些假设，需要和面试官确认，因为scale-up必然会丢失一定的精准性，一般可以大胆的假设
  1. sliding window不用特别精准，有几秒的boundry问题是没问题的。
  2. 对于特别高的QPS的用户，aggregation的数字也会一定的错误，是不是可以容忍的（如果不能容忍，问可不可以通过daily offline job来correct）

基于A1，A2的假设，我们就可以设计一个非常scalable的系统了
首先所有的数据应该不用read-after-write的consistency，所以把数据放入kafka，然后我们streaming processing他们
如果面试官坚持非常夸张的consistency要求，其实面试题反而简单了，因为其实没什么好发挥设计的余地了。

B，设计一个基本可用的系统，（注意：scalability是有问题的）
1. 我们设计一个kafka consumer，来consume这个streaming event，然后根据时间划定每隔1分钟的key（例如直接Unixtime//10）。Redis的key会类似于id-time1，id-time2，id-time3。处理event，读写Redis中的id-time1，利用CAS，或者Redis自带的incr功能去增加。
2. reader side，我们如果要读取一个窗口，例如过去的一个小时，那么就batch读取60个数据点。可以做一个小小的优化，例如长时间的做一些aggregation，从而减少读很久之前数据我速度很慢的问题（如果题目要求读取好几个小时的）。
3. 如果需要读取很长以前的，类似1-2天前的，那么需要把数据放入有磁盘backup的DB，例如mongodb，mysql。因为redis会crash
4. 如果crash发生了，例如redis crash了，那么我们会丢失一段时间的数据，那么简单的方式是调整kafka，然后重新consume kafka（我们C阶段会重新解释这个问题）
5. uid dedup不知道是不是要求，不过应该很简单，大家都会的
6. 这个系统有很多问题，主要是redis的读写太频繁。数据丢失，我们也不知道哪里丢失了，怎么retry。读的部分设计的太简单了，可以更高效一点

C， 设计一个非常scalable的系统
1. kafka提供了partition key，我们可以基于member id（或者你这里的did）来做partition routing，这样同member的数据就进入了一个partition了，这样一个kafka stream consumer（例如Flink），就可以利用local memory来做一个几秒内的aggregation，当数据满10秒了，再一口气flush进redis，甚至不需要redis层，直接进disk-back up的DB，因为QPS不高。注：这里也可以一并把UID的dedup给做了
2. 一旦flush成功了，kafka的offset才能commit，这样我们一旦flink task crash了，我们会自动从之前的kafka offset来consume。出错的数据的offset会很小。注：kafka的offset commit和reading是一个sliding window
3. C1带来了一个hot-partition的问题，如果一个member非常hot，那么这个kafka consumer也会过于hot，解决方案是对特别hot的member，把partition key改成member-id-random（10）。这样他就分散到10个partition了，但依然有C1，local 处理的好处。至于如何规划一个hot，这个是另外一个设计问题，how to discover hot trending
4. 对于特别夸张高的QPS，大概率我们可以sample，然后forecast了，所以不用一点点aggregate了

D 设计一个更好的读取和data correction
1. 读取的DB可以不要用Key，其实MYSQL加了合适的Shard也可以。业界会使用TSDB，更高效的存储时间数据。这个回头需要revisit一下需求，例如老的数据是不是可以丢失时间的精度，例如只能看到1天level的数据，而小时级别的就消失了
2. 设计一个offline correction job去解决可能潜在的aggregation非常边缘的重复的情况，（例如flush完，server trash，导致offset没commit）


最后看在我辛苦的思考了，码了那么字
求个大米！求个大米！求个大米！

好奇这个和distrubited system是什么必然联系？为什么redis可以解决distributed的问题？

ohshout 发表于 2024-02-17 15:33:16
好奇这个和distrubited system是什么必然联系？为什么redis可以解决distributed的问题？

可能我表述不清，指请求可能打在多台机器不能用本地缓存解决这个问题。

给你提供个思路 用 hash 结构 key是时间戳

discint count,应该是用reids hyperloglog做