events - 用于事件调度的队列/数据库？

Question

我可能会在某个时候建立自己的，但与此同时；是否有通用语言的事件调度程序——以例如:{time, priority, action} 作为输入——可跨分片分布，并支持:

• 在 O(1) 中排队(推送)
• 在 O(log n) 中出列(弹出)
• O(1) 中的下一个预定(查找分钟)
• 在 O(log n) 中任意删除，例如:通过使用指定为 delete_queue 的第二优先级队列

正在研究 Redis，但找不到合适的优先级队列接口(interface)。

Answer 1

我不认为您可以使用您为每个操作描述的确切复杂性假设使用 Redis 实现这样的队列。

你可以用 Redis 做的是使用 zset。在内部，一个 zset 被实现为一个标准的哈希表加上一个跳跃列表(按分数和值排序)。因此，您可以使用分数来存储时间戳，并使用值来编码优先级和操作。 zset 中的顺序首先是分数，然后是值本身(按字典顺序比较)。所以想法是选择一个值表示，其字典顺序对应于优先级所需的逻辑顺序。在这里，我假设时间优先于优先级(即优先级仅用于对具有相同时间戳的项目进行排序)。

例如:

# timestamp=0, priority=3
zadd myqueue 0 03-action1

# timestamp=10, priority=2
zadd myqueue 10 02-action3

# timestamp=10, priority=1
zadd myqueue 10 01-action2

# The dequeuing order will be action1,action2,action3
# (because of priorities)

我相信各种操作的复杂度将是:

• 入队 O(log n) [使用 zadd]
• 出队 O(log n) [使用 zremrangebyrank]
• 下一个预定项目 O(1) [使用 zrange 获取第一个项目]
• 任意删除 O(log n) [使用 zrem]

它们与您要找的东西不同，但还不错。