Design and implementation of a concurrent RingBuffer in Scala

Abstract

Queues are a significant algorithmic component to many systems and applications that enable decoupling of producers and consumers. Some of its real-life applications are ticket-ing (as a waiting list), a queue of packets in data communication or a queue of operating system processes. With the rapid growth of parallel processing and event-driven applica-tions, concurrent implementations of this data structure have gained significant importance. Despite the relevance, many available implementations in JVM ecosystem employ expen-sive operations such as thread blocking (BlockingQueue) or true unboundedness (Concur-rentLinkedQueue), a characteristic which discards the usage of the data structure where consumer backpressure is needed. This thesis is an attempt to address such concerns, by design and implement a lock-free concurrent bounded queue, or RingBuffer, in Scala.

The thesis focuses first on exploring the concurrency mechanisms that describe the JVM ecosystem. Then it proceeds to the lock-free RingBuffer implementations, employing differ-ent concurrency primitives and two different underlying data structures (Scala’s immutable Queue and Java’s mutable Array). The final section is dedicated to benchmarks comparing RingBuffer implementations and Java’s concurrent queue implementations. Measurements done for this section showed a significant improvement in speed over the available data structure although the API is presenting a few key differences.