DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Please enter at least three characters to search
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Last call! Secure your stack and shape the future! Help dev teams across the globe navigate their software supply chain security challenges.

Modernize your data layer. Learn how to design cloud-native database architectures to meet the evolving demands of AI and GenAI workloads.

Releasing software shouldn't be stressful or risky. Learn how to leverage progressive delivery techniques to ensure safer deployments.

Avoid machine learning mistakes and boost model performance! Discover key ML patterns, anti-patterns, data strategies, and more.

Related

  • How Milvus Implements Dynamic Data Update and Query
  • LLMops: The Future of AI Model Management
  • Transforming Customer Feedback With Automation of Summaries and Labels Using TAG and RAG
  • Vector Tutorial: Conducting Similarity Search in Enterprise Data

Trending

  • Breaking Bottlenecks: Applying the Theory of Constraints to Software Development
  • Stateless vs Stateful Stream Processing With Kafka Streams and Apache Flink
  • Doris: Unifying SQL Dialects for a Seamless Data Query Ecosystem
  • Revolutionizing Financial Monitoring: Building a Team Dashboard With OpenObserve
  1. DZone
  2. Data Engineering
  3. Data
  4. Ring Buffer: A Data Structure Behind Disruptor

Ring Buffer: A Data Structure Behind Disruptor

In this article, we look at Disruptor, a library for passing messages between threads, and look at how it's data structure enables high performance.

By 
Grzegorz Mirek user avatar
Grzegorz Mirek
·
Dec. 21, 17 · Analysis
Likes (6)
Comment
Save
Tweet
Share
23.2K Views

Join the DZone community and get the full member experience.

Join For Free

Disruptor is a high-performance library for passing messages between threads, developed and open sourced some years ago by LMAX Exchange company. They created this piece of software to handle an enormous traffic (more than 6 million TPS) in their retail financial trading platform. In 2010, they surprised everyone with how fast their system can be by doing all the business logic on a single thread. Even though a single thread was an important concept in their solution, Disruptor (which is not part of the business logic) works in a multithreaded environment. Disruptor is based on ring buffer, which is definitely not a new concept. 

Ring Buffer

Ring buffer has many names. You might have heard of a circular buffer, circular queue, or cyclic buffer. All of them mean the same thing. It is basically a linear data structure in which the end points to the beginning of the structure. It’s easy to reason about it as a circular array without the end.

Image title

As you can imagine, a ring buffer is mostly used as a queue. It has read and write positions which are used by the consumer and the producer, respectively. When the read or write index reaches the end of the underlying array, it is set back to 0. This activity is usually called “wrapping around,” and it requires a bit more explanation.

Wrapping Around

Consider the following situation: we have the write index at the end of the array and the read index at the beginning. Is it safe to wrap around?

Image title

Well, it’s easy to imagine a streaming example where stale data is not needed anymore because the fresher and more relevant data keeps coming, but usually, we do care about not yet processed data. If that’s the case, either returning a false boolean or blocking, as traditional bounded queues do, would work. If none of these solutions satisfies us, we can implement a ring buffer which can resize itself (but only when it gets full, not just when a producer reaches the end of the array and it can safely wrap around). Resizing would require moving all the elements to a newly allocated bigger array (if an array is used as an underlying data structure) which is an expensive operation, of course. 

Ring Buffer in Disruptor

What kind of problem does ring buffer solve in Disruptor? Let’s look at the typical use case for Disruptor:

Image title

As you can see, we have a single message being sent to the input queues of multiple consumers (1-4) - so it’s a typical multicast (sort of publish and subscribe semantics). Then we have a barrier - we want all consumers to finish processing the message before we move to the next step. When the barrier is passed, the message goes to the input queue of the last consumer. To sum up, we have four independent (and thus potentially parallel) tasks (Consumers 1-4) operating on the same data and one task (Dependant Consumer) which requires all the previous tasks to be finished before it starts working.

And where is the ring buffer in this architecture? Well, a ring buffer is actually this architecture.

Image title

Let’s imagine that a message is a single item in our ring buffer. Ring buffer represents our actual queue (or multiple downstream queues if you prefer). Each consumer is a separate thread traversing ring buffer round and round (or consuming messages from the queue if you prefer).

The barrier is implemented in a way that dependant consumer cannot go past any of the consumers which are required to be finished before it starts processing a ring buffer item (a message). 

Single Writer Principle

Even though the most performant way of using Disruptor is to have a single producer and multiple consumers, a multi-producers scenario is also possible. In that case, there might be a write contention on the same cursor. Disruptor doesn't use traditional locks to solve this problem - so it’s lock-free (with the exception of BlockingWaitStrategy). Instead, it relies on memory barriers and/or high-performance CAS operations.

What if the dependant consumer requires some data produced by any of the previous consumers? Can a consumer also modify the item in the ring buffer and thus be a writer? It turns out that a very simple rule is used here - each item in a ring buffer consists of a set of fields and each field has, at most, one consumer which is allowed to write to it.  This prevents any write-contention between consumers.

Summary

There are many other things which makes Disruptor fast, for example:

  • Consuming messages in a batching mode.
  • CPU-cache-friendly benefits using data locality in a ring buffer.
  • Preallocation of the messages in ring buffer to avoid frequent garbage collection of the items (so they are reused).

As I explained here, even though ring buffer is a relatively simple data structure, it can be easily used to implement way more complex scenarios and Disruptor is just an example.

Buffer (application) Data structure Data (computing)

Published at DZone with permission of Grzegorz Mirek, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

  • How Milvus Implements Dynamic Data Update and Query
  • LLMops: The Future of AI Model Management
  • Transforming Customer Feedback With Automation of Summaries and Labels Using TAG and RAG
  • Vector Tutorial: Conducting Similarity Search in Enterprise Data

Partner Resources

×

Comments
Oops! Something Went Wrong

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends:

Likes
There are no likes...yet! 👀
Be the first to like this post!
It looks like you're not logged in.
Sign in to see who liked this post!