multithreading - 实时多线程最大堆，用于top-N geohash

Question

要求保留一个城市中排名前十的地区的列表，这些城市在任何给定时刻都对我们的食品服务产生了需求。这个城市可能有成千上万的地方。
如果必须在内存中进行近乎实时的(滞后时间不超过5分钟)数据存储，
-保持按地区输入的需求计数(地理哈希)
-每分钟由数百家供应商读取(Ajax刷新每分钟)

我在想一个多线程同步最大堆。这将是一个复杂的解决方案，因为树锁定本身就是一个复杂的实现。

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

我们期望每秒10K QPS和100K更新。当我们扩展到其他城市和地区时，我们将需要在每个城市实现前10名。

有没有现成的解决方案？

不需要持久性，因此不需要基于mySQL的解决方案。如果您建议使用redis或mongo DB解决方案，请意识到查询不是按键的指向查询，而是前N个查询。

提前致谢。

Answer 1

如果您正在寻找所描述的内容，那么有几种方法可能会很好用。有几篇论文描述了可以用作优先级队列的并发数据结构。我不太熟悉的here is one option，但看起来很有希望。您可能还需要 check out 并发跳过列表，这些列表也应符合您的要求。

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

给定您的工作规模，您可能还需要考虑解决问题的近似解决方案。例如，count-min sketch数据结构是专门设计用来估计数据流中的频繁元素的，而且这样做的速度非常快。它可以通过类似于我上面描述的方式轻松地分发并与优先级队列链接。有很多好的实现，如果我没记错的话，这种数据结构实际上是在您所描述的情况下部署的。

希望这可以帮助!