Skip to content

Instantly share code, notes, and snippets.

@artempyanykh
Created July 17, 2018 21:27
Show Gist options
  • Save artempyanykh/d6a6e7a305b036727bf7995bf102b4ca to your computer and use it in GitHub Desktop.
Save artempyanykh/d6a6e7a305b036727bf7995bf102b4ca to your computer and use it in GitHub Desktop.
Scalaz RingBuffer project description

Scalaz RingBuffer

Goal

Scalaz RingBuffer adds a high-performance low-latency multi-producer/multi-consumer task queue to RTS for faster and smarter concurrency in ZIO.

Introduction & Highlights

ZIO RTS runs on a thread pool executor backed by LinkedBlockingQueue. This has the following consequences:

  1. Performance and latency are inhibited because: a) waiting on locks cause threads to be de-scheduled, b) traversing a linked list is not cache-friendly.
  2. Optimizations to Fiber cooperative multi-tasking strategy is limited because the thread pool doesn't expose any metrics on its queue remaining capacity\processing times.

Another approach is to use a lock-free concurrent queue backed by a RingBuffer which would act as a multi-producer\multi-consumer (MPMC) task queue for ZIO RTS. Main objectives are to:

  1. increase throughput,
  2. reduce latency,
  3. expose metrics on size, capacity, processing times.

Competition

There are two non-direct competing solutions in the Java world, which can actually be used as an inspiration and case-study:

  1. CoralQueue is a proprietary "ultra-low-latency, high-performance, lock-free, garbage-free, concurrent queue, demultiplexer, multiplexer, mpmc queue, and splitter".
  2. LMAX Disruptor is an open-source "high-performance inter-thread messaging library".

Background

The list below is not exhaustive, but is a good starting point:

  1. Article: The LMAX Architecture by Martin Fowler.
  2. Article: Yet another implementation of a lock-free circular array queue by Faustino Frechilla is a deep dive into the subject with examples in C++.
  3. Video: LMAX - How to do 100K TPS at less than 1ms latency by Martin Thompson is the first LMAX talk by one of the authors of LMAX.
  4. Video: Locks? We Don't Need No Stinkin' Locks! by Michael Barker is about v3 of LMAX that received a proper MPMC support.
  5. Paper: Draft: Lock-Free Ringbuffer Designs.
  6. Paper: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment