2

我有一个EventsManager从外部源接收事件。一个Event有一个type和一个value。

侦听器可以注册到EventsManager以被告知某种类型事件的连续值。

对于EventsManager给定类型的事件，承诺两件事：

  • 相同的值不会连续发送两次（当侦听器收到通知时，他们保证收到的值与上一次通知的值不同）。
  • 对于给定类型的事件，必须保留从外部源接收值的顺序。

我有一个工作synchronized版本，但我想提高吞吐量。

典型用途：< 1k 侦听器，< 10k 事件类型，< 1M 每秒接收的事件（但大多数被丢弃，因为没有为该类型事件注册的侦听器或值未更改）。

  • 实现该行为的最有效策略是什么（例如，我可以为每种事件类型使用一个队列/锁并将它们保存在 ConcurrentMap 中，但拥有 10k 个队列听起来不是一个好主意）？
  • 是否有任何现有的库可以使用可扩展的并发结构做类似的事情？

示例：Listenerlst1想要监听type1
EventManager 接收到的事件类型：

event: type2, value: 2
event: type1, value: 1
event: type1, value: 1 //no change => discard
event: type3, value: 4
event: type1, value: 7

lst1应该按以下顺序接收：（1仅一次） then 7。

4

2 回答 2

1

这个答案会随着评论的添加而改变。

如果您可以控制外部源，最快的改进是防止该源发送保证被丢弃/忽略的消息。例如，外部源可以保留一个Map或一些其他允许快速查找 + 更新的数据结构。外部来源将能够确定需要将哪些信息发送给您的EventQueue

如果您不控制外部来源，则队列应该有可能Event像您在原始帖子中所说的那样保持通用。我建议添加一个Radix Tree从您的Queue. 我的意思是将队列生成的值存储在radix tree中。这允许以下操作：

与平衡树不同，基数树允许在 O(k) 时间内而不是 O(log n) 时间内进行查找、插入和删除。这似乎不是一个优势，因为通常 k ≥ log n，但在平衡树中，每个比较都是字符串比较，需要 O(k) 最坏情况时间，其中许多在实践中很慢，因为公共前缀较长 (在比较从字符串开头开始的情况下）。在一个 trie 中，所有的比较都需要固定的时间，但是查找一个长度为 m 的字符串需要 m 次比较。基数树可以用更少的比较来执行这些操作，并且需要更少的节点。

更新

问题：

你知道基数树的线程安全实现吗？

并发树 没有测试过这些！

API：并发基数树

于 2012-12-14T12:28:43.440 回答
1

我会尝试实现这个事件流

  1. 所有传入的事件都被放入一个初始的EventQueue
  2. EventDispatcherThread读取 EventQueue，并将事件过滤并路由到每种类型的适当EventQueue（队列的简单映射）
  3. EventListernerThread的多个实例正在读取其类型的相应 EventQueue...

不需要锁/同步

于 2012-12-14T12:54:31.323 回答