ruby - 并发的，非阻塞的，固定大小的列表？

Question

我正在寻找一种具有以下特征的数据结构:
运作方式

按下:将元素添加到列表的前面。

读取:读取列表

中的所有元素

行为

固定大小的:列表不应超过指定的阈值，并且如果超过该阈值，则列表应自动从末尾(最旧的项目)截断。不需要严格执行此操作，但是一旦超过阈值，该列表最终应被截断。

并发安全的:结构应安全地容纳多个并行的推送程序和读取器

非阻塞:这是真正的问题。我想使用没有锁的实现。如果可能的话，许多线程应该能够同时推送/读取。较不理想但可接受的选项是具有锁定的实现，但可最大程度地减少多个插入器/读取器之间的争用。我熟悉读写器锁，但是那些假定不频繁写入，这不是我的用例。

可选但很不错

读写一致性:如果有单个线程推送到该结构，则紧随其后的读取应包含已写入的项目。很好，但是我想知道是否排除此要求可以使上述要求更易于实现。

我主要是并发数据结构的新手。是否存在这种数据结构的示例？环形缓冲区很有趣，但是我不认为它们可以是非阻塞的。链表很有前途，但是并发安全，无阻塞的要求使实现变得相当复杂。
我已经找到了一些有关使用原子CAS(比较和交换)操作实现非阻塞链表的好论文，但是固定大小的要求对此有些麻烦。也许该想法可以适应固定大小的列表？
对于它的值(value)，我有兴趣在Ruby中使用它。我知道MRI具有全局解释器锁，这对于MRI来说有点用，但是其他Ruby运行时可以利用这一点，并且我将其视为提高我的并发编程技能的学习练习。

Answer 1

分析
这个问题可能更适合Software Engineering，而不是Stack Overflow上的此处，因为它似乎更多是设计问题。就是说，如果您无法重新设计应用程序以完全避免使用单个共享对象，则建议使用线程安全数组或将资源争用委派给MVCC数据库。
推荐建议
您可以使用Concurrent::Array和#unshift和#pop方法来实现线程安全列表或模拟循环缓冲区。您还可以选择将锁定外部化到数据库之类的东西，其中Ruby的GIL与底层队列或锁定机制无关。但是，据我所知，尽管实现自己的multiversion concurrency control可能很接近，但是无法在Ruby中创建真正的无锁并发访问对象。
悬而未决的成果可能是外部化了对PostgreSQL等MVCC-capable database的读取和写入。如果您不能这样做，则可能需要接受ACID properties固有的权衡以及应用程序和数据结构的性能特征。特别是，使用单个共享数据结构是您可能应该重新评估的设计决策。
在开始那条路之前，只需确保您要解决一个真正的性能问题。当然，在某些情况下，锁会增加明显的开销，但即使在混合使用Ruby的GIL的情况下，许多实际应用程序仍具有足够的性能。您的里程肯定会有所不同。