用于top-N geohash的实时多线程max-heap

Question

我们要求在城市的前10个地方保持一个名单，在任何给定的时刻，对我们的餐饮服务的需求都是从那里产生的。这座城市可能有数以万计的地方。如果必须在内存中创建一个近乎实时的(延迟不超过5分钟)数据存储-按位置记录传入需求(地理哈希)-每分钟读取数百个供应商的数据( ajax刷新是每分钟)

我在考虑一个多线程同步的max-heap。这将是一个复杂的解决方案，因为树锁定本身就是一个复杂的实现。

对于在多线程环境中可以读取和更新的最佳内存(可复制主从)数据结构，有什么建议吗？

我们预计每秒10K QPS和100K更新。当我们扩展到其他城市和地区时，我们将需要每个城市实施top-10。

有现成的解决方案吗？

持久化不是必需的，因此没有基于mySQL的解决方案。如果您推荐redis或mongo DB解决方案，请意识到查询不是按键指向的查询，而是top-N查询。

提前谢谢。

Answer 1

如果您正在寻找您所描述的内容，有几种方法可能会很好地工作。有几篇文章描述了可以作为优先级队列工作的并发数据结构；我不是很熟悉here is one option，但它看起来很有前途。您可能还想检查并发跳过列表，这也应该符合您的要求。

如果我对您的问题陈述的解释是正确的，那么您希望根据您收到的点击数来维护前10个位置的列表。如果是这样的话，我会怀疑虽然更新的数量会很大，但两个位置交换位置的次数实际上不会那么多。换句话说，大多数更新实际上不需要数据结构改变形状。因此，您可以考虑使用标准二进制堆，其中每个元素都使用原子比较和设置整数键，并且具有某种锁定系统，仅在需要在堆中添加、移动或删除元素时使用。

考虑到您正在工作的规模，您可能还希望考虑问题的近似解决方案。例如，count-min sketch数据结构是专门为估计数据流中的频繁元素而设计的，而且速度非常快。它可以很容易地被分发，并以类似于我上面描述的方式与优先级队列相关联。有很多很好的实现，如果我没记错的话，这个数据结构实际上是在您所描述的情况下部署的。

希望这能有所帮助！