java - 单作者多读者原语图

Question

我正在尝试用Java编写一个actor实现。我的设计要求使用高性能 map 数据结构来查找特定参与者计划在哪个线程上。查找是通过int id完成的。所有 Actor 都有单独的ID。我有以下要求:

i)键是基本整数，而不是Integer类。

ii)值也是原语。值只能覆盖在实例化数据结构之前已知的几个数字。值只是线程/核心的ID，因此它可以是短。线程数少于计算机上的内核数，因此它实际上无法达到很高的数量。

iii)映射是由单线程写入的，但是是从多线程读取的。我希望我的实现是无锁的并且没有任何共享(false或其他方式)。因此，读取不应涉及对非线程本地内存的任何写入。

iv)(通过单个线程)的写入数量将大大超过使用该映射进行查找的多个读取器线程的读取数量。

v)所需的主要操作:

Set(key, value)和delete(key, value)始终从单个编写器线程中调用。设置的大多数键最终也会被删除，因此，大量删除后的性能不会降低。新的 key (actor-id)将使用递增的整数生成，并表示已创建actor。删除键( Actor 的ID)表示该 Actor 已退出并且永远不会恢复。这也意味着一旦删除 key 就再也不会设置了。重要的是我们不要在 map 上累积死角，因为会发生删除(角色退出)。

从阅读器线程调用的

Get(key)。

vi) get(key)操作必须是 eventually consistent，但有一些警告。假设编写者线程已将对key1-> value1更改为key1-> value2。如果其中一个读取器执行get(key1)并仍然接收value1，这不是问题。最终它应该获得value2。如果写入器线程已删除对key1-> value1对，并且读取器线程上的get(key1)仍返回value1，也很好。实际上，我的意思是可以合并Java的 putOrderedObject/lazySet/getObjectVolatile或C++ 11的 std::memory_order_relaxed/std::memory_order_acquire/std::memory_order_release之类的东西。另一方面，如果确实设置了值，则 get(key1)不应返回空值(例如-1)。我不介意 getStrict(key1)操作，如果 get(key1)返回一个空值来满足此要求，我可以调用该操作。

我不立即使用图书馆的原因是:

i) Java集合:它们需要包装器类，因此不符合我的目标(i)和(ii)

ii) Trove，FastUtil 等:它们确实具有原始映射，但是不提供任何并发访问功能。它们也不会针对稀疏范围内的值(在我的情况下为内核数)进行优化。

iii) Java ConcurrentHashMap/ConcurrentSkipListMap :它们需要包装器类，并且不会针对单个编写器和多个读取器用例进行优化。

我意识到这些是很多要求，因此如果答案能解决某些问题，而对其他问题仍然模棱两可，那就很好了。指出我对设计的源代码或评论会很棒。由于我正在尝试学习捕鱼方法，因此任何权衡取舍的解释都将是额外的收获。

如果我将详细的要求归结为几个问题，它们可能是:

i)如何针对单作者/多读者用例进行优化？

ii)如何设计 get(key)和 getStrict(key)操作？这是思考的正确方法吗？

iii)如何设计 map 以利用增量键和稀疏值范围？

iv)如何​​最佳处理频繁删除？任何调整大小/重新散列的操作都必须立即对阅读器线程可见，而不是最终可见。

也欢迎使用C++/C++ 11代码的任何答案。通过一些研究，我应该能够将大多数std::atomic操作转换为Java不安全的操作。

Answer 1

错误共享仅来自多个作者，因为您只有一个作者，所以作者之间的共享应该没有问题。

i) How can I optimize for the single-writer/multiple reader use case?

您不需要为多个读取器做任何特殊的事情，在这种情况下，每个线程都将具有数据结构的本地拷贝。单个编写器是最简单(也是最快)的用例。

因此Trove和ConcurrentMaps都可以做到这一点。 BTW ConcurrentMap还针对多个编写者进行了优化。

ii) How do I design the get(key) and getStrict(key) operations? Is this the right way of even thinking about it?

您所描述的是并发集合现在如何工作。我不清楚getStrict有什么不同之处。

iii) How can I design my map to take advantage of the incrementing keys and sparse value range?

如果您有普通的递增键，则环形缓冲区可能是一个更好的选择。如果您有 sparse values，则只需存储值即可。

iv) How do I optimally handle the frequent deletions?

环形缓冲区对于删除操作非常有效，具体取决于您正在执行的操作。要考虑的主要事情是制定内存/对象回收策略。这将减少重新分配和垃圾回收的成本。

Any resizing/rehashing will need to be immediately visible to the reader threads instead of being eventually visible.

如果值最终可以保持一致，那么我不明白为什么需要立即调整大小。